數(shù)據(jù)結(jié)構(gòu)與算法二級培訓(xùn)

數(shù)據(jù)結(jié)構(gòu)與算法二級培訓(xùn)第1章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2基本概念和術(shù)語1.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4算法與算法分析1.1什么是數(shù)據(jù)結(jié)構(gòu)一、計(jì)算機(jī)解決問題的一般過程。1、建立數(shù)學(xué)模型。2、根據(jù)數(shù)學(xué)模型，設(shè)計(jì)算法。3、編寫程序，調(diào)試直至問題的最終解決。二、數(shù)值問題與非數(shù)值問題。數(shù)值問題就是我們平時(shí)所說的計(jì)算問題，如已知圓的半徑，要求圓的面積。非數(shù)值問題就是問題中涉及的對象不能用數(shù)來表達(dá)的那些問題。1）數(shù)值問題例1已知：游泳池的長length和寬wide，求面積area。

分析：

問題涉及的對象：游泳池的長length寬wide，面積area；

對象之間的關(guān)系：area=lengthwide；main(){

intlen,wide,area;

scanf(“%d%d%\n”,&l,&w);

area=len*wide;

printf(“area=%d”,area);

}

2）非數(shù)值問題例2已知研究生選課情況，安排課程考試的日程。研究生選課情況表

姓名選修課1選修課1選修課1張ABE王CEF李DFA趙BF分析：

◆問題涉及的對象：課程；◆課程之間的關(guān)系：同一個研究生選修的不能按排在同一時(shí)間內(nèi)考試；課程及課程之間的關(guān)系可用如下所示的圖表示：DEFCBA頂點(diǎn)：表示課程；

邊：同一研究生選修的課程用邊連接課程考試安排問題轉(zhuǎn)化為圖的著色問題

用盡可能少的顏色為該圖的每個頂點(diǎn)著色，使相鄰的頂點(diǎn)著上不同的顏色；每一種顏色代表一個考試時(shí)間，著上相同顏色的頂點(diǎn)是可以按排在同一時(shí)間考試的課程；DEFCBAACEFBD課程著色的過程紅色：a，c；黃色：b，d；綠色：e；藍(lán)色：f

即a,c可安排在同一時(shí)間考試，b,d可安排在同一時(shí)間考試;設(shè)G表示課程關(guān)系圖，集合V包含圖G中所有尚未著色的頂點(diǎn)，NEW表示可以用新顏色著色的頂點(diǎn)集合。I=1；

WHILEV非空DO

置NEW為空集合；

FOR每個vVDO

IFv與NEW中所有的結(jié)點(diǎn)間都沒有邊

從V中去掉v；將v加入NEW；

（第I天考試課程為NEW中頂點(diǎn)所對應(yīng)的課程）

以某種形式輸出NEW中頂點(diǎn)所對應(yīng)的課程；

I=I+1；

通過對上個問題的分析，在這個問題的分析解決的過程中我們遇到了以下幾個問題：1、如何表示節(jié)點(diǎn)以及它們之間的關(guān)系（相鄰接）2、在計(jì)算機(jī)中如何存儲。3、相應(yīng)的操作如何描述。（染色過程）3）數(shù)值問題與非數(shù)值問題的比較

數(shù)值問題已知游泳池的長length,和寬wide,求面積area。（1）問題涉及的對象：length,wide,area是實(shí)數(shù)可用數(shù)值表示；

（2）對象之間的關(guān)系：area=lengthwide可用方程或函數(shù)表示；

（3）數(shù)據(jù)存儲：可用程序設(shè)計(jì)語言中的實(shí)型變量存儲；

（4）問題求解：用某種計(jì)算方法求解；已知研究生選課情況，安排課程考試的日程。1）問題涉及的對象：課程可用課程名表示,不能用數(shù)值表示2）對象之間的關(guān)系：同一研究生選修的課程不能安排在同一時(shí)間考試，同一研究生選修的課程之間有某種“沖突”關(guān)系——課程之間的這種關(guān)系不能用方程或函數(shù)表示3）數(shù)據(jù)及數(shù)據(jù)之間的關(guān)系如何存儲？4）如何求解？非數(shù)值數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，如何表示，如何存儲，如何處理的問題。

