数据结构数组广义表学习教案

1、会计学1数据结构数据结构(sh j ji u)数组广义表数组广义表第一页，共69页。第第5 5章数组和广义章数组和广义(gungy)(gungy)表表 5.1 5.1 数组数组5.2 5.2 广义广义(gungy)(gungy)表表 教学内容教学内容Page 22022-4-19第1页/共69页第二页，共69页。5.1 数组数组Page 32022-4-19数据结构数据结构(sh j ji u)(sh j ji u)中的中的“数组数组”与高级语言与高级语言中的中的“数组数组”区别：区别：数据结构数据结构(sh j ji u)(sh j ji u)中的数组是一种线性结构中的数组是一种线性结构高级

2、语言中的数组是顺序结构；高级语言中的数组是顺序结构；第2页/共69页第三页，共69页。第3页/共69页第四页，共69页。Page 52022-4-19 多维数组多维数组 d(d3)维数组，看作一个由维数组，看作一个由d-1维数组作为数据元素的线维数组作为数据元素的线性表；性表； 数组是一种较复杂数组是一种较复杂(fz)的线性表结构，由简单的数据结构的线性表结构，由简单的数据结构即线性表辗转合成而得。即线性表辗转合成而得。三维数组 5.1.1 数组的定义数组的定义(dngy)第4页/共69页第五页，共69页。 5.1.1 数组的定义数组的定义(dngy)数组特点数组特点(tdin)数组结构固定数

3、组结构固定数据元素同构数据元素同构数组基本操作数组基本操作 (1) InitArray (&A,n,bound1, boundn) /构造构造(guzo)数组数组A (2) DestroyArray (&A) / 销毁数组销毁数组A (3) Value(A,&e,index1,indexn) /取数组元素值取数组元素值 (4) Assign (A,&e,index1,indexn) /给数组元素赋值给数组元素赋值第5页/共69页第六页，共69页。唯一的下标值对应；5.1.2数组的顺序数组的顺序(shnx)表示表示与实现与实现 已知以下三要素，求数组中任一元素的地

4、址： 开始结点的存放地址（即基地址） 维数和每维的上、下界(xi ji)； 每个数组元素所占用的单元数第6页/共69页第七页，共69页。a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 0 1 2 3 4 5 6 7 8 9l l l l l l l l l l LOC(ai) =一维数组5.1.2 数组的顺序表示数组的顺序表示(biosh)与与实现实现LOC(a1)+（i-1）*l第7页/共69页第八页，共69页。以行序为主序以行序为主序C, PASCAL5.1.2 数组的顺序表示数组的顺序表示(biosh)与与实现实现 二维数组通常(tngchng)有两种顺序存储方式： 以行序

5、为主序 以列序为主序第8页/共69页第九页，共69页。5.1.2 数组的顺序数组的顺序(shnx)表表示与实现示与实现 a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .Loc( aij)= 按行序为主序存放按行序为主序存放 amn . am2 am1 . a2n . a22 a21 a1n . a12 a1101n-1m*n-1nLoc(a11)+(i-1)n+(j-1)*L 第9页/共69页第十页，共69页。 以列序为主序FORTRAN 二维数组通常(tngchng)有两种顺序存储方式： 以行序为主序 以列序为主序5.1.2 数组的顺序表示数组的顺序表示

6、(biosh)与实现与实现第10页/共69页第十一页，共69页。 按列序为主序存放按列序为主序存放01m-1m*n-1m amn . a2n a1n . am2 . a22 a12 am1 . a21 a11 a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .Loc(aij)=5.1.2 数组的顺序表示数组的顺序表示(biosh)与与实现实现Loc(a11)+(j-1)m+(i-1)*L第11页/共69页第十二页，共69页。111101121202111101101000nmamamanaaanaaanaaaa按列优先按列优先(yuxin) LOC ( i,

7、 j ) = a + ( j* m +i ) * l第12页/共69页第十三页，共69页。LOC ( i1, i2, i3 ) = a + ( i1* m2 * m3 + i2* m3 + i3 ) * l 前前i1页页总总元素元素(yun s)个数个数第第i1页页的的前前i2行行总元素总元素(yun s)个数个数第13页/共69页第十四页，共69页。limianjnjknkj*111LOC ( i1, i2, , in ) = a + ( i1*m2*m3*mn + i2*m3*m4*mn+ + + in-1*mn + in ) * l 第14页/共69页第十五页，共69页。Page 162

