公司的經(jīng)理大哥建議過我跌造，說趁年輕要深入學習算法與數(shù)據(jù)結構，設計模式， APP 架構吼鱼，當然也包括 iOS 底層的一些知識......半年多過去了，算法數(shù)據(jù)結構方面的書多少算是看過一些绰咽，但都是走馬觀花似的一掠而過菇肃，根本沒留下什么印象......2018 突然就到了......接下來會多讀書，并記錄下來取募，算是對自己的督促琐谤，更希望對看到的朋友有所幫助。

文章共分為三篇

第一篇：數(shù)據(jù)結構 -《大話數(shù)據(jù)結構》讀書筆記(1)

一玩敏、數(shù)據(jù)結構緒論
二斗忌、算法
三质礼、線性表

第二篇：數(shù)據(jù)結構 -《大話數(shù)據(jù)結構》讀書筆記(2)

四、棧與隊列
五织阳、串
六几苍、樹
七、圖

第三篇：數(shù)據(jù)結構 -《大話數(shù)據(jù)結構》讀書筆記(3)

八陈哑、查找
九妻坝、排序

一、數(shù)據(jù)結構緒論

1.1 數(shù)據(jù)結構

數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中的操作對象惊窖，以及它們之間的關系和操作等相關問題的學科刽宪。

1.2 基本概念和術語

• 數(shù)據(jù)
  數(shù)據(jù)是描述客觀事物的符號，是計算機中可以操作的對象界酒，是能被計算機識別圣拄，并輸入給計算機處理的符號集合。

數(shù)據(jù)不僅僅包括整形毁欣、實型等數(shù)值類型庇谆，還包括字符及聲音、圖像凭疮、視頻等非數(shù)值類型饭耳。

• 數(shù)據(jù)元素
  數(shù)據(jù)元素是組成數(shù)據(jù)的、有一定意義的基本單位执解，在計算機中通常作為整體處理寞肖，也被稱為記錄。

比如動物類中衰腌，牛新蟆、馬、羊右蕊、雞琼稻、鴨、鵝就是其數(shù)據(jù)元素饶囚。

• 數(shù)據(jù)項
  一個數(shù)據(jù)元素可以由若干數(shù)據(jù)項組成帕翻。數(shù)據(jù)項是數(shù)據(jù)不可分割的最小單位。

比如人這樣的數(shù)據(jù)元素坯约，有眼熊咽、耳、鼻闹丐、口、手被因、腳這些數(shù)據(jù)項卿拴，也可以有姓名衫仑、年齡、性別堕花、出生地址文狱、聯(lián)系電話等數(shù)據(jù)項，具體哪些數(shù)據(jù)項缘挽，要根據(jù)你的系統(tǒng)決定瞄崇。

• 數(shù)據(jù)對象
  數(shù)據(jù)對象是性質相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集壕曼。

所謂性質相同苏研，是指數(shù)據(jù)元素具有相同數(shù)量和類型的數(shù)據(jù)項昂利，比如人都有姓名流部，性別，生日等相同的數(shù)據(jù)項扰法。

• 數(shù)據(jù)結構
  數(shù)據(jù)結構是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合轧飞。

• 研究數(shù)據(jù)結構的意義：
  在計算機中衅鹿，數(shù)據(jù)元素不是孤立、雜亂無序的过咬，而是具有內(nèi)在聯(lián)系的數(shù)據(jù)集合大渤。數(shù)據(jù)元素之間存在的一種或多種特定關系，也就是數(shù)據(jù)的組織形式掸绞。為編寫一個好的程序兼犯，必須分析待處理對象的特性及各處理對象之間存在的關系。這也就是研究數(shù)據(jù)結構的意義所在集漾。

1.3 邏輯結構和物理結構：

按照視點的不同切黔，可以把數(shù)據(jù)結構分為邏輯結構和物理結構。

• 邏輯結構
  邏輯結構是指數(shù)據(jù)對象中數(shù)據(jù)元素之間的相互關系具篇。

