第5章数组和广义表1．教学目的：掌握数组和广义表的定义、特点及典型算法。2．教学要求：①掌握数组在以行为主的存储结构中的地址计算方法。②掌
握矩阵实现压缩存储时的下标变换。③理解稀疏矩阵的两种存储方式的特点和适用范围，领会以三元组表示稀疏矩阵时进行运算采用的处理方法。④
掌握广义表的定义及其存储结构，学会将广义表分解为表头，表尾的方法。3．教学重点：①掌握特殊矩阵的压缩存储。②掌握稀疏矩阵采用三元组
存储时典型算法的实现。③广义表的定义、运算。4．教学难点：数组的十字链表存储结构。5.1数组5.1.1数组的逻辑结构数组（
Array）是非常有用的数据结构，几乎所有的高级程序设计语言都提供了数组类型。特点：元素本身可以是具有某种结构的数据，但属于同一
数据类型。比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，依此类推。A=(α1α2…
αj…αn)a11a12…a1j…a1na21a22…a2j…a2na11a12…
a1j…a1na21a22…a2j…a2nAm×n=Am×n=ai1ai2…aij…ain
…………ai1ai2…aij…ainam1am2…amj…amn…………am1am2…a
mj…amnB=(a11a12…a1j…a1na21a22…a2j…a2nβ1β2Am×n=
………………………ai1ai2…aij…ainβi………………………am1am2…amj…amnβ
m如图是一个m行n列的二维数组矩阵Am×n看成n个列向量的线性表，也可看成m个行向量的线性表推广：n维数组—每个数据元素受n
个关系的约束，任一单个关系，仍是线性关系。数组Array是标量：有大小，无方向向量Vector是矢量：有大小，有方向数组的抽
象数据类型ADTArray{数据对象:数据关系:通过以上分析可总结出数组具有以下性质：⑴数组中数据元素数目固定。⑵数组中数
据元素具有相同的数据类型。⑶数组中每一个数据元素由唯一的一组下标来标识。⑷数组是随机存取的存储结构。在数组上不能做插入、删除数
据元素的操作。通常在各种高级语言中，数组一旦被定义，每一维的大小及上下界都不能改变。两种操作：⑴取值操作：给定一组下标，读其对应
的数据元素。⑵赋值操作：给定一组下标，存储或修改其相对应的数据元素。基本操作:(1)InitArray(&A,n,bou
nd1,?boundn)//构造数组A(2)DestroyArray(&A)/
/销毁数组A(3)Value(A,&e,index1,…,indexn)//取数组元素值(4)Assign(A,
&e,index1,…,indexn)//给数组元素赋值}ADTArray二维数组形式化表示为：A=(D,R)D={a
0,0,a0,1,……a0,m,……,am-1,n-1}R={Row,Col}Row={,2>……,……,……}Col={,0>……,……,……｝其中Row是行关系，Col是列关系a11a11a12a
21a11a12a13a13a12a21a22a23a21a22a22a13(c)以列为主序(a)2×3数组的逻辑状态(b)
以行为主序a23a23图5.22×3数组的物理状态5.1.2数组的存储结构数组的顺序存储结构有两种：1.按行序存储（行
优先）如：BASIC、COBOL和PASCAL语言。2.按列序存储（列优先）如：FORTRAN语言。一维数组a,
i=0LOC(i)=LOC(i-1)+l=a+il,i>00123
456789a3527491860547783
4102lllllllll
la+ilLOC(i)=LOC(i-1)+l=a+il二维数组以行序为主序C,PASCAL以列序为主序FORT
RAN二维数组的行序优先表示a[n][m]设数组开始存放位置LOC(0,0)=aLOC(j,k)=a
+jm+k三维数组按页/行/列存放，页优先的顺序存储①②③三维数组a[m1][m2][m3]各维元素个数
为m1,m2,m3下标为i1,i2,i3的数组元素的存储位置：LOC(i1,i2,i3)=a+
i1m2m3+i2m3+i3前i1页总元素个数第i1页的前i2行总元素个数第i2行前i3列元素个数
n维数组各维元素个数为m1,m2,m3,…,mn下标为i1,i2,i3,…,in的数组元素的存储位置：
设有二维数组Amn，按元素的下标求其地址的计算：设数组的基址为LOC(a11)，每个数组元素占据k个地址单元，那么aij的物理地址
计算：aij前面有i-1行，每行n个元素，第i行前面有j-1个元素1以“以行为主序”的分配为例：LOC(aij)=LOC(a1
1)+((i-1)n+j-1)k2以“以列为主序”的分配比例：LOC(aij)=LOC(a11)+((j-1)m+(i-
1))k3在C语言中，数组中每一维的下界定义为0，则：LOC(aij)=LOC(a00)+(in+j)k对于三维数组A
mnp，即m?×?n?×?p数组，对于数组元素aijk，其物理地址为：Loc(aijk)=Loc(a111)+((i-1)×n×
p+(j-1)×p+k-1)×L推广到一般的三维数组：A[c1..d1][c2..d2][c3..d3]，则aijk的物理地址为L
oc(aijk)=Loc(ac1c2c3)+((i-c1)×(d2-c2+1)×(d3-c3+1)?+(j-c2)×(d3-
c3+1)+(k-c3))×L对于n维数组A(c1..d1,c2..d2,…,cn..dn)，我们只要把上式推广，就可以容易
地得到ｎ维数组中任意元素aj1j2…jn的存储地址的计算公式：容易看出，数组元素的存储位置是其下标的线性函数，一旦数组下标确定之
后，数组中的元素可随机存取。我们称具有这一特点的存储结构为随机存储结构。a[0][0]数组a11矩阵数组Array信息科学概
念可以是多维的矩阵Matrix数学概念，元素只能是数字，二维矩阵用二维数组来表示练习1设有一个二维数组A[m][n]按行
优先顺序存储，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][
3](10)存放在什么位置？脚注(10)表示用10进制表示。设数组元素A[i][j]存放在起始地址为Loc(i,j)的存
储单元中∵Loc(2,2)=Loc(0,0)+2n+2=644+2n+2=
676.∴n=(676-2-644)/2=15∴Loc(3,3)=Loc(0,0
)+315+3=644+45+3=692.练习2设有二维数组A[10,20]，其每个元素占两个字节，
A[0][0]存储地址为100，若按行优先顺序存储，则元素A[6,6]的存储地址为，按列优先顺序存储，元素A[6,6]的存储地
址为。352232(620+6)2+100=352(610+6)2+100=232特殊矩阵的压缩存储1.什么是压缩存
储？若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间。2.什么样的矩阵能够压缩？一些特殊矩阵，如：
对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。3.什么叫稀疏矩阵？矩阵中非零元素的个数较少（一般小于5%）5.2特殊矩阵的压缩存
储矩阵：是一个二维数组，是科学和工程计算问题中常用到的数据模型。特殊矩阵：矩阵中的元素分布呈现某种规律。为了节省存储空间，特别是在
高阶矩阵的情况下，可以利用特殊矩阵的分布规律对他们进行压缩存储。压缩存储：为多个值相同的元素只分配一个存储空间，值为零的元素不分配
空间。注意：压缩存储时，节约了存储单元，但在压缩后还需解决如何找到某元素的方法，因此，还必须给出压缩前下标和压缩后下标之间的变换公
式，使压缩存储变得有意义。5.2.1对称矩阵特点：在一个n阶方阵中，有aij=aji，其中1≤i、j≤n。如图所示是一个5阶
对称矩阵对于对称矩阵，因其元素满足aij=aji，只需存储其下三角（或上三角）,即可实现压缩存储。对于n阶对称方阵，将？个元
素压缩到？个空间中。n×nn(n+1)/2对下三角部分以行为主序顺序存储到一个向量中去，在下三角中共有n×(n+1)/2个元素，
因此，不失一般性，设存储到向量SA[n(n+1)/2]中。设矩阵元素aij存储在A数组的A[k]中，则关键问题是要找i、j与k的关
系。根据存储原则：对于下三角元素aij，前面共有i-1行,这i-1行共有?个元素,当前行中aij是第个元素。所以ai
j是第?个元素。对于上三角元素aij，由于aij=aji,则访问和它对应的下三角中的aji即可。综合起来，对称矩阵中的任意元
素aij得到转换公式：i(i-1)/2ji(i-1)/2+jK=I(I-1)/2+J(其中I=max(i,j),J=m
in(i,j);)12345…n(n+1)/2a11a21a22a31a32a33…an1an2…anni≥j且1≤i≤n下
三角若i?子综合起来得到：k?=?I?×?(I-1)/2?+?J。数组下标(i,j)确定存储地址对称矩阵[特点]在n?n的矩阵a中，
满足如下性质：aij=aji(1?i,j?n)[存储方法]只存储下(或者上)三角(包括主对角线)的数据元素。共占用n
(n+1)/2个元素空间。k=i(i-1)/2+j当i?jj(j-1)/2+i当iaij(aji)ann......k1234
n(n+1)/2ajiaijK=I(I
+1)/2+J(其中I=max(i,j),J=min(i,j);)34810c294
6cc157ccc08cccc73cccc6
2ccc481cc7460c82957(b
)上三角矩阵(a)下三角矩阵5.2.2三角矩阵如图为一个三角矩阵，其中c为某个常数。其中：(a)为下三角矩阵：主对角线以上
(不包括对角线)均为同一个常数；(b)为上三角矩阵，主对角线以下(不包括对角线)均为同一个常数；下面讨论它们的压缩存储方法，可以借
用对称矩阵的压缩存储方法i(i-1)/2+j当i≥jn(n+1)/2+1当i)/2+1当i>jk=k=1下三角矩阵中元素aij(i>j)在一维数组A中，A数组的大小为？n(n+1)/2+1其中元素
aij(i在数组A中的存储位置为：下三角矩阵n(n+1)/2+1C上三角矩阵a11a12a21a22a23a32a33a34
a43a44a45……………Am×n=5.2.3带状矩阵若矩阵中所有非零元素都集中在以主对角线为
中心的带状区域中，区域外的值全为0，则称此矩阵为对角矩阵。特点：主对角线上下方各有b条次对角线。b为矩阵的半带宽，2b+1为矩阵的
带宽，常见的有三对角、五对角、七对角矩阵。如图所示为三对角矩阵：-1(ji)j-i=a11
a12a21a22a23a32a33a34a43a44a45……………以三对角矩阵为例讨
论对角矩阵的压缩存储1.确定存储该矩阵所需的一维向量空间的大小假设每个非零元素所占空间的大小为1个单元。所需一维向量空间
的大小为2+2+3(n-2)=3n-22.确定非零元素在一维数组空间中的位置Loc[i,j]=Loc[1,1]+前i-1行非零
元个数+第i行中aij前非零元个数;前i-1行元素个数为：3×(i-1)-1(因为第1行只有2个非零元素);第i行中aij前非零
元素个数=j-i+1，其中由此得到:Loc[i,j]=Loc[1,1]+3(i-1)-1+j-i+1=Loc[1,1]+
2(i-1)+j-15.3稀疏矩阵的压缩存储稀疏矩阵：设m×n矩阵中有t个非零元素，且t<.3.1稀疏矩阵的三元组表示在很多科学管理及工程计算中，常会遇到阶数很高的大型稀疏矩阵。若按常规的存储方法，将会浪费很多内存
。提出另外的存储方法：仅存放非零元素。由于这类矩阵，通常零元素分布没有规律，所以：将非零元素所在的行号、列号、及值构成一个三元组，
然后再按某种规律存储这些三元组，便可以节约存储空间。三元组表的类型说明如下：defineSMAX1024
/一个足够大的数/typedefstruct{inti,j; /非零元素
的行、列/datatypev; /非零元素值/}SPNode;
/三元组类型/typedefstruct{intmu,nu,tu; /矩阵的
行、列及非零元素的个数/SPNodedata[SMAX]; /三元组表/}SPMatrix;
/三元组表的存储类型/稀疏矩阵的转置矩阵转置，是指变换元素的位置，把位于(row，col)位置上的元素换到
(col，row)位置上，也就是说，把元素的行、列互换。采用矩阵的正常存储方式时，实现矩阵转置的经典算法如下：1void
TransMatrix(datatypesource[n][m],datatypedest[m][n])2{/
source和dest分别为被转置的矩阵和转置以后的矩阵/3inti,j;4for(i=0;
i[j][i];7}显然，时间复杂度为O(m?×?n)在A的三元组存储基础上得到B的三元组表存储算法思路：①由A的行数、列
数、非零元数目转化成B的列数、行数、非零元数目。②按A的列(B的行)进行循环处理：对A的每一列扫描三元组，找出相应的元素，若找到
，则交换其行号与列号，并存储到B的三元组中。1SPMatrixTransM1(SPMatrixA)2{S
PMatrixB;3intp,q,col;4B=(SPMatrix)malloc(sizeo
f(SPMatrix));/申请存储空间/5B->mu=A->nu;B->nu=A->mu;
B->tu=A->tu;/稀疏矩阵的行、列、元素个数/6if(B->tu>0)
/有非零元素则转换/7{q=1;8for(col=1;col<=(A->nu
);col++)/按A的列序转换/9for(p=1;p<=(A->tu);p++)
/扫描整个三元组表/10if(A->data[p].j==col)11{B
->data[q].i=A->data[p].j;12B->data[q].j=A->data[p]
.i;13B->data[q].v=A->data[p].v;14q+
+;15}/if/16}/if(B->tu>0)/17returnB;
/返回的是转置矩阵的指针/18}/TransM1/时间复杂度为O(A.nu×A.tu),
最坏情况当A.tu=A.mu×A.nu时，时间复杂度为O(A.m×A.n2)。快速转置方法：依次按三元组表A的次序进行转置，转置后
直接放到三元组表B的正确位置上。这种转置算法称为快速转置算法。为了能将待转置三元组表A中元素一次定位到三元组表B的正确位置上，需
要预先计算以下数据：待转置矩阵每一列中非零元素的个数。(2)待转置矩阵每一列中第一个非零元素在三元组表B中的正确位置。
为此，需要设两个数组num[col]————用来存放A中第col列非零元素个数position[col]————用来存
放A中第col列中第一个非零元素在三元组表B中的正确位置。rowrowcolcolee111132-312221163159co
l123456733321112-3num[col]22210104432651418554331249Position[col]
1357889665342241877461615-7(b)三元组表B(a)三元组表A88663414-7(1)num[co
l]的计算方法：将三元组表A扫描一遍，对于其中列号为k的元素，给相应的num[k]加1。(2)position[col]的计
算方法：position[1]=1，position[col]=position[col-1]+num[col-1]，其
中2≤col≤A.nu。其中：举例：算法如下：SPMatrixFastTM(TSMatrixA){SPMatrix
B;intcol,t,p，q;intnum[MAXSIZE],cpot[MAXSIZE];B->tu
=A->tu;B->nu=A->mu;B->mu=A->nu;if(B->tu){for(col=1;
col<=A->nu;col++)num[col]=0;for(t=1;t<=A->tu;t++)nu
m[A->data[t].col]++;将矩阵A转置为B所指的矩阵cpot[1]=1;for(col=2;colnu
;col++)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p{col=A.data[p].col;q=cpot[col];B->data[q].row=A.data[p].col;
B->data[q].col=A.data[p].row;B->data[q].e=A.data[p].e
cpot[col]++;}}}计算每一列的非零元素的个数求col列第一个非零元素在B.data[]的位置快速转置算法
时间耗费在四个并列的单循环上，这四个并列的单循环分别执行了A.nu，A.tu，A.nu，A.tu次；因而总的时间复杂度为O(A.n
u)+O(A.tu)+O(A.nu)+O(A.tu)。当待转置矩阵M中非零元素个数接近于A.mu×A.nu时，其时间复杂度接近
于经典算法的时间复杂度O(A.mu×A.nu)。空间耗费上除了三元组表所占用的空间外，还需要两个辅助向量空间，即num[1..A-
>nu]，cpot[1..A->nu]。可见，算法在时间上的节省，是以更多的存储空间为代价的。2)用三元组表实现稀疏矩阵的乘
法运算两个矩阵相乘也是矩阵的一种常用的运算。设矩阵M是m1×n1矩阵，N是m2×n2矩阵；若可以相乘，则必须满足矩阵M的列数n1
与矩阵N的行数m2相等，才能得到结果矩阵Q=M×N（一个m1×n2的矩阵）矩阵相乘把许多数据紧凑地集中到了一起，所以有时候可以简便
地表示一些复杂的模型，如电力系统网络模型。三元组表只对矩阵的非零元素做存储。所以可以采用固定三元组表a中的元素(i,k,D1)（1
≤i≤m1,1≤k≤n1），在三元组表b中找所有行号为k的对应元素(k,j,D2)（1≤k≤m2,1≤j≤n2）进行相乘、累加，
从而得到Q[i][j]，即以三元组表a中的元素为基准，依次求出其与三元组表b的有效乘积。算法中附设两个向量num[]、firs
t[]，其中num[row]表示三元组表b中第row行非零元素个数（1≤row≤m2），first[row]表示三元组表b中第
row行第一个非零元素所在的位置。显然，first[row+1]-1指向三元组表b中第row行最后一个非零元素的位置。5.3.
2稀疏矩阵的十字链表存储与用二维数组存储稀疏矩阵比较，用三元组表表示的稀疏矩阵不仅节约了空间，而且使得矩阵某些运算的运算时间
比经典算法还少。但是在进行矩阵加法、减法和乘法等运算时，有时矩阵中的非零元素的位置和个数会发生很大的变化。如A=A+B，将矩阵B
加到矩阵A上，此时若还用三元组表表示法，势必会为了保持三元组表“以行序为主序”而大量移动元素。rowcolvaluedown
right∧图5.14十字链表的结点结构112311424335300504
003000A＝∧∧∧(b)十字链表(a)稀疏矩阵图5.15一个稀疏矩阵的十字链表∧在十字链表中，矩
阵的每一个非零元素用一个结点表示，该结点除了（row，col，value）以外，还要有以下两个链域：right：用于链接同一行中
的下一个非零元素；down：用于链接同一列中的下一个非零元素。再附设一个存放所有行链表的头指针的一维数组和一个存放所有列链表的头
指针的一维数组。图5.15(b)给出了稀疏矩阵图5.15(a)的十字链表。十字链表的结构类型说明如下：非零元素的行和列下标ty
pedefstructOLNode{introw,col;datatypevalue;structO
LNoderight,down;}OLNode;OLink;非零元所在行、列表的后继链域typedef
struct{OLinkrow_head,col_head;intm,n,len;}CrossL
ist;行、列链表的头指针向量稀疏矩阵的行数、列数、非零元素的个数建立稀疏矩阵的十字链表的算法：采用十字链表存储结构，创建
稀疏矩阵MCreateCrossList(CrossListM){if(M!=NULL)free(M);sca
nf(&m,&n,&t);M->m=m;M->n=n;M->len=t;if(!(M->row_head=(OL
ink)malloc((m+1)sizeof(OLink))))exit(OVERFLOW);if(!(M->co
l-head=(OLink)malloc((n+1)sizeof(OLink))))exit(OVERFLOW);
M->row_head[]=M->col_head[]=NULL;for(scanf(&i,&j,&e);i!=
0;scanf(&i,&j,&e)){if(!(p=(OLNode)malloc(sizeof(OLNo
de))))exit(OVERFLOW);p->row=i;p->col=j;p->value=e;if(M-
>row-head［i］==NULL)M->row-head［i］=p;输入M的行数,列数和非零元素的个数初始化行、
列头指针向量，各行、列链表为空的链表生成结点寻找行表中的插入位置else{for(q=M->row_head[i];q->r
ight&&q->right->colright)p->right=q->right;q->right=p
;}if(M->col_head[j]==NULL)M->col_head[j]=p;else{for(q=M
->col_head[j];q->down&&q->down->rowdown)p->down=q->dow
n;q->down=p;}}}完成插入寻找列表中的插入位置完成插入建十字链表的算法的时间复杂度为O(t×s)，
s=MAX(m,n)。稀疏矩阵[特点]大多数元素为零。[常用存储方法]只记录每一非零元素(i,j,aij)节省空间，但丧
失随机存取功能顺序存储：三元组表链式存储：十字(正交)链表1500220-1501130
00000-6000000
00910000000280
006?65.4广义表⒈广义表的定义是n个数据元素a1，a2，…，ai，…，an的有序序列。一般记
为：ls=（a1，a2，a3，…，an）广义表广泛地应用于人工智能等领域的表处理语言LISP语言中。用二元组表示：List(D
,R)D={ai|ai∈Atomset或ai∈Lists}R={|ai,ai+1∈D;1<=i<=
n-1}其中（1）ai是单个元素或是一个广义表，称为ls的原子或子表（2）长度：n是广义表的长度，n=0的广义表为空表
（3）表头：a1是广义表ls的表头（4）表尾：其余元素组成的表是表尾。（5）广义表示一个递归定义的表。下面给出一些广义表的例子
，以加深对广义表概念的理解。D=()空表；其长度为零。A=(a,(b,c))表长度为2的广义表，其中第一个元素是单个数据a
，第二个元素是一个子表(b，c)。B=(A,A,D)长度为3的广义表，其前两个元素为表A，第三个元素为空表D。C=(a,C
)长度为2递归定义的广义表，C相当于无穷表(a，(a,(a，(…))))。下面以广义表A为例，说明求表头、表尾的操作：hea
d(A)=a表A的表头是a。tail(A)=((b,c))表A的表尾是((b,c))。广义表的表尾一定是一个表。⒉广义表的
性质从上述广义表的定义和例子可以得到广义表的重要性质：⑴广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而
子表的元素还可以是子表，…。⑵广义表可以是递归的表。例如表C就是一个递归的表。⑶广义表可以为其它表所共享。如广义表B就共享
表A。在表B中不必列出表A的内容，只要通过子表的名称就可以引用该表。A=(a,(b,c))B=(A,A,D)C=(a,C
)广义表的特点有次序性有长度有深度可递归可共享一个直接前驱和一个直接后继＝表中元素个数＝表中括号的重数自己可以作为自己的子表可以为
其他广义表所共享广义表与线性表的区别？线性表的成分都是结构上不可分的单元素广义表的成分可以是单元素，也可以是有结构的表线性表是一种
特殊的广义表广义表不一定是线性表，也不一定是线性结构⒊广义表基本运算基本操作，取头操作（Head）和取尾操作（Tail）。根据广
义表的表头、表尾的定义可知，对于任意一个非空的广义表，其表头可能是单元素也可能是广义表，而表尾必为广义表。例如：那么：head(B
)＝etail(B)=()head(C)＝atail(C)=(b,c,d
)head(D)=Atail(D)=(B,C)head(E)=ata
il(E)=(E)Head(F)=()tail(F)=()A＝()B＝(e)C＝(a,(b,c,
d))D＝(A,B,C)E＝(a,E)F＝(())在广义表上可以定义与线性表类似的一些操作，如建立、插入、删除、拆开、连接、复制
、遍历等。CreateLists(ls)：根据广义表的书写形式创建一个广义表ls。IsEmpty(ls)：若广义表ls空，则返回T
rue；否则返回False。Length(ls)：求广义表ls的长度。Depth(ls)：求广义表ls的深度。Locate(ls,
x)：在广义表ls中查找数据元素x。Merge(ls1,ls2)：以ls1为头、ls2为尾建立广义表。CopyGList(ls1,
ls2)：复制广义表，即按ls1建立广义表ls2。Head(ls)：返回广义表ls的头部。Tail(ls)：返回广义表的尾部。……
广义表的基本运算（1）求表头GetHead(L)：非空广义表的第一个元素，可以是一个单元素，也可以是一个子表（2）求表尾GetTa
il(L)：非空广义表除去表头元素以外其它元素所构成的表。表尾一定是一个表练习A=(a,b,(c,d),(e,(f,g)))
GetHead和GetTail均无定义GetHead(A)=(a)GetTail(A)=()GetHead(A)=aGet
Tail(A)=(b)GetHead(A)=aGetTail(A)=()GetHead(GetTail(GetHead(
GetTail(GetTail(A)))))A=()A=(a,b)A=(a)A=((a))d练习：求下列广义
表的长度1）A=()2）B=(e)3）C=(a,(b,c,d))4）D=(A,B,C
)5）E=(a,E)n=0，因为A是空表n=1，表中元素e是原子n=2，a为原子，(b,c,d)为子表n=3，3个元素都是子表
n=2，a为原子，E为子表D=(A,B,C)=((),(e),(a,(b,c,d)))，共享表E=(a,E)=(a,(a,E))=(a,(a,(a,…….)))，E为递归表5.4.2广义表的存储广义表的存储结构：顺序存储结构无法实现，单链表无法存储。例如：L=(a，(b，(c，d)，e)，f)如何访问到d？head(tail(head(tail(head(tail(L))))))=d任何一个非空的广义表都可以分解成表头和表尾两部分，表中的每个元素可用一个结点来表示。有两类结点：(1)单个元素结点：有两个域：标志域和值域。(2)表结点：由三个域构成：标志域、指向表头的指针域和指向表尾的指针域。tag=1hptp(a)表结点tag=0data图5.16头尾表示法的结点形式(a)元素结点ATOM=0单元素；LIST=1子表typedefenum{ATOM,LIST}Elemtag;typedefstructGLNode{Elemtagtag;union{datatypedata;struct{structGLNodehp,tp;}ptr;};}GList;标志域，用于区分元素结点和表结点元素结点和表结点的联合部分union共用体data是元素结点的值域ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾D1∧∧A∧111111110000abacB∧∧C∧图5.17广义表的头尾表示法存储结构示例例如：有以下广义表：A=(a,b,c)B=(A,A,D)C=(a,C)D=(())采用头尾表示法容易分清广义表中单元素或子表所在的层次。例如，在广义表A中，单元素a、b和c在同一层次上。最高层的表结点的个数即为广义表的长度。例如，广义表A的最高层有三个表结点，广义表长度为3。总结1.了解串的存储方法，理解串的模式匹配算法2.明确数组和广义表这两种数据结构的特点，掌握数组地址计算方法，了解几种特殊矩阵的压缩存储方法。3.掌握广义表的定义、性质及其GetHead和GetTail的操作。P1122P1133，6，7 |
|
