荔灣做網(wǎng)站上海優(yōu)化公司排行榜
?個人主頁:?熬夜學(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)指針:
為什么鏈表需要封裝一個迭代器的類呢???
- 鏈表的物理空間是不連續(xù)的,是通過結(jié)點(diǎn)的指針依次鏈接。
- 不能像string和vector一樣直接解引用去訪問其數(shù)據(jù)。
- 結(jié)點(diǎn)的指針解引用還是結(jié)點(diǎn),結(jié)點(diǎn)指針++還是結(jié)點(diǎn)指針。
- 在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é)束啦,謝謝大家的觀看,如果公主少年們有好的建議可以留言喔,謝謝大家啦!