計(jì)算機(jī)程序主要對(duì)數(shù)據(jù)進(jìn)行加工和處理。通常程序中要說(shuō)明數(shù)據(jù)的組織形式和存儲(chǔ)方式，即數(shù)據(jù)結(jié)構(gòu)；也要給出操作數(shù)據(jù)的步驟和方法，即算法。

數(shù)據(jù)結(jié)構(gòu)基本概念算法基本概念典型數(shù)據(jù)結(jié)構(gòu)典型算法

6

學(xué)

時(shí)本章主要內(nèi)容

6.1數(shù)據(jù)結(jié)構(gòu)基本概念

6.1.1數(shù)據(jù)結(jié)構(gòu)示例

學(xué)號(hào)姓名性別出生日期班級(jí)專業(yè)20040001劉強(qiáng)男1984/02/1314001機(jī)械20040002王曉紅女1986/05/0614001機(jī)械20040003李明男1984/10/2514001機(jī)械20040041張宇男1984/06/1414002機(jī)械

數(shù)據(jù)也稱為數(shù)據(jù)元素或結(jié)點(diǎn)，現(xiàn)實(shí)世界中一切客觀事物都可以抽象成數(shù)據(jù)元素。6.1.2數(shù)據(jù)結(jié)構(gòu)的定義

數(shù)據(jù)結(jié)構(gòu)是指具有相同特征、相互之間有關(guān)聯(lián)的數(shù)據(jù)集合。向量{2，43，68，45，32}是數(shù)據(jù)結(jié)構(gòu)每個(gè)數(shù)據(jù)元素由一個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)元素之間有位置上的前后關(guān)系每個(gè)數(shù)據(jù)元素由一個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)元素之間有位置上的前后關(guān)系季度名稱組成的集合是數(shù)據(jù)結(jié)構(gòu)：

{春，夏，秋，冬}家庭成員{祖父、父親、兒子}是數(shù)據(jù)結(jié)構(gòu)每個(gè)數(shù)據(jù)元素由一個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)元素之間有層次上的高低關(guān)系學(xué)生信息數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素由學(xué)號(hào)、姓名、性別、出生日期、班級(jí)和專業(yè)組成。每個(gè)數(shù)據(jù)元素由多個(gè)數(shù)據(jù)項(xiàng)組成

數(shù)據(jù)結(jié)構(gòu)是指帶有結(jié)構(gòu)特性的數(shù)據(jù)元素集合，主要研究：1）數(shù)據(jù)集合中數(shù)據(jù)元素之間所固有的關(guān)系，即數(shù)據(jù)邏輯結(jié)構(gòu)；2）數(shù)據(jù)處理時(shí)數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)；3）對(duì)數(shù)據(jù)所進(jìn)行的操作，即算法。6.1.3數(shù)據(jù)邏輯結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間所固有的關(guān)系描述成前后件（前驅(qū)與后繼）關(guān)系。

數(shù)據(jù)之間前后件關(guān)系是它們之間的邏輯關(guān)系，與它們?cè)谟?jì)算機(jī)中存儲(chǔ)位置無(wú)關(guān)，因此將這種關(guān)系稱為數(shù)據(jù)邏輯結(jié)構(gòu)。

一個(gè)數(shù)據(jù)結(jié)構(gòu)可以表示為：

S=（D，R）

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

D:數(shù)據(jù)元素集合

R:D中數(shù)據(jù)元素之間前后件關(guān)系集合，即數(shù)據(jù)邏輯結(jié)構(gòu)兩個(gè)元素之間前后件關(guān)系用一個(gè)二元組表示，例：(a1,a2)季節(jié)數(shù)據(jù)結(jié)構(gòu)可以定義成S=(D,R)

其中:D={春,秋,冬,夏}R={(春,夏),(夏,秋),(秋,冬)}向量數(shù)據(jù)結(jié)構(gòu)可以定義成S=(D,R)

其中:D={2,43,68,45,32}R={(2,43),(43,68),(68,45),(45,32)}線性結(jié)構(gòu)：數(shù)據(jù)之間有集合,線性,樹形和圖形

