第6章 特殊矩阵、广义表及其应用

1、第第6 6章章 16.1 数组与矩阵 6.2 特殊矩阵的压缩存储 6.3 矩阵的应用实例 6.4 广义表第6章 特殊矩阵、广义表及其应用第第6 6章章 2 6.1.1 数组与矩阵的概念及其相互关系 6.1.2 数组的存储结构第第6 6章章 3数组是满足下列条件的同类型数据元素数组是满足下列条件的同类型数据元素 的集合：的集合： 对于该集合中任一数据元素对于该集合中任一数据元素 来说，来说，ji = 0，bi-1， i =1，2，n，n0称为数组的维数，称为数组的维数，bi是数组是数组第第i维的长度，维的长度，ji是数组元素的第是数组元素的第i维下标；维下标； 数据元素之间的关系表示为数据元素之

2、间的关系表示为Ri = |，0jkbk-1 ，1kn且且ki，0jibi-2 ，i =1，2，n，且且R = R1，R2，. Rn； nijjja.1nijjja.11nijjja.1nijjja.1第第6 6章章 4 下面以二维数组为例解释上述关于数组的定义。下面以二维数组为例解释上述关于数组的定义。【例【例6.1】设有二维数组】设有二维数组A，其第，其第1维的长度维的长度b1= 3，第，第2维的长度维的长度b2 = 4；数据元素描述为，其中；数据元素描述为，其中j1 = 0，b1-1= 0，1，2，j2 = 0，b2-1= 0，1，2，3；则该二维数组共有；则该二维数组共有12个具有相同个

3、具有相同数据类型的数据元素，分别为：数据类型的数据元素，分别为： Amn = a11 a12 a1n a21 a22 a2n am1 am2 amn (1im, 1jn)第第6 6章章 5 可以看出，二维数组每一行是一个一维数组，元素可以看出，二维数组每一行是一个一维数组，元素间存在序偶关系；每一列也是一个一维数组，元素间也间存在序偶关系；每一列也是一个一维数组，元素间也同样存在序偶关系。即：每个元素都受着两个关系的约同样存在序偶关系。即：每个元素都受着两个关系的约束：束： 、 。 若把每一行看作是一个整体，则行与行之间是线性若把每一行看作是一个整体，则行与行之间是线性关系；若把每一列看作是一

4、个整体，则列与列之间也是关系；若把每一列看作是一个整体，则列与列之间也是线性关系。线性关系。 21jja121jja21jjia2jjia第第6 6章章 6 这样，我们可以把二维数组看成是一个线性表，它这样，我们可以把二维数组看成是一个线性表，它的每一个数据元素是一个一维数组，也是一个线性表。的每一个数据元素是一个一维数组，也是一个线性表。 由此可以推广到由此可以推广到n维数组。我们说维数组。我们说n维数组是一个线维数组是一个线性表，它的每一个数据元素是性表，它的每一个数据元素是n-1维数组，也是一个线维数组，也是一个线性表。性表。 数组一旦被定义，其维数及每维的长度数组一旦被定义，其维数及每

