第1章緒論

目前，計(jì)算機(jī)已深入到社會(huì)生活的各個(gè)領(lǐng)域，其應(yīng)用已不再僅僅局限于科學(xué)計(jì)算，而更多的是用于控制，管理及數(shù)據(jù)處理等非數(shù)值計(jì)算領(lǐng)域。計(jì)算機(jī)是一門研究用計(jì)算機(jī)進(jìn)行信息表示和處理的科學(xué)。這里面涉及到兩個(gè)問題：信息的表示，信息的處理。信息的表示和組織又直接關(guān)系到處理信息的程序的效率。

隨著應(yīng)用問題的不斷復(fù)雜，導(dǎo)致信息量劇增與信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，必須分析待處理問題中的對(duì)象的特征及各對(duì)象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問題。1.1數(shù)據(jù)結(jié)構(gòu)的基本概念1.1.1基本概念和術(shù)語(yǔ)1．?dāng)?shù)據(jù)數(shù)據(jù)是信息的載體，是描述客觀事物屬性的數(shù)、字符及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)集合。數(shù)據(jù)是計(jì)算機(jī)程序加工的原料。2．?dāng)?shù)據(jù)元素?cái)?shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)元素也叫做結(jié)點(diǎn)或記錄。在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。有時(shí)，一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成，例如，一本書的書目信息為一個(gè)數(shù)據(jù)元素，而書目信息的每一項(xiàng)（如書名、作者名等）為一個(gè)數(shù)據(jù)項(xiàng)。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。3．?dāng)?shù)據(jù)對(duì)象

數(shù)據(jù)對(duì)象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。4．?dāng)?shù)據(jù)類型數(shù)據(jù)類型是一個(gè)值的集合和定義在此集合上的一組操作的總稱。1）原子類型。其值不可再分的數(shù)據(jù)類型。

2）結(jié)構(gòu)類型。其值可以再分解為若干成分（分量）的數(shù)據(jù)類型。

3）抽象數(shù)據(jù)類型。抽象數(shù)據(jù)組織及與之相關(guān)的操作。5．?dāng)?shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合。在任何問題中，數(shù)據(jù)元素都不是孤立存在的，它們之間存在某種關(guān)系，這種數(shù)據(jù)元素相互之間的關(guān)系稱為結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)包括三方面的內(nèi)容：邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)是密不可分的兩個(gè)方面，一個(gè)算法的設(shè)計(jì)取決于選定的邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于所采用的存儲(chǔ)結(jié)構(gòu)。1.1.2數(shù)據(jù)結(jié)構(gòu)三要素1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)，其中的邏輯關(guān)系是指數(shù)據(jù)元素之間的前后間關(guān)系，而與他們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān)。邏輯結(jié)構(gòu)分類如下：集合：數(shù)據(jù)結(jié)構(gòu)中的元素之間除了“同屬一個(gè)集合”的相互關(guān)系外，別無(wú)其他關(guān)系。線性結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)一的相互關(guān)系。

樹形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)多的相互關(guān)系。圖形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在多對(duì)多的相互關(guān)系。2．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（又稱映像），也稱物理結(jié)構(gòu)。它包括數(shù)據(jù)元素的機(jī)內(nèi)表示和關(guān)系的機(jī)內(nèi)表示。常用的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和哈希存儲(chǔ)等。

1）順序存儲(chǔ)。把邏輯上相鄰的的元素存儲(chǔ)在物理位置上也相鄰的存儲(chǔ)單元中，元素之間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。其優(yōu)點(diǎn)是可以實(shí)現(xiàn)隨機(jī)存取，每個(gè)元素占用最少的存儲(chǔ)空間；缺點(diǎn)是只能使用相鄰的一整塊存儲(chǔ)單元，因此可能產(chǎn)生較多的外部碎片。

2）鏈?zhǔn)酱鎯?chǔ)。不是求邏輯上相鄰的元素在物理位置上也相鄰，借助指示元素存儲(chǔ)地址的指針來(lái)表示元素之間的邏輯關(guān)系。其優(yōu)點(diǎn)是不會(huì)出現(xiàn)碎片現(xiàn)象，能充分利用所有存儲(chǔ)單元；缺點(diǎn)是每個(gè)元素因存儲(chǔ)指針而占用額外的存儲(chǔ)空間，且只能實(shí)現(xiàn)順序存取。

3）索引存儲(chǔ)。在存儲(chǔ)元素信息的同時(shí)，還建立附加的索引表。索引表中的每項(xiàng)稱為索引項(xiàng)，索引項(xiàng)的一般形式是（關(guān)鍵字，地址）。其優(yōu)點(diǎn)是檢索速度快；缺點(diǎn)是附加的索引表額外占用存儲(chǔ)空間。另外，增加和刪除數(shù)據(jù)時(shí)也要修改索引表，因而會(huì)花費(fèi)較多的時(shí)間。

