?文中代碼源文件已上傳：數(shù)據(jù)結(jié)構(gòu)源碼 <-上一篇 初級數(shù)據(jù)結(jié)構(gòu)（一）——順序表????????|????????NULL 下一篇->

1、鏈表特征

? ? ? ? 與順序表數(shù)據(jù)連續(xù)存放不同，鏈表中每個(gè)數(shù)據(jù)是分開存放的，而且存放的位置尤其零散，毫無規(guī)則可言。對于零散的數(shù)據(jù)而言，我們當(dāng)然可以通過某種方式統(tǒng)一存儲每一個(gè)數(shù)據(jù)存放的地址，如下圖：

????????但這個(gè) sheet 無論怎么看都是一個(gè)數(shù)組，而 ptr_data 是個(gè)指針，也就是說，以上數(shù)據(jù)結(jié)構(gòu)仍然是一種順序表，只不過表中的數(shù)據(jù)從具體的值改為指針。它仍然沒有脫離順序表的范疇。自然順序表的優(yōu)勢及劣勢它也照單全收。

????????順序表的劣勢在于，開辟空間并非隨需開辟，釋放空間也顯得不那么靈活。如果順序表做到每次增加數(shù)據(jù)便拓展空間，刪除數(shù)據(jù)便回收空間，基于 realloc 可能異地開辟的特點(diǎn)，搬運(yùn)數(shù)據(jù)的時(shí)間復(fù)雜度為 O(N) 。如果順序表的長度是幾千萬乃至幾億，每添加或者刪除一個(gè)數(shù)據(jù)，其延遲是難以忽略的。因此上篇中的順序表每次開辟空間均是成批開辟。但這種方式也必然造成空間的浪費(fèi)。

? ? ? ? 如果有一種儲存方式可以解決上述問題，做到每一個(gè)數(shù)據(jù)的空間都按需開辟，且按需釋放，那么在最極端的情況下，它甚至可以節(jié)省近一半存儲空間。在此思想上，數(shù)組的特性完全不符合該要求，首先需要拋棄的便是數(shù)組。但上圖倘若沒了數(shù)組，每一個(gè)數(shù)據(jù)節(jié)點(diǎn)的位置便無從知曉。于是有了鏈表的概念。

? ? ? ? 鏈表可以將下一個(gè)節(jié)點(diǎn)的位置儲存在上一個(gè)節(jié)點(diǎn)中，此外還可以將上一個(gè)節(jié)點(diǎn)的位置儲存在下一個(gè)節(jié)點(diǎn)中。

? ? ? ? 如上圖。鏈表還需要一個(gè)頭指針指向第一個(gè)節(jié)點(diǎn)。上述結(jié)構(gòu)稱為單鏈表。此外鏈表還有以下常見結(jié)構(gòu)（環(huán)鏈、雙向鏈）。

????????比如這篇文章最頂端“上一篇”、“下一篇”的導(dǎo)航鏈接就類似雙向鏈。?

2、鏈表創(chuàng)建

2.1、文件結(jié)構(gòu)

? ? ? ? 本文以最基本的單鏈為例，因?yàn)槠渌冃伪葐捂湹膹?fù)雜程度高不了多少，有機(jī)會再作補(bǔ)充。仍是先從文件結(jié)構(gòu)開始，分別建立以下三個(gè)文件，

????????lnkTab.h ：用于創(chuàng)建結(jié)構(gòu)體類型及聲明函數(shù)；

? ? ? ? lnkFunction.c ：用于創(chuàng)建鏈表各種操作功能的函數(shù)；

? ? ? ? main.c ：僅創(chuàng)建?main 函數(shù)，用作測試。

2.2、前期工作

? ? ? ? 在 lnkTab.h 中先碼入以下內(nèi)容：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>//自定義數(shù)據(jù)類型和打印類型，方便后續(xù)更改儲存數(shù)據(jù)的類型
#define PRINT_FORMAT "%d"
typedef int DATATYPE;//創(chuàng)建鏈表節(jié)點(diǎn)的結(jié)構(gòu)體類型
typedef struct LinkedListType
{DATATYPE data;struct LinkedListType* next;
}LinkedListType;//---------------------函數(shù)聲明---------------------
//打印鏈表
extern void DataPrint(LinkedListType*);//創(chuàng)建節(jié)點(diǎn)
extern LinkedListType* NodeCreate(const DATATYPE, const LinkedListType*);//銷毀鏈表
extern void DataDestory(LinkedListType**);

