第4章程序設計基礎ppt課件

1、第4章 程序設計根底學習目的了解程序設計的根底知識、程序設計風格的重要性、根本的查找和排序方法。掌握構造化程序設計方法和面向對象程序設計方法的思想、幾種根本的數(shù)據(jù)構造。學習計算機首先要學習程序設計，良好的程序設計技藝和風格有助于加深對計算機的了解和進一步學習。第4章 程序設計根底4.1 程序設計根底程序設計是指用計算機言語對所要處理的問題中的數(shù)據(jù)以及處置問題的方法和步驟所做的完好而準確的描畫的過程。程序設計步驟如下：(1) 確定要處理的問題。(2) 分析問題。在著手處理問題之前，應該經過分析，充分了解問題，明確原始數(shù)據(jù)、解題要求、需求輸出的數(shù)據(jù)及方式等。(3) 選擇計算方法。(4) 確定數(shù)據(jù)構

2、造和算法。算法是解題的過程。首先集中精神于算法的總體規(guī)劃，然后逐層降低問題的籠統(tǒng)性，逐漸充實細節(jié)，直到最終把籠統(tǒng)的問題詳細化成可用程序語句表達的算法。這是一個自上而下、逐漸細化的過程。4.1 程序設計根底(5) 繪制流程圖。(6) 編寫程序。利用程序設計言語表示算法，編寫代碼。(7) 調試并測試程序。調試程序包括編譯和銜接等操作。程序員還要對程序執(zhí)行的結果進展分析，只需可以得到正確結果的程序才是所需的程序。(8) 整理資料，交付運用。高質量程序設計目的是構造化程度高、可讀性好、效率高、可靠性高、便于維護。4.2 程序設計方法程序設計初期，由于計算機硬件條件的限制，運算速度與存儲空間都迫使程序員

3、追求高效率，編寫程序成為一種技巧與藝術，而程序的可了解性、可擴展性等要素那么次之。隨著計算機硬件與通訊技術的開展，計算機運用領域越來越廣泛，運用規(guī)模也越來越大，程序設計不再是一兩個程序員就可以完成的義務。在這種情況下，編寫程序不再片面追求高效率，而是綜合思索程序的可靠性、可擴展性、可重用性和可了解性等要素。4.2.1 構造化程序設計方法構造化程序設計思想:采用自頂向下、逐漸求精的設計方法和單入口單出口的控制構造。1自上而下與自下而上先將一個大問題分解成假設干個子問題，把比較復雜的子問題繼續(xù)分解成更加簡單的二級子問題，直至每個子問題都有顯而易見的處理方法，然后在實現(xiàn)時采用自下而上的方法，逐一編寫

4、處理各個子問題的程序。設計程序時采用自上而下的方法比采用自下而上的方法效率要高得多。4.2.1 構造化程序設計方法采用自上而下處理問題的思緒如圖:4.2.1 構造化程序設計方法2構造化方法構造化方法有助于在正式編寫程序之前充分了解問題的本質和實現(xiàn)方法，并且可以在詳細編碼過程中提供指點。4.2.1 構造化程序設計方法構造化方法通常遵照以下原那么:(1) 用戶參與的原那么(3) 自上而下的原那么(4) 階段成果文檔化4.2.1 構造化程序設計方法3構造化程序設計方法構造化程序設計的原那么是：(1) 運用順序、選擇、循環(huán)3種根本控制構造表示程序邏輯。(2)程序語句組織成容易識別的語句模塊，每個模塊都

5、是單入口、單出口。(3)嚴厲控制GOTO語句的運用。4.2.1 構造化程序設計方法(a) 順序構造 (b) 選擇構造 (c) while循環(huán) (d) do-while循環(huán)4.2.1 構造化程序設計方法4模塊化方法一個復雜的問題可以劃分為多個簡單問題的組合。在自頂向下、逐漸細化的過程中，把復雜問題分解成一個個簡單問題的最根本方法就是模塊化。模塊化便于問題的分析，模塊表達了信息隱藏的概念。模塊常用子程序加以實現(xiàn)。4.2.1 構造化程序設計方法4.2.2 面向對象的程序設計方法1面向對象的思想OO(Object Oriented，面向對象)的程序設計把客觀事物看作具有屬性和行為的對象，經過籠統(tǒng)找出同

