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

順序存儲結(jié)構(gòu)

順序存儲結(jié)構(gòu)說白了就是排隊(duì)占位，大家都按順序排好，每個(gè)人占一小段控件，大家誰也別插誰的隊(duì)。數(shù)組就是這樣的順序存儲結(jié)構(gòu)。

• 鏈?zhǔn)酱鎯Y(jié)構(gòu)
  鏈?zhǔn)酱鎯Y(jié)構(gòu)：是把數(shù)據(jù)元素存放在任意的存儲單元里，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的。

鏈?zhǔn)酱鎯Y(jié)構(gòu)

數(shù)據(jù)元素的存儲關(guān)系并不能反應(yīng)其邏輯關(guān)系，因此需要用一個(gè)指針存放數(shù)據(jù)元素的地址，這樣通過地址就可以找到相關(guān)聯(lián)數(shù)據(jù)元素的位置。鏈?zhǔn)酱鎯Y(jié)構(gòu)比較靈活，數(shù)據(jù)存在哪里不重要，只要有一個(gè)指針存放了相應(yīng)的地址就能找到它了。比如現(xiàn)在去銀行醫(yī)院等地方，去了先領(lǐng)一個(gè)號，等著叫號，在等待的時(shí)候你可以做任何事情，只要及時(shí)回來就行。

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

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

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

• 抽象
  抽象：抽象是指抽取出事物具有的普遍性的本質(zhì)。它是抽出問題的特征而忽略非本質(zhì)的細(xì)節(jié)，是對具體事物的一個(gè)概括。抽象是一種思考問題的方式，它隱藏了繁雜的細(xì)節(jié)，只保留實(shí)現(xiàn)目標(biāo)所必需的信息。

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

• 原子類型：是不可以再分解的基本類型，包括整型、實(shí)型、字符型等；

• 數(shù)據(jù)類型：由若干個(gè)類型組合而成，是可以再分解的。例如，整型數(shù)組是由若干整型數(shù)據(jù)組成的。

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

比如在大型機(jī)、小型機(jī)、PC、平板電腦、PDA，甚至智能手機(jī)都擁有“整數(shù)”類型，也需要整數(shù)間的運(yùn)算，那么整型其實(shí)就是一個(gè)抽象數(shù)據(jù)類型，盡管它在上面提到的這些在不同計(jì)算機(jī)中實(shí)現(xiàn)方法上可能不一樣，但由于其定義的數(shù)學(xué)特性相同，在計(jì)算機(jī)編程者看來，它們都是相同的。因此，“抽象”的意義在于數(shù)據(jù)類型的數(shù)學(xué)抽象特性。

二、算法

2.1 算法定義

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

2.2 算法的特性

算法有五個(gè)基本特性：輸入、輸出、有窮性、確定性和可行性。

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

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

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

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

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

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

算法不是唯一的，同一個(gè)問題，可以有很多種解決問題的算法。好的算法應(yīng)該具有以下幾點(diǎn)要求：

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

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

1. 算法程序沒有語法錯(cuò)誤；
2. 算法程序?qū)τ诤戏ǖ妮斎霐?shù)據(jù)能夠產(chǎn)生滿足要求的輸出結(jié)果；
3. 算法程序?qū)τ诜欠ǖ妮斎霐?shù)據(jù)能夠得出滿足規(guī)格說明的結(jié)果；
4. 算法程序?qū)τ诰倪x擇的，甚至刁難的測試數(shù)據(jù)都有滿足要求的輸出結(jié)果。

一般情況下，我們把層次 3 作為算法是否正確的標(biāo)準(zhǔn)。

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

我們寫代碼的目的，一方面是為了讓計(jì)算機(jī)執(zhí)行，另一方面是為了便于他人閱讀，讓人理解和交流，自己將來也可能閱讀，如果可讀性不好，時(shí)間長了自己都不知道寫了什么，可讀性是算法好壞的一個(gè)很重要的標(biāo)志。

• 健壯性
  健壯性：當(dāng)輸入數(shù)據(jù)不合法時(shí)，算法也能做出相關(guān)處理，而不是產(chǎn)生異?；蚰涿畹慕Y(jié)果。

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

綜上，好的算法，應(yīng)該具有正確性、可讀性、健壯性、高效性和低存儲量的特點(diǎn)。

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

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

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

