数组和广义表线性的扩展表中的数据元素本身

《数组和广义表线性的扩展表中的数据元素本身》由会员分享，可在线阅读，更多相关《数组和广义表线性的扩展表中的数据元素本身（50页珍藏版）》请在装配图网上搜索。

1、5-1DGZ.SWFUData Structure第第5章章 数组和广义表数组和广义表 线性表的扩展：表中的数据元素本身也是一个数据结构线性表的扩展：表中的数据元素本身也是一个数据结构5.1 数组的定义数组的定义5.2 数组的顺序表示和实现数组的顺序表示和实现5.3 矩阵的压缩存储矩阵的压缩存储 5.3.1 特殊矩阵特殊矩阵 5.3.2 稀疏矩阵稀疏矩阵5-2DGZ.SWFUData Structure一、教学目的与要求一、教学目的与要求 理解数组的定义、顺序表示和实现；矩阵的压缩存理解数组的定义、顺序表示和实现；矩阵的压缩存储；广义表的定义和存储结构储；广义表的定义和存储结构二、主要教学内容

2、二、主要教学内容 数组的定义；数组的顺序表示和实现；矩阵的压缩数组的定义；数组的顺序表示和实现；矩阵的压缩存储、特殊矩阵、稀疏矩阵；广义表的定义、广义表的存储、特殊矩阵、稀疏矩阵；广义表的定义、广义表的存储结构存储结构三、教学重点、难点三、教学重点、难点 多维数组、特殊矩阵、稀疏矩阵、广义表的存储结多维数组、特殊矩阵、稀疏矩阵、广义表的存储结构构四、授课方法及手段四、授课方法及手段 采用多媒体大屏幕投影授课采用多媒体大屏幕投影授课五、讲课具体内容（讲稿）五、讲课具体内容（讲稿）5-3DGZ.SWFUData StructurelADT Array l数据对象：数据对象： ji=0,bi-1,I

3、=1,2,n;D = aj1j2.jn | n(0)称为数组的称为数组的维数维数,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,=2,n,nl 基本操作：基本操作： InitArray(&A,n,bound1,bound2,.,boundn)

4、; lADT Array5.1 5.1 数组的定义数组的定义5-4DGZ.SWFUData Structurel二维数组的类型定义二维数组的类型定义: :typedef ElemTypetypedef ElemType Array2mn; Array2mn; Array2 A;Array2 A;l等价于：等价于： typedef ElemTypetypedef ElemType Array1n; Array1n; typedef typedef Array1 Array2m; Array1 Array2m; Array2 A;Array2 A;维数和维界维数和维界5-5DGZ.SWFUData

5、 Structure a a00 a a01 a a02 . 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 Am mn n=( (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) ) )二维的数组二维的数组 = = 定长的线

6、性表定长的线性表5-6DGZ.SWFUData Structure5.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,.,

7、a,.,am-1,0m-1,0, a, am-1,1m-1,1,.a,.am-1,n-1m-1,n-1) )5-7DGZ.SWFUData Structure二维数组的存储二维数组的存储lL O C 0 , 0 L O C 0 , 0 为 基 地 址为 基 地 址 , , 二 维 数 组二 维 数 组Ab1b2Ab1b2中元素中元素a aijij的存储位置为的存储位置为: :LOCi,jLOCi,j=LOC0,0+(b2=LOC0,0+(b2i+j)i+j)L L0=i=b1-10=i=b1-10=j=b2-10=j=b2-1L L每个数据元素所占的存储空间大小每个数据元素所占的存储空间大小5

8、-8DGZ.SWFUData Structure例例5.1: 5.1: 若若 L=2, LOC0,0 = 1000L=2, LOC0,0 = 1000，求，求LOC2,3LOC2,3l LOC2,3 = LOC0,0 + (5 LOC2,3 = LOC0,0 + (5* *2+3)2+3)* *L Ll = 1000 + 13 = 1000 + 13 * * 2 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

