数据结构-用C语言描述(第二版)第5章数组和广义表.ppt

《数据结构-用C语言描述(第二版)第5章数组和广义表.ppt》由会员分享，可在线阅读，更多相关《数据结构-用C语言描述(第二版)第5章数组和广义表.ppt（51页珍藏版）》请在三一办公上搜索。

1、5.1 数组及其运算5.2 数组的顺序存储结构 5.3 矩阵的压缩存储5.4 广义表5.5 m元多项式的表示,第5章 数组和广义表,第5章 数组和广义表,本章前几章所讨论的线性表、栈、队列和串都是线性的数据结构。它们的组成元素的值都是不可分解的。本章将要讨论的多维数组和广义表是一种复杂的非线性结构，它的组成元素是可以分解的，每个元素可以有多个的直接前趋和直接后继。本章主要介绍数组的概念及多维数组在计算机中的存放，特殊矩阵的压缩存储及相应运算，广义表的概念和存储结构及其相关运算的实现。,5.1 数组及其计算,几乎所有的程序设计语言中都有利用数组来描述数据。由于数组中的各元素具有统一的类型，而且数

2、组元素的下标具有固定的上下界，所以，它比其它复杂的数据结构更容易处理。根据数组元素的组织形式不同，数组可以分为一维数组、二维数组以及多维（n维）数组。例如，二维数组,它由固定数量的mn个元素所组成，且每个数据元素aij均受两个下标关系约束。除边界外，每个数据元素都有两个直接前趋和直接后继结点，即行关系上的直接前趋aij-1和直接后继aij+1，列关系上的直接前趋ai-1j 和直接后继ai+1j，而且仅有一个开始结点a00，它没有直接前趋；仅有一个终端结点an-1n-1，它没有直接后继；而边界上的结点除开始和终端结点外，每个结点均只有一个直接前趋或只有一个直接后继，因此，二维数组可以看作是线性表

