第3章算法與數(shù)據(jù)結(jié)構(gòu)

第3章算法與數(shù)據(jù)結(jié)構(gòu)

3.1緒論3.2線性表3.3棧和隊(duì)列3.4數(shù)組3.5樹與二叉樹3.6圖3.7查找技術(shù)3.8排序技術(shù)第3章算法與數(shù)據(jù)結(jié)構(gòu)3.1緒論程序=算法+數(shù)據(jù)結(jié)構(gòu)算法是指對操作的描述，即操作的步驟；數(shù)據(jù)結(jié)構(gòu)是指對數(shù)據(jù)的描述，即數(shù)據(jù)的類型和組織形式； 線性結(jié)構(gòu)：線性表、棧、隊(duì)列、數(shù)據(jù)的邏輯結(jié)構(gòu)字符串、數(shù)組、廣義表非線性結(jié)構(gòu)：樹、圖

順序存儲數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)鏈?zhǔn)酱鎯? 檢索、排序、數(shù)據(jù)的運(yùn)算插入、刪除、修改等

圖3-1數(shù)據(jù)結(jié)構(gòu)主要研究的三個(gè)方面問題3.1.1數(shù)據(jù)結(jié)構(gòu)的基本概念1.數(shù)據(jù)：是指用符號來描述客觀事物,包含數(shù)值、字符、圖形、圖像、聲音等。2.數(shù)據(jù)項(xiàng)：是指能用來描述數(shù)據(jù)的最小單位。3.數(shù)據(jù)元素(記錄)：是描述數(shù)據(jù)的基本單位，一個(gè)數(shù)據(jù)元素可以由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成。4.數(shù)據(jù)對象：是一類性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。數(shù)據(jù)結(jié)構(gòu)的基本概念5.數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指相互之間有關(guān)系的數(shù)據(jù)元素的集合。組成：數(shù)據(jù)和結(jié)構(gòu)數(shù)據(jù)：數(shù)據(jù)元素的集合；結(jié)構(gòu)：數(shù)據(jù)元素之間關(guān)系的集合。數(shù)據(jù)元素之間的關(guān)系：（1）集合結(jié)構(gòu)：所有數(shù)據(jù)元素“屬于同一個(gè)集合，關(guān)系松散。（2）線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在“一對一”的相鄰關(guān)系（3）樹狀結(jié)構(gòu)：數(shù)據(jù)元素之間存在“一對多”的層次關(guān)系（4）圖狀結(jié)構(gòu)：數(shù)據(jù)元素之間存在“多對多”的任意關(guān)系邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)分類：邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。（1）邏輯結(jié)構(gòu)：用數(shù)學(xué)模型來描述數(shù)據(jù)元素之間的邏輯關(guān)系一個(gè)數(shù)據(jù)的邏輯結(jié)構(gòu)包括兩個(gè)方面內(nèi)容：①數(shù)據(jù)元素的信息；②數(shù)據(jù)元素之間的前后關(guān)系（前驅(qū)和后繼）。表示方法：Data_Structure=（D，R）D為數(shù)據(jù)元素的有限集合，R為D上關(guān)系的有限集合例如，每周的數(shù)據(jù)結(jié)構(gòu)表示為：Week=(D,R)D={周一,周二,周三,周四,周五,周六,周日}R={(周一,周二),(周二,周三),(周三,周四),(周四,周五),(周五,周六),(周六,周日)}邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)(2)存儲結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)內(nèi)的存儲形式。分類：順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)等順序存儲結(jié)構(gòu)的特點(diǎn)：借助于數(shù)據(jù)元素在存儲器中的相鄰位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。即邏輯上相鄰的數(shù)據(jù)元素在物理存儲地址上也相鄰。鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)：使用一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素，借助于指示數(shù)據(jù)元素存儲地址的指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。即邏輯上相鄰的數(shù)據(jù)元素在物理存儲地址上不一定相鄰。另外還有索引存儲結(jié)構(gòu)和散列存儲結(jié)構(gòu)，但是它們都是通過順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)復(fù)合而成。數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)不可分開的兩個(gè)方面。一方面，數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的抽象；另一方面，數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)在進(jìn)行數(shù)據(jù)處理時(shí)候，一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以依據(jù)需要而采用多種不同的存儲結(jié)構(gòu)，只要能反映出所要求的邏輯關(guān)系即可。但是，選用其中最合適的存儲結(jié)構(gòu)對于提高數(shù)據(jù)處理的效率是非常重要的。

3.1.2算法

1.算法的定義算法：是問題求解邏輯步驟的一種準(zhǔn)確而完整地描述。同一個(gè)算法如果采用不同的編程語言能夠編寫出不同的程序，所以，算法不等于程序，程序的編寫也絕不可能優(yōu)于算法的設(shè)計(jì)。描述算法的工具：自然語言、傳統(tǒng)流程圖、N-S流程圖、偽代碼、類計(jì)算機(jī)語言、計(jì)算機(jī)語言。

2.算法的基本特性

（1）有窮性：一個(gè)算法應(yīng)包含有限的操作步驟（2）確定性：一個(gè)算法中的每一步驟必須有確定的含義，不能是含糊不清的。并且算法只有一個(gè)入口和一個(gè)出口。（3）可行性：一個(gè)算法應(yīng)可以有效地執(zhí)行（4）輸入：一個(gè)算法有零個(gè)或多個(gè)外部輸入。零個(gè)輸入是指算法本身具有初始條件。（5）輸出：一個(gè)算法至少要有一個(gè)輸出。3.算法的基本要素兩個(gè)基本要素：（1）算法中對數(shù)據(jù)對象的運(yùn)算和操作：算法中基本的運(yùn)算和操作包括算術(shù)運(yùn)算、關(guān)系運(yùn)算、邏輯運(yùn)算和數(shù)據(jù)傳輸。（2）算法的控制結(jié)構(gòu)：是指算法中各個(gè)操作之間的先后執(zhí)行次序。一個(gè)算法的執(zhí)行次序可以使用順序、選擇和循環(huán)三種基本結(jié)構(gòu)組合而成。

4.算法設(shè)計(jì)的基本方法

