版本第5章数组和广义表

1、第五章 数组和广义表5.1 数组的类型定义数组的类型定义5.3 矩阵的压缩存储矩阵的压缩存储 5.2 数组的顺序表示和实现数组的顺序表示和实现5.4 广义表的类型定义广义表的类型定义5.5 广义表的存储结构广义表的存储结构学习提要：学习提要： 1.了解数组的两种存储表示方法，并掌握了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方数组在以行为主的存储结构中的地址计算方法。法。 2.掌握对特殊矩阵进行压缩存储时的下标掌握对特殊矩阵进行压缩存储时的下标变换公式。变换公式。 3.了解稀疏矩阵的两种压缩存储方法的特了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀

2、疏矩阵点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。时进行矩阵运算采用的处理方法。 4.掌握广义表的结构特点及其存储表示方掌握广义表的结构特点及其存储表示方法。法。ADT Array 数据对象数据对象： Daj1,j2, .,ji,jn| ji =0,.,bi -1, i=1,2,.,n 数据关系数据关系： RR1, R2, ., Rn Ri | 0 jk bk -1, 1 k n 且k i, 0 ji bi -2, i=2,.,n ADT Array 基本操作基本操作:5.1 数组的类型定义数组的类型定义基本操作基本操作：InitArray(&A, n, bou

3、nd1, ., boundn)DestroyArray(&A)Value(A, &e, index1, ., indexn)Assign(&A, e, index1, ., indexn)InitArray(&A, n, bound1, ., boundn) 操作结果：操作结果：若维数若维数 n 和各维长度合法，和各维长度合法， 则构造相应的数组则构造相应的数组A，并，并 返回返回OK。DestroyArray(&A) 操作结果：操作结果：销毁数组销毁数组A。 Value(A, &e, index1, ., indexn) 初始条件：初始条件：A

4、是是n维数组，维数组，e为元素变量，为元素变量， 随后是随后是n 个下标值。个下标值。 操作结果：操作结果：若各下标不超界，则若各下标不超界，则e赋值为赋值为 所指定的所指定的A 的元素值，并返的元素值，并返 回回OK。 Assign(&A, e, index1, ., indexn) 初始条件：初始条件：A是是n维数组，维数组，e为元素为元素 变量，随后是变量，随后是n 个下标值。个下标值。 操作结果：操作结果：若下标不超界，则将若下标不超界，则将e的的 值赋给所指定的值赋给所指定的A的元的元 素，并返素，并返OK。二维数组的定义二维数组的定义:数据对象数据对象: : D = aij

5、 | 0ib1-1, 0 jb2-1数据关系数据关系: : R = ROW, COL ROW = | 0ib1-2, 0jb2-1 COL = | 0ib1-1, 0 jb2-2二维数组的定义二维数组的定义:111110111110100100.nmmmnnnmaaaaaaaaaA5.2 数组的顺序表示和实现数组的顺序表示和实现类型特点类型特点: （1） 只有引用型操作，没有加工型操作；只有引用型操作，没有加工型操作； （2） 数组是多维的结构，而存储空间是数组是多维的结构，而存储空间是 一个一维的结构。一个一维的结构。有两种顺序映象的方式有两种顺序映象的方式: （1）以行序为主序以行序为主序

6、 （2）以列序为主序以列序为主序 a00 a01 a0n-1 a10 a11 a1n-1 am-10 am-11 am-1n-1 . 按行序为主序存放按行序为主序存放 am-1n-1 . am-11 am-10 . a1n -1 . a11 a10 a0n-1 . a01 a0001n-1m*n-1nLOC(i,j) = LOC(0,0) + (nij)L 按列序为主序存放按列序为主序存放01m-1m*n-1m am-1n-1 . a1n-1 a0n-1 . am-11 . a11 a01 am-10 . a10 a00 a00 a01 . a0n-1 a10 a11 . a1n-1 am-1

