深談連結清單&多線程狀态機

1.連結清單的引入

1.1、從數組的缺陷說起

(1)數組有2個缺陷，一個是數組中所有元素的類型必須一緻；第二個是數組的元素個數必須事先制定并且一旦指定之後不能更改。

(2)如何解決數組的2個缺陷：數組的第一個缺陷靠結構體去解決。結構體允許其中的元素的類型不相同，是以解決了數組的第一個缺陷。是以說結構體是因為數組不能解決某些問題是以才發明的。

(3)如何解決數組的第二個缺陷？我們希望數組的大小能夠實時擴充。譬如我剛開始定了一個元素個數是10，後來程式運作時覺得不夠是以動态擴充為20.普通的數組顯然不行，我們可以對數組進行封裝以達到這種目的；我們還可以使用一個新的資料結構來解決，這個新的資料結構就是連結清單。

總結：幾乎可以這樣了解：連結清單就是一個元素個數可以實時變大/變小的數組。

1.2、大學為什麼都有新校區？

(1)學校初建的時候（類似于變量定義并初始化時），這時候因為旁邊都是荒地而沒有建築，是以學校的校園大小由自己定的；但是學校建立了之後旁邊慢慢的也有了其他建築（類似于這個變量配置設定了之後，記憶體的相鄰區域又配置設定了其他變量與這個變量位址相連），這時候你的校園随着發展感覺不夠用了想要擴充，卻發現鄰居已經住滿了，校園的四周全部都是别人的建築，這時候學校要擴充有2個辦法：第一個是拆遷，第二個是搬遷，第三個是外部擴充。

(2)拆遷基本行不通，因為成本太高了。

(3)搬遷可以行的通。程式中解決數組大小擴充的一個思路就是整體搬遷。具體步驟是：先在另外的空白記憶體處建立一個大的數組，然後把原來的數組中的元素的值整個複制到新數組的頭部，然後再釋放掉原來數組的記憶體空間，并且把新的數組去替代原來的數組。這種可變數組在C語言中不支援，但是在更進階語言如C++、Java等裡面是支援的。

(4)外部擴充的思路是最常見的，基本可以說是最合理的。它的一個思路就是化整為零，在原來的不動的前提下去外部擴充新的分基地。外部擴充在學校的例子中就是新校區；外部擴充在程式設計解決數組問題的點上就是連結清單。

1.3、連結清單是什麼樣的？

(1)顧名思義，連結清單就是用鎖鍊連接配接起來的表。這裡的表指的是一個一個的節點（一個節點就是一個校區），節點中有一些記憶體可以用來存儲資料（是以叫表，表就是資料表）；這裡的鎖鍊指的是連結各個表的方法，C語言中用來連接配接2個表（其實就是2塊記憶體）的方法就是指針。

(2)連結清單是由若幹個節點組成的（連結清單的各個節點結構是完全類似的），節點是由有效資料和指針組成的。有效資料區域用來存儲資訊完成任務的，指針區域用于指向連結清單的下一個節點進而構成連結清單。

1.4、時刻别忘了連結清單是用來幹嘛的

(1)時刻謹記：連結清單就是用來解決數組的大小不能動态擴充的問題，是以連結清單其實就是當數組用的。直白點：連結清單能完成的任務用數組也能完成，數組能完成的任務用連結清單也能完成。但是靈活性不一樣。

(2)簡單說：連結清單就是用來存儲資料的。連結清單用來存資料相對于數組來說優點就是靈活性，需要多少個動态配置設定多少個，不占用額外的記憶體。數組的優勢是使用簡單（簡單粗暴）。

2.單連結清單的實作

2.1、單連結清單的節點構成

(1)連結清單是由節點組成的，節點中包含：有效資料和指針。

(2)定義的struct node隻是一個結構體，本身并沒有變量生成，也不占用記憶體。結構體定義相當于為連結清單節點定義了一個模闆，但是還沒有一個節點，将來在實際建立連結清單時需要一個節點時用這個模闆來複制一個即可。

2.2、堆記憶體的申請和使用