????????在 lnkFunction.c 中包含?lnkTab.h?并分別創(chuàng)建一個(gè)打印鏈表和銷毀鏈表的函數(shù)：?

#include "lnkTab.h"//打印鏈表
void DataPrint(LinkedListType* ptr_headNode)
{//創(chuàng)建節(jié)點(diǎn)指針LinkedListType* currentNode = ptr_headNode;//循環(huán)打印while (currentNode){//打印printf(PRINT_FORMAT" -> ", currentNode->data);//移動節(jié)點(diǎn)指針currentNode = currentNode->next;}printf("NULL\n");
}//創(chuàng)建節(jié)點(diǎn)
LinkedListType* NodeCreate(const DATATYPE data, const LinkedListType* next)
{LinkedListType* node = (LinkedListType*)malloc(sizeof(LinkedListType));//加入判斷防止空間開辟失敗if (node == NULL){perror("Malloc Fail");return NULL;}//節(jié)點(diǎn)賦值node->data = data;node->next = next;return node;
}//銷毀鏈表
void DataDestory(LinkedListType** ptr2_headNode)
{//空鏈表判斷if (!ptr2_headNode) return;//創(chuàng)建節(jié)點(diǎn)指針LinkedListType* currentNode = *ptr2_headNode;//循環(huán)逐個(gè)銷毀節(jié)點(diǎn)while (currentNode){LinkedListType* nextNode = currentNode->next;free(currentNode);currentNode = nextNode;}//頭指針置空*ptr2_headNode = NULL;
}

????????最后在 main.c 中包含?lnkTab.h，并創(chuàng)建一個(gè)鏈表頭指針：

#include "lnkTab.h"int main()
{LinkedListType* ptr_headNode = NULL;return 0;
}

????????至此，前期工作準(zhǔn)備完畢。

3、鏈表操作

3.1、增

? ? ? ? 同順序表一樣，鏈表除了指定位置插入數(shù)據(jù)之外，最好也定義下頭部插入數(shù)據(jù)及尾部插入數(shù)據(jù)的函數(shù)。因此先在 lnkTab.h 中加入以下函數(shù)聲明：

//指定位置插入數(shù)據(jù)
extern void DataPush(LinkedListType**, const int, const DATATYPE);
//頭部插入數(shù)據(jù)
extern void DataPushHead(LinkedListType**, const DATATYPE);
//尾部插入數(shù)據(jù)
extern void DataPushTail(LinkedListType**, const DATATYPE);

????????之后先創(chuàng)建 DataPush 函數(shù)。在此之前把函數(shù)的流程圖畫出，以助于思考。畫流程圖的過程中能認(rèn)識到空鏈表跟非空鏈表要分開處理，除了頭插，其他位置插入的邏輯是相同的：

????????對照上圖，照著在 lnkFunction.c 里寫出如下代碼：

void DataPush(LinkedListType** ptr2_headNode, const int pos, const DATATYPE data)
{//有效性檢查if (!ptr2_headNode) return;LinkedListType* currentNode = *ptr2_headNode;//如果插入位置小于等于0或者沒有節(jié)點(diǎn)if (pos <= 0 || !currentNode){//創(chuàng)建節(jié)點(diǎn)，將頭指針的值賦予該節(jié)點(diǎn)的指向，并將頭指針指向該節(jié)點(diǎn)LinkedListType* node = NodeCreate(data, currentNode);*ptr2_headNode = node;return;}//遍歷節(jié)點(diǎn)至插入位置前一節(jié)點(diǎn)for (int i = 0; i < pos - 1; i++){//若遇到最后一個(gè)節(jié)點(diǎn)則停止遍歷，當(dāng)前節(jié)點(diǎn)指針指向最后一個(gè)節(jié)點(diǎn)if (currentNode->next)currentNode = currentNode->next;elsebreak;}//創(chuàng)建節(jié)點(diǎn)，將當(dāng)前節(jié)點(diǎn)的指向值賦予創(chuàng)建的該節(jié)點(diǎn)的指向，并將當(dāng)前節(jié)點(diǎn)指向創(chuàng)建的節(jié)點(diǎn)LinkedListType* node = NodeCreate(data, currentNode->next);currentNode->next = node;
}

