中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置: 首頁 > news >正文

荔灣做網(wǎng)站上海優(yōu)化公司排行榜

荔灣做網(wǎng)站,上海優(yōu)化公司排行榜,網(wǎng)站建設(shè)要寫代碼嗎,石家莊seo網(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、迭…

?個人主頁:?熬夜學(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é)束啦,謝謝大家的觀看,如果公主少年們有好的建議可以留言喔,謝謝大家啦!

http://www.risenshineclean.com/news/52575.html

相關(guān)文章:

  • wordpress pdf 免費(fèi)濰坊seo按天收費(fèi)
  • flash做安卓游戲下載網(wǎng)站百度官方首頁
  • 《水利建設(shè)與管理》雜志社網(wǎng)站上海高端網(wǎng)站定制
  • Linux下使用wordpress公司seo排名優(yōu)化
  • 提供專業(yè)網(wǎng)站建設(shè)平臺收錄是什么意思
  • 心得體會萬能模板免費(fèi)網(wǎng)站seo
  • 有些網(wǎng)站下方只有版權(quán)沒有ICP簡述seo和sem的區(qū)別與聯(lián)系
  • 北京網(wǎng)站推廣怎么做不屬于網(wǎng)絡(luò)推廣方法
  • 公司網(wǎng)站建設(shè)需要多少錢googleplay官方下載
  • 買2g 空間做下載網(wǎng)站全網(wǎng)搜索關(guān)鍵詞查詢
  • 邯鄲網(wǎng)站設(shè)計哪家好好省推廣100種方法
  • h5可以用什么網(wǎng)站做app推廣渠道商
  • 幫企業(yè)建網(wǎng)站步驟seo公司杭州
  • 網(wǎng)站設(shè)計美工多少搜索引擎優(yōu)化大致包含哪些內(nèi)容或環(huán)節(jié)
  • xp怎么做網(wǎng)站服務(wù)器太原做網(wǎng)站的
  • wordpress播放本地mp3seo關(guān)鍵詞排名注冊價格
  • 全市網(wǎng)站建設(shè)情況摸底調(diào)查百度網(wǎng)站關(guān)鍵詞排名查詢
  • 網(wǎng)站設(shè)計制作費(fèi)用多少怎么做互聯(lián)網(wǎng)營銷推廣
  • 南陽東莞網(wǎng)站建設(shè)公司優(yōu)化排名推廣關(guān)鍵詞
  • 網(wǎng)站可以微信支付是怎么做的域名停靠網(wǎng)頁推廣大全
  • 網(wǎng)站定制化開發(fā)介紹新網(wǎng)
  • 哈爾濱網(wǎng)站建設(shè)2017站長統(tǒng)計 網(wǎng)站統(tǒng)計
  • 西安做網(wǎng)站朋朋抖音關(guān)鍵詞推廣
  • 商城網(wǎng)站建設(shè)系統(tǒng)企業(yè)網(wǎng)站建設(shè)推廣
  • 免費(fèi)網(wǎng)站推廣軟文發(fā)布中國國家數(shù)據(jù)統(tǒng)計網(wǎng)
  • 網(wǎng)站備案密碼忘做seo需要哪些知識
  • 貴州網(wǎng)絡(luò)推廣公司百色seo快速排名
  • 阿里巴巴吧做網(wǎng)站關(guān)鍵詞排名優(yōu)化網(wǎng)站
  • wordpress foxpay企業(yè)站seo報價
  • 虛擬主機(jī)能干什么優(yōu)化網(wǎng)站打開速度