?個人主頁：?熬夜學(xué)編程的小林

💗系列專欄：?【C語言詳解】?【數(shù)據(jù)結(jié)構(gòu)詳解】【C++詳解】

目錄

1、基本結(jié)構(gòu)

2、基本函數(shù)實(shí)現(xiàn)

2.1、默認(rèn)構(gòu)造函數(shù)

2.2、尾插數(shù)據(jù)

3、迭代器的封裝

3.1、迭代器的基本結(jié)構(gòu)

3.2、迭代器重載函數(shù)的實(shí)現(xiàn)

4、迭代器與list進(jìn)行關(guān)聯(lián)

4.1、使用迭代器打印鏈表數(shù)據(jù)

4.2、其他相關(guān)函數(shù)

總結(jié)

---

1、基本結(jié)構(gòu)

namespace lin
{template<class T>struct ListNode//雙向循環(huán)鏈表的基本結(jié)構(gòu){ListNode<T>* _prev;//前驅(qū)指針ListNode<T>* _next;//后繼指針T _data;//數(shù)據(jù)值//不傳值時使用T()默認(rèn)值構(gòu)造，傳值則傳值構(gòu)造ListNode(const T& val = T())//默認(rèn)構(gòu)造 + 傳值構(gòu)造:_prev(nullptr),_next(nullptr),_data(val){}};template<class T>struct ListIterator//迭代器封裝類，成員都會被調(diào)用，因此使用struct{typedef ListNode<T> Node;Node* _node;//結(jié)點(diǎn)指針}template<class T>class list//鏈表模板類，成員變量定義及函數(shù)封裝{typedef ListNode<T> Node;//將鏈表結(jié)構(gòu)取別名，簡化代碼public:typedef ListIterator<T> iterator;//迭代器重命名private:Node* _head;//鏈表頭指針size_t size;//鏈表長度}
}

上述代碼實(shí)現(xiàn)了雙向循環(huán)鏈表的基本結(jié)構(gòu)，其中包含了四個部分：

1.namespace lin，命令空間 lin 是用于封裝代碼，避免同名類型和函數(shù)沖突。

2.在命名空間中，定義了模板類ListNode(雙向循環(huán)鏈表基本結(jié)構(gòu))，該類包含三個成員變量：

• _prev : 存儲指向前一個結(jié)點(diǎn)的指針
• _next : 存儲指向后一個結(jié)點(diǎn)的指針
• _data : 存儲數(shù)據(jù)

ListNode類還實(shí)現(xiàn)一個有缺省值(T())的構(gòu)造函數(shù)，如果構(gòu)造函數(shù)沒有提供參數(shù)，則使用T類型的默認(rèn)構(gòu)造來初始化_data，如果傳值則使用該值來初始化_data，該構(gòu)造函數(shù)也會將_prev和_next指針指向nullptr。

3.模板類ListIterator(迭代器封裝)，該類包含一個成員變量，即鏈表的結(jié)點(diǎn)指針：

為什么鏈表需要封裝一個迭代器的類呢？？？

1. 鏈表的物理空間是不連續(xù)的，是通過結(jié)點(diǎn)的指針依次鏈接。
2. 不能像string和vector一樣直接解引用去訪問其數(shù)據(jù)。
3. 結(jié)點(diǎn)的指針解引用還是結(jié)點(diǎn)，結(jié)點(diǎn)指針++還是結(jié)點(diǎn)指針。
4. 在string和vector的物理空間是連續(xù)的，所以這倆不需要實(shí)現(xiàn)迭代器類，可以直接使用。

4.模板類list(鏈表的基本成員變量及其函數(shù)接口)，該類包含兩個成員變量：

• _head : 鏈表的頭結(jié)點(diǎn)指針
• _size : 鏈表的長度

2、基本函數(shù)實(shí)現(xiàn)

注意：我們實(shí)現(xiàn)的是帶頭雙向循環(huán)鏈表。

2.1、默認(rèn)構(gòu)造函數(shù)

list()

默認(rèn)構(gòu)造的函數(shù)功能是構(gòu)造一個沒有元素的空容器。

思路：我們實(shí)現(xiàn)的是帶頭雙向循環(huán)鏈表，因此默認(rèn)構(gòu)造時我們需要創(chuàng)建(new)一個頭結(jié)點(diǎn)，并將鏈表長度初始化為0。