7、0 am-11 am-1n-1 .LOC(i,j) = LOC(0,0) + (mji)L称为基地址基地址或基址以以“行序为主序行序为主序”的存储映象的存储映象:二维数组二维数组A中任一元素中任一元素ai,j 的存储位置的存储位置 LOC(i,j) = LOC(0,0) + (nij) L 以以“列序为主序列序为主序”的存储映象的存储映象:二维数组二维数组A中任一元素中任一元素ai,j 的存储位置的存储位置 LOC(i,j) = LOC(0,0) + (mji) L 例例5.1: 5.1: 若若 L=2, LOC1,1 = 1000L=2, LOC1,1 = 1000 LOC3,4 = LOC

8、1,1 + (5 LOC3,4 = LOC1,1 + (5* *(3-1)+4-1)(3-1)+4-1)* *L L = 1000 + 13 = 1000 + 13 * * 2 2 = 1026 = 1026一般地，若一般地，若LOC0,0 LOC0,0 为基地址为基地址: : LOCi,j = LOC0,0 + (nLOCi,j = LOC0,0 + (n* *i+j)i+j)* *L L (0=im, 0=jn, (0=im, 0=jn, 每个数据元素占每个数据元素占L L个存储单元个存储单元) )LOCi,j,k = LOC0,0,0 + (nLOCi,j,k = LOC0,0,0 +

9、(n* *h h* *i+ hi+ h* *j + k)j + k)* *L L(0=im, 0=jn, 0=kh, (0=im, 0=jn, 0=kh, 每个数据元素占每个数据元素占L L个存储单元个存储单元) ) a a11 a a12 a a13 a a14 a a15A A4x54x5 = a = a21 a a22 a a23 a a24 a a25 a a31 a a32 a a33 a a34 a a35 a a41 a a42 a a43 a a44 a a45推广到一般情况n维数组的行序为主序存储地址计算公式b b1 1,b,b2 2,.,b,.,bn n是是n n维的维界维

10、的维界, ,数组元素数组元素A(jA(j1 1,j,j2 2,.,j,.,jn n) )的存储位置为的存储位置为LOCjLOCj1 1,j,j2 2,.j,.jn n= LOC0,0,.,0 + (b= LOC0,0,.,0 + (b2 2* *b b3 3* * *b bn n* *j j1 1 + b + b3 3* * *b bn n* *j j2 2 + . + . + b + bn n* *j jn n-1-1 + j + jn )n )* *L L n-1 nn-1 n = LOC0,0,.,0 + ( = LOC0,0,.,0 + ( j ji i b bk + k + j jn

11、 n) )* *L L i=1 k=i+1i=1 k=i+1 例例: : 在在C C语言中语言中, ,设设 数组数组A5678A5678的首地址为的首地址为 2000, 2000, 每个元素占每个元素占2 2个字节个字节; ; 求元素求元素A3454A3454的地址的地址. . LOC3,4,5,4 = 2000 + (6 LOC3,4,5,4 = 2000 + (6* *7 7* *8 8* *3 + 73 + 7* *8 8* *4 + 84 + 8* *5 + 4)5 + 4)* *2 2 = 2000 + ( 336 = 2000 + ( 336* *3 + 563 + 56* *4

12、+ 84 + 8* *5 + 15 + 1* *4)4)* *2 2 = 2000 + (1008 + 224 + 40 + 4) = 2000 + (1008 + 224 + 40 + 4)* *2 = 45522 = 4552推广到一般情况，可得到推广到一般情况，可得到 n 维数组数据元素存储位置维数组数据元素存储位置的映象关系的映象关系 称为称为 n 维数组的维数组的映象函数映象函数。数组元素的存储位置是。数组元素的存储位置是其下标的线性函数。其下标的线性函数。其中其中 cn = L，ci-1 = bi ci , 1 i n。LOC(j1, j2, ., jn ) = LOC(0,0,.

13、,0) + ci ji i=1n列序为主序列序为主序: (FORTRAN): (FORTRAN)A Amxn= =(a(a11,a,a21,a,a31,.a,.am1),(a),(a12,a,a22,a,a32,.a,.am 2),.(a),.(a1n,a,a2n,a,a3n,.a,.amn) LOC1,1 LOC1,1 为基地址为基地址: : LOCi,j = LOC1,1 + (m LOCi,j = LOC1,1 + (m* *(j-1)+i-1)(j-1)+i-1)* *L L (1=i=m, 1=j=n, (1=i=m, 1=j=n, 每个数据元素占每个数据元素占L L个存储单元个存储

14、单元) )例例5.2: 5.2: 若若 L=2, LOC1,1 = 1000L=2, LOC1,1 = 1000LOC3,4 = LOC1,1 + (4LOC3,4 = LOC1,1 + (4* *(4-1)+3-1)(4-1)+3-1)* *L L = 1000 + 14 = 1000 + 14 * * 2 = 1028 2 = 1028LOC0,0 LOC0,0 为基地址为基地址: :LOCi,j = LOC0,0 + (mLOCi,j = LOC0,0 + (m* *j+i)j+i)* *L L (0=i=m, 0=j=n, (0=i=m, 0=j=n, 每个数据元素占每个数据元素占L

15、L个存储单元个存储单元) ) LOCi,j,k = LOC0,0,0 + (m LOCi,j,k = LOC0,0,0 + (m* *(n(n* *k)+j)+i) k)+j)+i) * *L La a11 a a12 a a13 a a14 a a15 a a21 a a22 a a23 a a24 a a25 a a31 a a32 a a33 a a34 a a35 a a41 a a42 a a43 a a44 a a45数组顺序存储的表示和实现数组顺序存储的表示和实现InitArray(Array &A, int dim, .); / 若维数若维数dim和随后的各维长度数合法