4）散列存儲(chǔ)。根據(jù)元素的關(guān)鍵字直接計(jì)算出該元素的存儲(chǔ)地址，又稱哈希存儲(chǔ)。其優(yōu)點(diǎn)是檢索、增加和刪除結(jié)點(diǎn)的操作都很快；缺點(diǎn)是若散列函數(shù)不好，則可能出現(xiàn)元素存儲(chǔ)單元的沖突，而解決沖突會(huì)增加時(shí)間和空間開銷。3．?dāng)?shù)據(jù)的運(yùn)算數(shù)據(jù)上的運(yùn)算包括運(yùn)算的定義和實(shí)現(xiàn)。運(yùn)算的定義是針對(duì)邏輯結(jié)構(gòu)的，指出運(yùn)算的功能；而運(yùn)算的實(shí)現(xiàn)是針對(duì)存儲(chǔ)結(jié)構(gòu)的，指出運(yùn)算的具體操作步驟。1.2算法1.2.1算法的基本概念算法（Algorithm）是指解題方案的準(zhǔn)確而完整的描述，它是指令的有限序列，其中的每條指令表示一個(gè)或多個(gè)操作。算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制。一個(gè)算法具有下列5個(gè)重要特性：1）有窮性（Finiteness）。算法的有窮性是指算法必須能在執(zhí)行有限個(gè)步驟之后終止。2）確切性（Definiteness）。算法的每一步驟必須有確切的定義。3）輸入項(xiàng)（Input）。一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫運(yùn)算對(duì)象的初始情況，所謂0個(gè)輸入是指算法本身定出了初始條件。4）輸出項(xiàng)（Output）。一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。沒有輸出的算法是毫無(wú)意義的。5）可行性（Effectiveness）。算法中執(zhí)行的任何計(jì)算步驟都是可以被分解為基本的可執(zhí)行的操作步驟，即每個(gè)計(jì)算步驟都可以在有限時(shí)間內(nèi)完成（也稱之為有效性）。一般情況下，設(shè)計(jì)一個(gè)“好”的算法應(yīng)該考慮達(dá)到以下目標(biāo)：1）正確性。算法應(yīng)能夠正確地解決問題。2）可讀性。算法應(yīng)具有良好的可讀性，以幫助人們理解。3）健壯性。輸入非法數(shù)據(jù)時(shí)，算法應(yīng)能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫名其妙的輸出結(jié)果。4）時(shí)間復(fù)雜度。算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量，實(shí)現(xiàn)算法應(yīng)達(dá)到較低的時(shí)間復(fù)雜度。5）空間復(fù)雜度。算法的空間復(fù)雜度是指算法需要消耗的內(nèi)存空間，實(shí)現(xiàn)算法應(yīng)達(dá)到較低的空間復(fù)雜度。1.2.2算法效率的評(píng)定1．時(shí)間復(fù)雜度

算法的時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。一般來(lái)說，計(jì)算機(jī)算法是問題規(guī)模的函數(shù)，算法的時(shí)間復(fù)雜度也因此記做：T(n)=O(f(n))

式中，O的含義是T(n)的數(shù)量級(jí)，其嚴(yán)格的數(shù)學(xué)定義是：若T(n)和f(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù)，則存在正常數(shù)C和n0，使得當(dāng)n≥n0時(shí)，都滿足0≤T(n)≤Cf(n)。最壞時(shí)間復(fù)雜度是指在最壞情況下，算法的時(shí)間復(fù)雜度。平均時(shí)間復(fù)雜度是指所有可能輸入實(shí)例在等概率出現(xiàn)的情況下，算法的期望運(yùn)行時(shí)間。最好時(shí)間復(fù)雜度是指在最好情況下，算法的時(shí)間復(fù)雜度。

一般總是考慮在最壞情況下的時(shí)間復(fù)雜度，以保證算法的運(yùn)行時(shí)間不會(huì)比它更長(zhǎng)。2．空間復(fù)雜度算法的空間復(fù)雜度是指算法需要消耗的內(nèi)存空間。同時(shí)間復(fù)雜度相比，空間復(fù)雜度的分析要簡(jiǎn)單得多。小結(jié)（1）數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算三個(gè)要素。數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)分為順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和散列存儲(chǔ)。（2）集合中的數(shù)據(jù)元素是相互獨(dú)立的，在線性結(jié)構(gòu)中數(shù)據(jù)元素具有“一對(duì)一”的關(guān)系，在樹形結(jié)構(gòu)中數(shù)據(jù)元素具有“一對(duì)多”的關(guān)系，在圖形結(jié)構(gòu)中數(shù)據(jù)元素具有“多對(duì)多”的關(guān)系。（3）算法（Alg