單鏈表
image-20200618221439465
image-20200618221516210
什么是單鏈表？
image-20200618221658525
單鏈表的定義
image-20200618221959788
別名
image-20200618222203154
image-20200618222313544
注釋：或者可以理解為指向頭節(jié)點的指針既可以表示整個單鏈表也可以表示頭節(jié)點，為了便于區(qū)分才建議使用 typedef 進(jìn)行重命名，以方便區(qū)別其不同的含義
頭插法建立單鏈表
image-20200619095117732
單鏈表的基本操作
單鏈表的初始化
不帶頭節(jié)點的單鏈表的初始化
image-20200619095400757
帶頭節(jié)點的單鏈表的初始化
image-20200619095545238
兩者區(qū)別是什么？
image-20200619095738329
總結(jié)
image-20200619095821536
插入和刪除
image-20200619104612536
插入
按位序插入（帶頭節(jié)點的單鏈表）
image-20200619105030154
具體實現(xiàn)
分析在表頭插入
image-20200619105401211
分析為什么不能顛倒
image-20200619105451377
分析在表中插入
image-20200619105800111
分析在表尾插入
image-20200619110039686
分析插入位置超出表長
image-20200619110159253
總結(jié)
image-20200619110309541
按位插入（不帶頭節(jié)點）
image-20200619110418752
具體實現(xiàn)
image-20200619110547637
結(jié)論：不帶頭節(jié)點的單鏈表，寫代碼更不方便，除非特別聲明，默認(rèn)推薦使用帶頭節(jié)點的實現(xiàn)方式，還有要注意在考試中帶頭、不帶頭都有可能考察，注意審題。
指定節(jié)點的后插操作
image-20200619111032277
指定節(jié)點的前插操作
通過傳入頭指針實現(xiàn)前插
image-20200619111607840
先進(jìn)行后插，然后交換前后數(shù)據(jù)，以此實現(xiàn)前插
image-20200619111716141
image-20200619111814873
刪除
帶有頭節(jié)點版本
image-20200619111915877
具體實現(xiàn)
image-20200619135048885
刪除指定結(jié)點
image-20200619135226089
如果P是最后一個節(jié)點，咋辦？
只能從表頭表頭依次尋找前驅(qū)，時間復(fù)雜度O(n)
image-20200619135401028
單鏈表的局限性：無法逆向檢索??！
總結(jié)
image-20200619135623242
查找
按位查找(帶頭節(jié)點)
image-20200619152704151
按值查找(帶頭節(jié)點)
image-20200619153147639
求表的長度(帶頭節(jié)點)
image-20200619153411974
總結(jié)
image-20200619153525681
單鏈表的建立方法
image-20200619153742876
PS：找不到對象就娶一個數(shù)據(jù)元素吧！哈哈
尾插法
第一種方法：
image-20200619154012867
問題：時間復(fù)雜度太高！！可以用一個指針記錄最后一個數(shù)據(jù)元素的位置來優(yōu)化時間。
優(yōu)化之后:
image-20200619172815577
頭插法
image-20200619172945304
具體實現(xiàn)：
image-20200619173800669
總結(jié)
image-20200619173925151