• 邏輯結構分為以下四種：

  • 集合結構：集合結構中的數(shù)據(jù)元素除了同屬于一個集合外纬霞，它們之間沒有其他關系。各個數(shù)據(jù)元素是“平等”的驱显，它們的共同屬性是同屬于一個集合诗芜。
    
    集合結構
  • 線性結構：線性結構中的數(shù)據(jù)元素是一對一的關系。
    
    線性結構
  • 樹形結構：樹形結構中的元素之間存在一種一對多的層次關系埃疫。
    
    樹形結構
  • 圖形結構：圖形結構的數(shù)據(jù)元素是多對多的關系伏恐。
    
    樹形結構

• 物理結構
  物理結構（存儲結構）：是指數(shù)據(jù)的邏輯結構在計算機中的存儲形式。

數(shù)據(jù)是數(shù)據(jù)元素的集合栓霜，那么根據(jù)物理結構的定義翠桦，實際上就是如何把數(shù)據(jù)元素存儲到計算機的存儲器中。數(shù)據(jù)的存儲結構應正確反映數(shù)據(jù)元素之間的邏輯關系，這才是最關鍵的销凑，如何存儲數(shù)據(jù)元素之間的邏輯關系丛晌，是實現(xiàn)物理結構的重點和難點。

數(shù)據(jù)元素的存儲結構形式有兩種：順序存儲和鏈式存儲斗幼。

• 順序存儲結構
  順序存儲結構：是把數(shù)據(jù)元素存放在地址連續(xù)的存儲單元里澎蛛，其數(shù)據(jù)間的邏輯關系和物理關系是一致的。

順序存儲結構

順序存儲結構說白了就是排隊占位蜕窿，大家都按順序排好谋逻，每個人占一小段控件，大家誰也別插誰的隊桐经。數(shù)組就是這樣的順序存儲結構毁兆。

• 鏈式存儲結構
  鏈式存儲結構：是把數(shù)據(jù)元素存放在任意的存儲單元里，這組存儲單元可以是連續(xù)的次询，也可以是不連續(xù)的荧恍。

鏈式存儲結構

數(shù)據(jù)元素的存儲關系并不能反應其邏輯關系，因此需要用一個指針存放數(shù)據(jù)元素的地址屯吊，這樣通過地址就可以找到相關聯(lián)數(shù)據(jù)元素的位置送巡。鏈式存儲結構比較靈活，數(shù)據(jù)存在哪里不重要盒卸，只要有一個指針存放了相應的地址就能找到它了骗爆。比如現(xiàn)在去銀行醫(yī)院等地方，去了先領一個號蔽介，等著叫號摘投，在等待的時候你可以做任何事情，只要及時回來就行虹蓄。

1.4 抽象數(shù)據(jù)類型：

• 數(shù)據(jù)類型
  數(shù)據(jù)類型：是指一組性質相同的值的集合及定義在此集合上的一些操作的總稱犀呼。

數(shù)據(jù)類型是按照值的不同進行劃分的，在高級語言中薇组，每個變量外臂、常量和表達式都有各自的取值范圍。類型就用來說明變量或表達式的取值范圍和所能進行的操作律胀。

• 抽象
  抽象：抽象是指抽取出事物具有的普遍性的本質宋光。它是抽出問題的特征而忽略非本質的細節(jié)，是對具體事物的一個概括炭菌。抽象是一種思考問題的方式罪佳，它隱藏了繁雜的細節(jié)，只保留實現(xiàn)目標所必需的信息黑低。

在C語言中赘艳，按照取值的不同，數(shù)據(jù)類型可以分為兩類：

• 原子類型：是不可以再分解的基本類型，包括整型第练、實型阔馋、字符型等玛荞；

• 數(shù)據(jù)類型：由若干個類型組合而成娇掏，是可以再分解的。例如勋眯，整型數(shù)組是由若干整型數(shù)據(jù)組成的婴梧。

• 抽象數(shù)據(jù)類型
  抽象數(shù)據(jù)類型：是指一個數(shù)學模型及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性客蹋，而與其在計算及內(nèi)部如何表示和實現(xiàn)無關塞蹭。