16、和随后的各维长度数合法,构造相应的数组构造相应的数组,并返回并返回OKDestroyArray (Array &A);/销毁数组销毁数组AValue(Array A, ElemType &e, .); 若各下标不超界若各下标不超界,则则e赋值为所指定的赋值为所指定的A的元素值的元素值,并返回并返回OK Assign(Array &A, ElemType e, .) 若各下标不超界若各下标不超界,则将则将e的值赋给所指定的的值赋给所指定的A的元素的元素,并返回并返回OK basedimboundsconstantsa0a1aiat.0 1 . dim-1.#include

17、 #include #define MAX_ARRAY_DIM 8/#define MAX_ARRAY_DIM 8/维数最大值维数最大值typedef struct typedef struct ElemType ElemType * *base;/base;/数组元素基址数组元素基址 int dim;/int dim;/维数维数 int int * *bounds; /bounds; /维界基址维界基址 int int * *constants;/constants;/映像函数映像函数常量基址，除常量基址，除dimdim外，均由外，均由InitArray分配分配Array;Array;练习假

18、设有二维数组假设有二维数组A 68，每个元素用相邻的，每个元素用相邻的6个字个字节存储，存储器按字节编址。已知节存储，存储器按字节编址。已知A的起始存储位的起始存储位置（基地址）为置（基地址）为1000，计算：，计算：（1）数组）数组A的体积（即存储量）；的体积（即存储量）；（2）数组）数组A的最后一个元素的最后一个元素a57的第一个字节的地址；的第一个字节的地址；（3）按行存储时，元素）按行存储时，元素a14的第一个字节的地址；的第一个字节的地址；（4）按列存储时，元素）按列存储时，元素a47的第一个字节的地址。的第一个字节的地址。 5.3.1 特殊矩阵特殊矩阵5.3 矩阵的压缩存储矩阵的压

