《数据结构-用C语言描述（第二版）》第5章 数组和广义表

第第五五章章数数组组和和广广义义表表数组及其运算数组的顺序存储结构矩阵的压缩存储广义表m元多项式的表示第5章

数组和广义表第五章

数组和广义表第5章

数组和广义表本章前几章所讨论的线性表、栈、队列和串都是线性的数据结构。它们的组成元素的值都是不可分解的。本章将要讨论的多维数组和广义表是一种复杂的非线性结构，它的组成元素是可以分解的，每个元素可以有多个的直接前趋和直接后继。本章主要介绍数组的概念及多维数组在计算机中的存放，特殊矩阵的压缩存储及相应运算，广义表的概念和存储结构及其相关运算的实现。第五章

数组和广义表5.1数组及其计算几乎所有的程序设计语言中都有利用数组来描述数据。由于数组中的各元素具有统一的类型，而且数组元素的下标具有固定的上下界，所以，它比其它复杂的数据结构更容易处理。根据数组元素的组织形式不同，数组可以分为一维数组、二维数组以及多维（n维）数组。例如，二维数组第五章

数组和广义表它由固定数量的m×n个元素所组成，且每个数据元素aij均受两个下标关系约束。除边界外，每个数据元素都有两个直接前趋和直接后继结点，即行关系上的直接前趋aij-1和直接后继aij+1，列关系上的直接前趋ai-1j

和直接后继ai+1j，而且仅有一个开始结点a00，它没有直接前趋；仅有一个终端结点an-1n-1

，它没有直接后继；而边界上的结点除开始和终端结点外，每个结点均只有一个直接前趋或只有一个直接后继，因此，二维数组可以看作是线性表的推广。同时，二维数组可看作是由二个一维数组作为数据元素定义的一维数组，数据元素之间在每一个关系中仍具有线性特性，但在整个结构中呈非线性关系。如图5.1所示。同样，三维数组A

m×n×p可以看作是其数据元素为二维数组表示的特殊线性表，每个元素最多可以有三个直接前趋和三个直接后

继，……；依此类推，n维数组中的每个元素最多可以有n个直接前趋和n个直接后继。由此可知，多维数组是一种复杂的数据结构，且也可以看作是线性结构的推广。对于一个数组结构而言，一般只有存取元素和修改元素值两种运算。第五章

数组和广义表A

m×n=(（a00，a01，…a

0n-1），（a10，a11，…a1n-1），…（am-10，a

m11，…,a

m-1n-1）)图5.1二维数组图例第五章

数组和广义表5.2数组的顺序存储结构数组的顺序存储结构指的是如何在计算机内存中利用一组地址连续的存储单元来存储数组元素的存储方式。由于计算机存储单元都是一维的结构，而多维数组是一个多维的结构，因此，要存放多维数组结构必须有一个次序约定的问题。例如，一个二维数组，可以有两种存储方式：一是以行为主序的优先存储方式，即数组元素按行优先关系排列，第i+1行的数据元素紧跟在第i行的数据元素之后，而同一行中的数据元素以列下标递增次序排列。二是以列为主序的优先存储方式，即数组元素按列优先关系排列，第j+1列中的数据元素紧跟在第j列中的数据元素后面，同一列中的元素以行下标递增次序排列，如图5.2所示。第五章

数组和广义表图5.2二维数组的两种存储方式第五章

数组和广义表由于多维数组其下标不只2个，一般规定以下标顺序或以逆下标顺序为主序的优先存储方式。顺序存储的数组是一个随机存取结构。多维数组的数据元素存储地址的计算。一个二维数组Am×n，若以行为主序优先存储，且已知a00的存储地址

LOC(a00)（即二维数组A的起始存储位置，亦称为基地址或基址）和每个数据元素所占用的存储单元个数c，则二维数组中任一数据元素ai,j的存储地址可由下式确定:LOC

(

aij

)

=

LOC

(

a00)

+

(i×n+j)

×c同理可推导出以列为主序优先存储时数据元素aij的存储地址，其计算公式为：LOC(

a

i

j

)

