【求助】用链表实现多项式相加并输出显示
< <一道数据结构题目> > 关于用链表实现多项式相加：
题目要求：用户可以不按升幂或降幂输入数据建立多项式链表，但必须按照指数降序排列输出多项式； 程序功能要求能够完成两个多项式的相加、相减，并将结果输出显示。
作答要求：多项式相加的基本过程的算法（可以使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；
以下是本人写的按升幂输入，升幂输出多项式的程序，但是编译通过，却运行不到结果，请大家帮忙指点修正：
[code]
#include <stdio.h>
#include <malloc.h>
#define LEN sizeof(struct Polynomial)
struct Polynomial
{ float coef;
long expn;
struct Polynomial *next;
};
int n=0,sum=0;
int cmp(long a,long b)
{
int flag;
if(a <b) flag=-1;
else if(a> b)
flag=1;
else flag=0;
return flag;
}
struct Polynomial *creat (void)
{
struct Polynomial *head;
struct Polynomial *p1,*p2;
p1=p2=(struct Polynomial *)malloc(LEN);
scanf( "%f,%ld ",&p1-> coef,&p1-> expn);
head=NULL;
while(p1-> coef!=0)
{
n++;
if(n==1) head=p1;
else p2-> next=p1;
p2=p1;
p1=(struct Polynomial *)malloc(LEN);
scanf( "%f,%ld ",&p1-> coef,&p1-> expn);
}
p2-> next=NULL;
return head;
}
struct Polynomial *add(struct Polynomial *ah,struct Polynomial *bh)
{
struct Polynomial *pa1,*pa2,*pb1,*pb2;
float sumcoef;
pa1=ah;
pb1=bh;
pa2=pa1-> next;
pb2=pb1-> next;
while(pa1&&pb1)
{
switch(cmp(pa2-> expn,pb2-> expn))
{
case -1:pb2-> next=pa2;
pa2-> next=pb2-> next;
pb2=pb2-> next;
pa2=pa1-> next;break;
case 0 :sumcoef=pa1-> coef+pb1-> coef;
if(sumcoef!=0.0){
pa1-> coef=sumcoef;}break;
case 1:pb1-> next=pa2;
pa2-> next=pb2;
pa2=pa1-> next-> next;
pb2=pb2-> next;
break;
}
}
if(pb2)
pb1-> next=pb2;
free(bh);
return ah;
}
void display(struct Polynomial *head)
{
struct Polynomial *p;
printf( "The combinated Polynomial is:\n ");
p=head;
if(p!=NULL)
do
{printf( "%f,x^%ld ",p-> coef,p-> expn);
p=p-> next;
}
while (p!=NULL);
}
void main()
{
struct Polynomial *pahead,*pbhead,*abhead;
printf( "Input list Pa:\n ");
pahead=creat();
sum=sum+n;
printf( "Input list Pb:\n ");
pbhead=creat();
sum=sum+n;
abhead=add(pahead,pbhead);
display(abhead);
}
[/code]
（1）其中有一段多项式相加函数没有按题目要求“可以不按升幂或降幂顺序排列输入”写，能力所限，只写了个一般性的程序，而且也得不到结果。请大家帮帮指出上面的错误。（C环境下无法输入，C＋＋下可以输入却输不出结果）
（2）上述程序如果按照题目要求写程序，是不是需要添加有关排序函数？怎么写？请高手指教修正
请赐教二点疑惑，谢谢！！
[解决办法]
以前写过一个全部按降幂排列的，lz拿去看看吧（系数和指数是整型的）
//要求：多项式按降幂排列
#include <stdafx.h>
#include <iostream.h>
struct node
{
int coef;//系数
int exp;//指数
node * next;
};
node * h1=NULL;//第一个多项式的头指针
node * h2=NULL;//第二个多项式的头指针
node * insert(int c,int e)//创建一个系数为c，指数为e的结点，并返回其地址
{
node * newnode=new node;//创建新结点
newnode-> coef=c;//系数等于c
newnode-> exp=e;//指数等于e
newnode-> next=NULL;
return newnode;
}
node * create(node * h)
{
int coef;
int exp;
char c;
cout < < "请输入系数： ";
cin> > coef;
cout < < "请输入指数： ";
cin> > exp;
h=insert(coef,exp);
cout < < "是否输入完毕？（Y/N） ";
cin> > c;
if(c== 'y '||c== 'Y ')
{
return h;//如果输入完毕，返回头指针地址
}
else
{
h-> next=create(h-> next);//否则递归建立下一个结点
return h;//返回头指针地址
}
}
node * copy(node * source)//将一个结点的内容复制到另一个结点，并返回该结点地址
{
if(source!=NULL)//如果源结点不为空
{
node * des=new node;//创建新结点
des-> coef=source-> coef;//新结点的系数等于源结点的系数
des-> exp=source-> exp;//新结点的指数等于源结点的指数
des-> next=NULL;
return des;//返回新结点地址
}
return NULL;
}
void print(node * head)//输出头指针为head的多项式链表
{
node * h=head;
if(h==NULL)
{
cout < < "0 ";//如果链表为空，输出0
}
else
{
while(h-> next!=NULL)//否则，当其下一个结点不为空时
{
if(h-> exp==0)//如果指数为0，即常数
{
if(h-> coef> 0)//如果系数大于0
{
cout < <h-> coef;//输出系数
}
else
{
cout < < "\b " < <h-> coef;//否则，退一格（消除前面的+号），输出系数
}
}
else if(h-> exp==1)//否则，如果指数为1
{
if(h-> coef> 0)//如果系数大于0
{
if(h-> coef==1)//如果系数等于1
{
cout < < "x " < < "+ ";//输出x+
}
else
{
cout < <h-> coef < < "*x " < < "+ ";//否则，输出相应的系数
}
}
else
{
if(h-> coef==-1)//否则，如果系数等于-1
{
cout < < "\b " < < "-x " < < "+ ";//退一格，输出-x
}
else
{
cout < < "\b " < <h-> coef < < "*x " < < "+ ";//否则，退一格，输出相应的系数
}
}
}
else//否则，指数大于1
{
if(h-> coef> 0)//如果系数大于0
{
if(h-> coef==1)//如果系数等于1
{
cout < < "x " < <h-> exp < < "+ ";
}
else
{
cout < <h-> coef < < "*x " < <h-> exp < < "+ ";
}
}
else
{
if(h-> coef==-1)//否则，如果系数等于-1
{
cout < < "\b " < < "-x " < <h-> exp < < "+ ";
}
else
{
cout < < "\b " < <h-> coef < < "*x " < <h-> exp < < "+ ";
}
}
}
h=h-> next;
}
//输出最后一项
if(h-> exp==0)//如果指数为0，即常数
{
if(h-> coef> 0)//如果系数大于0
{
cout < <h-> coef;//输出系数
}
else
{
cout < < "\b " < <h-> coef;//否则，退一格，输出系数
}
}
else if(h-> exp==1)//否则，如果指数为1
{
if(h-> coef> 0)//如果系数大于0
{
if(h-> coef==1)//如果系数等于1
{
cout < < "x ";//输出x
}
else
{
cout < <h-> coef < < "*x ";
}
}
else
{
if(h-> coef==-1)//否则，如果系数等于-1
{
cout < < "\b " < < "-x ";//退一格，输出-x
}
else
{
cout < < "\b " < <h-> coef < < "*x ";
}
}
}
else//否则，指数大于1
{
if(h-> coef> 0)//如果系数大于0
{
if(h-> coef==1)//如果系数等于1
{
cout < < "x " < <h-> exp;
}
else
{
cout < <h-> coef < < "*x " < <h-> exp;
}
}
else
{
if(h-> coef==-1)//否则，如果系数等于-1
{
cout < < "\b " < < "-x " < <h-> exp;
}
else
{
cout < < "\b " < <h-> coef < < "*x " < <h-> exp;
}
}
}
}
}
void prints(node * p1,node * p2,node * r)//输出相加结果，形如p1+p2=r
{
print(p1);
cout < <endl < < "+ " < <endl;
print(p2);
cout < <endl < < "= " < <endl;
print(r);
cout < <endl;
}
char compare(node * n1,node * n2)//比较两个结点的指数大小
{
if(n1-> exp==n2-> exp)
{
return '= ';
}
else if(n1-> exp> n2-> exp)
{
return '> ';
}
else
{
return ' < ';
}
}
node * add(node * p1,node * p2)//计算两个多项式相加，返回结果链表首地址
{
node * fr;
//如果有一个为空，就把另外一个链表其后的部分复制到结果链表的尾部
if(p1==NULL)
{
node * x=copy(p2);
node * temp=x;
while(p2!=NULL)
{
x-> next=copy(p2-> next);
x=x-> next;
p2=p2-> next;
}
return temp;
}
else if(p2==NULL)
{
node * x=copy(p1);
node * temp=x;
while(p1!=NULL)
{
x-> next=copy(p1-> next);
x=x-> next;
p1=p1-> next;
}
return temp;
}
//如果都不为空
else
{
switch(compare(p1,p2))//比较两个结点的指数大小
{
case '= '://相等
if(p1-> coef+p2-> coef!=0)//如果系数和不为0
{
fr=insert(p1-> coef+p2-> coef,p1-> exp);//新结点的系数为两个结点的系数和，指数为这两个结点的指数
fr-> next=add(p1-> next,p2-> next);
return fr;
}
else
{
fr=add(p1-> next,p2-> next);//否则，新结点地址为这两个结点之后的部分链表的和链表的首地址
return fr;
}
case '> '://大于
fr=copy(p1);//新结点的内容与p1相同
fr-> next=add(p1-> next,p2);//以p1-> next为新的p1，递归调用add，创建链表余下的部分
return fr;
case ' < '://小于
fr=copy(p2);//新结点的内容与p2相同
fr-> next=add(p1,p2-> next);//以p2-> next为新的p2，递归调用add，创建链表余下的部分
return fr;
default:
return NULL;
}
}
}
void main(void)
{
cout < < "先建立第一个多项式： " < <endl;
h1=create(h1);
cout < < "再建立第二个多项式： " < <endl;
h2=create(h2);
cout < < "和： " < <endl;
prints(h1,h2,add(h1,h2));
}
