這周開(kāi)始自學(xué)數(shù)據(jù)結(jié)構(gòu)與算法，在B站看了些視頻也有了一個(gè)初步的了解，由于是初學(xué)，一些概念還是記清楚點(diǎn)比較好，這篇博客就按我的學(xué)習(xí)順序來(lái)總結(jié)一下本周學(xué)習(xí)內(nèi)容。

初入門(mén)

一、基礎(chǔ)定義

數(shù)據(jù)結(jié)構(gòu)：

數(shù)據(jù)結(jié)構(gòu)(data structure)是帶有結(jié)構(gòu)特性的數(shù)據(jù)元素的集合，它研究的是數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)以及它們之間的相互關(guān)系，并對(duì)這種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法，并確保經(jīng)過(guò)這些運(yùn)算以后所得到的新結(jié)構(gòu)仍保持原來(lái)的結(jié)構(gòu)類(lèi)型。簡(jiǎn)而言之，數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，即帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合?！敖Y(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系，分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。

數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的兩個(gè)密切相關(guān)的方面，同一邏輯結(jié)構(gòu)可以對(duì)應(yīng)不同的存儲(chǔ)結(jié)構(gòu)。算法的設(shè)計(jì)取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于指定的存儲(chǔ)結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容是構(gòu)造復(fù)雜軟件系統(tǒng)的基礎(chǔ)，它的核心技術(shù)是分解與抽象。通過(guò)分解可以劃分出數(shù)據(jù)的3個(gè)層次；再通過(guò)抽象，舍棄數(shù)據(jù)元素的具體內(nèi)容，就得到邏輯結(jié)構(gòu)。類(lèi)似地，通過(guò)分解將處理要求劃分成各種功能，再通過(guò)抽象舍棄實(shí)現(xiàn)細(xì)節(jié)，就得到運(yùn)算的定義。上述兩個(gè)方面的結(jié)合可以將問(wèn)題變換為數(shù)據(jù)結(jié)構(gòu)。這是一個(gè)從具體（即具體問(wèn)題）到抽象（即數(shù)據(jù)結(jié)構(gòu)）的過(guò)程。然后，通過(guò)增加對(duì)實(shí)現(xiàn)細(xì)節(jié)的考慮進(jìn)一步得到存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)運(yùn)算，從而完成設(shè)計(jì)任務(wù)。這是一個(gè)從抽象（即數(shù)據(jù)結(jié)構(gòu)）到具體（即具體實(shí)現(xiàn)）的過(guò)程。?

數(shù)據(jù)的邏輯結(jié)構(gòu)

指反映數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)，其中的邏輯關(guān)系是指數(shù)據(jù)元素之間的前后間關(guān)系，而與他們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān)。邏輯結(jié)構(gòu)包括：

1.集合：數(shù)據(jù)結(jié)構(gòu)中的元素之間除了“同屬一個(gè)集合” 的相互關(guān)系外，別無(wú)其他關(guān)系；

2.線性結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)一的相互關(guān)系；

3.樹(shù)形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)多的相互關(guān)系；

4.圖形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在多對(duì)多的相互關(guān)系。

數(shù)據(jù)的邏輯結(jié)構(gòu)

指反映數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)，其中的邏輯關(guān)系是指數(shù)據(jù)元素之間的前后間關(guān)系，而與他們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān)。邏輯結(jié)構(gòu)包括：

1.集合：數(shù)據(jù)結(jié)構(gòu)中的元素之間除了“同屬一個(gè)集合” 的相互關(guān)系外，別無(wú)其他關(guān)系；

2.線性結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)一的相互關(guān)系；

3.樹(shù)形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)多的相互關(guān)系；

4.圖形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在多對(duì)多的相互關(guān)系。

數(shù)據(jù)的物理結(jié)構(gòu)

指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間的存放形式。

