數(shù)據(jù)結(jié)構(gòu)單元數(shù)據(jù)結(jié)構(gòu)與算法PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1 數(shù)據(jù)結(jié)構(gòu)單元數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)單元數(shù)據(jù)結(jié)構(gòu)與算法 教學(xué)目標(biāo)教學(xué)目標(biāo) 【知識(shí)目標(biāo)知識(shí)目標(biāo)】 l 了解數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié) 構(gòu)的有關(guān)概念 l 掌握數(shù)據(jù)結(jié)構(gòu)包含的三個(gè)方面、邏輯結(jié)構(gòu)的分類、基 本邏輯結(jié)構(gòu)、順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)方法 l 掌握算法及算法的特性 l 理解和掌握算法分析的方法 【能力目標(biāo)能力目標(biāo)】 l 能熟練地對(duì)算法進(jìn)行時(shí)間復(fù)雜度分析，從而選擇一個(gè) 好的算法。 第1頁/共25頁 引例描述引例描述 求兩個(gè)n 階方陣的乘積C=AB，其算法如下，計(jì)算該 算法的時(shí)間復(fù)雜度。程序段如下： for(i=0;in;i+) for(j=0;jn;j+) cij=0; for

2、(k=0;kn;k+) cij+=aik*bkj; 第2頁/共25頁 1.1 數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的概念 1.數(shù)據(jù)（數(shù)據(jù)（Data） 數(shù)據(jù)是信息的載體。它能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加 工處理。 2.數(shù)據(jù)元素（數(shù)據(jù)元素（Data Element） 數(shù)據(jù)元素是數(shù)據(jù)的基本單位。數(shù)據(jù)元素也稱元素、結(jié) 點(diǎn)、頂點(diǎn)、記錄。 3.數(shù)據(jù)項(xiàng)（數(shù)據(jù)項(xiàng)（Data item） 數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。一個(gè)數(shù)據(jù)元 素可以由若干個(gè)數(shù)據(jù)項(xiàng)（也可稱為字段、域、屬性）組成 。 4.數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（Data Structure） 數(shù)據(jù)結(jié)構(gòu)指的是數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織 形式。數(shù)據(jù)結(jié)構(gòu)一般包括以下三方面內(nèi)容：

3、 知識(shí)儲(chǔ)備知識(shí)儲(chǔ)備 第3頁/共25頁 (1)數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系。 數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存 儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從 具體問題抽象出來的數(shù)學(xué)模型。 數(shù)據(jù)（邏輯）結(jié)構(gòu)的形式定義：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組 （D，R），其中D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有 限集。 (2)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素及數(shù)據(jù)元素之間的關(guān)系在計(jì)算 機(jī)存儲(chǔ)器內(nèi)的表示。 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)（亦稱 為映象），它依賴于計(jì)算機(jī)語言。對(duì)機(jī)器語言而言，存儲(chǔ)結(jié) 構(gòu)是具體的。一般，只在高級(jí)語言的層次上討論存儲(chǔ)結(jié)構(gòu)。

4、【示例】某個(gè)班學(xué)生成績表，包括：學(xué)號(hào)、姓名和各科 成績，每一個(gè)學(xué)生的信息都是一個(gè)數(shù)據(jù)元素，數(shù)據(jù)元素 之間有這樣的邏輯關(guān)系：在一個(gè)數(shù)據(jù)元素的前面最多有 一個(gè)與其相鄰的數(shù)據(jù)元素（稱為直接前驅(qū)），在一個(gè)數(shù) 據(jù)元素的后面也最多有一個(gè)與其相鄰的數(shù)據(jù)元素（稱為 直接后繼）。數(shù)據(jù)元素之間的這種關(guān)系構(gòu)成了學(xué)生成績 表的邏輯結(jié)構(gòu)。 第4頁/共25頁 (3)數(shù)據(jù)的運(yùn)算數(shù)據(jù)的運(yùn)算：即對(duì)數(shù)據(jù)施加的操作。 數(shù)據(jù)的運(yùn)算定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上，只有確定了存 儲(chǔ)結(jié)構(gòu)，才能具體實(shí)現(xiàn)這些運(yùn)算。 數(shù)據(jù)的運(yùn)算通常包括以下五個(gè)操作： 插入：插入：在指定位置上添加一個(gè)新結(jié)點(diǎn)。 刪除：刪除：刪去指定位置上的結(jié)點(diǎn)。 更新：更新：修改某結(jié)點(diǎn)的

