数据结构多项式相加实验报告
2020-03-02 21:19:56 来源：范文大全收藏下载本文
天津理工大学计算机科学与技术专业
陈龙
题目要求：输入复杂多项式，做到化简和相加减运算。
一.算法模块分析：
将整个项目可分为四部分：
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
人人范文网 m.inrrp.com.cn 手机版