1、數據結構(C語言版) Data Structure授課教師：孫曉芳授課教師：孫曉芳聯系方式：聯系方式：教材：教材： 數據結構數據結構 高等教育出版社高等教育出版社 陳越陳越參考資料：參考資料：數據結構學習與實驗指導，陳越著，高等教育出版社數據結構學習與實驗指導，陳越著，高等教育出版社學時：學時：3636學時課堂學時課堂課程安排課程要求成績構成及比例成績構成及比例總評成績=平時總成績（40%）+期末考試成績60%其中平時成績包括考勤（占總分的10%）、作業（占總分的20%）、小測驗（占總分的10%）取消考試資格情況取消考試資格情況缺課累計13學時及以上者取消考試資格；無故曠課8學時者取消考試資格

2、；抄襲他人作業、未完成作業次數較多的取消考試資格。 引子引子 數據結構數據結構 算法算法 應用實例應用實例為什么要學數據結構？ “數據結構數據結構”是計算機科學與技術專業、軟件工程專業甚至于是計算機科學與技術專業、軟件工程專業甚至于其它電氣信息類專業的重要專業基礎課程。它所討論的知識內容和提其它電氣信息類專業的重要專業基礎課程。它所討論的知識內容和提倡的技術方法，無論對進一步學習計算機領域的其它課程，還是對從倡的技術方法，無論對進一步學習計算機領域的其它課程，還是對從事大型信息工程的開發，都是重要而必備的基礎。事大型信息工程的開發，都是重要而必備的基礎。 程序設計解決問題往往有多種方法，且不同

3、方法之間的效率可程序設計解決問題往往有多種方法，且不同方法之間的效率可能相差甚遠。程序的時間和空間效率，不僅跟數據的組織方式有關，能相差甚遠。程序的時間和空間效率，不僅跟數據的組織方式有關，也跟處理流程的巧妙程度有關。本課程將介紹并探討有關數據組織、也跟處理流程的巧妙程度有關。本課程將介紹并探討有關數據組織、算法設計、時間和空間效率的概念和通用分析方法，幫助學生學會數算法設計、時間和空間效率的概念和通用分析方法，幫助學生學會數據的組織方法和一些典型算法的實現，能夠針對問題的應用背景分析，據的組織方法和一些典型算法的實現，能夠針對問題的應用背景分析，選擇合適的數據結構，從而培養高級程序設計技能。

4、選擇合適的數據結構，從而培養高級程序設計技能。1 引子引子第第1章章 概論概論 為什么要學數據結構？考研課程考研課程計算機等級考試課程計算機等級考試課程程序員考試課程程序員考試課程編程基礎編程基礎 N.N.沃思（沃思（Niklaus Wirth)Niklaus Wirth)教授提出：教授提出： 程序=算法+數據結構實際應用需求實際應用需求 數值計算數值計算非數值計算非數值計算1 引子引子第第1章章 概論概論 第第1章章 概論概論 【定義定義】“數據結構是計算機中數據結構是計算機中存儲、組織數據存儲、組織數據的方式。的方式。精心選擇的數據結構可以帶來精心選擇的數據結構可以帶來最優效率的算法最優效

5、率的算法。”1/251 引子引子例例1.1 該該如何擺放書如何擺放書，才能讓讀者很方便地找到你手里這本，才能讓讀者很方便地找到你手里這本數據結構？數據結構？什么是數據結構？第第1章章 概論概論 【分析分析】2/251 引子引子方法方法1 隨便放隨便放-任何時候有新書進來，哪里有空就把書插到哪里。任何時候有新書進來，哪里有空就把書插到哪里。方法方法2 按照書名的按照書名的字母順序字母順序排放。排放。方法方法3 把書架把書架劃分成幾塊區域劃分成幾塊區域，每塊區域指定擺放某種類別的圖書；，每塊區域指定擺放某種類別的圖書；在每種類別內，按照書名的拼音字母順序排放。在每種類別內，按照書名的拼音字母順序排

