#include <iostream>
using namespace std;
#include <stdlib.h>
#include <string.h>
#include "stdio.h"

typedef struct
{  
	float coef;//结点类型
    int expn;
}polynomial;

typedef struct LNode
{ 
	polynomial data;//链表类型
    struct LNode *next;
}LNode,*Link;

typedef int (*PFUN)();

struct CMDINFO
{
	const char *pCmdName;
	const char *pCmdInfo;

	PFUN pFun;
};

/*调用的函数*/
void createLink(Link &L,int n);
void printList(Link L);
void addPolyn(Link &pc,Link pa,Link pb);
void substractPolyn(Link &pc,Link pa,Link pb);
void mulPolyn(Link &pc,Link pa,Link pb);
void copyLink(Link &pc,Link pa);
int locateLink(Link pa,Link e);
void destroyLink(Link &L);

/*命令行函数*/
void CmdProc(const char *pTitle);
int CreatePolyn();
int ShowPolyn();
int AddPolyn();
int SubPolyn();
int MulPolyn();
int DesPolyn();
int Clear();
int Help();
int Exit();

CMDINFO g_CmdInfo[] = { "CreatePolyn",	   "创建多项式",    CreatePolyn,
                        "ShowPolyn", 	   "显示多项式",    ShowPolyn,
						"AddPolyn",	       "多项式相加",    AddPolyn,
						"SubPolyn",        "多项式相减",    SubPolyn,
						"MulPolyn",        "多项式相乘",    MulPolyn,
						"DesPolyn",        "销毁多项式",    DesPolyn,
						"Clear",           "清屏操作",      Clear,
						"Help",		       "帮助信息",      Help,
						"Exit",		       "退出",		    Exit};

int g_nCmdSize = sizeof(g_CmdInfo)/sizeof(CMDINFO);
Link La = NULL,Lb = NULL;

void main()
{
    CmdProc("多项式");
}

void CmdProc(const char *pTitle)    //Dos界面命令行函数
{
	char szCmdBuf[50] = "";
	int i = 0;

    if(NULL == pTitle)
	{
		cout<<"xxx空系统 v 2.0"<<endl;
	}
	else
	{
		cout<<pTitle<<"系统 v 2.0"<<endl;
	}
	while(true)
	{
		cout<<">";
		cin>>szCmdBuf;
		
		for(i = 0; i < g_nCmdSize; i++)
		{
			if(!strcmp(szCmdBuf, g_CmdInfo[i].pCmdName))
			{
				g_CmdInfo[i].pFun();
				break;
			}
		}

		if(i == g_nCmdSize)
		{
			cout<<"您输入的命令有误，请用Help命令查询!"<<endl;
		}
	}
}

int CreatePolyn()   //创建多项式
{
	if(La != NULL && Lb != NULL)       //多项式校验
	{
	    cout<<"您已经创建了多项式，请使用其它命令!"<<endl;	
		return 0;
	}
	int n;
	cout<<"请输入你要运算的第一个一元多项式的项数: ";
	cin>>n;
	createLink(La,n);

	cout<<"请输入你要运算的第二个一元多项式的项数: ";
	cin>>n;
	createLink(Lb,n);
	return 0;
}

int ShowPolyn()        //显示多项式
{
	if(La == NULL || Lb == NULL)       //多项式校验
	{
	    cout<<"您还未创建多项式，请先创建!"<<endl;
		return 0;
	}

	cout<<"第一个一元多项式为："<<endl;
	printList(La);
	cout<<"第二个一元多项式为："<<endl;
	printList(Lb);
	return 0;
}

int AddPolyn()      //多项式相加
{
	Link L;
	if(La == NULL || Lb == NULL)   //多项式校验
	{
		cout<<"您还未创建多项式，请先创建!"<<endl;
		return 0;
	}

	addPolyn(L,La,Lb);
	cout<<"两个多项式相加后的结果为："<<endl;
	printList(L);
	destroyLink(L);
	return 0;
}

int SubPolyn()       //多项式相减
{
	Link L;
	if(La == NULL || Lb == NULL)    //多项式校验
	{
		cout<<"您还未创建多项式，请先创建!"<<endl;	
		return 0;
	}
	substractPolyn(L,La,Lb);
	cout<<"两个多项式相减后的结果为："<<endl;
	printList(L);
	destroyLink(L);
	return 0;
}

int MulPolyn()     //多项式相乘
{
	Link L;
	if(La == NULL || Lb == NULL)       //多项式校验
	{
		 cout<<"您还未创建多项式，请先创建!"<<endl;
		 return 0;
	}
	mulPolyn(L,La,Lb);
	cout<<"两个多项式相乘后的结果为："<<endl;
	printList(L);
	destroyLink(L);
	return 0;
}

