數(shù)據(jù)結(jié)構(gòu)001講義課件

1、數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)(Data Structure) 數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)元素（Data Element）之間抽象化的相互關(guān)系（邏輯結(jié)構(gòu)）和這種關(guān)系在計(jì)算機(jī)中的存儲(chǔ)表示（物理結(jié)構(gòu)），并對這種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法。 數(shù)據(jù)結(jié)構(gòu)主要指邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。 1. 邏輯結(jié)構(gòu)： 數(shù)據(jù)之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。通常分為 4 類基本結(jié)構(gòu)： 集合 結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系。 線性結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。 樹型結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。 四類數(shù)據(jù)基本結(jié)構(gòu)的示意圖：(a)集合

2、結(jié)構(gòu) (b)線性結(jié)構(gòu) (c)樹型結(jié)構(gòu) (d)圖形結(jié)構(gòu) 由以上例子可見，描述這類非數(shù)值計(jì)算問題的數(shù)學(xué)模型和方法不再是數(shù)學(xué)方程，而是諸如線性表、樹和圖之類的數(shù)據(jù)結(jié)構(gòu)。 數(shù)據(jù)對象可以是有限的，也可以是無限的。 數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)類型，也不同于數(shù)據(jù)對象，它不僅要描述數(shù)據(jù)類型的數(shù)據(jù)對象，而且要描述數(shù)據(jù)對象各元素之間的相互關(guān)系。 2. 存儲(chǔ)結(jié)構(gòu)： 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。它包括數(shù)據(jù)元素的表示和關(guān)系的表示。 表1-1所示的表格數(shù)據(jù)在計(jì)算機(jī)中可以有多種存儲(chǔ)表示： 數(shù)據(jù)既可以存放在一塊連續(xù)的內(nèi)存單元中，通過元素在存儲(chǔ)器中的位置來表示它們之間的邏輯關(guān)系（順序）； 也可以隨機(jī)分布在內(nèi)存中的不

3、同位置，通過指針元素表示數(shù)據(jù)元素之間的邏輯關(guān)系（鏈?zhǔn)剑?。這兩種不同的表示方法對應(yīng)有四種不同的存儲(chǔ)結(jié)構(gòu)（亦稱方式）： 順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、索引存儲(chǔ)結(jié)構(gòu)和散列存儲(chǔ)結(jié)構(gòu)。 (1)順序存儲(chǔ)結(jié)構(gòu)是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)之間的邏輯關(guān)系由存儲(chǔ)單元位置的鄰接關(guān)系來體現(xiàn)。優(yōu)點(diǎn)：占用較少的存儲(chǔ)空間；缺點(diǎn)：由于只能使用相鄰的一整塊存儲(chǔ)單元，因此可能產(chǎn)生較多的碎片現(xiàn)象。順序存儲(chǔ)結(jié)構(gòu)通常借助程序語言中的數(shù)組來描述。 順序存儲(chǔ)結(jié)構(gòu)主要應(yīng)用于線性的數(shù)據(jù)結(jié)構(gòu)。 (2) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)將結(jié)點(diǎn)所占的存儲(chǔ)單元分為兩部分，一部分存放結(jié)點(diǎn)本身的信息，另一部分存放結(jié)點(diǎn)的后繼結(jié)點(diǎn)地址，結(jié)點(diǎn)間的邏輯關(guān)系由

4、附加的指針字段表示。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)常借助于程序語言的指針類型描述。 優(yōu)點(diǎn)：不會(huì)出現(xiàn)碎片現(xiàn)象，充分利用所有的存儲(chǔ)單元； 缺點(diǎn)：每個(gè)結(jié)點(diǎn)占用較多的存儲(chǔ)空間。 (3)索引存儲(chǔ)方式是用結(jié)點(diǎn)的索引號(hào)來確定結(jié)點(diǎn)的存儲(chǔ)地址。 在儲(chǔ)存結(jié)點(diǎn)信息的同時(shí)，要建立附加的索引表。 優(yōu)點(diǎn)：檢索速度快。 缺點(diǎn)：增加了附加的索引表，占用較多的存儲(chǔ)空間；在增加和刪除數(shù)據(jù)時(shí)需要修改索引表而花費(fèi)較多時(shí)間。 (4) 散列存儲(chǔ)方式是根據(jù)結(jié)點(diǎn)的關(guān)鍵字值直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。通過散列函數(shù)把結(jié)點(diǎn)間的邏輯關(guān)系對應(yīng)到不同的物理空間。 優(yōu)點(diǎn):檢索、增加和刪除結(jié)點(diǎn)的操作都很快； 缺點(diǎn):當(dāng)采用不好的散列函數(shù)時(shí)可能出現(xiàn)結(jié)點(diǎn)存儲(chǔ)單元的沖突，為解決沖