數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對象以及他們之間關(guān)系和操作等的學(xué)科。1.2基本概念和術(shù)語1、數(shù)據(jù)：一切能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的信息，包括文字、表格、圖象等，都稱為數(shù)據(jù)。例如，一個個人書庫管理程序所要處理的數(shù)據(jù)可能是一張如表1-1所示的表格。2．?dāng)?shù)據(jù)元素?cái)?shù)據(jù)元素（也叫節(jié)點(diǎn)），它是組成數(shù)據(jù)的基本單位。在程序中通常作為一個整體進(jìn)行考慮和處理。例如，在表1-1所示的個人書庫中，為了便于處理，把其中的每一行（代表一本書）作為一個基本單位來考慮，故該數(shù)據(jù)由10個結(jié)點(diǎn)構(gòu)成。一般情況下，一個結(jié)點(diǎn)中含有若干個字段（也叫數(shù)據(jù)項(xiàng)）。例如，在表1-1所示的表格數(shù)據(jù)中，每個結(jié)點(diǎn)都有登錄號、書號、書名、作者、出版社和價(jià)格等六個字段構(gòu)成。字段是構(gòu)成數(shù)據(jù)的最小單位。表1-1個人書庫3、數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如，整數(shù)數(shù)據(jù)對象的集合N={0，±1，±2，……}，字母數(shù)據(jù)對象的集合C={‘A’,’B’,……’Z’}。4、數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)元素之間的相互關(guān)系稱為結(jié)構(gòu)。根據(jù)數(shù)據(jù)結(jié)構(gòu)之間關(guān)系，通常有下列4類基本結(jié)構(gòu)。集合線性結(jié)構(gòu)樹型結(jié)構(gòu)圖狀結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個二元組 Data_Structure=(D,S)其中：D是數(shù)據(jù)元素的有限集，S是D上的關(guān)系的有限集合。5、數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系。數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示。本課程中介紹的存儲結(jié)構(gòu)有：順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)

