一、题目

一元多项式的操作

设有两个一元多项式：

p(x)=p0+p1x+p2x2+···+pnxn

q(x)=q0+q1x+q2x2+···+qmxm

多项式项的系数为实数，指数为整数，设计实现一元多项式操作的程序：

① 多项式链表建立：以（系数，指数）方式输入项建立多项式，返回所建立的链表的头结点；

② 多项式排序：将所建立的多项式按指数非递减（从小到大）进行排序；

③ 多项式相加：实现两个多项式相加操作。操作生成一个新的多项式，原有的两个多项式不变，返回生成的多项式的头结点；

④ 多项式的输出；

⑤ 主函数通过调用多项式链表建立函数，输入两个多项式并分别输出；输出排序后的两个多项式；分别调用多项式相加函数实现多项式相加、相减操作，分别输出操作结果。

二、算法思想

定义多项式的结构体，包括两个数据域：系数、指数，一个指针域，保存下一个结点的地址。
尾插法建立多项式链表的函数：定义头指针和尾指针，在内存中开辟n个新结点、连续输入n个多项式的数据域并依次插入链表末尾。将尾结点的指针域赋值为空。
计算表长的函数：用count储存链表的长度，定义指向首元结点的指针p。若p不为空，则count自增，p后移一位，重复上述操作，直到p为空，返回count。
排序函数：使用冒泡排序法各个多项式的指数数据域，指数大的往后移。
多项式相加函数（前提是链表指数数据域已经升序排列）：建立新链表储存相加后的多项式，将指数小的一项插入新链表的表尾，若指数相同，则使系数相加。
多项式相加函数（前提是链表指数数据域已经升序排列）：将其中一个链表的各项变为相反数，其余操作和多项式相加函数一样。
多项式输出的函数：逐个输出链表的各个项。
主函数：依次调用各个函数实现不同的功能。

三、完整源代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>typedef struct polynomial {double coef;//系数int index;//指数struct polynomial* next;
};polynomial* CreateList(int n)//多项式链表建立的函数（尾插法）
{polynomial* L = (polynomial*)malloc(sizeof(polynomial));polynomial* r = L;//定义尾指针for (int i = 0; i < n; i++)//连续输入n个项的系数和指数{polynomial* p = (polynomial*)malloc(sizeof(polynomial));printf("请输入第%d项的系数、指数：", i+1);scanf("%lf %d", &p->coef, &p->index);r->next = p;r = r->next;//将尾指针后移一位}r->next = NULL;return L;
}int LengthList(polynomial* L)//计算表长的函数
{polynomial* p = L->next;int count = 0;while (p){count++;p = p->next;}return count;
}void sort(polynomial* L)//排序函数（冒泡排序法：数大后移）
{for (int i = 0; i <LengthList(L)-1; i++){polynomial* q = L->next;polynomial* p = L->next->next;for (int j = 0; j < LengthList(L)-i-1; j++){if (q->index > p->index)//指数大的项往后移{double temp1 = q->coef;//两数交换q->coef = p->coef;p->coef = temp1;int temp2 = q->index;q->index = p->index;p->index = temp2;}p = p->next;//指针后移q = q->next;}}
}polynomial* add(polynomial* L1, polynomial* L2)//多项式相加函数（前提是链表已经升序排列）
{polynomial* p = L1->next;polynomial* q = L2->next;polynomial* L = (polynomial*)malloc(sizeof(polynomial));//建立新链表储存相加后的多项式polynomial* r = L;while (p && q)//当p和q均不为空{if (p->index > q->index)//将指数小的一项插入新链表尾部{r->next = q;q = q->next;r = r->next;}else if (p->index < q->index){r->next = p;p = p->next;r = r->next;}else{if (p->coef + q->coef == 0)//若两项系数相加为0{p = p->next;q = q->next;}else{r->next = p;p->coef = p->coef + q->coef;q = q->next;p = p->next;r = r->next;}}r->next = p == NULL ? q : p;//将较长的多项式中未被操作的部分插入新链表的尾部}return L;
}polynomial* subtract(polynomial* L1, polynomial* L2)//多项式相减函数（前提是链表已经升序排列）
{polynomial* s = L2->next;//将被减数各项系数变为相反数while (s){s->coef = -s->coef;s = s->next;}polynomial* p = L1->next;//以下操作与多项式相加函数相同polynomial* q = L2->next;polynomial* L = (polynomial*)malloc(sizeof(polynomial));//建立新链表储存相加后的多项式polynomial* r = L;while (p && q)//当p和q均不为空{if (p->index > q->index)//将指数小的一项插入新链表尾部{r->next = q;q = q->next;r = r->next;}else if (p->index < q->index){r->next = p;p = p->next;r = r->next;}else{if (p->coef + q->coef == 0)//若两项系数相加为0{p = p->next;q = q->next;}else{r->next = p;p->coef = p->coef + q->coef;q = q->next;p = p->next;r = r->next;}}r->next = p == NULL ? q : p;//将较长的多项式中未被操作的部分插入新链表的尾部}return L;
}void VisitList(polynomial* L)//输出多项式的函数
{polynomial* p = L->next;while (p){printf("%.2lfx^%d ", p->coef, p->index);p = p->next;}printf("\n\n");
}//建立一个数据域与形参一样的新链表并返回，即将链表赋值一份
//定义该函数的原因是相加及相减函数会改变两个链表指针域的指向，故需要将链表先复制一份便于后续使用
polynomial* copy(polynomial* L)
{polynomial*CopyL= (polynomial*)malloc(sizeof(polynomial));polynomial* p = CopyL;polynomial* q = L->next;while (q){p->next = (polynomial*)malloc(sizeof(polynomial));p = p->next;p->coef = q->coef;p->index = q->index;q = q->next;}p->next = NULL;return CopyL;
}int main()
{int n1;printf("请输入第一个多项式的项数：");scanf("%d", &n1);printf("请输入第一个多项式：\n");polynomial* L1 = CreateList(n1);//多项式链表建立的函数printf("第一个多项式的各项为：\n");VisitList(L1);sort(L1);//排序函数polynomial* L3 = copy(L1);printf("排序后的多项式的各项为：\n");VisitList(L1);int n2;printf("请输入第二个多项式的项数：");scanf("%d", &n2);printf("请输入第二个多项式：\n");polynomial* L2 = CreateList(n2);//多项式链表建立的函数printf("第二个多项式的各项为：\n");VisitList(L2);sort(L2);//排序函数polynomial* L4 = copy(L2);printf("排序后的多项式的各项为：\n");VisitList(L2);polynomial* AddL = add(L1, L2);//多项式相加函数printf("相加后的多项式的各项为：\n");VisitList(AddL);polynomial* SubtractL = subtract(L3, L4);//多项式相减函数printf("相减后的多项式的各项为：\n");VisitList(SubtractL);//输出多项式的函数return 0;
}