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

在前段时间我们学习了如何使用数组形式实现的线性表,那是很简单的,有些成员函数只用了一句就完成了.相对来说,链表的实现比数组实现的线性表复杂一些,不过只要理解程序在任何时候的数据成员的值,以及执行哪些操作时需要改变哪些数据成员,其实实现链表数据结构也是很简单的.

在该程序中,List.h文件也需要使用,它还是用于定义一个虚基类,而且该文件的内容完全没有改变.
而该程序新添加了一个文件Link.h,它用于定义一个节点的数据结构的类Link,用来保存有用的信息以及下一个节点的位置.因为Link类的对象需要直接访问数据成员,所以在此所有的数据成员都定义成了公有成员.而该类的构造函数起到了无可代替的作用,它将用new操作进行创建一个节点时同时给节点赋值提供了很大的方便.
而LList.h和LList.cpp文件则用于定义LList类,它实现了List虚基类的所有操作.在我们的程序中可以直接包含这几个文件来实现单向链表的数据结构.
当然,为了说明链表的数据结构,从而只使用了最简单的int类型的数据,不过我们可以扩展其功能,但是有些运算符必须要重载否则会编译错误.下面是这几个文件的内容,为了便于比较,在此再给出List.h文件内容.

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:
 type data;
 Link<type> *next;   //两个数据成员.
 
Link(const type&,Link<type> * =NULL);
 Link(Link<type> * =NULL);  //两个构造函数,用于简化对成员的初始化.
};
///////////////////////////////////////////////////////////////////////////
//两个构造函数的实现.
///////////////////////////////////////////////////////////////////////////
template <class type>
Link<type>::Link(const type &val,Link<type> *p)
{
 data=val;
 next=p;
}
template <class type>
Link<type>::Link(Link<type> *p)
{
 next=p;
}

LList.h文件:
///////////////////////////////////////////////////////////////////////////
//定义一个LList类,它继承于List类,并且它有Link类的成员,该文件定义LList类实现
//单向链表的数据结构.
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
//必要的头文件包含.
///////////////////////////////////////////////////////////////////////////
#include "List.h"
#include "Link.h"
///////////////////////////////////////////////////////////////////////////
//LList类的定义.
///////////////////////////////////////////////////////////////////////////
template <class type>
class LList :public List<type>
{
public:     //公有成员函数.
 LList();
 ~LList();
 
///////////////////////////////////////////////////////////////////////////
//注意,下面的这四个函数与当前指针有关,那么对这几个函数的操作都是基于当前指
//针指向的节点之后的节点进行操作,例如插入,删除操作.而下面与当当前指针相关的都
//以这个原则为基准.
///////////////////////////////////////////////////////////////////////////
 void Clear();
 bool Insert(const type&);
 bool Append(const type&);
 bool Removed(type &);
 void SetStart();
 void SetEnd();
 bool SetPos(int);
 void Prev();
 void Next();
 int LeftLength();
 int RightLength();
 int ItemNumber();
 bool Paixu();
 void Print() const;
 void GetValue(type &);
private:
 void Init();
 void RemoveAll();  //两个私有成员函数.
 Link<type> *head;  //头指针,它始终指向头节点,而该节点不保存有较的值.
 Link<type> *current; //当前指向针.
 Link<type> *tail;  //尾指针,用于使从节点尾添加节点操作代价为一常量值.
 int  leftNumber; //当前节点左右各有几个节点数.注意,当前节点算在右边.
 int  rightNumber;
};

