单链表()
节点类
#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();这种语法有什么怀疑实际上int也可以看成一种class
单链表类定义与实现
#ifndef List_H
#define List_H
#ifndef TURE
#define TURE
#endif
#ifndef FALSE
#define FALSE
#endif
typedef int BOOL;
#include Nodeh
template <class Type> class List //单链表定义
{
//基本上无参数的成员函数操作的都是当前节点即current指的节点
//认为表中第个节点是第个节点请注意即表长为时最后一个节点是第个节点
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 = ;
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 <= ) return FALSE;
current = first>link;
for (int j = ; 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)
{
lFirst();
while (lcurrent>link != NULL) strm << *lNext() << ;
strm << endl;
lFirst();
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)
{<
