嚴蔚敏最新版《數(shù)據(jù)結構》電子教案

1、人民郵電出版社北京林業(yè)大學信息學院 4:04 人民郵電出版社北京林業(yè)大學信息學院 4:04 v編程基礎編程基礎v計算機及相關專業(yè)考研考博課程計算機及相關專業(yè)考研考博課程v計算機等級考試課程計算機等級考試課程v程序員考試課程程序員考試課程為什么要學習數(shù)據(jù)結構為什么要學習數(shù)據(jù)結構北京林業(yè)大學信息學院 4:04 課程學習指導課程學習指導 1.提前預習預習、認真聽課、按時完成書面及上機作業(yè)作業(yè) 2.注意先修課程的知識準備離散數(shù)學、C C語言語言 3.注意循序漸進：基本概念概念、基本思想思想、基本步驟步驟、算法算法設計 4.注意培養(yǎng)算法設計的能力理解所講算法、對此多做思考思考：若問題要求不同，應如何選擇

2、數(shù)據(jù)結構，設計有效的算法課程特點：課程特點：內(nèi)容抽象、概念性強、內(nèi)容靈活、不易掌握內(nèi)容抽象、概念性強、內(nèi)容靈活、不易掌握北京林業(yè)大學信息學院 4:04 平時成績 : 30% 作業(yè)、小測驗、實驗 課堂紀律無故遲到：無故曠課：上機：玩游戲、上網(wǎng)聊天 期末成績 : 70%(閉卷筆試)考核方式考核方式北京林業(yè)大學信息學院 4:04 教材和參考書教材和參考書教材：教材： 數(shù)據(jù)結構數(shù)據(jù)結構978-7-115-23490嚴蔚敏，李冬梅，人民郵電出版社出版嚴蔚敏，李冬梅，人民郵電出版社出版 參考書：參考書： 數(shù)據(jù)結構數(shù)據(jù)結構C語言版語言版，嚴蔚敏，清華大學出，嚴蔚敏，清華大學出版社版社 數(shù)據(jù)結構數(shù)據(jù)結構用面向

3、對象方法與用面向對象方法與C+描述描述，殷人昆等，清華大學出版社，殷人昆等，清華大學出版社 4:04 第第1 1章章緒論緒論1. 了解數(shù)據(jù)結構研究的主要內(nèi)容了解數(shù)據(jù)結構研究的主要內(nèi)容2.2.掌握數(shù)據(jù)結構中涉及的基本概念掌握數(shù)據(jù)結構中涉及的基本概念3. 掌握算法、算法的時間復雜度及其分析的掌握算法、算法的時間復雜度及其分析的簡易方法簡易方法 教學目標教學目標北京林業(yè)大學信息學院 4:04 1.1 數(shù)據(jù)結構的研究內(nèi)容數(shù)據(jù)結構的研究內(nèi)容1.2 基本概念和術語基本概念和術語1.3 抽象數(shù)據(jù)類型的表示與實現(xiàn)抽象數(shù)據(jù)類型的表示與實現(xiàn) 1.4 算法與算法分析算法與算法分析教學內(nèi)容教學內(nèi)容人民郵電出版社北京林

4、業(yè)大學信息學院 4:04 &N.N.沃思（沃思（Niklaus Wirth)Niklaus Wirth)教授提出：教授提出： 程序程序=算法算法+數(shù)據(jù)結構數(shù)據(jù)結構&電子計算機的主要用途：電子計算機的主要用途： 早期：早期： 主要用于數(shù)值計算。主要用于數(shù)值計算。 后來：后來： 處理逐漸擴大到非數(shù)值計算領域，能處理處理逐漸擴大到非數(shù)值計算領域，能處理多種復雜的具有一定結構關系的數(shù)據(jù)多種復雜的具有一定結構關系的數(shù)據(jù)1.1 數(shù)據(jù)結構的研究內(nèi)容數(shù)據(jù)結構的研究內(nèi)容北京林業(yè)大學信息學院 4:04 書目自動檢索系統(tǒng)登錄號：書名：作者名：分類號：出版單位：出版時間：價格：書目卡片001高等數(shù)學樊

