柚子快報(bào)激活碼778899分享：筆記 C語(yǔ)言—單鏈表

http://yzkb.51969.com/

目錄

一、鏈表的概念及結(jié)構(gòu)

二、單鏈表實(shí)現(xiàn)

（2.1）基本結(jié)構(gòu)定義

（2.2）申請(qǐng)節(jié)點(diǎn)

（2.3）打印函數(shù)

（2.4）頭部插入刪除\尾部插入刪除

（2.4.1）尾部插入

（2.4.2）頭部插入

（2.4.3）尾部刪除

（2.4.4）頭部刪除

（2.5）查找

（2.6）在指定位置之前插入數(shù)據(jù)

（2.7）刪除pos節(jié)點(diǎn)

（2.8）在指定位置之后插入數(shù)據(jù)

（2.9）刪除pos之后的節(jié)點(diǎn)

（2.10）銷毀鏈表

三、鏈表的分類

一、鏈表的概念及結(jié)構(gòu)

概念：鏈表是?種物理存儲(chǔ)結(jié)構(gòu)上?連續(xù)、?順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。

鏈表的結(jié)構(gòu)跟???廂相似，如圖所示：

與順序表不同的是，鏈表?的每節(jié)"?廂"都是獨(dú)?申請(qǐng)下來(lái)的空間，我們稱之為“結(jié)點(diǎn)/節(jié)點(diǎn)”。節(jié)點(diǎn)的組成主要有兩個(gè)部分：當(dāng)前節(jié)點(diǎn)要保存的數(shù)據(jù)和保存下?個(gè)節(jié)點(diǎn)的地址（指針變量）。圖中指針變量 plist 保存的是第?個(gè)節(jié)點(diǎn)的地址，我們一般稱之為頭指針。鏈表中每個(gè)節(jié)點(diǎn)都是獨(dú)?申請(qǐng)的（即需要插?數(shù)據(jù)時(shí)才去申請(qǐng)?塊節(jié)點(diǎn)的空間），所以我們需要通過(guò)指針變量來(lái)保存下?個(gè)節(jié)點(diǎn)位置才能從當(dāng)前節(jié)點(diǎn)找到下?個(gè)節(jié)點(diǎn)。

補(bǔ)充說(shuō)明： 1、鏈?zhǔn)綑C(jī)構(gòu)在邏輯上是連續(xù)的，在物理結(jié)構(gòu)上不?定連續(xù) 2、節(jié)點(diǎn)?般是從堆上申請(qǐng)的 3、從堆上申請(qǐng)來(lái)的空間，是按照?定策略分配出來(lái)的，每次申請(qǐng)的空間可能連續(xù)，可能不連續(xù)

二、單鏈表實(shí)現(xiàn)

注意：這里的單鏈表指的是不帶頭單向不循環(huán)鏈表（后面會(huì)介紹鏈表的分類）

（2.1）基本結(jié)構(gòu)定義

為了單鏈表的復(fù)用性，這里將 int 重命名為SLTDataType，單鏈表節(jié)點(diǎn)中包含一個(gè)數(shù)據(jù)域（data）,一個(gè)指針域（next）,數(shù)據(jù)域存放需要存放的數(shù)據(jù)，指針域存放下一個(gè)節(jié)點(diǎn)的地址。這里為了方便后續(xù)使用又將struct SListNode 重命名為SLTNode。

（2.2）申請(qǐng)節(jié)點(diǎn)

后續(xù)插入節(jié)點(diǎn)的函數(shù)都需要先申請(qǐng)節(jié)點(diǎn)，所以這里直接寫(xiě)一個(gè)申請(qǐng)節(jié)點(diǎn)的函數(shù)，方便后面使用，在該函數(shù)中，首先用malloc申請(qǐng)一塊節(jié)點(diǎn)大小的空間，然后判斷是否申請(qǐng)成功，如果申請(qǐng)失敗，用perror函數(shù)報(bào)錯(cuò)，然后結(jié)束程序，如果申請(qǐng)成功，將數(shù)據(jù)插入，并將指針域置空，然后返回節(jié)點(diǎn)地址。（形參是要插入的數(shù)據(jù)）

（2.3）打印函數(shù)

為了后續(xù)測(cè)試中方便查看單鏈表中的數(shù)據(jù)，我們這里實(shí)現(xiàn)一個(gè)打印函數(shù)，功能是打印單鏈表中的所有數(shù)據(jù)。

具體實(shí)現(xiàn)：

