**

《程序设计实践》第06练——多项式相乘

**
注意：打开相关源程序后，只能在//********与//=======之间编写程序，若修改其它部分可能得0分。

1. 多项式相乘：conv.cpp（本题100分）

【问题描述】 编程实现若干个多项式相乘。多项式的输入输出格式为：系数在前，指数在后，各项按指数递增排列，每个多项式输入时以两个0结束。系数为0的项不输出。

例如：1+4X3-9X5
 输入格式可以为：1 0 0 1 0 2 4 3 0 4 -9 5 0 0或者 1 0 4 3 -9 5 0 0，
 输出只能是：1 0 4 3 -9 5。
【输入】
输入文件conv.in包含n+1行：第1行为一个正整数n，表示多项式的个数。第2到n+1行，每行为一个多项式，多项式输入时以两个0结束。例如：
1 0 1 1 0 0
1 0 -1 1 0 0
1 0 1 2 0 0
表示：(1+x)(1-x)(1+x2)
【输出】
输出文件conv.out包含1行，为上述多项式相乘结果。上例的输出为：
1 0 -1 4
表示1-x4
【输入输出样例1】
conv.in conv.out
3
1 0 1 1 0 0
1 0 -1 1 0 0
1 0 1 2 0 0 1 0 -1 4
【数据限制】
所有系数、指数均为整数（int类型）。
多项式的个数n满足：2≤n≤20；
【提示】参考程序提供了2种解法
（1） 综合应用前序程序设计实践所掌握的数组、结构体、指针、有序链表合并等知识进行编程；
（2） 每个多项式存储一个链表中，链表节点中存储有多项式某个’项’的系数c和指数e。
（3） 多项式A和B相乘时，A的每个节点（指数）乘于B的各个节点，结果为一个多项式Temp；逐一累加上述多项式Temp（期间需要合并同类项，即指数相同的节点，即可获得多项式乘积的最终结果！

在这里插入代码片
/*实现n个多项式相乘*/
#include "stdio.h"
const int N0=20;	//常数: 多项式最多20个

typedef struct node{	//多项式的项(链表节点), 数据包含: 项的系数和指数, 下一项的指针.
	int c, e;			//c-系数(coefficient); e-指数(exponent)
	struct node *next;	//下一个多项式项的指针
}NP;

NP *createPoly(){	//创建一个多项式(对应一个多项式链表)
	int c, e;		//c-系数(coefficient); e-指数(exponent)
	NP *head, *p;	//head-多项式头指针; p-游标指针
	head=p=new NP;	//初始化多项式的 头指针 & 游标指针
	while( true ){
		/*(1)输入(获得)多项式'项'的数据[系数+指数]信息 */
		scanf("%d%d", &c, &e);	//输入多项式项 ==> 根据输入数据的特点: 系数+指数 紧接着出现!
		if( c==0 && e==0 ){	//根据约定, 系数 & 指数 都为0, 则多项式输入结束
			break;
		}else if(c==0){ //此多项式'项'的系数=0, 可以不需要次多项式'项'!
			continue;
		}
		
		/*(2)多项式数据项有效, 则创建 多项式'项'(对应于链表节点)*/
		p->next=new NP;
		p=p->next;
		
		/*(3)维护多项式项的数据信息*/
		p->c=c;
		p->e=e;
	}
	p->next=NULL; //多项式最后一个节点的 "下一个多项式项 指针"为空 ==> 标志为多项式(链表)末尾
	
	return head;  //返回多项式链表的头指针
}

void printPoly( NP *head ){ //打印输出多项式链表
	NP *p=head->next; //p-遍历指针
	while( p ){
		printf("%d %d ", p->c, p->e);
		p=p->next;
	}
	printf("\n");
}

void freePoly( NP *head){ //删除参数(头指针head)指定的多项式, 回收其所占用的内存空间
	NP *p; //p-遍历指针
	while( head ){
		p=head;
		head=head->next;
		delete p;
	}
}

NP *addPoly( NP *ha, NP *hb){ //实现两个多项式相加(需要处理同类项[即指数相同的项]),返回结果多项式的链头指针.
	//*************************************
	NP *hc, *pc, *pa=ha->next, *pb=hb->next; //hc,pc-结果多项式的链头和遍历游标指针; pa,pb-两个相加的多项式的遍历游标指针
	int c, e; //c,e-多项式'项'的系数和指数
	hc=pc=new NP; //初始化结果多项式的链头指针hc&遍历游标指针pc
	while( pa || pb ){
		/**(1)获得次数循环的 多项式'项'的: 系数c 和 指数e*/
		if( pa && (pb==NULL || pa->e < pb->e) ){ //(1)若pa'项'存在, 并且[(pb'项'为NULL) 或 (pa'项'的指数小于 pb的指数)], 即只处理pa'项'
			//和的'多项式项' 只包括pa的当前项
			c=pa->c;
			e=pa->e;
			
			pa=pa->next; //移动游标pa至下一个
		}else if( pb && (pa==NULL || pa->e > pb->e) ){ //与(1)类似, 只处理pb'项'
			//和的'多项式项' 只包括pa的当前项
			c=pb->c;
			e=pb->e;
			
			pb=pb->next; //移动游标pb至下一个
		}else{//pa'项' 和 pb'项'都不为空, 且指数相同, 则累加系数
			//和的'多项式项' pa和pb的当前项, 指数不变,系数相加
			c = pa->c + pb->c;
			e = pa->e;
			
			pa = pa->next;	 //移动游标pa至下一个
			pb = pb->next;	 //移动游标pb至下一个
		}
		
		/**(2)根据 多项式'项'的: 系数c 和 指数e, 创建对应节点*/
		if( c ){
			pc->next=new NP; //创建1个新链表节点(多项式'项')
			pc=pc->next; //维护链表节点关系
			
			pc->c=c; //此链表节点(多项式'项')的系数c
			pc->e=e; //此链表节点(多项式'项')的指数e
		}
	}
	pc->next=NULL; //相加结果多项式的链尾指针=NULL
	
	return hc; //返回2个多多项式(链表)相加的结果
	//=====================================
}