5、映川S01002理論力學羅遠祥L01003高等數(shù)學華羅庚S01004線性代數(shù)欒汝書S02書目文件按書名按作者名按分類號高等數(shù)學001，003理論力學002，.線性代數(shù)004，.樊映川001,華羅庚002,.欒汝書004,.L002,S001,003,索引表線性表人民郵電出版社北京林業(yè)大學信息學院 4:04 人機對奕問題樹.北京林業(yè)大學信息學院 4:04 / (root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp文件系統(tǒng)的系統(tǒng)結構圖文件系統(tǒng)的系統(tǒng)結構圖樹人民郵電出版社北京林業(yè)大學信息學院 4:04 多叉路口交通燈管理問題CED

6、ABABACADBABCBDDADBDCEAEBECED圖頂點：頂點：一條通路連線：連線：不能同時通行染色：染色：有連線的兩個頂點不能具有相同顏色人民郵電出版社北京林業(yè)大學信息學院 4:04 &求解非數(shù)值計算的問題：求解非數(shù)值計算的問題： 設計出合適的數(shù)據(jù)結構及相應的算法設計出合適的數(shù)據(jù)結構及相應的算法 即：首先要考慮即：首先要考慮對相關的各種信息如何表示、組織對相關的各種信息如何表示、組織和存儲？和存儲？ 數(shù)據(jù)結構的研究內(nèi)容為：數(shù)據(jù)結構的研究內(nèi)容為： 研究非數(shù)值計算的程序設計問題中計算機的研究非數(shù)值計算的程序設計問題中計算機的操作操作對象對象以及它們之間的以及它們之間的關系和操作關系

7、和操作。北京林業(yè)大學信息學院 4:04 &數(shù)據(jù)結構課程的形成和發(fā)展：數(shù)據(jù)結構課程的形成和發(fā)展： 形成階段：形成階段： 6060年代初期，年代初期，“數(shù)據(jù)結構數(shù)據(jù)結構”有關的內(nèi)容散見于操作系有關的內(nèi)容散見于操作系統(tǒng)、編譯原理和表處理語言等課程。統(tǒng)、編譯原理和表處理語言等課程。19681968年，年，“數(shù)據(jù)數(shù)據(jù)結構結構”被列入美國一些大學計算機科學系的教學計劃被列入美國一些大學計算機科學系的教學計劃。 發(fā)展階段：發(fā)展階段： 數(shù)據(jù)結構的概念不斷擴充，包括了網(wǎng)絡、集合代數(shù)論數(shù)據(jù)結構的概念不斷擴充，包括了網(wǎng)絡、集合代數(shù)論、關系等、關系等“離散數(shù)學結構離散數(shù)學結構”的內(nèi)容。的內(nèi)容。 7070年代后

8、期，我國高校陸續(xù)開設該課程。年代后期，我國高校陸續(xù)開設該課程。北京林業(yè)大學信息學院 4:04 &數(shù)據(jù)結構數(shù)據(jù)結構所處的地位：所處的地位：介于數(shù)學、計算介于數(shù)學、計算機硬件和計算機機硬件和計算機軟件三者之間的軟件三者之間的一門核心課程一門核心課程北京林業(yè)大學信息學院 4:04 北京林業(yè)大學信息學院 4:04 能夠分析研究計算機加工的對象的特性，獲能夠分析研究計算機加工的對象的特性，獲得其得其邏輯結構邏輯結構，根據(jù)需求，選擇合適，根據(jù)需求，選擇合適存貯結存貯結構及其相應的算法構及其相應的算法； 學習一些學習一些常用的算法常用的算法； 復雜程序設計的訓練過程，要求編寫的程序復雜程序設計的訓練

9、過程，要求編寫的程序結構清楚和正確易讀結構清楚和正確易讀； 初步掌握算法的初步掌握算法的時間分析和空間分析時間分析和空間分析技術技術北京林業(yè)大學信息學院 4:04 1、數(shù)據(jù)、數(shù)據(jù)（data)所有能輸入到計算機中去的描述客觀事物的符號u數(shù)值性數(shù)據(jù)數(shù)值性數(shù)據(jù)u非數(shù)值性數(shù)據(jù)（多媒體信息處理）非數(shù)值性數(shù)據(jù)（多媒體信息處理）2、數(shù)據(jù)元素、數(shù)據(jù)元素（data element）數(shù)據(jù)的基本單位，也稱結點（node）或記錄（record）3、數(shù)據(jù)項、數(shù)據(jù)項（data item）有獨立含義的數(shù)據(jù)最小單位，也稱域(field)三者之間的關系：數(shù)據(jù) 數(shù)據(jù)元素 數(shù)據(jù)項例：學生表 個人記錄 學號、姓名1.2 基本概念和術