解釋：形參是指向整個(gè)單鏈表頭部的指針，要打印單鏈表中的數(shù)據(jù)，首先單鏈表不能為空，如果是空表沒(méi)有數(shù)據(jù)可打印，所以先斷言頭指針不為空，然后定義一個(gè)臨時(shí)變量 cur 記錄鏈表頭部的地址（即將頭指針賦給cur），然后以 cur 作為循環(huán)條件，每次進(jìn)入循環(huán)，打印當(dāng)前節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)，打印后將指針向后移動(dòng)，當(dāng)打印完最后一個(gè)節(jié)點(diǎn)數(shù)據(jù)后，指針移動(dòng)到NULL，循環(huán)結(jié)束。最后可以再打印一個(gè)換行。

（2.4）頭部插入刪除\尾部插入刪除

（2.4.1）尾部插入

具體實(shí)現(xiàn)：

思路：遍歷找到尾節(jié)點(diǎn)，然后將新節(jié)點(diǎn)連接上，如果鏈表為空，直接將新節(jié)點(diǎn)作為頭。

解釋：該函數(shù)中有兩個(gè)形參，一個(gè)是二級(jí)指針，指向單鏈表的頭指針，一個(gè)是要插入的數(shù)據(jù)，首先這里的二級(jí)指針一定不可以為空，如果二級(jí)指針為空，我們將無(wú)法找到鏈表，所以先斷言二級(jí)指針不為空，然后判斷當(dāng)前鏈表是否為空，如果鏈表為空，直接將新申請(qǐng)的節(jié)點(diǎn)置為表頭（即直接讓頭指針指向該節(jié)點(diǎn)，注意這里的pphead是二級(jí)指針，要先解引用才是頭指針），如果鏈表不為空，先定義一個(gè)臨時(shí)指針指向鏈表頭部，然后當(dāng) cur 的 next 不為空的時(shí)候進(jìn)行循環(huán)，出循環(huán)時(shí)?cur 一定指向尾節(jié)點(diǎn)，因?yàn)殒湵碇忻總€(gè)節(jié)點(diǎn)（除尾節(jié)點(diǎn)）中的指針域存的都是下一個(gè)節(jié)點(diǎn)的地址，而最后一個(gè)節(jié)點(diǎn)后面已經(jīng)沒(méi)有節(jié)點(diǎn)了，所以它的指針域存的是NULL，而循環(huán)結(jié)束的條件就是 cur 指針域?yàn)镹ULL。找到尾節(jié)點(diǎn)后，將新申請(qǐng)的節(jié)點(diǎn)插入即可。

圖解：

測(cè)試：

（2.4.2）頭部插入

具體實(shí)現(xiàn)：

思路：將新節(jié)點(diǎn)插在原鏈表的頭的前面，并作為新的頭。

解釋：該函數(shù)中有兩個(gè)形參，一個(gè)是二級(jí)指針，指向單鏈表的頭指針，一個(gè)是要插入的數(shù)據(jù)，首先這里的二級(jí)指針一定不可以為空，如果二級(jí)指針為空，我們將無(wú)法找到鏈表，所以先斷言二級(jí)指針不為空，然后直接申請(qǐng)新節(jié)點(diǎn)，新節(jié)點(diǎn)的指針域存原鏈表的頭，然后將新節(jié)點(diǎn)賦給頭指針，這樣新節(jié)點(diǎn)就插入到原鏈表的頭部了并且成為新鏈表的頭。

圖解：

測(cè)試：

（2.4.3）尾部刪除

具體實(shí)現(xiàn)：

思路：遍歷找到尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，釋放尾節(jié)點(diǎn)，然后將尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)指針域置空，如果鏈表只有一個(gè)節(jié)點(diǎn)，直接釋放就行，但是要將頭指針置空。

解釋：該函數(shù)只有一個(gè)參數(shù)，即指向頭指針的二級(jí)指針，這里和上面一樣二級(jí)指針一定不可以為空，又因?yàn)槭莿h除，鏈表一定要存在，所以頭指針也不可以為空，所以先斷言這兩個(gè)指針不為空，尾刪分為兩種情況，當(dāng)鏈表只有一個(gè)節(jié)點(diǎn)時(shí)，刪除后鏈表為空，這時(shí)要將頭指針置空，當(dāng)鏈表不止一個(gè)節(jié)點(diǎn)時(shí)，通過(guò)循環(huán)找到尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，然后釋放最后一個(gè)節(jié)點(diǎn)，因?yàn)槲补?jié)點(diǎn)已經(jīng)被釋放了（即將空間還給操作系統(tǒng)了），所以尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的 next 指針要置空，成為新的尾節(jié)點(diǎn),這里之所以要找尾節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，而不直接找尾節(jié)點(diǎn)也是因?yàn)?next 指針置空的問(wèn)題，如果直接找尾節(jié)點(diǎn)，因?yàn)槭菃捂湵?，無(wú)法獲得它的前驅(qū)節(jié)點(diǎn)，想要將前驅(qū)節(jié)點(diǎn)的 next 指針置空就會(huì)變麻煩。

