数据结构课程设计2012年12月班级：XXX学号：XXX姓名： XXX指导教师：XXX一元稀疏多项式计算器【问题描述】设计一个一元稀疏多项式简单计算器【基本要求】一元多项式简单计算器的基本功能是：1，输入并建立多项式;2，输出多项式，输出形式为整数序列:n,c1,e1,c2,c2,...,cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列;3,多项式a和b相加，建立多项式a+b;4,多项式a和b相减，建立多项式a-b.【算法设计思想】①一般情况下的一元n次多项式可写成pn(x)=p1xe1+p2xe2+……+pmxem其中，p1是指数为ei的项的非零系数，且满足0≦e1<e2<……<em=n ,若用一个长度为m且每个元素有两个数据项（系数项和指数项）的线性表（（p1,e1）,(p2,e2),……,(pm,em)）便可惟一确定多项式pn(x)。

②用两个带表头结点的单链表分别存储两个多项式③根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；④只需要将第二个多项式的系数改为其相反数，然后根据一元多项式相加的运算规则便可以得到其相应的“差多项式”【【实现提示】用带表头结点的单链表存储多项式。

【程序代码】#include <stdio.h>#include <malloc.h>typedef struct node{float coef;int expn;struct node *next;}Lnode, *polynmial;void create(polynmial &L); //输入并建立多项式Lvoid display(polynmial L); //显示，输出多项式Lvoid sort(polynmial &L); //多项式L按指数排序void reverse(polynmial &L); //逆置void select(); //用户选择加减操作void add(polynmial La, polynmial Lb, polynmial &Lc); //多项式La,Lb相加void subtract(polynmial La, polynmial Lb, polynmial &Ld); //多项式La减去Lb，结果给Ldvoid create(polynmial &L) //输入并建立多项式L{int i, n;static struct node *p;scanf("%d", &n);L = (struct node *)malloc (sizeof(struct node));L->next = NULL;for(i = 0; i < n; i++){p = (struct node *)malloc(sizeof(struct node));scanf("%f %d", &p->coef, &p->expn);p->next = L->next;L->next = p;}}void display(polynmial L)//显示，输出多项式L{struct node *p, *q;int flag = 0;int k = 0;q = L->next;while(q)if(q->coef != 0)k++;q = q->next;}printf("%d, ", k);p = L->next;if(p->coef != 0){printf("%.1f,%d, ", p->coef, p->expn);flag++;}for(p = p->next; p; p = p->next){if(p->coef != 0){printf("%.1f,%d, ", p->coef, p->expn);flag++;}}if(flag == 0)printf("%d\n", flag);elseprintf("\n");}void sort(polynmial &L)//多项式L按指数排序{polynmial p, q, r, u;p = L->next;L->next = NULL;while(p != NULL){r = L;q = L->next;while((q != NULL) && (q->expn <= p->expn)) {r = q;q = q->next;}u = p->next;r->next = p;p->next = q;p = u;}void reverse(polynmial &L)//逆置{polynmial H;static struct node *p, *q, *s;H = (struct node*)malloc(sizeof(struct node));H->next = NULL;p = (struct node*)malloc(sizeof(struct node));s = L->next;p->coef = s->coef;p->expn = s->expn;p->next = s->next;while(s){p->coef = s->coef;p->expn = s->expn;p->next = s->next;q = H->next;H->next = p;p->next = q;p = (struct node*)malloc(sizeof(struct node));s = s->next;}p = H->next;q = L->next;while(p){q->coef = p->coef;q->expn = p->expn;q = q->next;p = p->next;}}void select() //用户选择加减操作{printf("请选择加减操作\n");printf("1.两个一元多项式相加\n");printf("2.两个一元多项式相减\n");}void add(polynmial La, polynmial Lb, polynmial &Lc)//多项式La,Lb相加{struct node *pa, *pb;static struct node *pc;Lc = (struct node*)malloc(sizeof(struct node));pa = La->next;pb = Lb->next;Lc->next = NULL;while(pa && pb){pc = (struct node*)malloc(sizeof(struct node)); if(pa->expn < pb->expn){pc->next = Lc->next;Lc->next = pc;pc->coef = pa->coef;pc->expn = pa->expn;pa = pa->next;}elseif(pa->expn == pb->expn){pc->next = Lc->next;Lc->next = pc;pc->expn = pa->expn;pc->coef = pa->coef + pb->coef;pa = pa->next;pb = pb->next;}else{pc->next = Lc->next;Lc->next = pc;pc->coef = pb->coef;pc->expn = pb->expn;pb = pb->next;}}while(pa){pc = (struct node*)malloc(sizeof(struct node)); pc->next = Lc->next;Lc->next = pc;pc->coef = pa->coef;pc->expn = pa->expn;pa = pa->next;}while(pb){pc = (struct node*)malloc(sizeof(struct node));pc->next = Lc->next;Lc->next = pc;pc->coef = pb->coef;pc->expn = pb->expn;pb = pb->next;}}void subtract(polynmial La, polynmial Lb, polynmial &Ld)//多项式La减去Lb，结果给Ld{struct node *pa, *pb;static struct node *pd;Ld = (struct node*)malloc(sizeof(struct node));pa = La->next;pb = Lb->next;Ld->next = NULL;while(pa && pb){pd = (struct node*)malloc(sizeof(struct node));if(pa->expn < pb->expn){pd->next = Ld->next;Ld->next = pd;pd->coef = pa->coef;pd->expn = pa->expn;pa = pa->next;}elseif(pa->expn == pb->expn){pd->next = Ld->next;Ld->next = pd;pd->expn = pa->expn;pd->coef = pa->coef - pb->coef;pa = pa->next;pb = pb->next;}else{pd->next = Ld->next;Ld->next = pd;pd->coef = pb->coef;pd->expn = pb->expn;pb = pb->next;}}while(pa){pd = (struct node*)malloc(sizeof(struct node)); pd->next = Ld->next;Ld->next = pd;pd->coef = pa->coef;pd->expn = pa->expn;pa = pa->next;}while(pb){pd = (struct node*)malloc(sizeof(struct node)); pd->next = Ld->next;Ld->next = pd;pd->coef = -pb->coef;pd->expn = pb->expn;pb = pb->next;}}int main(){int sign;polynmial La, Lb, Lc, Ld;printf("请输入第一个多项式：\n");create(La);sort(La);printf("请输入第二个多项式：\n");create(Lb);sort(Lb);select();scanf("%d", &sign);switch(sign){case 1:printf("多项式之和为:\n");add(La, Lb, Lc);sort(Lc);reverse(Lc);display(Lc);break;default:printf("多项式之差为:\n"); subtract(La, Lb, Ld); sort(Ld);reverse(Ld);display(Ld);break;}return 0;}【程序运行截图】。