6、一類對象的共同屬性(靜態(tài)特征)和行為(動態(tài)特征)，構成類。2對象、音訊傳送和類 對象: 是對現(xiàn)實問題的高度概括、分類和籠統(tǒng)。每個對象都只需本人的數(shù)據(jù)和相應的處置函數(shù)，整個程序是由一系列相互作用的對象來構成，不同對象之間是經過發(fā)送音訊來實現(xiàn)相互聯(lián)絡、相互作用。 4.2.2 面向對象的程序設計方法音訊傳送: 音訊是對象之間進展通訊的一種機制。發(fā)送給某個對象的一個音訊包含著要求接納對象完成某些活動的信息。接納到音訊的對象經過解釋，然后予以呼應。這個通訊機制叫做音訊傳送。發(fā)送音訊的對象并不需求知道接納音訊的對象如何對懇求予以呼應。4.2.2 面向對象的程序設計方法類: 定義了一組大體上類似的對象。一個

7、類所包含的方法和數(shù)據(jù)描畫一組對象的共同行為和屬性。 對象那么是類的詳細化，是類的實例。 類經過派生可以有子類，同樣也可以有父類，構成層次構造。4.2.2 面向對象的程序設計方法3籠統(tǒng)是對詳細事物(即對象)進展概括，即忽略事物的非本質特征，只留意那些與當前目的有關的本質特征，從而籠統(tǒng)出一類對象的共性并加以描畫。對一個問題的籠統(tǒng)普通來講應該包括兩個方面：數(shù)據(jù)籠統(tǒng)和代碼籠統(tǒng)(或稱為行為籠統(tǒng))。4.2.2 面向對象的程序設計方法4封裝性封裝的兩個含義： 第一是，將籠統(tǒng)得到的數(shù)據(jù)成員和代碼成員相結合，構成一個不可分割的整體，即對象，這種數(shù)據(jù)及行為的有機結合也就是封裝。 第二個含義稱為信息隱蔽，即盡能夠隱

8、蔽對象的內部細節(jié)。在隱蔽對象內部細節(jié)的同時，對象需求提供與外部世界進展交流的接口，并實現(xiàn)對數(shù)據(jù)訪問權限的合理控制，把整個程序中不同部分的相互影響減少到最低限制。4.2.2 面向對象的程序設計方法5承繼性是父類和子類之間共享數(shù)據(jù)和方法的機制。在定義一個類的時候，可以以一個曾經存在的類為根底，并把這個曾經存在的類所包含的屬性和方法作為本身的一部分，然后參與新的屬性和方法以區(qū)別于原來的類。原有的類稱為基類或父類，產生的新類稱為派生類。4.2.2 面向對象的程序設計方法6. 多態(tài)性在收到外部音訊時，對象通常要予以呼應。不同的對象收到同一音訊能夠產生完全不同的結果。4.2.2 面向對象的程序設計方法4.

9、2.3 函數(shù)程序設計函數(shù)程序設計言語運用非常簡單的計算模型或者程序觀念，一個程序是輸入集合到輸出集合的數(shù)學函數(shù)，執(zhí)行一個程序便是計算一個函數(shù)在給定輸入的輸出值。函數(shù)程序的特點是明晰、簡約和易讀等，這些特點使得大型程序的開發(fā)更高效，維護更容易。函數(shù)程序設計言語因其簡單的根本實際，使現(xiàn)代程序設計的根本思想，如籠統(tǒng)、數(shù)據(jù)籠統(tǒng)、多態(tài)和重載等都得到了最清楚的表達。因此，函數(shù)程序設計不僅是學習現(xiàn)代程序設計思想的理想言語，而且為傳統(tǒng)的命令式和面向對象的程序設計言語提供了很有意義的視角。4.2.4 程序設計風格程序設計風格指一個人編制程序時所表現(xiàn)出來的特點、習慣、邏輯思緒等。1源程序文檔化 (1) 標識符應按