(1)連結清單的記憶體要求比較靈活，不能用棧，也不能用data資料段。隻能用堆記憶體。

(2)使用堆記憶體來建立一個連結清單節點的步驟：1、申請堆記憶體，大小為一個節點的大小（檢查申請結果是否正确）；2、清理申請到的堆記憶體；3、把申請到的堆記憶體當作一個新節點；4、填充你哦個新節點的有效資料和指針區域。

2.3、連結清單的頭指針

(1)頭指針并不是節點，而是一個普通指針，隻占4位元組。頭指針的類型是struct node *類型的，是以它才能指向連結清單的節點。

(2)一個典型的連結清單的實作就是：頭指針指向連結清單的第1個節點，然後第1個節點中的指針指向下一個節點，然後依次類推一直到最後一個節點。這樣就構成了一個鍊。

2.4、實戰：建構一個簡單的單連結清單

(1)目标：建構一個連結清單，然後将一些資料（譬如1，2，3三個數字）存儲在連結清單中

3.單連結清單的算法之插入節點

3.1、繼續上節，通路連結清單中各個節點的資料

(1)隻能用頭指針，不能用各個節點自己的指針。因為在實際當中我們儲存連結清單的時候是不會儲存各個節點的指針的，隻能通過頭指針來通路連結清單節點。

(2)前一個節點内部的pNext指針能幫助我們找到下一個節點。

3.2、将建立節點的代碼封裝成一個函數

(1)封裝時的關鍵點就是函數的接口（函數參數和傳回值）的設計

3.3、從連結清單頭部插入新節點

3.4、從連結清單尾部插入新節點

(1)尾部插入簡單點，因為前面已經建立好的連結清單不用動。直接動最後一個就可以了。

4.單連結清單的算法之插入節點續

4.1、詳解連結清單頭部插入函數

4.2、什麼是頭節點

(1)問題：因為我們在insert_tail中直接預設了頭指針指向的有一個節點，是以如果程式中直接定義了頭指針後就直接insert_tail就會報段錯誤。我們不得不在定義頭指針之後先create_node建立一個新節點給頭指針初始化，否則不能避免這個錯誤；但是這樣解決讓程式看起來邏輯有點不太順，因為看起來第一個節點和後面的節點的建立、添加方式有點不同。

(2)連結清單還有另外一種用法，就是把頭指針指向的第一個節點作為頭節點使用。頭節點的特點是：第一，它緊跟在頭指針後面。第二，頭節點的資料部分是空的（有時候不是空的，而是存儲整個連結清單的節點數），指針部分指向下一個節點，也就是第一個節點。

(3)這樣看來，頭節點确實和其他節點不同。我們在建立一個連結清單時添加節點的方法也不同。頭節點在建立頭指針時一并建立并且和頭指針關聯起來；後面的真正的存儲資料的節點用節點添加的函數來完成，譬如insert_tail.

(4)連結清單有沒有頭節點是不同的。展現在連結清單的插入節點、删除節點、周遊節點、解析連結清單的各個算法函數都不同。是以如果一個連結清單設計的時候就有頭節點那麼後面的所有算法都應該這樣來處理；如果設計時就沒有頭節點，那麼後面的所有算法都應該按照沒有頭節點來做。實際程式設計中兩種連結清單都有人用，是以大家在看别人寫的代碼時一定要注意看它有沒有頭節點。

5.從連結清單頭部插入新節點

(1)注意寫代碼過程中的箭頭符号，和說話過程中的指針指向。這是兩碼事，容易搞混。箭頭符号實際上是用指針方式來通路結構體，是以箭頭符号的實質是通路結構體中的成員。更清楚一點說程式中的箭頭和連結清單的連接配接沒有任何關系；連結清單中的節點通過指針指向來連接配接，程式設計中表現為一個指派語句（用=來進行連接配接），實質是把後一個節點的首位址，指派給前一個節點中的pNext元素做為值。

(2)連結清單可以從頭部插入，也可以從尾部插入。也可以兩頭插入。頭部插入和尾部插入對連結清單來說幾乎沒有差别。對連結清單本身無差别，但是有時候對業務邏輯有差别。