19、缩存储 5.3.2 稀疏矩阵稀疏矩阵5.3.1 特殊矩阵特殊矩阵 特殊矩阵是指非零元素或零元素在特殊矩阵是指非零元素或零元素在矩阵中的分布有一定规律的矩阵。矩阵中的分布有一定规律的矩阵。 对称矩阵对称矩阵元素满足条件元素满足条件 aij=aji 1=i , j=n的的n阶矩阵。阶矩阵。按行序为主序：按行序为主序： a11 a12 . . a1n a21 a22 . . a2n an1 an2 . ann . a11 a21 a22 a31 a32 an1 ann . k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 jiijjjijiik, 12/ ) 1(12/ ) 1(，例5

20、.2 对称矩阵n = 5, 1+2+3+4+5 = 5n = 5, 1+2+3+4+5 = 5* *(5+1)/2 = 15(5+1)/2 = 15一维数组一维数组SA1.15SA1.15作为数组作为数组A A的存储结构的存储结构: :SA=(4 5 2 3 1 3 2 5 2 8 1 6 7 9 5)SA=(4 5 2 3 1 3 2 5 2 8 1 6 7 9 5)如如: a5,3 = a3,5 = 7: a5,3 = a3,5 = 7 k = 5(5-1)/2 + 3-1= 12 k = 5(5-1)/2 + 3-1= 12故故:sa12 = 7 :sa12 = 7 4 5 3 2 14

21、 5 3 2 15 2 1 5 65 2 1 5 63 1 3 2 73 1 3 2 72 5 2 8 92 5 2 8 91 6 7 9 51 6 7 9 5A =A =4 4 5 2 5 2 0 03 1 3 3 1 3 2 5 2 8 2 5 2 8 1 6 7 9 51 6 7 9 5A A = =三角矩阵三角矩阵按行序为主序：按行序为主序：Loc( aij)=Loc(a11)+ i*(i-1)/2 +(j-1)*L a11 0 0 . 0 a21 a22 0 . 0 an1 an2 an3. ann . 0a11 a21 a22 a31 a32 an1 ann . k=0 1 2 3

22、 4 n(n-1)/2 n(n+1)/2-1 例5.3 下三角矩阵 4 0 0 0 0 4 0 0 0 0 5 2 0 0 0 5 2 0 0 0 A A = 3 1 3 0 0 = 3 1 3 0 0 2 5 2 8 0 2 5 2 8 0 1 6 7 9 5 1 6 7 9 5如如: a5,3 = 7: a5,3 = 7 k = 5(5-1)/2 + 3-1 = 12 k = 5(5-1)/2 + 3-1 = 12故故:sa12 = 7 :sa12 = 7 但但 a3,5 = 0a3,5 = 0对角矩阵对角矩阵 a11 a12 0 . 0 a21 a22 a23 0 0 0 0 an-1,

23、n-2 an-1,n-1 an-1,n 0 0 an,n-1 ann 0 a32 a33 a34 0 0 Loc(aij)=Loc(a11)+3(i-1)+(j-i)*L 按行序为主序：按行序为主序：a11 a12 a21 a22 a23 ann-1 ann . k=0 1 2 3 4 3*n-3 saksak和和ai,jai,j的一一对应关系的一一对应关系: : sak, k = 3sak, k = 3* *(i-1) + j-i, (i-1) + j-i, ai, j = ai, j = 当当 |i - j|=1|i - j|1|i - j|1 a a1111 a a1212 0 0 .

24、0 0 0 . 0 a a2121 a a2222 a a2323 0 . 0 0 . 0Anxn = 0 aAnxn = 0 a3232 a a3333 a a3434 . 0 . 0 . . 0 0 0 . a 0 0 0 . ann-1nn-1 a annnn例5.4 对角矩阵 4 3 0 0 0 4 3 0 0 0 5 2 2 0 0 5 2 2 0 0 A = 0 1 0 4 0 A = 0 1 0 4 0 0 0 2 8 7 0 0 2 8 7 0 0 0 9 5 0 0 0 9 5一维数组一维数组SA0.3SA0.3* *5-35-3作为数组作为数组A A的存储结构的存储结构:

25、: SA=(4 3 5 2 2 1 0 4 2 8 7 9 5)SA=(4 3 5 2 2 1 0 4 2 8 7 9 5)如如: a5,4 = 9: a5,4 = 9 k = 3 k = 3* *(5-1) + 4-5= 11(5-1) + 4-5= 11故故:sa11 = 9:sa11 = 97600070015000001800000240001400003000000000009120M5.3.2 稀疏矩阵稀疏矩阵 以常规方法，即以二维数组表示以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的高阶的稀疏矩阵时产生的问题问题:(1) 零值元素占了很大空间零值元素占了很大空间;(2) 计算

26、中进行了很多和零值的运算。计算中进行了很多和零值的运算。(1) 尽可能少存或不存零值元素；尽可能少存或不存零值元素；解决问题的原则解决问题的原则:(2) 尽可能减少没有实际意义的运算；尽可能减少没有实际意义的运算；(3) 操作方便。操作方便。 即：即： 能尽可能快地找到与下标值能尽可能快地找到与下标值(i，j)对对应的元素，应的元素， 能尽可能快地找到同一行或同一列能尽可能快地找到同一行或同一列的非零值元。的非零值元。稀疏矩阵稀疏矩阵 假设假设 m 行行 n 列列的矩阵含的矩阵含 t 个非个非零元素零元素，则称，则称 为为稀疏因子稀疏因子。 通常认为通常认为 0.05 的矩阵为稀的矩阵为稀疏矩

27、阵。疏矩阵。nmt稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法:一、三元组顺序表一、三元组顺序表二、行逻辑链接的顺序表二、行逻辑链接的顺序表三、三、 十字链表十字链表 #define MAXSIZE 12500 typedef struct int i, j; /该非零元的行下标和列下标 ElemType e; / 该非零元的值 Triple; / 三元组类型三元组类型一、三元组顺序表一、三元组顺序表typedef struct Triple dataMAXSIZE + 1; int mu, nu, tu; TSMatrix; / 稀疏矩阵类型稀疏矩阵类型6 7 8 1 2 12 1 3 9

28、3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j e0 1 2 3 4 5 6 7 87600070015000001800000240001400003000000000009120M7600070015000001800000240001400003000000000009120M6700000000014000000007000000024009018000121500300NT如何求转置矩阵？如何求转置矩阵？用常规的二维数组表示时的算法 其时间复杂度为其时间复杂度为: O(munu) for (col=1; col=nu; +col) for

29、(row=1; row=mu; +row) Tcolrow = Mrowcol;6 7 8 1 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 e0 1 2 3 4 5 6 7 8i j e7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 0 1 2 3 4 5 6 7 8?M.dataT.data解决思路：解决思路： 只要做到只要做到 将矩阵行、列值互换；将矩阵行、列值互换； 将每个三元组中的将每个三元组中的i和和j相互调换；相互调换； 重排三元组次序，使

30、重排三元组次序，使T.data中中元素以元素以N的行的行(M的列的列)为主序为主序方法一：按方法一：按M的列序转置的列序转置 按按T.data中三元组次序依次在中三元组次序依次在M.data中找到相应的三元组进行转置，中找到相应的三元组进行转置，即按照矩阵即按照矩阵M的列序的列序来进行置换。来进行置换。 为找到为找到M中每一列所有非零元素，中每一列所有非零元素，需对其三元组表需对其三元组表M.data从第一行起扫从第一行起扫描一遍。由于描一遍。由于M.data中以中以M行序为主行序为主序，所以由此得到的恰是序，所以由此得到的恰是T.data中应中应有的顺序有的顺序。6 7 8 1 2 12 1

31、 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 -7 i j e0 1 2 3 4 5 6 7 8M.data7 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 i j e0 1 2 3 4 5 6 7 8T.dataqppppppppqqqqppppppppcol=1col=2Status TransposeSMatix(TSMatrix M,TSMatrix &T) /采用三元组表存储表示，求稀疏矩阵采用三元组表存储表示，求稀疏矩阵M的转置矩阵的转置矩阵T。 T.mu=M.

32、nu; T.nu=M.mu; T.tu=M.tu; If (T.tu) q=1; for (col=1; col=M.nu; +col) for (p=1; p=M.tu; +p) If (M.datap.j = col) T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.dataq.e = M.datap.e; +q; return OK;/TransposeSMatrixT(n)=O(nu*tu)方法二：快速转置方法二：快速转置 按按M.data中三元组次序转置，转置结果中三元组次序转置，转置结果放入放入T.data中恰当位置。中恰当位置。 此

33、法关键是要预先确定此法关键是要预先确定M中每一列第一中每一列第一个非零元在个非零元在T.data中位置，为确定这些位置，中位置，为确定这些位置，转置前应先求得转置前应先求得M的每一列中非零元个数。的每一列中非零元个数。实现：实现：设两个数组设两个数组numcol：表示矩阵：表示矩阵M中第中第col列中非零元个数列中非零元个数cpotcol：指示指示M中第中第col列第一个非零元在列第一个非零元在T.data中位置中位置显然有：显然有：cpot1=1;cpotcol=cpotcol-1+numcol-1; (2 col M.nu)6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14

34、4 3 24 5 2 18 6 1 15 6 4 -7 i j e0 1 2 3 4 5 6 7 8M.datai j e0 1 2 3 4 5 6 7 8T.datacolnumcolcpotcol1122323524715806817907 6 8 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 9 3 4 24 4 6 -7 6 3 14 pppppppp46297537600070015000001800000240001400003000000000009120M6 7 8 1 2 12 1 3 9 3 1 -3 3 6 14 4 3 24 5 2 18 6 1 15

35、 6 4 -7 i j e0 1 2 3 4 5 6 7 8for (col=1; col=M.nu; +col) numcol = 0;for (t=1; t=M.tu; +t) +numM.datat.j;cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1; Col 1 2 3 4 5 6 7Numcolcpotcolt1t1t1t1t2t2t2t10 01357889Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) T.mu = M.nu

