多维数组和广义表

《多维数组和广义表》由会员分享，可在线阅读，更多相关《多维数组和广义表（61页珍藏版）》请在装配图网上搜索。

1、,,单击此处编辑母版标题样式,,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,,*,,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,,*,,单击此处编辑母版标题样式,单击

2、此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,,*,多维数组和广义表,要 求,,2,,第,6,章 目 录,6-1 多维数组,6-2 特殊矩阵的压缩存储,6-3 稀疏矩阵,6-4 广义表,小 结,验证性实验６：,稀疏矩阵和广义表子系统,自主性实验6：稀疏矩阵十字链表的存储,,单元练习,6,3,,6-1,多维数组,6.1.1 逻辑构造,数组作为一种数据构造，其特点是构造中的元素可以是具有某种构造的数据，但属于同一数据类型。比方，一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组〞的一维数组，三维数组可以看作“数据元素是二维数组〞的一维数组。一般把三维以上的数组称

3、为多维数组，n维的多维数组可以视为n1维数组元素组成的线性构造。其中每一个一维数组又由m个单元组成。,图6-1是一个n行m列的数组。,,,4,,5,,在二维数组中的每一个元素最多可以有两个直接前驱和两个直接后继〔边界除外〕，在n维数组中的每一个元素最多可以有n个直接前驱和n个直接后继。所以多维数组是一种非线性构造。,数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识，通常在很多高级语言中数组一旦被定义，每一维的大小与上下界都不能改变。因此，在数组上一般不做插入或删除数据元素的操作。在数组中经常做的两种操作如下。,〔1〕取值操作：给定一组下标，读取其对应的数据元素。

4、 〔2〕赋值操作：给定一组下标，存储或修改与其相对应的数据元素。,6,,6.1.2 存储构造,通常，数组在内存被映象为向量，即用向量作为数组的一种存储构造，这是因为在计算机内存储构造是一维的。数组的行列固定后，通过一个映象函数，就可以根据数组元素的下标得到它的存储地址。对于一维数组只要按下标顺序分配即可；对多维数组分配时，要把它的元素映象存储在一维存储器中。,1．存储方式,〔1〕以行为主〔row major order〕,以行为主的存储方式也称为按行优先顺序方式，实现时按行号从小到大的顺序，先存储第0行的全部元素，再存放第1行的元素、第2行的元素……,一个2×3二维数组的逻辑构造如图6-2所

5、示，以行为主的内存映象如图6-3〔a〕所示，其分配顺序为：a00，a01，a02，a10 ，a11，a12。,7,,8,,以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变……，从右向左，最后是左下标。,〔2〕以列为主序〔column major order〕,以列为主的存储方式也称为按列优先顺序方式，实现时按列号从小到大的顺序，先存储第0列的全部元素，再存储第1列的元素、第2 列的元素……,图6-2所示的逻辑构造，以列为主的内存映象如图6-3〔b〕所示，其分配顺序为：a00，a10，a01，a11，a02，a12 。,以列为主分配的规律恰好与以行为