NP *oneXmulty( NP *pa, NP *hb ){ //pa-某个多项式'项'; hb-一个多项式(多个'项'), 返回pa*ha的结果多项式:头指针
	//*************************************
	NP *hc, *pc, *pb=hb->next; //hc-多项式'项'pa 与 多项式hb 相乘的结果:头指针; pc-结果多项式hc的遍历指针; pb-多项式hb的遍历指针;
	
	hc=pc=new NP; //初始化结果多项式hc的头指针hc 和 游标指针pc
	while( pb ){  //遍历多项式hb, 每个'项'pb 都与 多项式'项'pa相乘 ==> 从而获得相乘后的结果多项式
		//(a)新节点创建 & 链表维护
		pc->next=new NP; //当前多项式'项'pb 与 多项式项'pa'相乘的结果'项'(节点)
		pc=pc->next;
		
		//(b)维护相乘多项式'项'(节点)的系数c和指数e
		pc->c=pa->c*pb->c;
		pc->e=pa->e+pb->e;
		
		//(c)移动游标指针 至 多项式hb的下一个多项式'项'(节点)
		pb=pb->next;
	}
	pc->next=NULL; //相乘结果多项式的链尾指针=NULL
	
	return hc;//返回结果多项式的头指针
	//=====================================
}

NP *multyXmulty( NP *ha, NP *hb ){ //实现两个多项式ha和hb的相乘, 返回结果多项式hc(链表头指针)
	//*************************************
	NP *hc; //hc-ha和hb相乘的结果多项式; t
	NP *pa = ha->next; //pa-第一个多项式ha的遍历指针---> 获得每个多项式'项'(节点)==>以乘于另一个多项式项hb
	NP *t; //t-ha的某个多项式'项'节点 与 另一个多项式hb的乘积=一个多项式t
	
	hc=new NP; //初始化结果多项式hc的: 链头指针
	hc->next=NULL; //初始化结果多项式hc的: 链尾指针
	
	while( pa ){ //若多项式ha存在节点'项'存在, 则(1)此ha的此多项式'项'乘于另一多项式hb; (2)并把结果累加到结果多项式hc
		//(A)ha的当前多项式'项'(节点) 乘于另一多项式hb, 得到一个多项式t
		t=oneXmulty( pa, hb );
		
		//(B)将多项式t累加到最终结果多项式hc中
		hc=addPoly( hc, t);
		
		//(C)多项式ha的下一个节点
		pa=pa->next;
		
		//(D)累加完t, 回收t占用的内存空间
		freePoly( t );
	}
	
	return hc; //返回两个多项式相乘的结果多项式:头指针
	//=====================================
}

int main(){
	int n, i; //n-多项式的个数; i-循环控制变量
	NP *hink[N0], *hc, *temp;	//hink[]-待相乘的若干个多项式的头指针; hc-多项式相乘结果头指针;
	
	FILE *fp;
	if((fp=fopen("conv.in", "r")) != NULL ){
		fclose(fp);  //存在的话，要先把之前打开的文件关掉
		
		freopen("conv.in", "r", stdin);
		freopen("conv.out", "w", stdout);
	}
	
	scanf("%d", &n);	//输入多项式的个数n
	//******************************************
	/*(1)创建n个多项式链表*/
	for(i=0;i<n;i++){
		hink[i] = createPoly();	//创建多项式(对应于链表)
	}
	
	/*(2)进行n个多项式相乘*/
	temp=multyXmulty( hink[0], hink[1] );	
	for(i=2;i<n;i++){
		hc = multyXmulty( temp, hink[i]);	//调用函数进行多项式ha &  hb相乘, 结果存储在多项式hc中
		freePoly( temp );	//删除多项式相乘临时结果temp, 回收其所占用的内存空间
		temp = hc;
	}
	hc = temp;
	
	/*(3)输出n个多项式相乘的结果多项式 */
	printPoly( hc ); //打印输出相乘结果多项式
	
	
	/*(4)删除多项式hink[i] 和 hc, 回收其所占用的内存空间 */
	for(i=0;i<n;i++){
		freePoly( hink[i] );
	}
	freePoly( hc );	//删除多项式hc, 回收其所占用的内存空间
	//==========================================
	return 0;
}

在这里插入代码片
/*实现两个多项式相乘*/
#include "stdio.h"

typedef struct node{	//多项式的项(链表节点), 数据包含: 项的系数和指数, 下一项的指针.
	int c, e;			//c-系数(coefficient); e-指数(exponent)
	struct node *next;	//下一个多项式项的指针
}NP;

NP *createPoly(){	//创建一个多项式(对应一个多项式链表)
	int c, e;		//c-系数(coefficient); e-指数(exponent)
	NP *head, *p;	//head-多项式头指针; p-游标指针
	head=p=new NP;	//初始化多项式的 头指针 & 游标指针
	while( true ){
		/*(1)输入(获得)多项式'项'的数据[系数+指数]信息 */
		scanf("%d%d", &c, &e);	//输入多项式项 ==> 根据输入数据的特点: 系数+指数 紧接着出现!
		if( c==0 && e==0 ){	//根据约定, 系数 & 指数 都为0, 则多项式输入结束
			break;
		}else if(c==0){ //此多项式'项'的系数=0, 可以不需要次多项式'项'!
			continue;
		}
		
		/*(2)多项式数据项有效, 则创建 多项式'项'(对应于链表节点)*/
		p->next=new NP;
		p=p->next;
		
		/*(3)维护多项式项的数据信息*/
		p->c=c;
		p->e=e;
	}
	p->next=NULL; //多项式最后一个节点的 "下一个多项式项 指针"为空 ==> 标志为多项式(链表)末尾

	return head;  //返回多项式链表的头指针
}

void printPoly( NP *head ){ //打印输出多项式链表
	NP *p=head->next; //p-遍历指针
	while( p ){
		printf("%d %d ", p->c, p->e);
		p=p->next;
	}
	printf("\n");
}

void freePoly( NP *head){ //删除参数(头指针head)指定的多项式, 回收其所占用的内存空间
	NP *p; //p-遍历指针
	while( head ){
		p=head;
		head=head->next;
		delete p;
	}
}

