C++双向循环链表类模版实例代码分析

本文小编为大家详细介绍“c++双向循环链表类模版实例代码分析”，内容详细，步骤清晰，细节处理妥当，希望这篇“C++双向循环链表类模版实例代码分析”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。

1.插入某个节点流程

如下图所示:

对应代码如下所示:

       bool insert(int i, const T& value)    {        if (!((i>=0) && (i<=m_length))) {            ThrowException("Invalid parameter i to get value ...");            return false;        }        node* pre = getNode(i-1);        Node* node = new Node(value);    // new一个新节点        node->next = pre->next;          // 将node新节点的next链接到下个节点        node->prev = pre;                // 将node新节点的prev链接到pre上个节点        pre->next->prev = node;          // 将下个节点的prev链接到node新节点        pre->next = node;                // 将上个节点的next链接到node新节点        m_length +=1;        return true;    }

2.构造函数修改

在构造函数中,需要将头节点的next和prev都指向自己,从而实现一个闭环状态,代码如下所示:

LinkedList() { m_header.next = &m_header; m_header.prev = &m_header;    m_length = 0; }

3.重新实现append和prepend函数

因为是个双向循环链表,所以我们很轻松的就能获取到表头节点和表尾节点,代码如下所示:

    void append(const T &value)    {         Node* node = new Node(value);    // new一个新节点         node->next = &m_header;          // 新节点的下个节点为头节点         node->prev = m_header.prev;      // 新节点的上个节点为末尾节点         node->prev->next = node;         // 新节点的上个节点的下个节点为新节点         m_header.prev = node;            // 开头节点的上个节点为i         m_length +=1;    }    void prepend(const T &value)    {        Node* node = new Node(value);    // new一个新节点        node->next = m_header.next;      // 新节点的下个节点为头节点的next        node->prev = &m_header;          // 新节点的上个节点为头节点        m_header.next = node;            // 设置头结点下个节点为node        node->next->prev = node;         // 设置之前的节点前驱节点        m_length +=1;    }

4.修改迭代器类

由于现在是循环双链表,所以每个节点的next都是有值的,所以我们需要判断m_current当前指标是否等于头节点,如果等于则表示已经到链表末尾了.所以代码如下所示:

bool hasNext()  {  return  (m_current && m_current != list->constHeader()); }

由于现在有prev成员,所以需要增加向前遍历函数:

void toEnd() {  m_current = list->constHeader()->prev; }bool hasPrev()  { return  (m_current && m_current != list->constHeader()); }T& previous() { Node *ret = m_current;  m_current = m_current->prev; return ret->value; }

5.LinkedList.h代码如下

#ifndef LinkedLIST_H#define LinkedLIST_H#include "throw.h"// throw.h里面定义了一个ThrowException抛异常的宏,如下所示://#include <iOStream>//using namespace std;//#define ThrowException(errMsg)  {cout<<__FILE__<<" LINE"<<__LINE__<<": "<<errMsg<<endl; (throw errMsg);}template <typename T>struct LinkedNode{    inline LinkedNode(){ }    inline LinkedNode(const T &arg): value(arg) { }    LinkedNode *prev;         // 前驱结点    LinkedNode *next;         // 后驱节点    T value;                  // 节点值};template <class T>class LinkedList{protected:    typedef LinkedNode<T> Node;    mutable Node m_header;          // 头节点    int m_length;public:    LinkedList() { m_header.next = &m_header; m_header.prev = &m_header;    m_length = 0; }    ~LinkedList() { clear(); }    int length()  {return m_length;}    Node* begin() {return m_header.next;}    inline Node* constHeader() const  { return &m_header; }    static bool rangeValid(int i,int len)  {return ((i>=0) && (i<len));}    inline bool isEmpty() const { return m_length == 0; }    void append(const T &value)    {         Node* node = new Node(value);    // new一个新节点         node->next = &m_header;          // 新节点的下个节点为头节点         node->prev = m_header.prev;      // 新节点的上个节点为末尾节点         node->prev->next = node;         // 新节点的上个节点的下个节点为新节点         m_header.prev = node;            // 开头节点的上个节点为i         m_length +=1;    }    void prepend(const T &value)    {        Node* node = new Node(value);    // new一个新节点        node->next = m_header.next;      // 新节点的下个节点为头节点的next        node->prev = &m_header;          // 新节点的上个节点为头节点        m_header.next = node;            // 设置头结点下个节点为node        node->next->prev = node;         // 设置之前的节点前驱节点        m_length +=1;    }        Node* getNode(int i)    {        Node* ret = &m_header;        while((i--)>-1) {       // 由于有头节点所以,i为0时,其实ret = m_header->n            ret = ret->next;        }        return ret;    }        bool insert(int i, const T& value)    {        if (!((i>=0) && (i<=m_length))) {            ThrowException("Invalid parameter i to get value ...");            return false;        }        Node* pre = getNode(i-1);        Node* node = new Node(value);    // new一个新节点        node->next = pre->next;          // 将node新节点的next链接到下个节点        node->prev = pre;                // 将node新节点的prev链接到pre上个节点        pre->next->prev = node;          // 将下个节点的prev链接到node新节点        pre->next = node;                // 将上个节点的next链接到node新节点        m_length +=1;        return true;    }        bool remove(int i)    {        if (!rangeValid(i, m_length)) {            ThrowException("Invalid parameter i to get value ...");            return false;        }        Node* pre = getNode(i-1);        Node* current = pre->next; // 获取要删除的节点        pre->next = current->next;       // 将上个节点的next链接到前一个的next中        current->next->prev = pre;       // 将下个节点的prev链接到pre节点        delete current;                  // delete空闲的节点        m_length -=1;        return true;    }        T get(int i)    {        T ret;        if (!rangeValid(i, m_length)) {            ThrowException("Invalid parameter i to get value ...");        } else {            ret = getNode(i)->value;        }        return ret;    }        bool set(int i, const T& value)    {        if (!rangeValid(i, m_length)) {            ThrowException("Invalid parameter i to get value ...");            return false;        }        getNode(i)->value = value;        return true;    }    void clear()    {        while(m_length > 0) {            remove(0);        }    }    LinkedList<T>& operator << (const T& value)    {        append(value);        return *this;    }        int indexOf(const T &value, int from =0)    {        int ret = 0;        Node* node = m_header.next;        while(node) {           if (ret >= from && node->value == value) {               return ret;           }           node = node->next;           ret+=1;        }        return -1;    }};template <class T>class LinkedListIterator{    typedef LinkedNode<T> Node;    LinkedList<T> *list;    Node *m_current;     // 当前指标public:    explicit LinkedListIterator(LinkedList<T> &l):list(&l) { m_current = l.begin(); }    void toBegin() { m_current = list->begin(); }    void toEnd() {  m_current = list->constHeader()->prev; }    bool hasHeader()  { return (m_current && m_current == list->constHeader()); }    bool hasNext()  {  return  (m_current && m_current != list->constHeader()); }    T& next() { Node *ret = m_current;  m_current = m_current->next; return ret->value; }    bool hasPrev()  { return  (m_current && m_current != list->constHeader()); }    T& previous() { Node *ret = m_current;  m_current = m_current->prev; return ret->value; }    T& value()    {        if (m_current == nullptr) {            ThrowException(" Current value is empty ...");        }        return m_current->value;    }    T& move(int i)  {        if (!list->rangeValid(i, list->length())) {            ThrowException("Invalid parameter i to get value ...");        }        m_current = list->getNode(i);        return value();    }};#endif // LinkedLIST_H

6.测试运行

测试代码如下所示:

    LinkedList<int> list;    for(int i = 0; i< 5; i++)      list.append(i);    LinkedListIterator<int> it(list);    cout<<"list.length:"<<list.length()<<endl;    // 向后遍历    it.toBegin();    while (it.hasNext())        cout<<"next:"<<it.next()<<endl;    cout<<endl;    // 向前遍历    it.toEnd();                 // 将指标移动到尾结点    while (it.hasPrev())        cout<<"previous:"<<it.previous()<<endl;

运行打印:

while循环打印30次,代码如下所示:

    it.toBegin();    int i = 30;    while(i--) {        if (it.hasHeader()) it.next();      // 如果到头结点,需要舍弃掉        cout<<"i:"<<i<<" value:"<<it.next()<<endl;    }

读到这里，这篇“C++双向循环链表类模版实例代码分析”文章已经介绍完毕，想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会，如果想了解更多相关内容的文章，欢迎关注编程网其他教程频道。