int DesPolyn()        //销毁多项式
{
	if(La == NULL || Lb == NULL)       //多项式校验
	{
		 cout<<"您还未创建多项式，请先创建!"<<endl;
		 return 0;
	}
	if(La && Lb)
	{
		  destroyLink(La);
		  destroyLink(Lb);
		  cout<<"销毁成功！"<<endl;
	}
	else 
	{ 
		  cout<<"您还未创建多项式，请先创建!"<<endl;
	}
	return 0;
}

int Clear()       //清屏函数
{
	 char a;
	 a = getchar();
	 system("cls"); //system是DOS界面命令行操作函数 cls是清屏命令 ，format d: /q 是格式化D盘命令
	 cout<<"多项式系统 v 2.0"<<endl;
	 return 0;
}

int Help()      //帮助函数
{
	
	int i = 0;
	int j = 0;
	int nSize = 0;

	cout<<"相关命令信息: "<<endl;

	for(i = 0; i < g_nCmdSize; i++)
	{   
		cout<<"   "<<g_CmdInfo[i].pCmdName;
		nSize = strlen(g_CmdInfo[i].pCmdName);

		for(j = 0; j < 20 - nSize; j++)
		{
			cout<<" ";
		}

		cout<<g_CmdInfo[i].pCmdInfo<<endl;
	}
	return 0;
}

int Exit()        //退出函数
{
	exit(0);
	return 0;
}

void destroyLink(Link &L)  //清空链表
{
	 Link p;
	 p = L->next;
	 while(p)
	 {  
		 L->next = p->next;
		 delete p;
		 p = L->next;
	 }
	 delete L;
	 L = NULL;
}

/*判断指数是否与多项式中已存在的某项相同*/
int locateLink(Link L,Link e)
{
	 Link p;
	 p = L->next;
	 while(p != NULL && (e->data.expn != p->data.expn))
	 {
		 p = p->next;
	 }
	 if(p == NULL)
	 {
		 return 0;
	 }
	 else
	 {
		 return 1;
	 }
}

void createLink(Link &L,int n)   //创建链表
{
	  Link p,newp;
	  L = new LNode;
	  L->next = NULL;
	  (L->data).expn = -1;//创建头结点
	  p = L;
   
	  for(int i = 1; i <= n; i++)
	  {
			newp = new LNode;
			cout<<"请输入第"<<i<<"项的系数和指数:"<<endl;
			cout<<"系数: ";
			cin>>(newp->data).coef;
    
			cout<<"指数: ";
			cin>>(newp->data).expn;

			if(newp->data.expn < 0)    //指数校验
			{
				cout<<"您输入有误，指数不允许为负值!"<<endl;
				delete newp;
				i--;
				continue;
			}

			newp->next = NULL;
			p = L;

			if(newp->data.coef == 0)  //系数校验
			{
				cout<<"系数为零，重新输入!"<<endl;
				delete newp;
				i--;
				continue;
			}
		 
			while((p->next != NULL) && ((p->next->data).expn < (newp->data).expn)) 
			{                         //指数排序
				p = p->next;
			}
			if(!locateLink( L, newp))
			{
				 newp->next = p->next;
				 p->next = newp;
			}
			else 
			{
				 cout<<"输入的该项指数与多项式中已存在的某项相同,请重新创建一个正确的多项式"<<endl;
				 delete newp;
				 destroyLink(L);
				 createLink(L,n);
				 break;
			}
	  }
}

/*输出链表*/
void printList(Link L)
{
	  Link p;
  
	  if(L == NULL || L->next == NULL)  //校验
	  {
		  cout<<"该一元多项式为空 !";
	  }
	  else
	  {
	     p = L->next;  //跳过头结点
		 if((p->data).coef > 0 )
		 { 
	        if((p->data).expn == 0)
			{
				cout<<(p->data).coef;
			}
			else 
			{
				if((p->data).coef == 1 && (p->data).expn == 1)
				{
					cout<<"x";
				}
				else 
				{
					if((p->data).coef == 1 && (p->data).expn != 1)
					{
						cout<<"x^"<<(p->data).expn;
					}
					else
					{
						if((p->data).expn == 1 && (p->data).coef != 1)
						{
							cout<<(p->data).coef<<"x";
						}
						else 
						{
							cout<<(p->data).coef<<"x^"<<(p->data).expn;
						}
					}
				}
			}
		 }
		 if((p->data).coef < 0)
		 {    
		     if((p->data).expn == 0)
			 {
			    cout<<(p->data).coef;
			 }
		     else 
			 { 
			     if(p->data.coef == -1 && p->data.expn == 1)
				 {
				     cout<<"-x";
				 }
			     else 
				 {
				     if(p->data.coef == -1 && p->data.expn != 1)
					 {
					     cout<<"-x^"<<p->data.expn;
					 }
				     else 
					 {
					     if(p->data.expn == 1)
						 { 
						      cout<<p->data.coef<<"x";
						 }
		                 else  
						 {
						      cout<<(p->data).coef<<"x^"<<(p->data).expn;
						 }
					 }
				 }
			 }
		 }
	     p = p->next;
		 while(p != NULL)
		 {
		    if((p->data).coef > 0)
			{
				if((p->data).expn == 0) 
				{
					cout<<"+"<<(p->data).coef;
				}
				else 
				{
					if((p->data).expn == 1 && (p->data).coef != 1) 
					{
						cout<<"+"<<(p->data).coef<<"x";
					}
					else 
					{
						if((p->data).expn == 1 && (p->data).coef == 1)
						{
							cout<<"+x";
						}
						else  
						{
							if((p->data).coef == 1 && (p->data).expn != 1)
							{
								cout<<"+x^"<<(p->data).expn;
							}
							else 
							{
								cout<<"+"<<(p->data).coef<<"x^"<<(p->data).expn;
							}
						}
					}
				}
			}
			if((p->data).coef < 0)
			{ 
				 if((p->data).expn == 0)
				 {
					 cout<<(p->data).coef;
				 }
				 else 
				 {
					 if(p->data.coef == -1 && p->data.expn == 1)
					 {
						 cout<<"-x";
					 }
					 else 
					 {
						 if(p->data.coef == -1 && p->data.expn != 1)
						 {
							 cout<<"-x^"<<p->data.expn;
						 }
					     else 
						 {
						     if(p->data.expn == 1)
							 {
								cout<<p->data.coef<<"x";
							 }
							else  
							{
							    cout<<(p->data).coef<<"x^"<<(p->data).expn;
							}
						 }
					 }
				 }
			}

			p=p->next;
		 }
	  }
	  cout<<endl;
}