由上圖可知，當(dāng) n = 1，算法 A 效率不如算法 B；當(dāng) n = 2 時(shí)，兩者效率相同；當(dāng) n > 2 時(shí)，算法A開始優(yōu)于算法 B了。得出結(jié)論，加法常數(shù)可以忽略。

例子 2：

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

由上圖可知，當(dāng) n <= 3 時(shí)，算法 C 差于算法 D；當(dāng) n > 3 時(shí)，算法 C 的優(yōu)勢開始越來越優(yōu)于算法 D 了。得出結(jié)論：與最高次項(xiàng)相乘的常數(shù)并不重要。

2.5 算法時(shí)間復(fù)雜度

• 算法時(shí)間復(fù)雜度定義
  算法時(shí)間復(fù)雜度：在進(jìn)行算法分析時(shí)，語句總的執(zhí)行次數(shù) T(n) 是關(guān)于問題規(guī)模n的函數(shù)，進(jìn)而分析 T(n) 隨 n 的變化情況并確定 T(n) 的數(shù)量級。算法的時(shí)間復(fù)雜度，也就是算法的時(shí)間量度，記作：T(n) = O(f(n))。它表示隨問題規(guī)模 n 的增大，算法執(zhí)行時(shí)間的增長率和 f(n) 的增長率相同，稱作算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱為時(shí)間復(fù)雜度。其中 f(n) 是問題規(guī)模 n 的某個(gè)函數(shù)。

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

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

• 常用的算法時(shí)間復(fù)雜度

  
  

• 推導(dǎo)大 O 階方法
  • 用常數(shù) 1 取代運(yùn)行時(shí)間中的所有加法常數(shù)
  • 在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)
  • 如果最高階項(xiàng)存在且不是 1，則去除與這個(gè)項(xiàng)相乘的常數(shù)。

得到的結(jié)果就是大 O 階。

2.6 算法空間復(fù)雜度

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

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

通常，我們都使用“時(shí)間復(fù)雜度”來指運(yùn)行時(shí)間的需求，使用“空間復(fù)雜度”指空間需求。當(dāng)不用限定詞地使用“復(fù)雜度”時(shí)，通常都是指時(shí)間復(fù)雜度。

三、線性表

3.1 線性表定義

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

首先它是一個(gè)序列。也就是說，元素之間是有順序的，若元素存在多個(gè)，則第一個(gè)元素?zé)o前驅(qū)，最后一個(gè)元素?zé)o后繼，其它元素都有且只有一個(gè)前驅(qū)一個(gè)后繼。

然后，線性表強(qiáng)調(diào)是有限的，即元素個(gè)數(shù)是有限的。

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

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

ADT線性表(List)
Data
線性表的數(shù)據(jù)對象集合為 (a1, a2, a3, ……, an)， 每個(gè)元素的類型均為 DataType。其中，除第一個(gè)元素外，每個(gè)元素有且只有一個(gè)直接前驅(qū)元素；除了最后一個(gè)元素外，每個(gè)元素有且只有一個(gè)直接后繼元素。數(shù)據(jù)元素之間的關(guān)系是一對一的關(guān)系。
Operation
InitList (*L) : 初始化操作，建立一個(gè)空的線性表L。
ListEmpty (L): 若線性表為空，返回 true，否則返回 false。
ClearList (*L): 將線性表清空。
GetElem (L, i, *e): 將線性表 L 中的第 i 個(gè)元素值返回給 e。
LocateElem (L, e): 在線性表 L 中查找與給定值 e 相等的元素，如果查找成功，返回該元素在表中序號表示成功；否則，返回 0 表示失敗。
ListInsert (*L, i, e):  在線性表 L 中的第 i 個(gè)位置插入新元素 e。
ListDelete (*L, i, *e): 刪除線性表 L 中第 i 個(gè)位置元素，并用 e 返回其值。
ListLength (L): 返回線性表 L 的元素個(gè)數(shù)。

endADT

對于不同的應(yīng)用，線性表的基本操作是不同的，上述操作是最基本的，對于實(shí)際問題中涉及的關(guān)于線性表的更復(fù)雜操作，完全可以用這些基本操作的組合來實(shí)現(xiàn)。

3.3 線性表的順序存儲結(jié)構(gòu)

3.3.1 順序存儲定義

先來看看線性表的兩種物理結(jié)構(gòu)的第一種——順序存儲結(jié)構(gòu)。

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

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

線性表的順序存儲

3.3.2 順序存儲方式

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

