数据结构学习(C )单链表(定义与实现)

happycock（原作）转自CSDN 

节点类

#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;

    }

    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 *p = new Node(value, current->link);

current->link = p;

    }

    BOOL InsertBefore(const Type &value)//在当前节点的前面插入一节点，不改变current，改变prior

    {

Node *p = new Node(value);

        if (prior != NULL)

        {