一元多项式的相加及相乘

突然感觉时间好少啊，花了这么多时间训练希望最终能有不错的成绩⛽

大致思路：

要实现的是先输入两个一元多项式，然后输出这两个式子并且把两个式子相加和相乘，并输出结果

实验最大难点就在于插入函数和合并同类项函数怎么写，首先当插入的这个结点指数和表达式中某个项的指数相同，则只需要累加一下即可，判断表达式中是否存在一个项的指数和要插入的相同(LocateElem)，若没有则需要找到一个位置使得插入后指数从前往后还是递增的(Orderinsert)，有了这两个函数创建链表就很容易了

所谓相加，本质就是合并同类相，先把La中的元素移到Lc中，然后把Lb中的元素一个一个插入到Lc中，即得到了相加后的结果

所谓相乘，可以遍历两个表达式，两两结合，系数相乘，指数相加，得到的结果插入到L4中，最后即可得到答案

坑点

记得初始化链表时一定要先分配一个头节点，不然程序直接死了

全代码

#include <bits/stdc++.h>
using namespace std;
typedef bool Status;
struct term{
	double coef;
	int expn;
};
typedef struct Lnode{
	term data;
	Lnode *next;
}*Link,*Linklist;
//比较函数，返回a和b的指数大小比较结果 
Status comp(term a,term b){ 
	if(a.expn==b.expn) return 0;
	return a.expn-b.expn;
}

void Delnext(Link pre){  //删除pre指向的结点 
	Link tmp=pre->next;
	pre->next=tmp->next;
	free(tmp);
}
// 判断链表中是否有和e项相同的指数项，有返回1，没有返回0 
Status LocateElem(Linklist L,term e,Link &pre,Link &now){
	pre=L;
	now=pre->next;
	while(now && comp(e,now->data)){ //若该结点的指数和e的指数不同则遍历下一个结点 
		pre=now;
		now=now->next;
	} 
	if(!now) return 0; //若链表中每元素了就说明没有相同的 
	else return 1;
}
// 当链表中没有和e项指数相同的项时，找到这个项应该插入的位置，并插入 
void Orderinsert(Linklist &L, term e){
	Link pre,now,o;
	pre=L;  //pre是now的上一个指针 
	now=pre->next;
	while(now && now->data.expn<e.expn){  //若当前结点的指数小于要插入的结点指数就继续遍历 
		pre=now;
		now=now->next;
	}
	o=new Lnode;  //找到第一个大于要插入结点的指数的位置，并插入 
	o->data=e;
	o->next=now;
	pre->next=o;
}
//  将一个项插入链表中，并进行同类型合并 
void Orderinsertmerge(Linklist &L,term e){
	Link pre,now;
	if(LocateElem(L,e,pre,now)){ //若当前表达式中已经有和这个指数相同的项了就累加 
		now->data.coef+=e.coef;  //相同指数项系数累加 
		if(!(now->data.coef)){  //若累加后系数为0，则直接删除这个结点 
			Delnext(pre);
		}
	} else Orderinsert(L,e);  //没有相同的指数项，就维护表达式从前往后指数递增的特性，找到位置并插入 
}
//  新建一个表达式，存在链表中 
void Creatpolyn(Linklist &p,int num){
	printf("\n[Tips]: 请输入%d个系数和指数用空格符间隔\n",num);
	term e;
	p=new Lnode; //创建一个链表头结点 
	p->next=NULL; 
	for(int i=1;i<=num;i++){
		scanf("%lf%d",&e.coef,&e.expn);
		if(!e.coef) continue;  //若系数为0则无意义 
		Orderinsertmerge(p,e);
	}
}
//  输出表达式的系数指数 
void printpolyn(Linklist p) {
	Link q;
	q=p->next;
	printf("-------------------------\n");
	printf("    系数\t指数\n");
	while(q) {
		printf("    %.2f\t%d\n",q->data.coef,q->data.expn);
		q=q->next;
	}
	printf("-------------------------\n");
}
//  将La链表拷贝到Lb中 
void copy(Linklist La, Linklist &Lb) {
	La=La->next;
	Lb=new Lnode;  //创建Lb链表的头节点 
	Lb->next=NULL;
	while(La) {
		Orderinsert(Lb, La->data);  //把当前La结点的数据插入到Lb中 
		La=La->next;	
	}
}
//  打印表达式 
void PrintList(Linklist L) { 
	if(!L->next) { //若链表为空则直接输出0 
		printf("0\n");
		printf("*************************************************\n");
		return ;
	}
	Linklist q;
	q=L->next;
	while(q->next) {  //因为要保持输出格式，要判断当前元素是否为最后一个元素，如不是则还需要输出符号，否则不需要 
		if(!(q->data.expn)) {  //若当前元素指数为0，则不能输出x 
			if((q->next->data.coef>0)) printf("%.2f + ",q->data.coef);  //若下一个元素的符号是正则需要+ 
			else printf("%.2f  ",q->data.coef);  //若下一个元素的符号是负则需要- 
		} else {  //若指数不为0则还需要输出x 
			if((q->next->data.coef>0)) printf("%.2f X^ %d + ",q->data.coef,q->data.expn); //同上一个if 
			else printf("%.2f X^ %d  ",q->data.coef,q->data.expn);
		}
		q=q->next;
	}
	if(!(q->data.expn)) printf("%.2f \n",q->data.coef);  // 输出最后一个元素 
	else printf("%.2f x^ %d\n",q->data.coef,q->data.expn);
	printf("*************************************************\n");
}
//  La加Lb存到Lc中 
void add(Linklist La, Linklist Lb, Linklist &Lc) {
	copy(La, Lc);  //把La拷贝到Lc中 
	Link qb;
	term b;
	qb=Lb->next;
	while(qb) {
		b=qb->data; 
		Orderinsertmerge(Lc,b);  //由于该函数有合并同类项的功能所以可以直接插入 
		qb=qb->next;
	}
}
//  La乘以Lb放到Lc中 
void mul(Linklist La, Linklist Lb, Linklist &Lc) {
	Lc=new Lnode;  //创建新链表头节点 
	Lc->next=NULL; 
	Link ha=La->next;
	while(ha) {
		term now=ha->data;
		Link hb=Lb->next;
		while(hb) {
			term tmp, cur=hb->data;
			tmp={cur.coef*now.coef, cur.expn+now.expn}; //一一枚举La和Lb中的元素，一一相乘并合并同类项 
			Orderinsertmerge(Lc, tmp);
			hb=hb->next;
		}
		ha=ha->next;
	}
}

int main()
{
	int num;
	Linklist L1,L2,L3,L4;
	//输入第一个链表 
	printf("\n[Tips]: 请您输入第一个多项式的项数:  ");
	scanf("%d",&num);
	Creatpolyn(L1,num);
	printpolyn(L1);
	printf("\n[INFO]: L1= ");
	PrintList(L1);
	//输入第二个链表 
	printf("\n[Tips]: 请您输入第二个多项式的项数:  ");
	scanf("%d",&num);
	Creatpolyn(L2,num);
	printpolyn(L2);
	printf("\n[INFO]: L2= ");
	PrintList(L2);
	//相加 
	add(L1, L2, L3);
	printf("\n[result]: L1和L2相加结果：\n"); 
	PrintList(L3);
	//相乘 
	mul(L1, L2, L4);
	printf("\n[result]: L1和L2相乘结果：\n"); 
	PrintList(L4);
	
	return 0;
 }