6、主次序相反：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变……，从左向右，最后是右下标。,9,,2．存储地址,“以行为主〞次序分配存储单元为例看其地址的计算,〔1〕二维数组中aij的地址,在C语言中数组中每一维的下界定义为0，数组的基址为LOC(a00)，每个数组元素占据d个字节，那么aij 的物理地址可用一个线性寻址函数计算：,LOC(aij) = LOC(a00) + ( i×n + j ) × d 〔0下标起始的语言〕,〔2〕三维数组中aijk的地址,同理对于三维数组元素aijk的物理地址为：,LOC(aijk)=LOC(a000)+( (i×n×p+ j×

7、p +k) ×d 〔0下标起始的语言〕,10,,【例6-1】设二维数组A5×6，每个元素占4个字节〔Byte〕，存储器按字节编址。A的起始地址为2000。计算,〔1〕数组的大小,n×m×d=5×6×4=120 Byte,〔2〕数组结点a45的存储地址,LOC(aij)=LOC(a00)+(i*n+j)*d // n为总列数,LOC(a45)=2000+(4×6+5)×4=2116,〔3〕按行为主存储，计算a32的存储地址,LOC(aij)=LOC(a00)+(i*n+j)*d // n为总列数,LOC(a32)=2000+(3×6+2)×4=2080,〔4〕按列为主存储，计算a32的存

8、储地址,LOC(aij)=LOC(a00)+(j*m+i)*d // m为总行数,LOC(a32)=2000+(2×5+3)×4=2052,11,,,【例6-2】假设矩阵An×m 中存在某个元素aij，满足：aij是第i行中最小值且是第j列中的最大值，那么称该元素为矩阵A的一个鞍点。试编写一个算法，找出A中的所有鞍点。,根本思想：在矩阵A中求出每一行的最小值元素，然后判断该元素是否是它所在列中的最大值。如果是那么打印输出，接着处理下一行。,设矩阵A用一个二维数组表示，其算法如下：,void saddle(int A[][],int n,int m),{ int i,j,min;,for(i=

9、0;i=n),printf(,＂,%d,%d,%d\n,＂,,i,k,min);,},},},算法的时间复杂度为,O,(,n,(,m,+,n m,)),。,,13,,6-2,,特殊矩阵的压缩存储,矩阵是一

10、个二维数组，是众多科学与工程计算问题中研究的数学对象。在矩阵中非零元素或零元素的分布有一定规律的矩阵称为特殊矩阵，如三角矩阵、对称矩阵、带状矩阵、稀疏矩阵等。当矩阵的阶数很大时，用普通的二维数组存储这些特殊矩阵将会占用很多的存储单元。从节约存储空间的角度考虑，下面来考虑这些特殊矩阵的存储方法。,14,,6.2.1 对称矩阵,对称矩阵是一种特殊矩阵，n阶方阵的元素满足性质：aij=aji 〔0<=i , j<=n1〕。,如图6-4所示是一个５阶对称矩阵。对称矩阵是关于主对角线的对称，因此只需存储上三角或下三角局部的数据即可。比方，只存储下三角中的元素aij，其特点是中j<=i且0=

11、1，对于上三角中的元素aij ，它和对应的aji相等，因此当访问的元素在上三角时，直接去访问和它对应的下三角元素即可，这样，原来需要nn个存储单元，现在只需要n(n+1)/2个存储单元了，节约了n(n1)/2个存储单元。,15,,图,6-4 5,阶对称方阵与它的压缩存储,,16,,如何只存储下三角局部呢？将下三角局部以行序为主序顺序存储到一个向量SA中去。在下三角中共有n(n+1)/2个元素，存储到一个向量空间SA[0]至SA[n(n+1)/2-1]中，存储顺序可用图6-5示意。,图,6-5,对称矩阵下三角压缩存储,17,,原矩阵下三角中的某一个元素aij具体对应一个sak，用“以行优

12、先〞存放下三角局部的元素时，a00存入sa0，a10存入sa1，a11存入sa2……。sak与aij的一一对应关系为：,k=j(j +1)/2+i 〔0<=k< n (n+1)/21〕,当i≥j时，在下三角局部aij前有i行，共有1+2+3+…+i个元素，而aij是第i行的第j个元素，即有k=1+2+3+……+i+j =i(i+1)/2+j。,当i

13、 〔0<=k

14、n,的下三角矩阵压缩存储设到向量SA[,n,(,n,+1)/2 +1]中，这种的存储方式可节约,n,,(,n,,1)/2,,1个存储单元。sa,k,与,a,ji,的对应关系为：,,,,,,下三角矩阵压缩存储如图,6-7,所示。,20,,2．上三角矩阵,对于上三角矩阵，其存储思想与下三角类似，共需要,n,(,n,+1)/2+1个存储单元。 sa,k,与,a,ji,的对应关系为：,,,,上三角矩阵压缩存储如图6-8 所示。,图6-8 上三角矩阵压缩存储,21,,稀疏矩阵,上述特殊矩阵，由于元素的分布具有某种规律，所以能找到一种适宜的方法进展压缩存储。但实际应用中有一种矩阵，在mn的矩阵中有