=

LOC(

a00

)

+

(j×

n

+

i

)

×c对于三维数组A

m×n×p而言，若以行为主序优先存储时，则其数据元素aijk的存储地址可为：LOC

(

a

i

j

k)

=

LOC

(

a000)

+

[

i

×

m

×p

+

j

×p

+k

]

×c对于一般的二维数组A[c1…d1，c2…d2]而言，此处c1，c2的值不一定是0，a

i

j

的地址为：LOC

(

a

ij

)

=

LOC

(

a

c

1

c

2

)

+

[

(i

–

c

1

)*

(

d

2

–

c

2

+

1)

+

j

–

c

2

]

*

c第五章

数组和广义表5.3矩阵的压缩存储在很多科学计算与工程应用中，经常要使用矩阵。它是由m行和n

列的数值构成。在编程时，通常利用二维数组来存储矩阵。但在某些情况下，特别是在数值分析中经常会出现一些阶数很高的矩阵，其中含有许多值相同的元素或零元素，若利用二维数组存储会浪费空间。为了节省存储空间并且加快处理速度，需要对这类矩阵进行压缩存储，也就是说可以对多个具有相同值的元素只分配一个存储空间，而对零元素则不分配空间。一般的，压缩存储适用于特殊矩阵和稀疏矩阵。特殊矩阵是指那些具

有相同值的元素或零元素在矩阵中的分布有一定的规律矩阵；而稀疏矩阵

是指那些零元素远远多于非零元素，并且非零元素的分布没有规律的矩阵。第五章

数组和广义表5.3.1特殊矩阵1.三角矩阵n阶三角矩阵以对角线划分有上三角与下三角矩阵两种。上三角矩阵是指矩阵的下三角（不含对角线）中的元素均为常数C或零的n阶矩阵，下三角矩阵则与之相反，如图5.3所示。第五章

数组和广义表个元素，而在第i+1行上，aij是该行的第j-i+1个元素，从而可得存储单元M[k]的下标与aij的下标i、j的对应关系为：k

=i/2×(2n-i+1)+j-i

当i≤jn×(n+1)/2

当i>j在压缩存储时，矩阵中值相同的元素C可共享一个存储空间，元素为零则可不必分配空间，而其余的元素有n(n+1)/2个，因此三角矩阵可用一维数组M[n×(n+1)/2+1]来存储，其中常数C放在数组的最后一个下标变量中。上三角矩阵，主对角线之上的第p行（1≤p≤n）恰有n-p+1个元素，若按行为主序优先顺序存储，则aij之前的前i行共有：同样，可得下三角矩阵的存储单元M[k]的下标与aij的下标i、j的对应关系为:k

=i×(i+1)/2+j

当i≥jn×(n+1)/2

当i<j第五章

数组和广义表2.对称矩阵若一个n阶方阵A中的元素满足下列性质：a

ij=

a

ji

0≤i，j≤n-1则称A为对称矩阵，如一个4阶对称矩阵如图5.4所示。图5.4

4阶对称矩阵示例第五章

数组和广义表因此，可以按图5.5所示的次序将矩阵元素存放在一个一维数组M[n（n+1）/2]中，其存储方式如图5.6所示。这样，给出对称矩阵A中的任一个元素aij，依据它的下标i和j就可由对应关系式确定其在数组M中的位置k，aij

的地址LOC（aij）可由下式计算：LOC（aij）

=

LOC（M[k]）=

LOC（M[0]）+

k×c=

LOC（M[0]）+

[

I×（I+1）/2

+

J]

×c其中，c为每个数据元素所占的存储单元数目，且

I=max（i，j），J=min（i，j）从而，k=I*（I+1）/2+J，即k为i，j统一后的值。由于对称矩阵中的元素关于主对角线对称，所以可以只存储矩阵中主对角线（含对角线）以上或以下的元素，即只为每一对对称元素分配一个存储空间，将共有n×n个的元素压缩存储到n(n+1)/2个存储空间中，从而节省了空间。假定按以行为主序优先方式存储主对角线（包括对角线）以下的元素，则其存储次序如图5.5所示。在上述的下三角矩阵中，矩阵元素总数为：第五章

