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

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

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

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

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

5、序設(shè)計(jì)方法u 結(jié)構(gòu)化方法通常遵循以下原則:Ø (1) 用戶參與的原則Ø (3) 自上而下的原則Ø (4) 階段成果文檔化102014/12/24計(jì)算機(jī)科學(xué)導(dǎo)論4.2.1結(jié)構(gòu)化程序設(shè)計(jì)方法u 3結(jié)構(gòu)化程序設(shè)計(jì)方法Ø 結(jié)構(gòu)化程序設(shè)計(jì)的原則是：Ø (1) 使用順序、選擇、循環(huán)3種基本構(gòu)表示程序邏輯。結(jié)Ø (2)程序語句組織成容易識(shí)別的語句模塊，每個(gè)模塊都是單、單出口。Ø (3)嚴(yán)格GOTO語句的使用。112014/12/24計(jì)算機(jī)科學(xué)導(dǎo)論4.2.1結(jié)構(gòu)化程序設(shè)計(jì)方法真假假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ì)算機(jī)科學(xué)導(dǎo)論BAA真S真A4.2.1結(jié)構(gòu)化程序設(shè)計(jì)方法u 4模塊化方法Ø 一個(gè)復(fù)雜的問題可以劃分為多個(gè)簡(jiǎn)單問題的組合。Ø 在自頂向下、逐步細(xì)化的過程中，把復(fù)雜問題分解 成一個(gè)個(gè)簡(jiǎn)單問題的最基本方法就是模塊化。Ø 模塊化便于問題的分析，模塊體現(xiàn)了信息隱藏的概念。模塊常用子程序加以實(shí)現(xiàn)。132014/12/24計(jì)算機(jī)科學(xué)導(dǎo)論4.2.2面向?qū)ο蟮某绦蛟O(shè)計(jì)方法u 1面向?qū)ο蟮乃枷?#216; OO(Object Oriented，面向?qū)ο?的程序設(shè)計(jì)把客觀事物看作具有屬性和行為的對(duì)象，通過抽象找出同一類對(duì)象

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

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

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

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

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

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

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

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

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

16、提高程序效率的根本途徑在于選擇良好的設(shè)計(jì)方法、良好的數(shù)據(jù)結(jié)構(gòu)，而不是靠編程時(shí)對(duì)程序語句做調(diào)整。292014/12/24計(jì)算機(jī)科學(xué)導(dǎo)論4.2.5程序設(shè)計(jì)舉例例4.1 輸入三角形的3個(gè)邊長(zhǎng)a，b和c ，求三角形面積。s = (a + b + c) / 2area =s(s - a)(s - b)(s - c)則計(jì)算該三角形的面積的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ì)算機(jī)科學(xué)導(dǎo)論4.2.5程序設(shè)計(jì)舉例ax2 + bx + c = 0例4.2 求輸入，設(shè)根為：方程的根，a，b，c 由鍵盤- 4ac ³ 0b2，根據(jù)數(shù)學(xué)知識(shí)，可以求得方程的- b +- 4ac- b - 4acb2b2x1 =x2 =22p = - bb2- 4ac設(shè) :，q =2a2a則方程的根可以改寫為：x1 = p + qx2 = p - q312014/12/24計(jì)算機(jī)科學(xué)導(dǎo)論4

18、.2.5程序設(shè)計(jì)舉例計(jì)算該方程的根的源程序如下：#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ì)算機(jī)科學(xué)導(dǎo)論4.3基本數(shù)據(jù)結(jié)構(gòu)u 數(shù)據(jù)結(jié)構(gòu)(Data Structure)是系統(tǒng)設(shè)計(jì)和程序開發(fā)的重要基礎(chǔ)。332014/12/24

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