15、t个非零元素，且t远小于mn，我们这样的矩阵称为稀疏矩阵。在很多科学管理与工程计算中，常会遇到阶数很高的大型稀疏矩阵。假设按常规方法顺序分配在计算机内，那是相当浪费内存的。为此提出另外一些存储方法，仅仅存放非零元素。但对于这类矩阵，通常零元素分布没有规律，为了能找到相应的元素，仅存储非零元素的值是不够的，还要记下它所在的行和列等信息。,下面介绍几种常用的稀疏矩阵存储方法以与算法的实现。,22,,6.3.1 稀疏矩阵的存储,1．三元组表存储,将非零元素所在的行、列以与它的值构成一个三元组，然后再按某种规律存储这些三元组，采用这种方法存储稀疏矩阵称为三元组表，可以大大节约稀疏矩阵的存储空间。,

16、如图6-9的稀疏矩阵A，采用按行优先顺序方式存储该表，其三元组表如图6-10所示。显然，要唯一的表示一个稀疏矩阵，每个非零元素必须存储行、列、值〔i, j, v〕三个信息。,23,,24,,三元组表的定义：,#define SMAX 100 //,定义一个足够大的三元组表,struct SPNode //,定义三元组,{,int i,j,v; //,三元组非零元素的行、列和值,};,struct sparmatrix //,定义稀疏矩阵,{,int rows,cols,terms; //,稀疏矩阵行、列和非零元素的个数,SPNod

17、e data[SMAX]; //,三元组表,};,,这样的存储方法确实节约了存储空间，但矩阵的运算可能会变得复杂一些。,25,,2．带行指针的链表存储,假设把具有同一行号的非零元素用一个链表连接起来，那么稀疏矩阵中的假设干行组成假设干个单向链表，合起来就成为带行指针的单向链表。图6-9的稀疏矩阵A，可以用图6-11带行指针的单向链表表示。,26,,3．十字链表存储,三元组表可以看作稀疏矩阵顺序存储，但是在做一些操作〔如加法 、乘法〕时，非零元素的位置和个数会发生变化，三元组表就不太适宜了。此时采用十字链表来表示稀疏矩阵将是很方便的。,用十字链表存储稀疏矩阵的根本思想是：把每个非零元素作为一

18、个结点存储，结点中除了表示非零元素所在的行、列、值的三元组〔i, j, v〕以外还增加两个指针域，其构造如图6-14所示。其中：列指针域down用来指向本列中下一个非零元素；行指针域right用来指向本行中下一个非零元素。,27,,图,6-13,是一个稀疏矩阵,A,的十字链表。,,28,,稀疏矩阵中每一行的非零元素结点按其列号从小到大的顺序由right域连成一个带表头结点的循环行链表，同样每一列中的非零元素按其行号从小到大的顺序由down域也连成一个带表头结点的循环列链表。即每个非零元素aij既是第i行循环链表中的一个结点，又是第j列循环链表中的一个结点。行链表、列链表的头结点的i域和j域置0

19、。每一列链表的表头结点的down域指向该列链表的第一个元素结点，每一行链表的表头结点的right域指向该行表的第一个元素结点。由于各行、列链表头结点的i域、j域和v域均为零，行链表头结点只用right指针域，列链表头结点只用right指针域，故这两组表头结点可以合用，也就是说对于第i行的链表和第i列的链表可以共用同一个头结点。为了方便地找到每一行或每一列，将每行〔列〕的这些头结点们链接起来，因为头结点的值域空闲，所以用头结点的值域作为连接各头结点的链域，即第i行〔列〕的头结点的值域指向第i+1行〔列〕的头结点…… ，形成一个循环表。这个循环表又有一个头结点，这就是最后的总头结点，指针HA指向它

