栈和队列实践&多项式加法与乘法

本次来记录栈和队列进行实战，即来编写多项式的加法与乘法，首先我们先把题目列出来。P1067 [NOIP 2009 普及组] 多项式输出 – 洛谷。为了方便大家阅读，我把题目copy过来。

对于多项式而言，他分为系数和指数两个部分，我们的主要思路就是：相同指数的项系数相加，其余部分进行copy。

对此我们就可以构建两个单向链表，采用不带头结点的单向链表，按照指数递减的顺序排列各项。

对应的代码是：

struct PolyNode {
int coef; // 系数
int expon; // 指数
struct PolyNode *link; // 指向下一个节点的指针
};
typedef struct PolyNode *Polynomial;
Polynomial P1, P2;

先创建了结点，PolyNode，然后创建了链表类型也就是Polynomial。然后我们通过让Polynomial P1, P2;就可以创建出来两个链表了。

之后我们就可以考虑这个该怎么相加了，根据多项式相加规则，只有指数相同才可以相加，那么就是： P1->expon==P2->expon: 系数相加，若结果不为0，则作为结果多项式对应项的系数。同时，P1和P2都分别指向下一项； P1->expon>P2->expon: 将P1的当前项存入结果多项式，并使P1指向下一项； P1->expon<P2->expon: 将P2的当前项存入结果多项式，并使P2指向下一项； 当某一多项式处理完时，将另一个多项式的所有节点依次复制到结果多项式中去。 具体图解如图所示：

接下来我们就开始编写代码：

/* 多项式加法：将 P1 和 P2 相加，结果存入新链表并返回 */
Polynomial PolyAdd(Polynomial P1, Polynomial P2) {
Polynomial front, rear, temp;
int sum;

// 1. 初始化：创建一个临时的头结点，rear 指向当前结果链表的尾巴
rear = (Polynomial)malloc(sizeof(struct PolyNode));
front = rear; // front 记录头结点，最后用来释放

// 2. 双指针赛跑：当 P1 和 P2 都有项待处理时
while (P1 && P2) {
// Compare 函数返回：1 (P1指数大), -1 (P2指数大), 0 (指数相等)
switch (Compare(P1->expon, P2->expon)) {
case 1: // P1 指数大，把 P1 这一项接到结果后面
Attach(P1->coef, P1->expon, &rear);
P1 = P1->link;
break;
case -1: // P2 指数大，把 P2 这一项接到结果后面
Attach(P2->coef, P2->expon, &rear);
P2 = P2->link;
break;
case 0: // 指数相等
sum = P1->coef + P2->coef;
if (sum) Attach(sum, P1->expon, &rear); // 系数和不为0才插入
P1 = P1->link;
P2 = P2->link;
break;
}
}

// 3. 处理收尾：将未处理完的另一个多项式直接接在后面
for (; P1; P1 = P1->link) Attach(P1->coef, P1->expon, &rear);
for (; P2; P2 = P2->link) Attach(P2->coef, P2->expon, &rear);

// 4. 收尾工作
rear->link = NULL; // 封死队尾
temp = front; // 暂存头结点
front = front->link; // 令 front 指向真正的第一个非零项
free(temp); // 释放掉多余的临时头结点

return front;
}
/* 将系数c和指数e组成的新项接在 pRear 指向的节点后面 */
void Attach( int c, int e, Polynomial *pRear )
{
Polynomial P;

// 1. 盖新房：申请一个新节点的内存空间
P = (Polynomial)malloc(sizeof(struct PolyNode));

// 2. 装货：把系数和指数存进新节点
P->coef = c;
P->expon = e;

// 3. 封路：新节点暂时是最后一个，所以它的 link 指向 NULL
P->link = NULL;

// 4. 接轨：让当前链表的老尾巴（*pRear）伸出手，指向这个新节点 P
(*pRear)->link = P;

// 5. 挪位：更新尾指针，让它指向刚刚接好的新节点 P，准备下一次接客
*pRear = P;
}

我们开始对这段代码进行解读：我们看第一部分 1.初始化中，这一步是在创建rear和front两个指针指向的位置，我们先造一个头结点放在起点，因为一开始rear=front，所以front就像个图钉一样定住不动，rear像搬运工，负责往后接新的结点。 2.就是在进行对比，先是一个while循环，循环条件是P1和P2得有一个是有数的。然后我们进入switch中，switch的条件是，compare这两个的指数哪个大。然后进入了Attach部分

Attach部分算是核心了，对于Attach来说我们需要传入三个内容，1.XX的coef（系数）2.XX的expon（指数），还有我们的链表地址也就是&rear。

