[C/C++ 演算法]-資料結構與演算法(文魁)：兩個多項式相加的演算法

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