一元多项式的加/减法运算
问题描述：
假设2个稀疏一元多项式分别由带头结点的有序单链表A和B存储（指数项递增有序）。现要求设计一个算法，实现稀疏一元多项式的加减法计算。要求使用A和B的原存储空间（运算后B不再存在，A链表中保存结果多项式）。输入中的单链表的长度不得在计算算法中利用，仅作为建表使用。
注意：加/减法计算后，如某一项的结果系数为0，则该项要从多项式链表中删除。
输入说明：
第一行：加/减法选择（0：加法 1：减法）
第二行：一元多项式A的项数
第三行：一元多项式A的各项的系数（系数之间以空格分隔）
第四行：一元多项式A的各项的指数（指数之间以空格分隔）
第五行：一元多项式B的项数
第六行：一元多项式B的各项的系数（系数之间以空格分隔）
第七行：一元多项式B的各项的指数（指数之间以空格分隔）
如果A或B的项数为0，则认为输入的多项式只包含数字“0”，即系数为0，指数也为0。
输出说明：
第一行：多项式A的第一项的系数、指数（以空格分隔）
第一行：多项式A的第二项的系数、指数（以空格分隔）
…
第n行：多项式A的第n项的系数、指数（以空格分隔） （假设多项式A的项数为n）
（空行）
第一行：多项式B的第一项的系数、指数（以空格分隔）
第一行：多项式B的第二项的系数、指数（以空格分隔）
…
第m行：多项式B的第m项的系数、指数（以空格分隔） （假设多项式B的项数为m）
（空行）
第一行：加/减法计算后，结果多项式A的第一项的系数、指数（以空格分隔）
第一行：加/减法计算后，结果多项式A的第二项的系数、指数（以空格分隔）
…
第p行：加/减法计算后，结果多项式A的第n项的系数、指数（以空格分隔） （假设结果多项式的项数为p）
（多项式之间以空行分隔，如果多项式只包含“0”，则相应的多项式输出"0 0"，不包含引号。）
输入范例：
1
6
7 3 -22 9 5 -8
0 1 7 8 17 100
3
8 22 -9
1 7 8
输出范例：
7 0
3 1
-22 7
9 8
5 17
-8 100
8 1
22 7
-9 8
7 0
-5 1
-44 7
18 8
5 17
-8 100
注：此解是为了应对OJ测试。
#include<iostream>
using namespace std;
struct ListNode{
int num;
int zhishu;
struct ListNode *next;
};
ListNode *createByTail(){
ListNode *head=new ListNode;
ListNode *p,*p1;
p=head;
head->next=NULL;
int len,num,zhishu;
cin>>len;
int i=0;
while(i<len&&cin>>num){
p1=new ListNode;
p1->num=num;
p->next=p1;
p=p1;
i++;
}
p->next=NULL;
p=head->next;
while(p){
cin>>zhishu;
p->zhishu=zhishu;
p=p->next;
}
return head;
}
int length(ListNode *head){
int n=0;
ListNode *p=head->next;
while(p){
n++;
p=p->next;
}
return n;
}
void destroy(ListNode *head){
if(head==NULL){
return;
}
ListNode *p=head,*q=head;
while(p->next){
q=p->next;
delete p;
p=q;
}
delete p;
}
int main(){
int jiahuojian;
cin>>jiahuojian;
ListNode *headA=createByTail();
ListNode *headB=createByTail();
int lenA=length(headA);
int lenB=length(headB);
ListNode *ha=headA,*hb=headB;
for(int i=0;i<lenA;i++){
cout<<ha->next->num;
cout<<" ";
cout<<ha->next->zhishu<<endl;
ha=ha->next;
}
cout<<endl;
if(lenB==0){//完全为了应对OJ测试
cout<<"0 0"<<endl;
}else{
for(int i=0;i<lenB;i++){
cout<<hb->next->num;
cout<<" ";
cout<<hb->next->zhishu<<endl;
hb=hb->next;
}
}
cout<<endl;
if(jiahuojian==0){
ListNode *pre=headA,*qre=headB;
ListNode *p=headA->next;
ListNode *q=headB->next;
int tag=0,flag=0;
while(p&&q){
if(p->zhishu==q->zhishu){
int jia=p->num+q->num;
if(jia==0){
qre=q;
q=q->next;
pre=p;
p=p->next;
tag=1;
}else{
p->num=jia;
cout<<p->num<<" "<<p->zhishu<<endl;
pre=p;
p=p->next;
qre=q;
q=qre->next;
flag=1;
}
}else if(p->zhishu<q->zhishu){
cout<<p->num<<" "<<p->zhishu<<endl;
pre=p;
p=p->next;
flag=1;
}else{
qre=q;
q=q->next;
}
}
while(p){
cout<<p->num<<" "<<p->zhishu<<endl;
p=p->next;
flag=1;
}
if(tag==1&&flag==0){
cout<<"0 0"<<endl;
}
}else if(jiahuojian==1){
ListNode *pre=headA,*qre=headB;
ListNode *p=headA->next;
ListNode *q=headB->next;
int tag=0,flag=0;
while(p&&q){
if(p->zhishu==q->zhishu){
int jian=p->num-q->num;
if(jian==0){
qre=q;
q=q->next;
pre=p;
p=p->next;
tag=1;
}else{
p->num=jian;
cout<<p->num<<" "<<p->zhishu<<endl;
pre=p;
p=p->next;
qre=q;
q=qre->next;
flag=1;
}
}else if(p->zhishu<q->zhishu){
cout<<p->num<<" "<<p->zhishu<<endl;
pre=p;
p=p->next;
flag=1;
}else{
qre=q;
q=q->next;
}
}
while(p){
cout<<p->num<<" "<<p->zhishu<<endl;
p=p->next;
flag=1;
}
if(tag==1&&flag==0){
cout<<"0 0"<<endl;
}
}
destroy(headB);
}