NP *addPoly( NP *ha, NP *hb){ //实现两个多项式相加(需要处理同类项[即指数相同的项]),返回结果多项式的链头指针.
	NP *hc, *pc, *pa=ha->next, *pb=hb->next; //hc,pc-结果多项式的链头和遍历游标指针; pa,pb-两个相加的多项式的遍历游标指针
	int c, e; //c,e-多项式'项'的系数和指数
	hc=pc=new NP; //初始化结果多项式的链头指针hc&遍历游标指针pc
	while( pa || pb ){
		/**(1)获得此次循环的 多项式'项'的: 系数c 和 指数e*/
		if( pa && (pb==NULL || pa->e < pb->e) ){ //[1]若pa'项'存在, 并且[(pb'项'为NULL) 或 (pa'项'的指数小于 pb的指数)], 即只处理pa'项'
			//和的'多项式项' 只包括pa的当前项
			c=pa->c;
			e=pa->e;

			pa=pa->next; //移动游标pa至下一个
		}else if( pb && (pa==NULL || pa->e > pb->e) ){ //[2], 与([1]类似, 只处理pb'项'
			//和的'多项式项' 只包括pa的当前项
			c=pb->c;
			e=pb->e;

			pb=pb->next; //移动游标pb至下一个
		}else{//[3], pa'项' 和 pb'项'都不为空, 且指数相同, 则累加系数
			//和的'多项式项' pa和pb的当前项, 指数不变,系数相加
			c = pa->c + pb->c;
			e = pa->e;

			pa = pa->next;	 //移动游标pa至下一个
			pb = pb->next;	 //移动游标pb至下一个
		}

		/**(2)根据 多项式'项'的: 系数c 和 指数e, 创建对应节点*/
		if( c ){
			pc->next=new NP; //创建1个新链表节点(多项式'项')
			pc=pc->next; //维护链表节点关系

			pc->c=c; //此链表节点(多项式'项')的系数c
			pc->e=e; //此链表节点(多项式'项')的指数e
		}
	}
	pc->next=NULL; //相加结果多项式的链尾指针=NULL

	return hc; //返回2个多多项式(链表)相加的结果
}

NP *oneXmulty( NP *pa, NP *hb ){ //pa-某个多项式'项'; hb-一个多项式(多个'项'), 返回pa*ha的结果多项式:头指针
	NP *hc, *pc, *pb=hb->next; //hc-多项式'项'pa 与 多项式hb 相乘的结果:头指针; pc-结果多项式hc的遍历指针; pb-多项式hb的遍历指针;
	
	hc=pc=new NP; //初始化结果多项式hc的头指针hc 和 游标指针pc
	while( pb ){  //遍历多项式hb, 每个'项'pb 都与 多项式'项'pa相乘 ==> 从而获得相乘后的结果多项式
		//(a)新节点创建 & 链表维护
		pc->next=new NP; //当前多项式'项'pb 与 多项式项'pa'相乘的结果'项'(节点)
		pc=pc->next;

		//(b)维护相乘多项式'项'(节点)的系数c和指数e
		pc->c=pa->c*pb->c;
		pc->e=pa->e+pb->e;

		//(c)移动游标指针 至 多项式hb的下一个多项式'项'(节点)
		pb=pb->next;
	}
	pc->next=NULL; //相乘结果多项式的链尾指针=NULL

	return hc;//返回结果多项式的头指针
}

NP *multyXmulty( NP *ha, NP *hb ){ //实现两个多项式ha和hb的相乘, 返回结果多项式hc(链表头指针)
	NP *hc; //hc-ha和hb相乘的结果多项式; 
	NP *pa = ha->next; //pa-第一个多项式ha的遍历指针---> 获得每个多项式'项'(节点)==>以乘于另一个多项式项hb
	NP *t; //t-ha的某个多项式'项'节点 与 另一个多项式hb的乘积=一个多项式t
	
	hc=new NP; //初始化结果多项式hc的: 链头指针
	hc->next=NULL; //初始化结果多项式hc的: 链尾指针

	while( pa ){ //若多项式ha存在节点'项'存在, 则(1)此ha的此多项式'项'乘于另一多项式hb; (2)并把结果累加到结果多项式hc
		//(A)ha的当前多项式'项'(节点) 乘于另一多项式hb, 得到一个多项式t
		t=oneXmulty( pa, hb );
		
		//(B)将多项式t累加到最终结果多项式hc中
		hc=addPoly( hc, t);

		//(C)多项式ha的下一个节点
		pa=pa->next;

		//(D)累加完t, 回收t占用的内存空间
		freePoly( t );
	}

	return hc; //返回两个多项式相乘的结果多项式:头指针
}

int main(){
	int n; //n-多项式的个数
	NP *ha, *hb, *hc;	//ha,hb-待相乘的两个多项式; hc-多项式相乘结果(仍为多项式)
	
	FILE *fp;
	if((fp=fopen("conv.in", "r")) != NULL ){
		fclose(fp);  //存在的话，要先把之前打开的文件关掉
		
		freopen("conv.in", "r", stdin);
		freopen("conv.out", "w", stdout);
	}
	
	scanf("%d", &n);	//输入多项式的个数n

	ha=createPoly();	//创建多项式链表ha
	hb=createPoly();	//创建多项式链表hb
	//******************************************

	hc=multyXmulty( ha, hb);	//调用函数进行多项式ha &  hb相乘, 结果存储在多项式hc中

	printPoly( hc ); //打印输出相乘结果多项式
	
	//==========================================
	freePoly( ha );	//删除多项式ha, 回收其所占用的内存空间
	freePoly( hb );	//删除多项式hb, 回收其所占用的内存空间
	freePoly( hc );	//删除多项式hc, 回收其所占用的内存空间
	return 0;
}

在这里插入代码片
/*实现n个多项式相乘*/
#include "stdio.h"
const int N0=20;	//常数: 多项式最多20个

typedef struct node{	//多项式的项(链表节点), 数据包含: 项的系数和指数, 下一项的指针.
	int c, e;			//c-系数(coefficient); e-指数(exponent)
	struct node *next;	//下一个多项式项的指针
}NP;

