復(fù)習(xí)第4章程序設(shè)計基礎(chǔ)

1、4.1 程序設(shè)計基礎(chǔ)程序設(shè)計是指用計算機(jī)語言對所要解決的問題中的數(shù)據(jù)以及處理問題的方法和步驟所做的完整而準(zhǔn)確的描述的 過程。程序設(shè)計步驟如下：Ø (1) 確定要解決的問題。Ø (2) 分析問題。在著手解決問題之前，應(yīng)該通過分析，充分理解問題，明確原始數(shù)據(jù)、解題要求、需要輸出的數(shù)據(jù) 及形式等。Ø (3) 選擇計算方法。Ø (4) 確定數(shù)據(jù)結(jié)構(gòu)和算法。算法是解題的過程。首先集中精力于算法的總體，然后逐層降低問題的抽象性，逐步充實(shí)細(xì)節(jié)，直到最終把抽象的問題具體化成可用程序語句表達(dá)的算法。這是一個自上而下、逐步細(xì)化的過程。32014/12/24計算機(jī)科學(xué)導(dǎo)論4.

2、1 程序設(shè)計基礎(chǔ)Ø (5) 繪制流程圖。Ø (6) 編寫程序。利用程序設(shè)計語言表示算法，編寫代碼。Ø (7) 調(diào)試并測試程序。調(diào)試程序包括編譯和連接等操作。程序員還要對程序執(zhí)行的結(jié)果進(jìn)行分析，只有能夠得到正 確結(jié)果的程序才是所需的程序。Ø (8) 整理資料，交付使用。高質(zhì)量程序設(shè)計目標(biāo)是結(jié)構(gòu)化程度高、可讀性好、效 率高、可靠性高、便于維護(hù)。42014/12/24計算機(jī)科學(xué)導(dǎo)論4.2程序設(shè)計方法Ø 程序設(shè)計初期，由于計算機(jī)硬件條件的限制，運(yùn)算速度與空間都迫使程序員追求高效率，編寫程序成為一種技 巧與藝術(shù)，而程序的可理解性、可擴(kuò)充性等要素則次之。&

3、#216; 隨著計算機(jī)硬件與通信技術(shù)的發(fā)展，計算機(jī)應(yīng)用領(lǐng)域越來 越廣泛，應(yīng)用規(guī)模也越來越大，程序設(shè)計不再是一兩個程 序員就可以完成的任務(wù)。在這種情況下，編寫程序不再片 面追求高效率，而是綜合考慮程序的可靠性、可擴(kuò)充性、可重用性和可理解性等要素。52014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.1結(jié)構(gòu)化程序設(shè)計方法Ø 結(jié)構(gòu)化程序設(shè)計思想:Ø 采用自頂向下、逐步求精的設(shè)計方法和單單出口的結(jié)構(gòu)。62014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.1結(jié)構(gòu)化程序設(shè)計方法u 1自上而下與自下而上Ø 先將一個大問題分解成若干個子問題，把比較復(fù)雜的子問題繼續(xù)分解成更加簡單的子問題，直至每個子問

4、題都有顯而易見的解決辦法，然后在實(shí)現(xiàn)時采用自下而上的方法，逐一編寫解決各個子問題的程序。設(shè)計程序時采用自上而下的方 法比采用自下而上的方法效率要高得多。72014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.1結(jié)構(gòu)化程序設(shè)計方法Ø 采用自上而下解決問題的思路如圖:需要解決的復(fù)雜問題子問題子問題.82014/12/24計算機(jī)科學(xué)導(dǎo)論最小問題最小問題最小問題三級子問題三級子問題三級子問題子問題4.2.1結(jié)構(gòu)化程序設(shè)計方法u 2結(jié)構(gòu)化方法Ø 結(jié)構(gòu)化方法有助于在正式編寫程序之前充分理解問題的實(shí)質(zhì)和實(shí)現(xiàn)方法，并且可以在具體編碼過程中提供指導(dǎo)。92014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.1結(jié)構(gòu)化程

