數(shù)據(jù)結(jié)構(gòu)0學(xué)習(xí)方法與概念

1、講師：尹成QQ:77025077博客:http:/ 傳智播客傳智播客http:/高薪就業(yè)高薪就業(yè)第0章 學(xué)習(xí)方法與概念概述概 論3/44課程性質(zhì)課程性質(zhì)m“數(shù)據(jù)結(jié)構(gòu)與算法”是計(jì)算機(jī)專(zhuān)業(yè)的核心課程之一，本科教學(xué)的重中之重。m本課程q上承“程序設(shè)計(jì)”，q下啟“算法分析與設(shè)計(jì) ，q是操作系統(tǒng)、軟件工程、數(shù)據(jù)庫(kù)概論、編譯技術(shù)、人工智能、計(jì)算機(jī)圖形學(xué)等專(zhuān)業(yè)課程的必修先行課。m所有應(yīng)用軟件都要使用到各種數(shù)據(jù)結(jié)構(gòu)和算法編寫(xiě)程序。 概 論4/44概 論5/44m程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法m對(duì)清華大學(xué)計(jì)算機(jī)系歷屆畢業(yè)生和部分研究生追蹤調(diào)查顯示：幾乎所有的學(xué)生都認(rèn)為“數(shù)據(jù)結(jié)構(gòu)”是他們?cè)趯W(xué)校里學(xué)過(guò)的最有用的課程之

2、一。 國(guó)內(nèi)外許多軟件開(kāi)發(fā)機(jī)構(gòu)要求考核的基本課程之一。 公司面試或筆試考核的絕大部分內(nèi)容是數(shù)據(jù)結(jié)構(gòu)或算法。 計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程等專(zhuān)業(yè)研究生考試必考科目。概 論6/44教學(xué)目的教學(xué)目的m程序=數(shù)據(jù)結(jié)構(gòu)+算法q基本的數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算.q算法設(shè)計(jì)和分析技術(shù)m解決問(wèn)題能力q抽象能力：?jiǎn)栴}-數(shù)據(jù)-算法q合理組織數(shù)據(jù)、有效表示數(shù)據(jù)、有效處理數(shù)據(jù)m提高程序設(shè)計(jì)的質(zhì)量概 論7/44學(xué)習(xí)要求m熟練掌握基本內(nèi)容：熟知概念，理解算法，熟練編程，靈活使用上課上機(jī)m學(xué)有余力的同學(xué)：擴(kuò)展學(xué)習(xí)教材內(nèi)容m準(zhǔn)備找工作的同學(xué)：大量編程概 論8/44學(xué)習(xí)可能遇到的問(wèn)題m問(wèn)題一：太抽象，聽(tīng)不懂m建議：主

3、動(dòng)學(xué)習(xí)q樹(shù)立信心活著沒(méi)打到，上課小CASEq預(yù)習(xí)聰明鳥(niǎo)先飛早入林q提問(wèn)式學(xué)習(xí)我遇到這樣的問(wèn)題，怎么解決？q復(fù)習(xí)總結(jié)、提高、實(shí)踐q請(qǐng)教老師、同學(xué)：會(huì)哭的孩子有奶吃，沒(méi)人說(shuō)你笨，別不好意思概 論9/44學(xué)習(xí)可能遇到的問(wèn)題m問(wèn)題二：算法思想能懂，但代碼看不懂m建議：多寫(xiě)多想q多讀代碼先弄懂思想，再看代碼q找個(gè)實(shí)例，手工執(zhí)行代碼q上機(jī)調(diào)試，用不同的數(shù)據(jù)看輸入輸出q經(jīng)典代碼要能寫(xiě)出來(lái)（不是背，是用自己的風(fēng)格寫(xiě)）概 論10/44學(xué)習(xí)可能遇到的問(wèn)題m問(wèn)題三：不會(huì)編寫(xiě)代碼，或代碼質(zhì)量不高m建議：多寫(xiě)多練q有思想，寫(xiě)不出代碼簡(jiǎn)化條件，先寫(xiě)簡(jiǎn)單的，再擴(kuò)展q邊界處理不周到：舉出各種出現(xiàn)邊界情況的實(shí)例，抽象邊界問(wèn)題q