NP *createPoly(){	//创建一个多项式(对应一个多项式链表)
	int c, e;		//c-系数(coefficient); e-指数(exponent)
	NP *head, *p;	//head-多项式头指针; p-游标指针
	head=p=new NP;	//初始化多项式的 头指针 & 游标指针
	while( true ){
		/*(1)输入(获得)多项式'项'的数据[系数+指数]信息 */
		scanf("%d%d", &c, &e);	//输入多项式项 ==> 根据输入数据的特点: 系数+指数 紧接着出现!
		if( c==0 && e==0 ){	//根据约定, 系数 & 指数 都为0, 则多项式输入结束
			break;
		}else if(c==0){ //此多项式'项'的系数=0, 可以不需要次多项式'项'!
			continue;
		}
		
		/*(2)多项式数据项有效, 则创建 多项式'项'(对应于链表节点)*/
		p->next=new NP;
		p=p->next;
		
		/*(3)维护多项式项的数据信息*/
		p->c=c;
		p->e=e;
	}
	p->next=NULL; //多项式最后一个节点的 "下一个多项式项 指针"为空 ==> 标志为多项式(链表)末尾
	
	return head;  //返回多项式链表的头指针
}

void printPoly( NP *head ){ //打印输出多项式链表
	NP *p=head->next; //p-遍历指针
	while( p ){
		printf("%d %d ", p->c, p->e);
		p=p->next;
	}
	printf("\n");
}

void freePoly( NP *head){ //删除参数(头指针head)指定的多项式, 回收其所占用的内存空间
	NP *p; //p-遍历指针
	while( head ){
		p=head;
		head=head->next;
		delete p;
	}
}

NP *addPoly( NP *ha, NP *hb){ //实现两个多项式相加(需要处理同类项[即指数相同的项]),返回结果多项式的链头指针.
	NP *hc, *pc, *pa=ha->next, *pb=hb->next; //hc,pc-结果多项式的链头和遍历游标指针; pa,pb-两个相加的多项式的遍历游标指针
	int c, e; //c,e-多项式'项'的系数和指数
	hc=pc=new NP; //初始化结果多项式的链头指针hc&遍历游标指针pc
	while( pa || pb ){
		/**(1)获得次数循环的 多项式'项'的: 系数c 和 指数e*/
		if( pa && (pb==NULL || pa->e < pb->e) ){ //(1)若pa'项'存在, 并且[(pa'项'为NULL) 或 (pa'项'的指数小于 pb的指数)], 即只处理pa'项'
			//和的'多项式项' 只包括pa的当前项
			c=pa->c;
			e=pa->e;
			
			pa=pa->next; //移动游标pa至下一个
		}else if( pb && (pa==NULL || pa->e > pb->e) ){ //与(1)类似, 只处理pb'项'
			//和的'多项式项' 只包括pa的当前项
			c=pb->c;
			e=pb->e;
			
			pb=pb->next; //移动游标pb至下一个
		}else{//pa'项' 和 pb'项'都不为空, 且指数相同, 则累加系数
			//和的'多项式项' pa和pb的当前项, 指数不变,系数相加
			c = pa->c + pb->c;
			e = pa->e;
			
			pa = pa->next;	 //移动游标pa至下一个
			pb = pb->next;	 //移动游标pb至下一个
		}
		
		/**(2)根据 多项式'项'的: 系数c 和 指数e, 创建对应节点*/
		if( c ){
			pc->next=new NP; //创建1个新链表节点(多项式'项')
			pc=pc->next; //维护链表节点关系
			
			pc->c=c; //此链表节点(多项式'项')的系数c
			pc->e=e; //此链表节点(多项式'项')的指数e
		}
	}
	pc->next=NULL; //相加结果多项式的链尾指针=NULL
	
	return hc; //返回2个多多项式(链表)相加的结果
}

NP *oneXmulty( NP *pa, NP *hb ){ //pa-某个多项式'项'; hb-一个多项式(多个'项'), 返回pa*ha的结果多项式:头指针
	NP *hc, *pc, *pb=hb->next; //hc-多项式'项'pa 与 多项式hb 相乘的结果:头指针; pc-结果多项式hc的遍历指针; pb-多项式hb的遍历指针;
	
	hc=pc=new NP; //初始化结果多项式hc的头指针hc 和 游标指针pc
	while( pb ){  //遍历多项式hb, 每个'项'pb 都与 多项式'项'pa相乘 ==> 从而获得相乘后的结果多项式
		//(a)新节点创建 & 链表维护
		pc->next=new NP; //当前多项式'项'pb 与 多项式项'pa'相乘的结果'项'(节点)
		pc=pc->next;
		
		//(b)维护相乘多项式'项'(节点)的系数c和指数e
		pc->c=pa->c*pb->c;
		pc->e=pa->e+pb->e;
		
		//(c)移动游标指针 至 多项式hb的下一个多项式'项'(节点)
		pb=pb->next;
	}
	pc->next=NULL; //相乘结果多项式的链尾指针=NULL
	
	return hc;//返回结果多项式的头指针
}

NP *multyXmulty( NP *ha, NP *hb ){ //实现两个多项式ha和hb的相乘, 返回结果多项式hc(链表头指针)
	NP *hc; //hc-ha和hb相乘的结果多项式; t
	NP *pa = ha->next; //pa-第一个多项式ha的遍历指针---> 获得每个多项式'项'(节点)==>以乘于另一个多项式项hb
	NP *t; //t-ha的某个多项式'项'节点 与 另一个多项式hb的乘积=一个多项式t
	
	hc=new NP; //初始化结果多项式hc的: 链头指针
	hc->next=NULL; //初始化结果多项式hc的: 链尾指针
	
	while( pa ){ //若多项式ha存在节点'项'存在, 则(1)此ha的此多项式'项'乘于另一多项式hb; (2)并把结果累加到结果多项式hc
		//(A)ha的当前多项式'项'(节点) 乘于另一多项式hb, 得到一个多项式t
		t=oneXmulty( pa, hb );
		
		//(B)将多项式t累加到最终结果多项式hc中
		hc=addPoly( hc, t);
		
		//(C)多项式ha的下一个节点
		pa=pa->next;
		
		//(D)累加完t, 回收t占用的内存空间
		freePoly( t );
	}
	
	return hc; //返回两个多项式相乘的结果多项式:头指针
}

