多维数组矩阵和广义表

1、中国水利水电出版社中国水利水电出版社1 Data Structures: Chapter 5中国水利水电出版社中国水利水电出版社2 Data Structures: Chapter 55.1 多维多维数组数组5.3 稀疏矩阵稀疏矩阵5.2 特殊矩阵特殊矩阵5.4 广义表广义表中国水利水电出版社中国水利水电出版社3 Data Structures: Chapter 5二维数组的特点二维数组的特点：一维数组的特点：一维数组的特点：1 1个下标，个下标，a ai i 是是a ai+1i+1的直接前驱的直接前驱2 2个下标，个下标，每个元素每个元素ai,j 受到两个关系受到两个关系（行行关系关系和和列

2、列关系）的约束：关系）的约束：一个一个 mn 的二维数组可以的二维数组可以看成是看成是m 行行的一维数组，或的一维数组，或者是者是 n 列列的一维数组。的一维数组。N 维数组的特点：维数组的特点：n n 个下标，个下标，每个元素受到每个元素受到 n n 个关系约束个关系约束一个一个 n 维数组可以看成是维数组可以看成是由若干个由若干个 n-1 维数组组成的线性表。维数组组成的线性表。 a11 a12 a1n a21 a22 a2n am1 am2 amn Amn=5.1 多维数组多维数组中国水利水电出版社中国水利水电出版社4 Data Structures: Chapter 55.1.1 5.

3、1.1 数组的定义数组的定义二维数组数据对象二维数组数据对象: : D = aij | 0ib1-1, 0 jb2-1 二维数组数据关系二维数组数据关系: : R = ROW, COL ROW= | 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-2b1= mb2= n中国水利水电出版社中国水利水电出版社5 Data Structures: Chapter 5抽象数据类型多维数组的定义抽象数据类型多维数组的定义ADT Array 数据对象数据对象： Daj 1j 2, ., j i., j n| ji = 0,.,bi -1, i =1,2, .,n 数据关系数据关系

4、： R R1, R2, ., Rn Ri | 0 jk bk -1, 1 k n 且 k i, 0 ji bi -2, i =1,.,n 基本操作基本操作:中国水利水电出版社中国水利水电出版社6 Data Structures: Chapter 51. 构造多维数组构造多维数组InitArray(&A, n, bound1, ., boundn)操作结果：操作结果： 若维数 n 和各维长度合法，则构造相应的数组 A，并返回OK。基本操作基本操作:中国水利水电出版社中国水利水电出版社7 Data Structures: Chapter 5 2. 销毁数组销毁数组 DestroyArray

5、(&A) 操作结果：操作结果：释放数组 A。中国水利水电出版社中国水利水电出版社8 Data Structures: Chapter 5 3. 将数组将数组 A的的某元素的值某元素的值赋给变量赋给变量e Value ( A, &e, index1, ., indexn) 初始条件：初始条件：A 是 n 维数组，e为元素变量， 随后是n 个下标值。 操作结果：操作结果：若各下标不超界，则 e 赋值为 所指定的A 的元素值，并返回OK。中国水利水电出版社中国水利水电出版社9 Data Structures: Chapter 5 4. 为数组为数组A的某元素赋值的某元素赋值 Assi

6、gn(&A, e, index1, ., indexn) 初始条件：初始条件：A 是 n 维数组，e为元素变量， 随后是n 个下标值。 操作结果：操作结果：若下标不超界，则将e的值赋 给所指定的A的元素，并返回OK。中国水利水电出版社中国水利水电出版社10 Data Structures: Chapter 55.1.2 数组的存储表示数组的存储表示类型特点类型特点:(1) 一般不做插入、删除操作; 数组是多维的结构，而存储空间是 (2) 一维的结构。 有两种顺序映象的方式有两种顺序映象的方式: (1) 以行序为主序(低位下标优先); (2) 以列序为主序(高位下标优先);中国水利水电出

