数据结构多项式相加实验报告_多项式相加实验报告
数据结构多项式相加实验报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“多项式相加实验报告”。
天津理工大学计算机科学与技术专业
陈龙
题目要求：输入复杂多项式，做到化简和相加减运算。
一.算法模块分析：
将整个项目可分为四部分：
1.将输入字符串链表分析到单链表
2.单链表化简
3.链表值运算
4.输出 二.模块分块实现：
1.将输入字符串链表分析到单链表
分析：
一元稀疏多项式，包含字符有数字（系数和指数）
系数中小数点，指数符号，变量字母（以x为例）
运算符（+和-,其中加减也可以表示正负数）
通过以上分析可以构建如下结构体以用于存储每个单项
并完成相应标志任务
struct Record{
double factor;//记录系数95.12-26x+73x^3 =-80.52+48x-29x^3+4x^12
测试二：
5x+3x^2-15+21.45x^21+57.34-12x^2+20x 67x^3+51x-67x+123.456-81x+99x^21+41^2 多项式1和2最简结果: 加法运算
42.34+25x-9x^2+21.45x^21 + 123.456-97x+41x^2+67x^3+99x^21 = 165.796-72x+32x^2+67x^3+120.45x^21 减法运算
42.34+25x-9x^2+21.45x^21-123.456-97x+41x^2+67x^3+99x^21 =-81.116+122x-50x^2-67x^3-77.55x^21 四。总结
根据代码运行实例结果分析，其可以正确运算各种符合预定规则的输入。
代码健壮性良好。代码实现中，做到了不写重复代码的要求，将运算代码
合为一个。并符合代码模块化规则，将各模块分块实现，并完美的结合在一起。
具体实现代码： /* 实现多项式计算
*/
#include #include #include #include #include using namespace std;struct Record{ double factor;//记录系数
int power;//记录次方
int flt;//记录后面有多少小数,用复数表示
bool flag;//记录正或者
Record *next;};Record *InitRecord(){ Record *nr=new Record();nr->power=0;//初始化次方为0
nr->factor=1;//初始化系数为1
nr->flag=true;//初始化为正数
nr->next=NULL;nr->flt=0;return nr;} cla Polynomial{ public:
//初始化链表头，多项式字符串，进行分析
Polynomial(char *str=NULL);//重载构造函数，直接利用多项式进行给予对象
Polynomial(Record *h);
void Analsis(char* str);//分析多项式
void OutputPolynomial();//按规则输出多项式
Record* GetHead(){//得到头节点
return head;
} private:
void RemoveRepeatedAndZero();
//处理栈中存储的数据，将一项处理到节点中
void InsertToListTail(Record* node);
Record *head;//记录头节点
Record *tail;//记录尾节点
stack Q;};Polynomial::Polynomial(char* str){ head=InitRecord();//初始化头节点
tail=head;if(str!=NULL)Analsis(str);}
Polynomial::Polynomial(Record *h){ head=h;} void Polynomial::Analsis(char* str){ int n=strlen(str);int i=0;Record *temp;bool flag=false;
while(i
{
case '-':{
if(!Q.empty())
{
//已经记录了数据就可以插入了
InsertToListTail(temp);
i--;
flag=false;
}
else
{
temp->flag=!temp->flag;
}
break;
}
case '.':{
temp->flt=-1;
break;
}
case '+':{
if(!Q.empty())
{
//已经记录了数据就可以插入了
InsertToListTail(temp);
flag=false;
}
break;
}
case ' ':break;
case '^':{
temp->power=1;
break;
}
case 'x':{
temp->power=1;
if(Q.empty())Q.push(1);
break;
} default:{ if(!(str[i]>='0'&&str[i]
cout
if(temp->flt&&!temp->power)temp->flt--;
else if(temp->power)temp->power++;//多一个次方
Q.push(str[i]-'0');
break;
}
}
i++;} this->InsertToListTail(temp);this->RemoveRepeatedAndZero();} //完成插入到链表后新的数据，同时将factor计算出来
void Polynomial::InsertToListTail(Record* node){ double fr=0.0;int p=0;int temp=0;int i=0;
//统计平方值
if(node->power>1)//如果power大于1才计算
{ while(--node->power>0){ temp=Q.top();Q.pop();p+=temp*powl(10,i++);} node->power=p;} if(node->flt==0)node->flt--;while(!Q.empty()){ temp=Q.top();Q.pop();fr+=temp*powl(10,++node->flt);} node->factor=fr;
if(node->flag==false)//负数标志
{ node->factor=-node->factor;//使系数变符号
} if(node->factor!=0){ tail->next=node;//接入新节点
tail=node;} } void Polynomial::OutputPolynomial(){ Record* p=head;if(p->next==NULL){
cout
return;} int flag=0;while(p->next!=NULL){
//负数输出是会带有负号，不需要加入或验证
p=p->next;
//如果系数为正，且不是头项，就应该输出‘+’
if(p->factor>0&&flag)cout
flag=1;//标志此时不是输出第一项
if(p->factor==-1&&p->power)cout
}
//如果系数不等于1 或者没有x，就输出系数
else if(p->factor!=1||!p->power)coutfactor;if(p->power)//如果有x就要暑输出
cout
if(p->power>1)//次方大于1，要输出
coutpower;}
cout
void Polynomial::RemoveRepeatedAndZero(){ Record* h,*p,*temp,*pre;if(head->next==NULL)return;h=head->next->next;p=head->next;pre=head;
int flag=true;
while(flag){ flag=false;while(p!=NULL&&h!=NULL){
if(p->power==h->power)
{
p->factor+=h->factor;
p->next=h->next;
temp=h;
h=h->next;
delete temp;
flag=true;
continue;
}
if(p->power>h->power)
{
temp=h;
p->next=temp->next;
temp->next=p;
pre->next=temp;
p=pre->next;
h=p->next;
flag=true;
continue;
}
h=h->next;
pre=pre->next;
p=p->next;} if(p!=NULL)p->next=NULL;h=head->next->next;p=head->next;pre=head;} p=head->next;pre=head;while(p!=NULL)//去除系数为零的项
{ if(p->factor==0){
temp=p;
p=p->next;
}
pre->next=p;
delete temp;} if(p!=NULL){ p=p->next;pre=pre->next;} } pre->next=NULL;//将一个节点复制到一个新空间
Record* CopyTo(Record* h){ Record* nd=InitRecord();nd->factor=h->factor;nd->flag=h->flag;nd->flt=h->flt;nd->next=NULL;nd->power=h->power;return nd;} //多项式相加过程
Record* PolyAdd(Record* a,Record *b,int flag)//flag=1=>+else-{ Record* result=InitRecord();Record* p=result;Record* temp;a=a->next;b=b->next;while(a!=NULL&&b!=NULL){
if(a->powerpower)
{
temp=CopyTo(a);
a=a->next;
}
else if(b->powerpower)
{
temp=CopyTo(b);
if(!flag)temp->factor*=-1;
b=b->next;
}
else{
temp=CopyTo(a);
if(flag)
temp->factor+=b->factor;
else
temp->factor-=b->factor;
b=b->next;
a=a->next;
}
p->next=temp;
p=temp;} if(!a)a=b;while(a!=NULL){
p->next=CopyTo(a);
p=p->next;
a=a->next;} p->next=NULL;return result;} int main(){ char str[50];char st2[50];Record *p,*q,*re,*m;cin>>str;cin>>st2;Polynomial exp(str);Polynomial e2(st2);p=exp.GetHead();q=e2.GetHead();
re=PolyAdd(p,q,1);Polynomial res(re);cout
e2.OutputPolynomial();cout
m=PolyAdd(p,q,0);cout
e2.OutputPolynomial();cout