比如在大型機、小型機讶坯、PC番电、平板電腦、PDA辆琅，甚至智能手機都擁有“整數(shù)”類型漱办，也需要整數(shù)間的運算，那么整型其實就是一個抽象數(shù)據(jù)類型婉烟，盡管它在上面提到的這些在不同計算機中實現(xiàn)方法上可能不一樣娩井，但由于其定義的數(shù)學特性相同，在計算機編程者看來似袁，它們都是相同的洞辣。因此，“抽象”的意義在于數(shù)據(jù)類型的數(shù)學抽象特性昙衅。

二扬霜、算法

2.1 算法定義

算法是解決待定問題求解步驟的描述，在計算機中表現(xiàn)為指令的有限序列而涉，并且每條指令表示一個或多個操作著瓶。

2.2 算法的特性

算法有五個基本特性：輸入、輸出婴谱、有窮性蟹但、確定性和可行性。

• 輸入輸出
  輸入和輸出特性比較容易理解谭羔，算法具有零個或多個輸入华糖。絕大多數(shù)算法需要輸入?yún)?shù)，但有的是不需要的瘟裸，不如“hello world”這樣的代碼客叉，不需要任何參數(shù)，因此算法的輸入可以是零個。算法至少有一個或多個輸出兼搏，算法是一定要輸出的卵慰，不需要輸出，那用這個算法干嘛佛呻？輸出的形式可以使打印輸出裳朋，也可以是返回一個或多個值。

• 有窮性
  有窮性：指算法在執(zhí)行有限的步驟之后吓著，自動結束而不會出現(xiàn)無限循環(huán)鲤嫡，并且每一個步驟在可接受的時間內(nèi)完成。

• 確定性：
  算法的每一步驟都具有確定的含義绑莺，不會出現(xiàn)二義性暖眼。

算法在一定條件下，只有一條執(zhí)行路徑纺裁，相同的輸入只能有唯一的輸出結果诫肠，算法的每個步驟被精確定義而無歧義。

• 可行性：
  算法的每一步都必須是可行的欺缘，也就是說栋豫，每一步都能夠通過執(zhí)行有限次數(shù)完成。

2.3 算法設計的要求

算法不是唯一的浪南，同一個問題笼才，可以有很多種解決問題的算法。好的算法應該具有以下幾點要求：

• 正確性：
  正確性：算法的正確性是指算法至少應該具有輸入络凿、輸出和加工處理無歧義性骡送、能正確反映問題的需求、能夠得到問題的正確答案絮记。

算法的“正確”通常在語法上有很大的差別摔踱，大體分為以下四個層次。

1. 算法程序沒有語法錯誤怨愤；
2. 算法程序對于合法的輸入數(shù)據(jù)能夠產(chǎn)生滿足要求的輸出結果派敷；
3. 算法程序對于非法的輸入數(shù)據(jù)能夠得出滿足規(guī)格說明的結果；
4. 算法程序對于精心選擇的撰洗，甚至刁難的測試數(shù)據(jù)都有滿足要求的輸出結果篮愉。

一般情況下，我們把層次 3 作為算法是否正確的標準差导。

• 可讀性：
  可讀性：算法設計的另一目的是為了便于閱讀试躏、理解和交流。

我們寫代碼的目的设褐，一方面是為了讓計算機執(zhí)行颠蕴，另一方面是為了便于他人閱讀泣刹，讓人理解和交流，自己將來也可能閱讀犀被，如果可讀性不好椅您，時間長了自己都不知道寫了什么，可讀性是算法好壞的一個很重要的標志寡键。

• 健壯性
  健壯性：當輸入數(shù)據(jù)不合法時掀泳，算法也能做出相關處理，而不是產(chǎn)生異巢或莫名其妙的結果开伏。

• 時間效率高和存儲量低
  時間效率指的是算法的執(zhí)行時間膀跌，對于同一個問題遭商，如果有多個算法可以解決，執(zhí)行時間短的算法效率高捅伤，執(zhí)行時間長的效率低劫流。存儲量需求指的是算法在執(zhí)行過程中需要的最大存儲空間，主要指算法程序運行時所占用的內(nèi)存或外部硬盤存儲空間丛忆。設計算法應該盡量滿足時間效率高和存儲量低的需求祠汇。

