一元多项式相乘

2019-11-08 02:55:13

字体：大中小

来源：转载

供稿：网友

一、不靠谱的代码实现：

#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_NUM 40 //能够处理的一元多项式的长度 #define MAX_COEF 10 //系数或幂（带符号的情况下）能处理的最大长度 typedef struct Inode{ int coef; //系数 int exp; //幂 struct Inode* next;}Inode;typedef struct Inode *poly;typedef struct assistArray{ int coef; int exp;}assistArray;assistArray aArray[MAX_NUM];//辅助数组 int stringTonum(char* s,int *i,int n,int flag);int createAssistArray(char* s,int n);poly createPolynomial(int m);poly multiplyPolynomial(poly headA,poly headB);void outputPolynomial(poly head);void outputAssistArray(int m);void outputList(poly head);int getLength(char* s);void destroyPolynomial(poly head);int stringTonum(char* s,int *i,int n,int flag) //字符数向整型数转换的函数 { int j; char num[MAX_COEF]; memset(num,'/0',MAX_COEF); if(flag==0&&*i!=0){//系数时，需考虑符号 j=*i-1; while(1){ num[j-*i+1]=s[j]; ++j; if(s[j]>'9'||s[j]<'0'||j>n-1) break;//j>n-1处理类似这种情况：3X+100，后面这个100转换的情况 } } else if(flag==1||*i==0){//幂时，一元多项式不需要考虑 j=*i; while(1){ num[j-*i]=s[j]; ++j; if(s[j]>'9'||s[j]<'0'||j>n-1) break; } } *i=j-1; return atoi(num);}int createAssistArray(char* s,int n){ int *i,k,h=0,flag=0; //flag=1时为幂，flag=0时为系数 i=&k; for(k=0;k<n;++k){ if(s[k]<='9'&&s[k]>='0'){ if(flag==0){ aArray[h].coef=stringTonum(s,i,n,flag); if(k+1>=n||s[k+1]!='X'){aArray[h].exp=0;++h;}//处理一元多项式最后一项为常数，或期间某项为零次幂 } else if(flag==1) {aArray[h].exp=stringTonum(s,i,n,flag);++h;flag=0;} } else if(k==0&&s[k]=='X') aArray[h].coef=1; //处理类似于X+1的系数情况 else if(s[k]=='+'&&s[k+1]=='X') aArray[h].coef=1; //处理2X^2+X+1中X的系数情况 else if(s[k]=='-'&&s[k+1]=='X') aArray[h].coef=-1; //处理2X^2-X+1中X的系数情况 if(s[k-1]=='X'&&s[k]=='^') flag=1; //开始处理幂 if(s[k]=='X'&&s[k+1]!='^'){aArray[h].exp=1;++h;} //处理2X+1中X的幂的情况 } return h;}poly createPolynomial(int m){ int i; poly newp,PRe,temp,head=malloc(sizeof(Inode)); head->next=NULL; for(i=0;i<m;++i){ pre=head; temp=head->next; while(temp!=NULL&&temp->exp>aArray[i].exp){//调整为降序 pre=temp; temp=temp->next; } newp=malloc(sizeof(Inode)); newp->coef=aArray[i].coef; newp->exp=aArray[i].exp; newp->next=pre->next; pre->next=newp; } return head;}poly multiplyPolynomial(poly headA,poly headB){ int EXP,COEF; poly headN=malloc(sizeof(Inode)),tempA=headA->next,tempB=headB->next,tempN,Newp,pre; headN->next=NULL; while(tempA!=NULL){ pre=headN; tempN=headN; tempB=headB->next; while(tempB!=NULL){ EXP=tempA->exp+tempB->exp; COEF=tempA->coef*tempB->coef; while(tempN->next!=NULL){ pre=tempN; tempN=tempN->next; if(tempN->exp==EXP) break; } if(tempN->next==NULL&&tempN->exp!=EXP){//如果headN序列中未出现幂为EXP的项，则新建 Newp=malloc(sizeof(Inode)); Newp->coef=COEF; Newp->exp=EXP; tempN->next=Newp; Newp->next=NULL; tempN=Newp; } else{ tempN->coef=tempN->coef+COEF;//已有幂为EXP的项 if(tempN->coef==0){//系数若相加为零，则删去该项 pre->next=tempN->next; free(tempN); tempN=pre; } } tempB=tempB->next; } tempA=tempA->next; } return headN;}void outputPolynomial(poly head)//系数为0,1，-1时都要特殊处理 { int begin=1; poly temp=head->next; while(temp!=NULL){ if(temp->coef>0&&begin==0) printf("+"); if(temp->exp>1){ if(temp->coef!=1&&temp->coef!=-1) printf("%dX^%d",temp->coef,temp->exp); else if(temp->coef==1) printf("X^%d",temp->exp); else printf("-X^%d",temp->exp); } else if(temp->exp==1){ if(temp->coef!=1&&temp->coef!=-1) printf("%dX",temp->coef); else if(temp->coef==1) printf("X"); else printf("-X"); } else printf("%d",temp->coef); if(begin==1) begin=0; temp=temp->next; } printf("/n");} void outputAssistArray(int m){ int i; for(i=0;i<m;++i){ printf("%d %d/n",aArray[i].coef,aArray[i].exp); }}void outputList(poly head){ poly temp=head; while(temp->next!=NULL){ temp=temp->next; printf("%d %d/n",temp->coef,temp->exp); }}int getLength(char* s){ int i=0; while(s[i]!='/0'){ ++i; } return i;}void destroyPolynomial(poly head){ poly pre=head,temp=head; while(temp->next!=NULL){ pre=temp; temp=temp->next; free(pre); }}int main(){ int m1,m2; char s1[MAX_NUM],s2[MAX_NUM]; poly head1,head2,heads; memset(s1,'/0',MAX_NUM); memset(s2,'/0',MAX_NUM); printf("First Polynomial:/n"); gets(s1); printf("Second Polynomial:/n"); gets(s2); m1=createAssistArray(s1,getLength(s1)); head1=createPolynomial(m1); m2=createAssistArray(s2,getLength(s2)); head2=createPolynomial(m2); heads=multiplyPolynomial(head1,head2); printf("Result:/n"); outputPolynomial(heads); destroyPolynomial(head1); destroyPolynomial(head2); destroyPolynomial(heads); return 0;}

二、杂乱的总结笔记：

输入部分依旧很麻烦，要考虑各种特别情况，而且一般都是写完了才想起来，所以常常出现问题。测试用的输出函数一定要简洁而且正确，不然会浪费大量时间。链表循环时一定要多问自己这几个问题：a)这轮循环是否需要初始化？b)这轮循环后，temp指针在哪里？c)是否需要删除指针？d)会不会有指针为NULL情况，但你写了ptr->num类似的错误代码？

The End

上一篇：AsyncHttpClient 维持登录状态

下一篇：MyBatis源码剖析 - MyBatis 插件之拦截器（Interceptor）实现原理