int main(){
	int n, i; //n-多项式的个数; i-循环控制变量
	NP *hink[N0], *hc, *temp;	//hink[]-待相乘的若干个多项式的头指针; hc-多项式相乘结果头指针;
	
	FILE *fp;
	if((fp=fopen("conv.in", "r")) != NULL ){
		fclose(fp);  //存在的话，要先把之前打开的文件关掉
		
		freopen("conv.in", "r", stdin);
		freopen("conv.out", "w", stdout);
	}
	
	scanf("%d", &n);	//输入多项式的个数n
	//******************************************
	/*(1)创建n个多项式链表*/
	for(i=0;i<n;i++){
		hink[i] = createPoly();	//创建多项式(对应于链表)
	}
	
	/*(2)进行n个多项式相乘*/
	temp=multyXmulty( hink[0], hink[1] );	
	for(i=2;i<n;i++){
		hc = multyXmulty( temp, hink[i]);	//调用函数进行多项式ha &  hb相乘, 结果存储在多项式hc中
		freePoly( temp );	//删除多项式相乘临时结果temp, 回收其所占用的内存空间
		temp = hc;
	}
	hc = temp;
	
	/*(3)输出n个多项式相乘的结果多项式 */
	printPoly( hc ); //打印输出相乘结果多项式
	
	
	/*(4)删除多项式hink[i] 和 hc, 回收其所占用的内存空间 */
	for(i=0;i<n;i++){
		freePoly( hink[i] );
	}
	freePoly( hc );	//删除多项式hc, 回收其所占用的内存空间
	//==========================================
	return 0;
}

在这里插入代码片
/*功 能: 实现n个多项式相乘. 系数为:double型; 指数(次数)为: int型;
 *原 理: 两个多项式的系数f分别存在数组 x[]和y[]中，下标即为次数，*Max表示本多项式最高次数.

 */
#include "stdio.h"
#include "string.h"
const int N0=100;	//常数: 多项式最多N0个

/**
 * 读取数据,多项式的信息存储与数组poly[][]中，最高次数存储于数组exp[]. 注意:一行一个多项式，一个最高次数，共n行.
 */
void getPolynomial(double poly[][N0], int exp[], int n){
	double c;		//c-系数(coefficient); 
	int e, i;		//e-指数(exponent); i-(行)循环控制变量

	for(i=0; i<n; i++){ //输入n个多项式的信息(1行对应一个多项式, 长短不一)
		int maxExp=0; //多项式最高次数(指数)
		/*(1)获得多项式的系数和指数信息, 同时收集(更新)最高指数的信息*/
		while( true ){
			scanf("%lf%d", &c, &e);	//输入多项式项 ==> 根据输入数据的特点: 系数+指数 紧接着出现!
			//printf("c=%.3lf, e=%d; ", c, e);

			if( c==0 && e==0 ){	//根据约定, 系数 & 指数 都为0, 则多项式输入结束
				break;
			}
			
			poly[i][e] = c; //更新下标为e的多项式项的系数，下标e即为次数e
			
			if(e > maxExp){ //若有更高次数,则更新最高次数
				maxExp = e;
			}		
		}

		/*(2)记录当前多项式(第i个多项式)的最高指数信息*/
		exp[i] = maxExp;
		//printf("--->maxExp=%d \n", maxExp);
	}
}

/**
 *两个多项式x和y(系数分别存在x[]和y[]中，下标即为次数)相乘, 结果存储在result(也是一个多项式)中, *Max表示本多项式的最高次数.
 */
int polyMultiply(double x[], int xMax, double y[], int yMax, double result[], int *resultMax) {
    int i=0, k=0;
	
    *resultMax = xMax + yMax;//获取最新的最高次数
    memset(result, 0, (1+*resultMax)*sizeof(double));
	
    for(i=0; i<=xMax; i++) {//两个多项式相乘    
        for(k=0; k<=yMax; k++) {//下标即为变量的次数
            result[i+k] += x[i] * y[k];
        }
    }
	
    //运算完成后,result[]即为结果的系数,其下标为次数; (*resultMax)即为result[]的最高次数	
    return 0;
}

/**
 *打印输出一个多项式的信息
 */
void printPolynomial(double poly[], int maxExp){ 
	int j; //j-循环控制变量
	for(j=0; j<=maxExp; j++){
		if(poly[j] != 0 ){//系数不为0, 则输出多项式'项'的系数poly[j] & 指数j. 否则, 不输出!
			printf("%.3lf %d ", poly[j], j);
		}
	}
	printf("\n"); //输出一个多项式后换行
}

int main(){
	int n, i; //n-多项式的个数; i-循环控制变量
	double polyNomial[N0][N0]={0}; //polyNomial - n个多项式, 每行1个多项式,长短不一
	int polyExponent[N0]; //polyExponent - n个多项式之每个多项式的最高指数
	
	double rsPolyNomial[N0] = {0}; //rsPolyNomial - 多项式相乘的结果, 所有元素的初始值皆为0
	double tempPoly[N0] = {0}; //tempPoly - 多于2个多项式相乘时, 用于存储相乘结果的临时数组(对应于一个多项式), 所有元素的初始值皆为0
	int rsPolyExponent, tempExp; //rsPolyExponent - 多项式相乘结果的最高指数(exponent)
	
	FILE *fp;
	if((fp=fopen("conv.in", "r")) != NULL ){
		fclose(fp);  //存在的话，要先把之前打开的文件关掉
		
		freopen("conv.in", "r", stdin);
		freopen("conv.out", "w", stdout);
	}
	
	scanf("%d", &n);	//输入多项式的个数n
	if(n<2 || n>30){
		printf("输入的多项式数目少于2 或 超过最大数目30个!\n");
		return 1;
	}
	//******************************************
	/*(1)读取多项式数据信息(预处理 获得每个多项式的最高次数(指数))*/
	getPolynomial(polyNomial, polyExponent , n);
	for(i=0; i<n; i++)	printPolynomial(polyNomial[i], polyExponent[i]); //输出各多项式的信息

	/*(2)进行n个多项式相乘*/
	polyMultiply( polyNomial[0], polyExponent[0], polyNomial[1], polyExponent[1], rsPolyNomial, &rsPolyExponent);
	for(i=2; i<n; i++){
		/*(A)将两个多项式相乘的临时结果(也是多项式)-rsPolyNomial, 拷贝到临时空间tempPoly*/
		/**(A1)方法1*/
		memcpy(tempPoly, rsPolyNomial, (1+rsPolyExponent)*sizeof(double));//从源src所指的内存地址的起始位置开始拷贝n个字节到目标dest所指的内存地址的起始位置中
		/**(A1)方法2*/
		// for(int j = 0; j<=rsPolyExponent; j++){
		//	tempPoly[j] = rsPolyNomial[j];
		// 	}
		tempExp = rsPolyExponent; 

		/*(B)再次使用数组之前,要先把其中的数据清空 --> 这个工作统一在多项式相乘函数polyMultiply(...)中做 */
		//memset(rsPolyNomial, 0, (1+rsPolyExponent)*sizeof(int));

		/*(C)两个多项式相乘的结果与另一个多项式polyNomial[i] 相乘*/
		polyMultiply(tempPoly, tempExp, polyNomial[i], polyExponent[i], rsPolyNomial, &rsPolyExponent);
	}
	
	/*(3)输出n个多项式相乘的结果多项式rsPolyNomial */
	printPolynomial( rsPolyNomial, rsPolyExponent);

	//==========================================
	return 0;
}

