數(shù)據(jù)結(jié)構(gòu)教學大綱課程代碼：040631003課程英文名稱：Data Structure課程總學時：48 講課：40 實驗：0 上機：8適用專業(yè)：信息管理與信息系統(tǒng)大綱編寫（修訂）時間：2010.7一、大綱使用說明（一）課程的地位及教學目標本課程是信息管理與信息系統(tǒng)專業(yè)的一門重要的專業(yè)基礎(chǔ)課,它較詳細地闡述了使用計算機解決具體問題時，所建立的數(shù)學模型的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的多種類型，以及對數(shù)據(jù)進行具體操作的算法實現(xiàn)。通過本課程的學習，使學生了解和掌握使用高級語言編程時組織數(shù)據(jù)的基本理論和方法，是學生進一步學習其他專業(yè)課程的必備基礎(chǔ)。 通過本課程的學習，學生將達到以下要求： 1了解數(shù)據(jù)結(jié)構(gòu)及其分類、數(shù)據(jù)結(jié)構(gòu)與算法的密切關(guān)系； 2熟悉各種基本數(shù)據(jù)結(jié)構(gòu)及其操作，學會根據(jù)實際問題要求來選擇數(shù)據(jù)結(jié)構(gòu)； 3掌握設(shè)計算法的步驟和算法分析的方法； 4掌握數(shù)據(jù)結(jié)構(gòu)在排序和查找等常用算法中的應用。（二）知識、能力及技能方面的基本要求要求學生了解各種形式多樣的客觀問題中所涉及的數(shù)據(jù)對象可通過適當?shù)姆纸猓瑥亩梢詫獛追N數(shù)據(jù)結(jié)構(gòu)。學生應該能夠使用高級語言正確定義數(shù)據(jù)的邏輯結(jié)構(gòu)和選擇有效的存儲結(jié)構(gòu)，以解決具體問題。其操作的實現(xiàn)算法應注重時間效率和空間效率。對數(shù)據(jù)對象的查找與排序操作時較常用的基本操作，學生應掌握基本的算法，并學會合理使用。（三）實施說明 1教學方法：本課程對學生的動手能力要求較強，應配置相應的上機實驗。使學生在編程的訓練中，真正掌握算法的實現(xiàn)方法。在教師的講解過程中應深入淺出、循序漸進、聯(lián)系實際、結(jié)合實例，才能收到較好的效果。應培養(yǎng)學生良好的算法設(shè)計思想、方法與技巧，強化程序抽象能力與數(shù)據(jù)抽象能力。 2教學手段：本課程屬于專業(yè)基礎(chǔ)課，在教學中采用多媒體教學為主，輔以板書講解。確保在有限的學時內(nèi)，全面、高質(zhì)量地完成課程教學任務(wù)。（四）對先修課的要求要求學生有高級語言的基礎(chǔ)知識與編程經(jīng)驗。（五）對習題課、實踐環(huán)節(jié)的要求 1對重點、難點章節(jié)（如：線性表的鏈表實現(xiàn)、二叉樹的遍歷、圖的存儲結(jié)構(gòu)和遍歷、排序算法的實現(xiàn)等）應安排習題課。 2課后作業(yè)要少而精，內(nèi)容要多樣化，作業(yè)題內(nèi)容必須包括基本概念、基本算法理論及設(shè)計方面的內(nèi)容，作業(yè)要能起到鞏固理論，掌握數(shù)據(jù)結(jié)構(gòu)算法的分析和設(shè)計技巧。對作業(yè)中的重點、難點，課上應做必要的提示，并適當安排課內(nèi)講評作業(yè)。學生必須獨立、按時完成課外習題和作業(yè)，作業(yè)的完成情況應作為評定課程成績的一部分。 3每個學生要完成大綱中規(guī)定的必修上機實驗，通過實驗環(huán)節(jié)，學生應掌握典型數(shù)據(jù)結(jié)構(gòu)的設(shè)計及實現(xiàn)方法。實驗成績作為評定課程成績的一部分。（六）課程考核方式1.考核方式：考試。2.考核目標：在考核學生對數(shù)據(jù)結(jié)構(gòu)基本知識、算法的理論和設(shè)計方法的基礎(chǔ)上，重點考核學生的問題分析能力和算法設(shè)計能力。3.成績構(gòu)成：本課程的總成績主要由三部分組成：平時成績（包括中期考試、作業(yè)、小測驗、提問、出勤情況等）占10%，實驗成績占20%，期末考試成績占70%。平時成績由任課教師視具體情況按百分制給出；實驗成績由實驗老師參照相關(guān)規(guī)定按百分制給出，實驗無成績或?qū)嶒灢患案瘢∠谀┛荚囐Y格，總成績直接以不及格計。（七）主要參考書目:數(shù)據(jù)結(jié)構(gòu)(C語言版) 嚴蔚敏 清華大學出版社 2006.9數(shù)據(jù)結(jié)構(gòu) 李筠，姜學軍 清華大學出版社 2008.8二、中文摘要本課程是信息管理與信息系統(tǒng)專業(yè)學生必修的一門專業(yè)技術(shù)基礎(chǔ)課程。通過對本課程的講授，使得學生學會分析研究計算機加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應用涉及的數(shù)據(jù)選擇適當?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及其相應的算法。課程主要內(nèi)容包括數(shù)據(jù)結(jié)構(gòu)基本概念、線性表、棧和隊列、串、數(shù)組和廣義表、樹和二叉樹、圖、查找、排序等。本課程將為后續(xù)課程的學習以及畢業(yè)設(shè)計奠定重要的基礎(chǔ)。三、課程學時總體分配表序號教學內(nèi)容學時講課實驗上機1緒論222線性表8622.1線性表的類型定義，順序表示和實現(xiàn)22.2線性表的鏈式表示和實現(xiàn)4線性表的應用實驗23棧和隊列8623.1棧23.2棧的應用23.3隊列2棧應用實驗24串444.1串的定義、表示和實現(xiàn)24.2串的模式匹配算法25數(shù)組和廣義表445.1數(shù)組25.2廣義表26樹和二叉樹8626.1樹的定義，二叉樹126.2二叉樹2，樹和森林26.3赫夫曼樹及其應用2實現(xiàn)二叉樹的遍歷實驗27圖447.1圖的定義、存儲結(jié)構(gòu)、遍歷27.2圖的連通性問題28查找448.1靜態(tài)查找表，動態(tài)查找表128.2動態(tài)查找表2，哈希表29內(nèi)部排序6429.1插入排序，快速排序29.2選擇排序，歸并排序2排序?qū)嶒?合計48408四、教學內(nèi)容及基本要求第1部分 緒論總學時(單位：學時):2 講課:2 實驗:0 上機:0 具體內(nèi)容：1) 基本概念與術(shù)語2) 抽象數(shù)據(jù)類型的表示與實現(xiàn)3) 算法與算法分析重 點: 有關(guān)數(shù)據(jù)結(jié)構(gòu)中的基本概念難 點: 算法的描述方法習 題: 算法時間復雜度的計算第2部分 線性表總學時(單位：學時):8 講課:6 實驗:0 上機:2 具體內(nèi)容：1) 線性表的類型定義2) 線性表的順序表示和實現(xiàn)3) 線性表的鏈式表示和實現(xiàn)4) 循環(huán)鏈表和雙向鏈表重 點: 順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)、雙向鏈表的特點，雙向鏈表的類型定義及相關(guān)操作的實現(xiàn)難 點: 順序表的插入刪除算法中數(shù)據(jù)元素的移動 鏈表的插入與刪除算法習 題: 順序表和各種鏈表的插入和刪除操作實 驗: 線性表的應用實驗（2學時）第3部分 棧和隊列總學時(單位：學時):8 講課:6 實驗:0 上機:2 具體內(nèi)容：1) 棧概念2) 棧的基本運算3) 棧的表示和實現(xiàn)4) 棧的應用舉例5) 隊列的基本運算6) 隊列的順序存儲結(jié)構(gòu)7) 隊列的鏈式存儲結(jié)構(gòu)重 點: 堆棧和隊列的各種運算方法難 點: 鏈式存儲結(jié)構(gòu)及其實現(xiàn)方法習 題: 棧和隊列的基本操作實 驗: 棧應用實驗（2學時）第4部分 串總學時(單位：學時):4 講課:4 實驗:0 上機:0 具體內(nèi)容：1) 串類型的定義2) 串的表示和實現(xiàn)3) 串的模式匹配算法4) 串操作應用舉例重 點: 基本概念和存儲結(jié)構(gòu)難 點: 串的模式匹配第5部分 數(shù)組和廣義表總學時(單位：學時):4 講課:4 實驗:0 上機:0 具體內(nèi)容：1) 數(shù)組的定義2) 數(shù)組的順序表示和實現(xiàn)3) 矩陣的壓縮存儲4) 廣義表的定義5) 廣義表的存儲結(jié)構(gòu)重 點: 數(shù)組的幾種常用表示方法、矩陣的存儲、廣義表的存儲結(jié)構(gòu)方法難 點: 廣義表的存儲結(jié)構(gòu)方法第6部分 樹和二叉樹總學時(單位：學時):8 講課:6 實驗:0 上機:2 具體內(nèi)容：1) 二叉樹的定義和性質(zhì)2) 二叉樹的存儲結(jié)構(gòu)3) 遍歷二叉樹4) 線索二叉樹5) 樹和森林重 點: 二叉樹的定義和性質(zhì)，遍歷二叉樹難 點: 線索二叉樹習 題: 二叉樹的遍歷，樹與二叉樹的轉(zhuǎn)換實 驗: 實現(xiàn)二叉樹的遍歷實驗（2學時）第7部分 圖總學時(單位：學時):4 講課:4 實驗:0 上機:0 具體內(nèi)容：1) 圖的定義和術(shù)語2) 圖的存儲結(jié)構(gòu)3) 圖的遍歷4) 圖的連通性重 點: 圖的存儲結(jié)構(gòu)，圖的遍歷難 點: 圖的遍歷，最小生成樹習 題: 圖的存儲表示及遍歷算法第8部分 查找總學時(單位：學時):4 講課:4 實驗:0 上機:0 具體內(nèi)容：1) 順序表的查找2) 有序表的查找3) 動態(tài)查找表4) 哈希表重 點: 有序表的查找，動態(tài)查找表難 點: 哈希表習 題: 有序表