數據結構與算法二級培訓

數據結構與算法數據結構與算法二級培訓數據結構與算法二級培訓全文共75頁，當前為第1頁。第1章緒論1.1什么是數據結構1.2基本概念和術語1.3抽象數據類型的表示與實現1.4算法與算法分析數據結構與算法二級培訓全文共75頁，當前為第2頁。1.1什么是數據結構一、計算機解決問題的一般過程。1、建立數學模型。2、根據數學模型，設計算法。3、編寫程序，調試直至問題的最終解決。二、數值問題與非數值問題。數值問題就是我們平時所說的計算問題，如已知圓的半徑，要求圓的面積。非數值問題就是問題中涉及的對象不能用數來表達的那些問題。數據結構與算法二級培訓全文共75頁，當前為第3頁。1）數值問題例1已知：游泳池的長length和寬wide，求面積area。

分析：

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

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

intlen,wide,area;

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

area=len*wide;

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

}

數據結構與算法二級培訓全文共75頁，當前為第4頁。2）非數值問題例2已知研究生選課情況，安排課程考試的日程。研究生選課情況表

姓名選修課1選修課1選修課1張ABE王CEF李DFA趙BF數據結構與算法二級培訓全文共75頁，當前為第5頁。分析：

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

邊：同一研究生選修的課程用邊連接數據結構與算法二級培訓全文共75頁，當前為第6頁。課程考試安排問題轉化為圖的著色問題

用盡可能少的顏色為該圖的每個頂點著色，使相鄰的頂點著上不同的顏色；每一種顏色代表一個考試時間，著上相同顏色的頂點是可以按排在同一時間考試的課程；DEFCBAACEFBD

課程著色的過程紅色：a，c；黃色：b，d；綠色：e；藍色：f

即a,c可安排在同一時間考試，b,d可安排在同一時間考試;數據結構與算法二級培訓全文共75頁，當前為第7頁。設G表示課程關系圖，集合V包含圖G中所有尚未著色的頂點，NEW表示可以用新顏色著色的頂點集合。I=1；

WHILEV非空DO

置NEW為空集合；

FOR每個vVDO

IFv與NEW中所有的結點間都沒有邊

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

（第I天考試課程為NEW中頂點所對應的課程）

以某種形式輸出NEW中頂點所對應的課程；

I=I+1；

數據結構與算法二級培訓全文共75頁，當前為第8頁。

通過對上個問題的分析，在這個問題的分析解決的過程中我們遇到了以下幾個問題：1、如何表示節(jié)點以及它們之間的關系（相鄰接）2、在計算機中如何存儲。3、相應的操作如何描述。（染色過程）數據結構與算法二級培訓全文共75頁，當前為第9頁。3）數值問題與非數值問題的比較

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

（2）對象之間的關系：area=lengthwide

可用方程或函數表示；

（3）數據存儲：可用程序設計語言中的實型變量存儲；

（4）問題求解：用某種計算方法求解；數據結構與算法二級培訓全文共75頁，當前為第10頁。已知研究生選課情況，安排課程考試的日程。1）問題涉及的對象：課程可用課程名表示,不能用數值表示2）對象之間的關系：同一研究生選修的課程不能安排在同一時間考試，同一研究生選修的課程之間有某種“沖突”關系——課程之間的這種關系不能用方程或函數表示3）數據及數據之間的關系如何存儲？4）如何求解？數據結構與算法二級培訓全文共75頁，當前為第11頁。

非數值數據之間的結構關系，如何表示，如何存儲，如何處理的問題。