索引結(jié)構(gòu)散列結(jié)構(gòu)6、數(shù)據(jù)類型：數(shù)據(jù)類型是一個值的集合和定義在這個值集上的一組操作的總稱。7、抽象數(shù)據(jù)類型（ADT）是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型可以用下面的三元組來表示（D，S，P）其中，D是數(shù)據(jù)對象，S是D上的關(guān)系集，P是對D的基本操作集。本書采用以下格式定義抽象數(shù)據(jù)類型：ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)名。1.4算法和算法分析算法：是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作；它有5個重要特征。有窮性：確定性：相同的輸入得到相同的輸出?？尚行裕狠斎耄狠敵觯核惴ㄔO(shè)計(jì)的要求：正確性：正確的含義，有四個層次。可讀性：健壯性：效率和低存儲量的要求：一個用高級語言編寫的程序在計(jì)算機(jī)上運(yùn)行所需要的時(shí)間取決于下列因素：⑴依據(jù)算法所選用的策略。⑵問題的規(guī)模。一般情況下，處理的數(shù)據(jù)量越大，執(zhí)行的時(shí)間相對也越長。⑶書寫程序的語言。語言的級別越高，其執(zhí)行效率就越低。⑷編譯程序所生成目標(biāo)代碼的質(zhì)量。⑸機(jī)器指令執(zhí)行的速度（硬件的速度）。與硬件的配置高低有關(guān)。通常的做法是：不考慮不確定的情況，而以算法中簡單操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。為此，一個特定算法的運(yùn)行時(shí)間長短就只依賴于問題的規(guī)模n，或者說它是問題規(guī)模n的函數(shù)f(n)?！纠壳罄奂忧蠛蚷ntsum(intb[]，intn）｛intsum=0;/*第1條定義并賦初值語句執(zhí)行1次*/for（inti=0；i<n；i++）sum+=b[i];/*n次*/returnsum;/*返回語句執(zhí)行1次*/｝要精確地計(jì)算f(n)是困難的，引入漸進(jìn)時(shí)間復(fù)雜度在數(shù)量上估計(jì)一個算法的執(zhí)行時(shí)間。算法時(shí)間的度量記作T(n)=Ο(f(n))它表示隨問題的規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率和f(n)相同。使用大Ο記號，Ο(f(n))稱為算法的漸進(jìn)時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。例如，一個程序的實(shí)際執(zhí)行時(shí)間為2.7n3+3.8n2+5.3。則T(n)＝Ο(n3)。例、求下面程序段的時(shí)間復(fù)雜度。s=0;for(j=1;j<=n;j++)for(x=1,k=1;k<=n;k++){x=x*k;s+=x;}{++x;a=0;}T(n)=O(1);//常量階for(i=1;i<=n;++i){++x;s+=x;}T(n)=O(n);//線性階for(j=1;j<=n;++j)for(k=1;k<=n;++k){++x;s+=x;}T(n)=O(n2)//平方階通常將稱Ο(1)為常數(shù)階，Ο(n)為線性階，O(n2)為平方階。算法還可能呈現(xiàn)的復(fù)雜度有：對數(shù)階Ο(log2n)，指數(shù)階Ο(2n)等，不同數(shù)量級時(shí)間復(fù)雜度的關(guān)系有：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(2n)常見函數(shù)的增長率

第2章線性表

2.1線性表概念及基本操作2.2線性表的順序存儲和實(shí)現(xiàn)2.1線性表概念及基本操作

例1、數(shù)學(xué)中的數(shù)列（11，13，15，17，19，21）例2、英文字母表（A,B,C,D,EZ）。例3、某單位的號碼簿。姓名電話號碼

蔡穎63214444陳紅63217777劉建平63216666王小林63218888張力63215555...說明：設(shè)A=（a1,a2,...,ai-1,ai,ai+1,…,an）是一線性表1）線性表的數(shù)據(jù)元素可以是各種各樣的，但同一線性表中的元素必須是同一類型的；2）在表中ai-1領(lǐng)先于ai，ai領(lǐng)先于ai+1，稱ai-1是ai的直接前趨，ai+1是ai的直接后繼；3）在線性表中，除第一個元素和最后一個元素之外，其他元素都有且僅有一個直接前趨，有且僅有一個直接后繼，具有這種結(jié)構(gòu)特征的數(shù)據(jù)結(jié)構(gòu)稱為線性結(jié)構(gòu)。線性表是一種線性數(shù)據(jù)結(jié)構(gòu)；4）線性表中元素的個數(shù)n稱為線性表的長度，n=0時(shí)稱為空表；5）ai是線性表的第i個元素，稱i為數(shù)據(jù)元素ai的序號，每一個元素在線性表中的位置，僅取決于它的序號；2.2線性表的順序表示和實(shí)現(xiàn)線性表的順序存儲結(jié)構(gòu)，就是用一組連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元素。用順序表存儲線性表時(shí)，數(shù)據(jù)元素之間的邏輯關(guān)系，是通過數(shù)據(jù)元素的存儲順序反映出來的。假沒線性表中每個數(shù)據(jù)元素占用k個存儲單元，那么，在順序存儲結(jié)構(gòu)中，線性表的第i個元素的存儲位置與第1個元素的存儲位置的關(guān)系是：Loc(ai)=Loc(a1)+(i–1)k

這里L(fēng)oc(ai)是第i個元素的存儲位置,Loc(a1)是第1個元素的存儲位置，也稱為線性表的基址；線性表的順序存儲的基本操作1）初始化操作InitList_Sq(SqList&L)2）銷毀操作DetroyList_Sq(SqList&L){

功能：回收為順序表動態(tài)分配的存儲空間

3）置空操作ClearList_Sq(SqList&L)

功能：若L已存在，重新將其置成空表5）插入操作ListInsert_Sq(&L,i,e)

參數(shù)：L：順序表，i插入位置，e被插入元素;因?yàn)椴迦氩僮鲗樞虮磉M(jìn)行修改,所以用了引用參數(shù)&L;

i的取值范圍在1-ListLength_Sq(L)+1;功能：在順序表L的第i個元素之前插入一個新元素e;6)刪除操作ListDelete_sq(SqList&L,inti,ElemType&e)功能：刪除順序表L的第i個元素，并用e返回

