【问题描述】编写一个程序用单链表存储多项式，并实现两个一元多项式A与B相加的函数。A，B刚开始是无序的，A与B之和按降序排列。例如：
多项式A: 1.2X^0 2.5X^1 3.2X^3 -2.5X^5
多项式B: -1.2X^0 2.5X^1 3.2X^3 2.5X^5 5.4X^10
多项式A与B之和：5.4X^10 6.4X^3 5X^1
【输入形式】任意两个多项式A和B的项数及对应的系数和指数，要查询的第几项
【输出形式】多项式中某一项的系数与指数，系数保留一位小数
【输入样例】
4 1.2 0 2.5 1 3.2 3 -2.5 5
5 -1.2 0 2.5 1 3.2 3 2.5 5 5.4 10
2
【输出样例】6.4 3
1 #include<bits/stdc++.h> 2 #include<stdlib.h> 3 using namespace std; 4 typedef long long ll; 5 6 struct node{ 7 double data; 8 int index; 9 node* next; 10 node():index(0){} 11 node* operator [] (int n){ 12 node* end=next; 13 while(end&&n--)end=end->next; 14 return end; 15 } 16 bool operator < (const node &t) const { 17 return index>t.index; 18 } 19 node operator * (node& t); 20 }; 21 22 void newList(node & head,int length){ 23 node *a=new node[length];//这是这个函数的解释node* operator [] (int n)P11行 申请空间的方式 new int[10]申请10个int类型的空间 再返回node指针类型 24 for(int i=0;i<length;++i)cin>>a[i].data>>a[i].index; 25 //a是node类型数组啊 26 sort(a,a+length);//p16行的函数解释 27 node* end=&head; 28 for(int i=0;i<length;++i){ 29 node* t=new node; 30 t->data=a[i].data; 31 t->index=a[i].index; 32 end->next=t; 33 end=t; 34 }//他这好像就特别简单 end=xx 之后就申请了新节点 赋值 然后挂上去 35 delete[] a; 36 } 37 void show(node& head){//传递的这个是引用 38 node* end=head.next;//就还是这个类型 所以用的是. 39 while(end){ 40 if(end->index==1) cout<<end->data<<"X^"<<(end->next?" + ":" "); 41 else cout<<end->data<<"X^"<<end->index<<(end->next?" + ":" ");//末尾加的这个的意思是 如果下一个节点还有 就+上 如果没有就换行 42 end=end->next; 43 } 44 } 45 46 ///多项式相加： 47 void combine(node& a, node& b){//传递的是引用 48 node* p,*q,*tail,*temp; 49 double s; 50 p=a.next; 51 q=b.next; 52 tail=&a;//就直接修改a链表了 53 while(p&&q){ 54 if(p->index>q->index){ 55 tail->next=p;tail=p;p=p->next; 56 }else if(p->index==q->index){ 57 s=p->data+q->data; 58 if(s){ 59 p->data=s; 60 tail->next=p; tail=p;p=p->next; 61 temp=q;q=q->next;delete temp; 62 }else{ 63 temp=p;p=p->next;delete temp; 64 temp=q;q=q->next;delete temp; 65 }//删除没有用的节点这点甚是符合朕心 厉害 66 }else{ 67 tail->next=q; tail=q; q=q->next; 68 } 69 } 70 if(p)tail->next=p; 71 else tail->next=q; 72 } 73 74 int main(){ 75 node a,b; 76 int n1,n2;cin>>n1; 77 newList(a,n1); 78 cin>>n2; 79 newList(b,n2); 80 combine(a,b); 81 82 cin>>n1; 83 cout<<fixed<<setprecision(1)<<a[n1-1]->data<<" "<<a[n1-1]->index<<endl;//这里可以这么骚也是因为p11行 牛逼 84 show(a);//给引用传参数 就是传本身 不是传指针 85 }
