一元稀疏多项式计算器(数据结构).doc

【问题描述】设计一个一元稀疏多项式简单计算器【基本要求】一元多项式简单计算器的基本功能是：1，输入并建立多项式;2，输出多项式，输出形式为整数序列:n,c1,e1,c2,c2,.,cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列;3,多项式a和b相加，建立多项式a+b;4,多项式a和b相减，建立多项式a-b.【测试数据】1，(2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7)【实现提示】用带表头结点的单链表存储多项式。#include #include typedef struct nodefloat 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) /输入并建立多项式Lint i, n;static struct node *p;scanf(%d, &n);L = (struct node *)malloc (sizeof(struct node);L-next = NULL;for(i = 0; i coef, &p-expn); p-next = L-next; L-next = p;void display(polynmial L)/显示，输出多项式Lstruct 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(%dn, flag);else printf(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 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 expn) pc-next = Lc-next; Lc-next = pc; pc-coef = pa-coef; pc-expn = pa-expn; pa = pa-next; else if(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，结果给Ldstruct 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 expn) pd-next = Ld-next; Ld-next = pd; pd-coef = pa-coef; pd-expn = pa-expn; pa = pa-next; else if(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;