綜上，好的算法熄诡，應該具有正確性可很、可讀性、健壯性凰浮、高效性和低存儲量的特點我抠。

2.4 函數(shù)的漸進增長

• 函數(shù)的漸進增長：給定兩個函數(shù)f(n)與g(n)，如果存在一個整數(shù)N袜茧，使得對于所有n>N菜拓，f(n)總是比g(n)大，那么笛厦，我們說f(n)的增長漸進快于g(n)纳鼎。

例子 1：
A 算法與 B 算法，A 算法要做 2n+3 次操作裳凸；B 算法要做 3n+1 次操作贱鄙。問哪個執(zhí)行的更快？

由上圖可知姨谷，當 n = 1逗宁，算法 A 效率不如算法 B；當 n = 2 時菠秒，兩者效率相同疙剑；當 n > 2 時氯迂，算法A開始優(yōu)于算法 B了。得出結論言缤，加法常數(shù)可以忽略嚼蚀。

例子 2：

C 算法與 D 算法，C 算法要做 4n+8 次操作管挟；D 算法要做 2 n*n +1 次操作轿曙。問哪個執(zhí)行的更快？

由上圖可知僻孝，當 n <= 3 時导帝，算法 C 差于算法 D；當 n > 3 時穿铆，算法 C 的優(yōu)勢開始越來越優(yōu)于算法 D 了您单。得出結論：與最高次項相乘的常數(shù)并不重要。

2.5 算法時間復雜度

• 算法時間復雜度定義
  算法時間復雜度：在進行算法分析時荞雏，語句總的執(zhí)行次數(shù) T(n) 是關于問題規(guī)模n的函數(shù)虐秦，進而分析 T(n) 隨 n 的變化情況并確定 T(n) 的數(shù)量級。算法的時間復雜度凤优，也就是算法的時間量度悦陋，記作：T(n) = O(f(n))。它表示隨問題規(guī)模 n 的增大筑辨，算法執(zhí)行時間的增長率和 f(n) 的增長率相同俺驶，稱作算法的漸進時間復雜度，簡稱為時間復雜度棍辕。其中 f(n) 是問題規(guī)模 n 的某個函數(shù)暮现。

這樣用大寫 O() 來體系那算法時間復雜度的記法，我們稱之為大 O 記法痢毒。

一般情況下送矩，隨著n的增大，T(n) 增長最慢的算法為最優(yōu)算法哪替。

• 常用的算法時間復雜度

  
  

• 推導大 O 階方法
  • 用常數(shù) 1 取代運行時間中的所有加法常數(shù)
  • 在修改后的運行次數(shù)函數(shù)中栋荸，只保留最高階項
  • 如果最高階項存在且不是 1，則去除與這個項相乘的常數(shù)凭舶。

得到的結果就是大 O 階晌块。

2.6 算法空間復雜度

• 算法的空間復雜度通過計算算法所需的存儲空間實現(xiàn)，算法空間復雜度的計算公式記作：S(n) = O(f(n))帅霜，其中匆背，n 為問題的規(guī)模，f(n) 為語句關于 n 所占存儲空間的函數(shù)身冀。

一般情況下钝尸，一個程序在機器上執(zhí)行時括享，除了需要存儲程序本身的指令、常數(shù)珍促、變量和輸入數(shù)據(jù)外铃辖，還需要存儲對數(shù)據(jù)操作的存儲單元。若輸入數(shù)據(jù)所占空間只取決于問題本身猪叙，和算法無關娇斩，這樣只需要分析該算法在實現(xiàn)時所需的輔助單元即可。若算法執(zhí)行時所需的輔助空間相對于輸入的數(shù)據(jù)量而言是個常數(shù)穴翩，則稱此算法為原地工作犬第，空間復雜度為 O(n)。

