一元稀疏多项式计算器(数据结构)(共7页).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 <stdio.h>#include <malloc.h>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 < 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)/显示，输出多项式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 <= 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;      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 < pb->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;专心-专注-专业