（1）列舉法：根據(jù)實(shí)際問題，列舉出所有可能的情況（2）歸納法：通過對特殊的情況進(jìn)行歸納分析后找出一般的關(guān)系。（3）遞推法：從已知的條件逐漸推出結(jié)果。它也屬于歸納法。（4）遞歸法：先將復(fù)雜問題逐層分解（即回推）成最簡單的問題，當(dāng)解決了最簡單的問題后，再沿著原來分解的逆過程逐步回歸（即遞推）以便解決復(fù)雜問題（5）減半遞推法：將復(fù)雜問題的規(guī)模減少一半，并且重復(fù)進(jìn)行減半的過程。

5.算法的評價(jià)

（1）正確性：根據(jù)算法編寫的程序能夠得到滿足問題要求的結(jié)果。（2）可讀性：算法首先應(yīng)是便于理解、其次才是計(jì)算機(jī)可以執(zhí)行。（3）健壯性：輸入不合法數(shù)據(jù)時(shí)算法能作出相應(yīng)的處理，而不是陷入癱瘓。（4）高效率：根據(jù)算法編寫的程序有較快的運(yùn)算速度。（5）低存儲量：根據(jù)算法編寫的程序在運(yùn)行時(shí)占用較少的存儲空間。6.算法的復(fù)雜度（1）算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度：是指執(zhí)行算法所需要的計(jì)算工作量。算法的計(jì)算工作量應(yīng)使用算法在執(zhí)行過程中的基本運(yùn)算執(zhí)行次數(shù)來度量。算法執(zhí)行的基本運(yùn)算次數(shù)與問題的規(guī)模有關(guān)例如，兩個(gè)30階矩陣相乘的基本運(yùn)算次數(shù)一定大于兩個(gè)5階矩陣相乘的基本運(yùn)算次數(shù)。算法的復(fù)雜度（2）算法的空間復(fù)雜度

算法的空間復(fù)雜度：是指執(zhí)行算法所需存儲空間的度量。它包括算法程序占用的存儲空間、輸入的原始數(shù)據(jù)占用的存儲空間和執(zhí)行算法所需額外占用的存儲空間（如在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，既要存儲數(shù)據(jù)又要額外存儲鏈接地址以便來表示數(shù)據(jù)元素之間的關(guān)系）。

3.2線性表

3.2.1線性表的基本概念線性表是最簡單的一種數(shù)據(jù)結(jié)構(gòu)，它是由一組數(shù)據(jù)元素組成。一年的月份號（1，2，3，…，12）是一個(gè)線性表，每個(gè)數(shù)據(jù)元素是一個(gè)整型數(shù)。英文小寫字母表（a，b，c，…，z）是一個(gè)線性表，每個(gè)數(shù)據(jù)元素是一個(gè)小寫字母。學(xué)生成績表也是一個(gè)線性表，每個(gè)數(shù)據(jù)元素是由學(xué)號、姓名、數(shù)學(xué)、外語、計(jì)算機(jī)等數(shù)據(jù)項(xiàng)組成。

線性表的基本概念

綜上所述，線性表是由n（n≥0）個(gè)類型相同的數(shù)據(jù)元素a1，a2，…，ai-1，ai，ai+1，…，an組成的有限序列。一般可以表示為：L=（a1，a2，…，ai-1，ai，ai+1，…，an）其中，L稱為線性表的名稱。n稱為線性表的長度。當(dāng)n=0時(shí)稱為空線性表。非空線性表的特征①有且只有一個(gè)根結(jié)點(diǎn)，它沒有前驅(qū)結(jié)點(diǎn)。②有且只有一個(gè)終端結(jié)點(diǎn)，它沒有后繼結(jié)點(diǎn)③除根結(jié)點(diǎn)和終端結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且只有一個(gè)直接前驅(qū)結(jié)點(diǎn)，有且只有一個(gè)直接后繼結(jié)點(diǎn)。

3.2.2線性表的順序存儲及其基本運(yùn)算

在計(jì)算機(jī)中存放線性表，主要有兩種基本存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。順序存儲結(jié)構(gòu)：把線性表中邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素依次存放在計(jì)算機(jī)內(nèi)一組物理地址連續(xù)的存儲單元中，即把邏輯關(guān)系上相鄰接的數(shù)據(jù)元素存儲在物理地址也相鄰接的存儲單元之中。順序表：用順序存儲結(jié)構(gòu)來存儲的線性表。順序表具有的兩個(gè)基本特點(diǎn)：（1）順序表的所有數(shù)據(jù)元素所占的存儲空間是連續(xù)的；（2）順序表的各個(gè)數(shù)據(jù)元素在存儲空間中是按照邏輯順序依次存放的。線性表的順序存儲假設(shè)長度為n的順序表（a1，a2，…，ai-1，ai，ai+1，…，an）中每個(gè)數(shù)據(jù)元素所占的存儲空間相同（假設(shè)都為k字節(jié)），并且第i個(gè)數(shù)據(jù)元素ai的存儲地址用Address（ai）表示，順序表中第i個(gè)數(shù)據(jù)元素ai在計(jì)算機(jī)存儲空間中的存儲地址可以表示為：Address（ai）=Address（a1）+（i-1）*k（1≤i≤n）若知道順序表的起始地址Address（a1）和每個(gè)數(shù)據(jù)元素所占的字節(jié)數(shù)k，則順序表中任意一個(gè)數(shù)據(jù)元素都可隨機(jī)存取。順序表的存儲結(jié)構(gòu)是一個(gè)隨機(jī)存取的存儲結(jié)構(gòu)。1.順序表的插入運(yùn)算（1）在通常情況下，若在第i（1≤i≤n+1）個(gè)數(shù)據(jù)元素之前插入一個(gè)新的數(shù)據(jù)元素時(shí)，要從最后一個(gè)（即第n個(gè)）數(shù)據(jù)元素開始，直到第i個(gè)數(shù)據(jù)元素之間共n-i+1個(gè)數(shù)據(jù)元素依次向后移動(dòng)一個(gè)位置。（2）在特殊情況下，若要在順序表第一個(gè)數(shù)據(jù)元素之前插入一個(gè)新的數(shù)據(jù)元素，則需要依次向后移動(dòng)表中所有的n個(gè)數(shù)據(jù)元素若要在順序表最后一個(gè)數(shù)據(jù)元素之后插入一個(gè)新的數(shù)據(jù)元素，只要在表的末尾后面增加一個(gè)新的數(shù)據(jù)元素即可。（3）在平均情況下，插入一個(gè)新的數(shù)據(jù)元素需要移動(dòng)表中一半的數(shù)據(jù)元素。數(shù)據(jù)元素的移動(dòng)消耗很多時(shí)間，因此順序表的插入運(yùn)算效率低。2.順序表的刪除運(yùn)算（1）在通常情況下，若要在第i（1≤i≤n）個(gè)位置上刪除一個(gè)數(shù)據(jù)元素時(shí)，要從第i+1個(gè)數(shù)據(jù)元素開始，直到最后一個(gè)數(shù)據(jù)元素依次向前移動(dòng)一個(gè)位置。（2）在特殊情況下，若要?jiǎng)h除第一個(gè)數(shù)據(jù)元素，則需要依次向前移動(dòng)表中所有其它的數(shù)據(jù)元素；若要?jiǎng)h除最后一個(gè)數(shù)據(jù)元素，只要?jiǎng)h除表中末尾一個(gè)數(shù)據(jù)元素即可。（3）在平均情況下，刪除一個(gè)數(shù)據(jù)元素需要移動(dòng)表中一半的數(shù)據(jù)元素。數(shù)據(jù)元素的移動(dòng)消耗很多時(shí)間，因此順序表的刪除運(yùn)算效率低

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