數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象以及他們之間關系和操作等的學科。數據結構與算法二級培訓全文共75頁，當前為第12頁。1.2基本概念和術語1、數據：一切能夠輸入到計算機中并被計算機程序處理的信息，包括文字、表格、圖象等，都稱為數據。例如，一個個人書庫管理程序所要處理的數據可能是一張如表1-1所示的表格。2．數據元素數據元素（也叫節(jié)點），它是組成數據的基本單位。在程序中通常作為一個整體進行考慮和處理。例如，在表1-1所示的個人書庫中，為了便于處理，把其中的每一行（代表一本書）作為一個基本單位來考慮，故該數據由10個結點構成。一般情況下，一個結點中含有若干個字段（也叫數據項）。例如，在表1-1所示的表格數據中，每個結點都有登錄號、書號、書名、作者、出版社和價格等六個字段構成。字段是構成數據的最小單位。數據結構與算法二級培訓全文共75頁，當前為第13頁。表1-1個人書庫數據結構與算法二級培訓全文共75頁，當前為第14頁。3、數據對象：是性質相同的數據元素的集合，是數據的一個子集。例如，整數數據對象的集合N={0，±1，±2，……}，字母數據對象的集合C={‘A’,’B’,……’Z’}。4、數據結構：是相互之間存在一種或多種特定關系的數據元素的集合。數據元素之間的相互關系稱為結構。根據數據結構之間關系，通常有下列4類基本結構。集合線性結構樹型結構圖狀結構數據結構與算法二級培訓全文共75頁，當前為第15頁。數據結構的形式定義為：數據結構是一個二元組

Data_Structure=(D,S)其中：D是數據元素的有限集，S是D上的關系的有限集合。數據結構與算法二級培訓全文共75頁，當前為第16頁。5、數據的邏輯結構：數據元素之間的邏輯關系。數據的存儲結構：數據結構在計算機中的表示。本課程中介紹的存儲結構有：順序存儲結構鏈式存儲結構

索引結構散列結構6、數據類型：數據類型是一個值的集合和定義在這個值集上的一組操作的總稱。7、抽象數據類型（ADT）是指一個數學模型以及定義在該模型上的一組操作。數據結構與算法二級培訓全文共75頁，當前為第17頁。抽象數據類型可以用下面的三元組來表示（D，S，P）其中，D是數據對象，S是D上的關系集，P是對D的基本操作集。本書采用以下格式定義抽象數據類型：ADT抽象數據類型名{數據對象：<數據對象的定義>數據關系：<數據關系的定義>基本操作：<基本操作的定義>}ADT抽象數據名。數據結構與算法二級培訓全文共75頁，當前為第18頁。1.4算法和算法分析算法：是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作；它有5個重要特征。有窮性：確定性：相同的輸入得到相同的輸出?？尚行裕狠斎耄狠敵觯簲祿Y構與算法二級培訓全文共75頁，當前為第19頁。算法設計的要求：正確性：正確的含義，有四個層次?？勺x性：健壯性：效率和低存儲量的要求：數據結構與算法二級培訓全文共75頁，當前為第20頁。

一個用高級語言編寫的程序在計算機上運行所需要的時間取決于下列因素：⑴依據算法所選用的策略。⑵問題的規(guī)模。一般情況下，處理的數據量越大，執(zhí)行的時間相對也越長。⑶書寫程序的語言。語言的級別越高，其執(zhí)行效率就越低。⑷編譯程序所生成目標代碼的質量。⑸機器指令執(zhí)行的速度（硬件的速度）。與硬件的配置高低有關。數據結構與算法二級培訓全文共75頁，當前為第21頁。

通常的做法是：不考慮不確定的情況，而以算法中簡單操作重復執(zhí)行的次數作為算法的時間度量。為此，一個特定算法的運行時間長短就只依賴于問題的規(guī)模n，或者說它是問題規(guī)模n的函數f(n)?！纠壳罄奂忧蠛蚷ntsum(intb[]，intn）｛

intsum=0;/*第1條定義并賦初值語句執(zhí)行1次*/for（inti=0；i<n；i++）

sum+=b[i];/*n次*/returnsum;/*返回語句執(zhí)行1次*/

｝數據結構與算法二級培訓全文共75頁，當前為第22頁。

要精確地計算f(n)是困難的，引入漸進時間復雜度在數量上估計一個算法的執(zhí)行時間。算法時間的度量記作

T(n)=Ο(f(n))它表示隨問題的規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)相同。使用大Ο記號，Ο(f(n))稱為算法的漸進時間復雜度，簡稱時間復雜度。數據結構與算法二級培訓全文共75頁，當前為第23頁。例如，一個程序的實際執(zhí)行時間為

