一元多項式相乘

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）實現原理