5、序設(shè)計方法u 結(jié)構(gòu)化方法通常遵循以下原則:Ø (1) 用戶參與的原則Ø (3) 自上而下的原則Ø (4) 階段成果文檔化102014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.1結(jié)構(gòu)化程序設(shè)計方法u 3結(jié)構(gòu)化程序設(shè)計方法Ø 結(jié)構(gòu)化程序設(shè)計的原則是：Ø (1) 使用順序、選擇、循環(huán)3種基本構(gòu)表示程序邏輯。結(jié)Ø (2)程序語句組織成容易識別的語句模塊，每個模塊都是單、單出口。Ø (3)嚴(yán)格GOTO語句的使用。112014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.1結(jié)構(gòu)化程序設(shè)計方法真假假S出口ABS假出口(a) 順序結(jié)構(gòu)(b) 選擇結(jié)構(gòu)(c) w

6、hile循環(huán)(d) do-while循環(huán)122014/12/24計算機(jī)科學(xué)導(dǎo)論BAA真S真A4.2.1結(jié)構(gòu)化程序設(shè)計方法u 4模塊化方法Ø 一個復(fù)雜的問題可以劃分為多個簡單問題的組合。Ø 在自頂向下、逐步細(xì)化的過程中，把復(fù)雜問題分解 成一個個簡單問題的最基本方法就是模塊化。Ø 模塊化便于問題的分析，模塊體現(xiàn)了信息隱藏的概念。模塊常用子程序加以實(shí)現(xiàn)。132014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.2面向?qū)ο蟮某绦蛟O(shè)計方法u 1面向?qū)ο蟮乃枷?#216; OO(Object Oriented，面向?qū)ο?的程序設(shè)計把客觀事物看作具有屬性和行為的對象，通過抽象找出同一類對象

7、的共同屬性(靜態(tài)特征)和行為(動態(tài)特征)，形成類。142014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.2面向?qū)ο蟮某绦蛟O(shè)計方法u 2對象、消息傳遞和類Ø對象:是對現(xiàn)實(shí)問題的高度概括、分類和抽象。每個對象都只有的數(shù)據(jù)和相應(yīng)的處理函數(shù)，整個程序是由一系列相互作用的對象來，不同對象之間是通過消息來實(shí)現(xiàn)相互、相互作用。152014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.2 面向?qū)ο蟮某绦蛟O(shè)計方法Ø 消息傳遞:消息是對象之間進(jìn)行通信的一種機(jī)制。給某個對象的一個消息包含著要求接收對象完成某些活動的信息。接收到消息的對象經(jīng)過解釋，然后予以響應(yīng)。這個通信機(jī)制叫做消息傳遞。消息的對象并不需要知道接收消息

8、的對象如何對請求予以響應(yīng)。162014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.2面向?qū)ο蟮某绦蛟O(shè)計方法Ø 類:定義了一組大體上相似的對象。一個類所包含的方法和數(shù)據(jù)描述一組對象的共為和屬性。對象則是類的具體化，是類的實(shí)例。類通過派生可以有子類，同樣也可以有父類，形成層次結(jié)構(gòu)。172014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.2面向?qū)ο蟮某绦蛟O(shè)計方法u 3抽象Ø 是對具體事物(即對象)進(jìn)行概括，即忽略事物的非本質(zhì)特征，只注意那些與當(dāng)前目標(biāo)有關(guān)的本質(zhì)特 征，從而抽象出一類對象的共性并加以描述。Ø 對一個問題的抽象一般來講應(yīng)該包括兩個方面：數(shù)據(jù)抽象和代碼抽象(或稱為行為抽象)。18

9、2014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.2u 4封裝性Ø 封裝的兩個含義：第一是，將抽象得到的數(shù)據(jù)成員和代碼成員相結(jié)合， 形成一個不可分割的整體，即對象，這種數(shù)據(jù)及行為的有 機(jī)結(jié)合也就是封裝。第二個含義稱為信息隱蔽，即盡可能隱蔽對象的內(nèi)部細(xì)節(jié)。在隱蔽對象內(nèi)部細(xì)節(jié)的同時，對象需要提供與外部面向?qū)ο蟮某绦蛟O(shè)計方法世界進(jìn)行交流的接口，并實(shí)現(xiàn)對數(shù)據(jù)權(quán)限的合理，把整個程序中不同部分的相互影響減少到最低限度。192014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.2面向?qū)ο蟮某绦蛟O(shè)計方法u 5繼承性Ø 是父類和子類之間共享數(shù)據(jù)和方法的機(jī)制。在定義一 個類的時候，可以以一個已經(jīng)存在的類為基礎(chǔ)，并

