大學計算機基礎第4章

1、n 基本概念基本概念n 基本數(shù)據(jù)結構基本數(shù)據(jù)結構n 常用算法常用算法1 1什么是數(shù)據(jù)結構什么是數(shù)據(jù)結構 數(shù)據(jù)數(shù)據(jù)：是對客觀事物的符號表示，在計算機科學是對客觀事物的符號表示，在計算機科學中是指能輸入到計算機中并被計算機存儲、加工的符中是指能輸入到計算機中并被計算機存儲、加工的符號總稱。號總稱。 數(shù)據(jù)元素數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，由若干個數(shù)據(jù)項組是數(shù)據(jù)的基本單位，由若干個數(shù)據(jù)項組成，在程序中作為一個整體而加以考慮和處理。數(shù)據(jù)成，在程序中作為一個整體而加以考慮和處理。數(shù)據(jù)元素具有完整確定的實際意義，有時也稱為元素具有完整確定的實際意義，有時也稱為元素、結元素、結點、頂點或記錄。點、頂點或記錄。結

2、構結構：是數(shù)據(jù)元素之間的關聯(lián)關系是數(shù)據(jù)元素之間的關聯(lián)關系 。 通俗地說：通俗地說：數(shù)據(jù)結構是帶有結構的同性質數(shù)據(jù)元素數(shù)據(jù)結構是帶有結構的同性質數(shù)據(jù)元素的集合。的集合。2 2數(shù)據(jù)結構研究的三個方面：數(shù)據(jù)結構研究的三個方面：邏輯結構、存儲結構、和對數(shù)據(jù)的操作邏輯結構、存儲結構、和對數(shù)據(jù)的操作 1 1） 邏輯結構邏輯結構：數(shù)據(jù)元素之間邏輯上的關系，它是數(shù)數(shù)據(jù)元素之間邏輯上的關系，它是數(shù)據(jù)的組織形式。據(jù)的組織形式。通常將數(shù)據(jù)的通常將數(shù)據(jù)的邏輯結構邏輯結構簡稱為簡稱為數(shù)據(jù)結數(shù)據(jù)結構，構，數(shù)據(jù)的邏輯結構分成如下的四種結構：數(shù)據(jù)的邏輯結構分成如下的四種結構： A A： 其中其中C C 、D D為非線性結構為

3、非線性結構集合集合 線性結構線性結構樹型結構樹型結構 圖狀結構圖狀結構 2）存儲結構：）存儲結構：數(shù)據(jù)元素數(shù)據(jù)元素以及以及數(shù)據(jù)元素數(shù)據(jù)元素之間的邏輯關系之間的邏輯關系在計算機內存中的表示。在計算機內存中的表示。 一般地，一個存儲結構包括以下兩個主要部分：一般地，一個存儲結構包括以下兩個主要部分：數(shù)據(jù)元素的存儲：數(shù)據(jù)元素的存儲：用一個存儲單元用一個存儲單元( (簡稱結點簡稱結點) )存放每存放每一個數(shù)據(jù)元素一個數(shù)據(jù)元素, ,每個存儲單元稱為一個結點。每個存儲單元稱為一個結點。數(shù)據(jù)元素之間關系的存儲：數(shù)據(jù)元素之間關系的存儲：也就是邏輯結構在計算機也就是邏輯結構在計算機內部的表示。內部的表示。 數(shù)據(jù)

4、的四種常用的存儲結構：數(shù)據(jù)的四種常用的存儲結構：順序順序存儲方法存儲方法鏈式鏈式存儲方法存儲方法索引索引存儲方法存儲方法散列散列存儲方法存儲方法3） 數(shù)據(jù)的運算：數(shù)據(jù)的運算：查找，排序、增加，修改，刪除查找，排序、增加，修改，刪除等等，這些運算都是，這些運算都是邏輯結構邏輯結構上的操作。上的操作。1 1、算法、算法算法是對具體問題求解過程和步驟的一種描述。算法是對具體問題求解過程和步驟的一種描述。例例1 1：比較兩個數(shù)：比較兩個數(shù)a,ba,b，將兩個數(shù)中大的數(shù)顯示出來。，將兩個數(shù)中大的數(shù)顯示出來。操作步驟：操作步驟：1 1）輸入兩個數(shù)）輸入兩個數(shù)a,ba,b的值的值2 2）比較）比較a,ba,