5、突需要附加時(shí)間和空間的開銷。 3數(shù)據(jù)的運(yùn)算數(shù)據(jù)運(yùn)算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，即施加于數(shù)據(jù)的操作。 例如對一張表的記錄進(jìn)行查找、增加、刪除、修改，這就是對數(shù)據(jù)的運(yùn)算。 4數(shù)據(jù)結(jié)構(gòu)三方面的關(guān)系 數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)及數(shù)據(jù)的運(yùn)算三方面構(gòu)成一個(gè)數(shù)據(jù)結(jié)構(gòu)的整體。存儲(chǔ)結(jié)構(gòu)是對數(shù)據(jù)項(xiàng)的存儲(chǔ)。同一邏輯結(jié)構(gòu)可用不同存儲(chǔ)結(jié)構(gòu)就對應(yīng)不同的存儲(chǔ)標(biāo)識(shí)。例如，線性表若采用順序存儲(chǔ)方式，稱為順序表；若采用鏈?zhǔn)酱鎯?chǔ)方式，稱為鏈表；若采用散列存儲(chǔ)方式，可稱為散列表。 2、算法的特點(diǎn) 算法是執(zhí)行特定計(jì)算的有窮過程。這個(gè)過程有5個(gè)特點(diǎn)： 1) 動(dòng)態(tài)有窮：當(dāng)執(zhí)行一個(gè)算法時(shí)，不論是何種情況，在經(jīng)過了有限步驟后，這個(gè)算法一定要終

6、止。 2) 確定性：算法中的每條指令都必須是清楚的，指令無二義性。 3) 輸入：具有0個(gè)或多個(gè)由外界提供的量(輸入)。 4) 輸出：產(chǎn)生1個(gè)或多個(gè)結(jié)果。 5) 可行性：每條指令都充分基本，即：序列中的每個(gè)操作都是可以簡單完成的，都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算的有限次來實(shí)現(xiàn)。 注意：算法和程序是有區(qū)別的，即程序未必能滿足動(dòng)態(tài)有窮。在本書中只討論滿足動(dòng)態(tài)有窮的程序，因此“算法”和“程序” 是通用的。 算法效率的度量 1時(shí)間復(fù)雜度（Time complexity） 一個(gè)算法的時(shí)間復(fù)雜度是指算法運(yùn)行從開始到結(jié)束所需要的時(shí)間。 通常是所處理問題規(guī)模的一個(gè)函數(shù)T(n) ，常采用數(shù)量級的形式表示。記作：

7、T(n)=O(f(n) 稱T(n)為算法的(漸近)時(shí)間復(fù)雜度。 2空間復(fù)雜度（Space complexity） 一個(gè)算法的空間復(fù)雜度是指算法運(yùn)行從開始到結(jié)束所需的存儲(chǔ)量。 算法的存儲(chǔ)量指的是算法執(zhí)行過程中所需的最大存儲(chǔ)空間。 算法執(zhí)行期間所需要的存儲(chǔ)量應(yīng)該包括以下三部分： (1) 輸入數(shù)據(jù)所占空間； (2) 程序本身所占空間； (3) 輔助變量所占空間。 類似于算法的時(shí)間復(fù)雜度，通常以算法的空間復(fù)雜度作為算法所需存儲(chǔ)空間的量度。定義：S(n)=O(g(n)稱S(n)為算法的空間復(fù)雜度。 人有了知識(shí)，就會(huì)具備各種分析能力，明辨是非的能力。所以我們要勤懇讀書，廣泛閱讀，古人說“書中自有黃金屋。”通過閱