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

本次来记录栈和队列进行实战即来编写多项式的加法与乘法首先我们先把题目列出来。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-exponP2-expon: 系数相加若结果不为0则作为结果多项式对应项的系数。同时P1和P2都分别指向下一项P1-exponP2-expon: 将P1的当前项存入结果多项式并使P1指向下一项P1-exponP2-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两个指针指向的位置我们先造一个头结点放在起点因为一开始rearfront所以front就像个图钉一样定住不动rear像搬运工负责往后接新的结点。2.就是在进行对比先是一个while循环循环条件是P1和P2得有一个是有数的。然后我们进入switch中switch的条件是compare这两个的指数哪个大。然后进入了Attach部分Attach部分算是核心了对于Attach来说我们需要传入三个内容1.XX的coef系数2.XX的expon指数还有我们的链表地址也就是rear。对于case1或-1我们先进行讲解如果是其中一项的指数大那么就把这一项和他的系数都放到我们的链表后面这时候我们就需要先创建一个新的结点P。然后按规定申请空间然后进行赋值最后再把他的后继也就是P-link NULL;然后再把之前的和这个新节点链接(*pRear)-link P;最后是更新位置*pRear P;最后讲一下如果P1P2的指数相等怎么办那么这时候就需要先算一下他们的系数是不是为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