10、把 這個已經(jīng)存在的類所包含的屬性和方法作為自身的一部分，然后加入新的屬性和方法以區(qū)別于原來的類。Ø 原有的類稱為基類或父類，產(chǎn)生的新類稱為派生類。202014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.2面向?qū)ο蟮某绦蛟O(shè)計方法u 6. 多態(tài)性Ø 在收到外部消息時，對象通常要予以響應(yīng)。不同 的對象收到同一消息可能產(chǎn)生完全不同的結(jié)果。212014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.3函數(shù)程序設(shè)計u 函數(shù)程序設(shè)計語言使用非常簡單的計算模型或者程序觀點(diǎn)，一個程序是輸入集合到輸出集合的數(shù)學(xué)函數(shù)，執(zhí)行 一個程序便是計算一個函數(shù)在給定輸入的輸出值。u 函數(shù)程序的特點(diǎn)是清晰、簡潔和易讀等，這些特點(diǎn)使得

11、大型程序的開發(fā)更高效，維護(hù)更容易。u 函數(shù)程序設(shè)計語言因其簡單的基本理論，使現(xiàn)代程序設(shè)計的基本思想，如抽象、數(shù)據(jù)抽象、多態(tài)和重載等都得 到了最清楚的體現(xiàn)。因此，函數(shù)程序設(shè)計不僅是學(xué)習(xí)現(xiàn)代程序設(shè)計思想的理想語言，而且為傳統(tǒng)令式和面向?qū)ο蟮某绦蛟O(shè)計語言提供了很有意義的視角。222014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.4程序設(shè)計風(fēng)格u 程序設(shè)計風(fēng)格指一個人編制程序時所表現(xiàn)出來的特點(diǎn)、習(xí)慣、邏輯思路等。232014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.4程序設(shè)計風(fēng)格u 1源程序文檔化Ø (1) 標(biāo)識符應(yīng)按意取名。Ø (2) 程序應(yīng)加注釋。注釋是程序員與讀者之間通信的重要工具，用自然語

12、言或偽碼描述。它說明了程 序的功能，特別是在維護(hù)階段，對理解程序提供了 明確指導(dǎo)。注釋分序言性注釋和功能性注釋。序言性注釋應(yīng)置于每個模塊的起始部分。242014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.4程序設(shè)計風(fēng)格u 2數(shù)據(jù)說明Ø 為了使數(shù)據(jù)定義更易于理解和維護(hù)，有以下原則。Ø (1) 數(shù)據(jù)說明順序應(yīng)規(guī)范，使數(shù)據(jù)的屬性更易于查找，從而有利于測試、糾錯與維護(hù)。如常量說明、類型說明、全局變量說明、局部變量說明等。Ø (2) 一個語句說明多個變量時，各變量名按字典順序排列。Ø (3) 對于復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，要加注釋，說明在程序?qū)崿F(xiàn)時的特點(diǎn)。252014/12/24計算

13、機(jī)科學(xué)導(dǎo)論4.2.4程序設(shè)計風(fēng)格Ø 說明每個模塊的用途、功能。Ø 說明模塊的接口：調(diào)用形式、參數(shù)描述及從屬模塊的。Ø 數(shù)據(jù)描述：重要數(shù)據(jù)的名稱、用途、限制、約束及其他信息。Ø 開發(fā)歷史：設(shè)計者、審閱者姓名及日期，修改說明及日期。u 功能性注釋嵌入在源程序內(nèi)部，說明程序段或語 句的功能以及數(shù)據(jù)的狀態(tài)。注意以下幾點(diǎn)：Ø 注釋用來說明程序段，而不是每一行程序都要加注釋。Ø 使用空行、縮格或括號，以便于區(qū)分注釋和程序。Ø 修改程序也應(yīng)修改注釋。262014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.4u 3語句構(gòu)造Ø 語句構(gòu)造的原則