36、; T.nu = M.mu; T.tu = M.tu; if (T.tu) for (col=1; col=M.nu; +col) numcol = 0; for (t=1; t=M.tu; +t) +numM.datat.j; cpot1 = 1; for (col=2; col=M.nu; +col) cpotcol = cpotcol-1 + numcol-1; for (p=1; p=M.tu; +p) / 转置矩阵元素 col = M.datap.j; q = cpotcol; T.dataq.i =M.datap.j; T.dataq.j =M.datap.i; T.dataq.e

37、 =M.datap.e; +cpotcol; / for / if return OK; / FastTransposeSMatrixT(n)=O(nu+tu)T(n)=O(mu*nu) 三元组顺序表又称三元组顺序表又称有序的双下有序的双下标法标法，它的特点是，非零元在表中，它的特点是，非零元在表中按行序有序存储，因此按行序有序存储，因此便于进行依便于进行依行顺序处理的矩阵运算行顺序处理的矩阵运算。然而，若。然而，若需需随机随机存取某一行中的非零元，则存取某一行中的非零元，则需从头开始进行查找。需从头开始进行查找。 #define MAXMN 500 typedef struct Triple

38、 dataMAXSIZE + 1; /非零元三元组表 int rposMAXMN + 1; /各行第一个非零元的位置表各行第一个非零元的位置表 int mu, nu, tu; RLSMatrix; / 行逻辑链接顺序表类型二、行逻辑链接的顺序表二、行逻辑链接的顺序表000200105003M=00420120N=400160Q=Q = M N 1 1 3 1 4 5 i j e1 2 3 4 3 1 2 2 2 -1M.data 1 2 2 2 1 1 i j e1 2 3 4 3 2 4 3 1 -2N.data 2 1 -1 i j e1 2 3 4 Q.dataparow 1 2 3 r

