數(shù)據(jù)結(jié)構(gòu)第1章緒論資料

1、數(shù) 據(jù) 結(jié) 構(gòu) 第1章 緒論王嵐王嵐一、 基本概念 利用計(jì)算機(jī)處理的問題類型 數(shù)值計(jì)算問題，主要用不同的數(shù)學(xué)方程來描述 例1 利用有限元計(jì)算方法進(jìn)行結(jié)構(gòu)靜力分析計(jì)算 例2 利用環(huán)流模式方程進(jìn)行天氣預(yù)報(bào)計(jì)算 非數(shù)值計(jì)算問題，主要用不同的數(shù)據(jù)結(jié)構(gòu)來描述 例1 圖書館書目檢索 例 2 計(jì)算機(jī)和人對(duì)奕問題 例 3 交通燈的控制系統(tǒng)基本概念數(shù)據(jù)、數(shù)據(jù)對(duì)象等 數(shù)據(jù)（data） 是對(duì)客觀事物的符號(hào)化表示，是信息、概念與知識(shí)的載體 數(shù)據(jù)項(xiàng)（data item） 是構(gòu)成數(shù)據(jù)的相對(duì)獨(dú)立的分項(xiàng)，它反映客觀事物的某種特性 數(shù)據(jù)元素（data element） 是構(gòu)成數(shù)據(jù)的具有相同性質(zhì)的基本單元 數(shù)據(jù)對(duì)象（data o

2、bject） 是性質(zhì)相同的數(shù)據(jù)元素的集合。 是數(shù)據(jù)的一個(gè)子集。 是一種運(yùn)行時(shí)的概念?；靖拍顢?shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)（data structure） 是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合數(shù)據(jù)結(jié)構(gòu)的二元組表示：Data_Structure = (D, S)其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集基本概念數(shù)據(jù)結(jié)構(gòu) 例如一維數(shù)組是一種數(shù)據(jù)結(jié)構(gòu) Array = 數(shù)據(jù)元素的集合是D = a1, a2, , an 數(shù)據(jù)元素關(guān)系的集合是S = RR=| 1in 其中為序偶基本概念數(shù)據(jù)結(jié)構(gòu) 按照軟件系統(tǒng)開發(fā)過程中的數(shù)據(jù)層次模型，數(shù)據(jù)之間存在兩種結(jié)構(gòu)關(guān)系 數(shù)據(jù)的邏輯結(jié)構(gòu)（位于邏輯層），反映數(shù)據(jù)元素

3、之間的邏輯關(guān)系，由抽象數(shù)據(jù)類型來表達(dá) 數(shù)據(jù)的物理結(jié)構(gòu)（位于實(shí)現(xiàn)層），也稱存儲(chǔ)結(jié)構(gòu)，考慮的是數(shù)據(jù)在計(jì)算機(jī)中是如何存儲(chǔ)和組織的基本概念數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)元素之間的邏輯關(guān)系通?？煞譃?類基本的邏輯結(jié)構(gòu) 1. 集合 結(jié)構(gòu)中的數(shù)據(jù)元素之中同屬一個(gè)集合 2. 線性結(jié)構(gòu) 結(jié)構(gòu)中的元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系 3. 樹型結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)多個(gè)的關(guān)系 4. 圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu) 結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多個(gè)對(duì)多個(gè)的關(guān)系邏輯結(jié)構(gòu)例 學(xué)生選課問題 該問題可以用三張數(shù)據(jù)表來表示，每張表中每條記錄為數(shù)據(jù)元素 如表中數(shù)據(jù)元素是無序的，則數(shù)據(jù)表構(gòu)成集合結(jié)構(gòu) 如表中數(shù)據(jù)元素是有序的，則數(shù)據(jù)表構(gòu)成線性結(jié)構(gòu)學(xué)生表課程

4、表選課表學(xué)號(hào)姓名課程號(hào)課程名稱學(xué)號(hào)課程號(hào)成績(jī)S0001張三C0001數(shù)據(jù)結(jié)構(gòu)S0001C000185S0002李四C0002操作系統(tǒng)S0001C000376S0005王五C0003編譯原理S0002C000190C0004數(shù)據(jù)庫原理S0002C000483S0003 C000292邏輯結(jié)構(gòu)例 三維實(shí)體造型問題 左圖的機(jī)械零件可以分解成三個(gè)基本的實(shí)體模型通過布爾運(yùn)算+和-操作得到 右圖構(gòu)成了一個(gè)樹型的數(shù)據(jù)結(jié)構(gòu)，每一個(gè)節(jié)點(diǎn)為一個(gè)基本實(shí)體模型或通過布爾運(yùn)算得到的復(fù)合實(shí)體模型邏輯結(jié)構(gòu)例 地圖表示問題 左圖的地圖經(jīng)抽象可以得到右圖的結(jié)構(gòu) 右圖構(gòu)成了圖狀的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 邏輯結(jié)構(gòu)在