5、b兩個數(shù)，如兩個數(shù)，如果果a a大于大于b b，則輸出，則輸出a a的值；的值；否則輸出否則輸出b b的值。的值。實現(xiàn)的代碼：實現(xiàn)的代碼：Input “輸入輸入a的值的值:” to aInput “輸入輸入b的值的值:” to bIf ab ?aElse ?bEndif2 2、算法的、算法的 5 5 個特性。個特性。 有窮性有窮性 確定性確定性可行性可行性 零個或多個的輸入零個或多個的輸入 有有1 1個或多個的輸出個或多個的輸出 3 3算法設計的要求算法設計的要求 正確性正確性 可讀性可讀性 健壯性健壯性 效率高與低存儲量需求效率高與低存儲量需求4 4、算法性能描述、算法性能描述 算法的算法的

6、時間復雜度和空間復雜度時間復雜度和空間復雜度 v算法的時間性能算法的時間性能時間復雜度：時間復雜度：是指算法中所是指算法中所包含簡單操作的執(zhí)行次數(shù)。包含簡單操作的執(zhí)行次數(shù)。 一般是算法中執(zhí)行一般是算法中執(zhí)行頻度最大的語句頻度。頻度最大的語句頻度。v空間復雜度：空間復雜度：指算法執(zhí)行過程中所占用的存儲空間。指算法執(zhí)行過程中所占用的存儲空間。 v時間復雜度和空間復雜度都與問題的規(guī)模時間復雜度和空間復雜度都與問題的規(guī)模n有關有關，可以采用，可以采用T(n),S(n)表示。表示。常見的時間復雜度，按數(shù)量級遞增排列依次常見的時間復雜度，按數(shù)量級遞增排列依次為：為：O(1)O(log2n)O(n)O(nl

7、og2n)O(n2)O(n3) O(nk)O(2n)。求求1100個數(shù)據(jù)的和值。個數(shù)據(jù)的和值。main()int i,s; i=1,s=0; while ( ) Printf(“s=%dn”,s); 比較兩個數(shù)據(jù)比較兩個數(shù)據(jù)a,b，將大的數(shù)，將大的數(shù)據(jù)保存在據(jù)保存在a變量中。變量中。Main()int a,b,c; scanf(“%d%d”,&a,&b); if (ab) printf(“%d”,a);c=ab=ca=bs=s+ii=i+1ib輸出輸出a的值的值輸出輸出b的值的值結束結束YN比較比較a,b的值，的值，輸出兩個數(shù)中大輸出兩個數(shù)中大的數(shù)的流程圖的數(shù)的流程圖一、線性表

8、一、線性表1 1、線性表、線性表: 是是n(nO)n(nO)個同類型數(shù)據(jù)元素個同類型數(shù)據(jù)元素( (結點結點) )的有窮的有窮序列。序列。表示成：表示成：(a(a1 1，a a2 2 ，a an n) ) ，n n為為0 0則為空表。則為空表。例如：例如：12 34 43 57 62 74 33 23 9012 34 43 57 62 74 33 23 902626個英文字母表（個英文字母表（A,B,C,D,A,B,C,D,Z Z）2 2、線性表邏輯結構的基本特征、線性表邏輯結構的基本特征 存在惟一的一個被稱為存在惟一的一個被稱為“第一個第一個”的數(shù)據(jù)元素；的數(shù)據(jù)元素； 存在惟一的一個被稱為存在

