1、掌握线性表的链式存储结构；
2、掌握链表的基本操作，并能进行应用实践；
3、使用C/C++语言和线性表实现“一元多项式相加”专题。
二、【实验内容】结合课本第41页的例子，采用链式存储结构，将两个线性链表表示的一元多项式相加，并输出。此一元多项式遵循多项式相加运算规则：对于两个一元多项式中存在指数相同的项时，其对应系数相加：合并时系数和为零时，删除“和多项式”中此项；合并时系数和不为零时，则构成“和多项式”中的一项。对于两个一元多项式中存在的指数不相同的项，则分别复抄到“和多项式”中去，原多项式保持不变。
三、【实验步骤与要求】1、实验前的准备
（1）了解C语言的基本概念；
（2）了解C语言的基本段落。
2、上机操作
（1）了解链式存储结构的基本知识；
（2）掌握算法思想和数据结构的描述；
（3）掌握一元多项式相加的运算规则。
参考《数据结构实践教程》（C语言版）P7-17 四、【验收要点】① A、B均为有头结点
② 输入多项式A和B（要考虑乱序输入的情况，非乱序不扣分）
③ A、B有序排列（递增、递减均可）
④ A+B合并，并输出新的多项式（当指数相等时，需有考虑系数相加不为0和系数相加为0两种情况）
⑤ 输出A、B（要求原A、B保持不变）
五、【实验代码】#include#include typedef struct polynode* polynomial;//定义指向结构体的指针 typedef struct polynode { //结构体含有三个项 float coef; int expn; polynomial next; //指向下一个结构体的指针 }polynode; polynomial creatpoly(int n); //创建多项式 //int lengthpoly(polynomial p); //链表长度 polynomial sortpoly(polynomial p,int n); //多项式排序 polynomial addpoly(polynomial p1, polynomial p2); //多项式相加 void printpoly(polynomial p); //多项式输出 polynomial copypoly(polynomial p); //链表复制 int main() { int n, m; polynomial pa, pb, pc,pd,pp,ps; printf("请输入多项式A的个数:"); scanf("%d", &n); pa = creatpoly(n); printf("请输入多项式B的个数:"); scanf("%d", &m); pb = creatpoly(m); pc = copypoly(pa); pd = copypoly(pb); sortpoly(pc,n); sortpoly(pd,m); printf("合并后的结果为:n"); pp = addpoly(pc, pd); printpoly(pp); printf("合并之后的pa为:n"); printpoly(pa); printf("合并之后的pb为:n"); printpoly(pb); return 0; } polynomial creatpoly(int n) { //创建链表 polynomial pHead = (polynomial)malloc(sizeof(polynode)); //定义一个头节点 polynomial p = (polynomial)malloc(sizeof(polynode)),h; pHead->next = p; //头节点指向首节点 printf("请输入多项式的系数及指数:n"); scanf("%f %d", &p->coef, &p->expn); p->next = NULL; h = p; int i; for (i = 1;i < n;i++) { polynomial q = (polynomial)malloc(sizeof(polynode));//h用来指向最后一个节点 h->next = q; scanf("%f %d", &q->coef, &q->expn); q->next = NULL; h = q; } return pHead; //返回头节点 } //int lengthpoly(polynomial p) { // int length = 0; // polynomial pnext = p->next; // while (pnext!=NULL) // { // length++; // p = p->next; // pnext = p->next; // } // // return length; //} polynomial sortpoly(polynomial pHead,int n) { //选择排序,指针指向不好换，所以直接换里面的值 polynomial p,q; int i , j,ce,ex; for (i = 0, p= pHead->next; i < n-1; ++i,p=p->next) { for (j = i + 1, q = p->next;j < n;++j,q=q->next) { if (q == NULL) return pHead; if (p->expn > q->expn) { ce = p->coef; ex = p->expn; p->coef = q->coef; p->expn = q->expn; q->coef = ce; q->expn = ex; } } } return pHead; } void printpoly(polynomial p) { //打印 polynomial pnext = p->next; while (pnext!=NULL) { printf("%.f %d ", pnext->coef, pnext->expn); p = p->next; pnext = pnext->next; } printf("n"); } polynomial addpoly(polynomial pa, polynomial pb) { polynomial p, q, s, r,t; int cmp, x; p = pa->next; q = pb->next; s = pa; r = pb; while (p != NULL && q != NULL) { if (p->expn < q->expn) { cmp = -1; } else if (p->expn > q->expn) { cmp = 1; } else///指数相等 { cmp = 0; } switch (cmp) { case -1: { s = p; p = p->next;///pa表指针后移，没有插入 break; } case 0: { x = p->coef + q->coef;///指数相等，系数相加 if (x != 0) { p->coef = x; s = p; p = p->next; } else///系数为0,在pa表中删除该结点 { s->next = p->next; free(p); p = s->next; } r->next = q->next;///在pb表中删除该结点 free(q); q = r->next; break; } case 1: { t=q->next; q->next = s->next; s->next = q;///将pb表中的q插入到pa表中的s的后面 r->next = t; s = q; q = r->next; break; } } } if (q != NULL)///当pb连表还有剩余时接入到pa连表的尾部 { s->next = q; } free(pb); return pa; } polynomial copypoly(polynomial L) { polynomial h,a; if (L == NULL) return NULL; h = a = (polynomial)malloc(sizeof(polynode));//新链表的头指针（指向第一个结点的指针） while (1) { a->coef = L->coef;//复制数据 a->expn = L->expn; if (L->next != NULL)//还没有复制完 { L = L->next; a->next = (polynomial)malloc(sizeof(polynode));//为新链表再分配一个结点空间 a = a->next; } else { a->next = NULL; break; } } return h;//返回新链表的头指针 }