4種基本邏輯結(jié)構(gòu)。數(shù)據(jù)元素之間一對(duì)一關(guān)系除第一個(gè)結(jié)點(diǎn)無(wú)前件外,其他結(jié)點(diǎn)都只有一個(gè)前件除最后一個(gè)結(jié)點(diǎn)無(wú)后件外,其他結(jié)點(diǎn)都只有一個(gè)后件例如:春夏冬秋數(shù)據(jù)之間一對(duì)多關(guān)系一個(gè)結(jié)點(diǎn)僅有一個(gè)前件,可有多個(gè)后件前、后件之間層次關(guān)系樹型結(jié)構(gòu)：數(shù)據(jù)元素之間多對(duì)多關(guān)系一個(gè)結(jié)點(diǎn)可有多個(gè)前件和多個(gè)后件圖形結(jié)構(gòu)：集合：是一種松散結(jié)構(gòu)，數(shù)據(jù)元素之間的關(guān)系是屬于一個(gè)集合，可用其他結(jié)構(gòu)表示。集合

非線性結(jié)構(gòu):有多個(gè)開始結(jié)點(diǎn)和多個(gè)終端結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)可以有多個(gè)前件和多個(gè)后件。

線性結(jié)構(gòu):有且只有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)最多只有一個(gè)前件和一個(gè)后件，線性結(jié)構(gòu)也稱為線性表。

數(shù)據(jù)邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。6.1.4數(shù)據(jù)物理結(jié)構(gòu)

數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式稱為數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)（或數(shù)據(jù)物理結(jié)構(gòu)）。

數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間在計(jì)算機(jī)中的位置關(guān)系與邏輯關(guān)系不一定相同。

在數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)中，不僅要存放各個(gè)數(shù)據(jù)元素信息，還要存放數(shù)據(jù)元素之間前后件關(guān)系信息。

數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的表示。

數(shù)據(jù)元素在計(jì)算機(jī)中通常有四種存儲(chǔ)方式，即順序、鏈?zhǔn)健⑺饕蜕⒘?，常用順序存?chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。數(shù)據(jù)地址……A1A2A3A42000H2001H2002H2003H

順序存儲(chǔ)結(jié)構(gòu)是在內(nèi)存中開辟一塊連續(xù)內(nèi)存單元用于存放數(shù)據(jù)，邏輯上相鄰的結(jié)點(diǎn)在物理位置上也鄰接，結(jié)點(diǎn)之間的邏輯關(guān)系是由存儲(chǔ)單元相鄰關(guān)系來(lái)體現(xiàn)。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)域和指針域

數(shù)據(jù)域用于存放數(shù)據(jù)元素值

指針域用于存放前件或后件的存儲(chǔ)地址鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過指針反映數(shù)據(jù)元素之間的邏輯關(guān)系。a13003Ha22506Ha32509Ha42000H2001H3003H3004H2506H2507H2509H2510H6.2算法基本概念

6.2.1算法定義

算法是定義在邏輯結(jié)構(gòu)上的操作，獨(dú)立于計(jì)算機(jī)，而算法必須在計(jì)算機(jī)上執(zhí)行，因此算法的實(shí)現(xiàn)依賴于數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)。

算法是解決問題的具體方法和步驟的描述，是一組有限運(yùn)算序列。

算法的特征可行性確定性有窮性輸入輸出采取的方法和步驟可行，結(jié)構(gòu)另人滿意。算法中每個(gè)步驟結(jié)果都必須確定，不能產(chǎn)生歧義。執(zhí)行算法時(shí)從外界取得必要的信息。一個(gè)算法可以有零或多個(gè)輸入。算法得到的結(jié)果就是輸出,沒有輸出的算法是沒有意義的,一個(gè)算法應(yīng)該有一個(gè)或多個(gè)輸出。算法必須由有限步組成，并能在有效時(shí)間內(nèi)完成。

用于描述算法的工具很多，通常有流程圖、N-S圖、自然語(yǔ)言和偽代碼等工具。自然語(yǔ)言：帶序號(hào)的人類語(yǔ)言描述方法。將變量s清0；將變量n置1；把s+n的值賦給s；把n+1的值賦給n；判斷n