5、维的长度(维界维界)就不再就不再改变。因此，改变。因此，数组的运算除了初始化和销毁之外，只有数组的运算除了初始化和销毁之外，只有查找元素和修改元素值的操作。查找元素和修改元素值的操作。 第第6 6章章 7 矩阵是由矩阵是由mn个数排列成个数排列成m行行(横向横向)、n列列(纵向纵向)所所形成的矩形数表：形成的矩形数表： )1 ,1 (,.212222111211njmiaaaaaaaaaamnmmijnnnmA称为称为mn矩阵，简记为矩阵，简记为A=(aij)mn，其中，其中aij为为A的第的第i行行第第j列的元素。列的元素。 第第6 6章章 8 对照上述数组的定义，我们不难看出，矩阵中所有对

6、照上述数组的定义，我们不难看出，矩阵中所有数据元素组成了一个二维数组，矩阵的每一行、每一数据元素组成了一个二维数组，矩阵的每一行、每一列的数据元素分别组成等长的一维数组。列的数据元素分别组成等长的一维数组。 我们也可以说，矩阵是一个线性表，其每一个数据我们也可以说，矩阵是一个线性表，其每一个数据元素元素(行或列行或列)也是一个线性表。也是一个线性表。 第第6 6章章 9 6.1.1 数组与矩阵的概念及其相互关系 6.1.2 数组的存储结构第第6 6章章 10 由于数组一般不作插入和删除操作，因此采用顺序存储结构是理所当然的。 下面以二维数组为例来说明：二维数组一般有两种方法来存储：1、按行优先

7、顺序存储、按行优先顺序存储 将数组元素按行向量排列， i+1行向量接在 i 行向量后面。第第6 6章章 11 a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .Loc( aij)=Loc(a11)+(i-1)n+(j-1)*l 按行序为主序存放按行序为主序存放 amn . am2 am1 . a2n . a22 a21 a1n . a12 a1101n-1m*n-1n第第6 6章章 122、按列优先顺序存储、按列优先顺序存储 将数组元素按列向量排列， j+1列向量接在 j 列向量后面。第第6 6章章 13 按列序为主序存放按列序为主序存放01m-1m*n-1

8、m amn . a2n a1n . am2 . a22 a12 am1 . a21 a11 a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .Loc(aij)=Loc(a11)+(j-1)m+(i-1)*l 第第6 6章章 14 按上述两种方式顺序存储的数组，只要知道按上述两种方式顺序存储的数组，只要知道的值），以的值），以及及，就可求出各个数，就可求出各个数组元素的存储地址。组元素的存储地址。 第第6 6章章 15设设 数组的首地址数组的首地址 即：即： a11 的地址的地址 记为：记为： LOC (a11)则：二维数组按则：二维数组按“行优先顺序行优先顺

9、序”存储，数组元素的存存储，数组元素的存储地址为：储地址为： LOC (a11) + 前面前面 i 1行元素所占字节数行元素所占字节数 + 第第j 行中前行中前j 1个元素所占字节数个元素所占字节数即：即：LOC( aij ) = LOC(a11) + ( i-1)*n*d +(j -1)*d 前面前面 i 1行元素的行元素的个数（每行个数（每行n个）个）每个元素所占每个元素所占的字节数的字节数第第6 6章章 16 Loc(aij)=Loc(a11)+(j-1)*m+(i-1)*K （尽管是方阵，但公式仍不同）（尽管是方阵，但公式仍不同）【例【例1 1】一个二维数组一个二维数组A A，行下标的

10、范围是，行下标的范围是1 1到到6 6，列下标，列下标的范围是的范围是0 0到到7 7，每个数组元素用相邻的，每个数组元素用相邻的6 6个字节存储，个字节存储，存储器按字节编址。那么，这个数组占用存储器按字节编址。那么，这个数组占用 个字节。个字节。 答：答： m*n*L=(6-1+1)*(7- 0 +1)*6=48*6=288第第6 6章章 17 6.1 数组与矩阵 6.2 特殊矩阵的压缩存储 6.3 矩阵的应用实例 6.4 广义表第6章 特殊矩阵、广义表及其应用第第6 6章章 18 在用高级语言编写程序时，通常在用高级语言编写程序时，通常。但对一些数据分布呈某种规律的矩阵，或是。但对一些数

11、据分布呈某种规律的矩阵，或是0元元素大量存在素大量存在(远远多于非远远多于非0元素元素)的矩阵，采用上述存储的矩阵，采用上述存储方法会造成存储空间的极大浪费。方法会造成存储空间的极大浪费。 第第6 6章章 19 若矩阵中非若矩阵中非0 0元素呈某种规律分布，或存在大量元素呈某种规律分布，或存在大量0 0元元素，为节省存储空间，可对这类素，为节省存储空间，可对这类： 即：即：。 若值相同的非若值相同的非0 0元素或元素或0 0元素在矩阵中的分布有一元素在矩阵中的分布有一定的规律，我们称此矩阵为定的规律，我们称此矩阵为；反之，称为；反之，称为。第第6 6章章 20 所谓特殊矩阵是指非零元素或零元素

12、的分布有一所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。存储。 在一个在一个n n阶方阵阶方阵A A中，若元素满足下述性质：中，若元素满足下述性质： aij=aji 0=i, j=0)(i=0)，元素总数为：元素总数为：n(n+1)/2 因此，我们可以按从上到下、从左到右将这些元素存因此，我们可以按从上到下、从左到右将这些元素存放在一个向量放在一个向量san(n+1)/2中。为了便于访问对称矩阵中。为了便于访问对称矩阵A A中的元素，我们必须在中的元素，我们必须在aij和和sak之间找一个对应关系。之间找