20、數(shù)據(jù)的基本。在不同的應(yīng)用環(huán)境中，數(shù)據(jù)元素有時(shí)可以稱為節(jié)點(diǎn)、等。Ø 數(shù)據(jù)項(xiàng)是組成數(shù)據(jù)元素的不可分割的最小。最簡(jiǎn)單的數(shù)據(jù)元素是由一個(gè)數(shù)據(jù)項(xiàng)的。Ø 同類數(shù)據(jù)元素的集合稱為數(shù)據(jù)對(duì)象。352014/12/24計(jì)算機(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ì)算機(jī)科學(xué)導(dǎo)論4.3.1基本概念Ø 線性結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)中，如果數(shù)據(jù)元間存在著前后順序的關(guān)系，即

21、除了第一個(gè)數(shù)據(jù)元素和最后一個(gè)元素外，其他每個(gè)元素都有惟一的一個(gè)前驅(qū)和一個(gè)后繼元素，這樣的數(shù)據(jù)元 間的關(guān)系被稱為線性結(jié)構(gòu)。Ø 樹形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)中，如果數(shù)據(jù)元間有順序關(guān)系，且除了一個(gè)被稱為根節(jié)點(diǎn)的元素外，每個(gè)元素都有一個(gè)前驅(qū)節(jié)點(diǎn)， 并且可以有多個(gè)后繼節(jié)點(diǎn)，這種邏輯結(jié)構(gòu)稱為樹形結(jié)構(gòu)。Ø 圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)中，如果任何一個(gè)數(shù)據(jù)元素都可以有多個(gè)前 驅(qū)節(jié)點(diǎn)和多個(gè)后繼節(jié)點(diǎn)，這種邏輯結(jié)構(gòu)稱為圖形結(jié)構(gòu)。372014/12/24計(jì)算機(jī)科學(xué)導(dǎo)論4.3.1基本概念Ø (2) 數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)是指邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的表示。數(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ì)算機(jī)科學(xué)導(dǎo)論4.3.1基本概念Ø 順序結(jié)構(gòu)把所有元素存放在一片連續(xù)的單元中，邏輯上相鄰的元素在物理位置相鄰的單元中，由此得到的表示稱為順序結(jié)構(gòu)。順序結(jié)構(gòu)常借助于程序設(shè)計(jì)語言中的數(shù)組來實(shí)現(xiàn)。優(yōu)點(diǎn)是使用方法簡(jiǎn)單，缺點(diǎn)是必須預(yù)先分析出所需定義數(shù)組的大小。392014/12/24計(jì)算機(jī)科學(xué)導(dǎo)論4.3.1基本概念Ø 鏈表結(jié)構(gòu)對(duì)邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關(guān)系通過附設(shè)的指針域來實(shí)現(xiàn)，由此得到的表示稱為鏈?zhǔn)浇Y(jié)構(gòu)。鏈?zhǔn)浇Y(jié)構(gòu)通常借助于程序設(shè)計(jì)語言中的指針來實(shí)現(xiàn)。4020

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

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

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

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

27、DCBACBAEDCBA4.3.2 幾種典型的數(shù)據(jù)結(jié)構(gòu)Ø 操作用來檢查棧內(nèi)數(shù)據(jù)是否為空，返回結(jié)果是一個(gè)邏輯值：真或假。如果棧頂和棧底重合，說明堆棧為空。502014/12/24計(jì)算機(jī)科學(xué)導(dǎo)論4.3.2u 3. 隊(duì)列Ø (1) 定義對(duì)于由N個(gè)數(shù)據(jù)元素果在其固定的一端只幾種典型的數(shù)據(jù)結(jié)構(gòu)的一個(gè)線性序列，如數(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ì)算機(jī)科學(xué)導(dǎo)論4

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

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