100？是否成立，若成立，轉(zhuǎn)3；否則轉(zhuǎn)66.輸出s的值;S=1+2+3+…+99+100特點(diǎn):易懂卻不直觀,對(duì)復(fù)雜算法描述很困難,易產(chǎn)生歧義。若成立,偽代碼法：是一種假的代碼—不能被計(jì)算機(jī)執(zhí)行，可由計(jì)算機(jī)語(yǔ)言和自然語(yǔ)言構(gòu)成。0S1nwhilen100

{S+nSn+1n}printS

接近某種語(yǔ)言編寫的程序,便于轉(zhuǎn)換成程序。流程圖法：用一些圖框、線條以及文字說(shuō)明

來(lái)形象地、直觀地描述算法。輸入/輸出處理判斷起止連接點(diǎn)流程線符號(hào)說(shuō)明：開始0S1nS＋nSn＋1

n輸出S結(jié)束T

Fn100S=1+2+3+…+99+100優(yōu)點(diǎn):直觀形象缺點(diǎn):算法復(fù)雜時(shí),篇幅較多,費(fèi)時(shí)且不方便修改。N-S圖:

去掉箭頭流程線、算法處理步驟寫在大矩形框內(nèi),框內(nèi)還可包含一些小矩形框,適于結(jié)構(gòu)化程序設(shè)計(jì)。順序AB判斷條件FTBA當(dāng)型循環(huán)當(dāng)條件成立A直到型循環(huán)直到條件成立A0S1nn100S＋nSn＋1n輸出S的值算法評(píng)價(jià)

某一任務(wù)的算法設(shè)計(jì)得優(yōu)與劣,將直接影響程序的運(yùn)行效率、穩(wěn)定性和可維護(hù)性。從4個(gè)方面評(píng)價(jià)算法：正確性可讀性健壯性執(zhí)行效率算法本身沒有語(yǔ)法錯(cuò)誤,執(zhí)行時(shí)輸入正確數(shù)據(jù)能夠得到正確結(jié)果.算法要容易理解和閱讀,容易實(shí)現(xiàn)，便于程序維護(hù)和完善。算法執(zhí)行的時(shí)間性能和空間性能。算法能夠?qū)Ω鞣N輸入數(shù)據(jù)給予適當(dāng)處理和提示。

解決同一問題的多個(gè)算法，執(zhí)行時(shí)間短的算法時(shí)間效率高;占存儲(chǔ)空間少的算法空間效率高。

計(jì)算機(jī)資源有時(shí)間資源和空間資源，因而，算法復(fù)雜度有時(shí)間復(fù)雜度和空間復(fù)雜度之分。

一個(gè)算法復(fù)雜度高低體現(xiàn)在運(yùn)行該算法所需要資源的多少。需要資源越多，算法復(fù)雜度越高。6.2.4算法復(fù)雜度

算法復(fù)雜度是對(duì)算法效率的度量，是評(píng)價(jià)算法優(yōu)劣的重要依據(jù)。

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

算法時(shí)間復(fù)雜度是指執(zhí)行算法所需時(shí)間，可以表示為：

執(zhí)行時(shí)間=語(yǔ)句執(zhí)行時(shí)間×語(yǔ)句執(zhí)行次數(shù)

“規(guī)?！币话闶侵杆杼幚韱栴}的數(shù)據(jù)量大小，數(shù)據(jù)量越大，所花費(fèi)時(shí)間就越多。通常，語(yǔ)句執(zhí)行次數(shù)表示成以數(shù)據(jù)量n為自變量的函數(shù)，記為f(n)。

算法執(zhí)行時(shí)間可以轉(zhuǎn)換成對(duì)f(n)的分析。算法時(shí)間復(fù)雜度也變成是數(shù)據(jù)量n的函數(shù)，通常記為T(n)?！纠?-7】計(jì)算下列程序段的時(shí)間復(fù)雜度：

for（i=1；i<n；i++）

for（j=1；j<n；j++）

k=k+1；/*②*/

語(yǔ)句②執(zhí)行次數(shù)為:

(n-1)(n-1)=n2-2×n+1

即f(n)與n為二次方關(guān)系，所以，T(n)=O(n2)。

