求高手帮帮忙:关于数据结构课程设计的

Question

问题描述：设有两个带表头的单链表表示两个一元稀疏多项式A、B，实现两个一元稀疏多项式的处理。
实现要求：
⑴ 输入并建立多项式；
⑵ 输出多项式，输出形式为整数序列：n，c1，e1，c2，e2……cn，en，其中n是多项式的项数，ci，ei分别为第i项的系数和指数。序列按指数降序排列；
⑶ 多项式A和B相加，建立多项式A+B，输出相加的多项式；
⑷ 多项式A和B相减，建立多项式A-B，输出相减的多项式；
⑸ 设计一个菜单，上述操作要求的基本功能。
测试数据：
(1) (2x+5x8-3.1x11)+(7-5x8+11x9)
(2) (6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)
(3)(x+x2+x3)+0
(4)(x+x3)-(-x-x-3)

Answer 1

struct elem
{
int coef;
int exp;
elem *next;
};
//
class LinkList
{
public:
LinkList( ); //建立只有头结点的空链表
LinkList(elem a[], int n); //建立有n个元素的单链表
friend void printlist(LinkList &);
friend void Add(elem *polya,elem *polyb);

elem *first;
};

#include "LinkList.h"
//建立空单链表*********************************************************************************
LinkList:: LinkList( )
{
first=new elem; first->next=NULL;
}
//创建给定数组的单链表*************************************************************************
LinkList::LinkList(elem a[],int n)
{
first=new elem; //生成头结点
elem *r,*s;
r=first; //尾指针初始化
for (int i=0; i<n; i++)
{
s=new elem; s->coef=a[i].coef;s->exp=a[i].exp; //为每个数组元素建立一个结点
r->next=s; r=s; //插入到终端结点之后
}
r->next=NULL; //单链表建立完毕，将终端结点的指针域置空
}
//一元多项式相加***********************************************************************************
void Add(elem *polya,elem *polyb)
{
elem *p,*q,*pre,*temp;
int sum;
p=polya->next;
q=polyb->next;
pre=polya;
while(p!=NULL&&q!=NULL)
{
if(p->exp<q->exp)
{
pre->next=p;pre=pre->next;
p=p->next;
}
else if(p->exp==q->exp)
{
sum=p->coef+q->coef;
if(sum!=0)
{
p->coef=sum;
pre->next=p;pre=pre->next;
p=p->next;temp=q;q=q->next;delete temp;
}
else
{temp=p->next;delete p;p=temp;
temp=q->next;delete q;q=temp;
}
}
else
{pre->next=q;pre=pre->next;
q=q->next;
}
}
if(p!=NULL)
pre->next=p;
else
pre->next=q;
}

//打印单链表以ax^b代表****************************************************************************
void printlist(LinkList &A)
{ elem *p;
p=A.first->next;
while (p)
{
cout<<p->coef<<"X^"<<p->exp;

p=p->next;
if(p)cout<<"+";
}
cout<<endl;
};

//LinkListMain.cpp
#include "iostream.h" //引用输入输出流库函数的头文件
#include "LinkList.cpp" //引用单链表的类
void main()
{cout<<"*****************一元多项式相加******************"<<endl;
cout<<" !!!!2x^3表示 2乘以x的三次方~!!!!"<<endl;
cout<<"**************************************************"<<endl;
cout<<"Welcome to use!"<<endl;
cout<<"nPlease input the ploya include coef && exp:"<<endl;
int m,n;
cout<<"输入A的项数;"<<endl;//建立一元多项式A
cin>>m;
elem a[10];
for(int i=0;i<m;i++) {cout<<"coef:";cin>>a[i].coef;cout<<"exp:";cin>>a[i].exp;}
LinkList A(a,m);
printlist(A); //输出一元多项式A
cout<<"输入B的项数;"<<endl;//建立一元多项式B
cin>>n;
elem b[10];
for(int j=0;j<n;j++) {cout<<"coef:";cin>>b[j].coef;cout<<"exp:";cin>>b[j].exp;}
LinkList B(b,n);
printlist(B); //输出一元多项式B
cout<<"多项式相加后为"<<endl;
Add(A.first,B.first);
printlist(A);
}