数据结构(本)课程辅导练习

1、数据结构（本）课程辅导与练习-第5章第5章数组和广义表数组和广义表都是特殊的线性表，也是较常用的数据结构类型。一、相关术语数组、二维数组、特殊矩阵、对称矩阵、对角矩阵、稀疏矩阵、广义表、原子、子表、 表头、表尾二、数组1. 数组（向量）一一常用数据类型一维数组（向量）是存储于计算机的连续存储空间中的多个具有统一类型的数据元 素。同一数组的不同元素通过不同的下标标识。（ai,a 2,a n）2. 二维数组二维数组Amn可视为由m个行向量组成的向量，或由n个列向量组成的向量。cl|ainaaiw a «* » » * * »ain >3n|Urclni

2、nd二维数组中的每个元素aij既属于第i行的行向量，又属于第j列的列向量。3. 多维数组三维数组Amnp可视为以二维数组为数据元素的向量。四维数组可视为以三维数组为数据元素的向量三维数组中的每个元素ajk都属于三个向量。四维数组中的每个元素都属于四个向量4. 数组的顺序存储方式 由于计算机内存是一维的，多维数组的元素应排成线性序列后存人存储器。数组一般不做插入和删除操作，即结构中元素个数和元素间关系不变化。一般采用顺序存储方法表示数组。（1）行优先顺序将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。【例】二维数组 Amn的按行优先存储的线性序列为:a 11 ,a 12,a in

3、,a 21 ,a 22,a 2n,ami,a m2,，amnPASCALS C语言中，数组按行优先顺序存储。(2) 列优先顺序 将数组元素按列向量排列，第 i+1 个列向量紧接在第 i 个列向量后面。【例】二维数组 Amn的按列优先存储的线性序列为：a1n,a 2n, ， amna n,a 21,，a m1,a 12,a 22,a m2,注意：FORTRA语言中，数组按列优先顺序存储。5. 数组元素的地址计算公式(1)一维数组元素地址的计算在C语言中，数组的下标从0开始，若知道元素a0的存储地址是LOC(A0), 每个数组元素占 R个存储单元，由于元素 ai是数组元素的第i+1个元素，它之前有

4、i个 元素，而每个元素占 R个存储单元，因此可求得数组元素 aj的存储地址为：在它前面有 i 行个元素，共占用 i*n*R 个存储单元。在第 i+1 行上， aij 元素，因此共占用了LOC或写成 若数组下标从中 aij 的前面有 j-1LOC或写成j*R 个存储单元，所以可求得元素(aij) = LOC (a00LOC ( aij ) = LOC(a00+ (i*n+j )1 开始，数组元素 aij 的前面有 i-1前面共有 j 个aij 的地址 LOC(Aij)为：) +(i*n+j ) * R*R)行，每一行的元素个数为 n, 在第 i 行数据元素，则二维数组的地址计算公式为：(aij)

5、 = LOC (a00) +(i-1 ) *n+j-1)* RLOC (aij ) = LOC(a11+(i-1 ) *n+j-1)* RLOC或写成( ai ) = LOC(a0+i*R) LOC( ai) = LOC(a0+i*R)若数组的下标从 1 开始，则一维数组的地址计算公式为：LOC或写成( ai ) = LOC(a0+( i-1 ) *R)LOC( ai) = LOC(a0+( i-1 ) *R)(2) 二维数组元素地址的计算对于一个二维数组 amn ，知道第一数组元素的存储地址是 LOC( a00) (数组下标从0开始),每个数组元素占R个存储单元，元素aij位于数组中第i+1

6、行，第j+1列,三、特殊矩阵所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。常见的有对称矩阵、 三角矩阵和对角矩阵等。1对称矩阵 ( 1 )对称矩阵 在一个 n 阶方阵 A 中，若元素满足下述性质：aij=aji 0 E,j w1则称 A 为对称矩阵。【例】下图便是一个 5 阶对称矩阵。15137508001892630251_70613_个5阶的对称矩阵(2)对称矩阵的压缩存储对称矩阵中的元素关于主对角线对称， 故只要存储矩阵中上三角或下三角中的元素, 让每两个对称的元素共享一个存储空间。这样，能节约近一半的存储空间。 按"行优先顺序”存储主对角线(包括对角线)以下的元素H

7、u |即按 aoo,aio,aii,an-1,0 ,a n-1,1 ，an-y 次序存放在一个向量sa0 . n(n+1) /2-1中(下三角矩阵中，元素总数为n(n +1) /2)。其中：sa0= a 0o ,sa1 = a io , san(n+1) / 2-1= a n-i,n-i 元素aij的存放位置a ij元素前有i行，一共有：i x (i+1) / 2个元素；在第i行上，aij之前恰有j个元素(即aio, a* ,)，因此有:sai x (i+1) / 2+j= a j aj和sak之间的对应关系：+ j当i G时,aij在下三角矩阵中k 二二 2山 卫 i当i ： j时a,在上三

8、角矩阵中2注意：若数组下标从1开始，则a。和sak之间的对应关系为：业辺十j当i z j时在下三角矩阵中2k =弋也卫+i当i C时aij在上三角矩阵中 2 j2.三角矩阵（1）三角矩阵的划分以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。 上三角矩阵如下图所示，它的下三角（不包括主角线）中的元素均为常数 c。 下三角矩阵与上三角矩阵相反，它的主对角线上方均为常数c,如下图（b）所示。注意:在多数情况下，三角矩阵的常数 c为零。aooc,cawciui *<10, n-lCdLlai, n-l（H）上角如阵（h）卜角刘閘clLOhl i.c丄ff用胡（2）三角矩阵的压缩存储三角矩阵

