數(shù)據(jù)結構課程教學大綱.doc

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