4、代碼不清晰：學(xué)習(xí)養(yǎng)成好的編程風(fēng)格概 論11/44學(xué)習(xí)可能遇到的問(wèn)題m問(wèn)題四：學(xué)習(xí)吃力，但不好意思問(wèn)問(wèn)題m建議：鍛煉開(kāi)朗的性格q交流、溝通是必要的素質(zhì)q情商比智商更重要q虛心學(xué)習(xí)的人大家都?xì)g迎q前提：自己做了最大的努力概 論12/44什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)用計(jì)算機(jī)解決一個(gè)具體的問(wèn)題，需要以下幾個(gè)步驟：q 從具體問(wèn)題抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型；q 設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法；q 編出程序；q 進(jìn)行測(cè)試、調(diào)整直至得到最終解答。尋求數(shù)學(xué)模型的實(shí)質(zhì)：尋求數(shù)學(xué)模型的實(shí)質(zhì)： 分析問(wèn)題，從中分析問(wèn)題，從中提取操作的對(duì)象提取操作的對(duì)象，并找出這些，并找出這些操作對(duì)象之操作對(duì)象之間含有的關(guān)系間含有的關(guān)系，然后

5、用，然后用數(shù)學(xué)的語(yǔ)言加以描述數(shù)學(xué)的語(yǔ)言加以描述。概 論13/44什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)m很多問(wèn)題求解最后都轉(zhuǎn)化為求解數(shù)學(xué)方程或數(shù)學(xué)方程組。m如：求解梁架結(jié)構(gòu)中應(yīng)力的數(shù)學(xué)模型為線(xiàn)性方程組。m預(yù)報(bào)人口增長(zhǎng)情況的數(shù)學(xué)模型為微分方程。m然而：當(dāng)計(jì)算機(jī)進(jìn)入非數(shù)值計(jì)算領(lǐng)域，特別是用在管理上的時(shí)候，計(jì)算機(jī)的操作對(duì)象之間的關(guān)系就無(wú)法用數(shù)學(xué)方程加以描述了。非數(shù)值計(jì)算問(wèn)題的數(shù)學(xué)模型正是本課程要討論的數(shù)據(jù)結(jié)構(gòu)。非數(shù)值計(jì)算問(wèn)題的數(shù)學(xué)模型正是本課程要討論的數(shù)據(jù)結(jié)構(gòu)。概 論14/44例例1：計(jì)算機(jī)和人對(duì)奕問(wèn)題。計(jì)算機(jī)和人對(duì)奕問(wèn)題。計(jì)算機(jī)可以根據(jù)當(dāng)前棋盤(pán)格局，來(lái)預(yù)測(cè)棋局發(fā)展的趨計(jì)算機(jī)可以根據(jù)當(dāng)前棋盤(pán)格局，來(lái)預(yù)測(cè)棋局發(fā)

6、展的趨勢(shì)，甚至最后結(jié)局。勢(shì)，甚至最后結(jié)局。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu):對(duì)弈樹(shù)對(duì)弈樹(shù)。OO當(dāng)前格局當(dāng)前格局派生格局派生格局OOOOOOOOOO概 論15/44例例2：地圖的著色問(wèn)題。地圖的著色問(wèn)題。對(duì)地圖上的每個(gè)區(qū)域染一種顏色，并且要求相鄰的兩對(duì)地圖上的每個(gè)區(qū)域染一種顏色，并且要求相鄰的兩個(gè)區(qū)域不能具有相同顏色。個(gè)區(qū)域不能具有相同顏色。數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu):圖圖。12435671234567紅紅綠綠綠綠藍(lán)藍(lán)紅紅黑黑綠綠1243567用最少的顏色染色用最少的顏色染色概 論16/44例例3 3：圖書(shū)館的書(shū)目檢索自動(dòng)化問(wèn)題：圖書(shū)館的書(shū)目檢索自動(dòng)化問(wèn)題登錄號(hào)：書(shū)名：作者名：分類(lèi)號(hào)：出版單位：出版時(shí)間：價(jià)格：書(shū)目卡片概