20、。总头结点的i和j域存储原矩阵的行数和列数。,29,,因为非零元素结点的值域是datatype类型，在表头结点中需要一个指针类型，为了使整个构造的结点一致，我们规定表头结点和其他结点有同样的构造，因此该域用一个共用体来表示；改进后的结点构造如图6-14所示。,,,,结点的构造定义如下：,typedef struct node,{ int i,j;,struct node *down,*right;,union v_next // 定义一个共用体,{ datatype v; // 值域,struct node *next;

21、 // 表头结点使用的next域,},}MNode,*MLink;,30,,6.3.2 稀疏矩阵的算法,1．建立稀疏矩阵A的十字链表,首先输入的信息是：m〔A的行数〕，n〔A的列数〕，r〔非零项的数目〕，紧跟着输入的是r个形如〔i,j,aij〕的三元组。,算法的设计思想是：首先建立每行〔每列〕只有头结点的空链表，并建立起这些头结点拉成的循环链表；然后每输入一个三元组〔i, j, aij〕，那么将其结点按其列号的大小插入到第i个行链表中去，同时也按其行号的大小将该结点插入到第j个列链表中去。在算法中将利用一个辅助数组MNode hd[s+1]; 其中 s=max(m , n) ,

22、hd [i]指向第i行〔第i列〕链表的头结点。这样做可以在建立链表时随机的访问任何一行〔列〕，为建表带来方便。,31,,MLink CreatMLink() // 返回十字链表的头指针,｛,MLink H;,Mnode *p,*q,*hd[s+1];,int i,j,m,n,t;,datatype v;,scanf("d%,d%,%d",,H=new MNode; // 申请总头结点,H->row=m;,H->col=n;,hd[0]=H;,for(i=1; irow=

23、0; p->col=0;,p->right=p; p->down=p;,hd[i]=p; hd[i-1]->v_next.next=p; },,32,,hd[S]->v_next.next=H; // 将头结点们形成循环链表,for(k=1;k<=t;k++),{ scanf (“%d,%d,%d〞,// 输入一个三元组,p= new MNode;,p->row=i; p->col=j; p->v_next.v=v,q=hd[i];,while(q->right!=hd[i]&&(q->right->col)right;,p->ri

24、ght=q->right; // 插入,q->right=p; q=hd[i];,while(q->down!=hd[j]&&(q->down->row)down;,p->down=q->down; // 插入,q->down=p;,},return H;,},33,,上述算法中，建立头结点循环链表时间复杂度为O(S)，插入每个结点到相应的行表和列表的时间复杂度是O(tS)，这是因为每个结点插入时都要在链表中寻找插入位置，所以总的时间复杂度为O(tS)。该算法对三元组的输

25、入顺序没有要求。如果我们输入三元组时是按以行为主序〔或列〕输入的，那么每次将新结点插入到链表的尾部的，改进算法后，时间复杂度为O(S+t)。,34,,2．稀疏矩阵的加法,两个十字链表存储的稀疏矩阵A和B，计算C=A+B，C也采用十字链表方式存储，并且在A的根底上形成C。,由矩阵的加法规那么知，只有A和B行列对应相等，二者才能相加。C中的非零元素cij只可能有3种情况：或者是aij+bij，或者是aij〔bij=0〕，或者是bij〔aij=0〕，因此当B加到A上时，对A十字链表的当前结点来说，对应以下四种情况：或者改变结点的值〔aij+bij≠0〕，或者不变〔bij0〕，或者插入一个新结点〔a