5、存儲(chǔ)器中的映象 “數(shù)據(jù)元素”如何映象 ？ “關(guān)系”如何映象 ？數(shù)據(jù)的物理結(jié)構(gòu) 數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)部實(shí)際存儲(chǔ)時(shí)，根據(jù)各數(shù)據(jù)元素之間相對(duì)的存儲(chǔ)位置及相互之間的關(guān)系，存在著兩種存儲(chǔ)結(jié)構(gòu) 順序存儲(chǔ)結(jié)構(gòu) 在存儲(chǔ)器中，數(shù)據(jù)元素是依次存放的，數(shù)據(jù)元素在物理存儲(chǔ)器上的位置關(guān)系體現(xiàn)了它們?cè)谶壿嬌系捻樞蜿P(guān)系 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 在存儲(chǔ)器中，數(shù)據(jù)元素是分散存放的，在一個(gè)數(shù)據(jù)元素中，必須有一個(gè)或若干專門的數(shù)據(jù)項(xiàng)來指示其他相關(guān)聯(lián)的數(shù)據(jù)元素在存儲(chǔ)器中的位置數(shù)據(jù)的物理結(jié)構(gòu) 分別用順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)來存儲(chǔ)數(shù)列“10,20,30,40”數(shù)列的順序存儲(chǔ)結(jié)構(gòu)數(shù)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu) 鏈?zhǔn)接诚笮枰靡粋€(gè)附加信息指示下一元素的存儲(chǔ)位

6、置基本概念數(shù)據(jù)類型 數(shù)據(jù)類型在用高級(jí)程序語言編寫的程序中，必須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式，明確說明它們所屬的數(shù)據(jù)類型?；靖拍顢?shù)據(jù)類型（C+為例） 基本數(shù)據(jù)類型 字符（char）、整數(shù)（int）、浮點(diǎn)數(shù)（float/double）、指針（*）、引用（&） 復(fù)雜數(shù)據(jù)類型 數(shù)組（）、結(jié)構(gòu)（struct）、枚舉（enum）、類（class）、聯(lián)合（union） 不同類型的變量，其所能取的值的范圍不同， 所能進(jìn)行的操作不同?；靖拍顢?shù)據(jù)類型 數(shù)據(jù)類型 是一個(gè) 值的集合和定義在此集合上 的一組操作的總稱?；靖拍畛橄髷?shù)據(jù)類型 在軟件系統(tǒng)開發(fā)的全過程中，對(duì)客觀現(xiàn)實(shí)中存在的事物，存在三個(gè)觀

7、察層面 應(yīng)用層是用戶通過物理觀察得到的客觀事物的視圖，是可以用自然語言描述的，或用圖形、圖像、音頻、視頻等物理量表達(dá)的在概念層次上的數(shù)據(jù)。 邏輯層（抽象層）是從應(yīng)用層次抽象出來的數(shù)據(jù)視圖，利用抽象數(shù)據(jù)類型進(jìn)行形式化描述。 實(shí)現(xiàn)層明確地表示出了數(shù)據(jù)的組織與存儲(chǔ)結(jié)構(gòu)，并用某種具體的程序設(shè)計(jì)語言進(jìn)行代碼實(shí)現(xiàn)?；靖拍畛橄髷?shù)據(jù)類型 抽象數(shù)據(jù)類型（ADT，Abstract Data Type） 是與具體計(jì)算機(jī)內(nèi)部表示和實(shí)現(xiàn)方式無關(guān)的數(shù)據(jù)類型 是由一個(gè)邏輯上的數(shù)學(xué)模型以及定義在該模型上的一組操作構(gòu)成 可以用三元組定義 (D, S, P) D是數(shù)據(jù)對(duì)象 S是D上的關(guān)系集 P是對(duì)D的基本操作集 抽象數(shù)據(jù)類型和

8、數(shù)據(jù)類型實(shí)際上是一個(gè)概念基本概念抽象數(shù)據(jù)類型 ADT 有兩個(gè)重要特征: 一、數(shù)據(jù)抽象 用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。 二、數(shù)據(jù)封裝 將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。抽象數(shù)據(jù)類型例 ADT Set/ 集合的抽象數(shù)據(jù)類型 數(shù)據(jù)對(duì)象：D ai | aiElemType, i= 1, 2, ., n, n 0 數(shù)據(jù)關(guān)系：R = aiaj | ai,ajD 基本操作：Init() 操作結(jié)果：構(gòu)造一個(gè)空的集合。Destroy()操作結(jié)果：銷毀集合。IsEmpty() 操作結(jié)果：判斷集