6.單連結清單的算法之周遊節點

6.1、什麼是周遊

(1)周遊就是把單連結清單中的各個節點挨個拿出來，就叫周遊。

(2)周遊的要點：一是不能遺漏、二是不能重複、追求效率。

6.2、如何周遊單連結清單

(1)分析一個資料結構如何周遊，關鍵是分析這個資料結構本身的特點。然後根據本身特點來制定它的周遊算法。

(2)單連結清單的特點就是由很多個節點組成，頭指針+頭節點為整個連結清單的起始，最後一個節點的特征是它内部的pNext指針值為NULL。從起始到結尾中間由各個節點内部的pNext指針來挂接。由起始到結尾的路徑有且隻有一條。單連結清單的這些特點就決定了它的周遊算法。

(3)周遊方法：從頭指針+頭節點開始，順着連結清單挂接指針依次通路連結清單的各個節點，取出這個節點的資料，然後再往下一個節點，直到最後一個節點，結束傳回。

6.3、程式設計實戰

(1)寫一個連結清單周遊的函數，void bianli(struct node*pH);

7.單連結清單的算法之删除節點

7.1、為什麼要删除節點

(1)一直在強調，連結清單到底用來幹嘛的？

(2)有時候連結清單節點中的資料不想要了，是以要删掉這個節點。

7.2、删除節點的2個步驟

(1)第一步：找到要删除的節點；第二步：删除這個節點。

7.3、如何找到待删除的節點

(1)通過周遊來查找節點。從頭指針+頭節點開始，順着連結清單依次将各個節點拿出來，按照一定的方法比對，找到我們要删除的那個節點。

7.4、如何删除一個節點

(1)待删除的節點不是尾節點的情況:首先把待删除的節點的前一個節點的pNext指針指向待删除的節點的後一個節點的首位址（這樣就把這個節點從連結清單中摘出來了），然後再将這個摘出來的節點free掉接口。

(2)待删除的節點是尾節點的情況：首先把待删除的尾節點的前一個節點的pNext指針指向null（這時候就相當于原來尾節點前面的一個節點變成了新的尾節點），然後将摘出來的節點free掉。

7.5、注意堆記憶體的釋放

(1)前面幾節課我們寫的代碼最終都沒有釋放堆記憶體。當程式都結束了的情況下那些沒有free的堆記憶體也被釋放了。

(2)有時候我們的程式運作時間很久，這時候malloc的記憶體如果沒有free會一直被占用直到你free釋放它或者整個程式終止。

8.單連結清單的算法之逆序

8.1、什麼是連結清單的逆序

(1)連結清單的逆序又叫反向，意思就是把連結清單中所有的有效節點在連結清單中的順序給反過來。

8.2、單連結清單逆序算法分析

(1)當我們對一個資料結構進行一個操作時，我們就需要一套算法。這就是資料結構和算法的關系。

(2)我總結：算法有2個層次。第一個層次是數學和邏輯上的算法；第二次個層次是用程式設計語言來實作算法。

(3)從邏輯上來講，連結清單的逆序有很多種方法。這些方法都能實作最終的需要，但是效率是不一樣的。彼此的可擴充性、容錯性等不同。

(4)思路：首先周遊原連結清單，然後将原連結清單中的頭指針和頭節點作為新連結清單的頭指針和頭節點，原連結清單中的有效節點挨個依次取出來，采用頭插入的方法插入新連結清單中即可。

(5)連結清單逆序 = 周遊 + 頭插入

8.3、程式設計實戰

9.雙連結清單的引入和基本實作

9.1、單連結清單的局限性

(1)單連結清單是對數組的一個擴充，解決了數組的大小比較死闆不容易擴充的問題。使用堆記憶體來存儲資料，将資料分散到各個節點之間，其各個節點在記憶體中可以不相連，節點之間通過指針進行單向連結。連結清單中的各個節點記憶體不相連，有利于利用碎片化的記憶體。