算法的語(yǔ)句執(zhí)行次數(shù)是關(guān)于數(shù)據(jù)量n的多項(xiàng)式，則該算法時(shí)間復(fù)雜度只與n的最高次方有關(guān)，而忽略系數(shù)和其他各項(xiàng)。當(dāng)f(n)與n無(wú)關(guān)時(shí)，T(n)=O(1)；當(dāng)f(n)與n為線性關(guān)系時(shí)，T(n)=O(n)；當(dāng)f(n)與n為二次方關(guān)系時(shí)，T(n)=O(n2)；依次類推。

算法空間復(fù)雜度

一個(gè)算法的空間效率是指在算法執(zhí)行過程中，所占用附加空間數(shù)量。

6.3典型數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。

線性結(jié)構(gòu)也稱為線性表，棧、隊(duì)列、數(shù)組和串等是特殊線性表；

非線性結(jié)構(gòu)包括樹和圖。

6.3.1線性表

1.線性表定義

線性表是一組特征相同數(shù)據(jù)的有限序列，表示為:L=(a1,a2,a3,…an)

線性表中數(shù)據(jù)元素個(gè)數(shù)n（n≥0）稱為線性表長(zhǎng)度。當(dāng)n=0時(shí)，稱為空表。

在非空線性表中，每個(gè)數(shù)據(jù)元素都有一個(gè)確定位置，其位置取決于它的序號(hào)

a1是第一個(gè)元素，a2

是第二個(gè)元素，an是最后一個(gè)元素。

線性表通常采用順序存儲(chǔ)結(jié)構(gòu)或鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

順序存儲(chǔ)的線性表也稱為順序表;

鏈?zhǔn)酱鎯?chǔ)的線性表也稱為鏈表。

非空線性表的特征：每個(gè)數(shù)據(jù)元素ai，有且只有一個(gè)前件ai-1（除a1無(wú)前件外）每個(gè)數(shù)據(jù)元素ai，有且只有一個(gè)后件ai+1（除了an無(wú)后件外）2.線性表順序存儲(chǔ)線性表順序存儲(chǔ)是指用一段連續(xù)存儲(chǔ)單元存放表中數(shù)據(jù)元素

數(shù)據(jù)元素在存儲(chǔ)空間中按邏輯順序依次存放

線性表的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)相一致

同一線性表中數(shù)據(jù)元素類型相同

一個(gè)數(shù)據(jù)元素占用d個(gè)字節(jié)線性表的首地址Addr（a1）為K

數(shù)據(jù)元素ai的首地址為：

addr（ai）=addr（a1）+（i-1)×d=K+(i-1)×d

其中1≤i≤n2000a1占2個(gè)字節(jié)a2a320042002占2個(gè)字節(jié)占2個(gè)字節(jié)

在線性表中通過元素序號(hào)可以很方便地訪問某一元素在程序設(shè)計(jì)中，通常用數(shù)組來(lái)表示順序表

線性結(jié)構(gòu){a1，a2，a3}，其中每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)空間，假設(shè)存儲(chǔ)a1的首地址為2000。3.線性表鏈?zhǔn)酱鎯?chǔ)

線性表鏈?zhǔn)酱鎯?chǔ)是用一組存儲(chǔ)單元（可以連續(xù)，也可以不連續(xù)）存儲(chǔ)線性表中數(shù)據(jù)元素。數(shù)據(jù)元素由兩部分組成：數(shù)據(jù)域（值域）和指針域

數(shù)據(jù)域指針域

數(shù)據(jù)邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)互相獨(dú)立，物理位置上相鄰結(jié)點(diǎn)邏輯關(guān)系上不一定相鄰結(jié)點(diǎn)之間邏輯關(guān)系由指針域來(lái)確定單鏈表

定義：每個(gè)結(jié)點(diǎn)只有一個(gè)指針域的鏈表a1

a2a3a4a5^head每個(gè)單鏈表都有一個(gè)頭指針，存放表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)地址。每個(gè)結(jié)點(diǎn)指針域存放后件結(jié)點(diǎn)的存儲(chǔ)地址，最后一個(gè)結(jié)點(diǎn)無(wú)后件結(jié)點(diǎn)，指針域?yàn)榭眨肗ULL或^

表示。循環(huán)鏈表

循環(huán)鏈表中增設(shè)一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域的值可以任意或根據(jù)情況設(shè)置，指針域指向第一個(gè)結(jié)點(diǎn)。

