第5章数组和稀疏矩阵

1、第第5 5章章 数组和广义表数组和广义表 5.1 5.1 数组数组5.2 5.2 稀疏矩阵稀疏矩阵5.3 5.3 广义表广义表5.1.1 5.1.1 数组的基本概念数组的基本概念 数组是数组是n(n1)个相同类型数据元素个相同类型数据元素a1,a2,an构构成的有限序列成的有限序列,且该有限序列存储在一块地址连续的且该有限序列存储在一块地址连续的内存单元中。内存单元中。 由此可见由此可见,数组的定义类似于采用顺序存储结构数组的定义类似于采用顺序存储结构的线性表。的线性表。数组具有以下性质：数组具有以下性质： (1)数组中的数据元素数目固定。一旦定义了一数组中的数据元素数目固定。一旦定义了一个数

2、组个数组,其数据元素数目不再有增减变化。其数据元素数目不再有增减变化。 (2)数组中的数据元素具有相同的数据类型。数组中的数据元素具有相同的数据类型。 (3)数组中的每个数据元素都和一组惟一的下标数组中的每个数据元素都和一组惟一的下标值对应。值对应。 (4)数组是一种随机存储结构。可随机存取数组数组是一种随机存储结构。可随机存取数组中的任意数据元素。中的任意数据元素。5.1.2 5.1.2 数组的存储结构数组的存储结构 在一维数组中在一维数组中,一旦一旦a1的存储地址的存储地址LOC(a1)确定确定,并并假设每个数据元素占用假设每个数据元素占用k个存储单元个存储单元,则任一数据元素则任一数据元

3、素ai的存储地址的存储地址LOC(ai)就可由以下公式求出：就可由以下公式求出： LOC(ai)=LOC(a1)+(i-1)*k (0in) 上式说明上式说明,一维数组中任一数据元素的存储地址可一维数组中任一数据元素的存储地址可直接计算得到直接计算得到,即一维数组中任一数据元素可直接存即一维数组中任一数据元素可直接存取取,因此因此,一维数组是一种随机存储结构。同样一维数组是一种随机存储结构。同样,二维及二维及多维数组也满足随机存储特性。多维数组也满足随机存储特性。 nmmmnnnmaaaaaaaaaA,2,1 ,22,21 ,2, 12, 11 , 1对于一个对于一个m m行行n n列的二维数

4、组列的二维数组A Am mn n, ,有：有： 将将Am*n简记为简记为A, A是这样的一维数组：是这样的一维数组： A=( a1, a2, , ai , am )其中其中,ai=(ai,1,ai,2,ai,n) (1jm)。 显然显然,二维数组同样满足数组的定义。一个二维数组同样满足数组的定义。一个二维数组可以看作是每个数据元素都是相同类二维数组可以看作是每个数据元素都是相同类型的一维数组的一维数组。以此类推型的一维数组的一维数组。以此类推,任何多维任何多维数组都可以看作一个线性表数组都可以看作一个线性表,这时线性表中的每这时线性表中的每个数据元素也是一个线性表个数据元素也是一个线性表。多维

5、数组是线性。多维数组是线性表的推广。表的推广。 对于二维数组来说对于二维数组来说,由于计算机的存储结构是线性由于计算机的存储结构是线性的的,如何用线性的存储结构存放二维数组元素就有一个如何用线性的存储结构存放二维数组元素就有一个行列次序排放问题。行列次序排放问题。 以行序为主序的存储方式：以行序为主序的存储方式：即先存储第即先存储第1行行,然后紧然后紧接着存储第接着存储第2行行,最后存储第最后存储第m行。此时行。此时,二维数组的线二维数组的线性排列次序为：性排列次序为： a1,1,a1,2,a1,n, a2,1,a2,2,a2,n , , am,1,am,2,am,n 对一个已知以行序为主序的

