《數(shù)據(jù)結構》課程教學大綱

1、數(shù)據(jù)結構課程教學大綱一、課程基本信息課程名稱：數(shù)據(jù)結構課程代碼：CST202學 分：4（大學科基礎課）學 時：3學時/課，共48學時。二、任課教師、助教、教室等情況（四）教 室：C501 實 驗 室：D502（五）上課時間：每周二上午1，2，3節(jié)（六）紀 律：1、無特殊情況，不允許無故缺課。2、每次作業(yè)須在規(guī)定時間內提交。三、閱讀材料（一）推薦教材：數(shù)據(jù)結構，嚴蔚敏等著，清華大學出版社。2015年數(shù)據(jù)結構，劉小晶著，清華大學出版社。2015年（二）參考教材1. 熊偉編著，數(shù)據(jù)結構，機械工業(yè)出版社，2005年11月。2. 數(shù)據(jù)結構教材編寫組，數(shù)據(jù)結構（第三版），清華大學出版社，2006年。3數(shù)據(jù)

2、結構與算法Sartaj Sahni（美）著 汪詩林 孫曉東等譯 機械工業(yè)出版社。4DATA STRUCTURES WITH C+ 清華大學出版社。（三）進一步閱讀教材1The Art of Computer Programming Volumes 1-3 Boxed Set ，Donald E.Knuth，清華大學出版社。2 Data structures A Pseudocode Approach with C+ 英文版 美Richard F.Gilberg Behrouz A.Forouzan 著 ，人民郵電出版社。3中國知網(wǎng)()相關文獻四、課程內容概要（一）課程目標本課程的教學目的是使學

3、生學會在非數(shù)值計算數(shù)學模型下分析計算機加工數(shù)據(jù)的理論和方法，掌握各種數(shù)據(jù)結構（線性表、堆棧與隊列、樹、圖）的特性，為應用所涉及的數(shù)據(jù)選擇適當?shù)倪壿嫿Y構、存儲結構及相應的算法，并且靈活地進行各種數(shù)據(jù)結構的基本操作，同時初步掌握對算法的時間分析和空間效率分析。另一方面，通過對本課程算法設計和上機實踐的訓練，還應培養(yǎng)學生的數(shù)據(jù)抽象能力、良好的程序設計能力，為編譯原理、算法分析與設計、操作系統(tǒng)等后續(xù)課程的學習及以后從事軟件開發(fā)工作打下良好的基礎。（二）教學內容(分章節(jié))主 要 教 學 內 容第一章 概 論（3學時）第一節(jié) 基本概念和術語第二節(jié)學習數(shù)據(jù)結構的意義第三節(jié)抽象數(shù)據(jù)類型第四節(jié)算法的描述和分析第

4、二章 線性表（6學時）第一節(jié) 線性表的邏輯結構第二節(jié) 線性表的順序存貯結構第三節(jié) 線性表的鏈式存貯結構第四節(jié) 順序表和鏈表的比較第三章 棧和隊列（6學時）第一節(jié) 棧第二節(jié)隊列第三節(jié)棧與隊列的應用實例第四章 串（3學時）第一節(jié) 串及其運算第二節(jié)串的存貯結構第三節(jié)串的模式匹配(分章節(jié))主 要 教 學 內 容第五章 樹（6學時）第一節(jié) 樹的概念第二節(jié) 二叉樹第三節(jié)二叉樹的遍歷第四節(jié)線索二叉樹第五節(jié)樹和森林、哈夫曼樹及其應用第六節(jié)樹與等價問題、樹的計數(shù)第六章 圖（9學時）第一節(jié) 圖的概念第二節(jié) 圖的存貯結構第三節(jié) 圖的遍歷第四節(jié) 圖的連通性問題第五節(jié) 最短路徑第六節(jié) 有向無環(huán)圖及其應用第七章 動態(tài)存儲