將單鏈表最后一個(gè)結(jié)點(diǎn)的空指針域改為指向該鏈表的第一個(gè)結(jié)點(diǎn)，即首尾相連。head空循環(huán)鏈表非空循環(huán)鏈表a1a2…..headan注意頭指針和表頭結(jié)點(diǎn)的區(qū)別循環(huán)鏈表特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)，均可以找到其它所有結(jié)點(diǎn)；在任何情況下，帶有表頭結(jié)點(diǎn)的循環(huán)鏈表中至少有一個(gè)結(jié)點(diǎn)存在，從而使空表和非空表運(yùn)算統(tǒng)一。循環(huán)鏈表運(yùn)算與單鏈表區(qū)別：對(duì)單鏈表進(jìn)行操作時(shí)，要判斷是否是表尾，即指針是否為NULL；而對(duì)循環(huán)鏈表操作時(shí)，要判斷是否是頭指針。6.3.2棧棧是只能在表的一端進(jìn)行插入和刪除運(yùn)算的線性表

將允許插入和刪除運(yùn)算的一端稱為棧頂（top），另一端稱為棧底

（bottom）將插入元素操作稱為入棧，將刪除元素操作稱為出棧棧稱為“先進(jìn)后出”表或“后進(jìn)先出”表

設(shè)有一個(gè)棧S={a1,a2,…,an}，入棧順序是a1、a2…最后是an。棧的狀態(tài)如圖所示：a1a2an…棧底bottom棧頂top入棧出棧棧特點(diǎn)：后進(jìn)先出。

故也稱為“先進(jìn)后出”表或“后進(jìn)先出”表?xiàng)５幕具\(yùn)算

棧初始化：構(gòu)造一個(gè)空棧

空棧判斷：判斷棧是否為空

入棧：在棧頂插入一個(gè)元素

出棧：在棧頂刪除一個(gè)元素

讀棧：僅讀取棧頂數(shù)據(jù)，并不刪除元素棧的順序存儲(chǔ)

用一塊連續(xù)存儲(chǔ)區(qū)域存放棧中元素棧底:連續(xù)區(qū)域的低地址一端.棧底固定不變?nèi)霔＿\(yùn)算S1：如果top=n，則棧已滿，提示入棧失敗(?！吧弦纭卞e(cuò)誤)，并結(jié)束入棧；S2：top+1top；S3：將新元素放在當(dāng)前棧頂位置(top)上。

a1

a2a3bottomtopa4出棧運(yùn)算S1：如果top=0，則棧為空，提示出棧失敗(?！跋乱纭卞e(cuò)誤)，并結(jié)束出棧；S2：將當(dāng)前棧頂(top)元素賦給一個(gè)變量；S3：top–1top。a3top

a1

a2bottom例如，容量為6的棧中已有3個(gè)元素,如圖所示：123456ACBbottomtopX、Y兩個(gè)元素先后入棧XY元素Y出?！纠?-11】6.3.3隊(duì)列

允許一端插入、而另一端刪除的線性表，允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭。入隊(duì)退隊(duì)隊(duì)尾abc隊(duì)頭隊(duì)列的基本運(yùn)算

初始化隊(duì)列：創(chuàng)建一個(gè)空隊(duì)列。空隊(duì)列判斷：判斷隊(duì)列是否為空。入隊(duì)運(yùn)算：在隊(duì)尾插入一個(gè)元素。出隊(duì)運(yùn)算：在隊(duì)頭刪除一個(gè)元素。讀隊(duì)頭元素：讀取隊(duì)頭元素賦給一個(gè)指定變量，不刪除隊(duì)頭元素。隊(duì)列長(zhǎng)度：求隊(duì)列中元素個(gè)數(shù)。

隊(duì)列的順序存儲(chǔ)

通常將順序存儲(chǔ)的隊(duì)列稱為順序隊(duì)列。變量(front和rear)分別存放隊(duì)列頭和尾位置。

front和rear都是整型變量。

front指向隊(duì)列中第一個(gè)元素的前一個(gè)單元位置，

rear指向隊(duì)列中最后一個(gè)元素位置。設(shè)隊(duì)列中能容納元素個(gè)數(shù)為n。創(chuàng)建一個(gè)空隊(duì)列,并令front=rear=-11.初始化隊(duì)列front

