一元n次多项式
我把first开到公有了。
实验二：一元多项式的基本运算
实验目的：掌握用线性表实现一元多项式的基本运算。
实验内容：使用链式存储实现一元多项式的加法、减法、乘法和求导。即：
C(x)= A(x)+B(x)；C(x)= A(x)-B(x) C(x)= A(x)*B(x) C(x)= A’(x)
菜单：
1)C ：分别创建两个多项式A(x)和B(x)，其中 输入时按照 指数的升序顺序输入，遇到系数为0则停止。例如：输入 ：
1 2 3 4 5 6 7 8
2 3 4 5 6 7 0
则生成的多项式分别为：
A(x)=x^2+3x^4+5x^6+7x^8
B(x)=2x^3+4x^5+6x^7
2)P:计算C(x)= A(x)+B(x)，计算完毕后输出C(x)的 结果
3)S: 计算C(x)= A(x)-B(x)，计算完毕后输出C(x)的 结果
4)M: 计算C(x)= A(x)*B(x)，计算完毕后输出C(x)的 结果
5)D: 计算C(x)= A’(x)，计算完毕后输出C(x)的 结果
6)V: 首先输入一个 float型数据，然后计算 A(x)并输出计算的结果。
7)E: 分别清空A(x)、B(x)、C(x)三个多项式。
8)X: 退出程序。
例如:
输入期望输出实际输出 C 1 2 3 4 5 6 7 8 0 2 3 4 5 6 7 0 S P M D V 2 X C(x)=x^2-2x^3+3x^4-4x^5+5x^6-6x^7+7x^8 C(x)=x^2+2x^3+3x^4+4x^5+5x^6+6x^7+7x^8 C(x)=2x^5+10x^7+28x^9+52x^11+58x^13+42x^15 C(x)=2x+12x^3+30x^5+56x^7 2164.00 C(x)=x^2-2x^3+3x^4-4x^5+5x^6-6x^7+7x^8 C(x)=x^2+2x^3+3x^4+4x^5+5x^6+6x^7+7x^8 C(x)=2x^5+10x^7+28x^9+52x^11+58x^13+42x^15 C(x)=2x+12x^3+30x^5+56x^7 2164.00 C 2 2 0 2 2 3 3 0 P S M D V 3.1 X C(x)=4x^2+3x^3 C(x)=-3x^3 C(x)=4x^4+6x^5 C(x)=4x 19.22 C(x)=4x^2+3x^3 C(x)=-3x^3 C(x)=4x^4+6x^5 C(x)=4x 19.22 C 3 0 2 2 0 -2 2 3 3 0 M V 2.1 P S D X C(x)=-6x^2+9x^3-4x^4+6x^5 11.82 C(x)=3+3x^3 C(x)=3+4x^2-3x^3 C(x)=4x C(x)=-6x^2+9x^3-4x^4+6x^5 11.82 C(x)=3+3x^3 C(x)=3+4x^2-3x^3 C(x)=4x通过所有测试
#include <iostream> #include<bits/stdc++.h> using namespace std; class List; class LinkNode { friend class List; private: int a,p; LinkNode *link; public: LinkNode(const int & item1,const int& item2, LinkNode *ptr = NULL) { a=item1; p=item2; link=ptr; } LinkNode (LinkNode *ptr = NULL) { link=ptr; } ~LinkNode() { }; }; class List { private: public: LinkNode *first; List () { first = new LinkNode (); } ~List () { MakeEmpty(first); //析构函数 } void MakeEmpty (LinkNode *first); //链表置空 int Remove ( int i ); //需要补充的成员函数 void input( LinkNode *first); void output( LinkNode *aa); //需要补充的成员函数 void Sort( LinkNode *aa); void Insert(int val); void add(LinkNode *aa,LinkNode *b); void jian(LinkNode *aa,LinkNode *b); void mult(LinkNode *aa,LinkNode *b); void devide(LinkNode *aa); double caculate(LinkNode *aa,double val); }; void List:: MakeEmpty (LinkNode *first) { LinkNode *q; while (first->link != NULL ) { q = first->link; first->link = q->link; delete q; } } void List:: input( LinkNode *first) { int n,val,cnt; LinkNode *newnode; for(int i=1; ; i++) { cin>>val; if(val==0) break; cin>>cnt; newnode=new LinkNode(val,cnt); newnode->link=first->link; first->link=newnode; } } void List::Sort(LinkNode *first) { LinkNode *i=first->link,*j; while (i!= NULL ) { j=i->link; while(j!=NULL) { if(i->p>j->p) { int temp; temp=j->p; j->p=i->p; i->p=temp; temp=j->a; j->a=i->a; i->a=temp; ///改成结构体存ap的话，就很简单了，但是我不想改了hhh } j=j->link; } i=i->link; } } void List::output( LinkNode *first) { cout<<"C(x)="; LinkNode *q=first->link; int cnt=0; while (q!= NULL ) { if(q->a>0&&cnt>0)printf("+"); if(q->a==0) { } else { if(q->p==0&&q->a==1) printf("1"),cnt++; if(q->a!=1)printf("%d",q->a),cnt++; if(q->p==0) {cnt++;} else if(q->p!=1) { printf("x^%d",q->p); cnt++; } else if(q->p==1) { printf("x"); cnt++; } } q =q->link; } if(cnt==0) cout<<"0"<<endl; cout<<endl; } void List::add(LinkNode *aa,LinkNode *b) { LinkNode *i=aa,*newnode,*temp=first; //cout<<aa->link->a<<endl; while(i->link!=NULL) { int f=0; LinkNode *j=b; while(j->link!=NULL) { if((i->link->p)==(j->link->p)) { f=1; int val=i->link->a+j->link->a; //int cnt=i->link->p+j->link->p; newnode=new LinkNode(val,i->link->p); newnode->link=first->link; first->link=newnode; } j=j->link; } if(f==0) { newnode=new LinkNode(i->link->a,i->link->p); newnode->link=first->link; first->link=newnode; } i=i->link; } /// /// i=b;///*i=b是错误写法 while(i->link!=NULL) { int f=0; LinkNode *j=aa; while(j->link!=NULL) { if((i->link->p)==(j->link->p)) { f=1; } j=j->link; } if(f==0) { newnode=new LinkNode(i->link->a,i->link->p); newnode->link=first->link; first->link=newnode; } i=i->link; } } void List::jian(LinkNode *aa,LinkNode *b) { LinkNode *i=aa,*newnode,*temp=first; //cout<<aa->link->a<<endl; while(i->link!=NULL) { int f=0; LinkNode *j=b; while(j->link!=NULL) { if((i->link->p)==(j->link->p)) { f=1; int val=i->link->a-j->link->a; //int cnt=i->link->p+j->link->p; newnode=new LinkNode(val,i->link->p); newnode->link=first->link; first->link=newnode; } j=j->link; } if(f==0) { newnode=new LinkNode(i->link->a,i->link->p); newnode->link=first->link; first->link=newnode; } i=i->link; } /// /// i=b;///*i=b是错误写法 while(i->link!=NULL) { int f=0; LinkNode *j=aa; while(j->link!=NULL) { if((i->link->p)==(j->link->p)) { f=1; } j=j->link; } if(f==0) { newnode=new LinkNode(-i->link->a,i->link->p); newnode->link=first->link; first->link=newnode; } i=i->link; } } void List::mult(LinkNode *aa,LinkNode *b) { LinkNode *i=aa,*j=b,*newnode; while(i->link!=NULL) { j=b;///前面已经定义过了 while(j->link!=NULL) { newnode=new LinkNode(i->link->a*j->link->a,i->link->p+j->link->p); newnode->link=first->link; first->link=newnode; j=j->link; } i=i->link; } LinkNode *temp=first->link; Sort(first); //output(first); while(temp!=NULL) { LinkNode *tt=temp; if(temp->link!=NULL) { while(tt->p==tt->link->p&&tt->link!=NULL) { temp->a+=tt->link->a; temp->link=tt->link; tt=tt->link; } temp->link=tt->link; } temp=tt->link; } } void List::devide(LinkNode *aa) { LinkNode *newnode,*i=aa->link; while(i!=NULL) { newnode=new LinkNode(i->a*i->p,i->p-1); newnode->link=first->link; first->link=newnode; i=i->link; //cout<<newnode->a<<" "<<newnode->p<<endl; } } double List::caculate(LinkNode *aa,double val) { double ans=0; LinkNode *i=aa->link; while(i!=NULL) { ans+=i->a*pow(val,i->p); i=i->link; } return ans; } int main() { List La,Lb,Lc; string s; cin>>s; if(s[0]=='C') { La.input(La.first); La.Sort( La.first); Lb.input(Lb.first); Lb.Sort( Lb.first); } // La.output(La.first); // cout<<endl; // Lb.output(Lb.first); while(1) { cin>>s; if(s[0]=='X') return 0; else if(s[0]=='S') { Lc.MakeEmpty(Lc.first); Lc.jian(La.first,Lb.first); //Lc.output(Lc.first); Lc.Sort(Lc.first); Lc.output(Lc.first); } else if(s[0]=='P') { Lc.MakeEmpty(Lc.first); Lc.add(La.first,Lb.first); //Lc.output(Lc.first); Lc.Sort(Lc.first); Lc.output(Lc.first); } else if(s[0]=='M') { Lc.MakeEmpty(Lc.first); Lc.mult(La.first,Lb.first); //Lc.output(Lc.first); Lc.Sort(Lc.first); Lc.output(Lc.first); } else if(s[0]=='D') { //La.output(La.first); Lc.MakeEmpty(Lc.first); Lc.devide(La.first); Lc.Sort(Lc.first); Lc.output(Lc.first); } else if(s[0]=='V') { double data; cin>>data; printf("%.2f\n",La.caculate(La.first,data)); } else if(s[0]=='E') { La.MakeEmpty(La.first); Lb.MakeEmpty(Lb.first); Lc.MakeEmpty(Lc.first); } } return 0; }