通常芒帕，我們都使用“時間復雜度”來指運行時間的需求歉嗓，使用“空間復雜度”指空間需求。當不用限定詞地使用“復雜度”時副签，通常都是指時間復雜度遥椿。

三、線性表

3.1 線性表定義

零個或多個數(shù)據(jù)元素的有限序列淆储。

首先它是一個序列。也就是說家浇，元素之間是有順序的本砰，若元素存在多個，則第一個元素無前驅钢悲，最后一個元素無后繼点额，其它元素都有且只有一個前驅一個后繼。

然后莺琳，線性表強調是有限的还棱，即元素個數(shù)是有限的。

3.2 線性表的抽象數(shù)據(jù)類型

對于一個線性表來說惭等，插入或者刪除數(shù)據(jù)都是必須的操作珍手，因此線性表的抽象數(shù)據(jù)類型定義如下：

ADT線性表(List)
Data
線性表的數(shù)據(jù)對象集合為 (a1, a2, a3, ……, an)， 每個元素的類型均為 DataType辞做。其中琳要，除第一個元素外，每個元素有且只有一個直接前驅元素秤茅；除了最后一個元素外稚补，每個元素有且只有一個直接后繼元素。數(shù)據(jù)元素之間的關系是一對一的關系框喳。
Operation
InitList (*L) : 初始化操作课幕，建立一個空的線性表L厦坛。
ListEmpty (L): 若線性表為空，返回 true乍惊，否則返回 false粪般。
ClearList (*L): 將線性表清空。
GetElem (L, i, *e): 將線性表 L 中的第 i 個元素值返回給 e污桦。
LocateElem (L, e): 在線性表 L 中查找與給定值 e 相等的元素亩歹，如果查找成功，返回該元素在表中序號表示成功凡橱；否則小作，返回 0 表示失敗。
ListInsert (*L, i, e):  在線性表 L 中的第 i 個位置插入新元素 e稼钩。
ListDelete (*L, i, *e): 刪除線性表 L 中第 i 個位置元素顾稀，并用 e 返回其值。
ListLength (L): 返回線性表 L 的元素個數(shù)坝撑。

endADT

對于不同的應用静秆，線性表的基本操作是不同的，上述操作是最基本的巡李，對于實際問題中涉及的關于線性表的更復雜操作抚笔，完全可以用這些基本操作的組合來實現(xiàn)。

3.3 線性表的順序存儲結構

3.3.1 順序存儲定義

先來看看線性表的兩種物理結構的第一種——順序存儲結構侨拦。

• 順序存儲結構
  線性表的順序存儲結構殊橙，指的是用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。

線性表的順序存儲示意圖如下：

線性表的順序存儲

3.3.2 順序存儲方式

線性表的順序存儲結構狱从，就是在內(nèi)存中找了塊地兒膨蛮，通過占位的形式，把一定內(nèi)存空間給占了季研，然后把相同數(shù)據(jù)類型的數(shù)據(jù)元素依次存放在這塊空地中敞葛。既然線性表的每個數(shù)據(jù)元素的類型都相同，所以可以用 C 語言（其它語言也相同）的一維數(shù)組來實現(xiàn)順序存儲結構与涡，即把第一個數(shù)據(jù)元素存到數(shù)組下標為 0 的位置中惹谐，接著把線性表相鄰的元素存儲在數(shù)組中相鄰的位置。

• 線性表順序存儲的結構代碼：

/* 存儲空間初始分配量 */
#define MAXSIZE 20 

/* ElemType 類型根據(jù)實際情況而定递沪，這里假設為 int */
typedef int ElemType;

typedef struct {
    /* 數(shù)組存儲數(shù)據(jù)元素豺鼻，最大值為 MAXSIZE */
    ElemType data [MAXSIZE];
    /* 線性表當前長度 */
    int length;
}SqList;

• 這里我們發(fā)現(xiàn)描述順序存儲結構需要三個屬性：
  • 存儲空間的起始位置：數(shù)組 data， 它的存儲位置就是存儲空間的存儲位置款慨。
  • 線性表的最大存儲容量：數(shù)組長度 MAXSIZE儒飒。
  • 線性表的當前長度：length。

