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

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

2、待處理的對象以及待處理對象之間的關(guān)系成了一個必須的選擇。這也正是數(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)系，討論它們在計算機中的存儲表示，并結(jié)合各種數(shù)據(jù)結(jié)構(gòu)，討論對它們實行各種運算的實現(xiàn)算法。以上這些知識再配合以實際的上機編程練習(xí)，將增強求解復(fù)雜問題的能力，其中包括根據(jù)問題的性質(zhì)恰當(dāng)選擇數(shù)據(jù)結(jié)構(gòu)的能力，以及控制求解算法的復(fù)雜性的能力。愛莫能助什么是數(shù)據(jù)結(jié)構(gòu)？何謂數(shù)據(jù)？數(shù)據(jù)是對客觀事物的符號表示。在計算機科學(xué)中是指所有能輸入到計算機中并能被計算機處理的符號的總稱數(shù)據(jù)元素是數(shù)據(jù)的基本單位什么是數(shù)據(jù)結(jié)構(gòu)？何謂結(jié)構(gòu)？在任何問題中，數(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ù)在計算機中的存儲方式和在這種結(jié)構(gòu)上的一組可行的操作（運算）三個方面。為了敘述方便，把上述三個方面分別稱為：數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的運算數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)反映了人們對數(shù)據(jù)的含義解釋。人們對現(xiàn)實世界的某個特定領(lǐng)域的認(rèn)識，表現(xiàn)在對所涉及的事物之間的邏輯關(guān)系以及組成結(jié)構(gòu)的認(rèn)識數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)可以用集合論的觀點來分析：一個邏輯結(jié)構(gòu)可以用一個二元組來表示：，其中，D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集從這一角度來看，數(shù)據(jù)結(jié)構(gòu)就是一組存在特

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

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

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

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

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

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

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