39、posarow 1 3 4brow 1 2 3 4rposbrow 1 2 3 5ccol 1 2ctempt1tpq6p 1 2 6tpp2tq-1tp =5p1tq4 3 2 4三、三、 十字链表十字链表M.cheadM.rhead3 0 0 50 -1 0 02 0 0 01 1 31 4 52 2-13 1 2 Type struct OLNodeType struct OLNode int i,j; int i,j; int e; int e; struct OLNode struct OLNode * *right,right,* *down;down; OLNode; OLNod

40、e; * *OLink;OLink;Type struct Type struct OLink OLink * *rhead,rhead,* *chead;chead; int mu,nu,tu; int mu,nu,tu; CrossList; CrossList;5.4 广义表的类型定义广义表的类型定义ADT Glist 数据对象数据对象：Dei | i=1,2,.,n; n0; eiAtomSet 或 eiGList, AtomSet为某个数据对象 数据关系：数据关系： LR| ei-1 ,eiD, 2in ADT Glist 基本操作基本操作:广义表是广义表是递归递归定义的定义的线性结

41、构线性结构， LS = ( 1, 2, , n )其中：其中： i 或为原子或为原子 或为广义表或为广义表例如例如: A = ( ) F = (d, (e) D = (a,(b,c), F) C = (A, D, F) B = (a, B) = (a, (a, (a, , ) ) )广义表是一个多层次多层次的线性结构线性结构例如：例如：D=(E, F)其中: E=(a, (b, c) F=(d, (e)DEFa( ) d( )bce广义表广义表 LS = ( 1, 2, , n )的的结构特点结构特点:1) 广义表中的数据元素有相对广义表中的数据元素有相对次序次序；2) 广义表的广义表的长度长

42、度定义为最外层包含元素个数；定义为最外层包含元素个数；3) 广义表的广义表的深度深度定义为所含括弧的重数；定义为所含括弧的重数； 注意：注意：“原子原子”的深度为的深度为 0 “空表空表”的深度为的深度为 1 4) 广义表可以广义表可以共享共享；5) 广义表可以是一个广义表可以是一个递归递归的表。的表。 递归表的深度是无穷值，长度是有限值递归表的深度是无穷值，长度是有限值。6) 任何一个非空广义表任何一个非空广义表 LS = ( 1, 2, , n) 均可分解为均可分解为 表头表头 GetHead(LS) = 1 和和 表尾表尾 GetTail(LS) = ( 2, , n) 两部分。两部分。