3.3.3 數(shù)據(jù)長度與線性表長度區(qū)別

• 數(shù)組長度指的是存放線性表的存儲空間的長度檩奠，存儲分配后這個量一般是不變的（一般高級語言桩了，比如 C附帽，VB， C++都可以用編程手段實現(xiàn)動態(tài)分配數(shù)組長度井誉，不過這回帶來性能上的損耗）蕉扮。

• 線性表的長度指的是線性表中數(shù)據(jù)元素的個數(shù)，隨著線性表插入和刪除操作的進行颗圣，這個量是變化的喳钟。

在任何時刻，線性表的長度都應該小于等于數(shù)組的長度在岂。

3.3.4 地址計算方法

C 語言中的數(shù)組是從 0 開始第一個下標的奔则，線性表的第 i 個元素是要存儲在數(shù)組下標為i - 1的位置，即數(shù)據(jù)元素的序號和存放它的數(shù)組下標之間存在對應關系（如下圖）蔽午。

用數(shù)組存儲順序表意味著要分配固定長度的數(shù)組空間易茬，由于線性表中可以進行插入和刪除操作，因此分配的數(shù)組空間要大于等于當前線性表的長度及老。

• 地址
  存儲器中的每個存儲單元都有自己的編號抽莱，這個編號稱為地址。

3.4 順序存儲結構的插入和刪除

3.4.1 插入算法的思路

1. 如果插入位置不合理骄恶，拋出異常
2. 如果線性表長度大于等于數(shù)組長度食铐，則拋出異常或動態(tài)增加容量
3. 從最后一個元素開始向前遍歷到第 i 個位置叠蝇，分別將它們都向后移動一個位置
4. 將要插入元素填入位置 i 處
5. 表長加 1

3.4.2 刪除算法的思路

1. 如果刪除位置不合理璃岳，拋出異常
2. 取出刪除元素
3. 從刪除元素開始遍歷到最后一個元素位置，分別將它們都向前移動一個位置
4. 表長減 1

3.4.3 插入和刪除的時間復雜度

• 先來看最好情況悔捶，如果元素要插入到最后一個位置，或者刪除最后一個元素单芜，此時時間復雜度為O(1)蜕该，因為不需要移動元素的。

• 最壞的情況洲鸠，就是元素要插入到第一個位置堂淡，或者刪除第一個元素，此時所有元素都要移動扒腕，時間復雜度為 O(n)绢淀。

• 平均移動次數(shù)為(n - 1) / 2，可以得出平均時間復雜度是O(n)瘾腰。

3.4.4 線性表順序存儲結構的優(yōu)缺點

• 優(yōu)點
  • 無須為表示表中元素之間的邏輯關系而增加額外的存儲空間
  • 可以快速地存取表中任一位置的元素皆的。
• 缺點：
  • 插入和刪除操作是需要移動大量元素
  • 當線性表長度變化較大時，難以確定存儲空間的容量
  • 造成存儲空間的“碎片”蹋盆。

3.5 線性表的鏈式存儲結構

3.5.1 順序存儲結構的不足

順序存儲結構最大的缺點就是插入和刪除時需要移動大量元素费薄，這顯然就需要耗費時間硝全。

3.5.2線性表鏈式存儲結構定義

線性表的鏈式存儲結構的特點是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，這組存儲單元可以是連續(xù)的楞抡，也可以是不連續(xù)的伟众。這就意味著，這些數(shù)據(jù)元素可以存在內(nèi)存未被占用的任意位置召廷。

在順序結構中凳厢，每個數(shù)據(jù)元素只需要存數(shù)據(jù)元素信息就可以了，但在鏈式結構中竞慢，除了要存數(shù)據(jù)元素信息外先紫，還要存儲它的后繼元素的存儲地址。

