1、數據結構與簡單算法廣東汕頭華僑中學 歐陽玲用計算機解決問題一般步驟：具體問題數學模型算法編程、調試得到答案一般來說，用計算機解決一個具體問題時，大致經過以下幾個步驟：首先要從具體問題抽象出一個適當的數學模型，然后設計一個解此數學模型的算法，最后編出程序進行測試調整知道的到最終解答。尋求數學模型的實質就是分析問題，從中提取操作的對象，并找出這些操作對象之間含有的關系，然后用數學的語言加以描述。三種經典的數學模型圖書書目自動檢索系統線性關系博弈問題樹城市道路問題圖數據結構（data structure）簡單的解釋：相互之間存在一種或多種特定關系的數據元素的集合。數據間的聯系有邏輯關系、存儲聯系，通

2、常的數據結構指的是邏輯結構。 前面提到的三種經典的數學模型體現了數據結構的基本結構，數據結構通常有如下四種關系：（1）集合結構 （2）線性結構 （3）樹形結構 （4）圖狀結構 線性表（一）N個數據元素的有限序列存儲結構：順序存儲結構、鏈式存儲結構（1）（2）（3）（4）（5）（6）（7）（8）1213152234384320當需要在順序存儲的線性表中插入一個數據元素時，需要順序移動后續的元素以“騰”出某個合適的位置放置新元素。刪除元素呢？ 線性表（二）鏈式存儲插入新元素的時候只需要改變指針所指向的地址。 二維數組與線性表如果某一線性表，它的每一個數據元素分別是一個線性表，這樣的二維表在數據實現

3、上通常使用二維數組。二維數組的一個形象比喻多個縱隊形成的方塊 m * n 數組地址計算問題題目描述：已知N*(N+1) / 2個數據，按行的順序存入數組b1,b2,中。其中第一個下標表示行，第二個下標表示列。若aij (i>=j ,j=1,2,n)存于bk中，問：k,i,j之間的關系如何表示？給定k值，寫出能決定相應i,j的算法。答案 K=i*(i-1)/2+j Read(k);For i:=1 to k do for j:=1 to i do if k=(trunc(I*(I-1)/2)+j) then writeln(k,對應的i,j為：,i,j) 棧特殊的線性表操作特點：后進先出（

4、Last In First Out）棧頂表尾棧底表頭空棧 棧 （考題分析）（1998） 棧S初始狀態為空，現有5個元素組成的序列1，2，3，4，5，對該序列在棧S上一次進行如下操作（從序列中的1開始，出棧后不再進棧）：進棧、進棧、進棧、出棧、進棧、出棧、進棧。問出棧的元素序列是_D(A) 5,4,3,2,1 (B) 2,1 (C) 2,3 (D) 3,4 隊列先進先出允許插入的一端稱為隊尾(rear)，允許刪除的一端稱為隊頭(front)。 循環隊列頭指針指向隊列中隊頭元素的前一個位置，尾指針指示隊尾元素在隊列中的當前位置。(R-F+N) mod N 樹根、葉子、子樹結點的度：結點擁有的子樹數

5、二叉樹 二叉樹特點：每個結點至多只有二棵子樹，并且二叉樹的子樹有左右之分。第i層至多有 2i-1 個結點（i>=1）深度為K的二叉樹最多有 2k-1 個結點（K>=1） 二叉樹的遍歷先（根）序遍歷ABDFGCEH中（根）序遍歷BFDGACHE后（根）序遍歷FGDBHECA 例題分析給出一棵二叉樹的中序遍歷：DBGEACHFI 與后序遍歷：DGEBHIFCA ，畫出此二叉樹。 圖 圖的存儲結構鄰接矩陣有向圖、無向圖、帶權圖的鄰接矩陣 排序冒泡排序選擇排序快速排序希爾排序一、插入排序(Insertion Sort)1. 基本思想： 每次將一個待排序的數據元素，插入到前面已經排好序的數列

6、中的適當位置，使數列依然有序；直到待排序數據元素全部插入完為止。2. 排序過程： 【示例】：初始關鍵字 49 38 65 97 76 13 27 49 J=2(38) 38 49 65 97 76 13 27 49 J=3(65) 38 49 65 97 76 13 27 49 J=4(97) 38 49 65 97 76 13 27 49 J=5(76) 38 49 65 76 97 13 27 49 J=6(13) 13 38 49 65 76 97 27 49 J=7(27) 13 27 38 49 65 76 97 49 J=8(49) 13 27 38 49 49 65 76 97

7、Procedure InsertSort(Var R : FileType);/對R1.N按遞增序進行插入排序, R0是監視哨/ Begin for I := 2 To N Do /依次插入R2,.,Rn/ begin R0 := RI; J := I - 1; While R0 < RJ Do /查找RI的插入位置/ begin RJ+1 := RJ; /將大于RI的元素后移/ J := J - 1 end RJ + 1 := R0 ; /插入RI / end End; /InsertSort /二、選擇排序1. 基本思想：每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放

8、在已排好序的數列的最后，直到全部待排序的數據元素排完。2. 排序過程： 【示例】： 初始關鍵字 49 38 65 97 76 13 27 49第一趟排序后 13 38 65 97 76 49 27 49第二趟排序后 13 27 65 97 76 49 38 49第三趟排序后 13 27 38 97 76 49 65 49第四趟排序后 13 27 38 49 49 97 65 76第五趟排序后 13 27 38 49 49 97 97 76第六趟排序后 13 27 38 49 49 76 76 97第七趟排序后 13 27 38 49 49 76 76 97最后排序結果 13 27 38 49