10、意取名。 (2) 程序應加注釋。注釋是程序員與讀者之間通訊的重要工具，用自然言語或偽碼描畫。它闡明了程序的功能，特別是在維護階段，對了解程序提供了明確指點。注釋分序文性注釋和功能性注釋。序文性注釋應置于每個模塊的起始部分。4.2.4 程序設計風格2數(shù)聽闡明為了使數(shù)據(jù)定義更易于了解和維護，有以下原那么。 (1) 數(shù)聽闡明順序應規(guī)范，使數(shù)據(jù)的屬性更易于查找，從而有利于測試、糾錯與維護。如常量闡明、類型闡明、全局變量闡明、部分變量闡明等。 (2) 一個語句闡明多個變量時，各變量名按字典順序陳列。 (3) 對于復雜的數(shù)據(jù)構造，要加注釋，闡明在程序實現(xiàn)時的特點。4.2.4 程序設計風格 闡明每個模塊的用

11、途、功能。 闡明模塊的接口：調用方式、參數(shù)描畫及從屬模塊的清單。 數(shù)據(jù)描畫：重要數(shù)據(jù)的稱號、用途、限制、約束及其他信息。 開發(fā)歷史：設計者、審閱者姓名及日期，修正闡明及日期。 功能性注釋嵌入在源程序內部，闡明程序段或語句的功能以及數(shù)據(jù)的形狀。留意以下幾點： 注釋用來闡明程序段，而不是每一行程序都要加注釋。 運用空行、縮格或括號，以便于區(qū)分注釋和程序。 修正程序也應修正注釋。4.2.4 程序設計風格3語句構造語句構造的原那么是簡單、直接，不能為了追求效率而使代碼復雜化。為了便于閱讀和了解，一行只寫一條語句；不同層次的語句采用縮進方式，使程序的邏輯構造和功能特征更加明晰。要防止復雜的斷定條件，防止

12、多重的循環(huán)嵌套；表達式中運用括號以提高運算次序的明晰度等。4.2.4 程序設計風格4在編寫輸入和輸出語句時應思索原那么 (1) 輸入操作步驟和輸入格式盡量簡單。 (2) 應檢查輸入數(shù)據(jù)的合法性、有效性，報告必要的輸入形狀信息及錯誤信息。 (3) 輸入一批數(shù)據(jù)時，運用數(shù)據(jù)或文件終了標志，而不要用計數(shù)來控制。 (4) 交互式輸入時，提供可用的選擇和邊境值。 (5) 當程序設計言語有嚴厲的格式要求時，應堅持輸入格式的一致性。 (6) 輸出數(shù)據(jù)表格化、圖形化。 輸入、輸出風格還受其他要素的影響，如輸入/輸出設備、用戶閱歷及通訊環(huán)境等。4.2.4 程序設計風格5效率效率是指處置機時間和存儲空間的運用。(

13、1) 效率是一個性能要求，目的在需求分析時給出。 (2) 追求效率要建立在不損害程序可讀性和可靠性根底上，要在確保程序正確、明晰的情況下提高效率。(3) 提高程序效率的根本途徑在于選擇良好的設計方法、良好的數(shù)據(jù)構造，而不是靠編程時對程序語句做調整。4.2.4 程序設計風格4.2.5 程序設計舉例例4.1 輸入三角形的3個邊長a，b和c ，求三角形面積。 那么計算該三角形的面積的C言語源程序如下： #include main() float a,b,c,s,area; scanf(“%f,%f,%f,&a,&b,&c); s=1.0/2*(a+b+c); area=sqrt(s*(s-a)*(s