//構(gòu)造頭結(jié)點(diǎn)函數(shù)
void empty_init()
{_head = new Node;//創(chuàng)建新結(jié)點(diǎn)_head->_next = _head;_head->_prev = _head;_size = 0;
}//默認(rèn)構(gòu)造 構(gòu)造一個頭結(jié)點(diǎn)
list()
{empty_init();
}

為了后序使用方便，我們將構(gòu)造頭結(jié)點(diǎn)封裝成了一個函數(shù)。?

?2.2、尾插數(shù)據(jù)

為什么在第二個函數(shù)就寫尾插呢？因為后面的函數(shù)會大量用到尾插函數(shù)。

push_back()

思想：

• 先找到尾結(jié)點(diǎn)，即頭結(jié)點(diǎn)的前一個結(jié)點(diǎn)。
• 然后將尾結(jié)點(diǎn)，新結(jié)點(diǎn)以及頭結(jié)點(diǎn)進(jìn)行鏈接。

void push_back(const T& val)
{//tail _head->_prevNode* tail = _head->_prev;Node* newnode = new Node(val);//創(chuàng)建一個值為val的新結(jié)點(diǎn)//tail newnode _head //鏈接關(guān)系的順序tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;_size++;//尾插之后長度要++
}

我們尾插完數(shù)據(jù)之后，想要遍歷整個鏈表怎么遍歷呢？？？

我們在使用鏈表的時候是通過迭代器進(jìn)行遍歷，如下代碼：

void test_list1()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;cout << lt.size() << endl;
}

此時我們就需要對鏈表的迭代器進(jìn)行封裝！！！

3、迭代器的封裝

此時的迭代器是一個結(jié)點(diǎn)指針(Node*)。

3.1、迭代器的基本結(jié)構(gòu)

template<class T>
struct ListIterator
{typedef ListNode<T> Node;//類型起別名Node* _node;//成員變量ListIterator(Node* node)//構(gòu)造函數(shù):_node(node){}
};

但是我們使用迭代器時，是在list內(nèi)部進(jìn)行使用的，且類型名稱為iterator，因此需要在list內(nèi)部重命名迭代器類型(公有的，因為我們需要在類外訪問)。

template<class T>
class list 
{
public:  typedef ListIterator<T> iterator;//迭代器重命名
};

迭代器實(shí)質(zhì)是一個結(jié)點(diǎn)指針，因此類的成員是_node(結(jié)點(diǎn)指針)，此處我們使用一個結(jié)點(diǎn)的指針對其初始化。

typedef ListNode<T> Node;//類型起別名Node* _node;//成員變量ListIterator(Node* node)//構(gòu)造函數(shù):_node(node){}

3.2、迭代器重載函數(shù)的實(shí)現(xiàn)

前置++

先++，再使用，返回的是++后的結(jié)點(diǎn)，用引用返回。

//前置++
typedef ListIterator<T> Self//對返回迭代器類型重命名，因為原類型較長
Self& operator++()
{_node = _node->_next;return *this;
}

后置++

先使用，再++，返回的是++前的結(jié)點(diǎn)，傳值返回。

typedef ListIterator<T> Self
Self operator++(int)
{Self tmp(*this);//構(gòu)造一個臨時變量存儲之前的結(jié)點(diǎn)_node = _node->_next;return tmp;//返回臨時對象
}

注意：前置和后置的區(qū)別是，后置需要在形參中傳一個占位符，一般使用int類型。

?前置--

先--，再使用，返回的是--后的結(jié)點(diǎn)，用引用返回。

Self& operator--()
{_node = _node->_prev;return *this;
}

?后置--

先使用，再++，返回的是++前的結(jié)點(diǎn)，傳值返回。

Self operator--(int)
{Self tmp(*this);_node = _node->_prev;return tmp;
}

為什么前置++返回的是類對象引用，而后置++返回的是結(jié)點(diǎn)類型呢？？？

因為在前置++中，我們返回的是類本身，而后置++，我們返回的是一個局部的類對象，局部的類對象出了函數(shù)會自動銷毀。?

operator*

