线性表(双向链表)的C++实现

在这里我们创建一个DList类来实现双向链表.顾名思义,双向链表是指一个节点具有两个指针,其中一个指针是指向下一个节点,另一个节点是指向上一个节点,这种数据结构比单向链表的好处是很明显的,因为单向链表只保存一下个节点的指针,所以要得到上一个节点的地址却要花一点时间.其实单向以及双向链表的实现是大同小异的,只不过要记住一点:双向链表具有两个指针,而且这两个指针要同时指向上一个和下一个节点,这一点在任何时候,任何状态下的节点中都不能改变.

所以,我们要在单向链表的基础上,在Link类中,增加了一个指针,那么就必须要修改该类的构造函数.在这里我们使用了扩展型的Link类,即它重载了new和delete运算符,即由我们来决定内存的创建以及释放.而这些代码保存入Link.h文件中.而List类还是以纯虚函数的形式出现,它的内容与单向链表以及顺序表中的同名文件完全相同.
而DList类由DList.h和Dlist.cpp文件实现,下面是这些文件的内容:
List.h文件:
//////////////////////////////////////////////////////////////////////////////////
//定义一个虚类,用以设计线性表的ADT.在该类中,所有的成员函数必须作为虚函数,并
//且不能包含它们的定义.
//////////////////////////////////////////////////////////////////////////////////
template <class type>
class List
{
public:
 virtual void Clear() =0;   //用于清除原来的数据,并初始化数据成员
 virtual bool Insert(const type&) =0;  //从当前位置插入一个数值.
 virtual bool Append(const type&) =0;  //从线性表最后插入一个值.
 virtual bool Removed(type&) =0;  //从当前位置删除数据,并把删除的数据返回.
 virtual void SetStart() =0;   //设置当前位置为表头.
 virtual void SetEnd() =0;   //设置当前位置为表尾.
 virtual void Prev() =0;   //当前位置向前移动一个元素.
 virtual void Next() =0;   //当前位置向后移动一个元素.
 virtual bool SetPos(int) =0;   //设置当前位置.
 virtual int LeftLength() =0;  //返回当前位置左边的元素个数.
 virtual int RightLength() =0;  //返回当前位置右边的元素个数.
 virtual int ItemNumber() =0;  //返回总节点数.
 virtual void GetValue(type&) =0;  //返回当前位置的数值.
 virtual void Print() const =0;  //显示数值元素值以及个数.
 virtual bool Paixu() =0;   //对数组的排序.
};

