数据结构Ch数组和广义表ppt课件

1、数数 据据 结结 构构 Ch.5数组和广义表数组和广义表计计 算算 机机 学学 院院 肖明军肖明军: /xiaomj5.1 多维数组多维数组n多维数组多维数组n是最易处置的非线性构造。由于各元素是最易处置的非线性构造。由于各元素类型一致，各维上下界固定，所以它最容易类型一致，各维上下界固定，所以它最容易线性化，故可看做是线性表的拓广。例如：线性化，故可看做是线性表的拓广。例如：二维数组可以看做是由列向量组成的线性表。二维数组可以看做是由列向量组成的线性表。35.1 多维数组多维数组n 构造特性构造特性n 例：二维数组例：二维数组n ，它属

2、于两个向量；，它属于两个向量；i th行和行和j th列。列。n 除边境外，每个除边境外，每个aij恰有两个直接前驱和恰有两个直接前驱和两个直两个直n 接后继。接后继。111212122212nnmnmmmnaaaaaaAaaaijmnaA45.1 多维数组多维数组n 非线性特征ni th行：前驱aij-1，后继aij+1nj th列：前驱ai-1j，后继ai-1jn仅有一个开场结点：a11n仅有一个终端节点：amnn其他边境上的结点只需一个直接前驱或一个直接后继，类似的m维数组 的每一个元素都属于m个向量。1 2mnnnA55.1 多维数组多维数组n 存储n普通均采用顺序方式存储，缘由是构造

3、中的结点不变动，内存是一维的，必需将多维数组线性化。n 行优先行主序方式：n将(i+1)th行向量紧接在i th行向量之后：n特点：列下标变化快。Pascal、C等均是此方法。先排最右下标多维。11 12121 22212 , , , nnmmmna aaa aaa aa65.1 多维数组多维数组v 列优先列主序方法v特点行下标变化最快，先排最左下标可推行至多维。Fortan是用此方法。v 地址计算v 一维存储地址内部实现。v 基地址开场结点存储地址Loc(a11).v 维数每维的上下界假设下界固定，那么只须知道维长度v 每个元素占用的单元数元素大小：L11 21112 22212 , , ,

4、 mmnnmna aaa aaa aa i ja 75.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)=Loc(a00)+in+j LmnAmnA85.1 多维数组多维数组n多维推行：以C为例，行主序。n思索：Ac1.d1 , c2.d2nLoc(aij)=Loc(ac1c2)+(i-c1) (d2-c2+1)+(j-c2) Ln i th行前

5、行数 第2维长度 i th行aij之前结点数n特点：随机存取。n1 2n12n0.1,0.1,0.1d ddAAadd1 2.00.0123231()()(.)nj jjnnnnnLoc aLoc ajdddjddjdjL 95.2 矩阵的紧缩存储矩阵的紧缩存储n用二维数组表示的特点：随机存取，存储密用二维数组表示的特点：随机存取，存储密度为度为1。但对特殊和稀疏矩阵的存储那么浪费。但对特殊和稀疏矩阵的存储那么浪费空间，尤其是大规模科学与工程计算。空间，尤其是大规模科学与工程计算。n5.2.1 特殊矩阵特殊矩阵n有规律：紧缩后可找到地址变换公式，坚持有规律：紧缩后可找到地址变换公式，坚持随机存

6、取功能。随机存取功能。重复元素分布有规律零元素105.2 矩阵的紧缩存储矩阵的紧缩存储n对称阵对称阵n n阶方阵阶方阵A，假设，假设 那么称那么称A为对称阵。为对称阵。n由于矩阵元素关于主对角线对称，故只存上由于矩阵元素关于主对角线对称，故只存上三角或三角或n下三角元素即可，节约近一半空间。下三角元素即可，节约近一半空间。n不失普通性，存储下三角包括主对角线，不失普通性，存储下三角包括主对角线，以行以行n主序存储：主序存储：n元素个数元素个数 0,1,ijjiaai jn10(1)(1)/2niin n115.2 矩阵的紧缩存储矩阵的紧缩存储n紧缩存储：紧缩存储：n将其存于向量将其存于向量sa