?對該迭代器位置的數(shù)據(jù)進(jìn)行解引用，類似與指針解引用。

T& operator*()//遍歷及修改
{return _node->_data;//訪問鏈表的data數(shù)據(jù)
}

?operator!=

重載兩個迭代器不相等，指針不相等則返回true，相等則返回false。

bool operator!=(const Self& lt)
{return _node != lt._node;//兩個迭代器不相等即指針不相等
}	

operator==

bool operator==(const Self& lt)
{return _node == lt._node;
}

?注意：比較迭代器是否相等比較的是的地址。

4、迭代器與list進(jìn)行關(guān)聯(lián)

4.1、使用迭代器打印鏈表數(shù)據(jù)

void test_list1()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;cout << lt.size() << endl;
}

根據(jù)打印的測試函數(shù)我們可以知道，我們需要獲取鏈表的第一個結(jié)點(diǎn)的迭代器（即第一個結(jié)點(diǎn)的地址），但是這個地址只有在list類中有，因此我們需要在list類中封裝一個獲取第一個結(jié)點(diǎn)的迭代器(begin)，獲取end()也是同理。

begin()?

第一個結(jié)點(diǎn)的迭代器，即頭結(jié)點(diǎn)的下一個位置(_head->next)。

iterator begin() 
{return iterator(_head->_next);//調(diào)用迭代器類的構(gòu)造函數(shù)//return _head->next;//單參數(shù)的隱式類型轉(zhuǎn)換
}

?end()

最后一個結(jié)點(diǎn)的下一個位置，即_head位置。

iterator end()
{return iterator(_head);//return _head;
}

封裝完迭代器之后我們就可以進(jìn)行打印了。?

list類代碼：

template<class T>
class list
{typedef ListNode<T> Node;
public:typedef ListIterator<T> iterator;iterator begin() //打印鏈表時，只能訪問數(shù)據(jù)，不能修改內(nèi)容及指向的內(nèi)容{return iterator(_head->_next);}iterator end(){return iterator(_head);}
private:Node* _head;//鏈表頭指針size_t _size;//鏈表大小
};

?測試結(jié)果：

4.2、其他相關(guān)函數(shù)

insert()

在pos位置之前插入val。

思路：

• 先獲取當(dāng)前結(jié)點(diǎn)的地址
• 然后通過前驅(qū)指針找到前面一個結(jié)點(diǎn)的地址
• 再創(chuàng)建一個新的結(jié)點(diǎn)
• 最后將前驅(qū)結(jié)點(diǎn)，新結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)構(gòu)成鏈接關(guān)系

void insert(iterator pos, const T& val)//在pos位置前面插入val
{Node* cur = pos._node;//當(dāng)前結(jié)點(diǎn)指針Node* prev = cur->_prev;Node* newnode = new Node(val);//prev newnode curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;
}

erase()

刪除pos位置的值，并返回刪除前的下一個結(jié)點(diǎn)的地址。

思路：

• 先獲取當(dāng)前結(jié)點(diǎn)的地址
• 然后通過前驅(qū)指針找到前一個結(jié)點(diǎn)地址，通過后繼指針找到后一個結(jié)點(diǎn)的地址
• 將prev 前驅(qū)指針與后繼指針建立鏈接關(guān)系
• 釋放當(dāng)前結(jié)點(diǎn)
• 返回next結(jié)點(diǎn)

iterator erase(iterator pos)//刪除pos位置值，迭代器失效問題
{Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;//prev nextprev->_next = next;next->_prev = prev;delete cur;_size--;return iterator(next);//返回迭代器中結(jié)點(diǎn)指針
}

頭插尾插頭刪尾刪

復(fù)用insert()函數(shù)和erase()函數(shù)實(shí)現(xiàn)。

void push_back(const T& val)
{insert(end(), val);//end()之前插入
}
void push_front(const T& val)
{insert(begin(),val);//begin()之前插入
}
void pop_back()
{erase(--end());//刪除end前面一個結(jié)點(diǎn)
}
void pop_front()
{erase(begin());//刪除begin位置結(jié)點(diǎn)
}

總結(jié)

本篇博客就結(jié)束啦，謝謝大家的觀看，如果公主少年們有好的建議可以留言喔，謝謝大家啦！