8、022-4-19第15页/共69页第十六页，共69页。Page 172022-4-195.1.3矩阵矩阵(j zhn)的压缩存的压缩存储储第16页/共69页第十七页，共69页。1. 什么是压缩存储？什么是压缩存储？若多个数据元素的值都相同，则只分配一个元素值的存储空若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。间，且零元素不占存储空间。2. 什么样的矩阵能够压缩？什么样的矩阵能够压缩？ 一些一些(yxi)特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，特殊矩阵，如：对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。稀疏矩阵等。3. 什么叫稀疏矩阵？什么叫稀疏矩阵？矩阵中非零

9、元素的个数较少（一般小于矩阵中非零元素的个数较少（一般小于5%）5.1.3 矩阵矩阵(j zhn)的压缩存的压缩存储储第17页/共69页第十八页，共69页。5.1.3 矩阵的压缩矩阵的压缩(y su)存储存储1. 对称对称(duchn)矩阵矩阵 a0,0 a0,1 . . A0,n-1 a1,0 a1,1 . . A1,n-1 an-1,0 an-1,1 . An-1,n-1 . ajiaij特点特点 在在nn的矩阵的矩阵a中，满足如下性质中，满足如下性质(xngzh)：aij=aji (1 i, j n)存储方法存储方法 只存储下只存储下(或者上或者上)三角三角(包括主对角线包括主对角线)的

