一、單鏈表的結(jié)構(gòu)（以數(shù)據(jù)為不重復(fù)整數(shù)為例）
0、overview
鏈表元素由數(shù)據(jù)和指針構(gòu)成，因此鏈表的節(jié)點(diǎn)可以由一個(gè)包含這兩種元素的結(jié)構(gòu)體代表：
// 單鏈表節(jié)點(diǎn)
struct SingleListNode {
int data;
SingleListNode* next;
SingleListNode(int val, SingleListNode* ptr = nullptr);
};
鏈表包含插入、刪除操作，而插入、刪除又必須先查找元素是否存在，因此查找方法也必不可少。
//單鏈表
class SingleList {
public:
SingleListNode* dummy;
SingleList();
~SingleList();
public:
void add(int);
void remove(int);
SingleListNode* find(int);
};
1、插入操作
例如：我們需要在偽頭節(jié)點(diǎn)（不包含數(shù)據(jù)）和含有1的節(jié)點(diǎn)之間插入一個(gè)節(jié)點(diǎn)，發(fā)現(xiàn)，只需要改變dummy的指針和需要插入的指針即可。那么很容易想到下面的步驟：
-
將dummy的指針指向要添加的節(jié)點(diǎn)
-
將要添加節(jié)點(diǎn)的指針指向之前的下一個(gè)節(jié)點(diǎn)
 |
 |
|---|
這樣我們就添加了一個(gè)節(jié)點(diǎn)。
但是發(fā)現(xiàn)了一個(gè)問(wèn)題：因?yàn)閱蜗蜴湵碇荒?strong>通過(guò)前一個(gè)的指針尋找下一個(gè)元素，如果該指針指向改變了，我們就永遠(yuǎn)也找不到下一個(gè)元素了，因此，上面步驟2是錯(cuò)誤的。那我們應(yīng)該如何添加元素？
正確的添加順序：
-
先將要添加的元素的指針指向dummy節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)
-
再將dummy節(jié)點(diǎn)的指針指向要添加的節(jié)點(diǎn)
 |
 |
|---|
插入的情況討論：
- 插入時(shí)這里為了方便統(tǒng)一在dummy節(jié)點(diǎn)之后插入，也即每次插入一個(gè)新元素都在開(kāi)頭插入
圖例：
| 初始 | 插入2 | 插入3 |
|---|---|---|
 |
 |
 |
插入的代碼邏輯：
- 讀取find函數(shù)返回值判讀元素是否已存在
- 存在則輸出插入失敗，并返回
- 不存在則執(zhí)行插入操作
void SingleList::add(int val) {
auto ptr = find(val);
if (ptr) {
std::cerr << val << " exists, add failed!" << std::endl;
return;
} else {
auto temp = new SingleListNode(val);
temp->next = dummy->next;
dummy->next = temp;
}
}
2、刪除操作
相比于插入，刪除要簡(jiǎn)單一些
例如我們要?jiǎng)h除上圖包含2的節(jié)點(diǎn)，只需執(zhí)行下面的步驟
- 將需要?jiǎng)h除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的指針指向需要?jiǎng)h除的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，也即dummy的節(jié)點(diǎn)指向1
- 再將需要?jiǎng)h除的節(jié)點(diǎn)釋放掉
 |
 |