14、是簡單、直接，不能為了追求效率而使代碼復(fù)雜化。程序設(shè)計風(fēng)格Ø 為了便于閱讀和理解，一行只寫一條語句；Ø 不同層次的語句采用縮進(jìn)形式，使程序的邏輯結(jié)構(gòu)和功能特征更加清晰。Ø 要避免復(fù)雜的判定條件，避免多重的循環(huán)嵌套；Ø 表達(dá)式中使用括號以提高運(yùn)算次序的清晰度等。272014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.4程序設(shè)計風(fēng)格u 4在編寫輸入和輸出語句時應(yīng)考慮原則Ø (1) 輸入操作步驟和輸入格式盡量簡單。Ø (2) 應(yīng)檢查輸入數(shù)據(jù)的、有效性，報告必要的輸入狀態(tài)信息及錯誤信息。Ø (3) 輸入一批數(shù)據(jù)時，使用數(shù)據(jù)或文件結(jié)束標(biāo)志，而不

15、要用計數(shù)來。Ø (4) 交互式輸入時，提供可用的選擇和邊界值。Ø (5) 當(dāng)程序設(shè)計語言有嚴(yán)格的格式要求時，應(yīng)保持輸入格式的一致性。Ø (6) 輸出數(shù)據(jù)表格化、圖形化。Ø 輸入、輸出風(fēng)格還受其他因素的影響，如輸入/ 輸出設(shè)備、用戶經(jīng)驗(yàn)及通信環(huán)境等。282014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.4程序設(shè)計風(fēng)格u 5效率Ø 效率是指處理機(jī)時間和空間的使用。Ø (1) 效率是一個性能要求，目標(biāo)在需求分析時給出。Ø (2) 追求效率要建立在不損害程序可讀性和可靠性基礎(chǔ)上，要在確保程序正確、清晰的情況下提高效率。Ø (3)

16、提高程序效率的根本途徑在于選擇良好的設(shè)計方法、良好的數(shù)據(jù)結(jié)構(gòu)，而不是靠編程時對程序語句做調(diào)整。292014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.5程序設(shè)計舉例例4.1 輸入三角形的3個邊長a，b和c ，求三角形面積。s = (a + b + c) / 2area =s(s - a)(s - b)(s - c)則計算該三角形的面積的C語言源程序如下：#include<math.h> 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-b

17、)*(s-c);printf(“a=%7.2f,b=%7.2f,c=%7.2f,s=%7.2fn”,a,b,c,s); printf(“area=%7.2fn”,area);302014/12/24計算機(jī)科學(xué)導(dǎo)論4.2.5程序設(shè)計舉例ax2 + bx + c = 0例4.2 求輸入，設(shè)根為：方程的根，a，b，c 由鍵盤- 4ac ³ 0b2，根據(jù)數(shù)學(xué)知識，可以求得方程的- b +- 4ac- b - 4acb2b2x1 =x2 =22p = - bb2- 4ac設(shè) :，q =2a2a則方程的根可以改寫為：x1 = p + qx2 = p - q312014/12/24計算機(jī)科學(xué)導(dǎo)論4

18、.2.5程序設(shè)計舉例計算該方程的根的源程序如下：#include<math.h>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*a);x1=p+q;x2=p-q; printf(“nx1=%5.2fnx2=%5.2fn”,x1,x2);322014/12/24計算機(jī)科學(xué)導(dǎo)論4.3基本數(shù)據(jù)結(jié)構(gòu)u 數(shù)據(jù)結(jié)構(gòu)(Data Structure)是系統(tǒng)設(shè)計和程序開發(fā)的重要基礎(chǔ)。332014/12/24

19、計算機(jī)科學(xué)導(dǎo)論4.3.1基本概念u 1數(shù)據(jù)、數(shù)據(jù)類型Ø 數(shù)據(jù)是對客觀事物的符號表示。在計算機(jī)系統(tǒng)內(nèi)，數(shù) 據(jù)通常是指能夠輸入到計算機(jī)中并被計算機(jī)進(jìn)行處理 的符號的集合。例如，數(shù)字、字母、漢字、圖形、圖 像、聲音等信息在計算機(jī)內(nèi)部的表示都是數(shù)據(jù)，可以是數(shù)值數(shù)據(jù)，也可以是非數(shù)值數(shù)據(jù)。Ø 數(shù)據(jù)類型是指具有相同取值范圍和可以實(shí)施同種操作的數(shù)據(jù)的集合。例如，在程序設(shè)計語言中，通常定義 了字符型、整數(shù)型、數(shù)組等多種數(shù)據(jù)類型。342014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.1基本概念u 2數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對象Ø 能夠并完整地描述客觀世界實(shí)體的基本數(shù)據(jù)單元稱為數(shù)據(jù)元素，它是組成

