Question

C++设计：一元多项式相加

1. 问题描述
已知 A ( x ) = a 0 + a 1 x + a 2 x 2 + …… + a n x n 和 B ( x ) = b 0 + b 1 x + b 2 x 2 + …… + b m x m ，并且在 A ( x ) 和 B ( x ) 中指数相差很多，求 A ( x ) = A ( x ) + B ( x ) 。
2. 基本要求
⑴ 设计存储结构表示一元多项式； ⑵ 设计算法实现一元多项式相加； ⑶ 分析算法的时间复杂度和空间复杂度。
3. 设计思想
一元多项式求和 实质上是合并同类项的过程，其运算规则为： ⑴ 若两项的指数相等，则系数相加； ⑵ 若两项的指数不等，则将两项加在结果中。
一元多项式 A ( x ) =a 0 +a 1 x+a 2 x 2 + …… +a n x n 由 n +1 个系数唯一确定，因此，可以用一个线性表 ( a 0 ， a 1 ， a 2 ，……， a n ) 来表示，每一项的指数 i 隐含在其系数 a i 的序号里。但是，当多项式的指数很高且变化很大时，在表示多项式的线性表中就会存在很多零元素。一个较好的存储方法是只存非零元素，但是需要在存储非零元素系数的同时存储相应的指数。这样，一个一元多项式的每一个非零项可由系数和指数唯一表示。
由于两个一元多项式相加后，会改变多项式的系数和指数，因此采用顺序表不合适。 采用单链表存储，则每一个非零项对应单链表中的一个结点，且单链表应按指数递增有序排列。 结点结构如图 2 - 2 所示。

其中， coef ：系数域，存放非零项的系数； exp ：指数域，存放非零项的指数； next ：指针域，存放指向下一结点的指针。
将两个一元多项式用两个单链表存储后，如何实现二者相加呢？ 设两个工作指针 p 和 q ，分别指向两个单链表的开始结点。通过对结点 p 的指数域和结点 q 的指数域进行比较进行同类项合并，则出现下列三种情况： ⑴ 若 p -> exp <q->exp ，则结点 p 应为结果中的一个结点； ⑵ 若 p -> exp>q -> exp ，则结点 q 应为结果中的一个结点，将 q 插入到第一个链表中结点 p 之前； ⑶ 若 p -> exp=q -> exp ，则结点 p 与结点 q 为同类项，将 q 的系数加到 p 的系数上。若相加结果不为 0 ，则结点 p 应为结果中的一个结点，同时删除结点 q ；若相加结果为 0 ，则表明结果中无此项，删除结点 p 和结点 q ； 算法用伪代码描述如下：
直接把C++文件发到邮箱1424302624@qq.com，直接回复不给分

Answer 1

#include<iostream.h>
#include<malloc.h>
#define len sizeof(LNode)
typedef struct Lnode //结点结构声明
{ int nf; // 多项式系数
int ne; //多项式幂指数
struct LNode *next;
}LNode;
typedef LNode *Pol;

LNode *creat(void) //创建多项式函数
{ LNode *head,*q;
LNode *n;
head=q=n=(LNode *)malloc(len);
q->next=NULL;
do{n=(LNode *)malloc(len);
cin>>n->ne>>n->nf;
q->next=n;
q=n;}while(n->nf!=0||n->ne!=0);
q->next=NULL;
return head;}

LNode *output(LNode *head) //输出多项式的函数
{LNode *p;
p=head->next;int n=0;
if(p->nf==0&&p->ne==0) {cout<<"0";return 0;}
else do{if(p->nf!=0)
{if(n==0)
{if(p->ne==0) {cout<<p->nf;break;}
else{cout<<p->nf<<"X"<<p->ne;n++;p=p->next;}}
else {if(p->ne==0) {if(p->nf<0)cout<<p->nf;else cout<<"+"<<p->nf;break;}
else if(p->nf<0) {cout<<p->nf<<"X"<<p->ne;p=p->next;}
else {cout<<"+"<<p->nf<<"X"<<p->ne;p=p->next;}}}
else p=p->next;}while(p->nf!=0||p->ne!=0);
if(n==0&&p->nf==0&&p->ne==0) {cout<<"0";return 0;}
return 0;}

