【正文】 在計算機系統(tǒng)中，需要用隊列來完成對作業(yè)或?qū)ο到y(tǒng)設備如打印池的處理。在Delphi的 VCL中，有現(xiàn)成的 TStack抽象數(shù)據(jù)類型可以使用。其中， TList是 Delphi中最基本的鏈表，它能實現(xiàn)鏈表常用的操作，包括：增加、刪除、定位、查找、遍歷等，這足夠解決一切關于有序列表的問題。 ? 抽象數(shù)據(jù)類型（ ADT）就是與對該數(shù)據(jù)類型有意義的操作封裝在一起的數(shù)據(jù)聲明。換句話說，可以通過判斷排除一半的列表。 ? 對有序的列表可以使用更有效率的折半查找。一個含有 n個元素的列表，冒泡排序需要 n1次掃描來完成數(shù)據(jù)排序。其中，動態(tài)數(shù)組可以使用不確定的數(shù)組長度，而在程序中動態(tài)地分配數(shù)組的存儲空間。 Delphi程序設計 本章小結(jié) ? 集合類型是一群相同類型元素的組合，這些類型必須是有限類型。 ? 迭代和遞歸是用于編寫解決問題的算法的兩種途徑。排序是為了把不規(guī)則的信息進行整理，以提高查找效率。 Delphi程序設計 本章小結(jié) ? 常用算法包括基本算法、排序算法、查找算法、迭代和遞歸算法等。 PAD的目的在于以圖表現(xiàn)程序的邏輯結(jié)構(gòu)，使程序易讀、易記、易理解。 ? 算法不依賴于具體的編程語言，它可以用偽代碼和圖形這兩種方式來描述。隊列的結(jié)構(gòu)特點是先進隊列的元素先出隊列。 ? 回溯也是一種棧的重要應用。 Delphi程序設計 棧 1. 棧的基本操作 棧有許多操作，基本操作有入棧和出棧。 ? 棧有兩種存儲結(jié)構(gòu)即順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。對于棧來說，允許進行插入或刪除操作的一端稱為棧頂（ top），而另一端稱為棧底（ bottom）。 Delphi程序設計 鏈表 2. 鏈表的應用 TList是 Delphi中最基本的鏈表，它能實現(xiàn)鏈表常用的操作，包括增加、刪除、定位、查找以及遍歷等，這就可以解決一切關于有序列表的問題。 1000 A 1200 B 1312 C 1423 head 1000 1200 1312 D 1423 鏈表示意圖 Delphi程序設計 鏈表 （ 2） 循環(huán)鏈表 將單鏈表的形式稍加改動，讓表中最后一個結(jié)點的指針指向單鏈表的表頭結(jié)點，這樣就形成了一個循環(huán)鏈表， h r 非空循環(huán)鏈表 r h 空表 循環(huán)鏈表的示意圖 Delphi程序設計 鏈表 （ 3） 雙向鏈表 在單鏈表中，從任何一個結(jié)點能通過指針域找到它的后繼結(jié)點，但無法找到它的前趨結(jié)點，而雙向鏈表則正是彌補了單鏈表的這個不足。線性列表是一種具有順序結(jié)構(gòu)的列表，在該列表中每個元素都有唯一的后繼元素。 Delphi程序設計 數(shù)據(jù)類型的層次結(jié)構(gòu) 類型（ type），指特定類別數(shù)據(jù)對象的集合（即通常出現(xiàn)在 Delphi中作為 Type聲明的部分）。用戶可通過操作接口對數(shù)據(jù)進行輸入、存取、修改和刪除等操作。 Delphi程序設計 數(shù)組參數(shù) 2. 變體開放式數(shù)組參數(shù) 與上述開放式數(shù)組參數(shù)略有不同的，變體開放數(shù)組參數(shù)允許向單個過程或函數(shù)傳遞不同類型表達式的數(shù)組。所謂開放式數(shù)組，是指使用數(shù)組作為形參傳遞給過程或函數(shù)時，其長度是不確定的。有人不知道誰和誰結(jié)婚，于是詢問了六位新人中的三位，但聽到的回答是這樣的： A說他將和 X結(jié)婚； X說她的未婚夫是 C； C說他將和 Z結(jié)婚。有人不知道誰和誰結(jié)婚，于是詢問了六位新人中的三位，但聽到的回答是這樣的： A說他將和 X結(jié)婚； X說她的未婚夫是 C； C說他將和 Z結(jié)婚。通常有兩種結(jié)果，一種是能夠檢索到，即查找成功，此時查找的結(jié)果為給出整個元素的信息，或指出該元素所在的位置；另一種是找不到，即失敗，此時查找的結(jié)果為不成功的信息。它（這次以升序排列為例）的基本思想是：首先選取某個元素 u，通過一趟排序?qū)⒋判虻臄?shù)組元素分割成獨立的兩部分，其中前一部分元素的均比 u小，而后一部分元素均比 u大，然后再分別對這兩部分元素繼續(xù)進行排序，被分成的兩個部分以后不用再歸并，最終達到整個數(shù)組序列有序。 39。 39。 39。 39。 39。 ? BubbleSort(a)。 a[7]:=9。 a[3]:=3。 ? var ? a:Arraytype。 ? BubbleArray[j+1]:=temp。 ? procedure BubbleSort(var BubbleArray:Arraytype)。 Delphi程序設計 排序 1. 冒泡排序 冒泡法是最簡單的排序方法。 其中 myArray[0,0]表示數(shù)組第一個元素， myArray[5,7]表示該 數(shù)組的最后一個元素。 Delphi程序設計 動態(tài)數(shù)組 ? （ 2）多維動態(tài)數(shù)組 Type TmyArray= array of array of integer 。 End。 Begin SetLengeth(A,1)。 如要為數(shù)組分配內(nèi)存，則 SetLength(myArray,50)。取而代之的是，向動態(tài)數(shù)組賦值或把動態(tài)數(shù)組傳遞給 SetLength過程時，動態(tài)數(shù)組的內(nèi)存被重新分配。 那么， array4:=array6是否合法 ? array4:=array6是不合法的，系統(tǒng)認為是兩種不同類型，容易產(chǎn)生類 型相容問題。 array6: array[1..10] of real。 Delphi程序設計 靜態(tài)數(shù)組 （ 3）靜態(tài)數(shù)組的整體賦值 Type TMyArray＝ array[1..10] of real。 Var myArray:TMyArray。 Var myArray:TMyArray。從定義可以看出，靜態(tài)數(shù)組中元素的數(shù)量是有限的，其大小是所有索引類型范圍的乘積。數(shù)組中每個元素都有一個唯一的索引，因此，同一數(shù)組中可以含有多個相同的值。b39。 。 CharSet := CharSet[‘a(chǎn)’, ‘b’]。 Exclude(CharSet, ‘a(chǎn)’)。 Include(T1, ‘2’)。 TChar= set of (‘a(chǎn)’,’b’,’c’)。在檢查一個值是否屬于一個特定集合時，集合類型非常有用。Fibonacci數(shù)列的值為： 39。)。 var x:string。 {$APPTYPE CONSOLE} Uses SysUtils。 readln。 outCome:=FIB(strtoint(x))。 begin write(39。 result:=F[Num]。 //此時 F數(shù)組的元素為 F[0]F[num] F[1]:=0。 function FIB(Num:integer):integer。 現(xiàn)在的任務是如何求得 Fibonacci數(shù)列中的第 n個數(shù)。 Delphi程序設計 算法復雜性分析 * 1. 時間復雜性 時間復雜性描述了算法在計算機上執(zhí)行時，所占用的計算機時間資源的情況。 ? 遞歸 遞歸是一個算法自我調(diào)用的過程，用遞歸調(diào)用的算法就是遞歸算法。順序查找可以在任何列表中查找，折半查找則需要列表是有序的。這三種方法是程序設計中使用的快速排序的基礎。這類算法在程序中應用非常普遍，如：累加求和、累乘求積、求最大和最小值等。流程圖是最常用的算法圖形表示法。用以提高程序的設計、制造、檢查、維護等的生產(chǎn)效率