02-线性结构2 一元多项式的乘法与加法运算

#include<bits/stdc++.h>
using namespace std;
//这里我用链表存储数据，我想了想，要写的函数有
//插入函数，输出函数，合并函数，以及相乘函数
typedef struct lnode{
	int coefficient;//顺便学一波英语，coefficient（系数），exponent（指数） 
	int exponent;
	struct lnode *link;
}sqlist;
//后来我想了想应该用尾插法，头插法最后的数据就是倒着的了 
//void insertlist(sqlist*&l,int x,int y){
//	//为了节约时间，初始化直接写在插入函数里面
//	 sqlist*s;//这个是头节点的下一个节点 
//	 l=(sqlist*)malloc(sizeof(sqlist));//这个是头节点 
//	 l->link=NULL;
//	 s=(sqlist*)malloc(sizeof(sqlist));//为接下来的节点开辟一个内存
//	 s->coefficient=x;
//	 s->exponent=y;
//	 s->link=l->link;
//	 l->link=s; 
//}
//-------------------------------------------------------------
//这里我发现用尾插法，头节点可以不需要，后面反而碍事，于是我试着把它去掉 
//-------------------------------------------------------------
void insertlist(sqlist*&l,int n){
	int x,y;
	sqlist*s,*r;
	l=(sqlist*)malloc(sizeof(sqlist));
	r=l;
	for(int i=0;i<n;i++){
//	r->link=NULL;
	s=(sqlist*)malloc(sizeof(sqlist));
	cin>>x>>y;
	s->coefficient=x;
	s->exponent=y;
	r->link=s;
	r=s;
	}
	r->link=NULL;
	//如果必须要头节点，那最后我们可以给头节点删除了
	sqlist*t;
	t=l;
	l=l->link;
	free(t);
}
//---------------------------------------------------
//我最终是终于明白了，所谓必要的头结点是为了寻址而必要的，当我给头结点一开始就删除后，
//用自己作为头结点的话，因为自身本身就是在不断调用，这样链表虽然没有断，却无法用传递参数
//来表示头结点了， 
//之后我发现去掉头节点，只能读入一组数据了，莫名其妙的我也找不出bug 
//----------------------------------------------------- 
//void insertlist(sqlist*&l,int n){ 
//	int x,y;
//	sqlist*r;//这里需要一个指针来作为中介
//	r=(sqlist*)malloc(sizeof(sqlist));//这里加了初始化，但是发现还是不行，链表好像断了 
//	for(int i=0;i<n;i++){
//		l=(sqlist*)malloc(sizeof(sqlist));
//		cin>>x>>y;
//		l->coefficient=x;
//		l->exponent=y;
//		r->link=l;
//		r=l;
//	}
//	r->link=NULL; 
//	l=r->link;
//	free(r);
//}
void displist(sqlist*l){
	sqlist*p=l;
	while(p!=NULL&&p->coefficient<1000000){
		cout<<p->coefficient<<" "<<p->exponent<<" ";
		p=p->link;
	}
	cout<<endl;
}
sqlist* combinelist(sqlist*l,sqlist*p){//conbine（合并） 
	sqlist*q,*r;
	sqlist*s;//头节点 
	s=(sqlist*)malloc(sizeof(sqlist));
	r=s;
	sqlist*t1=l,*t2=p;
	while(t1&&t2){//当t1和t2都不空的时候 
		if(t1->exponent==t2->exponent){
			q=(sqlist*)malloc(sizeof(sqlist));//这里我应该写一个单个值的插入函数，为了省事，就只能让代码遭罪了 
			q->coefficient=t1->coefficient+t2->coefficient;
			q->exponent=t1->exponent;
			r->link=q;
			r=q;
			t1=t1->link;
			t2=t2->link;
		}
		else if(t1->exponent>t2->exponent){
			q=(sqlist*)malloc(sizeof(sqlist));
			q->coefficient=t1->coefficient;
			q->exponent=t1->exponent;
			r->link=q;
			r=q;
			t1=t1->link;
		}
		else{
			q=(sqlist*)malloc(sizeof(sqlist));	
			q->coefficient=t2->coefficient;
			q->exponent=t2->exponent;
			r->link=q;
			r=q;
			t2=t2->link;
		}
	}
	while(t1){
			q=(sqlist*)malloc(sizeof(sqlist));
			q->coefficient=t1->coefficient;
			q->exponent=t1->exponent;
			r->link=q;
			r=q;
			t1=t1->link;
	}
	while(t2){
			q=(sqlist*)malloc(sizeof(sqlist));	
			q->coefficient=t2->coefficient;
			q->exponent=t2->exponent;
			r->link=q;
			r=q;
			t2=t2->link;
	}
	r->link=NULL;
	//如果必须要头节点，那最后我们可以给头节点删除了
	sqlist*t;
	t=s;
	s=s->link;
	free(t);
	return s;
}
//这里我的想法是，每乘一个数，放入一个新的链表中，然后要做的事情是排序，合并同类项
//我又想了想，发现排序根本不可能，于是我想到在插入的时候就应该排序好，并且遍历一遍寻找同类项 
//sqlist* multiply(sqlist*l,sqlist*p){//multiply（相乘）
//	bool bl;
// 	sqlist *t1=l,*t2=p;
// 	sqlist *s,*r;
// 	//这里我还是用尾插法
//	sqlist *head;
//	head=(sqlist*)malloc(sizeof(sqlist));
//	r=head;
//	int coefficient,exponent;
//	while(t1){
//		while(t2){
//			r->link=NULL;
//			coefficient=t1->coefficient*t2->coefficient;
//			exponent=t1->exponent+t2->exponent;
//			//这里开始我们的插入时排序，和插入时合并
//			while(head){
//				//先判断合并
//				bl=1;
//				if(head->exponent==exponent){
//					head->coefficient+=coefficient;//这里有种难ban的情况就是head->cofficient可能会变成0，我先不考虑 
//					bl=0;
//					break;
//				}
//				if(exponent<head->exponent){
//					s=(sqlist*)malloc(sizeof(sqlist));
//					s->coefficient=coefficient;
//					s->exponent=exponent;
//					s->link=head->link;
//					head->link=s;
//					bl=0;
//					break;
//				}
//				head=head->link;	
//			}
//			if(bl){
//				s=(sqlist*)malloc(sizeof(sqlist));
//				s->coefficient=coefficient;
//				s->exponent=exponent;
//				r->link=s;
//				r=s;
//			}
//			t2=t2->link;
//		}
//		t1=t1->link;
//	}
//	r->link=NULL;
//}
sqlist* multiply(sqlist* L1,sqlist* L2){
	sqlist* tmpL1 = L1;
	sqlist* tmpL2 = L2;
	sqlist* mul=(sqlist*)malloc(sizeof(sqlist));
	mul->link = NULL;
	sqlist* head = mul;
	sqlist* t;
	for(;tmpL1;tmpL1=tmpL1->link)
		for(tmpL2 = L2;tmpL2;tmpL2=tmpL2->link){
			t = (sqlist*)malloc(sizeof(sqlist));
			t->coefficient = tmpL1->coefficient* tmpL2->coefficient;  // 系数相乘
			t->exponent = tmpL1->exponent + tmpL2->exponent;  // 指数相加
			t->link = NULL;
			head = combinelist(t,mul);  // 将新增结点和之前已经排好序的结点排序 
			mul = head; // 重新确定开头 
		}
	return head;
}
int main(){
	sqlist *l ,*p;
	int n;
	cin>>n;
	insertlist(l,n);
	cin>>n;
	insertlist(p,n);
//	displist(l);
//	displist(p);
	sqlist *s;
	s=combinelist(l,p);
	displist(s);
	sqlist *m;
	m=multiply(l,p);
	displist(m);
}