《数据结构》课件第4章(数组和广义表).ppt

1、第四章第四章 数组和广义表数组和广义表 数组的逻辑结构数组的逻辑结构 数组的顺序存储分配数组的顺序存储分配 矩阵的压缩存储矩阵的压缩存储 稀疏矩阵稀疏矩阵 广义表广义表数组的逻辑结构数组的逻辑结构数组可表示为：数组可表示为：A=a11 a12 a1na21 a22 a2n am1 am2 amn 它可以看成是由它可以看成是由m m个行向量或个行向量或n n个列向量组成的线性表。也即，个列向量组成的线性表。也即，二维数组可以看成是一种推广的二维数组可以看成是一种推广的线性表，这种线性表的每一个数线性表，这种线性表的每一个数据元素本身也是一个线性表。据元素本身也是一个线性表。类似地，类似地，一个三

2、维数组可以看成是数据元素为二维数组的线性表一个三维数组可以看成是数据元素为二维数组的线性表一个一个n维数组可视为其数据元素为维数组可视为其数据元素为n-1维数组的线性表。维数组的线性表。一个二维数组的类型定义如下：一个二维数组的类型定义如下：ElemType ;A m n数组的顺序存储分配数组的顺序存储分配1.1.一维数组一维数组Ana1a2a3an-1anLoc(ai)=Loc(a1)+(i-1)kAn=(a1,a2,a3,an )若已知每个元素占若已知每个元素占k 个存储单元，并且知道第个存储单元，并且知道第一个元素的存储地址一个元素的存储地址Loc(a1),则则2.二维数组二维数组Amn

3、 a11 a12 a13 a1n a21 a22 a23 a2n Amn=am1 am2 am3 amn 行序为主序分配方式行序为主序分配方式 列序为主序分配方式列序为主序分配方式a11.a1na21.a2na31.aij.amn第第1行行第第2行行 a11 a12 a13 a1n a21 a22 a23 a2nAmn=am1 am2 am3 amn 1)行序为主序分配方式行序为主序分配方式 a11 a12 a13 a1n a21 a22 a23 a2n a31 a32 a33 a3nAmn=aij am1 am2 am3 amni-1 行行 若已知每个元素占若已知每个元素占k个存储单元，并且

4、知道第一个存储单元，并且知道第一个元素的存储地址个元素的存储地址 LOC(a11),则则 Loc(aij)=Loc(a11)+(i 1)n k+(j 1)k=Loc(a11)+(i 1)n+(j 1)ka11.am1a12.am2a13.aij.amn第第1列列第第2列列 a11 a12 a13 a1n a21 a22 a23 a2nAmn=am1 am2 am3 amn 2)列序为主序分配方式列序为主序分配方式 a11 a12 a13 a1n a21 a22 a23 a2n a31 a32 a33 a3nAmn=aij am1 am2 am3 amnj-1 列列 若已知每个元素占若已知每个元

5、素占k个存储单元，并且知道第一个存储单元，并且知道第一个元素的存储地址个元素的存储地址 LOC(a11),则则 Loc(aij)=Loc(a11)+(j 1)m k+(i 1)k=Loc(a11)+(j 1)m+(i 1)k a11 a12 a13 a1n a21 a22 a23 a2n A =am1 am2 am3 amn Amn 所谓所谓压缩存储压缩存储是指为多个值相同的元素是指为多个值相同的元素,或者或者位置分布有规律的那些元素分配尽可能少的存储空位置分布有规律的那些元素分配尽可能少的存储空间，而对间，而对0元素一般情况下不分配存储空间。元素一般情况下不分配存储空间。传统做法传统做法特殊

