数据结构Ch5数组和广义表

《数据结构Ch5数组和广义表》由会员分享，可在线阅读，更多相关《数据结构Ch5数组和广义表（40页珍藏版）》请在金锄头文库上搜索。

1、数据结构Ch5数组和广义表Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望25.1 多维数组多维数组n多维数组多维数组是最易处理的非线性结构。因为各元素类型一致，是最易处理的非线性结构。因为各元素类型一致，各维上下界固定，所以它最容易线性化，故可看各维上下界固定，所以它最容易线性化，故可看做是线性表的拓广。例如：二维数组可以看做是做是线性表的拓广。例如：二维数组可以看做是由列向量组成的线性表。由列向量组成的线性表。35.1 多维数组多维数组1.结构特性结构特性例：二维数组 ，它属于两

2、个向量；i th行和j th列。除边界外，每个aij恰有两个直接前驱和两个直接后继。45.1 多维数组多维数组n非线性特征i th行：前驱aij-1，后继aij+1j th列：前驱ai-1j，后继ai-1j仅有一个开始结点：a11仅有一个终端节点：amn其他边界上的结点只有一个直接前驱或一个直接后继，类似的m维数组 的每一个元素都属于m个向量。55.1 多维数组多维数组2.存储一般均采用顺序方式存储，原因是结构中的结点不变动，内存是一维的，必须将多维数组线性化。行优先（行主序）方式：将(i+1)th行向量紧接在i th行向量之后：特点：列下标变化快。Pascal、C等均是此方法。先排最右下标（

3、多维）。65.1 多维数组多维数组列优先（列主序）方法特点行下标变化最快，先排最左下标（可推广至多维）。Fortan是用此方法。地址计算 一维存储地址（内部实现）。n基地址开始结点存储地址Loc(a11).n维数每维的上下界（若下界固定，则只须知道维长度）n每个元素占用的单元数（元素大小）：L75.1 多维数组多维数组例：行主序 。 A1.m,1.n原理：aij的地址=基址+排在aij之前的元素个数每 个元素的大小Loc(aij)=Loc(a11)+(i-1)n+(j-1) L 前i-1行结点总数 第i行上aij之前的结点数在C语言中， 是A0.m-1 , 0.n-1，故有： Loc(aij)

4、=Loc(a00)+in+j L85.1 多维数组多维数组n多维推广：以C为例，行主序。n思考：Ac1.d1 , c2.d2Loc(aij)=Loc(ac1c2)+(i-c1) (d2-c2+1)+(j-c2) L i th行前行数 第2维长度 i th行aij之前结点数n特点：随机存取。 95.2 矩阵的压缩存储矩阵的压缩存储n用用二二维数数组表表示示的的特特点点：随随机机存存取取，存存储密密度度为1。但但对特特殊殊和和稀稀疏疏矩矩阵的的存存储则浪浪费空空间，尤其是大尤其是大规模科学与工程模科学与工程计算。算。5.2.1 特殊矩阵特殊矩阵n有有规规律律：压压缩缩后后可可找找到到地地址址变变换

5、换公公式式，保保持持随随机存取功能。机存取功能。105.2 矩阵的压缩存储矩阵的压缩存储1.对称阵对称阵 n阶方阵A，若 则称A为对称阵。因为矩阵元素关于主对角线对称，故只存上三角或下三角元素即可，节约近一半空间。不失一般性，存储下三角（包括主对角线），以行主序存储：元素个数115.2 矩阵的压缩存储矩阵的压缩存储n压缩存储：压缩存储：将其存于向量sa0.n(n+1)/21中。如何访问aij？必须将其与sak的对应关系找出来。n地址计算：地址计算：下三角中有j i.aij之前有i行（0 i-1） 第i行上aij之前元素个数为j(0 j-1). 125.2 矩阵的压缩存储矩阵的压缩存储上三角中有

6、i j ,只需交换上式的j和i即可得：令I=max (i , j)，J=min (i , j)，则k和i，j之关系可统一表示为：2.三角矩阵三角矩阵 压缩方式同上，在sa中多增加一个单元： sa0.n(n+1)/2 将C存于最后一个分量中。135.2 矩阵的压缩存储矩阵的压缩存储3.对角矩阵对角矩阵总结：这类矩阵压缩存储后能找到地址计算公式，使其保持随机存取的功能。145.2 矩阵的压缩存储矩阵的压缩存储 5.2.2 稀疏矩阵稀疏矩阵n定定义义：设Amn中有t个非零元素，若 ，称A为稀疏矩阵。n稀疏因子： 一般非零元素分布无规律性n压缩存储：只存储非零元，故须存储辅助信息，才能确定其位置。三元