26、ij0〕，还可能是删除一个结点〔aij+bij0〕。整个运算从矩阵的第一行起逐行进展。对每一行都从行表的头结点出发，分别找到A和B在该行中的第一个非零元素结点后开场比较，然后按4种不同情况分别处理。设pa和pb分别指向A和B的十字链表中行号一样的两个结点，4种情况如下：,35,,〔1〕假设pa->col=pb->col且pa->v+pb->v≠0，那么只要用aij+bij的值改写pa所指结点的值域即可。,〔2〕假设pa->col=pb->col且pa->v+pb->v=0，那么需要在矩阵A的十字链表中删除pa所指结点，此时需改变该行链表中前趋结点的right域，以与该列链表中前趋结点的do

27、wn域。,〔3〕假设pa->col col且pa->col≠0〔即不是表头结点〕，那么只需要将pa指针向右推进一步，并继续进展比较。〔4〕 假设pa->col > pb->col或pa->col0〔即是表头结点〕，那么需要在矩阵A的十字链表中插入一个pb所指结点。,由前面建立十字链表算法知，总表头结点的行列域存放的是矩阵的行和列，而各行〔列〕链表的头结点其行列域值为零，当然各非零元素结点的行列域其值不会为零，下面分析的4种情况利用了这些信息来判断是否为表头结点。,36,,MLink AddMat(Ha,Hb),MLink Ha,Hb;,{ Mnode *p,*q,*pa,*pb,*ca,*

28、cb,*qa;,if(Ha->row!=Hb->row||Ha->col!=Hb->col),return NULL;,ca=Ha->v_next.next; // ca初始指向A矩阵中第一行表头结点,cb=Hb->v_next.next; // cb初始指向B矩阵中第一行表头结点,do{ pa=ca->right; // pa指向A矩阵当前行中第一个结点,qa=ca; // qa是pa的前驱,pb=cb->right; // pb指向B矩阵当前行中第一个结点,while(pb->col!=0) // 当前行没有处理完,{ if(pa->colcol &&

29、pa->col!=0),{ qa=pa; pa=pa->right;},else,if(pa->col>pb->col||pa->col==0),{ p=new MNode;,p->row=pb->row;,p->col=pb->col;,p->v=pb->v;,p->right=pa;,qa->right=p; // 新结点插入*pa的前面,pa=p; // 新结点还要插到列链表的适宜位置，先找位置，再插入,q=Find_JH(Ha,p->col); // 从列链表的头结点找起,while(q->down->row!=0&&q->down->rowrow),q=

30、q->down;,p->down=q->down; // 插在*q的后面,q->down=p;,pb=pb->right;,},else // 第一、二种情况,{ x=pa->v_next.v+pb->v_next.v;,if(x==0) // 第二种情况,{ qa->right=pa->right; // 从行链中删除，,// 要从列链中删除，找*pa的列前驱结点,q=Find_JH(Ha,pa->col); // 从列链表的头结点找起,while(q->down->row row),q=q->down;,q->down=p

31、a->down;,delete pa;,pa=qa;,},else // 第一种情况,{ pa->v_next.v=x; qa=pa; },pa=pa->right;,pb=pb->right;,},},ca=ca->v_next.next; // ca指向A中下一行的表头结点,cb=cb->v_next.next; // cb指向B中下一行的表头结点,},while(ca->row==0) // 当还有未处理完的行那么继续,return Ha;,},为了保持算法的层次，在上面的算法中用到了一个函数Find_JH()，其功

32、能是：返回十字链表H中第j列链表的头结点指针。,37,,3． 矩阵的转置,设SPMatrix A; 表示一m*n的稀疏矩阵，其转置B那么是一个n*m的稀疏矩阵，因此也有SPMatrix B; 由稀疏矩阵A求它的转置B只要将A的行、列转化成B的列、行。,将中每一三元组的行列交换后转化到后，似乎已完成了转置，其实不然。A的转置B如下图，图是它对应的三元组存储。也就是说，在A的三元组存储根底上得到B的三元组表存储。,38,,转置算法的实质是将矩阵A,的行和列转化成矩阵,B,的列和行。,sparmatrix Trans(sparmatrix A) // 调用稀疏矩阵A,{ sparmatrix

