欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++?雙向循環(huán)鏈表類模版實例詳解

 更新時間:2022年02月25日 16:49:56   作者:諾謙  
這篇文章主要為大家詳細介紹了C++?雙向循環(huán)鏈表類模版實例,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助

在上章C++圖解單向鏈表類模板和iterator迭代器類模版詳解

我們學習了單鏈表,所以本章來學習雙向循環(huán)鏈表

我們在上個文章代碼上進行修改, 由于雙向循環(huán)鏈表在我們之前學的單鏈表上相對于較為復雜,所以需要注意的細節(jié)如下所示.

1.插入某個節(jié)點流程

如下圖所示:

對應代碼如下所示:

   /*插入一個新的節(jié)點*/
    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一個新節(jié)點
        node->next = pre->next;          // 將node新節(jié)點的next鏈接到下個節(jié)點
        node->prev = pre;                // 將node新節(jié)點的prev鏈接到pre上個節(jié)點
        pre->next->prev = node;          // 將下個節(jié)點的prev鏈接到node新節(jié)點
        pre->next = node;                // 將上個節(jié)點的next鏈接到node新節(jié)點
        m_length +=1;
        return true;
    }

2.構(gòu)造函數(shù)修改

在構(gòu)造函數(shù)中,需要將頭節(jié)點的next和prev都指向自己,從而實現(xiàn)一個閉環(huán)狀態(tài),代碼如下所示:

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

3.重新實現(xiàn)append和prepend函數(shù)

因為是個雙向循環(huán)鏈表,所以我們很輕松的就能獲取到表頭節(jié)點和表尾節(jié)點,代碼如下所示:

    void append(const T &value)
    {
         Node* node = new Node(value);    // new一個新節(jié)點
         node->next = &m_header;          // 新節(jié)點的下個節(jié)點為頭節(jié)點
         node->prev = m_header.prev;      // 新節(jié)點的上個節(jié)點為末尾節(jié)點
         node->prev->next = node;         // 新節(jié)點的上個節(jié)點的下個節(jié)點為新節(jié)點
         m_header.prev = node;            // 開頭節(jié)點的上個節(jié)點為i
         m_length +=1;
    }
    void prepend(const T &value)
    {
        Node* node = new Node(value);    // new一個新節(jié)點
        node->next = m_header.next;      // 新節(jié)點的下個節(jié)點為頭節(jié)點的next
        node->prev = &m_header;          // 新節(jié)點的上個節(jié)點為頭節(jié)點
        m_header.next = node;            // 設(shè)置頭結(jié)點下個節(jié)點為node
        node->next->prev = node;         // 設(shè)置之前的節(jié)點前驅(qū)節(jié)點
        m_length +=1;
    }

4.修改迭代器類

由于現(xiàn)在是循環(huán)雙鏈表,所以每個節(jié)點的next都是有值的,所以我們需要判斷m_current當前指標是否等于頭節(jié)點,如果等于則表示已經(jīng)到鏈表末尾了.所以代碼如下所示:

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

由于現(xiàn)在有prev成員,所以需要增加向前遍歷函數(shù):

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);}
/*鏈表節(jié)點類模板*/
template <typename T>
struct LinkedNode
{
    inline LinkedNode(){ }
    inline LinkedNode(const T &arg): value(arg) { }
    LinkedNode *prev;         // 前驅(qū)結(jié)點
    LinkedNode *next;         // 后驅(qū)節(jié)點
    T value;                  // 節(jié)點值
};
/*鏈表類模板*/
template <class T>
class LinkedList
{
protected:
    typedef LinkedNode<T> Node;
    mutable Node m_header;          // 頭節(jié)點
    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一個新節(jié)點
         node->next = &m_header;          // 新節(jié)點的下個節(jié)點為頭節(jié)點
         node->prev = m_header.prev;      // 新節(jié)點的上個節(jié)點為末尾節(jié)點
         node->prev->next = node;         // 新節(jié)點的上個節(jié)點的下個節(jié)點為新節(jié)點
         m_header.prev = node;            // 開頭節(jié)點的上個節(jié)點為i
         m_length +=1;
    }
    void prepend(const T &value)
    {
        Node* node = new Node(value);    // new一個新節(jié)點
        node->next = m_header.next;      // 新節(jié)點的下個節(jié)點為頭節(jié)點的next
        node->prev = &m_header;          // 新節(jié)點的上個節(jié)點為頭節(jié)點
        m_header.next = node;            // 設(shè)置頭結(jié)點下個節(jié)點為node
        node->next->prev = node;         // 設(shè)置之前的節(jié)點前驅(qū)節(jié)點
        m_length +=1;
    }
    /*獲取i位置處的節(jié)點*/
    Node* getNode(int i)
    {
        Node* ret = &m_header;
        while((i--)>-1) {       // 由于有頭節(jié)點所以,i為0時,其實ret = m_header->n
            ret = ret->next;
        }
        return ret;
    }
    /*插入一個新的節(jié)點*/
    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一個新節(jié)點
        node->next = pre->next;          // 將node新節(jié)點的next鏈接到下個節(jié)點
        node->prev = pre;                // 將node新節(jié)點的prev鏈接到pre上個節(jié)點
        pre->next->prev = node;          // 將下個節(jié)點的prev鏈接到node新節(jié)點
        pre->next = node;                // 將上個節(jié)點的next鏈接到node新節(jié)點
        m_length +=1;
        return true;
    }
    /*刪除一個節(jié)點*/
    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;		 // 獲取要刪除的節(jié)點
        pre->next = current->next;       // 將上個節(jié)點的next鏈接到前一個的next中
        current->next->prev = pre;       // 將下個節(jié)點的prev鏈接到pre節(jié)點
        delete current;                  // delete空閑的節(jié)點
        m_length -=1;
        return true;
    }
    /*獲取節(jié)點數(shù)據(jù)*/
    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;
    }
    /*設(shè)置節(jié)點*/
    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;
    }
    /*在鏈表中向前查找value所在的索引號.默認從from索引號0(表頭)開始.如果未找到則返回-1.*/
    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();                 // 將指標移動到尾結(jié)點
    while (it.hasPrev())
        cout<<"previous:"<<it.previous()<<endl;