7、 論17/44例如例如書(shū)目文件按書(shū)名按作者名按分類(lèi)號(hào)索引表線(xiàn)性的數(shù)據(jù)結(jié)構(gòu)線(xiàn)性的數(shù)據(jù)結(jié)構(gòu)概 論18/44數(shù)學(xué)數(shù)學(xué)計(jì)算機(jī)計(jì)算機(jī)硬件硬件計(jì)算機(jī)計(jì)算機(jī)軟件軟件數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門(mén)數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門(mén)核心課程核心課程。概 論19/44數(shù)據(jù)結(jié)構(gòu)m數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題時(shí)處理的操作對(duì)象以及它們之間的關(guān)系和操作等等的學(xué)科。q解決數(shù)值計(jì)算問(wèn)題的中心: 建立適當(dāng)?shù)臄?shù)學(xué)模型。q解決非數(shù)值計(jì)算問(wèn)題的中心: 尋找適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)。概 論20/44m數(shù)據(jù)結(jié)構(gòu)的討論一般涉及以下三個(gè)方面的內(nèi)容：1 數(shù)據(jù)成員以及它們相互之

8、間的邏輯關(guān)系，也稱(chēng)為數(shù)據(jù)的邏輯結(jié)構(gòu)，簡(jiǎn)稱(chēng)為數(shù)據(jù)結(jié)構(gòu)；2 數(shù)據(jù)成員及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的存儲(chǔ)表示，也稱(chēng)為數(shù)據(jù)的物理結(jié)構(gòu)，簡(jiǎn)稱(chēng)為存儲(chǔ)結(jié)構(gòu)；3 施加于該數(shù)據(jù)結(jié)構(gòu)上的操作。概 論21/44概 論22/44邏輯結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)）m相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。m元素（結(jié)點(diǎn)）類(lèi)型：q基本數(shù)據(jù)類(lèi)型：整型、實(shí)型、布爾型q復(fù)合數(shù)據(jù)類(lèi)型：數(shù)組、結(jié)構(gòu)體、類(lèi)概 論23/44邏輯結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)）m結(jié)點(diǎn)間的關(guān)系結(jié)構(gòu)q先明確結(jié)點(diǎn)，再刻畫(huà)結(jié)點(diǎn)之間的關(guān)系q自頂向下的設(shè)計(jì)概 論24/44集合集合線(xiàn)性結(jié)構(gòu)線(xiàn)性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖狀結(jié)構(gòu)圖狀結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）（網(wǎng)狀結(jié)構(gòu)）概 論25/44數(shù)據(jù)結(jié)構(gòu)的形式定義m數(shù)據(jù)結(jié)構(gòu)

9、的形式定義q數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組 Data_Structure=(K,R) 其中，K是數(shù)據(jù)元素的有限集，R是K上關(guān)系的有限集。 例如：list=(K,R) 其中：K=1,2,3,4,5,6,7 R=,圖形表示圖形表示1234567概 論26/44物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）m數(shù)據(jù)邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示和實(shí)現(xiàn)。m包含數(shù)據(jù)元素的表示和關(guān)系的表示。概 論27/441.2.2 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)m計(jì)算機(jī)的主存儲(chǔ)器的特性q其存儲(chǔ)空間提供了一種具有非負(fù)整數(shù)地址編碼的，相鄰單元的集合，其基本的存儲(chǔ)單元是字節(jié)q計(jì)算機(jī)的指令具有按地址隨機(jī)訪(fǎng)問(wèn)存儲(chǔ)空間內(nèi)任意單元的能力，訪(fǎng)問(wèn)不同地址所需的訪(fǎng)問(wèn)時(shí)間基本相同 概 論28/44數(shù)

