第4章-程序設(shè)計基礎(chǔ)

第4章

程序設(shè)計基礎(chǔ)學(xué)習(xí)目標(biāo)了解程序設(shè)計的基礎(chǔ)知識、程序設(shè)計風(fēng)格的重要性、基本的查找和排序方法。掌握結(jié)構(gòu)化程序設(shè)計方法和面向?qū)ο蟪绦蛟O(shè)計方法的思想、幾種基本的數(shù)據(jù)結(jié)構(gòu)。學(xué)習(xí)計算機首先要學(xué)習(xí)程序設(shè)計，良好的程序設(shè)計技能和風(fēng)格有助于加深對計算機的理解和進一步學(xué)習(xí)。第4章

程序設(shè)計基礎(chǔ)4.1程序設(shè)計

程序設(shè)計是指用計算機語言對所要解決的問題中的數(shù)據(jù)以及處理問題的方法和步驟所做的完整而準(zhǔn)確的描述的過程。程序設(shè)計步驟如下：確定要解決的問題。分析問題。選擇計算方法。確定數(shù)據(jù)結(jié)構(gòu)和算法。

繪制流程圖。

編寫程序。

調(diào)試并測試程序。

整理資料，交付使用。高質(zhì)量程序設(shè)計目標(biāo)是結(jié)構(gòu)化程度高、可讀性好、效率高、可靠性高、便于維護。1．自上而下與自下而上先將一個大問題分解成若干個子問題，把比較復(fù)雜的子問題繼續(xù)分解成更加簡單的二級子問題，直至每個子問題都有顯而易見的解決辦法，然后逐一編寫解決各個子問題的程序。設(shè)計程序時采用自上而下的方法比采用自下而上的方法效率要高得多。4.2.1結(jié)構(gòu)化程序設(shè)計方法4.2程序設(shè)計方法采用自上而下解決問題的思路如圖:4.2.1結(jié)構(gòu)化程序設(shè)計方法4．模塊化方法在自頂向下、逐步細(xì)化的過程中，把復(fù)雜問題分解成一個個簡單問題的最基本方法就是模塊化：按功能或?qū)哟谓Y(jié)構(gòu)劃分模塊，再對每個模塊進一步細(xì)化。模塊化便于問題的分析，也有利于程序員的組織與合作。模塊體現(xiàn)了信息隱藏的概念。模塊常用子程序加以實現(xiàn)。4.2.1結(jié)構(gòu)化程序設(shè)計方法2．結(jié)構(gòu)化方法結(jié)構(gòu)化方法有助于在正式編寫程序之前充分理解問題的實質(zhì)和實現(xiàn)方法，并且可以在具體編碼過程中提供指導(dǎo)。常用的結(jié)構(gòu)化方法有：結(jié)構(gòu)化分析SA（系統(tǒng)分析階段）結(jié)構(gòu)化設(shè)計SD（系統(tǒng)設(shè)計階段）結(jié)構(gòu)化程序設(shè)計SP（系統(tǒng)實施階段）4.2.1結(jié)構(gòu)化程序設(shè)計方法結(jié)構(gòu)化方法通常遵循以下原則:用戶參與的原則先分析、再設(shè)計、后實現(xiàn)的原則自上而下的原則階段成果文檔化4.2.1結(jié)構(gòu)化程序設(shè)計方法3．結(jié)構(gòu)化程序設(shè)計方法SP基本思想：采用自上而下、逐步求精的設(shè)計方法和單入口單出口的控制結(jié)構(gòu)?；驹瓌t：(1)使用順序、選擇、循環(huán)3種基本控制結(jié)構(gòu)表示程序邏輯。(2)程序語句組織成容易識別的語句模塊，每個模塊都是單入口、單出口。(3)嚴(yán)格控制GOTO語句的使用。4.2.1結(jié)構(gòu)化程序設(shè)計方法(a)順序結(jié)構(gòu)(b)選擇結(jié)構(gòu)(c)while循環(huán)(d)do-while循環(huán)4.2.1結(jié)構(gòu)化程序設(shè)計方法4.2.2面向?qū)ο蟮某绦蛟O(shè)計方法1．面向?qū)ο蟮乃枷虢Y(jié)構(gòu)化程序設(shè)計方法將解決問題的重點放在了實現(xiàn)過程的細(xì)節(jié)方面，把數(shù)據(jù)和對數(shù)據(jù)的操作（函數(shù)）分開。如果需要對數(shù)據(jù)結(jié)構(gòu)進行修改，則所有相關(guān)的操作函數(shù)都必須修改；若程序要升級，也需要大量修改函數(shù)。OO(ObjectOriented，面向?qū)ο?方法的出發(fā)點和基本原則是盡可能地模擬人類的思維方式，使開發(fā)軟件的方法和過程盡可能地接近人類解決現(xiàn)實問題的方法和過程。人們對一個具體問題進行分析、抽象，將其中的一些屬性和行為抽象成相應(yīng)的數(shù)據(jù)和函數(shù)并封閉進一個“類”，在計算機中就用這個“類”描述現(xiàn)實世界中的問題。對象是用來描述客觀事物的一個實體張三李四抽象類是具有相同屬性和方法的一組對象的概括屬性方法性別,年齡…說話,行走…具體化繼承新類人說話,行走…性別,年齡…大學(xué)生性別,年齡,專業(yè)…說話,行走,學(xué)習(xí)…消息面向?qū)ο蟮幕靖拍罘庋b性、多態(tài)性2．對象、消息傳遞和類