7、版社中国水利水电出版社11 Data Structures: Chapter 5例如：例如： 称为基地址基地址或基址基址。以以“行序为主序行序为主序”的存储映象的存储映象 二维数组A中任一元素aij 的存储位置 LOC( i, j ) = LOC(0,0) + ( 3ij )a01a00a02a10a11a12a01a00a02a10a11a12d d 中国水利水电出版社中国水利水电出版社12 Data Structures: Chapter 5 设二维数组设二维数组 A 具有具有m 行行 n列列, 借助矩阵形式给出如下：借助矩阵形式给出如下：以以行行为主序的存储方式：为主序的存储方式：a0

8、00 0 a0 01 1 a0 0n-1-1 a1 10 0 a1 11 1 a1 1n-1-1 am-1-10 0 am-1-11 1 am-1-1n-1-10 1 n-1 n n+1 2n-1 mn-1Am n= =a00 a01 a0 n-1a10 a11 a1 n-1 am-1 0 am-1 1 am-1 n-1以以列列为主序的方式：为主序的方式：a0 00 0 a1 10 0 am-1-10 0 a0 01 1 a1 11 1 am-1-11 1 a0 0n-1-1 a1 1n-1-1 am-1-1n-1-1 0 1 m-1 m m+1 2m-1 nm-1中国水利水电出版社中国水利水

9、电出版社13 Data Structures: Chapter 5 数组元素存储地址的计算数组元素存储地址的计算 假设二维数组假设二维数组 A m n 每个每个元素元素占用占用 d 个存储单元，个存储单元， Loc( i,j )为元素为元素aij 的存储地址，的存储地址，Loc( 0,0 ) 是是 a00 存储位存储位置置, 也是二维数组也是二维数组A的的基址基址。 若以若以行序为主序行序为主序的方式存储二维数组，则元素的方式存储二维数组，则元素aij 的存储位置可由下式确定：的存储位置可由下式确定： Loc ( i, j ) = Loc( 0, 0 ) + ( n i+j ) d 若以若以列

10、序为主序列序为主序的方式存储二维数组，则元素的方式存储二维数组，则元素aij 的的存储位置可由下式确定：存储位置可由下式确定： Loc( i, j ) = Loc ( 0, 0 ) +（m j+i ) d中国水利水电出版社中国水利水电出版社14 Data Structures: Chapter 5 数组元素存储地址的计算数组元素存储地址的计算 假设三维数组假设三维数组 A s m n每个每个元素元素占用占用 d 个存储单元，个存储单元， Loc( i,j,k )为元素为元素aijk 的存储地址，的存储地址，Loc( 0,0,0 ) 是元素是元素 a000的存储位置的存储位置, 也是三维数组也是

11、三维数组 A的的基址基址。 若以若以行序为主序行序为主序的方式存储三维数组，则元素的方式存储三维数组，则元素aijk 的存储位置可由下式确定：的存储位置可由下式确定： Loc ( i, j,k) = Loc( 0, 0 ,0 ) + ( m n i+ n j + k ) d中国水利水电出版社中国水利水电出版社15 Data Structures: Chapter 5 无论规定无论规定行优先行优先或或列优先列优先，只要知道以下，只要知道以下3 3要素，便可随时求出任一元素的地址要素，便可随时求出任一元素的地址。这样数组中的任一元素便可以这样数组中的任一元素便可以随机存取！随机存取！ 开始结点的存

12、放地址（即开始结点的存放地址（即基地址基地址） 维数维数和和每维的每维的上、下上、下界；界； 每个数组元素所占用的每个数组元素所占用的存储单元数存储单元数Am n= =a00 a01 a0 n-1a10 a11 a1 n-1 am-1 0 am-1 1 am-1 n-1中国水利水电出版社中国水利水电出版社16 Data Structures: Chapter 5LOC ( j1, j2, , jn ) = LOC ( 0, 0, , 0 )若是若是n 维数组维数组，其中任一元素的，其中任一元素的地址地址该如何计算？该如何计算？niii1jC其中：其中：Cn=d, Ci-1= biCi ， 1