6、矩阵的压缩存储特殊矩阵的压缩存储 a11 a12 a13 a1n a21 a22 a23 a2n a31 a32 a33 a3nA1:n,1:n=an1 an2 an3 ann传统做法：传统做法：定义一个二维数组定义一个二维数组 Ann 1 1）对称矩阵的压缩存储）对称矩阵的压缩存储 一个一个n 阶矩阵阶矩阵A的元素满足性质的元素满足性质 aij=aji 1i,jn则称则称矩阵矩阵A为为n 阶对称矩阵。阶对称矩阵。a11a21a22.aij.ann k=1 2 3 k=1 2 3 .n n*(n+1)/2 (n+1)/2 a11 a12 a13 a1n a21 a22 a23 a2n a31

7、a32 a33 a3nAnn=an1 an2 an3 ann A中任意一元素中任意一元素aij与与Vk 之间存在对应关系之间存在对应关系:k=i(i-1)/2+j 当当ij时时j(j-1)/2+i 当当i j时时V传统做法：定义一个二维数组传统做法：定义一个二维数组 Bnn0元素元素0元素元素2 2）对角矩阵的压缩存储）对角矩阵的压缩存储 若一个矩阵中，值非若一个矩阵中，值非0的元素对称地集中在主对的元素对称地集中在主对角线两旁的一个带状区域中角线两旁的一个带状区域中(该区域之外的元素都为该区域之外的元素都为0元素元素)，称这样的矩阵为对角矩阵。，称这样的矩阵为对角矩阵。例例.三对角矩阵的压缩

8、存储三对角矩阵的压缩存储 b11 b12 b21 b22 b23 b32 b33 b34 bn-1n bnn-1 bnn0元素元素0元素元素非零元素的个数为非零元素的个数为3n-23n-2Bnn=b11b12b21 bij .b22.k=1 2 3 4 .3n-2 bnn b11 b12 b21 b22 b23 b32 b33 b34 bn-1n bnn-1 bn n0元素元素0元素元素B中任一非零元素中任一非零元素 bij 与与Vk 之间存在对应关系：之间存在对应关系：k=2 i+j 2 i=k/3+1 j=k-2(i-1)Bnn=传统做法：传统做法：定义一个二维数组定义一个二维数组 A66

9、1）稀疏矩阵的定义）稀疏矩阵的定义 一个较大的矩阵中，零元素的个数相对于整一个较大的矩阵中，零元素的个数相对于整 个矩阵元素的总个数所占比例较大时，可以称该个矩阵元素的总个数所占比例较大时，可以称该 矩阵为一个稀疏矩阵。矩阵为一个稀疏矩阵。A=15 0 0 22 0 -15 0 11 3 0 0 0 0 0 0 -6 0 0 0 0 0 0 0 0 91 0 0 0 0 0 0 0 28 0 0 0稀疏矩阵的压缩存储稀疏矩阵的压缩存储三元组三元组：(i,j,value)例如例如 ：（1,1,15）表示第）表示第1行、第行、第1列、值为列、值为15的元素。的元素。（1,4,22）表示第）表示第1

10、行、第行、第4 4列、值为列、值为22的元素。的元素。（1,6,-15）表示第）表示第1行、第行、第6列、值为列、值为-15的元素。的元素。15 0 0 22 0 -15 0 11 3 0 0 0 0 0 0 -6 0 0 0 0 0 0 0 0 91 0 0 0 0 0 0 0 28 0 0 02）稀疏矩阵的三元组表示）稀疏矩阵的三元组表示(m,n,t)其中，其中，m,n,t 分别表示稀疏矩阵的总的行数、分别表示稀疏矩阵的总的行数、总的列数与非零元素的总个数。总的列数与非零元素的总个数。A=15 0 0 22 0 -15 0 11 3 0 0 0 0 0 0 -6 0 0 0 0 0 0 0