13、一个对应关系。a11 a12 a1n a21 a22 a2n an1 an2 ann 第第6 6章章 23 若若，则，则aij在下三角形中。在下三角形中。 aij之前的之前的i i行（从第行（从第0 0行到第行到第i-1行）一共有行）一共有1+2+i=i(i+1)/2个元素，在第个元素，在第i i行行上，上， aij之前恰有之前恰有j个元素（即个元素（即ai0, ai1, ai2, , aij-1），因此），因此有：有： k=i*(i+1)/2+j 0k n(n+1)/2 若若，则，则aij是在上三角矩阵中。因为是在上三角矩阵中。因为aij= aji，所以只，所以只要交换上述对应关系式中的要交

14、换上述对应关系式中的i和和j即可得到：即可得到： k=j*(j+1)/2+i 0kj第第6 6章章 27 下三角矩阵的存储和对称矩阵类似，下三角矩阵的存储和对称矩阵类似，sak和和aij对应对应关系是：关系是： i(i+1)/2+j ij n(n+1)/2 ij k =第第6 6章章 28 对角矩阵中，所有的非零元素集中在以主对角线对角矩阵中，所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵，零。下图给

15、出了一个三对角矩阵， a00 a01 a10 a11 a12 a21 a22 a23 . . . an-2 n-3 an-2 n-2 an-2 n-1 an-1 n-2 an-1 n-1 第第6 6章章 29三对角矩阵有如下特点：三对角矩阵有如下特点： 1, 2, 11, 1, 101 , 0, 0nnjniiiijniji当当时，时，aij非非0； 其它情况时，其它情况时，aij的值为的值为0。 第第6 6章章 30 我们以行序为主序进行存储三对角矩阵，并且只存我们以行序为主序进行存储三对角矩阵，并且只存储矩阵中的非储矩阵中的非0元素。元素。 在在n阶三对角矩阵中，除了第一行和最后一行只有阶

16、三对角矩阵中，除了第一行和最后一行只有2个非个非0元素外，其余各行均有元素外，其余各行均有3个非个非0元素，元素， 共共2+2+3*(n-2) = 3n-2个非个非0元素。元素。 这样，可以将该三对角矩阵存储在一维数组这样，可以将该三对角矩阵存储在一维数组sa3n-2中。现在，对给定的非中。现在，对给定的非0元素元素aij，与其对应的数组元素的，与其对应的数组元素的下标是什么呢？下标是什么呢？第第6 6章章 31 由三对角矩阵的特点知，矩阵中的非由三对角矩阵的特点知，矩阵中的非0元素元素aij的前的前面有面有i行，共有行，共有3i-1个非个非0元素；在元素元素；在元素aij所在的第所在的第i行

17、，行，aij之前有之前有j-i+1个非个非0元素。因此可得与非元素。因此可得与非0元素元素aij对应对应的数组元素的下标为：的数组元素的下标为： k=3i-1+j-i+1=2i+j 这样，非零元素这样，非零元素aij的地址为：的地址为： LOC(i,j)=LOC(0,0)+3*i-1+(j-i+1)*d =LOC(0,0)+(2i+j)*d第第6 6章章 32 上述的各种特殊矩阵，其非零元素的分布都是有上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量个向量中，并且