（1）優(yōu)點(diǎn)：存儲的物理位置相鄰，不需要增加額外的存儲空間可以根據(jù)初始地址隨機(jī)存取線性表中任一數(shù)據(jù)元素運(yùn)算簡單方便，存儲空間緊湊，占用最少存儲空間（2）缺點(diǎn)：進(jìn)行插入、刪除操作時(shí)需要移動(dòng)大量的數(shù)據(jù)元素，消耗許多處理時(shí)間；由于占用連續(xù)存儲空間，只能進(jìn)行預(yù)先靜態(tài)分配，若開辟的存儲空間太大，造成存儲空間浪費(fèi)，若開辟的存儲空間小，當(dāng)分配的存儲空間已滿時(shí)，再插入數(shù)據(jù)就會(huì)發(fā)生“上溢”錯(cuò)誤，不便于擴(kuò)充；由于使用相鄰整塊存儲單元，會(huì)產(chǎn)生較多的碎片。結(jié)論：線性表的順序存儲結(jié)構(gòu)不適用于大線性表或者其中數(shù)據(jù)元素經(jīng)常變動(dòng)的線性表。適合于主要是進(jìn)行查找而很少做插入和刪除操作。

3.2.3線性表的鏈?zhǔn)酱鎯捌浠具\(yùn)算

鏈?zhǔn)酱鎯Y(jié)構(gòu)：使用一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素，借助于指示數(shù)據(jù)元素存儲地址的指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。即邏輯上相鄰的數(shù)據(jù)元素在物理存儲地址上不一定相鄰。線性鏈表：用鏈?zhǔn)酱鎯Y(jié)構(gòu)來存儲的線性表簡稱為鏈表。根據(jù)鏈接的方式把鏈表分為單鏈表、雙鏈表和循環(huán)鏈表等。鏈表適合于頻繁地進(jìn)行插入和刪除操作。

1．單鏈表

每個(gè)結(jié)點(diǎn)的存儲空間被分為兩個(gè)部分。數(shù)據(jù)域：存儲結(jié)點(diǎn)的值；指針域：存儲指向直接后繼的指針（地址）。所有的結(jié)點(diǎn)通過指針（地址）的連接按其邏輯順序鏈接在一起而組成了鏈表。線性單鏈表：每一個(gè)結(jié)點(diǎn)只包含一個(gè)指針域。頭指針（HEAD）：為了增強(qiáng)程序的可讀性，在線性單鏈表中增加一個(gè)指針指向鏈表的第一個(gè)結(jié)點(diǎn)。最后一個(gè)結(jié)點(diǎn)由于沒有直接后繼結(jié)點(diǎn)，則它的指針域值為空(用NULL、0或∧表示)，表示鏈表終止。由于任意一個(gè)結(jié)點(diǎn)的存取都必須從頭指針出發(fā)，順著鏈域逐個(gè)結(jié)點(diǎn)往下進(jìn)行，所以單鏈表是順序存取的存儲結(jié)構(gòu)。

（1）建立線性單鏈表

建立線性單鏈表①頭插法建立線性單鏈表：從空鏈表開始，每次申請生成一個(gè)新的結(jié)點(diǎn)，將讀入的數(shù)據(jù)存放到數(shù)據(jù)域，并設(shè)置指針域?yàn)榭?。然后將新結(jié)點(diǎn)插入到鏈表頭結(jié)點(diǎn)的后面，即新結(jié)點(diǎn)的指針域存儲原來頭結(jié)點(diǎn)指針域存放的指針，再將頭結(jié)點(diǎn)的指針域存儲指向新結(jié)點(diǎn)的指針（或存儲地址），重復(fù)以上的操作，直到讀入的數(shù)據(jù)為結(jié)束標(biāo)志。使用頭插法建立線性單鏈表時(shí)，結(jié)點(diǎn)的邏輯順序與輸入數(shù)據(jù)元素的順序相反。

（1）建立線性單鏈表

建立線性單鏈表②尾插法建立線性單鏈表：從空鏈表開始，每次申請生成一個(gè)新的結(jié)點(diǎn)，將讀入的數(shù)據(jù)存放到數(shù)據(jù)域，并設(shè)置指針域?yàn)榭?。然后將新結(jié)點(diǎn)插入到鏈表尾結(jié)點(diǎn)的后面，即原來鏈表尾結(jié)點(diǎn)的指針域存儲指向新結(jié)點(diǎn)的指針（或存儲地址），此時(shí)新結(jié)點(diǎn)轉(zhuǎn)變?yōu)樾碌奈步Y(jié)點(diǎn)，重復(fù)以上操作，直到讀入的數(shù)據(jù)為結(jié)束標(biāo)志。使用尾插法建立線性單鏈表時(shí)，結(jié)點(diǎn)的邏輯順序與輸入數(shù)據(jù)元素的順序相同

（2）線性單鏈表的查找

