第4章程序設(shè)計基礎(chǔ)ppt課件

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

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

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

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

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

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

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

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

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

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

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

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

13、1) 效率是一個性能要求，目的在需求分析時給出。 (2) 追求效率要建立在不損害程序可讀性和可靠性根底上，要在確保程序正確、明晰的情況下提高效率。(3) 提高程序效率的根本途徑在于選擇良好的設(shè)計方法、良好的數(shù)據(jù)構(gòu)造，而不是靠編程時對程序語句做調(diào)整。4.2.4 程序設(shè)計風(fēng)格4.2.5 程序設(shè)計舉例例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 由鍵盤輸入，設(shè) ，根據(jù)數(shù)學(xué)知識，可以求得方程的根為： 設(shè) : ， 那么方程的根可以改寫為：4.2.5 程序設(shè)計舉例計算該方程的根的源程序如下： #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 程序設(shè)計舉例4.3 根本數(shù)據(jù)構(gòu)造數(shù)據(jù)構(gòu)造(Data Structure)是系統(tǒng)設(shè)計和程序開發(fā)的重要根底。4.3.1 根本概念1數(shù)據(jù)、數(shù)據(jù)類型數(shù)據(jù)是對客觀事物的符號表示。在計算機系統(tǒng)內(nèi)，數(shù)據(jù)通常是指可以輸入到計算機中并被計算機進展處置的符號的集合。例如，數(shù)字、字母、漢字、圖形、圖像、聲音等信息在計算機內(nèi)部的表示都是數(shù)據(jù)，可以是數(shù)值數(shù)據(jù)，也可以是非數(shù)值數(shù)據(jù)。數(shù)據(jù)類型是指具有一樣取值范圍和可以實施同種操作的數(shù)據(jù)的集合。例如，在程序設(shè)計言語中，通常定義了字符型、整數(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ù)項構(gòu)成的。同類數(shù)據(jù)元素的集合稱為數(shù)據(jù)對象。4.3.1 根本概念3數(shù)據(jù)構(gòu)造數(shù)據(jù)構(gòu)造是指數(shù)據(jù)元素之間的相互關(guān)系的集合，包括了數(shù)據(jù)的邏輯構(gòu)造、物理構(gòu)造以及數(shù)據(jù)的運算。數(shù)據(jù)的邏輯構(gòu)造數(shù)據(jù)的邏輯構(gòu)造是指數(shù)據(jù)元素之間的邏輯關(guān)系。數(shù)據(jù)之間可以根據(jù)不同的關(guān)系組成不同的數(shù)據(jù)構(gòu)造。4.3.1 根本概念線性構(gòu)造 數(shù)據(jù)構(gòu)造中，假設(shè)數(shù)據(jù)元素之間存在著前后順序的關(guān)系，即除了第一個數(shù)

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

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

19、鍵字和用以指示該元素的地址指針。散列構(gòu)造 經(jīng)過構(gòu)造相應(yīng)的散列函數(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ù)構(gòu)造1線性表 (1)定義 線性表是由有限個一樣的數(shù)據(jù)元素構(gòu)成的序列，元素之間是一對一的線性關(guān)系，除了第一個元素只需直接后繼、最后一個元素只需直接前驅(qū)外，其他數(shù)據(jù)元素都有一個直接前驅(qū)和一個直接后繼，如圖：(2)運算和實現(xiàn) 線性表通常采用順序和鏈表兩種物理實現(xiàn)。對于經(jīng)常變化的表，通常采取鏈表構(gòu)造。線

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

21、處置的操作。這里的處置可以是讀、寫、或查詢等。4.3.2 幾種典型的數(shù)據(jù)構(gòu)造2. 棧(1)定義 對于由N個數(shù)據(jù)元素構(gòu)成的一個線性序列，假設(shè)只允許在其固定的一端位置插入和刪除一個數(shù)據(jù)元素，那么這種邏輯構(gòu)造的數(shù)據(jù)構(gòu)造稱為堆?；驐?stack)。 允許插入或刪除的這一端稱為棧項，另一個固定端稱為棧底。當(dāng)表中沒有元素時稱為空棧。4.3.2 幾種典型的數(shù)據(jù)構(gòu)造(2) 運算和實現(xiàn)棧的根本運算主要有：入棧、出棧和判別。入棧 入棧也叫壓棧，是在棧頂添加新元素的操作，新的元素入棧后成為新的棧頂元素。出棧 出棧也叫退棧或彈棧，是將棧頂元素從棧中退出并傳送給用戶程序的操作。4.3.2 幾種典型的數(shù)據(jù)構(gòu)造4.3.2

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

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

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

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

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

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

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

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