-1201rear2.入隊(duì)運(yùn)算S1：如果rear=n-1，則隊(duì)列已滿，提示入隊(duì)失敗(隊(duì)列“上溢”錯(cuò)誤)，并結(jié)束入隊(duì)；S2：rear+1

rear；S3：將新元素放在當(dāng)前隊(duì)列位置(rear)上frontrear-1201ABC3.退隊(duì)運(yùn)算S1：如果front=rear，則隊(duì)列已空,提示退隊(duì)失敗(隊(duì)列“下溢”錯(cuò)誤),并結(jié)束退隊(duì)；S2：front+1

front;S3：取front所指元素frontrear-1201ABC此時(shí)雖然隊(duì)列有空位置，但也不能插入新結(jié)點(diǎn)。循環(huán)隊(duì)列

將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，這樣可以把退隊(duì)的空間利用起來(lái)。023102134

在循環(huán)隊(duì)列中，仍然用front指向隊(duì)頭元素的前一個(gè)單元位置，用rear指向隊(duì)尾元素的位置。

圖6-21循環(huán)隊(duì)列元素入／隊(duì)出隊(duì)運(yùn)算示意圖返回⒉循環(huán)隊(duì)列的常用運(yùn)算在循環(huán)隊(duì)列中，出隊(duì)時(shí)隊(duì)頭指針追趕隊(duì)尾指針，入隊(duì)時(shí)隊(duì)尾指針追趕隊(duì)頭指針，隊(duì)列空或隊(duì)列滿時(shí)，隊(duì)頭和隊(duì)尾指針都相等。增加一個(gè)標(biāo)志變量flag，初始化時(shí)flag=0入隊(duì)成功時(shí)置

flag=1；出隊(duì)成功時(shí)置flag=0隊(duì)列空的判斷條件是：front=rear

且flag=0隊(duì)列滿的判斷條件是：front=rear

且flag=1⑴初始化隊(duì)列：創(chuàng)建一個(gè)空隊(duì)列，并設(shè)置

front=rear=0，flag=0

⑵入隊(duì)運(yùn)算：S1：如果front=rear

并且flag=1，則隊(duì)列已滿，入隊(duì)失敗(“上溢”錯(cuò)誤)，并結(jié)束入隊(duì)。S2：如果(rear+1)=n

，則0rear

；否則rear+1rear

。S3：將新元素放在當(dāng)前隊(duì)尾位置(rear)，1flag

⑶

出隊(duì)運(yùn)算：S1：如果front=rear，且flag=0，則隊(duì)列已空，出隊(duì)失?。ā跋乱纭卞e(cuò)誤），并結(jié)束出隊(duì)S2：如果（front+1）=n

，則0front

；否則front+1front

。S3：0flag

【例6-13】循環(huán)隊(duì)列運(yùn)算，如圖6-21所示圖（a）：循環(huán)隊(duì)列為空?qǐng)D（b）：元素a0、a1和a2相繼入隊(duì)圖（c）：元素a0、a1和a2先后出隊(duì)圖（d）：元素a3、a4、a5和a6先后入隊(duì)圖（e）：元素a7入隊(duì)6.3.5樹

樹是一種常用的非線性結(jié)構(gòu)，樹結(jié)構(gòu)中結(jié)點(diǎn)之間既有分支關(guān)系又有層次關(guān)系

樹是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合。當(dāng)n=0時(shí)，稱為空樹；否則，有且僅有一個(gè)根結(jié)點(diǎn)。當(dāng)n>1時(shí)，其余結(jié)點(diǎn)被分成m（m>0）個(gè)互不相交的子集T1，T2，...，Tm，每個(gè)子集又是一棵樹。

用圖形表示樹時(shí)，通常表示成一棵倒掛樹。AEBCDFGHIJKL前件后件結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)所擁有后件個(gè)數(shù)樹的度：樹中所有結(jié)點(diǎn)的最大度

AEBCDFGHIJKL根子結(jié)點(diǎn)葉結(jié)點(diǎn)

AEBCDFGHIJKL

結(jié)點(diǎn)的層次從根結(jié)點(diǎn)算起，根結(jié)點(diǎn)在第一層，根的直接后繼結(jié)點(diǎn)在第二層，同一層上所有結(jié)點(diǎn)的后繼結(jié)點(diǎn)均在下一層。