?????????至于頭插尾插數(shù)據(jù)，只不過是上述函數(shù) pos 位置的區(qū)別。因此：

//pos = 0 便是頭插
void DataPushHead(LinkedListType** ptr2_headNode, const DATATYPE data)
{DataPush(ptr2_headNode, 0, data);
}//由于 DataPush 函數(shù)在 pos 大于節(jié)點(diǎn)數(shù)時(shí)自動進(jìn)行尾插
//因此 pos = INT_MAX 在任意情況下都是尾插
void DataPushTail(LinkedListType** ptr2_headNode, const DATATYPE data)
{DataPush(ptr2_headNode, INT_MAX, data);
}

? ? ? ? 驗(yàn)證環(huán)節(jié)。在 main 函數(shù)中加入如下代碼試運(yùn)行：

	DataPush(&ptr_headNode, 10, 1234);DataPrint(ptr_headNode);        // 1234 NULLDataPushTail(&ptr_headNode, 1);DataPrint(ptr_headNode);        // 1234 1 NULLDataPushHead(&ptr_headNode, 2);DataPrint(ptr_headNode);        // 2 1234 1 NULLDataPushTail(&ptr_headNode, 3);DataPrint(ptr_headNode);        // 2 1234 1 3 NULLDataPush(&ptr_headNode, 1, 14542);DataPrint(ptr_headNode);        // 2 14542 1234 1 3 NULLDataPushHead(&ptr_headNode, 4);DataPrint(ptr_headNode);        // 4 2 14542 1234 1 3 NULLDataPushTail(&ptr_headNode, 114514);DataPrint(ptr_headNode);        // 4 2 14542 1234 1 3 114514 NULLDataPush(&ptr_headNode, 10, 1442);DataPrint(ptr_headNode);        // 4 2 14542 1234 1 3 114514 1442 NULL

?????????結(jié)果與預(yù)期無誤。至此插入功能便已完成。

3.2、刪

? ? ? ? 第一步當(dāng)然是在 lnkTab.h 中加入函數(shù)聲明：

//指定位置刪除數(shù)據(jù)
extern void DataPop(LinkedListType**, const int, const int);
//頭部刪除數(shù)據(jù)
extern void DataPopHead(LinkedListType**);
//尾部刪除數(shù)據(jù)
extern void DataPopTail(LinkedListType**);

? ? ? ? 完畢后，二話不說，先上流程圖。這里同樣要注意區(qū)分空鏈和其他位置刪除。不過刪除節(jié)點(diǎn)還得將頭刪及其他位置刪除分開判定。

? ? ? ? 而且這里要注意的是，刪除與插入不同，萬一 pos 值傳錯(cuò)導(dǎo)致小于 0 或者大于鏈表長度，便不能如上圖簡單粗暴地執(zhí)行頭刪尾刪。創(chuàng)建函數(shù)的時(shí)候多加一個(gè)參數(shù)來判斷是否要在這種情況下頭刪或者尾刪最好不過了。為了直觀，還是在 lnkTab.h 頭文件中加個(gè)枚舉類型：

//定義刪除節(jié)點(diǎn)的暴力模式和非暴力模式
enum Deletion { UNFORCED, FORCED };

? ? ? ? 然后，在 lnkFunction.c 里碼下這些：

