概論西南林學(xué)院計(jì)科系課件

1、第一章 概論西南林學(xué)院計(jì)算機(jī)與信息科學(xué)系董躍宇本章的主要內(nèi)容為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？什么是數(shù)據(jù)結(jié)構(gòu)？算法及其度量為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？原因1：數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科的一門(mén)專業(yè)基礎(chǔ)課，它可以為后續(xù)專業(yè)課程的學(xué)習(xí)提供必要的知識(shí)和技能準(zhǔn)備。例如：程序設(shè)計(jì)語(yǔ)言及其編譯技術(shù)要使用棧、散列表及語(yǔ)法樹(shù)操作系統(tǒng)會(huì)用到隊(duì)列、存儲(chǔ)管理表及目錄樹(shù)數(shù)據(jù)庫(kù)系統(tǒng)中會(huì)用到線性表、多鏈表及索引樹(shù)廣義表、集合以及圖的搜索在很多應(yīng)用領(lǐng)域經(jīng)常涉及為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)？原因2：現(xiàn)代電子計(jì)算機(jī)最初是設(shè)計(jì)用來(lái)處理數(shù)值型數(shù)據(jù)的，但隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的不斷拓展，所需要處理的不再只是數(shù)值型數(shù)據(jù)，這給程序設(shè)計(jì)等方面帶來(lái)了一些新的問(wèn)題。分析

2、待處理的對(duì)象以及待處理對(duì)象之間的關(guān)系成了一個(gè)必須的選擇。這也正是數(shù)據(jù)結(jié)構(gòu)這一課程出現(xiàn)的背景和原因。數(shù)據(jù)結(jié)構(gòu)課程的主要內(nèi)容介紹一些最常用的數(shù)據(jù)結(jié)構(gòu)，闡明數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論它們?cè)谟?jì)算機(jī)中的存儲(chǔ)表示，并結(jié)合各種數(shù)據(jù)結(jié)構(gòu)，討論對(duì)它們實(shí)行各種運(yùn)算的實(shí)現(xiàn)算法。以上這些知識(shí)再配合以實(shí)際的上機(jī)編程練習(xí)，將增強(qiáng)求解復(fù)雜問(wèn)題的能力，其中包括根據(jù)問(wèn)題的性質(zhì)恰當(dāng)選擇數(shù)據(jù)結(jié)構(gòu)的能力，以及控制求解算法的復(fù)雜性的能力。愛(ài)莫能助什么是數(shù)據(jù)結(jié)構(gòu)？何謂數(shù)據(jù)？數(shù)據(jù)是對(duì)客觀事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)處理的符號(hào)的總稱數(shù)據(jù)元素是數(shù)據(jù)的基本單位什么是數(shù)據(jù)結(jié)構(gòu)？何謂結(jié)構(gòu)？在任何問(wèn)題中，數(shù)據(jù)元

3、素都不是孤立存在的，而是在它們之間存在某種關(guān)系，這種數(shù)據(jù)元素相互之間的關(guān)系稱為結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)涉及數(shù)據(jù)之間的邏輯關(guān)系、數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式和在這種結(jié)構(gòu)上的一組可行的操作（運(yùn)算）三個(gè)方面。為了敘述方便，把上述三個(gè)方面分別稱為：數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的運(yùn)算數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)反映了人們對(duì)數(shù)據(jù)的含義解釋。人們對(duì)現(xiàn)實(shí)世界的某個(gè)特定領(lǐng)域的認(rèn)識(shí)，表現(xiàn)在對(duì)所涉及的事物之間的邏輯關(guān)系以及組成結(jié)構(gòu)的認(rèn)識(shí)數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)可以用集合論的觀點(diǎn)來(lái)分析：一個(gè)邏輯結(jié)構(gòu)可以用一個(gè)二元組來(lái)表示：，其中，D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集從這一角度來(lái)看，數(shù)據(jù)結(jié)構(gòu)就是一組存在特

4、定關(guān)系的數(shù)據(jù)元素的集合數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素的有限集D中的數(shù)據(jù)元素是對(duì)現(xiàn)實(shí)世界特定領(lǐng)域所涉及的事物的反映D中的元素可以是簡(jiǎn)單的基本類型，也可以是龐雜的復(fù)合類型數(shù)據(jù)的邏輯結(jié)構(gòu)可以利用集合R中的關(guān)系的性質(zhì)來(lái)刻畫(huà)數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，對(duì)其進(jìn)行分類數(shù)據(jù)的邏輯結(jié)構(gòu)可分為：集合線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖結(jié)構(gòu)集合D中的數(shù)據(jù)元素除了同屬于一個(gè)集合外，無(wú)其他關(guān)系集合反映了一種松散的邏輯結(jié)構(gòu)線性結(jié)構(gòu)數(shù)據(jù)元素的直接前驅(qū)節(jié)點(diǎn)若存在，則唯一數(shù)據(jù)元素的直接后繼節(jié)點(diǎn)若存在，則唯一線性結(jié)構(gòu)反映的是一種一對(duì)一的關(guān)系樹(shù)形結(jié)構(gòu)數(shù)據(jù)元素的直接前驅(qū)節(jié)點(diǎn)若存在，則唯一數(shù)據(jù)元素的直接后繼節(jié)點(diǎn)若存在，可不唯一樹(shù)形結(jié)構(gòu)反映的是一種一對(duì)多的關(guān)系圖結(jié)構(gòu)對(duì)于圖結(jié)