9、49 76 76 97Procedure SelectSort(Var R : FileType); /對R1.N進行直接選擇排序 / Begin for I := 1 To N - 1 Do /做N - 1趟選擇排序/ begin K := I; For J := I + 1 To N Do /在當前無序區RI.N中選最小的元素RK/ begin If RJ < RK Then K := J end; If K <> I Then /交換RI和RK / begin Temp := RI; RI := RK; RK := Temp; end; end End; /Select

10、Sort /三、冒泡排序(BubbleSort)1. 基本思想：兩兩比較待排序數據元素的大小，發現兩個數據元素的次序相反時即進行交換，直到沒有反序的數據元素為止。2. 排序過程：設想被排序的數組R1.N垂直豎立，將每個數據元素看作有重量的氣泡，根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反復進行，直至最后任何兩個氣泡都是輕者在上，重者在下為止。 【示例】：49 13 13 13 13 13 13 13 38 49 27 27 27 27 27 2765 38 49 38 38 38 38 3897 65 38 4

11、9 49 49 49 4976 97 65 49 49 49 49 4913 76 97 65 65 65 65 6527 27 76 97 76 76 76 7649 49 49 76 97 97 97 97 Procedure BubbleSort(Var R : FileType) /從下往上掃描的起泡排序/Begin For I := 1 To N-1 Do /做N-1趟排序/ begin NoSwap := True; /置未排序的標志/ For J := N - 1 DownTo 1 Do /從底部往上掃描/ begin If RJ+1< RJ Then /交換元素/ beg

12、in Temp := RJ+1; RJ+1 := RJ; RJ := Temp; NoSwap := False end; end; If NoSwap Then Return/本趟排序中未發生交換，則終止算法/ endEnd; /BubbleSort/四、快速排序（Quick Sort）1. 基本思想：在當前無序區R1.H中任取一個數據元素作為比較的"基準"(不妨記為X)，用此基準將當前無序區劃分為左右兩個較小的無序區：R1.I-1和RI+1.H，且左邊的無序子區中數據元素均小于等于基準元素，右邊的無序子區中數據元素均大于等于基準元素，而基準X則位于最終排序的位置上，即R

13、1.I-1X.KeyRI+1.H(1IH)，當R1.I-1和RI+1.H均非空時，分別對它們進行上述的劃分過程，直至所有無序子區中的數據元素均已排序為止。2. 排序過程： 【示例】：初始關鍵字 49 38 65 97 76 13 27 49第一次交換后 27 38 65 97 76 13 49 49 第二次交換后 27 38 49 97 76 13 65 49 J向左掃描，位置不變，第三次交換后 27 38 13 97 76 49 65 49 I向右掃描，位置不變，第四次交換后 27 38 13 49 76 97 65 49J向左掃描 27 38 13 49 76 97 65 49（一次劃分過

14、程） 初始關鍵字 49 38 65 97 76 13 27 49一趟排序之后 27 38 13 49 76 97 65 49 二趟排序之后 13 27 38 49 49 6576 97三趟排序之后 13 27 38 49 49 6576 97最后的排序結果 13 27 38 49 49 65 76 97 各趟排序之后的狀態Procedure Parttion(Var R : FileType; L, H : Integer; Var I : Integer);/對無序區R1,H做劃分，I給以出本次劃分后已被定位的基準元素的位置 /Begin I := 1; J := H; X := RI ;/

15、初始化，X為基準/ Repeat While (RJ >= X) And (I < J) Do begin J := J - 1 /從右向左掃描，查找第1個小于 X的元素/ If I < J Then /已找到RJ X/ begin RI := RJ; /相當于交換RI和RJ/ I := I + 1 end; While (RI <= X) And (I < J) Do I := I + 1 /從左向右掃描，查找第1個大于 X的元素/ end; If I < J Then /已找到RI > X / begin RJ := RI; /相當于交換RI和RJ

16、/ J := J - 1 end Until I = J; RI := X /基準X已被最終定位/End; /Parttion /Procedure QuickSort(Var R :FileType; S,T: Integer); /對RS.T快速排序/Begin If S < T Then /當RS.T為空或只有一個元素是無需排序/ begin Partion(R, S, T, I); /對RS.T做劃分/ QuickSort(R, S, I-1);/遞歸處理左區間RS,I-1/ QuickSort(R, I+1,T);/遞歸處理右區間RI+1.T / end;End; /Quick

17、Sort/五、堆排序(Heap Sort)1. 基本思想： 堆排序是一樹形選擇排序，在排序過程中，將R1.N看成是一顆完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。2. 堆的定義: N個元素的序列K1,K2,K3,.,Kn.稱為堆，當且僅當該序列滿足特性：KiK2i Ki K2i+1(1 I N/2)六、幾種排序算法的比較和選擇 1. 選取排序方法需要考慮的因素：(1) 待排序的元素數目n；(2) 元素本身信息量的大小；(3) 關鍵字的結構及其分布情況；(4) 語言工具的條件，輔助空間的大小等。2. 小結：(1) 若n較小(n <= 50)，則可以采用直接插入排序或直接選擇排序。由于直接插入排序所需的記錄移動操作較直接選擇排序多，因而當記錄本身信息量較大時，用直接選擇排序較好。(2) 若文件的初始狀態已按關鍵字基本有序