43、例如例如: D = ( E, F ) = (a, (b, c)，F )GetHead( D ) = E GetTail( D ) = ( F )GetHead( E ) = a GetTail( E ) = ( ( b, c) )GetHead( ( b, c) ) = ( b, c) Get Tail( ( b, c) ) = ( )GetHead( ( b, c) ) = b GetTail( ( b, c) ) = ( c )GetHead( ( c ) ) = c GetTail( ( c ) ) = ( )练习求下列广义表操作的结果：求下列广义表操作的结果：（1）GetHead( (

44、p, h, w) );（2） GetTail( (a ,b) ,(c ,d) );（3） GetHead ( GetTail ( (a,b),(c,d) ) )。 结构的创建和销毁结构的创建和销毁 InitGList(&L); DestroyGList(&L); CreateGList(&L, S); CopyGList(&T, L);基本操作基本操作 状态函数状态函数 GListLength(L); GListDepth(L); GListEmpty(L); GetHead(L); GetTail(L); 插入和删除操作插入和删除操作 InsertFirst_GL(&L, e); DeleteFirst_GL(&L, &e); 遍历遍历 Traverse_GL(L, Visit();5.5 广义表的表示方法广义表的表示方法通常采用头、尾指针的链表结构通常采用头、尾指针的链表结构表结点表结点:原子结点：原子结点：tag=1 hp tptag=0 data链表存储表示Typedef