13、in一个元素一个元素 的长度的长度 数组基址数组基址前面若干元素占用的前面若干元素占用的 地址字节地址字节总数总数第第i i维长度维长度与所存元素与所存元素个数个数有关的有关的系数系数，可用可用递推法递推法求出求出 教材已给出教材已给出低维低维( (行优先行优先) )优先优先的地址计算公式。的地址计算公式。 见见 （5-35-3）式）式, ,该式称为该式称为 n 维数组的维数组的映像函数映像函数。中国水利水电出版社中国水利水电出版社17 Data Structures: Chapter 5#define MaxArrayDim 8 / 假设最大假设最大维数维数为为8 typedef struc

14、t ELemType *base; / 数组元素数组元素基址基址 int dim; / 数组的数组的维数维数 int *bound; / 数组数组各维长度各维长度bi的的保存数组保存数组基址基址 int *constants; / 地址函数地址函数常量常量Ci的的保存数组保存数组基址基址 Array;n 维数组维数组的顺序存储表示的顺序存储表示中国水利水电出版社中国水利水电出版社18 Data Structures: Chapter 5 5.2 特殊矩阵特殊矩阵 非零非零元素元素或或零零元素的分布有一定规律的矩阵。元素的分布有一定规律的矩阵。 1. 对称矩阵对称矩阵 在一个在一个 n 阶方阵阶

15、方阵A中，若元素满足下述性质：中，若元素满足下述性质： aij = aji 1i, jn 则称则称 A 为为对称矩阵。对称矩阵。 只要存储矩阵中只要存储矩阵中上三角上三角或或下三角下三角中的元素，让中的元素，让每两个对称的元素共享一个存储空间，这样，能节每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。约近一半的存储空间。中国水利水电出版社中国水利水电出版社19 Data Structures: Chapter 5 i ( i -1) / 2 + j-1 当当 i j j ( j -1) / 2 + i-1 当当 i j a11 a21 a22 a31 a32 a33 an, n

16、注：注：aij = aji中国水利水电出版社中国水利水电出版社20 Data Structures: Chapter 5中国水利水电出版社中国水利水电出版社21 Data Structures: Chapter 5中国水利水电出版社中国水利水电出版社22 Data Structures: Chapter 5中国水利水电出版社中国水利水电出版社23 Data Structures: Chapter 5 假设假设 m 行行 n 列列的矩阵含的矩阵含 t 个非零元个非零元素素，则称表达式，则称表达式的值为的值为稀疏因子。稀疏因子。 通常认为通常认为: 0.05 的矩阵为的矩阵为稀疏矩阵稀疏矩阵。nm

17、t5.3 稀疏矩阵稀疏矩阵中国水利水电出版社中国水利水电出版社24 Data Structures: Chapter 57600070015000001800000240001400003000000000009120M中国水利水电出版社中国水利水电出版社25 Data Structures: Chapter 5 以常规方法二维数组来表示高阶的稀疏矩阵时有以下问题问题:(1) 零值元素零值元素占了很大空间占了很大空间;(2) 计算中进行了很多和计算中进行了很多和零值零值的运算，的运算， 遇遇除法除法，还需判别，还需判别除数除数是否为是否为零零。中国水利水电出版社中国水利水电出版社26 Data

18、 Structures: Chapter 5(1) 尽可能尽可能少存少存或或不存不存零零值元素值元素;解决问题的原则解决问题的原则:(2) 尽可能尽可能减少减少没有实际意义的没有实际意义的运算运算;(3) 操作方便操作方便; 如如: 能尽可能快地能尽可能快地找到找到 与下标值与下标值 (i, j) 对应的对应的元素元素; 能尽可能快地能尽可能快地找到找到 同一行同一行或或同一列的同一列的非零值元非零值元;中国水利水电出版社中国水利水电出版社27 Data Structures: Chapter 5(1) 特殊特殊矩阵矩阵 非零元非零元在矩阵中的分布有一定规则. 例如：对称矩阵、三角矩阵。(2)