33、 B; // 定义稀疏矩阵B,B.rows=A.cols;,B.cols=A.rows;,B.terms=A.terms;,for (int n=0;n<=A.terms-1;n++),{ B.data[n].i=A.data[n].j;,B.data[n].j=A.data[n].i;,B.data[n].v=A.data[n].v;,},return B; // 返回转置矩阵B,},本算法的时间复杂度为O(n)。,39,,广义表是线性表的推广，也有人称其为列表〔Lists〕。线性表中的元素仅限于单个数据元素

34、〔也称为原子项〕，即不可以再分割；而广义表中的元素既可以是原子项，也可以是子表。,6.4.1 广义表的定义和运算,1. 广义表的定义,广义表〔Generalized Lists〕是n〔n≥0〕个数据元素a1，a2，…，ai，…，an的有序序列，一般记作：,LS＝〔a1，a2，…，ai，…，an〕,其中：LS是广义表的名称，n是广义表的长度。每个ai〔1≤i≤n〕是LS的成员，它可以是单个元素〔原子〕，也可以是一个广义表〔子表〕。当广义表LS非空时，称第一个元素a1为LS的表头〔head〕，称其余元素组成的表〔a2，…，ai，…，an〕为LS的表尾〔tail〕。显然，广义表的定义是递归的。,6

