1、算法與數據結構內容概述2007年2月262n主講：胡俊峰 n教材： 算法與數據結構C語言描述（第二版） 張乃孝 高等教育出版社n教學參考： 本教材的學習輔導及習題詳解 電子工業(yè)出版社其他網上資料： 課程基本情況3上課安排：n周一 7-8節(jié)， 周五 9-10節(jié)(雙) 地點： 理教 109n周1 11-12節(jié) 上機 （第三周開始上機）4課程主要內容：n理解掌握常用的數據結構n掌握算法的設計技術，了解算法分析技術n算法與程序設計實踐nC+面向對象程序設計簡介*5所需要的其他相關知識nC語言程序設計（課程基礎）nC語言文件操作n離散數學6課時安排計劃n數據結構與算法的基本內容 34 學時n離散數學相關

2、內容簡介 2學時n算法實踐 4學時n面向對象編程 6 學時7課程考核方式n作業(yè)與平時成績：10% + 10%n算法與程序設計實踐：20%n期末考試：60%8課程內容簡介n什么是數據結構？n什么是算法？n算法 + 數據結構 ADT9什么是數據結構？ 從數據抽象到結構抽象1+2+,- ,*,10從數據抽象到結構抽象（線性結構）11n數據結構： 同類型數據元素組成的具有某種關系的集合體。n線性結構： （1）存在唯一的一個被稱做“第一個第一個”的數據元素；（2）存在唯一的一個被稱做“最后一個最后一個”的數據元素；（3）除第一個之外，集合中的每個數據元素均只有一個前驅前驅； （4）除最后一個之外，集合中

3、每個數據元素均只有一個后繼后繼。 從數據抽象到結構抽象（線性結構續(xù)）12從數據抽象到結構抽象（線性結構續(xù)） 線性結構的具體實現nint a20;nint p = a; p+;13Nodetype *s = head;if (s != NULL) s = s-next;從數據抽象到結構抽象（線性結構續(xù)） 線性結構的具體實現14從數據抽象到結構抽象（樹結構）上下位關系兄弟關系狀元進士舉人秀才部長局長處長科長自然科學計算機科學軟件理論算法與數據結構15由多個樹構成的森林 MM 定理16最短路經與關鍵路徑（圖）17所謂數據結構：n是研究元素集合中元素間相關關系結構的學問。n對于數據結構研究來講，元素的

4、類型、屬性并不重要，通過何種方式建立元素之間的關系也不重要。關心的是由元素間特定的關系結構所帶來的性質、問題以及解決方案。18數據結構與算法n單純意義上的元素間關系結構的討論屬于圖論所研究的問題。n只有當數據元素的關系結構與算法結合在一起并表現出特定的應用特征的時候才真正進入計算機科學研究的領域。19數據結構與算法（隊列）n多個隊列 VS 單個隊列n多任務時間片輪轉服務First Come First Service（queue）20數據結構與算法（排序與索引技術）自然科學自然科學社會科學社會科學期刊雜志期刊雜志TPTP311-TP312TP311.1221數據結構的實現與維護n隊列的實現與維

5、護： 前方刪除、后方加入。數組？鏈表？n索引結構的維護： 在合適的地方插入?？臻g溢出？n圖的計算機內部表示： 22抽象數據類型First Come First Service（queue）數據結構的物理實現InQueueOutQueueIsEmptyOverflowQueue（ADT）對外操作接口結構數據維護接口23抽象數據類型（續(xù)）First Come First Service（queue）數據結構的物理實現InQueueOutQueueIsEmptyOverflowQueue（ADT）對外操作接口結構數據維護接口24抽象數據類型（續(xù)）n數據結構 + 數據操作三元組表示：（D，S，P）其中

6、D是數據對象，S是D上的關系集，P是對D的基本操作集。25如何在計算機中表示數據對象？n基本數據類型 int floatn復合數據類型 struct node int i; node *next; ; typedef struct node inode;26如何表示數據對象間的關系n數組的順序存放用來表示線性關系 起始節(jié)點為下標為0的節(jié)點？ 尾節(jié)點？n鏈表用來表示線性關系 head指針 ptr != Null ，tail指針？ 27如何表示數據對象間的關系（續(xù)）n通過多維數組來表示關系 define MAXCONN 200; Node relation 2MAXCONN;n通過id來代替具體的

7、數據對象建立關系 Node elemSetNUMELEM = ; int relation 2MAXCONN;28通過關系數據庫中的表來表示關系：29如何在高級語言中實現自定義的ADTn類: 數據定義 + 操作定義Class Nameprivate: /access restriction a list of variable declarations; public: a list of function prototypes; / headerClass function definitions;30如何在高級語言中實現自定義的ADT31常見的ADTnBBS: 發(fā)貼，回帖， 刪貼n圖書館系

8、統(tǒng)nEmail系統(tǒng)32軟件的分層與ADT33算法與數據結構課程的主要目的n研究幾種常用數據結構（抽象數據類型）的實現方法及其常見應用。n掌握通過使用自定義數據結構與算法來實現程序的功能化模塊封裝的基本方法。n理解掌握幾種常用的問題求解方法與算法思路。n理解算法分析的相關內容。34如何把握課程的重點n是本次課的重點內容，要求理解掌握。n屬于課程的核心內容，在本次課只是進行引入性的介紹，后繼課程還會有更詳細的講解。要求掌握在知識體系中的位置，具體操作與算法可留后。n屬于一般了解性內容。n屬于擴展介紹性內容，主要為了幫助核心概念的理解。35如何使用教材及習題解n有精力和興趣的同學可以通讀。n要注意思考： 為什么這樣實現？能用在那些問題上？ 這樣的數據結構有什么好處、弱點？n配合課堂講授的內容重點概念的定義、重點算法的實現要認真閱讀掌握。36關于網上的教學參考資料n了解基本思路及內容。n可以閱讀課堂上推