圖解：

測(cè)試：

（2.4.4）頭部刪除

具體實(shí)現(xiàn)：

解釋：該函數(shù)只有一個(gè)參數(shù)，即指向頭指針的二級(jí)指針，和前面一樣，二級(jí)指針一定不可以為空，又因?yàn)樵摵瘮?shù)的功能是刪除，所以鏈表不可以為空，即頭指針不可以為空，所以先斷言這兩個(gè)指針不為空，然后定義一個(gè)臨時(shí)指針變量記錄頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的地址，釋放當(dāng)前頭節(jié)點(diǎn)，將記錄的后一個(gè)節(jié)點(diǎn)變?yōu)樾碌念^節(jié)點(diǎn)，這里一定要先去記錄后一個(gè)節(jié)點(diǎn)的位置，否則釋放后就找不到了。如果當(dāng)前鏈表只有一個(gè)節(jié)點(diǎn)也沒(méi)事，因?yàn)樗闹羔樣蚶锎娴氖荖ULL，釋放頭節(jié)點(diǎn)后就將NULL給了頭指針，這時(shí)鏈表就變?yōu)榭真湵砹恕?/p>

圖解：

測(cè)試：

（2.5）查找

思路：遍歷鏈表，對(duì)比數(shù)據(jù)域，如果相同則找到，返回節(jié)點(diǎn)地址，如果遍歷結(jié)束還沒(méi)有找到，則鏈表中沒(méi)有該數(shù)據(jù)，返回空。

功能：給出鏈表的頭指針和要查找的數(shù)據(jù)，該函數(shù)會(huì)在該鏈表中進(jìn)行查找，如果找到，返回存儲(chǔ)該數(shù)據(jù)的節(jié)點(diǎn)，如果沒(méi)找到，返回NULL。

具體實(shí)現(xiàn)：

解釋：該函數(shù)一共兩個(gè)形參，第一個(gè)是鏈表的頭指針，第二個(gè)是要查找的數(shù)據(jù)，因?yàn)楹竺嬉M(jìn)行遍歷鏈表，而頭指針要始終指向鏈表頭部，不能隨意移動(dòng)，所以先定義一個(gè)臨時(shí)變量記錄頭指針，然后作為循環(huán)條件進(jìn)行遍歷，對(duì)比數(shù)據(jù)，一樣就找到了，返回節(jié)點(diǎn)，結(jié)束函數(shù)，不一樣就向后移動(dòng)，訪問(wèn)下一個(gè)節(jié)點(diǎn)，如果遍歷結(jié)束還沒(méi)有找到說(shuō)明鏈表中沒(méi)有該數(shù)據(jù)，返回NULL。

圖解：

測(cè)試：

（2.6）在指定位置之前插入數(shù)據(jù)

具體實(shí)現(xiàn)：

解釋：該函數(shù)有三個(gè)參數(shù)，第一個(gè)是指向頭指針的二級(jí)指針，第二個(gè)是指定節(jié)點(diǎn)位置（可以配合查找函數(shù)確定），第三個(gè)要存儲(chǔ)的數(shù)據(jù)。二級(jí)指針和前面一樣，還是不可以為空，否則找不到鏈表，指定位置之前插入，其實(shí)就是指定節(jié)點(diǎn)之前插入，所以這個(gè)節(jié)點(diǎn)必須存在，又因?yàn)檫@個(gè)節(jié)點(diǎn)的存在，所以鏈表一定不為空，所以先進(jìn)行這三個(gè)條件的斷言，這里插入分為兩種情況，第一種情況，當(dāng)pos是頭節(jié)點(diǎn)的時(shí)候，在頭節(jié)點(diǎn)之前插節(jié)點(diǎn)，其實(shí)就是前面的頭插法，這里可以調(diào)用前面寫(xiě)好的頭插函數(shù)（SLTPushFront），也可以像我一樣自己寫(xiě)一下，第二種情況，當(dāng)pos不是頭節(jié)點(diǎn)的時(shí)候，我們需要遍歷鏈表，找到pos的前驅(qū)節(jié)點(diǎn)，然后將新節(jié)點(diǎn)插入，因?yàn)檫@是單鏈表，所以我們沒(méi)法通過(guò)pos節(jié)點(diǎn)向前插入節(jié)點(diǎn)，必須找到他的前驅(qū)節(jié)點(diǎn)。

圖解：

（2.7）刪除pos節(jié)點(diǎn)

