公共基礎(chǔ)知識第1章數(shù)據(jù)結(jié)構(gòu)與算法算法算法的基本概念算法是指對解題方案的準(zhǔn)確而完整的描述。簡單地說，就是解決問題的操作步驟。值得注意的是，算法不等于數(shù)學(xué)上的計算方法，也不等于程序。在用計算機(jī)解決實(shí)際問題時,往往先設(shè)計算法,用某種表達(dá)方式(如流程圖)描述，然后再用具體的程序設(shè)計語言描述此算法(即編程)。在編程時由于要受到計算機(jī)系統(tǒng)運(yùn)行環(huán)境的限制，因此，程序的編制通常不可能優(yōu)于算法的設(shè)計。算法的基本特征一般來說，一個算法應(yīng)具有以下4個基本特征。(1)可行性(Effectiveness)：算法在特定的執(zhí)行環(huán)境中執(zhí)行，應(yīng)當(dāng)能夠得出滿意的結(jié)果，即必須有一個或多個輸出。(2)確定性(Definiteness)：算法中的每一個步驟都必須有明確的定義，不允許有模棱兩可的解釋和多義性。(3)有窮性(Finiteness)：算法必需在有限時間內(nèi)做完，即算法必需能在執(zhí)行有限個步驟之后終止。（4）擁有足夠的情報：要使算法有效必需為算法提供足夠的情報。當(dāng)算法擁有足夠的情報時，此算法才是有效的；而當(dāng)提供的情報不夠時，算法可能無效。算法的基本要素通常，一個算法由兩種基本要素組成。對數(shù)據(jù)對象的運(yùn)算和操作；算法的控制結(jié)構(gòu)，即運(yùn)算或操作時間的順序。（1）算法中對數(shù)據(jù)的運(yùn)算和操作在一般的計算機(jī)系統(tǒng)中，基本的運(yùn)算和操作有以下的電如表1-1所示。表1-1 磷基本的運(yùn)算和操作運(yùn)苴類型操作實(shí)例篁末運(yùn)菖?、一、X、+a+b>3-1邏輯運(yùn)苴與（&X或（II1非（，）?1>1II0、1&1關(guān)系運(yùn)苴><=#a>bsa=c、b#c數(shù)據(jù)傳輸賦值、輸入、輸出b=3（2）算法的控制結(jié)構(gòu)一個算法的功能不僅僅取決于所選用的操作，而且還與各操作之間的執(zhí)行順序有關(guān)。算法中各操作之間的執(zhí)行順序稱為算法的控制結(jié)構(gòu)。算法的控制結(jié)構(gòu)給出了算法的基本框架，它不僅決定了算法中各操作的執(zhí)行順序，而且也直接反映了算法的設(shè)計是否符合結(jié)構(gòu)化原則。描述算法的工具通常有傳統(tǒng)流程圖、N-S結(jié)構(gòu)化流程圖、算法描述語言等。一個算法一般都可以用順序、選擇、循環(huán)3種基本控制結(jié)構(gòu)組合而成。算法設(shè)計的基本方法雖然設(shè)計算法是一件非常困難的工作，但是算法設(shè)計也不是無章可循，人們經(jīng)過實(shí)踐，總結(jié)和積累了許多行之有效的方法。常用的幾種算法設(shè)計方法有列舉法、歸納法、遞推法、遞歸法、減半遞推技術(shù)和回溯法。算法設(shè)計的要求通常一個好的算法應(yīng)達(dá)到如下目標(biāo)：(1)正確性(Correctness)正確性大體可以分為以下4個層次：①程序不含語法錯誤；②程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；③程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；④程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果。(2)可讀性(Readability)算法主要是為了方便人的閱讀與交流，其次才是其執(zhí)行?？勺x性好有助于用戶對算法的理解；晦澀難懂的程序易于隱藏較多錯誤，難以調(diào)試和修改。(3)健壯性(Robustness)當(dāng)輸入數(shù)據(jù)非法時，算法也能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，而不會產(chǎn)生莫名其妙的輸出結(jié)果。(4)效率與低存儲量需求效率指的是程序執(zhí)行時，對于同一個問題如果有多個算法可以解決，執(zhí)行時間短的算法效率高；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。1.1.2算法的復(fù)雜度算法的復(fù)雜度是算法效率的度量，是評價算法優(yōu)劣的重要依據(jù)。算法復(fù)雜度包括算法的時間復(fù)雜度和算法的空間復(fù)雜的。算法的時間復(fù)雜度算法的時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量。為了能夠比較客觀地反映出一個算法的效率，在度量一個算法的工作量時，不僅應(yīng)該與所使用的計算機(jī)、程序設(shè)計語言以及程序編制者無關(guān)，而且還應(yīng)該與算法實(shí)現(xiàn)過程中的許多細(xì)節(jié)無關(guān)。算法的計算工作量是用算法所執(zhí)行的基本運(yùn)算次數(shù)來度量的，而算法所執(zhí)行的基本運(yùn)算次數(shù)是問題規(guī)模(通常用整數(shù)n表示)的函數(shù)。即算法的工作量=f(n)例如，在NxN矩陣相乘的算法中，整個算法的執(zhí)行時間與該基本操作(乘法)重復(fù)執(zhí)行的次數(shù)小成正比，也就是時間復(fù)雜度為K即f(n)=0(n3)在有的情況下，算法中的基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。例如在起泡排序的算法中，當(dāng)要排序的數(shù)組a初始序列為自小至大有序時，基本操作的執(zhí)行次數(shù)為0；當(dāng)初始序列為自大至小有序時，基本操作的執(zhí)行次數(shù)為n(n-1)/2o對這類算法，可以采用平均性態(tài)和最壞情況復(fù)雜性兩種方法來分析。算法的空間復(fù)雜度算法的空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。一個算法所占用的存儲空間包括算法程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲空間以及算法執(zhí)行過程中所需要的額外空間。其中額外空間包括算法程序執(zhí)行過程中的工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲空間。如果額外空間量相對于問題規(guī)模來說是常數(shù)，則稱該算法是原地(inplace)工作的。在許多實(shí)際問題中，為了減少算法所占的存儲空間，通常采用壓縮存儲技術(shù)，以便盡量減少不必要的額外空間。1.2數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)是計算機(jī)科學(xué)與技術(shù)領(lǐng)域廣泛使用的一個基本術(shù)語，用來反映數(shù)據(jù)的內(nèi)部構(gòu)成。在給出數(shù)據(jù)結(jié)構(gòu)的定義之前，我們先弄清楚幾個概念。數(shù)據(jù)(data)：是對客觀事物的符號表示，在計算機(jī)科學(xué)中是指所有能輸入到計算機(jī)中并被計算機(jī)程序處理的符號的總稱。數(shù)據(jù)元素(dataelement)：是數(shù)據(jù)的基本單位，在計算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理。數(shù)據(jù)對象(dataobject)：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。簡單地說，數(shù)據(jù)結(jié)構(gòu)是指相互關(guān)聯(lián)的數(shù)據(jù)元素的集合，即數(shù)據(jù)的組織形式。所謂結(jié)構(gòu)，就是指數(shù)據(jù)元素之間的前后件關(guān)系(或稱直接前驅(qū)與直接后繼關(guān)系)。例如，在考慮一日三餐的時間順序關(guān)系時，"早餐“是"午餐”的前件（或直接前驅(qū)），而"午餐"是"早餐”的后件（或直接后繼）；同樣，"午餐"是"晚餐"的前件，"晚餐"是"午餐"的后件。又例如，在考慮學(xué)歷的順序關(guān)系時，"小學(xué)"是"初中"的前件，而“初中”是小學(xué)的后件。同樣，"初中"是"高中“的前件，”高中“是“初中"的后件。前后件關(guān)系是數(shù)據(jù)元素之間的一個基本關(guān)系，但前后件關(guān)系所表示的實(shí)際意義隨具體對象的不同而不同。一般來說，數(shù)據(jù)元素之間的任何關(guān)系都可以用前后件關(guān)系來描述。數(shù)據(jù)結(jié)構(gòu)的兩個要素「數(shù)據(jù)”和”結(jié)構(gòu)”是緊密聯(lián)系在一起的，“數(shù)據(jù)"是有結(jié)構(gòu)的數(shù)據(jù)，而不是無關(guān)聯(lián)的、松散的；而“結(jié)構(gòu)”就是數(shù)據(jù)元素間的關(guān)系，是由數(shù)據(jù)的特性所決定的。數(shù)據(jù)結(jié)構(gòu)作為計算機(jī)的一門學(xué)科，主要研究和討論以下三個方面：（1）數(shù)據(jù)集合中個數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；（2）在對數(shù)據(jù)元素進(jìn)行處理時，各數(shù)據(jù)元素在計算機(jī)中的存儲關(guān)系，即數(shù)據(jù)的存儲結(jié)構(gòu)；（3）對各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。討論以上問題的目的是為了提高數(shù)據(jù)處理的效率，即提高數(shù)據(jù)處理的速度以及盡量節(jié)省在數(shù)據(jù)處理過程中所占用的計算機(jī)存儲空間。數(shù)據(jù)的邏輯結(jié)構(gòu)由數(shù)據(jù)結(jié)構(gòu)的定義可知，一個數(shù)據(jù)結(jié)構(gòu)應(yīng)包含以下兩方面信息:（1）表示數(shù)據(jù)元素的信息；（2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。在此定義中，并沒有考慮數(shù)據(jù)元素的存儲，所以上述的數(shù)據(jù)結(jié)構(gòu)實(shí)際上是數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)是對數(shù)據(jù)元素之間的邏輯關(guān)系的描述，它可以用一個數(shù)據(jù)元素的集合和定義在此集合中的若干關(guān)系來表示。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個要素:一是數(shù)據(jù)元素的集合,通常記為D；二是D上的關(guān)系，它反映了數(shù)據(jù)元素之間的前后件關(guān)系，通常記為Ro一個數(shù)據(jù)結(jié)構(gòu)可以表示成B=（D,R）其中B表示數(shù)據(jù)結(jié)構(gòu)。為了反映D中各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來表示。例如，如果把一日三餐看作一個數(shù)據(jù)結(jié)構(gòu)，則可表示成B=（D,R）D=｛早餐，午餐，晚餐｝R=｛（早餐，午餐），（午餐，晚餐）｝數(shù)據(jù)的邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)、樹型結(jié)構(gòu)圖、網(wǎng)狀結(jié)構(gòu)圖和集合圖4種。數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu)（也稱數(shù)據(jù)的物理結(jié)構(gòu)）。在進(jìn)行數(shù)據(jù)處理時，被處理的各數(shù)據(jù)元素總是被存放在計算機(jī)的存儲空間中，而且各數(shù)據(jù)元素在計算機(jī)存儲空間中的位置關(guān)系與它們的邏輯關(guān)系可能不同。