14、-b)*(s-c); printf(“a=%7.2f,b=%7.2f,c=%7.2f,s=%7.2fn,a,b,c,s); printf(“area=%7.2fn,area); 例4.2 求 方程的根，a，b，c 由鍵盤輸入，設 ，根據(jù)數(shù)學知識，可以求得方程的根為： 設 : ， 那么方程的根可以改寫為：4.2.5 程序設計舉例計算該方程的根的源程序如下： #include main() float a,b,c,disc,x1,x2,p,q; scanf(“a=%f,b=%f,c=%f,&a,&b,&c); disc=b*b-4*a*c; p=-b/(2*a); q=sqrt(disc)/(2*

15、a); x1=p+q;x2=p-q; printf(“nx1=%5.2fnx2=%5.2fn,x1,x2); 4.2.5 程序設計舉例4.3 根本數(shù)據(jù)構造數(shù)據(jù)構造(Data Structure)是系統(tǒng)設計和程序開發(fā)的重要根底。4.3.1 根本概念1數(shù)據(jù)、數(shù)據(jù)類型數(shù)據(jù)是對客觀事物的符號表示。在計算機系統(tǒng)內，數(shù)據(jù)通常是指可以輸入到計算機中并被計算機進展處置的符號的集合。例如，數(shù)字、字母、漢字、圖形、圖像、聲音等信息在計算機內部的表示都是數(shù)據(jù)，可以是數(shù)值數(shù)據(jù)，也可以是非數(shù)值數(shù)據(jù)。數(shù)據(jù)類型是指具有一樣取值范圍和可以實施同種操作的數(shù)據(jù)的集合。例如，在程序設計言語中，通常定義了字符型、整數(shù)型、數(shù)組等多種數(shù)

16、據(jù)類型。2數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象可以獨立并完好地描畫客觀世界實體的根本數(shù)據(jù)單元稱為數(shù)據(jù)元素，它是組成數(shù)據(jù)的根本單位。在不同的運用環(huán)境中，數(shù)據(jù)元素有時可以稱為節(jié)點、記錄等。數(shù)據(jù)項是組成數(shù)據(jù)元素的不可分割的最小單位。最簡單的數(shù)據(jù)元素是由一個數(shù)據(jù)項構成的。同類數(shù)據(jù)元素的集合稱為數(shù)據(jù)對象。4.3.1 根本概念3數(shù)據(jù)構造數(shù)據(jù)構造是指數(shù)據(jù)元素之間的相互關系的集合，包括了數(shù)據(jù)的邏輯構造、物理構造以及數(shù)據(jù)的運算。數(shù)據(jù)的邏輯構造數(shù)據(jù)的邏輯構造是指數(shù)據(jù)元素之間的邏輯關系。數(shù)據(jù)之間可以根據(jù)不同的關系組成不同的數(shù)據(jù)構造。4.3.1 根本概念線性構造 數(shù)據(jù)構造中，假設數(shù)據(jù)元素之間存在著前后順序的關系，即除了第一個數(shù)

17、據(jù)元素和最后一個元素外，其他每個元素都有獨一的一個前驅和一個后繼元素，這樣的數(shù)據(jù)元素之間的關系被稱為線性構造。樹形構造 數(shù)據(jù)構造中，假設數(shù)據(jù)元素之間有順序關系，且除了一個被稱為根節(jié)點的元素外，每個元素都有一個前驅節(jié)點，并且可以有多個后繼節(jié)點，這種邏輯構造稱為樹形構造。圖形構造 數(shù)據(jù)構造中，假設任何一個數(shù)據(jù)元素都可以有多個前驅節(jié)點和多個后繼節(jié)點，這種邏輯構造稱為圖形構造。4.3.1 根本概念(2) 數(shù)據(jù)的物理構造 數(shù)據(jù)的物理構造是指邏輯構造在計算機存儲器中的表示。數(shù)據(jù)的物理構造不僅要存儲數(shù)據(jù)本身，還要存儲表示數(shù)據(jù)間的邏輯關系。 數(shù)據(jù)的物理構造主要有四種，分別是順序構造、鏈表構造、索引構造及散列構