數(shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（又稱映像），它包括數(shù)據(jù)元素的機(jī)內(nèi)表示和關(guān)系的機(jī)內(nèi)表示。由于具體實(shí)現(xiàn)的方法有順序、鏈接、索引、散列等多種，所以，一種數(shù)據(jù)結(jié)構(gòu)可表示成一種或多種存儲(chǔ)結(jié)構(gòu)。

數(shù)據(jù)元素的機(jī)內(nèi)表示（映像方法）： 用二進(jìn)制位（bit）的位串表示數(shù)據(jù)元素。通常稱這種位串為節(jié)點(diǎn)（node）。當(dāng)數(shù)據(jù)元素有若干個(gè)數(shù)據(jù)項(xiàng)組成時(shí)，位串中與個(gè)數(shù)據(jù)項(xiàng)對(duì)應(yīng)的子位串稱為數(shù)據(jù)域（data field）。因此，節(jié)點(diǎn)是數(shù)據(jù)元素的機(jī)內(nèi)表示（或機(jī)內(nèi)映像）。

關(guān)系的機(jī)內(nèi)表示（映像方法）：數(shù)據(jù)元素之間的關(guān)系的機(jī)內(nèi)表示可以分為順序映像和非順序映像，常用兩種存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序映像借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。非順序映像借助指示元素存儲(chǔ)位置的指針（pointer）來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。?

數(shù)據(jù)結(jié)構(gòu)有很多種，一般來(lái)說(shuō)，按照數(shù)據(jù)的邏輯結(jié)構(gòu)對(duì)其進(jìn)行簡(jiǎn)單的分類(lèi)，包括線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類(lèi)。

線性結(jié)構(gòu)

簡(jiǎn)單地說(shuō)，線性結(jié)構(gòu)就是表中各個(gè)結(jié)點(diǎn)具有線性關(guān)系。如果從數(shù)據(jù)結(jié)構(gòu)的語(yǔ)言來(lái)描述，線性結(jié)構(gòu)應(yīng)該包括如下幾點(diǎn)：

1、線性結(jié)構(gòu)是非空集。?

2、線性結(jié)構(gòu)有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)。?

3、線性結(jié)構(gòu)所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨結(jié)點(diǎn)和一個(gè)直接后繼結(jié)點(diǎn)。?

線性表就是典型的線性結(jié)構(gòu)，還有棧、隊(duì)列和串等都屬于線性結(jié)構(gòu)。?

非線性結(jié)構(gòu)

簡(jiǎn)單地說(shuō)，非線性結(jié)構(gòu)就是表中各個(gè)結(jié)點(diǎn)之間具有多個(gè)對(duì)應(yīng)關(guān)系。如果從數(shù)據(jù)結(jié)構(gòu)的語(yǔ)言來(lái)描述，非線性結(jié)構(gòu)應(yīng)該包括如下幾點(diǎn)：?

1、非線性結(jié)構(gòu)是非空集。?

2、非線性結(jié)構(gòu)的一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨結(jié)點(diǎn)和多個(gè)直接后繼結(jié)點(diǎn)。

在實(shí)際應(yīng)用中，數(shù)組、廣義表、樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)等數(shù)據(jù)結(jié)構(gòu)都屬于非線性結(jié)構(gòu)。

常用的數(shù)據(jù)結(jié)構(gòu)

在計(jì)算機(jī)科學(xué)的發(fā)展過(guò)程中，數(shù)據(jù)結(jié)構(gòu)也隨之發(fā)展。程序設(shè)計(jì)中常用的數(shù)據(jù)結(jié)構(gòu)包括如下幾個(gè)。?

數(shù)組(Array)

數(shù)組是一種聚合數(shù)據(jù)類(lèi)型，它是將具有相同類(lèi)型的若干變量有序地組織在一起的集合。數(shù)組可以說(shuō)是最基本的數(shù)據(jù)結(jié)構(gòu)，在各種編程語(yǔ)言中都有對(duì)應(yīng)。一個(gè)數(shù)組可以分解為多個(gè)數(shù)組元素，按照數(shù)據(jù)元素的類(lèi)型，數(shù)組可以分為整型數(shù)組、字符型數(shù)組、浮點(diǎn)型數(shù)組、指針數(shù)組和結(jié)構(gòu)數(shù)組等。數(shù)組還可以有一維、二維以及多維等表現(xiàn)形式。?

棧( Stack)

