南郵OJ 1006多項式乗算

多項式乗算
時間制限(通常/Java):
1000 MS/3000 MS実行メモリ制限:65536 KByte総発行:434テスト合格:206
試合の説明
線形テーブルは最も簡単で、最も基本的で、最もよく使われるデータ構造であり、その用途は非常に広く、例えば、表頭ノード付き単鎖テーブルで一元整係数多項式加算と乗算を解く.
2つの一元整係数多項式を与え,両者の積を解くことを要求する.
入力
各グループは1つの1元整係数多項式を表し、複数の行からなり、各行は多項式の各項目の係数と指数を与え、これらの行は指数減少順に並べ替えられる.各組の終了行入力は0-1
しゅつりょく
最初の2つのグループは1元整係数多項式であり、最後のグループは2つの多項式の積である.
一元整係数多項式出力形式は以下の通りである.
(1)多項式項4 x出力4 X
(2)多項式項4 x 2出力4 X^2
(3)第一項係数が正数の場合、プラス記号は出力しない
(4)定数係数項を除き項係数は1非明示出力、-1出力は-
例えば、4 x 3-x 2+x-1の正しい出力形式は4 X^3-X^2+X-1、エラー出力形式は+4 X^3-1 X^2+1 X-1
サンプル入力
3 14 -8 8 6 2 2 0 0 -1 2 10 4 8 -6 2 0 -1
サンプル出力
3X^14-8X^8+6X^2+2 2X^10+4X^8-6X^2 6X^24+12X^22-16X^18-50X^16+12X^12+76X^10+8X^8-36X^4-12X^2
ヒント
この問題は南京郵電大学の「データ構造A」実験1の内容に属し、教科書のコードを検証し、慎重に解答してください.
テーマソース
CHENZ

#include
using namespace std;

typedef struct node{
	int coefficient;			//     
	int exponent;				//     
	struct node *next;
}polynomialNode,*polynomial;

/*
*    ：     
*    ：head:        ；
*    ： 
*/
void printPolynomial(polynomial head){	//     
	polynomialNode *p = head->next;
	if(p == NULL)
		cout<coefficient > 0){				//  
			if(p != head->next)				//           “+”
				cout<coefficient != 1)			//   1   
				cout<coefficient;
		}
		else{								//  
			if(p->coefficient == -1)						//-1     “-”
				cout<coefficient;	
		}
		if(p->exponent == 0){				//   0,   ，   X^0，      1      			
			if(p->coefficient == 1 || p->coefficient == -1)
				cout<<1;
		}
		else if(p->exponent == 1)			//    1
			cout<exponent;
		p = p->next;
	}
	cout<next!=NULL && p->next->exponent>tempExponent)	//       ，      
		p = p->next;
	if(p->next == NULL || p->next->exponentcoefficient = tempCoefficient;
		tempNode->exponent = tempExponent;
		tempNode->next = p->next;
		p->next = tempNode;
	}
	else{													//        ，       
		q = p->next;										//               
		q->coefficient += tempCoefficient;
		if(q->coefficient == 0){
			p->next = q->next;								//    0     
			delete q;
		}
	}
}

/*
*    ：       ；
*    ：inputHead:              ；
         ：tempCoefficient:          
		 ：tempExponent   :          
*    ： 
*/
void inputPolynomial(polynomial inputHead){
	int tempCoefficient;
	int tempExponent;
	while(cin>>tempCoefficient>>tempExponent &&\
		(tempCoefficient!=0 || tempExponent!=-1)){
		if(tempCoefficient == 0)								//   0，     
			continue;	
		addElementToPolynomial(inputHead,tempCoefficient,tempExponent);
	}
}

/*
*    ：     ，out=add1+add2
*    ：add1:   1
*          add2:   2
*    ：out :     
*/
void addPolynomial(polynomial add1,polynomial add2,polynomial sum){
	polynomialNode *p,*q;
	p = add1->next;					//  add1   
	q = add2->next;					//  add2    
	while(p!=NULL){
		addElementToPolynomial(sum,p->coefficient,p->exponent);
		p = p->next;
	}
	while(q!=NULL){
		addElementToPolynomial(sum,q->coefficient,q->exponent);
		q = q->next;
	}
}
/*
*    ：       
*    ：head:        ；
*    ： 
*/
/*
void delePolynomial(polynomial head){
	polynomialNode *p =NULL;
	while(head!=NULL){
		p = head;
		head = head->next;
		delete p;
		p = NULL;
	}
}*/

/*
*    ：     ，out=m1*m2
*    ：m1:    1
*          m2:    2
*    ：out:     
*/
void multiply(polynomial m1,polynomial m2,polynomial out){
	polynomialNode *p,*q;
	p = m1->next;
	while(p!=NULL){											//m1     m2  
		q = m2->next;
		while(q!=NULL){
			addElementToPolynomial(out,p->coefficient*q->coefficient,p->exponent+q->exponent);
//			printPolynomial(out);
			q = q->next;
		}
		p = p->next;
	}
}

int main(void){
	polynomial inPolynomial[2];				//     
	polynomial outPolynomial;				//     
	int i = 0;	
	for(i=0;i<2;++i){
		inPolynomial[i] = new polynomialNode();	//  ()           
		inputPolynomial(inPolynomial[i]);
		printPolynomial(inPolynomial[i]);
	}
	outPolynomial = new polynomialNode();
	multiply(inPolynomial[0],inPolynomial[1],outPolynomial);
	printPolynomial(outPolynomial);
	return 0;
}