《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)大綱

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

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

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

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

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

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

7、根據(jù)實際情況增加課時11.1 數(shù)據(jù)結(jié)構(gòu)討論的范疇1.2 基本概念1.3 算法和算法的量度322.1 線性表的類型定義2.2 線性表類型的實現(xiàn)順序映象2.3 線性表類型的實現(xiàn)鏈?zhǔn)接诚?32.4 一元多項式的表示3.1 棧的類型定義3.2 棧的應(yīng)用舉例3.3 棧類型的實現(xiàn)3C程序設(shè)計練習(xí):指針和鏈表操作43.4 隊列的類型定義3.5 隊列類型的實現(xiàn)354.1 串的抽象數(shù)據(jù)類型的定義4.2 串的表示和實現(xiàn)31.復(fù)數(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 二叉樹的存儲結(jié)構(gòu)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 重（雙）連通圖和關(guān)節(jié)點7.6 兩點之間的最短路徑問題7.7 拓?fù)渑判?.8 關(guān)鍵路徑31、哈希樹2、最短路徑導(dǎo)游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、內(nèi)部排序比較五、考核方式考試形式