在这里插入代码片
/*功 能: 实现n个多项式相乘. 系数为:int型; 指数(次数)为: int型【指数不能为负】;
 *原 理: 两个多项式的系数f分别存在数组 x[]和y[]中，下标即为次数，*Max表示本多项式最高次数.

 */
#include "stdio.h"
#include "string.h"
const int N0=100;	//常数: 多项式最多N0个

/**
 * 读取数据,多项式的信息存储与数组poly[][]中，最高次数存储于数组exp[]. 注意:一行一个多项式，一个最高次数，共n行.
 */
void getPolynomial(int poly[][N0], int exp[], int n){
	int c, e, i;		//c-系数(coefficient); e-指数(exponent); i-(行)循环控制变量

	for(i=0; i<n; i++){ //输入n个多项式的信息(1行对应一个多项式, 长短不一)
		int maxExp=0; //多项式最高次数(指数)
		/*(1)获得多项式的系数和指数信息, 同时收集(更新)最高指数的信息*/
		while( true ){
			scanf("%d%d", &c, &e);	//输入多项式项 ==> 根据输入数据的特点: 系数+指数 紧接着出现!
			//printf("c=%d, e=%d; ", c, e);

			if( c==0 && e==0 ){	//根据约定, 系数 & 指数 都为0, 则多项式输入结束
				break;
			}
			
			poly[i][e] = c; //更新下标为e的多项式项的系数，下标e即为次数e
			
			if(e > maxExp){ //若有更高次数,则更新最高次数
				maxExp = e;
			}		
		}

		/*(2)记录当前多项式(第i个多项式)的最高指数信息*/
		exp[i] = maxExp;
		//printf("--->maxExp=%d \n", maxExp);
	}
}

/**
 *两个多项式x和y(系数分别存在x[]和y[]中，下标即为次数)相乘, 结果存储在result(也是一个多项式)中, *Max表示本多项式的最高次数.
 */
int polyMultiply(int x[], int xMax, int y[], int yMax, int result[], int *resultMax) {
    int i=0, k=0;
	
    *resultMax = xMax + yMax;//获取最新的最高次数
    memset(result, 0, (1+*resultMax)*sizeof(int));
	
    for(i=0; i<=xMax; i++) {//两个多项式相乘    
        for(k=0; k<=yMax; k++) {//下标即为变量的次数
            result[i+k] += x[i] * y[k];
        }
    }
	
    //运算完成后,result[]即为结果的系数,其下标为次数; (*resultMax)即为result[]的最高次数	
    return 0;
}

/**
 *打印输出一个多项式的信息
 */
void printPolynomial(int poly[], int maxExp){ 
	int j; //j-循环控制变量
	for(j=0; j<=maxExp; j++){
		if(poly[j] != 0 ){//系数不为0, 则输出多项式'项'的系数poly[j] & 指数j. 否则, 不输出!
			printf("%d %d ", poly[j], j);
		}
	}
	printf("\n"); //输出一个多项式后换行
}

int main(){
	int n, i; //n-多项式的个数; i-循环控制变量
	int polyNomial[N0][N0]={0}; //polyNomial - n个多项式, 每行1个多项式,长短不一
	int polyExponent[N0]; //polyExponent - n个多项式之每个多项式的最高指数
	
	int rsPolyNomial[N0] = {0}; //rsPolyNomial - 多项式相乘的结果, 所有元素的初始值皆为0
	int tempPoly[N0] = {0}; //tempPoly - 多于2个多项式相乘时, 用于存储相乘结果的临时数组(对应于一个多项式), 所有元素的初始值皆为0
	int rsPolyExponent, tempExp; //rsPolyExponent - 多项式相乘结果的最高指数(exponent)
	
	FILE *fp;
	if((fp=fopen("conv.in", "r")) != NULL ){
		fclose(fp);  //存在的话，要先把之前打开的文件关掉
		
		freopen("conv.in", "r", stdin);
		freopen("conv.out", "w", stdout);
	}
	
	scanf("%d", &n);	//输入多项式的个数n
	if(n<2 || n>30){
		printf("输入的多项式数目少于2 或 超过最大数目30个!\n");
		return 1;
	}
	//******************************************
	/*(1)读取多项式数据信息(预处理 获得每个多项式的最高次数(指数))*/
	getPolynomial(polyNomial, polyExponent , n);
	//for(i=0; i<n; i++)	printPolynomial(polyNomial[i], polyExponent[i]); //输出各多项式的信息

	/*(2)进行n个多项式相乘*/
	polyMultiply( polyNomial[0], polyExponent[0], polyNomial[1], polyExponent[1], rsPolyNomial, &rsPolyExponent);
	for(i=2; i<n; i++){
		/*(A)将两个多项式相乘的临时结果(也是多项式)-rsPolyNomial, 拷贝到临时空间tempPoly*/
		/**(A1)方法1*/
		memcpy(tempPoly, rsPolyNomial, (1+rsPolyExponent)*sizeof(int));//从源src所指的内存地址的起始位置开始拷贝n个字节到目标dest所指的内存地址的起始位置中
		/**(A1)方法2*/
		// for(int j = 0; j<=rsPolyExponent; j++){
		//	tempPoly[j] = rsPolyNomial[j];
		// 	}
		tempExp = rsPolyExponent; 

		/*(B)再次使用数组之前,要先把其中的数据清空 --> 这个工作统一在多项式相乘函数polyMultiply(...)中做 */
		//memset(rsPolyNomial, 0, (1+rsPolyExponent)*sizeof(int));

		/*(C)两个多项式相乘的结果与另一个多项式polyNomial[i] 相乘*/
		polyMultiply(tempPoly, tempExp, polyNomial[i], polyExponent[i], rsPolyNomial, &rsPolyExponent);
	}
	
	/*(3)输出n个多项式相乘的结果多项式rsPolyNomial */
	printPolynomial( rsPolyNomial, rsPolyExponent);

	//==========================================
	return 0;
}