18、造。4.3.1 根本概念順序構造 把一切元素存放在一片延續(xù)的存儲單元中，邏輯上相鄰的元素存儲在物理位置相鄰的存儲單元中，由此得到的存儲表示稱為順序存儲構造。 順序存儲構造常借助于程序設計言語中的數(shù)組來實現(xiàn)。優(yōu)點是運用方法簡單，缺陷是必需預先分析出所需定義數(shù)組的大小。4.3.1 根本概念鏈表構造 對邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關系經過附設的指針域來實現(xiàn)，由此得到的存儲表示稱為鏈式存儲構造。 鏈式存儲構造通常借助于程序設計言語中的指針來實現(xiàn)。4.3.1 根本概念索引構造 針對每個數(shù)據(jù)構造建立一張所謂的索引表，每個數(shù)據(jù)元素占用表中的一項，每個表項包含一個可以獨一識別一個元素的關

19、鍵字和用以指示該元素的地址指針。散列構造 經過構造相應的散列函數(shù)，由散列函數(shù)的值來確定元素存放的地址。4.3.1 根本概念(3) 數(shù)據(jù)運算 數(shù)據(jù)操作的集合。常見的數(shù)據(jù)操作有數(shù)據(jù)的插入、刪除、查找、遍歷等。 數(shù)據(jù)操作通常由計算機程序加以實現(xiàn)，通常也叫算法實現(xiàn)。4.3.1 根本概念4.3.2 幾種典型的數(shù)據(jù)構造1線性表 (1)定義 線性表是由有限個一樣的數(shù)據(jù)元素構成的序列，元素之間是一對一的線性關系，除了第一個元素只需直接后繼、最后一個元素只需直接前驅外，其他數(shù)據(jù)元素都有一個直接前驅和一個直接后繼，如圖：(2)運算和實現(xiàn) 線性表通常采用順序和鏈表兩種物理實現(xiàn)。對于經常變化的表，通常采取鏈表構造。線

20、性表常用的運算主要有：插入、刪除、查詢和遍歷。4.3.2 幾種典型的數(shù)據(jù)構造插入 在堅持原有的存儲構造的前提下，根據(jù)插入要求，在適當?shù)奈恢貌迦胍粋€元素。插入操作要求線性表要有足夠的存放新元素的空間，假設空間缺乏，插入操作無法進展，線性表會溢出。刪除 在線性表中，找到滿足條件的數(shù)據(jù)元素，并刪除。假設線性表為空，刪除就會失敗。4.3.2 幾種典型的數(shù)據(jù)構造查詢 在線性表中，按照查詢條件，定位數(shù)據(jù)元素的過程就是查詢。查詢的條件普通根據(jù)數(shù)據(jù)元素中的關鍵字進展。實踐上，數(shù)據(jù)的插入和刪除都需求首先定位數(shù)據(jù)元素。對于空的線性表是無法查詢的。遍歷 是指按照某種方式，逐一訪問線性表中的每一個數(shù)據(jù)元素，并執(zhí)行一樣

21、處置的操作。這里的處置可以是讀、寫、或查詢等。4.3.2 幾種典型的數(shù)據(jù)構造2. 棧(1)定義 對于由N個數(shù)據(jù)元素構成的一個線性序列，假設只允許在其固定的一端位置插入和刪除一個數(shù)據(jù)元素，那么這種邏輯構造的數(shù)據(jù)構造稱為堆?；驐?stack)。 允許插入或刪除的這一端稱為棧項，另一個固定端稱為棧底。當表中沒有元素時稱為空棧。4.3.2 幾種典型的數(shù)據(jù)構造(2) 運算和實現(xiàn)棧的根本運算主要有：入棧、出棧和判別。入棧 入棧也叫壓棧，是在棧頂添加新元素的操作，新的元素入棧后成為新的棧頂元素。出棧 出棧也叫退?；驈棗＃菍ｍ斣貜臈Ｖ型顺霾魉徒o用戶程序的操作。4.3.2 幾種典型的數(shù)據(jù)構造4.3.2

