本系列文章为浙江大学陈越、何钦铭数据结构学习笔记，前面的系列文章链接如下：
数据结构基础：P1-基本概念
数据结构基础：P2.1-线性结构—＞线性表
数据结构基础：P2.2-线性结构—＞堆栈
数据结构基础：P2.3-线性结构—＞队列
数据结构基础：P2.4-应用实例—＞多项式加法运算
文章目录
一、题意理解与多项式表示
1.1 题意理解
题目：设计函数分别求两个一元多项式的乘积与和
(
1
)
3
x
4
−
5
x
2
+
6
x
−
2
(1)3{x^4} - 5{x^2} + 6x - 2
(1)3x4−5x2+6x−2
(
2
)
5
x
20
−
7
x
4
+
3
x
(2)5{x^{20}} - 7{x^4} + 3x
(2)5x20−7x4+3x
输入样例：首先输入多项式项数，然后依次输入各项系数与指数。
4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1
多项式①有4项，多项式②有3项。相加起来有7项，然后合并同类项后有5项，结果如下：
5
x
20
−
4
x
4
−
5
x
2
+
9
x
−
2
5{x^{20}} - 4{x^4} - 5{x^2} + 9x - 2
5x20−4x4−5x2+9x−2
多项式①有4项，多项式②有3项。相乘起来有12项，然后合并同类项后有项，结果如下：
15
x
24
−
25
x
22
+
30
x
21
−
10
x
20
−
21
x
8
+
35
x
6
−
33
x
5
+
14
x
4
−
15
x
3
+
18
x
2
−
6
x
{\rm{15}}{x^{24}}{\rm{ - 25}}{x^{22}}{\rm{ + 30}}{x^{21}}{\rm{ - 10}}{x^{20}}{\rm{ - 21}}{x^8}{\rm{ + 35}}{x^6}{\rm{ - 33}}{x^5}{\rm{ + 14}}{x^4}{\rm{ - 15}}{x^3}{\rm{ + 18}}{x^2}{\rm{ - 6}}x
15x24−25x22+30x21−10x20−21x8+35x6−33x5+14x4−15x3+18x2−6x
输出样例：按系数从大到小地输出多项式相乘的结果(第一行)和相加的结果(第二行)：
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0
1.2 多项式表示
我们的求解思路如下：
1. 多项式表示
2. 程序框架
3. 读多项式
4. 加法实现
5. 乘法实现
6. 多项式输出
多项式表示：
多项式的表示方法最核心的就是要表现多项式的关键信息：非零项的系数和指数。一对一对的这个信息要把它表示出来，这就是一个线性的序列。线性序列计算机上面有两种存储实现方式：数组、链表。
数组
数组的方法比较简单且调试也比较容易，但是数组来必须要事先确定数组的大小。当你这个多项式的项数事先不知道的时候，我们就只能以最大可能的项数来进行表示。实际上像素可能会没那么多，那就会造成空间的浪费。
链表
链表的方法正好克服了数组的缺点。它不需要事先知道有多少项，你来一个我给你处理一个，并把它作为一个结点插到这个链表里去。所以他的优点是动态性比较强，但是编的程序就会比较复杂，涉及到指针，调试也比较困难。
注：对于这道题来讲，有一种比较好的实现方法：动态数组。但为了训练大家的链表方面的编程能力，这里仍然用链表。
数据结构设计：
链表他是由若干个结点所构成的，结点的信息：系数、指数、指向下一个结点的指针。
typedef struct PolyNode *Polynomial;
struct PolyNode {
int coef;
int expon;
Polynomial link;
};
对于前面那两个多项式，我们用链表来表示，他们的结构如下图所示：
二、程序框架及读入多项式
2.1 程序框架
根据我们程序编程的这个要求，我们整个程序的框架大概如下。
int main()
{
读入多项式1
读入多项式2
乘法运算并输出
加法运算并输出
return 0;
}
我们希望设计一些函数来辅助我们整个程序的这个完成，那我们应该设计哪些函数呢？
需要设计的函数：
• 读一个多项式
• 两多项式相乘
• 两多项式相加
• 多项式输出
根据这样的一种想法，我们的main函数的主要过程是这样：
①首先我们定义几个变量，其中P1 P2分别代表这两个输入的多项式，所以我们通过ReadPoly来读入这两个多项式，返回了P1 P2的指针。
②然后将这两个指针传递到函数Mult里面去做乘法运算，乘法运算的结果也是一个链表，所以返回的是一个结构的指针。
③接下来要把这个多项式输出，所以只要把链表的头作为参数传到函数PrintPoly，由他来输出多项式。
④我们还要需要做加法运算，那就把P1 P2作为参数传进Add函数中去。
⑤加法运算之后返回的是一个新的多项式的节点的指针，我把这个和的多项式Print出来。
相应代码如下：
int main()
{
Polynomial P1, P2, PP, PS;
P1 = ReadPoly();
P2 = ReadPoly();
PP = Mult( P1, P2 );
PrintPoly( PP );
PS = Add( P1, P2 );
PrintPoly( PS );
return 0;
}
2.2 读入多项式
有了这个框架了之后，首先我们来看一下怎么读多项式，相应代码结构如下：
Polynomial ReadPoly()
{
……
scanf("%d", &N);
……
while ( N-- ) {
scanf("%d %d", &c, &e);
Attach(c, e, &Rear);
}
……
return P;
}
接着我们来详细分析一下其结构：
题目要求输入的数他的格式是这样的：
4 3 4 -5 2 6 1 -2 0
第一个整数是代表他有多少项，接下来是一对一对的系数指数。所以读多项式这个程序来讲，他应该是先读这个整数，接下来是一对一对的读入系数跟指数。所以我们整个这个程序框架如下：
①首先使用scanf把这个4读进来赋给变量N
②接下来做四轮的循环，那么就是while（N–）这种形式来控制循环的次数。
③然后每轮循环里面要做什么事情呢？就是系数指数读进来，分别放到c跟e里面去并由此构造一个结点，把这个节点插到多项式里面去。读的过程是从指数递降的顺序来进行读的，所以读入一个新的节点的时候，应该插在前面一个节点的后面。
所以，最后就形成我们所需要P1所指向的这样的一张链表：
在上面分析中有一些关键问题：
1、新的结点应该插到原来结果的后面，所以我们这里就需要有个指针Rear代表当前结果多项式的最后一项，使得我们后面构造的一个结点能找到最后一项并插在其后面。这个插入的过程就通过函数 Attach 来完成。在这个过程当中我们应该注意到，Rear原来是指向一个链表的最后。你插入了一个新结点之后，这个新的结点就成为这个链表的最后一项。所以Rear要指到新的结点上面去，那么也就意味着Rear这个变量在Attach这个函数里面必须要被改变，因此我们需要将Rear的地址传递进Attach函数。
2、我们说Rear是指向到结果多项指的最后一项，那么一开始的时候Rear值是什么呢？这里有两种处理方法
①Rear一开始都设为NULL，在Attach函数中根据Rear是否为NULL做不同处理
Rear是NULL的时候，说明是刚开始的第一个结点，这个时候就要申请这个结点，然后把Rear指向这个结点。如果Rear值不为NULL，那么我们就直接把这个新的结点插到Rear的后面。
②一开始我们构造一个空的结点，然后让Rear值指向这个空的结点，以后所有的新插入的结点全插在这个Rear后面。
如果是这样的一种进行处理，那么在Attach函数里面就不需要判别Rear是不是NULL。这是一种利用临时申请一个空的结点的方法，使得程序的处理起来一致性比较强，而且代码比较简单。当然，到了最后的时候你必须要把这个空结点删掉。
根据上面创建空结点的思路，Attach函数设计如下：
void Attach( int c, int e, Polynomial *pRear )
{
Polynomial P;
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->coef = c; /* 对新结点赋值 */
P->expon = e;
P->link = NULL;
(*pRear)->link = P;
*pRear = P; /* 修改pRear值 */
}
根据前面的这个分析，我们读入多项式的这个完整的程序就出来了：
Polynomial ReadPoly()
{
Polynomial P, Rear, t;
int c, e, N;
scanf("%d", &N);
P = (Polynomial)malloc(sizeof(struct PolyNode)); /* 链表头空结点 */
P->link = NULL;
Rear = P;
while ( N-- ) {
scanf("%d %d", &c, &e);
Attach(c, e, &Rear); /* 将当前项插入多项式尾部 */
}
t = P; P = P->link; free(t); /* 删除临时生成的头结点 */
return P;
}
三、加法、乘法运算及多项式输出
3.1 加法运算
多项式加法运算我们前面已经提过，具体步骤为：
①我们一开始可以用t1 t2分别指向这两个多项式。接下来为了处理方便，我们先构造一个空结点，可以把t1 t2的这些项插入到后面
②当t1 t2都不空的时候，使用一个while循环，比较当前t1 t2所指向的指数。指数相等就做系数相加，然后看看是不等于0，等于0就不管他了。如果不等于0，那就把新的这个系数和指数加到Rear后面。最后，t1 t2分别往后挪。如果t1 t2指向的指数不相等，那我们就比较一下看哪个大，把大的拷贝到Rear的后面。这个循环不断的做，只要这两个多项式都不空。
③当t1 t2有一个空的时候，循环就退出来了。退出来了之后要把另外一个可能还不空的全部接到Rear的后面。所以接下来分别要用两个while循环分别来处理 t1不空的情况跟t2不空的情况。然后最后返回多项式的头。
加法运算相应代码如下：
Polynomial Add(Polynomial P1, Polynomial P2)
{
Polynomial t1 = P1;
Polynomial t2 = P2;
Polynomial temp;
Polynomial P = (Polynomial)malloc(sizeof(struct PolyNode)); P->link = NULL;
Polynomial Rear = P;
int sum;
while (t1 && t2) {
if (t1->expon == t2->expon) {
sum = t1->coef + t2->coef; //记录这两项的系数
if (sum) Attach(sum, t1->expon, &Rear); //如果系数相加不为0，则接到rear后
t1 = t1->link; //P1 P2都往后挪
t2 = t2->link;
}
else if (t1->expon > t2->expon) {
Attach(t1->coef, t1->expon, &Rear);
t1 = t1->link;
}
else {
Attach(t2->coef, t2->expon, &Rear);
t2 = t2->link;
}
}
while (t1) {
Attach(t1->coef, t1->expon, &Rear);
t1 = t1->link;
}
while (t2) {
Attach(t2->coef, t2->expon, &Rear);
t2 = t2->link;
}
Rear->link = NULL;
temp = P;
P = P->link; /*令front指向结果多项式第一个非零项 */
free(temp); /* 释放临时空表头结点 */
return P;
}
3.2 乘法运算
两个多项式相乘有两种方法。
1、将乘法运算转换为加法运算
将乘法运算转换为加法运算，将P1当前项(ci,ei)乘P2多项式，然后把这些结果都加起来。
t1 = P1; t2 = P2;
P = (Polynomial)malloc(sizeof(struct PolyNode)); P->link = NULL;
Rear = P;
while (t2) {
Attach(t1->coef*t2->coef, t1->expon+t2->expon, &Rear);
t2 = t2->link;
}
2、逐项插入
将P1当前项
(
c
1
i
,
e
1
i
)
{\rm{(c}}{{\rm{1}}_{\rm{i}}}{\rm{,e}}{{\rm{1}}_{\rm{i}}}{\rm{)}}
(c1i,e1i)乘P2当前项
(
c
2
i
,
e
2
i
)
{\rm{(c}}{{\rm{2}}_{\rm{i}}}{\rm{,e}}{{\rm{2}}_{\rm{i}}}{\rm{)}}
(c2i,e2i)，并插入到结果多项式中。初始结果多项式可由P1第一项乘P2获得。接下来就是把P1的当前项跟P2当前项相乘，逐步的插到这里面去。具体代码如下所示：
Polynomial Mult(Polynomial P1, Polynomial P2)
{
Polynomial P, Rear, t1, t2, t;
int c, e;
if (!P1 || !P2) return NULL;
t1 = P1; t2 = P2;
P = (Polynomial)malloc(sizeof(struct PolyNode)); P->link = NULL;
Rear = P;
while (t2) { /* 先用P1的第1项乘以P2，得到P */
Attach(t1->coef*t2->coef, t1->expon + t2->expon, &Rear);
t2 = t2->link;
}
t1 = t1->link;
//两重循环，让t1的每一项乘t2的每一项
while (t1) {
t2 = P2; Rear = P;
while (t2) {
e = t1->expon + t2->expon; //指数相加，系数相乘
c = t1->coef * t2->coef;
while (Rear->link && Rear->link->expon > e) //当前系数较小，则Rear往后挪动
Rear = Rear->link;
if (Rear->link && Rear->link->expon == e) {//指数相等则系数相加
if (Rear->link->coef + c)
Rear->link->coef += c;
else { //系数相加等于0，将其删掉
t = Rear->link;
Rear->link = t->link;
free(t);
}
}
else { //指数不相等，要做插入操作
t = (Polynomial)malloc(sizeof(struct PolyNode));
t->coef = c; t->expon = e;
//开始插入
t->link = Rear->link;
Rear->link = t; Rear = Rear->link;
}
t2 = t2->link;
}
t1 = t1->link;
}
//删掉最开始的空结点，让返回的指针指向结果多项式的第一项
t2 = P; P = P->link; free(t2);
return P;
}
3.3 多项式输出
多项式输出实际上是一个链表的遍历问题，遍历链表的每一项，并输出对应系数和指数。
void PrintPoly(Polynomial P)
{ /* 输出多项式 */
int flag = 0; /* 辅助调整输出格式用 */
if (!P) { printf("0 0\n"); return; }
while (P) {
if (!flag)
flag = 1;
else
printf(" ");
printf("%d %d", P->coef, P->expon);
P = P->link;
}
printf("\n");
}
四、整体代码与测试结果
整体代码如下所示：
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
typedef struct PolyNode *Polynomial;
struct PolyNode {
int coef;
int expon;
Polynomial link;
};
void Attach(int c, int e, Polynomial *pRear);
Polynomial ReadPoly();
void PrintPoly(Polynomial P);
Polynomial Add(Polynomial P1, Polynomial P2);
Polynomial Mult(Polynomial P1, Polynomial P2);
int main()
{
Polynomial P1, P2, PP, PS;
P1 = ReadPoly();
P2 = ReadPoly();
PrintPoly(P1);
PrintPoly(P2);
PP = Mult(P1, P2);
printf("乘法结果为：");
PrintPoly(PP);
PS = Add(P1, P2);
printf("加法结果为：");
PrintPoly(PS);
return 0;
}
void Attach(int c, int e, Polynomial *pRear)
{
Polynomial P;
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->coef = c; /* 对新结点赋值 */
P->expon = e;
P->link = NULL;
(*pRear)->link = P;
*pRear = P; /* 修改pRear值 */
}
Polynomial ReadPoly()
{
Polynomial P, Rear, t;
int c, e, N;
printf("请输入多项式的项数：\n");
scanf("%d", &N);
P = (Polynomial)malloc(sizeof(struct PolyNode)); /* 链表头空结点 */
P->link = NULL;
Rear = P;
printf("请输入各项系数与指数：\n");
while (N--) {
scanf("%d %d", &c, &e);
Attach(c, e, &Rear); /* 将当前项插入多项式尾部 */
}
printf("\n");
t = P; P = P->link; free(t); /* 删除临时生成的头结点 */
return P;
}
Polynomial Add(Polynomial P1, Polynomial P2)
{
Polynomial t1 = P1;
Polynomial t2 = P2;
Polynomial temp;
Polynomial P = (Polynomial)malloc(sizeof(struct PolyNode)); P->link = NULL;
Polynomial Rear = P;
int sum;
while (t1 && t2) {
if (t1->expon == t2->expon) {
sum = t1->coef + t2->coef; //记录这两项的系数
if (sum) Attach(sum, t1->expon, &Rear); //如果系数相加不为0，则接到rear后
t1 = t1->link; //P1 P2都往后挪
t2 = t2->link;
}
else if (t1->expon > t2->expon) {
Attach(t1->coef, t1->expon, &Rear);
t1 = t1->link;
}
else {
Attach(t2->coef, t2->expon, &Rear);
t2 = t2->link;
}
}
while (t1) {
Attach(t1->coef, t1->expon, &Rear);
t1 = t1->link;
}
while (t2) {
Attach(t2->coef, t2->expon, &Rear);
t2 = t2->link;
}
Rear->link = NULL;
temp = P;
P = P->link; /*令front指向结果多项式第一个非零项 */
free(temp); /* 释放临时空表头结点 */
return P;
}
Polynomial Mult(Polynomial P1, Polynomial P2)
{
Polynomial P, Rear, t1, t2, t;
int c, e;
if (!P1 || !P2) return NULL;
t1 = P1; t2 = P2;
P = (Polynomial)malloc(sizeof(struct PolyNode)); P->link = NULL;
Rear = P;
while (t2) { /* 先用P1的第1项乘以P2，得到P */
Attach(t1->coef*t2->coef, t1->expon + t2->expon, &Rear);
t2 = t2->link;
}
t1 = t1->link;
while (t1) {
t2 = P2; Rear = P;
while (t2) {
e = t1->expon + t2->expon;
c = t1->coef * t2->coef;
while (Rear->link && Rear->link->expon > e)
Rear = Rear->link;
if (Rear->link && Rear->link->expon == e) {
if (Rear->link->coef + c)
Rear->link->coef += c;
else {
t = Rear->link;
Rear->link = t->link;
free(t);
}
}
else {
t = (Polynomial)malloc(sizeof(struct PolyNode));
t->coef = c; t->expon = e;
t->link = Rear->link;
Rear->link = t; Rear = Rear->link;
}
t2 = t2->link;
}
t1 = t1->link;
}
t2 = P; P = P->link; free(t2);
return P;
}
void PrintPoly(Polynomial P)
{ /* 输出多项式 */
int flag = 0; /* 辅助调整输出格式用 */
if (!P) { printf("0 0\n"); return; }
while (P) {
if (!flag)
flag = 1;
else
printf(" ");
printf("%d %d", P->coef, P->expon);
P = P->link;
}
printf("\n");
}
运行，输入题目中给的测试样例，结果正确：