#include<stdio.h>
#include<stdlib.h>
typedef struct node* list;
struct node
{
	double coef;
	int expon;
	list next;
};
list create()                                                    //创建 
{
	int n;
	printf("输入多项式的项数:");
	scanf("%d", &n);
	printf("输入多项式的系数和指数(空格为界):");
	list head = (list)malloc(sizeof(struct node)), now = head, last;
	for (; n--; now = last)
	{
		last = (list)malloc(sizeof(struct node));
		scanf("%lf%d", &last->coef, &last->expon);
		now->next = last;
	}
	now->next = NULL;
	return head;
}
list mul(list a, list b)                                         //相乘 
{
	list head = (list)malloc(sizeof(struct node)), now = head, last;
	for (list i = a->next; i != NULL; i = i->next)for (list j = b->next; j != NULL; j = j->next)
	{
		last = (list)malloc(sizeof(struct node));
		last->coef = i->coef * j->coef;                         // 系数
		last->expon = i->expon + j->expon;                      // 指数
		now->next = last;
		now = last;
	}
	now->next = NULL;
	return head;
}
void sort(list a)                                              //排序并且将expon相同的合并 
{
	if (a->next == NULL || a->next->next == NULL)return;
	list r = a, i;
	while (r->next->next != NULL)r = r->next;
	for (; 1; r = i)
	{
		if (r != a)
			for (i = a; 1; i = i->next)
			{
				list j = i->next, k = j->next;
				if (j->expon < k->expon)
				{
					if (j == r)r = k;
					else if (k == r)r = j;
					i->next = k, j->next = k->next, k->next = j;
				}
				if (i->next == r)break;
			}
		if (r->next->next != NULL)
		{
			list j = r->next, k = j->next;
			if (j->expon == k->expon)j->coef += k->coef, j->next = k->next;
		}
		if (r == a)break;
	}
}
void show(list a)                                               //输出 
{
	list i = a->next;
	if (i != NULL)
	{
		printf("%g*x^%d", i->coef, i->expon);
		for (i = i->next; i != NULL; i = i->next)if (i->coef)
		{
			if (i->coef > 0)putchar('+');
			printf("%g*x^%d", i->coef, i->expon);
		}
	}
	putchar('\n');
	return;
}
int main()
{
	list a = create(), b = create(), c = mul(a, b);
	show(a);
	show(b);
	sort(c);
	show(c);
	return 0;
}

概述

一元多项式A，B按降次排列，用带头结点的链表存储，求C = A * B

思路

暑假的时候写过多项式A,B相加的，那个比较简单。这个要相乘，那就必须把A中的每一项分别和B中的每一项相乘。
所以就是，A中的每一项分别和B中的所有相乘，得到一个链表，然后把所有链表相加？感觉能做，但是好麻烦啊。有没有更简单的做法呢？
去网上搜索，emmm，快速傅里叶变换？快速数论变换？dbq我数学真的太菜了
具体分析一下，应该需要一个能通过输入创建链表的函数，删除链表的函数，多项式相加的函数，多项式与单项式相乘的函数，输出多项式的函数。
因为会有新创建链表，插入链表什么的，所以这里用链式存储结构比较方便。

cpp

全部

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <cstddef>
using namespace std;
typedef struct lnode{
	int coef;
	int exp;
	struct lnode* next;
}lnode, *poly;
void create_polyn(poly &h);//创建一个多项式 
void print_polyn(poly h);//打印一个多项式 
void destroy_polyn(poly h);//删除多项式 
poly multiply_polyn(poly h, int num, int exp);//单项式多项式相乘 
poly polyn_add(poly h1, poly h2);//多项式相加 
poly polyn_polyn(poly h1, poly h2);//多项式多项式相乘 
int main()
{
	poly h1 = NULL, h2 = NULL, h3 = NULL;
	//输入两个多项式 
	create_polyn(h1);
	create_polyn(h2);
	//多项式相乘 
	h3 = polyn_polyn(h1, h2);
	//输出结果 
	print_polyn(h3);
	//释放空间 
	destroy_polyn(h3);
	return 0;
}
void create_polyn(poly &h)
{
	cout<<"请输入多项式："<<endl;
	int coef, exp;
	h = new lnode;
	poly tem, last = h;
	cin>>coef>>exp;
	//都为0时结束输入 
	while(coef || exp){
		tem = new lnode;
		tem->coef = coef;
		tem->exp = exp;
		last->next = tem;
		last = tem;
		cin>>coef>>exp;
	}
	last->next = NULL;
}
void print_polyn(poly h)
{
	cout<<"多项式：";
	if(h == NULL || h->next == NULL)
	{
		cout<<"0"<<endl;
		return ;
	}
	h = h->next;
	while(h){
		cout<<" "<<h->coef<<"x^"<<h->exp<<" ";
		h = h->next;
		if(h)
		{
			cout<<"+";
		}
	}
	cout<<endl;
}
void destroy_polyn(poly h)
{
	poly tem;
	while(h)
	{
		tem = h;
		h = h->next;
		delete tem;
		tem = NULL;//这一步很重要一定要有 
	}
} 
poly multiply_polyn(poly h, int num, int exp)
{
	poly ne = NULL, last = NULL, tem = NULL;
	ne = new lnode;
	last = ne;//这一步必须放在给ne分配内存后，否则last = NULL 
	if(h == NULL) return ne;
	h = h->next;
	while(h)
	{
		tem = new lnode;
		tem->coef = num * h->coef;
		tem->exp = h->exp + exp;
		
		last->next = tem;
		last = tem;
		h = h->next;
	}
	last->next = NULL;//别忘了这个！！！！！ 
	return ne;
}
poly polyn_add(poly h1, poly h2)
{
	
	poly ne = NULL, last = NULL, tem = NULL ,tem1 = h1, tem2 = h2;
	ne = new lnode;
	last = ne;
	
	if(h1) h1 = h1->next;
	if(h2) h2 = h2->next;
	
	delete tem1;
	delete tem2;
	
	while(h1 && h2)
	{
		
		if(h1->exp > h2->exp)
		{
			last->next = h1;
			last = h1;
			h1 = h1->next;
		}
		else if(h1->exp < h2->exp)
		{
			last->next = h2;
			last = h2;
			h2 = h2->next;
		}
		else
		{
			tem = new lnode;
			tem1 = h1;
			tem2 = h2;
			tem->coef = h1->coef + h2->coef;
			tem->exp = h1->exp;
			delete tem1;
			delete tem2;
			h1 = h1->next;
			h2 = h2->next;
			last->next = tem;
			last = tem;
		}
	}
	if(last) last->next = NULL;
	if(h1 == NULL)
	{
		last->next = h2;
	}
	if(h2 == NULL)
	{
		
		last->next = h1;
	}
	return ne;
}
poly polyn_polyn(poly h1, poly h2)
{
	poly h = NULL, result = NULL;
	h1 = h1->next;
	result = new lnode;
	result->next = NULL;
	int num, exp;
	if(h2 == NULL) return result;
	
	while(h1)
	{
		
		num = h1->coef;
		exp = h1->exp;
		h = multiply_polyn(h2, num, exp);//单项式多项式相乘
		result = polyn_add(result, h);//结果加在结果链表中 
		
		h1 = h1->next;
	}
	return result;
}
/*
 测试用例
1.
0 0
3 2
0 0
2.
9 8
6 5
0 0
3 2 
2 1
0 0
answer:27x^10 + 18x^9 + 18x^7 + 12x^6
3.
3 2
0 0
0 0
answer:0
4.
1 2
2 1
1 0
0 0
1 1
1 0
0 0
answer: 1x^3 + 3x^2 + 3x^1 + 1x^0 
5.
-8 40
1 20
0 0
0 0 
answer: 0
6.
6 5
5 4
8 3
3 2
2 0
0 0
2 3
4 0
5 -1
0 0
*/