9、惟一的一個被稱為“最后一個最后一個”的數(shù)據(jù)元素；的數(shù)據(jù)元素； 除第一個結點外，其他結點有且僅有一個除第一個結點外，其他結點有且僅有一個直接前趨直接前趨； 除最后一個結點外除最后一個結點外, ,其他結點有且僅有一個其他結點有且僅有一個直接后繼直接后繼。 所含結點的個數(shù)稱為所含結點的個數(shù)稱為線性表的長度線性表的長度( (簡稱表長簡稱表長) )。 表長為表長為O O的線性表稱為空表。的線性表稱為空表。3、線性表的順序存儲結構、線性表的順序存儲結構 用一組用一組地址連續(xù)地址連續(xù)的存儲單元依次存儲線性表的數(shù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，該結構稱為據(jù)元素，該結構稱為順序表順序表。元素元素a a1 1

10、a a2 2a ai-1i-1a ai ia ai+1i+1 a an n相對地址相對地址1 12 2i-1i-1i in-1n-1n特點：特點：邏輯結構中相鄰的結點在存儲結構中仍相鄰邏輯結構中相鄰的結點在存儲結構中仍相鄰。10203040506078若若順序存放順序存放10,20,30,40,50,60,其物理存儲結構如下：其物理存儲結構如下：30013002300330043005300630073200內存內存地址地址存儲單元存儲單元返回元素元素a a1 1a a2 2a ai-1i-1a ai ia an n相對地址相對地址1 12 2i-1i-1i in(1)(1)插入插入(2)(2

11、)刪除刪除 元素元素a a1 1a a2 2a ai-1i-1a ai i a an n相對地址相對地址1 12 2i-1i-1i i n n3152224 24 221831518222418 22 24插入插入18刪除刪除151 1）含義：）含義：單單鏈表鏈表是用是用一組任意的不連續(xù)的存儲單元一組任意的不連續(xù)的存儲單元來存來存放線性表的結點。放線性表的結點。 5、單鏈表單鏈表線性表的鏈式存儲結構線性表的鏈式存儲結構a1a2an head結點結點2 2）結點組成：）結點組成：由由數(shù)據(jù)域數(shù)據(jù)域(data)(data)和和指針域指針域(next)(next)兩部分兩部分組成。組成。v數(shù)據(jù)域數(shù)據(jù)域

12、用于存儲線性表一個數(shù)據(jù)元素；用于存儲線性表一個數(shù)據(jù)元素；v指針域指針域存放一個指針，存放一個指針，指向其直接后繼結點指向其直接后繼結點。特點：指針為數(shù)據(jù)元素之間邏輯關系的反映特點：指針為數(shù)據(jù)元素之間邏輯關系的反映233045datanext例如：例如：10 ，124，50，956四個數(shù)的存放關系如下：四個數(shù)的存放關系如下：1021095022101242106.956210421052106210721082109211022102211存儲地址存儲地址存儲單元存儲單元一個單元存放一個單元存放數(shù)據(jù)數(shù)據(jù)，另一個存放另一個存放下一個下一個數(shù)據(jù)的地址數(shù)據(jù)的地址返回315222401831522240

13、18插入插入刪除刪除3） 其他鏈表其他鏈表循環(huán)鏈表：循環(huán)鏈表：是一種首尾相接的鏈表。是一種首尾相接的鏈表。 雙向鏈表：雙向鏈表：就是在單鏈表的每個結點里再增加一個指向其就是在單鏈表的每個結點里再增加一個指向其直接前趨的指針域直接前趨的指針域prior，這樣形成的鏈表就有，這樣形成的鏈表就有兩條不同方向的兩條不同方向的鏈鏈。 a1 a2anhead an a1a2head二、二、棧和隊列棧和隊列 棧和隊列棧和隊列都是都是操作受限的線性表。操作受限的線性表。是線是線性表的兩種特例。性表的兩種特例。 v棧是先進后出棧是先進后出v隊列是先進先出隊列是先進先出 棧的邏輯結構和線性表相同，棧的邏輯結構和線

14、性表相同，但棧但棧(Stack)是僅限在表的是僅限在表的進行進行插入和刪除運算的線性表，通常稱插入和刪除運算的線性表，通常稱插入、刪除這一端為插入、刪除這一端為棧頂棧頂，另一端，另一端稱為稱為棧底棧底,表中無元素時為空棧。表中無元素時為空棧。棧底棧底棧頂棧頂入棧入棧出棧出棧a1a2 an1、棧棧22153 18例如：例如：A A，B B，C C，D D四個元素依次進棧，可能的出棧順四個元素依次進棧，可能的出棧順序有幾種？序有幾種？1 1）D,C,B,A 2)C,B,D,AD,C,B,A 2)C,B,D,A3) A,B,C,D 4)B,C,A,D 3) A,B,C,D 4)B,C,A,D 5)

