《數據結構》課程教學大綱
、
課程中文名稱: 數據結構。
課程英文名稱：Data Structures。
課程類別：專業基礎課 必修。
課程學分數：3（16學時為1學分）
課程學時數：講課32學時，上機16學時。
授課對象：計算機科學與技術專業。
本課程的前導課程：高級語言程序設計。
本課程的後續課程：作業系統、資料庫應用技術等。
一、教學目的
數據結構課程是計算機專業一門重要的專業基礎課。通過本課程的學習，使得學生從數據邏輯結構、存儲結構和基本運算算法設計三個層面掌握基本的數據組織和數據處理方法，能夠從問題出發設計面向數據結構的求解算法，具有基本的算法時間複雜度和空間複雜度分析能力，為後續課程如作業系統等課程學習打下較好的基礎。
二、教學要求
通過講授和上機實驗，使學生領會數據結構的基本原理，掌握線性表、棧和隊列、串、數組和稀疏矩陣、樹和二叉樹、圖、查找和排序等基本數據結構及其相關算法設計方法，具備較好的數據組織、數據存儲和數據處理能力。
三、授課課時安排（48學時）
知識單元
涵蓋知識點情況*
知識點學時
小計
1、緒論
1.1 什麼是數據結構
1.2 算法及其描述
1.3 Python簡介
1
2
1.4 算法分析：
①算法時間複雜度分析；②算法空間複雜度分析
1
2、線性表
2.1 線性表的定義
2.2 線性表的順序存儲結構：
①順序表以及線性表基本運算算法在順序表中的實現；②順序表的應用算法設計示例
2
4
2.3 線性表的鏈式存儲結構：
①單鍊表以及線性表基本運算算法在單鍊表中的實現；②單鍊表的應用算法設計示例；③雙鍊表以及線性表基本運算算法在雙鍊表中的實現；④雙鍊表的應用算法設計示例
2
3、棧和隊列
3.1 棧：
①棧的定義；②順序棧及其實現；③順序棧的應用算法設計示例；④鏈棧及其實現；⑤鏈棧的應用算法設計示例
2
4
3.2 隊列：
①隊列的定義；②順序隊及其實現；③順序隊的應用算法設計示例；④鏈隊及其實現；⑤鏈隊的應用算法設計示例
2
4、串和數組
4.1 串
①串的定義；②串的存儲結構—順序串和鏈串
1
2
4.2 數組：
①數組的基本概念；②特殊矩陣的壓縮存儲
1
5、樹和二叉樹
6.1 樹：
①樹的定義和邏輯表示；②樹的基本術語；③樹的性質；④樹的基本運算；⑤樹的存儲結構
1
6
6.2 二叉樹：
①二叉樹的概念；②二叉樹的性質；③二叉樹存儲結構
1
6.3 二叉樹先序、中序和後序遍歷：
①二叉樹遍歷的概念；②先序、中序和後序遍歷遞歸算法
1
6.4 二叉樹的層次遍歷：
①層次遍歷過程；②層次遍歷算法設計
1
6.5 二叉樹的構造
6.7 哈夫曼樹
6.8 二叉樹與樹、森林之間的轉換
2
6、圖
7.1 圖的基本概念
7.2 圖的存儲結構：
①鄰接矩陣；②鄰接表
1
5
7.3 圖的遍歷：
①圖遍歷的概念；②深度優先遍歷；③廣度優先遍歷
1
7.4 生成樹和最小生成樹：
①生成樹和最小生成樹的概念；②普裡姆算法；③克魯斯卡爾算法
1.5
7.5 最短路徑：
①最短路徑的概念；②狄克斯特拉算法；③弗洛伊德算法
1.5
7、查找
8.1 查找的基本概念
8.2 線性表的查找：
①順序查找；②折半查找；③索引存儲結構和分塊查找
2
5
8.3 樹表的查找：
①二叉排序樹；②平衡二叉樹
2
8.4 哈希表查找：
①哈希表的基本概念；②哈希函數構造方法；③哈希衝突解決方法；④哈希表查找及性能分析
1
8、排序
9.1 排序的基本概念
9.2 插入排序：
①直接插入排序；②折半插入排序；③希爾排序
1
4
9.3 交換排序：
①冒泡排序；②快速排序
1
9.4 選擇排序：
①簡單選擇排序；②堆排序
1
9.5 歸併排序
9.6 基數排序
1
*教材中所有帶"*"的內容均為提高知識點，不作為課堂講授內容以減少課堂學時，刪除遞歸一章的課堂講授。知識單元
涵蓋知識點情況*
知識點學時
小計
1、緒論
1.1 什麼是數據結構
1.2 算法及其描述
1.3 Python簡介
1
2
1.4 算法分析：
①算法時間複雜度分析；②算法空間複雜度分析
1
2、線性表
2.1 線性表的定義
2.2 線性表的順序存儲結構：
①順序表以及線性表基本運算算法在順序表中的實現；②順序表的應用算法設計示例
2
6
2.3 線性表的鏈式存儲結構：
①單鍊表以及線性表基本運算算法在單鍊表中的實現；②單鍊表的應用算法設計示例；③雙鍊表以及線性表基本運算算法在雙鍊表中的實現；④雙鍊表的應用算法設計示例；⑤循環鍊表
2
2.4 順序表和鍊表的比較
2.5 線性表的應用：
求解兩個多項式相加問題
2
3、棧和隊列
3.1 棧：
①棧的定義；②順序棧及其實現；③順序棧的應用算法設計示例；④鏈棧及其實現；⑤鏈棧的應用算法設計示例
2
6
⑦棧的綜合應用（用棧求解簡單表達式求值問題，用棧求解迷宮問題）
1
3.2 隊列：
①隊列的定義；②順序隊及其實現；③順序隊的應用算法設計示例；④鏈隊及其實現；⑤鏈隊的應用算法設計示例
2
⑦隊列的綜合應用（用隊列求解迷宮問題）
1
4、串和數組
4.1 串
①串的定義；②串的存儲結構—順序串和鏈串；③串的模式匹配（BF算法和KMP算法）
2
4
4.2 數組：
①數組的基本概念；②特殊矩陣的壓縮存儲；③稀疏矩陣
2
5、遞歸
5.1 什麼是遞歸
①遞歸的定義；②何時使用遞歸；③遞歸模型；④遞歸的執行過程；⑤遞歸算法的時空分析
1
2
5.2 遞歸算法的設計：
①遞歸算法設計的步驟；②基於遞歸數據結構的遞歸算法設計；③基於歸納方法的遞歸算法設計
1
6、樹和二叉樹
6.1 樹：
①樹的定義和邏輯表示；②樹的基本術語；③樹的性質；④樹的基本運算；⑤樹的存儲結構
1
7
6.2 二叉樹：
①二叉樹的概念；②二叉樹的性質；③二叉樹存儲結構；④二叉樹的遞歸算法設計；⑤二叉樹的基本運算及其實現
2
6.3 二叉樹先序、中序和後序遍歷：
①二叉樹遍歷的概念；②先序、中序和後序遍歷遞歸算法；③遞歸遍歷算法的應用
1
6.4 二叉樹的層次遍歷：
①層次遍歷過程；②層次遍歷算法設計；③層次遍歷算法的應用
1
6.5 二叉樹的構造
6.6 線索二叉樹
1
6.7 哈夫曼樹
6.8 二叉樹與樹、森林之間的轉換
1
7、圖
7.1 圖的基本概念
7.2 圖的存儲結構：
①鄰接矩陣；②鄰接表
1
7
7.3 圖的遍歷：
①圖遍歷的概念；②深度優先遍歷；③廣度優先遍歷；④非連通圖的遍歷；⑤圖遍歷算法的應用
2
7.4 生成樹和最小生成樹：
①生成樹和最小生成樹的概念；②普裡姆算法；③克魯斯卡爾算法
1.5
7.5 最短路徑：
①最短路徑的概念；②狄克斯特拉算法；③弗洛伊德算法
1.5
7.6 拓撲排序
7.7 AOE網與關鍵路徑
1
8、查找
8.1 查找的基本概念
8.2 線性表的查找：
①順序查找；②折半查找；③索引存儲結構和分塊查找
2
7
8.3 樹表的查找：
①二叉排序樹；②平衡二叉樹；③B-樹和B+樹
3
8.4 哈希表查找：
①哈希表的基本概念；②哈希函數構造方法；③哈希衝突解決方法；④哈希表查找及性能分析
2
9、排序
9.1 排序的基本概念
9.2 插入排序：
①直接插入排序；②折半插入排序；③希爾排序
2
6
9.3 交換排序：
①冒泡排序；②快速排序
1
9.4 選擇排序：
①簡單選擇排序；②堆排序
1
9.5 歸併排序：
①自底向上的二路歸併排序；②自頂向下的二路歸併排序
9.6 基數排序
9.7 各種內排序方法的比較和選擇
2
10、複習
課程知識點歸納和總結
1
1
*教材中所有帶"*"的內容均為提高知識點，不作為課堂講授內容以減少課堂學時。知識單元
涵蓋知識點情況*
知識點學時
小計
1、緒論
1.1 什麼是數據結構
1.2 算法及其描述
1
4
1.3 Python簡介
1.5
1.4 算法分析：
①算法時間複雜度分析；②算法空間複雜度分析
1.5 數據結構的目標
1.5
2、線性表
2.1 線性表的定義
2.2 線性表的順序存儲結構：
①順序表以及線性表基本運算算法在順序表中的實現；②順序表的應用算法設計示例
3
8
2.3 線性表的鏈式存儲結構：
①單鍊表以及線性表基本運算算法在單鍊表中的實現；②單鍊表的應用算法設計示例；③雙鍊表以及線性表基本運算算法在雙鍊表中的實現；④雙鍊表的應用算法設計示例；⑤循環鍊表
3
2.4 順序表和鍊表的比較
2.5 線性表的應用：
求解兩個多項式相加問題
2
3、棧和隊列
3.1 棧：
①棧的定義；②順序棧及其實現；③順序棧的應用算法設計示例；④鏈棧及其實現；⑤鏈棧的應用算法設計示例
2
6
⑥棧的綜合應用（用棧求解簡單表達式求值問題，用棧求解迷宮問題）
1
3.2 隊列：
①隊列的定義；②順序隊及其實現；③順序隊的應用算法設計示例；④鏈隊及其實現；⑤鏈隊的應用算法設計示例；⑥Python中的雙端隊列deque
2
⑦隊列的綜合應用（用隊列求解迷宮問題）；⑧優先隊列（堆）
1
4、串和數組
4.1 串
①串的定義；②串的存儲結構—順序串和鏈串；③串的模式匹配（BF算法和KMP算法）
3
5
4.2 數組：
①數組的基本概念；②特殊矩陣的壓縮存儲；③稀疏矩陣
2
5、遞歸
5.1 什麼是遞歸：
①遞歸的定義；②何時使用遞歸；③遞歸模型；④遞歸的執行過程；⑤遞歸算法的時空分析
1
3
5.2 遞歸算法的設計：
①遞歸算法設計的步驟；②基於遞歸數據結構的遞歸算法設計；③基於歸納方法的遞歸算法設計
2
6、樹和二叉樹
6.1 樹：
①樹的定義和邏輯表示；②樹的基本術語；③樹的性質；④樹的基本運算；⑤樹的存儲結構
1
9
6.2 二叉樹：
①二叉樹的概念；②二叉樹的性質；③二叉樹存儲結構；④二叉樹的遞歸算法設計；⑤二叉樹的基本運算及其實現
2
6.3 二叉樹先序、中序和後序遍歷：
①二叉樹遍歷的概念；②先序、中序和後序遍歷遞歸算法；③遞歸遍歷算法的應用；④先序、中序和後序遍歷非遞歸算法
2
6.4 二叉樹的層次遍歷：
①層次遍歷過程；②層次遍歷算法設計；③層次遍歷算法的應用
1
6.5 二叉樹的構造
6.6 線索二叉樹
1
6.7 哈夫曼樹
6.8 二叉樹與樹、森林之間的轉換
1
6.9 併查集
1
7、圖
7.1 圖的基本概念
7.2 圖的存儲結構：
①鄰接矩陣；②鄰接表
1
8
7.3 圖的遍歷：
①圖遍歷的概念；②深度優先遍歷；③廣度優先遍歷；④非連通圖的遍歷；⑤圖遍歷算法的應用
2.5
7.4 生成樹和最小生成樹：
①生成樹和最小生成樹的概念；②普裡姆算法；③克魯斯卡爾算法
1.5
7.5 最短路徑：
①最短路徑的概念；②狄克斯特拉算法；③弗洛伊德算法
1.5
7.6 拓撲排序
7.7 AOE網與關鍵路徑
1.5
8、查找
8.1 查找的基本概念
8.2 線性表的查找：
①順序查找；②折半查找；③索引存儲結構和分塊查找
2
7
8.3 樹表的查找：
①二叉排序樹；②平衡二叉樹；③B樹；④B+樹
3
8.4 哈希表查找：
①哈希表的基本概念；②哈希函數構造方法；③哈希衝突解決方法；④哈希表查找及性能分析
2
9、排序
9.1 排序的基本概念
9.2 插入排序：
①直接插入排序；②折半插入排序；③希爾排序
2
8
9.3 交換排序：
①冒泡排序；②快速排序
1
9.4 選擇排序：
①簡單選擇排序；②堆排序
1
9.5 歸併排序：
①自底向上的二路歸併排序；②自頂向下的二路歸併排序
9.6 基數排序
9.7 各種內排序方法的比較和選擇
2
10.8 外排序：
①生成初始歸併段的方法；②多路歸併方法
2
10、複習
課程知識點歸納和總結
2
2
*教材中部分帶"*"的內容作為提高知識點，不作為課堂講授內容。
四、上機課時安排（16課時）
知識單元
實驗內容
學時
1、線性表
上機實驗題**
3
2、棧和隊列
上機實驗題
3
3、樹和二叉樹
上機實驗題
3
4、圖
上機實驗題
3
5、查找和排序
上機實驗題
4
**上機實驗題均來自於教材，教師可以根據學生的情況選擇相應的題目。本書提供1000多頁PPT課件，大綱，源碼，答案，上機，40小時視頻，教案，題庫（1000多道題目）本書配套《數據結構教程（Python語言描述)學習與上機實驗指導》（ISBN:9787302560838）本書配套視頻演示
六、考核
（1）期末考試：期末考試形式為筆試，一般以閉卷方式進行。
（2）課程成績評定方法：期末考試成績、課後作業、上機實驗（含實驗報告）和其他。後三項所佔成績比例加起來不低於30%。
公眾號「書圈」後臺回復【9787302560289】，下載本書配套資源
掃描優惠購書
七、參考圖書
點擊下方的【閱讀原文】，查看本書目錄