9、a24 a a30 a a31 a a32 a a33 a a345-9DGZ.SWFUData Structure三维数组的存储三维数组的存储l若若LOC0,0,0 LOC0,0,0 为基地址为基地址: : LOCi,j,kLOCi,j,k = LOC0,0,0+ = LOC0,0,0+ (n(n* *h h* *i+hi+h* *j+kj+k) )* *L L0 = i m0 = i m0 = j n0 = j n0 = k h0 = k h每个数据元素占每个数据元素占L L个存储单元个存储单元5-10DGZ.SWFUData Structure N N维数组存储维数组存储lb b1 1,

10、b,b2 2,.,b,.,bn n是是n n维数组维数组A A每一维的维每一维的维界界, ,数组元素数组元素A(jA(j1 1,j,j2 2,.,j,.,jn n) )的存储的存储位置为：位置为： LOCjLOCj1 1,j,j2 2,.j,.jn n=LOC0,0,.,0 + =LOC0,0,.,0 + (b (b2 2b b3 3b bn nj j1 1 + + b b3 3b bn nj j2 2 + . + . + b + bn nj jn n-1 -1 + j+ jn n ) )L LLjbjLOCnnikknii)()0 , 0 , 0(1115-11DGZ.SWFUData St

11、ructurenicbcLcjcLOCjjjLOCiiinniiin1 , , )0 , 0 , 0(,1121其中Sizeof(Elem Type)倒推公式倒推公式5-12DGZ.SWFUData Structurel例例: : 在在C C语言中语言中, ,设数组设数组A5678A5678的首地址为的首地址为2000,2000,每个元素占每个元素占2 2个字节；个字节；求元素求元素A3454A3454的地址。的地址。 LOC3,4,5,4 LOC3,4,5,4 = 2000+( = 2000+(6 6* *7 7* *8 8* *3 3+ +7 7* *8 8* *4 4+ +8 8* *5

12、 5+ +4 4) )* *2 2 = 2000+(1008+224+40+4) = 2000+(1008+224+40+4)* *2 2 = 4552 = 45525-13DGZ.SWFUData Structure数组顺序存储的表示和实现数组顺序存储的表示和实现#incluse stdarg.h#incluse #define MAX_ARRAY_DIM 8#define MAX_ARRAY_DIM 8typedef structtypedef struct ElemType ElemType * *base;base; int int dim; dim; int int * *bound

13、s; bounds; int int * *constants;constants;Array;Array;相当于相当于Loc(0,0)BiCi5-14DGZ.SWFUData Structurebasedimboundsconstantsa0a1aiat. 0 1 . dim-15-15DGZ.SWFUData Structure10 11 12 1320 21 22 2330 31 32 33A = 3.basedimboundsconstants 0 1 . dim-14821011313233= 25-16DGZ.SWFUData Structure5.3 5.3 矩阵的压缩存储矩阵的

14、压缩存储l矩矩 阵阵: : 二维数组二维数组l特殊矩阵特殊矩阵: : 大量大量重复元素重复元素或大量或大量0 0元素元素 l稀疏矩阵稀疏矩阵: : 大量大量0 0元素元素 l压缩存储压缩存储: : 重复元素重复元素只分配一个存储空间只分配一个存储空间, , 0 0元素元素不分配存储空间不分配存储空间5-17DGZ.SWFUData Structure5.3.1 5.3.1 特殊矩阵特殊矩阵l对对 称称 矩阵矩阵: a: aijij = a = ajiji (1=i,j=n) (1=i,j=n)l下三角矩阵下三角矩阵: : 当当ijij时时, aij, aij = 0, (1=i,j=n) =

15、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 a an2n2 a an3n3 . . a annnnA An nn n = =5-18DGZ.SWFUData Structure对称矩阵对称矩阵: a: aijij = a = ajiji (1=i , j=n) (1=i , j=ji

16、=j（下三角含对角线）（下三角含对角线） k= k= j(j-1)/2+i-1j(j-1)/2+i-1 当当ij ij （上三角）（上三角）5-20DGZ.SWFUData Structure例例5.3 5.3 对称矩阵对称矩阵ln = 5, 1+2+3+4+5 = 5n = 5, 1+2+3+4+5 = 5* *(5+1)/2 = 15(5+1)/2 = 15l一维数组一维数组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) ) 如如: :