棧是一種特殊的線性表，它只能在一個(gè)表的一個(gè)固定端進(jìn)行數(shù)據(jù)結(jié)點(diǎn)的插入和刪除操作。棧按照后進(jìn)先出的原則來(lái)存儲(chǔ)數(shù)據(jù)，也就是說(shuō)，先插入的數(shù)據(jù)將被壓入棧底，最后插入的數(shù)據(jù)在棧頂，讀出數(shù)據(jù)時(shí)，從棧頂開(kāi)始逐個(gè)讀出。棧在匯編語(yǔ)言程序中，經(jīng)常用于重要數(shù)據(jù)的現(xiàn)場(chǎng)保護(hù)。棧中沒(méi)有數(shù)據(jù)時(shí)，稱為空棧。

隊(duì)列(Queue)

隊(duì)列和棧類(lèi)似，也是一種特殊的線性表。和棧不同的是，隊(duì)列只允許在表的一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作。一般來(lái)說(shuō)，進(jìn)行插入操作的一端稱為隊(duì)尾，進(jìn)行刪除操作的一端稱為隊(duì)頭。隊(duì)列中沒(méi)有元素時(shí)，稱為空隊(duì)列。?

鏈表( Linked List)

鏈表是一種數(shù)據(jù)元素按照鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，這種存儲(chǔ)結(jié)構(gòu)具有在物理上存在非連續(xù)的特點(diǎn)。鏈表由一系列數(shù)據(jù)結(jié)點(diǎn)構(gòu)成，每個(gè)數(shù)據(jù)結(jié)點(diǎn)包括數(shù)據(jù)域和指針域兩部分。其中，指針域保存了數(shù)據(jù)結(jié)構(gòu)中下一個(gè)元素存放的地址。鏈表結(jié)構(gòu)中數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序來(lái)實(shí)現(xiàn)的。

樹(shù)( Tree)

樹(shù)是典型的非線性結(jié)構(gòu)，它是包括，2個(gè)結(jié)點(diǎn)的有窮集合K。在樹(shù)結(jié)構(gòu)中，有且僅有一個(gè)根結(jié)點(diǎn)，該結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)。在樹(shù)結(jié)構(gòu)中的其他結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)，而且可以有兩個(gè)后繼結(jié)點(diǎn)，m≥0。

圖(Graph)

圖是另一種非線性數(shù)據(jù)結(jié)構(gòu)。在圖結(jié)構(gòu)中，數(shù)據(jù)結(jié)點(diǎn)一般稱為頂點(diǎn)，而邊是頂點(diǎn)的有序偶對(duì)。如果兩個(gè)頂點(diǎn)之間存在一條邊，那么就表示這兩個(gè)頂點(diǎn)具有相鄰關(guān)系。

堆(Heap)

堆是一種特殊的樹(shù)形數(shù)據(jù)結(jié)構(gòu)，一般討論的堆都是二叉堆。堆的特點(diǎn)是根結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中最小的或者最大的，并且根結(jié)點(diǎn)的兩個(gè)子樹(shù)也是一個(gè)堆結(jié)構(gòu)。

散列表(Hash)

散列表源自于散列函數(shù)(Hash function)，其思想是如果在結(jié)構(gòu)中存在關(guān)鍵字和T相等的記錄，那么必定在F(T)的存儲(chǔ)位置可以找到該記錄，這樣就可以不用進(jìn)行比較操作而直接取得所查記錄。?

算法定義：

算法是解決特定問(wèn)題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列，并且每條指令表示一個(gè)或多個(gè)操作，每一個(gè)操作都有特定的功能

算法的基本特點(diǎn)：

（1）輸入輸出：算法具有0個(gè)或多個(gè)輸入，至少有一個(gè)或多個(gè)輸出；

（2）有窮性：指算法在執(zhí)行有限的步驟之后，自動(dòng)結(jié)束而不會(huì)出現(xiàn)無(wú)限循環(huán)，并且每一個(gè)步驟在可接受的時(shí)間內(nèi)完成；

（3）確定性：算法的每一步驟都具有確定的含義，不會(huì)出現(xiàn)二義性。

（4）可行性：算法的每一步都必須是可行的，也就是說(shuō)，每一步都能夠通過(guò)執(zhí)行有限次數(shù)完成；

算法設(shè)計(jì)要求：

（1）正確性：算法的正確性是指算法至少應(yīng)該具有輸入、輸出和加工處理無(wú)歧義性、能正確反映問(wèn)題的需求、能夠得到問(wèn)題的正確答案；

（2）可讀性：算法設(shè)計(jì)的另一目的是為了便于閱讀、理解和交流