LNode * add(Pol &Pa,Pol &Pb)//两个多项式相加的函数
{LNode *p1,*p2,*p,*pr,*p0;
p1=Pa->next;p2=Pb->next;
p0=pr=Pa;
while(p1->next!=NULL||p2->next!=NULL)
{if(p1->ne>p2->ne)
{pr=p1;p1=p1->next;}
else if(p1->ne==p2->ne)
{p1->nf=p1->nf+p2->nf;p2=p2->next;}
else {pr->next=p2;p2=p2->next; pr=pr->next;pr->next=p1;}
if(p1->ne==0&&p2->next==NULL) break;}
p1->next=p2;
return p0;
}
void main()//主函数
{char y;
for(;;){Pol p1,p2,p3;
cout<<"input ha"<<endl;
p1=creat(); //建立多项式HA
cout<<"input hb"<<endl;
p2=creat(); //建立多项式HB
cout<<"ha=";*output(p1);cout<<endl;//输出多项式HA
cout<<"hb=";*output(p2);cout<<endl; //输出多项式HB
p3=add(p1,p2); //多项式HA与HB相加
cout<<"ha+hb=";*output(p3);cout<<endl; 输出多项式HC
cout<<"ARE YOU CONTINUE?(Y|N)"<<endl;
cin>>y;
if(y=='n') break;}

追问

直接把C++文件发到邮箱1424302624@qq.com，直接回复不给分

追答

已发

Answer 2

#include "stdafx.h"
#include<iostream>
using namespace std;
template<class Telem>
class SqList
{
private:
Telem * elem;
int curlen;
int maxlen;
public:
SqList(int maxsz=100):maxlen(maxsz)
{
curlen=0;
elem=new Telem;
};
SqList(Telem a[],int n,int maxsz=100):maxlen(maxsz)
{
curlen=n;
elem=new Telem[maxlen];
for(int i=0;i<n;i++)elem[i]=a[i];
};
~SqList();
Telem gete(int i)
{
if(i>=1&&i<=curlen)return elem[i-1];
else return NULL;
};
int leng();
SqList<Telem>&merg(SqList<Telem>&l2);//声明两多项式相加的成员函数
};
template<class Telem>
SqList<Telem>&SqList<Telem>::merg(SqList<Telem>&l2)//两多项式相加的成员函数的实现
{
int i,j,m,n,k(0);
m=curlen;n=l2.curlen;
if(m+n<=maxlen)
{
for(i=0;i<n/2;i++)
{
for(j=0;j<m/2;j++)
if(elem[2*j+1]==l2.elem[2*i+1])
if(j==m/2)
}
}
curlen=m+n-2*k;
return *this;
}
void fun(double a[],int j)//该函数实现：输入2j个double型的数，并将其存储到数组中
{
int i;
for(i=0;i<j;i++)
{
double m,n;
cout<<"请输入第"<<i+1<<"项的系数和指数:";
cin>>m>>n;
a[2*i]=m;
a[2*i+1]=n;
}
}
void main()
{

int i,j,k;
cout<<"第一个多项式有多少项:";
cin>>j;
cout<<"系数和指数的输入格式：系数+空格键+指数+Enter"<<endl;
double *a=new double[2*j];
fun(a,j);
cout<<"第二个多项式有多少项:";
cin>>k;
double *b=new double[2*k];
fun(b,k);
SqList<double>sqla(a,2*j);
SqList<double>sqlb(b,2*k);
sqla.merg(sqlb);
cout<<"这二个多项式结果为：";
for(i=1;i<=sqla.leng()/2;i++)//用for循环将这二个多项式结果输出
{
cout<<sqla.gete(2*i-1)<<"X^"<<sqla.gete(2*i);
if(i!=sqla.leng()/2)cout<<"+";
}
cout<<endl;
}