数据结构实践教程——线性表（一元多项式相加）

一、实验要求 用户根据自己的需求输入两个一元多项式，要求能够显示输入的一元多项式，再将这两个一元多项式相加，输出结果。

二、代码实现

#include<iostream> #include<cstring> #include<malloc.h> #include<stdlib.h> #include<stdio.h> using namespace std; typedef struct PLNODE{ double dbCoef;//系数域 int nExpn; //指数域 struct PLNODE *next; }PLNODE; typedef PLNODE *PLinkList; void CreatePolyn(PLinkList &sPolyn)//创建空链表 { sPolyn=(PLinkList)malloc(sizeof(PLNODE));//为头结点开辟空间 if(!sPolyn) return;//判断sPolyn是否为空，是就退出 sPolyn->next=NULL; } void ListInsert(PLinkList sPolyn,PLNODE sNewNode) { PLinkList sTemp=sPolyn; PLinkList psNewNode=(PLinkList)malloc(sizeof(PLNODE)); if(!psNewNode) return;//判断是否为空 *psNewNode=sNewNode;//将指针所指对象的值修改为sNewNode while(sTemp->next!=NULL) sTemp=sTemp->next; sTemp->next=psNewNode;//将结点插入链表尾部 psNewNode->next=NULL;//将尾结点的指向置为空 } bool GetInt(int &value) { char str[256]={0}; fflush(stdin);//清空缓冲区 gets(str);//等待输入数据，并将数据存到str中 unsigned int index=1; int nTemp=0; if(str[0]=='-')//判断是否为负数 nTemp=1; for(index=nTemp;index<strlen(str);index++) { if(str[index]<'0'||str[index]>'9') return false; }//判断输入的字符串是否合理 value=atoi(str);//将字符串转化为整数 return true; } void PrintPoly(PLNODE sPTemp) { if(sPTemp.nExpn==0)//指数为0，直接输出系数 cout<<sPTemp.dbCoef; else if(sPTemp.dbCoef==1)//系数为1时 { if(sPTemp.nExpn==1) cout<<"x"; else cout<<"x^"<<sPTemp.nExpn; } else if(sPTemp.dbCoef==-1)//系数为-1时 { if(sPTemp.nExpn==1) cout<<"-x"; else cout<<"-x^"<<sPTemp.nExpn; } else { if(sPTemp.nExpn==1) cout<<sPTemp.dbCoef<<"x"; else cout<<sPTemp.dbCoef<<"x^"<<sPTemp.nExpn; } } void PrintPolyn(PLinkList sPolyn) { int nIndex=0; PLinkList sPTemp=sPolyn->next;//sPTemp指向第一个项数 if(!sPTemp) printf("0");//多项式之和为0时，输出0 while(sPTemp!=NULL) { nIndex++; if(nIndex==1)//直接输出第一项 PrintPoly(*sPTemp); else if(sPTemp->dbCoef>0)//系数大于0，先输出+号 { cout<<"+"; PrintPoly(*sPTemp); } else PrintPoly(*sPTemp); sPTemp=sPTemp->next; } } //多项式按指数从小到大排序 PLinkList ListSort(PLinkList sPolyn) { sPolyn = sPolyn->next;//注意指向第一个结点 PLinkList sTemp1,sTemp2;//这两个变量表示冒泡排序的两个遍历节点变量 int nTemp=0;//中间变量 double dbTemp=0.0;//中间变量 for(sTemp1=sPolyn;sTemp1!=NULL;sTemp1=sTemp1->next) { for(sTemp2=sTemp1->next;sTemp2!=NULL;sTemp2=sTemp2->next) { if(sTemp1->nExpn>sTemp2->nExpn) { //如果sTemp1结点的指数值大，则交换两个结点的指数 nTemp=sTemp2->nExpn; sTemp2->nExpn=sTemp1->nExpn; sTemp1->nExpn=nTemp; dbTemp=sTemp2->dbCoef; sTemp2->dbCoef=sTemp1->dbCoef; sTemp1->dbCoef=dbTemp; } } } return sPolyn; } void InputData(int nOrder,PLinkList &sPolyn) { CreatePolyn(sPolyn);//创建空链表 int n; do{ GetInt(n); if(n<0) cout<<"输入项数为负,重新输入"<<endl; }while(n<0); PLNODE sNewNode;//定义新结点 double dbCoef; int nExpn; int Expn[n]; for(int i=0;i<n;i++) { do{ cout<<"请输入第"<<i+1<<"项的系数:"; cin>>dbCoef; if(cin.fail()||dbCoef==0) cout<<"输入系数不合法"<<endl; }while(cin.fail()||dbCoef==0); cout<<"请输入第"<<i+1<<"项的指数:"; GetInt(nExpn); //cout<<endl; int Expn[n];// Expn[i]=nExpn;//使用数组记录之前输入的指数 for(int j=0;j<i-1;j++) if(nExpn==Expn[j]) { cout<<"指数输入重复"<<endl; return; }//当前指数是否已输入过，是则报错 sNewNode.dbCoef=dbCoef;//存入数据 sNewNode.nExpn=nExpn; ListInsert(sPolyn,sNewNode);//将新结点插入多项式链表的尾部 } } PLinkList AddPolyn(PLinkList sPolyn1,PLinkList sPolyn2) { PLinkList sPolynAdd;//要生成的多项式之和链表 CreatePolyn(sPolynAdd);//创建空链表，sPolynAdd为头指针 PLinkList sPolyn1Temp=sPolyn1->next;//指向第一个多项式的第一项 PLinkList sPolyn2Temp=sPolyn2->next;//指向第二个多项式的第一项 PLNODE sNewNode;//要插入和多项式中的结点 while((sPolyn1Temp!=NULL)&&(sPolyn2Temp!=NULL)) { int nEx=sPolyn1Temp->nExpn-sPolyn2Temp->nExpn;//计算指数差 if(nEx<0)//多项式sPolyn1当前节点的指数值小 { sNewNode.nExpn=sPolyn1Temp->nExpn; sNewNode.dbCoef=sPolyn1Temp->dbCoef; ListInsert(sPolynAdd,sNewNode);//将提取出来的项存入和链表中 sPolyn1Temp=sPolyn1Temp->next;//移动sPolyn1Temp的结点 } else if(nEx==0)//当前结点的指数相同 { double dbCo=sPolyn1Temp->dbCoef+sPolyn2Temp->dbCoef; if(dbCo!=0.0)//当前相同指数的项的系数之和不为0 { sNewNode.nExpn=sPolyn1Temp->nExpn; sNewNode.dbCoef=dbCo; ListInsert(sPolynAdd,sNewNode);//将提取出来的项存入和链表中 } sPolyn1Temp=sPolyn1Temp->next; sPolyn2Temp=sPolyn2Temp->next;//移动结点 } else { sNewNode.nExpn=sPolyn2Temp->nExpn; sNewNode.dbCoef=sPolyn2Temp->dbCoef; ListInsert(sPolynAdd,sNewNode); sPolyn2Temp=sPolyn2Temp->next; } } PLinkList sPolynTemp; CreatePolyn(sPolynTemp); if(sPolyn1Temp) sPolynTemp=sPolyn1Temp; else sPolynTemp=sPolyn2Temp; while(sPolynTemp)//链接剩余结点到和链表中 { sNewNode.nExpn=sPolynTemp->nExpn; sNewNode.dbCoef=sPolynTemp->dbCoef; ListInsert(sPolynAdd,sNewNode); sPolynTemp=sPolynTemp->next; } return sPolynAdd; } void FreePolyn(PLinkList sPolyn) { PLinkList sTemp=sPolyn; while(sPolyn!=NULL) { sPolyn=sPolyn->next; free(sTemp); sTemp=sPolyn; } } int main() { cout<<"/*注意：系数为浮点类型，指数为整数（可为负）类型。\n"; cout<<"请按指数从小到大的顺序输入多项式。*\n\n"; PLinkList A,B,C; int m,n; cout<<"请输入第1个多项式的项数："; InputData(m,A); ListSort(A); cout<<"第1个多项式:"; PrintPolyn(A); cout<<endl<<endl; cout<<"请输入第2个多项式的项数："; InputData(n,B); ListSort(B); cout<<"第2个多项式:"; PrintPolyn(B); cout<<endl<<endl; cout<<"多项式之和为："; C=AddPolyn(A,B); ListSort(C); PrintPolyn(C); cout<<endl; cout<<"第1个多项式:"; PrintPolyn(A); cout<<endl; cout<<"第2个多项式:"; PrintPolyn(B); //释放链表 FreePolyn(A); FreePolyn(B); FreePolyn(C); return 0; }

三、运行结果