《數(shù)據(jù)結(jié)構(gòu)》-付立冬.doc

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