数据结构PPT教学课件-第5章 数组和广义表.ppt

5.1 数组的基本概念 5.2 稀疏矩阵的三元组存储 5.3 稀疏矩阵的十字链表存储 5.4 广义表 5.5 迷宫问题,第5章 数组和广义表,返回主目录,第5章数组和广义表,5.1 数组的基本概念 5.1.1 数组的概念 数组是相同类型的数据有序的组合, 数组中的每一个数据通常称为数组元素, 数组元素用下标识别, 下标的个数取决于数组的维数。例如, 一个形式如式（5.1）的m*n阶矩阵是个二维数组, 其中的每个元素都可用下标变量aij来表示, i为元素的行下标, j为元素的列下标:,amn=,a11 a12 a1n a21 a22 a2n am1 am2 amn (1im, 1jn),类似于线性表, 一个二维数组的逻辑结构可定义为 2-array=(d, r) (5.2) 其中d=aij|i=c1, c1 +1, , d1, j= c2, c2 +1, d2, aij d0 r=row, col row=| c1 i d1, c2j d2 -1, aij , ai, j+1d,col=|c1id1-1, c2jd2, aij, ai+1, jd d0为某个数椐对象, c1, c2, d1, d2均为整数。 二维数组中含有(d1 - c1 +1)*(d2 - c2 +1)个数据元素, 每一个数据元素aij都受 row(行关系)和col(列关系)的约束。ai, j+1是aij在行关系中的直接后继元素; 而ai+1, j是aij在列关系中的直接后继元素。 若将上述定义推广为n维数组, 可写出n 维数组的逻辑结构的定义如下: n-array=(d, r),其中,d= a j1 j2 jn ji =ci, c i+1, , di, i=1, 2, , n (n0) aj1j2jn0, 且ci和di均为整数 r=r1, r2, , rn ri=ckjkdk, 1kn 且 ki cijidi-1 a j1 j2 ji jn, a j1j2(ji+1)jn,每个关系中，数据元素aj1j2 ji jn(cijid i-1)都有一个直接后继元素。因此，这n个关系中的任一关系， 就其单个关系而言， 仍是线性关系。如线性表一样，所有的数据元素都必须属于同一数据类型。,数组中的每个数据元素都对应于一组下标(j1, j2, jn)， 每个下标的取值范围是c1 ji di ，其中di-ci+1 称为第 i 维的长度(i=1,2,n)。 显然, 当n=1时, n 维数组就退化为定长的线性表。反之, n 维数组也可以看成是线性表的推广。由此可见, n维数组含有ni=1 (di-ci+1)个数据元素，每个数据元素都受着n个关系的约束，也可以从另一个角度来定义n维数组。 我们可以把二维数组看成是一个定长线性表， 该线性表的每一个元素也是一个定长线性表。例如, 图式(5.4)所示是一个二维数组, 以m 行n 列的矩阵形式表示。它可以看成一个线性表达式: a=(a1, a2, , ap ) (p = m或n） 其中每个数据元素 aj是一个列向量形式的线性表达式(参见式(5.5)：,aj=(a1j, a2j, , amj) 1jn 或者每个数据元素ai 是一个行向量形式的线性表达式(参见式(5.6)：,ai=(ai1, ai2, , ain) 1im a11 a12 a13 a1n a21 a22 a23 a2n a31 a32 a11 a3n am1 am2 am3 amn,amn=,在c语言中, 一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型, 也就是说 typedef elemtype array2mn; 等价于 typedef elemtype array1n; typedef array1 array2m; 同理, 一个n 维数组类型可以定义为其数据元素为n-1 维数组类型的一维数组类型。 对数组一般讨论两种算法: （1） 给定一组有定义的下标, 存取相应的数据元素; （2） 给定一组有定义的下标, 修改相应数据元素中的某个或几个数据项的值。 ,5.1.2 数组的顺序表示 数组的顺序表示, 指的是在计算机中, 用一组连续的存储单元来表示数组。以式(5.4)的矩阵为例, 它是两行三列的矩阵, 共有 6 个元素, 在计算机中存放在 6 个连续的存储单元中（假设每个元素占一个存储单元）。,a11 a12 a13 a21 a22 a23,式（5.7）可以有两种存储方式: 一种是按行顺序存储方式, 如表5.1(a)所示; 另一种是按列顺序存储方式, 如表5.1(b)所示。,式（5.7）可以有两种存储方式: 一种是按行顺序存储方式, 如表5.1(a)所示; 另一种是按列顺序存储方式, 如表5.1(b)所示。 在basic、 pl/1、 cobol、 c和pascal语言中, 数组元素都是以行顺序存储的; 而在fortran语言中, 数组元素则是以列顺序存储的。 在数组的顺序表示中, 我们很容易根据下标求出数组元素所在的地址。下面仅对按行优先顺序表示的情形进行讨论, 并且约定每个元素占一个存储单元。 (1) 对于一维数组, 用loc(ai)表示元素ai所在的地址。 则有: loc(ai)=loc(a1)+(i-1) ,(2) 对于二维数组, 数组元素地址的计算公式为 loc(aij)=loc(a11)+n(i-1)+(j-1) 二维数组amn是一个m行n列的数组。 当数组元素按行优先顺序存放时, 第一行元素存放之后, 接着存放第二行元素, , 最后是存放第m行元素。 公式中的n(i-1)表示已存放了i-1个整行(每行有n个元素)的元素。在大多数高级语言中, 二维数组的数组元素都是按行优先顺序存储的; 但在fortran语言中, 二维数组的元素是按列优先顺序存储的, 因此, fortran语言中二维数组元素地址的计算公式为,loc(aij)=loc(a11)+m(j-1)+(i-1) (3) 对于三维数组ad1 d2 d3 , 它是一个d1层、 d2行、d3列的数组。ai1i2i3中的3个下标分别表示层下标、 行下标、列下标。在大多数高级语言中, 三维数组元素都是先按层优先、在每层内是按行优先的顺序存放元素, 因此, 数组元素地址的计算公式为 loc(aii2i3)=loc(a111)+d2d3(i1-1)+d3(i2-1)+(i3-1) 其中1i1d1, 1i2d2, 1i3i3。公式中d2d3(i1-1)表示已经存放过i1-1个整层的元素, 每层d2d3个元素; d3(i2-1)表示又存放了当前层(i1)上的(i2-1)个整行的元素, 每行有d3个元素。,(4) 对于n维数组ad1 d2 dn , 在内存中是按左下标优先, 然后按次左下标优先, , 最后按右下标的顺序存放。 假设每个数组元素ai1i2in占用一个存储单元, 且1i1d1, 1i2d2, ,1indn, 在内存中按其下标i1, i2, , in出现的顺序存储, 则数组元素的地址计算公式为 loc(ai1i2in)=loc(a 111)+d2d3dn(i 1-1)+ d3d4dn(i2-1) + dn(in-1-1)+(in-1),此公式可以写成: loc(a i1i2in)=loc(a11 1)+ ,而ar= s(1rn-1)an=1 公式中的第2项是第1维下标减1乘上其后n-1维下标的上界d2d3dn(i1-1); 第3项是第2维的下标减1乘上其后n-2维下标的上界d3d4dn (i2 -1); 以此类推, 倒数第2项是第n-1维下标减1乘上第n维下标的上界dn (in -1-1)。 应该注意, 以上讨论的前提是数组每维下标下界均为1。 在实际应用中, c语言允许下标下界为0, 而pascal允许下标下界为负整数、0或正整数, 在这种情况下, 地址计算公式就与前面的讨论有所不同。以二维数组bmn为例, b数组行下标下界不为1而是c1, 上界为d1;,列下标下界是c2, 上界为d2要求c1d1, c2d2, m=d1-c1+1, n=d2-c2+1地址计算公式为 loc(bij)=loc(b11)+(d2-c2+1)(i-1)+(j-1) 公式中第2项是i-1个整行元素, 每行d2-c2+1个元素。也可以解释为第1维下标减1乘上后面第2维下标区间。 ,5.1.3 特殊矩阵的压缩存储 上述顺序表示数组的方法, 当数组具有完整的矩阵结构时(即数组元素ai1i2in的各下标在各自独立的范围1i1d1,1i2d2, ,1indn内改变时, 大部分元素值不为零), 一般是很适合的。但也有许多情况就不适合, 例如, 下三角矩阵(矩阵中对角线以上的元素值均为零)和对称矩阵。为了节省存储空间, 可以对这些矩阵进行压缩存储。所谓压缩存储就是将多个值相同的元素只分配给一个存储空间。下面是三种特殊矩阵的形式。,这些特殊矩阵的共同特点是非零元素的分布有明显的规律, 从而我们都可将其压缩到一维数组中, 并能找到每个非零元素在一维数组中的对应位置。 对于上三角形和下三角形矩阵, 按以行序为主序的原则将矩阵的所有非零元素压缩存储到一个一维数组m1 n(n+1)/2中, 则mk和矩阵非零元素aij之间存在一一对应的关系: ,下三角形矩阵: k=i*(i-1)/2+j (ij) 上三角形矩阵: k=(2n-i+2)*(i-1)/2+(j-i+1) (ij) 对于三对角矩阵, 按以行序为主序的原则将矩阵的所有非零元素压缩存储到一个一维数组m13n-2中, 则mk和矩阵中非零元素aij之间存在一一对应的关系: k=2*i+j-2 下面给出了三对角矩阵的压缩存储的实例。 设有矩阵:,a11 a12 a21 a22a23 a32 a33 a43 a(n-1)n an(n-1)ann,a=,则压缩存储如下: ,k= 1 2 3 4 5 2*i+j-2 3*n-2,5.2 稀疏矩阵的三元组存储,在实际应用中, 往往会遇到这样一种矩阵, 其中大多数元素的值为零, 只有少部分为非零元素, 这些非零元素在矩阵中的分布又没有一定的规律, 这种矩阵称为稀疏矩阵(sparsematrix)。 至于非零元素少到多少才算稀疏矩阵并无确切定义, 但这是人们都能直观地进行分辨的概念。 例如, 式(5.8)所示的矩阵m和它的转置矩阵n, 在36个元素中只有8个非零元素, 显然是个稀疏矩阵。,15 0 0 22 0 15 0 11 3 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 91 0 0 0 0 0 0 0 28 0 0 0,m=,15 0 0 0 91 0 0 11 0 0 0 1 0 3 0 0 0 28 22 0 6 0 0 0 0 0 0 0 0 0 15 0 0 0 0 0,n=,按照压缩存储概念, 只需存储稀疏矩阵的非零元素。 但是, 为了实现矩阵的各种运算, 除了存储非零元素的值外, 还必须同时记下它所在的行和列。 这样一个三元组(i, j, aij)便能唯一地确定矩阵中的一个非零元素, 其中i, j分别表示非零元素的行号和列号, aij表示非零元素的值。下列8个三元组表示了式(5.5)中矩阵m的8个非零元素: ,（1, 1, 15）(1, 4, 22) (1, 6, 15) (2, 2, 11) (2, 3, 3) (3, 4, 6) (5, 1, 91) (6, 3, 28) 若以某种方式（以行为主或以列为主的顺序）将8个三元组排列起来, 再加上一个表示矩阵m的行数, 列数及非零元素的个数的特殊的三元组(6, 6, 8), 则所形成的表就能唯一地确定稀疏矩阵。 ,5.2.1 三元组表 假设以顺序存储结构来表示三元组表(triple table), 则得到稀疏矩阵的一种压缩存储方式, 即三元组顺序表, 简称三元组表, 其结构描述如下: typedef struct elements int i, j; elemtype v; mat; struct spmatrix int m, n, t; mat datamaxsize; a, b;,要假定data域中表示非零元素的三元组是以行为主的顺序排列的。 表5.2表示了稀疏矩阵m和n中data域的排列情况。这种表示方法, 在矩阵足够稀疏的情况下, 对存储空间的需求量比通常的方法少得多。例如我们所说的66的矩阵m, 若用三元组表来表示,在每个元素占一个存储单元的情况下, 则只需27个存储单元(包括特殊三元组所占的3个单元); 若直接用二维数组按通常办法表示, 则需36个单元。矩阵越大, 越稀疏, 其优越性越明显。,5.2.2 稀疏矩阵的运算 下面讨论稀疏矩阵的转置运算。 矩阵的转置运算是变换元素的位置, 把位于(i, j)的元素换到(j, i)位置上。也就是说, 把元素的行和列对换。 所以一个mn的矩阵m, 它的转置矩阵是一个nm的矩阵, 且ni, j=mj, i, 其中, 1in, 1jm。 例如, 式(5.8)中的矩阵n就是矩阵m的转置矩阵, 矩阵n也是一个稀疏矩阵, 其非零元素的排列情况如表5.2(b)所示。求矩阵m的转置矩阵n, 实际上就是由表5.2(a)求表5.2(b)。 对表5.2的(a)和(b)稍加分析不难看出对每个非零元素而言, 从m转置到n, 只要把a.data的第一列数和第二列数对换即可。 然而这样得到的b.data不是表5.2(b), 而是如表5.3所示的b.data。虽然b.data也能唯一确定转置矩阵n, 但它是按非零元素在n中的列序排列的。,可是, 前面我们已约定, b.data中的非零元素应按照在矩阵n中的行序排列。如何得到按非零元素在矩阵n中的行序排列的b.data呢？若按a.data中的顺序逐行转换, 即按非零元素在矩阵m中的行序转换, 则必将引起元素的频繁移动。例如, 由a.data得到b.data的转换过程中有: (1,1,15)变换成(1,1,15) (1,4,22)变换成(4,1,22) (1,6,15)变换成(6,1,15) 将其连续存放起来, 从而产生b.data的第13行的元素。 而a.data的第4个非零元素变换后, 即: (2,2,11)变换成(2,2,11), 就不应当简单地成为b.data中的第4行元素, 此时必须将(2,2,11)插入到(1,1,15)与(4,1,22)之间。这就要把b.data中原来的第2、 3行元素往下平移1行, 使(2,2,11)成为b.data的第2行。若继续此过程势必引起元素的经常移动。为了避免这种移动, 可采用下面改进的办法。 ,1. 按b.data中三元组的次序进行转置 也就是说, 按照矩阵m的列序进行转置。 显然, 为了找到m中的每一列的所有的非零元素, 需要对a.data从第1行起整个扫描一遍。由于a.data是以m的行序来存放每一个非零元素的, 所以, 这样得到的顺序恰好是b.data应有的顺序。其具体算法描述如算法5.1。,算法5.1 transmat (struct spmatrix b, struct spmatrix a) b.m=a.n;b.n=a.m; b.t=a.t; if(a.t!=0) q=0;,for(col=1;col=a.n;col+) for(p=0;pa.t;p+) if(a.datap.j=col) b.dataq.j=a.datap.i; b.dataq.i=a.datap.j; b.dataq.v=a.datap.v; q+; ,该算法使用了一个二重循环语句。外循环来控制扫描的次数, 每执行完一次外循环体, 矩阵n相当于排好了一行; 内循环则用来控制扫描a.data的第1t行, 判断每个元素在该轮中是否需要转换。 分析这个算法, 除少数附加空间, 例如p、 q、 col和t外, 它所需要的存储量仅为两个三元组表a、 b所需要的空间。因此, 当非零元素个数tm*n/3时, 其所需存储空间比直接用二维数组要省。 至于执行时间, 因算法的主要工作是在col和p的二重循环中完成的, 故算法的执行时间为o(n*t)。当非零元素个数t的量级为m*n时, 其执行时间变为o(m*n*n)。 这比直接用二维数组表示矩阵的转置算法的时间量级o(m*n)要差。,不难看出, 此算法之所以耗费时间,问题在于其每形成转置矩阵的一行, 都必须对a.data从头到尾扫描一遍。 能否对a.data只扫描一次, 又不引起元素的移动就能得到要求的b.data呢？为此, 我们提出另一种方法。 2. 按照a.data中三元组的次序进行转置 按这种方法转置后的元素不连续存放, 直接放到b.data中应有的位置上, 这样既可以避免元素移动, 又只需对a.data扫描一次。为了确定矩阵m中的每一列(即n中每一行)的第一个非零元素在b.data中应有的位置, 需要先求得矩阵m中的每一列中非零元素的个数。为此, 需设置两个数组num1n和pot1n, 分别存放在矩阵m中每一列的非零元素个数和每一列第1个非零元素在b.data中的位置, 即: numcol表示矩阵m中第col列中非零元素的个数; ,potcol的初值表示m中第col列的第1个非零元素在b.data中的位置。 于是有 pot1=0 potcol=potcol-1+numcol-1 (2coln) 对于式(5.8)中的矩阵m, 其num和pot的值如表5.4所示。 具体转置算法描述如算法 5.2。 算法5.2 fasttran (struct spmatrix b, struct spmatrix a) b.m=a.n; b.n=a.m; b.t=a.t; if (a.t!=0) ,pot1=0; for (col=2;col=a.n;col+) potcol=potcol-1+numcol-1; for (p=0;pa.t;p+) col=a.datap.j; q=potcol; b.dataq.i=a.datap.j; b.dataq.j=a.datap.i; b.dataq.v=a.datap.v; potcol+; ,此算法仅比前一个算法多用了两个辅助数组。从时间上看, 算法中有4个并列的循环语句, 它们分别执行n, t, n-1和t次, 因此, 算法的执行时间为o(n+t)。 在t和m*n等量级时, 该算法的执行时间上升到o(m*n), 但在tm*n时, 此算法是比较有效的。,5.3 稀疏矩阵的十字链表存储,5.3.1 十字链表的组成 十字链表有以下 3 个基本特征: (1) 有一个指针hm, 它所指向的结点有5个域, 如图5.1(a)所示。 row域存放总行数m, col域存放总列数n, down和right两个指针域空闲不用, next指针指向第一个行列表头结点。 (2) 有s个(s取m, n之较大者)行列表头结点h1, h2, , hs。结点结构与总表头结点相同。,row和col域置0, next指向下一行列表头结点, right指向本行第1个非零元素结点, down指向本列第1个非零元素结点, 如图5.1(b)所示。 当最后一个行列表头结点的next域指向总表头结点hm时, 就形成循环链表, 见图5.2的第1行。 (3) 非零元素结点结构也有5个域, 与其它结点域结构相似, 只是next域为一变体域, 可为val域存放非零元素的值, row、 col存放行下标值和列下标值, right指向本行的下一个非零元素结点, down指向本列的下一个非零元素结点。稀疏矩阵中同一行的非零元素通过向右域right, 链接成一个带头结点的循环链表。,同一列的非零元素也通过向下域down, 链接成一个带头结点的循环链表。因此, 每一个非零元素既是第i行循环链表中的一个结点, 又是第j列循环链表中的一个结点。 这好比处于一个十字交叉路口上, 故称这样的链表为十字链表。 例如, 对于如式(5.9)所示的54阶稀疏矩阵a的十字链表如图5.2所示。 ,3 0 0 7 0 0 -1 0 2 0 0 0 0 0 0 0 0 0 0 -3 ,a=,由图5.2可见, 每一列链表的表头结点只需用一个链域(down域), 指向该列中第一个非零元素, 而每一行链表的表头结点只需right链域, 指向该行中第一个非零元素, 恰好它们的row和col域又同时为零, 故这两组的表头结点可以合用(即第i行链表和第j列链表共用一个表头结点), 这些表头结点本身又可以通过val域相链接(注意: val域在表头结点中为next域, 是指向下一个表头结点的链域), 加上附加结点(由指针hm指示), 又组成一个带表头结点的循环链。 hm所指结点为整个十字链表的表头结点, 其row域和col域 的值分别为稀疏矩阵的行数和列数, hm为头指针。由此, 只要给定hm指针值, 便可取得整个稀疏矩阵的全部信息 。 ,5.3.2 十字链表的有关算法 十字链表的结点结构如下: (1) 建立稀疏矩阵的十字链表算法描述如算法5.3。,typedef struct int row, col; struct matnode *down, *right; union struct matnode *next; elemtype val; node;,算法5.3 crt-linkedmat(node *hm) /*hm为头指针*/ scanf(“%d %d“, /*cp1s为一组指示行表头结点的指针,for(i=1;irow=0; p-col=0; cpi=p; p-right=p; p-down=p; cpi-1-next=p; cps-next=hm; scanf(“%d %d %f“, ,while(q-right!=cpr) /*输入下一个非零元素的三元组*/ ,(2) 输出十字链表算法描述如算法 5.4。 算法 5.4 pr-linkedmat(node *hm) /*输出稀疏矩阵中非零元素的值, 并标注行与列的序号*/ node *p, *p1; int i, j; for(i=0;icol;i+) printf(“%dt“, i); printf(“n“); for(i=1, p=hm-next; p!=hm; i+), printf(“%dt“, i); for(j=1, p1=p-right; p1!=p; j+) if(j=p1-col) printf(“%4f“, p1-val); p1=p1-right; else printf(“t“); printf(“n“); p=p-next; ,5.4 广义表,5.4.1 广义表的概念和特性 广义表是n(n0)个元素的有限序列, 记作 a=(a1, a2, , an) 其中, a是广义表的名称, n是它的长度, ai(1in)或者是数据元素, 或者是广义表。显然, 广义表的定义是一个递归的定义, 广义表中可以包含广义表。 按照惯例, 用英文大写字母表示广义表的名称, 小写字母表示数据元素。对于广义表a中的某个元素ai是一个数据元素时, 称其为a的一个原子; 当其不是一个数据元素时, 则称它为广义表a的子表。当广义表a非空时, 称第一个元素a1为a的表头（head）, 称其余元素组成的表(a2, , an)为a的表尾（tail）。 ,广义表举例如下: a=( ), a是一个空表, 其长度为零。 b=(e), 列表b只有一个原子e, b的长度为1。 c=(a, (b, c, d), 列表c的长度为2, 两个元素分别为原子a和子表(b, c, d) d=(a, b, c), 列表d的长度为3, 3 个元素都是列表。 e=(a, e), 这是一个递归的表, 其长度为2, e表相当于一个无穷表。 从以上例子可以看出, 广义表可以共享子表, 且允许递归。 另外, 广义表的元素之间除了存在次序关系外, 还存在层次关系。 广义表中元素的最大层次为表的深度。元素的层次就是包含该元素的括号对的数目。例如: ,f=(a, b, (c, (d) 其中, 数据元素a, b在第一层, 数据元素c在第二层, 数据元素d在第三层。广义表f的深度为3。 根据对表头和表尾的定义可知: 任何一个非空列表其表头可能是原子, 也可能是列表, 而其表尾必定为列表。例如: head(d)=a tail(d)=(b, c) head(c)=atail(c)=(b, c, d),5.4.2 广义表的存储结构 由于广义表（a1, a2, , an)中的数据元素可以具有不同的结构(或是原子, 或是列表）, 因此难以用顺序存储结构表示, 通常采用链式存储结构, 每个数据元素可用一个结点表示。 如何设定结点的结构？由于列表中的数据元素可能为原子或列表, 由此需要两种结构的结点: 一种是表结点, 用以表示列表; 一种是原子结点, 用以表示原子。从5.4.1节得知: 若列表不空, 则可分解成表头和表尾; 反之, 一对确定的表头和表尾可唯一确定列表。 由此, 一个表结点可由 3 个域组成: 标志域、指示表头的指针域和指示表尾的指针域; 而原子结点只需两个域: 标志域和值域, 如图5.3所示。,typedef enum atom, listelemtag; /*atom=0:原子, list=1:子表*/ typedef struct glnode elemtag tag; /*公共部分, 用于区分原子结点和表结点*/ union /*原子结点和表结点的联合部分*/ atomtype atom; /*atom是原子结点的值域, atomtype由用户定义*/ struct struct glnode *hp, *pptr; /*ptr是表结点的指针域, ptr.hp和ptr.pt分别指向表头和表尾 */ ; *glist; /*广义表类型*/,5.4.1节中曾列举了广义表的例子, 它们的存储结构如图5.4所示。在这种存储结构中有几种情况: 除空表的表头指针为空外, 对任何非空列表, 其表头指针均指向一个表结点, 且该结点中的hp域指示列表表头(或为原子结点, 或为表结点), tp域指向列表表尾(除非表尾为空, 则指针为空, 否则必为表结点); 容易分清列表中原子和子表所在层次。如在列表d中, 原子a和e在同一层次上, 而b、 c和d在同一层次且比a和e低一层, a、 b和c是同一层的子表; 最高层的表结点个数即为列表的长度。,5.4.3 求广义表的深度 广义表的深度定义为广义表中括弧的重数, 是广义表的一种量度。 设非空广义表为 ls=(a1, a2, , an ) 其中ai(i=1, 2, , n)或为原子或为ls的子表, 则求ls的深度可分解为n个子问题, 每个子问题为ai的深度, 若ai是原子, 则由定义知其深度为 0；若ai是广义表, 则和上述一样处理, 而ls的深度为各ai(i=1, 2, , n)的深度中最大值加1。 空表也是广义表, 并由定义可知空表的深度为1。 由此可见, 求广义表的深度是个递归算法, 它有两个终结状态: 空表和原子, 且只要求得ai(i=1, 2, , n)的深度, 广义表的深度就容易求得了。 显然, 它应比子表的最大值多1。 ,的深度depth(ls)的递归定义为: 基本项: depth(ls)=1 当ls为空表时 depth(ls)=0 当ls为原子时 归纳项:s)(ls)=1+max depth(ai) n1由此定义容易写出求深度的递归函数。假设l是glist型的变量, 则l=null表明广义表为空表, l-tag=0表明是原子。反之, l指向表结点中的hp指向表头, 即为l的第一个子表, 而结点中的tp指针所指表尾结点中的hp指针指向l的第二个子表。在第一层中由tp相连的所有尾结点中的hp指针均指向l的子表。由此, 求广义表深度的递归函数如算法5.5所示。,算法5.5 int glistdepth(glist l) /*采用头尾链表存储结构, 求广义表l的深度*/ if(!l) return 1; /*空表深度为1*/ if (l-tag=atom) return 0; /*原子深度为0 */ for (max=0, pp=l; pp; pp=pp-ptr.tp) dep=glistdepth(pp-ptr.hp); /*求以pp-ptr.hp为头指针的子表深度*/ if (depmax) max=dep; return max+1; /*非空表的深度是各元素的深度的最大值加1*/ /glistdepth,上述算法的执行过程实质上是遍历广义表的过程, 在遍历中首先求得各子表的深度, 然后, 综合得到广义表的深度。 例如, 图5.5展示了求广义表d的深度的过程。图中用虚线示意遍 历过程中指针l的变化状况, 在指向结点的虚线旁标记的是将要遍历的子表, 而在从结点射出的虚线旁标记的数字是刚求得的子表的深度, 从图可见广义表d=(a, b, c)=( ), (e), (a, (b, c, d)的深度为3。若按递归定义分析广义表d的深度, 则有,depth(d)=1+maxdepth(a), depth(b), depth(c) depth(a)=1 depth(b)=1+maxdepth(e)=1+0=1; depth(c)=1+maxdepth(a), depth(b, c, d) =2 depth(a)=0 depth(b,c,d)=1+maxdepth(b), depth(c), depth(d) =1+0=1 由此, depth(d)=1+max1, 1, 2=3。,5.4.4 广义表的输出 在5.4.1节曾提及, 任何一个非空广义表均可分解成表头和表尾, 反之, 一对确定的表头和表尾可唯一确定一个广义表。由此, 要输出一个广义表只要分别输出表头和表尾即可, 广义表的输出也是一个递归过程。设需输出的广义表为ls, 广义表输出操作的递归定义为: 基本项: 当ls为空表时, 输出一对空的圆括号。 当ls指向原子元素时, 输出原子元素。 归纳项: 当ls指向列表时, 先输出表头, 后输出表尾。 若广义表以图5.4的链表表示, 由此可写出广义表输出的递归算法如算法5.6所示。 ,算法 5.6 status outglist(glist l, int k) /*采用头尾链表存储结构, 把广义表输出 */ if (!l) printf(“%s“, “( )“); if (l-tag=atom) printf(“%s“, l-atom); if (k=0) printf(“%c“, “(“); outglist(l-ptr.hp, 0); if (!l-ptr.tp) printf(“%c“, “)“); else printf(“%c“, “, “); outglist(l-ptr.tp, 1); /outglist,5.4.5 建立广义表的存储结构 假设把广义表的书写形式看成是一个字符串s。 广义表字符串s可能有两种情况: s=( ) (带括弧的空白串); s=( a1, a2, , an), 其中 ai(i=1, 2, , n)是s的子串。对应于第一种情况, s的广义表为空表, 对应于第二种情况, s的广义表中含有n个子表, 每个子表的书写形式即为子串 ai(i=1, 2, , n)。 此时, 可类似于求广义表的深度, 分析由s建立的广义表和由 ai(i=1, 2, , n)建立的子表之间的关系。 假设按图5.4所示结点结构来建立广义表的存储结构, 则含有n个子表的广义表中有n个表结点序列，第i(i=1, 2, , n-1)个表结点中的表尾指针指向第i+1个表结点, 第n个表结点的表尾指针为null, 并且, 如果把原子也看成是子表的话, 则第i个表结点的表头指针hp指向ai(i=1, 2, , n)建立的子表。,由此, 由s建立广义表的问题可转化为由 ai(i=1, 2, , n)建立子表的问题。又有, ai可能的三种情况: 带括弧的空白串; 长度为1的单字符串; 长度1的字符串。 显然, 前两种情况为递归的终结状态, 子表为空表或只含有一个原子结点, 后一种情况为递归调用。由此, 在不考虑输入字符串可能出错的前提下, 可得下列建立广义表链表存储结构的递归定义： 基本项: 置空广义表 当s为空表串时 建原子结点的子表 当s为单字符串时 归纳项: 假设sub为脱去s中最外层括弧的子串, 记为s1, s2, sn, 其中si(i=1, 2, , n)为非空字符串。对每一个si建立一个表结点, 并令其hp域的指针为由si建立的子表的头指针, 除最后建立的表结点的尾指针为null外, 其余表结点的尾指针均指向在它之后建立的表结点。 ,假定函数sever(str, hstr)的功能为, 从字符串str中取出第一个“,”之前的子串赋给hstr, 并使str成为删去子串hstr和“,”之后的剩余串, 若str中没有字符“,”, 则操作后的hstr即为操作前的str, 而操作后的str为空串null。 根据上述递归定义可得到建立广义表存储结构的递归函数, 如算法5.7所示。函数sever如算法5.8所示。 算法 5.7 status createglist(glist l, sstring s) /*采用头尾链表存储结构, 由广义表的书写形式串s创建广义表l, 设emp=“( )“*/ if(strcompare(s, emp) l=null; /*创建空表 */ else if (!(l=(glist)malloc(sizeof(glnode) exit (overflow); / *建表结点*/,if (strlength(s)=1) l-tag=atom; l-atom=s; /*创建单原子广义表 */ else l-tag=list; p=l; substring(sub, s, 2, strlength(s)-2); /*脱外层括号 */ do /*重复建n个子表 */ sever(sub, hsub); /*从sub中分离出表头串hsub */ creatglist(p-p.hp, hsub); q=p; if (!strempty(sub) /*表尾不空*/ if(!(p=(glnode*)malloc(sizeof(glnode) exit(,overflow); p-tag=list; q-p.tp=p; /*if*/zk) while(!strempty(sub);zk) q-p.tp=null; /*else*/ /*else*/ return ok; /*createglist*/,算法 5.8 status sever(sstring *str, sstring *hstr) /*将非空串str分割成两部分:hsub为第一个, 之前的子串, str为之后的子串*/ n=strlength(str); i=1; k=0; /*k记尚未配对的左括号个数 */ for(i=1, k=0; i=n ,/*for*/ if (i=n) substring(hstr, str, 1, i-2); substring(str, str, i, n-i+1) else strcopy(hstr, str); clearstring(str) zk) /*sever*/,5.5 迷宫问题,现以迷宫问题为例子说明数组的应用。 所谓迷宫问题, 就是把一只老鼠放进一个无盖的大箱内, 箱内设置若干隔板, 使老鼠走动的方向受到阻碍, 看其如何找到一条通道, 走出大箱。 现用二维数组mazemn来模拟迷宫, 数组元素为0表示此路可通, 数组元素为1表示此路不通。不失一般性, 设迷宫入口是maze11, 出口mazemn,且maze11=0, mazemn=0。 现要求设计算法找一条从迷宫入口到迷宫出口的通道, 如图5.6所示, maze68表示一个6*8的迷宫。 ,现在介绍一种称为广度搜索法的算法。 其算法的基本思想是将迷宫的入点(1, 1)作为第一个出发点, 向四周搜索可通行的位置, 形成第一层新的出发点, 然后对第一层中各个位置再分别向四周搜索可通行的位置, 形成第二层新的出发点 , 如此进行下去直至到达迷宫的出口点(m, n)为止。 为了避免多次检测是否走到边缘, 将迷宫四周各镶上一条取值均为1的边, 相当于在迷宫周围布上一圈不通过的墙。由此, 表示迷宫的二维数组应为mazem+2n+2。 这样, 在迷宫任一位置(x, y)(1xm, 1yn)上都有 8 个可以搜索的方位, 如图5.7所示。,从(x, y)出发, 搜索的 8 个方位顺序是从正东起沿顺时针方向进行。 为了简化问题, 可以 将 8 个方位上的i和j坐标的增量预先依次存放在一个结构数组move8中, 如表5.5所示。 这样, 只要令v从0增至7, 便可通过下述计算公式得到(x, y)的每一个相邻(i, j): i=x+movev.x j=y+movev.y 为了避免有的点被重复到达, 应标志已经通过了的位置, 这可以采用一个标志数组markm+2n+2来标志。标志数组markm+2n+2的初始状态置为“全零”, 在搜索过程中, 若通过了位置(x, y),则将markxy置为1, 因此, 判别迷宫中的某一点是否可以通行的条件, 应是mazexy和markxy同时为零。 为了记录搜索过程中到达位置及其出发点, 可以建立一个结构数组sqr, 因为迷宫中每个点至多被访问一次, 所以r至多为m*n。 sq数组的每元素有 3 个域: x、 y和pre。其中x和y分别记下到达位置的行、列坐标, pre记下其出发点在sq中的坐标。 由于先到达的点其相邻点先被搜索, 故sq数组实际上是作为一个顺序队列, 用来保存已到达点的坐标。我们用头指针front指向sq数组中当前向四周搜索的出发点, 用尾指针rear指向sq数组中当前正搜索到的可达点。 ,广度搜索法的具体实施方法如下: 从(1, 1)开