6、放。 查找效率極低！查找效率極低！ 有時插入新書很困難！有時插入新書很困難！ 可能造成空間的浪費！可能造成空間的浪費！查找效率查找效率 跟數據的組織方式有關！跟數據的組織方式有關！第第1章章 概論概論 1 引子引子例例1.2 ：寫程序實現一個函數：寫程序實現一個函數PrintN，使得傳入一個正，使得傳入一個正整數為整數為N的參數后，能順序的參數后，能順序打印從打印從1到到N的全部正整數。的全部正整數。 void PrintN ( int N ) int i; for ( i=1; i=N; i+ ) printf(“%dn”, i ); return; void PrintN ( int N

7、) if ( !N ) return; PrintN( N 1 ); printf(“%dn”, N ); return; 3/25運行效率運行效率 跟空間的利用效率有關！跟空間的利用效率有關！第第1章章 概論概論 1 引子引子例例1.3 多項式的標準表達式可以寫為：多項式的標準表達式可以寫為： f(x) = a0 + a1x + a2x2 + + anxn現給定一個多項式的階數現給定一個多項式的階數 n，并將全體系數存放在數組，并將全體系數存放在數組 a 里。請寫程序計算這個多項式在里。請寫程序計算這個多項式在給定點給定點 x 處的值處的值。方法方法1 計算多項式函數值的計算多項式函數值的直

8、接法直接法 double f( int n, double a, double x ) /* 計算階數為計算階數為n，系數為，系數為a0.an的多項式在的多項式在x點的值點的值 */int i;double p = a0;for ( i=1; i0; i-)p = ai-1 + x*p;return p;4/25#include #include clock_t start, stop; /* clock_t是是clock()函數返回的變量類型函數返回的變量類型 */double duration; /* 記錄被測函數運行時間，以秒為單位記錄被測函數運行時間，以秒為單位 */int main

9、() /* 不在測試范圍內的準備工作寫在不在測試范圍內的準備工作寫在clock()調用之前調用之前*/ start = clock(); /* 開始計時開始計時 */ function(); /* 把被測函數加在這里把被測函數加在這里 */ stop = clock(); /* 停止計時停止計時 */ duration = (double)(stop - start)/CLK_TCK;/* 計算運行時間計算運行時間 */ /* 其他不在測試范圍的處理寫在后面，例如輸出其他不在測試范圍的處理寫在后面，例如輸出duration的值的值 */ return 0; 第第1章章 概論概論 1 引子引子5

10、/25代碼代碼1.6 測試函數測試函數function()的的運行時間運行時間秦九韶算法的計算速度明顯比秦九韶算法的計算速度明顯比直接法直接法快了一個數量級快了一個數量級！為什么會這樣？為什么會這樣？ 即使解決一個非常簡單的問題，往往也有即使解決一個非常簡單的問題，往往也有多種方法多種方法，且不同方法之間的且不同方法之間的效率可能相差甚遠效率可能相差甚遠 解決問題方法的解決問題方法的效率效率 跟數據的跟數據的組織方式組織方式有關（如例有關（如例1.1） 跟跟空間的利用效率空間的利用效率有關（如例有關（如例1.2） 跟跟算法的巧妙算法的巧妙程度有關（如例程度有關（如例1.3）第第1章章 概論概論

11、 1 引子引子6/25第第1章章 概論概論 數據對象數據對象： 計算機要處理的事物，通常計算機要處理的事物，通常是是性質相同性質相同的數據元素的集的數據元素的集合。合。如例如例1中中“圖書圖書” 。2.1 術語定義術語定義 操作操作：處理事物的動作集合，如例處理事物的動作集合，如例1中的中的“查找查找”和和“插入插入”，例例2的函數的函數“求值求值”等。等。 算法算法： 操作的實現方法，如例操作的實現方法，如例1的按字母序排放的的按字母序排放的“查找查找”和和“插入插入”、例、例2的的“直接法直接法”和和“秦九韶法秦九韶法”等；等； 通常一個算法用一個通常一個算法用一個函數函數來實現來實現。7