5、值。 查找：查找：尋找滿足指定條件的結(jié)點(diǎn)及其位置。 排序：排序：按指定的順序使結(jié)點(diǎn)重新排列。 第5頁/共25頁 1.2 數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu) 1.數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)有以下兩大類： 線性結(jié)構(gòu)線性結(jié)構(gòu) 有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，且所有結(jié)點(diǎn)都最 多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。 線性表是一個(gè)典型的線性結(jié)構(gòu)。棧、隊(duì)列、串等都是線性 結(jié)構(gòu)。 非線性結(jié)構(gòu)非線性結(jié)構(gòu) 一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前驅(qū)和多個(gè)直接后繼。 多維數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。 第6頁/共25頁 2.基本邏輯結(jié)構(gòu)基本邏輯結(jié)構(gòu) 集合結(jié)構(gòu)：集合結(jié)構(gòu)：數(shù)據(jù)元素的有限

6、集合。數(shù)據(jù)元素之間除了“屬 于同一個(gè)集合”的關(guān)系之外沒有其他關(guān)系。 線性結(jié)構(gòu)：線性結(jié)構(gòu)：數(shù)據(jù)元素的有序集合。數(shù)據(jù)元素之間形成一對(duì) 一的關(guān)系。 樹型結(jié)構(gòu)：樹型結(jié)構(gòu)：樹是層次數(shù)據(jù)結(jié)構(gòu)，樹中數(shù)據(jù)元素之間存在一 對(duì)多的關(guān)系。 圖狀結(jié)構(gòu)：圖狀結(jié)構(gòu)：圖中數(shù)據(jù)元素之間的關(guān)系是多對(duì)多的。 集合結(jié)構(gòu)線性結(jié)構(gòu)樹型結(jié)構(gòu) 圖狀結(jié)構(gòu) 第7頁/共25頁 3.存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu)可用以下四種存儲(chǔ)方法得到： 順序存儲(chǔ)方法：順序存儲(chǔ)方法：把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相 鄰的存儲(chǔ)單元里，結(jié)點(diǎn)之間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān) 系來體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。通常借 助程序設(shè)計(jì)語言的數(shù)組來描述。 鏈接存儲(chǔ)方

7、法：鏈接存儲(chǔ)方法：該方法不要求邏輯上相鄰的結(jié)點(diǎn)在物理位 置上也相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段來表示 的。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。通常借助程序 設(shè)計(jì)語言的指針來描述。如圖： 30001130 1 89.5 4000 1130 3 90.5 3050 1132 5 83 3020 11318 78 NUL L head3000400030503020 第8頁/共25頁 索引存儲(chǔ)方法：索引存儲(chǔ)方法：在建立結(jié)點(diǎn)信息的同時(shí)，還要建立附加的 索引表來標(biāo)識(shí)結(jié)點(diǎn)的地址。索引表中的每一項(xiàng)稱為索引項(xiàng)， 索引項(xiàng)由結(jié)點(diǎn)的關(guān)鍵字和該結(jié)點(diǎn)的存儲(chǔ)地址組成，關(guān)鍵字是 能唯一標(biāo)識(shí)一個(gè)結(jié)點(diǎn)的數(shù)據(jù)項(xiàng)。 散列存

8、儲(chǔ)方法：散列存儲(chǔ)方法：該方法的基本思想是：根據(jù)結(jié)點(diǎn)的關(guān)鍵字 直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。 同一邏輯結(jié)構(gòu)采用不同的存儲(chǔ)方法，可以得到不同的存 儲(chǔ)結(jié)構(gòu)。選擇何種存儲(chǔ)結(jié)構(gòu)表示相應(yīng)邏輯結(jié)構(gòu)，視具體要求 而定，主要考慮運(yùn)算方便及算法的時(shí)空要求。 第9頁/共25頁 1.3 算法及算法分析算法及算法分析 一、算法及其特性一、算法及其特性 1.算法算法 是對(duì)特定問題求解步驟的一種描述，是指令的有限序列 。一個(gè)算法是一系列將輸入轉(zhuǎn)換為輸出的計(jì)算步驟。 2.算法的重要特性算法的重要特性 輸入：輸入：算法應(yīng)該有零個(gè)或多個(gè)輸入。 有窮性：有窮性：算法必須在執(zhí)行有窮步驟之后正常結(jié)束。 確定性：確定性：算法中的每一條指令

9、必須有確切的含義。 可行性：可行性：算法中的每一條指令必須是切實(shí)可執(zhí)行的。 輸出：輸出：算法應(yīng)該有一個(gè)或多個(gè)輸出。 第10頁/共25頁 3.算法描述算法描述 框圖算法描述：框圖算法描述：使用流程圖或N-S圖來描述算法； 非形式算法描述：非形式算法描述：使用自然語言（中文或英文）和程序設(shè)計(jì) 語言中的語句來描述算法。 類高級(jí)語言算法描述：類高級(jí)語言算法描述：使用類C或C+的所謂偽語言來描述 算法。 高級(jí)語言算法描述：高級(jí)語言算法描述：使用高級(jí)語言來描述算法。 本課程將采用 C語言進(jìn)行算法描述。 4.算法與程序的關(guān)系算法與程序的關(guān)系 算法和程序都是用來表達(dá)解決問題的邏輯步驟；算法是對(duì) 解決問題的方法