6、计算机系统中对一个已知以行序为主序的计算机系统中,当二当二维数组第一个数据元素维数组第一个数据元素a1,1的存储地址的存储地址LOC(a1,1)和每和每个数据元素所占用的存储单元个数据元素所占用的存储单元k确定后确定后,则该二维数组则该二维数组中任一数据元素中任一数据元素ai,j的存储地址可由下式确定：的存储地址可由下式确定： LOC(ai,j)=LOC(a1,1)+(i-1)*n+(j-1)*k 其中其中n为列数。为列数。 同理可推出在以列序为主序的计算机系统中同理可推出在以列序为主序的计算机系统中有：有： LOC(ai,j)=LOC(a1,1)+(j-1)*m+(i-1)*k 其中其中m为

7、行数。为行数。 例例5.1 对二维数组对二维数组float a54计算：计算： (1)数组数组a中的数组元素数目；中的数组元素数目； (2)若数组若数组a的起始地址为的起始地址为2000,且每个数组元素长且每个数组元素长度为度为32位位(即即4个字节个字节),数组元素数组元素a32的内存地址。的内存地址。 解：解：由于由于C语言中数组的行、列下界均为语言中数组的行、列下界均为0,该数组该数组行上界为行上界为5-1=4,列上界为列上界为4-l=3,所以该数组的元素数目所以该数组的元素数目共有共有(4-0+1)*(3-0+1)=5*4=20个。个。 又由于又由于C语言采用行序为主序的存储方式语言采

8、用行序为主序的存储方式,则有：则有： LOC(a3,2)=LOC(a0,0)+(i*n+j)*k =2000+(3*4+2)*4=2056例例5.2 约瑟夫问题：设有约瑟夫问题：设有n个人站成一圈，编号从个人站成一圈，编号从1到到n。从编。从编号为号为1的人开始循环报数的人开始循环报数“1，2，3，4，”，数到，数到m的人出列，的人出列，然后出列者的下个人重新从然后出列者的下个人重新从1开始报数，数到开始报数，数到m的人又出列，的人又出列，如此反复进行，直到如此反复进行，直到n个人都出列为止。输出个人都出列为止。输出n个人的出列顺序。个人的出列顺序。void josephus( int n,

9、int m) int pMaxSize; int i, j, t; for (i=0; in; i+) pi=i+1; / n个人编号存入数组个人编号存入数组p t=0; / t是开始报数者的下标是开始报数者的下标 cout=1; i+) / i为圈中剩下的人数为圈中剩下的人数 t=(t+m-1)%i; / t是出列者的下标是出列者的下标 coutpt“ ”; for (j=t+1; ji; j+) pj-1=pj; / 将出列者后面的每个元素前移将出列者后面的每个元素前移5.1.3 特殊矩阵的压缩存储特殊矩阵的压缩存储 特殊矩阵是指非零元素或零元素的分布有一定规特殊矩阵是指非零元素或零元素的

10、分布有一定规律的矩阵律的矩阵,为了节省存储空间为了节省存储空间, 特别是在高阶矩阵的情特别是在高阶矩阵的情况下况下,可以利用特殊矩阵的规律可以利用特殊矩阵的规律, 对它们进行压缩存储对它们进行压缩存储,也就是说也就是说,使多个相同的非零元素共享同一个存储单使多个相同的非零元素共享同一个存储单元元,对零元素不分配存储空间。对零元素不分配存储空间。 特殊矩阵的主要形式有特殊矩阵的主要形式有对称矩阵、对角矩阵，上对称矩阵、对角矩阵，上三角矩阵，下三角矩阵等三角矩阵，下三角矩阵等,它们都是方阵它们都是方阵,即行数和列即行数和列数相同。数相同。 1. 对称矩阵的压缩存储对称矩阵的压缩存储 若 一 个若

