《資料結構》課程教學大綱
一、課程的基本情況
課程中文名稱:資料結構
課程英文名稱:data structure
課程編碼:0402019
課程類別:學科基礎課
課程性質:必修課
總學時: 54講課學時:44實驗學時: 10
學分:3
授課物件:電子資訊工程專業本科學生
前導課程:c語言
二、教學目的
《資料結構》是電信專業的一門重要的學科基礎課,主要介紹各種基本而又典型的資料結構、演算法思想及其實際應用。通過本課程的學習,應使學生掌握各種資料結構的特點、儲存表示、運算方法以及在電腦科學中最基本的應用;培養、訓練學生選用合適的資料結構和運用c語言編寫質量高、內容好的應用程式及初步評價演算法程式的能力。
三、教學基本要求
第1章緒論
1.1 什麼是資料結構(定義)
1.2 資料結構的內容
1.3 演算法
1.4 演算法描述的工具
1.5 對演算法作效能評價
基本要求:掌握資料結構的一些基本概念,掌握演算法的時間複雜度和空間複雜度的分析方法,了解抽象資料型別的定義和使用,了解演算法的描述方法。
重點與難點:演算法的時間複雜度和空間複雜度的分析和計算方法。
第2章線性表
2.1 線性表的概念及運算
2.2 線性表的順序儲存
2.3 線性表的鏈式儲存
2.4 一元多項式的表示及相加
基本要求:掌握線性表的基本概念和型別定義;熟練掌握對順序表和單鏈表的常用操作方法及其程式實現;掌握迴圈鍊錶和雙向鍊錶的定義和它的插入、刪除等操作方法。
重點與難點:順序表和單鏈表常用操作的程式實現;迴圈鍊錶的插入、刪除等操作方法。
第3章限定性線性表——棧和佇列
3.1 棧
3.2 佇列
基本要求:領會棧和佇列的定義,熟練掌握順序和鏈式儲存的棧和佇列的各種運算的方法及其程式實現,掌握表示式求值的方法並了解其演算法。
重點與難點:棧和佇列操作特點;順序和鏈式儲存方式以及在不同儲存方式下各種基本運算的程式實現;表示式求值的演算法實現。
第4章串
4.1 串的定義
4.2 抽象資料型別串的實現
基本要求:熟悉串的概念,了解串的抽象資料型別的實現方法,掌握串的常用操作方法。
重點與難點:串的定義;串的常用操作方法。
第5章陣列和廣義表
5.1 陣列的定義和運算
5.2 陣列的順序儲存和實現
5.3 特殊矩陣的壓縮儲存
5.4 廣義表
基本要求:掌握陣列、稀疏矩陣的定義和各種儲存結構,熟悉稀疏矩陣的轉置和相加的方法並了解其演算法,掌握廣義表的定義、儲存結構和求廣義表的長度及深度的演算法,掌握建立廣義表和輸出廣義表的方法並了解其演算法。
重點與難點:陣列、稀疏矩陣的定義和儲存方法及相關運算;廣義表的定義和廣義表的長度及深度計算方法。
第6章樹和二叉樹
6.1 樹的概念和定義
6.2 二叉樹
6.3 二叉樹的遍歷與線索化
6.4 樹、森林和二叉樹的關係
6.5 哈夫曼樹及其應用
基本要求:掌握樹的定義、性質、儲存結構及遍歷演算法,熟練掌握二叉樹的各種遍歷方法及其實現,掌握二叉樹的其他操作方法及實現,了解樹和二叉樹的轉換方法。掌握哈夫曼樹的定義和構造哈夫曼樹的方法,了解哈夫曼樹編碼的方法。
重點與難點:二叉樹的定義、性質和各種遍歷方法;樹和二叉樹的轉換;二叉樹的儲存結構及演算法實現;哈夫曼樹的定義和構造及哈夫曼編碼的實現。
第7章圖
7.1 圖的定義與基本術語
7.2 圖的儲存結構
7.3 圖的遍歷
7.4 圖的連通性問題
7.5 有向無環圖的應用
7.6 最短路徑
基本要求:熟悉圖的定義和術語;熟練掌握圖的儲存結構及深度和廣度優先搜尋方法及其實現;掌握圖的生成樹概念,掌握求最小生成樹的普里姆演算法和克魯斯卡爾演算法並了解其實現演算法;掌握拓撲排序的方法及其實現演算法;掌握關鍵路徑的求解演算法。
重點與難點:圖的相關術語、儲存結構和兩種搜尋方法;最小生成樹的性質及普里姆演算法和克魯斯卡爾演算法的實現;拓撲排序和關鍵路徑的實現演算法。
第8章查詢
8.1 查詢的基本概念
8.2 基於線性表的查詢法
8.3 基於樹的查詢法
8.4 計算式查詢法——雜湊法
基本要求:理解順序查詢和二分查詢的方法及實現;掌握分塊查詢的方法及實現;熟悉雜湊表的定義,利用除留餘數法構造雜湊函式的方法,利用線性探查法和鏈結法處理衝突的方法。
重點與難點:順序查詢和二分查詢的方法及實現;雜湊法中雜湊表的定義及線性探查法和鏈結法處理衝突的方法。
四、課程內容與學時分配
課程內容與學時分配表
五、教材與參考書
教材:耿國華《資料結構——c語言描述》 西安電子科技大學出版社 2023年
參考書:[1] 嚴蔚敏、吳偉民 《資料結構(c語言版)》 清華大學出版社 2023年
[2] 譚浩強 《c語言程式設計》(第三版)清華大學出版社2023年
六、教學方式和考核方式
1、教學方式:課堂講授為主,輔以實驗教學,課後作業。
2、考核方式:閉卷考試。
《資料結構》教學大綱
五 課程的教學內容 一 課堂講授的教學內容 1 資料結構的概念 資料結構的概念,抽象資料型別,演算法和演算法分析。2 線性表 線性表邏輯結構,線性表的順序儲存及運算實現,線性表的鏈式儲存和實現,一元多項式的表示與相加。3棧和佇列 棧基本概念及棧的應用,佇列基本概念及佇列的應用。4 串串及其基本運算,...
資料結構教學大綱
資料結構 data structure 電腦科學與技術 資訊管理及相關專業本科學生 課堂授課學時 60學時實驗學時 20學時 學分 4 c 語言或c 語言 離散數學 五 教學目的 資料結構 是電腦科學的一門實用性很強的專業基礎課。通過本課程的學習,學生能夠掌握電腦科學中的資料組織 儲存 處理方面的基...
《資料結構》課程教學大綱
保持青春的秘訣,是有一顆不安分的心。data structure a 課程 課程性質 專業基礎理論課 必修 適用專業 資訊計算 資訊保安 開課學期 5 總學時數 72 總學分數 4.5 編寫年月 2003年7月 修訂年月 2007年7月 執筆 高學軍 劉科峰 李小英 一 課程的性質和目的 資料結構是...