17、 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 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 = =5-21DGZ.SWFUData Structure下三

18、角矩阵下三角矩阵: :当当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 a2323 0 . 0 .0 0A An nn n = 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 annnn5-

19、24DGZ.SWFUData Structurel一维数组一维数组SA0.3SA0.3* *n-3n-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,k=0,2,3,4,5,6,3n-3,3n-3,3n-3,3n-3）lsasak k 和和aai,ji,j 的一一对应关系的一一对应关系: : sak,k sak,k=3=3* *(i-1)+j-i(i-1)+j-i， 当当|i-j|=1

20、|i-j|1|i-j|15-25DGZ.SWFUData Structure例例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 3* *5-35-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 =

21、 3 a5,4 = 9 k = 3* *(5-1) + 4 - 5 = 11(5-1) + 4 - 5 = 11 故故: : sa11 = 9 sa11 = 95-26DGZ.SWFUData Structure5.3.2 5.3.2 稀疏矩阵稀疏矩阵l稀疏因子：稀疏因子：假设在假设在m mn n的矩阵中，有的矩阵中，有t t个元个元素不为零。令素不为零。令=t/(m=t/(mn n) )，称，称为矩阵的为矩阵的稀疏因子，通常稀疏因子稀疏因子，通常稀疏因子0.050.05时称为稀疏时称为稀疏矩阵。矩阵。 0 0 12 912 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0

22、 0 0 0 0 0 M M(6(67)7) = = -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 05-27DGZ.SWFUData Structure转置矩阵转置矩阵 0 0 0 0 -3-3 0 0 0 0 1515 1212 0 0 0 0 0 0 1818 0 0 9 9 0 0 0 0 2424 0 0 0 0T T(7(76)6) = =0 0 0 0 0 0 0 0 0 0 -7-7 0 0 0

23、 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 05-28DGZ.SWFUData Structure稀疏矩阵的存储结构稀疏矩阵的存储结构 一一. . 三元组顺序表三元组顺序表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 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

24、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 5-29DGZ.SWFUData Structure三元组顺序表结构定义三元组顺序表结构定义#define MAXSIZE 12500#define MAXSIZE 12500typedef structtypedef struct int int i, j; i, j; Elemtype Elemtype e; e; TripleTriple; ;typedeftypedef struct struct TripleTriple

25、dataMAXSIZE+1; dataMAXSIZE+1; int int mu,nu,tu mu,nu,tu; ; TSMatrixTSMatrix; ;lTSMatrixTSMatrix M, T; M, T;5-30DGZ.SWFUData StructureM.datap .i .j .e012.tumu nutu1212.64-75-31DGZ.SWFUData Structure求稀疏矩阵求稀疏矩阵M M的转置矩阵的转置矩阵T T012345678678121213931-3361443245218611564-7M.datap .i .j .e76813-316152112251