12、/25數據結構數據結構： 數據對象在計算機中的數據對象在計算機中的組織方式組織方式 定義在數據對象之上的操作定義在數據對象之上的操作 邏輯結構邏輯結構：數據元素間抽象化的相互數據元素間抽象化的相互關系關系。與數據的存儲。與數據的存儲無關，獨立于計算機，它是從具體問題抽象出來的數學模型。無關，獨立于計算機，它是從具體問題抽象出來的數學模型。分為分為“集合集合”、“線性線性”、“樹樹”和和“圖圖”。例。例1中按方中按方法法1來處理，就是把圖書集看成是線性的結構；按方法來處理，就是把圖書集看成是線性的結構；按方法3來處理，就是把圖書集看成是樹型的結構。來處理，就是把圖書集看成是樹型的結構。 物理結構

13、物理結構：數據對象信息在計算機內存中的存儲組織關：數據對象信息在計算機內存中的存儲組織關系，它依賴于計算機語言。一般分為系，它依賴于計算機語言。一般分為“順序存儲順序存儲”和和“鏈鏈式存儲式存儲”。（索引存儲，散列存儲）。（索引存儲，散列存儲）數據對象在計算機中的組織方式：數據對象在計算機中的組織方式：邏輯結構邏輯結構、存儲結構存儲結構。第第1章章 概論概論 2.1 術語定義術語定義數據結構數據結構邏輯結構邏輯結構存儲（物理）結構存儲（物理）結構數據運算數據運算線性結構（線性表、棧、隊列、串、數組等）線性結構（線性表、棧、隊列、串、數組等）非線性結構非線性結構順序結構順序結構鏈式結構鏈式結構插

14、入插入刪除刪除查找查找排序排序修改修改樹結構樹結構圖結構圖結構數據的邏輯結構數據的邏輯結構就是數據元素之間的邏輯關系。可表示為：數據的邏輯結構就是數據元素之間的邏輯關系。可表示為： Data_Structure =(DData_Structure =(D，R)R)其中，其中，D D是組成數據的數據元素的有限集合，是組成數據的數據元素的有限集合，R R是數據元素之間的關系集合。是數據元素之間的關系集合。根據數據元素之間關系的不同特性，數據結構可分為線性數據結構和非線根據數據元素之間關系的不同特性，數據結構可分為線性數據結構和非線性數據結構。性數據結構。（1 1）線性結構的邏輯特征是除第一個結點和

15、最后一個結點外，其他所有結）線性結構的邏輯特征是除第一個結點和最后一個結點外，其他所有結點都有且只有一個直接前趨和一個直接后繼結點。點都有且只有一個直接前趨和一個直接后繼結點。（2 2）非線性結構的邏輯特征是一個結點可能有多個直接前趨和直接后繼。）非線性結構的邏輯特征是一個結點可能有多個直接前趨和直接后繼。數據的存儲結構數據的邏輯結構是面向應用問題的，是從用戶角度看到的數據的結數據的邏輯結構是面向應用問題的，是從用戶角度看到的數據的結構。數據必須在計算機內存儲，數據的存儲結構構。數據必須在計算機內存儲，數據的存儲結構(storage (storage structure)structure)是

16、研究數據元素和數據元素之間的關系如何在計算機中是研究數據元素和數據元素之間的關系如何在計算機中表示，是邏輯數據的存儲映像，它是面向計算機的。表示，是邏輯數據的存儲映像，它是面向計算機的。實現數據的邏輯結構到計算機存儲器的映像有多種不同的方式。通實現數據的邏輯結構到計算機存儲器的映像有多種不同的方式。通常，數據在存儲器中的存儲有兩種基本的映像方法。常，數據在存儲器中的存儲有兩種基本的映像方法。（1 1）順序存儲結構（）順序存儲結構（Sequential Storage StructureSequential Storage Structure）：把邏輯上）：把邏輯上相鄰的結點存儲在物理位置相鄰的