创建多项式

void create_polyn(poly &h)
{
	cout<<"请输入多项式："<<endl;
	int coef, exp;
	h = new lnode;
	poly tem, last = h;
	cin>>coef>>exp;
	//都为0时结束输入 
	while(coef || exp){
		tem = new lnode;
		tem->coef = coef;
		tem->exp = exp;
		last->next = tem;
		last = tem;
		cin>>coef>>exp;
	}
	last->next = NULL;
}

打印多项式

void print_polyn(poly h)
{
	cout<<"多项式：";
	if(h == NULL || h->next == NULL)
	{
		cout<<"0"<<endl;
		return ;
	}
	h = h->next;
	while(h){
		cout<<" "<<h->coef<<"x^"<<h->exp<<" ";
		h = h->next;
		if(h)
		{
			cout<<"+";
		}
	}
	cout<<endl;
}

删除多项式

void destroy_polyn(poly h)
{
	poly tem;
	while(h)
	{
		tem = h;
		h = h->next;
		delete tem;
		tem = NULL;//这一步很重要一定要有 
	}
} 

单项式乘多项式

poly multiply_polyn(poly h, int num, int exp)
{
	poly ne = NULL, last = NULL, tem = NULL;
	ne = new lnode;
	last = ne;//这一步必须放在给ne分配内存后，否则last = NULL 
	if(h == NULL) return ne;
	h = h->next;
	while(h)
	{
		tem = new lnode;
		tem->coef = num * h->coef;
		tem->exp = h->exp + exp;
		
		last->next = tem;
		last = tem;
		h = h->next;
	}
	last->next = NULL;//别忘了这个！！！！！ 
	return ne;
}

两个多项式相加

poly polyn_add(poly h1, poly h2)
{
	
	poly ne = NULL, last = NULL, tem = NULL ,tem1 = h1, tem2 = h2;
	ne = new lnode;
	last = ne;
	
	if(h1) h1 = h1->next;
	if(h2) h2 = h2->next;
	
	delete tem1;
	delete tem2;
	
	while(h1 && h2)
	{
		
		if(h1->exp > h2->exp)
		{
			last->next = h1;
			last = h1;
			h1 = h1->next;
		}
		else if(h1->exp < h2->exp)
		{
			last->next = h2;
			last = h2;
			h2 = h2->next;
		}
		else
		{
			tem = new lnode;
			tem1 = h1;
			tem2 = h2;
			tem->coef = h1->coef + h2->coef;
			tem->exp = h1->exp;
			delete tem1;
			delete tem2;
			h1 = h1->next;
			h2 = h2->next;
			last->next = tem;
			last = tem;
		}
	}
	if(last) last->next = NULL;
	if(h1 == NULL)
	{
		last->next = h2;
	}
	if(h2 == NULL)
	{
		
		last->next = h1;
	}
	return ne;
}

多项式相乘

poly polyn_polyn(poly h1, poly h2)
{
	poly h = NULL, result = NULL;
	h1 = h1->next;
	result = new lnode;
	result->next = NULL;
	int num, exp;
	if(h2 == NULL) return result;
	
	while(h1)
	{
		
		num = h1->coef;
		exp = h1->exp;
		h = multiply_polyn(h2, num, exp);//单项式多项式相乘
		result = polyn_add(result, h);//结果加在结果链表中 
		
		h1 = h1->next;
	}
	return result;
}

测试用例

1.
0 0
3 2
0 0
2.
9 8
6 5
0 0
3 2 
2 1
0 0
answer:27x^10 + 18x^9 + 18x^7 + 12x^6
3.
3 2
0 0
0 0
answer:0
4.
1 2
2 1
1 0
0 0
1 1
1 0
0 0
answer: 1x^3 + 3x^2 + 3x^1 + 1x^0 
5.
-8 40
1 20
0 0
0 0 
answer: 0
6.
6 5
5 4
8 3
3 2
2 0
0 0
2 3
4 0
5 -1
0 0

注意

注意先判断指针是否为空，在指针->next = NULL。
规定好创建指针的时候，若输入0 0则指针->next = NULL，而不是头指针为NULL.头指针只有出错的时候才为NULL。