2.5 线性表的应用举例
本节通过对一元多项式加法求解问题的分析与设计，进一步熟悉线性表的存储方式、运算实现技术等内容的应用。
【例2-10】已知两个一元多项式a（x）和b（x），要求设计算法实现两个一元多项式a（x）和b（x）的加法运算a（x）=a（x）+b（x）。
【问题分析】在数学中，符号多项式就是形如axe的项之和，其中a为系数，e为指数。换句话说，一个一元多项式可按升幂的形式写为
它由n+1个系数唯一确定。因此，在计算机里，可用一个线性表A来表示：
每一项的指数隐含在其系数所在的位序号里。
假设Bm（x）是一个一元m次多项式，同样可用线性表B来表示：
若m＜n，则Sn（x）=An（x）+Bm（x）也可以用线性表S来表示：
显然，可以在计算机内部对A，B和S采用顺序存储结构，从而使多项式的加法运算变得简单。但是在实际应用中，多项式的阶数可能很高，且相邻项之间的阶数相差很大。例如P（x）=8+4x1002-3x20003，这样的多项式若按照上述顺序存储方式，则需要用一长度为20004的线性表来表示，且表中仅有3项是非零元素，从而会造成大量的存储空间浪费。为避免这种情况，我们自然会想到只存储非零项，且在存储非零项系数时同时存储非零项的指数。在一般情况下，一元多项式可写为
其中：pi是指数为ei的项的非零系数，满足条件0≤e1＜e2＜…＜em=n。一元多项式可用以下线性表来表述：
虽然，对于一个非零项来说，其占用存储空间量比只存储系数要大，但对于P（x）类的多项式则大大地节省了存储空间。但究竟是选择顺序存储还是链式存储呢？这就要看多项式要做何种运算而定。因为多项式的加法运算规则是：两个多项式中所有指数相同的项对应的系数相加，若和不为零，则构成“和多项式”中的一项，而所有指数不相同的那些项均复制到“和多项式”中。由于求解结果中多项式的项数是无法预知的，且从提高空间利用率方面考虑，显然应采用链式存储结构。多项式的链式存储结构中的每一个系数非零项对应一个结点，每个结点的结构如图2-29所示。结点包含有三个域：其中coef数据域用来存放非零项的系数，expn数据域用来存放非零项的指数，而next指针域用来存放下一个非零项的结点地址。
图2-29 多项式链表的结点结构
C0 2-5-1
多项式的链表结点类型定义：
typedef struct PolyNode{ //项的表示
float coef； //系数
int expn； //指数
struct PolyNode *next；
}PolyNode，*PolyNomial；
下面用带头结点的有序单链表来实现一元多项式的存储。例如：对于两个一元多项式a（x）=2+3x+5x3+2x4-7x9，b（x）=1-3x+4x2+7x3，它们的链式存储结构如图2-30所示。
图2-30 两个多项式的链式存储结构
两个多项式相加的结果可用图2-31来描述，其中有“×”标志的结点是相加后被删除的结点。
图2-31 两个多项式相加后的结果
多项式相加运算的实现方法类似于例2-8中对两个有序单链表的合并方法。在运算过程中需引进三个工作指针：p，q和r。其中p，q分别指向两个多项式链中待比较的结点，其初始分别指向两个链表的首结点，r始终指向“和多项式”的当前尾结点。
【算法2-29】例2-10中一元多项式加法运算的设计算法
C0 2-5-2
Status PolyAdd（PolyNomial&La，PolyNomial Lb）
// 求多项式加法La=La+Lb：利用两个多项式的结点构成“和多项式”，并用La返回结果
{ float sum；
PolyNomial r=La； //r用于指向新形成链表的尾结点r
PolyNomial p=La-＞next； //p指向La的第一个结点
PolyNomial q=Lb-＞next； //q指向La的第一个结点
PolyNomial temp；
while（p&&q）
{ if（p-＞expn＜q-＞expn） //p的指数小于q的指数
{ r-＞next=p； //p加入和多项式的尾部
r=p； //r指向当前和多项式的尾结点
p=p-＞next； //p后移
}
else if（p-＞expn＞q-＞expn）//q的指数小于p的指数
{ r-＞next=q； //q加入和多项式的尾部
r=q； //r指向当前和多项式的尾结点
q=q-＞next； //q后移
}
else //指数相等
{ sum=p-＞coef+q-＞coef；
if（sum!=0）
{ p-＞coef=sum； //和写入p的系数域
r-＞next=p； //p加入和多项式的尾部
r=p； //r指向当前和多项式的尾结点
p=p-＞next； //p后移
temp=q； //q为待删除的结点
q=q-＞next； //q后移
free（temp）； //删除q
}
else //和为零，p与q都删除，且实现p，q都后移
{ temp=p-＞next；
free（p）；
p=temp；
temp=q-＞next；
free（q）；
q=temp；
}
}
}//while
r-＞next=（p!=NULL）? p：q； //将La或Lb中剩余的结点链接到和多项式的尾部
free（Lb）； //释放Lb的头结点
return OK；
}//算法2-29 结束
此算法的时间复杂度为O（ListLength（La）+ListLength（Lb））。
【综合应用思考】分别采用顺序存储和链式存储，完成学生成绩管理系统的设计与实现。该系统应至少具有增、删、查、改的功能。学生成绩表的结构如表2-3所示。
表2-3 学生成绩表
【提示】由表2-3可知，表中的数据元素是由学号、姓名、性别、大学英语和高等数学等5个数据项所构成的，所以可将数据元素类型具体定义为
typedef struct{
int number； //学号
char name[10]； //姓名
char sex； //性别（W/M）
float english； //大学英语
float math； //高等数学
}ElemType；
成绩表采用何种存储结构，它的基本操作的实现方法就与前面讨论过的对应存储结构上基本操作的实现方法相同，只不过现在将前面的数据元素类型具体化为一个学生的成绩记录。