问题描述： 假设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); }