接上節(jié)：C/C++編程筆記：如何使用C++實現(xiàn)單鏈表？單鏈表第一部分。

單鏈表上的基本運算實現(xiàn)

(四) 求表長

由于我們的代碼中已經(jīng)定義過一個叫做 curLength 的變量用來記錄我們的表長

所以我們可以直接返回，我們在定義中已經(jīng)實現(xiàn)了，也就是這句：

????????int size()const {return curLength;}//返回單鏈表的當前實際長度

但是如果我們沒有這樣一個變量，我們想要實現(xiàn)這樣的功能又是什么樣的方法呢？

(五) 遍歷單鏈表

我們需要從頭到尾訪問單鏈表中的每一個節(jié)點，并且輸出其中數(shù)據(jù)域的信息。

(六) 按照位序 i 尋找其元素對應內(nèi)存地址

設置一個移動工作指針，和一個計數(shù)器 count，初始時p指向頭結(jié)點，每當指針p移向下一個結(jié)點的時候，計數(shù)器count + 1 ，直到 p指向位序為 i的節(jié)點為止。返回 p。

(七) 按值查詢節(jié)點位序

設置一個移動工作指針，和一個計數(shù)器 count，從單鏈表的第一個節(jié)點開始，開始于給定的值進行比對，如果相等則查找成功，返回節(jié)點的位序，否則繼續(xù)查詢知道單鏈表結(jié)束，查詢失敗返回 -1。

(八) 插入節(jié)點

在位序為 i 出插入值為value 的新節(jié)點q，我們需要做的就是找到位序為i - 1 的節(jié)點p，讓q指針域指向原來p的后繼，然后修改p的后繼為q即可，說白了也就是修改插入元素位置前后的元素指向關系就可以了。

(九) 刪除節(jié)點

能看懂添加節(jié)點的方法，理解刪除節(jié)點也是手到擒來。

單鏈表整表的創(chuàng)建

回顧我們前面認識的順序表，它其實可以理解為一個數(shù)組，我們聲明一個類型，同時給定值，初始化其大小，但是單鏈表就不一樣了，它是一種動態(tài)組織，它不需要像順序表一樣元素集中，它可以隨著實際的情況來動態(tài)生成節(jié)點，所以也不需要預先分配空間大小和位置。

(一) 頭插法創(chuàng)建單鏈表

頭插法的意思就是說，每次新增節(jié)點全部插在頭結(jié)點之后，首元結(jié)點之前，你可以這樣理解，我先來排隊，但是后面來了人，他就會排到我的前面去，我們來借助圖看一下：

我們一次插入元素 123 但實際上輸出的是按照321的順序存儲的，也就是說和我們的邏輯順序是相反的。

我們來看一看怎么實現(xiàn)它：

逆置單鏈表

我們知道單鏈表中元素順序與讀入的順序是相反的，我們可以通過逆置單鏈表的算法，幫助我們重新恢復我們的慣有思維順序。

(二) 尾插法創(chuàng)建單鏈表

看完了頭插法，但是感覺這樣的順序與我們一貫的思維總是有一點別扭，而尾插法則是一種，邏輯順序與我們一致的創(chuàng)建方法。

還是看一下圖：

合并單鏈表

要求：假設我們給出兩個仍然是遞增的單鏈表la和lb，我們將其合并為lc 仍保證遞增，利用原表空間，但是我們?nèi)栽谙旅鎸⒈鞢稱作新表。

因為我們的要求是遞增的，所以使用尾插法是非常合適的，我們設計三個工作指針，分別指向兩個表的首元結(jié)點，然后將第三個指針指向新表的頭結(jié)點，比較前兩個指針指向的值，小的就放到新表的表尾，然后后移動兩表中較小的那一個的指針，以此類推，直到其中一個表尾空，將剩余的節(jié)點全部鏈接到新表的末尾。

總結(jié)

單鏈表，采取了鏈式存儲結(jié)構(gòu)，用一組任意的存儲單元存放線性表的元素，尤其對于需要頻繁的插入和刪除數(shù)據(jù)的時候更加適用，如果需要進行頻繁的查找還是推薦使用順序表，例如對于一個學生成績管理系統(tǒng)的制作，學生更多的時候是查看自己的成績，而錄入的老師，也只有在考試后錄入一次，所以應該使用順序表，而例如考勤打卡系統(tǒng)，更多的是打卡信息的記錄，所以還是選擇使用鏈表，當然例子可能不是很恰當，同時正常的開發(fā)中還會有更多復雜的問題需要考慮，舉例子只為了利于理解。

另外，UP在主頁上傳了一些學習C/C++編程的視頻教程，有興趣或者正在學習的小伙伴一定要去看一看哦！會對你有幫助的~