15、C,A,B,D 6)C,D,A,B 5) C,A,B,D 6)C,D,A,B 插入只能在表的一端進行插入只能在表的一端進行(只進不出只進不出)，而刪除只能，而刪除只能在表的另一端進行在表的另一端進行(只出不進只出不進)，允許刪除的一端稱為隊頭，允許刪除的一端稱為隊頭(Front)，允許插入的一端稱為隊尾，允許插入的一端稱為隊尾 (rear),空隊列時頭指空隊列時頭指針和尾指針指向同一個位置針和尾指針指向同一個位置 。 2、隊列隊列(Queue)31522隊頭隊頭隊尾隊尾出隊出隊(刪除刪除)入隊入隊(插入插入) 18三、三、樹樹AFBDEGC根結點根結點子樹子樹1、樹的概念樹的概念樹是樹是n(n

16、0)n(n0)個結點的有限集合。在任意一棵非空樹中個結點的有限集合。在任意一棵非空樹中有且僅有一個特定的稱為根的結點：有且僅有一個特定的稱為根的結點：當當nlnl時，其余結點分為時，其余結點分為m(m0)m(m0)個個互不相交互不相交的非空集合的非空集合, ,其中每一個集合本身又是一棵樹，并稱為根的其中每一個集合本身又是一棵樹，并稱為根的子樹子樹。樹是一種樹是一種“”結構。結構。 ACBDEFGHKIJ2、樹型結構的有關術語及其含義樹型結構的有關術語及其含義v 結點的度結點的度: :任一結點所擁有的任一結點所擁有的子樹子樹的數(shù)目。的數(shù)目。v樹的度：樹的度：所有結點所有結點度的最大值度的最大值。

17、v分支結點和終端結點（葉子）分支結點和終端結點（葉子）v孩子結點、雙親結點和兄弟結點孩子結點、雙親結點和兄弟結點v樹的深度：樹的深度：所有結點所有結點層數(shù)的最大值層數(shù)的最大值稱為該稱為該。 AFBDEGCABCDEFGH左子樹左子樹右子樹右子樹1 1）概念：）概念：二叉樹二叉樹是結點的有窮集合，它或者是空集是結點的有窮集合，它或者是空集，或者同時滿足下述兩個條件：，或者同時滿足下述兩個條件： 有且僅有一個稱為有且僅有一個稱為根的結點根的結點； 其余結點分為其余結點分為兩個互不相交的集合兩個互不相交的集合T1T1、T2T2，T1T1與與T2T2都是二叉樹，并且都是二叉樹，并且TlTl與與T2T2

18、有順序關系有順序關系(T1(T1在在T2T2之前之前) )，它們分別稱為根的它們分別稱為根的左子樹左子樹和和右子樹右子樹。 二叉樹的每個結點二叉樹的每個結點至多只有兩棵子樹至多只有兩棵子樹，分別稱為，分別稱為左、右子樹。左、右子樹。2 2）二叉樹的）二叉樹的基本形態(tài)基本形態(tài)空樹空樹只有根節(jié)點只有根節(jié)點只有左子樹只有左子樹只有右子樹只有右子樹有左右子樹有左右子樹3 3）二叉樹的基本性質）二叉樹的基本性質二叉樹第二叉樹第i(i1)i(i1)層上至多有層上至多有2 2i-1i-1個結點。個結點。 ABCDEFGH深度為深度為k(k1)k(k1)的二叉樹至多有的二叉樹至多有2 2k k-1-1個結點。

19、個結點。 對任何一棵二叉樹，如果其終端對任何一棵二叉樹，如果其終端結點數(shù)為結點數(shù)為n n0 0，度為，度為2 2的結點數(shù)為的結點數(shù)為n n2 2，則則n n0 0 = n = n2 2+1+1。ABCDFGEHIABEDFGC1 1）滿二叉樹：）滿二叉樹：一棵深度為一棵深度為k(k1)k(k1)且有且有2 2k k-1-1個結點的個結點的二叉樹稱為滿二叉樹，這種樹的每一層上的結點數(shù)都二叉樹稱為滿二叉樹，這種樹的每一層上的結點數(shù)都是最大結點數(shù)。是最大結點數(shù)。 4 4、滿二叉樹和完全二叉樹、滿二叉樹和完全二叉樹1245732 2）完全二叉樹：）完全二叉樹：深度為深度為k(k1)k(k1)有有n n

