數據結構與算法課程是電子科技大學於2018年02月26日首次在中國大學MOOC開設的慕課課程、國家精品線上開放課程。該課程授課教師為林劼、戴波、劉震、周益民。據2021年3月中國大學MOOC官網顯示，該課程已開課7次。
數據結構與算法課程共6個模組，包括緒論、線性表、查找、排序、遞歸與分治、樹與二叉樹、圖論與貪心算法、動態規劃等內容。
基本介紹
- 中文名：數據結構與算法
- 類別：慕課、國家精品線上開放課程
- 提供院校：電子科技大學
- 授課教師：林劼、戴波、劉震、周益民
- 授課平台：中國大學MOOC
- 開課時間：2018年02月26日（首次）
課程性質,課程定位,適應對象,開課信息,課程簡介,課程大綱,課前預備,預備知識,學習資料,授課目標,所獲榮譽,教師簡介,
課程性質
課程定位
數據結構與算法課程是計算機科學與技術的學科基礎課程，也是是計算機圖形學、計算機網路、編譯原理、計算機作業系統等後續課程的基礎理論之一，其套用範圍也早已擴展到圖像處理與模式識別、海量數據挖掘、科學數據處理、複雜網路分析等許多計算機前沿領域。
適應對象
數據結構與算法課程適合有程式設計語言基礎的同學學習。
開課信息
開課次數 | 開課時間 | 授課教師 | 學時安排 | 參與人數 |
|---|---|---|---|---|
第1次開課 | 2018年02月26日~2018年07月20日 | 林劼、戴波、劉震 | 3~4小時每周 | 26275人 |
第2次開課 | 2018年09月01日~2019年01月31日 | 3~5小時每周 | 24898人 | |
第3次開課 | 2019年02月20日~2019年07月20日 | 18853人 | ||
第4次開課 | 2019年08月20日~2020年01月10日 | 21731人 | ||
第5次開課 | 2020年02月14日~2020年06月30日 | 12613人 | ||
第6次開課 | 2020年08月10日~2021年01月15日 | 林劼、戴波、劉震、周益民 | 19734人 | |
第7次開課 | 2021年02月15日~2021年06月30日 | 7232人 |
（註：表格內容參考資料）
課程簡介
該課程研究計算機處理數據的結構特性，學習線性表、樹、圖等常用數據結構的邏輯結構與存儲結構；學習分治遞歸、動態規劃、貪心算法等典型算法，掌握分析與推導算法效率的方法。
課程大綱
第一章 緒論（1周） 1，教學內容 （1）數據結紙巴虹構相關概念和術語。 （2）程式、數據結構、算法的關係。 （企料紋捉3）算法的定義及特性；算法的最壞複雜度性能分析，常見計算機算法的運行時間。 2，教學要求 （1）掌握：數據結構及算法的概念內涵、特點及作用；分析和計算算法的時間和空間複雜度。 （2）理解：算法分析的數學基礎，漸近表示的特點及其與精確數學表示的差異。 （3）了解：項目開發基本流程；分析程式效率的基本方法；常見算法的運行時間。 3，教學方法 多媒體課件結合板書面授 第二章 線性表、棧與佇列（2周） 1，教學內容 （1）線性表的定義、邏輯結構特點。 （2）線性表的存儲結構——順序存儲和鏈式存儲及其存儲特點。 （3）線性表的基本操作——查找、插入、刪除在順序存儲及鏈式存儲結構上的具體編程實現。 （4）各種變形鍊表（循環鍊表、雙向鍊表、帶頭結點的鍊表等）的含義及基本操作的編程實現。 （5）數組的地址計算方法。 （6）棧、佇列的定義，棧與佇列在兩種存儲結構上的實現。循環佇列的判滿、判空方法。棧與佇列的簡單套用。 2，教學要求 （1）掌握 （a）(線性表的兩種存儲表示及其實現。 （b）順序表和鍊表的一些常見操作及編程實現，及這兩種線性結構各自適用的套用場合。運用線性表解決一些簡單的實際問題。 （c）棧和佇列定義、特徵及基本操作。循環佇列的入隊、出隊、判滿、判空等基本操作。 （2）理解 （a）線形表的4類基本操作類型。 （b）順序表和鍊表在存儲及實現上的異同。 （櫃匙設c）佇列的假溢出。 （d）變形鍊表的存儲特徵及用途 （e）數組的地址計算方法。 （3）了解 3，教學方法 （1）多媒體課件結合板書面授； （2）多媒體課件結合示例代碼講解、分析和演示； （3）程式編寫與調試演示； （4）上機編程練習與輔導 第三章 查找、排序與分治遞歸（3周，每個內容各1周） 1，教學內容 （1）查找的基本概念良簽嚷。順序查找、折半查找、索引查找的方法。 （2）哈希表的基本概念，哈希函式構造方法及衝突處理策略，哈希表的查找、插入、刪除等操作方法。 （3）排序的基本概念。各種內部排序算法，包括插入排序、快速排序、選擇排序、歸併排序。各種排序算法的性能及複雜度分析。 （4）分治遞歸算法的思想，分治遞歸算法設計基本步驟，利用分治遞歸的思想設計：大整數乘法。 （膠紋5）利用代催她糊嫌換法、遞歸樹與主方法求解遞歸式。 2，教學要求 （1）掌握 （a）順序查找、折半查找、索引查找以及哈希表的查找方法。 （b）哈希函式的基本構造方法，解決地址衝突的一些基本策略。 （c）直接插入排序、折半插入排序等插入排序算法；屑恥乃冒泡排序和快速排序等交換排序算法；簡單選擇排序算法；歸併排序算法。 （d）分治遞歸方法及其套用：大整數乘法。 （e）利用主方法求解遞歸式表達式。 （2）理解 （a）各查找算法的時間複雜度和空間複雜度。 （b）分治遞歸算法的解題思路。 （c）代換法和遞歸樹求解遞歸式的過程和方法。 （3）了解 （a）各種排序算法的穩定性和時空性能分析過程。 （b）分治遞歸算法的思想。 3，教學方法 （1）多媒體課件結合板書面授； （2）多媒體課件結合示例代碼講解、分析和演示； （3）程式編寫與調試演示； （4）上機編程練習與輔導。 （5）程式編寫與課堂討論； 第四章 樹與二叉樹（2周） 1，教學內容 | （1）二叉樹和樹的遞歸定義和基本性質。 （2）滿二叉樹和完全二叉樹的概念及特徵。 （3）二叉樹、樹及森林的順序存儲及鏈式存儲，各種遍歷方法及相互間的轉換。 （4）二叉排序樹、平衡二叉樹的構建、結點查找、插入與刪除。 （5）哈夫曼樹的構建和哈夫曼編碼。 （6）二叉樹及樹的典型套用——堆排序。 2，教學要求 （1）掌握 （a）二叉樹、樹、森林的基本概念、遍歷以及他們之間的相互轉換。 （b）二叉樹的基本性質。 （c）二叉排序樹的基本操作與編程實現。 （d）構建哈夫曼樹的方法。 （e）堆的定義、堆的建立與調整，堆排序的方法，堆與優先佇列的關係。 （f）滿二叉樹和完全二叉樹的概念和特徵。 （2）理解 （a）平衡二叉樹的構建及基本操作。 （b）哈夫曼編碼 （3）了解 B樹、2-3樹的定義及基本操作。 3，教學方法 （1）多媒體課件結合板書面授； （2）多媒體課件結合示例代碼講解、分析和演示； （3）提問式引導教學； （4）程式編寫與調試演示，課題討論； （5）上機編程練習與輔導 第五章 圖論與貪心算法（2周） 1，教學內容 （1）圖的基本概念，基本操作和存儲——鄰接矩陣、鄰接表（逆鄰接表）。 （2）圖的遍歷方法——深度優先和廣度優先。 （3）貪心算法思想，貪心算法基本要求，調度問題（Interval Scheduling）。 （4）圖的生成樹和最小生成樹，最小生成樹的兩種構建方法——普里姆和克魯斯卡爾。 （5）圖中兩結點以及所有結點間最短路徑的求取方法——迪傑斯特拉和弗洛伊德方法。 （6）有向無環圖的拓撲排序和關鍵路徑求取。 2，教學要求 （1）掌握 （a）圖的基本概念。 （b）圖的存儲結構——鄰接矩陣和鄰接表。 （c）圖基本操作——深度優先和廣度優先遍歷。 （d）最小生成樹，結點間的最短路徑，圖的拓撲排序以及關鍵路徑。 （e）貪心算法的設計思路，調度問題的貪心算法。 （2）理解 貪心算法的性質。 （3）了解 （a）圖的存儲結構——十字鍊表與鄰接多重表表示法的定義與存儲結構 （b）圖的連通分支、最大流、歐拉圖、哈密爾頓圖的套用。 （c）貪心算法的思想。 3，教學方法 （1）多媒體課件結合板書面授； （2）多媒體課件結合案例講解工程開發流程； （3）上機編程練習與輔導。 （4）項目驅動型教學； （5）程式編寫與課堂討論； 第六章 動態規劃（1周） 1，教學內容 （1）動態規划算法的思想；動態規劃技術及其特點。 （2）動態規劃與分治遞歸算法的區別。 （3）動態規劃套用：包括0-1背包問題、矩陣鏈乘法問題、文本相似度對比問題、裝配線調度問題、權重化的活動安排問題等。 2，教學要求 （1）掌握 （a）遞歸程式的動態規劃描述。 （b）動態規劃問題解題方法和典型套用：0-1背包問題、矩陣鏈乘法問題、文本相似度對比問題、權重化的活動安排問題。 （2）理解 動態規劃的基本原理、指導原則、基本步驟和最最佳化思想。 （3）了解 其他各種動態規划算法及其變形。 3，教學方法 （1）多媒體課件結合板書面授； （2）多媒體課件結合案例講解工程開發流程； （3）上機編程練習與輔導 （4）項目驅動型教學； （5）程式編寫與課堂討論。 |
（註：課程大綱排版從左到右列）
第一章 緒論 1-教學安排 3-算法 2-數據結構基本概念，術語與主要學習內容 緒論測驗 第二章2.1 線性表 （本章內容比較多，需要2周的學習時間） 5-棧 線性表測驗 1-線性表的基本概念 2-基於線性表操作的簡單套用 7-線性表的基本操作編程視頻（請儘量自己實現） 3-線性表的存儲結構及基本操作實現 4-線性表的套用 6-佇列 第二章 2.2 查找 2-順序查找 5-哈希查找 1-查找基本概念 3-折半查找 查找問題討論 4-索引查找 查找測驗 第二章 2.3 排序 3-選擇排序 2-插入排序 4-交換排序 5-基數排序 6-外部排序 | 排序測驗 1-排序的基本概念 第三章 遞歸與分治 1-遞歸 3-複雜度計算 2-分治 4-套用 遞歸與分治測驗 第四章 樹與二叉樹 （本章內容需要2周學習時間） 3-二叉樹的變形 4-樹與二叉樹的相互轉換 1-引子 2-二叉樹的定義與復原 AVL樹的補充 樹與二叉樹測驗 第五章 圖論與貪心算法（本章內容需要2周學習時間） 2-貪心算法理論 貪心算法作業 3-圖論與貪心算法的套用 1-圖論的基本概念 第六章 動態規劃 5-備忘錄法 2-動態規劃理論 6-項目實戰 3-動態規劃例子-矩陣連乘 動態規劃作業 1-引言 4-動態規劃要素 7-總結 |
（註：課程大綱排版從左到右列）
01緒論 推薦學習時間：1周 課時 1-教學安排 2-數據結構基本概念，術語與主要學習內容 3-算法 02線性表 推薦學習時間：2周 課時 1-線性表的基本概念 2-基於線性表操作的簡單套用 3-線性表的存儲結構及基本操作實現 4-線性表的套用 5-棧 6-佇列 7-線性表的基本操作編程視頻（請儘量自己實現） 03查找 推薦學習時間：1周 課時 1-查找基本概念 2-順序查找 3-折半查找 4-索引查找 5-哈希查找查找問題討論 04排序 推薦學習時間：2周 課時 1-排序的基本概念 2-插入排序 3-選擇排序 4-交換排序 5-基數排序 | 6-外部排序 05遞歸與分治 推薦學習時間：1周 課時 1-遞歸 2-分治 3-複雜度計算 4-套用 06樹與二叉樹 推薦學習時間：2周 課時 1-引子 2-二叉樹的定義與復原 3-二叉樹的變形 4-樹與二叉樹的相互轉換AVL樹的補充 07圖論與貪心算法 推薦學習時間:2周 課時 1-圖論的基本概念 2-貪心算法理論 3-圖論與貪心算法的套用 08動態規劃 推薦學習時間：2周 課時 1-引言 2-動態規劃理論 3-動態規劃例子-矩陣連乘 4-動態規劃要素 5-備忘錄法 6-項目實戰 7-總結 |
（註：課程大綱排版從左到右列）
第一章 緒論 1-教學安排 2-數據結構基本概念，術語與主要學習內容 3-算法 緒論測驗 第二章2.1 線性表 （本章內容比較多，需要2周的學習時間） 1-線性表的基本概念 2-基於線性表操作的簡單套用 3-線性表的存儲結構及基本操作實現 4-線性表的套用 5-棧 6-佇列 臨時補充內容：7-線性表的基本操作編程視頻（請儘量自己實現） 線性表測驗 第二章 2.2 查找 1-查找基本概念 2-順序查找 3-折半查找 4-索引查找 5-哈希查找 查找問題討論 查找測驗 第二章 2.3 排序 1-排序的基本概念 2-插入排序 3-選擇排序 4-交換排序 5-基數排序 | 6-外部排序 排序測驗 第三章 遞歸與分治 1-遞歸 2-分治 3-複雜度計算 4-套用 遞歸與分治測驗 第四章 樹與二叉樹 （本章內容需要2周學習時間） 1-引子 2-二叉樹的定義與復原 3-二叉樹的變形 4-樹與二叉樹的相互轉換 臨時補充：AVL樹 樹與二叉樹測驗 第五章 圖論與貪心算法（本章內容需要2周學習時間） 1-圖論的基本概念 2-貪心算法理論 3-圖論與貪心算法的套用 貪心算法測驗 第六章 動態規劃 1-引言 2-動態規劃理論 3-動態規劃例子-矩陣連乘 4-動態規劃要素 5-備忘錄法 6-項目實戰 7-總結 動態規劃測驗 |
（註：課程大綱排版從左到右列）
第一章 緒論 1-教學安排 2-數據結構基本概念，術語與主要學習內容 3-算法 緒論測驗 第二章2.1 線性表 （本章內容比較多，需要2周的學習時間） 1-線性表的基本概念 2-基於線性表操作的簡單套用 3-線性表的存儲結構及基本操作實現 4-線性表的套用 5-棧 6-佇列 臨時補充內容：7-線性表的基本操作編程視頻（請儘量自己實現） 線性表測驗 第二章 2.2 查找 1-查找基本概念 2-順序查找 3-折半查找 4-索引查找 5-哈希查找 查找問題討論 查找測驗 第二章 2.3 排序 1-排序的基本概念 2-插入排序 3-選擇排序 4-交換排序 5-基數排序 6-外部排序 排序測驗 | 第三章 遞歸與分治 1-遞歸 2-分治 3-複雜度計算 4-套用 遞歸與分治測驗 第四章 樹與二叉樹 （本章內容需要2周學習時間） 1-引子 2-二叉樹的定義與復原 3-二叉樹的變形 4-樹與二叉樹的相互轉換 臨時補充：AVL樹 樹與二叉樹測驗 第五章 圖論與貪心算法（本章內容需要2周學習時間） 1-圖論的基本概念 2-貪心算法理論 3-圖論與貪心算法的套用 貪心算法測驗 第六章 動態規劃 1-引言 2-動態規劃理論 3-動態規劃例子-矩陣連乘 4-動態規劃要素 5-備忘錄法 6-項目實戰 7-總結 動態規劃測驗 第二部分 數據結構全面複習 1-線性表 4-查找與排序 2-樹 3-圖 |
（註：課程大綱排版從左到右列）
課前預備
預備知識
學習數據結構與算法課程需具備程式設計語言（C，C++，java，python等任何一門語言）。
學習資料
書名 | 作者 | ISBN | 出版時間 | 出版社 |
|---|---|---|---|---|
《數據結構與算法》 | 林劼，劉震，陳端兵，戴波 | 978-7-301-29776-6 | 2018年 | 北京大學出版社 |
《數據結構與算法》 | 吳躍等 | 978-7-111-28825-1 | 2010年 | 機械工業出版社 |
《算法設計與分析》 | 王曉東 | 978-7-302-16343-5 | 2008年 | 清華大學出版社. |
《算法設計》 | Jon Kleinberg等 | 978-7-302-14335-2 | 2007年 |
（註：表格內容參考資料）
授課目標
通過對該課程的學習，能夠解決非數值計算與工程套用問題，達到選擇或設計恰當的邏輯結構、存儲結構及相應的算法的水平，為學生進一步理論學習和解決實際工程套用問題打下基礎。通過理論知識的系統學習與工程實驗的操作，初步培養學生的計算思維能力、算法設計與分析能力、程式設計與編程實現能力、計算機系統的認知、分析、設計和運用能力、工程實踐能力。
所獲榮譽
2020年，該課程被中華人民共和國教育部認定首批國家級一流本科課程。
教師簡介
該課程授課教師為電子科技大學教師團隊，其中林劼、戴波、劉震三位教師為電子科技大學副教授，周益民為電子科技大學教授。
教師簡介
該課程授課教師為電子科技大學教師團隊，其中林劼、戴波、劉震三位教師為電子科技大學副教授，周益民為電子科技大學教授。