①按照值進(jìn)行查找：從線性單鏈表的頭指針出發(fā)，順著鏈表逐個(gè)將結(jié)點(diǎn)數(shù)據(jù)域的值和要查找的給定值作比較。實(shí)際應(yīng)用中，為了便于操作，需要在線性單鏈表中查找包含給定值x元素的前一結(jié)點(diǎn)存儲位置（用指針pre指向），可以方便地在該結(jié)點(diǎn)后插入新的結(jié)點(diǎn)或者刪除該結(jié)點(diǎn)后的結(jié)點(diǎn)。查找的結(jié)果如下：若單鏈表中存在要查找的給定值，則返回的（pre）為第一次找到的包含給定值x元素的前一結(jié)點(diǎn)位置；若單鏈表中不存在要查找的給定值，則返回的(pre)為單鏈表的最后結(jié)點(diǎn)位置。線性單鏈表的查找②按照序號進(jìn)行查找：從線性單鏈表的頭指針出發(fā)，順著鏈表逐個(gè)結(jié)點(diǎn)往下掃描直到第i個(gè)結(jié)點(diǎn)為止。實(shí)際應(yīng)用中，為了便于操作，在線性單鏈表中查找第i個(gè)結(jié)點(diǎn)的前一結(jié)點(diǎn)存儲位置（用指針pre指向），就可以方便地在該結(jié)點(diǎn)后插入新的結(jié)點(diǎn)或者刪除該結(jié)點(diǎn)后的結(jié)點(diǎn)。查找的結(jié)果：查找到結(jié)點(diǎn)（1≤i≤n），則返回的（pre）為第i個(gè)結(jié)點(diǎn)的前一結(jié)點(diǎn)位置；沒查找到返回的(pre)為單鏈表的最后結(jié)點(diǎn)位置.

（3）線性單鏈表的插入

線性單鏈表的插入：在線性單鏈表中插入一個(gè)新的數(shù)據(jù)元素。①按照值進(jìn)行插入：是在線性單鏈表中指定值數(shù)據(jù)元素之前插入一個(gè)新數(shù)據(jù)元素。運(yùn)算過程：1）申請新結(jié)點(diǎn)：生成一個(gè)新結(jié)點(diǎn)，輸入數(shù)據(jù)存放到數(shù)據(jù)域；2）查找：在單鏈表中查找包含給定值x元素的前一結(jié)點(diǎn)存儲位置（用指針pre指向）；3）修改鏈接：首先設(shè)置新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)x，然后再設(shè)置x前一結(jié)點(diǎn)的指針域指向新結(jié)點(diǎn)。線性單鏈表的插入②按照序號進(jìn)行插入：是指在線性單鏈表中第i個(gè)結(jié)點(diǎn)之前插入一個(gè)新的結(jié)點(diǎn)。運(yùn)算過程：1）申請新結(jié)點(diǎn)：生成一個(gè)新結(jié)點(diǎn)，輸入數(shù)據(jù);2）查找：在單鏈表中查找第i個(gè)結(jié)點(diǎn)之前的結(jié)點(diǎn)ai-1的存儲位置（用指針pre指向）；3）修改鏈接：首先設(shè)置新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)ai，再設(shè)置結(jié)點(diǎn)ai-1的指針域指向新結(jié)點(diǎn)（注意，在程序設(shè)計(jì)時(shí)此順序不能顛倒）。在線性單鏈表的插入過程中，不需要移動(dòng)數(shù)據(jù)元素，只要改變相關(guān)結(jié)點(diǎn)的指針就可以實(shí)現(xiàn)，提高了效率。

（4）線性單鏈表的刪除

線性單鏈表的刪除:是指在線性單鏈表中刪除一個(gè)數(shù)據(jù)元素。①按照值進(jìn)行刪除：是指在線性單鏈表中刪除指定值的數(shù)據(jù)元素。運(yùn)算過程：1）查找：在單鏈表中查找包含給定值x元素的前一結(jié)點(diǎn)存儲位置，用指針pre指向；2）修改鏈接：設(shè)置x的前一結(jié)點(diǎn)指向x的直接后繼結(jié)點(diǎn)；3）釋放結(jié)點(diǎn)：釋放結(jié)點(diǎn)x所占用的存儲空間。

線性單鏈表的刪除

②按照序號進(jìn)行刪除：是指在線性單鏈表中刪除第i個(gè)結(jié)點(diǎn)。運(yùn)算過程：1）查找：在單鏈表中查找第i個(gè)結(jié)點(diǎn)之前的結(jié)點(diǎn)ai-1的存儲位置（用指針pre指向）；2）修改鏈接：設(shè)置ai-1指向ai的直接后繼結(jié)點(diǎn)ai+1，即把a(bǔ)i-1的指針域改變?yōu)榇娣沤Y(jié)點(diǎn)ai指針域的值（為ai+1的存儲地址），就能把結(jié)點(diǎn)ai從鏈上摘下；3）釋放結(jié)點(diǎn)：最后釋放結(jié)點(diǎn)ai所占用的存儲空間鏈表的優(yōu)缺點(diǎn)：①優(yōu)點(diǎn):在鏈表中進(jìn)行插入、刪除操作時(shí)只需要修改指針而不需要移動(dòng)表中的數(shù)據(jù)元素.適合對于頻繁進(jìn)行插入、刪除操作的線性表；②缺點(diǎn):對鏈表中的數(shù)據(jù)元素只能順著鏈表進(jìn)行順序存取而不能進(jìn)行隨機(jī)存取。

2．雙鏈表

在線性單鏈表中，指針可以很方便地找到后繼結(jié)點(diǎn)，但是卻不能找到前驅(qū)結(jié)點(diǎn)；在線性單鏈表的每個(gè)結(jié)點(diǎn)中再增加一個(gè)指針域用來指向該結(jié)點(diǎn)的直接前驅(qū)。每個(gè)結(jié)點(diǎn)包含兩個(gè)指針指向直接前驅(qū)結(jié)點(diǎn)的指針稱為左指針(llink)，指向直接后繼結(jié)點(diǎn)的指針稱為右指針(rlink)，由此形成的線性鏈表就有兩個(gè)不同方向的鏈，則稱為雙向鏈表，簡稱為雙鏈表（doublelinkedlist）。3．循環(huán)鏈表將單鏈表中最后一個(gè)結(jié)點(diǎn)的指針域由空（NULL）改變?yōu)橹赶蝾^結(jié)點(diǎn)而使鏈表頭尾相接形成環(huán)狀，稱為單向循環(huán)鏈表，簡稱為循環(huán)鏈表（circularlinkedlist）。在單向循環(huán)鏈表中，只是對表的鏈接方式稍微改變一些，就使得可以從任意一個(gè)結(jié)點(diǎn)出發(fā)來訪問表中所有其它的結(jié)點(diǎn)，提高了查找的效率。而線性單鏈表卻做不到這一點(diǎn)。