2.7n3+3.8n2+5.3。則T(n)＝Ο(n3)。例、求下面程序段的時間復雜度。

s=0;for(j=1;j<=n;j++)for(x=1,k=1;k<=n;k++){x=x*k;s+=x;}數據結構與算法二級培訓全文共75頁，當前為第24頁。{++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)//平方階數據結構與算法二級培訓全文共75頁，當前為第25頁。通常將稱Ο(1)為常數階，Ο(n)為線性階，O(n2)為平方階。算法還可能呈現的復雜度有：對數階Ο(log2n)，指數階Ο(2n)等，不同數量級時間復雜度的關系有：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(2n)數據結構與算法二級培訓全文共75頁，當前為第26頁。常見函數的增長率數據結構與算法二級培訓全文共75頁，當前為第27頁。

第2章線性表

2.1線性表概念及基本操作2.2線性表的順序存儲和實現數據結構與算法二級培訓全文共75頁，當前為第28頁。2.1線性表概念及基本操作

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

姓名電話號碼

蔡穎63214444

陳紅63217777

劉建平63216666

王小林63218888

張力63215555...數據結構與算法二級培訓全文共75頁，當前為第29頁。說明：設A=（a1,a2,...,ai-1,ai,ai+1,…,an）是一線性表1）線性表的數據元素可以是各種各樣的，但同一線性表中的元素必須是同一類型的；2）在表中ai-1領先于ai，ai領先于ai+1，稱ai-1是ai的直接前趨，ai+1是ai的直接后繼；數據結構與算法二級培訓全文共75頁，當前為第30頁。3）在線性表中，除第一個元素和最后一個元素之外，其他元素都有且僅有一個直接前趨，有且僅有一個直接后繼，具有這種結構特征的數據結構稱為線性結構。線性表是一種線性數據結構；4）線性表中元素的個數n稱為線性表的長度，n=0時稱為空表；5）ai是線性表的第i個元素，稱i為數據元素ai的序號，每一個元素在線性表中的位置，僅取決于它的序號；數據結構與算法二級培訓全文共75頁，當前為第31頁。2.2線性表的順序表示和實現

線性表的順序存儲結構，就是用一組連續(xù)的內存單元依次存放線性表的數據元素。用順序表存儲線性表時，數據元素之間的邏輯關系，是通過數據元素的存儲順序反映出來的。假沒線性表中每個數據元素占用k個存儲單元，那么，在順序存儲結構中，線性表的第i個元素的存儲位置與第1個元素的存儲位置的關系是：

Loc(ai)=Loc(a1)+(i–1)k