18、一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。随机存取。第第6 6章章 33 什么是稀疏矩阵？什么是稀疏矩阵？ 简单说，设矩阵简单说，设矩阵A A中有中有s s个非零元素，若个非零元素，若s s远远小于矩远远小于矩阵元素的总数（即阵元素的总数（即smst 存放矩阵M的数组是 adatamaxsize am , n , t data 1 3 -3 1 6 15 2 1 12 2 5 18 3 1 93 4 244 6 -75 3 14 第第6 6章章 40 第一个数组元素（三元组）所在的行号、列号分别第一个数

19、组元素（三元组）所在的行号、列号分别是：是： ( adata0).i (adata0) .j 它的值为：它的值为： ( adata0).v 第第6 6章章 41 若矩阵的非若矩阵的非0元素的个数和位置在操作过程中变化元素的个数和位置在操作过程中变化较大，则不宜采用顺序存储结构来表示三元组的线较大，则不宜采用顺序存储结构来表示三元组的线性表。性表。 可采用链式存储结构来表示三元组的线性表。可采用链式存储结构来表示三元组的线性表。第第6 6章章 42 在链表中，每个非在链表中，每个非0 0元素可用一个含有五个域的元素可用一个含有五个域的结点表示：结点表示：ijvcptrrptr i , j ,v

20、三个域分别表示该元素所在的行、列三个域分别表示该元素所在的行、列和非和非0元素的值。行指针域元素的值。行指针域 rptr 用以链接同一行中下一用以链接同一行中下一个非个非0元素；列指针域元素；列指针域 cptr 用以链接同一列中下一个非用以链接同一列中下一个非0元素。元素。 第第6 6章章 43 存储时，每个非存储时，每个非0 0元既是某个行链表中的一个结点，元既是某个行链表中的一个结点，又是某个列链表中的一个结点；整个矩阵构成了一个十又是某个列链表中的一个结点；整个矩阵构成了一个十字交叉的链表字交叉的链表故称这样的存储结构为故称这样的存储结构为 两个两个一维一维数组数组 M-chead M-

21、rhead 第第6 6章章 44十字链表中非十字链表中非0元结点的类型说明如下：元结点的类型说明如下： typedef struct lnode int i , j ; datatype v ; struct lnode *cptr , *rptr ; OLnode； ijvcptrrptr第第6 6章章 45十字链表的类型描述如下：十字链表的类型描述如下： #define N 10 /预设稀疏矩阵的行数预设稀疏矩阵的行数 #define K 10 /预设稀疏矩阵的列数预设稀疏矩阵的列数 typedef /*行数、列数、非行数、列数、非0元个数元个数*/ Crosslist ; Crossli

22、st *M ; 第第6 6章章 46 讨论：讨论：如何建立一个十字链表如何建立一个十字链表 算法步骤：算法步骤： 1、建立两个一维数组 Mchead 、 Mrhead 分别存储列链表及行链表的头指针。 初始时， Mcheadj = NULL , Mrheadj = NULL. 2、读入非0元结点的三元组（ i , j , v ），生成一个结点*p ,将其插入第 i 个行链表和第j个列链表的正确位置上。 第第6 6章章 47 6.1 数组与矩阵 6.2 特殊矩阵的压缩存储6.3 矩阵的应用实例 6.4 广义表第6章 特殊矩阵、广义表及其应用第第6 6章章 48求稀疏矩阵求稀疏矩阵A A的转置矩阵

23、的转置矩阵B B 一个一个m mn n的矩阵的矩阵A A，它的转置，它的转置B B是一个是一个n nm m的矩阵，的矩阵，且且aij=bjiaij=bji，0 0i im m，0 0j jn n，即，即A A的行是的行是B B的的列，列，A A的列是的列是B B的行的行。0 0 -3 0 0 1512 0 0 0 18 09 0 0 24 0 00 0 0 0 0 70 0 14 0 0 0 0 0 0 0 0 00 0 0 0 0 0A = 0 12 9 0 0 0 00 0 0 0 0 0 0-3 0 0 0 14 0 00 0 24 0 0 0 00 18 0 0 0 0 0 15 0