由于數(shù)據(jù)元素在計算機(jī)存儲空間中的位置關(guān)系可能與邏輯關(guān)系不同，因此，為了表示存放在計算機(jī)存儲空間中的各數(shù)據(jù)元素之間的邏輯關(guān)系(即前后件關(guān)系)，在數(shù)據(jù)的存儲結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。一種數(shù)據(jù)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)，常用的存儲結(jié)構(gòu)有順序、鏈接、索引等存儲結(jié)構(gòu)。而采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。因此，在進(jìn)行數(shù)據(jù)處理時，選擇合適的存儲結(jié)構(gòu)是很重要的。數(shù)據(jù)結(jié)構(gòu)的圖形表示數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。在數(shù)據(jù)結(jié)構(gòu)的圖形表示中，對于數(shù)據(jù)集合D中的每一個數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示，一般稱之為數(shù)據(jù)結(jié)點(diǎn)，并簡稱為結(jié)點(diǎn)；為了進(jìn)一步表示各數(shù)據(jù)元素之間的前后件關(guān)系，對于關(guān)系R中的每一個二元組，用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。例如，例如，一日三餐的數(shù)據(jù)結(jié)構(gòu)可以用如圖l-5(a)所示的圖形來表示。又例如，軍職數(shù)據(jù)結(jié)構(gòu)可以用如圖l-5(b)所示的圖形來表示。(a)U*數(shù)據(jù)結(jié)構(gòu)的圖形及示圖1-5(b)(a)U*數(shù)據(jù)結(jié)構(gòu)的圖形及示圖1-5(b)軍職數(shù)據(jù)結(jié)構(gòu)的圖形表示數(shù)據(jù)結(jié)構(gòu)的圖形表示在數(shù)據(jù)結(jié)構(gòu)中，沒有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；沒有后件的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)(也稱為葉子結(jié)點(diǎn))。一個數(shù)據(jù)結(jié)構(gòu)中的結(jié)點(diǎn)可能是在動態(tài)變化的。根據(jù)需要或在處理過程中，可以在一個數(shù)據(jù)結(jié)構(gòu)中增加一個新結(jié)點(diǎn)（稱為插入運(yùn)算），也可以刪除數(shù)據(jù)結(jié)構(gòu)中的某個結(jié)點(diǎn)（稱為刪除運(yùn)算）。插入與刪除是對數(shù)據(jù)結(jié)構(gòu)的兩種基本運(yùn)算。除此之外，對數(shù)據(jù)結(jié)構(gòu)的運(yùn)算還有查找、分類、合并、分解、復(fù)制和修改等。線性結(jié)構(gòu)與非線性結(jié)構(gòu)如果在一個數(shù)據(jù)結(jié)構(gòu)中一個數(shù)據(jù)元素都沒有，則稱該數(shù)據(jù)結(jié)構(gòu)為空的數(shù)據(jù)結(jié)構(gòu)。在只有一個數(shù)據(jù)元素的數(shù)據(jù)結(jié)構(gòu)中，刪除該數(shù)據(jù)元素，就得到一個空的數(shù)據(jù)結(jié)構(gòu)；在一個空的數(shù)據(jù)結(jié)構(gòu)中插入一個新的元素后變成非空。根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件：（1）有且只有一個根結(jié)點(diǎn)；（2）每一個結(jié)點(diǎn)最多有一個前件，也最多有一個后件。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱為線性表。由此可見，在線性結(jié)構(gòu)中，各數(shù)據(jù)元素之間的前后件關(guān)系是很簡單的。需要特別說明的是，在一個線性表中插入或刪除任何一個結(jié)點(diǎn)后還應(yīng)是線性結(jié)構(gòu)。如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。在非線性結(jié)構(gòu)中，各數(shù)據(jù)元素之間的前后件關(guān)系要比線性結(jié)構(gòu)復(fù)雜。鏈?zhǔn)浇Y(jié)構(gòu)是總常用的非線性結(jié)構(gòu)。線性結(jié)構(gòu)與非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)。對于空的數(shù)據(jù)結(jié)構(gòu)，如果對該數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是按線性結(jié)構(gòu)的規(guī)則來處理的，則屬于線性結(jié)構(gòu)；否則屬于非線性結(jié)構(gòu)。線性表的定義線性表是一種最簡單且最常見的線性數(shù)據(jù)結(jié)構(gòu)。線性表是n(n>0)個元素構(gòu)成的有限序列(a］，a?,…，aQ。表中除了第一個外的每個元素，有且只有一個前件；除最后一個元素外的每個元素，有且只有一個后件。即線性表要么是一個空表，要么可以表示為(a］，a2,…，aQ其中a(i=l,2,n)是屬于數(shù)據(jù)對象的元素，通常也稱其為線性表中的一個結(jié)點(diǎn)。同一線性表中的數(shù)據(jù)元素必定具有相同的特性，即屬于同一數(shù)據(jù)對象。每個數(shù)據(jù)元素的具體含義，在不同情況下各不相同，它可以是一個數(shù)或一個字符，也可以是一個具體事物，甚至其他更復(fù)雜的信息。例如，英文字母表(A,B,C,Z)是一個長度為26的線性表，其中每個字母字符就是一個數(shù)據(jù)元素；線性表中元素的個數(shù)n(n>0)定義為線性表的長度，當(dāng)n=0時，稱為空表。線性表的長度是可以變的，當(dāng)向線性表中插入一個元素時，線性表的長度加1;當(dāng)刪除線性表中的一個元素時，線性表的長度減1。線性表的順序存儲結(jié)構(gòu)通常，線性表可以采用順序存儲和鏈?zhǔn)酱鎯?，本小?jié)主要討論順序存儲結(jié)構(gòu)。線性表的順序存儲指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。線性表的順序存儲結(jié)構(gòu)具備如下兩個基本特征:(1)線性表中的所有元素所占的存儲空間是連續(xù)的；(2)線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。用順序存儲結(jié)構(gòu)存儲的線性表稱為順序表。在順序表中，其前、后件兩個元素在存儲空間中是緊鄰的，且前件元素一定存儲在后件元素的前面。如長度為n的線性表(a1，a2, an)的順序存儲如圖1-6所示?！瑼DR(0|)1a\ADR(atHK26…ia,ADR(%E加1內(nèi)n4…數(shù)據(jù)兀素在線存儲地址性我中的序，內(nèi)存狀態(tài)空間分配占*個字W占K個字節(jié)占K個字節(jié)占K個字節(jié)圖16線性&的順序存儲結(jié)構(gòu)示意圖在順序表中，如果每個元素占有K個存儲單元，則下標(biāo)為i+1的元素的存儲位置與下標(biāo)為i的元素的存儲位置之間，滿足下列關(guān)系：ADR(ai+1)=ADR(a。+K通常把順序表中第1個數(shù)據(jù)元素的存儲地址ADR(a])稱為線性表的首地址，線性表中第i個元素研的存儲地址為：ADR(a。=ADR(a。+(i-1)K例如，在順序表中存儲數(shù)據(jù)(14,23,25,78,15,68,27),每個數(shù)據(jù)元素占有2個存儲單元，第1個數(shù)據(jù)元素14的存儲地址是200,則第3個數(shù)據(jù)元素25的存儲地址是：ADR(a3)=ADR(a。+(3-1)x2=200+4=204從這種表示方法可以看到，它是用元素在計算機(jī)內(nèi)物理位置上的相鄰關(guān)系來表示元素之間邏輯上的相鄰關(guān)系。只要確定了首地址，線性表內(nèi)任意元素的地址都可以方便地計算出來。順序表的插入運(yùn)算順序表的插入運(yùn)算是指在表的第i(l<i<n+l)個位置上，插入一個新結(jié)點(diǎn)x,使長度為n的順序表(a1，…，3j-i，a”…，an)變成長度為n+1的順序表在第i個元素之前插入一個新元素，完成插入操作主要有以下3個步驟。(1)把原來第n個結(jié)點(diǎn)至第i個結(jié)點(diǎn)依次往后移一個元素位置。(2)把新結(jié)點(diǎn)放在第i個位置上。(3)修正線性表的結(jié)點(diǎn)個數(shù)。例如，圖l-4(a)表示一個存儲空間為10,長度為7的順序表。為了在順序表的第6個元素(即56)之前插入一個值為27的數(shù)據(jù)元素,則需將第6個和第7個數(shù)據(jù)元素依次往后移動一個位置，空出第6個元素的位置，如圖l-4(a)中箭頭所示，然后將新元素27插入到第6個位置。插入一個新元素后，順序表的長度增加1,薇8,嫡l-4(b)所示。一般情況下，在第i(lWWn)個元素之前插入一個元素時，需將第i個元素之后(包括第i個元素)的所有元素向后移動一個位置。再例如，在圖l-4(b)的順序表的第2個元素之前，再插入一個值為35的新元素，采用同樣的步驟：將第2個元素之后的元素(包括第2個元素)，即第2個元素至第8個元素，共n-i+l=8-2+l=7個元素向后移動一個位置，然后將新元素插入到第2個位置，如圖l-4(b)

變成9,如圖1-7?變成9,如圖1-7?所序號數(shù)據(jù)元素(b)插入元素27后線性表”8線性表的*序存儲結(jié)構(gòu)插入前后的狀況序號數(shù)據(jù)元素(b)插入元素27后線性表”8線性表的*序存儲結(jié)構(gòu)插入前后的狀況序，數(shù)據(jù)兀素(c)插入元素3S后線性衣不=9圖|-7順序表的插入運(yùn)算，其時間主要花費(fèi)在結(jié)點(diǎn)的移動上，所需移動結(jié)點(diǎn)的次數(shù)不僅與表的長度有關(guān)，而且與插入的位置有關(guān)。順序表的刪除運(yùn)算線性表的刪除運(yùn)算是指將表的第i(l<i<n)個結(jié)點(diǎn)刪除，使長度為n的線性表：(a1,…'Sj.i，apaj+i，???,an)變成長度為n-1的線性表9???9 9a1+l，???9該算法的時間分析與插入算法相似，結(jié)點(diǎn)的移動次數(shù)也是由表長n和位置i決定。若1中，則由于循環(huán)變量的初值大于終值，前移語句將不執(zhí)行，無需移動結(jié)點(diǎn)；若i=l,則前移語句將循環(huán)執(zhí)行n-1次,需移動表中除開始結(jié)點(diǎn)外的所有結(jié)點(diǎn)。這兩種情況下算法的時間復(fù)雜度分別為0(1)和O(n)o順序表的刪除運(yùn)算是指將表的第i(l<i<n)個結(jié)點(diǎn)刪除，使長度為n的順序表：變成長度為n-1的順序表(31，...?8j.i，3j+i，…，3n)刪除時應(yīng)將第i+1個元素至第n個元素依次向前移一個元素位置,共移動了n-i個元素，完成刪除主要有以下幾個步驟。(1)把第i個元素之后(不包含第i個元素)的n-i個元素依次前移一個位置。(2)修正順序表的結(jié)點(diǎn)個數(shù)。例如，圖l-8(a)為一個長度為8的順序表，將第一個元素45刪除的過程如下：從第2個元素35開始直到最后一個元素56,將其中的每一個元素均依次往前移動一個位置，如圖L8(a)中箭頭所示。此時，順序表的長度減少了1,變成了7,如圖l-8(b)所示。一般情況下，要刪除第i(l<i<n)個元素時，則要從第i+1個元素開始，直到第n個元素之間共n-i個元素依次向前移動一個位置。刪除結(jié)束后，順序表的長度減少1。倘若再要刪除圖l-8(b)中順序表的第3個元素82,則采用同樣的步驟：從第4個元素開始至最后一個元素56,將其中的每一個元素均依次往前移動一個位置，如圖l-8(b)中箭頭所示。此時，順序表的長度減少了1,變成了6,如圖1-8?所示。(a)刪除前線性表〃=8(b)(a)刪除前線性表〃=8(b)刪除兀素45后線性表尸7(0制除元素82后線性表《=6圖18線性衣的順序存儲結(jié)構(gòu)刪除前后的狀況顯然，如果刪除運(yùn)算在順序表的末尾進(jìn)行，即刪除第n個元素，則不需要移動順序表中的元素。如果要刪除第1個元素，則需要移動表中所有的元素。在一般情況下，如果刪除第i(14。)個元素，則原來第i個元素之后的所有元素都必須依次往前移動一個位置。1.4棧和隊列棧和隊列都是一種特殊的線性表，它們都有自己的特點(diǎn)，棧是"先進(jìn)后出"的線性表，而隊列是“先進(jìn)先出”的線性表。棧及其基本運(yùn)算.棧的定義棧(Stack)是一種特殊的線性表，它所有的插入與刪除都限定在表的同一端進(jìn)行。在棧中，一端是封閉的，既不允許進(jìn)行插入元素，也不允許刪除元素；另一端是開口的，允許插入和刪除元素。

例如，槍械的子彈匣就可以用來形象地表示棧結(jié)構(gòu)。如圖l-9(a)所示，子彈匣的一端是完全封閉的，最后被壓入彈匣的子彈總是最先被彈出，而最先被壓入的子彈最后才能被彈出。在棧中，允許插入與刪除的一端稱為棧頂，不允許插入與刪除的另一端稱為棧底。當(dāng)棧中沒有元素時，稱為空棧。例如，沒有子彈的子彈匣為空棧。通常用指針top來指示棧頂?shù)奈恢茫弥羔榖ottom來指向棧底。假設(shè)棧S=(3i，a2,...?an),則稱a1為棧底元素，an為棧頂元素。棧中元素按a］，a?,…，an的次序進(jìn)棧，退棧的第一個元素應(yīng)為棧頂元素an。圖l-9(b)是棧的入棧、退棧示意圖。(a)用「彈匣表示校(a)用「彈匣表示校圖19棧結(jié)構(gòu).棧的特點(diǎn)根據(jù)棧的上述定義，棧具有以下特點(diǎn)。校的特點(diǎn)■底元素總是最早破插入的元素，也是量晚才能被刪除的元素’在順序存儲結(jié)構(gòu)芭找的插入9■底元素總是最早破插入的元素，也是量晚才能被刪除的元素’在順序存儲結(jié)構(gòu)芭找的插入9副除運(yùn)算都不需要移動表中其他數(shù)據(jù)元素枚頂指針top動態(tài)反映了板中［元素的變化情況,口、枚頂元素總站最后'械插入的元素,也是J早祓■除的元素J棧的修改原則是‘后進(jìn)先出"(LastInFirstOut,LIFO)或"先進(jìn)后出"(FirstInLastOut,FILO),因此，棧也稱為"后進(jìn)先出"表或"先進(jìn)后出"表。.棧的基本運(yùn)算

棧的基本運(yùn)算包括入棧、退棧和讀棧定元素。（1）入棧運(yùn)算入棧運(yùn)算是指在棧頂位置插入一個新元素。首先將棧頂指針加1（即top加1）,然后將新元素插入到棧頂指針指向的位置。當(dāng)棧頂指針已經(jīng)指向存儲空間的最后一個位置時，說明?？臻g已滿，不可能再進(jìn)行入棧操作。這種情況稱為棧"上溢"錯誤。（2）退棧運(yùn)算退棧是指取出棧頂元素并賦給一個指定的變量。首先將棧頂元素（棧頂指針指向的元素）賦給一個指定的變量，然后將棧頂指針減1（即top減1）。當(dāng)棧頂指針為。時，說明?？?，不可進(jìn)行退棧操作。這種情況稱為棧的"下溢"錯誤。（3）讀棧頂元素讀棧頂元素是指將棧頂元素賦給一個指定的變量。這個運(yùn)算不刪除棧頂元素，只是將它賦給一個變量，因此棧頂指針不會改變。當(dāng)棧頂指針為。時，說明棧空，讀不到棧頂元素。圖1-10所示是一個順序表示的棧的動態(tài)示意圖。隨著元素的插入和刪除，棧頂指針top反應(yīng)了棧的狀態(tài)不斷地變化。⑻空棧（b）插入元素A⑻空棧（b）插入元素A后（c）插入兀索B、C、D、E、F后（d）刪除元素E、F后圖I10棧的動態(tài)示意圖1.4.2隊列及其基本運(yùn)算.4.2.1隊列的定義及運(yùn)算隊列也是一種特殊的線性表。隊列是指允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。允許進(jìn)行刪除運(yùn)算的一端稱為隊頭(或排頭)，允許進(jìn)行插入運(yùn)算的一端稱為隊尾。若有隊列：Q=(q2，...?qn)那么，q1為隊頭元素(排頭元素)，q0為隊尾元素。隊列中的元素是按照心，q2,…，qn的順序進(jìn)入的，退出隊列也只能按照這個次序依次退出，也就是說，只有在q1，q2,qC都退隊之后，qn才能退出隊列。因最先進(jìn)入隊列的元素將最先出隊，所以隊列具有"先進(jìn)先出"的特性，體現(xiàn)“先來先服務(wù)"的原則。隊頭元素5是最先被插入的元素，也是最先被刪除的元素。隊尾元素qn是最后被插入的元素，也是最后被刪除的元素。因此，與棧相反,隊列又稱為"先進(jìn)先出"(FirstInFirstOut,FIFO)或"后進(jìn)后出"(LastInLastOut,LILO)的線性表。例如，火車進(jìn)隧道，最先進(jìn)隧道的是火車頭，最后進(jìn)的是火車尾，而火車出隧道的時候也是火車頭先出，火車尾后出?？梢杂庙樞虼鎯Φ木€性表來表示隊列，為了指示當(dāng)前執(zhí)行退隊運(yùn)算的隊頭位置，需要一個隊頭指針(排頭指針)front,為了指示當(dāng)前執(zhí)行入隊運(yùn)算的隊尾位置，需要一個隊尾指針rear。排頭指針fr。尸總是指向隊頭元素的前一個位置，而隊尾指針rear總是指向隊尾元素。往隊列的隊尾插入一個元素稱為入隊運(yùn)算，從隊列的排頭刪除一個元素稱為退隊運(yùn)算。4.2.2循環(huán)隊列及其運(yùn)算在實(shí)際應(yīng)用中，隊列的順序存儲結(jié)構(gòu)一般采用循環(huán)隊列的形式。所謂循環(huán)隊列，就是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間。在循環(huán)隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置。因此，從排頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間所有的元素均為隊列中的元素。一維數(shù)組(l：m),最大存儲空間為m,數(shù)組(l:m)作為循環(huán)隊列的存儲空間時，循環(huán)隊列的初始狀態(tài)為空，即front=rear=m,圖1-13所示是循環(huán)隊列初始狀態(tài)的示意圖。循環(huán)隊列的初始狀態(tài)為空，BPfront=rear=moL1 2… …mII「??1I「??11frontrear圖卜13循環(huán)隊列初始狀態(tài)示意圖循環(huán)隊列主要有兩種基本運(yùn)算：入隊運(yùn)算和退隊運(yùn)算。(1)入隊運(yùn)算入隊運(yùn)算是指在循環(huán)隊列的隊尾加入一個新元素。首先將隊尾指針進(jìn)1(即rear=rear+l),并當(dāng)rear=m+l時置rear=l；然后將新元素插入到隊尾指針指向的位置。例如，在圖l-14(a)中進(jìn)行入隊運(yùn)算，首先隊尾指針進(jìn)1,此時rear=m+l,置rear=l,則在第1個位置上插入數(shù)據(jù)a,見圖l-14(b)；當(dāng)插入第2個數(shù)據(jù)b時，隊尾指針進(jìn)1,rear=2,在第2個位置上插入數(shù)據(jù)b,依此類推，直到把所有的數(shù)據(jù)元素插入完成，見圖1-14?所示。(2)退隊運(yùn)算退隊運(yùn)算是指在循環(huán)隊列的隊頭位置退出一個元素并賦給指定的變量。首先將隊頭指針進(jìn)1(BPfront=front+l),并當(dāng)front=m+l時，置fronts；然后將排頭指針指向的元素賦給指定的變量。例如，在圖1-14?中進(jìn)行退隊運(yùn)算時,排頭指針進(jìn)1(即front+1),此時front=m+l,置front=l,刪除此位置的數(shù)據(jù)，即數(shù)據(jù)a。rear frontabed-rear frontabed-e~~IfI卜、c、d、e、1入隊~~~~~~底 后的循環(huán)隊列TTrearfront1 2 3 4 5 6IIb|c|d|e|f|9)a退隊后的循環(huán)隊列f tfront rear圖174循環(huán)隊列動態(tài)示意圖從圖l-14(a)和圖1-14?可以看出，循環(huán)隊列在隊列滿時，和隊列空時都有front=rear,如何區(qū)分循環(huán)隊列是空還是滿的呢？在實(shí)際應(yīng)用中，通常增加一個標(biāo)志量S,S值的定義如下：循環(huán)隊列為空時S=0循環(huán)隊列為非空時S=1由此可以判斷隊列空和隊列滿這兩種情況。當(dāng)s=o時，循環(huán)隊列為空，此時不能再進(jìn)行退隊運(yùn)算，否則會發(fā)生"下溢"錯誤。當(dāng)S=1時，并且front=rear時，循環(huán)隊列滿。此時不能再進(jìn)行入隊運(yùn)算，否則會發(fā)生"上溢”錯誤。在定義了S以后，循環(huán)隊列初始狀態(tài)為空，表示為：s=o,且front=rear=mo1.5線性鏈表線性表的順序存儲結(jié)構(gòu)具有簡單、操作方便等優(yōu)點(diǎn)。但在對其做插入或刪除操作時，需要移動大量的元素。因此，對于大的線性表，特別是元素變動頻繁的大線性表不宜采用順序存儲結(jié)構(gòu)，而是通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。線性單鏈表的結(jié)構(gòu)線性鏈表的基本概念在鏈?zhǔn)酱鎯Y(jié)構(gòu)中。存儲數(shù)據(jù)結(jié)構(gòu)的存儲空間可以不連續(xù)，各數(shù)據(jù)結(jié)點(diǎn)的存儲順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致，而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來確定的。鏈?zhǔn)酱鎯Ψ绞郊瓤捎糜诒硎揪€性結(jié)構(gòu)，也可以表示非線性結(jié)構(gòu)。線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性鏈表。由于這種鏈表中，每個結(jié)點(diǎn)只有一個指針域，故又稱為單鏈表。在鏈?zhǔn)酱鎯Ψ绞街?，要求每個結(jié)點(diǎn)由兩部分組成：一部分用于存放數(shù)據(jù)元素值，稱為數(shù)據(jù)域；另一部分用于存放指針，稱為指針域。其中指針用于指向該結(jié)點(diǎn)的前一個或后一個結(jié)點(diǎn)（即前件或后件）。如圖1-15所示。存儲序號 數(shù)據(jù)域指針域D(0NEXT(7)圖IT5線性鏈去的一個存儲結(jié)點(diǎn)線性單鏈表的存儲結(jié)構(gòu)用一組任意的存儲單元來依次存放線性表的結(jié)點(diǎn)，這組存儲單元既可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。因此，鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲每個結(jié)點(diǎn)值的同時，還必須存儲指示其后件結(jié)點(diǎn)的地址（或位置）信息，這個信息稱為指針（pointer）或鏈（link）。這兩部分組成了鏈表中的結(jié)點(diǎn)結(jié)構(gòu)，如圖1-16所示。圖1-16線性表的邏輯結(jié)構(gòu)顯然，單鏈表中每個結(jié)點(diǎn)的存儲地址是存放在其前驅(qū)結(jié)點(diǎn)Next域中，而開始結(jié)點(diǎn)無前驅(qū)，故應(yīng)設(shè)頭指針HEAD指向開始結(jié)點(diǎn)。同時，由于終端結(jié)點(diǎn)無后件，故終端結(jié)點(diǎn)的指針域為空，即NULL。帶鏈的棧與隊列（1）帶鏈的棧棧也是線性表，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。在實(shí)際應(yīng)用中，帶鏈的棧可以用來收集計算機(jī)存儲空間中所有空閑的存儲結(jié)點(diǎn)，這種帶鏈的棧稱為可利用棧，如圖1-19（a）所示。（2）帶鏈的隊列_隊列也是線性表，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，如圖1-19（b）所ZJSo圖IT9帶鏈的棧和帶跳的隊列線性鏈表的基本運(yùn)算對線性鏈表進(jìn)行的運(yùn)算主要包括查找、插入、刪除、合并、分解、逆轉(zhuǎn)、復(fù)制和排序。在線性鏈表中查找指定元素查找指定元素所處的位置是插入和刪除等操作的前提，只有先通過查找定位才能進(jìn)行元素的插入和刪除等進(jìn)一步的運(yùn)算。在鏈表中查找指定元素必須從隊頭指針出發(fā)，沿著指針域Next逐個結(jié)點(diǎn)搜索，直到找到指定元素或鏈表尾部為止，而不能像順序表那樣，只要知道了首地址，就可以計算出任意元素的存儲地址。因此，線性鏈表不是隨機(jī)存儲結(jié)構(gòu)。在鏈表中，如果有指定元素，則掃描到等于該元素值的結(jié)點(diǎn)時,停止掃描，返回該結(jié)點(diǎn)的位置，因此，如果鏈表中有多個等于指定元素值的結(jié)點(diǎn)，只返回第一個結(jié)點(diǎn)的位置。如果鏈表中沒有元素的值等于指定元素，則掃描完所有元素后，返回NULL。線性鏈表的插入線性鏈表的插入是指在鏈?zhǔn)酱鎯Y(jié)構(gòu)下的線性鏈表中插入一個新兀素O插入運(yùn)算是將值為X的新結(jié)點(diǎn)插入到表的第i個結(jié)點(diǎn)的位置上，即插入到a〉i與aj之間。因此，我們必須首先找到ar】的存儲位置p,然后生成一個數(shù)據(jù)域為x的新結(jié)點(diǎn)*p,并令結(jié)點(diǎn)*p的指針域指向新結(jié)點(diǎn)，新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)ai。如圖1-15所示。圖1-15 線性表的插入示意圖1.5.23線性鏈表的刪除線性鏈表的刪除是指在鏈?zhǔn)酱鎯Y(jié)構(gòu)下的線性鏈表中刪除包含指定元素的結(jié)點(diǎn)。刪除運(yùn)算是將表的第i個結(jié)點(diǎn)刪去。因為在單鏈表中結(jié)點(diǎn)砒的存儲地址是在其直接前趨結(jié)點(diǎn)4的指針域Next中，所以我們必須首先找到a｝】的存儲位置p。然后令p->Next指向ai的直接后件結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間。如圖1-16所示。圖1-16線性表的刪除示意圖1.5.3線性雙向鏈表的結(jié)構(gòu)及其基本運(yùn)算什么是雙向鏈表在單鏈表中，從某個結(jié)點(diǎn)出發(fā)可以直接找到它的直接后件，時間復(fù)雜度為O(D,但無法直接找到它的直接前件；在單循環(huán)鏈表中，從某個結(jié)點(diǎn)出發(fā)可以直接找到它的直接后件，時間復(fù)雜度仍為0(1),直接找到它的直接前件，時間復(fù)雜度為o(n)o有時，希望能快速找到一個結(jié)點(diǎn)的直接前件，這時，可以在單鏈表中的結(jié)點(diǎn)中增加一個指針域指向它的直接前件，這樣的鏈表，就稱為雙向鏈表(一個結(jié)點(diǎn)中含有兩個指針)。如果每條鏈構(gòu)成一個循環(huán)鏈表，則會得到雙向循環(huán)鏈表，如圖1-17所示。HEAD ———? —?-4a -二~0圖1-17 雙向鏈表示意圖雙向鏈表的基本運(yùn)算(1)插入在HEAD為頭指針的雙向鏈表中，在值為丫的結(jié)點(diǎn)之后插入值為X的結(jié)點(diǎn)，插入結(jié)點(diǎn)的指針變化，如圖1-18所示(若改為在值為丫的結(jié)點(diǎn)之前插入值為X的結(jié)點(diǎn)，可以做類似分析)。圖1-18 雙向鏈表的插入(2)刪除在以HEAD為頭指針的雙向鏈表中刪除值為X的結(jié)點(diǎn)，刪除算法的指針變化，如圖1-19所示。圖1-19 雙向鏈表的刪除1.5.4循環(huán)鏈表的結(jié)構(gòu)及其基本運(yùn)算從單鏈表可知，最后一個結(jié)點(diǎn)的指針域為NULL,表示單鏈表已經(jīng)結(jié)束。如果將單鏈表最后一個結(jié)點(diǎn)的指針域改為存放鏈表中頭結(jié)點(diǎn)（或第一個結(jié)點(diǎn)）的地址，就使得整個鏈表構(gòu)成一個環(huán)，又沒有增加額外的存儲空間，如圖1-20所示。這樣的鏈表稱為循環(huán)鏈表。⑻非空循環(huán)鏈表

心,戛^!—I?⑹空柢表圖1-20 循環(huán)鏈表的邏輯結(jié)構(gòu)對單鏈表的訪問是一種順序訪問，從其中某一個結(jié)點(diǎn)出發(fā)，只能找到它的直接后繼（即后件），但無法找到它的直接前驅(qū)（即前件），而且對于空表和第一個結(jié)點(diǎn)的處理必須單獨(dú)考慮，空表與非空表的操作不統(tǒng)一。在循環(huán)鏈表中，只要指出表中任何一個結(jié)點(diǎn)的位置，就可以從它出發(fā)訪問到表中其他所有的結(jié)點(diǎn)。并且，由于表頭結(jié)點(diǎn)是循環(huán)鏈表所固有的結(jié)點(diǎn)，因此，即使在表中沒有數(shù)據(jù)元素的情況下，表中也至少有一個結(jié)點(diǎn)存在，從而使空表和非空表的運(yùn)算統(tǒng)一。1.6樹與二叉樹樹的定義樹(Tree)是一種簡單的非線性結(jié)構(gòu)，直觀地來看，樹是以分支關(guān)系定義的層次結(jié)構(gòu)。由于它呈現(xiàn)與自然界的樹類似的結(jié)構(gòu)形式，所以稱它為樹。樹結(jié)構(gòu)在客觀世界中是大量存在的。例如，一個家族中的族譜關(guān)系：A有后代B,C；B有后代D,E,F;C有后代G；E有后代H,Io則這個家族的成員及血統(tǒng)關(guān)系可用圖1-24這樣一棵倒置的樹來描述。圖「24樹的示例在樹的圖形表示中，一般認(rèn)為在用直線連起來的兩端結(jié)點(diǎn)中，上端結(jié)點(diǎn)是前件，下端結(jié)點(diǎn)是后件。這樣，表示前后件關(guān)系的箭頭就可以省略。下面結(jié)合圖1-24介紹樹的相關(guān)術(shù)語。在樹結(jié)構(gòu)中，每一個結(jié)點(diǎn)只有一個前件，稱為父結(jié)點(diǎn)；沒有前件的結(jié)點(diǎn)只有一個，稱為樹的根結(jié)點(diǎn)，簡稱樹的根。例如，在圖1-24中，結(jié)點(diǎn)A是樹的根結(jié)點(diǎn)。在樹結(jié)構(gòu)中，每一個結(jié)點(diǎn)可以有多個后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)；沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。例如，在圖1-24中，結(jié)點(diǎn)D、H、I、F、G均為葉子結(jié)點(diǎn)。在樹結(jié)構(gòu)中，一個結(jié)點(diǎn)所擁有的后件個數(shù)稱為該結(jié)點(diǎn)的度，所有結(jié)點(diǎn)中最大的度稱為樹的度。例如，在圖1-24中，根結(jié)點(diǎn)說結(jié)點(diǎn)E的度為2,結(jié)點(diǎn)B的度為3,結(jié)點(diǎn)C的度為1,葉子結(jié)點(diǎn)D、H、I、F、G的度為0。所以，該樹的度為3。定義一棵樹的根結(jié)點(diǎn)所在的層次為1,其他結(jié)點(diǎn)所在的層次等于它的父結(jié)點(diǎn)所在的層次加1。樹的最大層次稱為樹的深度。例如，在圖1-24中，根結(jié)點(diǎn)A在第1層，結(jié)點(diǎn)B、C在第2層，結(jié)點(diǎn)D、E、F、G在第3層，結(jié)點(diǎn)H、I在第4層。該樹的深度為4。在樹中，以某結(jié)點(diǎn)的一個子結(jié)點(diǎn)為根構(gòu)成的樹稱為該結(jié)點(diǎn)的一棵子樹。例如，在圖1-24中，結(jié)點(diǎn)A有2棵子樹，它們分別以B、C為根結(jié)點(diǎn)；結(jié)點(diǎn)B有3棵子樹，它們分別以D、E、F為根結(jié)點(diǎn)，其中,以D、F為根結(jié)點(diǎn)的子樹實(shí)際上只有根結(jié)點(diǎn)一個結(jié)點(diǎn)。樹的葉子結(jié)點(diǎn)度為0,所以沒有子樹。二叉樹的定義及其基本性質(zhì)二叉樹的定義二叉樹是由n（n>0）個結(jié)點(diǎn)的有限集合構(gòu)成，此集合或者為空集，或者由一個根結(jié)點(diǎn)及兩棵互不相交的左右子樹組成，并且左右子樹都是二叉樹。二叉樹可以是空集合，根可以有空的左子樹或空的右子樹。二叉樹不是樹的特殊情況，它們是兩個概念。二叉樹具有以下兩個特點(diǎn)：（1）非空二叉樹只有一個根結(jié)點(diǎn)；（2）每一個結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。二叉樹的每個結(jié)點(diǎn)最多有兩個孩子，或者說，在二叉樹中，不存在度大于2的結(jié)點(diǎn)，并且二叉樹是有序樹（樹為無序樹），其子色的順序不能顛倒，因此，二叉樹有5種不同的形態(tài)，如圖1-26所ZJSo圖126二叉樹的5種基本形態(tài)圖l-26(a)表示空二叉樹；圖l-26(b)是僅有根結(jié)點(diǎn)的二叉樹，即左子樹和右子樹都為空二叉樹；圖l-26(c)是左、右子樹均非空的二叉樹；圖l-26(d)是左子樹非空，右子樹為空的 二叉樹；圖116(e)是右子樹非空，左子樹為空的二叉樹。在二叉樹中，當(dāng)一個非根結(jié)點(diǎn)的結(jié)點(diǎn)，既沒有右子樹，也沒有左子樹時，該結(jié)點(diǎn)即是葉子結(jié)點(diǎn)。二叉樹的基本性質(zhì)二叉樹具有以下幾個性質(zhì)：性質(zhì)1:在二叉樹的第k層上至多有2門(心1)個結(jié)點(diǎn)。性質(zhì)2：深度為m的二叉樹至多有2巾-1個結(jié)點(diǎn)。深度為m的二叉樹表示該二叉樹共有m層。根據(jù)性質(zhì)1,只要將第1層到第m層上的最大的結(jié)點(diǎn)數(shù)相加，就可以得到整個二叉樹中結(jié)點(diǎn)數(shù)的最大值，及2皿+22、...+2m』=2m-l。性質(zhì)3：對任何一棵二叉樹，度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個。證明：設(shè)一棵非空二叉樹中有n個結(jié)點(diǎn)，葉子結(jié)點(diǎn)個數(shù)為n。，度為1的結(jié)點(diǎn)個數(shù)為nl,度為2的結(jié)點(diǎn)個數(shù)為明。所以：n=n()+ni+n2(1)在二叉樹中，除根結(jié)點(diǎn)外，其余每個結(jié)點(diǎn)都有且僅有一個前件(直接前驅(qū))和一條從其前件結(jié)點(diǎn)指向它的邊。假設(shè)邊的總數(shù)為B,則二叉樹中總的結(jié)點(diǎn)數(shù)為：n=B+l由于二叉樹中的邊都是由度為1和度為2的結(jié)點(diǎn)發(fā)出的。所以有:B=ni+n2x2綜合(1)、(2)、(3)式，可得：n0=n2+l性質(zhì)4：具有n個結(jié)點(diǎn)的完全二叉樹的深度至少為［logzn］+1,其中［logzn］表示log2n的整數(shù)部分。1.6.23滿二叉樹與完全二叉樹滿二叉樹和完全二叉樹是兩種特殊形態(tài)的二叉樹。(1)滿二叉樹滿二叉樹是指除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個子結(jié)點(diǎn)。即在滿二叉樹的第k層上有個結(jié)點(diǎn)。從上面滿二叉樹定義可知，必須是二叉樹每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大，否則就不是滿二叉樹。深度為m的滿二叉樹有2m“個結(jié)點(diǎn)。圖1-23是兩棵滿二叉樹。圖l-23(a)是深度為3的滿二叉樹，圖l-23(b)是深度為4的滿二叉樹。在滿二叉樹中，只有度為2和度為0的結(jié)點(diǎn)，沒有度為1的結(jié)點(diǎn)。所有度為。的結(jié)點(diǎn)即葉子結(jié)點(diǎn)都在同一層，即最后一層。(2)完全二叉樹完全二叉樹是指除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。完全二叉樹也可以這樣來描述：如果對滿二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號，從根結(jié)點(diǎn)開始，對二叉樹的結(jié)點(diǎn)自上而下，自左至右用自然數(shù)進(jìn)行連續(xù)編號，則深度為K的，有n個結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為K的滿二叉樹中編號從1到n的結(jié)點(diǎn)一一對應(yīng)時，稱之完全二叉樹。由完全二叉樹可知，滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。圖l-28(a)是深度為3的3棵完全二叉樹，圖l-28(b)是深度為4的一棵完全二叉樹。圖I28完全.又樹完全二叉樹還具有以下兩個性質(zhì)：性質(zhì)1：具有n個結(jié)點(diǎn)的完全二叉樹深度為[logzn]+lo性質(zhì)2：如果對一棵有n個結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號（從第1層到第[log2n]+1層，每層從左到右），則對任一結(jié)點(diǎn)k（l<k<n）,有：①如果k=l,則結(jié)點(diǎn)k父結(jié)點(diǎn)，是二叉樹的根；如果k>l,則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號為INT（k/2）；②如果2kE,則結(jié)點(diǎn)k的左子結(jié)點(diǎn)編號為2k；否則該結(jié)點(diǎn)沒有左子結(jié)點(diǎn)（顯然也沒有右子結(jié)點(diǎn)）；③如果2k+l",則結(jié)點(diǎn)k的右子結(jié)點(diǎn)編號為2k+l；否則該結(jié)點(diǎn)沒有右子結(jié)點(diǎn)。1.6.2.4二叉樹的存儲結(jié)構(gòu)在計算機(jī)中，二叉樹通常采用鏈?zhǔn)酱鎯Y(jié)構(gòu)。用于存儲二叉樹中各元素的存儲結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)域與指針域。但在二叉樹中，由于每一個元素可以有兩個后件（兩個子結(jié)點(diǎn)），因此，用于存儲二叉樹的存儲結(jié)點(diǎn)的指針域有兩個：一個用于指向該結(jié)點(diǎn)的左子結(jié)點(diǎn)的存儲地址，稱為左指針域；另一個用于指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲地址，稱為右指針域。如圖1-29所示。左指針域 數(shù)據(jù)域右指針域U0Data(7)R(i)圖1-29 :叉樹的一個存儲結(jié)點(diǎn)由于二叉樹的存儲結(jié)構(gòu)中每一個存儲結(jié)點(diǎn)有兩個指針域，因此,二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)也稱為二叉鏈表。1.6.3二叉樹的遍歷二叉樹的遍歷是指不重復(fù)地訪問二叉樹中的所有結(jié)點(diǎn)。在遍歷二叉樹的過程中，一般先遍歷左子樹，再遍歷右子樹。在先左后右的原則下，根據(jù)訪問根結(jié)點(diǎn)的次序不同，二叉樹的遍歷可以分為3種：前序遍歷、中序遍歷、后序遍歷。.前序遍歷前序遍歷中“前”的含義是：訪問根結(jié)點(diǎn)在訪問左子樹和訪問右子樹之前。即首先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹;并且在遍歷左子樹和右子樹時，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。前序遍歷可以描述為：若二叉樹為空，則執(zhí)行空操作；否則①訪問根結(jié)點(diǎn)，②前序遍歷左子樹，③前序遍歷右子樹。例如，對圖1-30中的二叉樹進(jìn)行前序遍歷的結(jié)果（或稱為該二叉樹的前序序列）為：A,B,D,H,E,I,C,F,Go圖130?棵.義樹.中序遍歷中序遍歷中“中”的含義是：訪問根結(jié)點(diǎn)在訪問左子樹和訪問右子樹兩者之間。即首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。并且在遍歷左子樹和右子樹時，仍然首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。中序遍歷可以描述為：若二叉樹為空，則執(zhí)行空操作；否則①中序遍歷左子樹，②訪問根結(jié)點(diǎn)，③中序遍歷右子樹。例如，對圖1-30中的二叉樹進(jìn)行中序遍歷的結(jié)果（或稱為該二叉樹的中序序列）為：H,D,B,E,I,A,C,G,Fo.后序遍歷后序遍歷中“后”的含義是：訪問根結(jié)點(diǎn)在訪問左子樹和訪問右子樹之后。即首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn);并且在遍歷左子樹和右子樹時，仍然首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)。后序遍歷可以描述為：若二叉樹為空，則執(zhí)行空操作；否則①后序遍歷左子樹，②后序遍歷右子樹，③訪問根結(jié)點(diǎn)。例如，對圖1-30中的二叉樹進(jìn)行后序遍歷的結(jié)果（或稱為該二叉樹的后序序列）為：H,D,I,E,B,G,F,C,Ao查找技術(shù)查找就是在某種數(shù)據(jù)結(jié)構(gòu)中，找出滿足指定條件的元素。查找是插入和刪除等運(yùn)算的基礎(chǔ)，是數(shù)據(jù)處理的重要內(nèi)容。由于數(shù)據(jù)結(jié)構(gòu)是算法的基礎(chǔ)，因此，對于不同的數(shù)據(jù)結(jié)構(gòu)，應(yīng)選用不同的查找算法,以獲得更高的查找效率。順序查找與二分法查找順序查找順序查找（順序搜索）是最簡單的查找方法，它的基本思想是:從線性表的第一個元素開始，逐個將線性表中的元素與被查元素進(jìn)行比較，如果相等，則查找成功，停止查找；若整個線性表掃描完畢，仍未找到與被查元素相等的元素，則表示線性表中沒有要查找的元素，查找失敗。在進(jìn)行順序查找過程中，如果線性表中的第一個元素就是要查找的元素，則比較次數(shù)為1;如果最后一個元素才是要找的元素，或者在線性表中，沒有要查找的元素，則需要與線性表中所有的元素比較，這是順序查找的最壞情況。在平均情況下，利用順序查找法在線性表中查找一個元素，大約要與線性表中一半的元素進(jìn)行比較。由此可以看出，對于大的線性表來說，順序查找的效率很低。雖然順序查找的效率不高，但在下列兩種情況下也只能采用順序查找：（1）如果線性表是無序表（即表中的元素是無序的），則不管是順序存儲結(jié)構(gòu)還是鏈?zhǔn)酱鎯Y(jié)構(gòu)，都只能用順序查找。（2）即使是有序線性表，如果采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，也只能用順序查找。二分法查找二分法查找也稱拆半查找，是一種高效的查找方法。能使用二分法查找的線性表必須滿足兩個條件：?用順序存儲結(jié)構(gòu)；?線性表是有序表。在本書中，為了簡化問題，而更方便討論，"有序"是特指元素按非遞減排列，即從小到大排列，但允許相鄰元素相等。下一節(jié)排序中，有序的含義也是如此。對于長度為n的有序線性表，利用二分法查找元素X的過程如下。將X與線性表的中間項比較：?如果X的值與中間項的值相等，則查找成功，結(jié)束查找；?如果X小于中間項的值，則在線性表的前半部分以二分法繼續(xù)查找；?如果X大于中間項的值，則在線性表的后半部分以二分法繼續(xù)查找。例如，長度為8的線性表關(guān)鍵碼序列為：［5,12,26,29,37,45,46,69］,被查元素為37,首先將與線性表的中間項比較，即與第4個數(shù)據(jù)元素29相比較,37大于中間項29的值,則在線性表［37,45,46,69］繼續(xù)查找；接著與中間項比較，即與第2個元素45相比較，37小于45,則在線性表［37］繼續(xù)查找，最后一次比較相等,查找成功。順序查找法每一次比較，只將查找范圍減少1,而二分法查找，每比較一次，可將查找范圍減少為原來的一半，效率大大提高。可以證明，對于長度為n的有序線性表，在最壞情況下，二分法查找只需比較logzn次，而順序查找需要比較n次。排序技術(shù)排序是數(shù)據(jù)處理的重要內(nèi)容0所謂排序是指將一個無序序列整理成按值非遞減順序排列的有序序列。排序的方法有很多，根據(jù)待排序序列的規(guī)模以及對數(shù)據(jù)處理的要求，可以采用不同的排序方法。交換類排序法交換類排序法是借助數(shù)據(jù)元素的“交換”來進(jìn)行排序的一種方法。本小節(jié)介紹冒泡排序法和快速排序法，它們都使用交換排序方法。冒泡排序法冒泡排序法是最簡單的一種交換類排序方法。在數(shù)據(jù)元素的序列中，對于某個元素，如果其后存在一個元素小于它，則稱之為存在一個逆序。冒泡排序（BubbleSort）的基本思想就是通過兩兩相鄰數(shù)據(jù)元素之間的比較和交換，不斷地消去逆序，直到所有數(shù)據(jù)元素有序為止。冒泡排序法的基本過程如下：第一遍，在線性表中，從前往后掃描，如果相鄰的兩個數(shù)據(jù)元素，前面的元素大于后面的元素，則將它們交換，并稱為消去了一個逆序。在掃描過程中，線性表中最大的元素不斷的往后移動，最后，被交換到了表的末端。此時，該元素就已經(jīng)排好序了。然后對當(dāng)前還未排好序的范圍內(nèi)的全部結(jié)點(diǎn)，從后往前掃描，如果相鄰兩個數(shù)據(jù)元素，后面的元素小于前面的元素，則將它們交換，也稱為消去了一個逆序。在掃描過程中，最小的元素不斷地往前移動，最后，被換到了線性表的第一個位置，則認(rèn)為該元素已經(jīng)排好序了。對還未排好序的范圍內(nèi)的全部結(jié)點(diǎn)，繼續(xù)第二遍，第三遍的掃描，這樣，未排好序的范圍逐漸減小，最后為空，則線性表已經(jīng)變?yōu)橛行蛄?。圖1-31是一個冒泡排序法的例子。原始序列4<—fl6+-?5+32<-—?3第一遍（從前往后）[14<-f5+f23]6（從后往前）1[245<-+3]6第：遍（從前往后）1[24<—-*3]56（從后往前）12[34]56最終結(jié)果123456圖1-31冒泡排序示例在最壞情況下，對長度為n的線性表排序，冒泡排序需要比較的次數(shù)為n（n-1）/2O快速排序法在冒泡排序中，一次掃描只能確保最大的元素或最小的元素移到了正確位置，而未排序序列的長度可能只減少了1。快速排序（QuickSort）是對冒泡排序方法的一種本質(zhì)的改進(jìn)?？焖倥判虻幕舅枷胧牵涸诖判虻膎個元素中取一個元素K（通常取第一個元素），以元素K作為分割標(biāo)準(zhǔn)，把所有小于K元素的數(shù)據(jù)元素都移到K前面，把所有大于K元素的數(shù)據(jù)元素都移到K后面。這樣，以K為分界線，把線性表分割為兩個子表，這稱為一趟排序。然后，對K前后的兩個子表分別重復(fù)上述過程。繼續(xù)下去，直到分割的子表的長度為1為止，這時，線性表已經(jīng)是排好序的了。第一趟快速排序的具體做法是：附設(shè)兩個指針low和hi曲，它們的初值分別指向線性表的第一個元素（K元素）和最后一個元素。首先從high所指的位置向前掃描，找到第一個小于K元素的元素并與K元素互相交換。然后從low所指位置起向后掃描，找到第一個大于K元素的數(shù)據(jù)元素并與K元素交換。重復(fù)這兩步，直到low=high為止。圖1-32是一個快速排序法的例子o初始狀態(tài)回306! 8274 122649t tlow highhigh向左掃描畫3061 8274 1226 49第?次交換后263061 8274 12囤49t tlow highlow向右孑I描263061 8274 12圖49第?次交換后2630回8274 12 61 49high向左打描并交換后2630 128274圓61 49low向右掃描并交換后2630 12囤748261 49ikAlowhighhigh向左打描26 3012圓748261 49(a)第一趟掃描過程初始狀態(tài)網(wǎng)30618274122649第一陋排序后(263045[74|826149]第.楞排序后破6)26【時45[49|61)74網(wǎng)第一:超排序后1226304549啊17482排序結(jié)果1226304549617482(b)在垣排序之后的狀態(tài)圖I32快速持序示例快速排序的平均時間效率最佳，為o(nlog2n),最壞情況下,即每次劃分，只得到一個子序列，時間效率為O(n2)o1.8.2選擇類排序法選擇排序的基本思想是通過每一趟從待排序序列中選出值最小的元素，順序放在已排好序的有序子表的后面，直到全部序列滿足排序要求為止。簡單選擇排序法簡單選擇排序(SimpleSelectionSort)的基本思想是：首先從所有n個待排序的數(shù)據(jù)元素中選擇最小的元素，將該元素與第1個元素交換，再從剩下的n-1個元素中選出最小的元素與第2個元素交換。重復(fù)這樣的操作直到所有的元素有序為止。對初始狀態(tài)為(73,26,41,5,12,34)的序列進(jìn)行簡單選擇排序過程如圖1-33所示。圖中方括號”［內(nèi)為有序的子表，方括號”［］”外為無序的子表，每次從無序子表中取出最小的一個元素加入到有序子表的末尾。步驟如下：從這6個元素中選擇最小的元素5,將5與第1個元素交換，得到有序序列［5］；從剩下的5個元素中挑出最小的元素12,將12與第2個元素交換,得到有序列［5,12］；從剩下的4個元素中挑出最小的元素26,將26與第3個元素交換,得到有序序列［5,12,26］;依此類推，直到所以的元素都有序地排列到有序的子表中。［初始］[48]37659675122649/=2[3748]659675122649i=3[374865]9675122649[37486596]75122649/=5[3748657596]122649/=6[123748657596]2649/=7[12263748657596149/=8[1226374849657596]圖1-33簡單插入排序過程簡單選擇排序法在最壞的情況下需要比較n(n-1)/2次。堆排序法堆排序?qū)儆谶x擇類的排序方法。(1)堆的定義若有n個元素的序列(h】，h2,hn),將元素按順序組成一棵完全二叉樹，當(dāng)且僅當(dāng)滿足下列條件時稱為堆。,兒w%濁聲％(1). 或(2)其中，i=l,2,3,...,n/2o(1)情況稱為小根堆，所有結(jié)點(diǎn)的值小于或等于左右子結(jié)點(diǎn)的值。(2)情況稱為大根堆，所有結(jié)點(diǎn)的值大于或等于左右子結(jié)點(diǎn)的值。本節(jié)只討論大根堆的情況。例如，序列(91,85,53,36,47,30,24,12)是一個堆，則它對應(yīng)的完全二叉樹如圖1-36所示。圖I36堆頂元素為用大的推(2)調(diào)整建堆在調(diào)整建堆的過程中，總是將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)進(jìn)行比較，若不滿足堆的條件，則將左、右子樹根結(jié)點(diǎn)值中的大者與根結(jié)點(diǎn)值進(jìn)行交換，這個調(diào)整過程從根節(jié)點(diǎn)開始一直延伸到所有葉子結(jié)點(diǎn)，直到所有子樹均為堆為止。(3)堆排序首先將一個無序序列建成堆，然后將堆頂元素與堆中的最后一個元素交換。不考慮已經(jīng)換到最后的那個元素，將剩下的n-1個元素重新調(diào)整為堆，重復(fù)執(zhí)行此操作，直到所有元素有序為止。對于數(shù)據(jù)元素較少的線性表來說，堆排序的優(yōu)越性并不明顯，但對于大量的數(shù)據(jù)元素來說，堆排序是很有效的。在最壞情況下，堆排序法需要比較的次數(shù)為O(nlogzn)o1.8.3插入類排序法插入排序是每次將一個待排序元素，按其元素值的大小插入到前面已經(jīng)排好序的子表中的適當(dāng)位置，直到全部元素插入完成為止。簡單插入排序法簡單插入排序是把n個待排序的元素看成是一個有序表和一個無序表，開始時，有序表只包含一個元素，而無序表包含另外n-1個元素，每次取無序表中的第一個元素插入到有序表中的正確位置，使之成為增加一個元素的新的有序表。插入元素時，插入位置及其后的記錄依次向后移動。最后有序表的長度為n,而無序表為空，此時排序完成。簡單插入排序過程如圖1-33所示。圖中方括號"[]"內(nèi)為有序的子表，方括號"[]"外為無序的子表，每次從無序子表中取出第一個元素插入到有序子表中。[初始][48]37659675122649r=2[3748]659675122649[374865]9675122649r=4[37486596]75122649/=5[3748657596)122649r=6[123748657596]2649i=l[12263748657596]49r=8[1226374849657596]圖133簡單插入排序過程在最好情況下，即初始排序序列就是有序的情況下，簡單插入排序的比較次數(shù)為n-1次，移動次數(shù)為0次。在最壞情況下，即初始排序序列是逆序的情況下，比較次數(shù)為n(n-1)/2,移動次數(shù)為n(n-1)/2O假設(shè)待排序的線性表中的各種排列出現(xiàn)的概率相同，可以證明，其平均比較次數(shù)和平均移動次數(shù)都約為//%因此直接插入排序算法的時間復(fù)雜度為O(n2)o在簡單插入排序中，每一次比較后最多移掉一個逆序，因此,這種排序方法的效率與冒泡排序法相同。希爾排序法希爾排序(ShellSort)又稱為“縮小增量排序“，它也是一種插入類排序的方法，但在時間效率上較簡單插入排序有較大的改進(jìn)。希爾排序的基本思想是：先取一個整數(shù)(稱為增量)djVn,把全部數(shù)據(jù)元素分成由個組，所有距離為由倍數(shù)的元素放在一組中，組成了一個子序列，對每個子序列分別進(jìn)行簡單插入排序。然后取dzVd]重復(fù)上述分組和排序工作；直到5=1,即所有記錄在一組中為止。一方面，簡單插入排序在線性表初始狀態(tài)基本有序時，排序時間較少。另一方面，當(dāng)n值較小時，n和n差別也較小。希爾排序開始時增量較大，分組較多，每組的數(shù)據(jù)元素數(shù)目較少，故在各組內(nèi)采用簡單插入排序較快，后來增量d逐漸縮小，分組數(shù)減少，各組的記錄數(shù)增多，但由于已經(jīng)按注1分組排序，線性表比較接近有序狀態(tài)，所以新的一趟排序過程也較快?？捎懈鞣N不同的取法，例如，一般取力=”2,5+1=4/2。希爾排序的時間效率與所取的增量序列有關(guān)，如果增量序列為：山=”2,di+]=d/2(n為等待排序序列的元素個數(shù))。則在最壞情況下，希爾排序所需要的比較次數(shù)為0(n”)。圖1-34為希爾排序過程。初始狀態(tài)#5第?初始狀態(tài)#5第?趟柞序結(jié)果d=248376496751326505451326505454837649675第二趟排序結(jié)果第三趟排序結(jié)果第四趟排序結(jié)果TOC\o"1-5"\h\z13 5 48 37 26 50 54 64 96 7513 5 26 37 48 50 54 64 96 755 13 26 37 48 50 54 64 75 96圖1-34希爾排序過程各種排序方法時間復(fù)雜度、空間復(fù)雜度對比見表1-2。表1-2各種排序方法時間、空間復(fù)雜度對比排序方法時間復(fù)雜度空間復(fù)雜度品雜性平均情況最壞情況最好情況直接插入排序0(I*2)(KiC)0(n)0(1)筒冷宵泡排序0(n1)0(m)0(1)荷年希爾挎序O(n\o^n)0(1)收星條快速排序0(nlog,n)a/)0(nlog2n)O(nl<f:n)較復(fù)雜鹵接近界排序0(nJ)a”')0(iis)0(1)同單堆排序0(nlog.n)0(nlog.n)0(nl?g3n)0(1)較復(fù)雜第2章程序設(shè)計基礎(chǔ)程序設(shè)計方法與風(fēng)格程序設(shè)計經(jīng)歷的階段程序是計算機(jī)的一組指令，是程序設(shè)計的最終結(jié)果。程序的功能要經(jīng)過編譯和執(zhí)行才能最終完成。程序設(shè)計是指設(shè)計、編制、調(diào)試程序的方法和過程。與其他方法一樣，程序設(shè)計也需要一定的方法來指導(dǎo)。需要注意的是，程序設(shè)計并不等同于通常意義上的編程。程序設(shè)計有多個步驟組成，編程只是程序設(shè)計整個過程中的一小步。程序設(shè)計方法所要做的工作是，如何對實(shí)際問題進(jìn)行抽象和分解以及對程序進(jìn)行組織，才能使程序的可讀性、穩(wěn)定性、可維護(hù)性、效率等更好。程序設(shè)計主要經(jīng)歷了結(jié)構(gòu)化設(shè)計和面向?qū)ο蟮某绦蛟O(shè)計階段。良好的編程風(fēng)格應(yīng)注意的因素程序設(shè)計風(fēng)格是指編寫程序時所表現(xiàn)出來的特點(diǎn)、習(xí)慣和邏輯思路。良好的程序設(shè)計風(fēng)格可以使程序結(jié)構(gòu)清晰合理，程序代碼便于維護(hù)，因此，程序設(shè)計風(fēng)格深深地影響著軟件的質(zhì)量和維護(hù)。要形成良好的程序設(shè)計風(fēng)格，主要應(yīng)注意和考慮下述一些因素。(1)源程序的文檔化源程序文檔化是指在源程序中可包含一些內(nèi)部文檔，以幫助閱讀和理解源程序。①符號名的命名規(guī)則：符號名的命名應(yīng)具有一定的實(shí)際含義，以便理解程序功能。②程序注釋：在源程序中添加正確的注釋可幫助人們理解程序。程序注釋可分為序言性注釋和功能性注釋，以給出程序的整體說明和程序的主要功能。③視覺組織：可以在程序中利用空格、空行、縮進(jìn)等技巧使程序?qū)哟吻逦?2)數(shù)據(jù)說明的方法為使程序中的數(shù)據(jù)說明易于理解和維護(hù)，可采用下列數(shù)據(jù)說明的風(fēng)格，見表2-1。表2-1表2-1數(shù)據(jù)說明風(fēng)格詳細(xì)說明次序應(yīng)規(guī)范化使數(shù)據(jù)說明次序固定，使數(shù)據(jù)的屬性容易查找，也有利于測試、排錯和維護(hù)變量安排有序化當(dāng)多個變量出現(xiàn)在同一個說明語句中時，變量名應(yīng)按字母順序排序，以便于查找使用注釋在定義一個復(fù)雜的數(shù)據(jù)結(jié)構(gòu)時，應(yīng)通過注釋來說明該數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)(3)語句的結(jié)構(gòu)為使程序更簡單易懂，語句構(gòu)造應(yīng)該簡單直接，應(yīng)注意如下原則：①在一行內(nèi)只寫一條語句；②程序編寫應(yīng)優(yōu)先考慮清晰性；③程序編寫要做到清晰第一，效率第二；④在保證程序正確的基礎(chǔ)上再要求提高效率；⑤避免使用臨時變量而使程序的可讀性下降；⑥避免不必要的轉(zhuǎn)移；⑦盡量使用庫函數(shù)；⑧避免采用復(fù)雜的條件語句；⑨盡量減少使用“否定"條件語句；⑩數(shù)據(jù)結(jié)構(gòu)要有利于程序的簡化；⑩要模塊化，使模塊功能盡可能單一化；⑩利用信息隱蔽，確保每一個模塊的獨(dú)立性；⑩從數(shù)據(jù)出發(fā)去構(gòu)造程序；⑩不要修補(bǔ)不好的程序，要重新編寫。(4)輸入輸出輸入輸出方式和風(fēng)格應(yīng)盡可能方便用戶的使用，應(yīng)考慮如下原則：（1）對所有輸入的數(shù)據(jù)都要檢驗數(shù)據(jù)的合法性；（2）檢查輸入項的各種重要組合的合理性；（3）輸入格式要簡單，使得輸入的步驟和操作盡可能簡單；（4）輸入數(shù)據(jù)時，應(yīng)允許使用自由格式；（5）應(yīng)允許默認(rèn)值；（6）輸入一批數(shù)據(jù)時，最好使用輸入結(jié)束標(biāo)志；（7）在以交互式輸入/輸出方式進(jìn)行輸入時，要在屏幕上使用提示符明確提示輸入的請求，同時在數(shù)據(jù)輸入過程中和輸入結(jié)束時，應(yīng)在屏幕上給出狀態(tài)信息；（8）當(dāng)程序設(shè)計語言對輸入格式有嚴(yán)格要求時，應(yīng)保持輸入格式與輸入語句的一致性。結(jié)構(gòu)化程序設(shè)計由于軟件危機(jī)的出現(xiàn)，人們開始研究程序設(shè)計方法，其中最受關(guān)注的是結(jié)構(gòu)化程序設(shè)計方法，它引入了工程思想和結(jié)構(gòu)化思想，使大型軟件的開發(fā)和編制都得到了極大的改善。結(jié)構(gòu)化程序設(shè)計的原則結(jié)構(gòu)化程序設(shè)計方法的重要原則是自頂向下、逐步求精、模塊化及限制使用got。語句。（1）自頂向下程序設(shè)計時，先考慮總體，后考慮細(xì)節(jié)；先考慮全局目標(biāo)，后考慮局部目標(biāo)。（2）逐步求精對復(fù)雜問題，應(yīng)設(shè)計一些子目標(biāo)做過渡，逐步細(xì)化。(3)模塊化模塊化是把程序要解決的總目標(biāo)分解為分目標(biāo)，再進(jìn)一步分解為具體的小目標(biāo)，把每個小目標(biāo)稱為一個模塊。(4)限制使用goto語句結(jié)構(gòu)化程序的基本結(jié)構(gòu)與特點(diǎn)1966年，Boehm和Jacopini證明了程序設(shè)計語言僅僅使用順序、選擇和重復(fù)三種基本控制結(jié)構(gòu)就足以表達(dá)出各種其他形式結(jié)構(gòu)的程序設(shè)計方法。它們的共同特征是：嚴(yán)格地只有一個入口和一個出口。(1)順序結(jié)構(gòu)順序結(jié)構(gòu)是指按照程序語句行的先后順序，自始至終一條語句一條語句地順序執(zhí)行，它是最簡單也是最常用的基本結(jié)構(gòu)。如圖2-1所示，虛線框內(nèi)就是一個順序結(jié)構(gòu)，在執(zhí)行A中的運(yùn)算后，必然執(zhí)行B中的運(yùn)算，然后執(zhí)行C中的運(yùn)算，沒有分支，也沒有轉(zhuǎn)移和重復(fù)。(2)選擇結(jié)構(gòu)選擇結(jié)構(gòu)又稱分支結(jié)構(gòu)，簡單選擇結(jié)構(gòu)和多分支選擇結(jié)構(gòu)都屬于這類基本結(jié)構(gòu)，這種結(jié)構(gòu)可以根據(jù)設(shè)置的條件，判斷應(yīng)該選擇哪一枝分支來執(zhí)行相應(yīng)的語句序列。圖2-2虛線框內(nèi)是一個簡單選擇結(jié)構(gòu)。根據(jù)條件C判斷，若成立則執(zhí)行A中的運(yùn)算，若不成立則執(zhí)行B中的運(yùn)算。圖2圖2I理序結(jié)構(gòu)圖22簡單選擇結(jié)構(gòu)(3)重復(fù)結(jié)構(gòu)重復(fù)結(jié)構(gòu)又稱為循環(huán)結(jié)構(gòu)，它根據(jù)給定的條件，判斷是否需要重復(fù)執(zhí)行某一相同的或類似的程序段。在程序設(shè)計語言中，重復(fù)結(jié)構(gòu)對應(yīng)兩類循環(huán)語句，對先判斷后執(zhí)行的循環(huán)體稱為當(dāng)型循環(huán)結(jié)構(gòu)；對先執(zhí)行循環(huán)體后判斷的稱為直到型循環(huán)結(jié)構(gòu)，如圖2-4所示。總之，遵循結(jié)構(gòu)化程序的設(shè)計原則，按結(jié)構(gòu)化程序設(shè)計方法設(shè)計出的程序具有明顯的優(yōu)點(diǎn)：?程序易于理解、使用和維護(hù)；?提高了編程工作的效率，降低了軟件開發(fā)成本。2.2.3結(jié)構(gòu)化程序設(shè)計原則和方法的應(yīng)用基于對結(jié)構(gòu)化程序設(shè)計原則、方法以及結(jié)構(gòu)化程序基本構(gòu)成結(jié)構(gòu)的掌握和了解，在結(jié)構(gòu)化程序設(shè)計的具體實(shí)施中，要注意把握如下要素：①使用程序設(shè)計語言中的順序、選擇、循環(huán)等有限的控制結(jié)構(gòu)表示程序的控制邏輯；②選用的控制結(jié)構(gòu)只準(zhǔn)許有一個入口和一個出口；③程序語句組成容易識別的塊，每塊只有一個入口和一個出口；④復(fù)雜結(jié)構(gòu)應(yīng)該用嵌套的基本控制結(jié)構(gòu)進(jìn)行組合嵌套來實(shí)現(xiàn)；⑤語言中所沒有的控制結(jié)構(gòu)，應(yīng)該采用前后一致的方法來模擬；⑥盡量避免GOTO語句的使用。23面向?qū)ο蟮某绦蛟O(shè)計現(xiàn)在，面向?qū)ο蠓椒ㄒ呀?jīng)發(fā)展為主流的軟件開發(fā)方法。它歷經(jīng)了30多年的研究和發(fā)展，已經(jīng)日益成熟和完善，應(yīng)用也越來越深入和廣泛。面向?qū)ο蟮姆椒陀^世界中任何一個事物都可以被看成是一個對象，面向?qū)ο蠓椒ǖ谋举|(zhì)就是主張從客觀世界固有的事物出發(fā)來構(gòu)造系統(tǒng)，提倡用人類在現(xiàn)實(shí)生活中常用的思維方法來認(rèn)識、理解和描述客觀事物，強(qiáng)調(diào)最終建立的系統(tǒng)能夠映射問題域，也就是說，系統(tǒng)中的對象以及對象之間的關(guān)系能夠如實(shí)地反映問題域中固有事物及其關(guān)系。從計算機(jī)的角度來看，一個對象應(yīng)該包括兩個要素：一是數(shù)據(jù);二是需要進(jìn)行的操作。對象就是一個包含數(shù)據(jù)以及與這些數(shù)據(jù)有關(guān)的操作的集合。面向?qū)ο缶褪沁\(yùn)用對象、類、繼承、封裝、消息、結(jié)構(gòu)與連接等面向?qū)ο蟮母拍顚栴}進(jìn)行分析、求解的系統(tǒng)開發(fā)技術(shù)。面向?qū)ο笥腥缦轮饕獌?yōu)點(diǎn)：①與人類習(xí)慣的思維方法一致。②穩(wěn)定性好。③可重用性好。④易于開發(fā)大型軟件產(chǎn)品。⑤可維護(hù)性好。面向?qū)ο蠓椒ǖ幕靖拍铌P(guān)于面向?qū)ο蠓椒?，對其概念有許多不同的看法和定義，但是都涵蓋對象及對象屬性與方法、類、繼承、多態(tài)性幾個基本要素。2.3.2.1對象對象是面向?qū)ο蠓椒ㄖ凶罨镜母拍?。對象可以用來表示客觀世界中的任何實(shí)體，也就是說，應(yīng)用領(lǐng)域中有意義的、與所要解決的問題有關(guān)系的任何事物都可以作為對象。總之，對象是對問題域中某個實(shí)體的抽象。例如，書本、課桌、老師、電腦等都可以看做一個對象。面向?qū)ο蟮某绦蛟O(shè)計方法中涉及的對象是系統(tǒng)中用來描述客觀事物的一個實(shí)體，是構(gòu)成系統(tǒng)的一個基本單位，它由一組表示其靜態(tài)特征的屬性和它可執(zhí)行的一組操作組成?？陀^世界中的實(shí)體通常既具有靜態(tài)的屬性，又具有動態(tài)的行為，因此，面向?qū)ο蠓椒▽W(xué)中的對象是由描述該對象屬性的數(shù)據(jù)以及可以對這些數(shù)據(jù)施加的操作封裝在一起構(gòu)成的統(tǒng)一體。對象可以執(zhí)行的操作表示它的動態(tài)行為。屬性即對象所包含的信息，它在設(shè)計對象時確定，一般只能通過執(zhí)行對象的操作來改變。操作描述了對象執(zhí)行的功能，若通過信息的傳遞，還可以為其他對象使用。對象具有如下特點(diǎn)：①標(biāo)識唯一性：指對象是可區(qū)分的，并且由對象的內(nèi)在本質(zhì)來區(qū)分，而不是通過描述來區(qū)分；②分類性：指可以將具有相同屬性和操作的對象抽象成類；③多態(tài)性：指同一個操作可以是不同對象的行為；③封裝性：從外面看只能看到對象的外部特征，而不知道也無需知道數(shù)據(jù)的具體結(jié)構(gòu)以及實(shí)現(xiàn)操作的算法；⑤模塊獨(dú)立性好：對象是面向?qū)ο蟮能浖幕灸K，對象內(nèi)部各種元素彼此結(jié)合得很緊密，內(nèi)聚性強(qiáng)。2.322類和實(shí)例類是具有共同屬性、共同方法的對象的集合，是關(guān)于對象的抽象描述，反映屬于該對象類型的所有對象的性質(zhì)。一個具體對象則是其對應(yīng)類的一個實(shí)例。要注意的是："實(shí)例”這個術(shù)語，必然是指一個具體的對象。"對象"這個術(shù)語，則既可以指一個具體的對象，也可以泛指一般的對象。因此，在使用“實(shí)例”這個術(shù)語的地方，都可以用"對象”來代替,而使用"對象'這個術(shù)語的地方，則不一定能用"實(shí)例"來代替。例如，“大學(xué)生”是一個大學(xué)生類，它描述了所有大學(xué)生的性質(zhì)。因此，任何大學(xué)生都是類“大學(xué)生”的一個對象（這里的"對象"不可以用"實(shí)例"來代替），而一個具體的大學(xué)生"張三"是類"大學(xué)生"的一個實(shí)例。類是關(guān)于對象性質(zhì)的描述，它同對象一樣，包括一組數(shù)據(jù)屬性和在數(shù)據(jù)上的一組合法操作。2.3.23消息消息傳遞是對象間通信的手段，一個對象通過向另一對象發(fā)送消息來請求其服務(wù)。消息機(jī)制統(tǒng)一了數(shù)據(jù)流和控制流。消息的使用類似于函數(shù)調(diào)用。通常一個消息由下述3部分組成：?接收消息的對象名稱；?消息選擇符（也稱為消息名）；?零個或多個參數(shù)。消息只告訴接收對象需要完成什么操作，但并不指示怎樣完成操作。消息完全由接收者解釋，獨(dú)立決定采用什么方法來完成所需的操作。一個對象能夠接收不同形式、不同內(nèi)容的多個消息；相同形式的消息可以送往不同的對象，不同的對象對于形式相同的消息可以有不同的解釋，能夠作出不同的反應(yīng)。一個對象可以同時往多個對象傳遞消息，兩個對象也可以同時向某一個對象傳遞消息。消息傳遞如圖2-4所示。23.2.4繼承繼承是面向?qū)ο蟮囊粋€主要特征。繼承是使用已有的類定義作為基礎(chǔ)建立新類的技術(shù)。已有的類可當(dāng)作基類來應(yīng)用，則新類相應(yīng)地可當(dāng)作派生類來引用。廣義地說，繼承是指能夠直接獲得已有的性質(zhì)和特征，而不必重復(fù)定義它們。例如，"四邊形"類是"矩形”類的父類，”四邊形“類可以有"頂點(diǎn)坐標(biāo)"等屬性，有"移動"、"旋轉(zhuǎn)"、"求周長"等操作。而"矩形“類除了繼承”四邊形”類的屬性和操作外，還可定義自己的屬性和操作，"長"、"寬”等屬性和“求面積”等操作。繼承具有傳遞性，如果類Z繼承類Y,類丫繼承類X,貝揆Z繼承類Xo因此，一個類實(shí)際上繼承了它上層的全部基類的特性，也就是說，屬于某類的對象除了具有該類定義的特性外，還具有該類上層全部基類定義的特性。繼承分為單繼承與多重繼承。單繼承是指一個類只允許有一個父類，即類等價為樹型結(jié)構(gòu)。多重繼承是指一個類允許有多個父類。多重繼承的類可以組合多個父類的性質(zhì)構(gòu)成所需要的性質(zhì)。繼承的優(yōu)點(diǎn)是：相似的對象可以共享程序代碼和數(shù)據(jù)結(jié)構(gòu)，從而大大減少了程序中的冗余信息，提高軟件的可重用性，便于軟件修改維護(hù)。另外，繼承性使得用戶在開發(fā)新的應(yīng)用系統(tǒng)時不必完全從零開始，可以繼承原有的相似系統(tǒng)的功能或者從類庫中選取需要的類，再派生出新的類以實(shí)現(xiàn)所需的功能。2.325多態(tài)性對象根據(jù)所接收的消息而做出動作，同樣的消息被不同的對象接收時可導(dǎo)致完全不同的行為，該現(xiàn)象稱為多態(tài)性。在面向?qū)ο蟮能浖夹g(shù)中，多態(tài)性是指子類對象可以像父類對