节点类 #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) {} Node(const Type &item, Node<Type> *p) : data(item), link(p) {} };   #endif 【说明】因为数据结构里用到这个结构的地方太多了，如果用原书那种声明友元的做法，那声明不知道要比这个类的本身长多少。不如开放成员，事实上，这种结构只是C中的struct，除了为了方便初始化一下，不需要任何的方法，原书那是画蛇添足。下面可以看到，链表的public部分没有返回Node或者Node*的函数，所以，别的类不可能用这个开放的接口对链表中的节点操作。 【重要修改】原书的缺省构造函数是这样的Node() : data(NULL), link(NULL) {}  。我原来也是照着写的，结果当我做扩充时发现这样是不对的。当Type为结构而不是简单类型（int、……），不能简单赋NULL值。这样做使得定义的模板只能用于很少的简单类型。显然，这里应该调用Type的缺省构造函数。 这也要求，用在这里的类一定要有缺省构造函数。在下面可以看到构造链表时，使用了这个缺省构造函数。当然，这里是约定带表头节点的链表，不带头节点的情况请大家自己思考。 【闲话】请不要对int *p = new int(1);这种语法有什么怀疑，实际上int也可以看成一种class。 单链表类 #ifndef List_H #define List_H   #ifndef TURE #define TURE 1 #endif #ifndef FALSE #define FALSE 0 #endif typedef int BOOL;   #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;        }          BOOL Put(Type const &value)//改变当前节点的data，使其为value        {               if (current != NULL)               {                      current->data = value;                      return TURE;               }               else return FALSE;        }               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, 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到表尾        {               if (last->link != NULL)               {                      for ( ;current->link != NULL; current = current->link)                      prior = current;                      last = current;               }               current = last;               }            BOOL Find(const Type &value)//移动current到数据等于value的节点        {               if (IsEmpty()) return FALSE;               for (current = first->link, prior = 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;               l.First();               return strm; }   protected:  /*主要是为了高效的入队算法所添加的。因为Insert()，Remove()，RemoveAfter()有可能改变last但没有改变last所以这个算法如果在public里除非不使用这些，否则不正确。但是last除了在队列中非常有用外，其他的时候很少用到，没有必要为了这个用途而降低Insert()，Remove()的效率所以把这部分放到protected，实际上主要是为了给队列继承*/       void LastInsert(const Type &value)        {               Node<Type> *p = new Node<Type>(value, last->link);               last->link = p;               last = p;        }          void Initialize()//当表为空表时使指针复位        {               current = last = first;               prior = NULL;        }          //这部分函数返回类型为Node<Type>指针,是扩展List功能的接口        Node<Type> *pGet()        {               return current;        }          Node<Type> *pNext()        {               prior = current;               current = current->link;               return current;

评论