10、的具體描述，程序是算法在計(jì)算機(jī)中的具體實(shí) 現(xiàn)；程序是算法，但算法不一定是程序。 第11頁/共25頁 二、二、算法分析算法分析 1.算法設(shè)計(jì)的要求算法設(shè)計(jì)的要求 通常從以下五個(gè)方面評(píng)價(jià)算法的質(zhì)量： 正確性：正確性：算法應(yīng)能正確地實(shí)現(xiàn)預(yù)定功能和要求。 易讀性：易讀性：算法應(yīng)易于閱讀和理解，便于調(diào)試、修改和擴(kuò)充 。 健壯性：健壯性：對(duì)正確的輸入能得到正確的輸出。當(dāng)遇到非法輸 入時(shí)應(yīng)能作適當(dāng)?shù)姆磻?yīng)或處理，而不會(huì)產(chǎn)生不需要或不正確 的結(jié)果。 高效性：高效性：解決同一問題的執(zhí)行時(shí)間越短，算法的時(shí)間效率 就越高。 低存儲(chǔ)量：低存儲(chǔ)量：解決同一問題的占用存儲(chǔ)空間越少，算法的空 間效率就越高。 第12頁/共25

11、頁 2.影響算法運(yùn)行時(shí)間的因素影響算法運(yùn)行時(shí)間的因素 計(jì)算機(jī)硬件； 實(shí)現(xiàn)算法的語言； 編譯生成的目標(biāo)代碼的質(zhì)量； 問題的規(guī)模：?jiǎn)栴}的規(guī)模：算法求解問題的輸入量稱為問題的規(guī)模,一般 用一個(gè)整數(shù)表示 。 在各種因素都不能確定的情況下，很難比較出算法的執(zhí) 行時(shí)間，即使用執(zhí)行算法的絕對(duì)時(shí)間來衡量算法的效率是不 合適的。 為此，可以將與計(jì)算機(jī)軟硬件相關(guān)的因素確定下來，這 樣，一個(gè)特定算法的運(yùn)行工作量就只依賴于問題的規(guī)模，即 算法的運(yùn)行時(shí)間是問題規(guī)模n的函數(shù)T(n)。 第13頁/共25頁 3.算法的時(shí)間效率分析算法的時(shí)間效率分析 一個(gè)算法所耗費(fèi)的時(shí)間，應(yīng)該是該算法中每條語句的執(zhí)行 時(shí)間之和，而每條語句的執(zhí)

12、行時(shí)間是該語句的執(zhí)行次數(shù)(稱為 頻度)與該語句執(zhí)行一次所需時(shí)間的乘積。 但當(dāng)算法轉(zhuǎn)換為程序之后，每條語句執(zhí)行一次所需的時(shí)間 取決于機(jī)器的指令性能、速度以及編譯所產(chǎn)生的代碼質(zhì)量，這 是很難確定的。 我們假設(shè)每條語句執(zhí)行一次所需的時(shí)間均是單位時(shí)間，這 樣，一個(gè)算法的時(shí)間耗費(fèi)，就是該算法中所有語句的頻度之一個(gè)算法的時(shí)間耗費(fèi)，就是該算法中所有語句的頻度之 和和。于是，我們就可以獨(dú)立于機(jī)器的軟、硬件系統(tǒng)來分析算法 的時(shí)間耗費(fèi)。 第14頁/共25頁 4.算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度 定義：定義：設(shè)問題的規(guī)模為n，把一個(gè)算法的時(shí)間耗費(fèi)T(n)稱為 該算法的時(shí)間復(fù)雜度，它是問題規(guī)模為n的函數(shù)。 算法的漸進(jìn)