11、 0 91 0 0 0 0 0 0 0 28 0 0 0 A66 6681115142216-15221134-623351916328 B=B93 若一个若一个m n阶稀疏矩阵具有阶稀疏矩阵具有t个非零元素，则用个非零元素，则用t+1个三个三元组来存储元组来存储,其中第一个三元组分别用来给出稀疏矩阵的总其中第一个三元组分别用来给出稀疏矩阵的总行数行数m、总列数、总列数n 以及非零元素的总个数以及非零元素的总个数t；第二个三元组；第二个三元组到第到第 t+1 个三元组按行序为主序的方式依次存储个三元组按行序为主序的方式依次存储t个非零元个非零元素。素。15 0 0 22 0-1515 0 0

12、22 0-15 0 11 3 0 0 0 0 11 3 0 0 0 0 0 0 -6 0 0 0 0 0 -6 0 0 0 0 0 0 0 0 0 0 0 0 0 091 0 0 0 0 091 0 0 0 0 0 0 0 28 0 0 0 0 28 0 0 0 0M=15 0 0 0 91 0 15 0 0 0 91 0 0 11 0 0 0 0 0 11 0 0 0 0 0 3 0 0 0 28 0 3 0 0 0 28 22 0-6 0 0 0 22 0-6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0-15 0 0 0 0 0-15 0 0 0 0 0N=表示稀疏矩阵表示

13、稀疏矩阵M的三列的二维数组的三列的二维数组 1 2 3 1 2 3A0,6 6 8A0,6 6 8A1,1 1 15A1,1 1 15A2,1 4 22A2,1 4 22A3A3，1 6-151 6-15A4,2 2 11A4,2 2 11A5,2 3 3A5,2 3 3A6A6，3 4 -63 4 -6A7,5 1 91A7,5 1 91A8,6 3 28A8,6 3 28 1 2 3 1 2 3B0,6 6 8B0,6 6 8B1,1 1 15B1,1 1 15B2,1 5 91B2,1 5 91B3,2 2 11B3,2 2 11B4,3 2 3B4,3 2 3B5,3 6 28B5,3

14、 6 28B6,4 1 22B6,4 1 22B7,4 3 -6B7,4 3 -6B8,6 4-15B8,6 4-15表示稀疏矩阵表示稀疏矩阵M的三列的二维数组的三列的二维数组A=B=3）矩阵的转置矩阵的转置(1(1)转置过程按照转置过程按照B B数组中元素的最终排列顺序进行数组中元素的最终排列顺序进行 由于矩阵由于矩阵M的列经过转置后变为的列经过转置后变为N的行的行,所以可以按照所以可以按照M的的列序来转置列序来转置.为了按顺序找到为了按顺序找到M中的每一列的所有非中的每一列的所有非0元素元素,对对数组数组A从第一行起将每行的第二列扫描从第一行起将每行的第二列扫描n遍遍,每遍扫描分别找到每遍

15、扫描分别找到矩阵矩阵N的从第一行到第的从第一行到第n行的各行所有非行的各行所有非0元素元素,并产生并产生B数组相数组相应的行。应的行。void transmat(A,B);(m,n,t)=(A01,A02,A03);B01,B02,B03)=(n,m,t);if(t!=0)q=1;for(col=1;col=n;col+)for(p=1;p=t;p+)if(Ap2=col)Bq1=Ap2;Bq2=Ap1;Bq3=Ap3;q=q+1;算法的评价算法的评价1.1.空间开销：空间开销：3 3*(t+1)(t+1)，当，当t1/3t1/3*(m(m*n)n)时，所需存储量比按矩时，所需存储量比按矩 形

