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

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