10、語基本概念和術語人民郵電出版社北京林業(yè)大學信息學院 4:04 u整數(shù)數(shù)據(jù)對象整數(shù)數(shù)據(jù)對象 N = 0, N = 0, 1, 1, 2, 2, u學生數(shù)據(jù)對象學生數(shù)據(jù)對象 學生記錄的集合學生記錄的集合4 4、數(shù)據(jù)對象數(shù)據(jù)對象(Data Object)(Data Object)：相同特性相同特性數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集北京林業(yè)大學信息學院 4:04 5 5、數(shù)據(jù)結構（、數(shù)據(jù)結構（Data Structure）是相互之間是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。存在一種或多種特定關系的數(shù)據(jù)元素的集合。數(shù)據(jù)結構是帶數(shù)據(jù)結構是帶“結構結構”的數(shù)據(jù)元素的集合，的數(shù)據(jù)元素的集合，“結構結構”

11、就是指數(shù)據(jù)元素之間存在的關系。就是指數(shù)據(jù)元素之間存在的關系。北京林業(yè)大學信息學院 4:04 &數(shù)據(jù)結構的兩個層次：數(shù)據(jù)結構的兩個層次：&邏輯結構邏輯結構- 數(shù)據(jù)元素間抽象化的相互關系，與數(shù)據(jù)的存儲無關，獨立于計算機，它是從具體問題抽象出來的數(shù)學模型。&存儲結構（物理結構）存儲結構（物理結構）- 數(shù)據(jù)元素及其關系在計算機存儲器中的存儲方式。北京林業(yè)大學信息學院 4:04 劃分方法一劃分方法一 （1）線性結構- 有且僅有一個開始和一個終端結點，并且所有結點都最多只有一個直接前趨和一個后繼。 例如：線性表、棧、隊列、串 （2）非線性結構- 一個結點可能有多個直接前趨和直接后繼

12、。 例如：樹、圖邏輯結構邏輯結構北京林業(yè)大學信息學院 4:04 線性結構一個對一個，如線性表、棧、隊列樹形結構一個對多個，如樹集合數(shù)據(jù)元素間除“同屬于一個集合”外，無其它關系圖形結構多個對多個，如圖邏輯結構邏輯結構劃分方法二劃分方法二北京林業(yè)大學信息學院 4:04 存儲結構分為：順序存儲結構借助元素在存儲器中的相對位置來表示 數(shù)據(jù)元素間的邏輯關系鏈式存儲結構借助指示元素存儲地址的指針表示數(shù)據(jù) 元素間的邏輯關系存儲存儲結構結構北京林業(yè)大學信息學院 4:04 元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲地址存儲內(nèi)容存儲

13、內(nèi)容Loc(元素元素i)=Lo+（i-1)*m順序存儲順序存儲北京林業(yè)大學信息學院 4:04 1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存儲地址存儲地址 存儲內(nèi)容存儲內(nèi)容 指針指針 1345 1345 元素元素1 1 14001400 1346 1346 元素元素4 4 . . . . . 14001400 元素元素2 2 1536 1536 . . . . . 1536 1536 元素元素3 3 1346 1346 鏈式存儲鏈式存儲 h人民郵電出版社北京林業(yè)大學信息學院 4:04 邏輯結構和存儲結構都相同邏輯結構和存儲結構都相同, , 但運算

