数组与广义表相关知识cghc.pptx

《数组与广义表相关知识cghc.pptx》由会员分享，可在线阅读，更多相关《数组与广义表相关知识cghc.pptx（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、表表示示稀稀疏疏矩矩阵阵时进行矩阵运算采用的处理方法。时进行矩阵运算采用的处理方法。4.掌掌握握广广义义表表的的结结构构特特点点及及其其存存储储表表示示方方法。法。ADTArray 数据对象数据对象：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,bound1,.,boundn)DestroyArray(&A)Value(A

3、,&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是是n维数组，维数组，e为元素变量，为元素变量，随后是随后是n个下标值。个下标值。操作结果：操作结果：若各下标不超界，则若各下标不超界，则e赋值为赋值为所指定的所指定的A的

4、元素值，并返的元素值，并返回回OK。Assign(&A,e,index1,.,indexn)初始条件：初始条件：A是是n维数组，维数组，e为元素为元素变量，随后是变量，随后是n个下标值。个下标值。操作结果：操作结果：若下标不超界，则将若下标不超界，则将e的的值赋给所指定的值赋给所指定的A的元的元素，并返素，并返OK。二维数组的定义二维数组的定义:数据对象数据对象:D=aij|0ib1-1,0 jb2-1数据关系数据关系:R=ROW,COL ROW=|0ib1-2,0jb2-1 COL=|0ib1-1,0 jb2-2二维数组的定义二维数组的定义:5.2数数组的的顺序表示和序表示和实现类型特点类型

5、特点:（1）只有引用型操作，没有加工型操作；只有引用型操作，没有加工型操作；（2）数组是多维的结构，而存储空间是数组是多维的结构，而存储空间是一个一维的结构。一个一维的结构。有两种顺序映象的方式有两种顺序映象的方式:（1）以行序为主序以行序为主序（2）以列序为主序以列序为主序a00a01a0n-1a10a11a1n-1am-10am-11am-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

6、-1m*n-1m am-1n-1 .a1n-1 a0n-1 .am-11 .a11 a01 am-10 .a10 a00a00a01.a0n-1a10a11.a1n-1am-10am-11am-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)

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

8、Ci,j,k=LOC0,0,0+(n*h*i+h*j+k)*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维的的维界界,数数组元素元素A(jA(j1 1,j,j2

9、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 n)*)*L L i=1 k=i+1i=1 k=i+1 例例:在在C C语言中语言中,设设 数组数组A5678A5678的首地址为的首地址为 2000

10、,2000,每个元素占每个元素占2 2个字节个字节;求元素求元素A3454A3454的地址的地址.LOC3,4,5,4=2000+(6*7*8*3+7*8*4+8*5+4)*2 LOC3,4,5,4=2000+(6*7*8*3+7*8*4+8*5+4)*2 =2000+(336*3+56*4+8*5+1*4)*2 =2000+(336*3+56*4+8*5+1*4)*2 =2000+(1008+224+40+4)*2=4552 =2000+(1008+224+40+4)*2=4552推广到一般情况，可得到推广到一般情况，可得到n维数组数据元素存储位置维数组数据元素存储位置的映象关系的映象关系称

11、为称为n维数组的维数组的映象函数映象函数。数组元素的存储位置是。数组元素的存储位置是其下标的线性函数。其下标的线性函数。其中其中cn=L，ci-1=bici,1i n。LOC(j1,j2,.,jn)=LOC(0,0,.,0)+cijii=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*(j-1)+i-1)*L

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

13、(0=i=m,0=j=n,每个数据元素占每个数据元素占L L个存个存储单元元)LOCi,j,k=LOC0,0,0+(m*(n*k)+j)+i)*L LOCi,j,k=LOC0,0,0+(m*(n*k)+j)+i)*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,intdim,.);/若若维数数dim和随后的各和随后的各维长

14、度数合法度数合法,构造相构造相应的数的数组,并返回并返回OKDestroyArray(Array&A);/销毁数数组AValue(ArrayA,ElemType&e,.);若各下若各下标不超界不超界,则e赋值为所指定的所指定的A的元素的元素值,并返回并返回OKAssign(Array&A,ElemTypee,.)若各下若各下标不超界不超界,则将将e的的值赋给所指定的所指定的A的元素的元素,并返回并返回OKbasedimboundsconstantsa0a1aiat.01.dim-1.#include#include#define MAX_ARRAY_DIM 8/#define MAX_ARRA