3.1

棧

3.1.1棧的概念3.1.2棧的順序存儲和實(shí)現(xiàn)第3章棧和隊(duì)列3.1.1抽象數(shù)據(jù)類型棧的定義棧是限定僅能在表尾一端進(jìn)行插入、刪除操作的線性表說明：設(shè)（a1,a2,a3,…,an）是一個棧1）表尾稱為棧頂，表頭稱為棧底，即a1為棧底元素，an為棧頂元素。

2）在表尾插入元素的操作稱進(jìn)棧操作，在表頭刪除元素的操作稱為出棧操作;

（a1,a2,...,ai-1,ai,ai+1,…,an）棧底棧頂進(jìn)棧出棧cbafed棧操作演示3）元素按a1,a2,a3,…,an的次序進(jìn)棧,第一個進(jìn)棧的元素一定在棧底，最后一個進(jìn)棧的元素一定在棧頂,第一個出棧的元素為棧頂元素；4）棧的元素具有后進(jìn)先出的特點(diǎn),所以棧又稱為后進(jìn)先出表（LIFO表）

5）由于進(jìn)棧、出棧操作總是在棧頂一端進(jìn)行，通常設(shè)置稱為棧頂指針的變量指示棧頂?shù)奈恢?。棧的基本操?）

初始化操作InitStack(&S)

操作結(jié)果：構(gòu)造一個空棧S；2）銷毀棧操作DestroyStack(&S)

初始條件：棧S存在。操作結(jié)果：銷毀一個已存在的棧;

3）置空棧操作ClearStack(&S)

初始條件：棧S存在。操作結(jié)果：將棧S置為空棧;4）判空操作StackEmpty(S)

初始條件：棧S存在。操作結(jié)果：若棧S為空，則返回True，否則返回False;5）求棧長度操作StackLength(S）初始條件：棧S存在。操作結(jié)果：返回S元素的個數(shù)，即棧的長度。6）取棧頂元素操作GetTop(S,&e)

初始條件：棧S存在，且非空。操作結(jié)果：取棧頂元素，并用e返回;7）進(jìn)棧操作Push(&S,e)

初始條件：棧S存在。操作結(jié)果：元素e進(jìn)棧;8）退棧操作Pop(&S,&e)

操作結(jié)果：棧頂元素退棧，并用e返回;9）棧的遍歷操作StackTraverse（S，visit（））初始條件：棧S存在。操作結(jié)果：從棧底到棧頂依次對S的每個數(shù)據(jù)元素調(diào)用函數(shù)visit()，一旦visit()失敗，則操作失敗。3.1.2棧的順序存儲和實(shí)現(xiàn)棧的順序存儲結(jié)構(gòu)也是利用一組連續(xù)的內(nèi)存單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，棧頂元素的位置由一個稱為棧頂指針的變量指示。棧操作圖示topbasebasetopbasetopbasetopAABCDAB空棧A進(jìn)棧BCD進(jìn)棧DC出棧

3.2隊(duì)列3.2.1隊(duì)列的概念3.2.2循環(huán)隊(duì)列

一什么是隊(duì)列隊(duì)列是限定僅能在表頭進(jìn)行刪除，表尾進(jìn)行插入的線性表（a1,a2,...,ai-1,ai,ai+1,…,an）插入刪除3.2.1隊(duì)列的概念說明：設(shè)（a1,a2,

a3,...,an）為一隊(duì)列

1）表尾稱作隊(duì)尾，表頭稱為隊(duì)頭；

2）a1為隊(duì)頭元素，an為隊(duì)尾元素；

3）在表尾插入元素操作，稱為入隊(duì)操作；在表頭刪除元素的操作，稱為出隊(duì)操作；

4）元素按a1,a2,a3,...an順序入隊(duì)，第一個入隊(duì)的元素為a1，最后一個入隊(duì)的元素是an，

第一個出隊(duì)的元素為a1，最后一個出隊(duì)的元素是an；

5）隊(duì)列具有先進(jìn)先出的特點(diǎn)，所以又稱為先進(jìn)先出表（FIFO表）

隊(duì)列的示意圖

隊(duì)列類似于日常的排隊(duì)，新來的人站在隊(duì)尾，隊(duì)頭的人進(jìn)行事務(wù)處理后離隊(duì)。隊(duì)列通常設(shè)置兩個變量分別指示隊(duì)頭元素位置和隊(duì)尾元素的位置，這兩個變量分別稱為隊(duì)頭指針、隊(duì)尾指針；

a1a2a3an入隊(duì)列隊(duì)頭隊(duì)尾出隊(duì)列二隊(duì)列的基本操作1）初始化操作InitQueue(&Q)

功能：構(gòu)造一個空隊(duì)列Q；

2）銷毀操作DestroyQueue(&Q)

功能：銷毀已存在隊(duì)列Q；

3）置空操作ClearQueue(&Q)功能：將隊(duì)列Q置為空隊(duì)列；4）判空操作QueueEmpty(Q)功能：若隊(duì)列Q為空,則返回True，否則返回False；

5）求隊(duì)列長度QueueLength（LinkQueue&Q)6）取隊(duì)頭元素操作GetHead(Q,&e)