/*把一个链表的内容复制给另一个链表*/
void copyLink(Link &pc,Link pa)
{
	 Link p,q,r;
	 pc = new LNode;
	 pc->next = NULL;
	 r = pc;
	 p = pa;

	 while(p->next != NULL)
	 {
		  q = new LNode;
		  q->data.coef = p->next->data.coef;    //跳过头结点
		  q->data.expn = p->next->data.expn;
		  r->next = q;
		  q->next = NULL;
		  r = q;
		  p = p->next;
	 }
}

/*将两个一元多项式相加*/
void addPolyn(Link &pc,Link pa,Link pb)
{   
	 Link p1,p2,p,pd;
	 /*以下为保护原多项式操作 分别复制到 p1、p2里*/
	 copyLink(p1,pa);
	 copyLink(p2,pb);

	 pc = new LNode;
	 pc->next = NULL;
	 p = pc;
	 p1 = p1->next;  //跳过头结点
	 p2 = p2->next;

	 while(p1 != NULL && p2 != NULL)       //蛇形连接
	 {
		  if(p1->data.expn < p2->data.expn)
		  {
			   p->next = p1;
			   p = p->next;
			   p1 = p1->next;
		  }
		  else 
		  {
			  if(p1->data.expn > p2->data.expn)
			  {
				   p->next = p2;
				   p = p->next;
				   p2 = p2->next;
			  }
			  else   //两结点指数相等
			  {
				   p1->data.coef = p1->data.coef + p2->data.coef;
			       if(p1->data.coef != 0)   //这个是必须有的,对两个相同多项式相减时有用
				   {
						p->next = p1;
						p = p->next;
						p1 = p1->next;
						p2 = p2->next;
				   }
				   else         
				   {
						pd = p1;
						p1 = p1->next;
						p2 = p2->next;
						delete pd;
				   }
			  }
		  }
	 }
	 if(p1 != NULL)
	 {
	     p->next = p1;
	 }
	 if(p2 != NULL)
	 {
	     p->next = p2;
	 }
}
/*将两个多项式相减*/
void substractPolyn(Link &pc,Link pa,Link pb)
{
	  Link p,pt;
	  copyLink(pt,pb);
	  p = pt;

	  while(p!=NULL)
	  {  
		 (p->data).coef = (-(p->data).coef);
	     p = p->next;
	  }
	  addPolyn(pc,pa,pt);
	  destroyLink(pt);
}
/*将两个一元多项式相乘*/
void mulPolyn(Link &pc,Link pa,Link pb)
{
	 Link p1,p2,p,pd,newp,t;
	 pc = new LNode;
	 pc->next = NULL;
	 p1 = pa->next;   //跳过头结点
	 p2 = pb->next;

	 while(p1 != NULL)
	 {
		  pd = new LNode;
		  pd->next = NULL;
		  p = new LNode;
		  p->next = NULL;
		  t = p;
		  while(p2)
		  {
			   newp = new LNode;
			   newp->next = NULL;
			   newp->data.coef = p1->data.coef * p2->data.coef;
			   newp->data.expn = p1->data.expn + p2->data.expn;
			   t->next = newp;
			   t = t->next;
			   p2 = p2->next;
		  }
		  addPolyn(pd,pc,p);
		  copyLink(pc,pd);
		  p1 = p1->next;
		  p2 = pb->next;
		  destroyLink(p);
		  destroyLink(pd);
	 }
}