849
多項式運算線性鏈表的應用
最忙的時候迎來了我們數據結構的大實驗周一的時候編好了一個 線性鏈表的都是什麼什麼係統的 一點意思都沒有啊 看到了一個多項式的 於是我就試了一下 說是要先判斷稀疏度 在確定用線性存儲的還是順序存儲的 順序存儲的我沒寫 覺得還是鏈表的好 因為順序存儲的的開兩個數組 一個是指數是正的 一個指數是負的 覺得可能很不好寫 於是還是寫了個鏈表的 雙向鏈表的 用的C++寫的 覺得可以運算符重載挺好的
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
class Xiang //此乃線性鏈表 下麵還要開數組再做 我真是蒙了
{
public:
double coefficient;//多項式係數
int power; //多項式的冪
Xiang* next;
Xiang* last;
};
class polynomial//多項式
{
public:
int num;//項數
Xiang *head;
Xiang *tail;
polynomial();//初始化
void input();//從鍵盤輸入多項式
void displayup();//按指數升序輸出多項式
void displaydown();//按指數降序輸出多項式
void sort();//合並同類項並將多項式排序並刪除係數為0的項
bool addXiang();//從鍵盤輸入增加項 構建多項式
bool addXiang(double co,int po);//按照參數增加項
polynomial qiuhe(polynomial p1,polynomial p2);//求和函數
polynomial qiucha(polynomial p1,polynomial p2);//求差函數
polynomial chengji(polynomial p1,polynomial p2);//求乘積
polynomial operator +(polynomial p2);//重載運算符
polynomial operator -(polynomial p2);
polynomial operator *(polynomial p2);
};
polynomial::polynomial()//初始化
{
num=0;
head=new Xiang;
head->next=NULL;
head->last=NULL;
tail=NULL;
}
void polynomial::input()
{
do
{
cout<<"please input the num of polynomial(num>=0)"<<endl;
cin>>num;
}
while(num<0);
for(int i=0; i<num; i++)
cout<<"num "<<i+1<<": ",addXiang();
sort();
}
void polynomial::displayup()
{
if(num==0)
{
cout<<0<<endl;
return ;
}
Xiang *p=head->next;
for(int i=0; i<num; i++)
{
if(p->coefficient<0)
cout<<p->coefficient<<"X^"<<p->power;
else if(i)
cout<<"+"<<p->coefficient<<"X^"<<p->power;
else
cout<<p->coefficient<<"X^"<<p->power;
p=p->next;
}
cout<<endl;
}
void polynomial::displaydown()
{
if(num==0)
{
cout<<0<<endl;
return ;
}
Xiang *p=tail;
for(int i=0; i<num; i++)
{
if(p->coefficient<0)
cout<<p->coefficient<<"X^"<<p->power;
else if(i)
cout<<"+"<<p->coefficient<<"X^"<<p->power;
else
cout<<p->coefficient<<"X^"<<p->power;
p=p->last;
}
cout<<endl;
}
bool polynomial::addXiang()
{
Xiang *p=new Xiang;
Xiang *q=tail;
double c=0;
int po=0;
cin>>c>>po;
if(head->next==NULL)
{
head->next=p;
p->coefficient=c;
p->power=po;
p->next=NULL;
p->last=head;
tail=p;
}
else
{
q->next=p;
p->last=q;
p->coefficient=c;
p->power=po;
p->next=NULL;
tail=p;
}
return 1;
}
bool polynomial::addXiang(double co,int po)
{
Xiang *p=new Xiang;
Xiang *q=tail;
if(head->next==NULL)
{
head->next=p;
p->coefficient=co;
p->power=po;
p->next=NULL;
p->last=head;
tail=p;
}
else
{
q->next=p;
p->last=q;
p->coefficient=co;
p->power=po;
p->next=NULL;
tail=p;
}
num++;
sort();
return 1;
}
void polynomial::sort()//先排序 再合並同類項 再刪除係數是0的項 是的= = 這就是這個作業的核心啊 無論加減乘除都少不了= =
{
Xiang *a=head->next;
Xiang *b;
for(int i=0; i<num; i++) //排序的時間複雜度為 n^2 沒有操作指針直接用swap函數交換值 這樣也可以吧。。
{
b=a;
for(int j=i; j<num; j++)
{
if(b->power<a->power)
swap(a->coefficient,b->coefficient),swap(a->power,b->power);
b=b->next;
}
a=a->next;
}
a=head->next;
for(int i=0; i<num; i++) //合並同類項
{
if(a->coefficient==0)
{
a=a->next;
continue;
}
b=a->next;
for(int j=i+1; j<num; j++)
{
if(b->power!=a->power)
break;
a->coefficient+=b->coefficient;
b->coefficient=0;
b=b->next;
}
a=a->next;
}
int newnum=0;
a=head->next;
tail=a;
Xiang *p=head->next;
for(int i=0; i<num; i++)//去0 把利用已有的結構 還是改數非零的前移最後尾結點提前
{
if(a->coefficient!=0)
{
p->coefficient=a->coefficient;
p->power=a->power;
tail=p;
p=p->next;
newnum++;
}
a=a->next;
}
tail->next=NULL;
num=newnum;
}
polynomial polynomial::qiuhe(polynomial p1,polynomial p2)
{
polynomial ans;
Xiang *p;
p=p1.head->next;
for(int i=0; i<p1.num; i++)
ans.addXiang(p->coefficient,p->power),p=p->next;
p=p2.head->next;
for(int i=0; i<p2.num; i++)
ans.addXiang(p->coefficient,p->power),p=p->next;
ans.sort();
return ans;
}
polynomial polynomial::qiucha(polynomial p1,polynomial p2)
{
polynomial ans;
Xiang *p;
p=p1.head->next;
for(int i=0; i<p1.num; i++)
ans.addXiang(p->coefficient,p->power),p=p->next;
p=p2.head->next;
for(int i=0; i<p2.num; i++)
ans.addXiang(-p->coefficient,p->power),p=p->next;
ans.sort();
return ans;
}
polynomial polynomial::chengji(polynomial p1,polynomial p2)
{
polynomial ans;
Xiang *p,*q;
q=p2.head->next;
for(int i=0; i<p2.num; i++)
{
p=p1.head->next;
for(int j=0; j<p1.num; j++)
{
ans.addXiang(p->coefficient*q->coefficient,p->power+q->power);
p=p->next;
}
q=q->next;
ans.sort();
}
return ans;
}
polynomial polynomial:: operator+(polynomial p2)
{
polynomial p1;
return p1.qiuhe(*this,p2);
}
polynomial polynomial:: operator-(polynomial p2)
{
polynomial p1;
return p1.qiucha(*this,p2);
}
polynomial polynomial:: operator*(polynomial p2)
{
polynomial p1;
return p1.chengji(*this,p2);
}
int main()
{
polynomial p,ans,q;
p.input();
p.displayup();
p.displaydown();
p.addXiang(1,5);
p.displayup();
q.input();
q.displayup();
ans=p+q;
ans.displayup();
ans=p-q;
ans.displayup();
ans=p*q;
ans.displayup();
return 0;
}
最後更新：2017-04-02 00:06:57