16、结构存储的二维数组要少。形结构存储的二维数组要少。2.2.时间开销：时间开销：O(nO(n*t)t)。常规矩阵的转置运算需要的时间为。常规矩阵的转置运算需要的时间为O(nO(n*m),m),若非若非0 0元素的个数元素的个数t t与与m m*n n有相同的数量级时，算法有相同的数量级时，算法tranmat的运的运 算量就达到了算量就达到了O(mO(m*n n2 2)了，这时，虽然节省了一些存储空间，却了，这时，虽然节省了一些存储空间，却 浪费了大量的计算时间。浪费了大量的计算时间。算法的改进之处：对算法的改进之处：对A数组的扫描存在着浪费现象，即数组的扫描存在着浪费现象，即n次扫描次扫描中每次

17、都要检查中每次都要检查t个元素，实际并不需要。因为：每次需要扫描个元素，实际并不需要。因为：每次需要扫描的的A的元素在减少，凡在某遍扫描中已转置到的元素在减少，凡在某遍扫描中已转置到B中去的中去的A的元素的元素以后就不需要再扫描了。以后就不需要再扫描了。(2(2)B)B数组中元素的生成不是顺序的而是跳跃式的数组中元素的生成不是顺序的而是跳跃式的 即转换按数组即转换按数组A A中行的顺序进行，但转换后的元素在中行的顺序进行，但转换后的元素在B B中中不是连续存放，而是将它放入它在不是连续存放，而是将它放入它在B B中最终应占据的位置。中最终应占据的位置。Numn:存放矩阵存放矩阵N中各行非中各行

18、非0元素的个数元素的个数;Potn:存放矩阵存放矩阵N中各行第一个非中各行第一个非0元素在数组元素在数组B中应占的位置中应占的位置.pot1=1potj=potj-1+numj-1 (2jn)(2jn)15 0 0 22 0-1515 0 0 22 0-15 0 11 3 0 0 0 0 11 3 0 0 0 0 0 0 -6 0 0 0 0 0 -6 0 0 0 0 0 0 0 0 0 0 0 0 0 091 0 0 0 0 091 0 0 0 0 0 0 0 28 0 0 0 0 28 0 0 0 0M=j 1 2 3 4 5 6 Numj 2 1 2 2 0 1 Potj 1 3 4 6

19、 8 8void fasttranmat(A,B);(m,n,t)=(A01,A02,A03);(B01,B02,B03)=(n,m,t);if(t!=0)for(i=1;i=n;i+)numi=0;for(i=1;i=t;i+)numAi2=numAi2+1;pot1=1;for(j=2;j=n;j+)potj=potj-1+numj-1;for(i=1;i=t;i+)k=Ai2;Bpotk1=Ai2;Bpotk2=Ai1;Bpotk3=Ai3;potk=potk+1;4)矩阵的相乘矩阵的相乘8 0 0 40 0-2 03-5 0 00 0 0 6S=0 0 7 0-20 0 5 0 04

20、0 0 0 00 0 0-3 0R=R=5 4 61 1 81 4 42 3-23 1 33 2-55 4 6A=B=4 5 51 3 71 5-72 3 53 1 44 4-3 由于两个稀疏矩阵的积并不一定仍是稀疏矩阵，故结果由于两个稀疏矩阵的积并不一定仍是稀疏矩阵，故结果矩阵矩阵c=sc=s*r r仍需采用通常的矩形结构的二维数组存储方式。仍需采用通常的矩形结构的二维数组存储方式。在经典算法中，不管元素是否为在经典算法中，不管元素是否为0都需要相乘，但实际上都需要相乘，但实际上只有只有Si,k和和Rk,j均不为均不为0时，乘积才不为时，乘积才不为0。因此，需在。因此，需在A、B中找出相应的

21、各对元素中找出相应的各对元素(即数组即数组A中第二列的值与数组中第二列的值与数组B中第中第一列的值相等的元素一列的值相等的元素)相乘即可。相乘即可。为了得到非为了得到非0的乘积，对的乘积，对A中每一行的元素中每一行的元素(i,k,Sik)，需要，需要在在B中找到所有相应的元素中找到所有相应的元素(k,j,Rkj),为了便于在为了便于在B中寻找中寻找R中第中第k行的第一个非行的第一个非0元素，和前面类似，需设置两个数组元素，和前面类似，需设置两个数组Numn和和Potn+1，其中，其中numk表示表示R中第中第k行非行非0元素的个数；元素的个数；potk表示表示R中第中第k行第一个非行第一个非0

