数据结构讲义第5章-数组和广义表

第五章数组和广义表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.3.1特殊矩阵5.3.2稀疏矩阵5.4广义表的定义5.5广义表的存储结构前4章介绍的数据结构共同特点：（1）都属于线性数据结构；（2）每种数据结构中的数据元素，都作为原子数据，不再进行分解；本章讨论的两种数据结构：数组和广义表，其共同特点是：1）从逻辑结构上看它们，可看成是线性结构的一种扩展；2）数据元素本身也是一个数据结构；5.1数组的定义和运算1、n维数组：n维数组是由∏bi个元素组成，每个元素受着n个关系的约束。在每个关系中，元素aj1j2…jn（0≤ji≤bi-2）都有一个后继。故这n个关系是线性关系。数组中的所有元素必须属于同一数据类型。每个元素都对应一组下标（j1，j2，…jn），每个下标的范围0≤ji≤bi-1，bi称为第i维的长度。∏bi为n维数组的长度。当n=1时，n维数组退化为定长的线性表。一、数组的概念以二维数组为例：二维数组中的每个元素都受两个线性关系的约束即行关系和列关系，在每个关系中，每个元素aij都有且仅有一个直接前趋，都有且仅有一个直接后继。Amn=a00a01a0n-1a10a11a1n-1am-10am-11am-1n-1在行关系中aij直接前趋是aij-1aij直接后继是aij+1在列关系中aij直接前趋是ai-1jaij直接后继是ai+1jAm×n=a11a12┅a1j┅a1na21a22┅a2j┅a2n┇┇ai1ai2┅aij┅ain┇┇am1am2┅amj┅amnA=（12┅j┅n)我们可以把二维数组看成一个线性表：A=(12…j…n)，其中j（1≤j≤n）本身也是一个线性表，称为列向量。矩阵Am×n看成n个列向量的线性表,即j=(a1j,a2j,…,amj)Am×n=a11a12…a1j…a1na21a22…a2j…a2n┇┇ai1ai2…aij…ain┇┇am1am2…amj…amnB‖12┇i┇m我们还可以将数组Am×n看成另外一个线性表:B=(1，,2,，…，m)，其中i（1≤i≤m）本身也是一个线性表，称为行向量，即：I=（ai1，ai2，…，aij，…，ain）。二、数组的基本操作1读元素操作2写元素操作操作方法根据其存储结构决定5.2数组的顺序表示和实现数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就有次序约定的问题。通常有两种顺序存储方式：⑴行优先顺序——将数组元素按行排列，第i+1个行向量紧接在第i个行向量后面在PASCAL、C语言中，数组就是按行优先顺序存储的。⑵列优先顺序——将数组元素按列向量排列，第j+1个列向量紧接在第j个列向量之后在FORTRAN语言中，数组就是按列优先顺序存储的。对于二维数组:以行为主序的方式：以列为主序的方式：01m-1mm+12m-1nm-1a00a10am-10a01a11am-11a0n-1a1n-1am-1n-1Amn=a00a01a0n-1a10a11a1n-1am-10am-11am-1n-101n-1nn+12n-1mn-1a00a01a0n-1a10a11a1n-1am-10am-1n-1以行为主序：LOC(aij)=LOC(a00)+(i*n+j)*l以列为主序：LOC(aij)=LOC(a00)+(j*m+n)*l一般地，对A[c1..d1,c2..d2]则：以行为主序有：LOC(aij)=LOC(ac1c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*l以列为主序：LOC(aij)=LOC(ac1c2)+[(j-c2)*(d1-c1+1)+(i-c1)]*l推广到n维数组Ab1b2..bnLOC(aj1j2..jn)=LOC(a00..0)+(j1*b2*b3*…*bn+j2*b3*b4*…*bn+…+jn-1*bn+jn)*l以列为主序：LOC(aj1j2..jn)=LOC(a00..0)+(jn*bn-1*bn-2*…*b1+jn-1*bn-2*bn-3*…*b1+…+j2*b1+j1)*l一般地，对A[c1..d1,c2..d2,…,cn..dn]则：以行为主序有：LOC(aj1j2..jn)=LOC(ac1c2..cn)+[(j1-c1)*(d2-c2+1)*(d3-c3+1)*…*(dn-cn+1)+(j2-c2)*(d3-c3+1)*(d4-c4+1)*…*(dn-cn+1)+…+(jn-1-cn-1)*(dn-cn+1)+jn-cn]*l以列为主序：LOC(aj1j2..jn)=LOC(ac1c2..cn)+[(jn-cn)*(dn-1-cn-1+1)*(dn-2-cn-2+1)*…*(d1-c1+1)+(jn-2-cn-2)*(dn-3-cn-3+1)*(dn-4-cn-4+1)*…*(d1-c1+1)+…+(j2-c2)*(d1-c1+1)+j1-c1]*l例1:设二维数组A68按“行优先顺序”存储在内存中，每个元素占用6个存储单元，已知A的起始地址为1000，计算a14的地址。。解：LOC(a14)=LOC(a00)+[i*n+j]*l=1000+[1*8+4]*6=1072例2:设二维数组A[0..8,1..10],每元素占6字节，已知A的起始地址为1000，求：(1)存储A共需多少字节？(2)以行序为主序存储，求a85的地址。(3)A的第8列第5行共占多少字节？解:(1)共需((d2-c2+1)*(d1-c1+1))*l=10*9*6=540字节(2)LOC(a85)=LOC(ac1c2)+[(j1-c1)*(d2-c2+1)+(j2-c2)]*l=1000+[8*10+4]*6=1504(3)第8列共有9个元素，第5行有10个元素，第8列第5行共有9+10-1个元素，共占18*6个字节。一、数组的顺序存储表示#includestdarg.h#defineMAX_ARRAY_DIM8typedefstruct{ElemType*base;intdim;int*bounds;int*constants;}Array;二、数组操作的实现对于一个矩阵结构，显然用一个二维数组来表示是非常恰当的。但有时会遇到这样一类矩阵：在这种矩阵中有许多值相同的元素或者是零元素、为了节省存储空间，可以对这类矩阵进行压缩存储。压缩存储是：为多个值相同的元素只分配一个存储空间：对零元素不分配存储空间。特殊矩阵：值相同的元素或者零元素在矩阵中的分布有一定规律，则称此类矩阵为特殊矩阵，反之，称为稀疏矩阵。5.3矩阵的压缩存储5.3.1特殊矩阵的压缩存储1、对称矩阵（1）在一个n阶方阵A中，若元素满足下述性质：aij=aji0≦i,j≦n-1则称A为对称矩阵。（2）压缩存储方法：由于对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，则可将n2个元素存储到n(n-1)/2个元素空间中。不失一般性，以行序为主序存储其下三角的元素。例：5阶对称方阵及它的压缩存储３６４７８６２８４２４８１６９７４６０５８２９５７A=３６２４８１７４６０８２９５７一般地，设对称矩阵A的下三角部分以行为主序顺序存储到一个向量SA[n(n+1)/2]中，如图所示。a11a21a22a31a32a33…an1an2…an第3行第2行第n行第1行图一般对称矩阵的压缩存储012345n(n+1)/2-1则sa[k]和aij之间的下标对应关系为：k=i(i-1)/2+j-1当i=jj(j-1)/2+i-1当ij2、三角矩阵形下图的矩阵称为三角矩阵，其中c为某个常数。其中(a)为上三角矩阵：主对角线以下均为同一个常数；(b)为下三角矩阵，主对角线以上为同一个常数；在大多数情况下，三角矩阵常数为零。a11a12…a1na11c…cca22…a2na21a22…c…………………..……………..cc…annan1an2…ann(a)上三角矩阵(b)下三角矩阵下三角矩阵与对称矩阵类似，设存入向量：SA[n*(n+1)+1]中，sa[k]与aij的对应关系为：k=i(i-1)/2+j-1当i=jn(n+1)/2当ija11a21a22a31a32a33…an1an2…anc第3行第2行第n行第1行012345n(n+1)/2上三角矩阵设存入向量：SA[n*(n+1)+1]中，sa[k]与aij的对应关系为：k=(i-1)(2n-i+2)/2+j-i当i=jn(n+1)/2当ija11a12…a1na22a23…a2n…annc第2行第n行第1行012345n(n+1)/25.4.1广义表的概念1什么是广义表广义表也称为列表，是线性表的一种扩展，也是数据元素的有限序列。记作：LS=(a1,a2,......an)。其中ai既可以是单个元素，也可以是广义表。说明1）广义表的定义是一个递归定义，因为在描述广义表时又用到了广义表；2）在线性表中数据元素是单个元素，而在广义表中，元素可以是单个元素,称为单元素(原子)，也可以是广义表，称为广义表的子表；3）n是广义表长度；5．4广义表5．4广义表4）下面是一些广义表的例子；A=()空表，表长为0；B=(a,(b,c,d))B的表长为2，两个元素分别为a和子表（b,c,d)；C=(e)C中只有一个元素e，表长为1；D=(A,B,C,f)D的表长为4，它的前三个元素A，B，C广义表,第四个是单元素；E=(a,E)递归表.5．4广义表5）若广义表不空，则可分成表头和表尾，反之，一对表头和表尾可唯一确定广义表对非空广义表：称第一个元素为L的表头，其余元素组成的表称为LS的表尾；B=(a,(b,c,d))表头：a表尾((b,c,d))即HEAD（B）=a,TAIL(B)=((b,c,d)),C=(e)表头：e表尾()D=(A,B,C,f)表头：A表尾(B,C,f)运算可以嵌套，如：HEAD（TAIL（B））=b,TAIL(TAIL(B))=(c,d)。5．4广义表广义表的元素之间除了存在次序关系外，还存在层次关系。如：DABCfaDebcd2广义表的基本操作1）创建广义表L；2）销毁广义表L；3）已有广义表L，由L复制得到广义表T；4）求广义表L的长度；5）求广义表L的深度；6）判广义表L是否为空；7）取广义表L的表头；8）取广义表L的表尾；9）在L中插入元素作为L的第i个元素；10）删除广义表L的第i个元素；11）遍历广义表L，用函数traverse()处理每个元素；5．4广义表5.4.2广义表的存储结构由于广义表中数据元素可以具有不同结构，故难以用顺序结构表示广义表。通常采用链表存储方式一头尾表示法二孩子兄弟链表法5．4广义表taghptp表结点10tagatomtptaghptp表结点10tagatom原子结点原子结点习题五5.1假设按行优先存储整数数组A[9][3][5][8]时，第一个元素的字节地址时１００，每个整数占４个字节。问下列元素的存储地址是什么。(1)a0000(2)a1111(3)a31255.2数组A中，每个元素A的存储占3个单元，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元个数是（(1)），若该数组按行存放时，元素A[8][5]的起始地址是((2)），若该数组按列存放时，元素A[8][5]的起始地址是（(3)）。(1)A.80B.100C.240D.270(2)A.SA+141B.SA+144C.SA+222D.SA+225(3)A.SA+117B.SA+180C.SA+222D.SA+2255.3求下列广义表的操作结果GetHead[((a),a)]GetTail[((a),a)]GetTail[GetHead[((a,b),(c,d))]]GetHead[GetHead[((a,b),(c,d