數據結構與算法(上)

課程簡介

計算機是現代社會中用于解決問題的重要工具。利用計算機解決實際問題需要將問題抽象，并對數據進行操作，最后通過計算機程序求解問題。而本門課程主要內容就是對以上內容進行研究。

課程大綱

第一章 概論

1.1課程介紹

1.2問題求解

1.3數據結構與抽象數據類型

1.4算法特性及分類

1.5算法效率與度量

1.6補充  面向對象簡介

1.7補充  類的特殊成員

1.8補充 模版函數與模版類

1.9補充 輸入輸出流

第二章 線性表

2.1線性結構

2.2順序表

2.3鏈表

2.4順序表和鏈表的比較

第三章 棧與隊列

3.1棧

3.2棧與遞歸

3.3遞歸轉非遞歸（選修）

3.4隊列

3.5隊列的應用

第四章 字符串

4.1字符串基本概念  

4.2字符串的存儲結構  

4.3字符串運算的算法實現

4.4字符串的快速模式匹配（選修）

第五章 二叉樹（上）

5.1二叉樹的概念  

5.2二叉樹的抽象數據類型  

5.3二叉樹的搜索    

5.4二叉樹的存儲結構

第六章 二叉樹（下）

6.1二叉搜索樹  

6.2堆與優先隊列

6.3Huffman樹及其應用

第七章 樹

7.1樹的定義、樹與二叉樹的等價轉換

7.2樹的抽象數據類型及樹的遍歷  

7.3樹的鏈式存儲結構    

7.4樹的父指針表示法  

7.5樹的順序存儲和K叉樹  

第八章 圖

8.1圖的概念和抽象數據類型

8.2圖的存儲結構  

8.3圖的遍歷    

8.4最短路徑

8.5最小生成樹  

課程說明

本課程采用張銘主編的國家“十一五”規劃教材《數據結構與算法》（高等教育出版社）。適合計算機以及相關理工專業的大二本科生學習，需要先修過計算概論等課程，具有結構化和面向對象的程序設計基礎。

課程主要包括的內容有：線性表，棧與隊列，字符串，二叉樹，樹，圖，排序（內排序，外排序），檢索，索引，高級數據結構、以及數據結構應用。課程持續16周（分為兩個部分，每個8周），學習者每周在本課程上需要投入4－8小時。在第一部分學完了線性表、棧與隊列、字符串、二叉樹、樹和圖這些基礎數據結構之后，第二部分我們將深入學習排序、檢索、索引、高級數據結構以及數據結構應用等內容。涉及快速排序、外排序等各種經典排序算法，集合、散列、位圖等檢索方法，B/B+樹、Trie樹等索引結構，廣義表、多維數組等高級線性結構，AVL、紅黑樹、伸展樹等平衡二叉樹。第二部分課程持續8周，學習者每周在本課程上需要投入4－8小時。本課程的本次開設得到Google研究經費支持。

參考資料

[1] 張銘，王騰蛟，趙海燕，《數據結構與算法》，高等教育出版社，2008年 6月。普通高等教育“十一五”國家級規劃教材。
Textbook: Ming Zhang, Tengjiao Wang, Haiyan Zhao, "Data Structures and Algorithms", Higher Education Press, 2008.
[2] 張銘，趙海燕，王騰蛟，《數據結構與算法實驗教程》，高等教育出版社，2011年 1月。普通高等教育“十一五”國家級規劃教材。
[3] 張銘、趙海燕、王騰蛟，《數據結構與算法－－學習指導與習題解析》，高等教育出版社，2005年 10月。 “十五”國家級規劃教材配套參考書。
[4] S. Sahni ，《數據結構算法與應用—C++語言描述》 ，汪詩林等譯，機械工業出版社，2000.
[5] M. H. Alsuwaiyel, Algorithms Design Techniques and Analysis, 電子工業出版社影印，2003年1月。
[6] T. H.Cormen, C. E.Leiserson, R. L. Rivest, C. Stein, Inroduction to Algorithms, 高等教育出版社影印，2002年5月。
[7] D. E.Knuth 著，蘇運霖 譯，《計算機程序設計藝術，第1卷基本算法》，國防工業出版社，2002年。
[8] J. Kleinberg, E. Tardos. Algorithm Design. Addison Wesley, 2005.
[9] C. A. Shaffer, Data Structures and Algorithm Analysis in C++, Third Edition, Dover Publications., 2011.
[10] 王曉東，《算法設計與分析》 ，清華大學出版社，2003年1月。

拓展閱讀

其他

主講教師

張銘   教授

北京大學信息科學技術學院教授，ACM Education Council惟一的中國委員兼任中國ACM教育專委會主席，ACM中國教育專委會主席，CCF教育工委會副主任。自1984年考入北京大學，分別獲得學士、碩士和博士學位。研究方向為文本挖掘、社會網絡分析等，目前主持國家自然科學基金和教育部博士點基金在研項目。合作發表學術論文100多篇（不乏TKDE、ICML、KDD、AAAI、ACL、WWW等A類會議和期刊），獲得機器學習頂會ICML2014最佳論文獎，獲得網絡領域頂級會議WWW2016最佳論文提名。出版學術專著1部，獲軟件著作權6項，獲發明專利3項。主編多部教材，其中2部教材為國家“十一五”規劃教材，《數據結構與算法》獲北京市精品教材獎并得到國家“十二五”規劃教材支持。主持的“數據結構與算法”被評選為國家級和北京市級精品課程。

趙海燕   副教授

暫無簡介

宋國杰   副教授

暫無簡介

王騰蛟   教授

王騰蛟，男，北京大學信息學院教授，博士生導師。北京大學文理大數據研究中心常務副主任、先進技術研究院數據與知識工程研究中心主任。中國軟件行業協會數據庫及應用軟件分會秘書長，中國計算機學會數據庫專委會委員，大數據專委會委員。

黃駿   講師

暫無簡介

鄒磊   教授

暫無簡介

課程助教