• 線性表順序存儲的結(jié)構(gòu)代碼：

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

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

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

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

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

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

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

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

3.3.4 地址計(jì)算方法

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

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

• 地址
  存儲器中的每個(gè)存儲單元都有自己的編號，這個(gè)編號稱為地址。

3.4 順序存儲結(jié)構(gòu)的插入和刪除

3.4.1 插入算法的思路

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

3.4.2 刪除算法的思路

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

3.4.3 插入和刪除的時(shí)間復(fù)雜度

• 先來看最好情況，如果元素要插入到最后一個(gè)位置，或者刪除最后一個(gè)元素，此時(shí)時(shí)間復(fù)雜度為O(1)，因?yàn)椴恍枰苿釉氐摹?/p>

• 最壞的情況，就是元素要插入到第一個(gè)位置，或者刪除第一個(gè)元素，此時(shí)所有元素都要移動，時(shí)間復(fù)雜度為 O(n)。

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

3.4.4 線性表順序存儲結(jié)構(gòu)的優(yōu)缺點(diǎn)

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

3.5 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

3.5.1 順序存儲結(jié)構(gòu)的不足

順序存儲結(jié)構(gòu)最大的缺點(diǎn)就是插入和刪除時(shí)需要移動大量元素，這顯然就需要耗費(fèi)時(shí)間。

3.5.2線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)定義

線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)是用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的。這就意味著，這些數(shù)據(jù)元素可以存在內(nèi)存未被占用的任意位置。

在順序結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素只需要存數(shù)據(jù)元素信息就可以了，但在鏈?zhǔn)浇Y(jié)構(gòu)中，除了要存數(shù)據(jù)元素信息外，還要存儲它的后繼元素的存儲地址。

為了表示每個(gè)數(shù)據(jù)元素 a(i) 與其直接后繼數(shù)據(jù)元素 a(i+1) 之間的邏輯關(guān)系，對數(shù)據(jù)元素a(i)來說，除了存儲其本身的信息之外，還需存儲一個(gè)指示其直接后繼的信息(即直接后繼的存儲位置)。我們把存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，把存儲直接后繼位置的域稱為指針域。指針域中存儲的信息稱作指針或鏈。這兩部分信息組成數(shù)據(jù)元素a(i)的存儲映像，稱為結(jié)點(diǎn)(Node)。

N 個(gè)結(jié)點(diǎn)鏈接成一個(gè)鏈表，即為線性表（a1，a2，…，a（n））的鏈?zhǔn)酱鎯Y(jié)構(gòu)，因?yàn)榇随湵淼拿總€(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，所以叫做單鏈表。單鏈表正是通過每個(gè)結(jié)點(diǎn)的指針域?qū)⒕€性表的數(shù)據(jù)元素按其邏輯次序鏈接在一起。如下圖所示：

對于線性表來說，總得有個(gè)頭有個(gè)尾，鏈表也不例外。我們把鏈表中第一個(gè)結(jié)點(diǎn)的存儲位置叫做頭指針，那么整個(gè)鏈表的存取就必須是從頭指針開始進(jìn)行了。之后的每一個(gè)結(jié)點(diǎn)，其實(shí)就是上一個(gè)的后繼指針指向的位置。最后一個(gè)結(jié)點(diǎn)指針為“空”，如下圖所示：

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

3.5.3 頭指針與頭結(jié)點(diǎn)的異同

• 頭指針

  • 頭指針是指鏈表指向第一個(gè)結(jié)點(diǎn)的指針，若鏈表有頭結(jié)點(diǎn)，則是指向頭結(jié)點(diǎn)的指針
  • 頭指針具有標(biāo)識作用，所以常用指針冠以鏈表的名字
  • 無論鏈表是否為空，頭指針均不為空，頭指針是鏈表的必要元素。

• 頭結(jié)點(diǎn)

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

3.6 單鏈表的讀取

在線性表的順序存儲結(jié)構(gòu)中，我們要計(jì)算任意一個(gè)元素的存儲位置是很容易的，但在單鏈表中，必須得從頭開始找。因此，對于單鏈表實(shí)現(xiàn)獲取第 i 個(gè)元素的數(shù)據(jù)的操作 GetElem ，在算法上，相對要麻煩一些。