3、的推广。同时，二维数组可看作是由二个一维数组作为数据元素定义的一维数组，数据元素之间在每一个关系中仍具有线性特性，但在整个结构中呈非线性关系。如图5.1所示。同样，三维数组A mnp可以看作是其数据元素为二维数组表示的特殊线性表，每个元素最多可以有三个直接前趋和三个直接后继，；依此类推，n维数组中的每个元素最多可以有n个直接前趋和n个直接后继。由此可知，多维数组是一种复杂的数据结构，且也可以看作是线性结构的推广。对于一个数组结构而言，一般只有存取元素和修改元素值两种运算。,A mn=(（a00，a01，a 0n-1），（a10，a11，a1n-1），（am-10，a m11，,a m-1n-1

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

5、顺序存储结构,图5.2 二维数组的两种存储方式,由于多维数组其下标不只2个，一般规定以下标顺序或以逆下标顺序为主序的优先存储方式。顺序存储的数组是一个随机存取结构。多维数组的数据元素存储地址的计算。一个二维数组Amn，若以行为主序优先存储，且已知a00的存储地址LOC(a00)（即二维数组A的起始存储位置，亦称为基地址或基址）和每个数据元素所占用的存储单元个数c，则二维数组中任一数据元素ai,j的存储地址可由下式确定:LOC(aij)=LOC(a00)+(in+j)c同理可推导出以列为主序优先存储时数据元素aij的存储地址，其计算公式为：LOC(a i j)=LOC(a00)+(j n+i)c

6、 对于三维数组 A mnp而言，若以行为主序优先存储时，则其数据元素aijk的存储地址可为：LOC(a i j k)=LOC(a000)+i m p+j p+k c 对于一般的二维数组Ac1d1，c2d2而言，此处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 列的数值构成。在编程时，通常利用二维数组来存储矩阵。但在某些情况下，特别是在数值分析中经常会出现一些阶数很高的矩阵，其中含有许多值相同的元素或

7、零元素，若利用二维数组存储会浪费空间。为了节省存储空间并且加快处理速度，需要对这类矩阵进行压缩存储，也就是说可以对多个具有相同值的元素只分配一个存储空间，而对零元素则不分配空间。一般的，压缩存储适用于特殊矩阵和稀疏矩阵。特殊矩阵是指那些具有相同值的元素或零元素在矩阵中的分布有一定的规律矩阵；而稀疏矩阵是指那些零元素远远多于非零元素，并且非零元素的分布没有规律的矩阵。,5.3.1 特殊矩阵 1.三角矩阵 n阶三角矩阵以对角线划分有上三角与下三角矩阵两种。上三角矩阵是指矩阵的下三角（不含对角线）中的元素均为常数C或零的n阶矩阵，下三角矩阵则与之相反，如图5.3所示。,个元素，而在第i+1行上，ai

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

9、 k=n(n+1)/2 当i j,2.对称矩阵 若一个n阶方阵A中的元素满足下列性质：a ij=a ji 0i，jn-1则称A为对称矩阵，如一个4阶对称矩阵如图5.4所示。,图5.4 4阶对称矩阵示例,因此，可以按图5.5所示的次序将矩阵元素存放在一个一维数组Mn（n+1）/2中，其存储方式如图5.6所示。这样，给出对称矩阵A中的任一个元素aij，依据它的下标i和j就可由对应关系式确定其在数组M中的位置k，aij 的地址LOC（aij）可由下式计算：LOC（aij）=LOC（Mk）=LOC（M0）+kc=LOC（M0）+I（I+1）/2+J c 其中，c为每个数据元素所占的存储单元数目，且 I

10、=max（i，j），J=min（i，j）从而，k=I*（I+1）/2+J，即k为i，j统一后的值。,由于对称矩阵中的元素关于主对角线对称，所以可以只存储矩阵中主对角线（含对角线）以上或以下的元素，即只为每一对对称元素分配一个存储空间，将共有nn个的元素压缩存储到n(n+1)/2个存储空间中，从而节省了空间。假定按以行为主序优先方式存储主对角线（包括对角线）以下的元素，则其存储次序如图5.5所示。在上述的下三角矩阵中，矩阵元素总数为：,图5.5 对称矩阵的行优先排列存放,K=0 1 2 n(n+1)/2-1,图5.6 对称矩阵的压缩存储情况,5.3.2 稀疏矩阵 如果矩阵中非零元素的个数远远小于

11、矩阵元素的总数，并且非零元素的分布没有规律，则称此类矩阵为稀疏矩阵。稀疏矩阵的压缩存储，可以在存储非零元素的同时，存储适当的辅助信息。例如，可以利用一个三元组元素（i，j，aij）就可唯一地确定矩阵A中的非零元素，这样，稀疏矩阵可由表示非零元素的三元组及其行、列数唯一地确定。例如，稀疏矩阵A：,可由三元组表(0,1,5)，(0,4,8)，(1,0,1)，(1,2,3)，(2,1,-2)，(3,0,6)加上(4,5)这一行、列数对来描述。,一般地，可以用三元组表表示法和十字链表作为稀疏矩阵的压缩存储方法，其中以三元组表示法最常用。1.三元组顺序表 若将表示稀疏矩阵的三元组按行优先（或列优先）的顺

12、序排列，则可得到一个结点均是三元组的线性表即三元组表，若以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方式，称为三元组顺序表。如图5.7所示为三元组以行为主序优先顺序存储的A稀疏矩阵所对应的三元组表。其类型定义为：#define MAXSIZE 999/*非零元素个数的最大值设为1000*/typedef struct int i，j；/*非零元素的行，列下标*/datatype v；/*元素值*/node；typedef struct int mu，nu，tu；/*行，列数，非零元素个数*/node dataMAXSIZE；/*三元组表*/matrix/*稀疏矩阵类型*/mat

13、rix*a；,图5.7 稀疏矩阵A所对应的三元组表a-data,（1）矩阵的转置 一个m n的稀疏矩阵A，它的转置矩阵B仍是稀疏矩阵，且为n m的矩阵，同时有Aij=Bji成立（0im-1，0jn-1），即B的行是A的列，B的列是A的行，如图5.8所示，A，B两矩阵互为转置。假设A和B矩阵分别用matrix型指针变量a和b表示，矩阵的转置可以按以下进行：由于的行是的列，所以可按照b-data三元组表的次序在a-data中找到相应的三元组进行转置，即可按a-data的列序转置，所得到的转置矩阵的三元组表b-data必定是按行优先存放的。因此，可以对三元组表a-data从第一行起扫描，找到的每一列

14、中所有的非零元素，就可以实现转置。算法描述如下：,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-tu0）bn=0；for(col=0；colnu；col+)/*按*a的列序转置*for(am=0；amtu；am+)/*扫描整个三元组表*if(a-data am.j=col)/*列号为col时转置*b-data bn.i=a-data am

15、.j；/*行、列交换*/b-data bn.j=a-data am.i；b-data bn.v=a-data am.v；bn+；/*b-data中的结点序号加1*return b;/*返回转置矩阵的指针*/*transmatrix*/以上算法的时间复杂度为（tunu）。一般的，上述转置算法只适用于当tumu nu的情况。,0im1-1，0jn2-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=ci j+ai k*bk j；,（2）矩阵的乘法 设矩阵m1n1与mn，当n1m时，可得矩阵相乘为：m

16、1xn2=Am1n1 Bm2n1 由矩阵乘法的定义得：,该算法的时间复杂度为（m1n1n2）。,要求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-dat

17、a是以行为主序存放非零元素的三元组，若能预先确定矩阵B中每一行的第一个非零元素在b-data中应有的位置，就可以顺序存取b-data中第k行的所有非零元素。显然，应先求出B中的每一行中非零元素个数之后才可确定这些位置。为此，可用一个数组numm2-1存储每一行中非零元素的个数，用另一个数组rposm2-1存储每一个非零元素在b-data中所在的位置，从而应有以下式子成立。rpos 0=0 rpos row=rpos row-1+num row-1(1rowm2-1),例如，B矩阵其rpos数组的值可用下表表示：,由于rposrow表示B的第row行中第一个非零元素在b-data中的序号，所以r

18、posrow+1-1表示第row行中最后一个非零元素在b-data中的序号。显然，最后一行中最后一个非零元素在b-data中的位置就是rposm21（此时b.mu=m2），且有rposm2=rposm2-1+numm21。从而可以得到稀疏矩阵相乘的具体做法：对于A中的每个元素a-datap（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的乘积，作为乘积矩阵累加和项ci j中的一部分。可以对每个元素设一个累计和的变量，初始时置各变量为零，然后扫描三元组表a-data，求得相应元

19、素的乘积并累加到累计和的变量上。乘积矩阵中的各元素只有在求得累加和后才可确定是否为零，由于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 tu；crow+)numcrow=0；/*数组初始化*for(t=0；t tu；t+)numb-data t.i=nu

20、mb-data t.i+1；/*求B的每一行非零元素个数*rpos0=0；for(crow=1；crowmu；crow+)rposcrow=rposcrow-1+numcrow-1；/*求一维数组rposb-mu的值*c=(matrix*)malloc(sizeof(matrix)；c-mu=a-mu；c-nu=b-nu；c-tu=0；p=0；/*初始化*,do crow=a-datap.i；/*crow指示当前处理的行号*for(k=0；knu-1；k+)ctemp k=0；/*初始化累加器*while(p tu)&(a-data p.i=crow)brow=a-data p.j；/*bro

21、w表示b-dataq在B中的行号*for(q=rposbrow；qdata q.j；/*k指示乘积元素在c中行号*ctempk=ctempk+a-datap.vb-dataq.v；p+；for(k=0；knu-1；k+)if(ctempk!=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.十字链表 对于矩阵的一些运算如矩阵加法等运算非零元素的位置和个数经常发生变化，就不宜采用三元组表，此时采用链式存储结构来表示三元组方便一些。我们

22、一般采用一种称之为十字链表的链接存储结构，其基本做法就是在链表中，每个非零元素结点中除了表示非零元素的三元组(i，j，v)外，还增加了两个链域：向下域（down）和向右域（right），其中向下域用于链接同一列中的非零元素，向右域（right）用于链接同一行中的非零元素，如图5.10（a）的结点格式。,图5.10 十字链表非零元素结点格式,利用这种结构形式的结点就可将稀疏矩阵中同一行的非零元素通过向右域right链接成一个带表头结点的链表，称之为行链表；而同一列中的非零元素也可以通过向下域down链接成一个带表头结点的链表，称之为列链表。这样，对于稀疏矩阵的每一个非零元素aij，它既是第i行链

23、表上的一个结点，又是第j列链表上的结点，好比处在一个十字交叉路口上，故称为十字链表。为了便于运算，在每一个行链表和列链表上增加一个表头结点（结点结构如图5.10（b）所示），而非零元素结点称之为表结点，而且可将表头结点的行、列域置为零，所有的行、列链表和它的头结点一起链成一个单循环链表，而且第i行链表和第列链表可共享同一个表头结点。由于表头结点中值域不用，所以可将其作为指针域next，用于存放指向下一个表头结点的指针，这样，通过该指针域就可以将所有的表头结点链接，最后，再加上一个附加的表头结点（表头结点由五个域i、j、next、down、right组成）由指针hm指示，组成一个带表头结点的循环

24、链表，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行

25、链表和第j列链表的正确位置上，其具体算法可描述如下：,crosslink*creatcrosslink（）/*返回稀疏矩阵的十字链表头指针*/crosslink*p，*q，*hm，*cpMAXSIZE；int i，j，k，m，n，t，s；datatype v；scanf(“%d%d%d”，&m，&n，&t)；/*输入行、列数，非零元素个数*/if(mn)s=m；else s=n；/*确定表头结点个数s=max（m，n）*/hm=(crosslink*)malloc(sizeof(crosslink)；/*建立十字链表头结点*h*/hm-i=m；hm-j=n；cp0=hm；/*cp是指针数组，分

26、别指向头结点和行、列表头结点*/for(i=1；ii=0；p-j=0；p-right=p；p-down=p；cpi=p；cpi-1-val.next=p；cps-val.next=hm；,for(k=1；ki=i；/*输入一个非零表结点*p*/p-j=j；p-val.v=v；q=cpi；/*取第i行表头结点*/while(q-right!=cpi)&(q-right-jright；/*在第i行找第一个列号大于j的结点*/p-right=q-right；q-right=p；/*p插在*q之后*/q=cp j；/*取第j列表头结点*/while(q-down!=cpj)&(q-down-i dow

27、n；/*在第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）；或者是零元素。然后根据不同的情况分别作相应处理。其算法

28、如下：首先定义一个插入函数：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结点链接在行表中*/cpccol-next-down=s；cpccol-next=s；/*将s结点链接到列表中*/*insert*/,矩阵相加运算的算法如下：crosslink*matrixadd（a，b，c，cp）crosslink*a，*b，*c，*cp；i

29、nt 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-i else n=a-j；cp0=c；for(i=1；ii=0；s-j=0；s-right=s；s-down=s；cpi=s；,arow=a-next；brow=b-next；/*读入A，B的初始行*/last=cp0；/*last置初值*/i=0；while(arrow!=a)&(brow!=b)/*读A，B矩

30、阵*/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/*分别取当前行的下一个结点*/else if(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-rig

31、ht；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=cpi；i+；last=cpi；/*开始下一行*/arrow=arow-next；brow=brow-next；for(i=1；ij；i+)/*关闭全部列表*/cpi-next-down=cpi；for(i=1；inext=cpi+1；if(n=0)c-next=c；else

32、 cpn-next=c；c-next=cp1;；/*matriadd*/,5.4 广义表,5.4.1 广义表的定义 广义表简称表，它是线性表的推广。一个广义表是n个（n0）元素的一个序列。当n=0时称为空表；在一个非空的广义表中，其元素可以是单元素；也可以是广义表。广义表是一种递归的数据结构。通常记广义表Ls=（a1，a2，an），其中n为广义表的长度，n0。若ai是广义表，则称它为Ls的子表。如()为一个空表，其长度为；(，)为一长度为的广义表，它有两个元素；(a，(b，c，d)C 为一长度为的广义表；E=(b，E)=(b，(b，(b，()E为一个长度为的广义表。对于Ls=（a1，a2，an

33、），若其非空，n，则a1称为Ls的表头，而其余元素组成的表（a2，an）称为Ls的表尾。广义表可以利用图形简单进行表示，如图5.12。,5.4.2 广义表的存储结构 广义表中的数据元素可以具有不同的数据结构，因此很难为每个广义表分配固定大小的存储空间，所以采用动态链接结构，每个数据元素可用一个结点表示。一个广义表中的数据元素可以是单元素，也可以是子表的特点，相应地在对应的链接存储结构中的结点也有单元素结点和子表之分。这样，单元素结点应包括值域和指向其后继结点的指针域，而对于子表结点，应包括指向子表中第一个结点的表头指针和指向其后继结点的指针域。其结点结构可为：,1 结点为单元素atom=0 结

34、点为子表,第二个域是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可作为标志域，用于区分单元素还是子表，其取值如下：,一些常见广义表的存储结构如图5.13所示。,有时也可采用双链表表示

35、法，该方法中每个结点结构为：,其中next1用于指向该结点的子表，next2用于指向该结点的同层中的直接后继结点。当next1非空时，表明该结点是子表结点，此时next1为指向该子表中第一个结点的指针；data域用于存放单元素信息或子表的名字，类型定义如下：typedef struct dbnode datatype data;struct dbnode*next1，*next2；dblists；双链表示法如下图5.14所示：,5.4.3 广义表的运算 广义表的运算主要有求广义表的长度和深度、向广义表插入元素和从广义表中查找、删除元素以及建立广义表的存储结构等，由于广义表是一种递归的数据结构，

36、因此对于广义表的运算一般采用递归进行。一般将广义表的深度定义为表中括号嵌套的最大的层数或者是广义表中的括弧的重数，它是广义表的一种度量。利用递归的定义，广义表的深度等于所有子表中表的最大的深度加1。可设dep表示广义表的深度，max表示所有子表中表的最大深度，则应有depth=max+1。递归算法如下：,int depth（slists*ls）/*求广义表ls的深度*int max，dep；max=0；/*给max赋初值*/while(ls!=NULL)if(ls-atom=1)dep=depth(ls-snext)；/*递归求出子表的深度*/if(dep max)max=dep；ls=ls-

37、next；/*使ls指向同一层下一个结点（即后继结点）*/return max+l；/*非空表的深度是各元素的深度最大值加1*/*depth*/,例，三元多项式 P(x，y，z)=6 x9 y3 z2+8 x6 y3 z2+3 x5 y2 z2+4 x4 y4 z+5 x3 y4 z+y z+10 可以写作：P(x，y，z)=(6 x9 y3+8 x6 y3+3 x5 y2)z2+(4 x4 y4+5 x3 y4+y)z+10 显然，上式可以看作是变元Z的多项式：A Z2+B Z+1 其中，A=6 x9 y3+8 x6 y3+3 x5 y2；B=4 x4 y4+5 x3 y4+y 上式也可以写

38、作：P(x，y，z)=(6 x9+8 x6)y3+3 x5 y2)z2+(4 x4+5 x3)y4+y)z+10 此时，又可将A Z2+B Z+10中的A、B看作是y的多项式，依此下去，可知每个多项式都可看作是一个变量加上若干个系数指数的有序对组成。,5.5 m元多项式的表示,显然，对于任何一个m元多项式，都可先分配出一个主变元，然后再分解出第二个变元等等。由此可见，一个m元多项式，首先应是它的主变元的多项式，而其系数又是第二个变元的多项式，由此可用广义表来表示m元多项式。如上述中的三元多项式可用下式广义表来表示。P=Z(A，2)，(B，1)，(10，0)其中，A=y(C，3)，(D，2)B=

39、y(E，4)，(F，1)C=x(6，9)，(8，6)D=x(3，5)E=x(4，4)，(5，3)F=x(1，0)从而可以类似于广义表的第二种存储结构来定义m元多项式的广义表存储结构。结点结构如图5.15所示。,图5.15 链表的结点结构,其类型可说明如下：typedef struct mulnode elemint atom；/*标志域，区分单元素和表结点*/int exp;/*指数域*/union float coef；/*系数域*/struct mulnode*hp;/*表结点的表头指针*/；struct mulnode*tp；/*指向下一个元素结点的指针*/*mullists 上述例子中三元多项式的广义表存储结构示意图如图5.16所示。,图5.16 三元多项式的存储结构示意图,