24、0 -7 0 0 0B = 第第6 6章章 49 将将A A转置为转置为B B，就是将，就是将A A的三元组表的三元组表a-dataa-data置换为表置换为表B B的三元组表的三元组表b-datab-data。 有有： at = bt ; am = bn ; an = bm ; 但但:(adatax).i (bdatax).j 为什么？ 第第6 6章章 50 也不能将也不能将 (adatax).i 与与(adatax).j 简单互简单互换！换！为什么？ 如果只是简单地交换如果只是简单地交换a-dataa-data中中i i和和j j的内容，那的内容，那么得到的么得到的b-datab-data

25、将是一个按列优先顺序存储的稀疏矩将是一个按列优先顺序存储的稀疏矩阵阵B B，要得到按行优先顺序存储的，要得到按行优先顺序存储的b-datab-data，就必须重新，就必须重新排列三元组的顺序。排列三元组的顺序。 第第6 6章章 510 0 -3 0 0 1512 0 0 0 18 09 0 0 24 0 00 0 0 0 0 70 0 14 0 0 0 0 0 0 0 0 00 0 0 0 0 0A = 0 12 9 0 0 0 00 0 0 0 0 0 0-3 0 0 0 14 0 00 0 24 0 0 0 00 18 0 0 0 0 0 15 0 0 -7 0 0 0B = 行号行号i

26、列号列号j 值值v行号行号i 列号列号j 值值v1 3 -31 6 152 1 122 5 18 3 1 93 4 244 6 -75 3 141 2 12 1 3 93 1 -33 5 144 3 245 2 186 1 156 4 -7第第6 6章章 52算法步骤如下：算法步骤如下：(1) 产生顺序表b，存放转置后的矩阵B Spmatrix *b; b = malloc( sizeof (Spmatrix); 并并确定其结点个数、行数、列数。即：bt = at ;bm = an ; bn = am ;第第6 6章章 53(2) 一维数组一维数组 bdata结点个数结点个数 中各数组元素赋值

27、，中各数组元素赋值，且且bdata 按行优先。按行优先。 具体做法如下：具体做法如下： 对三元组表对三元组表adata 扫描扫描(从第一行开始从第一行开始) 令：令：x为数组为数组adata 中数组元素的下标中数组元素的下标 y为数组为数组bdata 中数组元素的下标中数组元素的下标第第6 6章章 54扫描过程：扫描过程：首先，令首先，令 y = 0; for (x = 0; x datax).j = = 1 (1是列号是列号) 若为1 则 (bdatay).v = (adatax).v (bdatay).i = (adatax).j (bdatay).j = (adatax).i y+第第6

28、 6章章 55 下面再次扫描三元组表（数组）下面再次扫描三元组表（数组）adata ，查，查寻矩阵寻矩阵M中第二列的元素：中第二列的元素：此时，此时，； for (x = 0; x datax).j = = 2 (2是列号是列号) 若为若为2 则则 (bdatay).v = (adatax).v (bdatay).i = (adatax).j (bdatay).j = (adatax).i y+第第6 6章章 56这样，整个扫描的过程可描述为： for ( = 1; =； +) for (x = 0; x datax).j = = ) (bdatay).v = (adatax).v ; (bd

29、atay).i = (adatax).j ; (bdatay).j = (adatax).i ; y+ ; 第第6 6章章 57算法分析：算法分析： 该算法的时间主要耗费在 z 和 x 的二重循环上，若矩阵M的列数为 n ，非0元素个数为 t ，则 算法的时间复杂度数量级为算法的时间复杂度数量级为: O( n*t )第第6 6章章 58 6.1 数组与矩阵 6.2 特殊矩阵的压缩存储 6.3 矩阵的应用实例 6.4 广义表第6章 特殊矩阵、广义表及其应用第第6 6章章 596.4.1 广义表的概念 6.4.2 广义表的存储结构 6.4.3 广义表的应用6.4 广义表第第6 6章章 60 广 义