数组和广义表图5.5对称矩阵的行优先排列存放a00a10a11……an0……an-1n-1n(n+1)/2

-

1K

=

0

1

2

……图5.6对称矩阵的压缩存储情况第五章

数组和广义表5.3.2稀疏矩阵如果矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素的分布没有规律，则称此类矩阵为稀疏矩阵。稀疏矩阵的压缩存储，可以在存储非零元素的同时，存储适当的辅助信息。例如，可以利用一个三元组元素（i，j，aij）就可唯一地确定矩阵

A中的非零元素，这样，稀疏矩阵可由表示非零元素的三元组及其行、列数唯一地确定。例如，稀疏矩阵A：可由三元组表((0,1,5)，(0,4,8)，(1,0,1)，(1,2,3)，(2,1,-2)，(3,0,(4,5)这一行、列数对来描述。第五章

数组和广义表一般地，可以用三元组表表示法和十字链表作为稀疏矩阵的压缩存储方法，其中以三元组表示法最常用。1.三元组顺序表若将表示稀疏矩阵的三元组按行优先（或列优先）的顺序排列，则可得到一个结点均是三元组的线性表即三元组表，若以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方式，称为三元组顺序表。。如图5.7所示为三元组以行为主序优先顺序存储的A稀疏矩阵所对应的三元组表。其类型定义为：#define

MAXSIZE

999/*非零元素个数的最大值设为1000*/typedef

struct{

int

i，j；

/*非零元素的行，列下标*/datatype

v

；/*元素值*/}node；typedef

struct{int

mu，nu，tu；/*行，列数，非零元素个数*/node

data[MAXSIZE]；/*三元组表*/}matrix

/*稀疏矩阵类型*/matrix

*a；第五章

数组和广义表图5.7 稀疏矩阵A所对应的三元组表a->data第五章

数组和广义表（1）矩阵的转置一个m×n的稀疏矩阵A，它的转置矩阵B仍是稀疏矩阵，且为n×m的矩阵，同时有A[i][j]=B[j][i]成立（0≤i≤m-1，0≤j≤n-1），即B的行是的列，B的列是A的行，如图5.8所示，A，B两矩阵互为转置。假设A和B矩阵分别用matrix型指针变量a和b表示，矩阵的转置可以

按以下进行：由于Ｂ的行是Ａ的列，所以可按照b->data三元组表的次序在a->data中找到相应的三元组进行转置，即可按a->data的列序转置，所得到的转置矩阵Ｂ的三元组表b->data必定是按行优先存放的。因此，可以对三元组表a->data从第一行起扫描，找到Ａ的每一列中所有的非零元素，就可以实现转置。算法描述如下：第五章

数组和广义表第五章

数组和广义表matrix

*transmatrix（matrix *

a

）{

int

am，bn，col；matrix *

b；/*转置后的矩阵b*/b

=

(

matrix

*

)malloc

(sizeof(matrix))；b->mu=a->nu；b->nu=a->mu；/*行、列数目交换*/b->tu=a->tu；/*非零元素个数赋值*/if（b->tu>0）{

bn=

0；for(col=0；col<a->nu；col++)/*按*a的列序转置*／for(am=0；am<a->tu；am++)/*扫描整个三元组表*／if(a->data[am].j==col)/*列号为col时转置*／{b->data[bn].i=a->data[am].j；/*行、列交换*/b->data[bn].j=a->data[am].i；b->data[bn].v=a->data[am].v；

bn++；/*b->data中的结点序号加1*／}}return

b;/*返回转置矩阵的指针*/}

/*transmatrix*/以上算法的时间复杂度为Ｏ（tu×nu）。一般的，上述转置算法只适用于当tu《mu×nu的情况。第五章

数组和广义表（2）矩阵的乘法设矩阵Ａm1ｘn1与Ｂm２ｘn２，当n1＝m２时，可得矩阵相乘为：Ｃm1xn2

=Am1×n1×Bm2×n1由矩阵乘法的定义得：0≤i≤m1-1，0≤j≤n2-1

；其算法可描述如下：for

(

i

=

0；i

<

m1；i

+

+)for

(

j

=

0；j

<

n2；j

+

+

){

c

[i]

[j]

=

0；for

(k

=

0；k

<

n1

；k

+

+

)c

[i]

[j]

=

c[i]

[j]

+

a[i]

[k]

*

b[k]

[j]

；}该算法的时间复杂度为Ｏ（m1×n1×n2）。第五章

数组和广义表要求C=A×B，显然在上述算法中，不论aik和bkj的值是否为零都要作一次乘法。由于在稀疏矩阵中存在大量的零元素，所以可以避免许多无用的运算。若利用三元组表作为稀疏矩阵的存储结构，只需在a->data和b->data中找到相应的各对元素（即a->data中j和b->data中的i相等的元素）相乘即可求得两矩阵的乘法值。例如，矩阵Ａ与B为：第五章

数组和广义表它们对应的三元组表a->data，b->data和c->data分别如图5.9所示：第五章

数组和广义表为了得到非零的乘积项，必须在b->data中查找矩阵B中第k行的所有非零元素。由于b->data是以行为主序存放非零元素的三元组，若能预先确定矩阵B中每一行的第一个非零元素在b->data中应有的位置，就可以顺序存取b->data中第k行的所有非零元素。显然，应先求出B中的每一行中非零元素个数之后才可确定这些位置。为此，可用一个数组num[m2-1]存储每一行中非零元素的个数，用另一个数组rpos[m2-1]存储每一个非零元素在b->data中所在的位置，从而应有以下式子成立。rpos

[0]

=

0rpos

[row]

=

rpos

[row-1]

+

num

[row-1]

(1≤row≤m2-1)例如，B矩阵其rpos数组的值可用下表表示：第五章

数组和广义表由于rpos[row]表示B的第row行中第一个非零元素在b->data中的序号，所以rpos[row+1]-1表示第row行中最后一个非零元素在b->data中的序号。显然，最后一行中最后一个非零元素在b->data中的位置就是rpos[m2]－1（此时b.mu=m2），且有rpos[m2]=rpos[m2-1]+num[m2－1]。从而可以得到稀疏矩阵相乘的具体做法：对于A中的每个元素a->data[p]（p=0，1，2，…，m.tu-1）,找到B中所有满足条件a->data[p].j=b->data[q].i的元素b->data[q]，然后求a->data[p].v和b->data[q].v的积，作为乘积矩阵累加和项c[i][j]中的一部分。可以对每个元素设一个累计和的变量，初始时置各变量为零，然后扫描三元组表a->data，求得相应元素的乘积并累加到累计和的变量上。乘积矩阵中的各元素只有在求得累加和后才可确定是否为零，由于c中元素的行号一致，且a中元素以A的行序为主序排序，所以可对c逐行处理。先求得累计求和的中间结果，然后再压缩存储到c->data中去。两矩阵相乘的算法如下：第五章

数组和广义表matrix

*mul(matrix

*a，matrix

*b){matrix

*c；int

crow，k，brow，p，t；int

num[

]，rpos[

]；datatype

ctemp[

]；if

(

a->tu*b->tu!=

0){for(crow=0；crow<=b->tu；crow++)

num[crow]=0；

/*数组初始化*／for

(t

=0；t

<=b->tu；t

++)num[b->data

[t].i=

num[b->data

[t].i]+1；/*求B的每一行非零元素个数*／rpos[0]=0；for

(crow

=1；crow<=b->mu；crow

++)rpos[crow]=rpos[crow-1]+num[crow-1]；/*求一维数组rpos[b->mu]的值*／c

=

(matrix

*

)malloc

(sizeof(matrix))；c->mu

=a->mu；c->nu

=b->nu

；c->tu

=

0

；p=0；/*初始化*／第五章

数组和广义表do{crow=a->data[p].i；/*crow指示当前处理的行号*／for(k=0；k<=c->nu-1；k++)ctemp[k]=0；/*初始化累加器*／while

((p

<=a->tu)

&&

(a->data

[p].i=

=crow)){brow=a->data[p].j；/*brow表示b->data[q]在B中的行号*／for(q=rpos[brow]；q<=rpos[brow+1]-1；q++){k=b->data[q].j；/*k指示乘积元素在c中行号*／ctemp[k]=ctemp[k]+a->data[p].v×b->data[q].v；}

p++；}for(k=0；k<=c->nu-1；k++

)if

(ctemp[k]!=0){

c->tu

=c->tu+1；c->data

[c->tu]

=

(crow，k，ctemp

[k])；/*将ctemp中非空元素压缩到c->data中*／

}}while

(p

>a->tu)

；return

c；/*返回乘积矩阵c*／}／*mul*／第五章

数组和广义表2.十字链表对于矩阵的一些运算如矩阵加法等运算非零元素的位置和个数经常发生变化，就不宜采用三元组表，此时采用链式存储结构来表示三元组方便一些。我们一般采用一种称之为十字链表的链接存储结构，其基本做法就是在链表中，每个非零元素结点中除了表示非零元素的三元组(i，j，v)外，还增加了两个链域：向下域（down）和向右域（right），其中向下域用于链接同一列中的非零元素，向右域（right）用于链接同一行中的非零元素，如图5.10（a）的结点格式。图5.10十字链表非零元素结点格式第五章

数组和广义表利用这种结构形式的结点就可将稀疏矩阵中同一行的非零元素通过向右域right链接成一个带表头结点的链表，称之为行链表；而同一列中的非零元素也可以通过向下域down链接成一个带表头结点的链表，称之为列链表。这样，对于稀疏矩阵的每一个非零元素aij，它既是第i行链表上的一个结点，又是第j列链表上的结点，好比处在一个十字交叉路口上，故称为十字链表。为了便于运算，在每一个行链表和列链表上增加一个表头结点（结点结构如图5.10（b）所示），而非零元素结点称之为表结点，而且可将表头结点的行、列域置为零，所有的行、列链表和它的头结点一起链成一个单循环链表，而且第i行链表和第ｊ列链表可共享同一个表头结点。由于表头结点中值域ｖ不用，所以可将其作为指针域next，用于存放指向下一个表头结点的指针，这样，通过该指针域就可以将所有的表头结点链接，最后，再加上一个附加的表头结点（表头结点由五个域i、j、next、down、right组成）由指针hm指示，组成一个带表头结点的循环链表，hm就是十字链表的头指针，只要给定hm指针，就可取得稀疏矩阵的全部信息了。例如，上述例子中矩阵Ａ的十字链表如图5.11所示。第五章

数组和广义表图5.11矩阵A的十字链表第五章

数组和广义表十字链表类型定义如下：typedef

struct

node{

int

i，j；struct

node

*down，*right；union{struct

node

*next；/*表示头结点时用作next域*/datatype

v；/*表示表结点时用作v域*/}val；}

crosslink；建立十字链表可分为二步：第一步：建立表头结点的循环链表。第二步：依次读入稀疏矩阵的非零元素的三元组（i，j，v），生成一个非零元素结点*p，将其插入到第i行链表和第j列链表的正确位置上，其具体算法可描述如下：第五章

数组和广义表crosslink

*creatcrosslink（）/*返回稀疏矩阵的十字链表头指针*/{crosslink

*

p，*q，*hm，*cp[MAXSIZE]；int

i，j，k，m，n，t，s；datatype

v；scanf(“%d%d%d”，&m，&n，&t)；/*输入行、列数，非零元素个数*/if(m>n)s=m；else

s=n；/*确定表头结点个数s=max（m，n）

*/hm=(crosslink

*)malloc(sizeof(crosslink))；/*建立十字链表头结点*hm->i=m；hm->j=n；cp[0]=hm；/*

cp[]是指针数组，分别指向头结点和行、列表头结点*/for(i=1；i<=s；i++)/*建立头结点循环链表*/{

p=

(crosslink

*)malloc(sizeof(crosslink))；p->i=0；p->j=0；p->right

=

p；p->down

=

p；cp[i]=

p；cp[i-1]->val.next

=p；}cp[s]->val.next

=

hm；第五章

数组和广义表for(k=1；k<=t；k++){scanf(“%d%d%d”，&i，&j，&v)；p=(crosslink

*)malloc(sizeof(crosslink))；p->i=i；/*输入一个非零表结点*p

*/p->j=j；p->val.v=v；q=cp[i]；/*取第i行表头结点*/while((q->right!=cp[i])&&(q->right->j<j))q=q->right；/*在第i行找第一个列号大于j的结点*/p->right=q->right；q->right=p；/**p插在*q之后*/q=cp[j]；/*取第j列表头结点*/while((q->down!=

cp[j])&&(q->down->i

<

i))q=q->down；/*在第j列中找第一个行号大于i的结点*/p->down=q->down；q->down=p；/*结点*p插在*q之后*/}return

hm；/*返回十字链表头指针*/}

/*

creatcrosslink

*/第五章

数组和广义表*3.十字链表表示的运算举例—矩阵加法设矩阵C=A+B，整个运算过程可从矩阵的第一行起逐行进行，对每一行都从行表头出发，分别找到A和B在该行中的第一个非零元素结点后开始比较，然后按以下几种情况处理。对于C=A+B矩阵而言，C矩阵中的元素cij可能有四种情形：cij

或者是aij+bij；或者是aij（bij=0）；或者是bij（aij=0）；或者是零元素。然后根据不同的情况分别作相应处理。其算法如下：首先定义一个插入函数：insert（

int

crow，

int

ccol，

int

cval，

crosslink

*cp[

]

）{

crosslink

*s

，*last；s=(crosslink

*)malloc(sizeof(crosslink))；s

->i=crow；s

->j=ccol；s

->v=cval；last->right=s；last=s；/*将s结点链接在行表中*/cp[ccol]->next->down=s；cp[ccol]->next=s；/*将s结点链接到列表中*/}/*

insert

*/第五章

数组和广义表矩阵相加运算的算法如下：crosslink

*

matrixadd（a，b，c，cp）crosslink

*a，*b，*c，*cp[

]；{

int

n，i，arow，brow，crosslink

*last，*arow，*brow，*s，*pa，*pb；c=(crosslink

*)

malloc

(sizeof(crosslink))；c->i=a->i；c->j=a->j；/*对c的表头链表的表头结点赋值*/if(a->i>a->j)n=a->ielse

n=a->j；cp[0]

=c；for(i=1；i<=n；i++)/*表头结点初始化*/{

s=(crosslink

*)malloc(sizeof(crosslink))；s->i=0；s->j=0；s->right=s；s->down=s；cp[i]

=s；}第五章

数组和广义表arow=a

->next；brow=b->next；/*读入A，B的初始行*/last=cp[0]；/*

last置初值*/i=0；while((arrow!=a)&&(brow!=b)/*读A，B矩阵*/{

pa

=arow->right；pb=brow->right；/*指向A，B行中的当前结点*/while((pa!=arrow)＆＆(pb!=brow))/*读A，B的当前行*/{if(pa->j==pb->j)/*

A，B中同一位置上都有非零元素*/{

if(pa

->v+pb->v!=0)insert(pa->i，pa->j，pa->v+pb->v，cp)；pa=pa->right；pb=pb->right/*分别取当前行的下一个结点*/}elseif(pa->j

>

pb->j){

insert(pb->i，pb->j，pb->v，cp)；pb=pb->right；}第五章

数组和广义表else{

insert(pa->i，pa->j，pa->v，cp)；pa=pa->

right；}}；while(pa!=arrow)/*B的当前行已没有非零元素*/{

insert(pa->i，pa->j，pa->v，cp)；pa

=pa->right；}while(pb==brow)/*

A的当前行已没有非零元素*/{

insert(pb->i，pb->j，pb->v，cp)；pb=pb->right；}/*当前行结束*/第五章

数组和广义表last->right=cp[i]；i++；last=cp[i]；/*开始下一行*/arrow=arow->next；brow=brow->next}；for(i=1；i<=c->j；i++)/*关闭全部列表*/cp[i]->next->down=cp[i]；for(i

=1；i<=n-1；i++)cp[i]->next

=cp[i+1]；if(n=

=0)c->next

=c；else{

cp[n]->next=c；c->next=cp[1];}；}

/*

matriadd

*/第五章

数组和广义表5.4广义表5.4.1广义表的定义广义表简称表，它是线性表的推广。一个广义表是n个（n≥0）元素的一个序列。当n=0时称为空表；在一个非空的广义表中，其元素可以是单元素；也可以是广义表。广义表是一种递归的数据结构。通常记广义表Ls=（a1，a2，…，an），其中n为广义表的长度，n≥0。若ai是广义表，则称它为Ls的子表。如Ａ＝()Ａ为一个空表，其长度为０；Ｌ＝(ａ，ｂ)Ｌ为一长度为２的广义表，它有两个元素；Ｃ＝(a，(b，c，d))C为一长度为２的广义表；E=(b，E)=(b，(b，(b，(…))))E为一个长度为２的广义表。对于Ls=（a1，a2，…，an），若其非空，n≥１，则a1称为Ls的表头，而其余元素组成的表（a2，…，an）称为Ls的表尾。广义表可以利用图形简单进行表示，如图5.12。第五章

数组和广义表第五章

数组和广义表atomdata/snextnext5.4.2广义表的存储结构广义表中的数据元素可以具有不同的数据结构，因此很难为每个广义表分配固定大小的存储空间，所以采用动态链接结构，每个数据元素可用一个结点表示。一个广义表中的数据元素可以是单元素，也可以是子表的特点，相

应地在对应的链接存储结构中的结点也有单元素结点和子表之分。这样，单元素结点应包括值域和指向其后继结点的指针域，而对于子表结点，

应包括指向子表中第一个结点的表头指针和指向其后继结点的指针域。

其结点结构可为：atom

=0结点为子表第二个域是data域或是snext域，取决于标志域atom上的值。next域存放指向与该结点同层的直接后继结点的指针。由于这种方法类似于线性表的单链表的结构，有时称为单链表方法，其类型说明如下：typedef

struct

bnode{

int

atom；struct

bnode

*next

;union{struct

bnode

*snext；/*atom=1为子表*/datatype

data；/*atom=0时为单元素*/}

elemtype

；}

slists

；第五章

数组和广义表其中，atom可作为标志域，用于区分单元素还是子表，其取值如下：1结点为单元素第五章

数组和广义表一些常见广义表的存储结构如图5.13所示。第五章

数组和广义表next1datanext2有时也可采用双链表表示法，该方法中每个结点结构为：其中next1用于指向该结点的子表，next2用于指向该结点的同层中的直接后继结点。当next1非空时，表明该结点是子表结点，此时next1为指向该子表中第一个结点的指针；data域用于存放单元素信息或子表的名字，类型定义如下：typedef

struct

dbnode{

datatype

data;struct

dbnode

*next1，*next2

；}

dblists；双链表示法如下图5.14所示：第五章

数组和广义表第五章

数组和广义表5.4.3广义表的运算广义表的运算主要有求广义表的长度和深度、向广义表插入元素和从广义表中查找、删除元素以及建立广义表的存储结构等，由于广义表是一种递归的数据结构，因此对于广义表的运算一般采用递归进行。一般将广义表的深度定义为表中括号嵌套的最大的层数或者是广义表中的括弧的重数，它是广义表的一种度量。利用递归的定义，广义表的深度等于所有子表中表的最大的深度加1。可设dep表示广义表的深度，max表示所有子表中表的最大深度，则应有depth=max+1。递归算法如下：第五章

数组和广义表int

depth（slists

*ls）/*求广义表ls的深度*{

int

max，dep；max=0；/*给max赋初值*/while(