duoxiangshi.rar_多项式加减_多项式加减法

//0610427 计算机 张琳 //使用链表实现两个多项式的加法和减法操作。 //各结点按指数升幂或降幂排列，生成的结果多项式仍使用原多项式所占用的存储空间： //两个同类项相加或相减时，如果系数不为0，则修改该结点的系数值，而指数值不变，将该结点链入结果多项式中，而另一项则释放空间； //如果系数为0，则这两项占用的空间均需释放。不同类项则直接放入结果多项式中。 //本程序按降幂输入输出,指数和系数均为整形。 #include<iostream.h> #include<fstream.h> //对自定义磁盘文件进行读和写的操作 #include<process.h> //使用“exit” #include<string.h> //使用“strlen” #include<malloc.h> //使用“free” const int nMaxChar=200; //假设文件每行不超过199个字符 //建立一个类，类中数据成员包括多项式的系数，指数以及下一个元素的地址，函数成员包括多项式加法和减法的运算以及多项式的输出。 class C_Polynomial { public: int nCoefficient; //多项式的系数 int nExponent; //多项式的指数 C_Polynomial *next; //下一个元素的地址 //输出函数,在一个文本文件中输出所求的多项式，用循环遍历链表，逐个输出。 void print(C_Polynomial *h,char *outputfile) //h为求得的链表的首地址，outputfile为建立的输出文件的名称 { ofstream fout(outputfile); //打开文件 C_Polynomial *p=h->next; fout<<p->nCoefficient<<"x"<<p->nExponent; //输出多项式第一项 p=p->next; while(p->next!=NULL) //输出其余项,如果nCoefficient为正则前面输出一个+号 { if(p->nCoefficient>0) fout<<"+"; fout<<p->nCoefficient<<"x"<<p->nExponent; p=p->next; } if(p->nCoefficient>0) fout<<"+"; if(p->nExponent!=0) //判断最后一项是否为常数项并输出 fout<<p->nCoefficient<<"x"<<p->nExponent; else fout<<p->nCoefficient; fout<<endl; } /*两个多项式相加的函数。A=A+B，相加结果（1）相加结果不为0，直接将B的内容加到A中；（2）相加结果为0，从A、B链表中删除此项 （3）原来A中无而B中有的项，则在A中插入一结点。算法是：从两链表头开始逐个移向下一个结点（1）如果A的指数大于B的指数，则A中 此结点不做修改，A继续移向下一个结点（2）如果两项指数相同，则完成加法运算结果放入A中此结点处，并释放B中此结点（3）如果A的 指数小于B的指数则把B结点插入A所指的结点之前。若A先处理完，则把B后面的结点接到A的尾部。*/ void add_Polynomial(C_Polynomial *A,C_Polynomial *B) { C_Polynomial *p,*q,*u,*pre; //p,q分别指向两个多项式的当前结点，u,pre用来记录某一特殊结点的位置 int nSum; //nSum记录系数相加的和 p=A->next; q=B->next; while((p!=NULL)&&(q!=NULL)) { if(p->nExponent>q->nExponent) //p的指数大于q的指数的情况 { pre=p; p=p->next; } else { if(p->nExponent==q->nExponent) //两指数相等执行加法 { nSum=p->nCoefficient+q->nCoefficient; if(nSum!=0) //系数和不为0时继续 { p->nCoefficient=nSum; pre=p; } else //系数和为零，删除p结点，释放空间 { pre->next=p->next; free(p); } p=pre->next; //执行完操作释放q结点的空间 u=q; q=q->next; free(u); } else //p指数小于q的指数,把结点q插入到p节点之前 { u=q->next; q->next=p; pre->next=q; pre=q; q=u; } } } if(q!=NULL) //A先处理完，把B后面的结点接到A的尾部 pre->next=q; } /*两个多项式相减的函数。A=A-B，相减结果（1）相减结果不为0，直接将A-B的结果放入A中（2）相减为0，从A、B链表中删除此项（3） 原来A中无而B中有的项，则用0减系数后插入A中。算法是：从两链表头开始逐个移向下一个结点（1）如果A的指数大于B的指数，则A中 此结点不做修改，A继续移向下一个结点（2）如果两项指数相同，则完成加法运算结果放入A中此结点处，并释放B中此结点（3）如果A的 指数小于B的指数则用0减B系数后插入A所指的结点之前。若A先处理完，则用0减B后的结点接到A的尾部。*/ void sub_Polynomial(C_Polynomial *A,C_Polynomial *B) { C_Polynomial *p,*q,*u,*pre; //p,q分别指向两个多项式的当前结点，u,pre用来记录某一特殊结点的位置 int nSub; //nSum记录系数相加的和 p=A->next; q=B->next; while((p!=NULL)&&(q!=NULL)) { if(p->nExponent>q->nExponent) //p的指数大于q的指数的情况 { pre=p; p=p->next; } else { if(p->nExponent==q->nExponent) //两指数相等执行减法 { nSub=p->nCoefficient-q->nCoefficient; if(nSub!=0) //系数和不为0时继续 { p->nCoefficient=nSub; pre=p; } else //系数差为零，删除p结点，释放空间 { pre->next=p->next; free(p); } p=pre->next; //执行完操作释放q结点的空间 u=q; q=q->next; free(u); } else //p指数小于q的指数,把0减q后的结点插入到p节点之前 { nSub=0-q->nCoefficient; q->nCoefficient=nSub; u=q->next; q->next=p; pre->next=q; pre=q; q=u; } } } if(q!=NULL) //A先处理完，把B的每个结点的系数用0减后接到A的尾部 { while(q!=NULL) { nSub=0-q->nCoefficient; q->nCoefficient=nSub; pre->next=q; q=q->next; } } } }; /*建立多项式链表。将存放二项式字符串数组中的数字提取出来形成一个数组，根据数组里的数据创建链表。 算法：从字符串的第一位开始逐 个判断，如果遇到‘，’或‘（’则将其后至下一个‘，’或‘）’的数字按照逐位乘十的方法组成一个完整的数，放在nData数组的一位上直 到字符串结束。如果遇到‘-’号，则先忽略，然后用0减去其对应的nData中的数，还原成负数。数组每两位记录一个结点的内容，逐个在链尾 加入，生成链表*/ C_Polynomial*set_Polynomial(char chPolynomial[nMaxChar]) { //建立存放数据的数组。 int nData[nMaxChar],k=0; for(unsigned int i=0;i<strlen(chPolynomial);i++) //将字符串中的数移入数组 { if(chPolynomial[i]=='('||chPolynomial[i]==',') //判断数首位的位置 { if(chPolynomial[i+1]=='-') //遇到负号先求出数，再用0减 { i++; i++; nData[k]=chPolynomial[i]-'0'; while((chPolynomial[i+1]!=',')&&(chPolynomial[i+1]!=')')) { nData[k]=10*nData[k]+(chPolynomial[i+1]-'0'); i++; } nData[k]=0-nData[k]; k++; } else //正数则直接用逐位乘十的方法得出 { i++; nData[k]=chPolynomial[i]-'0'; while((chPolynomial[i+1]!=',')&&(chPolynomial[i+1]!=')')) { nData[k]=10*nData[k]+(chPolynomial[i+1]-'0'); i++; } k++; } } } //建立链表 C_Polynomial *p,*r,*s; //p记录链首的位置，r,s用来生成链表 p=r=new C_Polynomial; int j=0; while((nData[j]!=0)||(nData[j+1]!=0)) //以（0，0）做为多项式结束，链表结束 { s=new C_Polynomial; s->nCoefficient=nData[j]; s->nExponent=nData[j+1]; r->next=s; r=s; j+=2; } r->next=NULL; //链表结束，返回 return p; } void main(){ char chInputfilename[30]; //记录输入的文件名 char chOutputfilename[30]; //记录输出的文件名 char chPolynomial1[nMaxChar]; //记录从文件读出的第一个多项式的数据 char chPolynomial2[nMaxChar]; //记录从文件读出的第二个多项式的数据 char chOrder[10]; //记录读入的做加法还是减法的命令 cout<<"请输入读入文件名(**.txt):"; //要求输入文件全称.例:inputfile1.txt cin>>chInputfilename; ifstream fin(chInputfilename,ios::nocreate); //仅打开一个已存在的chIn