1234樹中結(jié)點(diǎn)的最大層次稱為樹的深度或高度

6.3.6二叉樹

二叉樹是另一種樹形結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)最多只有兩個(gè)后件。其特點(diǎn)是：

非空二叉樹有且只有一個(gè)根結(jié)點(diǎn)；每個(gè)結(jié)點(diǎn)最多有兩棵子樹，且有左右之分二叉樹用五種形態(tài)(a)空二叉樹(b)只有根結(jié)點(diǎn)(c)只有左子樹(d)有左和右子樹(e)只有右子樹二叉樹基本性質(zhì)性質(zhì)一在二叉樹的第i層上，最多有2i-1個(gè)結(jié)點(diǎn)(i≥1).性質(zhì)二深度為k的二叉樹最多有2k-1個(gè)結(jié)點(diǎn)(k≥1).性質(zhì)三對(duì)于任意一棵二叉樹，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總比度為2的結(jié)點(diǎn)多1個(gè).２1-1=１ATXCRBPSEGFY２2-1=2２3-1=4２4-1=8１ATXCRBPSEGFY245２4-1=15>12ATXCRBPSEGFY度為0結(jié)點(diǎn)數(shù)6,度為2結(jié)點(diǎn)數(shù)5滿二叉樹擁有2k-1個(gè)結(jié)點(diǎn)，深度為k的二叉樹。

每一層的結(jié)點(diǎn)數(shù)都達(dá)到最大值,葉子結(jié)點(diǎn)都在最下面的同一層上

完全二叉樹

一棵深度為k的二叉樹,如果第一層到第k-1層是一棵滿二叉樹,第k層上的結(jié)點(diǎn)數(shù)可能沒達(dá)到最大值2k-1,但這些結(jié)點(diǎn)都滿放在該層最左邊。如果某個(gè)結(jié)點(diǎn)沒有左子樹,則它一定沒有右子樹

ATXCEMBP2４-1＝15個(gè)結(jié)點(diǎn)的滿二叉樹SDNFRYQ注：滿二叉樹是完全二叉樹，但完全二叉樹不一定是滿二叉樹。ATXCRBPSEGFY24-1=8>5滿二叉樹滿放在最左邊完全二叉樹性質(zhì)12個(gè)結(jié)點(diǎn)的完全二叉樹ATXCRBPSEGFY性質(zhì)一具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n」+1。其中，log2n」表示取log2n的整數(shù)部分。性質(zhì)二在n個(gè)結(jié)點(diǎn)的完全二叉樹中,將結(jié)點(diǎn)從上到下,從左到右編號(hào)1,2,…,n,對(duì)編號(hào)為k的結(jié)點(diǎn)有：k=1為根結(jié)點(diǎn)。k>1時(shí),該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為int(k/2)。2k<=n時(shí),編號(hào)為k結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k,否則無(wú)左子結(jié)點(diǎn)。2k+1<=n時(shí),編號(hào)為k結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+1,否則無(wú)右子結(jié)點(diǎn)。ATXCRBPSEQFY123456710119812二叉樹的順序存儲(chǔ)指用一組連續(xù)存儲(chǔ)單元存儲(chǔ)二叉樹中的結(jié)點(diǎn)。結(jié)點(diǎn)存儲(chǔ)順序是按著從上到下、從左到右順序。ACBEGDFABCDEFG

1

2

3

4

5

67

按完全二叉樹每個(gè)結(jié)點(diǎn)編號(hào)的順序存放結(jié)點(diǎn),通過結(jié)點(diǎn)的編號(hào)準(zhǔn)確地反映結(jié)點(diǎn)之間的邏輯關(guān)系。1234567非完全二叉樹順序存儲(chǔ)ACBEGFABC

EFG

1

2

3

4

5

67顯然,順序結(jié)構(gòu)適用于完全二叉樹，對(duì)于非完全二叉樹，浪費(fèi)許多存儲(chǔ)空間。1234567二叉樹鏈?zhǔn)酱鎯?chǔ)二叉樹每個(gè)結(jié)點(diǎn)由數(shù)據(jù)域和指針域組成。兩個(gè)指針域：