20、個結點的二叉樹，個結點的二叉樹，當且僅當其每一個結點都與深度為當且僅當其每一個結點都與深度為k k的滿二叉樹中編號的滿二叉樹中編號從從1 1至至n n的結點一一對應時，稱之為完全二叉樹。的結點一一對應時，稱之為完全二叉樹。 完全二叉樹的特性：完全二叉樹的特性：具有具有n n個結點的完全二叉樹的深度為個結點的完全二叉樹的深度為 loglog2 2n +ln +l。12457368vi i結點的雙親結點編號為結點的雙親結點編號為 /2 /2 。vi i結點的左孩子的編號為結點的左孩子的編號為2i2i。vi i結點的右孩子的編號為結點的右孩子的編號為2i+12i+1。如果將一棵有如果將一棵有n n個

21、結點的完全二叉樹按層個結點的完全二叉樹按層編號，則對任一編號為編號，則對任一編號為i i的結點有如下特性：的結點有如下特性：12457368例例: :已知完全二叉樹有已知完全二叉樹有100個結點個結點, ,該二叉樹有多該二叉樹有多少個葉子結點少個葉子結點? ?12457368二叉樹順序存儲二叉樹順序存儲 將一棵完全二叉樹中的所有將一棵完全二叉樹中的所有n n個結點個結點按層按層編號，編號，將結點存于將結點存于一組地址連續(xù)一組地址連續(xù)的存儲單元中，即編號為的存儲單元中，即編號為i i的結點存入第的結點存入第i i個存儲單元中。個存儲單元中。 5 5、二叉樹的存儲結構、二叉樹的存儲結構123456

22、789101112例如：下圖的完全二叉樹對應的存例如：下圖的完全二叉樹對應的存儲結構圖：儲結構圖：3201320232033204320532063207320832093210321132121234567320132023203320432053206320732083209321032113212例如：非完全二叉樹對例如：非完全二叉樹對應的存儲結構：應的存儲結構：綠色標識的結點為虛設綠色標識的結點為虛設的結點的結點若二叉樹不是完全二叉樹，則通過在非完全若二叉樹不是完全二叉樹，則通過在非完全二叉樹的二叉樹的“殘缺殘缺”位置上增設位置上增設“虛結點虛結點”將將其轉化為完全二叉樹。其轉化為完全

23、二叉樹。 用順序存儲方式對于完全二叉樹而言其用順序存儲方式對于完全二叉樹而言其結構簡單又節(jié)省空間，但是對于一般二叉樹結構簡單又節(jié)省空間，但是對于一般二叉樹并不合適。并不合適。 二叉樹的二叉樹的 結點結構中設兩個指針域結點結構中設兩個指針域和和分別指向該結分別指向該結點的點的和和，另有一個另有一個數(shù)據(jù)域數(shù)據(jù)域存放結點數(shù)存放結點數(shù)據(jù)據(jù). 6 6、二叉樹的遍歷、二叉樹的遍歷 按某種次序按某種次序“訪問訪問”二叉樹上的所有結點，二叉樹上的所有結點，使每個結點被訪問一次，而且僅被訪問一次。使每個結點被訪問一次，而且僅被訪問一次。 先根遍歷先根遍歷( (先序先序):):根左右根左右 中根遍歷中根遍歷( (

24、中序中序):):左根右左根右 后根遍歷后根遍歷( (后序后序):):左右根左右根 先序先序中序中序后序后序ABCDEFGHIKCBEDAGHFKIABCEDFGIHKABCDEFGHIKABCEDFGIHKCBEDAGHFKIABCEDFGIHKCEDBHGKIFA先序先序AB CD E FG H I JA中序中序CDB F E AI H GJABCEDFGIHJB CCDB F E AI H GJABCEEG HGH例如：例如：已知某已知某二叉樹二叉樹的的先序先序和中序和中序遍歷遍歷,寫寫出后序出后序遍歷遍歷.網站：211.64.202.231考試代號：1938500可用學號：2009040

25、01200904300 一、一、 查找查找就是從一個就是從一個中找出某中找出某個個或找出滿足某類特征的數(shù)或找出滿足某類特征的數(shù)據(jù)元素的過程。據(jù)元素的過程。 查找查找實際上就是進行實際上就是進行比較比較的過程，比較的的過程，比較的次數(shù)次數(shù)作為評價查找算法的效率指標作為評價查找算法的效率指標，該指標稱為查找算，該指標稱為查找算法的法的平均查找長度平均查找長度。1 1、順序查找、順序查找1 1）查找過程）查找過程： 例如：在如下的序列中查找例如：在如下的序列中查找“15”的處理過的處理過程。程。 12 45 32 5 78 28 60 15 49 815 15 151515151515成功成功2 2

