#include <iostream>
using namespace std;
typedef struct PNODE{
	int xs;	int cs;	PNODE *next;}pnode;
int CreateList(pnode* header,int n){
	for(int i=1; i<=n; i++){		pnode *new_node = new pnode;//创建新节点		if (!new_node)		{			cout<<"创建失败"<<endl;			return 0;		}
		new_node->next = nullptr;		bool flag = true;//判断本次输入的数据是否已经存在相同次数项的标志		cout<<"请输入系数和次数:";		cin>> new_node->xs >> new_node->cs;		pnode *s1 = header->next;		
if (header->next==nullptr)		{			header->next = new_node;		}
else		{			while(s1!=nullptr){//查找是否有相同次数的项				if(s1->cs==new_node->cs){//找到同次数的项					if(s1->xs+new_node->xs==0){//如果系数和为0 移除该节点						pnode *del = header->next;						while (del->next!=s1){//找到前结点							del = del->next;						}						del->next = s1->next;						delete s1,new_node;						flag = false;						break;					}
else{//系数和不为0则 直接加 并且删除新节点						s1->xs += new_node->xs;						delete s1,new_node;						flag = false;						break; 					}				}else{//该项次数不同则找下一个结点					s1 = s1->next;				}			}			
if(flag){//没有同次数项则 直接在对应位置插入新节点				//查找该结点的前驱和后驱 				s1 = header->next;//s1保存前驱的位置				pnode *s2;//s2保存后驱				s2 = s1;//从首元结点开始查找				if (s1==nullptr){//如果还没有数据则直接填入					header->next = new_node;					new_node->next = nullptr;					delete s1,s2;				}
else{					while(s2!=nullptr && s2->cs < new_node->cs){//找到第一个比该节点次数大的项						s1 = s2;						s2 = s2->next;					}//如果没找到s1应该为最后一项，s2为空					new_node->next = s2;					s1->next = new_node;				}			}		}	}	return 0; }
int AddList(pnode*& header1,pnode*& header2)//合并
{	pnode* p1 = header1->next;	pnode* p2 = header2->next;	pnode *research = header2->next;//指向header2的头结点	bool flag = true;//判断本次输入的数据是否已经存在相同次数项的标志(True表示未找到)	for (p1; p1!=nullptr; p1 = p1->next){		while(p2!=nullptr){//查找header2中是否有相同次数的项			if(p2->cs==p1->cs){//找到同次数的项				if(p2->xs+p1->xs==0){//如果系数和为0 移除p2中对应节点 有下列三种情况					if (header1->next==p1 && header2->next==p2){//1. p1 p2为首元结点						header1->next = p1->next;						header2->next = p2->next;					}else if(header1->next==p1){//2. p1为首元 p2不是						header1->next = p1->next;						pnode *flag2 = header2->next;						while (flag2->next!=p2){//找到p2前驱							flag2 = flag2->next;						}						flag2->next = p2->next;					}else{//3. p2是首元 p1不是						header2->next = p2->next;						pnode *flag1 = header1->next;						while (flag1->next!=p1){//找到p1前驱							flag1 = flag1->next;						}						flag1->next = p1->next;					}					delete p2;//删除结点 				}else{//系数和不为0则 直接加xs					p2->xs += p1->xs;				}				flag = false;				p2 = header2->next;				break; 			}else{//该项次数不同则找下一个结点				p2 = p2->next;			}		}		if(flag){//没有同次数项则 直接找到p2对应位置插入			if (header2->next->cs > p1->cs){//次数小于首元结点直接插在首元结点前				p1->next = header2->next;				header2->next = p1;			}else{				pnode *front = header2->next;//保存前驱的位置				pnode *back = front->next;//保存后驱				while(back!=nullptr && front->cs<p1->cs){//在header2中找到第一个比p1次数大的项					front = back;					back = back->next;				}				pnode *add_node = new pnode;//插入到header2中的新节点				if (!add_node)				{					cout<<"申请失败"<<endl;					return 0;				}				add_node = p1;				add_node->next = back;				front->next = add_node;			}		}		p2 = header2->next;//重新指向首元结点		flag = true;//重新初始化	}	return 0;} 
int main(int argc, char** argv) {	
pnode *header1 = new pnode ,*header2 = new pnode;	header1->next = nullptr,header2->next = nullptr;	pnode *p1,*p2;	int n,m;	cout<<"第一个多项式输入几个项？:";	cin>>n;	CreateList(header1,n);	p1 = header1->next;	while (p1!=nullptr)	{		cout<<"系数："<<p1->xs<<"次数："<<p1->cs<<endl;		p1 = p1->next;	}	cout<<"第二个多项式输入几个项？:";	cin>>m;	CreateList(header2,m);	p2 = header2->next;	while (p2!=nullptr)	{		cout<<"系数："<<p2->xs<<"次数："<<p2->cs<<endl;		p2 = p2->next;	}	AddList(header1,header2);	cout<<"*********************************************"<<endl;	while (header2->next!=nullptr)	{		header2 = header2->next;		cout<<"系数："<<header2->xs<<"次数："<<header2->cs<<endl;	}	system("pause");	return 0;}