26、8319342446-76314012345678T.dataq .i .j .e方法：方法：1. 1. 将矩阵的将矩阵的行列值行列值相互相互交换交换； 2. 2. 将每个三元组中的将每个三元组中的i i、j j相互相互调换调换； 3. 3. 重排三元组之间的次序。重排三元组之间的次序。5-32DGZ.SWFUData Structure算法算法5.15.1：求稀疏矩阵：求稀疏矩阵M M的转置矩阵的转置矩阵T TStatus TransposeSMatrixStatus TransposeSMatrix(TSMatrix M,TSMatrix(TSMatrix M,TSMatrix &T) &

27、T) T.mu=M.nu; T.nu=M.mu; T.tu=M.tu T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; ; if (T.tu if (T.tu) q = 1;) q = 1; for (col = 1; col for (col = 1; col = = M.nuM.nu; +col; +col) ) for (p = 1; p = for (p = 1; p = M.tuM.tu; +p); +p) if (M.datap.j = col if (M.datap.j = col ) ) T.dataq.i = M.datap.j; T.dataq.i = M.

28、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; retrun retrun OK; OK;/TransposeSMatrix/TransposeSMatrix算法复杂度：算法复杂度： O(nu*tu)5-33DGZ.SWFUData Structure算法算法5.25.2：求转置矩阵的快速方法：求转置矩阵的快速方法l为了减少算法复杂度为了减少算法复杂度, ,增加两个向量增加两个向量numnum和和cpotcpot: :lnumc

29、olnumcol: 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=col=m.nu2=col=m.nu）5-34DGZ.SWFUData Structurel例例5.65.6 0 0 12 912 9 0 0 0 0 0 0 0 0 0 0 0 0

30、 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 3 5 7 8 8 95-35DGZ.SWFUD

31、ata Structurei 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 122 1 122 1 124 6 -74 6 -

32、7 colcol 1 2 3 4 5 6 7 1 2 3 4 5 6 7 cpot cpot 1 3 5 7 8 8 9 1 3 5 7 8 8 946297538M M 5-36DGZ.SWFUData StructureStatus FastTransposeSMatrix(TSMatrix M,TSMatrixStatus FastTransposeSMatrix(TSMatrix M,TSMatrix &T) &T) T.mu = M.nu; T.nu = M.mu; T.tu = M.tu T.mu = M.nu; T.nu = M.mu; T.tu = M.tu; ; if (T.

33、tu if (T.tu) for(col=1; col=M.nu; +col) numcol for(col=1; col=M.nu; +col) numcol = 0; = 0; for(t=1; t=M.tu for(t=1; t=M.tu; +t) +numM.datat.j; +t) +numM.datat.j; cpot1 = 1; cpot1 = 1; for(col=2; col=M.nu; +col for(col=2; col=M.nu; +col) ) cpotcol cpotcol=cpotcol-1+numcol-1;=cpotcol-1+numcol-1; for(p

34、=1; p=M.tu for(p=1; p=M.tu; +p); +p) col=M.datap.j; q=cpotcol col=M.datap.j; q=cpotcol; 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; +cpotcol+cpotcol; retrun retrun OK; OK; / FastTransposeSMatrix / FastTrans

35、poseSMatrix算法复杂度： O(nu+tu)5-37DGZ.SWFUData Structure三元组顺序表（有序的双下标法）小结三元组顺序表（有序的双下标法）小结特点特点/ /优点：优点： 非零元在表中按非零元在表中按行序行序有序存储，便于有序存储，便于进行依行序顺序处理的矩阵运算。进行依行序顺序处理的矩阵运算。缺点：缺点： 若需按行号存取某一行的非零元，则若需按行号存取某一行的非零元，则需从头开始进行查找。需从头开始进行查找。5-38DGZ.SWFUData Structure#define MAXRC 100typedef struct int i, j; Elemtype e;

36、Triple;二、行逻辑链接的顺序表二、行逻辑链接的顺序表（指出每一行的第一个非零元素在三元组中的位置）（指出每一行的第一个非零元素在三元组中的位置）typedef struct Triple dataMAXSIZE+1; int rposMAXRC+ 1; int mu,nu,tu;RLSMatrix;5-39DGZ.SWFUData Structure1212 . 64-7M.datap .i .j .e012.maxsize133567M.rposrow5-40DGZ.SWFUData Structure三、十字链表三、十字链表（行和列都是线性链表（行和列都是线性链表非线性结构）非线性结

37、构）5-41DGZ.SWFUData Structure row col val *right *down 非零元素结点：非零元素结点： mu nu tu *rhead *chead 表头结点：表头结点：十字链表：十字链表：5-42DGZ.SWFUData Structure1 什么是广义表什么是广义表 广义表也称为列表，是线性表的一种扩展，也是数据广义表也称为列表，是线性表的一种扩展，也是数据元素的有限序列。元素的有限序列。 记作：记作：LS= (d1, d2, . . . . . .dn)。其中。其中di既可以是单个元素，也可以是广义表。既可以是单个元素，也可以是广义表。说明说明 1）广义

38、表的定义是一个）广义表的定义是一个递归定义递归定义，因为在描述广义表时，因为在描述广义表时又用到了广义表；又用到了广义表； 2）在线性表中数据元素是单个元素，而在广义表中，）在线性表中数据元素是单个元素，而在广义表中， 元素可以是单个元素元素可以是单个元素, 称为称为单元素单元素(原子原子)，也可以是广，也可以是广义表，称为广义表的义表，称为广义表的子表子表； 3）n 是广义表长度；是广义表长度；5.4 广义表广义表5-43DGZ.SWFUData Structure4）下面是一些广义表的例子：）下面是一些广义表的例子： A = ( ) 空表，表长为空表，表长为0 B = (a,(b,c,d)

39、 B的表长为的表长为2，两个元，两个元素分别为素分别为 a 和子表（和子表（b,c,d) C = (e) C中只有一个元素中只有一个元素e，表长为，表长为1 D = (A,B,C,f ) D 的表长为的表长为4，它的前，它的前三个元素三个元素 A，B，C是是 广义表，第四个是单广义表，第四个是单元素元素 E=( a ,E ) 递归表递归表5-44DGZ.SWFUData Structure5）表头和表尾：表头和表尾： 若广义表不空，则可分成若广义表不空，则可分成表头表头和和表表尾尾，反之，一对表头和表尾可唯一确定，反之，一对表头和表尾可唯一确定一个广义表一个广义表 对非空广义表：对非空广义表：

40、 称第一个称第一个元素元素为为L的的表头表头 其余元素组成的其余元素组成的表表称为称为LS的的表尾表尾；5-45DGZ.SWFUData Structure例如：例如：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)=?5-46DGZ.SWFUData Structure广义表的元素之间除了存在广义表的元素之间除了存在次