9、中的重复元素c可共享一个存储空间，其余的元素正好有nx（n+1） / 2个，因此，三角矩阵可压缩存储到向量sa0 . n（n+1） /2中，其中c存放在向量的最后一个分量中。下三角矩阵中aj和sak之间的对应关系9 j当i_j时2i当j时2四、稀疏矩阵设矩阵Am n中有s个非零元素，若s远远小于矩阵元素的总数（即s<<mx n），则称A为 稀疏矩阵。1稀疏矩阵的压缩存储为了节省存储单元，可只存储非零元素。由于非零元素的分布一般是没有规律的，因此 在存储非零元素的同时，还必须存储非零元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。稀疏矩阵的压缩存储会失去随机存取功

10、能。其中每一个非零元素所在的行号、列号和值组成一个三元组（i, j, aij），并由此三元组惟一确定。稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。2.三兀组表将表示稀疏矩阵的非零元素的三元组按行优先（或列优先）的顺序排列（跳过零元素），并依次存放在向量中，这种稀疏矩阵的顺序存储结构称为三元组表。以下的讨论中，均假定三元组是按行优先顺序排列的。【例】下图（a）所示的稀疏矩阵A的三元组表表示见图（b）000220015'011000170000-60000000039091000000<0028000°ijv00322106152111131517423-653

11、5396409175228矩阵M及其三元组顺序表下面讨论压缩存储结构上矩阵的转置运算一个mKn的矩阵A,它的转置矩阵 B是一个nXm的矩阵，且：Aij=Bji, Ow i<m, Owj<n ,即A的行是B的列，A的列是B的行。 三元组表表示的矩阵转置的思想方法第一步：根据 A矩阵的行数、列数和非零元总数确定B矩阵的列数、行数和非零元总数。第二步：当三元组表非空（A矩阵的非零元不为 0）时，根据A矩阵三元组表的结点空 间data （以下简称为三元组表），将A的三元组表a->data置换为B的三元组表b->data。 三元组表的转置方法一：简单地交换a->data中i

12、和j中的内容，得到按列优先顺序存储倒b->data;再将b->data重排成按行优先顺序的三元组表。方法二：由于A的列是B的行，因此，按 a->data的列序转置，所得到的转置矩阵B的三元组表b->data必定是按行优先存放的。按这种方法设计的算法，其基本思想是：对A中的每一列col（0 w col <a ->n-1），通过从头至尾扫描三元组表a->data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放人 b->data中，即可得到B的按行优先的压缩存贮表示。五、广义表广义表（Lists，又称列表）是线性表的推广。即广义表中

13、放松对表元素的原子限制，容许 它们具有其自身结构。1.广义表定义广义表是n（n >个元素a1, a?,，a“，an的有限序列。其中： ai-或者是原子或者是一个广义表。 广义表通常记作：Ls=( ai, a?,，a,，為)。 Ls是广义表的名字，n为它的长度。 若 ai 是广义表,则称它为 Ls 的 子表 。 广义表通常用圆括号括起来，用逗号分隔其中的元素。 为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。 若广义表Ls非空(n >1)则a是LS的表头，其余元素组成的表(a?,出，a“称为Ls 的表尾。 广义表是递归定义的2广义表表示(1 )广义表常用表示 E

14、=()E 是一个空表,其长度为0。 L=(a , b)L 是长度为 ? 的广义表,它的两个元素都是原子,因此它是一个线性表 A=(x, L)=(x , (a, b)A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L。 B=(A , y)=(x , (a, b), y)B是长度为2的广义表，第一个元素是子表A，第二个元素是原子y。 C=(A, B)=(x , (a, b), (x, (a, b), y)C 的长度为 2,两个元素都是子表。 D=(a, D)=(a, (a, (a, ()D 的长度为 2,第一个元素是原子,第二个元素是 D 自身,展开后它是一个无限的广 义表。(2) 广义

15、表的深度一个表的 "深度"是指表展开后所含括号的层数。【例】表L、A B C的深度为分别为1、2、3、4，表D的深度为(3) 带名字的广义表表示 如果规定任何表都是有名字的,为了既表明每个表的名字,又说明它的组成,则可以在每个表的前面冠以该表的名字,于是上例中的各表又可以写成： E() L(a , b) A(x, L(a , b) B(A(x, L(a , b) , y) C(A(x, l(a , b) , B(A(x , L(a , b) , y) D(a , D(a , D()3广义表运算由于广义表是对线性表和树的推广 并且具有共享和递归特性的广义表可以和有向图(见第

16、7 章)建立对应 因此广义表的大部分运算与这些数据结构上的运算类似。在此 只讨论广义表的两个特殊的基本运算：取表头 head(Ls) 和取表尾 tail(Ls) 。 根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素 它可以是原子，也可以是子表，而其表尾必定是子表。【例】head(L)=a ， tail(L)=(b) head(B)=A ， tail(B)=(y) 由于 tail(L) 是非空表，可继续分解得到： head(tail(L)=b ， tail(tail(L)=() 对非空表A和(y)，也可继续分解。六、练习题单项选择题1. 一维数组A采用顺序存储结构，每个元素占用100，则该数组的首地址是()。A 64B28C 70D906 个字节，第 6 个元素的存储地址为2稀疏矩阵采用压缩存储的目的主要是()。A.表达变得简单BC 去掉矩阵中的多余元素D.对矩阵元素的存取变得简单.减少不必要的存储空间的开销3. 一个非空广义表的表头()。A .不可能是原子BC .只能是原子D4. 常对数组进行的两种基本操作是(A.建立与删除BC.查找和修改D.只能是子表 .可以是子表或原子)。.索引与、和修改.查找与索引5. 设二维数组 A56 按行优先顺序存储在内存中，已知A00 起始地址为 1000，每个数组元素占用 5 个存储单