22、幾種典型的數(shù)據(jù)構造判別 判別操作用來檢查棧內數(shù)據(jù)能否為空，前往結果是一個邏輯值：真或假。假設棧頂和棧底重合，闡明堆棧為空。4.3.2 幾種典型的數(shù)據(jù)構造3. 隊列(1) 定義對于由N個數(shù)據(jù)元素構成的一個線性序列，假設在其固定的一端只允許插入數(shù)據(jù)元素，且在另一端只允許刪除數(shù)據(jù)元素，這種邏輯構造稱為隊列(Queue)。只允許插入的一端稱為隊尾(Rear)，只允許刪除的一端稱為隊首(Front)。隊列是一種“先進先出的數(shù)據(jù)構造，在操作系統(tǒng)的進程調度管理、網絡數(shù)據(jù)包的存儲轉發(fā)等多種領域中被廣泛運用。4.3.2 幾種典型的數(shù)據(jù)構造(2) 運算 隊列的根本運算主要有：入隊、出隊和判別。入隊 入隊是在隊列中

23、插入一個新數(shù)據(jù)元素的過程，插入在隊尾進展，新的元素成為隊尾。出隊 出隊是在隊列中刪除一個數(shù)據(jù)元素的過程，刪除在隊首進展并把出來的數(shù)據(jù)傳送給用戶程序。4.3.2 幾種典型的數(shù)據(jù)構造4.3.2 幾種典型的數(shù)據(jù)構造4.3.2 幾種典型的數(shù)據(jù)構造判別： 判別操作用來檢查隊列能否為空，前往結果是一個邏輯值：真或假，如圖:4.3.2 幾種典型的數(shù)據(jù)構造(3) 循環(huán)隊列的實現(xiàn)4.3.2 幾種典型的數(shù)據(jù)構造4. 樹(1) 定義在樹型構造中，每個數(shù)據(jù)元素稱為一個結點，除了獨一的根結點外，其他每個結點都有且僅有一個父結點，每個元素可以有多個子結點。樹型構造是一種非常重要的非線性數(shù)據(jù)構造，可以用來描畫客觀世界中廣泛

24、存在的以分支關系定義的層次構造，如各種各樣的社會組織構造關系。在計算機領域中，樹型構造可以用于大型列表的搜索、源程序的語法構造、人工智能系統(tǒng)等諸多問題。4.3.2 幾種典型的數(shù)據(jù)構造(2) 運算樹常見的根本運算有：插入、刪除和遍歷。插入 在樹中適宜的位置，添加一個節(jié)點，通常插入新的節(jié)點后，依然應該堅持該樹本身所具有的性質。刪除 在樹中找到滿足條件的節(jié)點并刪除。通常刪除節(jié)點后，也要堅持該樹本身所具有的性質。遍歷 按照某種順序或規(guī)那么，對樹中的每個節(jié)點逐一進展訪問的過程。4.3.2 幾種典型的數(shù)據(jù)構造4.3.2 幾種典型的數(shù)據(jù)構造5. 圖(1) 定義圖形構造是一種比樹型構造更復雜的非線性構造。在圖

25、形構造中，每個數(shù)據(jù)元素稱為一個頂點，恣意兩個頂點之間都能夠相關，這種相關性用一條邊來表示，頂點之間的鄰接關系可以是恣意的。圖在計算機領域有著廣泛的運用，可以用來描畫計算機網絡的拓撲構造，以及圖論中的最小生成樹等問題。除此以外，圖在自然科學、社會科學和人文科學等許多領域也都有著非常廣泛的運用。4.3.2 幾種典型的數(shù)據(jù)構造(2) 運算常見的根本運算有：添加頂點、刪除頂點、添加邊、刪除邊和遍歷圖。添加頂點 在圖中添加新的頂點，新添加的頂點通常是孤立的節(jié)點，還沒有邊銜接。刪除頂點 在圖中去掉一個頂點，顯然，在去掉一個頂點的同時還應該刪除與該頂點所銜接的邊。4.3.2 幾種典型的數(shù)據(jù)構造添加邊 根據(jù)指