功能：取隊(duì)頭元素，并用e返回；

7）入隊(duì)操作EnQueue(&Q,e)

功能：將元素e插入Q的隊(duì)尾；

8）出隊(duì)操作DeQueue(&Q,&e)

功能：若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用e返回其值，并返回OK，否則返回ERROR；第4章樹和二叉樹4.1

樹的有關(guān)概念1．樹的概念樹結(jié)構(gòu)（除了一個稱為根的結(jié)點(diǎn)外）每個元素都有且僅有一個直接前趨，有且僅有零個或多個直接后繼。樹是n個結(jié)點(diǎn)的有限集合，在任一棵非空樹中：

（1）有且僅有一個稱為根的結(jié)點(diǎn)。

（2）其余結(jié)點(diǎn)可分為個互不相交的集合，而且這些集合中的每一集合都本身又是一棵樹，稱為根的子樹。樹是遞歸結(jié)構(gòu)，在樹的定義中又用到了樹的概念例：下面的圖是一棵樹T={A,B,C,D,E,F,G,H,I,J}A是根，其余結(jié)點(diǎn)可以劃分為3個互不相交的集合：

T1={B,E,F},T2={C,D},T3={D,H,I,J}這些集合中的每一集合都本身又是一棵樹，它們是A的子樹。

例如對于T1，B是根，其余結(jié)點(diǎn)可以劃分為2個互不相交的集合：T11={E}，T12={F}，T11,T12是B的子樹。JIACBDHGFE從邏輯結(jié)構(gòu)看：

1）樹中只有根結(jié)點(diǎn)沒有前趨；

2）除根外，其余結(jié)點(diǎn)都有且僅一個前趨；3）樹的結(jié)點(diǎn)，可以有零個或多個后繼；4）樹是一種層次結(jié)構(gòu)JIACBDHGFE樹的基本術(shù)語樹的結(jié)點(diǎn)：包含一個數(shù)據(jù)元素及若干指向子樹的分支；

孩子結(jié)點(diǎn)：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子；

雙親結(jié)點(diǎn)：B結(jié)點(diǎn)是A結(jié)點(diǎn)的孩子，則A結(jié)點(diǎn)是B結(jié)點(diǎn)的雙親；

兄弟結(jié)點(diǎn)：同一雙親的孩子結(jié)點(diǎn)；

堂兄結(jié)點(diǎn)：同一層上結(jié)點(diǎn)；

