用C++模板描述的链表、栈、队列（声明与实现）

主要参考书是《数据结构（用面向对象方法与C++描述）》殷人昆等编著，清华大学出版社。原书看起来很费事，显而易见的把教学目的和提供实例的目的搞混了，结果是个四不象：作为教科书，条理不清晰；提供各个方法的实现，也不是很实用，相反，重复建设太多。但是，这是清华的考研参考书目，一定有许多人和我一样在研读此书。我把我重新定义的类和实现发表出来，就是希望和我一样的人，或者是打算学习数据结构而选择了这本书的人，能更好的理解和学习。当然，如果你想使用这些数据结构，又不想学STL，这些类也能帮你达成目的。

我照着原书的类名和对应的函数名，写下了如下的类的定义，部分代码采用了原书的。把成员函数的实现写在类定义里，完全是为了将就VC++6的ClassView，不然一双击一个成员函数，就蹦出来“我找不到它的实现”，而实际上，一般我们都看的是ClassView显示的类的接口，很少去看类的定义。
这是第一部分，马上我会完成树等结构。我只测试了int类型各个成员函数的正确性，并且也没做什么“极端测试”，欢迎测试。另外，欢迎反映这样的定义是否好看些，容易懂些。

#ifndef Node_H
#define Node_H

template <class Type> class Node //单链节点类
{
public:
 Type data;
 Node<Type> *link;
 Node() : data(Type()), link(NULL) {}       
 Node(const Type &item) : data(item), link(NULL) {}
};

#endif
说明：因为数据结构里用到这个结构的地方太多了，如果用原书那种声明友元的做法，那声明不知道要比这个类的本身长多少。不如开放成员，事实上，这种结构只是C中的struct，除了为了方便初始化一下，不需要任何的方法，原书那是画蛇添足。

一点重要的修改：原书的缺省构造函数是这样的Node() : data(NULL), link(NULL) {}  。我原来也是照着写的，结果当我做扩充时发现这样是不对的。当Type为结构而不是简单类型（int、……），不能简单赋NULL值。这样做使得定义的模板只能用于很少的简单类型。显然，这里应该调用Type的缺省构造函数。 这也要求，用在这里的类一定要有缺省构造函数。在下面可以看到构造链表时，使用了这个缺省构造函数。当然，这里是约定带表头节点的链表，不带头节点的情况请大家自己思考。  

下面可以看到，链表的public部分没有返回Node或者Node*的函数，所以，别的类不可能用这个开放的接口对链表中的节点操作。

#ifndef List_H
#define List_H

#include "Node.h"