（3）健壯性：當(dāng)輸入數(shù)據(jù)不合法時(shí)，算法也能做出相關(guān)處理，而不是產(chǎn)生異常或莫名其妙的結(jié)果；

（4）時(shí)間效率高存儲(chǔ)量低：時(shí)間效率指的是算法的執(zhí)行時(shí)間，對(duì)于同一個(gè)問(wèn)題，如果有多個(gè)算法能夠解決，執(zhí)行時(shí)間短的算法效率高，執(zhí)行時(shí)間長(zhǎng)的效率低。存儲(chǔ)量需求指的是算法在執(zhí)行過(guò)程中需要的最大存儲(chǔ)空間，主要指算法程序運(yùn)行時(shí)所占用的內(nèi)存或外部硬盤(pán)存儲(chǔ)空間。設(shè)計(jì)算法應(yīng)該盡量滿足時(shí)間效率高和存儲(chǔ)量低的需求。

常用算法

數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容：就是如何按一定的邏輯結(jié)構(gòu)，把數(shù)據(jù)組織起來(lái)，并選擇適當(dāng)?shù)拇鎯?chǔ)表示方法把邏輯結(jié)構(gòu)組織好的數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)的存儲(chǔ)器里。研究的目的是為了更有效的處理數(shù)據(jù)，提高數(shù)據(jù)運(yùn)算效率。數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，但運(yùn)算的具體實(shí)現(xiàn)要在存儲(chǔ)結(jié)構(gòu)上進(jìn)行。一般有以下幾種常用運(yùn)算：?

(1)檢索。檢索就是在數(shù)據(jù)結(jié)構(gòu)里查找滿足一定條件的節(jié)點(diǎn)。一般是給定一個(gè)某字段的值，找具有該字段值的節(jié)點(diǎn)。?

(2)插入。往數(shù)據(jù)結(jié)構(gòu)中增加新的節(jié)點(diǎn)。?

(3)刪除。把指定的結(jié)點(diǎn)從數(shù)據(jù)結(jié)構(gòu)中去掉。?

(4)更新。改變指定節(jié)點(diǎn)的一個(gè)或多個(gè)字段的值。

(5)排序。把節(jié)點(diǎn)按某種指定的順序重新排列。例如遞增或遞減。?

以上是我覺(jué)得入門(mén)數(shù)據(jù)結(jié)構(gòu)和算法需要了解的東西?。?！

時(shí)間復(fù)雜度和空間復(fù)雜度

時(shí)間復(fù)雜度

（1）時(shí)間頻度

一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來(lái)的，必須上機(jī)運(yùn)行測(cè)試才能知道。但我們不可能也沒(méi)有必要對(duì)每個(gè)算法都上機(jī)測(cè)試，只需知道哪個(gè)算法花費(fèi)的時(shí)間多，哪個(gè)算法花費(fèi)的時(shí)間少就可以了。并且一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱為語(yǔ)句頻度或時(shí)間頻度。記為T(mén)(n)。算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。

（2）時(shí)間復(fù)雜度

在剛才提到的時(shí)間頻度中，n稱為問(wèn)題的規(guī)模，當(dāng)n不斷變化時(shí)，時(shí)間頻度T(n)也會(huì)不斷變化。但有時(shí)我們想知道它變化時(shí)呈現(xiàn)什么規(guī)律。為此，我們引入時(shí)間復(fù)雜度概念。