20、數(shù)據(jù)的基本。在不同的應(yīng)用環(huán)境中，數(shù)據(jù)元素有時可以稱為節(jié)點(diǎn)、等。Ø 數(shù)據(jù)項(xiàng)是組成數(shù)據(jù)元素的不可分割的最小。最簡單的數(shù)據(jù)元素是由一個數(shù)據(jù)項(xiàng)的。Ø 同類數(shù)據(jù)元素的集合稱為數(shù)據(jù)對象。352014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.1基本概念u 3數(shù)據(jù)結(jié)構(gòu)Ø 數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)元間的相互關(guān)系的集合，包括了數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)以及數(shù)據(jù)的運(yùn)算。Ø 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元間的邏輯關(guān)系。數(shù)據(jù)之間可以根據(jù)不同的關(guān)系組成不同的數(shù)據(jù)結(jié)構(gòu)。362014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.1基本概念Ø 線性結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)中，如果數(shù)據(jù)元間存在著前后順序的關(guān)系，即

21、除了第一個數(shù)據(jù)元素和最后一個元素外，其他每個元素都有惟一的一個前驅(qū)和一個后繼元素，這樣的數(shù)據(jù)元 間的關(guān)系被稱為線性結(jié)構(gòu)。Ø 樹形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)中，如果數(shù)據(jù)元間有順序關(guān)系，且除了一個被稱為根節(jié)點(diǎn)的元素外，每個元素都有一個前驅(qū)節(jié)點(diǎn)， 并且可以有多個后繼節(jié)點(diǎn)，這種邏輯結(jié)構(gòu)稱為樹形結(jié)構(gòu)。Ø 圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)中，如果任何一個數(shù)據(jù)元素都可以有多個前 驅(qū)節(jié)點(diǎn)和多個后繼節(jié)點(diǎn)，這種邏輯結(jié)構(gòu)稱為圖形結(jié)構(gòu)。372014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.1基本概念Ø (2) 數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)是指邏輯結(jié)構(gòu)在計算機(jī)存儲器中的表示。數(shù)據(jù)的物理結(jié)構(gòu)不僅要數(shù)據(jù)本身，還要表示數(shù)據(jù)間的邏輯關(guān)

22、系。數(shù)據(jù)的物理結(jié)構(gòu)主要有四種，分別是順序結(jié)構(gòu)、鏈表結(jié)構(gòu)、索引結(jié)構(gòu)及散列結(jié)構(gòu)。382014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.1基本概念Ø 順序結(jié)構(gòu)把所有元素存放在一片連續(xù)的單元中，邏輯上相鄰的元素在物理位置相鄰的單元中，由此得到的表示稱為順序結(jié)構(gòu)。順序結(jié)構(gòu)常借助于程序設(shè)計語言中的數(shù)組來實(shí)現(xiàn)。優(yōu)點(diǎn)是使用方法簡單，缺點(diǎn)是必須預(yù)先分析出所需定義數(shù)組的大小。392014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.1基本概念Ø 鏈表結(jié)構(gòu)對邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關(guān)系通過附設(shè)的指針域來實(shí)現(xiàn)，由此得到的表示稱為鏈?zhǔn)浇Y(jié)構(gòu)。鏈?zhǔn)浇Y(jié)構(gòu)通常借助于程序設(shè)計語言中的指針來實(shí)現(xiàn)。4020

23、14/12/24計算機(jī)科學(xué)導(dǎo)論4.3.1基本概念Ø 索引結(jié)構(gòu)每個數(shù)據(jù)結(jié)構(gòu)建立一張所謂的索引表，每個數(shù)據(jù)元素占用表中的一項(xiàng)，每個表項(xiàng)包含一個能夠惟一識別一個元素的關(guān)鍵字和用以指示該元素的地址指針。Ø 散列結(jié)構(gòu)通過構(gòu)造相應(yīng)的散列函數(shù)，由散列函數(shù)的值來確定元素存放的地址。412014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.1基本概念Ø (3) 數(shù)據(jù)運(yùn)算數(shù)據(jù)操作的集合。常見的數(shù)據(jù)操作有數(shù)據(jù)的、刪除、查找、遍歷等。數(shù)據(jù)操作通常由計算機(jī)程序加以實(shí)現(xiàn)，通常也叫算法實(shí)現(xiàn)。422014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.2u 1線性表Ø (1)定義線性表是由有限個相同的數(shù)據(jù)元素幾