對象:

是對現(xiàn)實問題的高度概括、分類和抽象。每個對象都只有自己的數(shù)據(jù)和相應(yīng)的處理函數(shù)，整個程序是由一系列相互作用的對象來構(gòu)成，不同對象之間是通過發(fā)送消息來實現(xiàn)相互聯(lián)系、相互作用。

4.2.2面向?qū)ο蟮某绦蛟O(shè)計方法消息傳遞:

消息是對象之間進行通信的一種機制。發(fā)送給某個對象的一個消息包含著要求接收對象完成某些活動的信息。接收到消息的對象經(jīng)過解釋，然后予以響應(yīng)。這個通信機制叫做消息傳遞。發(fā)送消息的對象并不需要知道接收消息的對象如何對請求予以響應(yīng)。4.2.2面向?qū)ο蟮某绦蛟O(shè)計方法類:

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

第一是，將抽象得到的數(shù)據(jù)成員和代碼成員相結(jié)合，形成一個不可分割的整體，即對象，這種數(shù)據(jù)及行為的有機結(jié)合也就是封裝。第二個含義稱為信息隱蔽，即盡可能隱蔽對象的內(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)存在的類為基礎(chǔ)，并把這個已經(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.2.3函數(shù)程序設(shè)計函數(shù)程序設(shè)計語言使用非常簡單的計算模型或者程序觀點，一個程序是輸入集合到輸出集合的數(shù)學(xué)函數(shù)，執(zhí)行一個程序便是計算一個函數(shù)在給定輸入的輸出值。函數(shù)程序的特點是清晰、簡潔和易讀等，這些特點使得大型程序的開發(fā)更高效，維護更容易。函數(shù)程序設(shè)計語言因其簡單的基本理論，使現(xiàn)代程序設(shè)計的基本思想，如抽象、數(shù)據(jù)抽象、多態(tài)和重載等都得到了最清楚的體現(xiàn)。因此，函數(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．源程序文檔化標(biāo)識符應(yīng)按意取名。

程序應(yīng)加注釋。注釋是程序員與讀者之間通信的重要工具，用自然語言或偽碼描述。它說明了程序的功能，特別是在維護階段，對理解程序提供了明確指導(dǎo)。注釋分序言性注釋和功能性注釋。序言性注釋應(yīng)置于每個模塊的起始部分。內(nèi)容為：①說明每個模塊的用途、功能。

②說明模塊的接口：調(diào)用形式、參數(shù)描述及從屬模塊的清單。

③數(shù)據(jù)描述：重要數(shù)據(jù)的名稱、用途、限制、約束及其他信息。

④開發(fā)歷史：設(shè)計者、審閱者姓名及日期，修改說明及日期。

功能性注釋嵌入在源程序內(nèi)部，說明程序段或語句的功能以及數(shù)據(jù)的狀態(tài)。注意以下幾點：

①注釋用來說明程序段，而不是每一行程序都要加注釋。

②使用空行、縮格或括號，以便于區(qū)分注釋和程序。

③修改程序也應(yīng)修改注釋。4.2.4程序設(shè)計風(fēng)格示例2．?dāng)?shù)據(jù)說明為了使數(shù)據(jù)定義更易于理解和維護，有以下原則。