為了表示每個數(shù)據(jù)元素 a(i) 與其直接后繼數(shù)據(jù)元素 a(i+1) 之間的邏輯關系梗顺，對數(shù)據(jù)元素a(i)來說泡孩，除了存儲其本身的信息之外，還需存儲一個指示其直接后繼的信息(即直接后繼的存儲位置)寺谤。我們把存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域仑鸥，把存儲直接后繼位置的域稱為指針域。指針域中存儲的信息稱作指針或鏈变屁。這兩部分信息組成數(shù)據(jù)元素a(i)的存儲映像眼俊，稱為結點(Node)。

N 個結點鏈接成一個鏈表粟关，即為線性表（a1疮胖，a2，…闷板，a（n））的鏈式存儲結構澎灸，因為此鏈表的每個結點中只包含一個指針域，所以叫做單鏈表遮晚。單鏈表正是通過每個結點的指針域將線性表的數(shù)據(jù)元素按其邏輯次序鏈接在一起性昭。如下圖所示：

對于線性表來說，總得有個頭有個尾县遣，鏈表也不例外糜颠。我們把鏈表中第一個結點的存儲位置叫做頭指針，那么整個鏈表的存取就必須是從頭指針開始進行了萧求。之后的每一個結點其兴，其實就是上一個的后繼指針指向的位置。最后一個結點指針為“空”夸政，如下圖所示：

有時元旬，我們?yōu)榱烁臃奖愕貙︽湵磉M行操作，會在單鏈表的第一個結點前附設一個結點，稱為頭結點法绵。頭結點的數(shù)據(jù)域可以不存儲任何信息箕速，也可以存儲諸如線性表的長度等附加信息，頭結點的指針域存儲指向第一個結點的指針朋譬。如下圖所示：

3.5.3 頭指針與頭結點的異同

• 頭指針

  • 頭指針是指鏈表指向第一個結點的指針盐茎，若鏈表有頭結點，則是指向頭結點的指針
  • 頭指針具有標識作用徙赢，所以常用指針冠以鏈表的名字
  • 無論鏈表是否為空字柠，頭指針均不為空，頭指針是鏈表的必要元素狡赐。

• 頭結點

  • 頭結點是為了操作的統(tǒng)一和方便而設立的窑业，放在第一元素的結點之前，其數(shù)據(jù)域一般無意義（也可存放鏈表的長度）
  • 有了頭結點枕屉，對在第一元素結點前插入結點和刪除第一結點常柄，其操作與其它結點的操作就統(tǒng)一了
  • 頭結點不一定是鏈表必須要素。

3.6 單鏈表的讀取

在線性表的順序存儲結構中搀擂，我們要計算任意一個元素的存儲位置是很容易的西潘，但在單鏈表中，必須得從頭開始找哨颂。因此喷市，對于單鏈表實現(xiàn)獲取第 i 個元素的數(shù)據(jù)的操作 GetElem ，在算法上威恼，相對要麻煩一些矩桂。

• 獲得鏈表第 i 個數(shù)據(jù)的算法思路：
  1. 聲明一個結點 p 指向鏈表第一個結點楚午，初始化 j 從 1 開始；
  2. 當 j < i 時拖陆，就遍歷鏈表攒射，讓 p 的指針向后移動师幕，不斷指向下一結點猿妈，j 累加 1芬失；
  3. 若到鏈表末尾 p 為空，則說明第 i 個元素不存在附迷；
  4. 否則查找成功，返回結點 p 的數(shù)據(jù)哎媚。

3.7 單鏈表的插入和刪除

3.7.1單鏈表的插入

假設存儲元素 e 的結點為 s喇伯，要實現(xiàn)結點 p、p->next 和 s 之間邏輯關系的變化拨与，只需將結點 s 插入到結點 p 和 p->next 之間即可稻据。如何插入？

用不著驚動其它結點，只需讓 s->next 和 p->next 的指針做一點改變即可捻悯。

s->next=p->next; p->next=s;

解讀代碼：讓 p 的后繼結點改成 s 的后繼結點匆赃，再把結點 s 變成 p 的后繼結點。

