1、數據結構數據結構主講教師：賈海洋主講教師：賈海洋教學計劃n第一章 緒論n第二章 線性表、堆棧和隊列n第三章 數組和字符串n第六章 遞歸n第四章 樹n第五章 圖n第七章 排序n第八章 查找答疑和上機時間n答疑q課后+郵件n上機實驗（5分制：平時成績 + 上機考試）q第5-12周（共八次，使用VC+環境）q周三 5-8節節q計算機樓實驗室計算機樓實驗室 A211為什么要學習數據結構為什么要學習數據結構n在計算機科學中是一門綜合性的在計算機科學中是一門綜合性的專業基礎課專業基礎課。n不僅是一般程序設計的基礎，而且是編譯原理、不僅是一般程序設計的基礎，而且是編譯原理、操作系統、數據庫系統及其他專業課的

2、重要基操作系統、數據庫系統及其他專業課的重要基礎礎n數據結構課程的目的就是從對問題抽象和求解數據結構課程的目的就是從對問題抽象和求解的角度來介紹常用的數據結構，闡明其內在的角度來介紹常用的數據結構，闡明其內在邏邏輯關系輯關系，在計算機中的，在計算機中的存儲表示存儲表示，以及刻畫施，以及刻畫施加于其上之加于其上之各種操作的算法各種操作的算法第一章第一章 緒論緒論n1.2數據結構概念數據結構概念n1.3算 法n1.4算法的正確性證明n1.5算法分析基礎數據結構的發展歷史n20世紀40年代，電子計算機剛剛誕生q處理處理純數值性的信息純數值性的信息，稱為，稱為數值計算數值計算30噸！170m2！!數據

3、結構的發展歷史n20世紀40年代：處理純數值性的信息純數值性的信息n20世紀50年代末q計算機大量應用于解決非數值計算非數值計算問題q從簡單的數值發展到復雜數據復雜數據q各種高級程序設計語言高級程序設計語言的出現（1951 FORTRAN）q產生了數組、記錄、串和層次表結構等新的數據結構新的數據結構數據結構的發展歷史n20世紀40年代：處理純數值性的信息純數值性的信息n20世紀50年代末：解決非數值計算問題非數值計算問題n20世紀60年代q美國計算機界出現了“信息結構”的概念（據結構概念的前身）1968年，“數據結構”列為一門獨立的課程獨立的課程q著名計算機科學家克努斯（D. E. Knuth

4、）陸續出版了包括基本算法、半數值算法和排序和查找等三卷的曠世之作計算機程序設計技巧計算機程序設計技巧(The Art of Computer Programming)/uno//uno/1974年，因其在算法分析和編程語言設計方面年，因其在算法分析和編程語言設計方面的突出貢獻，的突出貢獻，榮獲美國計算機協會圖靈獎，是榮獲美國計算機協會圖靈獎，是歷史上最年輕的獲獎者歷史上最年輕的獲獎者。圖靈獎被稱為計算機。圖靈獎被稱為計算機界的諾貝爾獎。界的諾貝爾獎。計算機程序設計

5、藝術計算機程序設計藝術一書一書與牛頓的與牛頓的自然哲學的數學原理自然哲學的數學原理等書一起，等書一起，被評為被評為“世界歷史上最偉大的十種科學著作世界歷史上最偉大的十種科學著作”之一。之一。他的所有著作都有個奇特他的所有著作都有個奇特“附加效應附加效應”，那，那就是任何人發現書中的錯誤，就是任何人發現書中的錯誤，不論是技術上不論是技術上的或是排版上的還是歷史上的錯誤，都可以的或是排版上的還是歷史上的錯誤，都可以向他指出，并可領取向他指出，并可領取2.56美元！美元！數據結構的發展歷史n1972年，著名計算機科學家霍爾（C. A. R. Hoare）在其論文“數據結構札記”中，澄清了關于數據結構