7、组(i，j，aij)：（行号，列号，非零元的值）唯一确定一个非零元。当用三元组表示非零元时，有两种压缩方式：顺序和链式。155.2 矩阵的压缩存储矩阵的压缩存储1.三元三元组顺序表（三元序表（三元组表）表）以行主序（或列主序）的顺序存储非零元，跳以行主序（或列主序）的顺序存储非零元，跳过零元。得到一个其节点均是三元组的线性表，过零元。得到一个其节点均是三元组的线性表，称此顺序存储结构为三元组表。称此顺序存储结构为三元组表。#define MaxSize 10000typedef int DataTypetypedef struct/三元组int i, j；DataType v;TripleNo

8、de;165.2 矩阵的压缩存储矩阵的压缩存储typedef struct/三元组表TripleNode dataMaxSize;int m, n, t; /行数，列数，非零元总数TripleTable;设设a，b是是TripleTable型变量。型变量。n转置运算转置运算 175.2 矩阵的压缩存储矩阵的压缩存储185.2 矩阵的压缩存储矩阵的压缩存储方法一：方法一：按B的次序或按A的列序转置。A的列是B的行，故按A的列序转置，所得B是按行主序存放的。基本思想：对A中每列，从头至尾扫描a.data，找出所有列号为col的三元组(0coln-1)，将它们的行、列号互换后依次放入b.data，即

9、可得行主序表示的B的三元组。正确性：按A的列号递增序转置，保证B按行号增序排列，B中同一行号的三元组，扫描A时所得三元组 必有iB int p, q, col; if (a.t = 0) Error(“A is empty”); b.m = a.n; b.n = a.m; b.t = a.t ; /行列数互换 q=0; /指示转置过的三元组 for( col = 0; col a.n ; col+)/对A的每一列号 for( p = 0; p a.t; p+)/扫描A的三元组表 if (a.datap.j = col) /找A的列号为col的三元组 b.dataq.i = a.datap.j

10、; b.dataq.j = a.datap.i ; b.dataq.v = a.datap.v ; q+; 205.2 矩阵的压缩存储矩阵的压缩存储方法二：按A的行序转置。若简单的变换a.data的行和列，则b.data为列主序存储，要重排。但若预先确定A中每一列（即B中每一行）的第一个非零元在b.data中应有的位置，则可正确转置。位置向量：215.2 矩阵的压缩存储矩阵的压缩存储n思想 先求出A中每一列的非零元个数，可将第col列的非零元个数记入potcol+1中。step1：初始化将所有pot中元素清0./O(n)step2：扫描a.data，将列号为col的非零元个数累加到potcol

11、+1中。/O(t)step3：令potcol=potcol-1+potcol 1cola.n-1/O(n)step4：扫描a.data，将(i,col,v)转置后放于b.datapotcol中，potcol+./O(t)时间O(n+t)，快速。key：pot1.a.n=第0a.n-1列的非零元个数。225.2 矩阵的压缩存储矩阵的压缩存储void FastTransMatrix(TripleTable &a , Tripletable &b) /pot0.a.n，比n多1if (a.t = 0) Error(“”);/A全零b.m = a.n; b.n = a.n; b.t = a.t;for

12、 ( col = 0; col=a.n ; col+) potcol = 0; /step1初始化 for ( p = 0; p a.t; p+) / step2扫描a.data pota.datap.j + 1+; /设a.datap.j = col pota.n是哨兵for ( col = 1; col a.n; col+)/step3. pota.n无用，但第二个循环须统计 potcol = potcol 1 + potcol;for ( p = 0; p a.t; p+) /step4 col = a.datap.j; /当前三元组列号. q = potcol+; b.dataq.i

13、= a.datap.j; b.dataq.j = a.datap.i; b.dataq.v = a.datap.v;235.2 矩阵的压缩存储矩阵的压缩存储以上图为例，2.带行表的三元组表。（顺序方式）在行优先存储的三元组表中，加入一个行表来记录稀疏矩阵压缩后每行非零元在三元组表中的起始位置。245.2 矩阵的压缩存储矩阵的压缩存储3.十字链表上两种方式是顺序存储，若非零元位置或个数经常发生变化，会引起结点移动，效率降低。此时宜用链式存储。例：AA+B稀疏矩阵的链接存储方式有多种，这里仅介绍十字链表n结点结构 n存储结构分别设两个指针数组作为各行、列单链表的头指针。255.2 矩阵的压缩存储矩

14、阵的压缩存储typedef struct CLNodeint i, j ;DataType v;struct CLNode * right, *down;CLNode;typedef struct CLNode *rheadMaxRow; /行链表头指针，MaxRow在前定义CLNode *cheadMaxCol; /列int m,n, t;CrossList;CrossList A;265.2 矩阵的压缩存储矩阵的压缩存储275.3 广义表（广义表（Lists）1.概念概念是线性表的推广，如将线性表中元素是线性表的推广，如将线性表中元素ai放宽到可以是自放宽到可以是自身的结构。身的结构。n定

