[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);
}