《数组和广义表线性表的扩展表中的数据元素本身》由会员分享，可在线阅读，更多相关《数组和广义表线性表的扩展表中的数据元素本身（50页珍藏版）》请在金锄头文库上搜索。
1、5-1DGZ.SWFU第第5章章 数组和广义表数组和广义表 线性表的扩展：表中的数据元素本身也是一个数据结构线性表的扩展：表中的数据元素本身也是一个数据结构5.1 数组的定义数组的定义5.2 数组的顺序表示和实现数组的顺序表示和实现5.3 矩阵的压缩存储矩阵的压缩存储 5.3.1 特殊矩阵特殊矩阵 5.3.2 稀疏矩阵稀疏矩阵Data Structure5-2DGZ.SWFU一、教学目的与要求一、教学目的与要求 理理解解数数组组的的定定义义、顺顺序序表表示示和和实实现现；矩矩阵阵的的压压缩缩存存储；广义表的定义和存储结构储；广义表的定义和存储结构二、主要教学内容二、主要教学内容 数数组组的的定
2、定义义；数数组组的的顺顺序序表表示示和和实实现现；矩矩阵阵的的压压缩缩存存储储、特特殊殊矩矩阵阵、稀稀疏疏矩矩阵阵；广广义义表表的的定定义义、广广义义表表的的存储结构存储结构三、教学重点、难点三、教学重点、难点 多多维维数数组组、特特殊殊矩矩阵阵、稀稀疏疏矩矩阵阵、广广义义表表的的存存储储结结构构四、授课方法及手段四、授课方法及手段 采用多媒体大屏幕投影授课采用多媒体大屏幕投影授课五、讲课具体内容（讲稿）五、讲课具体内容（讲稿）Data Structure5-3DGZ.SWFUlADT Array l数据对象：数据对象： ji=0,bi-1,I=1,2,n;D = aj1j2.jn | n(0
3、)称为数组的称为数组的维数维数,bi是数组第是数组第i维的维的长度长度,ji是数组元素的第是数组元素的第i维下标维下标, aj1j2. . .jnElemsetElemset l数据关系：数据关系： R=R1 , R2 . Rn Ri = aj1.ji.jn, aj1.ji+1.jn | 对每一维是线性的对每一维是线性的0jkbk-1, 1kn 且且ki0jibi-2, aj1.ji.jn, aj1.ji+1.jnD,ID,I=2,n=2,nl 基本操作：基本操作： InitArray(&A,n,bound1,bound2,.,boundn); lADT Array5.1 5.1 数组的定义数
4、组的定义Data Structure5-4DGZ.SWFUl二维数组的类型定义二维数组的类型定义: :typedeftypedef ElemTypeElemType Array2mn; Array2mn; Array2 A;Array2 A;l等价于：等价于： typedeftypedef ElemTypeElemType Array1n; Array1n; typedeftypedef Array1 Array2m; Array1 Array2m; Array2 A;Array2 A;维数和维界维数和维界Data Structure5-5DGZ.SWFU a a00 a a01 a a02
5、. A . A0,n-1 a a10 a a11 a a12 . A . A1,n-1 A Amxnmxn= .= . a am-1,0 a am-1,1 a am-1,2 . A . Am-1,n-1 A Amnmn=( (a=( (a0000,a,a0101,.a,.a0,n-10,n-1),), (a (a1010,a,a1111,.a,.a1,n-11,n-1),), ., ., (a (am-1,0m-1,0,a,am-1,1m-1,1,.a,.am-1,n-1m-1,n-1) ) )二维的数组二维的数组 = = 定长的线性表定长的线性表Data Structure5-6DGZ.SW
6、FU5.2 5.2 数组的顺序表示和实现数组的顺序表示和实现l除了初始化和销毁之外除了初始化和销毁之外, , 数数组组一一般般只只有有存存取取操操作作和和修修改改元元素素值值的的操作，操作， 也没有也没有插入插入和和删除删除操作。操作。l存存储储时时一一般般以以行行序序为为主主序序:(:(如如C C语语言言, , PASCAL, BASICPASCAL, BASIC等等) ) A Amxnmxn=(a=(a0000,a,a0101,.a,.a0,n-10,n-1,a,a1010,a,a1111,.a,.a1,n-1,n-1 1,.,a,.,am-1,0m-1,0, a, am-1,1m-1,1
7、,.a,.am-1,n-1m-1,n-1) )Data Structure5-7DGZ.SWFU二维数组的存储二维数组的存储lLOC0,0LOC0,0为为 基基 地地 址址 , ,二二 维维 数数 组组Ab1b2Ab1b2中元素中元素a aijij的存储位置为的存储位置为: :LOCi,jLOCi,j=LOC0,0+(b2i+j)L=LOC0,0+(b2i+j)L0=i=b1-10=i=b1-10=j=b2-10=j=b2-1LL每个数据元素所占的存储空间大小每个数据元素所占的存储空间大小Data Structure5-8DGZ.SWFU例例5.1: 5.1: 若若 L=2, LOC0,0 =
8、 1000L=2, LOC0,0 = 1000，求，求LOC2,3LOC2,3l LOC2,3 = LOC0,0 + (5*2+3)*L LOC2,3 = LOC0,0 + (5*2+3)*Ll = 1000 + 13 * 2 = 1000 + 13 * 2 l = 1026 = 1026 a a00 a a01 a a02 a a03 a a04A A4x54x5 = a = a10 a a11 a a12 a a13 a a14 a a20 a a21 a a22 a a23 a a24 a a30 a a31 a a32 a a33 a a34Data Structure5-9DGZ.S
9、WFU三维数组的存储三维数组的存储l若若LOC0,0,0 LOC0,0,0 为基地址为基地址: : LOCi,j,kLOCi,j,k = LOC0,0,0+ = LOC0,0,0+ (n*h*(n*h*i+hi+h* *j+kj+k)*L)*L0 = i m0 = i m0 = j n0 = j n0 = k h0 = k h每个数据元素占每个数据元素占L L个存储单元个存储单元Data Structure5-10DGZ.SWFU N N维数组存储维数组存储lb b1 1,b,b2 2,.,.,b bn n是是n n维数组维数组A A每一维的维每一维的维界界, ,数组元素数组元素A(jA(j1
10、 1,j,j2 2,.,.,j jn n) )的存储的存储位置为：位置为： LOCjLOCj1 1,j,j2 2,.,.j jn n=LOC0,0,.,0 + =LOC0,0,.,0 + (b (b22b b33bbnnj j1 1 + + b b33bbnnj j2 2 + . + . + b + bnnj jn n-1 -1 + + j jn n ) )L LData Structure5-11DGZ.SWFUSizeof(Elem Type)倒推公式倒推公式Data Structure5-12DGZ.SWFUl例例: : 在在C C语言中语言中, ,设数组设数组A5678A5678的首地
11、址为的首地址为2000,2000,每个元素占每个元素占2 2个字节；个字节；求元素求元素A3454A3454的地址。的地址。 LOC3,4,5,4 LOC3,4,5,4 = 2000+( = 2000+(6*7*86*7*8*3*3+ +7*87*8*4*4+ +8 8*5*5+ +4 4)*2)*2 = 2000+(1008+224+40+4)*2 = 2000+(1008+224+40+4)*2 = 4552 = 4552Data Structure5-13DGZ.SWFU数组顺序存储的表示和实现数组顺序存储的表示和实现# #incluseincluse #define MAX_ARRAY
12、_DIM 8#define MAX_ARRAY_DIM 8typedeftypedef structstruct ElemTypeElemType *base; *base; intint dim; dim; intint *bounds; *bounds; intint *constants; *constants;Array;Array;相当于相当于Loc(0,0)BiCiData Structure5-14DGZ.SWFUbasedimboundsconstantsa0a1aiat. 0 1 . dim-1Data Structure5-15DGZ.SWFU10 11 12 1320 2
13、1 22 2330 31 32 33A = 3.basedimboundsconstants 0 1 . dim-14821011313233= 2Data Structure5-16DGZ.SWFU5.3 5.3 矩阵的压缩存储矩阵的压缩存储l矩矩 阵阵: : 二维数组二维数组l特殊矩阵特殊矩阵: : 大量大量重复元素重复元素或大量或大量0 0元素元素 l稀疏矩阵稀疏矩阵: : 大量大量0 0元素元素 l压缩存储压缩存储: : 重复元素重复元素只分配一个存储空间只分配一个存储空间, , 0 0元素元素不分配存储空间不分配存储空间Data Structure5-17DGZ.SWFU5.3.1
14、5.3.1 特殊矩阵特殊矩阵l对对 称称 矩阵矩阵: : a aijij = = a ajiji (1=i,j=n) (1=i,j=n)l下三角矩阵下三角矩阵: : 当当ijij时时, , aijaij = 0, (1=i,j=n) = 0, (1=i,j1|i-j| 1时时, , a aijij = 0, = 0, (1=i,j=n) (1=i,j=n) a a1111 a a1212 a a1313 . a . a1n1n a a2121 a a2222 a a2323 . a . a2n2n a a3131 a a3232 a a3333 . a . a3n3n . . a an1n1
15、a an2n2 a an3n3 . . a annnnA Annnn = =Data Structure5-18DGZ.SWFU对称矩阵对称矩阵: : a aijij = = a ajiji (1=i , j=n) (1=i , j=ji=j（下三角含对角线）（下三角含对角线） k= k= j(j-1)/2+i-1j(j-1)/2+i-1 当当ij ij （上三角）上三角）Data Structure5-20DGZ.SWFU例例5.3 5.3 对称矩阵对称矩阵ln = 5, 1+2+3+4+5 = 5*(5+1)/2 = 15n = 5, 1+2+3+4+5 = 5*(5+1)/2 = 15l
16、一维数组一维数组SA0.14SA0.14作为数组作为数组A A的存储结构的存储结构: :SA=(SA=(4 4 5 5 2 2 3 13 1 3 3 2 5 22 5 2 8 8 1 6 7 91 6 7 9 5 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 4 5 3 2 1 5 3 2 15 5 2 2 1 5 6 1 5 63 1 3 1 3 3 2 7 2 72 5 2 2 5 2 8 8 9 91
17、6 7 9 1 6 7 9 5 5A =A =4 4 5 5 2 2 0 03 13 1 3 3 2 5 22 5 2 8 8 1 6 7 91 6 7 9 5 5A A = =Data Structure5-21DGZ.SWFU下三角矩阵下三角矩阵: :当当ijij时时, ,a aijij=0,(1=i,j=n)=0,(1=i,j=j)i=j)lai,j=ai,j= 0 0 ( (当当ij)i 1|i-j| 1时时, , a aijij = 0, (1=i,j=n) = 0, (1=i,j=n) a a1111 a a1212 0 0 . 0 0 .0 0 a a2121 a a2222 a
18、 a2323 0 . 0 .0 0A Annnn = 0 = 0 a a3232 a a3333 a a3434 . . 0 0 . . a an-1nn-1n 0 0 0 . 0 0 0 . a ann-1nn-1 a annnnData Structure5-24DGZ.SWFUl一一维维数数组组SA0.3*n-3SA0.3*n-3作作为为数数组组A A三三角角元元素素的的存存储结构储结构: :SAk=SAk=a a1111,a,a1212, ,a a2121,a,a2222,a,a2323,a,a3232,.,.,a ann-1nn-1,a,annnn （k=0,2,3,4,5,6,3n
19、-3,3n-3k=0,2,3,4,5,6,3n-3,3n-3）lsasak k 和和aai,ji,j 的一一对应关系的一一对应关系: : sak,ksak,k=3*(i-1)+j-i=3*(i-1)+j-i， 当当|i-j|=1|i-j|1|i-j|1Data Structure5-25DGZ.SWFU例例5.5 5.5 三对角矩阵三对角矩阵 4 4 3 3 0 0 0 0 0 0 5 5 2 2 2 2 0 0 0 0 A = 0 A = 0 1 1 0 0 4 4 0 0 0 0 0 0 2 2 8 8 7 7 0 0 0 0 0 0 9 9 5 5l一维数组一维数组SASA0 0.3*5
20、-33*5-3 作为数组作为数组A A的存储结构的存储结构: : 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)l如如: : a5,4 = 9 k = 3*(5-1) + 4 - 5 = 11 a5,4 = 9 k = 3*(5-1) + 4 - 5 = 11 故故: : sa11 = 9 sa11 = 9Data Structure5-26DGZ.SWFU5.3.2 5.3.2 稀疏矩阵稀疏矩阵l稀稀疏疏因因子子：假假设设在在mnmn的的矩矩阵阵中中，有有t t个个元元素素不不为为零零。令令=t/(mnt/(mn) )
21、，称称为为矩矩阵阵的的稀稀疏疏因因子子，通通常常稀稀疏疏因因子子0.050.05时时称称为为稀稀疏疏矩阵。矩阵。 0 0 12 912 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 M M(67)(67) = = -3-3 0 0 0 0 0 0 0 0 1414 0 0 0 0 0 0 2424 0 0 0 0 0 0 0 0 0 0 1818 0 0 0 0 0 0 0 0 0 0 1515 0 0 0 0 -7-7 0 0 0 0 0 0Data Structure5-27DGZ.SWFU转置矩阵转置矩阵 0 0 0 0 -3-3 0 0 0
22、0 1515 1212 0 0 0 0 0 0 1818 0 0 9 9 0 0 0 0 2424 0 0 0 0T T(76)(76) = =0 0 0 0 0 0 0 0 0 0 -7-7 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1414 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0Data Structure5-28DGZ.SWFU稀疏矩阵的存储结构稀疏矩阵的存储结构 一一. . 三元组顺序表三元组顺序表l M:M: i j ei j e T:T: i j ei j e 1 2 12 1 3 -3 1 2 12 1 3 -3 1 3 9 1
23、6 15 1 3 9 1 6 15 3 1 -3 2 1 12 3 1 -3 2 1 12 3 6 14 2 5 18 3 6 14 2 5 18 4 3 24 3 1 9 4 3 24 3 1 9 5 2 18 3 4 24 5 2 18 3 4 24 6 1 15 4 6 -7 6 1 15 4 6 -7 6 4 -7 6 3 14 6 4 -7 6 3 14 Data Structure5-29DGZ.SWFU三元组顺序表结构定义三元组顺序表结构定义#define MAXSIZE 12500#define MAXSIZE 12500typedeftypedef structstruct
24、intint i, j; i, j; ElemtypeElemtype e; e; TripleTriple; ;typedeftypedef structstruct TripleTriple dataMAXSIZE+1; dataMAXSIZE+1; intint mu,nu,tumu,nu,tu; ; TSMatrixTSMatrix; ;lTSMatrixTSMatrix M, T; M, T;Data Structure5-30DGZ.SWFUM.datap .i .j .e012.tumu nutu1212.64-7Data Structure5-31DGZ.SWFU求稀疏矩阵求稀
25、疏矩阵M M的转置矩阵的转置矩阵T T012345678M.datap .i .j .e012345678T.dataq .i .j .e方法：方法：1. 1. 将矩阵的将矩阵的行列值行列值相互相互交换交换； 2. 2. 将每个三元组中的将每个三元组中的i i、j j相互相互调换调换； 3. 3. 重排三元组之间的次序。重排三元组之间的次序。Data Structure5-32DGZ.SWFU算法算法5.15.1：求稀疏矩阵：求稀疏矩阵M M的转置矩阵的转置矩阵T TStatus Status TransposeSMatrixTransposeSMatrix(TSMatrix(TSMatrix
26、 M,TSMatrixM,TSMatrix &T) &T) T.muT.mu= =M.nuM.nu; ; T.nuT.nu= =M.muM.mu; ; T.tuT.tu= =M.tuM.tu; ; if ( if (T.tuT.tu) q = 1;) q = 1; for ( for (colcol = 1; = 1; colcol = = M.nuM.nu; +; +colcol) ) for (p = 1; p = for (p = 1; p = M.tuM.tu; +p); +p) if (M.datap.j = if (M.datap.j = colcol ) ) T.dataq.i
27、= M.datap.j; T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.dataq.j = M.datap.i; T.dataq.e = M.datap.e; T.dataq.e = M.datap.e; +q;+q; retrunretrun OK; OK;/TransposeSMatrixTransposeSMatrix算法复杂度：算法复杂度： O(nu*tu)Data Structure5-33DGZ.SWFU算法算法5.25.2：求转置矩阵的快速方法：求转置矩阵的快速方法l为为了了减减少少算算法法复复杂杂度度, ,增增加加两两个个向向量
28、量numnum和和cpotcpot: :lnumcolnumcol: M: M中中第第 colcol 列列中中非零元素的个数非零元素的个数; ;lcpotcolcpotcol: : M M中中第第colcol列列中中的的第第一一个个非非零零元元素素在在T.dataT.data中的中的位置位置; ;l有有: : cpot1 = 1;cpot1 = 1; cpotcolcpotcol=cpotcol-1+numcol-1;=cpotcol-1+numcol-1; （2=2=colcol=m.num.nu）Data Structure5-34DGZ.SWFUl例例5.65.6 0 0 12 912
29、9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 M= M= -3-3 0 0 0 0 0 0 0 0 1414 0 0 0 0 0 0 2424 0 0 0 0 0 0 0 0 0 0 1818 0 0 0 0 0 0 0 0 0 0 1515 0 0 0 0 -7-7 0 0 0 0 0 0 l上例中的向量上例中的向量numnum和和cpotcpot: :l colcol 1 2 3 4 5 6 7 1 2 3 4 5 6 7 l numnum 2 2 2 1 0 1 0 2 2 2 1 0 1 0l cpotcpot 1 3 5 7 8 8 9 1
30、 3 5 7 8 8 9Data Structure5-35DGZ.SWFUi j vi j vi j vi j v0 01 12 23 34 45 56 67 78 8 7 6 87 6 83 4 243 4 241 6 151 6 153 1 93 1 96 3 146 3 142 5 182 5 18 T T 1 3 -31 3 -30 01 12 23 34 45 56 67 78 83 1 -33 1 -36 1 156 1 156 7 86 7 85 2 185 2 181 3 91 3 94 3 244 3 246 4 -76 4 -73 6 143 6 141 2 121 2
31、122 1 122 1 124 6 -74 6 -7 colcol 1 2 3 4 5 6 7 1 2 3 4 5 6 7 cpotcpot 1 3 5 7 8 8 9 1 3 5 7 8 8 946297538M M Data Structure5-36DGZ.SWFUStatus Status FastTransposeSMatrix(TSMatrixFastTransposeSMatrix(TSMatrix M,TSMatrixM,TSMatrix &T) &T) T.muT.mu = = M.nuM.nu; ; T.nuT.nu = = M.muM.mu; ; T.tuT.tu = =
32、 M.tuM.tu; ; if ( if (T.tuT.tu) for(colfor(col=1; =1; colcol=M.nuM.nu; +; +colcol) ) numcolnumcol = 0; = 0; for(t=1; t= for(t=1; t=M.tuM.tu; +t) +numM.datat.j; +t) +numM.datat.j; cpot1 = 1; cpot1 = 1; for(colfor(col=2; =2; colcol=M.nuM.nu; +; +colcol) ) cpotcolcpotcol=cpotcol-1+numcol-1;=cpotcol-1+n
33、umcol-1; for(p=1; p= for(p=1; p=M.tuM.tu; +p); +p) colcol=M.datap.j; q=M.datap.j; q=cpotcolcpotcol; T.dataq.i = M.datap.j; T.dataq.i = M.datap.j; T.dataq.j = M.datap.i; T.dataq.j = M.datap.i; T.dataq.e = M.datap.e; T.dataq.e = M.datap.e; +cpotcolcpotcol; retrunretrun OK; OK; / / FastTransposeSMatrix
34、FastTransposeSMatrix算法复杂度： O(nu+tu)Data Structure5-37DGZ.SWFU三元组顺序表（有序的双下标法）小结三元组顺序表（有序的双下标法）小结特点特点/ /优点：优点： 非零元在表中按非零元在表中按行序行序有序存储，便于有序存储，便于进行依行序顺序处理的矩阵运算。进行依行序顺序处理的矩阵运算。缺点：缺点： 若需按行号存取某一行的非零元，则若需按行号存取某一行的非零元，则需从头开始进行查找。需从头开始进行查找。Data Structure5-38DGZ.SWFU#define MAXRC 100typedef struct int i, j; El
35、emtype e;Triple;二、行逻辑链接的顺序表二、行逻辑链接的顺序表（指出每一行的第一个非零元素在三元组中的位置）（指出每一行的第一个非零元素在三元组中的位置）typedef struct Triple dataMAXSIZE+1; int rposMAXRC+ 1; int mu,nu,tu;RLSMatrix;Data Structure5-39DGZ.SWFUM.datap .i .j .e012.maxsizeM.rposrowData Structure5-40DGZ.SWFU三、十字链表三、十字链表（行和列都是线性链表（行和列都是线性链表非线性结构）非线性结构） 当矩阵的非
36、零元个数和位置在操作过程中变当矩阵的非零元个数和位置在操作过程中变当矩阵的非零元个数和位置在操作过程中变当矩阵的非零元个数和位置在操作过程中变化较大时，不宜采用顺序存储结构，采用链式存化较大时，不宜采用顺序存储结构，采用链式存化较大时，不宜采用顺序存储结构，采用链式存化较大时，不宜采用顺序存储结构，采用链式存储结构表示更恰当。储结构表示更恰当。储结构表示更恰当。储结构表示更恰当。 十字链表的表示法十字链表的表示法十字链表的表示法十字链表的表示法是是是是稀疏矩阵的链式存储方稀疏矩阵的链式存储方稀疏矩阵的链式存储方稀疏矩阵的链式存储方法法法法之一，其之一，其之一，其之一，其基本思想基本思想基本思想
37、基本思想为：为：为：为：将将将将稀疏矩阵同一行的所稀疏矩阵同一行的所稀疏矩阵同一行的所稀疏矩阵同一行的所有非零元素串成一个带表头的环形链表，同一列有非零元素串成一个带表头的环形链表，同一列有非零元素串成一个带表头的环形链表，同一列有非零元素串成一个带表头的环形链表，同一列的所有非零元素也串成一个带表头的环形链表。的所有非零元素也串成一个带表头的环形链表。的所有非零元素也串成一个带表头的环形链表。的所有非零元素也串成一个带表头的环形链表。因此，在十字链表的表示中有两类结点，因此，在十字链表的表示中有两类结点，因此，在十字链表的表示中有两类结点，因此，在十字链表的表示中有两类结点，非零元非零元非零
38、元非零元素结点素结点素结点素结点和和和和表头结点表头结点表头结点表头结点。Data Structure5-41DGZ.SWFU row col val *right *down 非零元素结点：非零元素结点： mu nu tu *rhead *chead 表头结点：表头结点：十字链表：十字链表：Data Structure5-42DGZ.SWFU1 什么是广义表什么是广义表 广义表也称为列表，是线性表的一种扩展，也是数据广义表也称为列表，是线性表的一种扩展，也是数据元素的有限序列。元素的有限序列。 记作：记作：LS= (d1, d2, . . . . . .dn)。其中其中di既可以是单个元素，
39、也可以是广义表。既可以是单个元素，也可以是广义表。说明说明 1）广义表的定义是一个）广义表的定义是一个递归定义递归定义，因为在描述广义表时，因为在描述广义表时又用到了广义表；又用到了广义表； 2）在线性表中数据元素是单个元素，而在广义表中，）在线性表中数据元素是单个元素，而在广义表中， 元素可以是单个元素元素可以是单个元素, 称为称为单元素单元素(原子原子)，也可以是，也可以是广义表，称为广义表的广义表，称为广义表的子表子表； 3）n 是广义表长度；是广义表长度；5.4 广义表广义表Data Structure5-43DGZ.SWFU4）下面是一些广义表的例子：）下面是一些广义表的例子： A
40、= ( ) 空表，表长为空表，表长为0 B = (a,(b,c,d) B的表长为的表长为2，两个元，两个元素分别为素分别为 a 和子表（和子表（b,c,d) C = (e) C中只有一个元素中只有一个元素e，表长为表长为1 D = (A,B,C,f ) D 的表长为的表长为4，它的前，它的前三个元素三个元素 A，B，C是是 广义表，第四个是单广义表，第四个是单元素元素 E=( a ,E ) 递归表递归表Data Structure5-44DGZ.SWFU5）表头和表尾：表头和表尾： 若广义表不空，则可分成若广义表不空，则可分成表头表头和和表表尾尾，反之，一对表头和表尾可唯一确定，反之，一对表头
41、和表尾可唯一确定一个广义表一个广义表 对非空广义表：对非空广义表： 称第一个称第一个元素元素为为L的的表头表头 其余元素组成的其余元素组成的表表称为称为LS的的表尾表尾；Data Structure5-45DGZ.SWFU例如：例如：B = (a,(b,c,d) 表头：表头：a 表尾：表尾： (b,c,d) 即即 HEAD（B）=a TAIL(B)=(b,c,d)C = (e) 表头：表头：e 表尾：表尾：( )D = (A,B,C,f ) 表头：表头：A 表尾：表尾：(B,C,f )运算可以嵌套运算可以嵌套，如：，如：H(H(T(B)=? T(T(B)=?Data Structure5-46
42、DGZ.SWFU广义表的元素之间除了存在广义表的元素之间除了存在次序次序关系外，关系外，还存在还存在层次层次关系。如：关系。如：DABCfaDebcdData Structure5-47DGZ.SWFU5.5 广义表的存储结构广义表的存储结构 由于广义表中数据元素可以具有不同结由于广义表中数据元素可以具有不同结构，故难以用顺序结构表示广义表。通常采构，故难以用顺序结构表示广义表。通常采用用链表存储方式。链表存储方式。 如何设定链表结点？广义表中的数据元如何设定链表结点？广义表中的数据元素可能为单元素（原子）或子表，由此需要素可能为单元素（原子）或子表，由此需要两种结点：一种是两种结点：一种是表
43、结点表结点，用以表示广义表；，用以表示广义表；一种是一种是单元素结点单元素结点，用以表示单元素（原子），用以表示单元素（原子）。Data Structure5-48DGZ.SWFUtag hp tp表结点表结点1 0 tag atom原子结点原子结点方法方法1：tag hp tp表结点表结点1 0 tag atom tp原子结点原子结点方法方法2：Data Structure5-49DGZ.SWFU广义表的存储结构示例广义表的存储结构示例 1 1 A =() B =(e) C = (a,(b,c,d) D = (A,B,C) E = (a, E)Data Structure5-50DGZ.SWFU广义表的存储结构示例广义表的存储结构示例 2 2 A =() B =(e) C = (a,(b,c,d) D = (A,B,C) E = (a, E)Data Structure
