數據結構與算法是北京大學於2018年02月26日首次在中國大學MOOC開設的慕課課程，是國家精品線上開放課程。該課程授課教師為張銘、陳斌、盧宗青、劉雲淮、趙海燕、宋國傑、黃駿、鄒磊、王騰蛟。據2021年2月中國大學MOOC官網顯示，該課程已開課4次。
數據結構與算法課程內容包括數據結構與抽象數據類型、算法特性及分類、算法效率與度量、線性結構、順序表、鍊表、棧與佇列、棧與遞歸、遞歸轉非遞歸、字元串的存儲結構、字元串運算的算法實現、字元串的快速模式匹配、二叉樹的抽象數據類型、二叉樹的搜尋、二叉樹的存儲結構、樹與二叉樹的等價轉換、樹的抽象數據類型及樹的遍歷、樹的鏈式存儲結構、樹的父指針表示法、樹的順序存儲和K叉樹、圖的概念和抽象數據類型、圖的存儲結構、圖的遍歷、內排序、檢索等內容。
基本介紹
- 中文名：數據結構與算法
- 開課時間：2018年02月26日（首次）
- 提供院校：北京大學
- 類別：國家精品線上開放課程
- 授課平台：中國大學MOOC
- 授課教師：張銘、陳斌、盧宗青、劉雲淮、趙海燕、宋國傑、黃駿、鄒磊、王騰蛟
課程性質,課程背景,課程定位,適應對象,開課信息,課程簡介,課程大綱,課前預備,預備知識,學習資料,授課目標,所獲榮譽,教師簡介,
課程性質
課程背景
計算機是現代社會中用於解決問題的重要工具，支撐這個工具高效運轉的就是其後的各種系統程式、應用程式。數據結構，是抽象的表示數據的方式；算法，則是計算的一系列有效、通用的步驟。算法與數據結構是程式設計中相輔相成的兩個方面，是計算機學科的重要基石。
課程定位
數據結構與算法是介紹基本數據結構以及相關的經典算法，強調問題-數據-算法的抽象過程，關注數據結構與算法的時間空間效率，培養學生編寫出高效程式從而解決實際問題的綜合能力的一門課程。
適應對象
數據結構與算法適合計算機以及相關理工專業的本科生學習。對於具有C語言結構化程式設計基礎的學生，該課程第0章補充了一些面向對象的基本內容。
開課信息
開課次數 | 開課時間 | 學時安排 | 授課教師 | 參與人數 |
|---|---|---|---|---|
第1次開課 | 2018年02月26日 ~ 2018年07月01日 | 4-8小時每周 | 張銘、陳斌、盧宗青、劉雲淮、趙海燕、宋國傑、黃駿、鄒磊 | 30697 |
第2次開課 | 2018年09月17日 ~ 2019年01月13日 | 4-8小時每周 | 張銘、陳斌、趙海燕、宋國傑、黃駿、鄒磊、王騰蛟 | 50179 |
第3次開課 | 2019年09月09日 ~ 2020年01月13日 | 3-5小時每周 | 張銘、趙海燕、王騰蛟、宋國傑、黃駿、鄒磊 | 55514 |
第4次開課 | 2020年09月21日 ~ 2021年01月20日 | 3-5小時每周 | 張銘、王騰蛟、趙海燕、宋國傑、鄒磊 | 13281 |
（以上表格內容參考資料：）
課程簡介
數據結構與算法圍繞著“算法+數據結構=程式”的思路，以問題求解為導向進行學習，運用問題抽象、數據抽象、算法抽象來分析問題，套用適當的數據結構和算法來設計和實現相應的程式。在求解實際問題方面，該課程會學習到通過權衡時空和其他資源開銷，利用數據結構來組織數據、設計高效的算法、完成高質量的程式以滿足錯綜複雜的實際套用需要。課程所學到的內容會被利用到計算機科學後續的各個課程中，如作業系統、軟體工程、資料庫概論、編譯技術、計算機圖形學、人機互動等。
課程大綱
第一章 概論（兩周） | 4.4字元串的快速模式匹配（選修） | 8.4交換排序（冒泡排序、快速排序） |
1.1課程介紹 | 第五章 二叉樹（兩周） | 8.5歸併排序 |
1.2問題求解 | 5.1二叉樹的概念 | 8.6桶排序 |
1.3數據結構與抽象數據類型 | 5.2二叉樹的抽象數據類型 | 8.7靜態基數排序（選修） |
1.4算法特性及分類 | 5.3二叉樹的搜尋 | 8.8鏈式基數排序（選修） |
1.5算法效率與度量 | 5.4二叉樹的存儲結構 | 8.9索引排序（選修） |
1.6補充 面向對象簡介（選修） | 5.5二叉搜尋樹 | 8.10排序算法的時間代價 |
1.7補充 類的特殊成員（選修） | 5.6堆與優先佇列 | 第十章 檢索 |
1.8補充 模版函式與模版類（選修） | 5.7 Huffman樹及其套用 | 10.1檢索的概念 |
1.9補充 輸入輸出流（選修） | 第六章 樹 | 10.2基於線性表的檢索 |
第二章 線性表 | 6.1樹的定義、樹與二叉樹的等價轉換 | 10.3集合的檢索 |
2.1線性結構 | 6.2樹的抽象數據類型及樹的遍歷 | 10.4散列表的概念和散列函式 |
2.2順序表 | 6.3樹的鏈式存儲結構 | 10.5散列衝突處理 |
2.3鍊表 | 6.4樹的父指針表示法（選修） | 10.6散列的實現及性能分析 |
2.4順序表和鍊表的比較 | 6.5樹的順序存儲和K叉樹 | 擴展：第九章（選修） |
第三章 棧與佇列 | 第七章 圖 | 9.1 主存儲器和外存儲器 |
3.1棧 | 7.1圖的概念和抽象數據類型 | 9.2 檔案的組織和管理 |
3.2棧與遞歸 | 7.2圖的存儲結構 | 9.3 外排序 |
3.3遞歸轉非遞歸（選修） | 7.3圖的遍歷 | 擴展：字典（選修） |
3.4佇列 | 7.4最短路徑 | B樹B+樹 |
3.5佇列的套用 | 7.5最小生成樹 | Trie 樹 |
第四章 字元串 | 第八章 內排序（兩周） | AVL樹 |
4.1字元串基本概念 | 8.1 排序問題的基本概念 | Splay樹 |
4.2字元串的存儲結構 | 8.2插入排序 ( Shell 排序) | （課程大綱排版從左到右列） |
4.3字元串運算的算法實現 | 8.3選擇排序 (堆排序) |
課前預備
預備知識
學習數據結構與算法課程需要下面課程裡面的部分基本知識：
建議先修過計算概論等課程，最好具備C++等面向對象的程式設計基礎。
學習資料
書名 | 作者 | ISBN | 出版時間 | 出版社 |
|---|---|---|---|---|
《數據結構與算法》 | 張銘，王騰蛟，趙海燕 | 9787040239614 | 2008年6月 | 高等教育出版社 |
《數據結構與算法實驗教程》 | 張銘，趙海燕，王騰蛟 | 9787040302141 | 2011年1月 | |
《數據結構與算法－－學習指導與習題解析》 | 張銘、趙海燕、王騰蛟 | 704017829X | 2005年10月 | 高等教育出版社 |
《數據結構算法與套用—C++語言描述》 | S. Sahni著，汪詩林等譯 | 9787111076452 | 2000年 | |
Algorithms Design Techniques and Analysis | M. H. Alsuwaiyel | 9789810237400 | 2003年1月 | 電子工業出版社影印 |
Inroduction to Algorithms | T. H.Cormen, C. E.Leiserson, R. L. Rivest, C. Stein | / | 2002年5月 | 高等教育出版社影印 |
《電腦程式設計藝術，第1卷基本算法》 | D. E.Knuth著，蘇運霖譯 | 9787118027990 | 2002年 | |
Algorithm Design | J. Kleinberg, E. Tardos | 9780321295354 | 2005年 | Addison Wesley |
Data Structures and Algorithm Analysis in C++, Third Edition | C. A. Shaffer | 9780486485829 | 2011年 | Dover Publications |
《算法設計與分析》 | 王曉東 | 9787302061861 | 2003年1月 | 清華大學出版社 |
（表格內容參考資料：）
授課目標
通過學習此課程，提高理論、抽象、設計的能力；在紮實的經典理論基礎上，運用問題抽象、數據抽象、算法抽象來分析問題，套用適當的數據結構和算法來設計和實現相應的程式；通過課程學習，抽象思維能力、問題求解能力能得到較大提升，編程能力和代碼質量會有質的飛躍。
所獲榮譽
2019年1月8日，數據結構與算法被中華人民共和國教育部認定為“國家精品線上開放課程”。
教師簡介
張銘，北京大學信息科學技術學院教授。
陳斌，北京大學地球與空間科學學院教授。
盧宗青，北京大學助理教授。
劉雲淮，北京大學研究員。
趙海燕，北京大學副教授。
宋國傑，北京大學信息科學技術學院副教授。
黃駿，北京大學高能效計算與套用中心助理教授。
鄒磊，北京大學教授。
王騰蛟，北京大學信息科學技術學院教授。