template <class Type> class List //单链表定义
{
//基本上无参数的成员函数操作的都是当前节点，即current指的节点
//认为表中“第1个节点”是第0个节点，请注意，即表长为1时，最后一个节点是第0个节点
public:
 List() { first = current = last = new Node<Type>(); prior = NULL; }
 ~List() { MakeEmpty(); delete first; }
 
  void MakeEmpty() //置空表
 {  
  Node<Type> *q;
  while (first->link != NULL)
  {
   q = first->link;
   first->link = q->link;
   delete q;
  }
 Initialize()
 }
 
 BOOL IsEmpty()
 {
  if (first->link == NULL)
  {
   Initialize();
   return TURE;
  }
  else return FALSE;
 }
 
 int Length() const  //计算带表头节点的单链表长度                                  
 {
  Node<Type> *p = first->link;
  int count = 0;
  while (p != NULL)
  {
   p = p->link;
   count++;
  }
  return count;
 }

 Type *Get()//返回当前节点的数据域的地址
 {
  if (current != NULL) return &current->data;
  else return NULL;
 }

 Type *GetNext()//返回当前节点的下一个节点的数据域的地址，不改变current
 {
  if (current->link != NULL) return &current->link->data;
  else return NULL;
 }

 Type *Next()//移动current到下一个节点，返回节点数据域的地址
 {
  if (current != NULL && current->link != NULL)
  {
   prior = current;
   current = current->link;
   return &current->data;
  }
  else
  {
   return NULL;
  }
 }

  void Insert(const Type &value)//在当前节点的后面插入节点，不改变current
 {
  Node<Type> *p = new Node<Type>(value);
  p->link = current->link;
  current->link = p;
 }

 BOOL InsertBefore(const Type &value)//在当前节点的前面插入一节点，不改变current，改变prior
 {
  Node<Type> *p = new Node<Type>(value);
  if (prior != NULL)
  {
   p->link = current;
   prior->link = p;
   prior = p;
   return TURE;
  }
  else return FALSE;
 } 

 BOOL Locate(int i)//移动current到第i个节点
 {
  if (i <= -1) return FALSE;
  current = first->link;
  for (int j = 0; current != NULL && j < i; j++, current = current->link)
   prior = current;
  if (current != NULL) return TURE;
  else return FALSE;
 }

 void First()//移动current到表头
 {
  current = first;
  prior = NULL;
 }
 void End()//移动current到表尾，同时使last真正指向表尾
 {
  if (last->link != NULL)
  {
   for ( ;current->link != NULL; current = current->link)
   prior = current;
  }

  last = current;
 }

 BOOL Find(const Type &value)//移动current到数据等于value的节点
 {
  for (current = first; current != NULL && current->data != value;
   current = current->link)
    prior = current;
  if (current != NULL) return TURE;
  else return FALSE;
 }

 BOOL Remove()//删除当前节点，current指向下一个节点，如果current在表尾，执行后current = NULL
 {
  if (current != NULL && prior != NULL)
  {
   Node<Type> *p = current;
   prior->link = p->link;
   current = p->link;
   delete p;
   return TURE;
  }
  else return FALSE;
 }

 BOOL RemoveAfter()//删除当前节点的下一个节点，不改变current
 {
  if (current->link != NULL && current != NULL)
  {
   Node<Type> *p = current->link;
   current->link = p->link;
   delete p;
   return TURE;   
  }
  else return FALSE;
 }

friend ostream & operator << (ostream & strm, List<Type> &l)
{
  l.First();
  while (l.current->link != NULL) strm << *l.Next() << " " ;
  strm << endl;
  return strm;
  l.First();
}

protected:

void Initialize()//当表为空表时使指针复位
 {
  current = last = first;
  prior = NULL;
 }

 /*主要是为了高效的入队算法所添加的。因为Insert()，Remove()，RemoveAfter()有可能改变last但没有改变last所以这个算法如果在public里除非不使用这些，否则不正确。但是last除了在队列中非常有用外，其他的时候很少用到，没有必要为了这个用途而降低Insert()，Remove()的效率所以把这部分放到protected，实际上主要是为了给队列继承*/
  void LastInsert(const Type &value)
 {
  Node<Type> *p = new Node<Type>(value);
  last->link = p;
  last = p;
 } //这部分函数返回类型为Node<Type>指针,是扩展List功能的接口
 Node<Type> *pGet()
 {
  return current;
 }

 Node<Type> *pNext()
 {
  current = current->link;
  return current;
 }

 Node<Type> *pGetNext()
 {
  return current->link;
 }
 //这部分插入删除函数不建立或删除节点，是原位操作的接口
 void Insert(Node<Type> *p)
 {
  p->link = current->link;
  current->link = p;
 }

 void InsertBefore(Node<Type> *p)
 {
  p->link = current;
  prior->link = p;
  piror = p;
 } 
 
 void LastInsert(Node<Type> *p)
 {
  p->link = NULL;
  last->link = p;
  last = p;
 }

 Node<Type> *pRemove()
 { 
  if (current != NULL && prior != NULL)
  {
   Node<Type> *p = current;
   prior->link = current->link;
   current = current->link;
   return p;
  }
  else return NULL;
 }

 Node<Type> *pRemoveAfter()
 {
  if (current->link != NULL && current != NULL)
  {
   Node<Type> *p = current->link;
   current->link = current->link->link;
   return p;   
  }
  else return NULL;
 }

 

private:

 List(const List<Type> &l);

 Node<Type> *first, *current, *prior, *last;//尽量不要使用last，如果非要使用用先用End()确保正确

};

#endif

说明：我在iostream.h加了enum BOOL { FALSE, TURE};如果报告BOOL没有定义，自己加上。protected是功能扩展的接口，实际上，除了完成书上的作业，可能根本用不到这部分。将复制构造函数声明为private，是采用了林锐的方法，防止乱用。写完这个有点感受，就是为什么要加上存取限制：能在编译阶段找出错误总比运行起来莫名其妙的错误解决起来容易。

#ifndef Stack_H
#define Stack_H

#include "List.h"

template <class Type> class Stack : List<Type>//栈类定义
{
 
public:
 /*私有继承List类的方法
 List类初始化时current = first，所以栈顶指针top = current->link；
 因此,入栈操作就是在current位置后插一节点；
 出栈操作就是先返回current后面元素，然后在current位置后删一节点；
 置空栈操作同置空表操作；
 判空栈操作同判空表操作；*/

 void Push(Type value)
 {
  Insert(value);
 }

 Type Pop()
 {
  //不须执行判空操作，因为连续执行Pop时前面必定执行判空，
  //而GetNext()和RemoveAfter()没有副作用，顶多返回NULL和FALSE
  Type p = *GetNext();
  RemoveAfter();
  return p;
 }

 Type GetTop()
 {
  return *GetNext();
 }
 
 List<Type> ::MakeEmpty;

 List<Type> ::IsEmpty;
 
};

#endif