9、合是否為空，如為空，則返回TRUE；否則返回FALSE。 Insert(e)操作結(jié)果：在集合中加入一個(gè)元素。如元素已存在，返回FALSE；否則返回TRUE。 Remove(e) 操作結(jié)果：在集合中移除一個(gè)元素。如元素存在，則返回TRUE；否則返回FALSE。 IsMember(e) 操作結(jié)果：判斷在集合中是否存在元素。FindFirst(&e)操作結(jié)果：找到集合中的第一個(gè)元素。如成功，返回TRUE；如果集合為空，返回FALSE抽象數(shù)據(jù)類型例 FindFirst(&e)操作結(jié)果：找到集合中的第一個(gè)元素。如成功，返回TRUE；如果集合為空，返回FALSEFindNext(&

10、e) 初始條件：已經(jīng)執(zhí)行過FindFirst或FindNext操作 操作結(jié)果：在上一次查找的前提下，找到集合中的下一個(gè)元素；如成功，返回TRUE；如上次查找已到最后一個(gè)元素，返回FALSE。 Union(s)操作結(jié)果：與另一個(gè)集合s做并運(yùn)算，返回并集。Intersection(s)操作結(jié)果：與另一個(gè)集合s做交運(yùn)算，返回交集。Difference(s)操作結(jié)果：與另一個(gè)集合s做差運(yùn)算，返回差集。二、算法與算法分析 程序 為計(jì)算機(jī)處理問題編制一組指令集 算法 處理問題的策略 數(shù)據(jù)結(jié)構(gòu) 問題的數(shù)學(xué)模型Algorithm + Data Structures = Programs算法 + 數(shù)據(jù)結(jié)構(gòu) =

11、程序 - Niklaus Wirth算法 算法（algorithm） 解決某一特定問題的具體步驟的描述，是指令的有限序列 算法的五個(gè)重要特征 有窮性 確定性 可行性 輸入 輸出算法 1有窮性 對(duì)于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成。 2確定性 對(duì)于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑。算法 3可行性 算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之。 4有輸入 作為算法加工對(duì)象的量值，通常體現(xiàn)為算法中的一組變量

12、。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實(shí)際上已被嵌入算法之中。 5有輸出 它是一組與“輸入”有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。 算法 算法設(shè)計(jì)的原則 設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)： 1正確性 2. 可讀性 3健壯性 4高效率與低存儲(chǔ)量需求 算法的性能分析與度量 算法性能的度量方法 事后測(cè)試 可采用一些程序運(yùn)行性能跟蹤與測(cè)量工具（如Profiler） 預(yù)先評(píng)做 不考慮算法的實(shí)現(xiàn)語言、編譯器、運(yùn)行的硬件平臺(tái)，只考慮在一定問題規(guī)模下算法運(yùn)行的時(shí)間復(fù)雜度和空間復(fù)雜度 性能度量 時(shí)間復(fù)雜度 按某種算法設(shè)計(jì)的程序在計(jì)算機(jī)上執(zhí)行

13、時(shí)花費(fèi)的CPU時(shí)間的度量 空間復(fù)雜度 按某種算法設(shè)計(jì)的程序在計(jì)算機(jī)上執(zhí)行時(shí)需要使用的存儲(chǔ)空間的度量 算法的性能分析與度量 和算法執(zhí)行時(shí)間相關(guān)的因素： 1算法選用的策略 2問題的規(guī)模 3編寫程序的語言 4編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量 5計(jì)算機(jī)執(zhí)行指令的速度 算法的性能分析與度量 一個(gè)特定算法的“運(yùn)行工作量” 的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)。 算法的性能分析與度量 算法 = 控制結(jié)構(gòu) + 原操作 （固有數(shù)據(jù)類型的操作） 算法的執(zhí)行時(shí)間 = 原操作(i)的執(zhí)行次數(shù)原操作(i)的執(zhí)行時(shí)間 算法的性能分析與度量 時(shí)間的復(fù)雜度 從算法中選取對(duì)于所處理問題來說是

14、關(guān)鍵步驟的程序語句作為基本操作，該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間量度。 基本操作重復(fù)執(zhí)行的次數(shù)一般為問題規(guī)模n的某個(gè)函數(shù)f(n)，因此時(shí)間的復(fù)雜度T(n)記作T (n) = O( f (n) ) 上式表示隨著問題規(guī)模n的增長(zhǎng)，算法執(zhí)行時(shí)間T(n)和f(n)同比增長(zhǎng)時(shí)間復(fù)雜度例 語句+x為三個(gè)算法的基本操作，問題規(guī)模為n 三段程序中基本操作的執(zhí)行次數(shù)分別為1、n和n2 故三段程序的時(shí)間復(fù)雜度分別為O(1)、O (n)和O (n2)，稱為常量階、線性階和平方階/ 例1 +x;/基本操作 s = 0;/ 例2for (i = 0; i n; +i) +x;/基本操作 s += x;/ 例3fo