17、存儲單元里，結點間的邏輯關系由相鄰的結點存儲在物理位置相鄰的存儲單元里，結點間的邏輯關系由存儲單元的鄰接關系來體現。由此得到的存儲表示稱為順序存儲結構，存儲單元的鄰接關系來體現。由此得到的存儲表示稱為順序存儲結構，它主要用于線性數據結構，非線性的數據結構也可以通過某種線性化它主要用于線性數據結構，非線性的數據結構也可以通過某種線性化的方法來實現順序存儲。的方法來實現順序存儲。（2 2）鏈式存儲結構（）鏈式存儲結構（Linked Storage StructureLinked Storage Structure）：鏈式存儲結構）：鏈式存儲結構把邏輯上相鄰的兩個元素存放在物理上不一定相鄰的存儲單元

18、中，結把邏輯上相鄰的兩個元素存放在物理上不一定相鄰的存儲單元中，結點間的邏輯關系是由附加的指針字段表示的。鏈式存儲結構的特點就點間的邏輯關系是由附加的指針字段表示的。鏈式存儲結構的特點就是將存放每個數據元素的結點分為兩部分：一部分存放數據元素是將存放每個數據元素的結點分為兩部分：一部分存放數據元素( (稱稱為數據域為數據域) )；另一部分存放指示存儲地址的指針；另一部分存放指示存儲地址的指針( (稱為指針域稱為指針域) )，借助，借助指針表示數據元素之間的關系。指針表示數據元素之間的關系。例：復數74i 的兩種存儲方式： （1）地址 內容 （2）地址 內容7403200322707020320

19、032207024 數據結構定義：數據結構定義： 按某種按某種邏輯關系邏輯關系組織起來的一批數據（或稱帶結構的數據元素的集合）應用計算機語言并按一定的存儲表示按一定的存儲表示 方式方式把它們存儲在計算機的存儲器中，并在其上定義了一個運在其上定義了一個運算的集合算的集合。定義定義2-是相互之間存在相互之間存在一種或多種特定關系一種或多種特定關系的數據元素的數據元素的集合。的集合。第第1章章 概論概論 數據類型：數據類型： 數據對象的類型確定了其數據對象的類型確定了其“操作集操作集”和和“數據定義域數據定義域”。比如：整型，字符型等。比如：整型，字符型等。2.2 抽象數據類型抽象數據類型 抽象數據

20、類型（抽象數據類型（Abstract Data Type ，簡稱簡稱ADT） ： 由用戶定義，用以表示應用問題的數據模型數據模型。它由基本的數據類型構成，并包括一一組相關組相關的服務（或稱操作操作）。8/25 ADT的形式化定義是三元組：的形式化定義是三元組：ADT=(D，S，P)其中：其中：D是是數據對象數據對象，S是是D上的上的關系集關系集，P是對是對D的的基本操基本操作集作集。第第1章章 概論概論 例例1.4“矩陣矩陣”的抽象數據類型定義的抽象數據類型定義2.2 抽象數據類型抽象數據類型類型名稱類型名稱：Matrix數據對象集：數據對象集：一個一個M N的矩陣的矩陣 A。操作集操作集：對

21、于任意矩陣：對于任意矩陣A、B、C Matrix，以及正整數，以及正整數i、j、M、N，以下僅列出幾項有代表性的操作。以下僅列出幾項有代表性的操作。1）Matrix Create( int M, int N )：返回一個返回一個M N的空矩陣；的空矩陣；2） int GetMaxRow( Matrix A )：返回矩陣：返回矩陣A的總行數；的總行數；3）int GetMaxCol( Matrix A )：返回矩陣：返回矩陣A的總列數；的總列數；4）ElementType GetEntry( Matrix A, int i, int j )：返回矩陣：返回矩陣A的第的第i行、行、第第j列的元素；