说明：可以比较原书，原书那叫重复建设，而且，也不利于理解。

#ifndef Queue_H
#define Queue_H

#include "List.h"

template <class Type> class Queue : List<Type>//队列定义
{
/* 私有继承List类的方法，初始化时current = first
因此，队列的头指针指向current->link，尾指针为last
入队时，执行LastInsert()，连带修改last，只在这里使用，这个算法就是正确的
出队时，先返回current后面的元素，然后删除current后面的节点*/
public:
 void EnQueue(const Type &value)
 {
  LastInsert(value);
 }
 
 Type DeQueue()
 { 
  //不须执行判空操作，因为连续执行DeQueue时前面必定执行判空，
  //而GetNext()和RemoveAfter()没有副作用，顶多返回NULL和FALSE
  Type p = *GetNext();
  RemoveAfter();
  IsEmpty();//出队后如果变成空队要复位last指针
  return p;
 }

 Type GetFront()
 {
  return *GetNext();
 }

 List<Type> ::MakeEmpty;

 List<Type> ::IsEmpty;
};

#endif

说明：很显然，从链表继承省掉了大量代码和构思，原书虽然想用面向对象的方法描述，但忽视了继承。做了大量重复建设，而且让人理解起来也很艰辛。

只是简单测试了int类型各个函数能否工作，欢迎多提意见。

#include <iostream.h>
#include "List.h"
#include "Stack.h"
#include "Queue.h"

void ListTest();
void StackTest();
void QueueTest();

void main()
{
 ListTest();
 StackTest();
 QueueTest();
 }

void ListTest()
{
 cout << "链表测试" << endl;
 cout << "下面构造一个链表" << endl;
 List<int> a;
 cout << "链表是空的吗?" << a.IsEmpty() << endl;
 cout << "执行后插入操作" << endl;
 for (int i = 0; i < 20; i++) a.Insert(i);
 cout << "链表当前内容:" << endl;
 cout << a;
 cout << "表长是" << a.Length() << endl;
 a.Locate(4);
 a.Remove();
 cout << "删除第4个元素后:" << endl;
 cout << a;
 a.Find(3);
 a.Remove();
 cout << "删除元素3后:" << endl;
 cout << a;
 a.Find(7);
 cout << "在元素7前插入24后:" << endl;
 a.InsertBefore(24);
 cout << a;
 cout << "在元素9后插入25后:" << endl;
 a.Find(9);
 a.Insert(25);
 cout << a;
 cout << "第7个元素是:" << endl;
 a.Locate(7);
 cout << *a.Get();
 cout << "接下来是:" << *a.GetNext() << endl;
 cout << "删掉它后:" << endl;
 a.RemoveAfter();
 cout << a;
 cout << "在表尾后面插入元素78" << endl;
 a.End();
 a.Insert(78);
 cout << a;
 cout << "置空表后表的内容为" << endl;
 a.MakeEmpty();
 cout << a;
 cout << endl;
}

void StackTest()
{
 cout << "栈测试" << endl;
 cout << "下面构造一个栈" << endl;
 Stack<int> a;
 cout << "栈现在是空的吗?" << a.IsEmpty() << endl;
 cout << "将0～19入栈" << endl;
 for (int i = 0; i < 20; i++) a.Push(i);
 cout << "栈现在是空的吗?" << a.IsEmpty() << endl;
 cout << "全部出栈" << endl;
 while (!a.IsEmpty()) cout << a.Pop() << " ";
 cout << endl;
 cout << "栈现在是空的吗?" << a.IsEmpty() << endl;
 cout << "将0～19入栈" << endl;
 for (i = 0; i < 20; i++) a.Push(i);
 cout << "栈顶元素是：" << a.GetTop() << endl;
 cout << "置空栈" << endl;
 a.MakeEmpty();
 cout << "栈现在是空的吗?" << a.IsEmpty() << endl;
 cout << endl;
}

void QueueTest()
{
 cout << "队列测试" << endl;
 cout << "从下面构造一个队列" << endl;
 Queue<int> a;
 cout << "队列现在是空的吗?" << a.IsEmpty() << endl;
 cout << "将0～19入队" << endl;
 for (int i = 0; i < 20; i++) a.EnQueue(i);
 cout << "队列现在是空的吗?" << a.IsEmpty() << endl;
 cout << "全部出队" << endl;
 while (!a.IsEmpty()) cout << a.DeQueue() << " ";
 cout << endl;
 cout << "队列现在是空的吗?" << a.IsEmpty() << endl;
 cout << "将0～19入队" << endl;
 for (i = 0; i < 20; i++) a.EnQueue(i);
 cout << "队头元素是：" << a.GetFront() << endl;
 cout << "置空队" << endl;
 a.MakeEmpty();
 cout << "队列现在是空的吗?" << a.IsEmpty() << endl;
}