思路：兩種情況，第一種：要?jiǎng)h除的是頭節(jié)點(diǎn)時(shí)，因?yàn)轭^節(jié)點(diǎn)被刪除，所以頭指針要進(jìn)行移動(dòng)。第二種：刪除的不是頭節(jié)點(diǎn)，頭指針不需要移動(dòng)，如果先刪除pos節(jié)點(diǎn)，我們就沒(méi)有辦法找到pos節(jié)點(diǎn)后面的節(jié)點(diǎn)了，所以先找到pos節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，然后將pos節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)和后面的節(jié)點(diǎn)連接起來(lái)，再去刪除pos節(jié)點(diǎn)。

具體實(shí)現(xiàn)：

（2.8）在指定位置之后插入數(shù)據(jù)

思路：首先想在pos位置之后插入數(shù)據(jù)，pos節(jié)點(diǎn)一定要存在，然后先讓新節(jié)點(diǎn)的指針域存pos節(jié)點(diǎn)后面節(jié)點(diǎn)的地址，然后再讓pos節(jié)點(diǎn)的指針域存新節(jié)點(diǎn)的地址，順序不能顛倒，如果先讓pos節(jié)點(diǎn)指針域存新節(jié)點(diǎn)，那么就無(wú)法找到pos后面的節(jié)點(diǎn)。

具體實(shí)現(xiàn)：

（2.9）刪除pos之后的節(jié)點(diǎn)

思路：刪除pos節(jié)點(diǎn)之后的節(jié)點(diǎn)，pos節(jié)點(diǎn)必須存在，正常情況下，pos后面那個(gè)要?jiǎng)h的節(jié)點(diǎn)也必須存在，所以可以對(duì)這兩個(gè)節(jié)點(diǎn)都斷言一下，這里我用了 if 語(yǔ)句，允許pos后面沒(méi)有節(jié)點(diǎn)，當(dāng)沒(méi)有節(jié)點(diǎn)時(shí)，函數(shù)不會(huì)做任何事，直接結(jié)束，如果有，先將要?jiǎng)h除的節(jié)點(diǎn)記錄下來(lái)，然后將pos和要?jiǎng)h除的節(jié)點(diǎn)的后面的節(jié)點(diǎn)連接起來(lái)，如果前面沒(méi)有記錄要?jiǎng)h除的節(jié)點(diǎn)，這里連接后就找不到要?jiǎng)h除的節(jié)點(diǎn)了。然后釋放要?jiǎng)h除的節(jié)點(diǎn)就可以了。

具體實(shí)現(xiàn)：

（2.10）銷毀鏈表

思路：要找到鏈表，二級(jí)指針不能為空，如果當(dāng)前鏈表已經(jīng)為空了，函數(shù)結(jié)束，不會(huì)做任何事；如果鏈表不為空，定義兩個(gè)指針，一個(gè)記錄當(dāng)前要釋放的節(jié)點(diǎn)，一個(gè)記錄釋放的節(jié)點(diǎn)后面的節(jié)點(diǎn)，因?yàn)獒尫藕缶蜔o(wú)法找到它后面的節(jié)點(diǎn)了，這里先記錄下來(lái)，這樣就可以在刪除節(jié)點(diǎn)后將記錄要釋放節(jié)點(diǎn)的指針移動(dòng)到鏈表的下一個(gè)節(jié)點(diǎn)，然后繼續(xù)釋放，直到循環(huán)到所有節(jié)點(diǎn)都被釋放，這里當(dāng)cur為空時(shí)，已經(jīng)釋放了所有節(jié)點(diǎn)，next 此時(shí)也為空，沒(méi)必要再向后移動(dòng)了，所以用 if 判斷一下。

具體實(shí)現(xiàn)：

三、鏈表的分類

鏈表的結(jié)構(gòu)?常多樣，以下情況組合起來(lái)就有8種（2x2x2）鏈表結(jié)構(gòu)：

雖然有這么多的鏈表的結(jié)構(gòu)，但是我們實(shí)際中最常?還是兩種結(jié)構(gòu)：?jiǎn)捂湵砗碗p向帶頭循環(huán)鏈表。

1.?頭單向?循環(huán)鏈表：結(jié)構(gòu)簡(jiǎn)單，?般不會(huì)單獨(dú)?來(lái)存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的?結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試?試中出現(xiàn)很多。 2.帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，?般?在單獨(dú)存儲(chǔ)數(shù)據(jù)。實(shí)際中使?的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使?代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶來(lái)很多優(yōu)勢(shì)，實(shí)現(xiàn)反?簡(jiǎn)單了。

柚子快報(bào)激活碼778899分享：筆記 C語(yǔ)言—單鏈表

http://yzkb.51969.com/

精彩內(nèi)容