循環(huán)鏈表

循環(huán)鏈表的特點(diǎn)：①循環(huán)鏈表增加一個(gè)頭結(jié)點(diǎn)，其數(shù)據(jù)域可以依據(jù)需要設(shè)置，其指針域指向第一個(gè)結(jié)點(diǎn)。即循環(huán)鏈表的頭指針HEAD指向頭結(jié)點(diǎn)，而頭結(jié)點(diǎn)指向第一個(gè)結(jié)點(diǎn)；②循環(huán)鏈表最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)而不是空。

3.3棧和隊(duì)列

3.3.1棧及其基本運(yùn)算1．棧的基本概念棧（stack）是一種特殊的線性表，它是限定僅在一端進(jìn)行插入或刪除操作的線性表。允許進(jìn)行插入或刪除操作的一端稱為棧頂（top）；不允許進(jìn)行插入、刪除操作的另一端稱為棧底（bottom）。不含數(shù)據(jù)元素的棧稱為空棧。棧是根據(jù)“先進(jìn)后出或“后進(jìn)先出”的原則組織數(shù)據(jù)。向棧中插入一個(gè)數(shù)據(jù)元素稱為入棧；從棧中刪除一個(gè)數(shù)據(jù)元素稱為退棧。

2．棧的順序存儲及其基本運(yùn)算棧的順序存儲結(jié)構(gòu)的基本運(yùn)算：入棧運(yùn)算、退棧運(yùn)算、讀棧運(yùn)算。（1）順序棧的入棧運(yùn)算順序棧的入棧運(yùn)算是指在棧頂位置插入一個(gè)新的數(shù)據(jù)元素。運(yùn)算過程：①修改指針：將棧頂指針加1（top加1）；②插入；在當(dāng)前棧頂指針?biāo)赶虻奈恢脤⑿碌臄?shù)據(jù)元素插入。在順序棧的入棧運(yùn)算過程中，若棧頂指針已經(jīng)指向棧存儲空間的最后位置（即top=n），表明此時(shí)棧的空間已滿，不能再進(jìn)行入棧運(yùn)算，否則會(huì)產(chǎn)生棧的上溢錯(cuò)誤。

棧的順序存儲及其基本運(yùn)算

（2）順序棧的退棧運(yùn)算順序棧的退棧運(yùn)算是指在棧頂位置取走一個(gè)數(shù)據(jù)元素并且把它賦給某個(gè)變量。運(yùn)算過程：①退棧：將棧頂指針?biāo)赶虻臈ｍ斣刈x取后并且賦給一個(gè)變量；②修改指針：將棧頂指針減1（top減1）。在順序棧的退棧運(yùn)算過程中，若棧頂指針已經(jīng)為0時(shí)（即top=0），表明此時(shí)?？?，不能再進(jìn)行退棧運(yùn)算，否則會(huì)產(chǎn)生棧的下溢錯(cuò)誤。

棧的順序存儲及其基本運(yùn)算

（3）順序棧的讀棧運(yùn)算順序棧的讀棧運(yùn)算是指在棧頂位置讀取一個(gè)數(shù)據(jù)元素并且把它賦給某個(gè)變量。運(yùn)算過程：將棧頂指針?biāo)赶虻臈ｍ斣刈x取并賦給一個(gè)變量，棧頂指針保持不變。在順序棧的讀棧運(yùn)算過程中，若棧頂指針已經(jīng)為0時(shí)（即top=0），表明此時(shí)?？眨荒茉龠M(jìn)行讀棧運(yùn)算，即讀不到棧頂元素。

3．棧的鏈?zhǔn)酱鎯捌浠具\(yùn)算

與一般的線性表類似，在程序設(shè)計(jì)時(shí)，棧也可以使用鏈?zhǔn)酱鎯Y(jié)構(gòu)。用鏈?zhǔn)酱鎯Y(jié)構(gòu)來存儲的棧，稱為帶鏈的棧，簡稱為鏈棧。它其實(shí)就是運(yùn)算受限的單鏈表，其插入和刪除操作僅限制在鏈表的表頭位置上進(jìn)行，所以，棧頂指針就是鏈表的頭指針，頭指針指向棧頂結(jié)點(diǎn)（不帶頭結(jié)點(diǎn)）或者頭結(jié)點(diǎn)（帶頭結(jié)點(diǎn)）。

3.3.2隊(duì)列及其基本運(yùn)算

1．隊(duì)列的基本概念隊(duì)列也是一種特殊的線性表，它是限定在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表。其中，允許進(jìn)行插入操作的一端稱為隊(duì)尾，允許進(jìn)行刪除操作的另一端稱為隊(duì)頭。不含數(shù)據(jù)元素的隊(duì)列稱為空隊(duì)列。隊(duì)列是根據(jù)“先進(jìn)先出或“后進(jìn)后出的原則組織數(shù)據(jù)，一般用隊(duì)頭指針（front）指向隊(duì)頭位置數(shù)據(jù)元素的前一個(gè)單元，用隊(duì)尾指針（rear）指向隊(duì)尾位置數(shù)據(jù)元素。向隊(duì)列中插入一個(gè)數(shù)據(jù)元素稱為入隊(duì)，插入的結(jié)點(diǎn)只能加到隊(duì)尾。從隊(duì)列中刪除一個(gè)數(shù)據(jù)元素稱為退隊(duì)，刪除的結(jié)點(diǎn)只能來自隊(duì)頭位置。

2．隊(duì)列的順序存儲及其運(yùn)算