一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，若有某個(gè)輔助函數(shù)f(n),存在一個(gè)正常數(shù)c使得fn*c>=T(n)恒成立。記作T(n)=O(f(n)),稱O(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。

在各種不同算法中，若算法中語(yǔ)句執(zhí)行次數(shù)為一個(gè)常數(shù)，則時(shí)間復(fù)雜度為O(1),另外，在時(shí)間頻度不相同時(shí)，時(shí)間復(fù)雜度有可能相同，如T(n)=n^2+3n+4與T(n)=4n^2+2n+1它們的頻度不同，但時(shí)間復(fù)雜度相同，都為O(n^2)。

按數(shù)量級(jí)遞增排列，常見(jiàn)的時(shí)間復(fù)雜度有：

常數(shù)階O(1),對(duì)數(shù)階O(log2n)(以2為底n的對(duì)數(shù)，下同),線性階O(n),

線性對(duì)數(shù)階O(nlog2n),平方階O(n^2)，立方階O(n^3),...，

k次方階O(n^k),指數(shù)階O(2^n)。隨著問(wèn)題規(guī)模n的不斷增大，上述時(shí)間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。

這是我截取的視頻中的常見(jiàn)時(shí)間復(fù)雜度表:

空間復(fù)雜度

與時(shí)間復(fù)雜度類(lèi)似，空間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需存儲(chǔ)空間的度量。記作:

S(n)=O(f(n))

算法執(zhí)行期間所需要的存儲(chǔ)空間包括3個(gè)部分：

算法程序所占的空間；

輸入的初始數(shù)據(jù)所占的存儲(chǔ)空間；

算法執(zhí)行過(guò)程中所需要的額外空間。

在許多實(shí)際問(wèn)題中，為了減少算法所占的存儲(chǔ)空間，通常采用壓縮存儲(chǔ)技術(shù)。

線性表

一、順序表（數(shù)組）

1. 性質(zhì)：①?隨機(jī)訪問(wèn)（查找快，直接定位） ② 存儲(chǔ)密度高，只存儲(chǔ)數(shù)據(jù)元素 ③ 插入、刪除操作需要大量移動(dòng)元素( 插入平均移動(dòng)? n/2 個(gè)元素，刪除平均移動(dòng) (n-1)/2 個(gè)元素 )

2. 順序表的插入：時(shí)間復(fù)雜度：O(n) ; 空間復(fù)雜度：O(1)

//先判斷插入是否合法（省略）for(inti=L.length;i>=pos;i--)//pos為插入位置，數(shù)組下表從0開(kāi)始L.data[i]=L.data[i-1];L.data[i-1]=e;//e為插入元素L.length++;//線性表長(zhǎng)度加1

3. 順序表的刪除：時(shí)間復(fù)雜度：O(n) ; 空間復(fù)雜度：O(1)

//先判斷刪除是否合法（省略）for(inti=pos;i<L.length;i++)//pos為刪除位置，數(shù)組下表從0開(kāi)始L.data[i-1]=L.data[i];L.length--;//線性表長(zhǎng)度減1

4. 順序表的訪問(wèn)：時(shí)間復(fù)雜度：O(1) （基于隨機(jī)訪問(wèn)）

5. 順序表的遍歷和交換太簡(jiǎn)單了，估計(jì)看完一遍書(shū)絕大部分的人都會(huì)吧

6. 算法分析（以后會(huì)開(kāi)一個(gè)專(zhuān)題說(shuō)的，現(xiàn)在這個(gè)階段先把基礎(chǔ)打好，有能力的同學(xué)可以試試寫(xiě)一寫(xiě)數(shù)組逆置； 用O(n)的方法刪除數(shù)組中不等于5的元素； 歸并操作； 二分查找）這些后面都會(huì)說(shuō)的

二、鏈表

1. 單鏈表

性質(zhì)： 非隨機(jī)存儲(chǔ)（查找要逐個(gè)遍歷），所以查找比較慢 、插入刪除操作快（已經(jīng)找到了位置的前提下）

①頭指針指向鏈表的第一個(gè)結(jié)點(diǎn)，頭結(jié)點(diǎn)的帶頭結(jié)點(diǎn)鏈表的第一個(gè)結(jié)點(diǎn)（通常不存儲(chǔ)信息）。

PS：為什么要設(shè)立頭結(jié)點(diǎn)？ 可以對(duì)鏈表統(tǒng)一操作，邊界操作統(tǒng)一

有頭結(jié)點(diǎn)：第一個(gè)有效數(shù)據(jù)的地址為 L->next

無(wú)頭結(jié)點(diǎn)：第一個(gè)有效數(shù)據(jù)的地址 L

②建立：頭插法、尾插法（設(shè)一個(gè)指向表尾的結(jié)點(diǎn)指針rear）

③插入： O（n） 如下圖理解

在第i個(gè)位置 插入

p=GetElem(L,i-1);//時(shí)間復(fù)雜度O(n)s->next=p->next;//①? 注意①②順序不能換，假如交換了就斷鏈了，i-1就找不到原來(lái)i了p->next=s;//② （注意，單單只是將這個(gè)插入操作有時(shí)候只強(qiáng)調(diào)插入，即后兩行代碼，為O(1)）

注意一個(gè)小細(xì)節(jié)，我的圖跟書(shū)上的不一樣，我的 “→”箭頭的起始端是跟“圓圈”連起來(lái)的，其實(shí)“→”就是next域，“圓圈”就是data域，連起來(lái)才是一個(gè)結(jié)構(gòu)體。而書(shū)上的箭頭跟圓圈是分開(kāi)的，我覺(jué)得這樣不助于我們學(xué)生理解。以后我都用下面的寫(xiě)法來(lái)畫(huà)結(jié)點(diǎn)這樣才能完整的保留結(jié)點(diǎn)的存儲(chǔ)特性。

書(shū)上的寫(xiě)法

有助于理解的寫(xiě)法

④刪除：?O（n） 如下圖理解

刪除 第i個(gè)元素

p = GetElem(L, i-1);? ? //時(shí)間復(fù)雜度O(n) 后面的操作為O(1)

q = p->next;

p->next = q->next;

free(q);

問(wèn)：帶有尾指針的單鏈表，在表尾插入一個(gè)元素的時(shí)間復(fù)雜度是O（1），但是刪除表尾的元素時(shí)間復(fù)雜度是O(n)。 大家可以思考一下為什么？

答：

不知道大家發(fā)現(xiàn)沒(méi)有，插入（刪除）操作，都是要找到插入（刪除）元素之前的一個(gè)元素，我們上面是用“p”來(lái)指向的，都是通過(guò)這個(gè)“p”來(lái)完成后續(xù)操作的。

在帶有尾指針rear的鏈表,插入直接用 rear->next = s 就可以了，因?yàn)閞ear正是待插入結(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)。

