一元稀疏多项式计算器(数据结构).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+5x^8-3.1x^11)+(7-5x^8+11x^9)=(-3.1x^11+11x^9+2x+7) 
【实现提示】 
用带表头结点的单链表存储多项式。 
#include <stdio.h>
#include <malloc.h>
typedef struct node
{
float coef;
int expn;
struct node *next;
}Lnode, *polynmial;
void create(polynmial &L);   //输入并建立多项式L
void display(polynmial L);   //显示，输出多项式L
void 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，结果给Ld
void 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);
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，结果给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;
   }
   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;
}