14、不同但運算不同, , 則數(shù)據(jù)結構不同則數(shù)據(jù)結構不同. . 例如例如, , 棧與隊列棧與隊列 對于一種數(shù)據(jù)結構對于一種數(shù)據(jù)結構, , 常見的運算常見的運算 插入插入 刪除刪除 修改修改 查找查找 排序排序數(shù)據(jù)的運算數(shù)據(jù)的運算北京林業(yè)大學信息學院 4:04 數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構 數(shù)據(jù)的存儲結構數(shù)據(jù)的存儲結構 數(shù)據(jù)的運算：插入、刪除、修改、查找、排序數(shù)據(jù)的運算：插入、刪除、修改、查找、排序 線性結構線性結構 非線性結構非線性結構 順序存儲順序存儲 鏈式存儲鏈式存儲 線性表線性表 棧、隊列棧、隊列 串、數(shù)組串、數(shù)組樹形結構樹形結構圖形結構圖形結構邏輯結構邏輯結構唯一唯一存儲結構存儲結構不唯一不

15、唯一運算的實現(xiàn)運算的實現(xiàn)依賴于依賴于存儲結構存儲結構人民郵電出版社北京林業(yè)大學信息學院 4:04 n定義：定義：在一種程序設計語言中，變量所具有在一種程序設計語言中，變量所具有的數(shù)據(jù)種類的數(shù)據(jù)種類數(shù)據(jù)類型數(shù)據(jù)類型FORTRAN語言：語言：整型、實型、和復數(shù)型整型、實型、和復數(shù)型 C語言語言：基本數(shù)據(jù)類型：基本數(shù)據(jù)類型： char int float double void構造數(shù)據(jù)類型：構造數(shù)據(jù)類型：數(shù)組、結構體、共用體、文件數(shù)組、結構體、共用體、文件 數(shù)據(jù)類型是一組性質相同的值的集合數(shù)據(jù)類型是一組性質相同的值的集合, , 以及以及定義于這個集合上的一組運算的總稱定義于這個集合上的一組運算的總稱

16、人民郵電出版社北京林業(yè)大學信息學院 4:04 抽象數(shù)據(jù)類型 (ADTs: Abstract Data Types)u更高層次的數(shù)據(jù)抽象更高層次的數(shù)據(jù)抽象u由用戶定義，用以表示應用問題的由用戶定義，用以表示應用問題的數(shù)據(jù)模型數(shù)據(jù)模型u由由基本的數(shù)據(jù)類型基本的數(shù)據(jù)類型組成組成, , 并包括并包括一組相關的一組相關的操作操作抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型北京林業(yè)大學信息學院 4:04 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型可以用以下的三元組來表示：可以用以下的三元組來表示： ADT = （D，S，P） 數(shù)據(jù)對象數(shù)據(jù)對象 D上的關系集上的關系集 D上的操作集上的操作集 ADTADT抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)數(shù)據(jù)對

17、象對象： 數(shù)據(jù)數(shù)據(jù)關系關系： 基本基本操作操作 ： ADT ADT抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型名名ADT常用常用定義定義格式格式北京林業(yè)大學信息學院 4:04 抽抽象象數(shù)數(shù)據(jù)據(jù)類類型型查找插入查找插入 刪除刪除 修改修改 線性表線性表接口或用戶界面數(shù)據(jù)類型的物理實現(xiàn)封裝信息隱蔽信息隱蔽和和數(shù)據(jù)封裝數(shù)據(jù)封裝，使用與實現(xiàn)相分離，使用與實現(xiàn)相分離北京林業(yè)大學信息學院 4:04 1.3 抽象數(shù)據(jù)類型的表示與實現(xiàn)抽象數(shù)據(jù)類型的表示與實現(xiàn)抽象數(shù)據(jù)類型可以通過抽象數(shù)據(jù)類型可以通過固有的固有的數(shù)據(jù)類型（如整數(shù)據(jù)類型（如整型、實型、字符型等）來表示和實現(xiàn)。型、實型、字符型等）來表示和實現(xiàn)。它有些類似它有些類似C C