Link.h文件:
///////////////////////////////////////////////////////////////////////////
//定义一个数据节点的实现.
///////////////////////////////////////////////////////////////////////////
template <class type>
class Link
{
public:
 Link<type> *prev;   //前节点指针
 type data;    //数值
 Link<type> *next;   //后节点指针
 
Link(const type&,Link<type> * =NULL,Link<type> * =NULL);
 Link(Link<type> * =NULL,Link<type> * =NULL);  //两个构造函数,用于简化对成员的初始化.
 ~Link();    //析构函数,真正用系统级的delete操作释放内存.
 void* operator new(size_t);
 void operator delete(void*);  //在Link类中,重载new和delete运算符.
private:
 static Link<type> *freelist;  //静态成员,所的对象共享同一个成员.
};
///////////////////////////////////////////////////////////////////////////
//两个构造函数以及一个析构函数的实现.
///////////////////////////////////////////////////////////////////////////
template <class type>
Link<type>::Link(const type &val,Link<type> *p,Link<type> *n)
{
 prev=p;
 data=val;
 next=n;
}
template <class type>
Link<type>::Link(Link<type> *p,Link<type> *n)
{
 prev=p;
 next=n;
}
///////////////////////////////////////////////////////////////////////////
//Link类中,在析构函数中,定义系统级的delete操作符,来释放内存空间,因为LList类
//的析构函数只是调用Link类的delete重载函数来释放Link类的对象,而重载函数只是
//将释放的节点的内存保存入缓冲区中,所以在Link类中要定义一个析构函数实现真正
//的释放空间.而我们只用释放我们定义的缓冲区的空间就完成了LList类和Link类中
//定义的任何Link类的对象.
///////////////////////////////////////////////////////////////////////////
template <class type>
Link<type>::~Link()
{
 Link<type> *temp;
 while(freelist)
 {
  temp=freelist;
  freelist=freelist->next;
  ::delete temp;
 }
}
///////////////////////////////////////////////////////////////////////////
//对私有静态成员进行初始化.
///////////////////////////////////////////////////////////////////////////
template <class type>
Link<type>* Link<type>::freelist=NULL;  //可以直接在类外面初始化静态成员,注意格式.
///////////////////////////////////////////////////////////////////////////
//new和delete运算符的重载函数,用于自定义一个缓冲区,然后new和delete操作在该
//缓冲区中操作,当该缓冲区为空时才真正执行系统级的new和delete操作,这样不仅不
//会造成空间的浪费,而且还会大大缩小内存分配和释放的时间.其实该缓冲区为一个叫
//做栈的数据结构,该结构在后面分析.
///////////////////////////////////////////////////////////////////////////
template <class type>
void* Link<type>::operator new(size_t)
{
 if(freelist==NULL)
  return ::new Link<type>; //如果缓冲区为空时,才调用系统级的new返回空间.
 Link<type> *temp=freelist;  //否则返回缓冲区最顶端的空间.
 freelist=freelist->next;  //缓冲区指针释放一个节点空间.
 return temp;    //返回得到的空间.
}
template <class type>
void Link<type>::operator delete(void *p)
{
 ((Link<type>*)p)->next=freelist; //将删除的节点保存入缓冲区的顶端.注意要加括号.
 freelist=((Link<type>*)p);  //freelist重新指向新的缓冲区顶端.
 return;
}

DList.h文件:
#include "List.h"
#include "Link.h"
////////////////////////////////////////////////////////////////////////////
//DList类的实现,它是一个双向链表,它继承于List类,而使用Link类作为节点来创建一
//个双向链表.
////////////////////////////////////////////////////////////////////////////
template <class type>
class DList :public List<type>
{
public:
 DList();
 ~DList();
 void Clear();
 bool Insert(const type&);
 bool Append(const type&);
 bool Removed(type&);
 bool SetPos(int);
 void SetStart();
 void SetEnd();
 void Prev();
 void Next();
 int LeftLength();
 int RightLength();
 int ItemNumber();
 void GetValue(type&);
 void Print() const;
 bool Paixu();
private:
 Link<type> *head;
 Link<type> *current;
 Link<type> *tail;
 int leftNumber;
 int rightNumber;
 void RemoveAll();
 void Init();
};