LList.cpp文件:
///////////////////////////////////////////////////////////////////////////
//实现LList类的成员函数.
///////////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include <iostream>
#include "LList.h"
using namespace std;
///////////////////////////////////////////////////////////////////////////
//定义两个私有成员函数,它用于构造函数以及析构函数中.
///////////////////////////////////////////////////////////////////////////
template <class type>
void LList<type>::Init()
{
 head=current=tail=new Link<type>; //调用Link类的第二个构造函数,使next=NULL
 leftNumber=rightNumber=0;  //左右节点数均为0.
 return;
}
template <class type>
void LList<type>::RemoveAll()
{
 while(head)
 {
  current=head;
  head=head->next;
  delete current;
 }
 return;
}
///////////////////////////////////////////////////////////////////////////
//定义构造函数以及析构函数.它们只是简单的调用了上面的Init()以及RemoveAll()
//函数.注意,除了在构造函数中以外,在其它地方调用Init()函数之前必须先调用
//RemoveAll()来清除节点内存,否则产生内存泄漏.
///////////////////////////////////////////////////////////////////////////
template <class type>
LList<type>::LList()
{
 Init();
}
template <class type>
LList<type>::~LList()
{
 RemoveAll();
}
///////////////////////////////////////////////////////////////////////////
//定义对链表节点操作的函数例如清空链表,对链表节点的插入,追加,删除等式操作.
//在这里要十分注意在任何节点之前有一个头节点是不保存数据的,这一点要注意.
///////////////////////////////////////////////////////////////////////////
template <class type>
void LList<type>::Clear()
{
 RemoveAll();    //清除链表.
 Init();     //初始化链表,并创建头节点.
 return;
}
template <class type>
bool LList<type>::Insert(const type &val)
{
 current->next=new Link<type>(val,current->next); //插入节点语句.
 if(current==tail)
  tail=current->next;
 rightNumber++;      //右边节点加一.
 return true;
}
template <class type>
bool LList<type>::Append(const type &val)
{
 tail=tail->next=new Link<type>(val,NULL);  //添加一个节点.在尾部.
 rightNumber++;      //右节点数加一.
 return true;
}
template <class type>
bool LList<type>::Removed(type &val)
{
 Link<type> *temp;
 if(current==tail)
  return false;   //当前指针为尾节点,不能删除操作.
 temp=current->next;   //要删除的是当前节点之后的节点.
 if(temp==tail)    //要删除的是最后的那个节点.
  tail=current;   //使指针向后移一位.
 val=temp->data;    //返回删除节点的值.
 current->next=temp->next;  //删除节点.
 delete temp;    //删除节点所内存.
 rightNumber--;    //右边节点数减一.
 return true;
}
///////////////////////////////////////////////////////////////////////////
//定义影响当前位置指针的函数,例如使当前位置指向开头,结尾,向前移,向后移以及
//设置当前指针位置等.
///////////////////////////////////////////////////////////////////////////
template <class type>
void LList<type>::SetStart()
{
 current=head;    //指向头节点.
 rightNumber+=leftNumber;
 leftNumber=0;
 return;
}
template <class type>
void LList<type>::SetEnd()
{
 current=tail;    //指向尾节点.
 leftNumber+=rightNumber;
 rightNumber=0;
 return;
}
template <class type>
void LList<type>::Prev()
{
 Link<type> *temp=head;
 if(current==head)
  return;    //当前节点为头节点,不能再向后移了.
 while(temp->next!=current)
  temp=temp->next;  //如果下面的节点不是当前节点,那么前移一个节点.
 current=temp;    //调整当前节点,使之向后移.
 rightNumber++;    //右边节点数加一,左边减一.
 leftNumber--;
 return;
}
template <class type>
void LList<type>::Next()
{
 if(current==tail)
  return;    //如果当前节点为尾节点,那么返回.
 current=current->next;   //否则前移一个节点.
 rightNumber--;
 leftNumber++;    //左边节点数加一,右边减一.
 return;
}
template <class type>
bool LList<type>::SetPos(int pos)
{
 int Number;
 if(pos<0 || pos>leftNumber+rightNumber) //pos只能在0到总数之间.为0时指向头节点.
  return false;   //否则返回false
 current=head;    //当前指针指向头节点,以便遍历链表.
 for(int i=1;i<=pos;i++)
  current=current->next;  //从1到总数之间,那么移动.为0时不移动,
      //表示指向头节点.
 Number=leftNumber+rightNumber;  //得到总节点数.
 leftNumber=pos;
 rightNumber=Number-pos;   //根据当前节点位置,重新计算左右节点.
 return true;
}
///////////////////////////////////////////////////////////////////////////
//定义与左右节点以及总节点相关的函数.它将返回左右节点数,以及总节点数.
///////////////////////////////////////////////////////////////////////////
template <class type>
int LList<type>::LeftLength()
{
 return leftNumber;
}
template <class type>
int LList<type>::RightLength()
{
 return rightNumber;
}
template <class type>
int LList<type>::ItemNumber()
{
 return leftNumber+rightNumber;
}
///////////////////////////////////////////////////////////////////////////
//其它成员的定义,它用于得到当前指针指向的值,打印链表,以及对节点中的数据排序.
///////////////////////////////////////////////////////////////////////////
template <class type>
void LList<type>::GetValue(type &val)
{
 if(current->next)   //如果当前节点后有一节点,则返回.
  val=current->next->data;
 return;
}
template <class type>
void LList<type>::Print() const
{
 Link<type> *p=head;
 p=p->next;    //指向头节点之后的第一节点.
 while(p)
 {
  cout<<p->data<<"  ";
  p=p->next;
 }
 cout<<endl;
 return;
}
template <class type>
bool LList<type>::Paixu()
{
 Link<type> *p=head,*q;
 type temp;
 p=p->next;    //p指向第一节点.
 if(!p)
  return false;
 while(p)
 {
  q=p->next;   //q指向下一个节点.
  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;
}

下面是一个测试上面链表的函数:
int _tmain(int argc, _TCHAR* argv[])
{
///////////////////////////////////////////////////////////////////////////
//测试Clear(),Insert(),Append(),Removed()四个成员函数.
///////////////////////////////////////////////////////////////////////////
 LList<int> value;
 int  result;
 value.Clear();   //清除并重建头节点.
 value.Insert(3);
 value.Insert(2);
 value.Insert(1);  //插入三个节点.
 value.Append(4);  //添加一个节点.
 value.Print();
 value.SetPos(3);  //设置当前节点.
 value.Removed(result);  //删除一个节点并返回该节点的值.
 value.Print();
 cout<<result<<endl;  //输出节点的值,并输出删除的节点的值.
///////////////////////////////////////////////////////////////////////////
//测试SetStart(),SetEnd(),Prev(),Next()以及SetPos函数.
///////////////////////////////////////////////////////////////////////////
 value.SetStart();  //当前指针指向节点头.
 value.Insert(5);
 value.SetEnd();
 value.Insert(6);  //首尾各加上一个节点.
 value.Print();   //输出.
 value.SetPos(2);
 value.Prev();
 value.GetValue(result);
 cout<<result<<endl;
 value.SetPos(2);
 value.Next();
 value.GetValue(result);
 cout<<result<<endl;  //输出第四节点前后的节点的值.
///////////////////////////////////////////////////////////////////////////
//测试LeftLength(),RightLength(),ItemNumber()函数.
///////////////////////////////////////////////////////////////////////////
 result=value.LeftLength();
 cout<<result<<"  ";
 result=value.RightLength();
 cout<<result<<"  ";
 result=value.ItemNumber(); //当前位置在3,输出左右以及总节点数.
 cout<<result<<endl;
///////////////////////////////////////////////////////////////////////////
//测试GetValue(),Print(),Paixu()函数.
///////////////////////////////////////////////////////////////////////////
 value.Clear();
 for(int i=0;i<5;i++)
  value.Append(5-i);  //用5 4 3 2 1填充链表.
 value.Print();    //输出.
 value.Paixu();    //对链表排序.
 value.Print();    //输出.
 
for(int i=0;i<value.ItemNumber();i++)
 {
  value.SetPos(i);
  value.GetValue(result);
  cout<<result<<"  ";  //对链表进行单个枚举输出.
 }
 cout<<endl;
 return 0;
}
程序虽然长,但是都包含了非常详细的注释,所以应该不难理解.理解这个程序的最重要的一点是认清哪个成员函数需要改变哪些成员变量,由其是listNumber以及rightNumber,因为它们的改变会导致另外的成员变量或函数执行的改变.

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