課程簡介

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

課程大綱


第一章 概論

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周),學習者每周在本課程上需要投入48小時。在第一部分學完了線性表、棧與隊列、字符串、二叉樹、樹和圖這些基礎數據結構之后,第二部分我們將深入學習排序、檢索、索引、高級數據結構以及數據結構應用等內容。涉及快速排序、外排序等各種經典排序算法,集合、散列、位圖等檢索方法,B/B+樹、Trie樹等索引結構,廣義表、多維數組等高級線性結構,AVL、紅黑樹、伸展樹等平衡二叉樹。第二部分課程持續8周,學習者每周在本課程上需要投入48小時。本課程的本次開設得到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,
電子工業出版社影印,20031月。
[6] T. H.Cormen, C. E.Leiserson, R. L. Rivest, C. Stein, Inroduction to Algorithms,
高等教育出版社影印,20025月。
[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]
王曉東,《算法設計與分析》 ,清華大學出版社,20031月。

拓展閱讀

其他

主講教師

張銘   教授

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

趙海燕   副教授

暫無簡介

宋國杰   副教授

暫無簡介

王騰蛟   教授

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

黃駿   講師

暫無簡介

鄒磊   教授

暫無簡介

課程助教

  • wangzhuo

  • zhujile

  • 李浩然

  • 馮雪松

  • 黃梓銘

  • dulun2834

  • 李博遠

  • Seter

  • zhuting.cs

  • bookug

  • 張一舟[宋老師201

  • ztan

  • shanxigy

  • jingpinmooc

  • 張筱雅

  • liushixing

相關課程推薦

  • 正在進行
    計算機組成
    本課程的重點在于計算機內部的主要部件以及各部件之間的聯系,主要內容包括:馮·諾依曼計算機結構的要點,計算機執行指令的工作過程,當前流行的指令系統的分析對比,高級語言、匯編語言和機器語言之間的關系等。
  • 正在進行
    數據結構與算法(下)
    計算機是現代社會中用于解決問題的重要工具。利用計算機解決實際問題需要將問題抽象,并對數據進行操作,最后通過計算機程序求解問題。而本門課程主要內容就是對以上內容進行研究。 該課程并未正式開課,報名后僅提供前三周課程視頻預覽,開課信息敬請持續關注。
  • 正在進行
    解密教育的技術變革史
    互聯網并非人類歷史上第一次“信息技術”革命。人類歷史上一共出現過5種媒介技術:口頭語言、手工抄寫/羊皮書、印刷技術、廣播電視和互聯網。 媒介技術提供的記錄和傳承功能,對人類的群體社會認知,帶來了革命性的影響。西方歷史上曾經發生的兩次文明的大發展,都正好處于媒介技術變革前后。希臘文明處于希臘從口傳到手工抄寫的媒介技術變革中;近代科學史上的哥白尼革命,又正好處于歐洲從手工抄寫到機器印刷的技術轉型中;今天,輪到了信息技術…… 吟唱、詩歌、戲曲、繪畫、文字書寫等,都曾經是一種表達“技術”;《荷馬史詩》、《圣經》都曾經充當過識字課本;口頭語言、羊皮紙卷、印刷書、廣播電視,都是曾經的“教育技術”。 這門課程從重新定義教育和人這兩個核心概念開始,帶著你從媒介史、知識產業分工配套體系、教學模式和教育組織方式等不同的視角,游歷人類一路走來傳播生態環境、知識產業、教育教學的發展過程,從中尋找媒介技術影響教育變革的規律,指導學習者迎接未來教育變革的挑戰,尋找創新和發展方向!

恭喜,報名成功

進入學習中心

恭喜,報名成功

確定

請進入開課界面預覽

確定

X

請去您的郵箱驗證

還沒收到驗證郵件?

1. 試試去廣告郵件、垃圾郵件目錄看看

2. 再次發送驗證郵件

對不起,班次容量已滿

請報名下一班次

知道了~!

對不起,您沒有操作權限

知道了~!

香蕉视频在线观看