DList.cpp文件:
#include "stdafx.h"
#include <iostream>
#include "DList.h"
using namespace std;
////////////////////////////////////////////////////////////////////////////
//对DList类的成员函数的实现.
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
//两个私有成员函数的实现,它用于清空链表以及初始化链表.
////////////////////////////////////////////////////////////////////////////
template <class type>
void DList<type>::RemoveAll()
{
 while(head)
 {
  current=head;   //指向前一个节点.
  head=head->next;  //指向下一个节点.
  delete current;   //删除前一个节点.
 }     //循环直到删除完所有节点为止.
 return;
}
template <class type>
void DList<type>::Init()
{
 head=current=tail=new Link<type>; //创建一个空的头节点,前驱和后继节点都为NULL
 leftNumber=rightNumber=0;  //左右节点数都为0.
 return;
}
////////////////////////////////////////////////////////////////////////////
//DList类的构造以及析构函数的实现.
////////////////////////////////////////////////////////////////////////////
template <class type>
DList<type>::DList()
{
 Init();     //初始化DList类中的所有私有成员.
}
template <class type>
DList<type>::~DList()
{
 RemoveAll();    //清除所有节点.即清空链表.
}
////////////////////////////////////////////////////////////////////////////
//对链表进行初始化,插入,删除,追加函数的实现.
////////////////////////////////////////////////////////////////////////////
template <class type>
void DList<type>::Clear()
{
 RemoveAll();   //先清空所有节点内存.
 Init();    //再初始化链表.
}
template <class type>
bool DList<type>::Insert(const type &val)
{
 current->next=new Link<type>(val,current,current->next);//一句话实现插入操作.
 if(current->next->next)    //新插入的节点不是尾节点.
  current->next->next->prev=current->next;//第三个节点前驱节点设为插入的节点.
 else
  tail=current->next;  //如果插入的节点为最后的节点,那么调整尾节点.
 rightNumber++;
 return true;
}
template <class type>
bool DList<type>::Append(const type &val)
{
 tail=tail->next=new Link<type>(val,tail,NULL); //一句完成追加.
 rightNumber++;
 return true;
}
template <class type>
bool DList<type>::Removed(type &val)
{
 if(!current->next)
  return false;   //如果下一个节点为空,即当前节点为尾节点.
 val=current->next->data;  //返回要删除节点的数值.
 Link<type> *temp=current->next;  //temp指向要删除节点.
 current->next=temp->next;  //修改current节点的后继节点.
 if(temp->next)
  temp->next->prev=current; //修改删除的节点后的那个节点的前驱节点.
 else
  tail=current;   //如果删除的节点为尾节点,那么修改尾节点的值.
 delete temp;    //删除节点.
 rightNumber--;
 return true;
}
////////////////////////////////////////////////////////////////////////////
//对当前位置的指针的操作的函数.即将指针设为头节点,尾节点,向前向后移动当前指
//针,以前设置当前指位置.
////////////////////////////////////////////////////////////////////////////
template <class type>
bool DList<type>::SetPos(int pos)
{
 if(pos<0 || pos>rightNumber+leftNumber)
  return false;
 current=head;    //当前位置初始化为头节点.
 for(int i=1;i<=pos;i++)
  current=current->next;
 int Number=leftNumber+rightNumber; //Number值为节点总数.
 leftNumber=pos;
 rightNumber=Number-pos;   //重新计算左右节点个数.
 return true;
}
template <class type>
void DList<type>::SetStart()
{
 current=head;    //当前节点设为头节点.
 rightNumber+=leftNumber;
 leftNumber=0;    //重新计算左右节点个数.
 return;
}
template <class type>
void DList<type>::SetEnd()
{
 current=tail;    //当前节点为尾节点.
 leftNumber+=rightNumber;
 rightNumber=0;    //重新计算左右节点个数.
 return;
}
template <class type>
void DList<type>::Prev()
{
 if(current!=head)   //如果当前节点不是头节点.
  current=current->prev;  //那么指向前一节点.
 return;
}
template <class type>
void DList<type>::Next()
{
 if(current!=tail)   //如果当前节点不是尾节点.
  current=current->next;  //那么指向下一个节点.
 return;
}
////////////////////////////////////////////////////////////////////////////
//返回左右节点以前总节点数的成员函数.
////////////////////////////////////////////////////////////////////////////
template <class type>
int DList<type>::LeftLength()
{
 return leftNumber;
}
template <class type>
int DList<type>::RightLength()
{
 return rightNumber;
}
template <class type>
int DList<type>::ItemNumber()
{
 return leftNumber+rightNumber;
}
////////////////////////////////////////////////////////////////////////////
//获取节点数值,打印链表以及对链表节点排序的成员函数
////////////////////////////////////////////////////////////////////////////
template <class type>
void DList<type>::GetValue(type &val)
{
 if(current->next)
  val=current->next->data; //如果该节点不是尾节点,那么返回下一节点的值.
 return;
}
template <class type>
void DList<type>::Print() const
{
 Link<type> *temp=head->next;  //temp指向第一个有效节点.
 while(temp)   
 {
  cout<<temp->data<<"  ";
  temp=temp->next;  //如果链表不空的话,那么输出数据成员的值.
 }     //并指向下一个节点.
 cout<<endl;
 return;
}
template <class type>
bool DList<type>::Paixu()
{
 Link<type> *p,*q;
 type temp;
 p=head->next;    //指向第一个有效节点.
 if(!p)
  return false;
 while(p)
 {
  q=p->next;
  while(q)   //指向下一个节点.
  {
   if(p->data>q->data)
   {
    temp=p->data; //将两个相邻节点的数值进行比较,小的放在前.
    p->data=q->data;
    q->data=temp;
   }
   q=q->next;  //指向下一个节点.
  }
  p=p->next;   //指向下一个节点.
 }
 return true;
}
////////////////////////////////////////////////////////////////////////////
//这是一个DList类的测试程序.
////////////////////////////////////////////////////////////////////////////
int _tmain(int argc, _TCHAR* argv[])
{
 int result;
 DList<int> value;
////////////////////////////////////////////////////////////////////////////
//测试Clear(),Insert(),Removed(),Append()这几个函数.
////////////////////////////////////////////////////////////////////////////
 value.Clear();    //清除链表并重建头节点.
 value.Insert(3);
 value.Insert(2);
 value.Insert(1);
 value.Append(4);   //插入三个数值,后面再追加一个数值.
 value.Print();    //输出链表节点数值.
 value.SetPos(2);   //设置当前位置为2
 value.Removed(result);   //删除第三个节点(删除的节点为当前节点之后)
 value.Print();    //再输出删除后的链表.
 cout<<result<<endl;   //输出删除的节点的数值.
////////////////////////////////////////////////////////////////////////////
//测试SetPos(),SetStart(),SetEnd(),Next(),Prev()一共五个函数.
////////////////////////////////////////////////////////////////////////////
 value.SetStart();
 value.Insert(5);
 value.SetEnd();
 value.Insert(6);
 value.Print();    //在链表头以及链表尾增加两个节点并输出.
 value.SetPos(3);
 value.Prev();
 value.GetValue(result);
 cout<<result<<"  ";
 value.SetPos(3);
 value.Next();
 value.GetValue(result);
 cout<<result<<endl;   //输出当前位置之前和之后的两个节点的值.
////////////////////////////////////////////////////////////////////////////
//测试LeftLength(),RightLength(),ItemNumber()函数.
////////////////////////////////////////////////////////////////////////////
 cout<<value.LeftLength()<<"  "<<value.RightLength()<<"  ";
 cout<<value.ItemNumber()<<endl;
////////////////////////////////////////////////////////////////////////////
//测试Print(),GetValue(),Paixu()函数.
////////////////////////////////////////////////////////////////////////////
 value.Clear();    //清除链表中所有的节点,并初始化.
 for(int i=1;i<6;i++)
  value.Insert(i);
 value.Print();    //测试Print()函数.
 value.Paixu();    //对链表进行排序.
 value.Print();    //对排序后的输出.
 int Number;
 Number=value.ItemNumber();  //保存总节点数.
 for(int i=0;i<Number;i++)  //该循环实现打印链表的功能,与Print()的功能相同.
 {
  value.SetPos(i);  //定位节点.
  value.GetValue(result);  //得到某个节点的值.
  cout<<result<<"  ";
 }
 cout<<endl;
 return 0;
}
上面的DList类的成员函数主要的改变是在这几个函数中:
Removed();
Insert();
Append();
Prev();
如果对一个节点进行操作时,必须考虑到本身节点的前驱和后继指针,前一个节点的后继指针,以及后一个节点的前驱指针的影响,所以在上面列出的四个函数中,前三个函数代码量的增加实际上是考虑到这几个指针的影响.而由于双向链表的便利,所以Prev()函数可以写得非常简单,即只用一条语句就可以完成向后移动一个节点.
而大部分的代码与单向链表类似,所以不再说明,况且上面的代码包含了详细的注释.

本文来源 我爱IT技术网 http://www.52ij.com/jishu/1761.html 转载请保留链接。