|---|
刪除的代碼邏輯：
- 讀取find函數(shù)的返回值判斷元素是否存在
- 不存在則輸出錯(cuò)誤提示并返回
- 存在則執(zhí)行刪除操操作
void SingleList::remove(int val) {
auto ptr = find(val);
if (ptr == nullptr) {
std::cerr << val << " does not exist, remove failed!" << std::endl;
return;
} else {
auto temp = ptr->next;
ptr->next = ptr->next->next;
delete temp;
}
}
3、查找操作
通過(guò)對(duì)插入和刪除的討論，我們了解到，插入調(diào)用find函數(shù)時(shí)，并不需要操作其返回值，所以，返回值具體是該元素的節(jié)點(diǎn)還是其前面的節(jié)點(diǎn)并沒(méi)有影響；但是，由于單鏈表只能通過(guò)前一個(gè)的指針尋找下一個(gè)元素，因此，刪除操作時(shí)我們必須得到需要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，因此find的返回值必須設(shè)為需要尋找的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，而第一個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)是dummy，這也是我們需要dummy這個(gè)偽頭節(jié)點(diǎn)的原因之一。
查找代碼的邏輯：
- 從第一個(gè)含有元素的節(jié)點(diǎn)開(kāi)始尋找，依次向后
- 如果找到該節(jié)點(diǎn)，則返回之
- 如果鏈表遍歷完也沒(méi)有找到，就返回nullptr
SingleListNode* SingleList::find(int val) {
auto prev = dummy;
auto temp = dummy->next;
while (temp) {
if (temp->data == val)
return prev;
prev = prev->next;
temp = temp->next;
}
return nullptr;
}
循環(huán)鏈表的查找
當(dāng)單鏈表為循環(huán)鏈表時(shí)，最后一個(gè)元素的next指針不是指向nullptr，而是dummy節(jié)點(diǎn)，因此，查找代碼有一些小變化，同時(shí)構(gòu)造、析構(gòu)以及測(cè)試代碼都圍繞dummy的next指針有相應(yīng)的小變化（詳見(jiàn)代碼）文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-716894.html
SingleListNode* SingleList::find(int val) {
auto prev = dummy;
auto temp = dummy->next;
while (temp != dummy) { //循環(huán)條件變?yōu)閠emp不等于dummy
if (temp->data == val)
return prev;
prev = prev->next;
temp = temp->next;
}
return nullptr;
}
4、完整代碼
// SingleList.h 單鏈表類定義
// 單鏈表節(jié)點(diǎn)
struct SingleListNode {
int data;
SingleListNode* next;
SingleListNode(int val, SingleListNode* ptr = nullptr);
};
//單鏈表
class SingleList {
public:
SingleListNode* dummy;
SingleList();
~SingleList();
public:
void add(int);
void remove(int);
SingleListNode* find(int);
};
// SingleList.cpp 單鏈表類的函數(shù)實(shí)現(xiàn)及靜態(tài)成員定義
#include <iostream>
#include "SingleList.h"
SingleListNode::SingleListNode(int val, SingleListNode* ptr)
: data(val), next(ptr) { }
SingleList::SingleList() : dummy(new SingleListNode(-1)) { }
SingleList::~SingleList() {
auto ptr = dummy->next;
while (ptr) {
auto temp = ptr;
ptr = ptr->next;
delete temp;
std::cout << "Element deleted!" << std::endl;
}
delete dummy;
std::cout << "SingleList Destroyed!" << std::endl;
}
void SingleList::add(int val) {
auto ptr = find(val);
if (ptr) {
std::cerr << val << " exists, add failed!" << std::endl;
return;
} else {
auto temp = new SingleListNode(val);
temp->next = dummy->next;
dummy->next = temp;
}
}
void SingleList::remove(int val) {
auto ptr = find(val);
if (ptr == nullptr) {
std::cerr << val << " does not exist, remove failed!" << std::endl;
return;
} else {
auto temp = ptr->next;
ptr->next = ptr->next->next;
delete temp;
}
}
SingleListNode* SingleList::find(int val) {
auto prev = dummy;
auto temp = dummy->next;
while (temp) {
if (temp->data == val)
return prev;
prev = prev->next;
temp = temp->next;
}
return nullptr;
}
// SingleListTest.cpp 對(duì)該單鏈表的測(cè)試代碼
#include <iostream>
#include "SingleList.h"
int main(void) {
SingleList list;
list.add(0);
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(4); // 添加已存在元素
list.remove(0); // 末尾元素
list.remove(2); // 中間元素
list.remove(4); // 開(kāi)頭元素
list.remove(4); // 刪除不存在元素
for (auto temp = list.dummy->next; temp; temp = temp->next)
std::cout << temp->data << " ";
std::cout << std::endl;
/*期望的輸出
4 exists, add failed!
4 does not exist, remove failed!
3 1
Element deleted!
Element deleted!
SingleList Destroyed!
*/
return 0;
}
5、循環(huán)鏈表的代碼
鏈表的結(jié)構(gòu)僅有查找函數(shù)有變化同時(shí)，測(cè)試的代碼也有相應(yīng)的變化文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-716894.html
// SingleList.h 單循環(huán)鏈表類定義
// 單循環(huán)鏈表節(jié)點(diǎn)
struct SingleListNode {
int data;
SingleListNode* next;
SingleListNode(int val, SingleListNode* ptr = nullptr);
};
//單循環(huán)鏈表
class SingleList {
public:
SingleListNode* dummy;
SingleList();
~SingleList();
public:
void add(int);
void remove(int);
SingleListNode* find(int);
};
// SingleList.cpp 單循環(huán)鏈表類的函數(shù)實(shí)現(xiàn)及靜態(tài)成員定義
#include <iostream>
#include "SingleList.h"
SingleListNode::SingleListNode(int val, SingleListNode* ptr)
: data(val), next(ptr) { }
SingleList::SingleList()
: dummy(new SingleListNode(-1)) { // 構(gòu)造dummy時(shí)，需要把next指向本身
dummy->next = dummy;
}
SingleList::~SingleList() {
auto ptr = dummy->next;
while (ptr != dummy) { // 析構(gòu)條件變?yōu)閜tr != dummy
auto temp = ptr;
ptr = ptr->next;
delete temp;
std::cout << "Element deleted!" << std::endl;
}
delete dummy;
std::cout << "SingleList Destroyed!" << std::endl;
}
void SingleList::add(int val) {
auto ptr = find(val);
if (ptr) {
std::cerr << val << " exists, add failed!" << std::endl;
return;
} else {
auto temp = new SingleListNode(val);
temp->next = dummy->next;
dummy->next = temp;
}
}
void SingleList::remove(int val) {
auto ptr = find(val);
if (ptr == nullptr) {
std::cerr << val << " does not exist, remove failed!" << std::endl;
return;
} else {
auto temp = ptr->next;
ptr->next = ptr->next->next;
delete temp;
}
}
SingleListNode* SingleList::find(int val) {
auto prev = dummy;
auto temp = dummy->next;
while (temp != dummy) { //循環(huán)條件變?yōu)閠emp不等于dummy
if (temp->data == val)
return prev;
prev = prev->next;
temp = temp->next;
}
return nullptr;
}
// SingleListTest.cpp 對(duì)該單循環(huán)鏈表的測(cè)試代碼
#include <iostream>
#include "SingleList.h"
int main(void) {
SingleList list;
list.add(0);
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(4); // 添加已存在元素
list.remove(0); // 末尾元素
list.remove(2); // 中間元素
list.remove(4); // 開(kāi)頭元素
list.remove(4); // 刪除不存在元素
for (auto temp = list.dummy->next; temp != list.dummy; temp = temp->next) // 循環(huán)鏈表循環(huán)條件為temp != list.dummy
std::cout << temp->data << " ";
std::cout << std::endl;
/*期望的輸出
4 exists, add failed!
4 does not exist, remove failed!
3 1
Element deleted!
Element deleted!
SingleList Destroyed!
*/
return 0;
}
到了這里，關(guān)于C++實(shí)現(xiàn)單鏈表【每一步詳細(xì)深入講解，代碼清晰、簡(jiǎn)單、易懂】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[C++]：萬(wàn)字超詳細(xì)講解多態(tài)以及多態(tài)的實(shí)現(xiàn)原理（面試的必考的c++考點(diǎn)）](https://imgs.yssmx.com/Uploads/2024/02/421127-1.png)