26、）平均查找長度：）平均查找長度：為確定元素在查找表中的位置，為確定元素在查找表中的位置，需和給定值進行比較的元素個數(shù)的期望值。需和給定值進行比較的元素個數(shù)的期望值。 長度為長度為n n的順序表，在等概率情況下查找成功的的順序表，在等概率情況下查找成功的平均查找長度為：平均查找長度為： (n+1)(n+1)2 23 3）順序查找的優(yōu)缺點：）順序查找的優(yōu)缺點：優(yōu)點：優(yōu)點：算法簡單，無須排序，順序或鏈式存儲結算法簡單，無須排序，順序或鏈式存儲結構都可以。構都可以。缺點：缺點：平均查找長度較大。平均查找長度較大。2 2、二分查找、二分查找( (折半查找折半查找) )算法算法 對于任何一個對于任何一個，

27、若其中的所有結點按，若其中的所有結點按鍵鍵值的某種次序排列，則稱為值的某種次序排列，則稱為 用中間位置上的數(shù)據(jù)元素與給定值用中間位置上的數(shù)據(jù)元素與給定值K K比較比較: :若若K K等于中間元素的值，則查找成功，查找結束。等于中間元素的值，則查找成功，查找結束。若若K K比中間值大則舍棄前半部分比中間值大則舍棄前半部分. .若若K K比中間值小則舍棄后半部分比中間值小則舍棄后半部分. .在新的區(qū)間內重復上述過程，直到查找成功或查在新的區(qū)間內重復上述過程，直到查找成功或查找區(qū)間長度為找區(qū)間長度為0(0(即查找不成功即查找不成功) )為止。為止。 基基 本本 步步 驟驟10 16 20 36 46

28、 68 80 983636686846 對于長度為對于長度為n的有序線性表，在最壞的情況的有序線性表，在最壞的情況下，二分查找需比較下，二分查找需比較log2n次。次。 順序查找需比較順序查找需比較n次。次。 比順序查找的比順序查找的平均查找長度小平均查找長度小，查，查找速度快。找速度快。 只限于只限于順序存儲結構的有序表。順序存儲結構的有序表。排序排序: :將一個無序序列按照關鍵字的大小排列成有將一個無序序列按照關鍵字的大小排列成有序序列。序序列。常用的排序算法：常用的排序算法：直接插入排序、冒泡排序、選直接插入排序、冒泡排序、選擇法排序。擇法排序。排序的基本步驟：排序的基本步驟：比較比較

29、移動元素位置移動元素位置23621236 7214585算法：算法：依次將無序表中每個記錄插入到一個有序的依次將無序表中每個記錄插入到一個有序的子序列中去。子序列中去。1 1、直接插入排序、直接插入排序例如：將序列例如：將序列12 5 78 34 26 9 排成有序序列排成有序序列 。 初初 始始12第一趟第一趟5 12第二趟第二趟5 12 78第三趟第三趟5 12 34 78 第四趟第四趟5 12 26 34 78 第五趟第五趟5 9 12 26 34 78 最理想的情況：最理想的情況：各記錄已排好序，則關鍵字比較次數(shù)為各記錄已排好序，則關鍵字比較次數(shù)為n-n-1(1(最小值最小值) )，記

30、錄的移動次數(shù)為，記錄的移動次數(shù)為0(0(最小值最小值) )，則時間復雜度，則時間復雜度是是o(n)o(n)。例如：例如：5 16 33 67 895 16 33 67 89直接插入排序算法的時、空性能：直接插入排序算法的時、空性能：最差的情況：最差的情況：各記錄是逆序時，關鍵字比較次數(shù)為各記錄是逆序時，關鍵字比較次數(shù)為(n+2)(n-1)/2(n+2)(n-1)/2；記錄的移動次數(shù)為；記錄的移動次數(shù)為(n-1)(n+4)/2(n-1)(n+4)/2，則時，則時間復雜度為間復雜度為o(no(n2 2) )，空間復雜度為，空間復雜度為o(1)o(1)。例如：例如：89 67 33 16 589 6