(1)數(shù)據(jù)說明順序應(yīng)規(guī)范，使數(shù)據(jù)的屬性更易于查找，從而有利于測試、糾錯與維護。如常量說明、類型說明、全局變量說明、局部變量說明等。

(2)一個語句說明多個變量時，各變量名按字典順序排列。

(3)對于復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，要加注釋，說明在程序?qū)崿F(xiàn)時的特點。4.2.4程序設(shè)計風(fēng)格3．語句構(gòu)造語句構(gòu)造的原則是簡單、直接，不能為了追求效率而使代碼復(fù)雜化；一行只寫一條語句；不同層次的語句采用縮進形式；要避免復(fù)雜的判定條件，避免多重的循環(huán)嵌套；表達(dá)式中使用括號以提高運算次序的清晰度等。4.2.4程序設(shè)計風(fēng)格4．在編寫輸入和輸出語句時應(yīng)考慮原則

輸入操作步驟和輸入格式盡量簡單。

應(yīng)檢查輸入數(shù)據(jù)的合法性、有效性，報告必要的輸入狀態(tài)信息及錯誤信息。

輸入一批數(shù)據(jù)時，使用數(shù)據(jù)或文件結(jié)束標(biāo)志，而不要用計數(shù)來控制。

交互式輸入時，提供可用的選擇和邊界值。

當(dāng)程序設(shè)計語言有嚴(yán)格的格式要求時，應(yīng)保持輸入格式的一致性。

輸出數(shù)據(jù)表格化、圖形化。

輸入、輸出風(fēng)格還受其他因素的影響，如輸入/輸出設(shè)備、用戶經(jīng)驗及通信環(huán)境等。4.2.4程序設(shè)計風(fēng)格5．效率效率是指處理機時間和存儲空間的使用。(1)效率是一個性能要求，目標(biāo)在需求分析時給出。

(2)追求效率要建立在不損害程序可讀性和可靠性基礎(chǔ)上，要在確保程序正確、清晰的情況下提高效率。(3)提高程序效率的根本途徑在于選擇良好的設(shè)計方法、良好的數(shù)據(jù)結(jié)構(gòu)，而不是靠編程時對程序語句做調(diào)整。4.2.4程序設(shè)計風(fēng)格4.2.5程序設(shè)計舉例例4.1輸入三角形的3個邊長a，b和c

，求三角形面積。

則計算該三角形的面積的C語言源程序如下：

#include<stdio.h>#include<math.h>voidmain(){floata,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)*(s-c));printf(“a=%7.2f,b=%7.2f,c=%7.2f,s=%7.2f\n”,a,b,c,s);printf(“area=%7.2f\n”,area);//輸出語句}

例4.2

求

方程的根，a、b、c由鍵盤輸入，設(shè)，根據(jù)數(shù)學(xué)知識，可以求得方程的根為：

設(shè):

，

則方程的根可以改寫為：4.2.5程序設(shè)計舉例計算該方程的根的源程序如下：