o

一個(gè)用于指向左子結(jié)點(diǎn)

o

一個(gè)用于指向右子結(jié)點(diǎn)

常見二叉樹結(jié)點(diǎn)結(jié)構(gòu)如圖：LChildDataRChild數(shù)據(jù)域存儲(chǔ)左子結(jié)點(diǎn)地址存儲(chǔ)右子結(jié)點(diǎn)地址ATXCZYBP深度為4的二叉樹二叉樹鏈?zhǔn)酱鎯?chǔ)ATXCZYBP深度為4的二叉樹∧∧∧∧∧A∧∧∧∧TXBCPZYBT二叉樹遍歷

遍歷二叉樹就是按照某種順序訪問二叉樹中每個(gè)結(jié)點(diǎn)的過程，每個(gè)結(jié)點(diǎn)被訪問一次且僅一次。非空二叉樹可以看成由根結(jié)點(diǎn)、左子樹和右子樹三部分構(gòu)成。二叉樹的遍歷分為先序遍歷、中序遍歷和后序遍歷。先序遍歷

√訪問根結(jié)點(diǎn)

√先序遍歷左子樹

√先序遍歷右子樹ATXCZYBP深度為4的二叉樹A遍歷結(jié)果：TBZXCPY因?yàn)樽笞訕淇?，故遍歷右子樹中序遍歷

√中序遍歷左子樹

√訪問根結(jié)點(diǎn)

√中序遍歷右子樹ATXCZYBP深度為4的二叉樹ATZBCXYP因?yàn)樽笞訕淇毡闅v結(jié)果：

√后序遍歷左子樹

√后序遍歷右子樹

√訪問根結(jié)點(diǎn)后序遍歷ATXCZYBP深度為4的二叉樹遍歷結(jié)果：ATXCZYBP深度為4的二叉樹ATZBCXYP因?yàn)樽笞訕淇?，故遍歷右子樹6.4典型算法

6.4.1查找算法

查找又稱檢索，是數(shù)據(jù)處理中使用最頻繁的一種操作。

查找是指在數(shù)據(jù)集合中查找某個(gè)數(shù)據(jù)元素的過程。若存在這樣數(shù)據(jù)元素，則查找成功；否則，查找失敗。順序查找

順序查找適用于線性表。其基本方法是：從線性表中第一個(gè)元素開始，依次將線性表中元素與給定值進(jìn)行比較。若相等，則查找成功；若直到最后一個(gè)元素，還沒找到與給定值相等的元素，則查找失敗。例如：在(88,15,23,80,63,8,86,46,71,101)中,查找值為71的數(shù)據(jù)元素。從線性表中第一個(gè)元素88開始,依次將

線性表中元素與71進(jìn)行比較。直到第九個(gè)元素為71,查找成功。特點(diǎn)：順序查找算法簡(jiǎn)單,但是執(zhí)行效率較低

在下列兩種情況下,只能使用順序查找法：①線性表鏈?zhǔn)酱鎯?chǔ)。②線性表順序存儲(chǔ)，但元素?zé)o序排列。比較了9次××××××××√2二分查找

又稱折半查找,要求被查找的表用順序存儲(chǔ)結(jié)構(gòu)且數(shù)據(jù)元素按數(shù)據(jù)值升序或降序排列,即二分查找法只適用于有序表。基本思想

(設(shè)順序表升序排列)將給定值與中間元素（[(L+R)/2]）比較,若相等,則找成功；若給定值小于中間元素值,則繼續(xù)對(duì)前半再折半查找；若給定值大于中間元素值,則繼續(xù)對(duì)后半再折半查找。設(shè)待查找序列的序號(hào)區(qū)間為[L…R]，則中間序號(hào)位置為mid=[(L+R)/2]第一次查找mid=(1+12)/2」=6

6671808688101789101112第二次查找mid=96671

78【例6-14】在有序順序表（8，15，23，37，46，63，66，71，80，86，88，101）中，用折半查找法查找值為71的數(shù)據(jù)元素。key=71815233746636671808688101123456789101112

第三次查找mid=771

8

第四次查找mid=8查找成功排序算法

排序是將一組無(wú)序數(shù)據(jù)按值遞增（