11、一 个 n 阶 方 阵阶 方 阵 A n n 中 的 元 素 满 足中 的 元 素 满 足ai,j=aj,i(0i,jn-1),则称其为则称其为n阶对称矩阵。阶对称矩阵。 由于对称矩阵中的元素关于主对角线对称由于对称矩阵中的元素关于主对角线对称,因此因此在存储时可只存储对称矩阵中上三角或下三角中的在存储时可只存储对称矩阵中上三角或下三角中的元素元素,使得对称的元素共享一个存储空间。这样使得对称的元素共享一个存储空间。这样,就就可以将可以将n2个元素压缩存储到个元素压缩存储到n(n+1)/2个元素的空间中。个元素的空间中。不失一般性不失一般性,我们以行序为主序存储其下三角我们以行序为主序存储其下

12、三角(包括包括对角线对角线)的元素。的元素。 n2个元素个元素 n(n+1)/2个元素个元素 A0.n-1,0.n-1 B0.n(n+1)/2-1 aij bk21)i(i k=+ j ij+ i ij21)j(j 156752896831079104B 1 5 2 6 8 3 7 91040 1 2 .9上三角矩阵：上三角矩阵： bk=aijA0.n-1,0.n-1 B0.n(n+1)/22)12(* ini2)1( nnk=+ j i ij时时ij时cccccB 1 5 6 7 2 8 9 3104 c0 1 2 .9 10下三角矩阵：下三角矩阵：bk=aijA0

13、.n-1,0.n-1 B0.n(n+1)/2 jii2)1(* 2)1( nnk= ij时时 ij时cccccB 1 5 2 6 8 3 7 9104 c0 1 2 .9 10 2. 对角矩阵的压缩存储对角矩阵的压缩存储 若一个若一个n阶方阵阶方阵A满足其所有非零元素都集中在满足其所有非零元素都集中在以主对角线为中心的带状区域中以主对角线为中心的带状区域中,则称其为则称其为n阶对角阶对角矩阵。其主对角线上下方各有矩阵。其主对角线上下方各有b条次对角线条次对角线,称称b为为矩阵半带宽矩阵半带宽,(2b+1)为矩阵的带宽。对于半带宽为为矩阵的带宽。对于半带宽为b(0b(n

14、-1)/2)的对角矩阵的对角矩阵,其其|i-j|b的元素的元素ai,j不为零不为零,其余元素为零。下图所示是半带宽为其余元素为零。下图所示是半带宽为b的对角矩阵的对角矩阵示意图。示意图。 . b条 b条 0 0 . . b条 b条 0 0 . 半带宽为半带宽为b b的对角矩阵的对角矩阵 当当b1时称为三对角矩阵。时称为三对角矩阵。其压缩地址计算公式如下：其压缩地址计算公式如下： k=2i+j A B aij bk A0.n-1,0.n-1 B0.3n-312000034500006780000910110000121314000015165.2 5.2 稀疏矩阵稀疏矩阵 一个阶数较大的矩阵中的

15、非零元素个数一个阶数较大的矩阵中的非零元素个数s相对相对于矩阵元素的总个数于矩阵元素的总个数t十分小时十分小时,即即st时时,称该矩称该矩阵为稀疏矩阵。例如一个阵为稀疏矩阵。例如一个100100的矩阵的矩阵,若其中若其中只有只有100个非零元素个非零元素,就可称其为稀疏矩阵。就可称其为稀疏矩阵。6 7000000000000000000000000123567000000040000A5.2.1 5.2.1 稀疏矩阵的三元组表示稀疏矩阵的三元组表示 稀疏矩阵的压缩存储方法是只存储非零元素。稀疏矩阵的压缩存储方法是只存储非零元素。 由于稀疏矩阵中非零元素的分布没有任何规律由于稀疏矩阵中非零元素的

16、分布没有任何规律,所所以在存储非零元素时还必须同时存储该非零元素所以在存储非零元素时还必须同时存储该非零元素所对应的行下标和列下标。这样稀疏矩阵中的每一个对应的行下标和列下标。这样稀疏矩阵中的每一个非零元素需由一个三元组非零元素需由一个三元组(i,j,ai,j)惟一确定惟一确定,稀疏矩阵稀疏矩阵中的所有非零元素构成中的所有非零元素构成三元组线性表三元组线性表。 假设有一个假设有一个67阶稀疏矩阵阶稀疏矩阵A(为图示方便为图示方便,我们所取我们所取的行列数都很小的行列数都很小), A中元素如下图所示。则对应的三元中元素如下图所示。则对应的三元组线性表为：组线性表为： ( (0,2,1), (1,

17、1,2), (2,0,3), (3,3,5), (4,4,6), (5,5,7), (5,6,4) ) 47000000060000000500000000030000020000010076A一个稀疏矩阵一个稀疏矩阵A A 若把稀疏矩阵的三元组线性表按顺序存储结若把稀疏矩阵的三元组线性表按顺序存储结构存储构存储, ,则称为稀疏矩阵的则称为稀疏矩阵的三元组顺序表三元组顺序表。则三。则三元组顺序表的数据结构可定义如下：元组顺序表的数据结构可定义如下： #define MaxSize 100 /*矩阵中非零元素最多个数矩阵中非零元素最多个数*/ typedef struct int r; /*行号

18、行号*/ int c; /*列号列号*/ ElemType d; /*元素值元素值*/ TupNode; /*三元组定义三元组定义*/ typedef struct int rows; /*行数值行数值*/ int cols; /*列数值列数值*/ int nums; /*非零元素个数非零元素个数*/ TupNode dataMaxSize; TSMatrix; /*三元组顺序表定义三元组顺序表定义*/ 其中其中, data域中表示的非零元素通常域中表示的非零元素通常以行序为以行序为主序顺序排列主序顺序排列,它是一种下标按行有序的存储结构。它是一种下标按行有序的存储结构。这种有序存储结构可简化

19、大多数矩阵运算算法。这种有序存储结构可简化大多数矩阵运算算法。下面的讨论假设下面的讨论假设data域按行有序存储。域按行有序存储。 (1)从一个二维矩阵创建其三元组表示从一个二维矩阵创建其三元组表示 以行序方式扫描二维矩阵以行序方式扫描二维矩阵A,将其非零的元素插入到将其非零的元素插入到三元组三元组t的后面。算法如下：的后面。算法如下：void CreatMat(TSMatrix &t, ElemType AMN) int i, j; t.rows=M; t.cols=N; t.nums=0; for (i=0; iM; i+) for (j=0; j=t.rows | cs=t.co

20、ls) return 0; while (kt.datak.r) k+;/*查找行查找行*/ while (kt.datak.c) k+;/*查找列查找列*/ if (t.datak.r=rs & t.datak.c=cs) t.datak.d=x; /*存在这样的元素存在这样的元素 else /*不存在这样的元素时插入一个元素不存在这样的元素时插入一个元素*/ for (i=t.nums-1;ik;i-) /*元素后移元素后移*/ t.datai+1.r=t.datai.r; t.datai+1.c=t.datai.c; t.datai+1.d=t.datai.d; t.datak.

21、r=rs; t.datak.c=cs; t.datak.d=x; t.nums+; return 1; (3)将指定位置的元素值赋给变量将指定位置的元素值赋给变量 先在三元组先在三元组t中找到指定的位置中找到指定的位置,将该处的元素值将该处的元素值赋给赋给x。算法如下：。算法如下：int Assign(TSMatrix t, ElemType &x, int rs, int cs) int k=0; if (rs=t.rows | cs=t.cols) return 0; while (kt.datak.r) k+; while (kt.datak.c) k+; if (t.datak

22、.r=rs & t.datak.c=cs) x=t.datak.d; return 1; else return 0; (4)输出三元组输出三元组 从头到尾扫描三元组从头到尾扫描三元组t,依次输出元素值。算法如下：依次输出元素值。算法如下：void DispMat(TSMatrix t) int i; if (t.nums=0) return;printf(“t%dt%dt%dn, t.rows, t.cols, t.nums); printf( -n); for (i=0;it.nums;i+) printf(t%dt%dt%dn,t.datai.r, t.datai.c, t.da

23、tai.d); (5)矩阵转置矩阵转置 对于一个对于一个mn的矩阵的矩阵Amn,其转置矩阵是一个其转置矩阵是一个nm的矩阵。设为的矩阵。设为Bn m,满足满足ai , j=bj , i,其中其中1im,1jn。其完整的转置算法如下：。其完整的转置算法如下：void TranTat(TSMatrix t, TSMatrix &tb ) int p, q=0, v; /*q为为tb.data的下标的下标*/ tb.rows=t.cols; tb.cols=t.rows; tb.nums=t.nums; if (t.nums!=0) for (v=0; vt.cols; v+) for (p

24、=0; pt.nums; p+) /*p为为t.data的下标的下标*/ if (t.datap.c=v) tb.dataq.r=t.datap.c; tb.dataq.c=t.datap.r; tb.dataq.d=t.datap.d; q+; 以上算法的时间复杂度为以上算法的时间复杂度为O(t.cols*t.nums),而将而将二维数组存储在一个二维数组存储在一个m行行n列矩阵中时列矩阵中时,其转置算法的其转置算法的时间复杂度为时间复杂度为O(m*n)。最坏情况是当稀疏矩阵中的。最坏情况是当稀疏矩阵中的非零元素个数非零元素个数t.nums和和m*n同数量级时同数量级时,上述转置算上述转置算

25、法的时间复杂度就为法的时间复杂度就为O(m*n2)。 对其他几种矩阵运算也是如此。可见对其他几种矩阵运算也是如此。可见,常规的非常规的非稀疏矩阵应采用二维数组存储稀疏矩阵应采用二维数组存储,只有当矩阵中非零元只有当矩阵中非零元素个数素个数s满足满足s(N)?(M):(N) /*矩阵行列较大者矩阵行列较大者*/typedef struct mtxn int row; /*行号行号*/ int col;/*列号列号*/ struct mtxn *right,*down;/*向右和向下的指针向右和向下的指针*/ union int value; struct mtxn *link; tag; Mat

26、Node;/*十字链表类型定义十字链表类型定义*/输出十字链表矩阵的算法Void DispMat(MatNode *h ) MatNode *p, *q ; printf(“行数=%d, 列数=%dn”, h-row, h-col)； p=h-tag.link;While ( p!=h ) q=p-right; / p指向某行的头结点 q指向该行的元素结点 while ( q!=p ) printf(“t%dt%dt%dn”, q-row,q-col, q-tag.value); q=q-right; / q指向该行的下个元素结点 p=p-tag.link; / 当输出完一行后，p指向下行的头

27、结点 5.3 5.3 广义表广义表5.3.1 5.3.1 广义表的定义广义表的定义 广义表简称表广义表简称表,它是线性表的推广。一个广义表是它是线性表的推广。一个广义表是n(n0)个元素的一个序列个元素的一个序列,若若n=0时则称为空表。设时则称为空表。设ai为为广义表的第广义表的第i个元素个元素,则广义表则广义表GL的一般表示与线性表的一般表示与线性表相同：相同： GL=(a1,a2,ai,an) 其中其中n表示广义表的长度表示广义表的长度,即广义表中所含元素的即广义表中所含元素的个数个数,n0。如果。如果ai是单个数据元素是单个数据元素,则则ai是广义表是广义表GL的的原子；如果原子；如果

28、ai是一个广义表是一个广义表,则则ai是广义表是广义表GL的子表。的子表。 广义表具有如下重要的特性：广义表具有如下重要的特性： (1)广义表中的数据元素有相对次序；广义表中的数据元素有相对次序； (2)广义表的长度定义为最外层包含元素个数；广义表的长度定义为最外层包含元素个数； (3)广义表的深度定义为所含括弧的重数。其中广义表的深度定义为所含括弧的重数。其中,原原子的深度为子的深度为0,空表的深度为空表的深度为1； 上述上述D的深度为的深度为3 (4)广义表可以共享；一个广义表可以为其他广义广义表可以共享；一个广义表可以为其他广义表共享；这种共享广义表称为再入表；表共享；这种共享广义表称为

29、再入表； L=(a,b,c) F = (d, L)=(d, (a,b,c) ) D = (a,(b,c), F) 长度=2 (5)广义表可以是一个递归的表。一个广义表可以是自已广义表可以是一个递归的表。一个广义表可以是自已的子表。这种广义表称为递归表。递归表的深度是无穷值的子表。这种广义表称为递归表。递归表的深度是无穷值,长度是有限值；长度是有限值； B = (a, B) = (a, (a, (a, , ) ) ) (6)任何一个非空广义表任何一个非空广义表GL均可分解为均可分解为 表头表头head(GL) = a1 表尾表尾tail(GL) = ( a2,an) 两部分。两部分。 例如例如:

30、 D = ( E, F ) = (a, (b, c)，F )head( D ) = E tail( D ) = ( F )head( E ) = a tail( E ) = ( ( b, c) )head( ( b, c) ) = tail( ( b, c) ) = head( ( b, c) ) =? tail( ( b, c) ) =?head( ( c ) ) = tail( ( c ) ) =练习：head(tail(head( ( (a,d), (c,d) ) ) )=tail(head(tail( (a,d),(c,d) ) ) )=head( ( b, c) ) =b tail(

31、 ( b, c) ) =(c)head( ( c ) ) =c tail( ( c ) ) =( )head( ( b, c) ) =( b, c) tail( ( b, c) ) = ( )head(tail(head( ( (a,d), (c,d) ) ) )=dtail(head(tail( (a,d),(c,d) ) ) )=(d)我们规定用小写字母表示原子我们规定用小写字母表示原子,用大写字母表示广用大写字母表示广义表的表名。例如：义表的表名。例如： A=( ) B=(e) C=(a,(b,c,d) D=(A,B,C)=( ( ),(e),(a,(b,c,d) E=(a,(a,b),

32、(a,b),c) 如果把每个表的名字如果把每个表的名字(若有的话若有的话)写在其表的前面写在其表的前面,则则上面的上面的5个广义表可相应地表示如下：个广义表可相应地表示如下： A( ) B(e) C(a,(b,c,d) D(A( ), B(e), C(a, (b, c, d) E(a, (a,b), (a,b), c) c a b a b E d e a b c D A B C d b c C a B e A a 若用圆圈和方框分别表示表和单元素若用圆圈和方框分别表示表和单元素,并用线段把表并用线段把表和它的元素和它的元素(元素结点应在其表结点的下方元素结点应在其表结点的下方)连接起连接起来来

33、,则可得到一个广义表的图形表示。例如则可得到一个广义表的图形表示。例如,上面五个上面五个广义表的图形表示如下图所示。广义表的图形表示如下图所示。 A( ) B(e) C(a,(b,c,d) D(A( ),B(e),C(a,(b,c,d)E(a,(a,b),(a,b),c)5.3.2 5.3.2 广义表的存储结构广义表的存储结构 广义表是一种递归的数据结构广义表是一种递归的数据结构,因此很难为每个因此很难为每个广义表分配固定大小的存储空间广义表分配固定大小的存储空间,所以其存储结构只所以其存储结构只好采用动态链式结构。好采用动态链式结构。 为了使子表和原子两类结点既能在形式上保持一为了使子表和原

34、子两类结点既能在形式上保持一致，又能进行区别，其结点定义如下：致，又能进行区别，其结点定义如下：tagsublist / datalinkTag=0时，表示原子，用时，表示原子，用data域；域；Tag=1时，表示子表，用时，表示子表，用sublist域（指针）域（指针） C 1 0 a 1 0 b 0 c 0 d 广义表的存储结构广义表的存储结构C=( a, (b,c,d) ) typedef struct lnode int tag; /*结点类型标识结点类型标识*/ union ElemType data; struct lnode *sublist; val; struct lnode

35、 *link;/*指向下一个元素指向下一个元素*/ GLNode;/*广义表结点类型定义广义表结点类型定义*/广义表的两种基本情况广义表的两种基本情况 ： g1 1 g2 1 * * * * * * 第 1 个元素 第 2 个元素 第 n 个元素 （a）空表 （b）非空表 为原子的情况为原子的情况 ： g3 0 a 5.3.3 5.3.3 广义表的运算广义表的运算1. 求广义表的长度求广义表的长度 在广义表中在广义表中,同一层次的每个结点是通过同一层次的每个结点是通过link域链域链接起来的接起来的,所以可把它看做是由所以可把它看做是由link域链接起来的单域链接起来的单链表。这样链表。这样,

36、求广义表的长度就是求单链表的长度求广义表的长度就是求单链表的长度,可可以采用以前介绍过的求单链表长度的方法求其长度。以采用以前介绍过的求单链表长度的方法求其长度。求广义表长度的非递归算法如下：求广义表长度的非递归算法如下： int GLLength(GLNode *g) /*g为一个广义表头结点的指针为一个广义表头结点的指针*/ int n=0; g=g-val.sublist;/*g指向广义表的第一个元素指向广义表的第一个元素*/ while (g!=NULL) n+; g=g-link; return n; 2. 求广义表的深度求广义表的深度 对于带头结点的广义表对于带头结点的广义表g,广

37、义表深度的递归定义广义表深度的递归定义是它等于所有子表中表的最大深度加是它等于所有子表中表的最大深度加1。若。若g为原子为原子,其深度为其深度为0。 求广义表深度的递归模型求广义表深度的递归模型f( )如下：如下：f(g)= 0 若若g为原子为原子 1 若若g为空表为空表MAXf(subg)+1 其他情况其他情况,subg为为g的子表的子表 int GLDepth(GLNode *g) /*求带头结点的广义表求带头结点的广义表g的深度的深度*/ int max=0,dep; if (g-tag=0) return 0; /*为原子时返回为原子时返回0*/ g=g-val.sublist; /*

38、g指向第一个元素指向第一个元素*/ if (g=NULL) return 1; /*为空表时返回为空表时返回1*/ while (g!=NULL) /*遍历表中的每一个元素遍历表中的每一个元素*/ if (g-tag=1) /*元素为子表的情况元素为子表的情况*/ dep=GLDepth(g); /*递归调用求出子表的深度递归调用求出子表的深度*/ if (depmax) max=dep; /*max为同一层所求过的子表中深度的最大值为同一层所求过的子表中深度的最大值*/ g=g-link; /*使使g指向下一个元素指向下一个元素*/ return(max+1); /*返回表的深度返回表的深度*/ g 1 0 a 1 0 b 0 c 0 d 3. 建立广义表的链式存储结构建立广义表的链式存储结构 假定广义表中的元素类型假定广义表中的元素类型ElemType为为char类型类型,每每个原子的值被限定为英文字母。个原子的值被限定为英文字母。 并假定广义表是一个表达式并假定广义表是一个表达式,其格式为：元素之间用其格式为：元素之间用一个逗号分隔一个逗号分隔,表元素的起止符号分别为左、右圆括号表元素的起止符号分别为左、右圆括号,空表在其圆括号内不包含任何字符。例如空表在其圆括号内不包含任何字符。例如“(a,(b,c,d)”就是一个符合上述规定的广义表格式