多项式求解思路

这里的每一项对应单向链表的一个结点，这个结点包含三个变量:系数、指数、指针(指向下一项)，按照指数递降的顺序串在一起。

如果是加法运算，那么找到指数相等的，系数相加。

如果是乘法运算，那么每一项相乘，系数相乘，指数相加。

多项式的关键信息:非零项的系数和指数，这种线性队列有两种在计算机上面存储实现方式:第一种是数组，另一种是链表，链表克服了数组需要事先确定数组大小的特点。

/*
多项式的链表数据结构表示
*/
struct PolyNode{
	//系数
	int coefficient;
	//指数
	int exponent;
	//指向下一个结点的指针
	struct PolyNode *link;
};
typedef struct PolyNode *Polynomial;
Polynomial P1,P2;

多项式程序框架搭建

步骤:

读入多项式1、

读入多项式2、

乘法运算并输出、

加法运算并输出。

#include<stdio.h>
/*
多项式的程序框架搭建
*/
int main(void){
	/*
	链表
	*/
	Polynomial P1, P2, PP, PS;
	/*
	读入多项式
	*/
	P1 = ReadPoly();
	P2 = ReadPoly();
	/*
	多项式相乘
	PP为指针
	*/
	PP = Mult(P1,P2);
	/*
	多项式输出
	*/
	PrintPoly(PP);
	/*
	多项式相加
	PS为指针
	*/
	PS = Add(P1,P2);
	/*
	多项式输出
	*/
	PrintPoly(PS);

	return 0;
}

读入多项式

/*
如何读入多项式
*/
Polynomical ReadOnly(){
	......
	scanf("%d",&N);
	......
	while(N--){
		scanf("%d %d", &c, &e);
		Attach(c,e,&Rear);
	}
	......
	return P;
}

此串数字，第一项4代表一共多少项，接下来是一对对的系数指数，所指向的这个链表。

那么这里的关键问题是，读的时候从左到右，从高指数向低指数读取，然后插入到上述的链表中。

在链表中，按照指数递降排序，在插入数据时候，要插入到链表的最后方，那么如果要读入一个新的结点能插入到最后一项的后面，需要一个pRear指针指向当前结果多项式的最后一项，通过函数Attach来完成，最后pRear要指到新的结点。

关于pRear的初值是多少?两种处理方法:

第一种:pRear初值为NULL，在Attach函数中根据pRear是否为NULL做不同处理。

第二种:pRear指向一个空结点，到最后，必须把这个空结点删除。

/*
如何读入多项式
*/
Polynomical ReadOnly(){
	Polynomical P, Rear, t;
	int c,e,N;
	scanf("%d",&N);
	/*
	链表头空结点
	*/
	P = (Polynomical)malloc(sizeof(struct PolyNode));
	P->link = NULL;
	Rear = P;
	while(N--){
		scanf("%d %d", &c, &e);
		/*
		将当前项插入多项式尾部
		*/
		Attach(c,e,&Rear);
	}
	t = P;
	//P指向下一个结点
	P = P->link;
	/*
	删除临时生成的头结点
	*/
	free(t);
	return P;
}

/*
如何读入多项式
c系数
e指数
Polynomial *pRear	最后一个结点的指针位置(*pRear指针的指针.C语言是函数常数值传递.)
*/
void Attach(int c, int e,Polynomial *pRear){
	/*
	由于在本函数中需要改变当前结果表达式尾项指针的值,
	所以函数传递进来的是结点指针的地址,*pRear指向尾项。
	*/
	Polynomial P;
	/*
	申请新结点
	*/
	P = (Polynomial)malloc(sizeof(struct PolyNode));
	/*
	对新结点赋值
	*/
	P->coefficient = c;
	P->exponent = e;
	P->link = NULL;

	/*
	最后两个语句:
	将(新申请的结点)P指向的新结点插入到当前结果表达式尾项rear的后面。
	要注意*pRear是指针。
	*/
	(*pRear)->link = P;
	/*
	修改pRear的值
	最后一个结点的指针位置就是新结点P的位置
	*/
	*pRear = P;
}

两多项式相加

/*
多项式的加法运算
*/
struct PolyNode{
	//系数
	int coefficient;
	//指数
	int exponent;
	//指向下一个结点的指针
	struct PolyNode *link;
};
typedef struct PolyNode *Polynomial;
Polynomial P1,P2;

这里的每一项对应单向链表的一个结点，这个结点包含三个变量:系数、指数、指针(指向下一项)，按照指数递降的顺序串在一起，找到指数相等的，系数相加。

P1和P2中某两项的指数相同，则二者做加减，指数不同，那么P1或P2直接存入结果多项式，P1或P2指向下一项，如果P2空了，那么就把P1后面的所有项都接到结果多项式的后面。

