Zi 字媒體

[C/C++ 演算法]-資料結構與演算法(文魁)：兩個多項式相加的演算法     線上執行結果：http://www.tutorialspoint.com/compile_c_online.php   /* =========== Program Description ========= */ /* 程式名稱 : 4_1.cpp */ /* 演算法名稱：兩個多項式相加的演算法 */ /* 輸入：用陣列代表的多項式 */ /* 輸出：用陣列代表的二個多項式相加的結果 */ /* ========================================= */ // 宣告標頭檔 #include "stdio.h" #include "malloc.h" #include "string.h" // 宣告函式原型 // 利用傳址的方式把Array AV,AW,BV,BW,CV,CW傳進polyadd函式中 void polyadd(int *AV,int *AW,int *BV,int *BW,int *CV,int *CW); void main() { int AV[5]={4,1,3,4,5}; int AW[5]={0,1,3,4,5}; int BV[4]={3,2,3,6}; int BW[4]={0,2,3,6}; int CV[10]={0}; int CW[10]={0}; int i; /*list Array A*/ printf("A:"); for(i=1;i<=AV[0];i++) if(i==AV[0]) printf("%d*(X**%d) \n",AV[i],AW[i]); else printf("%d*(X**%d) + ",AV[i],AW[i]); /*list Array B*/ printf("B:"); for(i=1;i<=BV[0];i++) if(i==BV[0]) printf("%d*(X**%d) \n",BV[i],BW[i]); else printf("%d*(X**%d) + ",BV[i],BW[i]); polyadd(AV,AW,BV,BW,CV,CW); /*list Array B*/ printf("C:"); for(i=1;i<=CV[0];i++) { if(CV[i]==0) continue; if(i==CV[0]) printf("%d*(X**%d) \n",CV[i],CW[i]); else printf("%d*(X**%d) + ",CV[i],CW[i]); } getchar(); } void polyadd(int *AV,int *AW,int *BV,int *BW,int *CV,int *CW) { int Ano,Bno,Tno=0,k=0,i,j,c; /*Ano，Bno��A，B多項式非零的項數*/ Ano=AV[0];Bno=BV[0]; i=1;j=1; int *TV=(int*)malloc((Ano+Bno)*sizeof(int)); int *TW=(int*)malloc((Ano+Bno)*sizeof(int)); for(i=1;i<=Ano+Bno;i++) //以數列A為主 { c=AW[i]; //決定現在要處理的指數值 k++; TW[k]=AW[i]; //先把這個指數值的係數的��起來 TV[k]=AV[i]; for(j=1;j<=Bno;j++) //來看數列B中的元素 { if (c==BW[j]) //處理相同指數值的項 { TV[k]=TV[i]+BV[j]; BV[j]=0; BW[j]=0; }else if (c<BW[j]) //假設數列B��遞增,所以後面已經沒有相同的項了 break; else if (c>BW[j]) //假設數列B��遞增,所以後面可能還有相同的項了 continue; } } c=1; Tno=Ano; for(i=1;i<=Tno;i++) //以數列T為主 { for(j=1;j<=Bno;j++) //來看數列B中剩下沒有處理的元素 { if((BV[j]!=0) && (BW[j]!=0)) { if(TW[i]<BW[j]) { CV[c]=TV[i]; CW[c]=TW[i]; c++; }else{ i--; CV[c]=BV[j]; CW[c]=BW[j]; c++; BV[j]=0; BW[j]=0; } break; } } } for(j=1;j<=Bno;j++) //來看數列B中剩下沒有處理的元素 { if((BV[j]!=0) && (BW[j]!=0)) { CV[c]=BV[j]; CW[c]=BW[j]; c++; } } CV[0]=c-1; //第0項放的��個數要扣除掉 free(TV); free(TW); }