6、術語和概念等方面的雜亂局面，并深刻論述了算法與數據結構密不可分的算法與數據結構密不可分的關系關系；n1976年，著名計算機科學家沃思（N. Wirth）出版了名為算法數據結構程序算法數據結構程序的專著，不僅形象地描述了數據結構、算法與程序之間的關系，還旗幟鮮明的提出數據結構和算法對程序設計的重要性。數據結構的發展歷史n20世紀40年代：處理純數值性的信息純數值性的信息n20世紀50年代末：解決非數值計算問題非數值計算問題n20世紀60年代：數據結構列為一門獨立的課程獨立的課程n20世紀70年代后期：隨著數據庫技術的成功應用，數據結構相應地增加了文件組織、存儲和管理文件組織、存儲和管理等方面的內

7、容。n20世紀80年代，隨著面向對象概念和面向對象技術的興起，數據結構增加了抽象數據類型抽象數據類型等概念數數 據據 結結 構構數數 據據 結結 構構 0101 韓韓 冬冬 0505 楊楊 帆帆 0303 劉禹伯劉禹伯 0404 孫曉東孫曉東 0202 馮馮 明明 0606 遲克遜遲克遜 0909 張原沫張原沫 0707 陸靜雅陸靜雅 0808 薛薛 楊楊 1010 張張 雷雷 n什么是數據？數據n數據是人們利用文字符號、數字符號以及其他規定的符號對現實世界的事物及其活動所做的描述。在計算機科學中，數據的含義非常廣泛，我們把一切能夠輸入到計算機中并被計算機程序處理的信息，包括文字、表格、圖象等

8、，都稱為數據數據。數據元素(元素、結點、頂點、Data Element )n數據元素數據元素是組成數據的是組成數據的基本單位基本單位。在程序中。在程序中通常把結點作為一個整體進行考慮和處理。通常把結點作為一個整體進行考慮和處理。學號學號姓名姓名5308010153080101韓冬韓冬5308010253080102馮明馮明5308010353080103劉禹伯劉禹伯5308010453080104孫曉東孫曉東5308010553080105楊帆楊帆5308010653080106遲克遜遲克遜5308010753080107陸靜雅陸靜雅53080105 53080105 楊帆楊帆每一行（代表一個

9、同學每一行（代表一個同學）作為一個基本單位來考作為一個基本單位來考慮。慮。數據項n一般情況下，一個數據元素含有若干個一般情況下，一個數據元素含有若干個數據項數據項, ,數據項是構成數據的最小單位。數據項是構成數據的最小單位。n每個數據元素都有學號、姓名這兩個數據項構每個數據元素都有學號、姓名這兩個數據項構成。成。數數 據據 結結 構構什么是結構？HHNNNNNH H N N N N N分子結構什么是結構nAGCT GACT GCAT AGCT ACGT TAGCnDNA的結構的結構：DNA雙螺旋模型數據數據+結構結構學號學號姓名姓名5308010153080101韓冬韓冬53080102530

10、80102馮明馮明5308010353080103劉禹伯劉禹伯5308010453080104孫曉東孫曉東5308010553080105楊帆楊帆5308010653080106遲克遜遲克遜5308010753080107陸靜雅陸靜雅5308010853080108薛楊薛楊5308010953080109張原沫張原沫5308011053080110張雷張雷線性結構非線性結構數據的邏輯結構邏輯結構01韓冬02馮明03劉禹伯04孫曉東05楊帆長春市四平市吉林省遼寧省沈陽市大連市中國線性結構數據的存儲結構存儲結構/物理結構物理結構n數組n鏈表01韓冬02馮明03劉禹伯04孫曉東05楊帆01韓冬02馮

11、明03劉禹伯04孫曉東05楊帆數據上的運算集合n查找q尋找1班學號為20的同學姓名q查找所有1班姓王的同學n排序q將8班同學按照姓名拼音排序q按照專業課總成績排名數據結構的組成：n數據的邏輯結構數據的邏輯結構n數據的存儲結構數據的存儲結構n數據上施加的操作數據上施加的操作邏輯結構n數據元素之間的邏輯關系稱為數據的邏輯結構。數據元素之間的邏輯關系稱為數據的邏輯結構。n邏輯結構的形式化表示邏輯結構的形式化表示邏輯結構表示為二元組邏輯結構表示為二元組 L=(N, R)，其中，其中N(L)是結點的有限集合，是結點的有限集合， R(L)是是N上的關系集合。上的關系集合。一般地，一般地，R=r。邏輯結構

