单链表的C++实现（采用模板类）

采用模板类实现的好处是，不用拘泥于特定的数据类型。就像活字印刷术，制定好模板，就可以批量印刷，比手抄要强多少倍！

此处不具体介绍泛型编程，还是着重叙述链表的定义和相关操作。

链表结构定义

定义单链表的结构可以有4方式。如代码所示。

本文采用的是第4种结构类型

/*************************************************************************

1、复合类：在Node类中定义友元的方式，使List类可以访问结点的私有成员

*************************************************************************/

class LinkNode

{

    friend class LinkList;

private:

    int data;

    LinkNode *next;

};

class LinkList

{

public:

    //单链表具体操作

private:

    LinkNode *head;

}; 

/*************************************************************************

2、嵌套类：在List内部定义Node类，但是Node的数据成员放在public部分，使List

和Node均可以直接访问Node的成员

*************************************************************************/

class LinkList

{

public:

    //单链表具体操作

private:

    class LinkNode

    {

    public:

        int data;

        LinkNode *next;

    };

    LinkNode *head;

}; 

/*************************************************************************

3、继承：在Node类中把成员定义为protected，然后让List继承Node类，这样就可以

访问Node类的成员了。

*************************************************************************/

class LinkNode

{

protected:

    int data;

    LinkNode *next;

};

class LinkList : public LinkNode

{

public:

    //单链表具体操作

private:

    LinkNode *head;

}; 

/*************************************************************************

4、直接用struct定义Node类，因为struct的成员默认为公有数据成员，所以可直接

访问（struct也可以指定保护类型）。

*************************************************************************/

struct LinkNode

{

    int data;

    LinkNode *next;

};

class LinkList

{

public:

    //单链表具体操作

private:

    LinkNode *head;

};

单链表的模板类定义

使用模板类需要注意的一点是template<class T>必须定义在同一个文件，否则编译器会无法识别。

如果在.h中声明类函数，但是在.cpp中定义函数具体实现，会出错。所以，推荐的方式是直接在.h中定义。

/* 单链表的结点定义 */

template<class T>

struct LinkNode

{

    T data;

    LinkNode<T> *next;

    LinkNode(LinkNode<T> *ptr = NULL){next = ptr;}

    LinkNode(const T &item, LinkNode<T> *ptr = NULL)    

    //函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面

    {

        next = ptr;

        data = item;

    }

};

/* 带头结点的单链表定义 */

template<class T>

class LinkList

{

public:

    //无参数的构造函数

    LinkList(){head = new LinkNode<T>;}

    //带参数的构造函数

    LinkList(const T &item){head = new LinkNode<T>(item);}

    //拷贝构造函数

    LinkList(LinkList<T> &List);

    //析构函数

    ~LinkList(){Clear();}

    //重载函数:赋值

    LinkList<T>& operator=(LinkList<T> &List);

    //链表清空

    void Clear();

    //获取链表长度

    int Length() const;

    //获取链表头结点

    LinkNode<T>* GetHead() const;

    //设置链表头结点

    void SetHead(LinkNode<T> *p);

    //查找数据的位置，返回第一个找到的满足该数值的结点指针

    LinkNode<T>* Find(T &item);

    //定位指定的位置，返回该位置上的结点指针

    LinkNode<T>* Locate(int pos);

    //在指定位置pos插入值为item的结点，失败返回false

    bool Insert(T &item, int pos);

    //删除指定位置pos上的结点，item就是该结点的值，失败返回false

    bool Remove(int pos, T &item);

    //获取指定位置pos的结点的值，失败返回false

    bool GetData(int pos, T &item);

    //设置指定位置pos的结点的值，失败返回false

    bool SetData(int pos, T &item);

    //判断链表是否为空

    bool IsEmpty() const;

    //打印链表

    void Print() const;

    //链表排序

    void Sort();

    //链表逆置

    void Reverse();

private:

    LinkNode<T> *head;

};

定位位置

/* 返回链表中第pos个元素的地址，如果pos<0或pos超出链表最大个数返回NULL */

template<class T>

LinkNode<T>* LinkList<T>::Locate(int pos)

{

    int i = ;

    LinkNode<T> *p = head;

    if (pos < )

        return NULL;

    while (NULL != p && i < pos)

    {

        p = p->next;

        i++;

    }

    return p;

}

插入结点

单链表插入结点的处理如图

图：单链表插入操作

要在p结点后插入一个新结点node，（1）要让node的next指针指向p的next结点；（2）再让p的next指向node结点（即断开图中的黑色实线，改成红色虚线指向node）

接下来：node->next = p->next; p->next = node;

template<class T>

bool LinkList<T>::Insert(T &item, int pos)

{

    LinkNode<T> *p = Locate(pos);

    if (NULL == p)

        return false;

    LinkNode<T> *node = new LinkNode<T>(item);

    if (NULL == node)

    {

        cerr << "分配内存失败!" << endl;

        exit();

    }

    node->next = p->next;

    p->next = node;

    return true;

}

删除结点

删除结点的处理如图：

图：单链表删除

删除pos位置的结点，如果这个位置不存在结点，则返回false；

如果找到对应结点，则通过实参item输出要删除的结点的数值，然后删除结点并返回true。

template<class T>

bool LinkList<T>::Remove(int pos, T &item)

{

    LinkNode<T> *p = Locate(pos);

    if (NULL == p || NULL == p->next)

        return false;

    LinkNode<T> *del = p->next;

    p->next = del->next;

    item = del->data;

    delete del;

    return true;

}

清空链表

遍历整个链表，每次head结点的next指针指向的结点，直到next指针为空。

最后保留head结点。

template<class T>

void LinkList<T>::Clear()

{

    LinkNode<T> *p = NULL;

    //遍历链表，每次都删除头结点的next结点，最后保留头结点

    while (NULL != head->next)

    {

        p = head->next;

        head->next = p->next;   //每次都删除头结点的next结点

        delete p;

    }

}

求链表长度和打印链表

着两个功能的实现非常相近，都是遍历链表结点，不赘述。

template<class T>

void LinkList<T>::Print() const

{

    int count = ;

    LinkNode<T> *p = head;

    while (NULL != p->next)

    {

        p = p->next;

        std::cout << p->data << " ";

        if (++count %  == )  //每隔十个元素，换行打印

            cout << std::endl;

    }

}

template<class T>

int LinkList<T>::Length() const

{

    int count = ;

    LinkNode<T> *p = head->next;

    while (NULL != p)

    {

        p = p->next;

        ++count;

    }

    return count;

}

单链表倒置

单链表的倒置处理如图：

图：单链表倒置

（1）初始状态：prev = head->next; curr = prev->next;

（2）让链表的第一个结点的next指针指向空

（3）开始进入循环处理，让next指向curr结点的下一个结点；再让curr结点的next指针指向prev。即：next = curr->next; curr->next = prev;

（4）让prev、curr结点都继续向后移位。即：prev = curr; curr = next;

（5）重复(3)、（4）动作，直到curr指向空。这时循环结束，让haed指针指向prev，此时的prev是倒置后的第一个结点。即：head->next = prev;

template<class T>

void LinkList<T>::Reverse()

{

    LinkNode<T> *pre = head->next;

    LinkNode<T> *curr = pre->next;

    LinkNode<T> *next = NULL;

    head->next->next = NULL;

    while (curr)

    {

        next = curr->next;

        curr->next = pre;

        pre = curr;

        curr = next;

    }

    head->next = pre;

}

巴特西

单链表的C++实现（采用模板类）

最新文章

热门文章