附表1-1 理論課程教學(xué)大綱

1、理論課程教學(xué)大綱課程名稱數(shù)據(jù)結(jié)構(gòu)英文名稱DataStructures課程編號(hào)不填總學(xué)時(shí)60學(xué)分不填預(yù)修課程C語(yǔ)言開課學(xué)期不填大綱撰寫人黃劉生一、教學(xué)目標(biāo)和基本要求?目的：目的：使學(xué)生較全面地掌握各種常用的數(shù)據(jù)結(jié)構(gòu)，提高其數(shù)據(jù)抽象和程序設(shè)計(jì)能力為學(xué)習(xí)后續(xù)軟件課程提供堅(jiān)實(shí)的基礎(chǔ)。?基本要求：基本要求：使學(xué)生能夠從邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算三個(gè)方面去掌握各種數(shù)據(jù)結(jié)構(gòu)的特性對(duì)算法的時(shí)、空復(fù)雜性有一定的分析能力，使之能夠針對(duì)具體的應(yīng)用問(wèn)題，選

2、擇合適的數(shù)據(jù)結(jié)構(gòu)及設(shè)計(jì)結(jié)構(gòu)清晰、正確有效的算法解決之。二、課程簡(jiǎn)介數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)學(xué)科一門重要的專業(yè)基礎(chǔ)課，該課程系統(tǒng)地討論各種常用的數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用，以及查找和排序的各種方法及其綜合分析比較，培養(yǎng)學(xué)生數(shù)據(jù)抽象和程序設(shè)計(jì)的能力，算法時(shí)、空復(fù)雜性的分析能力。三、教學(xué)重點(diǎn)、難點(diǎn)1概論：概論：重點(diǎn)是了解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及數(shù)據(jù)的運(yùn)算三方面的概念及其相互關(guān)系，難點(diǎn)是抽象數(shù)據(jù)類型和算法復(fù)雜度的分析方法。2線性表：線性表：重點(diǎn)是熟練掌握順

3、序表和單鏈表上實(shí)現(xiàn)的各種基本算法及相關(guān)的時(shí)間性能分析，難點(diǎn)是能夠使用所學(xué)到的基本知識(shí)設(shè)計(jì)有效算法解決與線性表相關(guān)的應(yīng)用問(wèn)題。3棧和隊(duì)列：棧和隊(duì)列：重點(diǎn)是掌握棧和隊(duì)列在兩種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的基本運(yùn)算，難點(diǎn)是循環(huán)隊(duì)列中對(duì)邊界條件的處理。4串：串：重點(diǎn)是掌握串上實(shí)現(xiàn)的模式匹配算法，這也是本章的難點(diǎn)。5樹：樹：重點(diǎn)掌握二叉樹的遍歷算法及其有關(guān)應(yīng)用，難點(diǎn)是使用本章所學(xué)到的有關(guān)知識(shí)設(shè)計(jì)出有效算法解決與樹或二叉樹相關(guān)的應(yīng)用問(wèn)題。6圖：圖：重點(diǎn)掌握?qǐng)D在鄰

4、接矩陣與鄰近表上實(shí)現(xiàn)的遍歷算法。難點(diǎn)是求圖的最小生成樹、最短路徑、拓?fù)渑判虻葢?yīng)用算法及其時(shí)間性能分析。7動(dòng)態(tài)存儲(chǔ)管理動(dòng)態(tài)存儲(chǔ)管理:重點(diǎn)是內(nèi)存空間的分配與回收算法，以及可利用空間表的結(jié)構(gòu)。本章難點(diǎn)是無(wú)用單元收集算法的理解與掌握。8查找：查找：重點(diǎn)掌握順序查找、二分查找、二叉查找樹上查找以及散列表上查找的基本思想和算法實(shí)現(xiàn)。本章難點(diǎn)是二叉查找樹的刪除算法及B樹上的插入和刪除算法。9文件：文件：本章重點(diǎn)是介紹存儲(chǔ)在外存上的數(shù)據(jù)結(jié)構(gòu)（文件）的有

5、關(guān)概念、各種文件的特點(diǎn)、組織方法及查詢和更新操作。四、教材名稱及主要參考書《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版》嚴(yán)蔚敏、吳偉民，清華大學(xué)出版社，2000?！稊?shù)據(jù)結(jié)構(gòu)第2版》黃劉生、唐策善，中國(guó)科技大學(xué)出版社，2001?！癉ataStructureswithC“WilliawFdetal.PrenticeHallInc.1996.“DataStructures&ProgramDesigninC2ndEd.“RobertKruseetal.PrenticeH

6、allInc.1997.五、課程章節(jié)主要內(nèi)容及學(xué)時(shí)分配第一章第一章概論（3學(xué)時(shí)）第一節(jié)基本概念和術(shù)語(yǔ)第二節(jié)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義第三節(jié)抽象數(shù)據(jù)類型第四節(jié)算法的描述和分析第二章第二章線性表線性表（6學(xué)時(shí)）第一節(jié)線性表的邏輯結(jié)構(gòu)第二節(jié)線性表的順序存貯結(jié)構(gòu)第三節(jié)線性表的鏈?zhǔn)酱尜A結(jié)構(gòu)第四節(jié)順序表和鏈表的比較第三章第三章棧和隊(duì)列棧和隊(duì)列（6學(xué)時(shí)）第一節(jié)棧第二節(jié)隊(duì)列第三節(jié)棧與隊(duì)列的應(yīng)用實(shí)例第四章第四章串（4學(xué)時(shí)）第一節(jié)串及其運(yùn)算第二節(jié)串的存貯結(jié)構(gòu)第三節(jié)

7、串的模式匹配第六章第六章樹（10學(xué)時(shí)）第一節(jié)樹的概念第二節(jié)二叉樹第三節(jié)二叉樹的遍歷第四節(jié)線索二叉樹第五節(jié)樹和森林第六節(jié)哈夫曼樹及其應(yīng)用第七節(jié)樹與等價(jià)問(wèn)題、樹的計(jì)數(shù)第六章第六章圖（10學(xué)時(shí)）第一節(jié)圖的概念第二節(jié)圖的存貯結(jié)構(gòu)第三節(jié)圖的遍歷第四節(jié)圖的連通性問(wèn)題第五節(jié)最短路徑第六節(jié)有向無(wú)環(huán)圖及其應(yīng)用第七章第七章動(dòng)態(tài)存儲(chǔ)管理動(dòng)態(tài)存儲(chǔ)管理（5學(xué)時(shí)）第一節(jié)概述第二節(jié)可利用空間表及分配算法第三節(jié)邊界標(biāo)識(shí)法第四節(jié)伙伴系統(tǒng)第五節(jié)無(wú)用單元收集第八章第八章查找