实验二 线性表的应用(双向链表)
注意事项:
注意输出多项式的时候,当一项的系数为0时该项不输出,系数为1时省略1,系数为-1时省略1保留负号,除第一项之外系数为负数时该项需要打括号,次数为0时该项为系数的值,次数为负数时需要将次数括起来。
定义的sort函数是根据选择排序的思想将多项式降幂排列的。
定义的add函数实现的前提是两个多项式都有序(降幂),因此两个多项式相加前先排序。
这里将尾结点处理为同头结点一样,数据域为空。头结点的前驱结点为NULL,尾结点的后继结点为NULL。
输入的多项式不要出现两项或两项以上次数相同的情况。
下列代码仅供参考。
运行结果:
Link.h
#include <iostream>
using namespace std;
#ifndef _Link
#define _Link
namespace wangzhe
{
template<typename E>
class Link
{
public:
E coeff;//coefficient,系数
E index;//index,次数
Link *prev;
Link *next;
Link(const E& ele1,const E& ele2,Link* prevp=NULL,Link* nextp =NULL)
{
coeff=ele1;
index=ele2;
prev=prevp;
next=nextp;
}
Link(Link* prevp=NULL,Link* nextp=NULL)
{
prev=prevp;
next=nextp;
}
};
}
#endif
List.h
#include <iostream>
using namespace std;
#ifndef _List
#define _List
namespace wangzhe
{
template <typename E>
class List
{
private:
void operator =(const List&) {}
List(const List&) {}
public:
List() {}
virtual ~List() {}
virtual void clear() =0;
virtual void insert(const E& it1,const E& it2) =0;
virtual void append(const E& it1,const E& it2) =0;
virtual E remove() =0;
virtual void moveToStart() =0;
virtual void next() =0;
virtual int length() const =0;
virtual const E& getValue() const =0;
};
}
#endif
LList.h
#include<iostream>
using namespace std;
#include"List.h"
#include"Link.h"
#ifndef _LList
#define _LList
namespace wangzhe
{
template<typename E>
class LList:public List<E>
{
private:
Link<E>* head;
Link<E>* tail;
Link<E>* curr;
int cnt;
void init();
void removeall();
public:
LList(int size);
~LList();
void print() const;
void clear();
void insert(const E& it1,const E& it2);
void append(const E& it1,const E& it2);
E remove();
void moveToStart();
void next();
int length() const;
const E& getValue() const;
void add(Link<E>* aug);
Link<E>* HEAD();//返回头指针
Link<E>* TAIL();//返回尾指针
void swap(Link<E>* p,Link<E>* q);//交换p,q指向的结点位置
void sort();//降幂排列
};
}
#endif
LList.cpp
#include<iostream>
using namespace std;
#include"LList.h"
namespace wangzhe
{
template<typename E>
void LList<E>::init()
{
curr=head=new Link<E>;
tail=new Link<E>;
head->next=tail;
tail->prev=head;
cnt=0;
}
template<typename E>
void LList<E>::removeall()
{
while(head!=NULL)
{
curr=head;
head=head->next;
delete curr;
}
}
template<typename E>
LList<E>::LList(int size)
{
init();
}
template<typename E>
LList<E>::~LList()
{
removeall();
}
template<typename E>
void LList<E>::print() const
{
Link<E>* temp=head->next;
int cnt=0;//有效的项数
while(temp!=tail)
{
if(temp->coeff!=0)
{
cnt++;
if(cnt>1) cout<<'+';
if(temp->index==0)
{
cout<<temp->coeff;
}
else
{
if(temp->coeff!=1&&temp->coeff!=-1)
{
if(temp->coeff<0&&cnt>1) cout<<"(";
cout<<temp->coeff;
if(temp->index!=1)
{
cout<<"x^";
if(temp->index<0) cout<<"(";
cout<<temp->index;
if(temp->index<0) cout<<")";
}
else cout<<"x";
if(temp->coeff<0&&cnt>1) cout<<")";
}
else if(temp->coeff==1)
{
if(temp->index!=1)
{
cout<<"x^";
if(temp->index<0) cout<<"(";
cout<<temp->index;
if(temp->index<0) cout<<")";
}
else cout<<"x";
}
else if(temp->coeff==-1)
{
if(cnt>1) cout<<"(";
cout<<"-";
if(temp->index!=1)
{
cout<<"x^";
if(temp->index<0) cout<<"(";
cout<<temp->index;
if(temp->index<0) cout<<")";
}
else cout<<"x";
if(cnt>1) cout<<")";
}
}
}
temp=temp->next;
}
if(!cnt) cout<<'0';
}
template<typename E>
void LList<E>::clear()
{
removeall();
init();
}
template<typename E>
void LList<E>::insert(const E& it1,const E& it2)
{
curr->next=curr->next->prev=new Link<E>(it1,it2,curr,curr->next);
cnt++;
}
template<typename E>
void LList<E>::append(const E& it1,const E& it2)
{
tail->prev=tail->prev->next=new Link<E>(it1,it2,tail->prev,tail);
cnt++;
}
template<typename E>
E LList<E>::remove()//删除当前指向的下一个结点,返回次数
{
if(curr->next==tail)
{
cout<<"No element"<<endl;
return NULL;
}
E it=curr->next->index;
Link<E>* temp=curr->next;
curr->next->next->prev=curr;
curr->next=curr->next->next;
delete temp;
cnt--;
return it;
}
template<typename E>
void LList<E>::moveToStart()
{
curr=head;
}
template<typename E>
void LList<E>::next()
{
if(curr==tail)
{
cout<<"curr is the tail\n";
return;
}
curr=curr->next;
}
template<typename E>
int LList<E>::length() const
{
return cnt;
}
template<typename E>
const E& LList<E>::getValue() const
{
if(curr->next==NULL)
{
cout<<"No value\n";
return -1;
}
return curr->next->index;
}
template<typename E>
void LList<E>::add(Link<E>* aug)
{
Link<E>* p,* q;
for(p=aug->next;p->next!=NULL;p=p->next)
{
for(q=head->next;q!=tail;q=q->next)
{
if(p->index==q->index)
{
q->coeff+=p->coeff;
break;
}
else if(p->index>q->index)
{
Link<E>* temp=new Link<E>(p->coeff,p->index,q->prev,q);
q->prev->next=temp;
q->prev=temp;
break;
}
}
if(q==tail)//到达末尾新增结点
{
Link<E>* temp=new Link<E>(p->coeff,p->index,tail->prev,tail);
tail->prev=tail->prev->next=temp;
}
}
delete p;
delete q;
}
template<typename E>
Link<E>* LList<E>::HEAD()
{
return head;
}
template<typename E>
void LList<E>::swap(Link<E>* p,Link<E>* q)
{
Link<E>* temp1=new Link<E>(q->coeff,q->index,p->prev,p->next);
p->prev->next=p->next->prev=temp1;
Link<E>* temp2=new Link<E>(p->coeff,p->index,q->prev,q->next);
q->prev->next=q->next->prev=temp2;
delete p;
delete q;
}
template<typename E>
void LList<E>::sort()//选择排序
{
Link<E>* p,* q;
for(p=head->next;p->next!=tail;p=p->next)
{
Link<E>* Max=p;//最大的结点
for(q=p->next;q!=tail;q=q->next)
if(p->index<q->index)
Max=q;
if(Max!=p) swap(p,Max); //进行交换
}
delete p;
delete q;
}
}
main.cpp
#include <iostream>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
#include"LList.h"
#include"LList.cpp"
using namespace wangzhe;
int main(int argc, char** argv)
{
LList<int> a(10010),b(10010);
for(int i=1;i<=50;i++) cout<<'*';
cout<<"\n实验二:线性表的应用(双向链表实现)\n";
for(int i=1;i<=50;i++) cout<<'*';
cout<<"\n请输入第一个多项式:\n";
cout<<"项数:";
int n1;
cin>>n1;
cout<<"请依次输入"<<n1<<"项的系数和次数(如2 3 4 5代表第一项是2x^3,第二项是4x^5)\n";
for(int i=1;i<=n1;i++)
{
int co,in;
cin>>co>>in;
a.insert(co,in);
}
cout<<"\n请输入第二个多项式:\n";
cout<<"项数:";
int n2;
cin>>n2;
cout<<"请依次输入"<<n2<<"项的系数和次数(如2 3 4 5代表第一项是2x^3,第二项是4x^5)\n";
for(int i=1;i<=n2;i++)
{
int co,in;
cin>>co>>in;
b.insert(co,in);
}
a.sort();
b.sort();
cout<<"\n第一个多项式是:(降幂排列输出)\n";
a.print();
cout<<"\n第二个多项式是:(降幂排列输出)\n";
b.print() ;
cout<<endl;
a.add(b.HEAD());
cout<<"\n这两个多项式的和是:(降幂排列输出)\n";
a.print();
}