18、語言中的語言中的結構（結構（struct)struct)類型類型，但增加，但增加了相關的了相關的操作操作教材中用的是教材中用的是類類C C語言（介于偽碼和語言（介于偽碼和C C語言之間）作語言之間）作為描述工具為描述工具但上機時要用具體語言實現(xiàn)，如但上機時要用具體語言實現(xiàn)，如C C或或C+C+等等人民郵電出版社北京林業(yè)大學信息學院 4:04 (1) (1) 預定義常量及類型預定義常量及類型 /函數(shù)結果狀態(tài)代碼函數(shù)結果狀態(tài)代碼 #define OK 1 #define OK 1 #define ERROR 0 #define ERROR 0 #define INFEASIBLE -1 #defi

19、ne INFEASIBLE -1 #define OVERFLOW -2 #define OVERFLOW -2 / Status/ Status是函數(shù)返回值類型，其值是函數(shù)結是函數(shù)返回值類型，其值是函數(shù)結果狀態(tài)代碼。果狀態(tài)代碼。 typedef int Status; typedef int Status; 人民郵電出版社北京林業(yè)大學信息學院 4:04 (2)(2)數(shù)據(jù)元素被約定為數(shù)據(jù)元素被約定為ElemType ElemType 類型，類型，用用戶需要根據(jù)具體情況，自行定義該數(shù)據(jù)類型。戶需要根據(jù)具體情況，自行定義該數(shù)據(jù)類型。(3)(3)算法描述為以下的函數(shù)形式：算法描述為以下的函數(shù)形式：

20、函數(shù)類型函數(shù)類型 函數(shù)名（函數(shù)參數(shù)表）函數(shù)名（函數(shù)參數(shù)表） 語句序列；語句序列； 北京林業(yè)大學信息學院 4:04 （4 4）內(nèi)存的動態(tài)分配與釋放）內(nèi)存的動態(tài)分配與釋放使用使用new和和delete動態(tài)分配和釋放內(nèi)存空動態(tài)分配和釋放內(nèi)存空間間分配空間指針變量分配空間指針變量=new數(shù)據(jù)類型數(shù)據(jù)類型;釋放空間釋放空間delete指針變量指針變量;（5 5）賦值語句）賦值語句（6 6）選擇語句）選擇語句（7 7）循環(huán)語句）循環(huán)語句北京林業(yè)大學信息學院 4:04 （8）使用的結束語句形式有：使用的結束語句形式有：函數(shù)結束語句函數(shù)結束語句 return return 循環(huán)結束語句循環(huán)結束語句 break

