數(shù)據(jù)結(jié)構(gòu)與簡單算法

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

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

3、上通常使用二維數(shù)組。二維數(shù)組的一個形象比喻多個縱隊形成的方塊 m * n 數(shù)組地址計算問題題目描述：已知N*(N+1) / 2個數(shù)據(jù)，按行的順序存入數(shù)組b1,b2,中。其中第一個下標表示行，第二個下標表示列。若aij (i>=j ,j=1,2,n)存于bk中，問：k,i,j之間的關(guān)系如何表示？給定k值，寫出能決定相應(yīng)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,對應(yīng)的i,j為：,i,j) 棧特殊的線性表操作特點：后進先出（

4、Last In First Out）棧頂表尾棧底表頭空棧 棧 （考題分析）（1998） 棧S初始狀態(tài)為空，現(xiàn)有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)。 循環(huán)隊列頭指針指向隊列中隊頭元素的前一個位置，尾指針指示隊尾元素在隊列中的當前位置。(R-F+N) mod N 樹根、葉子、子樹結(jié)點的度：結(jié)點擁有的子樹數(shù)

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

6、中的適當位置，使數(shù)列依然有序；直到待排序數(shù)據(jù)元素全部插入完為止。2. 排序過程： 【示例】：初始關(guān)鍵字 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是監(jiān)視哨/ 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. 基本思想：每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，順序放

8、在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。2. 排序過程： 【示例】： 初始關(guān)鍵字 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最后排序結(jié)果 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 /在當前無序區(qū)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. 基本思想：兩兩比較待排序數(shù)據(jù)元素的大小，發(fā)現(xiàn)兩個數(shù)據(jù)元素的次序相反時即進行交換，直到?jīng)]有反序的數(shù)據(jù)元素為止。2. 排序過程：設(shè)想被排序的數(shù)組R1.N垂直豎立，將每個數(shù)據(jù)元素看作有重量的氣泡，根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組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/本趟排序中未發(fā)生交換，則終止算法/ endEnd; /BubbleSort/四、快速排序（Quick Sort）1. 基本思想：在當前無序區(qū)R1.H中任取一個數(shù)據(jù)元素作為比較的"基準"(不妨記為X)，用此基準將當前無序區(qū)劃分為左右兩個較小的無序區(qū)：R1.I-1和RI+1.H，且左邊的無序子區(qū)中數(shù)據(jù)元素均小于等于基準元素，右邊的無序子區(qū)中數(shù)據(jù)元素均大于等于基準元素，而基準X則位于最終排序的位置上，即R

13、1.I-1X.KeyRI+1.H(1IH)，當R1.I-1和RI+1.H均非空時，分別對它們進行上述的劃分過程，直至所有無序子區(qū)中的數(shù)據(jù)元素均已排序為止。2. 排序過程： 【示例】：初始關(guān)鍵字 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、程） 初始關(guān)鍵字 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最后的排序結(jié)果 13 27 38 49 49 65 76 97 各趟排序之后的狀態(tài)Procedure Parttion(Var R : FileType; L, H : Integer; Var I : Integer);/對無序區(qū)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);/遞歸處理左區(qū)間RS,I-1/ QuickSort(R, I+1,T);/遞歸處理右區(qū)間RI+1.T / end;End; /Quick

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