• 單鏈表第 i 個數(shù)據(jù)插入結點的算法思路：
  1. 聲明一結點 p 指向鏈表第一個結點今缚，初始化 j 從 1 開始算柳；
  2. 當 j < i 時，就遍歷鏈表姓言，讓 p 的指針向后移動瞬项，不斷指向下一結點，j 累加 1何荚；
  3. 若到鏈表末尾 p 為空囱淋，則說明第 i 個元素不存在；
  4. 否則查找成功餐塘，在系統(tǒng)中生成一個空結點 s妥衣；
  5. 將數(shù)據(jù)元素 e 賦值給 s-> data；
  6. 單鏈表的插入標準語句 s->next = p->next; p->next=s戒傻；
  7. 返回成功

3.7.2單鏈表的刪除

假設存儲元素 a 的結點為 q税手，要實現(xiàn)結點 q 刪除單鏈表的操作，其實就是將它的前繼結點的指針繞過稠鼻，指向它的后繼結點即可冈止。

q=p->next; p->next=q->next;

解讀代碼：讓 p 的后繼結的后繼結點改成 p 的后繼結點。

• 單鏈表第 i 個數(shù)據(jù)刪除結點的算法思路：
  1. 聲明一結點 p 指向鏈表第一個結點候齿，初始化 j 從 1 開始熙暴；
  2. 當 j < i 時，就遍歷鏈表慌盯，讓 p 的指針向后移動周霉，不斷指向下一個結點，j 累加 1亚皂；
  3. 若到鏈表末尾 p 為空俱箱，則說明第 i 個元素不存在；
  4. 否則查找成功灭必，將欲刪除的結點 p->next 賦值給 q狞谱；
  5. 單鏈表的刪除標準語句 p->next=q->next;
  6. 將 q 結點中的數(shù)據(jù)賦值給 e，作為返回禁漓；
  7. 釋放 q 結點跟衅；
  8. 返回成功。

3.8 單鏈表的整表創(chuàng)建與刪除

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

順序存儲結構的創(chuàng)建播歼，其實就是一個數(shù)組的初始化伶跷，即聲明一個類型和大小的數(shù)組并賦值的過程。而鏈表和順序存儲結構不一樣，它不像順序存儲結構這么集中叭莫，它可以很散蹈集，是一種動態(tài)結構。對每個鏈表來說雇初，它所占用空間的大小和位置是不需要預先分配劃定的拢肆，可以根據(jù)系統(tǒng)的情況和實際的需求即時生成。

所以創(chuàng)建單鏈表的過程就是一個動態(tài)生成鏈表的過程抵皱。即從“空表”的初始化狀態(tài)起善榛，依次建立各元素結點，并逐個插入鏈表呻畸。

• 單鏈表整表創(chuàng)建的算法思路：
  1. 聲明一結點 p 和計數(shù)器變量 i移盆；
  2. 初始化一空鏈表L；
  3. 讓 L 的頭結點的指針指向 NULL伤为，即建立一個帶頭結點的單鏈表咒循；
  4. 循環(huán)：生成一新結點賦值給 p；隨機生成一數(shù)字賦值給 p 的數(shù)據(jù)域 p->data绞愚；將 p 插入到頭結點與前一新結點之間叙甸。

3.8.2 單鏈表的整表刪除

當我們不打算使用這個單鏈表時，我們需要把它銷毀位衩，其實也就是在內(nèi)存中將它釋放掉裆蒸，以便留出空間給其它程序或軟件使用。

• 單鏈表整表刪除的算法思路：
  1. 聲明一結點 p 和 q糖驴；
  2. 將第一個結點賦值給 p僚祷；
  3. 循環(huán)：將下一結點賦值給 q；釋放 p贮缕；將 q 賦值給 p辙谜。

3.9 單鏈表結構與順序存儲結構優(yōu)缺點

• 鏈表結構和順序存儲結構對比圖：
  
  
  由上圖可知，線性表的順序存儲結構和單鏈表結構各有其優(yōu)缺點感昼，不能簡單的說哪個好哪個不好装哆，需要根據(jù)實際情況，來綜合平衡采用哪種數(shù)據(jù)結構更能滿足和達到需求和性能定嗓。
  
  
  

下一篇：數(shù)據(jù)結構 -《大話數(shù)據(jù)結構》讀書筆記(2)