/**
数据结构习题1
多项式的相加和相乘
@刘辉
**/
struct Node{
int data;
int index;
Node* next;
};
Node *insertList(Node* head,Node* p); //插入链表
Node *createList(); //创建链表
void printList(Node *head); //打印链表
Node *addList(Node *p1,Node *p2); //实现加法运算

Node *createList()
{
int index,data;
Node *p,*head,*q;
head = new Node;
p = head;
cout<<"请输入要输入的多项式a的幂指数：";
cin>>index;
cout<<"请输入该指数的参数：";
cin>>data;
while(index!=0)
{
q = new Node;
q->index = index;
q->data = data;
p->next = q;
p = q;
cout<<"请输入要输入的多项式a的幂指数：";
cin>>index;
cout<<"请输入该指数的参数：";
cin>>data;
}
p->next = NULL;
return head;
}
//多项式相加
Node *addList(Node *p1,Node *p2)
{
int add;
Node *temp,*head,*p3;
p1 = p1->next;
p2 = p2->next;
head = temp = new Node;
head->next = NULL;
while(p1&&p2)
{

if(p1->index==p2->index)
{
add = p2->data + p1->data;
if(add!=0)
{
p3 = new Node;
p3->index = p2->index;
p3->data = add;
p3->next = NULL;
}
p1 = p1->next;
p2 = p2->next;
}
else if(p1->index<p2->index)
{
p3 = new Node;
p3->data = p2->data;
p3->index = p2->index;
p3->next = NULL;
p2 = p2->next;

}
else
{
p3 = new Node;
p3->data = p1->data;
p3->index = p1->index;
p3->next = NULL;
p1 = p1->next;

}
if(head->next ==NULL)
{
head->next = p3;
temp = p3;
}
else
{
temp->next = p3;
temp = p3;
}
}
temp->next = p1?p1:p2;
return head;

}

//多项式相乘
Node* mulList(Node *p1,Node *p2)
{
Node *head,*temp,*s,*r,*q;
head = new Node;
head->next = NULL;
temp = new Node;
temp->next = NULL;
p1 = p1->next;
p2 = p2->next;
for(s=p1;s;s=s->next)
{
for(r=p2;r;r=r->next)
{
q = new Node;
temp->next = q;
q->data = s->data * r->data;
q->index = s->index + r->index;
q->next = NULL;
head = addList(temp,head);
}
}
return head;
}

//打印多项式
void printList(Node *head)
{
Node *p = NULL;
p = head->next;
if(p==NULL)
{
cout<<"文件为空";
}
else
{
do
{
if(p->data>=0)
cout<<p->data<<"x^"<<p->index;
else
cout<<p->data<<"x^"<<p->index;
if(p->next!=NULL)
cout<<"+";
p=p->next;
}while(p != NULL);
cout<<endl;
}
}

//主函数
int main()
{
int i;
Node *p1=NULL,*p2=NULL,*p3=NULL,*p4=NULL;
cout<<"创建第一个多项式的链表："<<"\n";
p1 = createList();
cout<<"\n";
cout<<"创建第二个多项式的链表："<<"\n";
p2 = createList();
cout<<"第一个多项式为：";
printList(p1);
cout<<"\n"<<"第二个多项式为：";
printList(p2);
p3 = addList(p1,p2); //实现多项式相加
cout<<"\n"<<"多项式相加后为：";
printList(p3);
cout<<endl;
p4 = mulList(p1,p2); //实现多项式相乘
cout<<"多项式相乘后为：";
printList(p4);
cin>>i;
return 0;
}