void DataPop(LinkedListType** ptr2_headNode, const int pos, const int deletionMode)
{//如果沒有節(jié)點(diǎn)則直接退出if (!ptr2_headNode || !*ptr2_headNode) return;LinkedListType* currentNode = *ptr2_headNode;//如果插入位置小于等于0則頭刪，前提是在非暴力模式下if (pos == 0 || (pos < 0 && deletionMode)){*ptr2_headNode = (*ptr2_headNode)->next;free(currentNode);return;}//遍歷節(jié)點(diǎn)至需要刪除的節(jié)點(diǎn)前一節(jié)點(diǎn)int i;for (i = 1; i <= pos - 1; i++){//若遇到倒數(shù)第二個(gè)節(jié)點(diǎn)則停止遍歷，當(dāng)前節(jié)點(diǎn)指針指向倒數(shù)第二個(gè)節(jié)點(diǎn)if (currentNode->next->next)currentNode = currentNode->next;elsebreak;}//模式不暴力的話，pos超出表長度就直接退出了if (i < pos - 1 && !deletionMode) return;//刪！LinkedListType* freeNode = currentNode->next;currentNode->next = currentNode->next->next;free(freeNode);
}

? ? ? ? 然后頭刪 pos 為 0 ，尾刪 pos = INT_MAX 且刪除模式為 FORCED 。就沒必要再贅述了：

//刪除頭部節(jié)點(diǎn)
void DataPopHead(LinkedListType** ptr2_headNode)
{DataPop(ptr2_headNode, 0, UNFORCED);
}//刪除尾部節(jié)點(diǎn)
void DataPopTail(LinkedListType** ptr2_headNode)
{DataPop(ptr2_headNode, INT_MAX, FORCED);
}

? ? ? ? 題外話，這里再提另一種更安全的方式，?指定位置刪除的 pos 如果超出鏈表范圍直接報(bào)錯(cuò)，然后頭刪尾刪單獨(dú)寫：

//刪除頭部節(jié)點(diǎn)
void DataPopHead(LinkedListType** ptr2_headNode)
{if (!ptr2_headNode) return;LinkedListType* currentNode = *ptr2_headNode;//如果沒有節(jié)點(diǎn)則直接退出if (currentNode == NULL) return;//將頭指針置為第一個(gè)節(jié)點(diǎn)的指向，并釋放第一個(gè)節(jié)點(diǎn)*ptr2_headNode = currentNode->next;free(currentNode);
}//刪除尾部節(jié)點(diǎn)
void DataPopTail(LinkedListType** ptr2_headNode)
{if (!ptr2_headNode) return;LinkedListType* currentNode = *ptr2_headNode;//如果沒有節(jié)點(diǎn)則直接退出if (currentNode == NULL) return;//如果只有一個(gè)節(jié)點(diǎn)則采用頭刪else if (currentNode->next == NULL){DataPopHead(ptr2_headNode);return;}//遍歷至倒數(shù)第二個(gè)節(jié)點(diǎn)，釋放最后一個(gè)節(jié)點(diǎn)，并將倒數(shù)第二個(gè)節(jié)點(diǎn)指向置空else{while (currentNode->next->next){currentNode = currentNode->next;}free(currentNode->next);currentNode->next = NULL;}
}

? ? ? ? 回歸正題，之后是熟悉的測試階段。 main 函數(shù)中添加：?

	printf("\n----------DataPopTest----------\n");DataPop(&ptr_headNode, 0, UNFORCED);DataPrint(ptr_headNode);                // 2 14542 1234 1 3 114514 1442 NULLDataPop(&ptr_headNode, 2, UNFORCED);DataPrint(ptr_headNode);                // 2 14542 1 3 114514 1442 NULLDataPop(&ptr_headNode, 1000, UNFORCED);DataPrint(ptr_headNode);                // 2 14542 1 3 114514 1442 NULLDataPop(&ptr_headNode, 1000, FORCED);DataPrint(ptr_headNode);                // 2 14542 1 3 114514 NULLDataPop(&ptr_headNode, 0, UNFORCED);DataPrint(ptr_headNode);                // 14542 1 3 114514 NULL           DataPop(&ptr_headNode, 0, UNFORCED);DataPrint(ptr_headNode);                // 1 3 114514 NULL   DataPop(&ptr_headNode, 0, UNFORCED);DataPrint(ptr_headNode);                // 3 114514 NULL  DataPop(&ptr_headNode, 0, UNFORCED);DataPrint(ptr_headNode);                // 114514 NULL  DataPop(&ptr_headNode, 0, UNFORCED);DataPrint(ptr_headNode);                // NULL  DataPop(&ptr_headNode, 0, UNFORCED);DataPrint(ptr_headNode);                // NULL  