13、時(shí)間復(fù)雜度算法的漸進(jìn)時(shí)間復(fù)雜度 設(shè)T(n)為一個(gè)算法的時(shí)間復(fù)雜度，當(dāng)問題的規(guī)模n趨向無窮 大時(shí)，時(shí)間復(fù)雜度T(n)的數(shù)量級(jí)(階)稱為算法的漸進(jìn)時(shí)間復(fù)雜 度。 即當(dāng)n趨向無窮大時(shí)， T(n)與函數(shù)f(n)的比值的極限是一 個(gè)非零常數(shù)M，即 ， M nf nT n )( )( lim 記作T(n)=O(f(n)，則稱 O(f(n)為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度，也稱T(n) 與f(n)的數(shù)量級(jí)相同，通常，f(n)應(yīng)該是算法中頻度最大的語 句的頻度。 第15頁/共25頁 常用的算法的時(shí)間復(fù)雜度的順序常用的算法的時(shí)間復(fù)雜度的順序 O(1)O(lgn)O(n)O(nlgn)O(n2)O(n3)=

14、0 (4)return i; 此算法中的語句(3)的頻度不僅與問題規(guī)模n有關(guān)，還與輸 入實(shí)例中A的各元素取值及K的取值有關(guān)： 若A中沒有與K相等的元素，則語句(3)的頻度f(n)=n； 若A的最后一個(gè)元素等于K,則語句(3)的頻度f(n)是常數(shù)0。 第16頁/共25頁 最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度最壞時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度 最壞情況下的時(shí)間復(fù)雜度稱為最壞時(shí)間復(fù)雜度。最壞 情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行時(shí)間的 上界。 平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等概率 出現(xiàn)的情況下，算法的期望運(yùn)行時(shí)間。 如果不作特別說明，我們討論的時(shí)間復(fù)雜度均是平均 時(shí)間復(fù)雜度。 第17頁/共2

15、5頁 【例例1-1】 求在含有n（n3）個(gè)元素的數(shù)組array中輸出第3 個(gè)元素算法的時(shí)間復(fù)雜度。 (1) i=3; (2) printf(%dn,arrayi); 解：解：各行語句的執(zhí)行次數(shù)均為1，所以該算法的時(shí)間耗費(fèi) T(n)= 1+1=2，該算法的時(shí)間耗費(fèi)T(n)與問題的規(guī)模n無關(guān)， 因此，該算法的時(shí)間復(fù)雜度T(n)=O(1)。 第18頁/共25頁 【例例1-2】 求下列算法的時(shí)間復(fù)雜度。 (1) x=1; (2) for(i=1;i=n;i+) (3) for(j=1;j=i;j+) (4) for(k=1;k=j;k+) (5) x+; 分析：分析：該程序段中頻度最大的語句是(5)，

16、內(nèi)循環(huán)語句(4)和 (3)雖然與n無關(guān)，但外循環(huán)(2)與n有關(guān)。所以，可以從內(nèi)層循 環(huán)向外層分析語句(5)的執(zhí)行次數(shù) 。 解：解： 循環(huán)結(jié)構(gòu)(4)的循環(huán)體(5)執(zhí)行了j次，循環(huán)結(jié)構(gòu)(3)的循環(huán) 體執(zhí)行了i次，(2)的循環(huán)體執(zhí)行了n次，即語句(5)的執(zhí)行次數(shù) 為： 6/ )2)(1(2/ )2/ ) 1(6/ ) 12)(1(2/ )(2/ ) 1( 1i1111 2 nnnnnnnniiiij ni j n i n i n i 因此，該算法的時(shí)間復(fù)雜度T(n)=O(n3)。 第19頁/共25頁 【課堂實(shí)踐【課堂實(shí)踐1-1】 分析并計(jì)算下面程序段執(zhí)行的時(shí) 間復(fù)雜度。 (1) i=1; k=0;

17、while(i=n-1) k+=10*i; i+; (2) i=1; j=0; while(i+jj) j+; else i+; 做做 一一 做做 第20頁/共25頁 引例分析引例分析 分析分析1： 計(jì)算程序段中的每一行的執(zhí)行次數(shù)。 第(1)行for(i=0; in; i+)中只考慮循環(huán)條件表達(dá)式in的 執(zhí)行次數(shù)（忽略初始化表達(dá)式i=0和修正表達(dá)式i+的執(zhí)行次 數(shù)，下同），表達(dá)式in共執(zhí)行n+1次（i為0到n-1時(shí)該表達(dá)式 非零，共n次，i為n時(shí)該表達(dá)式為零，共1次，合計(jì)執(zhí)行n+1 次），所以，第(1)行共執(zhí)行n+1次； 第(2)行for(j=0; jn; j+)，在第(1)行for(i=0; in; i+)中 的表達(dá)式in非零時(shí)（共n次）都要執(zhí)行一遍，而每一遍同樣 要執(zhí)行n+1次，所以，第(2)行共執(zhí)行n（n+1）次； 第21頁/共25頁 引例分析引例分析 第(4)行cij=0;在表達(dá)式in和jn均非零時(shí)執(zhí)行，共執(zhí) 行n2次； 第(5)行for(k=0; kn; k+)在表達(dá)式in和jn均非零時(shí)執(zhí) 行一遍，而每一遍同樣要執(zhí)行n+1次，所以，第(5)行共執(zhí)行 n2(n+1)次； 第(6)行cij+=aik*bkj; 在表達(dá)式in、jn和kn均 非零時(shí)執(zhí)行，共執(zhí)行n3次； 因此，各行執(zhí)行次數(shù)分別為：n+1，n(n+1)，n2，n2(n+1) ，n3。 如果用T(n)表示該