26、定的頂點，添加相應的邊。刪除邊 根據(jù)指定的頂點，刪除相應的邊。遍歷圖 按照一定的規(guī)那么，對圖中的每個數(shù)據(jù)頂點逐一進展訪問。4.3.2 幾種典型的數(shù)據(jù)構造(3) 實現(xiàn)圖通常用數(shù)組和鏈表兩種構造加以實現(xiàn)。對于各個頂點和頂點之間的關系分別采用鄰接矩陣和鄰接列表來進展描畫。4.3.2 幾種典型的數(shù)據(jù)構造4.3.2 幾種典型的數(shù)據(jù)構造4.3.3 查找查找是指根據(jù)給定的某個值，在查找表中確定一個其關鍵字等于給定值的記錄或數(shù)據(jù)元素。假設表中存在這樣的一個記錄，那么稱查找是勝利的，此時查找的結果為給出整個記錄的信息，或指示該記錄在查找表中的位置；假設表中不存在關鍵字等于給定值的記錄，那么稱查找失敗，此時查找的

27、結果可給出一個“空記錄或“空指針。查找的方法主要有順序查找、二分查找、分塊查找、數(shù)表的動態(tài)查找二叉排序樹查找、平衡二叉樹AVL樹、B樹、B+樹、哈希查找等。1 順序查找順序查找是在一個隊列中找出與給定關鍵字一樣數(shù)值的詳細位置。原理是讓關鍵字與隊列中的數(shù)從第一個開場逐個比較，直到找出與給定關鍵字一樣的數(shù)值為止。4.3.3 查找2二分查找二分查找又稱折半查找，它是一種效率較高的查找方法。但二分查找必需采用順序存儲構造，且必需按關鍵字大小有序對給定隊列進展陳列。二分查找算法的思想是：將表中間位置記錄的關鍵字與查找關鍵字進展比較，假設兩者相等，那么查找勝利；否那么利用中間位置記錄將表分成前、后兩個子表

28、，假設中間位置記錄的關鍵字小于查找關鍵字，那么進一步查找前一子表假定隊列是從小到大陳列，否那么進一步查找后一子表。反復以上過程，直至找到滿足條件的記錄，使查找勝利，或直至子表不存在為止，此時查找失敗。4.3.3 查找優(yōu)、缺陷：二分查找法的優(yōu)點是比較次數(shù)少，查找速度快，平均性能好；其缺陷是要求待查表為有序表，且插入、刪除困難。因此，二分查找方法適用于不經常變動而查找頻繁的有序列表。4.3.3 查找3分塊查找分塊查找又稱索引順序查找，它是順序查找的一種改良方法。分塊的原那么是將n個數(shù)據(jù)元素“按塊有序劃分為m塊m n。每一塊中的結點不用有序，但塊與塊之間必需“按塊有序；即第1塊中任一元素的關鍵字都必

29、需小于第2塊中任一元素的關鍵字；而第2塊中任一元素又都必需小于第3塊中的任一元素等。分塊查找是首先選取各塊中的最大關鍵字構成一個索引表；然后查找分兩個部分：先對索引表進展二分查找或已確定待查記錄在哪一塊中；最后在已確定的塊中用順序法進展查找。4.3.3 查找4.3.4 排序排序是計算機程序設計中的一種重要操作。簡單地說，排序就是要整理文件中的記錄，使之按關鍵字遞增(或遞減)次序陳列起來。排序的方法很多，但就其全面性能而言，很難提出一種被以為是最好的方法，每一種方法都有各自的優(yōu)、缺陷，適宜在不同的環(huán)境(如記錄的初始陳列形狀等)中運用。假設按排序過程中根據(jù)的不同原那么對內部排序方法進展分類，那么可分為直接插入排序、冒泡排序、快速排序等。1直接插入排序直接插入排序是一種最簡單的排序方法，它的根本操作是將一個記錄插入到已排好序的有序表中，從而得到一個新的、記錄數(shù)增1的有序表。4.3.4 排序2冒泡排序