15、Y_DIM 8/维数最大值维数最大值typedef struct typedef struct ElemType *base;/ElemType *base;/数组元素基址数组元素基址 int dim;/int dim;/维数维数 int *bounds;/int *bounds;/维界基址维界基址 int *constants;/int *constants;/映像函数常映像函数常量基址，除量基址，除dimdim外，均由外，均由InitArray分配分配Array;Array;练习假假设有二有二维数数组A68，每个元素用相，每个元素用相邻的的6个字个字节存存储，存，存储器按字器按字节编址。已

16、知址。已知A的起始存的起始存储位置位置（基地址）（基地址）为1000，计算：算：（1）数）数组A的体的体积（即存（即存储量）；量）；（2）数）数组A的最后一个元素的最后一个元素a57的第一个字的第一个字节的地的地址；址；（3）按行存）按行存储时，元素，元素a14的第一个字的第一个字节的地址；的地址；（4）按列存）按列存储时，元素，元素a47的第一个字的第一个字节的地址。的地址。5.3.1特殊矩阵特殊矩阵5.3矩阵的压缩存储矩阵的压缩存储5.3.2稀疏矩阵稀疏矩阵以常规方法，即以二维数组表示以常规方法，即以二维数组表示高阶的稀疏矩阵时产生的高阶的稀疏矩阵时产生的问题问题:(1)零值元素占了很大空

17、间零值元素占了很大空间;(2)计算中进行了很多和零值的运算。计算中进行了很多和零值的运算。(1)尽可能少存或不存零值元素；尽可能少存或不存零值元素；解决问题的原则解决问题的原则:(2)尽可能减少没有实际意义的运算；尽可能减少没有实际意义的运算；(3)操作方便。操作方便。即：即：能尽可能快地找到与下标值能尽可能快地找到与下标值(i，j)对对应的元素，应的元素，能尽可能快地找到同一行或同一列能尽可能快地找到同一行或同一列的非零值元。的非零值元。5.3.1特殊矩特殊矩阵 特殊矩阵是指非零元素或零元素在特殊矩阵是指非零元素或零元素在矩阵中的分布有一定规律的矩阵。矩阵中的分布有一定规律的矩阵。对称矩阵对

18、称矩阵元素满足条件元素满足条件aij=aji1=i,j=n的的n阶矩阵。阶矩阵。按行序为主序：按行序为主序：a11a12.a1na21a22.a2nan1an2.ann.a11 a21 a22 a31 a32 an1 ann.k=0 1 2 3 4 n(n-1)/2 n(n+1)/2-1 例5.2 对称矩阵n=5,1+2+3+4+5=5*(5+1)/2=15n=5,1+2+3+4+5=5*(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

19、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 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

20、-1)*La1100.0a21a220.0an1an2an3.ann.0a11 a21 a22 a31 a32 an1 ann.k=0 1 2 3 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对角矩阵对

21、角矩阵a11a120.0a21a22a230000an-1,n-2an-1,n-1an-1,n00an,n-1ann0a32a33a3400Loc(aij)=Loc(a11)+2(i-1)+(j-1)*L按行序为主序：按行序为主序：a11 a12 a21 a22 a23 ann-1 ann.k=0 1 2 3 4 3*n-3 saksak和和ai,jai,j的一一的一一对应关系关系:sak,k=3*(i-1)+j-i,sak,k=3*(i-1)+j-i,ai,j=ai,j=当当|i-j|=1|i-j|1|i-j|1 a a1111 a a1212 0 0.0 0 0.0 a a2121 a a

22、2222 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.3*5-3SA0.3*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

23、4 2 8 7 9 5)如如:a5,4=9:a5,4=9 k=3*(5-1)+4-5=11 k=3*(5-1)+4-5=11故故:sa11=9:sa11=95.3.2稀疏矩阵稀疏矩阵假设假设m行行n列列的矩阵含的矩阵含t个非个非零元素零元素，则称，则称为为稀疏因子稀疏因子。通常认为通常认为 0.05的矩阵为稀的矩阵为稀疏矩阵。疏矩阵。稀疏矩阵的压缩存储方法稀疏矩阵的压缩存储方法:一、三元组顺序表一、三元组顺序表二、行逻辑链接的顺序表二、行逻辑链接的顺序表三、三、十字链表十字链表#define MAXSIZE 12500 typedefstructint i,j;/该非零元的行下标和列下标 El

