|
//可通用的单链表
#include<iostream.h>
#include<stdio.h>
class MultiNomial//多项式
{
public:
int coefficient;
int index;
MultiNomial();//确保灵活性
MultiNomial(int c,int i);//确保调用时方便
~MultiNomial();//直接用一个输出就行了,这里没有必要用delete
friend istream& operator>>(istream& in, MultiNomial& a);//不定义display,按坐标形式输出
friend ostream& operator<<(ostream& out,const MultiNomial& a);
friend MultiNomial operator+( const MultiNomial& p,const MultiNomial& q);
bool operator<(const MultiNomial& parameter);//这里要说明的是:这时的"=="是系统自带的
bool operator<=(const MultiNomial& parameter);
bool operator>(const MultiNomial& parameter);
bool operator>=(const MultiNomial& parameter);
bool operator==(const MultiNomial& parameter);
bool operator!=(const MultiNomial& parameter);
void pursuit();//求导
void Negative();//将系数变成负的
};
MultiNomial operator+(const MultiNomial& p,const MultiNomial& q)
{
return MultiNomial(p.coefficient+q.coefficient,p.index);
}
ostream& operator<<(ostream& out,const MultiNomial& a)
{
out<<'('<<a.coefficient<<','<<a.index<<')'<<" ";
return out;
}
void MultiNomial::pursuit()
{
coefficient*=index;
index-=1;
}
MultiNomial::MultiNomial()
{
cout<<"输入单项式的参数:"<<endl;
cin>>coefficient>>index;
getchar();
cout<<endl;
}
MultiNomial::MultiNomial(int c,int i)
{cout<<"单项式建立"<<endl;coefficient=c;index=i;}
MultiNomial::~MultiNomial()
{
cout<<"单项式删除"<<endl;
}
istream& operator>>(istream& in, MultiNomial& a)
{
cout<<"进行单项式的输入"<<endl;
cout<<"其系数是"<<endl;
in>>a.coefficient;
getchar();
cout<<"其指数是:"<<endl;
in>>a.index;
getchar();
return in;
}
void MultiNomial::Negative()//单个点数据变负,在链表中要用到它的
{
coefficient=-coefficient;
}
bool MultiNomial::operator<(const MultiNomial& parameter)
{ int i;
cout<<"如果对系数进行比较请输入1,对指数比较请输入0"<<endl;
cin>>i;
getchar();
if(i==1)
{
if(coefficient<parameter.coefficient)
return true;
else return false;
}
else
{
if(index<parameter.index)
return true;
else return false;
}
}
bool MultiNomial::operator<=(const MultiNomial& parameter)
{
int i;
cout<<"如果对系数进行比较请输入1,对指数比较请输入0"<<endl;
cin>>i;
getchar();
if(i==1)
{
if(coefficient<=parameter.coefficient)
return true;
else return false;
}
else
{
if(index<=parameter.index)
return true;
else return false;
}
}
bool MultiNomial::operator>(const MultiNomial& parameter)
{
int i;
cout<<"如果对系数进行比较请输入1,对指数比较请输入0"<<endl;
cin>>i;
getchar();
if(i==1)
{
if(coefficient>parameter.coefficient)
return true;
else return false;
}
else
{
if(index>parameter.index)
return true;
else return false;
}
}
bool MultiNomial::operator>=(const MultiNomial& parameter)
{
int i;
cout<<"如果对系数进行比较请输入1,对指数比较请输入0"<<endl;
cin>>i;
getchar();
if(i==1)
{
if(coefficient>=parameter.coefficient)
return true;
else return false;
}
else
{
if(index>=parameter.index)
return true;
else return false;
}
}
bool MultiNomial::operator==(const MultiNomial& parameter)
{
int i;
cout<<"如果对系数进行比较请输入1,对指数比较请输入0"<<endl;
cin>>i;
getchar();
if(i==1)
{
if(coefficient==parameter.coefficient)
return true;
else return false;
}
else
{
if(index==parameter.index)
return true;
else return false;
}
}
bool MultiNomial::operator!=(const MultiNomial& parameter)
{
int i;
cout<<"如果对系数进行比较请输入1,对指数比较请输入0"<<endl;
cin>>i;
getchar();
if(i==1)
{
if(coefficient!=parameter.coefficient)
return true;
else return false;
}
else
{
if(index!=parameter.index)
return true;
else return false;
}
}
//对于多项式的求和运算,就只要在SLink中对combine进行一个小的改变,即相等时的变化
template<class T>
struct Node//用class 与struct都一样的,在C++中没有区别
{
public: T data;//数据成员设为公有易于访问
Node* next;
Node(const T& d): data(d),next(0){cout<<"新建结点"<<endl;}//常引用的好处,实参可以是常数
Node(){
cout<<"无参的构造结点"<<endl;next=NULL;}//对next的值的添加,是为了在添加结点时,不出错,是个关键,否则不能运行
~Node()
{
cout<<"结点的析构,释放结点空间"<<endl;//node的析构,会调用T的析构函数
}
T& GetElem()
{
return data;
}
};
template<class T>//这一行不可少
class SLink
{
private:
Node<T>* head;//指向头结点的头指针
int length;//不包括头结点
public:
SLink();
~SLink();
int GetLength();//要加上返回值型
Node<T>* GetNode(int i);
Node<T>* Find(const T& data);
bool Add(int i,const T& a);
bool Remove(int i);
void Display();
void Display(Node<T>* p);
void Combine(Node<T>* p,Node<T>* q);//传递两个链表的头结点位置
bool Exchange(int i,int j);
Node<T>* Max();
void SelectSort();
void Reverse();
Node<T>* HalfIndex(const T& a);
void Sum(Node<T>* p,Node<T>* q);
void Pursuit();
};
template<class T>
void SLink<T>::Pursuit()
{
cout<<"进行求导数的运算开始"<<endl;
Node<T>* pin=head->next;
while(pin!=NULL)
{
(pin->data).pursuit();
pin=pin->next;
}
cout<<"求导数运算结束"<<endl;
}
template<class T>
void SLink<T>::Sum(Node<T>* p,Node<T>* q)
{
cout<<"当前正在进行求和,按的是指数来求的"<<endl;
int i=1;
while(p!=NULL && q!=NULL)
{
if(p->data>q->data)
{
Add(i,q->data);i++;q=q->next;}
else if(p->data<q->data)
{
Add(i,p->data);i++;p=p->next;}
else
{ cout<<"存在可加的项,接下来按系数比较"<<endl;
T a=q->data;
a.Negative();
if(p->data==a) cout<<"存在相反的项"<<endl;//这是在对象级的运算,这里的空语句有一定的好处
else
{
cout<<"没有相反项"<<endl;
Add(i,p->data+q->data);i++;
}
p=p->next;
q=q->next;
}
}
while(p!=NULL)
{
Add(i,p->data);i++;p=p->next;
}
while(q!=NULL)
{
Add(i,q->data);i++;q=q->next;}
cout<<"求和运算结束"<<endl;
}
template<class T>
SLink<T>::SLink()
{
cout<<"创建链表"<<endl;
head=new Node<T> ;
length=0;
cout<<"创建工作完成"<<endl;
}
template<class T>
int SLink<T>::GetLength()//当这个类产生派生类，可直接通过这个接口来访问
{
return length;
}
template<class T>
Node<T>* SLink<T>::GetNode(int i)//I表示位置
{
if(i<1 || i>length)
{
cout<<"不存在这样的结点元素"<<endl;
return NULL;
}
Node<T>* pin=head->next;
int flag=1;//记录位置
while(flag!=i)
{
pin=pin->next;
flag++;
}
return pin;
}
template<class T>
Node<T>* SLink<T>::Find(const T& data)
{
Node<T>* pin=head->next;
while( pin->data!=data)//顺序不一样,执行的效率会不一样
{
pin=pin->next;
if(pin==NULL)
{
cout<<"没有找到这个元素"<<endl;//这个if放在外面时,可读性也有影响,可见这个代码的位置也可是可读性的一种
return NULL;
}
}
cout<<"找到这样的元素"<<endl;
return pin;
}
template<class T>
bool SLink<T>::Add(int i,const T& a)// i表示的是位置//SLink易忘记
{
if(i<1 || i>length+1)
{
cout<<"不能插入元素"<<endl;
return false;
}
int location=1;
Node<T>* pin=head;
Node<T>* p=new Node<T> (a);//这里没有传Node型号参数,故要用到new,这里不用Node时,我们函数调用时更简单,整个框架都简单了
while(location!=i)//千万不能写成i-1,location反映了pin指的位置
{
pin=pin->next;
location++;
}
p->next=pin->next;
pin->next=p;
length++;
return true;
}
template<class T>
bool SLink<T>::Remove(int i)
{
if(i<1 || i>length)
{
cout<<"没有这样的结点元素"<<endl;
return false;
}
int location=1;
Node<T>* pin=head;//pin移动一次,指向i,pin一定指向i-1
while(location!=i)//反正i总是大于等于1
{
pin=pin->next;
location++;//循环执行i-1次
}
Node<T>* temp=NULL,*q=NULL;
q=pin->next;
temp=pin->next->next;
delete q;
pin->next=temp;
length--;
cout<<"删了该元素"<<endl;
return true;
}
template<class T>
void SLink<T>::Display()
{
Node<T>* pin;
pin=head->next;
while(pin!=NULL)
{
cout<<pin->data<<" ";
pin=pin->next;
}
cout<<'\n';
}
template<class T>
void SLink<T>::Display(Node<T>* p)
{
cout<<p->data<<endl;
}
template<class T>
SLink<T>::~SLink()
{
/* Node* first=head;
Node* rear=head->next;
while(first!=NULL)
{
if(rear!=NULL)
{
delete first;
first=rear;
rear=rear->next;
}
else
{
delete first;
break;
}
}*/
//上面的这段代码的思想在双链时可到,但是此处没有这个必要
cout<<"链表的析构"<<endl;
Node<T>* pin=head->next;
while(pin!=NULL)
{
head->next=pin->next;
delete pin;
pin=head->next;
}
delete head;
}
template<class T>
void SLink<T>::Combine(Node<T>* p,Node<T>* q)//逐位的连接
{
int i=1;
while(p!=NULL && q!=NULL)
{
if(p->data>q->data)
{
Add(i,q->data);i++;q=q->next;}
else if(p->data<q->data)
{
Add(i,p->data);i++;p=p->next;}
else
{
Add(i,p->data);i++;p=p->next;
Add(i,q->data);i++;q=q->next;
}
}
while(p!=NULL)
{
Add(i,p->data);i++;p=p->next;
}
while(q!=NULL)
{
Add(i,q->data);i++;q=q->next;}
}
template<class T>
bool SLink<T>::Exchange(int i,int j)
{
Node<T>* p=GetNode(i);
Node<T>* q=GetNode(j);
T temp;
cout<<"要进行交换时,要定义临时变量"<<endl;
temp=p->data;
p->data=q->data;
q->data=temp;
return true;
}
template<class T>
Node<T>* SLink<T>::Max()
{
Node<T>* later=head->next;//存放最大元素地址
Node<T>* pin=later->next;
while(pin!=NULL)
{
if(pin->data>later->data)
later=pin;
pin=pin->next;//这个语句要写在if外
}
cout<<"最大元素是"<<later->data<<endl;
return later;
}
template<class T>
void SLink<T>::SelectSort()
{
cout<<"开始排序"<<endl;
int i,k;
for(i=1;i<length;i++)
{
k=i;//当I要更新是,i指向下一次要比较的起点,而将i给k时,是把当前的起点给它
for(int j=i+1;j<=length;j++)
{
Node<T>* p=GetNode(k);Node<T>* q=GetNode(j);
if(p->data>q->data)
k=j;//但是k会自动变化的,指向最小位置
}
Exchange(k,i);//将当前要交换的i与k交换
}
cout<<"结束排序"<<endl;
}
template<class T>
void SLink<T>::Reverse()//可用于判断回文,即先将其倒序,再比较字符串否相等
{
int i=length;//这里可以看到一点,一个判断回文的问题(复杂问题),在经过我们的一步步分解之后,能够较快的解决.(简单问题),这是一种重要的思路
int j=1;//当然,这其中什么才是最基本的呢?这就是数据结构要学习的.
while(i>j)
{
Exchange(i,j);
i--;
j++;
}
}
template<class T>
Node<T>* SLink<T>::HalfIndex(const T& a )
{
Node<T>* pin=new Node<T>(a);
int head=1;
int end=length;
Node<T>* p;
while(head<=end)
{
p=GetNode((head+end)/2);
if(p->data<pin->data)
head=1+(head+end)/2;
else if(p->data==pin->data)
{cout<<"有这样的元素"<<endl; return p;}
else end=(end+head)/2-1;
}
cout<<"没有这样的元素"<<endl;
return NULL;
}
/*对于某些函数要返回指针的原由,这里作几点说明:
1.关键字的检索,如Find,由于这是一个结点,可以说这是一个数据元素,它可能包含多个数据项,若我们想知道这个结点的其它的信息,如成绩的查询
是以学号来看的.即按学号搜索,若要知道该学生的各科分数,则不仅是返回某一项,而是所有的成绩.
2.单链表不是可实现机随访问的,能得其地址,固然好,因为以后要访问它,是比较困难的.
排序的问题:
这里用的是模板,可谓是泛型的编程,我们只要T数据类型有“==”、“>=”、“<=”、“!=”的重载即可扩充排序这个基本的算法*/
void main()
{
SLink<MultiNomial> a,b,j;//第一数是没有用的.
MultiNomial h(3,5),c(-2,12),d(7,10),e(1,4),f(2,12),g(8,11);
a.Add(1,h);
a.Add(2,c);
a.Add(3,d);
a.Display();
//\\\\\\\\\a.Pursuit();
//a.Display();
b.Add(1,e);
b.Add(2,f);
b.Add(3,g);
b.Display();
a.SelectSort();
a.Display();
b.SelectSort();
b.Display();
Node<MultiNomial>* pin=a.GetNode(1),*q=b.GetNode(1);
j.Sum(pin,q);
j.Display();
}
|