12、L=(N,R)， N=a, b, c, d, e , R=r， r=aecdb邏輯結構 L=(N,R)， N=a, b, c, d, e , R=r， r=, , , a b c d e L=(N,R)， N=k1，k2，k9 R=r，r=， ， ， ， ， ， ，k1k2k3k4k7k8k5k6k9邏邏輯輯結結構構集合集合線性線性樹樹圖圖邏輯結構的分類邏輯結構的分類線性結構線性結構 結構中有且僅有一個結構中有且僅有一個始結點始結點和一個和一個終結點終結點，始結點只有一個，始結點只有一個后繼結點后繼結點，終結，終結點只有一個點只有一個前趨結點前趨結點，每個，每個內結點內結點有且僅有且僅有一個前

13、趨結點和一個后繼結點。有一個前趨結點和一個后繼結點。非線性結構（樹、圖）非線性結構（樹、圖）結構中的結點可能有多個前趨結點結構中的結點可能有多個前趨結點和多個后繼結點。和多個后繼結點。數據結構的組成：n數據的邏輯結構數據的邏輯結構n數據的存儲結構數據的存儲結構n數據上施加的操作數據上施加的操作存儲結構存儲結構v是指數據的邏輯結構在計算機中所需的存儲是指數據的邏輯結構在計算機中所需的存儲空間、空間的構成結構及對該存儲結構的訪空間、空間的構成結構及對該存儲結構的訪問方式等的總稱問方式等的總稱v數據的存儲結構是建立一種數據的存儲結構是建立一種由邏輯結構到存由邏輯結構到存儲結構的映射儲結構的映射：v建

14、立結點集合建立結點集合 N N 到存儲區域到存儲區域 M M 的映射：的映射：N-MN-M，中，中每個結點每個結點j jN N都對應唯一的連續存儲單元都對應唯一的連續存儲單元c cM Mv對于每一個關系元組對于每一個關系元組(a(a，b)b) r r，映射為存儲單元，映射為存儲單元的地址順序關系（或指針的地址指向關系）的地址順序關系（或指針的地址指向關系）存儲結構存儲結構v是指數據的邏輯結構在計算機中所需的存儲是指數據的邏輯結構在計算機中所需的存儲空間、空間的構成結構及對該存儲結構的訪空間、空間的構成結構及對該存儲結構的訪問方式等的總稱問方式等的總稱v數據的存儲結構是建立一種數據的存儲結構是建

15、立一種由邏輯結構到存由邏輯結構到存儲結構的映射儲結構的映射：01韓冬02馮明03劉禹伯04孫曉東05楊帆01韓冬02馮明03劉禹伯04孫曉東05楊帆學號學號姓名姓名5308010153080101韓冬韓冬5308010253080102馮明馮明5308010353080103劉禹伯劉禹伯5308010453080104孫曉東孫曉東5308010553080105楊帆楊帆存儲結構存儲結構v是指數據的邏輯結構在計算機中所需的存儲是指數據的邏輯結構在計算機中所需的存儲空間、空間的構成結構及對該存儲結構的訪空間、空間的構成結構及對該存儲結構的訪問方式等的總稱問方式等的總稱v數據的存儲結構是建立一種數據

16、的存儲結構是建立一種由邏輯結構到存由邏輯結構到存儲結構的映射儲結構的映射：v順序、鏈接、索引和散列四種方法順序、鏈接、索引和散列四種方法數據結構的組成：n數據的邏輯結構數據的邏輯結構n數據的存儲結構數據的存儲結構n數據上施加的操作數據上施加的操作對數據結構的操作n幾種數據結構上的常用的操作：查找、插入、幾種數據結構上的常用的操作：查找、插入、刪除、合并、排序、統計以及簡單計算等的操刪除、合并、排序、統計以及簡單計算等的操作過程。作過程。n查找查找q尋找尋找1班學號為班學號為20的同學姓名的同學姓名q查找所有查找所有1班姓王的同學班姓王的同學n排序排序q將將8班同學按照姓名拼音排序班同學按照姓名

