多项式相加减【数据结构实验报告】

系统管理员 2022-06-07 11:42 211阅读 0赞

###      实验名称：实验一 多项式加减法  学号：\*\*\*  姓名：gnosed  实验日期：2017.10.16  一、实验目的  通过实现多项式的加减法，对链表有更深入的了解  二、实验具体内容  1、实验题目1：  （1）题目  问题描述：  设计一个一元稀疏多项式简单的加减法计算器  实现要求：  一元稀疏多项式简单计算器的基本功能是：  （1）输入并建立多项式  （2）输出多项式  （3）多项式A和B相加，建立多项式C＝A＋B，并输出相加的结果多项式C  （4）选作：多项式A和B相减，建立多项式C＝A－B，并输出相加的结果多项式D  （5）添加多项式因式  （6）摧毁多项式       （2）分析  对于各种功能  （1） 输入并建立多项式：  为输入输出格式的统一，本人规定因式格式为ax^b(a,b为int 类型) 。  规定指数呈递增输入输出。  创建两个单链表，表示两个一元多项式，单链表的一个结点表示多项式的一个因式，结点有一元参数的系数域、指数域和连接多个因式的指针域。  为方便对多项式进行删除或修改，单链表应该带空头结点。  （2） 输出多项式：  输出各系数的符号时，要判断系数是正数则在其前输出加号，是负数则只需输出它本身（自带负号）。  （3） 多项式A和B相加或相减  申请两个节点指针分别指向A和B的首个因式，比较它们的指数，  相同则系数相加减，申请新的节点来储存系数和指数，两个指针同时右移；  若不相同，则将指数小的因式赋值给新申请的节点，插在新的单链表上，将指向指数较小因式的指针右移。  重复上述比较，当有指针为空时，  若有一个指针为空，则将另一个指针指向的剩余的多项式因式连接到新的多项式后面；  若两个指针同时为空，return。  由此看出，规定按指数从小到大的顺序储存多项式，决定了实现多项式相加减的这种算法的出现。  （4） 添加多项式因式：  因为多项式是按指数从小到大储存的，所以插入新因式时，需要找到插入的位置。充分考虑是单链表的前头中间还是末尾。  （5） 摧毁多项式：  申请一个节点类型的指针，通过其移动，释放掉单链表的全部节点，返回空的头结点。  （3）实验代码  源代码：  （1） Poly.h 头文件  `#ifndefPOLY_H_INCLUDED #definePOLY_H_INCLUDED structPolynode{ int cof,exp; struct Polynode* next; }; typedef structPolynode* plist; plistCrea_poly(plist head); voidprint_poly(plist head); plistaddnode_poly(plist head); plistdestor_poly(plist head); plistadd_or_substr_poly(plist a,plist b,char ope); #endif //POLY_H_INCLUDED`       （2） Poly.cpp 方法文件  `#include<iostream> #include<cstdlib> #include"Poly.h" usingnamespace std; intstr_to_dec(string s){ int ans=0; int l=s.size(),ten=10*(l-1); for(int j=0;j<l;j++){ if(ten) ans+=(s[j]-'0')*ten; else ans+=s[j]-'0'; ten/=10; } return ans; } plistCrea_poly(plist head){ head=(plist)malloc(sizeof(structPolynode)); head->next=NULL; plist p=head; char ope='+'; string poly;string tcof=""; cin>>poly; for(int i=5;i<poly.size();i++){ if(poly[5]=='-') ope='-'; if(poly[i]=='+'||poly[i]=='-'){ ope=poly[i]; continue; } if(poly[i]=='x'){ int varcof=str_to_dec(tcof);//字符串式系数转为十进制数 plist t=(plist)malloc(sizeof(structPolynode)); ope=='+'?t->cof=varcof:t->cof=-varcof; tcof=""; ope='+'; string texp=""; int k=i+2; while(poly[k]!='+'&&poly[k]!='-'&&k<poly.size()){ texp+=poly[k]; k++; } int varexp=str_to_dec(texp);//字符串式的指数转化为十进制 t->exp=varexp; p->next=t; p=t; i=k-1; continue; } tcof+=poly[i]; } p->next=NULL; return head; } voidprint_poly(plist head){ if(head==NULL){ cout<<" isnull!\n";return; } cout<<"="; head=head->next; while(head){ if(head->cof==0) head=head->next; if(head->cof>0) cout<<"+"; cout<<head->cof<<"x^"<<head->exp; head=head->next; } cout<<endl; } plistaddnode_poly(plist head){ cout<<"Input cof,exp toadd:"<<endl; int c,e; cin>>c>>e; if(head==NULL){ plistnewhead=(plist)malloc(sizeof(struct Polynode)); plist t=(plist)malloc(sizeof(structPolynode)); newhead->next=t; t->cof=c; t->exp=e; newhead->next=t; t->next=NULL; return newhead; } else{ plist p=head->next; if(p->exp>e){ plist t=(plist)malloc(sizeof(structPolynode)); t->cof=c; t->exp=e; t->next=p; head->next=t; } else if(p->exp==e){ p->cof+=c; return head; } else{ plist pre; while(p!=NULL&&p->exp<e){ pre=p; p=p->next; } if(p==NULL){ plistt=(plist)malloc(sizeof(struct Polynode)); t->cof=c; t->exp=e; pre->next=t; t->next=NULL; } else if(p->exp>e){ plistt=(plist)malloc(sizeof(struct Polynode)); t->cof=c; t->exp=e; t->next=p; pre->next=t; } else if(p->exp==e) p->cof+=c; } return head; } } plistdestor_poly(plist head){ plist t=head; while(t){ head=head->next; free(t); t=head; } return t; } plistadd_or_substr_poly(plist a,plist b,char ope){ if(a==NULL||b==NULL){ cout<<"A(x) or B(x)";return 0; } plist i=a->next; plist j=b->next; plist k=(plist)malloc(sizeof(structPolynode)); plist new_poly_head=k; plist t; while(i!=NULL&&j!=NULL){ t=(plist)malloc(sizeof(structPolynode)); if(i->exp==j->exp){ ope=='+'?t->cof=i->cof+j->cof:t->cof=i->cof-j->cof; t->exp=i->exp; i=i->next; j=j->next; } else if(i->exp<j->exp){ t->cof=i->cof; t->exp=i->exp; i=i->next; } else if(i->exp>j->exp){ ope=='+'?t->cof=j->cof:t->cof=-j->cof; t->exp=j->exp; j=j->next; } k->next=t; k=t; } if(i==NULL&&j!=NULL){ k->next=j; if(ope=='-'){ k=k->next; while(k!=NULL){ k->cof=-k->cof; k=k->next; } } } else if(j==NULL&&i!=NULL) k->next=i; else k->next=NULL; return new_poly_head; }`       （3） Main.cpp 主函数  `//sourcefile2: "main.cpp" #include<iostream> #include"Poly.h" usingnamespace std; void print(){ cout<<"********************************\n"; } int main() { cout<<"******PolynomialOperation******"<<endl; cout<<" Please create poly A(x),B(x)first"<<endl; plist lis1=Crea_poly(lis1); plist lis2=Crea_poly(lis2); print(); cout<<"Input number to operateA(x),B(x)"<<endl; cout<<"0.Adding a factor\n1.AddA(x) to B(x)\n2.A(x) minus B(x)\n"; cout<<"3.Print A(x),B(x)\n4.Destroy\n5.stop\n"; print(); int n;string c; while(cin>>n){ switch(n){ case 0: cout<<"A(x) orB(x)?"<<endl; cin>>c; c=="A(x)"?lis1=addnode_poly(lis1): lis2=addnode_poly(lis2);break; case 1: cout<<"C(x)";print_poly(add_or_substr_poly(lis1,lis2,'+'));break; case 2: cout<<"C(x)";print_poly(add_or_substr_poly(lis1,lis2,'-'));break; case3:cout<<"A(x)";print_poly(lis1);cout<<"B(x)";print_poly(lis2);break; case 4: cout<<"A(x) orB(x)?"<<endl; cin>>c; c=="A(x)"?lis1=destor_poly(lis1):lis2=destor_poly(lis2); cout<<"Haddestroyed!"<<endl;break; default:return 0; } print(); } return 0; }`       运行结果：  `******PolynomialOperation****** Please create poly A(x),B(x) first A(x)=7x^0+3x^1+9x^8+5x^17 B(x)=-8x^1+22x^7-9x^8 ******************************** Input numberto operate A(x),B(x) 0.Adding afactor 1.Add A(x) toB(x) 2.A(x) minusB(x) 3.PrintA(x),B(x) 4.Destroy 5.stop ******************************** 3 A(x)=+7x^0+3x^1+9x^8+5x^17 B(x)=-8x^1-22x^7-9x^8 ******************************** 1 C(x)=+7x^0-5x^1-22x^7+5x^17 ******************************** 2 C(x)=+7x^0+11x^1+22x^7+18x^8+5x^17 ******************************** 0 A(x) or B(x)? A(x) Input cof,expto add: -23 -7 ******************************** 0 A(x) or B(x)? B(x) Input cof,expto add: 8 7 ******************************** 0 A(x) or B(x)? A(x) Input cof,expto add: -15 17 ******************************** 0 A(x) or B(x)? B(x) Input cof,expto add: 36 123 ******************************** 3 A(x)=-23x^-7+7x^0+3x^1+9x^8-10x^17 B(x)=-8x^1-14x^7-9x^8+36x^123 ******************************** 1 C(x)=-23x^-7+7x^0-5x^1-14x^7-10x^17+36x^123 ******************************** 2 C(x)=-23x^-7+7x^0+11x^1+14x^7+18x^8-10x^17-36x^123 ******************************** 4 A(x) or B(x)? A(x) Had destroyed! ******************************** 3 A(x) is null! B(x)=-8x^1-14x^7-9x^8-36x^123 ******************************** 1 C(x)A(x) orB(x) is null! ******************************** 2 C(x)A(x) orB(x) is null! ******************************** 4 A(x) or B(x)? B(x) Had destroyed! ******************************** 3 A(x) is null! B(x) is null! ******************************** 1 C(x)A(x) orB(x) is null! ******************************** 2 C(x)A(x) orB(x) is null! ******************************** 0 A(x) or B(x)? A(x) Input cof,expto add: -666 -23 ******************************** 0 A(x) or B(x)? B(x) Input cof,expto add: 999 32 ******************************** 3 A(x)=-666x^-23 B(x)=+999x^32 ******************************** 1 C(x)=-666x^-23+999x^32 ******************************** 2 C(x)=-666x^-23-999x^32 ******************************** 4 A(x) or B(x)? A(x) Had destroyed! ******************************** 4 A(x) or B(x)? B(x) Had destroyed! ******************************** 3 A(x) is null! B(x) is null! ******************************** 5 Processreturned 0 (0x0) execution time :33.397 s Press any keyto continue.`       三、实验小结  1. 实现代码之前，对框架和具体方法的思考不全，以致实现过程中停顿次数多，效率低。  2. 实现各个代码框架要主次分明，一块一块搭建，专心实现一种方法。  3. 在代码量增多的情况下找bug，单步调式跟踪代码尤为高效解决bug。  4. 此代码本人规定输入输出格式为ax^b(a,b为int 类型)，当 b=0 时也依照此输入输出，难免有些呆板，例如当多项式其中一个式子是常数时。这涉及到字符串的细心处理，这些技巧倒是占用不少实现时间。  5. 本实验以单链表为基础，通过对其各种ADT 实现，自己对单链表的使用更为熟练，理解更为深刻。 ###