10、数据元素。共占的数据元素。共占用用n(n+1)/2个元素空间。个元素空间。第18页/共69页第十九页，共69页。5.1.3 矩阵的压缩矩阵的压缩(y su)存储存储1. 对称对称(duchn)矩阵矩阵 jiijjjijiik,2/)1(，2/)1(a0,0 a1,0 a1,1 a2,0 a2,1 aij an-1,n-1 . 0 1 2 3 4 k n(n+1)/2-1 按行序为主序：按行序为主序：ajiaijb a0,0 a0,1 . . A0,n-1 a1,0 a1,1 . . A1,n-1 an-1,0 an-1,1 . An-1,n-1 . 第19页/共69页第二十页，共69页。Pag

11、e 212022-4-191. 对称对称(duchn)矩阵矩阵 对称对称(duchn)矩阵矩阵 typedef int Elemtype;typedef struct sp_Matrix Elemtype *data;sp_Matrix;定义一个(y )压缩矩阵结构void InitMatrix(sp_Matrix *M） M-data=(Elemtype *)malloc(sizeof(Elemtype)*(N*(N+1/2);初始化对称矩阵的压缩矩阵第20页/共69页第二十一页，共69页。Page 222022-4-191. 对称对称(duchn)矩阵矩阵 对称对称(duchn)矩阵矩阵

12、void AssignMatrix(sp_Matrix *M,Elemtype e,int i,int j) if(i=j) M-datai*(i+1)/2+j=e; else M-dataj*(j+1)/2+i=e;指定缩矩阵(j zhn)结构中的元素void PrintMatrix(sp_Matrix *M)/ int i,j; for(i=0;iN;i+) for(j=0;jj n(n+1)/2 ij5.1.3 矩阵矩阵(j zhn)的压缩存的压缩存储储 a0,0 0 0 . 0 a1,0 a1,1 0 . 0 an-1,0 an-1,1 an-1,2. an-1,n-1 . 0a0,0

13、 a1,0 a1,1 a1,2 a2,1 ai,j an-1,n-1 . 0 1 2 3 4 k n(n+1)/2-1 n(n+1)/2 按行序为主序：按行序为主序：0第23页/共69页第二十四页，共69页。 对角矩阵中，所有对角矩阵中，所有(suyu)(suyu)的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。 666556555445444334333223222112111001000000

14、00000000000000000000000000aaaaaaaaaaaaaaaaaaa 5.1.3 矩阵的压缩矩阵的压缩(y su)存储存储第24页/共69页第二十五页，共69页。 66655655544544433433322322211211100100000000000000000000000000000000aaaaaaaaaaaaaaaaaaa 5.1.3 矩阵的压缩矩阵的压缩(y su)存储存储术语(shy)b矩阵半带宽：主对角线上下方各有b条次对角线；(2b+1)矩阵的带宽。在一个nn的带宽为三的对角矩阵中，只有n+n-1+n-1个非零元素，故只需3n-2个存储单元即可，零元

15、已不占用存储单元。 第25页/共69页第二十六页，共69页。5.1.3 矩阵的压缩矩阵的压缩(y su)存储存储（a1,0 a2,1 a3,2 an-2,n-1）,有有j=i-1 66655655544544433433322322211211100100000000000000000000000000000000aaaaaaaaaaaaaaaaaaa （a0,0 a1,1 a2,2 an-1,n-1）,有有j=i（a0,1 a1,2 a2,3 an-2,n-1）,有有j=i+1第26页/共69页第二十七页，共69页。5.1.3 矩阵的压缩矩阵的压缩(y su)存储存储（a1,0 a2,1 a

16、3,2 an-2,n-1）,有有j=i-1（a0,0 a1,1 a2,2 an-1,n-1）,有有j=i（a0,1 a1,2 a2,3 an-2,n-1）,有有j=i+1用i、j确定(qudng)k前i行元素个数：2+3(i-1)=3i-1aij是本行第1个非零元素，k=3i-1 aij是本行第2个非零元素，k=3iaij是本行第3个非零元素，k=3i+1 =2i+j=2i+j=2i+j第27页/共69页第二十八页，共69页。Page 292022-4-191. 1. 数组数组A0.4,-1.-3,5.7A0.4,-1.-3,5.7中含有中含有(hn yu)(hn yu)元素的个数（元素的个数

17、（ ）。）。 A A55 B55 B45 C45 C36 D36 D16162.2.设二维数组设二维数组A1. mA1. m，1. n1. n（即（即m m行行n n列）按行存储列）按行存储(cn ch)(cn ch)在数组在数组B1. mB1. m* *nn中，则二维数组元素中，则二维数组元素Ai,jAi,j在一维数组在一维数组B B中的下标为（中的下标为（ ）。）。 A A(i-1)(i-1)* *n+j Bn+j B(i-1)(i-1)* *n+j-1 n+j-1 C Ci i* *(j-1) D(j-1) Dj j* *m+i-1 m+i-1 3.3.若对称矩阵若对称矩阵A1.n,1.

18、nA1.n,1.n以行序为主序方式将其下三角形的元素以行序为主序方式将其下三角形的元素( (包括主对角线上所有元素包括主对角线上所有元素) )依次依次(yc)(yc)存放于一维数组存放于一维数组B1.(n(n+1)/2B1.(n(n+1)/2中，则在中，则在B B中确定中确定aijaij（ijirow=M; Mt-col=N; Mt-num=0; /非零元素(yun s)个数先赋值为0 for(i=0;iM;i+) for(j=0;jdataMt-num.r=i; Mt-dataMt-num.c=j; Mt-dataMt-num.e=Aij; Mt-num+; 行行行行( (r ro ow w

19、) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 0 0 0 3 3 2 22 2 1 0 0 6 6 1 15 5 2 1 1 1 1 1 11 1 3 1 1 5 5 1 17 7 4 2 2 3 3 - - - -6 6 5 3 3 5 5 3 39 9 6 4 4 0 0 9 91 1 7 5 5 2 2 2 28 8678 0000280000000091039000000006000017000110150022000第38页/共69页第三十九页，共69页。Page 402022-4-193）稀疏）稀疏(xsh)矩阵的基本操作矩阵的

20、基本操作bool Getvalue(SMatrix *Mt,ElemType *x,int i,int j); /获取(huq)指定位置的元素值赋给变量x 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 0 0 0 3 3 2 22 2 1 0 0 6 6 1 15 5 2 1 1 1 1 1 11 1 3 1 1 5 5 1 17 7 4 2 2 3 3 - - - -6 6 5 3 3 5 5 3 39 9 6 4 4 0 0 9 91 1 7 5 5 2 2 2 28 8678 int k=0; if(i

21、=Mt-row | j=Mt-col) /判断位置是否(sh fu)合理 return false; while(knum & iMt-datak.r)k+; while(knum & jMt-datak.c) k+; if(i=Mt-datak.r & j=Mt-datak.c) / 找到了*x=Mt-datak.e; else *x=0; /没找到，则为稀疏矩阵中的零值元素 return true;第39页/共69页第四十页，共69页。Page 412022-4-193）稀疏）稀疏(xsh)矩阵的基本操作矩阵的基本操作思考(sko)：为三元组元素赋值。 行行行行(

22、(r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 0 0 0 3 3 2 22 2 1 0 0 6 6 1 15 5 2 1 1 1 1 1 11 1 3 1 1 5 5 1 17 7 4 2 2 3 3 - - - -6 6 5 3 3 5 5 3 39 9 6 4 4 0 0 9 91 1 7 5 5 2 2 2 28 8 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 0 0 0 3 3 2 22 2 1 0 0 6 6 1 15 5

23、2 1 1 1 1 1 11 1 3 1 1 5 5 1 17 7 4 2 2 3 3 - - - -6 6 5 3 3 5 5 3 39 9 6 4 4 0 0 9 91 1 7 5 5 2 2 2 28 8 行行行行( (r ro ow w) ) 列列列列( (c co ol l) ) 值值值值( (v va al lu ue e) ) 0 0 0 3 3 2 22 2 1 0 0 6 6 1 15 5 2 1 1 1 1 1 11 1 3 1 1 5 5 1 17 7 4 2 2 3 3 - - - -6 6 5 3 3 5 5 3 39 9 6 4 4 0 0 9 91 1 7 5 5

24、 2 2 2 28 8情况一：为指定(zhdng)的非零元素重新赋值。例如：i=2，j=3，e=8情况二：指定的元素为零值元素例如：i=2，j=4，e=885 2 4 8678第40页/共69页第四十一页，共69页。3）稀疏）稀疏(xsh)矩阵的基本操作矩阵的基本操作7600070015000001800000240001400003000000000009120M6700000000014000000007000000024009018000121500300N转置转置(zhun zh)第41页/共69页第四十二页，共69页。3）稀疏）稀疏(xsh)矩阵的基本操作矩阵的基本操作row col

25、 valuerow col value0 01 12 23 34 45 56 67 78 82 0 -32 0 -35 0 155 0 150 1 120 1 124 1 184 1 180 2 90 2 93 2 243 2 245 3 -75 3 -72 5 142 5 146 7 86 7 8row colv alue row colv alue 0 01 12 23 34 45 56 67 78 81 0 121 0 123 5 -73 5 -70 2 -30 2 -32 3 242 3 240 5 150 5 152 0 92 0 95 2 145 2 141 4 181 4 187

26、 6 87 6 8row colv alue row colv alue 0 01 12 23 34 45 56 67 78 81 0 121 0 123 5 -73 5 -70 2 -30 2 -32 3 242 3 240 5 150 5 152 0 92 0 95 2 145 2 141 4 181 4 187 6 87 6 8MN第42页/共69页第四十三页，共69页。3）稀疏）稀疏(xsh)矩阵的基本操作矩阵的基本操作row col valuerow col value0 01 12 23 34 45 56 67 78 82 0 -32 0 -35 0 155 0 150 1 120

27、 1 124 1 184 1 180 2 90 2 93 2 243 2 245 3 -75 3 -72 5 142 5 146 7 86 7 8row colv alue row colv alue 0 01 12 23 34 45 56 67 78 81 0 121 0 123 5 -73 5 -70 2 -30 2 -32 3 242 3 240 5 150 5 152 0 92 0 95 2 145 2 141 4 181 4 187 6 87 6 8转置运算转置运算(yn sun)算法一：按照算法一：按照M的列序来进行转换的基本思想的列序来进行转换的基本思想对对 M 从头至尾扫描：从

28、头至尾扫描：第一次扫描时，将第一次扫描时，将 M 中列号为中列号为0的所有元组交换行列值后，依次赋值到的所有元组交换行列值后，依次赋值到 N 中中。第二次扫描时，将第二次扫描时，将 N 中列号为中列号为1的所有元组交换行列值后，依次赋值到的所有元组交换行列值后，依次赋值到 N 中中。依此类推，直至将依此类推，直至将 M 的所有三元组赋值到的所有三元组赋值到 N 中。中。MN第43页/共69页第四十四页，共69页。i j vi j v0 1 120 1 120 2 90 2 92 0 -32 0 -32 5 142 5 143 2 243 2 244 1 184 1 185 0 155 0 15

29、5 3 -75 3 -7i j vi j v2 0 -32 0 -31 4 181 4 180 2 -30 2 -35 0 155 0 150 5 150 5 150 1 120 1 121 0 121 0 124 1 184 1 180 2 90 2 92 0 92 0 93 2 243 2 242 3 242 3 245 3 -75 3 -73 5 -73 5 -72 5 142 5 145 2 145 2 14M M矩阵矩阵(j (j zhn)zhn)N N矩阵矩阵(j (j zhn)zhn)对对M M七次扫描完成转置七次扫描完成转置(zhun zh)(zhun zh)运算运算第一次扫描

30、查找第第一次扫描查找第0 0列元素列元素第一次扫第一次扫描结束描结束第二次扫第二次扫描结束描结束第二次扫描查第二次扫描查找第找第1 1列元素列元素第三次扫描查找第第三次扫描查找第2 2列元素列元素第四次扫描查第四次扫描查找第找第3 3列元素列元素第五次扫描查找第五次扫描查找第第4 4列元素列元素第六次扫描查第六次扫描查找第找第5 5列元素列元素0 01 12 23 34 45 56 67 76 7 86 7 87 6 87 6 83）稀疏矩阵的基本操作）稀疏矩阵的基本操作第七次扫描查第七次扫描查找第找第6 6列元素列元素MN第44页/共69页第四十五页，共69页。Page 462022-4-1

31、93）稀疏）稀疏(xsh)矩阵的基本操作矩阵的基本操作void TransposeMatrix(SMatrix *Mt,SMatrix *T)/Mt转置为T； int i,j,k=0; /k为转置后T的下标标识值 T-row=Mt-col; T-col=Mt-row; T-num=Mt-num; for(i=0;icol;i+) /依次扫描(somio)Mt中的每一列 for(j=0;jnum;j+) /依次扫描(somio)每一个非零元素 if(Mt-dataj.c=i) T-datak.r=Mt-dataj.c; /将该元素行列互换放在T中 T-datak.c=Mt-dataj.r; T-

32、datak.e=Mt-dataj.e; k+; /*如果扫描的非零元素(yun s)的列值为当前列，则表示在当前列中找到了非零元素(yun s)*/设置转置后的矩阵T的行、列、非零元素个数算法分析：算法分析：设矩阵三元组表总共有设矩阵三元组表总共有 Terms Terms 项，其时间代价为项，其时间代价为 OO ( ( ColsCols* * Terms Terms ) )。 T(n)=T(n)=O(O(M M的列数的列数n n 非零元个数非零元个数t)t)第45页/共69页第四十六页，共69页。3）稀疏）稀疏(xsh)矩阵的基本操作矩阵的基本操作row col valuerow col va

33、lue0 01 12 23 34 45 56 67 78 82 0 -32 0 -35 0 155 0 150 1 120 1 124 1 184 1 180 2 90 2 93 2 243 2 245 3 -75 3 -72 5 142 5 146 7 86 7 8row colv alue row colv alue 0 01 12 23 34 45 56 67 78 81 0 121 0 123 5 -73 5 -70 2 -30 2 -32 3 242 3 240 5 150 5 152 0 92 0 95 2 145 2 141 4 181 4 187 6 87 6 8M中每一列(y

34、 li)非零元素个数c0：2c1：2c2：2c3：1C4：0c5：1c6：0MT第46页/共69页第四十七页，共69页。3）稀疏）稀疏(xsh)矩阵的基本操作矩阵的基本操作第47页/共69页第四十八页，共69页。7600070015000001800000240001400003000000000009120Mcolnumcolcpotcol0212223140516002467783）稀疏）稀疏(xsh)矩阵的基本操作矩阵的基本操作第48页/共69页第四十九页，共69页。3）稀疏）稀疏(xsh)矩阵的基本操作矩阵的基本操作void TransposeMatrix2(SMatrix *M,SM

35、atrix *T) T-row=Mt-col; T-col=Mt-row; T-num=Mt-num; /为两个辅助向量(xingling)开辟空间 int *num=(int *)malloc(sizeof(int)* Mt-col) assert(num!=NULL); int * cpot=(int *)malloc(sizeof(int)*Mt-col); assert(cpot!=NULL); /开辟空间,存放M中每一列中非零元素的个数/开辟空间，用cpot存放M中每一列非零元素转置后存放的起始位置第49页/共69页第五十页，共69页。3）稀疏）稀疏(xsh)矩阵的基本操作矩阵的基本

36、操作if(Mt-num!=0) for(int col=0;colcol;col+) /初始化num numcol=0; int t; for(t=0;tnum;t+) numMt-datat.c+; /计算每一列中第一个非零元素的起始位置 cpot0=0; /第0列第一个元素的起始位置为0 for(int col=1;colcol;col+) cpotcol=cpotcol-1+numcol-1; /依次从第1列开始(kish),当前列非零元素的起始位置/*查看查看(chkn)每个元素所在的列数每个元素所在的列数,并并将对应的将对应的num个数个数+；*/第50页/共69页第五十一页，共69

37、页。3）稀疏）稀疏(xsh)矩阵的基本操作矩阵的基本操作int q=0;for(int p=0;pnum;p+) int col=Mt-datap.c; /依次获取非零元素所在列 q=cpotcol; /再将第col列存放的首个位置赋值给q T-dataq.r=Mt-datap.c; T-dataq.c=Mt-datap.r; T-dataq.e=Mt-datap.e; /col列中已经有元素占用了，所以要将位置向下移动(ydng)一个 cpotcol+; free(num); /释放空间 free(cpot);/根据起始位置(wi zhi)，在T中放置M转置后的非零元素第51页/共69页第五

38、十二页，共69页。Page 532022-4-19只保存(bocn)非零值为每一行设置一个(y )单独链表，同时也为每一列设置一个(y )单独链表。5.1.4 稀疏稀疏(xsh)矩阵矩阵4）稀疏矩阵的十字链表表示方法）稀疏矩阵的十字链表表示方法34008000450003A113418225234第52页/共69页第五十三页，共69页。 数据元素结点数据元素结点(ji din)定义：定义：typedef struct nodetypedef struct node int row,col,val; int row,col,val; struct node struct node * *down

39、, down, * *right;right;MatNode;MatNode;row col valdownright34008000450003A1134182252345.1.4 稀疏稀疏(xsh)矩阵矩阵4）稀疏矩阵的十字）稀疏矩阵的十字(sh z)链表表示方法链表表示方法第53页/共69页第五十四页，共69页。 补充：十字补充：十字(sh z)链表具体实现链表具体实现4）稀疏矩阵的十字）稀疏矩阵的十字(sh z)链表表示方法链表表示方法Mt=1 0 0 20 0 3 00 0 0 4第54页/共69页第五十五页，共69页。第第5 5章数组和广义章数组和广义(gungy)(gungy)表

40、表 5.1 5.1 数组数组5.2 5.2 广义广义(gungy)(gungy)表表 教学内容教学内容Page 562022-4-19第55页/共69页第五十六页，共69页。Page 572022-4-195.2广义广义(gungy)表表（1）定义(dngy) 广义表是具有n个元素的有限序列.记为： GL=( a1,a2,an)注意: 一个广义表通常用一对圆括号括起来，n是它的长度 ai可以是单个元素，也可以是广义表，分别叫原子和子表,子表再用一对圆括号括起来. 用大写字母表示广义表的名称,用小写字母表示原子 广义表非空时，第一个元素a1为LS的表头(head)，其余(qy)元素组成的表(a2

41、,a3,an)时LS的表尾(tail)第56页/共69页第五十七页，共69页。(1)A=( ) (2)B=(a,（b,c） )(3) C=(x,y,z) (4) D=(B,C) (5) E=(a,E) 5.2 广义广义(gungy)表表A为空表，长度为空表，长度(chngd)为为0。B是长度为是长度为2的广义表，第一项为原子，第二项为子表。的广义表，第一项为原子，第二项为子表。C是长度为是长度为3的广义表，每一项都是原子。的广义表，每一项都是原子。D是长度为是长度为2的广义表，每一项都是上面提到的子表。的广义表，每一项都是上面提到的子表。是长度为是长度为2的广义表，第一项为原子，第二项为它本身

42、。的广义表，第一项为原子，第二项为它本身。(6)广义表（广义表（ ）、）、 ( ( ) )的长度分别为的长度分别为_ 、 _ 。 01第57页/共69页第五十八页，共69页。一个广义表的深度是指该广义表展开后所含括号一个广义表的深度是指该广义表展开后所含括号的层数。的层数。例如，例如，A=(b,c)的深度为的深度为1，B=(A,d)的深度为的深度为2，C=(f,B,h)的深度为的深度为3。示例示例(shl):设有广义表设有广义表D(a,b,D)，其长度为，其长度为_，深度为，深度为_。广义表广义表(a,(a,b),d,e,(i,j),k)的长度是的长度是_，深度是，深度是_。5.2 广义广义(

43、gungy)表表3无穷53第58页/共69页第五十九页，共69页。Page 602022-4-195.2 广义广义(gungy)表表A=()B=(e)C=(a,(b,c,d)D=(),(e),(a,(b,c,d)E=(a,(a,b),(a,b),c)第59页/共69页第六十页，共69页。若广义表若广义表LSLS（n=1)n=1)非空，则非空，则a1a1是是LSLS的表头，其余的表头，其余元素组成的表元素组成的表(a1,a2,an)(a1,a2,an)称为称为LSLS的表尾。的表尾。任何一个非空广义表其表头可能任何一个非空广义表其表头可能(knng)(knng)是原子表，是原子表，也可能也可能(

44、knng)(knng)是广义表，而其表尾必定是广义表。是广义表，而其表尾必定是广义表。广义广义(gungy)表表(a),a)的表头是的表头是 ，表尾是，表尾是 。 广义广义(gungy)表表(a,b),c,d)的表头是的表头是 ，表尾是，表尾是 。广义广义(gungy)表表(a,b,c,d)的表头是的表头是 ，表尾是，表尾是 。5.2 广义表广义表(a)(a)(a,b)(c,d)(b,c,d)a第60页/共69页第六十一页，共69页。设设HAEDpHAEDp为求广义表为求广义表p p的表头函数，的表头函数，TAILpTAILp为求为求广义表广义表p p的表尾函数，其中的表尾函数，其中是函数的符

45、号是函数的符号(fho)(fho)，给，给出下列广义表的运算结果：出下列广义表的运算结果：HEADHEAD（a a，b b，c c） 的结果是的结果是_ _ _ _ _。TAILTAIL（a,b,ca,b,c） 的结果是的结果是_ _ _。HEAD(a),(b)HEAD(a),(b)的结果是的结果是_ _ _。TAIL(a),(b)TAIL(a),(b)的结果是的结果是_。HEADTAIL(a,b,c)HEADTAIL(a,b,c)的结果是的结果是_ _ _TAILHEAD(a,b),(c,d)TAILHEAD(a,b),(c,d)的结果是的结果是_ _ _。HEADHEAD(a,b),(c,

46、d)HEADHEAD(a,b),(c,d)的结果是的结果是_ _ _。TAILTAIL(a,(c,d)TAILTAIL(a,(c,d)的结果是的结果是_ _ _。5.2 广义广义(gungy)表表第61页/共69页第六十二页，共69页。由于广义表由于广义表(a1,a2,a3,an)(a1,a2,a3,an)中的数据元素中的数据元素(yun s)(yun s)可以具有不同的结构，（或是原子，或是广义表），因可以具有不同的结构，（或是原子，或是广义表），因此，难以用顺序存储结构表示，通常采用链式存储结构，此，难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素每个数据元素(yun s)(yun