22、元素在元素在B中的位置。中的位置。pot1=11=1potj=potj-1+numj-1 (2jn)(2jn)void matrix-multiplication(A,B,C);(m,n,t)=(A01,A02,A03);if(n=B01)(p,t2)=(B02,B03)else printf(“Incompatible matrix”);return;if(t1*t2=0)return;/乘积为乘积为0矩阵矩阵 for(i=1;i=m;i+)for(j=1;j=p;j+)Cij=0;for(i=1;i=n;i+)numi=0;for(i=1;i=t2;i+)numBi1=numBi1+1;p

23、ot1=0;for(i=2;i=n+1;i+)poti=poti-1+numi-1;for(i=1;i=t1;i+)k=ai2;for(j=potk;j=potk+1-1;j+)CAi1Bj2=CAi1Bj2+Ai3*Bj3;(4).).修改有关的边结点的修改有关的边结点的adjvex 域的内容。域的内容。为稀疏矩阵的每一行设置一个单独的循环链表，为稀疏矩阵的每一行设置一个单独的循环链表，同样为每一列设置一个单独的循环链表。同样为每一列设置一个单独的循环链表。矩阵中每矩阵中每 一个非零元素同时包含在两个循环链表中，一个非零元素同时包含在两个循环链表中，即包含即包含 在它所在的行链表与所在的列链

24、表中在它所在的行链表与所在的列链表中,即两个链表的即两个链表的 交汇处交汇处。5)稀疏矩阵的稀疏矩阵的十字十字链表表示链表表示 对于一个对于一个m n的稀疏矩阵，分别建立的稀疏矩阵，分别建立m个行个行的循环链表与的循环链表与n个列的循环链表，个列的循环链表，每个非零元素用每个非零元素用一个链结点存储一个链结点存储.其中，其中，row,col,value 分别表示某个非零元素所在的分别表示某个非零元素所在的行号、列号和元素的值；行号、列号和元素的值；down 和和 right 分别为向下与分别为向下与向向右指针，分别用来链接同一列中的与同一行中的所有非右指针，分别用来链接同一列中的与同一行中的所

25、有非零元素对应的链结点。零元素对应的链结点。链结点的构造为链结点的构造为：rowcolvaluedownright一共设置一共设置MAX(m,n)个头结点个头结点.00downright 对对m个行链表，分别设置个行链表，分别设置m个行链表表头结点。个行链表表头结点。表头结点的构造与链表中其他链结点一样，表头结点的构造与链表中其他链结点一样，只是令只是令row与与col 的值分别为的值分别为0，right域指向相应行链表的第域指向相应行链表的第一个结链点。同理，对一个结链点。同理，对n个列链表个列链表,分别设置分别设置n个列链个列链表表头结点表表头结点。其中其中,令令row和和col的值分别为

26、的值分别为0，down域指向相应列链表的第一个结链点。域指向相应列链表的第一个结链点。另外，再设置一个总的头结点另外，再设置一个总的头结点(如下所示如下所示),),通过通过value域域把所有表头结点也链接成一个循环链表。把所有表头结点也链接成一个循环链表。m n val t总头结点总头结点 :B=对于如下稀疏矩阵对于如下稀疏矩阵B如下如下，十字链表表示如下十字链表表示如下：4 0 0 20 2 9 04 6 0 -53 470 03 03 00 00 01 1 43 4 20 02 2 22 3 90 00 03 1 43 2 63 4-5001HEAD4 0 0 20 2 9 04 6 0

27、-5广义表广义表(a1,a2,a3,an-1,an)若若ai 为不可再分割的数据元素，为不可再分割的数据元素，则称则称ai 为为原子元素原子元素；若若ai 为一个子表，则称为一个子表，则称ai 为为表元素表元素。这里，这里，用小写字母用小写字母表示原子元素，用大写字母表示表元素。表示原子元素，用大写字母表示表元素。一一.广义表的定义广义表的定义 一个长度为一个长度为n0 的广义表是一个数据结构的广义表是一个数据结构LS=(a1,a2,an-1,an)其中，其中，LS为广义表的名字为广义表的名字,ai为表中元素；为表中元素；ai 可以是可以是原子元素，也可以是一个子表。原子元素，也可以是一个子表