31、7 33 16 5直接插入排序是穩(wěn)定排序。直接插入排序是穩(wěn)定排序。穩(wěn)定排序：穩(wěn)定排序：在排序過程中，關鍵字相同的兩個元素的相對在排序過程中，關鍵字相同的兩個元素的相對次序不變，則為穩(wěn)定排序。次序不變，則為穩(wěn)定排序。例如：例如：34 6 27 89 12 27 4534 6 27 89 12 27 45算法：算法：將第一個元素和后面的元素比較，若為逆序，將第一個元素和后面的元素比較，若為逆序，則將兩個元素交換，然后依此往后比較。則將兩個元素交換，然后依此往后比較。完成完成第一趟排序第一趟排序，值最大的元素被安置到最后一個位，值最大的元素被安置到最后一個位置上，然后進行第二趟冒泡排序，置上，然后進

32、行第二趟冒泡排序，直至排序結，直至排序結束。束。 2 2、冒泡排序、冒泡排序32125836124排序舉例排序舉例逆逆序序1232583612412325836124交交換換逆逆序序1232358612412323586124逆逆序序12323582461交交換換交交換換第一趟排序結果第一趟排序結果1233224586131224325861第二趟第二趟第三趟第三趟616158615832最理想的情況：最理想的情況：記錄已有序，關鍵字比較次數(shù)為記錄已有序，關鍵字比較次數(shù)為n-n-1(1(最小值最小值) )，記錄的移動次數(shù)為，記錄的移動次數(shù)為0(0(最小值最小值) )。其時間復。其時間復雜度是雜

33、度是O(n)O(n)。例如：例如：3 14 21 36 56 78 933 14 21 36 56 78 93冒泡排序算法的時、空性能冒泡排序算法的時、空性能冒泡排序是穩(wěn)定的排序冒泡排序是穩(wěn)定的排序最壞情況：最壞情況：記錄逆序時記錄逆序時, ,關鍵字比較次數(shù)為關鍵字比較次數(shù)為: : (n+2)(n-1)(n+2)(n-1)2(2(最大值最大值) )；記錄的移動次數(shù)為；記錄的移動次數(shù)為: : 3n(n-1)3n(n-1)2(2(最大值最大值) )。此時的時間復雜度為此時的時間復雜度為o(no(n2 2);); 空間復雜度是空間復雜度是o(1)o(1)。例如：例如：93 78 36 21 36 1

34、4 393 78 36 21 36 14 33 3、算法（按升序）算法（按升序）：1）在序列中先）在序列中先假定一個元素為最小假定一個元素為最小。2）用當前假定的最小值與后面的元素進行比較，若比）用當前假定的最小值與后面的元素進行比較，若比當前數(shù)小，則當前數(shù)小，則記錄當前最小數(shù)的位置記錄當前最小數(shù)的位置。3）用當前最小數(shù)與后面元素繼續(xù)比較，直到最后一個）用當前最小數(shù)與后面元素繼續(xù)比較，直到最后一個元素比較完，可以元素比較完，可以找到真正最小數(shù)的位置找到真正最小數(shù)的位置。4）將假定的最小數(shù)與真正最小數(shù)進行）將假定的最小數(shù)與真正最小數(shù)進行交換交換。5）再假定第二個最小數(shù)，再依次比較，找到第二個最）

35、再假定第二個最小數(shù)，再依次比較，找到第二個最小數(shù)，小數(shù)，例如：例如：34 78 23 16 3 42 29 67按升序排按升序排列。列。 1 2 3 4 5 6 7 834 782316 3422967P=1假假定定最最小小數(shù)數(shù)位位置置P=3P=4P=5真真正正最最小小數(shù)數(shù)位位置置交換交換 P=2第一趟比較的次數(shù)第一趟比較的次數(shù):7第一趟交換的次數(shù)第一趟交換的次數(shù):1 1 2 3 4 5 6 7 8378231634422967第二趟比較第二趟比較: P=2第二趟比較的次數(shù)第二趟比較的次數(shù):6第二趟交換的次數(shù)第二趟交換的次數(shù):1總共進行比較的次數(shù)總共進行比較的次數(shù):總共進行交換的次數(shù)總共進行交