與一般的線性表類似，在程序設(shè)計(jì)時(shí)，可以使用一維數(shù)組作為隊(duì)列的順序存儲空間。用順序存儲結(jié)構(gòu)來存儲的隊(duì)列簡稱為順序隊(duì)列。隊(duì)列的順序存儲結(jié)構(gòu)可以采用循環(huán)隊(duì)列的形式。將順序存儲的隊(duì)列的最后一個(gè)位置指向第一個(gè)位置，從而使順序隊(duì)列形成邏輯上的環(huán)狀空間，稱為循環(huán)隊(duì)列。當(dāng)循環(huán)隊(duì)列的最后一個(gè)位置已經(jīng)被使用而還要進(jìn)行入隊(duì)運(yùn)算時(shí)，此時(shí)只要第一個(gè)位置空閑，就可以將數(shù)據(jù)元素插入到第一個(gè)位置，即將第一個(gè)位置作為新的隊(duì)尾。可以設(shè)置n表示循環(huán)隊(duì)列的最大存儲空間。循環(huán)隊(duì)列在循環(huán)隊(duì)列中，從隊(duì)頭指針front指向的下一個(gè)位置到隊(duì)尾指針rear指向的隊(duì)尾位置之間的所有數(shù)據(jù)元素都是隊(duì)列中的數(shù)據(jù)元素。循環(huán)隊(duì)列具有兩種基本運(yùn)算：入隊(duì)運(yùn)算、退隊(duì)運(yùn)算。循環(huán)隊(duì)列的初始狀態(tài)為空，此時(shí)front=rear=n。循環(huán)隊(duì)列進(jìn)行一次退隊(duì)運(yùn)算，隊(duì)頭指針front就加1，若front=n+1時(shí)，則設(shè)置front=1。循環(huán)隊(duì)列進(jìn)行一次入隊(duì)運(yùn)算，隊(duì)尾指針rear就加1，若rear=n+1時(shí)，則設(shè)置rear=1。由于在循環(huán)隊(duì)列中，循環(huán)隊(duì)列為空或滿都有front=rear，即根據(jù)front=rear不能判定隊(duì)列是空還是滿，一般還要增加一個(gè)標(biāo)志sign，用sign=0表示隊(duì)列空；用sign=1且front=rear表示隊(duì)列滿。

循環(huán)隊(duì)列的兩種基本運(yùn)算

（1）循環(huán)隊(duì)列的入隊(duì)運(yùn)算循環(huán)隊(duì)列的入隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)尾位置插入一個(gè)新的數(shù)據(jù)元素。運(yùn)算過程：①修改隊(duì)尾：將隊(duì)尾加1（即rear=rear+1），此時(shí)若rear=n+1則設(shè)置rear=1；②結(jié)點(diǎn)插入：將新結(jié)點(diǎn)插入到將隊(duì)尾指針?biāo)赶虻奈恢?。?dāng)sign=1并且rear=front，循環(huán)隊(duì)列空間已滿，就不能進(jìn)行入隊(duì)，否則會(huì)產(chǎn)生上溢錯(cuò)誤。（2）循環(huán)隊(duì)列的退隊(duì)運(yùn)算。循環(huán)隊(duì)列的退隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)頭位置退出一個(gè)數(shù)據(jù)元素并且保存在指定的變量中。運(yùn)算過程：①修改隊(duì)頭：先將隊(duì)頭加1（即front=front+1），此時(shí)若front=n+1則設(shè)置front=1；②結(jié)點(diǎn)退出保存：將隊(duì)頭指針?biāo)赶蛭恢玫臄?shù)據(jù)元素退出并且賦給一個(gè)指定變量。當(dāng)sign=0時(shí)循環(huán)隊(duì)列為空，就不能進(jìn)行退隊(duì)，否則會(huì)產(chǎn)生下溢錯(cuò)誤。

3.4數(shù)組

3.4.1數(shù)組的基本概念數(shù)組是一種特殊的線性表，它的數(shù)據(jù)元素自身也是一個(gè)線性表。在科學(xué)計(jì)算中，矩陣是一種常用的數(shù)學(xué)對象，在使用高級語言編寫程序時(shí)，一般將一個(gè)矩陣描述為一個(gè)二維數(shù)組。所以在此主要研究二維數(shù)組。因?yàn)橛?jì)算機(jī)的內(nèi)存空間是一維結(jié)構(gòu)，而數(shù)組是多維結(jié)構(gòu)，所以使用計(jì)算機(jī)的內(nèi)存單元存儲數(shù)組元素存在次序問題。二維數(shù)組有兩種存儲次序：以行為主序的順序存儲和以列為主序的順序存儲。

3.4.2數(shù)組的存儲結(jié)構(gòu)

以行為主序的順序存儲是將數(shù)組中的數(shù)據(jù)元素從第一行開始一行接一行地順序存儲在計(jì)算機(jī)內(nèi)連續(xù)的存儲空間中。以列為主序的順序存儲是將數(shù)組中的數(shù)據(jù)元素從第一列開始一列接一列地順序存儲在計(jì)算機(jī)內(nèi)連續(xù)的存儲空間中。例如，C語言的數(shù)組在計(jì)算機(jī)中采用以行為主序的順序存儲方式。在二維數(shù)組以行為主序的順序存儲中，數(shù)據(jù)元素aij在一維內(nèi)存空間中存儲地址為：Address(aij)=Address(a11)+[(i-1)*n+j-1]k其中，Address(a11)為二維數(shù)組中第一個(gè)數(shù)據(jù)元素的存儲地址，每個(gè)數(shù)據(jù)k字節(jié),n為列數(shù)。

3.5樹與二叉樹

樹是一類非線性數(shù)據(jù)結(jié)構(gòu)，其中最為常用的是二叉樹。使用圖形來表示樹這樣的數(shù)據(jù)結(jié)構(gòu)時(shí)，很像是自然界中一棵倒長的樹。在現(xiàn)實(shí)生活中，有許多能用樹的結(jié)構(gòu)表示的關(guān)系：人類家族的血緣關(guān)系、銀行的行政關(guān)系、書目錄的層次關(guān)系等。3.5.1樹的基本概念樹（tree）是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，在任意一棵非空樹中：①有且僅有一個(gè)結(jié)點(diǎn)稱為樹的根（root）；②其余n-1個(gè)結(jié)點(diǎn)被分成為m（m≥0）個(gè)互相不相交的有限集合，其中每一個(gè)集合自身又是一棵樹，稱為根結(jié)點(diǎn)的子樹（subtree）。樹的定義是一個(gè)遞歸定義。樹的基本概念在樹的結(jié)構(gòu)中，樹中的每個(gè)數(shù)據(jù)元素也稱為結(jié)點(diǎn)?？煞譃楦Y(jié)點(diǎn)、分支結(jié)點(diǎn)和葉子結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)的上一層結(jié)點(diǎn)稱為該結(jié)點(diǎn)的雙親結(jié)點(diǎn)。沒有雙親的結(jié)點(diǎn)稱為樹的根。每個(gè)結(jié)點(diǎn)的下一層結(jié)點(diǎn)稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)擁有的子樹數(shù)目稱為該結(jié)點(diǎn)的度。所有結(jié)點(diǎn)的度中最大的值稱為樹的度。樹中度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。從根結(jié)點(diǎn)開始到某結(jié)點(diǎn)的層數(shù)稱為該結(jié)點(diǎn)的深度。所有結(jié)點(diǎn)的層數(shù)中最大的值稱為樹的深度。若樹中結(jié)點(diǎn)的各棵子樹是從左至右有先后次序的，則稱該樹為有序樹，否則稱為無序樹。