/*
多项式的加法运算实现
对于多项式来讲,要知道多项式的头结点与尾结点的位置。
*/
Polynomial PolyAdd(Polynomial P1, Polynomial P2){

	Polynomial front, rear, temp;
	int sum;
	/*
	为方便表头插入,先产生一个临时空结点作为结果多项式链表头
	*/
	rear = (Polynomial)malloc(sizeof(struct PolyNode));
	/*
	由front记录结果多项式链表头结点
	*/
	front = rear;
	/*
	当两个多项式都有非零项待处理时(二者都不为空)
	*/
	while(P1 && P2){
		/*
		比较两个指数的大小
		*/
		switch(Compare(P1->exponent,P2->exponent)){
			/*
			P1中的数据项指数较大
			*/
			case 1:
				Attach(P1->coefficient,P1->exponent,&rear);
				P1 = P1->link;
				break;
			/*
			P2中的数据项指数较大
			*/
			case -1:
				Attach(P2->coefficient,P2->exponent,&rear);
				P2 = P2->link;
				break;
			/*
			P1和P2中的数据项指数较大相等
			*/
			case 0:
				//系数相加
				sum = P1->coefficient + P2->coefficient;
				//不等于0就把结果加到多项式中去
				if(sum){
					Attach(sum, P1->exponent, &rear);
				}
				P1 = P1->link;
				P2 = P2->link;
				break;
		}
	}
	/*
	将未处理完的另一个多项式的所有结点依次复制到结果多项式中去
	这俩FOR循环做完,就意味着两个相加基本完成了。
	有一个是空的,就要把另外一个后面剩余的项全部接到多项式的后面。
	*/
	/*
	第一个for循环:处理P1不空,如果P1不空,那么P2肯定空了。
	P1不空,就是把P1后面的每一项全部attach,同时P1往后挪。
	*/
	for(;P1;P1 = P1->link){
		Attach(P1->coefficient, P1->exponent, &rear);
	}
	/*
	第二个for循环:处理P2不空,如果P2不空,那么P1肯定空了。
	P2不空,就是把P2后面的每一项全部attach,同时P2往后挪。
	*/
	for(;P2;P2 = p2->link){
		Attach(P2->coefficient, P2->exponent, &rear);
	}
	/*
	做函数返回之前的扫尾工作
	rear指向结果多项式的最后一项,现在加完了,那么最后一项就没了,那么释放掉NULL空结点。
	*/
	rear->link = NULL;
	temp = front;
	/*
	将front指向结果多项式第一个非零项。
	front往后挪,front原来是指向这个临时结点的表头结点,
	这个表头结点的下一项就是真正的多项式的第一项。
	*/
	front = front->link;
	/*
	释放临时空表头结点
	*/
	free(temp);
	/*
	return的是这个结果多项式/单向链表的第一个结点
	*/
	return front;
}

两多项式相乘

/*
多项式相乘模板
*/
Polynomial Mult(Polynomial P1,Polynomial P2){
	......
	t1 = P1;
	t2 = P2;
	......
	/*
	先用P1的第一项乘以P2,得到P2。
	*/
	while(t2){
		......
	}
	t1 = t1->link;
	while(t1){
		t2 = P2;
		Rear = P;
		while(t2){
			e = t1->expon + t2->expon;
			c = t1->coef * t2->coef;
			......
			t2 = t2->link;
		}
		t1 = t1->link;
	}
	......

}

/*
多项式相乘案例
*/
Polynomial Mult(Polynomial P1,Polynomial P2){

	Polynomial P,t1,t2,t;
	int c,e;

	if(!P1 || !P2){
		return NULL;
	}
	t1 = P1;
	t2 = P2;
	P = (Polynomial)malloc(sizeof(struct PolyNode));
	P->link = NULL;
	Rear = P;

	while(t2){
		/*
		先用P1的第一项乘以P2,得到P.
		*/
		Attach(t1->coefficient * t2->coefficient, t1->exponent + t2.exponent, &Rear);
		t2 = t2->link;
	}
	t1 = t1->link;
	/*
	如何插入某结点
	*/
	while(t1){
		t2 = P2;
		Rear = P;
		while(t2){
			e = t1->exponent + t2->exponent;
			c = t1->coefficient * t2->coefficient;
			while(Rear->link && Rear->link->exponent > e){
				Rear = Rear->link;
			}
			/*
			指向要插入的结点的后面
			*/
			if(Rear->link && Rear->link->exponent == e){
				if(Rear->link->coefficient + c){
					Rear->link->coefficient += c;
				}else{
					t = Rear->link;
					Rear->link = t->link;
					free(t);
				}
			}else{
				t = (Polynomial)malloc(sizeof(struct PolyNode));
				t->coefficient = c;
				t->exponent = e;
				t->link = Rear->link;
				Rear->link = t;
				Rear = Rear->link;
			}
		}
		t1 = t1->link;
	}
	/*
	释放临时结点并重新指针指向
	*/
	t2 = P;
	P = P->link;
	free(t2);

	return P;

}

多项式输出

/*
多项式输出模板
*/
void PrintPoly(Polynomial P){
	/*
	输出多项式
	*/
	......
	while(P){
		......
		P = P->link;
	}
	......
}

/*
多项式输出案例
无论相加还是相乘,都有一个指针指向这个多项式的第一个结点。
这实际上是一个链表的遍历问题。
输出案例:
5 20空格-4 4空格-5 2空格9 1空格-2 0
系数指数空格
如何控制这么一个过程?
那么可以倒过来理解,可以把其理解成每一项都是空格系数指数,第一项没有空格除外(flag=1标识)。
*/
void PrintPoly(Polynomial P){
	/*
	输出多项式
	*/
	int flag = 0;//辅助调整输出格式使用
	if(!P){
		print("0 0\n");
		return;
	}
	while(P){
		if(!flag){
			flag = 1;
		}else{
			print(" ");
		}
		printf("%d %d",P->coefficient,P->exponent);
		P = P->link;
	}
	print("\n");
}

小总结