<b>数据构造学习(C++)之单链表</b>[VC/C++编程]

节点类

【阐明】因为数据构造里用到这个构造的地方太多了,假如用《数据构造》那种声明友元的做法,那声明不知道要比这个类的本身长多少.不如开放成员,事实上,这种构造只是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 ¤t->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 ¤t->link->data;
　　　else return NULL;
　　}
　　Type *Next()//移动current到下一个节点,返回节点数据域的地址
　　{
　　　if (current != NULL && current->link != NULL)
　　　{
　　　　prior = current;
　　　　current = current->link;
　　　　return ¤t->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;
　}
　Node<Type> *pGetNext()
　{
　　return current->link;
　}
　Node<Type> *pGetFirst()
　{
　　return first;
　}
　Node<Type> *pGetLast()
　{
　　return last;
　}
　Node<Type> *pGetPrior()
　{
　　return prior;
　}
　void PutLast(Node<Type> *p)
　{
　　last = p;
　}
//这部份插入删除函数不成立或删除节点,是原位操作的接口
　void Insert(Node<Type> *p)
　{
　　p->link = current->link;
　　current->link = p;
　}
　void InsertBefore(Node<Type> *p)
　{
　　p->link = current;
　　prior->link = p;
　　prior = 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()使指针last精确
};
#endif

【阐明】我将原书的游标类Iterator的功效放在了链表类中,屏蔽掉了返回值为Node以及Node*范例的接口,这样的链表简单、实用,扩大性能也很好.