C语言写一个程序，用链表实现多项式相加相减

Question

对于形如3*x^a+5*x^b+2*x^c+.........的多项式A，B，求它们的和以及差，链表实现

Answer 1

//要求：多项式按降幂排列
#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));
}