24、emType e;/该非零元的值 Triple;/三元组类型三元组类型一、三元组顺序表一、三元组顺序表typedefstruct Triple dataMAXSIZE+1;int mu,nu,tu;TSMatrix;/稀疏矩阵类型稀疏矩阵类型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 8T如何求转置矩阵？如何求转置矩阵？用常规的二维数组表示时的算法其时间复杂度为其时间复杂度为:O(munu)for(col=1;col=nu;+col)for(row=1;row=mu;+row

25、)Tcolrow=Mrowcol;678121213931-3361443245218611564-7ije0 1 2 3 4 5 6 7 8ije76813-3161521122518319342446-763140 1 2 3 4 5 6 7 8?M.dataT.data解决思路：解决思路：只要做到只要做到将矩阵行、列值互换；将矩阵行、列值互换；将每个三元组中的将每个三元组中的i和和j相互调换；相互调换；重排三元组次序，使重排三元组次序，使T.data中中元素以元素以N的行的行(M的列的列)为主序为主序方法一：按方法一：按M的列序转置的列序转置按按T.data中三元组次序依次在中三元组次序

26、依次在M.data中找到相应的三元组进行转置，中找到相应的三元组进行转置，即按照矩阵即按照矩阵M的列序的列序来进行置换。来进行置换。为找到为找到M中每一列所有非零元素，中每一列所有非零元素，需对其三元组表需对其三元组表M.data从第一行起扫从第一行起扫描一遍。由于描一遍。由于M.data中以中以M行序为主行序为主序，所以由此得到的恰是序，所以由此得到的恰是T.data中应中应有的顺序有的顺序。678121213931-3361443245218611564-7i j e0 1 2 3 4 5 6 7 8M.data76813-3161521122518319342446-76314ije0

27、1 2 3 4 5 6 7 8T.dataqppppppppqqqqppppppppcol=1col=2StatusTransposeSMatix(TSMatrixM,TSMatrix&T)/采用三元组表存储表示，求稀疏矩阵采用三元组表存储表示，求稀疏矩阵M的转置矩阵的转置矩阵T。T.mu=M.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.

28、e;+q;returnOK;/TransposeSMatrixT(n)=O(nu*tu)方法二：快速转置方法二：快速转置按按M.data中三元组次序转置，转置结果中三元组次序转置，转置结果放入放入T.data中恰当位置。中恰当位置。此法关键是要预先确定此法关键是要预先确定M中每一列第一中每一列第一个非零元在个非零元在T.data中位置，为确定这些位置，中位置，为确定这些位置，转置前应先求得转置前应先求得M的每一列中非零元个数。的每一列中非零元个数。实现：实现：设两个数组设两个数组numcol：表示矩阵：表示矩阵M中第中第col列中非零元个数列中非零元个数cpotcol：指示指示M中第中第col

29、列第一个非零元在列第一个非零元在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 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 pp

30、pppppp46297536 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 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;Col1234567Numcolcpotcolt1t1t1t1t2t2t2t10 01357889Status FastTransposeSMatrix(TS

31、Matrix M,TSMatrix&T)T.mu=M.nu;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=M.datap.e;+cpotcol

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

33、osMAXMN+1;/各行第一个非零元的位置表各行第一个非零元的位置表 int mu,nu,tu;RLSMatrix;/行逻辑链接顺序表类型二、行逻辑链接的顺序表二、行逻辑链接的顺序表M=N=Q=Q=MN113145 i j e1 2 3 4 31222-1M.data122211 i j e1 2 3 4 32431-2N.data21-1 i j e1 2 3 4 Q.dataparow 1 2 3 rposarow 134brow 1 2 3 4rposbrow 1235ccol 1 2ctempt1tpq6p126tpp2tq-1tp=5p1tq4324三、三、十字链表十字链表3 0

34、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*right,*down;struct OLNode*right,*down;OLNode;*OLink;OLNode;*OLink;Type struct Type struct OLink *rhead,*chead;OLink *rhead,*chead;int mu,nu,tu;int mu,nu,tu;CrossList;CrossList;5.4广义表的

35、类型定义广义表的类型定义ADTGlist 数据对象数据对象：Dei|i=1,2,.,n;n0;eiAtomSet 或 eiGList,AtomSet为某个数据对象 数据关系：数据关系：LR|ei-1,eiD,2inADT Glist基本操作基本操作:广义表是广义表是递归递归定义的定义的线性结构线性结构，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)D