#include<math.h>voidmain(){floata,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.2f\nx2=%5.2f\n”,x1,x2);}4.2.5程序設(shè)計舉例4.3基本數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(DataStructure)是系統(tǒng)設(shè)計和程序開發(fā)的重要基礎(chǔ)。程序＝數(shù)據(jù)結(jié)構(gòu)＋算法4.3.1基本概念1．?dāng)?shù)據(jù)、數(shù)據(jù)類型在計算機系統(tǒng)內(nèi)，數(shù)據(jù)通常是指能夠輸入到計算機中并被計算機進行處理的符號的集合，可以是數(shù)值數(shù)據(jù)，也可以是非數(shù)值數(shù)據(jù)。數(shù)據(jù)類型是指具有相同取值范圍和可以實施同種操作的數(shù)據(jù)的集合。例如，在程序設(shè)計語言中，通常定義了字符型、整數(shù)型、數(shù)組等多種數(shù)據(jù)類型。2．?dāng)?shù)據(jù)元素、數(shù)據(jù)項能夠獨立并完整地描述客觀世界實體的基本數(shù)據(jù)單元稱為數(shù)據(jù)元素，它是組成數(shù)據(jù)的基本單位。在不同的應(yīng)用環(huán)境中，數(shù)據(jù)元素有時可以稱為節(jié)點、記錄等。數(shù)據(jù)項是組成數(shù)據(jù)元素的不可分割的最小單位。最簡單的數(shù)據(jù)元素是由一個數(shù)據(jù)項構(gòu)成的。4.3.1基本概念學(xué)號姓名性別專業(yè)3．?dāng)?shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)元素之間的相互關(guān)系的集合，包括了數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)以及數(shù)據(jù)的運算。（1）數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系。4.3.1基本概念線性結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)中，如果數(shù)據(jù)元素之間存在著前后順序的關(guān)系，即除了第一個數(shù)據(jù)元素和最后一個元素外，其他每個元素都有惟一的一個前驅(qū)和一個后繼元素，這樣的數(shù)據(jù)元素之間的關(guān)系被稱為線性結(jié)構(gòu)。樹形結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)中，如果數(shù)據(jù)元素之間有順序關(guān)系，且除了一個被稱為根節(jié)點的元素外，每個元素都有一個前驅(qū)節(jié)點，并且可以有多個后繼節(jié)點，這種邏輯結(jié)構(gòu)稱為樹形結(jié)構(gòu)。圖形結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)中，如果任何一個數(shù)據(jù)元素都可以有多個前驅(qū)節(jié)點和多個后繼節(jié)點，這種邏輯結(jié)構(gòu)稱為圖形結(jié)構(gòu)。4.3.1基本概念（2）數(shù)據(jù)的物理結(jié)構(gòu)

數(shù)據(jù)的物理結(jié)構(gòu)是指邏輯結(jié)構(gòu)在計算機存儲器中的表示。

數(shù)據(jù)的物理結(jié)構(gòu)主要有四種，分別是順序結(jié)構(gòu)、鏈表結(jié)構(gòu)、索引結(jié)構(gòu)及散列結(jié)構(gòu)。4.3.1基本概念①順序結(jié)構(gòu)

把所有元素存放在一片連續(xù)的存儲單元中，邏輯上相鄰的元素存儲在物理位置相鄰的存儲單元中，由此得到的存儲表示稱為順序存儲結(jié)構(gòu)。

程序設(shè)計語言中的數(shù)組常使用順序存儲結(jié)構(gòu)來實現(xiàn)。優(yōu)點是使用方法簡單，缺點是必須預(yù)先分析出所需定義的數(shù)組的大小。4.3.1基本概念②鏈表結(jié)構(gòu)

對邏輯上相鄰的元素不要求其物理位置相鄰，元素間的邏輯關(guān)系通過附設(shè)的指針域來實現(xiàn)，由此得到的存儲表示稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。

鏈?zhǔn)酱鎯Y(jié)構(gòu)通常借助于程序設(shè)計語言中的指針來實現(xiàn)。4.3.1基本概念③索引結(jié)構(gòu)

針對每個數(shù)據(jù)結(jié)構(gòu)建立一張所謂的索引表，每個數(shù)據(jù)元素占用表中的一項，每個表項包含一個能夠惟一識別一個元素的關(guān)鍵字和用以指示該元素的地址指針。④散列結(jié)構(gòu)

通過構(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ù)結(jié)構(gòu)1．線性表

(1)定義

線性表是由有限個相同的數(shù)據(jù)元素構(gòu)成的序列，元素之間是一對一的線性關(guān)系，除了第一個元素只有直接后繼、最后一個元素只有直接前驅(qū)外，其余數(shù)據(jù)元素都有一個直接前驅(qū)和一個直接后繼，如圖：(2)運算和實現(xiàn)

線性表通常采用順序和鏈表兩種物理實現(xiàn)。對于經(jīng)常變化的表，通常采取鏈表結(jié)構(gòu)。線性表常用的運算主要有：插入、刪除、查詢和遍歷。4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)①遍歷

是指按照某種方式，逐一訪問線性表中的每一個數(shù)據(jù)元素，并執(zhí)行相同處理的操作。這里的處理可以是讀、寫、或查詢等。

②查詢