(2)單連結清單各個節點之間隻由一個指針單向連結，這樣實作有一些局限性。局限性主要展現在單連結清單隻能經由指針單向移動（一旦指針移動過某個節點就無法再回來，如果要再次操作這個節點除非從頭指針開始再次周遊一次），是以單連結清單的某些操作就比較麻煩（算法比較有局限）。回憶之前單連結清單的所有操作（插入、删除節點、 周遊、從單連結清單中取某個節點的數·····），因為單連結清單的單向移動性導緻了不少麻煩。

總結：單連結清單的單向移動性導緻我們在操作單連結清單時，目前節點隻能向後移動不能向前移動，是以不自由，不利于解決更複雜的算法。

9.2、解決思路：有效資料+2個指針的節點（雙連結清單）

(1)單連結清單的節點 = 有效資料 + 指針（指針指向後一個節點）

(2)雙向連結清單的節點 = 有效資料 + 2個指針（一個指向後一個節點，另一個指向前一個節點）

9.3、雙連結清單的封裝和程式設計實作

10.雙連結清單的算法之插入節點

10.1、尾部插入

10.2、頭部插入

11.雙連結清單的算法之周遊節點

(1)雙連結清單是單連結清單的一個父集。雙連結清單中如何完全無視pPrev指針，則雙連結清單就變成了單連結清單。這就決定了雙連結清單的正向周遊（後向周遊）和單連結清單是完全相同的。

(2)雙連結清單中因為多了pPrev指針，是以雙連結清單還可以前向周遊（從連結清單的尾節點向前面依次周遊直到頭節點）。但是前向周遊的意義并不大，主要是因為很少有目前當了尾節點需要前向周遊的情況。

(3)總結：雙連結清單是對單連結清單的一種有成本的擴充，但是這個擴充在有些時候意義不大，在另一些時候意義就比較大。是以在實踐用途中要根據業務要求選擇适合的連結清單。

12.雙連結清單的算法之删除節點

13.linux核心連結清單

13.1、前述連結清單資料區域的局限性

(1)之前定義資料區域時直接int data;我們認為我們的連結清單中需要存儲的是一個int類型的數。但是實際上現實程式設計中連結中的節點不可能這麼簡單，而是多種多樣的。

(2)一般實際項目中的連結清單，節點中存儲的資料其實是一個結構體，這個結構體中包含若幹的成員，這些成員加起來構成了我們的節點資料區域。

13.2、一般性解決思路：資料區封裝為一個結構體

(1)因為連結清單實際解決的問題是多種多樣的，是以内部資料區域的結構體構成也是多種多樣的。這樣也導緻了不同程式當中的連結清單總體構成是多種多樣的。導緻的問題是：我們無法通過一個泛性的、普遍适用的操作函數來通路所有的連結清單。這就意味着我們設計一個連結清單就得寫一套連結清單的操作函數（節點建立、插入、删除、周遊······）

(2)實際上深層次分析會發現：不同的連結清單雖然這些方法不能通用需要單獨寫，但是實際上内部的思路和方法是相同的，隻是函數的局部地區有不同。（實際上連結清單操作是相同的，而涉及到資料區域的操作就有不同）

(3)鑒于以上2點：我們的理念就是，能不能有一種辦法把所有連結清單中操作方法裡共同的部分提取出來用一套标準方法實作，然後把不同的部分留着讓具體連結清單的實作者自己去處理。

13.3、核心連結清單的設計思路

(1)核心連結清單中自己實作了一個純連結清單（純連結清單就是沒有資料區域，隻有前後向指針）的封裝，以及純連結清單的各種操作函數（節點建立、插入、删除、周遊······）。這個純連結清單本身自己沒有任何用處，它的用法是給我們具體連結清單作為核心來調用。

13.4、list.h檔案簡介

(1)核心中核心純連結清單的實作在include/linux/list.h檔案中

(2)list.h中就是一個純連結清單的完整封裝，包含節點定義和各種連結清單操作方法。

14.核心連結清單的基本算法和使用簡介

14.1、核心連結清單的節點建立、删除、周遊等

14.2、核心連結清單的使用實踐