15、义：定义： ，它由，它由n个元素构成的有限个元素构成的有限序列，其中序列，其中ai或是原子，或是广义表（子表）。或是原子，或是广义表（子表）。LS-名字，名字，n-长度长度，n=0为空表。为空表。一般用小写字母表示原子，大写字母表示子表。一般用小写字母表示原子，大写字母表示子表。n表头、表尾、深度表头、表尾、深度若若 ，则，则a1成为成为表头表头（首），剩余元素构成的表（首），剩余元素构成的表 为为表尾表尾。广义表是递归定义的，展开到每一。广义表是递归定义的，展开到每一元素均为原子时括号的最大层数为元素均为原子时括号的最大层数为深度深度。 285.3 广义表（广义表（Lists）n例：例：E=

16、( ) 空表，长度空表，长度n = 0，深度，深度d = 1.L=(a, b) n = 2，d = 1. （线性表）（线性表）A=(x, L)=(x, (a, b) n=2, d=2. a1为原子，为原子，a2为子表为子表B=(A, y)=(x, (a, b), y) n = 2, d = 3.C=(A, B)=(x, (a, b), (x, (a, b), y) n = 2, d = 4.D=(a, D)=(a, (a, (a, () n = 2, d = .n若规定任何表都有名字，则可在每个表前冠名。若规定任何表都有名字，则可在每个表前冠名。E( ) L(a, b) A(x, L(a, b

17、)295.3 广义表（广义表（Lists）n图示n各种表之关系305.3 广义表（广义表（Lists）n运算求表头、表尾。head(A) = x, tail(A) = (a, b) /表尾是表，表头不一定表尾是表，表头不一定head(tail(A) = (a, b) 表表Note： 和和 不同。不同。 为空表为空表n=0n=0，不能求表头和表尾。，不能求表头和表尾。 为非空表，为非空表，n=1. n=1. 可求表头和尾：可求表头和尾： 315.3 广义表（广义表（Lists）2.存储结构因为广义表数据元素可具有不同结构，故难以用顺序方式存储。一般用链接方式存储，称之为广义链表。(1)广义表的头

18、尾链表表示方法。n表结点：n原子结点：存储结构见书上说明325.3 广义表（广义表（Lists）n图示E=NIL335.3 广义表（广义表（Lists）n特点除空表的表头指针为空外，头指针均指向表结点。任一表结点的hp均指向表头部（原子结点或表结点）任一表结点的tp均指向表尾部（当表尾部为空表时，tp=NIL，否则必指向表结点）易分清表中原子和子表所在层次。如x、L在第一层，a、b在第二层。最高层的表结点数即为广义表的长度。浪费空间，易求表长和表深度。345.3 广义表（广义表（Lists）(2) 单链表示法模仿线性表的单链表结构，当所有元素为原子时，等价于单链表模仿线性表的单链表结构，当所有

19、元素为原子时，等价于单链表。n结点结构：n图示：图示：E=NILC=(A, B)=(x, (a, b), (x, (a, b), y) =(A(x, L(a, b), B(A(x, L(a, b), y)355.3 广义表（广义表（Lists）n存储结构说明typedef struct GLNodeint atom; /亦可定义为枚举类型，标志域struct GLNode *slink; /指向同层后继union struct GLNode *slink; /指向子表的第一个结点DataType data； /原子结点数据域optval; /候选值 *GList;365.3 广义表（广义表（L

20、ists）n缺点：若要在某一表中开始处插入或删除一个结点，则要找出所有指向该结点的指针，逐一加以修改。例如，上图中，删除A表中的x，修改A的头指针外，须修改来自于B、C表的指针，引用来源点不易知道。删除一个表可能导致错误。例如，删除A表时，A的所有结点释放后，会引起B、C表的错误。375.3 广义表（广义表（Lists）n改进引入表头结点，使子表内部的变化不会涉及外部元素的变化，插删第一个结点方便。头结点和其他结点结构相同，只是以示区别：删除表时，头结点引用计数减1，仅当引用计数为0时，才释放表中所有结点。385.3 广义表（广义表（Lists）(3) 双链表示法该方法类似于第6章的二叉链表。n结点结构n存储说明typedef struct GLNodeDataType data; /子表名字或原子数据struct GLNode *link1, *link2; *GList;395.3 广义表（广义表（Lists）n图示n特点简洁方便，类似于二叉链表，可借助于二叉链表表示处理，易求长度深度。在表结点中保存了子表的名字信息，有时子表名字和原子信息同样重要。405.3 广义表（广义表（Lists）n例子(姓名姓名,工资收入工资收入(基本工资基本工资,午餐补助午餐补助,津贴津贴),扣除扣除(公积金公积金,水电费水电费,其它其它),实发工资实发工资)3. 运算：略运算：略