這里Loc(ai)是第i個元素的存儲位置,Loc(a1)是第1個元素的存儲位置，也稱為線性表的基址；數據結構與算法二級培訓全文共75頁，當前為第32頁。線性表的順序存儲的基本操作1）初始化操作InitList_Sq(SqList&L)2）銷毀操作DetroyList_Sq(SqList&L){

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

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

功能：若L已存在，重新將其置成空表數據結構與算法二級培訓全文共75頁，當前為第33頁。5）插入操作ListInsert_Sq(&L,i,e)

參數：L：順序表，i插入位置，e被插入元素;因為插入操作對順序表進行修改,所以用了引用參數&L;

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

數據結構與算法二級培訓全文共75頁，當前為第34頁。3.1

棧

3.1.1棧的概念3.1.2棧的順序存儲和實現第3章棧和隊列數據結構與算法二級培訓全文共75頁，當前為第35頁。3.1.1抽象數據類型棧的定義棧是限定僅能在表尾一端進行插入、刪除操作的線性表說明：設（a1,a2,a3,…,an）是一個棧1）表尾稱為棧頂，表頭稱為棧底，即a1為棧底元素，an為棧頂元素。

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

（a1,a2,...,ai-1,ai,ai+1,…,an

）棧底棧頂進棧出棧數據結構與算法二級培訓全文共75頁，當前為第36頁。cbafed棧操作演示數據結構與算法二級培訓全文共75頁，當前為第37頁。3）元素按a1,a2,a3,…,an的次序進棧,第一個進棧的元素一定在棧底，最后一個進棧的元素一定在棧頂,第一個出棧的元素為棧頂元素；

4）棧的元素具有后進先出的特點,所以棧又稱為后進先出表（LIFO表）

5）由于進棧、出棧操作總是在棧頂一端進行，通常設置稱為棧頂指針的變量指示棧頂的位置。數據結構與算法二級培訓全文共75頁，當前為第38頁。棧的基本操作1）

初始化操作InitStack(&S)

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

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

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

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

初始條件：棧S存在。操作結果：若棧S為空，則返回True，否則返回False;5）求棧長度操作StackLength(S）初始條件：棧S存在。操作結果：返回S元素的個數，即棧的長度。數據結構與算法二級培訓全文共75頁，當前為第39頁。6）取棧頂元素操作GetTop(S,&e)

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

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

操作結果：棧頂元素退棧，并用e返回;9）棧的遍歷操作StackTraverse（S，visit（））初始條件：棧S存在。操作結果：從棧底到棧頂依次對S的每個數據元素調用函數visit()，一旦visit()失敗，則操作失敗。數據結構與算法二級培訓全文共75頁，當前為第40頁。3.1.2棧的順序存儲和實現

棧的順序存儲結構也是利用一組連續(xù)的內存單元依次存放自棧底到棧頂的數據元素，棧頂元素的位置由一個稱為棧頂指針的變量指示。數據結構與算法二級培訓全文共75頁，當前為第41頁。

棧操作圖示topbasebasetopbasetopbasetopAABCDAB空棧A進棧BCD進棧DC出棧數據結構與算法二級培訓全文共75頁，當前為第42頁。

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

數據結構與算法二級培訓全文共75頁，當前為第43頁。一什么是隊列

隊列是限定僅能在表頭進行刪除，表尾進行插入的線性表（a1,a2,...,ai-1,ai,ai+1,…,an

）插入刪除3.2.1隊列的概念數據結構與算法二級培訓全文共75頁，當前為第44頁。說明：設（a1,a2,

a3,...,an

）為一隊列

1）表尾稱作隊尾，表頭稱為隊頭；

2）a1為隊頭元素，an為隊尾元素；

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

4）元素按a1,a2,a3,...an

順序入隊，第一個入隊的元素為a1

，最后一個入隊的元素是an，

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

5）隊列具有先進先出的特點，所以又稱為先進先出表（FIFO表）

數據結構與算法二級培訓全文共75頁，當前為第45頁。隊列的示意圖

隊列類似于日常的排隊，新來的人站在隊尾，隊頭的人進行事務處理后離隊。隊列通常設置兩個變量分別指示隊頭元素位置和隊尾元素的位置，這兩個變量分別稱為隊頭指針、隊尾指針；a1a2a3an入隊列隊頭隊尾出隊列數據結構與算法二級培訓全文共75頁，當前為第46頁。二隊列的基本操作1）初始化操作InitQueue(&Q)

功能：構造一個空隊列Q；

2）銷毀操作DestroyQueue(&Q)

功能：銷毀已存在隊列Q；

3）置空操作ClearQueue(&Q)

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

數據結構與算法二級培訓全文共75頁，當前為第47頁。5）求隊列長度QueueLength（LinkQueue&Q)6）取隊頭元素操作GetHead(Q,&e)

功能：取隊頭元素，并用e返回；

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

功能：將元素e插入Q的隊尾；

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

功能：若隊列不空，則刪除Q的隊頭元素，用e返回其值，并返回OK，否則返回ERROR；數據結構與算法二級培訓全文共75頁，當前為第48頁。第4章樹和二叉樹數據結構與算法二級培訓全文共75頁，當前為第49頁。4.1

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

（1）有且僅有一個稱為根的結點。

（2）其余結點可分為個互不相交的集合，而且這些集合中的每一集合都本身又是一棵樹，稱為根的子樹。樹是遞歸結構，在樹的定義中又用到了樹的概念數據結構與算法二級培訓全文共75頁，當前為第50頁。例：下面的圖是一棵樹T={A,B,C,D,E,F,G,H,I,J}A是根，其余結點可以劃分為3個互不相交的集合：

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

例如對于T1，B是根，其余結點可以劃分為2個互不相交的集合：

T11={E}，T12={F}，T11,T12是B的子樹。JIACBDHGFE數據結構與算法二級培訓全文共75頁，當前為第51頁。從邏輯結構看：

1）樹中只有根結點沒有前趨；

2）除根外，其余結點都有且僅一個前趨；3）樹的結點，可以有零個或多個后繼；4）樹是一種層次結構JIACBDHGFE數據結構與算法二級培訓全文共75頁，當前為第52頁。

樹的基本術語樹的結點：包含一個數據元素及若干指向子樹的分支；

孩子結點：結點的子樹的根稱為該結點的孩子；

雙親結點：B結點是A結點的孩子，則A結點是B結點的雙親；

兄弟結點：同一雙親的孩子結點；

堂兄結點：同一層上結點；

結點層：根結點的層定義為1；根的孩子為第2層結點 ，依此類推；

樹的高度：樹中最大的結點層．數據結構與算法二級培訓全文共75頁，當前為第53頁。結點的度：結點子樹的個數

樹的度：樹中最大的結點度。

葉子結點：也叫終端結點，是度為0的結點；

分枝結點：度不為0的結點；

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

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

無序樹：不考慮子樹的順序；數據結構與算法二級培訓全文共75頁，當前為第54頁。5樹的基本操作1）InitTree(&T);2）DestroyTree(&T);3）CreateTree(&T,definition);4）ClearTree(&T);5）TreeEmpty(T);6）TreeDepth(T);7）Root(T);

數據結構與算法二級培訓全文共75頁，當前為第55頁。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());數據結構與算法二級培訓全文共75頁，當前為第56頁。4.2.1二叉樹的定義二叉樹：它的特點是每個結點至多只有兩棵子樹，并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。