36、EFa()d()bce广义表广义表LS=(1,2,n)的的结构特点结构特点:1)广义表中的数据元素有相对广义表中的数据元素有相对次序次序；2)广义表的广义表的长度长度定义为最外层包含元素个数；定义为最外层包含元素个数；3)广义表的广义表的深度深度定义为所含括弧的重数；定义为所含括弧的重数；注意：注意：“原子原子”的深度为的深度为0“空表空表”的深度为的深度为14)广义表可以广义表可以共享共享；5)广义表可以是一个广义表可以是一个递归递归的表。的表。递归表的深度是无穷值，长度是有限值递归表的深度是无穷值，长度是有限值。6)任何一个非空广义表任何一个非空广义表LS=(1,2,n)均可分解为均可分解

37、为表头表头GetHead(LS)=1和和表尾表尾GetTail(LS)=(2,n)两部分。两部分。例如例如:D=(E,F)=(a,(b,c)，F)GetHead(D)=EGetTail(D)=(F)GetHead(E)=aGetTail(E)=(b,c)GetHead(b,c)=(b,c)GetTail(b,c)=()GetHead(b,c)=bGetTail(b,c)=(c)GetHead(c)=cGetTail(c)=()练习求下列广求下列广义表操作的表操作的结果：果：（1）GetHead(p,h,w);（2）GetTail(a,b),(c,d);（3）GetHead(GetTail(a,

38、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 广义表的表示方法广义表的表示方法通常采用头、尾指针的链表结构通常采用头、尾

39、指针的链表结构表结点表结点:原子结点：原子结点：tag=1hptptag=0data链表存储表示TypedefenumATOM,LISTElemTag;/ATOM=0:原子，原子，LIST=1：子表：子表TypedefstructGLNodeElemTagtag;/区分原子或子表的公共区分原子或子表的公共标记union/原子原子/表表结点的点的联合部分合部分AtomTypeatom;/原子原子结点点值域域structstructGLNode*hp,*tp;ptr;/表表结点指点指针域域;*Glist;（1）表头、表尾分析法：表头、表尾分析法：构造存储结构的两种分析方法构造存储结构的两种分析方法

40、:若表头为原子，则为若表头为原子，则为空表空表 ls=NIL非空表非空表lstag=1指向表头的指针指向表尾的指针tag=0data否则，依次类推。否则，依次类推。L=(a,(x,y),(x)a(x,y)()1LL=()0a111110 x ()x练习按教科按教科书5.5节中中图5.8所示所示结点点结构，画出下列广构，画出下列广义表的存表的存储结构构图，并求它的深度。，并求它的深度。（1）(),a,(b,c),(),d),(e)（2(a),b),(),d),(e,f)（2）子表分析法：子表分析法：若子表为原子，则为若子表为原子，则为空表空表 ls=NIL非空表非空表指向子表1 的指针tag=0

41、atom否则，依次类推。否则，依次类推。指向子表2 的指针指向子表n 的指针111ls 1 tag=1hptp例如例如:LS=(a,(x,y),(x)0a11ls10 x0y10 x练习：练习：画画出下列广义表两种存储结构图出下列广义表两种存储结构图LS=(),A,(B,(C,D),(E,F)LS=(),A,(B,(C,D),(E,F)【南京航空航天大学南京航空航天大学 （1010分）分）】1.1.了了解解数数组组的的两两种种存存储储表表示示方方法法，并并掌掌握握数数组在以行为主的存储结构中的地址计算方法。组在以行为主的存储结构中的地址计算方法。2.2.掌掌握握对对特特殊殊矩矩阵阵进进行行压压

42、缩缩存存储储时时的的下下标标变变换公式。换公式。3.3.了了解解稀稀疏疏矩矩阵阵的的两两类类压压缩缩存存储储方方法法的的特特点点和和适适用用范范围围，领领会会以以三三元元组组表表示示稀稀疏疏矩矩阵阵时时进进行矩阵运算采用的处理方法。行矩阵运算采用的处理方法。本章学习要点本章学习要点4.4.掌握广义表的结构特点及其存储表示方掌握广义表的结构特点及其存储表示方法，读者可根据自己的习惯熟练掌握任意一法，读者可根据自己的习惯熟练掌握任意一种结构的链表，学会对非空广义表进行分解种结构的链表，学会对非空广义表进行分解的两种分析方法：即可将一个非空广义表分的两种分析方法：即可将一个非空广义表分解为表头和表尾两部分或者分解为解为表头和表尾两部分或者分解为n n个子表。个子表。Thats all for this chapter!Thank you for listening!