• 獲得鏈表第 i 個(gè)數(shù)據(jù)的算法思路：
  1. 聲明一個(gè)結(jié)點(diǎn) p 指向鏈表第一個(gè)結(jié)點(diǎn)，初始化 j 從 1 開始；
  2. 當(dāng) j < i 時(shí)，就遍歷鏈表，讓 p 的指針向后移動，不斷指向下一結(jié)點(diǎn)，j 累加 1；
  3. 若到鏈表末尾 p 為空，則說明第 i 個(gè)元素不存在；
  4. 否則查找成功，返回結(jié)點(diǎn) p 的數(shù)據(jù)。

3.7 單鏈表的插入和刪除

3.7.1單鏈表的插入

假設(shè)存儲元素 e 的結(jié)點(diǎn)為 s，要實(shí)現(xiàn)結(jié)點(diǎn) p、p->next 和 s 之間邏輯關(guān)系的變化，只需將結(jié)點(diǎn) s 插入到結(jié)點(diǎn) p 和 p->next 之間即可。如何插入？

用不著驚動其它結(jié)點(diǎn)，只需讓 s->next 和 p->next 的指針做一點(diǎn)改變即可。

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

解讀代碼：讓 p 的后繼結(jié)點(diǎn)改成 s 的后繼結(jié)點(diǎn)，再把結(jié)點(diǎn) s 變成 p 的后繼結(jié)點(diǎn)。

• 單鏈表第 i 個(gè)數(shù)據(jù)插入結(jié)點(diǎn)的算法思路：
  1. 聲明一結(jié)點(diǎn) p 指向鏈表第一個(gè)結(jié)點(diǎn)，初始化 j 從 1 開始；
  2. 當(dāng) j < i 時(shí)，就遍歷鏈表，讓 p 的指針向后移動，不斷指向下一結(jié)點(diǎn)，j 累加 1；
  3. 若到鏈表末尾 p 為空，則說明第 i 個(gè)元素不存在；
  4. 否則查找成功，在系統(tǒng)中生成一個(gè)空結(jié)點(diǎn) s；
  5. 將數(shù)據(jù)元素 e 賦值給 s-> data；
  6. 單鏈表的插入標(biāo)準(zhǔn)語句 s->next = p->next; p->next=s；
  7. 返回成功

3.7.2單鏈表的刪除

假設(shè)存儲元素 a 的結(jié)點(diǎn)為 q，要實(shí)現(xiàn)結(jié)點(diǎn) q 刪除單鏈表的操作，其實(shí)就是將它的前繼結(jié)點(diǎn)的指針繞過，指向它的后繼結(jié)點(diǎn)即可。

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

解讀代碼：讓 p 的后繼結(jié)的后繼結(jié)點(diǎn)改成 p 的后繼結(jié)點(diǎn)。

• 單鏈表第 i 個(gè)數(shù)據(jù)刪除結(jié)點(diǎn)的算法思路：
  1. 聲明一結(jié)點(diǎn) p 指向鏈表第一個(gè)結(jié)點(diǎn)，初始化 j 從 1 開始；
  2. 當(dāng) j < i 時(shí)，就遍歷鏈表，讓 p 的指針向后移動，不斷指向下一個(gè)結(jié)點(diǎn)，j 累加 1；
  3. 若到鏈表末尾 p 為空，則說明第 i 個(gè)元素不存在；
  4. 否則查找成功，將欲刪除的結(jié)點(diǎn) p->next 賦值給 q；
  5. 單鏈表的刪除標(biāo)準(zhǔn)語句 p->next=q->next;
  6. 將 q 結(jié)點(diǎn)中的數(shù)據(jù)賦值給 e，作為返回；
  7. 釋放 q 結(jié)點(diǎn)；
  8. 返回成功。

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

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

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

所以創(chuàng)建單鏈表的過程就是一個(gè)動態(tài)生成鏈表的過程。即從“空表”的初始化狀態(tài)起，依次建立各元素結(jié)點(diǎn)，并逐個(gè)插入鏈表。

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

3.8.2 單鏈表的整表刪除

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

• 單鏈表整表刪除的算法思路：
  1. 聲明一結(jié)點(diǎn) p 和 q；
  2. 將第一個(gè)結(jié)點(diǎn)賦值給 p；
  3. 循環(huán)：將下一結(jié)點(diǎn)賦值給 q；釋放 p；將 q 賦值給 p。

3.9 單鏈表結(jié)構(gòu)與順序存儲結(jié)構(gòu)優(yōu)缺點(diǎn)

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

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