24、種典型的數(shù)據(jù)結(jié)構(gòu)的序列，元間是一對一的線性關(guān)系，除了第一個元素只有直接后繼、最后一個元素只有直接前驅(qū)外，其余數(shù) 據(jù)元素都有一個直接前驅(qū)和一個直接后繼，如圖：432014/12/24計算機(jī)科學(xué)導(dǎo)論元素 1元素 n元素 2元素 34.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)Ø (2)運(yùn)算和實(shí)現(xiàn)線性表通常采用順序和鏈表兩種物理實(shí)現(xiàn)。對于經(jīng)常變化的表，通常采取鏈表結(jié)構(gòu)。線性表常用的運(yùn)算主要有：、刪除、和遍歷。442014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)Ø 在保持原有的求，在適當(dāng)?shù)奈恢媒Y(jié)構(gòu)的前提下，根據(jù)要一個元素。操作要求線性表要有足夠的存放新元素的空間，如果空間不足，操作無法

25、進(jìn)行，線性表會溢出。Ø 刪除性表中，找到滿足條件的數(shù)據(jù)元素，并刪除。如果線性表為空，刪除就會失敗。452014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)Ø 性表中，按照條件，數(shù)據(jù)元素的過程就是。的條件一般根據(jù)數(shù)據(jù)元素中的關(guān)鍵字進(jìn)行。實(shí)際上，數(shù)據(jù)的和刪除都需要首先定位數(shù)據(jù)元素。對于空的線性表是無法Ø 遍歷的。是指按照某種方式，逐一線性表中的每一個數(shù)據(jù)元素，并執(zhí)行相同處理的操作。這里的處理可以是讀、寫、或等。462014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)u 2. 棧Ø (1)定義對于由N個數(shù)據(jù)元素在其固定的一端位置的一個線性序

26、列，如果只和刪除一個數(shù)據(jù)元素，那么這種邏輯結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)稱為堆?；驐?stack)?；騽h除的這一端稱為棧項(xiàng)，另一個固定端稱為棧底。當(dāng)表中沒有元素時稱為空棧。472014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)Ø (2) 運(yùn)算和實(shí)現(xiàn)棧的基本運(yùn)算主要有：入棧、出棧和Ø 入棧。入棧也叫壓棧，是在棧頂添加新元素的操作，新的元素入棧后成為新的棧頂元素。Ø 出棧出棧也叫退棧或彈棧，是將棧頂元素從棧中并傳遞給用戶程序的操作。482014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)出棧數(shù)據(jù)元素D入棧數(shù)據(jù)元素 E492014/12/24計算機(jī)科學(xué)導(dǎo)論DCBA

27、DCBACBAEDCBA4.3.2 幾種典型的數(shù)據(jù)結(jié)構(gòu)Ø 操作用來檢查棧內(nèi)數(shù)據(jù)是否為空，返回結(jié)果是一個邏輯值：真或假。如果棧頂和棧底重合，說明堆棧為空。502014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.2u 3. 隊(duì)列Ø (1) 定義對于由N個數(shù)據(jù)元素果在其固定的一端只幾種典型的數(shù)據(jù)結(jié)構(gòu)的一個線性序列，如數(shù)據(jù)元素，且在另一端只刪除數(shù)據(jù)元素，這種邏輯結(jié)構(gòu)稱為隊(duì)列(Queue)。只的一端稱為隊(duì)尾(Rear)，刪除的一端稱為隊(duì)首(Front)。隊(duì)列是一種“先進(jìn)先出”的數(shù)據(jù)結(jié)構(gòu)，在操作只系統(tǒng)的進(jìn)程調(diào)度管理、網(wǎng)絡(luò)數(shù)據(jù)包的轉(zhuǎn)發(fā)等多種領(lǐng)域中被廣泛使用。512014/12/24計算機(jī)科學(xué)導(dǎo)論4