結(jié)點(diǎn)層：根結(jié)點(diǎn)的層定義為1；根的孩子為第2層結(jié)點(diǎn) ，依此類推；

樹的高度：樹中最大的結(jié)點(diǎn)層．結(jié)點(diǎn)的度：結(jié)點(diǎn)子樹的個數(shù)

樹的度：樹中最大的結(jié)點(diǎn)度。

葉子結(jié)點(diǎn)：也叫終端結(jié)點(diǎn)，是度為0的結(jié)點(diǎn)；

分枝結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)；

森林；互不相交的樹集合；

有序樹：子樹有序的樹，如：家族樹；

無序樹：不考慮子樹的順序；5樹的基本操作1）InitTree(&T);2）DestroyTree(&T);3）CreateTree(&T,definition);4）ClearTree(&T);5）TreeEmpty(T);6）TreeDepth(T);7）Root(T);

8）Value(T,&cur_e);9）Assign(T,cur_e,value);10）Parent(T,cur_e);11）LeftChild(T,cur_e);12）RightSibling(T,cur_e);13）InsertChild(&T,&p,i,c);14）DeleteChild(&T,&p,i);15）TraverseTree(T,Visit());4.2.1二叉樹的定義二叉樹：它的特點(diǎn)是每個結(jié)點(diǎn)至多只有兩棵子樹，并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。二叉樹是遞歸結(jié)構(gòu)，在二叉樹的定義中又用到了二叉樹的概念。

A

F

G

E

D

C

B

4.2二叉樹

A

F

G

E

D

C

B

(a)、(b)是不同的二叉樹，(a)的左子樹有四個結(jié)點(diǎn)，(b)的左子樹有兩個結(jié)點(diǎn)，(a)

A

G

E

D

B

C

F(b)

2．二叉樹的基本形態(tài)

φ4.3二叉樹的遍歷 遍歷：按某種搜索路徑訪問二叉樹的每個結(jié)點(diǎn)，而且每個結(jié)點(diǎn)僅被訪問一次。 訪問：含義很廣，可以是對結(jié)點(diǎn)的各種處理，如修改結(jié)點(diǎn)數(shù)據(jù)、輸出結(jié)點(diǎn)數(shù)據(jù)。 遍歷是各種數(shù)據(jù)結(jié)構(gòu)最基本的操作，許多其他的操作可以在遍歷基礎(chǔ)上實(shí)現(xiàn)。對于線性結(jié)構(gòu)由于每個結(jié)點(diǎn)只有一個直接后繼，遍歷是很容易的事。思考：二叉樹是非線性結(jié)構(gòu)，每個結(jié)點(diǎn)可能有兩個后繼，如何訪問二叉樹的每個結(jié)點(diǎn)，而且每個結(jié)點(diǎn)僅被訪問一次？

二叉樹的遍歷方法二叉樹由根、左子樹、右子樹三部分組成二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子樹令：L：遍歷左子樹

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

R：遍歷右子樹

有六種遍歷方法：DLR，LDR，LRD，DRL，RDL，RLD

約定先左后右,有三種遍歷方法：DLR、LDR、LRD，分別稱為：先序遍歷、中序遍歷、后序遍歷。

A

F

G

E

D

C

B先序遍歷（DLR）若二叉樹非空（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹；

先序遍歷序列：A,B,D,E,G,C,F

A

F

G

E

D

C

B中序遍歷（LDR）若二叉樹非空

（1）中序遍歷左子樹

（2）訪問根結(jié)點(diǎn)（3）中序遍歷右子樹中序遍歷序列：D,B,G,E,A,C,F

A

F

G

E

D

C

B后序遍歷（LRD）若二叉樹非空

（1）后序遍歷左子樹

（2）后序遍歷右子樹（3）訪問根結(jié)點(diǎn)后序遍歷序列：D,G,E,B,F,C,A

A

F

G

E

D

C

B

e

d

c

b

f

a

+

*

/

-

-

后序遍歷序列：a,b,c,d,-,*,+,e,f,/,-