3.5.2二叉樹及其基本性質(zhì)

由于對二叉樹的操作算法相對簡單，所以二叉樹在樹結(jié)構(gòu)的實(shí)際應(yīng)用中起著重要的作用，它解決了樹的存儲結(jié)構(gòu)及其運(yùn)算中的復(fù)雜性問題。1．什么是二叉樹二叉樹是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合。它或者為空集，或者是由一個(gè)根結(jié)點(diǎn)加上兩棵互相不相交的左子樹和右子樹組成，并且左子樹和右子樹也都是二叉樹。二叉樹的特點(diǎn)：①二叉樹的每個(gè)結(jié)點(diǎn)至多有二棵子樹（即不存在度大于2的結(jié)點(diǎn)）。②二叉樹的子樹分為左子樹、右子樹，其次序也不能任意顛倒互換。

2．二叉樹的基本性質(zhì)

性質(zhì)1：在二叉樹的第i（i≥1）層上，至多有2i-1個(gè)結(jié)點(diǎn)。性質(zhì)2：在深度為k（k≥1）的二叉樹上，至多有2k-1個(gè)結(jié)點(diǎn)。性質(zhì)3：在任意一棵二叉樹中，葉子結(jié)點(diǎn)的數(shù)目總比度為2的結(jié)點(diǎn)數(shù)目多一個(gè)。性質(zhì)4：在具有n個(gè)結(jié)點(diǎn)的一棵二叉樹中，其深度至少為【log2n】＋1。其中【log2n】為取log2n的整數(shù)部分

二叉樹的基本性質(zhì)

滿二叉樹除最后一層葉子結(jié)點(diǎn)以外的各層任何結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)，并且所有的葉子結(jié)點(diǎn)都在同一層上。就是說滿二叉樹中的每一層的結(jié)點(diǎn)數(shù)都達(dá)到了最大值。完全二叉樹除最后一層外，每一層結(jié)點(diǎn)數(shù)都達(dá)到最大值；最后一層結(jié)點(diǎn)在該層左對齊，但可以缺少右邊的若干結(jié)點(diǎn)。完全二叉樹的特點(diǎn)是：（1）如果最大層次為k，則葉子結(jié)點(diǎn)都在第k－1層或k層上。（2）對任意結(jié)點(diǎn)，如果其右子樹的最大層次為k，則其左子樹的最大層次為k或k＋1。

二叉樹的基本性質(zhì)

性質(zhì)5：在具有n個(gè)結(jié)點(diǎn)的一棵完全二叉樹中，其深度為【log2n】＋1。其中【log2n】為取log2n的整數(shù)部分。性質(zhì)6：在具有n個(gè)結(jié)點(diǎn)的一棵完全二叉樹中，若把結(jié)點(diǎn)按層序編號（從上層到下層，每層從左到右)，則對任一結(jié)點(diǎn)i（1≤i≤n)，有：（1）如果i＝1，則結(jié)點(diǎn)i是二叉樹的根，無雙親結(jié)點(diǎn)；如果i>1，則結(jié)點(diǎn)i的雙親結(jié)點(diǎn)編號是【i/2】。其中【i/2】為取i/2的整數(shù)部分。（2）如果2i≤n，則結(jié)點(diǎn)i的左孩子結(jié)點(diǎn)編號是2i；否則無左孩子結(jié)點(diǎn)。（3）如果2i+1≤n，則結(jié)點(diǎn)i的右孩子結(jié)點(diǎn)編號是2i＋1；否則無右孩子結(jié)點(diǎn)。性質(zhì)7：在具有n個(gè)結(jié)點(diǎn)的一棵完全二叉樹中，當(dāng)n為偶數(shù)時(shí)，有且只有一個(gè)度為1的結(jié)點(diǎn)；當(dāng)n為奇數(shù)時(shí)，則沒有度為1的結(jié)點(diǎn)。性質(zhì)8：在具有n個(gè)結(jié)點(diǎn)的一棵完全二叉樹中，編號大于【n/2】的結(jié)點(diǎn)均為葉子結(jié)點(diǎn)。其中【n/2】為取n/2的整數(shù)部分。

3.5.3二叉樹的存儲結(jié)構(gòu)

1．二叉樹的順序存儲結(jié)構(gòu)在二叉樹中，將所有結(jié)點(diǎn)的數(shù)值按照由上到下、由左到右的順序來存儲在一個(gè)一維數(shù)組（線性結(jié)構(gòu)）中，這樣的存儲方式稱為二叉樹的順序存儲結(jié)構(gòu)。對于滿二叉樹或完全二叉樹可以使用順序存儲結(jié)構(gòu)來存儲。因?yàn)闈M二叉樹或完全二叉樹可以按照層的順序進(jìn)行順序存儲，并能很快確定每一個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)和左右孩子結(jié)點(diǎn)，能明確樹中各個(gè)結(jié)點(diǎn)的之間的相互關(guān)系，并且可以節(jié)省存儲空間。對于一般的二叉樹應(yīng)使用鏈?zhǔn)酱鎯Y(jié)構(gòu)來存儲。