15、r (i = 0; i n; +i) for (j = 0; j n; +j) +x;/基本操作 s += x; 時(shí)間復(fù)雜度例 語句+x為算法的基本操作 算法中基本操作的執(zhí)行次數(shù)是0 + 1 + . + (n 2) = (n 1) (n 2) / 2 上式中隨著n的增長(zhǎng)，增長(zhǎng)率最快的項(xiàng)是n2 ，故該算法的時(shí)間復(fù)雜度分別為O (n2)/ 例4for (i = 2; i = n; +i) for (j = 2; j = i - 1; +j) +x;/基本操作 s += x; 時(shí)間復(fù)雜度例 例例: 兩個(gè)矩陣相乘兩個(gè)矩陣相乘void mult(int a, int b, int& c ) /

16、以二維數(shù)組存儲(chǔ)矩陣元素，c 為 a 和 b 的乘積 for (i=1; i=n; +i) for (j=1; j=n; +j) ci,j = 0; for (k=1; k=n; +k) ci,j += ai,k*bk,j; /for /mult基本操作: 乘法乘法操作時(shí)間復(fù)雜度: O(n3)時(shí)間復(fù)雜度例 例例: 選擇排序選擇排序void select_sort(int& a, int n) / 將將 a 中整數(shù)序列重新排列成自小至大有序的整數(shù)序列中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。for ( i = 0; i n-1; +i ) j = i ;/ 選擇第選擇第 i i 個(gè)最小元

17、素個(gè)最小元素 for ( k = i+1; k n; +k ) if (ak aj ) j = k; if ( j != i ) aj ai / select_sort基本操作:比較比較(數(shù)據(jù)元素)操作操作時(shí)間復(fù)雜度: O(n2)算法的性能分析與度量算法的空間復(fù)雜度 算法的存儲(chǔ)量包括: 1輸入數(shù)據(jù)所占空間 2程序本身所占空間 3輔助變量所占空間算法的空間復(fù)雜度 若輸入數(shù)據(jù)所占空間只取決于問題本身， 和算法無關(guān)，則只需要分析除輸入和程序 之外的輔助變量所占額外空間。 若所需額外空間相對(duì)于輸入數(shù)據(jù)量來說 是常數(shù)，則稱此算法為原地工作。 若所需存儲(chǔ)量依賴于特定的輸入，則通 常按最壞情況考慮。算法的空

18、間復(fù)雜度 空間的復(fù)雜度 根據(jù)問題規(guī)模n，算法執(zhí)行所需要的額外存儲(chǔ)空間大小的量度 空間的復(fù)雜度S(n)記作S (n) = O( f (n) )描述算法的語言 。一個(gè)算法可以采用多種表述方式，比如，人類的自然語言可以用來表述算法，但在很多情況下，算法描述更多地采用一些形式化方法。程序流程圖就是一種形式化的算法描述，還可能采用判定表、判定樹及狀態(tài)轉(zhuǎn)移圖等多種方式。一種廣泛使用的形式化算法描述方法，就是參照某種程序設(shè)計(jì)語言，設(shè)計(jì)出一種算法描述語言。算法描述語言和程序設(shè)計(jì)語言比較類似，但沒有嚴(yán)格的語法規(guī)則，甚至可以在其中加入一些自然語言描述。有了用算法描述語言描述的算法，可以很容易地轉(zhuǎn)換成實(shí)際可運(yùn)行的程序。描述算法的語言 選擇選擇C+語言描述算法語言描述算法 本教材另一個(gè)特點(diǎn)是將面向?qū)ο蟮姆椒ㄒ氲綌?shù)據(jù)結(jié)構(gòu)領(lǐng)域。面向?qū)ο蠹夹g(shù)不僅是一種程序設(shè)計(jì)方法學(xué)，而且是一種認(rèn)識(shí)方法學(xué)，數(shù)據(jù)結(jié)構(gòu)討論的正是數(shù)據(jù)的描述與處理，與面向?qū)ο蟮恼J(rèn)知方法具有天然的聯(lián)系。面向?qū)ο蟪绦蛟O(shè)計(jì)語言提供的封裝、繼承、多態(tài)和泛型程序設(shè)計(jì)等機(jī)