28、.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)Ø (2) 運(yùn)算隊(duì)列的基本運(yùn)算主要有：入隊(duì)、出隊(duì)和Ø 入隊(duì)。入隊(duì)是在隊(duì)列中一個新數(shù)據(jù)元素的過程，在隊(duì)尾進(jìn)行，新的元素成為隊(duì)尾。Ø 出隊(duì)出隊(duì)是在隊(duì)列中刪除一個數(shù)據(jù)元素的過程，刪除在隊(duì)首進(jìn)行并把出來的數(shù)據(jù)傳遞給用戶程序。522014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)F，G 入隊(duì)532014/12/24計算機(jī)科學(xué)導(dǎo)論尾指針尾指針ABCDEFG頭指針ABCDE頭指針4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)A，B，C 出隊(duì)542014/12/24計算機(jī)科學(xué)導(dǎo)論尾指針尾指針頭指針DEFGABCDE頭指針4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)Ø

29、 ：操作用來檢查隊(duì)列是否為空，返回結(jié)果是一個邏輯值：真或假，如圖:552014/12/24計算機(jī)科學(xué)導(dǎo)論尾指針頭指針4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)Ø (3) 循環(huán)隊(duì)列的實(shí)現(xiàn)內(nèi)存塊第一個單元隊(duì)列移動內(nèi)存塊最后一個單元562014/12/24計算機(jī)科學(xué)導(dǎo)論FG尾指針頭指針ABCDE4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)u 4. 樹Ø (1) 定義在樹型結(jié)構(gòu)中，每個數(shù)據(jù)元素稱為一個結(jié)點(diǎn)，除了唯一的根結(jié)點(diǎn)外，其他每個結(jié)點(diǎn)都有且僅有一個父 結(jié)點(diǎn)，每個元素可以有多個子結(jié)點(diǎn)。樹型結(jié)構(gòu)是一種非常重要的非線性數(shù)據(jù)結(jié)構(gòu)，可以客觀世界中廣泛存在的以分支關(guān)系定義的層次結(jié)構(gòu)，如各種各樣的組織結(jié)構(gòu)關(guān)系。在計算機(jī)領(lǐng)

30、域中，樹型結(jié)構(gòu)可以用于大型列表的搜索、源程序的語法結(jié)構(gòu)、人工智能系統(tǒng)等諸多問題。572014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.2Ø (2) 運(yùn)算樹常見的基本運(yùn)算有：Ø 幾種典型的數(shù)據(jù)結(jié)構(gòu)、刪除和遍歷。在樹中合適的位置，添加一個節(jié)點(diǎn)，通常新的節(jié)點(diǎn)后，仍然應(yīng)該保持該樹本身所具有的性質(zhì)。Ø 刪除在樹中找到滿足條件的節(jié)點(diǎn)并刪除。通常刪除 節(jié)點(diǎn)后，也要保持該樹本身所具有的性質(zhì)。Ø 遍歷按照某種順序或規(guī)則，對樹中的每個節(jié)點(diǎn)逐一進(jìn)行的過程。582014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)592014/12/24計算機(jī)科學(xué)導(dǎo)論EDFCRightLeft

31、BRightLeftARight4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)u 5. 圖Ø (1) 定義Ø 圖形結(jié)構(gòu)是一種比樹型結(jié)構(gòu)更復(fù)雜的非線性結(jié)構(gòu)。 在圖形結(jié)構(gòu)中，每個數(shù)據(jù)元素稱為一個頂點(diǎn)，任意 兩個頂點(diǎn)之間都可能相關(guān)，這種相關(guān)性用一條邊來表示，頂點(diǎn)之間的鄰接關(guān)系可以是任意的。Ø 圖在計算機(jī)領(lǐng)域有著廣泛的應(yīng)用，可以計算機(jī)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，以及圖論中的最小生成樹等問題。除此以外，圖在自然科會科學(xué)和人文科學(xué)等許多領(lǐng)域也都有著非常廣泛的應(yīng)用。602014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.2Ø (2) 運(yùn)算常見的基本運(yùn)算有：添加頂點(diǎn)、刪除頂點(diǎn)、添加邊、刪除邊和遍歷圖。