35、-4,,广义表,40,,广义表通常用圆括号括起来，并用逗号分隔表中的元素。为了清楚起见，通常用大写字母表示广义表，用小写字母表示单个数据元素。,广义表的长度指该广义表中所包含的元素〔包括原子和子表〕的个数。广义表的深度指该广义表中所包含括号的层数。,广义表中的结点具有不同的构造，即原子结点和子表结点。为了将两者统一，一般用一个标志tag，当其为1时表示是原子结点，其data域存储结点的值，link域指向下一个结点；当tag为0时表示是子表结点，其sublist为指向子表的指针。广义表的存储结点可定义如下：,struct linknode,{ int tag; //

36、 区分原子和子表的标志位,linknode *link; // 存放下一个元素的地址,union data_sublist,{ char data; // 元素的值域,linknode *sublist; // 存放子表的指针,}node;,};,41,,2. 广义表的性质,从上述广义表的定义和例子可以得到广义表的以下重要性质：〔1〕广义表是一种多层次的数据构造，其中的元素可以是单元素，也可以是子表。,〔2〕广义表可以是递归的表，即广义表也可以是其自身的子表。例如表E就是一个递归的表。,〔3〕义表可以为其他表所共享。

37、例如表B、表C是表D的共享子表。,广义表的构造相当灵活，它可以兼容线性表、数组、树和有向图等各种常用的数据构造。当二维数组的每行〔或每列〕作为子表处理时，二维数组即为一个广义表。另外，树和有向图也可以用广义表来表示。,广义表不仅集中了线性表、数组、树和有向图等常见数据构造的特点，而且可有效地利用存储空间，因此在计算机的应用领域有许多成功应用的实例。,42,,【例6.3】广义表的例子,〔1〕A＝()，广义表A是长度为0的空表。,〔2〕B＝(a，b)，B是长度为2的广义表。由于表中的元素全部是原子项，它实质上就是线性表。,〔3〕C＝(c，(d，e))，C是长度为2的广义表，其中第一项为原子项，第二

38、项为子表。,〔4〕D＝(B，C)，D是长度为2的广义表，其中每一项都是子表。,〔5〕E＝(f ，g，E)，E是长度为3的广义表，其中第一、第二项为原子项，第三项是本身，这样的广义表也称为递归表。,43,,广义表的头元素和尾元素。,Head〔A〕＝〔〕 Tail〔A〕＝〔〕,Head〔B〕＝a Tail〔B〕＝ b,Head〔C〕＝c Tail〔C〕＝〔〔d，e〕〕,Head〔D〕＝B Tail〔D〕＝ C,Head〔E〕＝f Tail〔E〕＝〔g，E〕,3. 广义表根本运算,〔1〕 创立广义表：CreateGL (GL),操作结果：创立一个广义表GL,〔2

39、〕  求广义表的长度：Len(GL),初始条件：广义表存在。,操作结果：返回广义表的长度。,44,,〔3〕 求广义表的深度：Depth (GL),初始条件：广义表存在。,操作结果：返回广义表的深度。,〔4〕查找操作：Search(GL，x),初始条件：广义表GL存在，ｘ是给定的一个数据元素或子表。,操作结果：查找成功返回1； 否那么返回0。,〔5〕 求广义表头部：Head(LS),初始条件：广义表存在。,操作结果：返回广义表的头元素。,〔6〕 求广义表尾部：Tail(LS),初始条件：广义表存在。,操作结果：返回广义表的尾元素。,45,,6.4.2 广义表的首尾存储法,广义表中的数据元素可以

40、具有不同的构造，因此难以用顺序的存储构造来表示，而链式存储构造分配灵活，易于解决广义表的共享与递归问题，所以通常都采用链式的存储构造来存储广义表。,广义表中的元素可以是数据元素，也可以是表，因此结点的构造也需要两种：一种是表结点，用以表示表；另一种是原子结点，用以表示原子。按结点形式的不同，广义表的链式存储构造又可以分为不同的两种存储方式。,由于广义表中的数据元素既可能是表也可能是单元素，相应地在头尾表示法中结点的构造形式有两种：一种是表结点，用以表示表；另一种是元素结点，用以表示原子。表结点由三个域：标志域〔tag=1〕、表头指针域〔hp〕、表尾指针域〔tp〕组成；而原子结点由两个域：标志域

41、〔tag=0〕和值域〔data〕组成。,46,,广义表的结点形式如图 6.17 所示。,广义表的这种表示法也称为头尾表示法。假设广义表不空，那么可分解成表头和表尾；反之，一对确定的表头和表尾可惟一地确定一个广义表。头尾表示法就是根据这一性质设计而成的一种存储方法。,广义表的例子所列举的广义表A、B、C、D、E，假设采用头尾表示法的存储方式，其存储构造如图6.18所示。,47,,48,,6.4.3 广义表的算法,1．创立广义表算法,设广义表以单链表形式存储，元素的类型为字符型char。广义表的元素由键盘输入，假定全部为字母。元素之间用逗号分割，元素的起止符号分别用左、右圆括号表示。,linkn

42、ode *CreateGL(char s[]),{ linknode *p,*q,*r,*gh;,char subs[100],hstr[100];,int len;,len=strlen(s);,if (!strcmp(s,"()")),gh=NULL;,else,49,,if (len==1),{ gh=new linknode;,gh->tag=0;,gh->node.data=*s;,gh->link=NULL;,},else,{ gh=new linknode;,gh->tag=1;,p=gh;,s++;,strncpy(subs,s,len-2);,subs[len-2]='\

43、0';,},50,,do,{ Disastr(subs,hstr);,r=CreateGL(hstr);,p->node.sublist=r;,q=p;,len=strlen(subs);,if (len>0),{ p=new linknode;,p->tag=1;,q->link=p;,},}while (len>0);,q->link=NULL;,},return gh;,},创立广义表算法的时间复杂度为O(n)。,51,,2．广义表取头算法,假设广义表GL=〔a1，a2，……，an〕，那么head〔GL〕=a1 。取表头运算的结果可以是原子，也可以是一个子表。,例如，head〔〔a1

44、，a2〕，〔a3，a4，a5〕，a6〕=〔a1，a2〕。,Head(linknode *GL),{,if GL->tag==1,p=GL->hp;,return p;,},52,,3. 广义表取尾算法,假设广义表GL=〔a1，a2，……，an〕，那么tail〔GL〕=〔a2，……，an〕 。取表尾运算的结果是取出除表头以外的所有元素。,例如，tail〔〔a1，a2〕，〔a3，a4，a5〕，a6〕=〔〔a3，a4，a5〕，a6〕。,Tail(linknode *GL),{,if GL->tag==1,p=GL->tp;,return p;,},53,,4. 求广义表深度算法,int Dept

45、h(linknode *GL),{ int max=0;,while (GL!=NULL),{ if (GL->tag==0),// 有子表,{ int dep=Depth(GL->sublit),if (dep>max),max=dep;,},GL=GL->link;,},return max+1;,// 非空表的深度是各元素的深度的最大值加1,},求广义表深度算法的时间复杂度为O(n)。,54,,〔1〕 数组是一个具有固定格式和数量的数据有序集，每一个数据元素有唯一的一组下标来标识，在数组上不太适宜做插入、删除数据元素的操作。,〔2〕二维数组中aij的地址为：,LOC(aij) = LOC

46、(a00) + ( i×n + j ) × d 〔0下标起始的语言〕,〔3〕三维数组中aijk的地址为：,LOC(aijk)=LOC(a000)+( (i×n×p+ j×p +k) ×d 〔0下标起始的语言〕,〔4〕对称矩阵是一种特殊矩阵，n阶方阵的元素满足性质：,aij=aji 〔0≤i , j≤n-1〕。对称矩阵是关于主对角线的对称，因此只需存储上三角或下三角局部的数据即可。,小 结,55,,〔5〕三角矩阵的特殊性是以主对角线划分矩阵。主对角线任意一侧〔不包括主对角线中〕的元素均为常数〔C〕。下三角矩阵，主对角线以上均为同一个常数；上三角矩阵，主对角线以下均为同一个常数，均可以

47、采用压缩存储。,〔6〕在m*n的矩阵中有t个非零元素，且t远小于m*n，这样的矩阵称稀疏矩阵。稀疏矩阵常用的有：三元组表存储、带行指针的链表存储、十字链表存储等存储方法。,,,,〔7〕 广义表是n〔n≥0〕个数据元素的有序序列，广义表的元素可以是单元素，也可以是一个广义表。,〔8〕 由于广义表的元素有两种形式，所以其结点的存储形式也有两种：表结点由标志域、表头指针域、表尾指针域组成；而原子结点由标志域和值域组成。,56,,1．实验目的,〔1〕 掌握稀疏矩阵三元组表的存储方法。,〔2〕掌握稀疏矩阵三元组表创立、显示、转置和查找等算法。,〔3〕掌握广义表的存储方法。,〔4〕掌握广义表的新建、显示和

48、查找等算法。,〔5〕掌握稀疏矩阵三元组表和广义表的算法分析方法。,2．实验内容,〔1〕编写稀疏矩阵三元组表的存储程序；,〔2〕编写疏矩阵三元组表创立、显示、转置和查找程序；,〔3〕编写建立广义表的程序；,〔4〕编写广义表的显示和查找程序；,〔5〕设计选择式菜单，其一级菜单形式如下：,验证性实验,6,: 稀疏矩阵和广义表子系统系统,57,,稀疏矩阵和广义表子系统,*******************************************,* 1-----稀 疏 矩 阵 *,* 2-----广 义 表

49、 *,* 0-----退 出 *,*******************************************,请输入菜单号〔0-2〕:,,稀疏矩阵二级菜单形式如下：,稀疏矩阵的三元组存储,******************************************,* 1-----新 建 *,* 2-----转 置 *,* 3-----查 找 *,*

50、 4-----显 示 *,* 0-----返 回 *,******************************************,请输入菜单号〔0-4〕:,58,,广义表二级菜单形式如下：,,广 义 表,******************************************,* 1-----新 建 *,* 2-----查 找 *,* 3-----显 示 *,* 0-----返 回 *,******************************************,请输入菜单号〔0-3〕:,59,,谢谢欣赏,60,谢谢观赏！,61,2020/11/5,