小白 【详解】C语言 多项式加减法 数据结构：单链表
最近学习了链表，老师布置的大作业，开始也不清楚从哪里入手，想着在网上找到一些解析，发现网上没有适合一个小白的对于多项式加减法的详细的解析，刚刚写出了多项式加减法，于是想着尝试一下写一篇csdn的帖子，本文主要讲解其中的代码的以及思路，希望也可以和小伙伴们沟通交流，并且如果有问题，希望可以指出。
问题描述：
给定两个多项式，求解其和与差。多项式的项数为M，而最高幂次为N。（1<=M<=10，1<=N<=1000000）
输入说明
输入包含了两个多项式，分为两行给出（同行数据间以空格隔开）：
每一行为两组数据：第一组为一个值，表示多项式的非零项数M；第二组为2*M个值，每相邻两个值表达一个多项式的非零系数项，分别为系数值、幂次值（其中各项按照幂次的降序排列）。但如果多项式没有非零系数项，则仅用0（M的值）表示，后面没有系数和幂次值出现。例如，第一行的数据为：4 1 10 2 5 3 4 4 0，那么表示多项式有4项，对应的多项式为：x10+2x5+3x^4+4. 又例如，第二行的数据为：4 1 8 -2 5 3 3 4 1，表示多项式有4项，对应的多项式为：x8-2x5+3x^3+4x。那么上述两个多项式相加的输出结果应为：6 1 10 1 8 3 4 3 3 4 1 4 0，对应的多项式为：x10+x8+3x4+3x3+4x+4.第一个多项式减去第二个多项式的输出结果为：7 1 10 -1 8 4 5 3 4 -3 3 -4 1 4 0，对应多项式：x10-x8+4x5+3x4-3x^3-4x+4.
输出说明
输出包含了两个多项式，分为两行给出（同行数据间以空格隔开）：
第一行是多项式相加的结果，第二行是多项式相减的结果。每一行为两组数据：第一组为一个值，表示多项式的非零项数M；第二组为2*M个值，每相邻两个值表达一个多项式的非零系数项，分别为系数值、幂次值（其中各项按照幂次的降序排列）。但如果多项式没有非零系数项，则仅用0（M的值）表示，后面没有系数和幂次值出现。
输入样例
例1：
4 1 10 2 5 3 4 4 0
4 1 8 -2 5 3 3 4 1
输出样例
例1：
6 1 10 1 8 3 4 3 3 4 1 4 0
7 1 10 -1 8 4 5 3 4 -3 3 -4 1 4 0
知识储备：
这道题目想要考察的是链表的知识，这个是本题目的数据结构了，这个大家可以搜索一下数据结构链表的知识，比较容易找到相关的链接知识。
首先，我们要有指针的基础，在构造链表的小节点的时候，其中就有出现指针，想必有一些同学应该和我一样，在大一的时候学c语言，并没有对指针有比较深入的理解，刚上手还是有一些蒙圈，找来找去，在这里推荐一个链接，认为写的非常好，很透
https://www.cnblogs.com/tongye/p/9650573.html
这里面写的指针是一种保存变量地址的变量，我感觉有一种豁然开朗的感觉，如果还是感觉不太清楚的话，我感觉可以搜一些简单的指针描述，然后再看这篇文章。
然后，还有关于typedef的描述，我认为他就是在为自己规定的一中数据类型进行了命名，例如int，其实就是C语言中的一种数据类型，他表示整数型，并且有一定的范围，这就是对于一种数据类型的定义。typedef也是如此。
其中还有一些没遇见过的函数，例如malloc函数，free函数， 分配所需的内存空间，并返回一个指向它的指针。个人理解是结点都需要空间来存储里面的数据，所以需要给他分配内存，而在分配内存的后面，还需要为他返回指向这个地址的指针。后面也不要忘记free（），关于这些的更多描述，请见下面的链接。
https://zhuanlan.zhihu.com/p/105090421
大家可能也还会遇到一些其他的关于基础本的C语言的知识的问题，就像我一样，不过也没有关系，在网上可以找到一些资源，找一会，会找到自己认为最合适自己的知识储备的文章，分享的这几个链接自己搜索到的比较全面的文章，希望也可以帮到你。
想法与思路：
最近数据结构学习了链表，于是，使用链表对多项式进行一个描述，开始我以为链表在C语言里面就像是数组一样，直接就是一个表，后来发现，他是由一个一个得到结点构成的，而这一个一个的结点就，就是一个个的小结构体，其中包括了系数（coef），指数（exp），还有指向他的下一个结点的地址的指针。这个地方还是比较好理解的。
然后就是创建链表了，这里大家要注意一下，就是链表也是有不同的类型的，在最开始的时候，我是看到书上面的实例代码，以为这样一敲就ok了，其实并不是这样的，他是一个循环链表，个人感觉还是不太方便，有兴趣的同学可以试一试。
在这里我用的是单链表，顾名思义，就是单单的一条线形的链表，最符合一个小白对于链表的初始认知，（循环链表的话，就比较像一个圈了，就大致这个意思），一个头结点，head，然后中间几个比较相似的结点，然后最后就是以NULL结束了。
我认为这道题的基本创建的知识就ok了，下面我们来进行解题。
这个只讲一下大致的方式，具体的解释是写在代码的注释里面了
首先，创建多项式create（），将输入的多项式的系数和指数分别赋到一个变量上面，然后将值传到结点的数据上面。每一次完成，都要将结点向后面移动一位，直至循环结束，但还没有完，还差最后的一个结点，他为NULL。
还有记得，每一次循环的时候都要分配空间给结点，否则是不行的，数据没有地方进行存储。另外，记得对每一个所分配的空间都要进行free。我的方式是在最后有一个ployfree的函数，最后将所有的空间都释放。
然后多项式加法ployadd（ploynode *ploy1，ploynode *ploy2），这里我们输入进去两个多项式的头结点，注意：我们向函数里面输入的都是指向多项式的头结点的指针，之后我们是通过一个一个结点的后移来进行操作的（我想这个就是用c语言编链表的精华吧），然后就是我们最后想返回一个ploy1+ploy2的多项式，所以我们创建一个头结点，然后最后可以输出所多项式，然后就ok了，细节读一下代码就ok了。
之后**多项式减法ploysub(ploynode ploy1,ploynode ploy2) 这里我么就只需要在创建一个多项式ploy3，让他是负的ploy2，这里的ploy3的创建出来就已经比较像上面的相加的结果的多项式的创建过程了，最后只需要进行ployadd(ploy1,ploy3),就ok了。
下面*多项式所含的项数的个数ploysum(ploynode ploy)，输入一个多项式的头结点，然后对他进行循环，每循环一次，指向下一个结点，向着后面移动一位，直至为NULL结束，返回int类型的sum。
***多项式的输出printf(ploynode *ploy)****根据题目的要求，我们的输出形式是输出多项式的项的个数ploysum，然后输出多项式的coef和exp。
**之前分配给多项式的空间的free，freeploy(ploynode ploy)，这里我们对输入函数的多项式进行循环，然后再吧每一个结点都free（），然后就ok了。
这样我们的程序就ok了！
代码（讲在前面，请不要仅仅的只是抄袭，希望可以根据上文读懂代码，并自己敲一遍）：
输出的结果如图。
完整代码：
#include<stdio.h>
#include<stdlib.h>
typedef struct node {
int coef;//系数
int exp;//指数
struct node *next;//指向下一个结点的指针
} ploynode;//将上面的结构体node数据类型命名为ploynode
ploynode *create()//创建多项式 ，返回一个 ploynode类型的指针
{
ploynode *p,*q,*s;
ploynode *head=(ploynode*)malloc(sizeof(ploynode));//这个我们需要创建的多项式的头结点，要分配空间
// head->coef=0;
// head->exp=-1;
p=head;
int coef;
int exp;
int n;
printf("请输入所拥有的项数个数");
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d %d",&coef,&exp);
s=(ploynode*)malloc(sizeof(ploynode));
//这里我们用s来作为一个中间变量，为什么没有用p->next呢
//其实也是可以的不过开始这样看起开会简洁一些
//可以自己尝试
// p->next->coef=coef;
// p->next->exp=exp;
s->coef=coef;
s->exp=exp;
p->next=s;//让p的下一个指向的就是s指向的地址，我们的开始的p是head
p=p->next;//p后移一位
}
p->next=NULL;//最后不要忘记p的结尾为null
return head;
}
void freeploy(ploynode *ploy)//释放多项式的各个结点的所分配的内存
{
ploynode *p,*q;
p=ploy;
while (p!=NULL)
{
q=p->next;//先创建一个q防止free之后p变成了野指针，后面的next找不到，程序崩溃
free(p);
p=q;
}
}
int ploysum(ploynode *ploy)//计算多项式的项的个数
{
ploynode *p;
p=ploy->next;
int sum=0;
while(p!=NULL)
{
sum++;
p=p->next;
}
return sum;
}
void printf(ploynode *ploy)//输出多项式
{
printf("%d \n",ploysum(ploy));
ploynode *p;
p=ploy->next;
while(p)
{
printf("%d %d \n",p->coef,p->exp);
p=p->next;
}
printf("\n");
}
ploynode *ployadd(ploynode *ploy1,ploynode *ploy2)
{
ploynode *head=(ploynode *)malloc(sizeof(ploynode));//返回一个新的多项式头结点 的指针
ploynode *r,*p,*q,*s;
r=head;
p=ploy1->next;
q=ploy2->next;
while(p&&q)
{
//当p的指数大于q的指数时，直接将p‘复制’到r中
if(p->exp>q->exp)
{
s=(ploynode *)malloc(sizeof(ploynode));
s->exp=p->exp;
s->coef=p->coef;
r->next=s;
r=r->next;
p=p->next;//p走向下一个位置
}
//当p的指数小于于q的指数时
else if(p->exp<q->exp)
{
s=(ploynode *)malloc(sizeof(ploynode));
s->exp=q->exp;
s->coef=q->coef;
r->next=s;
r=r->next;
q=q->next; //q走向下一个位置
}
else//如果两者相等
{
s=(ploynode *)malloc(sizeof(ploynode));
s->exp=p->exp;
s->coef=p->coef+q->coef;//相加
if(s->coef!=0)
{
r->next=s;
r=r->next;
}
p=p->next;
q=q->next;
}
}
while(p)//如果p的项还剩一些
{
s=(ploynode *)malloc(sizeof(ploynode));
s->exp=p->exp;
s->coef=p->coef;
r->next=s;
r=r->next;
p=p->next;//p走向下一个位置
}
while(q)//如果q的项还剩一些
{
s=(ploynode *)malloc(sizeof(ploynode));
s->exp=q->exp;
s->coef=q->coef;
r->next=s;
r=r->next;
q=q->next; //q走向下一个位置
}
r->next=NULL;//r最后以null结尾
return head;
}
ploynode *ploysub(ploynode *ploy1,ploynode *ploy2)
{
ploynode *head=(ploynode *)malloc(sizeof(ploynode));
ploynode *r,*p,*q,*s,*ploy3;//创建那个新得到的相减的多项式
r=head;
q=ploy2->next;
while(q)
{
s=(ploynode *)malloc(sizeof(ploynode));
s->coef=-1*(q->coef);//将ploy2变成负的
s->exp=q->exp;
r->next=s;
r=r->next;
q=q->next;
}
r->next=NULL;
ploy3=ployadd(ploy1,head);//多项式相加
return ploy3;
}
int main()
{
ploynode *ploy1,*ploy2,*ployyy,*ployy;
ploy1=create(); //创建第一个多项式
ploy2=create(); //创建第二个多项式
ployyy=ployadd(ploy1,ploy2); //加法
printf(ployyy); //输出加法的多项式
ployy=ploysub(ploy1,ploy2); //减法
printf(ployy); //输出减法的多项式
freeploy(ploy1); //释放空间
freeploy(ploy2);
freeploy(ployy);
freeploy(ployyy);
}
完整代码，输出格式，其中还是有一些改变，以防止开放题目的答案对本人可能造成的不良影响。
希望你可以自己敲一遍，然后提交，并且如果我的代码哪里有问题，或者更优的解，欢迎交流指正。
写在最后：
这是小白的第一次写总结，其中可能有一些疏漏之处，但是个人认为，对于一位已经可以开始写这道题的同学，其中的知识点，以及代码中的注释，是比较详细的了。
星光不问赶路人，时光不负有心人。
加油！
参考：
https://bbs.csdn.net/topics/397798324
https://zhuanlan.zhihu.com/p/105090421
https://www.cnblogs.com/tongye/p/9650573.html