32、6; 添加頂點(diǎn)在圖中添加新的頂點(diǎn)，新添加的頂點(diǎn)通常是孤立的節(jié)點(diǎn)，還沒有邊連接。Ø 刪除頂點(diǎn)在圖中去掉一個頂點(diǎn)，顯然，在去掉一個頂點(diǎn)的同時還應(yīng)該刪除與該頂點(diǎn)所連接的邊。幾種典型的數(shù)據(jù)結(jié)構(gòu)612014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)Ø 添加邊根據(jù)指定的頂點(diǎn)，添加相應(yīng)的邊。Ø 刪除邊根據(jù)指定的頂點(diǎn)，刪除相應(yīng)的邊。Ø 遍歷圖按照一定的規(guī)則，對圖中的每個數(shù)據(jù)頂點(diǎn)逐一進(jìn)行。622014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.2 幾種典型的數(shù)據(jù)結(jié)構(gòu)Ø (3) 實(shí)現(xiàn)圖通常用數(shù)組和鏈表兩種結(jié)構(gòu)加以實(shí)現(xiàn)。對于各個頂點(diǎn)和頂點(diǎn)之間的關(guān)系分別采用鄰接矩陣

33、和鄰接列表來進(jìn)行描述。632014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)EABCDEAA B C DEDCB(a)(b)ABCD(642014/12/24計算機(jī)科學(xué)導(dǎo)論c)DBAEECDBECAEB01001101010101000101110104.3.3 查找u 查找是指根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的或數(shù)據(jù)元素。若表中存在這樣的的，此時查找的結(jié)果為給出一個整個，則稱查找是的信息，或指示該在查找表中的位置；若表中不存在關(guān)鍵字等于給定值的此時查找的結(jié)果可給出一個“空”，則稱查找失敗，或“空”指針。652014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.3 查找&

34、#216; 查找的方法主要有順序查找、二分查找、分塊查找、數(shù)表的動態(tài)查找（二叉排序樹查找、平衡二叉樹AVL樹、B樹、B+樹）、哈希查找等。u 1 順序查找Ø 順序查找是在一個隊(duì)列中找出與給定關(guān)鍵字相同數(shù)值的具置。原理是讓關(guān)鍵字與隊(duì)列中的數(shù)從第一個開始逐個比較，直到找出與給定關(guān)鍵字相同的數(shù)值為止。662014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.3 查找u 2二分查找Ø 二分查找又稱折半查找，它是一種效率較高的查找方法。但二分查找必須采用順序結(jié)構(gòu)，且必須按關(guān)鍵字大小有序?qū)o定隊(duì)列進(jìn)行排列。Ø 二分查找算法的思想是：將表中間位置的關(guān)鍵字與查找關(guān)鍵字進(jìn)行比較，如果兩者相等，

35、則查找；否則利用中間位置將表分成前、后兩個子表，如果中間位置的關(guān)鍵字小于查找關(guān)鍵字，則進(jìn)一步查找前一子表（假定隊(duì)列是從小到大排列），否則進(jìn)一步查找后一子表。重復(fù)以上過程，直至找到滿足條件的，使查找，或直至子表不存在為止，此時查找失敗。672014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.3 查找Ø 優(yōu)、缺點(diǎn)：二分查找法的優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好；其缺點(diǎn)是要求待查表為有序表，且、刪除。因此，二分查找方法適用于不經(jīng)常變動而查找頻繁的有序列表。682014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.3 查找u 3分塊查找Ø 分塊查找又稱索引順序查找，它是順序查找的一種改進(jìn)方法。&#

36、216; 分塊的原則是將n個數(shù)據(jù)元素“按塊有序”劃分為m塊（m n）。每一塊中的結(jié)點(diǎn)不必有序，但塊與塊之間必須“按塊有 序”；即第1塊中任一元素的關(guān)鍵字都必須小于第2塊中任一元素的關(guān)鍵字；而第2塊中任一元素又都必須小于第3塊中的任一元素等。Ø 分塊查找是首先選取各塊中的最大關(guān)鍵字一個索引表；然后查找分兩個部分：先對索引表進(jìn)行二分查找或已確定待查在哪一塊中；最后在已確定的塊中用順序法進(jìn)行查找。692014/12/24計算機(jī)科學(xué)導(dǎo)論4.3.4 排序Ø 排序是計算機(jī)程序設(shè)計中的一種重要操作。簡單地說，排，使之按關(guān)鍵字遞增(或遞減)序就是要整理文件中的次序排列起來。Ø 排序的方法很多，但就其全面性能而言，很難提出一種被認(rèn)為是最好的方法，每合在不同的環(huán)境(如法都有各自的優(yōu)、缺點(diǎn)，適的初始排列狀態(tài)等)中使用。如果按排序過程中依據(jù)的不同原則對內(nèi)部排序方法進(jìn)行分類，則可分為直接排序、冒泡排序、快速排序