对于case=1或-1我们先进行讲解，如果是其中一项的指数大，那么就把这一项和他的系数都放到我们的链表后面，这时候我们就需要先创建一个新的结点，P。然后按规定申请空间，然后进行赋值，最后再把他的后继也就是P->link = NULL;然后再把之前的和这个新节点链接(*pRear)->link = P;最后是更新位置*pRear = P;

最后讲一下如果P1，P2的指数相等怎么办？那么这时候就需要先算一下他们的系数是不是为0，也就是sum = P1->coef + P2->coef;和if (sum)。只有if (sum)！=0的时候，我们才会进行Attach(sum, P1->expon, &rear);，由于系数一样啊，于是这个填P1->expon还是P2->expon都无所谓的。最后再把他们P1和P2的值双双往后移，P1 = P1->link; P2 = P2->link;当然前边每做完一个都会把这一个的往后移动。做完这些，我们就再把未处理完的另一个多项式的所有节点依次复制到结果多项式中去，就是那两个for循环。最后再把这个尾部rear封好，指向NULL，然后再把之前没东西的空的头结点删除，但是在删除之前就先把这个front指向头结点的的LINK，然后再把它free了就可以了。

多项式相乘：

// 核心函数：多项式相乘
Polynomial Mult(Polynomial P1, Polynomial P2) {
Polynomial P, t1, t2, Rear, temp;
int c, e;

if (!P1 || !P2) return NULL; // 有一个为空，结果就是空

t1 = P1; t2 = P2;
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->link = NULL;
Rear = P;

// 第一步：先拿 P1 的第 1 项乘以 P2 的所有项，建立初始结果链表
// 这一步是为了给后面的插入打个“底”
while (t2) {
Attach(t1->coef * t2->coef, t1->expon + t2->expon, &Rear);
t2 = t2->link;
}
t1 = t1->link; // P1 第一项处理完了，跳到第二项

多项式相乘的代码有点长，我们一点一点讲，先讲这一段，这一段就是最基础的创建链表这一块，然后我们先把P1的第一项去乘以P2的每一项，先把链表填进去一些值，也为后续插入做好基础。

// 第二步：嵌套循环，处理 P1 剩下的每一项乘以 P2 的每一项
while (t1) {
t2 = P2;
Rear = P; // 每次新一轮乘法，Rear 都要回到结果链表的头，准备寻找插入位置
while (t2) {
e = t1->expon + t2->expon; // 新的指数
c = t1->coef * t2->coef; // 新的系数

// 【关键插入逻辑】：找位置！
// 只要结果链表的下一项指数比当前新项指数大，Rear 就一直往后走
while (Rear->link && Rear->link->expon > e)
Rear = Rear->link;

// 情况1：指数相等，合并系数
if (Rear->link && Rear->link->expon == e) {
if (Rear->link->coef + c != 0) {
Rear->link->coef += c; // 相加不为0，直接更新
} else {
// 相加为0，删除这个节点
temp = Rear->link;
Rear->link = temp->link;
free(temp);
}
}
// 情况2：指数更小，说明新项应该插在 Rear 和 Rear->link 之间
else {
temp = (Polynomial)malloc(sizeof(struct PolyNode));
temp->coef = c;
temp->expon = e;
temp->link = Rear->link;
Rear->link = temp; // 插入新房
Rear = Rear->link; // Rear 移动到新节点，继续下一次相乘
}
t2 = t2->link;
}
t1 = t1->link;
}

这一部分就是最主要的代码了，首先就是两个while循环的嵌套，最外边是更新t1的值，里边是更新t2的值，在里边的时候我们要更新指数和系数的值。e = t1->expon + t2->expon;  c = t1->coef * t2->coef；在后面的判断条件里有Rear->link && Rear->link->expon这个有同学可能会问，那我们直接看结点的expon不行吗？为啥还要有前边这个Rear->Link？目的是为了确保这个确实存在，而不是NULL。然后后边的情况1就是指数相等的情况下我们要合并系数，然后如果我们系数相加=0的话，那么就代表说这个结点得=0，所以就需要创立一个临时节点去接收这个Rear->Link的结点，然后最后把他free了。

后面就是如果指数小的话，俺么就代表他应该插入在Rear 和 Rear->link 之间，所以后边的else就是先创建一个临时的结点，然后再把它插入进主链表里。最后我们再把这个临时结点free了就好了！，于是多项式的乘法就结束了。接下来就是最简单的多项式的输入和输出了，这块直接给代码了好吧

多项式输入：

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;
}

多项式输出：

void PrintPoly(Polynomial P) {
int flag = 0; // 用来控制空格：第一项前面不加空格，后面每项前面加空格

if (!P) { // 如果链表是空的，代表是0多项式
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");
}

附完整代码：https://github.com/luchenming727-hash/ZJU-Data-Structure-class.git