28、。n 为表的长度，长为表的长度，长度为度为0 的表称为空表。的表称为空表。A=();长度为长度为0的空表。的空表。B=();是以空表作为唯一元素的表，长度为是以空表作为唯一元素的表，长度为1。C=(a,b);有两个元素有两个元素a,b长度为长度为2。D=(a,(b,c);含有一个原子元素和一广义表，长度为含有一个原子元素和一广义表，长度为2。E=(x,D,y);长度为长度为3的广义表。的广义表。F=(a,F);长度为长度为2的递归的广义表。的递归的广义表。广义表的例子：广义表的例子：ababcxyabcaCDEDF表元素表元素原子元素原子元素 列表可以是一个递归的表，即列表可以是列表可以是一个

29、递归的表，即列表可以是本身的一个子表。本身的一个子表。列表可以为其他表所共享。列表可以为其他表所共享。列表的元素可以是子表列表的元素可以是子表,而子表的元素还可而子表的元素还可 以是子表以是子表,。结论结论1结论结论2结论结论3定义：一个表的深度是指表中所包含的括号的层数。定义：一个表的深度是指表中所包含的括号的层数。二二.广义表的存储广义表的存储flaginfolink其中，其中，flag为标志位为标志位,令令 1 表示本结点为表结点表示本结点为表结点 0 表示本结点为原子结点表示本结点为原子结点当当flag=0时时,info域存放相应原子元素的信息域存放相应原子元素的信息；当当flag=1

30、时，时，info域存放子表第一个元素对应的链结点的地址；域存放子表第一个元素对应的链结点的地址；link域存放本元素同一层的下一个元素所在链接点的地址，域存放本元素同一层的下一个元素所在链接点的地址，当本元素为所在层的最后一个元素时，当本元素为所在层的最后一个元素时，link域为域为null。flag=广义表一般采用链式存储结构，链结点的构造可以为广义表一般采用链式存储结构，链结点的构造可以为A=NilB=()1BC=(a,b)0a0bD=(a,(b,c)C0aD0b0c1E=(x,D,y)0 xE10yF=(a,F)0aF1多元多项式的广义表表示多元多项式的广义表表示P(x,y,z)=x10

31、y3z2+2x8y3z2+3x8y2z2+x4y4z+6x2y4z+2yz =(x10+2x8)y3+3x8y2)z2+(x4+6x2)y4+2y)zP(z)=Az2+BzA(x,y)=(x10+2x8)y3+3x8y2B(x,y)=(x4+6x2)y4+2yA(y)=Cy3+Dy2B(y)=Ey4+FyC(x)=x10+2x8D(x)=3x8E(x)=x4+6x2F(x)=2x0coef exp link若链结点的构造设计为若链结点的构造设计为其中其中,coef 表示多项式的某一项的系数表示多项式的某一项的系数,exp 表示多项式的某一项的指数表示多项式的某一项的指数,link 为链接多项式中同一层各链结点的指针为链接多项式中同一层各链结点的指针.相当于相当于data域域z21y32 y4x3 8 1 P6 2 1 4x1 102 8 xx2 0 P(x,y,z)=x10y3z2+2x8y3z2+3x8y2z2+x4y4z+6x2y4z+2yz =(x10+2x8)y3+3x8y2)z2+(x4+6x2)y4+2y)z该多项式的广义表的表示形式为：该多项式的广义表的表示形式为：C(x)=x10+2x8E(x)=x4+6x2D(x)=3x8F(x)=2x0A(y)=Cy3+Dy2B(y)=Ey4+FyP(z)=Az2+Bz