2．二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)在二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，存儲二叉樹的每個(gè)結(jié)點(diǎn)的存儲空間也被分為兩個(gè)部分：數(shù)據(jù)域和指針域。由于二叉樹的每個(gè)結(jié)點(diǎn)可以有兩個(gè)子結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)上需要有兩個(gè)指針域，分別指向其左子樹和右子樹，這種二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為二叉鏈表。與分別指向直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)的雙向鏈表不同，二叉鏈表的兩個(gè)指針一個(gè)用于指向該結(jié)點(diǎn)的左子結(jié)點(diǎn)，另一個(gè)用于指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)。3.5.4二叉樹的遍歷不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。一般先遍歷左子樹，再遍歷右子樹。根據(jù)訪問根結(jié)點(diǎn)的次序，可分為三種：前序遍歷、中序遍歷、后序遍歷二叉樹的前序遍歷（根左右）先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。再遍歷左右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。如下圖前序序列：ABDECFABCDEF二叉樹的中序遍歷（左根右）先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。再遍歷左右子樹時(shí)，仍然先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。如下圖中序序列：DBEAFCABCDEF二叉樹的后序遍歷（左右根）先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)。再遍歷左右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)。如下圖后序序列：DEBFCAABCDEF二叉樹的遍歷例：設(shè)一顆二叉樹的中序遍歷結(jié)果為DBEAFC，前序遍歷結(jié)果為ABDECF，則后序遍歷結(jié)果為

。結(jié)果：DEBFCA

3.7查找技術(shù)

3.7.1查找的基本概念查找:在一個(gè)含有若干記錄（或數(shù)據(jù)元素）的列表中找出關(guān)鍵字值與給定值相同的記錄的過程。若找到相應(yīng)的記錄，則查找成功，返回記錄在表中的位置或記錄的信息；否則，查找失敗，返回空地址或失敗的信息。在查找過程中，若只是對表內(nèi)數(shù)據(jù)進(jìn)行查詢，則稱為靜態(tài)查找；在對表內(nèi)數(shù)據(jù)進(jìn)行查詢的同時(shí)，還對表進(jìn)行更新（如插入或刪除）操作，則稱為動(dòng)態(tài)查找。

3.7.2基于線性表的查找

基于線性表的查找分為：順序查找、二分法查找和分塊查找。1．順序查找順序查找是最簡單的一種查找方法。它是從線性表的任意一端開始，從前向后或從后向前逐個(gè)將表中數(shù)據(jù)元素與給定的關(guān)鍵字進(jìn)行比較，若表中某個(gè)記錄的關(guān)鍵字值與給定的關(guān)鍵字值相等，則查找成功；若到達(dá)表的另一端后，所有記錄的關(guān)鍵字值與給定的關(guān)鍵字值都不相等，則查找失敗。順序查找的存儲結(jié)構(gòu)既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。只能使用順序查找的兩種情況：①對于無序線性表（即線性表中數(shù)據(jù)元素排列是無序的），無論是采用順序存儲結(jié)構(gòu)，還是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，都必須使用順序查找；②對于有序線性表（即線性表中數(shù)據(jù)元素排列是有序的），若采用的是鏈?zhǔn)酱鎯Y(jié)構(gòu)，也必須使用順序查找。

基于線性表的查找

（1）線性表在順序存儲結(jié)構(gòu)下的順序查找返回為要查找的數(shù)據(jù)元素x在線性表中的序號；若不存在時(shí)，返回NULL。若線性表的存儲空間中含有多個(gè)數(shù)據(jù)元素值為x的記錄，則只能返回第一個(gè)查找到的數(shù)據(jù)元素x在線性表中的序號。例如，已知線性表（5，15，20，40，60，35，50，70，85，100）用順序存儲結(jié)構(gòu)來存儲。若順序查找與給定的關(guān)鍵字值“60”相等的數(shù)據(jù)元素，則要將給定的關(guān)鍵字從前向后依次與線性表中第1個(gè)位序（數(shù)據(jù)元素為5）到第5個(gè)位序（數(shù)據(jù)元素為60）之間的數(shù)據(jù)元素進(jìn)行比較，返回的是要查找的數(shù)據(jù)元素在線性表中的序號5。

基于線性表的查找

（2）線性表在鏈?zhǔn)酱鎯Y(jié)構(gòu)下的順序查找返回要查找的數(shù)據(jù)元素x在線性鏈表中的存儲地址；若不存在時(shí)，返回NULL。若線性鏈表的存儲空間中含有多個(gè)數(shù)據(jù)元素值為x的記錄，只能返回第一個(gè)查找到的數(shù)據(jù)元素x在線性鏈表中的存儲地址。順序查找的算法簡單，查找的效率與數(shù)據(jù)元素所在的位置有關(guān)。優(yōu)點(diǎn)是對表中數(shù)據(jù)元素的存儲沒有特別要求；它的缺點(diǎn)是在平均情況下查找大約要與表中一半的數(shù)據(jù)元素進(jìn)行比較，當(dāng)線性表的長度很大時(shí)效率較低，即不適用于長度較大的線性表的查找。

2．二分法查找

線性表采用順序存儲結(jié)構(gòu)存儲并按照關(guān)鍵字有序排列。二分查找的查找過程：①若線性表中間位置記錄的關(guān)鍵字值與給定的關(guān)鍵字值相等，則查找成功；②若線性表中間位置記錄的關(guān)鍵字值大于給定的關(guān)鍵字值，則在線性表的前半部分子表以同樣的方法進(jìn)行查找；③若線性表中間位置記錄的關(guān)鍵字值小于給定的關(guān)鍵字值，則在線性表的后半部分子表以同樣的方法進(jìn)行查找。重復(fù)以上過程，直到查找成功；或者直到子表不存在為止，此時(shí)查找失敗。長度為n的有序線性表在最壞情況下，順序查找需要比較n次，而二分查找只需要比較log2n次。

3.8排序技術(shù)

按照排序過程中依據(jù)的原則不同，將排序分為以下幾類：①插入排序：將無序序列中的數(shù)據(jù)元素依次插入到有序序列中。②交換排序：通過比較數(shù)據(jù)元素的關(guān)鍵字大小決定是否進(jìn)行交換。例如，冒泡排序、快速排序。③選擇排序：將無序序列中關(guān)鍵字值最小的數(shù)據(jù)元素依次放到有序序列中的指定位置。例如，簡單選擇排序、樹型選擇排序、堆排序。

3.8.1插入類排序

插入排序是指每次將一個(gè)待排序的數(shù)據(jù)元素插入到有序序列中，直到將所有待排序的數(shù)據(jù)元素全部插入為止。常用的插入排序有直接插入排序、