(1)問題：核心連結清單隻有純連結清單，沒有資料區域，怎麼使用？

(2)設計的使用方法是将核心連結清單作為将來整個資料結構的結構體的一個成員内嵌進去。

15.什麼是狀态機

15.1、有限狀态機

(1)常說的狀态機是有限狀态機FSM。FSM指的是有有限個狀态（一般是一個狀态變量的值），這個機器同時能夠從外部接收信号和資訊輸入，機器在接收到外部輸入的信号後會綜合考慮目前自己的狀态和使用者輸入的資訊，然後機器做出動作：跳轉到另一個狀态。

(2)考慮狀态機的關鍵點：目前狀态、外部輸入、下一個狀态

15.2、兩種狀态機：Moore型和Mealy型

(1)Moore型狀态機特點是：輸出隻與目前狀态有關（與輸入信号無關）。相對簡單，考慮狀态機的下一個狀态時隻需要考慮它的目前狀态就行了。

(2)Mealy型狀态機的特點是：輸出不隻和目前狀态有關，還與輸入信号有關。狀态機接收到一個輸入信号需要跳轉到下一個狀态時，狀态機綜合考慮2個條件（目前狀态、輸入值）後才決定跳轉到哪個狀态。

15.3、狀态機的主要用途：電路設計、FPGA程式設計、軟體設計

(1)電路設計中廣泛使用了狀态機思想

(2)FPGA程式設計

(3)軟體設計（架構類型的設計，譬如作業系統的GUI系統、消息機制）

15.4、狀态機解決了什麼問題

(1)我們平時寫程式都是順序執行的，這種程式有個特點：程式的大體執行流程是既定的，程式的執行是遵照一定的大的方向有迹可尋的。

(2)但是偶爾會碰到這樣的程式：外部不一定會按照既定流程來給程式輸入資訊，而程式還需要完全能夠接收并響應外部的這些輸入信号，還要能做出符合邏輯的輸出。

16.C語言實作簡單的狀态機

16.1、題目：開鎖狀态機。功能描述：使用者連續輸入正确的密碼則會開鎖，如果密碼輸入過程錯誤則鎖會退回到初始狀态重新計入密碼，即：使用者隻需要連續輸入出正确的密碼即可開鎖（輸入錯誤不用撤銷、也不用删除）

16.2、題目分析

17.多線程簡介

17.1、作業系統下的并行執行機制

(1)并行就是說多個任務同時被執行。并行分微觀上的并行和宏觀上的并行。

(2)宏觀上的并行就是從長時間段（相對于人來說）來看，多個任務是同時進行的；微觀上的并行就是真的在并行執行。

(3)作業系統要求實作宏觀上的并行。宏觀上的并行有2種情況：第一種是微觀上的串行，第二種是微觀上的并行。

(4)理論來說，單核CPU本身隻有一個核心，同時隻能執行一條指令，這種CPU隻能實作宏觀上的并行，微觀上一定是串行的。微觀上的并行要求多核心CPU。多核CPU中的多個核心可以同時微觀上執行多個指令，是以可以達到微觀上的并行，進而提升宏觀上的并行度。

17.2、程序和線程的差別和聯系

(1)程序和線程是作業系統的兩種不同軟體技術，目的是實作宏觀上的并行（通俗一點就是讓多個程式同時在一個機器上運作，達到宏觀上看起來并行執行的效果）。

(2)程序和線程在實作并行效果的原理上不同。而且這個差異和作業系統有關。譬如windows中程序和線程差異比較大，在linux中程序和線程差異不大（linux中線程就是輕量級的程序）。

(3)不管是多程序還是多線程，最終目标都是實作并行執行。

17.3、多線程的優勢

(1)前些年多程序多一些，近些年多線程開始用得多。

(2)現代作業系統設計時考慮到了多核心CPU的優化問題，保證了：多線程程式在運作的時候，作業系統會優先将多個線程放在多個核心中分别單獨運作。是以說多核心CPU給多線程程式提供了完美的運作環境。是以在多核心CPU上使用多線程程式有極大的好處。