運行打印:

while循環(huán)打印30次,代碼如下所示:

    it.toBegin();
    int i = 30;
    while(i--) {
        if (it.hasHeader()) it.next();      // 如果到頭結(jié)點,需要舍棄掉
        cout<<"i:"<<i<<" value:"<<it.next()<<endl;
    }

總結(jié)

本篇文章就到這里了,希望能夠給你帶來幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!  

相關(guān)文章

  • C++連接mysql數(shù)據(jù)庫的兩種方法小結(jié)

    C++連接mysql數(shù)據(jù)庫的兩種方法小結(jié)

    這篇文章主要介紹了C++連接mysql數(shù)據(jù)庫的兩種方法小結(jié),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2020-04-04
  • 使用C++獲取邏輯執(zhí)行毫秒數(shù)的方法

    使用C++獲取邏輯執(zhí)行毫秒數(shù)的方法

    這篇文章主要為大家詳細介紹了如何使用C++獲取邏輯執(zhí)行毫秒數(shù)的方法,文中借助c++11提供的steady_clock,實現(xiàn)了精確獲取邏輯執(zhí)行時間的方法,需要的可以參考下
    2024-02-02
  • c++調(diào)用實現(xiàn)yolov5轉(zhuǎn)onnx介紹

    c++調(diào)用實現(xiàn)yolov5轉(zhuǎn)onnx介紹

    大家好,本篇文章主要講的是c++調(diào)用實現(xiàn)yolov5轉(zhuǎn)onnx介紹,感興趣的同學趕快來看一看吧,對你有幫助的話記得收藏一下,方便下次瀏覽
    2021-12-12
  • 淺談使用Rapidxml 庫遇到的問題和分析過程(分享)

    淺談使用Rapidxml 庫遇到的問題和分析過程(分享)

    下面小編就為大家?guī)硪黄獪\談使用Rapidxml 庫遇到的問題和分析過程(分享)。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-05-05
  • Qt 使用QDialog實現(xiàn)界面遮罩的示例(蒙版)

    Qt 使用QDialog實現(xiàn)界面遮罩的示例(蒙版)

    界面遮罩在很多時候都可以用到,例如彈窗,本文主要介紹了Qt 使用QDialog實現(xiàn)界面遮罩的示例,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2022-04-04
  • Qt數(shù)據(jù)庫相關(guān)應用開發(fā)總結(jié)

    Qt數(shù)據(jù)庫相關(guān)應用開發(fā)總結(jié)

    這篇文章主要為大家介紹了在Qt數(shù)據(jù)庫應用開發(fā)中的一些經(jīng)驗總結(jié),以及一些組件的使用介紹。文中的示例代碼講解詳細,需要的可以參考一下
    2022-02-02
  • C語言中隱藏結(jié)構(gòu)體的細節(jié)

    C語言中隱藏結(jié)構(gòu)體的細節(jié)

    以筆者粗淺的認識,有兩種最常用的方法,可以實現(xiàn)庫內(nèi)結(jié)構(gòu)體定義的隱藏:接口函數(shù)形參使用結(jié)構(gòu)體指針,接口函數(shù)形參使用句柄。
    2017-05-05
  • C++中String的語法及常用接口的底層實現(xiàn)詳解

    C++中String的語法及常用接口的底層實現(xiàn)詳解

    在C語言中,string是一個標準庫類(class),用于處理字符串,它提供了一種更高級、更便捷的字符串操作方式,string 類提供了一系列成員函數(shù)和重載運算符,以便于對字符串進行操作和處理,本編文章會對C++中的 string 進行詳解,希望本篇文章會對你有所幫助
    2023-06-06
  • c++實現(xiàn)簡單的線程池

    c++實現(xiàn)簡單的線程池

    這里給大家介紹了C++中對于pthread線程的一個簡單應用以及使用繼承CDoit,實現(xiàn)其中的start和end,有需要的小伙伴可以參考下
    2015-11-11
  • C語言中函數(shù)與指針的應用總結(jié)

    C語言中函數(shù)與指針的應用總結(jié)

    本篇文章是對C語言中函數(shù)與指針的應用進行了詳細的分析介紹,需要的朋友參考下
    2013-05-05

最新評論