7、0.n(n+1)/21中。中。n如何访问如何访问aij？必需将其与？必需将其与sak的对应关系找的对应关系找出来。出来。n地址计算：地址计算：n下三角中有下三角中有j i.naij之前有之前有i行行0 i-1nnn第第i行上行上aij之前元素个数为之前元素个数为j(0 j-1).n 10(1)(1)/2itti i元素个数(1)/2ki ij125.2 矩阵的紧缩存储矩阵的紧缩存储n上三角中有i jn ,只需交换上式的j和i即可得：n令I=max (i , j)，J=min (i , j)，那么k和i，j之关系可一致表示为：n三角矩阵n 紧缩方式同上，在sa中多添加一个单元：n sa0.n(n

8、+1)/2n 将C存于最后一个分量中。(1)/2kj jijiijaa(1)/2kI IJ135.2 矩阵的紧缩存储矩阵的紧缩存储n对角矩阵对角矩阵nn总结：这类矩阵紧缩存储后能找到地址计算总结：这类矩阵紧缩存储后能找到地址计算公式，使其坚持随机存取的功能。公式，使其坚持随机存取的功能。145.2 矩阵的紧缩存储矩阵的紧缩存储 5.2.2 稀疏矩阵稀疏矩阵定义：设定义：设Amn中有中有t个非零元素，假设个非零元素，假设 ，称，称A为为稀疏矩阵。稀疏矩阵。稀疏因子：稀疏因子： 普通非零元素分布无规律性普通非零元素分布无规律性紧缩存储：紧缩存储：只存储非零元，故须存储辅助信息，才干确只存储非零元，

9、故须存储辅助信息，才干确定其位置。定其位置。三元组三元组(i，j，aij)：行号，列号，非零元的：行号，列号，非零元的值独一确定一个非零元。值独一确定一个非零元。当用三元组表示非零元时，有两种紧缩方式：当用三元组表示非零元时，有两种紧缩方式：顺序和链式。顺序和链式。tmn0.05tm n155.2 矩阵的紧缩存储矩阵的紧缩存储n三元组顺序表三元组表三元组顺序表三元组表n以行主序或列主序的顺序存储非零元，以行主序或列主序的顺序存储非零元，跳过零元。得到一个其节点均是三元组的线性跳过零元。得到一个其节点均是三元组的线性表，称此顺序存储构造为三元组表。表，称此顺序存储构造为三元组表。n#define

10、 MaxSize 10000ntypedef int DataTypentypedef struct/三元组三元组nint i, j；nDataType v;nTripleNode;165.2 矩阵的紧缩存储矩阵的紧缩存储typedef struct/三元组表TripleNode dataMaxSize;int m, n, t; /行数，列数，非零元总数TripleTable;设a，b是TripleTable型变量。转置运算4 505008103000200060000A5 401065020030000008000BmnnmAB A ijB ji01,01imjn175.2 矩阵的紧缩存储矩

11、阵的紧缩存储4 505008103000200060000A5 401065020030000008000B185.2 矩阵的紧缩存储矩阵的紧缩存储v方法一：按方法一：按B的次序或按的次序或按A的列序转置。的列序转置。vA的列是的列是B的行，故按的行，故按A的列序转置，所得的列序转置，所得B是按行主序存放的。是按行主序存放的。v根本思想：对根本思想：对A中每列，从头至尾扫描中每列，从头至尾扫描a.data，找，找出一切列号为出一切列号为col的三元组的三元组(0coln-1)，将它们的，将它们的行、列号互换后依次放入行、列号互换后依次放入b.data，即可得行主序表，即可得行主序表示的示的B的

12、三元组。的三元组。v正确性：正确性：按按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

13、) /找A的列号为col的三元组 b.dataq.i = a.datap.j ; b.dataq.j = a.datap.i ; b.dataq.v = a.datap.v ; q+; 205.2 矩阵的紧缩存储矩阵的紧缩存储n方法二：按A的行序转置。n假设简单的变换a.data的行和列，那么b.data为列主序存储，要重排。但假设预先确定A中每一列即B中每一行的第一个非零元在b.data中应有的位置，那么可正确转置。n位置向量：00 /0 110.1potApot colpot colcolcolan的第 列起址第列非零元个数215.2 矩阵的紧缩存储矩阵的紧缩存储n思想n 先求出A中每一列