22、列的元素；5）Matrix Add( Matrix A, Matrix B )：如果：如果A和和B的行、列數一致，則的行、列數一致，則返回矩陣返回矩陣C=A+B，否則返回錯誤標志；，否則返回錯誤標志；6） Matrix Multiply( Matrix A, Matrix B )：如果：如果A的列數等于的列數等于B的行數，的行數，則返回矩陣則返回矩陣C = AB，否則返回錯誤標志；，否則返回錯誤標志；7）9/25第第1章章 概論概論 2.2 抽象數據類型抽象數據類型“抽象抽象”描述數據對象時，并描述數據對象時，并不規定不規定其中其中數據元素的類型數據元素的類型對數據對象的描述對數據對象的描述不

23、依賴不依賴其在計算機中的其在計算機中的存儲方法存儲方法描述操作時，只描述操作要實現的功能，描述操作時，只描述操作要實現的功能，并不涉及并不涉及具體實現方法具體實現方法【定義定義】一個一個算法算法是解決某一類問題的步驟的描述。是解決某一類問題的步驟的描述。一般一般而言，算法應該符合以下五項要求：而言，算法應該符合以下五項要求：(1) 輸入輸入：它接受一些輸入（有些情況下不需要輸入）；它接受一些輸入（有些情況下不需要輸入）；(2) 輸出輸出：至少產生一個輸出；至少產生一個輸出；(3) 確定性確定性：算法的每一步必須有充分明確的含義，不可以有歧義；算法的每一步必須有充分明確的含義，不可以有歧義；(4

24、) 有限性有限性：算法是一個有限指令集，并一定在有限步驟之后終止；算法是一個有限指令集，并一定在有限步驟之后終止；(5) 可行性可行性：算法的每一步必須在計算機能處理的范圍之內算法的每一步必須在計算機能處理的范圍之內第第1章章 概論概論 3.1 算法定義算法定義 另外，另外，算法的描述算法的描述可以不依賴于任何一種計算機語言以及具體的可以不依賴于任何一種計算機語言以及具體的實現手段。可以用實現手段。可以用自然語言、流程圖自然語言、流程圖等方法來描述。等方法來描述。 但是，用某一種計算機語言進行但是，用某一種計算機語言進行偽碼描述偽碼描述往往使算法容易被理解，往往使算法容易被理解，本書即采用本書

25、即采用C語言的部分語法作為描述算法的工具。語言的部分語法作為描述算法的工具。10/25例例 選擇法排序選擇法排序：把：把n個整數排序成從小到大。個整數排序成從小到大。思想：從余下的未排序的部分整數中，挑選最小整數放在前思想：從余下的未排序的部分整數中，挑選最小整數放在前面已排序部分的后面面已排序部分的后面.如何進行排序如何進行排序? 哪里哪里?void SelectionSort ( int List, int N ) /* 將將N個整數個整數List0.ListN-1進行非遞減排序進行非遞減排序 */ for ( i = 0; i N; i + ) MinPosition = ScanFor

26、Min( List, i, N1 ); /* 從從Listi到到ListN1中找最小元，并將其位置賦給中找最小元，并將其位置賦給MinPosition */ Swap( Listi, ListMinPosition ); /* 將未排序部分的最小元換到有序部分的最后位置將未排序部分的最小元換到有序部分的最后位置 */ 選擇排序選擇排序 = 找最小整數找最小整數 + 交換至合適位置交換至合適位置.第第1章章 概論概論 3.1 算法例子算法例子11/25第第1章章 概論概論 3.2 算法復雜度算法復雜度 什么是什么是“好好”的算法？的算法？12/25算法設計的基本要求（評價指標）算法設計的基本要求