17、拼音排序q按照專業課總成績排名按照專業課總成績排名數據結構數據結構研究的主要問題：研究的主要問題：1.按某種邏輯關系將一批數據元按某種邏輯關系將一批數據元素組織起來；素組織起來；2.按一定的存儲方式把它們存儲按一定的存儲方式把它們存儲起來；起來；3.在數據上定義需要施加的操作。在數據上定義需要施加的操作。第一章第一章 緒論緒論n1.2數據結構概念n1.3算算 法法n1.4算法的正確性證明n1.5算法分析基礎n計算機解決一個具體問題時，大致需要經過下列計算機解決一個具體問題時，大致需要經過下列幾個步驟：幾個步驟：q首先要從具體問題中抽象出一個適當的首先要從具體問題中抽象出一個適當的數學模型數學模

18、型q然后設計一個解此數學模型的然后設計一個解此數學模型的算法算法(Algorithm(Algorithm）q最后編出最后編出程序程序、進行測試、調整直至得到最終解答、進行測試、調整直至得到最終解答n算法就是一個算法就是一個有窮規則的集合有窮規則的集合，其中的規則規定了一個解，其中的規則規定了一個解決某一特定類型問題的運算序列；決某一特定類型問題的運算序列；算法有如下算法有如下5 5個特性：個特性： (1)(1)有限性：有限性：當執行一個算法時，不論是何種情況，在經過當執行一個算法時，不論是何種情況，在經過了有限步驟后，這個算法一定要終止。了有限步驟后，這個算法一定要終止。 (2)(2)確定性：

19、確定性：算法中的每條指令都必須是清楚的，指令無二算法中的每條指令都必須是清楚的，指令無二義性。義性。 (3)(3)輸入：輸入：具有具有0 0個或個或0 0個以上由外界提供的量。個以上由外界提供的量。 (4)(4)輸出：輸出：產生產生1 1個或多個結果。個或多個結果。 (5)(5)可行性：可行性：每條指令都十分基本，原則上可由人僅用筆和每條指令都十分基本，原則上可由人僅用筆和紙在有限的時間內也能完成。紙在有限的時間內也能完成。 注意：算法和程序是有區別的，程序未必能滿足動態有注意：算法和程序是有區別的，程序未必能滿足動態有 窮。窮。 1.計算機處理問題，以適當的數據結構為基礎，制定出計算機處理問

20、題，以適當的數據結構為基礎，制定出的切實可行的方法和步驟的切實可行的方法和步驟計算機算法計算機算法。1976年，沃斯提出：年，沃斯提出： 算法算法+數據結構數據結構=程序程序(Algorithm + Data Structures = Programs) 算法描述語言算法描述語言: 算法可以用自然語言、數學語言或者約定算法可以用自然語言、數學語言或者約定的符號語言來描述。的符號語言來描述。如類如類Pascal語言、語言、C語言或偽代碼等。語言或偽代碼等。 類類pascal語言：過多涉及數據類型的定義語言：過多涉及數據類型的定義 knuth語言：不方便描述遞歸語言：不方便描述遞歸 ADL （Al

21、gorithm Describe Language）：）：直觀方便直觀方便例例1.3 歐幾里得算法 算法算法E ( m , n . n )/* 給定兩個正整數m和n，算法E求它們的最大公因子（即能同時整除m和n的最大正整數），輸出結果在n中 */E1. 求余數 r m m/n n . / 有0 r nE2. 余數為零？ IF r 0 THEN RETURN n. / 若余數為 0，n即為答案E3. 減少 m n. nr. GOTO E1.2.2.算法描述語言算法描述語言 ADL ADL 的格式的格式算法算法 （變量變量i i1 1, , ,變量變量i im m. .變量變量j j1 1, ,

22、,變量變量j jn n）/ 或者或者 /* */ . . 1 J . . 語句序列語句序列. . 2.2.算法描述語言算法描述語言 ADL ADL 的格式的格式算法算法 （變量變量i i1 1, , ,變量變量i im m. .變量變量j j1 1, , ,變量變量j jn n）/ 或者或者 /* */ . . 1 J . . 語句序列語句序列. . 算法名算法名 是由字母和數字是由字母和數字組成的有限字符串，且串中組成的有限字符串，且串中第一個符號必須是字母；第一個符號必須是字母；在變量表中，變量在變量表中，變量 ik 為輸為輸入變量，入變量，1 k m, m 0，當當m = 0時，表示無輸

23、入變時，表示無輸入變量；變量量；變量 jk 為輸出變量，為輸出變量，1 k n，n 1 . 2.2.算法描述語言算法描述語言 ADL ADL 的格式的格式算法算法 （變量變量i i1 1, , ,變量變量i im m. .變量變量j j1 1, , ,變量變量j jn n）/ 或者或者 /* */ . . 1 J . . 語句序列語句序列. . 對整個算法進行概括說明，應包含算法的主要思想、參變量和功能等的解釋.2.2.算法描述語言算法描述語言 ADL ADL 的格式的格式算法算法 （變量變量i i1 1, , ,變量變量i im m. .變量變量j j1 1, , ,變量變量j jn n）/

24、 或者或者 /* */ . . 1 J . . 語句序列語句序列. . 算法的每一步驟都要有名稱，名稱由步驟名：算法名或算法名縮寫數字.組成；步驟名后緊接（不計空格）一對方括號，該方括號內是該步驟所執行操作的高度概括；2.2.算法描述語言算法描述語言 ADL ADL 的格式的格式算法算法 （變量變量i i1 1, , ,變量變量i im m. .變量變量j j1 1, , ,變量變量j jn n）/ 或者或者 /* */ . . 1 J . . 語句序列語句序列. . 本步驟的一系列操作，每個操作由ADL語句給出，若某操作難于理解則需在其后對其做出解釋.每個算法都需要用符號“”作為其被書寫完畢

25、的結束符，注意算法不一定在符號“”處運行結束.例例1.3 歐幾里得算法 算法算法E ( m , n . n )/* 給定兩個正整數m和n，算法E求它們的最大公因子（即能同時整除m和n的最大正整數），輸出結果在n中 */E1. 求余數 置 r m m/n n . / 有0 r nE2. 余數為零？ IF r 0 THEN RETURN n. / 若余數為 0，n即為答案E3. 減少 置m n. nr. GOTO E1. 表達式表達式算術運算符算術運算符 +,-,*,/,DIV,MOD, , 關系運算符關系運算符=, , 邏輯運算符邏輯運算符AND，OR，NOT 邏輯常量邏輯常量 true，fal

26、se集合運算符集合運算符 ， （差），（差）， ， 語句語句 每條語句都用每條語句都用“.”作為結束符作為結束符 賦值語句賦值語句 a b. a b. a b c. 條件語句條件語句IF IF THEN THEN （ 語句語句1. 1. . . 語句語句m m ）. . IF IF THEN THEN （ 語句語句1. 1. . . 語句語句m m ）. . ELSE ELSE （ 語句語句1. 1. . . 語句語句n n ）. .CASE DOCASE DO（ : (1: (語句語句1. 1. . .語句語句n n1 1）. . : (m: (語句語句1. 1. . .語句語句n nm m

27、).). 循環語句循環語句WHILE DO （語句（語句1. . 語句語句n）. FOR = TO STEP DO （語句（語句1. . 語句語句n）.FOR DO（語句（語句1. . 語句語句n）. 轉移語句轉移語句 GOTO () . EXIT 語句語句可以提前結束可以提前結束WHILE或者或者FOR 循環的執行循環的執行 RETURN 語句語句指出算法執行的終點指出算法執行的終點其它其它輸入語句為：READ ( x )，表示讀取輸入值賦給變量x輸出語句為：PRINT（輸出信息）例例 A是一個含有是一個含有n個不同元素的實數數組，給出求個不同元素的實數數組，給出求A中最大和最小元素的算法。

28、中最大和最小元素的算法。 算法算法SM(A,n . max,min) SM1.初始化初始化 maxminA1. SM2.比較比較 FOR i=2 TO n DO /求最大和最小元素求最大和最小元素 ( IF Ai max THEN maxAi. IF Ai max THEN maxAi. IF Ai max THEN maxAi. IF Ai min THEN minAi). 算法算法SMSM的時間復雜性為的時間復雜性為2(n-1)2(n-1) (i+j)/2 .如果規定算法如果規定算法BSBS的基本運算亦為元素的的基本運算亦為元素的比較，則容易看出算法比較，則容易看出算法BSBS對不同的輸入

29、對不同的輸入AiAi到到AjAj都有相同的基本運算次數。設表示都有相同的基本運算次數。設表示算法算法BSBS的基本運算次數，根據算法的基本運算次數，根據算法BSBS的遞的遞歸過程，有如下的遞歸表達式：歸過程，有如下的遞歸表達式：0 1( )1 2( /2)( /2) 2 2nTnnT nT nnv在剛才的遞歸表達式中，當在剛才的遞歸表達式中，當n n是是2 2的冪的冪時（即存在正整數時（即存在正整數k k，使得，使得n=2n=2k k）有）有()2 *(/ 2 )2TnTn 2 * ( 2 *(/ 4 )2 )2Tn 4 *(/ 4 )42Tn111 . 2*( 2 )2kkiiT1 2223

30、 22kknBS與與SM的比較的比較 雖然算法雖然算法SMSM和算法和算法BSBS的時間復雜性的時間復雜性均為線性型，但因均為線性型，但因 ，故就計算時間而言，算法故就計算時間而言，算法BSBS優于算法優于算法SMSM。 然而算法然而算法BSBS是遞歸算法，因此它是遞歸算法，因此它的實現需要額外的輔助空間棧。的實現需要額外的輔助空間棧。32221nn()設設f(n)和和g(n)是正整數集到正實數集上的函數，定是正整數集到正實數集上的函數，定義：義：稱稱g(n)的階至多為的階至多為f(n)，當且僅當存在一個正常數，當且僅當存在一個正常數C和和n0，使得對任意的使得對任意的nn0，有，有g(n)

31、C f(n) 記記 g(n)為為 O(f(n)f和和g之間的關系可以描述為之間的關系可以描述為“f(n)的階至多為的階至多為 g(n)”或或“f至多與至多與g增長得一樣快增長得一樣快”222232(1)(log log)(log)( )( log)()()(2 )nOOnOnO nO nnO nO nO定義定義2.2 設設f(n)和和g(n)是正整數集到正實數集上的是正整數集到正實數集上的函數，定義：函數，定義：（1）稱）稱g(n)的階至少為的階至少為f(n)，當且僅當存在一個正常數，當且僅當存在一個正常數C和和n0，使得對任意的，使得對任意的nn0，有，有g(n) C f(n) 記記 g(n

32、)為為 (f(n)（2）稱）稱g(n)的階至多為的階至多為f(n)，當且僅當存在一個正常數，當且僅當存在一個正常數C和和n0，使得對任意的，使得對任意的nn0，有，有g(n) C f(n) 記記 g(n)為為 (f(n)（ 3）稱）稱g(n)的階為的階為f(n)，當且僅當存在正常數，當且僅當存在正常數C1、C2和和n0，使得對任意的，使得對任意的n n0，有，有C1f(n) g(n)C2f(n) 記記 g(n)為為 (f(n)時間與空間分析時間與空間分析 一個算法在一個算法在不同的執行時間內不同的執行時間內，它，它占用的內存占用的內存空間量不一定相等空間量不一定相等，占用空間量，占用空間量y是時間是時間x的函數，即的函數，即y=f(x)。稱積分。稱積分 為該算法的時空積分，其中為該算法的時空積分，其中t是該算法的執行時間。基于時空積分，可以比較算法是該算法的執行時間。基于時空積分，可以比較算法優劣，時空積分較小的算法較優。優劣，時空積分較小的算法較優。dxxft0)(807060302010YX效率效率圖圖2.2 時空分布示意圖時空分布示意圖 例如，一個算法執行時間為