數(shù)據(jù)結(jié)構(gòu)基本概念.ppt

數(shù)據(jù)結(jié)構(gòu) DATA STRUCTURE, 用C描述,第一章 基本概念,什么是數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)的抽象層次 算法定義 性能分析與度量,“學生”表格,初等項：如學生性別、籍貫等，不能再分割的最小數(shù)據(jù)單位。 組合項：如一組成績，可以再劃分為物理成績、化學成績等更小的項。,選課關(guān)系包含如下信息 學號 課程編號 成績 學生選課系統(tǒng)中實體構(gòu)成的網(wǎng)狀關(guān)系,UNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖,在應用程序中涉及到各種各樣的數(shù)據(jù)，為了存儲它們，組織它們，需要討論它們的歸類及它們之間的關(guān)系，從而建立相應的數(shù)據(jù)結(jié)構(gòu)，并依此實現(xiàn)要求的軟件功能。,數(shù)據(jù)：信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計算機中，被計算機程序識別和處理的符號的集合。 數(shù)值性數(shù)據(jù) 如整數(shù)、實數(shù)、雙精度數(shù)等 主要用于工程和科學計算，及商業(yè)事務處理中使用。 非數(shù)值性數(shù)據(jù) 如字符串、多媒體信息（文字、圖形、語音）等。 數(shù)據(jù)對象：數(shù)據(jù)的子集。具有相同性質(zhì)的數(shù)據(jù)成員（數(shù)據(jù)元素）的集合。 整數(shù)數(shù)據(jù)對象 N = 0, 1, 2, 英文字母數(shù)據(jù)對象LETTER=A, B, , Z 學生數(shù)據(jù)對象,什么是數(shù)據(jù)結(jié)構(gòu)？,定義:一組數(shù)據(jù)對象及數(shù)據(jù)對象之間的關(guān)系組成。記為： Data_Structure = D, R 其中，D是數(shù)據(jù)對象的有限集合，R是該集合中所有數(shù)據(jù)對象之間的關(guān)系的有限集合。,n個網(wǎng)站之間的連通關(guān)系,以最小代價將n個網(wǎng)站連通 樹形關(guān)系,任一網(wǎng)站出現(xiàn)故障而整個網(wǎng)絡暢通 網(wǎng)狀關(guān)系,數(shù)據(jù)結(jié)構(gòu)的分類,根據(jù)數(shù)據(jù)對象之間的關(guān)系不同，分為兩大類： 線性結(jié)構(gòu) 非線性結(jié)構(gòu) 線性結(jié)構(gòu)中各個數(shù)據(jù)對象依次排列在一個線性序列中； 非線性結(jié)構(gòu)中各個數(shù)據(jù)對象不再保持在一個線性序列中，每個數(shù)據(jù)對象可能與零個或多個其它數(shù)據(jù)對象有某種特定的聯(lián)系。,根據(jù)考慮問題的角度不同，分為兩大類：邏輯結(jié)構(gòu) 物理結(jié)構(gòu) 邏輯結(jié)構(gòu)是指從解決問題出發(fā)，為實現(xiàn)必要的功能所建立的數(shù)據(jù)結(jié)構(gòu)，屬于用戶視圖，面向問題，根據(jù)問題所要實現(xiàn)的功能建立； 物理結(jié)構(gòu)是指數(shù)據(jù)應該如何在計算機中存放，是數(shù)據(jù)邏輯結(jié)構(gòu)的存儲方式，是屬于具體實現(xiàn)的視圖，面向計算機，根據(jù)問題所要求的響應速度、處理時間、修改時間、存儲空間和單位時間的處理量等建立。,抽象數(shù)據(jù)類型,數(shù)據(jù)類型 定義：一組性質(zhì)相同的值的集合, 以及定義于這個值集合上的一組操作的總稱. 由用戶定義，用以表示應用問題的數(shù)據(jù)模型，由基本的數(shù)據(jù)類型組成, 并包括一組相關(guān)的服務（或稱操作） 特征是使用與實現(xiàn)相分離，實行信息隱蔽和數(shù)據(jù)封裝。 在抽象數(shù)據(jù)類型設計時，把類型的聲明與其實現(xiàn)分離開來。,抽象數(shù)據(jù)類型,嚴格區(qū)分抽象數(shù)據(jù)類型的兩個不同視圖 從使用者角度 只要了解該抽象數(shù)據(jù)類型的規(guī)格說明，就可以利用其公共界面中的服務來使用這個類型，而不必關(guān)心其物理實現(xiàn)，這樣使用者可以在開發(fā)過程中抓住重點，集中精力考慮如何解決應用問題，使問題得到簡化。 從實現(xiàn)者角度 把抽象數(shù)據(jù)類型的物理實現(xiàn)封裝起來，有利于編碼、測試以及將來修改。因為這樣做可以使錯誤局部化，一旦出現(xiàn)錯誤，其傳播范圍不至于影響其它模塊。 如果為了提高效率希望改進數(shù)據(jù)結(jié)構(gòu)，可能需要改變抽象數(shù)據(jù)類型的物理實現(xiàn)，但只要界面中的服務的使用方式不變，其它所有使用該數(shù)據(jù)類型的程序都可以不變，從而大大提高系統(tǒng)穩(wěn)定性。,數(shù)據(jù)結(jié)構(gòu)的抽象層次,最高的數(shù)據(jù)抽象是一個聚集類，其作用是把所有的數(shù)據(jù)抽象關(guān)聯(lián)在一起，代表數(shù)據(jù)結(jié)構(gòu)，并給出數(shù)據(jù)結(jié)構(gòu)都具有的操作初始化(initial)、插入(insert)、刪除(delete)和查找(search)。,線性聚類線性表 類中所有數(shù)據(jù)成員都按某種次序排列在一個序列中。 根據(jù)對聚集中元素存取方法的不同： 直接存取類 數(shù)組、記錄、文件 直接存取某一指定項而不須先訪問其前驅(qū)。 順序存取類 棧、隊列、表 只能從序列中第一個元素起，按序逐個訪問到指定的元素。 廣義索引類 散列表、詞典 “關(guān)鍵碼值”偶對的集合。,非線性聚類 所有數(shù)據(jù)元素與其它數(shù)據(jù)元素之間不存在簡單的線性關(guān)系。 根據(jù)關(guān)系的不同： 層次聚集類 樹，二叉樹，堆 按層次劃分的數(shù)據(jù)元素的集合，指定層次上元素可以有零個或多個處于下一層次上的直接后繼。 群聚集類 集合，圖 所有元素之間沒有任何順序關(guān)系。,線性聚集類中各數(shù)據(jù)成員之間的線性關(guān)系,樹形結(jié)構(gòu),樹 二叉樹 二叉搜索樹,堆結(jié)構(gòu),“最大”堆 “最小”堆,群聚類,圖結(jié)構(gòu) 網(wǎng)絡結(jié)構(gòu),算法定義,定義：一個有窮的指令集，這些指令為解決某一特定任務規(guī)定了一個運算序列。 特性： 輸入 必須有0個或多個輸入，是算法開始運算前給于算法的量。 輸出 應有一個或多個輸出(處理結(jié)果)，輸出的量是算法計算的結(jié)果。 確定性 每步定義都是確切、無歧義的，對于每一種情況，需要執(zhí)行的動作都應嚴格地、清晰地規(guī)定。 有窮性 算法應在執(zhí)行有窮步后結(jié)束。 有效性 每一條運算應足夠基本，原則上能夠精確執(zhí)行，甚至人們僅用筆和紙做有限次運算就能完成。,事例學習：選擇排序問題 明確問題：非遞減排序 解決方案：逐個選擇最小數(shù)據(jù) 算法框架： for ( int i=0; in-1; i+ ) /n-1趟 從ai檢查到an-1; 若最小的整數(shù)在ak, 交換ai與ak; 細化程序：程序 SelectSort 如何選擇值最小的數(shù)據(jù)； 如何交換兩個數(shù)據(jù)的值。,算法設計 自頂向下，逐步求精,void selectSort ( int a , const int n ) /對n個整數(shù)a0,a1,an-1, 按非遞減順序排序 for ( int i=0; in-1; i+ ) int k = i; /從ai檢查到an-1, 找最小的整數(shù), 在ak for ( int j=i+1; jn; j+ ) if ( aj ak ) k = j; /k指示當前找到的最小整數(shù) int temp = ai; ai = ak; ak = temp; /交換ai與ak ,算法的性能分析與度量,算法的性能標準 算法的空間復雜性 算法的時間復雜性,算法的性能標準,數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣與算法直接有關(guān)，其性能由實現(xiàn)其各個服務的算法來體現(xiàn)。對數(shù)據(jù)結(jié)構(gòu)的分析實質(zhì)上是對實現(xiàn)其各個服務的算法的性能的分析。 判斷一個算法的優(yōu)劣的標準： 正確性最重要標準 要求算法能夠正確地執(zhí)行預先規(guī)定的功能和性能要求。 要求算法的編寫者對問題要求有正確的理解； 正確地、無歧義地描述和利用某種編程語言正確地實現(xiàn)對算法的要求。,可使用性用戶友好性 要求算法能夠很方便地使用。 為了便于用戶使用，要求算法具有良好的界面，完備的用戶文檔。 算法設計必須符合抽象數(shù)據(jù)類型和模塊化的要求； 最好所有的輸入和輸出數(shù)據(jù)都通過參數(shù)表顯示地傳遞，少用公共變量； 每一個算法只完成一個功能。,可讀性 算法應當可讀，是理解、測試和修改算法的需要。 為了達到這一要求，算法邏輯必須清晰、簡單和結(jié)構(gòu)化： 所有的變量名、函數(shù)名的命名必須有實際含義，讓人見名知義； 在算法中必須加入注釋，簡要說明： 算法的功能； 輸入與輸出參數(shù)的使用規(guī)則； 重要數(shù)據(jù)的作用； 算法中各程序段完成的功能等。,效率 算法執(zhí)行時計算機資源的消耗，包括存儲（空間代價）和運行時間（時間代價）的開銷。 與多種因素有關(guān)： 計算機系統(tǒng)、可用存儲容量和算法復雜性。 健壯性容錯性或例外處理 要求在算法中加入對輸入?yún)?shù)、打開文件、讀文件記錄、子程序調(diào)用狀態(tài)進行自動檢錯、報錯并通過與用戶對話來糾錯的功能。 一個算法必須具有健壯性，能夠?qū)Σ缓侠淼臄?shù)據(jù)進行檢查。 在算法初寫時可暫不管，待算法成熟時再追加。,算法的運行時間依賴于所使用的計算機系統(tǒng)、編譯器、可用存儲空間大小等。 同樣的算法在速度不同的計算機上，執(zhí)行速度相差非常大。 算法用不同的編譯器編譯出的目標代碼不一樣長，完成同樣功能所需時間不同。 如果可用存儲空間不夠，算法需要的運行時間很多；如果空間足夠大，則時間明顯減少。 通過比較算法的復雜性來評價。 算法復雜性與具體運行環(huán)境和編譯器無關(guān)。,空間復雜性(Space Complexity) 當問題的規(guī)模以某種單位從1增加到n時，解決這個問題的算法在執(zhí)行時所占的存儲空間也以某種單位由1增加到f(n)。 問題的規(guī)?？梢詮膯栴}的描述中找到。 因為算法針對某一實例（類的對象），問題規(guī)模可視為實例的特性。 在有n個記錄的學生文件中查找某個學生，或者對一個n階線性方程求解，n即為問題的規(guī)模。 空間單位一般規(guī)定為一個工作單元所占的存儲空間的大小。,空間復雜性度量,存儲空間的固定部分 主要包括程序指令代碼的空間，常數(shù)、簡單變量、定長成分(如數(shù)組元素、結(jié)構(gòu)成分等)變量所占的空間等，屬靜態(tài)空間，只要做簡單的統(tǒng)計就可估算。 可變部分 主要包括尺寸與實例特性有關(guān)的成分變量所占空間、引用變量所占空間、以及遞歸棧所用的空間，還有在算法運行過程中通過動態(tài)分配和動態(tài)刪除動態(tài)使用的內(nèi)存空間。,時間復雜性和度量,編譯時間 與編譯程序有關(guān)，與實例特性無關(guān)。 運行時間 從程序結(jié)構(gòu)著手，統(tǒng)計算法的程序步數(shù)。 語法上或語義上有意義的一段指令序列 執(zhí)行時間與實例特性無關(guān) 程序步數(shù)舉例： 注 釋：0 聲明語句：0 表達式：1 賦值語句：0,例 以迭代方式求累加和的函數(shù) 行 float sum ( float a , const int n ) 1 2 float s = 0.0; 3 for ( int i=0; in; i+ ) 4 s += ai; 5 return s; 6 ,程序步確定方法 在程序中插入計數(shù)全局變量count； 建表，列出程序內(nèi)各個語句的程序步數(shù)。,在求累加和程序中加入count語句 float sum ( float a , const int n ) float s = 0.0; count+; /count是全局變量，統(tǒng)計執(zhí)行語句條數(shù) for ( int i=0; in; i+ ) count+; /針對for語句 s += ai; count+; /針對賦值語句 count+; /針對for的最后一次 count+; /針對return語句 return s; 執(zhí)行結(jié)束得 程序步數(shù)count =2 * n + 3,程序的簡化形式 void sum ( float a , const int n ) for ( int i=0; in; i+ ) count += 2; count += 3; ,注意： 一個語句本身的程序步數(shù)可能不等于該語句一次執(zhí)行所具有的程序步數(shù)。 例如：賦值語句 x = sum (R, n); 本身的程序步數(shù)為1； 一次執(zhí)行對函數(shù) sum (R, n) 的調(diào)用需要的程序步數(shù)為 2*n+3； 一次執(zhí)行的程序步數(shù)為 1+2*n+3 = 2*n+4,時間復雜性的漸進表示法,全面分析一個算法，需要考慮在最壞、最好、平均情況下的時間代價。 大O表示法最壞情況 當且僅當存在正整數(shù)c和n0，使得T(n)cf(n)對所有的nn0成立，則稱該算法的漸進時間復雜度為T(n)=O(f(n)。 當實例特性n充分大時，算法的時間復雜度隨n變化，在最壞情況下若存在一個增長的上界，即cf(n) ，則該算法的時間復雜度增長的數(shù)量級為f(n) ，即稱該算法的漸進時間復雜度為T(n)=O(f(n)。,大O表示法的使用 需要考慮關(guān)鍵操作的程序步數(shù)； 關(guān)鍵操作大多在循環(huán)和遞歸中； 在大多數(shù)場合中，程序步驟與執(zhí)行頻度一一對應。 如果給出的是漸進值，可直接考慮關(guān)鍵操作的執(zhí)行頻度，提出其與實例特性n的函數(shù)關(guān)系g(n)，從而得到漸進時間復雜度。 漸進時間復雜度的計算 單個循環(huán) 在循環(huán)內(nèi)的簡單語句即為關(guān)鍵操作，該程序段的漸進時間復雜度應是此關(guān)鍵操作的執(zhí)行頻度的大O表示。,幾個并列的循環(huán) 先分析每個循環(huán)的漸進時間復雜度，然后利用大O表示法的加法規(guī)則來計算漸進時間復雜度。 大O表示法的加法規(guī)則 當兩個并列的程序段的時間代價分別為T1(n)=O(f(n)和T2(m)=O(g(m)時， 則將兩個程序段連在一起后整個程序段的時間代價為： T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m) 所謂(max (f (n), g (m)，是指當n與m充分大時f (n)與g (m)中的大值，具有如下關(guān)系： c log2n n nlog2n n2 n3 2n 3n n! 取c、log2n、n、nlog2n時間效率比較高； 取n2、n3時間效率差強人意； 取2n、3n、n!當n稍微大一點，算法的時間代價變?yōu)楹艽螅灾劣诓荒苡嬎恪?兩個并列循環(huán)的例子 void example (float x , int m, int n, int k) float sum ; for ( int i=0; im; i+ ) /x 中各行 sumi = 0.0; /數(shù)據(jù)累加 for ( int j=0; jn; j+ ) sumi += xij; /關(guān)鍵操作1，漸進時間復雜度為O(m*n)。 for ( i = 0; i m; i+ ) /打印各行數(shù)據(jù)和 printf( “ Line %d :%dn “, i, sum i); /關(guān)鍵操作2，漸進時間復雜度為O(m)。 /根據(jù)大o表示法的加法規(guī)則，漸進