30、 表 是广 义 表 是 n ( n 0 ) 个 元 素 的 有 限 序 列个 元 素 的 有 限 序 列 , 记 作记 作 A=(a1, a2, , an) 其中其中, A是广义表的名称是广义表的名称, n是它的长度是它的长度, ai(1in)或者或者是数据元素是数据元素, 或者是广义表。或者是广义表。 习惯上：习惯上： 用英文大写字母表示广义表的名称用英文大写字母表示广义表的名称, 小写字小写字母表示数据元素。母表示数据元素。第第6 6章章 61 对于广义表对于广义表A中的某个元素中的某个元素ai ：若它是一个数：若它是一个数据元素时据元素时, 称其为称其为A的一个原子的一个原子; 当其不是

31、一个数据当其不是一个数据元素时元素时, 则称它为广义表则称它为广义表A的子表。的子表。 当广义表当广义表A非空时非空时, 称第一个元素称第一个元素a1为为A的表头的表头(head), 称其余元素组成的表称其余元素组成的表(a2, , an)为为A的表尾的表尾(tail)。广义表举例如下广义表举例如下: A=( ) A是一个空表是一个空表, 其长度为零。其长度为零。 B=(e) 广义表广义表B只有一个原子只有一个原子e, B的长度为的长度为1。 第第6 6章章 62 C=(a, (b, c, d), 广义表广义表C的长度为的长度为2, 两个元素分别两个元素分别为原子为原子a和子表和子表(b, c

32、, d) D=(A, B, C), 广义表广义表D的长度为的长度为3, 3 个元素都是广个元素都是广义表。义表。 E=(a, E), 这是一个递归的表这是一个递归的表, 其长度为其长度为2, E表相当表相当于一个无穷表。于一个无穷表。从以上例子可以看出：从以上例子可以看出： 广义表可以共享子表广义表可以共享子表, 且允许递归。且允许递归。 广义表的元素之间除了存在次序关系外广义表的元素之间除了存在次序关系外, 还存在层还存在层次关系。次关系。 第第6 6章章 63 广义表中元素的最大层次为表的深度。元素的层次广义表中元素的最大层次为表的深度。元素的层次就是包含该元素的括号对的数目。就是包含该元

33、素的括号对的数目。 例如例如: F=(a, b, (c, (d) 其中其中, 数据元素数据元素a, b在第一层在第一层, 数据元素数据元素c在第二层在第二层, 数据元素数据元素d在第三层。广义表在第三层。广义表F的深度为的深度为3。 任何一个非空广义表，其表头可能是原子任何一个非空广义表，其表头可能是原子, 也可能是也可能是广义表广义表, 而其表尾必定为广义表。而其表尾必定为广义表。第第6 6章章 64例如例如: 若若 C=(a, (b, c, d) D=(A, B, C) 则：Head(D)=A Tail(D)=(B, C) Head(C)=a Tail(C)=(b, c, d)以上是广义表

34、的两个操作以上是广义表的两个操作： 取表头 Head 、取表尾Tail 这些操作还可以嵌套调用：这些操作还可以嵌套调用： Head（ Tail(D) ） Head(B,C) = B取广义表取广义表D D的第二个元的第二个元素素第第6 6章章 65注意：注意： 广义表广义表（）（）和广义表和广义表( )不同。不同。 （）（）为空表，长度为空表，长度 n0 ，不能分解成表头和表尾。，不能分解成表头和表尾。 ( ) 不是空表，其长度不是空表，其长度 n = 1 ，可以分解得到表头是，可以分解得到表头是空表空表( ) , 表尾是空表表尾是空表( ) .第第6 6章章 66 6.4.1 广义表的概念 6

35、.4.2 广义表的存储结构 6.4.3 广义表的应用6.4 广义表第第6 6章章 67 由于广义表（由于广义表（a1, a2, , an)中的数据元素可以具有不中的数据元素可以具有不同的结构同的结构(或是原子或是原子, 或是列表）或是列表）, 因此难以用顺序存储因此难以用顺序存储结构表示结构表示, 通常采用链式存储结构通常采用链式存储结构, 每个数据元素可用每个数据元素可用一个结点表示。一个结点表示。 如何设定结点的结构？由于列表中的数据元素可能如何设定结点的结构？由于列表中的数据元素可能为原子或列表为原子或列表, 由此需要两种结构的结点由此需要两种结构的结点: 一种是表结点一种是表结点, 用

36、以表示列表用以表示列表; 一种是原子结点一种是原子结点, 用用以表示原子。以表示原子。 第第6 6章章 68 按前述分析：按前述分析： 由此由此, 一个一个可由可由 3 个域组成个域组成: ; 而而只需两个只需两个域域: ：原子结点原子结点atomtag = 0 tag = 1hptp表结点表结点第第6 6章章 69原子结点原子结点atomtag = 0 类型说明如下：类型说明如下： typedef enum ATOM, LIST ElemTag ; /*ATOM=0：原子, LIST=1:子表*/tag = 1hptp表结点表结点枚举类型枚举类型第第6 6章章 70typedef struc

37、t GLNode ElemTag tag ; union AtomType atom ; struct struct GLNode *hp, *tp ; ptr ; ; Glist ;公共部分公共部分, 用于区分用于区分原子结点和表结点原子结点和表结点原子结点和原子结点和表结点的联表结点的联合部分合部分ptr.hp和和ptr.pt分别指向分别指向表头和表尾表头和表尾广义表类型广义表类型第第6 6章章 71 A=( ) B=(e) C=(a, (b, c, d) D=(A, B, C) E=(a, E)Glist *A; A = NULL10eBCDE110a1110b0c0d111110a第第

38、6 6章章 72在这种存储结构中有几种情况：在这种存储结构中有几种情况： 除空表的表头指针为空外，对任何非空广义表，除空表的表头指针为空外，对任何非空广义表，其表头指针均指向一个表结点，且该结点中的其表头指针均指向一个表结点，且该结点中的（或为原子结点，或为表结点），（或为原子结点，或为表结点），（除非表尾为空，则指针为空，否则（除非表尾为空，则指针为空，否则必为表结点）；必为表结点）；第第6 6章章 73 如在广如在广义表义表D中，原子中，原子a和和e在同一层次上，而在同一层次上，而b、c和和d在同一在同一层次且比层次且比a和和e低一层，低一层，B和和C是同一层的子表；是同一层的子表； 第第

39、6 6章章 74 6.4.1 广义表的概念 6.4.2 广义表的存储结构 6.4.3 广义表的应用6.4 广义表第第6 6章章 75 一个一个m元多项式的每一项最多有元多项式的每一项最多有m个变元，如果用个变元，如果用单链表表示，则每个节点应该包括单链表表示，则每个节点应该包括m个指数项和一个数个指数项和一个数据项；如果多项式各项的变元数不相同，将势必造成存据项；如果多项式各项的变元数不相同，将势必造成存储空间的浪费。为此，我们考虑采用其它的方式来存储储空间的浪费。为此，我们考虑采用其它的方式来存储一个一个m元多项式。元多项式。 我们以三元多项式：我们以三元多项式：P(x,y,z) = x10

40、y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15 为例，讨论其存储表示。为例，讨论其存储表示。 第第6 6章章 76P(x,y,z) = x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15 该多项式中各项的变元数目不尽相同，某些因子多该多项式中各项的变元数目不尽相同，某些因子多次出现，我们可以将其改写为：次出现，我们可以将其改写为：P(x,y,z) = (x10 + 2x6)y3+3x5y2)z2+(x4 + 6x3)y4+2y)z+15 此时，该多项式就变成了变元此时，该多项式就变成了变元z的多项式，的多项式，即即A z2 + B z1 +15 z0，对这个一元多项式我们用单链表，对这个一元多项式我们用单链表表示为：表示为： 第第6 6章章 77 变元变元z的多项式的多项式A z2 + B z1 +15 z0中的中的A、B又是一个又是一个多项式。多项式。 其中，其中，A = (x10 + 2x6) y3 + 3x5y2