5、構(gòu)，R中的關(guān)系沒(méi)有任何約束，因此圖結(jié)構(gòu)反映的是多對(duì)多的關(guān)系圖結(jié)構(gòu)也被稱為網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)首先必須了解的問(wèn)題：計(jì)算機(jī)主存儲(chǔ)器的特性計(jì)算機(jī)主存儲(chǔ)器的特性：空間相鄰：主存儲(chǔ)器的存儲(chǔ)空間提供了一種具有非負(fù)整數(shù)地址編碼的、在存儲(chǔ)空間上相鄰的單元集合隨機(jī)訪問(wèn)：計(jì)算機(jī)的指令具有按地址隨機(jī)訪問(wèn)存儲(chǔ)空間中任意單元的能力，訪問(wèn)不同單元所需要的時(shí)間基本相同數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)的一個(gè)主要任務(wù)，是要充分利用主存儲(chǔ)器的兩個(gè)特點(diǎn)，利用順序存儲(chǔ)單元空間相鄰關(guān)系來(lái)表達(dá)數(shù)據(jù)結(jié)構(gòu)的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)通常被存儲(chǔ)在一片連續(xù)的存儲(chǔ)區(qū)域內(nèi)如何將邏輯關(guān)系映射到存儲(chǔ)結(jié)構(gòu)的地址關(guān)系上，利用存儲(chǔ)地址表達(dá)邏輯關(guān)系，所采用的表達(dá)方法的好壞會(huì)

6、非常影響存儲(chǔ)空間的開(kāi)銷，而且也會(huì)影響到算法的效率四種基本的存儲(chǔ)映射方法可以利用映射來(lái)表示存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是建立一種由邏輯結(jié)構(gòu)到存儲(chǔ)空間的映射四種基本的存儲(chǔ)映射方法是：順序的方法鏈接的方法索引的方法散列的方法順序的方法用一塊無(wú)空隙的存儲(chǔ)區(qū)域存儲(chǔ)數(shù)據(jù)元素稱為順序存儲(chǔ)順序存儲(chǔ)將一組數(shù)據(jù)元素存放在按地址相鄰的存儲(chǔ)單元里，數(shù)據(jù)元素間的邏輯關(guān)系采用存儲(chǔ)單元的自然順序關(guān)系來(lái)表達(dá)順序存儲(chǔ)結(jié)構(gòu)被稱為緊湊存儲(chǔ)結(jié)構(gòu)，其緊湊性是指它的存儲(chǔ)空間除了存儲(chǔ)有用數(shù)據(jù)外，沒(méi)有用于存儲(chǔ)其他附加的信息鏈接的方法采用的數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)中附加指針字段的方法稱為鏈接法。兩個(gè)數(shù)據(jù)元素的邏輯后繼關(guān)系可以用指針的指向來(lái)表達(dá)鏈接的方法

7、是經(jīng)常使用的，特別是對(duì)于那些經(jīng)常增刪結(jié)點(diǎn)的復(fù)雜數(shù)據(jù)結(jié)構(gòu)，順序結(jié)構(gòu)往往會(huì)遇到困難索引的方法索引法是順序法的一種推廣，它使用一個(gè)索引表存儲(chǔ)存儲(chǔ)一串指針，每個(gè)指針指向存儲(chǔ)區(qū)域的一個(gè)數(shù)據(jù)結(jié)點(diǎn)。索引法的一個(gè)直接用途是可以把大小不等的數(shù)據(jù)結(jié)點(diǎn)順序存儲(chǔ)，并且仍然可以使用整數(shù)下標(biāo)來(lái)間接訪問(wèn)數(shù)據(jù)結(jié)點(diǎn)位置散列的方法散列方法可以認(rèn)為是索引方法的一種延伸和擴(kuò)展，通過(guò)散列函數(shù)進(jìn)行索引值的計(jì)算，然后通過(guò)索引表求出結(jié)點(diǎn)的指針地址抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型是描述數(shù)據(jù)結(jié)構(gòu)的一種理論工具，其特點(diǎn)是把數(shù)據(jù)結(jié)構(gòu)作為獨(dú)立于應(yīng)用程序的一種抽象代數(shù)結(jié)構(gòu)，使得人們可以獨(dú)立于程序的實(shí)現(xiàn)細(xì)節(jié)來(lái)理解數(shù)據(jù)結(jié)構(gòu)的主要性質(zhì)和約束條件抽象數(shù)據(jù)類型的表示對(duì)應(yīng)