30、域中，樹型結(jié)構(gòu)可以用于大型列表的搜索、源程序的語法結(jié)構(gòu)、人工智能系統(tǒng)等諸多問題。572014/12/24計(jì)算機(jī)科學(xué)導(dǎo)論4.3.2Ø (2) 運(yùn)算樹常見的基本運(yùn)算有：Ø 幾種典型的數(shù)據(jù)結(jié)構(gòu)、刪除和遍歷。在樹中合適的位置，添加一個(gè)節(jié)點(diǎn)，通常新的節(jié)點(diǎn)后，仍然應(yīng)該保持該樹本身所具有的性質(zhì)。Ø 刪除在樹中找到滿足條件的節(jié)點(diǎn)并刪除。通常刪除 節(jié)點(diǎn)后，也要保持該樹本身所具有的性質(zhì)。Ø 遍歷按照某種順序或規(guī)則，對(duì)樹中的每個(gè)節(jié)點(diǎn)逐一進(jìn)行的過程。582014/12/24計(jì)算機(jī)科學(xué)導(dǎo)論4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)592014/12/24計(jì)算機(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)中，每個(gè)數(shù)據(jù)元素稱為一個(gè)頂點(diǎn)，任意 兩個(gè)頂點(diǎn)之間都可能相關(guān)，這種相關(guān)性用一條邊來表示，頂點(diǎn)之間的鄰接關(guān)系可以是任意的。Ø 圖在計(jì)算機(jī)領(lǐng)域有著廣泛的應(yīng)用，可以計(jì)算機(jī)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，以及圖論中的最小生成樹等問題。除此以外，圖在自然科會(huì)科學(xué)和人文科學(xué)等許多領(lǐng)域也都有著非常廣泛的應(yīng)用。602014/12/24計(jì)算機(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)在圖中去掉一個(gè)頂點(diǎn)，顯然，在去掉一個(gè)頂點(diǎn)的同時(shí)還應(yīng)該刪除與該頂點(diǎn)所連接的邊。幾種典型的數(shù)據(jù)結(jié)構(gòu)612014/12/24計(jì)算機(jī)科學(xué)導(dǎo)論4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)Ø 添加邊根據(jù)指定的頂點(diǎn)，添加相應(yīng)的邊。Ø 刪除邊根據(jù)指定的頂點(diǎn)，刪除相應(yīng)的邊。Ø 遍歷圖按照一定的規(guī)則，對(duì)圖中的每個(gè)數(shù)據(jù)頂點(diǎn)逐一進(jìn)行。622014/12/24計(jì)算機(jī)科學(xué)導(dǎo)論4.3.2 幾種典型的數(shù)據(jù)結(jié)構(gòu)Ø (3) 實(shí)現(xiàn)圖通常用數(shù)組和鏈表兩種結(jié)構(gòu)加以實(shí)現(xiàn)。對(duì)于各個(gè)頂點(diǎn)和頂點(diǎn)之間的關(guān)系分別采用鄰接矩陣

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

34、#216; 查找的方法主要有順序查找、二分查找、分塊查找、數(shù)表的動(dòng)態(tài)查找（二叉排序樹查找、平衡二叉樹AVL樹、B樹、B+樹）、哈希查找等。u 1 順序查找Ø 順序查找是在一個(gè)隊(duì)列中找出與給定關(guān)鍵字相同數(shù)值的具置。原理是讓關(guān)鍵字與隊(duì)列中的數(shù)從第一個(gè)開始逐個(gè)比較，直到找出與給定關(guān)鍵字相同的數(shù)值為止。662014/12/24計(jì)算機(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、則查找；否則利用中間位置將表分成前、后兩個(gè)子表，如果中間位置的關(guān)鍵字小于查找關(guān)鍵字，則進(jìn)一步查找前一子表（假定隊(duì)列是從小到大排列），否則進(jìn)一步查找后一子表。重復(fù)以上過程，直至找到滿足條件的，使查找，或直至子表不存在為止，此時(shí)查找失敗。672014/12/24計(jì)算機(jī)科學(xué)導(dǎo)論4.3.3 查找Ø 優(yōu)、缺點(diǎn)：二分查找法的優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好；其缺點(diǎn)是要求待查表為有序表，且、刪除。因此，二分查找方法適用于不經(jīng)常變動(dòng)而查找頻繁的有序列表。682014/12/24計(jì)算機(jī)科學(xué)導(dǎo)論4.3.3 查找u 3分塊查找Ø 分塊查找又稱索引順序查找，它是順序查找的一種改進(jìn)方法。&#

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