在線性表中，按照查詢條件，定位數(shù)據(jù)元素的過程就是查詢。查詢的條件一般根據(jù)數(shù)據(jù)元素中的關(guān)鍵字進行。4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)③插入

在保持原有的存儲結(jié)構(gòu)的前提下，根據(jù)插入要求，在適當(dāng)?shù)奈恢貌迦胍粋€元素。插入操作要求線性表要有足夠的存放新元素的空間，如果空間不足，插入操作無法進行，線性表會溢出。④刪除

在線性表中，找到滿足條件的數(shù)據(jù)元素，并刪除。如果線性表為空，刪除就會失敗。4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)演示2.棧(1)定義

對于由N個數(shù)據(jù)元素構(gòu)成的一個線性序列，如果只允許在其固定的一端位置插入和刪除一個數(shù)據(jù)元素，那么這種邏輯結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)稱為堆?；驐?stack)。

允許插入或刪除的這一端稱為棧頂，另一個固定端稱為棧底。當(dāng)表中沒有元素時稱為空棧。特點：先進后出4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)(2)運算和實現(xiàn)①入棧：也叫壓棧，是在棧頂添加新元素的操作，新的元素入棧后成為新的棧頂元素。②出棧：也叫退?；驈棗＃菍ｍ斣貜臈Ｖ型顺霾鬟f給用戶程序的操作。③判斷（判空/滿）：用來檢查棧內(nèi)數(shù)據(jù)是否為空，返回結(jié)果是一個邏輯值。如果棧頂指針和棧底重合，說明堆棧為空；如果棧頂指針和棧頂重合，說明堆棧為滿。4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)棧頂指針棧頂指針棧頂指針棧頂指針數(shù)據(jù)出棧只是邏輯上離開棧，通過移動棧頂指針來標(biāo)識，但物理上仍然留存于原來的存儲空間，將來有新數(shù)據(jù)入棧時，便會覆蓋舊數(shù)據(jù)。3.隊列(1)定義

對于由N個數(shù)據(jù)元素構(gòu)成的一個線性序列，如果在其固定一端只允許插入數(shù)據(jù)元素，且在另一端只允許刪除，這種邏輯結(jié)構(gòu)稱為隊列(Queue)。允許插入的一端稱為隊尾(Rear)，允許刪除的一端稱為隊首(Front)。

特點：先進先出4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)(2)運算和實現(xiàn)①入隊：在隊列中插入一個新數(shù)據(jù)元素的過程，插入在隊尾進行，新的元素成為隊尾。②出隊出隊是在隊列中刪除一個數(shù)據(jù)元素的過程，刪除在隊首進行，并把出來的數(shù)據(jù)傳遞給用戶程序。F、G入隊③判斷：

判斷操作用來檢查隊列是否為空，返回結(jié)果是一個邏輯值：真或假，如圖:4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)(3)循環(huán)隊列的實現(xiàn)4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)4.樹(1)定義

在樹型結(jié)構(gòu)中，每個數(shù)據(jù)元素稱為一個結(jié)點，除了唯一的根結(jié)點外，其他每個結(jié)點都有且僅有一個父結(jié)點，每個元素可以有多個子結(jié)點。

樹型結(jié)構(gòu)是一種非常重要的非線性數(shù)據(jù)結(jié)構(gòu)，可以用來描述客觀世界中廣泛存在的以分支關(guān)系定義的層次結(jié)構(gòu)，如各種各樣的社會組織結(jié)構(gòu)關(guān)系。在計算機領(lǐng)域中，樹型結(jié)構(gòu)可以用于大型列表的搜索、源程序的語法結(jié)構(gòu)、人工智能系統(tǒng)等諸多問題。4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)(2)實現(xiàn)：主要采用鏈表的方式(3)運算

樹常見的基本運算有：插入、刪除和遍歷。①插入

在樹中合適的位置，添加一個節(jié)點，通常插入新的節(jié)點后，仍然應(yīng)該保持該樹本身所具有的性質(zhì)。②刪除

在樹中找到滿足條件的節(jié)點并刪除。通常刪除節(jié)點后，也要保持該樹本身所具有的性質(zhì)。③遍歷