8、于數(shù)據(jù)結(jié)構(gòu)的二元組表示法，可采用三元組法表示抽象數(shù)據(jù)類型：，其中D是數(shù)據(jù)元素的有限集R是D上的關(guān)系集P是對(duì)D的基本操作集算法分析基礎(chǔ)何謂“算法”？解決那些適合計(jì)算機(jī)實(shí)現(xiàn)的問(wèn)題的方法對(duì)特定問(wèn)題求解步驟的一種描述。在編寫(xiě)一個(gè)計(jì)算機(jī)程序時(shí)，我們通常會(huì)實(shí)現(xiàn)一個(gè)事先設(shè)計(jì)好的解決問(wèn)題的方法。這個(gè)方法與具體使用的計(jì)算機(jī)無(wú)關(guān)，它可以適用于許多計(jì)算機(jī)和計(jì)算機(jī)語(yǔ)言。我們必須學(xué)習(xí)的是解決問(wèn)題的方法，而不是計(jì)算機(jī)程序本身?！八惴ā边@一術(shù)語(yǔ)就是這個(gè)方法在計(jì)算機(jī)科學(xué)中的對(duì)應(yīng)物算法分析基礎(chǔ)算法的五個(gè)特性：有窮性：對(duì)于任何合法的輸入，一個(gè)算法必須在執(zhí)行有窮步后結(jié)束，每個(gè)步驟必須在有窮時(shí)間內(nèi)完成確定性：算法中的每個(gè)指令必須有確

9、切的含義可行性：算法中描述的操作都是可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)輸入：一個(gè)算法有零個(gè)或多個(gè)輸入輸出：一個(gè)算法有一個(gè)或多個(gè)輸出算法分析基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系大多數(shù)算法關(guān)心計(jì)算機(jī)中數(shù)據(jù)的組織方式。而使用這種方式建立的對(duì)象稱為“數(shù)據(jù)結(jié)構(gòu)”從算法的角度看，數(shù)據(jù)結(jié)構(gòu)是算法的副產(chǎn)物或最終產(chǎn)物算法分析基礎(chǔ)算法設(shè)計(jì)的要求正確性：算法應(yīng)當(dāng)滿足具體問(wèn)題的需求可讀性：算法主要是為了人的閱讀和交流，其次才是機(jī)器執(zhí)行健壯性：對(duì)于非法的輸入數(shù)據(jù)，算法也能適當(dāng)?shù)淖鞒龇磻?yīng)或進(jìn)行處理效率和低存儲(chǔ)需求：時(shí)空資源的消耗以少為佳算法分析基礎(chǔ)算法分析的兩種策略：事后統(tǒng)計(jì)事前分析主要采取的事前分析的策略算法分析基礎(chǔ)算法的

10、漸進(jìn)分析簡(jiǎn)稱算法分析算法的漸進(jìn)分析算法在計(jì)算機(jī)上實(shí)現(xiàn)時(shí)，需要消耗時(shí)間（CPU執(zhí)行指令的時(shí)間）和使用存儲(chǔ)空間資源（占用的存儲(chǔ)單元數(shù)）算法分析與算法所求解的問(wèn)題的規(guī)模直接相關(guān)，因此通常將問(wèn)題規(guī)模n作為一個(gè)參照量，求算法的時(shí)空消耗與n的關(guān)系算法分析主要考慮求解問(wèn)題的規(guī)模n逐漸增大時(shí)，算法時(shí)空消耗的變化趨勢(shì)算法分析基礎(chǔ)算法分析方法的幾點(diǎn)說(shuō)明在具體估計(jì)時(shí)空消耗時(shí)，要對(duì)算法的整個(gè)執(zhí)行過(guò)程進(jìn)行全面檢查，求出所執(zhí)行的操作的總數(shù)量每一個(gè)操作的消耗估計(jì)與具體計(jì)算機(jī)的技術(shù)細(xì)節(jié)相關(guān)，這些細(xì)節(jié)不必牽涉到算法分析中，因此算法分析不應(yīng)拘泥于操作的種類、不同操作種類間的消耗的差別，而主要關(guān)注消耗隨n的變化趨勢(shì)最好、最好和平均情況時(shí)空互換問(wèn)題數(shù)據(jù)結(jié)構(gòu)