10、據(jù)元素的表示m數(shù)據(jù)元素的表示: 通常用位串表示一個(gè)數(shù)據(jù)元素q例，用八位表示一個(gè)字符、三十二位表示一個(gè)整數(shù)請(qǐng)問(wèn): 在C+語(yǔ)言中表示一個(gè)學(xué)生的基本信息(姓名、年齡、性別)，最少需要多少位？概 論29/44數(shù)據(jù)元素之間關(guān)系的表示m順序存儲(chǔ)結(jié)構(gòu)q結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。 通常順序存儲(chǔ)結(jié)構(gòu)是借助于語(yǔ)言的數(shù)組來(lái)描述的。m鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)q不要求邏輯上相鄰的結(jié)點(diǎn)物理上也相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。 概 論30/44順序（sequential）的方法 m用一塊無(wú)空隙的存儲(chǔ)區(qū)域存儲(chǔ)數(shù)據(jù)稱(chēng)為順序存儲(chǔ)m順序存儲(chǔ)把一組結(jié)點(diǎn)存儲(chǔ)在按地址相鄰的順序存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯后繼關(guān)系用存儲(chǔ)

11、單元的自然順序關(guān)系來(lái)表達(dá) m順序存儲(chǔ)法為使用整數(shù)編碼來(lái)訪(fǎng)問(wèn)數(shù)據(jù)結(jié)點(diǎn)提供了便利 概 論31/44元素n.元素i.元素2元素1存儲(chǔ)內(nèi)容存儲(chǔ)內(nèi)容LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)地址順序存儲(chǔ)結(jié)構(gòu)概 論32/44鏈接（linked）的方法 m利用指針，在結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)中附加指針字段稱(chēng)為鏈接法。兩個(gè)結(jié)點(diǎn)的邏輯后繼關(guān)系可以用指針的指向來(lái)表達(dá)m任意的邏輯關(guān)系r，也可以使用這種指針地址來(lái)表達(dá)。一般的做法是將數(shù)據(jù)結(jié)點(diǎn)分為兩部分:q一部分存放結(jié)點(diǎn)本身的數(shù)據(jù)，稱(chēng)為數(shù)據(jù)字段q另一部分存放指針，稱(chēng)指針字段，鏈接到某個(gè)后繼結(jié)點(diǎn)，指向它的存儲(chǔ)單元的開(kāi)始地址。多個(gè)相關(guān)結(jié)點(diǎn)的依次鏈接就會(huì)形成鏈索概

12、 論33/441536元素21536元素21346元素31346元素3 元素4 元素4存儲(chǔ)地址 存儲(chǔ)內(nèi)容 指針 1345 元素1 1400 1346 元素4 . . . 1400 元素2 1536 . . . 1536 元素3 13461400元素1h1400元素1h鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)概 論34/44索引（indexing）的方法 m索引法是順序存儲(chǔ)法的一種推廣，它也使用整數(shù)編碼來(lái)訪(fǎng)問(wèn)數(shù)據(jù)結(jié)點(diǎn)位置m索引方法是要建造一個(gè)由整數(shù)域Z映射到存儲(chǔ)地址域D的函數(shù)Y：ZD，把結(jié)點(diǎn)的整數(shù)索引值 zZ映射到結(jié)點(diǎn)的存儲(chǔ)地址 dD 。它稱(chēng)為索引函數(shù)，一般而言它并不象數(shù)組那樣，是簡(jiǎn)單的線(xiàn)性函數(shù)。概 論35/44索引（in

13、dexing）的方法概 論36/44散列（hashing）的方法 m散列方法是索引方法的一種延伸和擴(kuò)展m利用一種稱(chēng)為散列函數(shù)(hash functions)進(jìn)行索引值的計(jì)算，然后通過(guò)索引表求出結(jié)點(diǎn)的指針地址m散列函數(shù)是將字符串s映射到非負(fù)整數(shù)z的一類(lèi)函數(shù)h: S Z ， 對(duì)任意的 s S，散列函數(shù) h(s)=z，z Z概 論37/44邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)密切相關(guān)m算法設(shè)計(jì)取決于選定的邏輯結(jié)構(gòu)。m算法實(shí)現(xiàn)依賴(lài)于采用的存儲(chǔ)結(jié)構(gòu)。概 論38/44 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等