数据结构第五章C.ppt

第五章 多维数组和广义表 5.1 多维数组 5.2 矩阵的压缩存储 5.2.1 特殊矩阵 5.2.2 稀疏矩阵 5.3 广义表的概念 5.4 广义表的存储 对许多应用程序来说，使用简单的线性表和数组完成任务就足够了，但是有一些应用程序不能使用简单线性表来有效地实现。人们可以对线性表进行扩展，实现一些功能更强大、具有更多操作的高级线性结构。 前几章讨论的线性结构中的数据元素都是非结构的原子类型，元素的值是不再分解的。本章讨论的两种数据结构----数组和广义表可以看成是线性表在下述含义上的扩展：表中的数据元素本身也是一个数据结构。 纯线性结构表如右图所示： 但是现实中往往有一些更加复杂的情况，例如表示一个地区列表： 按这种方法设计的算法，其基本思想是：对A中的每一列 col(0≦col≦n-1)，通过从头至尾扫描三元表a.data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放入b.data中，即可得到B的按行优先的压缩存储表示。 i j v 0 2 -3 0 5 15 1 0 12 1 4 18 2 0 9 2 3 24 3 5 -7 5 2 14 i j v 0 1 12 0 2 9 2 0 -3 2 5 14 3 2 24 4 1 18 5 0 15 5 3 -7 Void transmatrix(tripletable a,tripletable b) { int p q col; b.m=a.n; b.n=a.m; b.t=a.t; if(b.t=0) printf(“A=0\n”); q=0; for(col=1;col=a.n;col++) for(p=0;p=a.t;p++) if(a.data[p].j==col){ b.data[q].i=a.data[p].j; b.data[q].j=a.data[p].i; b.data[q].v=a.data[p].v; q++; } } 分析这个算法，主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(n*t)，即矩阵的列数和非零元素 的个数的乘积成正比。而一般传统矩阵的转置算法为： for(col=0;col=n-1;++col) for(row=0;row=m;++row) t[col][row]=m[row][col]; 其时间复杂度为O(n*m)。当非零元素的个数t和m*n同数量级时，算法transmatrix的时间复杂度为O(n*n2)。 三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算法的难度。因此，此算法仅适用于tm*n的情况。 2、十字链表 稀疏矩阵中非零元素的位置或个数经常变动时，三元组就不适合于作稀疏矩阵的存储结构，此时，采用链表作为存储结构更为恰当。 十字链表为稀疏矩阵链接存储中的一种较好的存储方法，在该方法中，每一个非零元素用一个结点表示，结点中除了表示非零元素所在的行、列和值的三元组(i,j,v)外，还需增加两个链域：行指针域(rptr)，用来指向本行中下一个非零元素；列指针域(cptr)，用来指向本列中下一个非零元素。稀疏矩阵中同一行的非零元素通过向右的rptr指针链接成一个带表头结点的循环链表。同一列的非零元素也通过cptr指针链接成一个带表头结点的循环链表。因此，每个非零元素既是第i行循环链表中的一个结点，又是第j列循环链表中的一个结点，相当于处在一个十字交叉路口，故称链表为十字链表。 用十字链表表示稀疏矩阵的结构特点： (1)稀疏矩阵的每一行与每一列均用带表头结点的循环链表表示。 (2)表头结点中的行域与列域的值均置为0（即i＝0，j＝0）。 (3)行、列链表的表头结点合用，且这些表头结点通过