目錄
一、順序表優(yōu)缺點(diǎn)
二、鏈表的定義
①：概念：
②：結(jié)點(diǎn)
③：單鏈表的定義：
④：頭結(jié)點(diǎn)：
三 、單鏈表的C語言結(jié)構(gòu)定義：
四、單鏈表基本操作：
四.1、遍歷單鏈表
四.2、用malloc函數(shù)創(chuàng)建新結(jié)點(diǎn)
四.3、尾插法
四.4、頭插法
四.5、尾刪法
四.6、頭刪法
一、順序表優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：我們知道順序表結(jié)構(gòu)簡單，便于隨機(jī)訪問表中任一元素；
缺點(diǎn)：順序存儲(chǔ)結(jié)構(gòu)不利于插入和刪除，不利于擴(kuò)充，也容易造成空間浪費(fèi)。
二、鏈表的定義
①：概念：
用一組任一的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素（可以是連續(xù)，也可以是不可連續(xù)的），數(shù)據(jù)元素之間的邏輯關(guān)系借助指示元素存儲(chǔ)位置的指針來表示，這種存儲(chǔ)方式叫做線性表的 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ，簡稱 鏈表 。②：結(jié)點(diǎn)
為了表示數(shù)據(jù)元素間的邏輯關(guān)系，除了存儲(chǔ)數(shù)據(jù)本身信息之外，還需要存放其直接后繼的存儲(chǔ)位置（地址），這兩部分（數(shù)據(jù)域和指針域）組成一個(gè) 結(jié)點(diǎn) 用于表示一個(gè)元素。數(shù)據(jù)域：存儲(chǔ)數(shù)據(jù)元素的信息；指針域：存放直接后繼的元素的地址。表示圖如下：
同時(shí)還需要注意以下幾點(diǎn)：注意：我們規(guī)定鏈表的尾結(jié)點(diǎn)（最后一個(gè)結(jié)點(diǎn)）的指針域?yàn)镹ULL，這樣可以方便進(jìn)行操作。
③：單鏈表的定義：
若鏈表的每個(gè)結(jié)點(diǎn)只包含一個(gè)指針域，則稱此鏈表為 線性鏈表或 單鏈表。④：頭結(jié)點(diǎn)：
有時(shí)為了操作方便，在單鏈表的第一個(gè)結(jié)點(diǎn)之前添加一個(gè)結(jié)點(diǎn)，稱為 頭結(jié)點(diǎn)或偽結(jié)點(diǎn)。不帶哨兵的頭結(jié)點(diǎn)就直接使用；
帶哨兵的頭結(jié)點(diǎn)就按以下規(guī)則：頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存放任何信息，也可以存放其他特殊信息；頭結(jié)點(diǎn)的指針域存放第一個(gè)結(jié)點(diǎn)的存儲(chǔ)地址，即指向第一個(gè)結(jié)點(diǎn)；
本次小編用的是不帶哨兵的頭結(jié)點(diǎn)。有頭結(jié)點(diǎn)的單鏈表叫做“帶頭結(jié)點(diǎn)的單鏈表”。
三 、單鏈表的C語言結(jié)構(gòu)定義：
typedef int SLDataType;//方便以后跟改數(shù)據(jù)類型 typedef struct SLisrNode { SLDataType data;//數(shù)據(jù)域 struct SListNode* next;//指針域 }Lnode, * LinkList;//用typedef重定義后，Londe為結(jié)點(diǎn)類型,LinkList為指向結(jié)點(diǎn)的指針類型
四、單鏈表基本操作：
作幾點(diǎn)說明：
①：為了方便讓大家感受一下單鏈表，所以先實(shí)現(xiàn)遍歷單鏈表，讓大家體會(huì)其結(jié)構(gòu)的韻味；
②：我們一般都默認(rèn)用帶有頭結(jié)點(diǎn)的單鏈表；
③：大家一般都會(huì)寫與控制臺(tái)有互動(dòng)的代碼，但小編這里只是帶大家入門上手，只是簡單實(shí)現(xiàn)，所以大家可以根據(jù)小編的思路自行設(shè)計(jì)。
④：本次實(shí)現(xiàn)小編也是采用多文件操作，沒聽說過的小伙伴可以大致了解一下，就幾句話意思很簡單。
⑤：跟往常不一樣的是，小編會(huì)把詳細(xì)說明放在注釋里面，大家請(qǐng)認(rèn)真解讀，有疑問或沒看懂的歡迎大家評(píng)論區(qū)討論。
四.1、遍歷單鏈表
源代碼：
//遍歷單鏈表 void SLTPrint(SLTNode* phead) { //一般頭指針phead我們都不會(huì)動(dòng)，方便我們多次操作 //所以我們可以創(chuàng)建一個(gè)臨時(shí)指針來進(jìn)行操作 SLTNode* tmp = phead; //因?yàn)閱捂湵砦步Y(jié)點(diǎn)的指針域?yàn)镹ULL，所以循環(huán)條件可以為tmp //當(dāng)tmp為NULL時(shí)，說明鏈表遍歷完成，并且退出循環(huán) while (tmp) { //打印數(shù)據(jù)域（打印"->"只是方便展示鏈表結(jié)構(gòu)) printf("%d->", tmp->data); //因?yàn)橹羔樣蛑赶蛳乱粋€(gè)結(jié)點(diǎn)，所以可以通過賦值方法找到下一個(gè)結(jié)點(diǎn) tmp = tmp->next; } //方便展示鏈表結(jié)構(gòu)，所以末尾打印一個(gè)NULL printf("->NULL\n"); }
四.2、用malloc函數(shù)創(chuàng)建新結(jié)點(diǎn)
因?yàn)橹羔榩head剛開始創(chuàng)建時(shí)并沒有指向任何結(jié)點(diǎn)，需要在程序執(zhí)行過程中通過按結(jié)點(diǎn)的類型向系統(tǒng)申請(qǐng)建立一個(gè)新結(jié)點(diǎn)，通過調(diào)用標(biāo)準(zhǔn)函數(shù)malloc動(dòng)態(tài)開辟空間生成，
即創(chuàng)建一個(gè)新結(jié)點(diǎn)，具體格式如下：
phead=(SLTNnode*)malloc(sizeof(SLTNode));當(dāng)phead結(jié)點(diǎn)不需要時(shí)，我們應(yīng)該用free函數(shù)釋放空間，收回結(jié)點(diǎn)；
因?yàn)橛卸喾N操作，所以我們將這個(gè)操作寫成一個(gè)函數(shù)，方便后續(xù)調(diào)用；
源代碼：
//創(chuàng)建新結(jié)點(diǎn) //因?yàn)橐祷貏?dòng)態(tài)申請(qǐng)的結(jié)點(diǎn)，所以有返回類型 SLTNode* BuySLiseNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); //判斷是否開辟成功 if (newnode == NULL) { perror("malloc"); exit(-1); } //填充數(shù)據(jù) newnode->data = x; newnode->next = NULL; //返回 return newnode; }
四.3、尾插法
尾插法：顧名思義就是在鏈表尾部進(jìn)行插入數(shù)據(jù)；
大致步驟分為兩步：
①：找到鏈表尾結(jié)點(diǎn)（根據(jù)尾結(jié)點(diǎn)的next域?yàn)镹ULL來作為循環(huán)條件進(jìn)行尋找）；
②：將新結(jié)點(diǎn)鏈接到尾結(jié)點(diǎn)的next域即可；
源代碼即解釋如下：
//尾插法 //函數(shù)第一個(gè)形參是二級(jí)指針，是存儲(chǔ)鏈表的地址，用的傳址調(diào)用 //函數(shù)第二個(gè)形參是要插入的數(shù)據(jù) void SLTPushBack(SLTNode** pphead1, SLTDataType x) { //得到一個(gè)新結(jié)點(diǎn) SLTNode* newnode = BuySLiseNode(x); //若鏈表為空鏈表，則直接將新結(jié)點(diǎn)賦值給鏈表，因?yàn)槲覀兪莻髦氛{(diào)用，可以改變外面鏈表的內(nèi)容 if (*pphead1 == NULL) { *pphead1 = newnode; } else { //同理將鏈表拷貝到一個(gè)臨時(shí)結(jié)點(diǎn)中便于操作 SLTNode* tmp = *pphead1; //①：找到尾結(jié)點(diǎn) //因?yàn)槲步Y(jié)點(diǎn)的next域?yàn)镹ULL，所以可以作為循環(huán)判斷條件 while (tmp->next == NULL) { tmp = tmp->next; } //②：鏈接 tmp->next = newnode; //這里可能有的小伙伴不理解，"覺得這里不也是直接賦值嗎，怎么改變外部鏈表的"? //所以大家就要注意一句話，如下： //1.改變結(jié)構(gòu)體，用結(jié)構(gòu)體指針 //2.改變結(jié)構(gòu)體指針，要用結(jié)構(gòu)體指針的指針（二級(jí)指針） // //上面的pphead就是一個(gè)結(jié)構(gòu)體二級(jí)指針，用于改變結(jié)構(gòu)體指針 //但這里的next是結(jié)構(gòu)體成員，所以我們只需要改變結(jié)構(gòu)體，所以就用結(jié)構(gòu)體指針 //而tmp本來就是我們結(jié)構(gòu)頭指針拷貝過來的，所以改變了tmp的next就相當(dāng)于改變了外部鏈表的尾結(jié)點(diǎn)的next } //因?yàn)閠mp、newnode這些都是局部變量，函數(shù)結(jié)束后會(huì)自動(dòng)銷毀 //第二次又會(huì)從初始位置開始操作，所以我們不用調(diào)整這些變量的值 //但鏈表結(jié)點(diǎn)內(nèi)容不會(huì)被銷毀，因?yàn)槲覀兪怯胢alloc函數(shù)在堆區(qū)上面申請(qǐng)的空間，只有free后才會(huì)銷毀 }測(cè)試結(jié)果：
void TestList2() { SLTNode* phead = NULL;//頭結(jié)點(diǎn),用于鏈接新結(jié)點(diǎn) //尾插100、200、300 SLTPushBack(&phead, 100); SLTPushBack(&phead, 200); SLTPushBack(&phead, 300); //打印 SLTPrint(phead); } int main() { //測(cè)試 // TestSLTist1(); TestList2(); return 0; }運(yùn)行結(jié)果：
四.4、頭插法
當(dāng)我們理解清楚尾插法里面的各種細(xì)節(jié)后，頭插以及后面的操作都會(huì)覺得很簡單；
頭插大致分為
①：將新結(jié)點(diǎn)的next域指向首結(jié)點(diǎn)；
②：再讓頭指針指向新結(jié)點(diǎn)；
源代碼及解釋如下：
//頭插法 //形參和尾插法是相同的道理 void SLTPushFront(SLTNode** pphead, SLTDataType x) { //因?yàn)槲覀兠恳徊蕉家褂貌粠诒念^結(jié)點(diǎn)，所以每次都要改變結(jié)構(gòu)體指針 // 所以形參用二級(jí)指針是必須的，并且不用區(qū)分鏈表是否為空 //先得到一個(gè)新結(jié)點(diǎn) SLTNode* tmp = BuySLiseNode(x); //①：新結(jié)點(diǎn)的next域指向首結(jié)點(diǎn) tmp->next = *pphead; //②：頭結(jié)點(diǎn)指向新結(jié)點(diǎn) *pphead = tmp; }
四.5、尾刪法
尾刪法也涉及到許多細(xì)節(jié)，大家也需要仔細(xì)思考；
因?yàn)槲覀兪褂玫氖遣粠诒念^指針，就會(huì)涉及改變結(jié)構(gòu)體和改變結(jié)構(gòu)體指針的問題；
只要記?。?/p>
改變next和data域就是改變結(jié)構(gòu)體，只需要使用結(jié)構(gòu)體指針；
改變頭指針就是改變結(jié)構(gòu)體指針，這時(shí)需要結(jié)構(gòu)體二級(jí)指針；
尾刪法分為三中=種情況：
①：鏈表為空；
②：鏈表里面只有一個(gè)結(jié)點(diǎn)；
③：鏈表里面有兩個(gè)或兩個(gè)以上的結(jié)點(diǎn);
具體細(xì)節(jié)看注釋：
源代碼如下：//頭刪法 //形參是結(jié)構(gòu)體二級(jí)指針，因?yàn)榉譃閹追N情況，有一種情況會(huì)改變結(jié)構(gòu)體指針 void SLTPopBack(SLTNode** pphead) { //情況一：鏈表為空則提示刪除失敗 if (*pphead == NULL) { printf("此鏈表為空，無法刪除!\n"); return; } //情況二：只有一個(gè)結(jié)點(diǎn)，此時(shí)需要使用頭指針，所以要用到二級(jí)指針 //直接用free釋放掉頭指針即可，因?yàn)槲覀冇玫氖遣粠诒念^指針，頭指針指向的就是首元素 //又因?yàn)橹挥幸粋€(gè)元素，所以直接釋放頭指針，在將頭指針置空即可 // if((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { //情況三：有兩個(gè)及其以上的結(jié)點(diǎn)：步驟如下： //①：定位到尾結(jié)點(diǎn)； //②：釋放尾結(jié)點(diǎn)； //將尾結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的next域置空(所以一定要保存前一結(jié)點(diǎn)的地址) //同理先將鏈表內(nèi)容拷貝到臨時(shí)指針中進(jìn)行操作,因?yàn)槲覀儾僮鞯氖墙Y(jié)構(gòu)體，所以用結(jié)構(gòu)體指針即可實(shí)現(xiàn) SLTNode* tmp = *pphead; //如果tmp->next->next為NULL，說明tmp->next就是尾結(jié)點(diǎn)，tmp就是尾結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，所以就可以進(jìn)行釋放了 while (tmp->next->next) { tmp = tmp->next; } free(tmp->next); tmp->next = NULL; } }
四.6、頭刪法
頭刪法比較簡單，但因?yàn)槭窃陬^部操作，所以每一步都是在改變結(jié)構(gòu)體指針（即頭指針），所以每一步都要用結(jié)構(gòu)體二級(jí)指針，所以形參是結(jié)構(gòu)體二級(jí)指針；
頭刪法只有兩種情況：
①：鏈表為空，與尾刪一樣；
②：鏈表不為空；這里沒有區(qū)分一個(gè)結(jié)點(diǎn)和多個(gè)結(jié)點(diǎn)是因?yàn)槲覀兠恳徊蕉家玫浇Y(jié)構(gòu)體二級(jí)指針，所以兩者操作是一樣的；
具體細(xì)節(jié)即源代碼如下：
//頭刪法 //參數(shù)同尾刪一樣，會(huì)改變結(jié)構(gòu)體指針，所以用結(jié)構(gòu)體二級(jí)指針 void SLTPopFront(SLTNode** pphead) { //情況一：鏈表為空，同尾刪一樣 if (*pphead == NULL) { printf("此鏈表為空，無法刪除!\n"); return; } //情況二：鏈表不為空 //①：先將第二個(gè)結(jié)點(diǎn)的地址（即(*pphead->next))保存到臨時(shí)指針 //②：再釋放頭指針（即釋放首元素) //③：再將存放第二個(gè)結(jié)點(diǎn)地址的臨時(shí)指針賦給頭指針*pphead SLTNode* nextnode = (*pphead)->next; free(*pphead); *pphead = nextnode; }
四.7、查找指定結(jié)點(diǎn)
這個(gè)操作很簡單，只需遍歷鏈表即可；
//尋找結(jié)點(diǎn) //參數(shù)一用了結(jié)構(gòu)體指針，因?yàn)椴恍枰淖兘Y(jié)構(gòu)體指針，只需要遍歷鏈表，所以不需要結(jié)構(gòu)體二級(jí)指針 //參數(shù)二是我們要找的數(shù)據(jù)x SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { //同理習(xí)慣用一個(gè)臨時(shí)指針來進(jìn)行操作 SLTNode* tmp = phead; //用循環(huán)遍歷鏈表，同時(shí)比較數(shù)據(jù)域是否等于x，若相等則返回tmp結(jié)點(diǎn)，若 沒找到。則返回空 while (tmp) { if (tmp->data == x) { return tmp; } tmp = tmp->next; } //沒找到返回NULL return NULL; }
四.8、在pos結(jié)點(diǎn)之前插入結(jié)點(diǎn)
有三種情況：
情況一：鏈表為空；
情況二：鏈表中只有一個(gè)結(jié)點(diǎn)；
情況三：鏈表中有多個(gè)結(jié)點(diǎn)。
具體解釋看注釋：
//在pos結(jié)點(diǎn)之前插入x //參數(shù)一是結(jié)構(gòu)體二級(jí)指針 //參數(shù)二是pos位置 //參數(shù)三是要插入的數(shù)據(jù) void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { //情況一、鏈表為空表 if (*pphead == NULL) { printf("此鏈表為空，插入失??！\n"); return; } //情況二、鏈表中只有一個(gè)結(jié)點(diǎn) if (*pphead == pos) { //即為頭插，直接調(diào)用頭插函數(shù),所以會(huì)改變頭指針，所以要用結(jié)構(gòu)體二級(jí)指針 SLTPushFront(pphead, x); } //情況二、鏈表中有多個(gè)結(jié)點(diǎn) else { //臨時(shí)指針 SLTNode* tmp = *pphead; //找到pos結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn) while (tmp->next == pos) { //得到一個(gè)新結(jié)點(diǎn) SLTNode* newnode = BuySLiseNode(x); //開始插入 newnode->next = pos; tmp->next = newnode; } } }
四.8、在pos結(jié)點(diǎn)之后插入結(jié)點(diǎn)
這種情況就比四.7簡單多了，因?yàn)槲覀兪窃诮Y(jié)點(diǎn)的后面插入，所以不涉及頭插（即不用結(jié)構(gòu)體二級(jí)指針），也不用循環(huán)找什么結(jié)點(diǎn)，直接插即可；
情況一、鏈表為空；
情況二、鏈表不為空，因?yàn)槲覀兪窃诮Y(jié)點(diǎn)之后插入，所以不涉及改變頭指針（不涉及頭插）。所以用結(jié)構(gòu)體指針就能達(dá)到目的；
如下：
//在pos結(jié)點(diǎn)之后插入新結(jié)點(diǎn) void SLTInsertAfter(SLTNode* phead, SLTNode* pos, SLTDataType x) { //情況一、鏈表為空表 if (phead == NULL) { printf("此鏈表為空，插入失敗！\n"); return; } //情況二、鏈表不為空 //得到一個(gè)新結(jié)點(diǎn) SLTNode* newnode = BuySLiseNode(x); //開始插入 newnode->next = pos->next; pos->next = newnode; }
四.9、刪除pos位置的結(jié)點(diǎn)
有三種情況：
情況一、鏈表為空；
情況二、鏈表只有一個(gè)結(jié)點(diǎn)（頭刪法）；
情況三、鏈表有多個(gè)結(jié)點(diǎn)；
如下：
?文章來源：http://www.zghlxwxcb.cn/news/detail-718116.html//刪除pos位置的結(jié)點(diǎn) void SLTErace(SLTNode** pphead, SLTNode* pos) { //情況一、鏈表為空表 if (*pphead == NULL) { printf("此鏈表為空，刪除失??！\n"); return; } //情況二、鏈表中只有一個(gè)結(jié)點(diǎn)（頭刪） if (*pphead == pos) { SLTPopFront(pphead); } //情況三、鏈表中有多個(gè)結(jié)點(diǎn) else { //臨時(shí)指針 SLTNode* tmp = *pphead; //找到指針結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn) while (tmp->next != pos) { tmp = tmp->next; } //開始刪除 tmp->next = pos->next; free(pos); pos = NULL; } }
五、測(cè)試源代碼
main.c:
#include"Slist.h" 測(cè)試函數(shù) //void TestSLTist1() //{ // int n = 0; // printf("請(qǐng)輸入鏈表長度;>\n"); // scanf("%d", &n); // printf("請(qǐng)輸入每個(gè)結(jié)點(diǎn)的值"); // SLTNode* phead = NULL;//頭結(jié)點(diǎn),用于鏈接新結(jié)點(diǎn) // int i = 0; // for (i = 0; i < n; i++) // { // SLTDataType val; // scanf("%d", &val); // //獲取新結(jié)點(diǎn) // SLTNode* newnode = BuySLiseNode(val); // //一個(gè)個(gè)結(jié)點(diǎn)有了，我們還需要將其串起來 // //即鏈接新結(jié)點(diǎn) // if (phead == NULL) // { // phead = newnode; // } // else // { // //頭插(這種方法不用考慮剛開始鏈表是否為空) // newnode->next = phead; // phead = newnode; // } // } // //打印鏈表 // SLTPrint(phead); // //} void TestList2() { SLTNode* phead = NULL;//頭結(jié)點(diǎn),用于鏈接新結(jié)點(diǎn) //尾插100、200、300 SLTPushBack(&phead, 100); SLTPushBack(&phead, 200); SLTPushBack(&phead, 300); //打印 SLTPrint(phead); //頭插10/20/30 SLTPushFront(&phead, 10); SLTPushFront(&phead, 20); SLTPushFront(&phead, 30); //打印 SLTPrint(phead); //尾刪兩個(gè)元素； SLTPopBack(&phead); SLTPopBack(&phead); //打印 SLTPrint(phead); //頭刪兩個(gè)元素 SLTPopFront(&phead); SLTPopFront(&phead); //打印 SLTPrint(phead); // 100之前插入300 SLTNode* pos = SLTFind(phead,100); SLTInsert(&phead, pos, 300); //100之后插入1000 SLTInsertAfter(phead, pos, 1000); //打印 SLTPrint(phead); //刪除300和1000位置的結(jié)點(diǎn) SLTNode* pos1 = SLTFind(phead, 300); SLTNode* pos2 = SLTFind(phead, 1000); SLTErace(&phead, pos1); SLTErace(&phead, pos2); //打印 SLTPrint(phead); } int main() { //測(cè)試 // TestSLTist1(); TestList2(); return 0; }SList.c:
#include"Slist.h" //創(chuàng)建新結(jié)點(diǎn) //因?yàn)橐祷貏?dòng)態(tài)申請(qǐng)的結(jié)點(diǎn)，所以有返回類型 SLTNode* BuySLiseNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); //判斷是否開辟成功 if (newnode == NULL) { perror("malloc"); exit(-1); } //填充數(shù)據(jù) newnode->data = x; newnode->next = NULL; //返回 return newnode; } //遍歷單鏈表 void SLTPrint(SLTNode* phead) { //一般頭指針phead我們都不會(huì)動(dòng)，方便我們多操作 //所以我們可以創(chuàng)建一個(gè)臨時(shí)指針來進(jìn)行操作 SLTNode* tmp = phead; //因?yàn)閱捂湵砦步Y(jié)點(diǎn)的指針域?yàn)镹ULL，所以循環(huán)條件可以為tmp //當(dāng)tmp為NULL時(shí)，說明鏈表遍歷完成，并且退出循環(huán) while (tmp) { //打印數(shù)據(jù)域（打印"->"只是方便展示鏈表結(jié)構(gòu)) printf("%d->", tmp->data); //因?yàn)橹羔樣蛑赶蛳乱粋€(gè)結(jié)點(diǎn)，所以可以通過賦值方法找到下一個(gè)結(jié)點(diǎn) tmp = tmp->next; } //方便展示鏈表結(jié)構(gòu)，所以末尾打印一個(gè)NULL printf("NULL\n"); } //尾插法 //函數(shù)第一個(gè)形參是二級(jí)指針，是存儲(chǔ)鏈表的地址，用的傳址調(diào)用 //函數(shù)第二個(gè)形參是要插入的數(shù)據(jù) void SLTPushBack(SLTNode** pphead1, SLTDataType x) { //得到一個(gè)新結(jié)點(diǎn) SLTNode* newnode = BuySLiseNode(x); //若鏈表為空鏈表，則直接將新結(jié)點(diǎn)賦值給鏈表，因?yàn)槲覀兪莻髦氛{(diào)用，可以改變外面鏈表的內(nèi)容 if (*pphead1 == NULL) { *pphead1 = newnode; } else { //同理將鏈表拷貝到一個(gè)臨時(shí)結(jié)點(diǎn)中便于操作 SLTNode* tmp = *pphead1; //①：找到尾結(jié)點(diǎn) //因?yàn)槲步Y(jié)點(diǎn)的next域?yàn)镹ULL，所以可以作為循環(huán)判斷條件 while (tmp->next != NULL) { tmp = tmp->next; } //②：鏈接 tmp->next = newnode; //這里可能有的小伙伴不理解，"覺得這里不也是直接賦值嗎，怎么改變外部鏈表的"? //所以大家就要注意一句話，如下： //1.改變結(jié)構(gòu)體，用結(jié)構(gòu)體指針 //2.改變結(jié)構(gòu)體指針，要用結(jié)構(gòu)體指針的指針（二級(jí)指針） // //上面的pphead就是一個(gè)結(jié)構(gòu)體二級(jí)指針，用于改變結(jié)構(gòu)體指針 //但這里的next是結(jié)構(gòu)體成員，所以我們只需要改變結(jié)構(gòu)體，所以就用結(jié)構(gòu)體指針 //而tmp本來就是我們結(jié)構(gòu)頭指針拷貝過來的，所以改變了tmp的next就相當(dāng)于改變了外部鏈表的尾結(jié)點(diǎn)的next } //因?yàn)閠mp、newnode這些都是局部變量，函數(shù)結(jié)束后會(huì)自動(dòng)銷毀 //第二次又會(huì)從初始位置開始操作，所以我們不用調(diào)整這些變量的值 //但鏈表結(jié)點(diǎn)內(nèi)容不會(huì)被銷毀，因?yàn)槲覀兪怯胢alloc函數(shù)在堆區(qū)上面申請(qǐng)的空間，只有free后才會(huì)銷毀 } //頭插法 //形參和尾插法是相同的道理 void SLTPushFront(SLTNode** pphead, SLTDataType x) { //因?yàn)槲覀兠恳徊蕉家褂貌粠诒念^結(jié)點(diǎn)，所以每次都要改變結(jié)構(gòu)體指針 // 所以形參用二級(jí)指針是必須的，并且不用區(qū)分鏈表是否為空 //先得到一個(gè)新結(jié)點(diǎn) SLTNode* tmp = BuySLiseNode(x); //①：新結(jié)點(diǎn)的next域指向首結(jié)點(diǎn) tmp->next = *pphead; //②：頭結(jié)點(diǎn)指向新結(jié)點(diǎn) *pphead = tmp; } //頭刪法 //形參是結(jié)構(gòu)體二級(jí)指針，因?yàn)榉譃閹追N情況，有一種情況會(huì)改變結(jié)構(gòu)體指針 void SLTPopBack(SLTNode** pphead) { //情況一：鏈表為空則提示刪除失敗 if (*pphead == NULL) { printf("此鏈表為空，無法刪除!\n"); return; } //情況二：只有一個(gè)結(jié)點(diǎn)，此時(shí)需要使用頭指針，所以要用到二級(jí)指針 //直接用free釋放掉頭指針即可，因?yàn)槲覀冇玫氖遣粠诒念^指針，頭指針指向的就是首元素 //又因?yàn)橹挥幸粋€(gè)元素，所以直接釋放頭指針，在將頭指針置空即可 // if((*pphead)->next == NULL) { free(*pphead); *pphead = NULL; } else { //情況三：有兩個(gè)及其以上的結(jié)點(diǎn)：步驟如下： //①：定位到尾結(jié)點(diǎn)； //②：釋放尾結(jié)點(diǎn)； //將尾結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的next域置空(所以一定要保存前一結(jié)點(diǎn)的地址) //同理先將鏈表內(nèi)容拷貝到臨時(shí)指針中進(jìn)行操作,因?yàn)槲覀儾僮鞯氖墙Y(jié)構(gòu)體，所以用結(jié)構(gòu)體指針即可實(shí)現(xiàn) SLTNode* tmp = *pphead; //如果tmp->next->next為NULL，說明tmp->next就是尾結(jié)點(diǎn)，tmp就是尾結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，所以就可以進(jìn)行釋放了 while (tmp->next->next) { tmp = tmp->next; } free(tmp->next); tmp->next = NULL; } } //頭刪法 //參數(shù)同尾刪一樣，會(huì)改變結(jié)構(gòu)體指針，所以用結(jié)構(gòu)體二級(jí)指針 void SLTPopFront(SLTNode** pphead) { //情況一：鏈表為空，同尾刪一樣 if (*pphead == NULL) { printf("此鏈表為空，無法刪除!\n"); return; } //情況二：鏈表不為空 //①：先將第二個(gè)結(jié)點(diǎn)的地址（即(*pphead->next))保存到臨時(shí)指針 //②：再釋放頭指針（即釋放首元素) //③：再將存放第二個(gè)結(jié)點(diǎn)地址的臨時(shí)指針賦給頭指針*pphead SLTNode* nextnode = (*pphead)->next; free(*pphead); *pphead = nextnode; } //尋找結(jié)點(diǎn) //參數(shù)一用了結(jié)構(gòu)體指針，因?yàn)椴恍枰淖兘Y(jié)構(gòu)體指針，只需要遍歷鏈表，所以不需要結(jié)構(gòu)體二級(jí)指針 //參數(shù)二是我們要找的數(shù)據(jù)x SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { //同理習(xí)慣用一個(gè)臨時(shí)指針來進(jìn)行操作 SLTNode* tmp = phead; //用循環(huán)遍歷鏈表，同時(shí)比較數(shù)據(jù)域是否等于x，若相等則返回tmp結(jié)點(diǎn)，若 沒找到。則返回空 while (tmp) { if (tmp->data == x) { return tmp; } tmp = tmp->next; } //沒找到返回NULL return NULL; } //在pos結(jié)點(diǎn)之前插入x //參數(shù)一是結(jié)構(gòu)體二級(jí)指針 //參數(shù)二是pos位置 //參數(shù)三是要插入的數(shù)據(jù) void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { //情況一、鏈表為空表 if (*pphead == NULL) { printf("此鏈表為空，插入失?。n"); return; } //情況二、鏈表中只有一個(gè)結(jié)點(diǎn) if (*pphead == pos) { //即為頭插，直接調(diào)用頭插函數(shù),所以會(huì)改變頭指針，所以要用結(jié)構(gòu)體二級(jí)指針 SLTPushFront(pphead, x); } //情況二、鏈表中有多個(gè)結(jié)點(diǎn) else { //臨時(shí)指針 SLTNode* tmp = *pphead; while (tmp->next == pos) { //得到一個(gè)新結(jié)點(diǎn) SLTNode* newnode = BuySLiseNode(x); //開始插入 newnode->next = pos; tmp->next = newnode; } } } //在pos結(jié)點(diǎn)之后插入新結(jié)點(diǎn) void SLTInsertAfter(SLTNode* phead, SLTNode* pos, SLTDataType x) { //情況一、鏈表為空表 if (phead == NULL) { printf("此鏈表為空，插入失??！\n"); return; } //情況二、鏈表不為空 //得到一個(gè)新結(jié)點(diǎn) SLTNode* newnode = BuySLiseNode(x); //直接開始插入 newnode->next = pos->next; pos->next = newnode; } //刪除pos位置的結(jié)點(diǎn) void SLTErace(SLTNode** pphead, SLTNode* pos) { //情況一、鏈表為空表 if (*pphead == NULL) { printf("此鏈表為空，刪除失??！\n"); return; } //情況二、鏈表中只有一個(gè)結(jié)點(diǎn)（頭刪） if (*pphead == pos) { SLTPopFront(pphead); } //情況三、鏈表中有多個(gè)結(jié)點(diǎn) else { //臨時(shí)指針 SLTNode* tmp = *pphead; //找到指針結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn) while (tmp->next != pos) { tmp = tmp->next; } //開始刪除 tmp->next = pos->next; free(pos); pos = NULL; } }SList.h:
?#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include<stdlib.h> #include<string.h> typedef int SLTDataType;//方便以后跟改數(shù)據(jù)類型 typedef struct SListNode { SLTDataType data;//數(shù)據(jù)域 struct SListNode* next;//指針域 }SLTNode, * LinkList;//用typedef重定義后，Londe為結(jié)點(diǎn)類型,LinkList為指向結(jié)點(diǎn)的指針類型 //遍歷單鏈表 void SLTPrint(SLTNode* phead); //創(chuàng)建新結(jié)點(diǎn) SLTNode* BuySLiseNode(SLTDataType x); //尾插法 void SLTPushBack(SLTNode** pphead1, SLTDataType x); //頭插法 void SLTPushFront(SLTNode** pphead, SLTDataType x); //尾刪法 void SLTPopBack(SLTNode** pphead); //頭刪法 void SLTPopFront(SLTNode** pphead); //尋找結(jié)點(diǎn) SLTNode* SLTFind(SLTNode* phead, SLTDataType x); //在pos結(jié)點(diǎn)之前插入新結(jié)點(diǎn) void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //在pos結(jié)點(diǎn)之后插入新結(jié)點(diǎn) void SLTInsertAfter(SLTNode* phead, SLTNode* pos, SLTDataType x); //刪除pos位置的結(jié)點(diǎn) void SLTErace(SLTNode** pphead, SLTNode* pos);
本次知識(shí)到此結(jié)束，希望對(duì)你有所幫助！文章來源地址http://www.zghlxwxcb.cn/news/detail-718116.html
到了這里，關(guān)于線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