14、的非零元个数，可将第col列的非零元个数记入potcol+1中。nstep1：初始化将一切pot中元素清0. /O(n)nstep2：扫描a.data，将列号为col的非零元个数累加到potcol+1中。 /O(t)nstep3：令potcol=potcol-1+potcol 1cola.n-1/O(n)nstep4：扫描a.data，将(i,col,v)转置后放于b.datapotcol中，potcol+. /O(t)n时间O(n+t)，快速。nkey：pot1.a.n=第0a.n-1列的非零元个数。225.2 矩阵的紧缩存储矩阵的紧缩存储void FastTransMatrix(Tripl

15、eTable &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 ( 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无用，但第二个循环须

16、统计 potcol = potcol 1 + potcol;for ( p = 0; p a.t; p+) /step4 col = a.datap.j; /当前三元组列号. q = potcol+; b.dataq.i = a.datap.j; b.dataq.j = a.datap.i; b.dataq.v = a.datap.v;235.2 矩阵的紧缩存储矩阵的紧缩存储以上图为例，带行表的三元组表。顺序方式在行优先存储的三元组表中，参与一个行表来记录稀疏矩阵紧缩后每行非零元在三元组表中的起始位置。4 5A245.2 矩阵的紧缩存储矩阵的紧缩存储v十字链表v上两种方式是顺序存储，假设非零元

17、位置或个数经常发生变化，会引起结点挪动，效率降低。此时宜用链式存储。v例：AA+Bv稀疏矩阵的链接存储方式有多种，这里仅引见十字链表v结点构造vv存储构造v分别设两个指针数组作为各行、列单链表的头指针。255.2 矩阵的紧缩存储矩阵的紧缩存储typedef struct CLNodeint i, j ;DataType v;struct CLNode * right, *down;CLNode;typedef struct CLNode *rheadMaxRow; /行链表头指针，MaxRow在前定义CLNode *cheadMaxCol; /列int m,n, t;CrossList;Cro

18、ssList A;265.2 矩阵的紧缩存储矩阵的紧缩存储275.3 广义表广义表Lists概念概念是线性表的推行，如将线性表中元素是线性表的推行，如将线性表中元素ai放宽到可放宽到可以是本身的构造。以是本身的构造。定义：定义： ，它由，它由n个元素构成的有限个元素构成的有限序列，其中序列，其中ai或是原子，或是广义表子表。或是原子，或是广义表子表。LS-名字，名字，n-长度，长度，n=0为空表。为空表。普通用小写字母表示原子，大写字母表示子表。普通用小写字母表示原子，大写字母表示子表。表头、表尾、深度表头、表尾、深度假设假设 ，那么，那么a1成为表头首，剩余元素成为表头首，剩余元素构成的表构

19、成的表 为表尾。广义表是递归定义的，展开到每为表尾。广义表是递归定义的，展开到每一元素均为原子时括号的最大层数为深度。一元素均为原子时括号的最大层数为深度。 12( ,),0nLSa aanLS 2(,)naa285.3 广义表广义表Listsn例：例：nE=( ) 空表，长度空表，长度n = 0，深度，深度d = 1.nL=(a, b) n = 2，d = 1. 线性表线性表nA=(x, L)=(x, (a, b) n=2, d=2. a1为原子，为原子，a2为子为子表表nB=(A, y)=(x, (a, b), y) n = 2, d = 3.nC=(A, B)=(x, (a, b), (

20、x, (a, b), y) n = 2, d = 4.nD=(a, D)=(a, (a, (a, () n = 2, d = .n假设规定任何表都有名字，那么可在每个表前冠名。假设规定任何表都有名字，那么可在每个表前冠名。nE( ) L(a, b) A(x, L(a, b)295.3 广义表广义表Listsn图示n各种表之关系n递归表再入表纯表线性表305.3 广义表广义表Listsn运算n求表头、表尾。nhead(A) = x, tail(A) = (a, b) /表尾是表，表头不一定nhead(tail(A) = (a, b) 表nNote： 和 不同。n 为空表n=0，不能求表头和表尾。

21、n 为非空表，n=1. 可求表头和尾：n head( head( tail(A) = atail( head( tail(A) = (b) 原子表head( tail( head( tail(A) = btail( tail( head( tail(A) = ( ) 原子表( )( )( )( )head ( ) ( ), tail ( ) ( )315.3 广义表广义表Listsn存储构造n由于广义表数据元素可具有不同构造，故难以用顺序方式存储。普通用链接方式存储，称之为广义链表。n广义表的头尾链表表示方法。n表结点：n原子结点：n存储构造见书上阐明1hptptag0atom表结点，使用和原

22、子结点，使用325.3 广义表广义表Listsn图示nE=NIL335.3 广义表广义表Listsn特点n除空表的表头指针为空外，头指针均指向表结点。n任一表结点的hp均指向表头部原子结点或表结点n任一表结点的tp均指向表尾部当表尾部为空表时，tp=NIL，否那么必指向表结点n易分清表中原子和子表所在层次。n如x、L在第一层，a、b在第二层。n最高层的表结点数即为广义表的长度。n浪费空间，易求表长和表深度。345.3 广义表广义表Lists(2) 单链表示法模拟线性表的单链表构造，当一切元素为原子时，等价于单链表。结点构造：图示：E=NILC=(A, B)=(x, (a, b), (x, (a, b), y) =(A(x, L(a, b), B(A(x, L(a, b), y)0slinkatom1data 本结点为子表（指向子表的第一个结点）本结点为原子（）355.3 广义表广义表Listsn存储构造阐明ntypedef struct GLNodenint atom; /