? ? ? ? 完事！?

3.3、改和查

? ? ? ? 這兩個(gè)功能簡直不要太簡單。查的邏輯跟打印邏輯一致，至于改，用查的功能返回節(jié)點(diǎn)地址，直接改 data 完事。

? ? ? ? lnkTab.h ：

//查找節(jié)點(diǎn)
extern LinkedListType* DataSearch(const LinkedListType*, const DATATYPE);
//修改節(jié)點(diǎn)
extern void DataModify(const LinkedListType*, DATATYPE, DATATYPE);

? ? ? ? lnkFunction.c：?

//查找節(jié)點(diǎn)
LinkedListType* DataSearch(const LinkedListType* ptr_headNode, const DATATYPE data)
{LinkedListType* currentNode = ptr_headNode;while (currentNode){if (currentNode->data == data) break;currentNode = currentNode->next;}return currentNode;
}//修改節(jié)點(diǎn)
void DataModify(const LinkedListType* ptr_headNode, DATATYPE target, DATATYPE replace)
{LinkedListType* node = DataSearch(ptr_headNode, target);if (!node) return;node->data = replace;
}

? ? ? ? ?main.c 測試：

printf("\n----------DataSearchModifyTest----------\n");for (int i = 20; i >= 10; i--){DataPushHead(&ptr_headNode, i);}DataPrint(ptr_headNode);            // 10 12 13 14 15 16 17 18 19 20 NULLDataModify(ptr_headNode, 3, 23457);	DataPrint(ptr_headNode);            // 10 12 13 14 15 16 17 18 19 20 NULLDataModify(ptr_headNode, 13, 23457);DataPrint(ptr_headNode);            // 10 12 23457 14 15 16 17 18 19 20 NULL

? ? ? ? 搞定！準(zhǔn)備下一篇。撒花！?

4、作點(diǎn)補(bǔ)充

? ? ? ? 一開始就提到雙向鏈表和環(huán)鏈。雖然結(jié)構(gòu)復(fù)雜了，但是這兩種結(jié)構(gòu)比單鏈簡單太多了?？梢哉f學(xué)懂了單鏈，那么其他結(jié)構(gòu)的鏈表跟玩似的。

? ? ? ? 以另一個(gè)常規(guī)的極端（不考慮中途環(huán)狀），環(huán)狀雙向鏈舉例。在數(shù)據(jù)操作的代碼上，這個(gè)結(jié)構(gòu)可比單鏈節(jié)省了尋找尾節(jié)點(diǎn)以及記錄上一個(gè)節(jié)點(diǎn)指針的麻煩。

? ? ? ? 雙向鏈如果一直找上一個(gè)（ prev ）節(jié)點(diǎn)，它也只不過是另一種單鏈，視作 next 結(jié)構(gòu)的倒序。最直觀的在于鏈表倒置：

while(currentNode)
{DATATYPE* nextNode = currentNode->next;currentNode->next = currentNode->prev;currentNode->prev = temp;currentNode = nextNode;
}

? ? ? ? 一個(gè)循環(huán)搞定整個(gè)鏈表導(dǎo)致，而如果是單鏈，需要考慮遍歷分別頭插之類的，代碼量直線上升。至于環(huán)鏈，尾節(jié)點(diǎn)的 next 指向頭節(jié)點(diǎn)。事實(shí)上這種結(jié)構(gòu)提供了尋找尾節(jié)點(diǎn)的便利（ currentNode->prev ）。那是更便利了，只不過不支持迭代，總有犧牲嘛。

? ? ? ? 構(gòu)建節(jié)點(diǎn)的結(jié)構(gòu)體特別自由，鏈表也就那么幾種大體結(jié)構(gòu)，細(xì)節(jié)沒有規(guī)定。總之，只要實(shí)現(xiàn)節(jié)點(diǎn)內(nèi)記錄其他節(jié)點(diǎn)的信息便屬于鏈表。奧力給！