數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)課件章節(jié)1

第1章緒論

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

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

數(shù)據(jù)對象是具有相同性質(zhì)的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。4．?dāng)?shù)據(jù)類型數(shù)據(jù)類型是一個值的集合和定義在此集合上的一組操作的總稱。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)、存儲結(jié)構(gòu)和數(shù)據(jù)的運算。數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)是密不可分的兩個方面，一個算法的設(shè)計取決于選定的邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴于所采用的存儲結(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)系，而與他們在計算機(jī)中的存儲位置無關(guān)。邏輯結(jié)構(gòu)分類如下：集合：數(shù)據(jù)結(jié)構(gòu)中的元素之間除了“同屬一個集合”的相互關(guān)系外，別無其他關(guān)系。線性結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對一的相互關(guān)系。

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

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

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

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

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

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

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

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