41、序次序关系外，关系外，还存在还存在层次层次关系。如：关系。如：DABCfaDebcd5-47DGZ.SWFUData Structure5.5 广义表的存储结构广义表的存储结构 由于广义表中数据元素可以具有不同结由于广义表中数据元素可以具有不同结构，故难以用顺序结构表示广义表。通常采构，故难以用顺序结构表示广义表。通常采用用链表存储方式。链表存储方式。 如何设定链表结点？广义表中的数据元如何设定链表结点？广义表中的数据元素可能为单元素（原子）或子表，由此需要素可能为单元素（原子）或子表，由此需要两种结点：一种是两种结点：一种是表结点表结点，用以表示广义表；，用以表示广义表；一种是一种是单元素结

42、点单元素结点，用以表示单元素（原，用以表示单元素（原子）。子）。5-48DGZ.SWFUData Structuretag hp tp表结点表结点1 0 tag atom原子结点原子结点方法方法1：tag hp tp表结点表结点1 0 tag atom tp原子结点原子结点方法方法2：5-49DGZ.SWFUData Structure广义表的存储结构示例广义表的存储结构示例 1 1 A =() B =(e) C = (a,(b,c,d) D = (A,B,C) E = (a, E)5-50DGZ.SWFUData Structure广义表的存储结构示例广义表的存储结构示例 2 2 A =() B =(e) C = (a,(b,c,d) D = (A,B,C) E = (a, E)