LinkList
文章目錄
- 1 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
- 1.1 鏈?zhǔn)酱鎯?chǔ)的定義
- 1.2 鏈?zhǔn)酱鎯?chǔ)邏輯結(jié)構(gòu)
- 1.3 專業(yè)術(shù)語的統(tǒng)一
- 1.4 鏈表中的基本概念
- 1.5 單鏈表中的結(jié)點(diǎn)定義
- 1.6 單鏈表的內(nèi)部結(jié)構(gòu)
- 1.7 在目標(biāo)位置處插入數(shù)據(jù)元素
- 1.8 在目標(biāo)位置處刪除數(shù)據(jù)元素
- 2 LinkList設(shè)計(jì)要點(diǎn)
- 3 繼承關(guān)系圖和接口實(shí)現(xiàn)
- 4 代碼實(shí)現(xiàn)
- 5 頭結(jié)點(diǎn)存在的隱患
- 6 順序表和單鏈表分析
- 6.1 時(shí)間復(fù)雜度對(duì)比分析
- 6.2 效率深度分析
- 7 單鏈表的遍歷與優(yōu)化
- 7.1 當(dāng)前遍歷的問題
- 7.2 優(yōu)化的思路
- 7.3 代碼實(shí)現(xiàn)
1 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
順序存儲(chǔ)結(jié)構(gòu)的最大問題就是插入和刪除時(shí)需要移動(dòng)大量的元素，這個(gè)時(shí)候就需要鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表出場(chǎng)了。
1.1 鏈?zhǔn)酱鎯?chǔ)的定義
為了表示每個(gè)數(shù)據(jù)元素與其直接后繼元素之間的邏輯關(guān)系，數(shù)據(jù)元素除了存儲(chǔ)本身的信息外，還需要存儲(chǔ)直接后繼的信息。
1.2 鏈?zhǔn)酱鎯?chǔ)邏輯結(jié)構(gòu)
基于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表中，每個(gè)結(jié)點(diǎn)都包含數(shù)據(jù)域和指針域。
- 數(shù)據(jù)域：存儲(chǔ)數(shù)據(jù)元素本身。
- 指針域：存儲(chǔ)相鄰結(jié)點(diǎn)的地址。
1.3 專業(yè)術(shù)語的統(tǒng)一
順序表
- 基于順序存儲(chǔ)結(jié)構(gòu)的線性表
鏈表
- 基于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表
- 單鏈表：每個(gè)結(jié)點(diǎn)只包含直接后繼的地址信息
- 循環(huán)鏈表：單鏈表中的最后一個(gè)結(jié)點(diǎn)的直接后繼為第一個(gè)結(jié)點(diǎn)
- 雙向鏈表：單鏈表中的結(jié)點(diǎn)包含直接前驅(qū)和直接后繼的地址信息
1.4 鏈表中的基本概念
頭結(jié)點(diǎn)： 鏈表中的輔助結(jié)點(diǎn)，包含指向第一個(gè)數(shù)據(jù)元素的指針。
數(shù)據(jù)結(jié)點(diǎn)： 鏈表中代表數(shù)據(jù)元素的結(jié)點(diǎn)，表現(xiàn)形式為：（數(shù)據(jù)元素，地址）。
尾結(jié)點(diǎn)： 鏈表中的最后一個(gè)數(shù)據(jù)結(jié)點(diǎn)，包含的地址信息為空。
1.5 單鏈表中的結(jié)點(diǎn)定義
1.6 單鏈表的內(nèi)部結(jié)構(gòu)
頭結(jié)點(diǎn)在單鏈表中的意義： 輔助數(shù)據(jù)元素的定位，方便插入和刪除操作；因此，頭結(jié)點(diǎn)不存儲(chǔ)實(shí)際的數(shù)據(jù)元素。
1.7 在目標(biāo)位置處插入數(shù)據(jù)元素
node->value = e;
node->next = current->next;
current->next = node;
1.8 在目標(biāo)位置處刪除數(shù)據(jù)元素
toDel = current->next;
current->next = toDel->next;
delete toDel;
注意： 插入和刪除操作一定要保證鏈表的完整性。
2 LinkList設(shè)計(jì)要點(diǎn)
- 類模板，通過頭結(jié)點(diǎn)訪問后繼結(jié)點(diǎn)。
- 定義內(nèi)部結(jié)點(diǎn)類型Node，用于描述數(shù)據(jù)域和指針域。
- 實(shí)現(xiàn)線性表的關(guān)鍵操作（增，刪，查，等）。
3 繼承關(guān)系圖和接口實(shí)現(xiàn)
繼承關(guān)系圖
接口實(shí)現(xiàn)
4 代碼實(shí)現(xiàn)
LinkList.h
#ifndef LINKLIST_H #define LINKLIST_H#include "List.h" #include "Exception.h"namespace LemonLib { template < typename T > class LinkList : public List<T> { protected:struct Node : public Object{T value;Node* next;};mutable Node m_header;int m_length;Node* position(int index) const{Node* ret = &m_header;for (int i=0; i<index; i++){ret = ret->next;}return ret;} public:LinkList(){m_header.next = NULL;m_length = 0;}bool insert(int index, const T& e){bool ret = (0 <= index) && (index <= m_length);if (ret){Node* node = new Node();if (node != NULL){Node* current = position(index);node->value = e;node->next = current->next;current->next = node;m_length++;}else{THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to inset element ...");}}return ret;}bool insert(const T& e)// 插入到尾部{return insert(m_length, e);}bool remove(int index){bool ret = (0 <= index) && (index < m_length);if (ret){Node* current = position(index);Node* toDel = current->next;current->next = toDel->next;m_length--;delete toDel;}return ret;}bool set(int index, const T& e){bool ret = (0 <= index) && (index < m_length);if (ret){position(index)->next->value = e;}return ret;}bool get(int index, T& e) const{bool ret = (0 <= index) && (index < m_length);if (ret){e = position(index)->next->value;}return ret;}T get(int index) const{T ret;if (get(index, ret)){return ret;}else{THROW_EXCEPTION(InvalidParameterException, "Invalid parameter in get element...");}}int find(const T& e) const{int ret = -1;int index = 0;Node* current = m_header.next;while (current){if (current->value == e){ret = index;break;}else{index++;current = current->next;}}return ret;}int length() const{return m_length;}void clear(){while (m_header.next){Node* toDel = m_header.next;m_header.next = toDel->next;m_length--;delete toDel;}}~LinkList(){clear();} }; }#endif // LINKLIST_Hmain.cpp
#include <iostream> #include "Object.h" #include "Exception.h" #include "List.h" #include "Seqlist.h" #include "Staticlist.h" #include "Dynamiclist.h" #include "Staticarray.h" #include "DynamicArray.h" #include "Linklist.h"using namespace std; using namespace LemonLib;int main() {LinkList<int> list;for (int i=0; i<5; i++){list.insert(i);}for (int i=0; i<list.length(); i++){int val = 0;if (list.get(i, val)){cout << val << endl;}}cout << endl;list.remove(1);for (int i=0; i<list.length(); i++){cout << list.get(i) << endl;}cout << endl;return 0; }5 頭結(jié)點(diǎn)存在的隱患
如果寫出如上的代碼將會(huì)直接拋出異常，這顯然是不合適的，因?yàn)檫@個(gè)時(shí)候僅僅創(chuàng)建了單鏈表類而沒有創(chuàng)建有問題的Test類，因此我們需要對(duì)頭結(jié)點(diǎn)進(jìn)行優(yōu)化。
優(yōu)化后的代碼如下：
LinkList.h
6 順序表和單鏈表分析
6.1 時(shí)間復(fù)雜度對(duì)比分析
順序表的整體時(shí)間復(fù)雜度比單鏈表要低，那么單鏈表還有使用價(jià)值嗎？
6.2 效率深度分析
注意：在實(shí)際工程開發(fā)中，時(shí)間復(fù)雜度只是效率的一個(gè)參考指標(biāo)。
| 內(nèi)置基礎(chǔ)類型 | 順序表和鏈表效率不相上下 | 順序表和鏈表效率不相上下 |
| 自定義類型 | 順序表在效率上低于單鏈表 | 順序表在效率上低于單鏈表 |
| 插入和刪除 | 涉及大量數(shù)據(jù)對(duì)象的復(fù)制操作 | 只涉及指針操作，效率與數(shù)據(jù)對(duì)象無關(guān) |
| 數(shù)據(jù)訪問 | 隨機(jī)訪問，可直接定位數(shù)據(jù)對(duì)象 | 順序訪問，必須從頭訪問數(shù)據(jù)，無法直接定位 |
工程開發(fā)中的實(shí)際選擇：
- 順序表：數(shù)據(jù)元素類型相對(duì)簡單，不涉及深拷貝；數(shù)據(jù)元素相對(duì)穩(wěn)定，訪問操作遠(yuǎn)多于插入和刪除操作。
- 單鏈表：數(shù)據(jù)元素類型相對(duì)復(fù)雜，復(fù)制操作相對(duì)耗時(shí)；數(shù)據(jù)元素不穩(wěn)定，需要經(jīng)常插入和刪除，訪問操作較少。
7 單鏈表的遍歷與優(yōu)化
7.1 當(dāng)前遍歷的問題
問題： 如何遍歷單鏈表中每一個(gè)元素？
對(duì)于當(dāng)前實(shí)現(xiàn)的鏈表來說，可以用如下的方式進(jìn)行遍歷：
可以看到通過上面的遍歷方法我們不能以線性的時(shí)間復(fù)雜度完成單鏈表的遍歷，目前遍歷鏈表的時(shí)間復(fù)雜度是O(n2)，這顯然是有改進(jìn)的空間的。我們需要為單鏈表提供新的方法，以便實(shí)現(xiàn)在線性的時(shí)間內(nèi)完成遍歷。
7.2 優(yōu)化的思路
設(shè)計(jì)思路
- 在單鏈表內(nèi)部定義一個(gè)游標(biāo)（Node* m_current）
- 遍歷開始前將游標(biāo)指向位置為0的數(shù)據(jù)元素
- 獲取游標(biāo)指向的數(shù)據(jù)元素
- 通過結(jié)點(diǎn)中的next指針移動(dòng)游標(biāo)
我們可以提供如下的一組函數(shù)，從而以線性的時(shí)間復(fù)雜度遍歷鏈表。
遍歷函數(shù)原型設(shè)計(jì)
注意：遍歷相關(guān)的成員函數(shù)是相互依賴、相互配合的關(guān)系，一定要按照規(guī)則使用，否則將有可能出現(xiàn)錯(cuò)誤！
7.3 代碼實(shí)現(xiàn)
為了實(shí)現(xiàn)單鏈表類的擴(kuò)展，我們對(duì)當(dāng)前單鏈表內(nèi)部再進(jìn)行一次封裝。
為了提高擴(kuò)展性，我們對(duì)結(jié)點(diǎn)的申請(qǐng)和釋放進(jìn)行封裝，這樣我們就可以自己指定結(jié)點(diǎn)分配的空間。這里我們?yōu)殪o態(tài)單鏈表（StaticLinkList）的實(shí)現(xiàn)做準(zhǔn)備，StaticLinkList與LinkList的不同僅在于鏈表結(jié)點(diǎn)在內(nèi)存分配上的不同。因此，只需要將僅有不同封裝在父類和子類的虛函數(shù)中。
LinkList.h
#ifndef LINKLIST_H #define LINKLIST_H#include "List.h" #include "Exception.h"namespace LemonLib { template < typename T > class LinkList : public List<T> { protected:struct Node : public Object{T value;Node* next;};/* 注意：當(dāng)前結(jié)構(gòu)體必須繼承自O(shè)bject類，否則會(huì)導(dǎo)致和Node的內(nèi)存布局不同，直接拋出異常 */mutable struct : public Object{char reserved[sizeof(T)];Node* next;}m_header;int m_length;Node* m_current;int m_step;Node* position(int index) const{Node* ret = reinterpret_cast<Node*>(&m_header);for (int i=0; i<index; i++){ret = ret->next;}return ret;}virtual Node* create(){return new Node();}virtual void destroy(Node* pn){delete pn;} public:LinkList(){m_header.next = NULL;m_length = 0;m_current = NULL;m_step = 0;}bool insert(int index, const T& e){bool ret = (0 <= index) && (index <= m_length);if (ret){Node* node = create();if (node != NULL){Node* current = position(index);node->value = e;node->next = current->next;current->next = node;m_length++;}else{THROW_EXCEPTION(NoEnoughMemoryException, "No enough memory to inset element ...");}}return ret;}bool insert(const T& e)// 插入到尾部{return insert(m_length, e);}bool remove(int index){bool ret = (0 <= index) && (index < m_length);if (ret){Node* current = position(index);Node* toDel = current->next;current->next = toDel->next;if (m_current == toDel){m_current = toDel->next;}m_length--;destroy(toDel);}return ret;}bool set(int index, const T& e){bool ret = (0 <= index) && (index < m_length);if (ret){position(index)->next->value = e;}return ret;}bool get(int index, T& e) const{bool ret = (0 <= index) && (index < m_length);if (ret){e = position(index)->next->value;}return ret;}virtual T get(int index) const{T ret;if (get(index, ret)){return ret;}else{THROW_EXCEPTION(InvalidParameterException, "Invalid parameter in get element...");}}int find(const T& e) const{int ret = -1;int index = 0;Node* current = m_header.next;while (current){if (current->value == e){ret = index;break;}else{index++;current = current->next;}}return ret;}virtual bool move(int index, int step = 1){bool ret = ((0 <= index) && (index < m_length) && (step > 0));if (ret){m_current = position(index)->next;m_step = step;}return ret;}virtual bool end(){return (m_current == NULL);}virtual T current(){if (!end()){return m_current->value;}else{THROW_EXCEPTION(InvalidOperationException, "Invalid operation to get current value ...");}}virtual bool next(){int i = 0;while ((i < m_step) && (!end())){m_current = m_current->next;i++;}return (i == m_step);}int length() const{return m_length;}void clear(){while (m_header.next){Node* toDel = m_header.next;m_header.next = toDel->next;m_length--;destroy(toDel);}}~LinkList(){clear();} }; }#endif // LINKLIST_Hmain.cpp
#include <iostream> #include "Object.h" #include "Exception.h" #include "List.h" #include "Seqlist.h" #include "Staticlist.h" #include "Dynamiclist.h" #include "Staticarray.h" #include "DynamicArray.h" #include "Linklist.h"using namespace std; using namespace LemonLib;int main() {LinkList<int> list;for (int i=0; i<5; i++){list.insert(0, i);}for (list.move(0); !list.end(); list.next()){cout << list.current() << endl;}return 0; }總結(jié)
- 上一篇： 抗美援潮起止时间
- 下一篇： 使用C++访问MySQL数据库（VS20