19、 随机随机稀疏矩阵稀疏矩阵 非零元非零元在矩阵中随机随机出现。有两类矩阵适合有两类矩阵适合压缩存储压缩存储：中国水利水电出版社中国水利水电出版社28 Data Structures: Chapter 57600070015000001800000240001400003000000000009120M中国水利水电出版社中国水利水电出版社29 Data Structures: Chapter 5例如：例如： M 的存储，的存储，由由矩阵的行列数矩阵的行列数（6,76,7）和）和三元组表三元组表: : ( (1,2,(1,2,1212),(1,3,),(1,3,9 9),(3,1,),(3,1,-

20、3-3),(3,6,),(3,6,1414),), (4,3, (4,3,2424),(5,2,),(5,2,1818), (6,1,), (6,1,1515), (6,4,), (6,4,-7-7) )）惟一确定。惟一确定。7600070015000001800000240001400003000000000009120M存储原则：存储原则：只存矩阵的只存矩阵的行、列数行、列数和每个和每个非零元非零元的的行、列行、列下标下标及其及其值值。称为称为三元组三元组中国水利水电出版社中国水利水电出版社30 Data Structures: Chapter 5 对对稀疏矩阵稀疏矩阵三元组表三元组表的不

21、同的存储的不同的存储方法，对应方法，对应稀疏矩阵稀疏矩阵不同的不同的压缩存储压缩存储方方法。常见的有：法。常见的有：一、三元组顺序表一、三元组顺序表二、二、 十字链表十字链表中国水利水电出版社中国水利水电出版社31 Data Structures: Chapter 5 #define MaxSize 100 typedef struct int i, j ; / 该非零元的该非零元的行下标行下标和和列下标列下标 ElemType e; / 该非零元的该非零元的值值 Triple; / 三元组类型三元组类型 一、三元组顺序表一、三元组顺序表typedef struct Triple data M

22、axSize + 1; / 0号单元不用号单元不用 int mu, nu, tu; / 行数行数, 列数列数, 非非 0 元个数元个数. TSMatrix; / 稀疏矩阵类型稀疏矩阵类型中国水利水电出版社中国水利水电出版社32 Data Structures: Chapter 5 M M的的三元组三元组顺序表图示顺序表图示 M = 0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0 设设M是是TSMatrix 类型的结构变量，类型的结构变量，则则M有有4 个域，其中

23、个域，其中M.data用于存储矩用于存储矩阵阵M的三元组表，的三元组表，如右图所示如右图所示: i j e0123456783 1 -36 1 151 2 125 2 181 3 94 3 246 4 -73 6 14M.data678M.muM.nuM.tu按按行序行序有有序序中国水利水电出版社中国水利水电出版社33 Data Structures: Chapter 5矩阵的运算矩阵的运算 如何求如何求转置矩阵？转置矩阵？028003600070500140005280000007143600矩阵MM的转置矩阵T中国水利水电出版社中国水利水电出版社34 Data Structures: Ch

24、apter 5028003600070500140005280000007143600M =T =3553 i j e0123452 2 -71 2 141 5 -53 4 283 1 36 i j e0123452 2 -72 1 145 1 -54 3 281 3 36 i j e0123452 2 -71 3 362 1 145 1 -54 3 28M.dataT.dataT.data ?中国水利水电出版社中国水利水电出版社35 Data Structures: Chapter 5用常规的二维数组表示时的算法 其时间复杂度为其时间复杂度为: O( nm ) for (col=1; col

25、=n; +col) for (row=1; row=m; +row) Tcolrow = Mrowcol;列列 数数行行 数数中国水利水电出版社中国水利水电出版社36 Data Structures: Chapter 5 矩阵转置算法矩阵转置算法 算法算法5.6 基本思想基本思想: : 对三元组表的对三元组表的 M.data 从头至尾扫描：从头至尾扫描： 第第 1 次扫描时，将次扫描时，将M.data中所有中所有列号为列号为 1 的三元的三元 组赋值到组赋值到T.data中；中； 第第 2 次扫描时，将次扫描时，将M.data中所有中所有列号为列号为 2 的三元的三元 组赋值到组赋值到T.da

26、ta中；中； 依此类推依此类推，直至，直至 第第 M.nu 次扫描，将次扫描，将 M.data中所有所有中所有所有列号为列号为 n 的三元组赋值到的三元组赋值到T.data中。中。中国水利水电出版社中国水利水电出版社37 Data Structures: Chapter 5用用“三元组三元组”表示时，实现矩阵转置。表示时，实现矩阵转置。1 2 151 5 -52 2 -73 1 363 4 282 1 155 1 -52 2 -71 3 364 3 28M.dataT.data算法算法 5.6（P.101）图示图示中国水利水电出版社中国水利水电出版社38 Data Structures: Ch

27、apter 5 int TransposeSMatrix ( TSMatrix a, TSMatrix &b ） / 采用三元组表存储表示，求稀疏矩阵采用三元组表存储表示，求稀疏矩阵 A 的转置矩阵的转置矩阵 B int p, q, col; b.mu = a.nu; b.nu = a.mu; b.tu = a.tu; if ( b.tu ) return OK; / TransposeSMatrix 算法算法5.6 求矩阵求矩阵A的转置矩阵的转置矩阵BP.101 中国水利水电出版社中国水利水电出版社39 Data Structures: Chapter 5 int Transpose

28、SMatrix ( TSMatrix a, TSMatrix &b ) if ( b.tu ) q = 1; / q 表示表示 b.data 中元素的下标中元素的下标 for ( col = 1; col = a.nu; +col ) / 按列序求转置按列序求转置 for ( p = 1; p = a.tu; +p ) / p 遍历遍历 a.data 中所有三元组中所有三元组 if ( a.datap.j = = col ) b.dataq.i = a.datap.j; b.dataq.j = a.datap.i; b.dataq.e = a.datap.e; +q; 算法算法5.6

29、求矩阵求矩阵A的转置矩阵的转置矩阵B-P.101 中国水利水电出版社中国水利水电出版社40 Data Structures: Chapter 5用三元组表示，实现矩阵用三元组表示，实现矩阵快速转置。快速转置。1 2 151 5 -52 2 -73 1 363 4 282 1 155 1 -52 2 -71 3 364 3 28算法算法 5.7（P.102）图示图示12345中国水利水电出版社中国水利水电出版社41 Data Structures: Chapter 5快速转置算法思想：快速转置算法思想： 为了求得为了求得 M.data 各列各列第第 1 1 个个三元组三元组在在 T.data中的

30、位置中的位置, , 设置两个辅助向量设置两个辅助向量 : : num 、cpos 。 num col ：存储第：存储第col 列列非零元个数。非零元个数。 cpos col ：存储第：存储第col 列列第第 1 个个三元组三元组在在T.data中的位置。中的位置。 cpos col 的计算方法是：的计算方法是： cpos 1 =1 cpos col =cposcol-1+numcol-1 ， 2 col ncolnumcolcpotcol1234567 22811001352784539上一列上一列的起始的起始位置位置上一列上一列非零元非零元个数个数中国水利水电出版社中国水利水电出版社42 D

31、ata Structures: Chapter 5 快速转置算法主要步骤：快速转置算法主要步骤：1.1.求求 M 中各列中各列非零元非零元个数，在于个数，在于 num 数组数组;2.2.求求 M 中各列中各列第第 1 个非零元个非零元在在T.data中的下标中的下标 cpos .3.3.对对 M.data 进行进行 1 次扫描，次扫描， 遇到遇到 col 列的列的第第 1 个个三三 元组元组时，按时，按 cposcol 的位置，将其放至的位置，将其放至T.data 中，中， 当再次遇到当再次遇到 col 列的列的三元组三元组时，只须顺序放到时，只须顺序放到T.data 中中col列元素的后面。

32、列元素的后面。中国水利水电出版社中国水利水电出版社43 Data Structures: Chapter 51 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j e 1 2 3 4 5 6 7 8a.datai j e 1 2 3 4 5 6 7 8b.datacolnumcolcpotcol1122323524715806817901 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 pppppppp4629753快速转快速转置算法置算法图示图示：中国水利水电出版社中国水利

33、水电出版社44 Data Structures: Chapter 5 分析算法分析算法FastTransposeTSMatrix的时间复杂度：的时间复杂度：时间复杂度为时间复杂度为: : O( M.nu+M.tu) for ( col=1; col=M.nu; +col ) for ( t=1; t=M.tu; +t ) for ( col=2; col=M.nu; +col ) for ( p=1; p=M.tu; +p ) 中国水利水电出版社中国水利水电出版社45 Data Structures: Chapter 5二、二、 十字链表十字链表稀疏矩阵的链式存储稀疏矩阵的链式存储设设行行指针

34、数组和指针数组和列列指针数组，分别指向指针数组，分别指向每行、每列的第每行、每列的第 1 个个非零元非零元结点。结点。用途：用途：方便稀疏矩阵的方便稀疏矩阵的加减加减运算。运算。方法：方法：每个每个非非 0 元素用元素用 5 个域组成的结点表示个域组成的结点表示.中国水利水电出版社中国水利水电出版社46 Data Structures: Chapter 5 十字链表的特点：十字链表的特点：（1）每每行行非零元素非零元素链接成一个链接成一个行行链表；链表； 每每列列非零元素非零元素链接成一个链接成一个列列链表。链表。（2）每个）每个非零元素非零元素既是既是行行链表中的一个结点链表中的一个结点,

35、又是又是列列链表中的一个结点。链表中的一个结点。 即结构成即结构成呈呈十字链状。十字链状。中国水利水电出版社中国水利水电出版社47 Data Structures: Chapter 5typedef struct / 十字链表结点十字链表结点结构结构 int row, col ; / 该非零元的行和列下标该非零元的行和列下标 ElemType v; / 非零元素值非零元素值 struct OLNode *right, *down; / 该非零元所在该非零元所在 OLNode, *OLink; / 行行表和表和列列表的后继链域表的后继链域typedef struct / 十字链表十字链表结构结构

36、 Olink *rhead, *chead; / 行列行列链表链表头指针头指针向量基址向量基址 int mu,nu,tu; / 稀疏矩阵的稀疏矩阵的行列数行列数和和非零元个数非零元个数 CrossList;十字链表类型定义十字链表类型定义中国水利水电出版社中国水利水电出版社48 Data Structures: Chapter 5十字链表十字链表结点结点示意：示意：right downvcolrow同一列中下一非同一列中下一非 零元素的指针零元素的指针同一行中下一非同一行中下一非 零元素的指针零元素的指针 chead rhead mu 行数 nu 列数 tu十字链表十字链表结构示意：结构示意：

37、非零元个数非零元个数中国水利水电出版社中国水利水电出版社49 Data Structures: Chapter 5 chead rhead 行数 列数 非零元个数 M 5 4 5 0 1 2 3 4 0 1 2 3 4 5 1 1 3 1 4 7 5 4 8 2 3 1 3 1 2 3 0 0 7 0 0 1 0 2 0 0 0 0 0 0 0 0 0 0 8 ( (a a) ) 矩矩阵阵A A ( (b b) ) 稀稀疏疏矩矩阵阵A A 的的十十字字链链表表 A= 十字链表示例：十字链表示例：中国水利水电出版社中国水利水电出版社50 Data Structures: Chapter 55.4

38、 广义表广义表广义表广义表是线性表的推广，也称为是线性表的推广，也称为列表列表（lists）记为记为： LS = ( a1 , a2 , ， an ) 广义表名广义表名 表头表头(Head） 表尾表尾 (Tail)1. 概念概念 第第 1 个个元素是元素是表头表头，而，而其余其余元素组成的表元素组成的表称为称为表尾表尾； 用用小写小写字母表示字母表示原子原子类型，用类型，用大写大写字母表示字母表示列表列表。n是表长是表长 在广义表中约定：在广义表中约定： 广义表广义表与与线性表线性表的区别和联系？的区别和联系？ 广义表中广义表中元素元素既可以是既可以是原子原子类型，类型，也可以是也可以是列表列

39、表； 当每个元素都为当每个元素都为原子原子且且类型类型相同时，就是相同时，就是线性表线性表。( a2 , ， an )单个元素单个元素中国水利水电出版社中国水利水电出版社51 Data Structures: Chapter 52. 特点特点 有次序性有次序性 有长度有长度 有深度有深度 可递归可递归 可共享可共享一个直接前驱一个直接前驱和和一个直接后继一个直接后继定义为表中定义为表中最外层最外层包含的包含的元素个数元素个数为表中为表中括号括号的的重数重数。原子原子深度为深度为0，空表空表深度为深度为1广义表广义表可以作为可以作为自己自己的的子表子表。长度有限。长度有限, ,深度无穷深度无穷广

40、义表广义表可以为可以为其他广义表其他广义表所共享。所共享。注意：注意： 任何一个非空表，表头可能是任何一个非空表，表头可能是原子原子，也可能是，也可能是列表列表；但；但表尾表尾一定是一定是列表列表。中国水利水电出版社中国水利水电出版社52 Data Structures: Chapter 5 E=(a,E)=(a,(a,E)= (a,(a,(a,.) E为为递归表递归表(1) A = ( )(2) B = ( e ) (3) C = ( a ,( b , c , d ) ) (4) D = ( A , B ,C )(5) E = ( a, E )例例 1：求下列求下列广义表广义表的长度的长度

41、n、深度深度 h 。n=0，因为因为A 是是空表。空表。h=1n=1，表中元素，表中元素 e 是原子。是原子。h=1n=2，a 为原子为原子,( b,c,d )为子表为子表. h=2n=3，3 个元素都是个元素都是子表子表。h=3n=2，a 为原子，为原子，E为为子表。子表。h=D=(A,B,C)=( ),(e),(a,(b,c,d) 共享表共享表中国水利水电出版社中国水利水电出版社53 Data Structures: Chapter 5ABDCeabcd A=( a , ( b, A ) )例例2：试用试用图形图形表示下列表示下列广义表广义表。 设设 代表代表原子原子， 代表代表子表子表。

42、 D=( A,B,C )=( ( ),(e),( a, ( b,c,d ) ) )Aab的长度为的长度为3，深度为，深度为3的长度为的长度为2，深度为，深度为深度深度最大最大括号括号的的重数重数 结点的结点的层数层数中国水利水电出版社中国水利水电出版社54 Data Structures: Chapter 5ADT Glist 数据对象：数据对象： D ei | i =1,2,n; n0; eiAtomSet 或或 eiGList, AtomSet 为某个数据对象集为某个数据对象集 数据关系：数据关系： LR | ei-1 ,eiD, 2in 基本操作：基本操作： ADT Glist3.广义表

43、的广义表的抽象数据类型定义抽象数据类型定义中国水利水电出版社中国水利水电出版社55 Data Structures: Chapter 5两种最两种最基本的操作基本的操作： GetHead( L)取表头取表头（可能是（可能是原子原子或或列表列表） GetTail( L ) 取表尾取表尾（一定是（一定是列表列表） 。中国水利水电出版社中国水利水电出版社56 Data Structures: Chapter 51. GetTail ( b, k, p, h ) ; 2. GetHead ( (a, b), (c, d) ) ; 3. GetTail ( (a, b), (c, d ) ) ; 4.

44、GetTail(GetHead (a, b),(c, d ) ;例例3 3：求下列求下列广义表广义表的操作结果。的操作结果。( k, p, h )( b )(a, b)5. GetTail ( e ) ; 6. GetHead( ( ) ) ;7. GetTail ( ( ) ) ;( )( a, b )( )( )( ( c, d ) )表尾表尾定定是是列表列表中国水利水电出版社中国水利水电出版社57 Data Structures: Chapter 5 广义表的存储结构广义表的存储结构 由于广义表的元素可以是由于广义表的元素可以是原子原子或或列表列表，所，所以通常采用以通常采用链式存储结构链式存储结构，每个，每个元素元素用一个用一个结结点点表示。表示。表示原子表示原子 atom tag=0 标志域 值域tp atom tag=0 标志域 值域 指向下一 个结点法法2 2：扩展链表扩展链表表示表示法法1 1：头尾链表头尾链表表示表示中国水利水电出版社中国水利水电出版社5