27、（評價指標）u正確性u可讀性u健壯性u效率和低存儲量需求常用時間復雜度來衡量常用時間復雜度來衡量常用空間復雜度來衡量常用空間復雜度來衡量度量程序的執行時間的方法1事后統計，指的是通過計事后統計，指的是通過計算機內部計算時間，并進算機內部計算時間，并進行分析行分析。2事前分析估算，主要事前分析估算，主要指的指的是在分析時間復雜度等因是在分析時間復雜度等因素基礎上進行研究。素基礎上進行研究。 第第1章章 概論概論 3.2 算法復雜度算法復雜度 時間復雜度時間復雜度 T(n) 根據算法寫成的根據算法寫成的程序在執行時耗費時間的長程序在執行時耗費時間的長度度。這個長度往往也與輸入數據的規模。這個長度往

28、往也與輸入數據的規模 有關。時間復雜度過高的低有關。時間復雜度過高的低效算法可能導致我們在有生之年都等不到運行結果。效算法可能導致我們在有生之年都等不到運行結果。12/25 T(n)-常用程序中常用程序中最深層循環內最深層循環內的語句的原操作的的語句的原操作的執行頻度執行頻度(重重復執行的次數復執行的次數)來表示來表示.第第1章章 概論概論 3.2 算法復雜度算法復雜度12/25（1）定義（算法執行時間的增長率）定義（算法執行時間的增長率） T(n)=o(f(n)（2）說明）說明 f( n)是基本操作（包括語句）的重復執行的次數是基本操作（包括語句）的重復執行的次數 o( )為漸進符號為漸進符

29、號 （3）計算方法）計算方法 T(n)由嵌套最深層語句的（頻度）執行次數決定由嵌套最深層語句的（頻度）執行次數決定 例如：分析以下程序段的時間復雜度例如：分析以下程序段的時間復雜度 i=1; For (i=1;i=2n;i+) i=i+2; 分析：語句的頻度是分析：語句的頻度是1 1，語句，語句2 2的頻度是的頻度是f(n)=2nf(n)=2n 所以該程序段的時間復雜度T(n)=O(n)T(n)=O(n)01234567891001020304050602nn2n log nnlog nfn第第1章章 概論概論 3.3 復雜度的漸進表示法復雜度的漸進表示法18/25補充說明：時間復雜度T(n)

30、按數量級遞增順序如下通常，把算法在執行時所需的輔助空間的大小作為分析算法空間復雜通常，把算法在執行時所需的輔助空間的大小作為分析算法空間復雜度的依據。度的依據。空間復雜度空間復雜度S(n)S(n)（1 1）定義（算法所需存儲空間的度量）定義（算法所需存儲空間的度量） S(n)=o(f(n) S(n)=o(f(n)常見的幾種空間復雜度有：常見的幾種空間復雜度有：O(1)O(1)，O(n)O(n)，O(nO(n2 2) )，O(nO(n3 3) )等。等。（2 2）說明）說明算法本身所占用的存儲空間算法本身所占用的存儲空間算法的輸入、輸出數據所占用的存儲空間算法的輸入、輸出數據所占用的存儲空間算法

31、運行過程中臨時占用的存儲空間算法運行過程中臨時占用的存儲空間 例例1.51.5下面算法實現求一個數組元素的累加和，計算該算法的時間下面算法實現求一個數組元素的累加和，計算該算法的時間復雜度。復雜度。int sum(int list,int n)int sum(int list,int n) / /* * 執行次數執行次數 * */ /int sum=0.0; int sum=0.0; for (int i=0; in; i+ ) for (int i=0; in; i+ ) / /* * =n+1 =n+1 * */ /sum += listi; sum += listi; / /* * =n =n * */ /return sum; return sum; / /* * =1 =1 * */ / 時間復雜度為：時間復雜度為：(n+1)+n+1=2n+2(n+1)+n+1=2n+2，記為：，記為： O(n) O(n) 例例1.61.6下面過程實現兩矩陣乘法，計算該過程的時間復雜度。下面過程實現兩矩陣乘法，計算該過程的時間復雜度。 / /* *執行次數執行次數* */ /for(i=0; in; i+)for(i=0; in; i+) / /* * =n+1 =n+1 * */ / for(j=0; jn; j+) for(j=0; jn; j+) /