而刪除表尾元素，就要找到rear的前驅(qū)結(jié)點(diǎn)，由于單鏈表所以要進(jìn)行一次遍歷，找到rear的前驅(qū)結(jié)點(diǎn)，再進(jìn)行刪除操作。

PS:大家知道為什么要設(shè)立head頭結(jié)點(diǎn)這么一說(shuō)了吧，正是因?yàn)橛辛薶ead結(jié)點(diǎn)這一個(gè)前驅(qū)結(jié)點(diǎn)，插入(刪除)操作才會(huì)統(tǒng)一。（鏈表為空的插入，鏈表還剩下一個(gè)的時(shí)候刪除）

總之，在單鏈表的操作中，大家一定要重視待插入（刪除）的前驅(qū)結(jié)點(diǎn)的學(xué)習(xí)。上面總結(jié)出來(lái)的大家一定要好好理解。

2. 雙鏈表：在單鏈表的基礎(chǔ)上，結(jié)構(gòu)體增加一個(gè)指向前驅(qū)結(jié)點(diǎn)的prior的指針

3. 循環(huán)單鏈表：在單鏈表的基礎(chǔ)上，在表尾的next指向表頭 r->next = L;

4. 循環(huán)雙鏈表：在循環(huán)單鏈表基礎(chǔ)上，結(jié)構(gòu)體增加一個(gè)指向前驅(qū)結(jié)點(diǎn)的prior的指針，加上L->prior = r；r->next = L;

5. 靜態(tài)鏈表：用連續(xù)的塊內(nèi)存空間當(dāng)鏈表使用（跟操作系統(tǒng)中文件管理中的文件分配方式的顯示鏈接一樣）

以上說(shuō)的都離不開(kāi)單鏈表的基本操作，只要把單鏈表理解透徹，這些都是小Case。

我覺(jué)得一個(gè)適合自己的筆記，不是什么都寫(xiě)的非常詳細(xì)，只是讓自己有個(gè)索引，具體的書(shū)都是很清楚的，我就沒(méi)有必要在做了重復(fù)了，免得話就跟抄書(shū)沒(méi)有什么區(qū)別了。

三、順序表與鏈表的選用：

通常比較穩(wěn)定的線性表，用順序存儲(chǔ)。（靜態(tài)）

頻繁做插入、刪除操作的線性表，用鏈?zhǔn)酱鎯?chǔ)（動(dòng)態(tài)）

訪問(wèn)查找比較多的 —— 順序表

插入、刪除比較多的，要求占空間小 —— 鏈表