36、換的次數(shù):77+6+5+4+3+2+1選擇排序算法的時、空性能選擇排序算法的時、空性能 不管待排序的不管待排序的n n個數(shù)據(jù)是否有序，直接選擇排序都要個數(shù)據(jù)是否有序，直接選擇排序都要執(zhí)行執(zhí)行n(n-1)n(n-1)2 2次比較。次比較。 有序序列，數(shù)據(jù)移動次數(shù)為有序序列，數(shù)據(jù)移動次數(shù)為0 0次。次。 逆序序列，則要移動逆序序列，則要移動(n-1)(n-1)次。次。時間復雜度是時間復雜度是o(no(n2 2) )，空間復雜度為，空間復雜度為o(1)o(1)。直接選。直接選擇排序是擇排序是不穩(wěn)定的排序不穩(wěn)定的排序。例如：例如：3434 23 23 34 34 8 78 2 15 51 8 78 2

37、 15 51 3 3、直接選擇排序、直接選擇排序 首先在所有的記錄中選出鍵值最小的記錄，把它與第一首先在所有的記錄中選出鍵值最小的記錄，把它與第一個記錄交換；然后在其余的記錄中再選出鍵值最小的記錄個記錄交換；然后在其余的記錄中再選出鍵值最小的記錄與第二個記錄交換；依次類推，直至所有記錄排序完成。與第二個記錄交換；依次類推，直至所有記錄排序完成。在第在第i i趟中，通過趟中，通過n-1n-1次鍵值比較選出所需記錄。次鍵值比較選出所需記錄。 直接選擇排序算法的時、空性能直接選擇排序算法的時、空性能如果待排序的記錄初始序列就是已排好序的正序，則不做如果待排序的記錄初始序列就是已排好序的正序，則不做記

38、錄移動，即移動記錄記錄移動，即移動記錄0 0次：如果待排序的記錄初始序列恰次：如果待排序的記錄初始序列恰好是逆序，則要做好是逆序，則要做3(n-1)3(n-1)次記錄移動次記錄移動 。 從表中第一個（或最后一個）元素開始，逐個進行元素從表中第一個（或最后一個）元素開始，逐個進行元素值和給定值的比較，若某個元素的值和給定值比較相等，值和給定值的比較，若某個元素的值和給定值比較相等，則查找成功；反之，若直至最后一個元素，其值和給定則查找成功；反之，若直至最后一個元素，其值和給定值比較都不等，則表明表中沒有所查數(shù)據(jù)，查找失敗。值比較都不等，則表明表中沒有所查數(shù)據(jù)，查找失敗?？偨浝碡攧詹拷浝砣耸虏拷浝?/p>

39、研發(fā)部經理銷售部經理 生產部經理例例2 2：求兩個數(shù)的最大公約數(shù)。：求兩個數(shù)的最大公約數(shù)。算法：（采用輾轉相除法）算法：（采用輾轉相除法）1 1）設兩個數(shù)分放到）設兩個數(shù)分放到m m和和n n兩個量中。兩個量中。2 2）用）用m m除以除以n n（即（即m/nm/n），取得余數(shù)），取得余數(shù)r r3)3)使使m m等于等于n n的值，的值，n n等于等于r r的值的值4 4）判斷）判斷r r，若，若r r為為0 0，則，則m m的值即為最大公約數(shù)的值即為最大公約數(shù)，否則繼續(xù)執(zhí)行，否則繼續(xù)執(zhí)行步驟步驟2 2）程序（程序（VFPVFP的描述）：的描述）：Input “Input “輸入輸入m m的值

40、：的值：” ” to mto mInput “Input “輸入輸入n n的值：的值：” ” to nto nr=nr=nDo while r0Do while r0 r=mod(m,n) r=mod(m,n) m=n m=n n=r n=rEnddoEnddo?m?m 6、插入、刪除運算在單鏈表上的實現(xiàn)插入、刪除運算在單鏈表上的實現(xiàn) (1)(1)插入：基本步驟如下：插入：基本步驟如下： 在單鏈表上找到插入位置；在單鏈表上找到插入位置； 生成一個值為生成一個值為x x的新結點；的新結點； 將新結點鏈入將新結點鏈入 假定指針假定指針p p指向單鏈表中的第指向單鏈表中的第i-1i-1個結點，個結點，s s指向已生成的指向已生成的新結點，在單鏈表上第新結點，在單鏈表上第i-1i-1個結點之后插入結點個結點之后插入結點s s的操作過程的操作過程如圖所示。如圖所示?；静僮髡Z句為：基本操作語句