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

數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱課程名稱中文：數(shù)據(jù)結(jié)構(gòu)英文：（Data Structure）課程編號學(xué)分/學(xué)時3/51所屬教研室信息管理與信息系統(tǒng)前后課程先修課程：計(jì)算機(jī)文化基礎(chǔ)、C+程序設(shè)計(jì)；并行課程：計(jì)算機(jī)網(wǎng)絡(luò)、操作系統(tǒng)；后續(xù)課程：SQL Server數(shù)據(jù)庫、C#與.NET或Java設(shè)計(jì)等課程。課程類型專業(yè)基礎(chǔ)課考核方式考試授課對象05信管AB教學(xué)目的具體教學(xué)目的：掌握數(shù)據(jù)組織存儲和處理的常用方法和常用的算法思想及在實(shí)際中的應(yīng)用技巧，為今后學(xué)習(xí)后續(xù)專業(yè)課和進(jìn)行軟件開發(fā)打下良好的基礎(chǔ)。教學(xué)重點(diǎn)、難點(diǎn)：第一章：（重點(diǎn)）數(shù)據(jù)結(jié)構(gòu)的基本概念；數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)以及二者之間的關(guān)系；算法及特性等（難點(diǎn)）抽象數(shù)據(jù)類型的定義和使用；算法的時間復(fù)雜度分析。 第二章：（重點(diǎn)）線性表的順序存儲結(jié)構(gòu)、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)；（難點(diǎn)）單鏈表上的算法設(shè)計(jì)；雙鏈表操作的實(shí)現(xiàn)。 第三章：（重點(diǎn)）棧的存儲結(jié)構(gòu)及其基本操作、隊(duì)列存儲結(jié)構(gòu)及其基本操作；（難點(diǎn)）模式匹配KMP算法。 第四章：（重點(diǎn)）特殊矩陣的的壓縮存儲廣義表的定義、術(shù)語、存儲結(jié)構(gòu)、運(yùn)算；（難點(diǎn)）遞歸算法設(shè)計(jì)。 第五章：（重點(diǎn)）二叉樹的遍歷、線索算法、哈夫曼樹及其應(yīng)用；（難點(diǎn)）線索算法、哈夫曼樹及其應(yīng)用。 第六章：（重點(diǎn)）圖的基本術(shù)語、存儲結(jié)構(gòu)和圖的遍歷操作；（難點(diǎn)）圖的幾個典型應(yīng)用問題。 第七章：（重點(diǎn)）線性查找、索引查找、動態(tài)查找表及查找算法：二叉排序樹；（難點(diǎn)）哈希表及查找算法、二叉排序樹。 第八章：（重點(diǎn)）各種排序算法的基本思想、執(zhí)行過程、設(shè)計(jì)、時間復(fù)雜度的分析以及它們之間的比較；（難點(diǎn)）快速排序、堆排序、歸并排序等算法的設(shè)計(jì)。教材和主要參考資料：教 材：數(shù)據(jù)結(jié)構(gòu)（C+語言描述）（第1版），清華大學(xué)出版社、北京交通大學(xué)出版社，丁芝芳、劉杰主編，2004年7月參考書：1 數(shù)據(jù)結(jié)構(gòu)教程（C語言版），希望電子工業(yè)出版社，王慶瑞編著， 2數(shù)據(jù)結(jié)構(gòu)與算法：C+，清華大學(xué)出版社，Drozdek A.著， 教學(xué)內(nèi)容學(xué)時基本要求課程介紹1了解課程教學(xué)大綱等第一章 緒論第一節(jié)程序=算法+數(shù)據(jù)結(jié)構(gòu)第二節(jié)數(shù)據(jù)結(jié)構(gòu)的基本內(nèi)涵第三節(jié)時間復(fù)雜度和空間復(fù)雜度第四節(jié)數(shù)據(jù)結(jié)構(gòu)與面向?qū)ο缶幊?2（上機(jī)）1了解程序的概念2熟悉數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)3掌握算法的時間復(fù)雜度計(jì)算第二章 線性表第一節(jié) 線性表的邏輯特點(diǎn)第二節(jié) 線性表的順序存儲結(jié)構(gòu)循序表第三節(jié) 線性表的鏈?zhǔn)酱鎯^程鏈表52（上機(jī)）1了解線性表的邏輯特點(diǎn)和基本操作2理解順序存儲和鏈?zhǔn)酱鎯Φ漠愅陀腥秉c(diǎn)3掌握順序表和單鏈表的實(shí)現(xiàn)第三章 棧和隊(duì)列第一節(jié)棧的概念第二節(jié)順序棧棧的順序存儲表示第三節(jié)棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈棧第四節(jié) 隊(duì)列的基本概念第五節(jié) 隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈隊(duì)列第六節(jié) 隊(duì)列的順序存儲結(jié)構(gòu)第七節(jié) 優(yōu)先級隊(duì)列 104（上機(jī)）1了解棧和隊(duì)列邏輯特點(diǎn)和基本操作2理解順序存儲和鏈?zhǔn)酱鎯ο碌膶?shí)現(xiàn)3掌握隊(duì)列和棧特別是棧在程序設(shè)計(jì)中的各種應(yīng)用第四章數(shù)組和廣義表第一節(jié)數(shù)組的邏輯特點(diǎn)第二節(jié)數(shù)組的存儲結(jié)構(gòu)第三節(jié)特殊矩陣的壓縮存儲第四節(jié)稀疏矩陣的壓縮存儲第五節(jié)稀疏矩陣運(yùn)算的 實(shí)現(xiàn)第六節(jié)廣義表第七節(jié)遞歸21了解數(shù)組和廣義表的概念2理解遞歸算法設(shè)計(jì)第五章 樹和二叉樹第一節(jié)樹的邏輯結(jié)構(gòu)第二節(jié)二叉樹第三節(jié)二叉樹遍歷第四節(jié)線索二叉樹第五節(jié)堆第六節(jié)樹和森林第七節(jié)哈夫曼樹及其應(yīng)用82（上機(jī)）1了解二叉樹的定義和特性2理解二叉樹的各種遍歷算法和重構(gòu)3掌握二叉樹的簡單實(shí)現(xiàn)4應(yīng)用哈夫曼樹第六章 圖第一節(jié)圖的定義和術(shù)語第二節(jié)圖的存儲結(jié)構(gòu)第三節(jié)圖的遍歷第四節(jié)圖的應(yīng)用21了解圖的概念2了解圖的若干應(yīng)用第七章 查找第一節(jié)查找的基本概念第二節(jié)線性表查找第三節(jié)索引表查找第四節(jié)樹表查找第五節(jié)散列表查找84（上機(jī)）1了解查找的概念和原理2理解二叉排序樹的原理和查找算法3掌握線性表的查找原理和算法，算法復(fù)雜度的計(jì)算第八章 排序第一節(jié)排序的基本概念第二節(jié)插入排序第三節(jié)交換排序第四節(jié)選擇排序第五節(jié)歸并排序第六節(jié)基數(shù)排序第七節(jié)各種排序方法的比較104（上機(jī)）1了解排序的基本概念和基本原理2理解常見的幾種排序算法和時間