数据结构(本)课程辅导与练习-第5章

1数据结构(本)课程辅导与练习-第5章第5章数组和广义表数组和广义表都是特殊的线性表，也是较常用的数据结构类型。一、相关术语数组、二维数组、特殊矩阵、对称矩阵、对角矩阵、稀疏矩阵、广义表、原子、子表、表头、表尾二、数组1.数组（向量）——常用数据类型一维数组（向量）是存储于计算机的连续存储空间中的多个具有统一类型的数据元素。同一数组的不同元素通过不同的下标标识。（a1,a2,…,an)2.二维数组二维数组Amn可视为由m个行向量组成的向量，或由n个列向量组成的向量。二维数组中的每个元素aij既属于第i行的行向量，又属于第j列的列向量。3.多维数组三维数组Amnp可视为以二维数组为数据元素的向量。四维数组可视为以三维数组为数据元素的向量……三维数组中的每个元素aijk都属于三个向量。四维数组中的每个元素都属于四个向量……4.数组的顺序存储方式由于计算机内存是一维的，多维数组的元素应排成线性序列后存人存储器。数组一般不做插入和删除操作，即结构中元素个数和元素间关系不变化。一般采用顺序存储方法表示数组。（1）行优先顺序将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。2【例】二维数组Amn的按行优先存储的线性序列为：a11,a12,…,a1n,a21,a22,…,a2n,……，am1,am2,…，amn注意：PASCAL和C语言中，数组按行优先顺序存储。（2）列优先顺序将数组元素按列向量排列，第i+1个列向量紧接在第i个列向量后面。【例】二维数组Amn的按列优先存储的线性序列为：a11,a21,…,am1,a12,a22,…,am2,……，a1n,a2n,…，amn注意：FORTRAN语言中，数组按列优先顺序存储。5.数组元素的地址计算公式（1）一维数组元素地址的计算在C语言中，数组的下标从0开始，若知道元素a[0]的存储地址是LOC（A[0]），每个数组元素占R个存储单元，由于元素a[i]是数组元素的第i+1个元素，它之前有i个元素，而每个元素占R个存储单元，因此可求得数组元素a[j]的存储地址为：LOC（a[i]）=LOC(a[0]+i*R)或写成LOC（ai）=LOC(a0+i*R)若数组的下标从1开始，则一维数组的地址计算公式为：LOC（a[i]）=LOC(a[0]+（i-1）*R)或写成LOC（ai）=LOC(a0+（i-1）*R)(2)二维数组元素地址的计算对于一个二维数组a[m][n]，知道第一数组元素的存储地址是LOC（a[0][0]）(数组下标从0开始),每个数组元素占R个存储单元，元素a[i][j]位于数组中第i+1行，第j+1列，在它前面有i行个元素，共占用i*n*R个存储单元。在第i+1行上，a[i][j]前面共有j个元素，因此共占用了j*R个存储单元，所以可求得元素a[i][j]的地址LOC（A[i][j]）为：LOC（a[i][j]）=LOC（a[0][0]）+（i*n+j）*R或写成LOC（aij）=LOC(a00+（i*n+j）*R)若数组下标从1开始，数组元素aij的前面有i-1行，每一行的元素个数为n,在第i行中aij的前面有j-1数据元素，则二维数组的地址计算公式为：LOC（a[i][j]）=LOC（a[0][0]）+(（i-1）*n+j-1)*R或写成LOC（aij）=LOC(a11+(（i-1）*n+j-1)*R三、特殊矩阵所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。常见的有对称矩阵、三角矩阵和对角矩阵等。1．对称矩阵（1）对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji0≤i,j≤n-1则称A为对称矩阵。【例】下图便是一个5阶对称矩阵。3（2）对称矩阵的压缩存储对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。这样，能节约近一半的存储空间。①按行优先顺序存储主对角线(包括对角线)以下的元素即按a00,a10,a11,……，an-1,0,an-1,1…，an-1,n-1次序存放在一个向量sa[0．．n(n+1)／2-1]中（下三角矩阵中，元素总数为n(n+1)／2）。其中：sa[0]=a00,sa[1]=a10,……，sa[n(n+1)／2-1]=an-1,n-1②元素aij的存放位置aij元素前有i行，一共有：i×(i+1)／2个元素；在第i行上，aij之前恰有j个元素(即ai0，ail，…，ai,j-1)，因此有：sa[i×(i+1)／2+j]=aij③aij和sa[k]之间的对应关系：在上三角矩阵中时当在下三角矩阵中时当ijijajiijjajijiik2)1(,2)1(注意：若数组下标从1开始，则aij和sa[k]之间的对应关系为：4在上三角矩阵中时当在下三角矩阵中时当ijijajiijjajijiik2)1(,2)1(2.三角矩阵（1）三角矩阵的划分以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。①上三角矩阵如下图(a)所示，它的下三角(不包括主角线)中的元素均为常数c。②下三角矩阵与上三角矩阵相反，它的主对角线上方均为常数c，如下图(b)所示。注意：在多数情况下，三角矩阵的常数c为零。（2）三角矩阵的压缩存储三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n×(n+1)／2个，因此，三角矩阵可压缩存储到向量sa[0．．n(n+1)／2]中，其中c存放在向量的最后一个分量中。下三角矩阵中aij和sa[k]之间的对应关系时当时当jiinnjijiik2)1(2)1(四、稀疏矩阵设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数(即sm×n)，则称A为稀疏矩阵。1．稀疏矩阵的压缩存储为了节省存储单元，可只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。稀疏矩阵的压缩存储会失去随机存取功能。其中每一个非零元素所在的行号、列号和值组成一个三元组(i，j，aij)，并由此三元组惟一确定。稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。2．三元组表5将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)，并依次存放在向量中，这种稀疏矩阵的顺序存储结构称为三元组表。注意：以下的讨论中，均假定三元组是按行优先顺序排列的。【例】下图(a)所示的稀疏矩阵A的三元组表表示见图(b)矩阵M及其三元组顺序表下面讨论压缩存储结构上矩阵的转置运算一个m×n的矩阵A，它的转置矩阵B是一个n×m的矩阵，且：A[i][j]=B[j][i]，0≤im，0≤jn，即A的行是B的列，A的列是B的行。①三元组表表示的矩阵转置的思想方法第一步：根据A矩阵的行数、列数和非零元总数确定B矩阵的列数、行数和非零元总数。第二步：当三元组表非空（A矩阵的非零元不为0）时，根据A矩阵三元组表的结点空间data（以下简称为三元组表），将A的三元组表a-data置换为B的三元组表b-data。②三元组表的转置方法一:简单地交换a-data中i和j中的内容，得到按列优先顺序存储倒b-data;再将b-data重排成按行优先顺序的三元组表。方法二:由于A的列是B的行，因此，按a-data的列序转置，所得到的转置矩阵B的三元组表b-data必定是按行优先存放的。按这种方法设计的算法，其基本思想是：对A中的每一列col(0≤col≤a-n-1)，通过从头至尾扫描三元组表a-data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放人b-data中，即可得到B的按行优先的压缩存贮表示。五、广义表广义表(Lists，又称列表)是线性表的推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。1．广义表定义广义表是n(n≥0)个元素a1，a2，…，ai，…，an的有限序列。其中：①ai--或者是原子或者是一个广义表。ijv[0]0322[1]0615[2]1111[3]1517[4]23-6[5]3539[6]4091[7]522800002800000000910390000000060000170001101500220006②广义表通常记作：Ls=(a1，a2，…，ai，…，an)。③Ls是广义表的名字，n为它的长度。④若ai是广义表，则称它为Ls的子表。注意：①广义表通常用圆括号括起来，用逗号分隔其中的元素。②为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。③若广义表Ls非空(n≥1)，则al是LS的表头，其余元素组成的表(a2，a3，…，an)称为Ls的表尾。④广义表是递归定义的2．广义表表示（1）广义表常用表示①E=()E是一个空表，其长度为0。②L=(a，b)L是长度为2的广义表，它的两个元素都是原子，因此它是一个线性表③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）广义表的深度一个表的深度是指表展开后所含括号的层数。【例】表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．广义表运算由于广义表是对线性表和树的推广，并且具有共享和递归特性的广义表可以和有向图(见第7章)建立对应，因此广义表的大部分运算与这些数据结构上的运算类似。在此，只讨论广义表的两个特殊的基本运算：取表头head(Ls)和取表尾tail(Ls)。根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可7以是原子，也可以是子表，而其表尾必定是子表。【例】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采用顺序存储结构，每个元素占用6个字节，第6个元素的存储地址为100，则该数组的首地址是（）。A．64B．28C．70D．902．稀疏矩阵采用压缩存储的目的主要是（）。A．表达变得简单B．对矩阵元素的存取变得简单C．去掉矩阵中的多余元素D．减少不必要的存储空间的开销3．一个非空广义表的表头（）。A．不可能是原子B．只能是子表C．只能是原子D．可以是子表或原子4．常对数组进行的两种基本操作是（）。A．建立与删除B．索引与、和修改C．查找和修改D．查找与索引5.设二维数组A[5][6]按行优先顺序存储在内存中，已知A[0][0]起始地址为1000，每个数组元素占用5个存储单元，则元素A[4][4]的地址为（）。A．1140B．1145C．1120D．11256．设有一个20阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a9,2在一维数组B中的下标是（）。A．41B．32C．18D．387．一个非空广义表的表头（）。A．不可能是子表B．只能是子表C．只能是原子D．可以是子表或原子练习题答案单项选择题1