中序遍歷序列：a,+,b,*,c,-,d,-,e,/,f

先序遍歷序列：-,+,a,*,b,-,c,d,/,e,f例：先序遍歷、中序遍歷、后序遍歷下圖所示的二叉樹一、順序表及查找（線性表及查找）查找表組織：查找表用線性表表示。即將查找表的記錄排成一個記錄序列。L1=(45,53,12,3,37,24,100,61,90,78)基本思想：從表的最后一個記錄（或第一個記錄）開始，依次將記錄的關(guān)鍵字與給定值比較，若相等：查找成功，否則，繼續(xù)查找。第5章查找和排序5.1查找二、有序表及查找有序表：若線性表中的記錄按關(guān)鍵字有序，則稱為有序表。二分查找法（也稱為折半查找法）基本思想：將查找范圍中間位置的記錄關(guān)鍵字與給定值比較：＜：繼續(xù)在前半個表中用二分查找法查找=：查找成功，返回記錄位置＞：繼續(xù)在后半個表中中用二分查找法查找L2=(3,12,24,37,45,53,61,78,90,100)，查找Key=24的記錄

1234567891031224374553617890100lowmidhigh1234567891031224374553617890100lowmidhigh24＜45繼續(xù)在前半個表中用二分查找法查找1234567891031224374553617890100Lowmidhigh24＞12繼續(xù)在后半個表中用二分查找法查找5.2.1插入排序基本思想依次將待排記錄插入到有序子表中，并使插入子表后仍保持有序，直到全部記錄插入完畢；初始時(shí)，有序子表中只有一個元素。直接插入排序

插入排序的關(guān)鍵：如何查找插入位置。直接插入排序是用順序查找法定位插入位置。若采用二分查找法定位插入位置則得到另一種插入算法，二分插入排序

5.2排序例：待排記錄4938659776132749

（49）38659776132749 （3849）659776132749（384965）9776132749

（38496597）76132749（3849657697）132749（133849657697）2749（13273849657697）49（1327384949657697） 交換法排序基本思想：對待排序列中相鄰元素進(jìn)行比較，如果為逆序，則將這兩個元素的位置交換。重復(fù)此操作直到整個序列全部有序?yàn)橹?。一、冒泡排序基本思路為：首先將第一個記錄的關(guān)鍵字和第二個記錄的關(guān)鍵字比較，若為逆序，則兩個記錄交換；然后比較第二個記錄和第三個記錄的關(guān)鍵字，……，直至第n-1個記錄和第n個記錄的關(guān)鍵字比較、交換結(jié)束為止。經(jīng)過第一趟排序后，關(guān)鍵字最大(或最小)的記錄被調(diào)整到最后一個記錄的位置。下一趟排序時(shí)，這個關(guān)鍵字最大(或最小)的記錄就不必考慮了。直到某一趟排序過程中沒有進(jìn)行交換操作為止。5.2.3快速排序二、快速排序 當(dāng)冒泡排序在數(shù)據(jù)元素的關(guān)鍵字呈逆序時(shí)進(jìn)行排序，需要進(jìn)行多次比較和移動操作，數(shù)據(jù)元素移動是一步一步進(jìn)行的，且有很多是重復(fù)的?？焖倥判蚴菍γ芭菖判蛩惴ǖ母倪M(jìn)。基本思想：快速排序又稱為分區(qū)交換法，是通過對某關(guān)鍵字(支點(diǎn))的比較，將各待排序列分成前后兩部分，后半部分所有記錄的關(guān)鍵字值大于等于支點(diǎn)的關(guān)鍵字值，前半部分所有記錄的關(guān)鍵字小于等于支點(diǎn)的關(guān)鍵字值。將待排序列按關(guān)鍵字以支點(diǎn)分成兩部分的過程，稱為一次劃分。對各部分不斷的劃分，直到整個序列按關(guān)鍵字有序?yàn)橹?。【例】一趟快速排序過程示例r[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]r[8]r[9]r[10]4328397698694515828

r[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]r[8]r[9]r[10]434328397698694515828↑