21、;break;異常結束語句異常結束語句 exitexit（異常代碼）；（異常代碼）；北京林業(yè)大學信息學院 4:04 （9）輸入輸出語句形式有：輸入輸出語句形式有：輸入語句 cin (scanf( )輸出語句 cout (printf( )（10）擴展函數(shù)有：擴展函數(shù)有：求最大值 max求最小值 min人民郵電出版社北京林業(yè)大學信息學院 4:04 1.4 算法和算法分析算法和算法分析北京林業(yè)大學信息學院 4:04 人民郵電出版社北京林業(yè)大學信息學院 4:04 人民郵電出版社北京林業(yè)大學信息學院 4:04 算法效率：用依據(jù)該算法編制的程序在計算機上算法效率：用依據(jù)該算法編制的程序在計算機上執(zhí)行所消

22、耗的時間來度量執(zhí)行所消耗的時間來度量事后統(tǒng)計事后統(tǒng)計事前分析估計事前分析估計北京林業(yè)大學信息學院 4:04 1.1.事后統(tǒng)計：事后統(tǒng)計：利用計算機內(nèi)的計時功能，不同算法利用計算機內(nèi)的計時功能，不同算法的程序可以用一組或多組相同的統(tǒng)計數(shù)據(jù)區(qū)分的程序可以用一組或多組相同的統(tǒng)計數(shù)據(jù)區(qū)分 缺點：缺點：必須先運行依據(jù)算法編制的程序必須先運行依據(jù)算法編制的程序所得時間統(tǒng)計量依賴于硬件、軟件等環(huán)境因素所得時間統(tǒng)計量依賴于硬件、軟件等環(huán)境因素，掩蓋算法本身的優(yōu)劣，掩蓋算法本身的優(yōu)劣 北京林業(yè)大學信息學院 4:04 2.2.事前分析估計：事前分析估計：一個高級語言程序在計算機上運行所消耗的時間取一個高級語言程序

23、在計算機上運行所消耗的時間取決于：決于： 依據(jù)的算法選用何種策略依據(jù)的算法選用何種策略 問題的規(guī)模問題的規(guī)模 程序語言程序語言 編譯程序產(chǎn)生機器代碼質量編譯程序產(chǎn)生機器代碼質量 機器執(zhí)行指令速度機器執(zhí)行指令速度 同一個算法用不同的語言、不同的編譯程序、在不同同一個算法用不同的語言、不同的編譯程序、在不同的計算機上運行，效率均不同，的計算機上運行，效率均不同，使用使用絕對時絕對時間單位間單位衡量算法效率不合適衡量算法效率不合適北京林業(yè)大學信息學院 4:04 算法中關鍵操作關鍵操作（循環(huán)和遞歸）（循環(huán)和遞歸）重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n),算法的時間量度記作：T(n)=T(n)=O(

24、f(n)(f(n) 時間復雜度的漸進表示法時間復雜度的漸進表示法漸進符號（漸進符號（O）的定義：當且僅當存在一個正的常數(shù)）的定義：當且僅當存在一個正的常數(shù) C C和和n0 ，使得對所有的，使得對所有的 n n0 ，有，有 T(n) T(n) Cf(n) Cf(n)，則，則T(n) = O(f(n)表示隨著n的增大，算法執(zhí)行的時間的增長率和f(n)的增長率相同，稱漸近時間復雜度漸近時間復雜度。北京林業(yè)大學信息學院 4:04 n * n階矩陣加法：階矩陣加法：for( i = 0; i n; i+)for( j = 0; j n; j+)cij = aij + bij;語句的頻度語句的頻度（Fre

25、quency Count ): 重復執(zhí)行的次數(shù)：重復執(zhí)行的次數(shù)：n*n;T( n ) = O ( n 2)即：矩陣加法的運算量和問題的規(guī)模即：矩陣加法的運算量和問題的規(guī)模n的平方是同一個量級的平方是同一個量級北京林業(yè)大學信息學院 4:04 x = 0; y = 0;for ( int k = 0; k n; k + ) x +;for ( int i = 0; i n; i+ ) for ( int j = 0; j n; j+ ) y +;T1(n) = O(1)T2(n) = O(n)T3(n) = O(n2)T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n,

26、 n2 ) ) = O(n2)北京林業(yè)大學信息學院 4:04 void exam ( float x , int m, int n ) float sum ; for ( int i = 0; i m; i+ ) /x中各行 sumi = 0.0; /數(shù)據(jù)累加 for ( int j = 0; j n; j+ ) sumi += xij; /關鍵操作關鍵操作 for ( i = 0; i m; i+ ) /打印各行數(shù)據(jù)和 cout i “ : ” sum i endl; /關鍵操作關鍵操作 漸進時間復雜度為 O(max (m*n, m)算法的時間復雜度是由算法的時間復雜度是由嵌套最深層嵌套最深

27、層語句的頻度決定的語句的頻度決定的北京林業(yè)大學信息學院 4:04 例1：NN矩陣相乘for(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij=cij+aik*bkj; 算法中的基本操作語句為算法中的基本操作語句為cij=cij+aikcij=cij+aik* *bkj;bkj; 233111111( )1()nnnnnnijkijiT nnnno n 3T nO n北京林業(yè)大學信息學院 4:04 例例2：for( i=1; i=n; i+) for (j=1; j=i; j+) for (k=1; k=j; k+)x=x+1;niniijniijjkiij1111112)1(16)2)(1(2)1(6)12)(1(2121112nnnnnnnniinini語