二叉樹是遞歸結構，在二叉樹的定義中又用到了二叉樹的概念。

A

F

G

E

D

C

B

4.2二叉樹數據結構與算法二級培訓全文共75頁，當前為第57頁。

A

F

G

E

D

C

B

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

A

G

E

D

B

C

F(b)數據結構與算法二級培訓全文共75頁，當前為第58頁。

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

φ數據結構與算法二級培訓全文共75頁，當前為第59頁。4.3二叉樹的遍歷

遍歷：按某種搜索路徑訪問二叉樹的每個結點，而且每個結點僅被訪問一次。 訪問：含義很廣，可以是對結點的各種處理，如修改結點數據、輸出結點數據。 遍歷是各種數據結構最基本的操作，許多其他的操作可以在遍歷基礎上實現。對于線性結構由于每個結點只有一個直接后繼，遍歷是很容易的事。

思考：二叉樹是非線性結構，每個結點可能有兩個后繼，如何訪問二叉樹的每個結點，而且每個結點僅被訪問一次？

數據結構與算法二級培訓全文共75頁，當前為第60頁。二叉樹的遍歷方法二叉樹由根、左子樹、右子樹三部分組成二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子樹令：L：遍歷左子樹

D：訪問根結點

R：遍歷右子樹

有六種遍歷方法：

