数据结构学习—单链表定义与实现

节点类

　　#ifndef Node_H

　　#define Node_H

　　template class Node //单链节点类

　　{

　　public:

　　 Type data;

　　 Node *link;

　　 Node() : data(Type()), link(NULL) {}

　　 Node(const Type &item) : data(item), link(NULL) {}

　　Node(const Type &item, Node *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 List //单链表定义

　　{

　　//基本上无参数的成员函数操作的都是当前节点，即current指的节点

　　//认为表中“第1个节点”是第0个节点，请注意，即表长为1时，最后一个节点是第0个节点

　　public:

　　 List() { first = current = last = new Node; prior = NULL; }

　　 ~List() { MakeEmpty(); delete first; }

　　 void MakeEmpty() //置空表

　　 {

　　 Node *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 *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;

　　 }

　　

节点类

　　#ifndef Node_H

　　#define Node_H

　　template class Node //单链节点类

　　{

　　public:

　　 Type data;

　　 Node *link;

　　 Node() : data(Type()), link(NULL) {}

　　 Node(const Type &item) : data(item), link(NULL) {}

　　Node(const Type &item, Node *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 List //单链表定义

　　{

　　//基本上无参数的成员函数操作的都是当前节点，即current指的节点

　　//认为表中“第1个节点”是第0个节点，请注意，即表长为1时，最后一个节点是第0个节点

　　public:

　　 List() { first = current = last = new Node; prior = NULL; }

　　 ~List() { MakeEmpty(); delete first; }

　　 void MakeEmpty() //置空表

　　 {

　　 Node *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 *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;