《數(shù)據(jù)結(jié)構(gòu)與算法》理論教學(xué)大綱

《數(shù)據(jù)結(jié)構(gòu)與算法》理論教學(xué)大綱（DataStructureandAlgorithm）課程代碼：0610009總學(xué)時：80學(xué)時（其中：講課50學(xué)時、實驗30學(xué)時）先修課程：《C語言程序設(shè)計》、《離散數(shù)學(xué)》一、課程的性質(zhì)、目的與任務(wù)《數(shù)據(jù)結(jié)構(gòu)與算法》是計算機科學(xué)與技術(shù)專業(yè)、信息管理和信息系統(tǒng)專業(yè)的一門重要專業(yè)基礎(chǔ)課，是計算機及相關(guān)學(xué)科的公認主干課。計算機科學(xué)各領(lǐng)域及有關(guān)的系統(tǒng)和應(yīng)用軟件都要用到各種數(shù)據(jù)結(jié)構(gòu)。本課程是計算機科學(xué)與技術(shù)專業(yè)、信息管理和信息系統(tǒng)專業(yè)的專業(yè)課，主要介紹用計算機解決一系列問題，特別是非數(shù)值計算類問題時所用的各種數(shù)據(jù)組織方法、存儲結(jié)構(gòu)，以及在各種結(jié)構(gòu)上執(zhí)行的主要操作。通過本課程的學(xué)習(xí)，要使學(xué)生熟練地掌握數(shù)據(jù)結(jié)構(gòu)的內(nèi)在邏輯關(guān)系及其在計算機中的表示方法（存儲結(jié)構(gòu)），以及有關(guān)基本操作的算法實現(xiàn)；熟悉它們在計算機科學(xué)中的基本應(yīng)用；培養(yǎng)和訓(xùn)練學(xué)生結(jié)合實際應(yīng)用，根據(jù)求解的問題合理選擇數(shù)據(jù)結(jié)構(gòu)、應(yīng)用高級語言編寫和實現(xiàn)結(jié)構(gòu)清晰、正確易讀的有效算法的能力；并為學(xué)習(xí)《操作系統(tǒng)》、《編譯原理》、《數(shù)據(jù)庫原理》等后續(xù)課程和研制開發(fā)各種系統(tǒng)和應(yīng)用軟件打下扎實的理論和實踐基礎(chǔ)。二、教學(xué)基本內(nèi)容與基本要求1．基本內(nèi)容本課程主要教學(xué)基本內(nèi)容包括：線性表、棧與隊列、串、數(shù)組和廣義表、樹和二叉樹、圖、查找表、內(nèi)部排序等。每種數(shù)據(jù)結(jié)構(gòu)都要介紹數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)定義和物理存儲實現(xiàn)以及該數(shù)據(jù)結(jié)構(gòu)的主要應(yīng)用。2．基本要求通過本課程的學(xué)習(xí)，要求學(xué)生了解數(shù)據(jù)結(jié)構(gòu)及其分類、數(shù)據(jù)結(jié)構(gòu)與算法的密切關(guān)系；熟悉各種基本數(shù)據(jù)結(jié)構(gòu)及其操作，學(xué)會根據(jù)實際問題要求來選擇數(shù)據(jù)結(jié)構(gòu)；掌握設(shè)計算法的步驟和算法分析方法；掌握數(shù)據(jù)結(jié)構(gòu)在排序和查找等常用算法中的應(yīng)用。三、教學(xué)內(nèi)容及學(xué)時分配教學(xué)內(nèi)容教學(xué)要求重點(☆)難點(Δ)學(xué)時安排備注第一章緒論1、什么是數(shù)據(jù)結(jié)構(gòu)2、基本概念和術(shù)語3、抽象數(shù)據(jù)類型的表示與實現(xiàn)4、算法與算法分析BBAA☆☆ΔΔ3第二章線性表1、線性表的類型定義2、線性表的順序表示與實現(xiàn)3、線性表的鏈式表示與實現(xiàn)4、一元多項式的表示及相加AAAC☆ΔΔΔ6第三章棧和隊列1、棧2、棧的應(yīng)用舉例3、棧與遞歸的實現(xiàn)4、隊列ABCA☆☆ΔΔΔ5第四章串1、串類型的定義2、串的表示與實現(xiàn)3、串的模式匹配算法4、串操作應(yīng)用舉例CAB☆☆ΔΔ3第五章數(shù)組與廣義表1、數(shù)組的定義2、數(shù)組的順序表示與實現(xiàn)3、矩陣的壓縮存儲4、廣義表的定義5、廣義表的存儲結(jié)構(gòu)CBABB☆ΔΔΔ5第六章樹和二叉樹1、樹的定義和基本術(shù)語2、二叉樹3、遍歷二叉樹和線索二叉樹4、樹和森林5、赫夫曼樹及其應(yīng)用CAABA☆ΔΔΔ8第七章圖1、圖的定義和術(shù)語2、圖的存儲結(jié)構(gòu)3、圖的遍歷4、圖的連通性問題5、有向無環(huán)圖及其應(yīng)用6、最短路徑BAABBB☆☆☆ΔΔΔΔΔΔ9第八章查找1、靜態(tài)查找表2、動態(tài)查找表3、哈希表ABA☆ΔΔΔ5第九章內(nèi)部排序1、概述2、插入排序3、快速排序4、選擇排序5、歸并排序6、基數(shù)排序CABABB☆☆ΔΔΔΔΔ6合計55（教學(xué)要求：A—熟練掌握；B—掌握；C—了解）四、建議實驗項目及學(xué)時分配序號實驗項目名稱實驗學(xué)時內(nèi)容提要實驗要求實驗類型1單鏈表的建立、插入和刪除3掌握線性表的鏈式存儲結(jié)構(gòu)操作算法必做驗證2棧的建立、入棧和出棧2掌握棧的操作算法必做驗證3隊列的建立、入隊和出隊3掌握隊列的操作算法必做驗證4模式串的匹配3掌握串的模式匹配算法必做驗證5稀疏矩陣的轉(zhuǎn)置2掌握稀疏矩陣轉(zhuǎn)置的操作算法必做驗證6二叉樹操作3掌握用指針類型描述、訪問和處理二叉樹的操作算法必做驗證7圖的最小生成樹5掌握圖的最小生成樹算法必做驗證8直接插入排序3掌握直接插入排序操作算法必做驗證9哈夫曼編碼/譯碼器6完成一個大作業(yè)，利用哈夫曼樹的知識來設(shè)計，并在VisualC++6.0環(huán)境下實現(xiàn)必做綜合合計30五、教學(xué)方法與教學(xué)手段1．教學(xué)方法：在重視課堂講授的同時，加強實驗教學(xué)，培養(yǎng)學(xué)生的實際應(yīng)用能力及實踐能力。在課堂教學(xué)中采用啟發(fā)式、討論式、參與式等教學(xué)方法，調(diào)動學(xué)生的積極性和學(xué)習(xí)興趣，提高教學(xué)質(zhì)量，促進教學(xué)相長。2．教學(xué)手段：利用多媒體、CAI課件等現(xiàn)代化教學(xué)手段，提高課堂教學(xué)水平。采取講練結(jié)合、理論聯(lián)系實際等方式，提高課堂教學(xué)效果。六、建議教材與參考書目1．建議教材：①《數(shù)據(jù)結(jié)構(gòu)》，嚴蔚敏、吳偉民編著，清華大學(xué)出版社，2008年3月。②《數(shù)據(jù)結(jié)構(gòu)題集》，嚴蔚敏，吳偉民編著，清華大學(xué)出版社，2004年7月。2．參考書目：①《數(shù)據(jù)結(jié)構(gòu)實踐教程》，胡元義等編著，西安電子科技大學(xué)出版社，2002年。②《數(shù)據(jù)結(jié)構(gòu)算法設(shè)計指導(dǎo)》，胡學(xué)鋼編著，清華大學(xué)出版社，1999年2月。③《數(shù)據(jù)結(jié)構(gòu)》，黃劉生，唐策善編著，中國科學(xué)技術(shù)大學(xué)出版社，2000年8月。④《數(shù)據(jù)結(jié)構(gòu)》，王曉東編著，電子工業(yè)出版社，2007年7月。七、大綱編寫的依據(jù)與說明本課程教學(xué)大綱，是根據(jù)計算機科學(xué)與技術(shù)專業(yè)、信息管理和信息系統(tǒng)專業(yè)培養(yǎng)目標，向計算機軟件方向拓展的要求，結(jié)合本課