DLR，LDR，LRD，

DRL，RDL，RLD

約定先左后右,有三種遍歷方法：DLR、LDR、LRD

，分別稱為：先序遍歷、中序遍歷、后序遍歷。

A

F

G

E

D

C

B數據結構與算法二級培訓全文共75頁，當前為第61頁。先序遍歷（DLR）若二叉樹非空（1）訪問根結點；（2）先序遍歷左子樹；（3）先序遍歷右子樹；

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

A

F

G

E

D

C

B數據結構與算法二級培訓全文共75頁，當前為第62頁。中序遍歷（LDR）若二叉樹非空

（1）中序遍歷左子樹

（2）訪問根結點（3）中序遍歷右子樹中序遍歷序列：D,B,G,E,A,C,F

A

F

G

E

D

C

B數據結構與算法二級培訓全文共75頁，當前為第63頁。后序遍歷（LRD）若二叉樹非空

（1）后序遍歷左子樹

（2）后序遍歷右子樹（3）訪問根結點后序遍歷序列：D,G,E,B,F,C,A

A

F

G

E

D

C

B數據結構與算法二級培訓全文共75頁，當前為第64頁。

e

d

c

b

f

a

+

*

/

-

-

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

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

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

1234567891031224374553617890100lowmidhigh1234567891031224374553617890100lowmidhigh24＜

45繼續(xù)在前半個表中用二分查找法查找1234567891031224374553617890100Lowmidhigh24＞

12繼續(xù)在后半個表中用二分查找法查找數據結構與算法二級培訓全文共75頁，當前為第68頁。5.2.1插入排序

基本思想依次將待排記錄插入到有序子表中，并使插入子表后仍保持有序，直到全部記錄插入完畢；初始時，有序子表中只有一個元素。直接插入排序

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

5.2排序數據結構與算法二級培訓全文共75頁，當前為第69頁。例：待排記錄4938659776132749

（49）38659776132749

（3849）659776132749

（384965）9776132749

（38496597）76132749

（3849657697）132749

（133849657697）2749

（13273849657697）49

（1327384949657697）數據結構與算法二級培訓全文共75頁，當前為第70頁。

交換法排序基本思想：對待排序列中相鄰元素進行比較，如果為逆序，則將這兩個元素的位置交換。重復此操作直到整個序列全部有序為止。一、冒泡排序基本思路為：首先將第一個記錄的關鍵字和第二個記錄的關鍵字比較，若為逆序，則兩個記錄交換；然后比較第二個記錄和第三個記錄的關鍵字，……，直至第n-1個記錄和第n個記錄的關鍵字比較、交換結束為止。經過第一趟排序后，關鍵字最大(或最小)的記錄被調整到最后一個記錄的位置。下一趟排序時，這個關鍵字最大(或最小)的記錄就不必考慮了。直到某一趟排序過程中沒有進行交換操作為止。5.2.3快速排序數據結構與算法二級培訓全文共75頁，當前為第71頁。二、快速排序 當冒泡排序在數據元素的關鍵字呈逆序時進行排序，需要進行多次比較和移動操作，數據元素移動是一步一步進行的，且有很多是重復的。快速排序是對冒泡排序算法的改進。

基本思想：快速排序又稱為分區(qū)交換法，是通過對某關鍵字(支點)的比較，將各待排序列分成前后兩部分，后半部分所有記錄的關鍵字值大于等于支點的關鍵字值，前半部分所有記錄的關鍵字小于等于支點的關鍵字值。將待排序列按關鍵字以支點分成兩部分的過程，稱為一次劃分。對各部分不斷的劃分，直到整個序列按關鍵字有序為止。數據結構與算法二級培訓全文共75頁，當前為第72頁?！纠恳惶丝焖倥判蜻^程示例

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]