數(shù)據(jù)結(jié)構(gòu)之單鏈表

單鏈表是一種鏈式存取的數(shù)據(jù)結(jié)構(gòu)，用一組地址任意的存儲單元 存放線性表中的數(shù)據(jù)元素 。鏈表中的數(shù)據(jù)是以結(jié)點來表示的，每個結(jié)點的構(gòu)成：元素( 數(shù)據(jù)元素 的映象) + 指針 (指示后繼元素存儲位置)，元素就是存儲數(shù)據(jù)的存儲單元，指針就是連接每個結(jié)點的地址數(shù)據(jù)。

介紹:單鏈表就是結(jié)構(gòu)體變量和結(jié)構(gòu)體變量 通過指針成員連接在一起，故：單鏈表就是多個結(jié)構(gòu)體變量。

鏈表分類

根據(jù)鏈表有無頭結(jié)點，指針是是否雙向，鏈表是否環(huán)狀，我們把鏈表分為以下幾種：

帶頭結(jié)點單鏈表。

無頭結(jié)點單鏈表。

雙向鏈表。

雙向循環(huán)鏈表。

單鏈表操作

帶頭結(jié)點的鏈式結(jié)構(gòu)主要有以下常規(guī)操作:

創(chuàng)建鏈表:創(chuàng)建頭結(jié)點。

創(chuàng)建結(jié)點:為插入做準備。

表頭插入。

表尾插入。

指定位置插入。

表頭刪除。

表尾刪除。

指定位置刪除。

鏈表的打印。

插曲：指針如何當做變量使用？

通過賦值變量的地址。

通過動態(tài)內(nèi)存申請。

代碼如下：

結(jié)構(gòu)體定義

數(shù)據(jù)結(jié)構(gòu)中的結(jié)構(gòu)體設(shè)計， 一般都是單一個體的抽象，即把整個結(jié)構(gòu)拆開的零件。

創(chuàng)建表頭

單鏈表就是結(jié)構(gòu)體變量和結(jié)構(gòu)體變量 通過指針成員連接在一起，故如果定義一個函數(shù)去創(chuàng)建鏈表，其實就是創(chuàng)建表頭，表頭也是一個結(jié)構(gòu)體變量，故就是創(chuàng)建結(jié)構(gòu)體變量的過程，然后數(shù)據(jù)結(jié)構(gòu)一般習慣用指針去表示，指針變成變量，故通過動態(tài)內(nèi)存是申請即可變成變量，最后只需要給變量初始化即可。

單鏈表的創(chuàng)建表頭源碼：

創(chuàng)建節(jié)點

創(chuàng)建結(jié)點單獨用一個函數(shù)封裝，為插入節(jié)點做準備，結(jié)點也是結(jié)構(gòu)體變量，相對于表頭只是多了一個數(shù)據(jù)域，而數(shù)據(jù)可以形參傳進去，這樣就可以實現(xiàn)數(shù)據(jù)加工，加工為一個結(jié)點數(shù)據(jù)。

單鏈表的結(jié)點創(chuàng)建代碼：

表頭法插入

因為是一個有表頭的鏈表，故表頭位置不可改變，插入結(jié)點只能放在表頭后面。表頭就像講臺，學生座位怎么排，都只能放在講臺后面，不能排到講臺前面去。

單鏈表的表頭插入代碼：

表尾插入

表尾插入，首先找到表尾，然后把插入的結(jié)點放到表尾結(jié)點后面即可。

單鏈表的表尾插入代碼：

指定位置插入

只要找到指定位置與指定位置前面哪個結(jié)點，我想每一個同學都應該會插入結(jié)點。指定位置插入問題轉(zhuǎn)換為找到指定位置以及指定位置的前面哪個結(jié)點。

單鏈表的指定位置插入代碼實現(xiàn)：

鏈表遍歷

因為做的是一個有表頭的鏈表 ，故打印數(shù)據(jù)的時候是從第二個節(jié)點開始打印，如果存在數(shù)據(jù)，打印數(shù)據(jù)，打印完后往下一個結(jié)點移動即可。就像公交車一樣，過一站下一批乘客。

單鏈表的遍歷實現(xiàn)：

測試檢驗

首先表頭插入數(shù)據(jù)1，在表頭插入數(shù)據(jù)3 ，鏈表中數(shù)據(jù)為 3 1。

在指定1前面插入2，鏈表中數(shù)據(jù)為3 2 1。

最后表尾插入0，鏈表中數(shù)據(jù)為3 2 1 0。

故打印結(jié)果是3 2 1 0

代碼示例：

另外如果你想更好的提升你的編程能力，學好C語言C++編程！彎道超車，快人一步！

分享（源碼、項目實戰(zhàn)視頻、項目筆記，基礎(chǔ)入門教程）

歡迎轉(zhuǎn)行和學習編程的伙伴，利用更多的資料學習成長比自己琢磨更快哦！

學習C/C++編程知識，提升C/C++編程能力，歡迎關(guān)注UP一起來成長！
另外，UP在主頁上傳了一些學習C/C++編程的視頻教程，有興趣或者正在學習的小伙伴一定要去看一看哦！會對你有幫助的~