5、管理（3學時）第一節(jié) 概述第二節(jié)可利用空間表及分配算法第三節(jié)邊界標識法第四節(jié)伙伴系統(tǒng)第五節(jié)無用單元收集第八章 查找（3學時）第一節(jié) 基本概念第二節(jié) 靜態(tài)查找第三節(jié) 動態(tài)查找第四節(jié) 散列查找第九章 文件簡介（3學時）第一節(jié)文件基本概念第二節(jié)順序文件與索引文件第三節(jié) ISAM和VSAM文件第三節(jié)散列文件第十章 排序（3學時）第一節(jié) 概述第二節(jié) 插入排序第三節(jié) 快速排序第四節(jié) 堆排序第五節(jié) 歸并排序第六節(jié) 基數(shù)排序第七節(jié) 各種排序方法的綜合比較第八節(jié) 外部排序（三）課程要求1.文獻與參考書閱讀作業(yè)：課堂進行隨機抽查回答與提前指定匯報結合方式。2.平時課后作業(yè)：按時規(guī)定的時間交與助教進行批改，隔一周上

6、課時間助教與授課教師進行評講。3.上機作業(yè)：上機實驗作業(yè)按照“學號-姓名-實驗*”方式命名，課后及時在課程中心作業(yè)論壇中進行提交。4.課程設計：課程設計第12個教學周開始，以小組方式進行，每組由5-6名學生組成，設計報告以小組名義提交。要求運用本課程所學理論與方法，分析解決現(xiàn)實中企業(yè)組織面臨的管理決策或優(yōu)化問題，第16周課堂進行答辯，課程設計內容要求詳見課程設計指導書。（四）教學安排周數(shù)教學時數(shù)及內容備注課堂講授課堂討論實驗實習或上機作業(yè)章節(jié)內容課時題目課時內容及要求復習程序設計知識（C）1.數(shù)據(jù)類型及運算符,表達式2.算法及其描述3.程序設計基礎4.數(shù)組,函數(shù)5.指針及結構6.鏈表及其應用3

7、根據(jù)實際情況增加課時11.1 數(shù)據(jù)結構討論的范疇1.2 基本概念1.3 算法和算法的量度322.1 線性表的類型定義2.2 線性表類型的實現(xiàn)順序映象2.3 線性表類型的實現(xiàn)鏈式映象332.4 一元多項式的表示3.1 棧的類型定義3.2 棧的應用舉例3.3 棧類型的實現(xiàn)3C程序設計練習:指針和鏈表操作43.4 隊列的類型定義3.5 隊列類型的實現(xiàn)354.1 串的抽象數(shù)據(jù)類型的定義4.2 串的表示和實現(xiàn)31.復數(shù)運算 2約瑟夫環(huán) 3.迷宮求解64.3 串的模式匹配算法5.1 數(shù)組的類型定義5.2 數(shù)組的順序表示和實現(xiàn)375.3 稀疏矩陣的壓縮存儲 5.4 廣義表的類型定義5.5 廣義表的表示方法5

8、.6 廣義表操作的遞歸函數(shù)386.1 樹的類型定義6.2 二叉樹的類型定義6.3 二叉樹的存儲結構396.4 二叉樹的遍歷6.5 線索二叉樹6.6 樹和森林的表示方法31、矩陣運算2、求廣義表深度3、求最小生成樹106.7 樹和森林的遍歷6.8 哈夫曼樹與哈夫曼編碼3117.1 抽象數(shù)據(jù)類型圖的定義7.2 圖的存儲表示3127.3 圖的遍歷7.4 最小生成樹3137.5 重（雙）連通圖和關節(jié)點7.6 兩點之間的最短路徑問題7.7 拓撲排序7.8 關鍵路徑31、哈希樹2、最短路徑導游149.1 靜態(tài)查找表9.2 動態(tài)查找樹表9.3 哈希表31510.1 概述10.2 插入排序10.3 快速排序31610.4 堆排序10.5 歸并排序10.6 基數(shù)排序10.7 各種排序方法的綜合比較10.8 外部排序31、平衡二叉樹查找2、內部排序比較五、考核方式考試形式