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

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

分析：

問(wèn)題涉及的對(duì)象：游泳池的長(zhǎng)length寬wide，面積area；

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

intlen,wide,area;

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

area=len*wide;

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

}

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

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

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

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

用盡可能少的顏色為該圖的每個(gè)頂點(diǎn)著色，使相鄰的頂點(diǎn)著上不同的顏色；每一種顏色代表一個(gè)考試時(shí)間，著上相同顏色的頂點(diǎn)是可以按排在同一時(shí)間考試的課程；DEFCBAACEFBD課程著色的過(guò)程紅色：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每個(gè)vVDO

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

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

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

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

I=I+1；

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

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

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

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

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

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

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

第2章線性表

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

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

蔡穎63214444陳紅63217777劉建平63216666王小林63218888張力63215555...說(shuō)明：設(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）在線性表中，除第一個(gè)元素和最后一個(gè)元素之外，其他元素都有且僅有一個(gè)直接前趨，有且僅有一個(gè)直接后繼，具有這種結(jié)構(gòu)特征的數(shù)據(jù)結(jié)構(gòu)稱為線性結(jié)構(gòu)。線性表是一種線性數(shù)據(jù)結(jié)構(gòu)；4）線性表中元素的個(gè)數(shù)n稱為線性表的長(zhǎng)度，n=0時(shí)稱為空表；5）ai是線性表的第i個(gè)元素，稱i為數(shù)據(jù)元素ai的序號(hào)，每一個(gè)元素在線性表中的位置，僅取決于它的序號(hào)；2.2線性表的順序表示和實(shí)現(xiàn)線性表的順序存儲(chǔ)結(jié)構(gòu)，就是用一組連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元素。用順序表存儲(chǔ)線性表時(shí)，數(shù)據(jù)元素之間的邏輯關(guān)系，是通過(guò)數(shù)據(jù)元素的存儲(chǔ)順序反映出來(lái)的。假?zèng)]線性表中每個(gè)數(shù)據(jù)元素占用k個(gè)存儲(chǔ)單元，那么，在順序存儲(chǔ)結(jié)構(gòu)中，線性表的第i個(gè)元素的存儲(chǔ)位置與第1個(gè)元素的存儲(chǔ)位置的關(guān)系是：Loc(ai)=Loc(a1)+(i–1)k

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

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

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

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

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

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

3.1

棧

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

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

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

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

初始化操作InitStack(&S)

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

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

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

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

初始條件：棧S存在。操作結(jié)果：若棧S為空，則返回True，否則返回False;5）求棧長(zhǎng)度操作StackLength(S）初始條件：棧S存在。操作結(jié)果：返回S元素的個(gè)數(shù)，即棧的長(zhǎng)度。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é)果：從棧底到棧頂依次對(duì)S的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit()，一旦visit()失敗，則操作失敗。3.1.2棧的順序存儲(chǔ)和實(shí)現(xiàn)棧的順序存儲(chǔ)結(jié)構(gòu)也是利用一組連續(xù)的內(nèi)存單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，棧頂元素的位置由一個(gè)稱為棧頂指針的變量指示。棧操作圖示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ì)列的概念說(shuō)明：設(shè)（a1,a2,

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

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

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

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

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

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

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

隊(duì)列的示意圖

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

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

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

2）銷毀操作DestroyQueue(&Q)

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

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

5）求隊(duì)列長(zhǎng)度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章樹(shù)和二叉樹(shù)4.1

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

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

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

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

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

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

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

孩子結(jié)點(diǎn)：結(jié)點(diǎn)的子樹(shù)的根稱為該結(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) ，依此類推；

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

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

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

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

森林；互不相交的樹(shù)集合；

有序樹(shù)：子樹(shù)有序的樹(shù)，如：家族樹(shù)；

無(wú)序樹(shù)：不考慮子樹(shù)的順序；5樹(shù)的基本操作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二叉樹(shù)的定義二叉樹(shù)：它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有兩棵子樹(shù)，并且，二叉樹(shù)的子樹(shù)有左右之分，其次序不能任意顛倒。二叉樹(shù)是遞歸結(jié)構(gòu)，在二叉樹(shù)的定義中又用到了二叉樹(shù)的概念。

A

F

G

E

D

C

B

4.2二叉樹(shù)

A

F

G

E

D

C

B

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

A

G

E

D

B

C

F(b)

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

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

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

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

R：遍歷右子樹(shù)

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

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

A

F

G

E

D

C

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

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

A

F

G

E

D

C

B中序遍歷（LDR）若二叉樹(shù)非空

（1）中序遍歷左子樹(shù)

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

A

F

G

E

D

C

B后序遍歷（LRD）若二叉樹(shù)非空

（1）后序遍歷左子樹(shù)

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

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

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

5.2排序例：待排記錄4938659776132749

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

（38496597）76132749（3849657697）132749（133849657697）2749（13273849657697）49（1327384949657697） 交換法排序基本思想：對(duì)待排序列中相鄰元素進(jìn)行比較，如果為逆序，則將這兩個(gè)元素的位置交換。重復(fù)此操作直到整個(gè)序列全部有序?yàn)橹?。一、冒泡排序基本思路為：首先將第一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字比較，若為逆序，則兩個(gè)記錄交換；然后比較第二個(gè)記錄和第三個(gè)記錄的關(guān)鍵字，……，直至第n-1個(gè)記錄和第n個(gè)記錄的關(guān)鍵字比較、交換結(jié)束為止。經(jīng)過(guò)第一趟排序后，關(guān)鍵字最大(或最小)的記錄被調(diào)整到最后一個(gè)記錄的位置。下一趟排序時(shí)，這個(gè)關(guān)鍵字最大(或最小)的記錄就不必考慮了。直到某一趟排序過(guò)程中沒(méi)有進(jìn)行交換操作為止。5.2.3快速排序二、快速排序 當(dāng)冒泡排序在數(shù)據(jù)元素的關(guān)鍵字呈逆序時(shí)進(jìn)行排序，需要進(jìn)行多次比較和移動(dòng)操作，數(shù)據(jù)元素移動(dòng)是一步一步進(jìn)行的，且有很多是重復(fù)的?？焖倥判蚴菍?duì)冒泡排序算法的改進(jìn)?；舅枷耄嚎焖倥判蛴址Q為分區(qū)交換法，是通過(guò)對(duì)某關(guān)鍵字(支點(diǎn))的比較，將各待排序列分成前后兩部分，后半部分所有記錄的關(guān)鍵字值大于等于支點(diǎn)的關(guān)鍵字值，前半部分所有記錄的關(guān)鍵字小于等于支點(diǎn)的關(guān)鍵字值。將待排序列按關(guān)鍵字以支點(diǎn)分成兩部分的過(guò)程，稱為一次劃分。對(duì)各部分不斷的劃分，直到整個(gè)序列按關(guān)鍵字有序?yàn)橹埂！纠恳惶丝焖倥判蜻^(guò)程示例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↑