按照某種順序或規(guī)則，對樹中的每個節(jié)點逐一進行訪問的過程。4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)5.圖(1)定義圖形結(jié)構(gòu)是一種比樹型結(jié)構(gòu)更復(fù)雜的非線性結(jié)構(gòu)。在圖形結(jié)構(gòu)中，每個數(shù)據(jù)元素稱為一個頂點，任意兩個頂點之間都可能相關(guān)，這種相關(guān)性用一條邊來表示，頂點之間的鄰接關(guān)系可以是任意的。圖在計算機領(lǐng)域有著廣泛的應(yīng)用，可以用來描述計算機網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，以及圖論中的最小生成樹等問題。除此以外，圖在自然科學(xué)、社會科學(xué)和人文科學(xué)等許多領(lǐng)域也都有著非常廣泛的應(yīng)用。4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)(2)實現(xiàn)：主要采用數(shù)組或鏈表的方式(3)運算

常見的基本運算有：添加頂點、刪除頂點、添加邊、刪除邊和遍歷圖。①添加頂點

在圖中添加新的頂點，新添加的頂點通常是孤立的節(jié)點，還沒有邊連接。②刪除頂點

在圖中去掉一個頂點，顯然，在去掉一個頂點的同時還應(yīng)該刪除與該頂點所連接的邊。4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)③添加邊

根據(jù)指定的頂點，添加相應(yīng)的邊。④刪除邊

根據(jù)指定的頂點，刪除相應(yīng)的邊。⑤遍歷圖

按照一定的規(guī)則，對圖中的每個數(shù)據(jù)頂點逐一進行訪問。4.3.2幾種典型的數(shù)據(jù)結(jié)構(gòu)4.3.3查找查找是指根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。若表中存在這樣的一個記錄，則稱查找是成功的，此時查找的結(jié)果為給出整個記錄的信息，或指示該記錄在表中的位置；若表中不存在關(guān)鍵字等于給定值的記錄，則稱查找失敗，此時查找的結(jié)果可給出一個“空”記錄或“空”指針。查找的方法主要有順序查找、二分查找、分塊查找、數(shù)表的動態(tài)查找（二叉排序樹查找、平衡二叉樹AVL樹、B樹、B+樹）、哈希查找等。1．順序查找順序查找是在一個隊列中找出與給定關(guān)鍵字相同數(shù)值的具體位置。原理是讓關(guān)鍵字與隊列中的數(shù)從第一個開始逐個比較，直到找出與給定關(guān)鍵字相同的數(shù)值為止。4.3.3查找2．二分查找二分查找又稱折半查找，它是一種效率較高的查找方法。但二分查找必須采用順序存儲結(jié)構(gòu)，且必須按關(guān)鍵字大小有序?qū)o定隊列進行排列。二分查找算法的思想優(yōu)、缺點：二分查找法的優(yōu)點是比較次數(shù)少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入、刪除困難。因此，二分查找方法適用于不經(jīng)常變動而查找頻繁的有序列表。4.3.3查找要查找數(shù)字21：2510151721223541556370889598251015172122354155637088959825101517

21

223541556370889598開始開始開始結(jié)束結(jié)束結(jié)束中值中值中值3．分塊查找分塊查找又稱索引順序查找，它是順序查找的一種改進方法。分塊的原則是將n個數(shù)據(jù)元素“按塊有序”劃分為m塊（m≤n）。每一塊中的結(jié)點不必有序，但塊與塊之間必須“按塊有序。分塊查找是首先選取各塊中的最大關(guān)鍵字構(gòu)成一個索引表；然后查找分兩個部分：先對索引表進行二分查找用于確定待查記錄在哪一塊中；最后在已確定的塊中用順序法進行查找。4.3.3查找索引表中的關(guān)鍵字是每塊中的最大值要查找數(shù)字46：215078991481232111244633505560786686998091123456789101112131415索引表查找表4.3.4排序排序是計算機程序設(shè)計中的一種重要操作。簡單地說，排序就是要整理文件中的記錄，使之按關(guān)鍵字遞增(或遞減)次序排列起來。排序的方法很多，每一種方法都有各自的優(yōu)、缺點，適合在不同的環(huán)境中使用。常見的內(nèi)部排序方法有直接插入排序、冒泡排序、快速排序等。1．直接插入排序直接插入排序是一種最簡