1、數(shù)據(jù)結(jié)構(gòu)教學(xué)大綱課程編號(hào)：290305Z5課程名稱：數(shù)據(jù)結(jié)構(gòu)（Data Structures）課程性質(zhì)：必修（考試課）學(xué) 分：3學(xué)分總學(xué)時(shí)：48學(xué)時(shí)理論學(xué)時(shí)：24學(xué)時(shí)實(shí)驗(yàn)學(xué)時(shí)：24學(xué)時(shí)先修課程：C語(yǔ)言程序設(shè)計(jì)參考教材：1.李云清等主編，數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）（第三版），人民郵電出版社，2018.2.曲朝陽(yáng)主編，數(shù)據(jù)結(jié)構(gòu)（第一版），中國(guó)電力出版社，2016.一、課程在培養(yǎng)方案中的地位、目的和任務(wù)用計(jì)算機(jī)來(lái)解決實(shí)際問(wèn)題時(shí)，涉及到數(shù)據(jù)表示及數(shù)據(jù)處理，而數(shù)據(jù)表示及數(shù)據(jù)處理正是數(shù)據(jù)結(jié)構(gòu)課程的主要研究對(duì)象，通過(guò)這兩方面的學(xué)習(xí)，為后續(xù)課程，特別是軟件方面的課程打下了厚實(shí)的知識(shí)基礎(chǔ)，同時(shí)也提供了必要的技能訓(xùn)練。

2、因此，數(shù)據(jù)結(jié)構(gòu)課程在計(jì)算機(jī)應(yīng)用中具有舉足輕重的作用。目的：數(shù)據(jù)結(jié)構(gòu)作為一門主干課程主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及對(duì)數(shù)據(jù)的各種操作。主要有三個(gè)方面：數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)；對(duì)數(shù)據(jù)的操作（或算法）。通常，算法的設(shè)計(jì)取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，算法的實(shí)現(xiàn)取決于數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)。在基礎(chǔ)方面，要求學(xué)生掌握常用數(shù)據(jù)結(jié)構(gòu)的基本概念及其不同的實(shí)現(xiàn)方法；在技能方面，通過(guò)系統(tǒng)學(xué)習(xí)能夠在不同存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)不同的運(yùn)算，并對(duì)算法設(shè)計(jì)和技巧有所體會(huì)。二、課程教學(xué)的基本要求1.掌握數(shù)據(jù)結(jié)構(gòu)的基本概念、理解常用術(shù)語(yǔ)。2.初步掌握分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度的方法。3.掌握線性表的基本概念和基本操作。4

3、.掌握棧、隊(duì)列的定義及其基本運(yùn)算。5.掌握串、數(shù)組的基本概念，串的順序存儲(chǔ)表示及其實(shí)現(xiàn)算法。6.掌握二叉樹(shù)的性質(zhì)、存儲(chǔ)結(jié)構(gòu)以及在該存儲(chǔ)結(jié)構(gòu)下各種基本操作的實(shí)現(xiàn)。7.掌握?qǐng)D的基本概念和相關(guān)算法。8.理解查找的基本概念和常用的查找算法。9.掌握常用的排序算法。三、課程學(xué)時(shí)分配理論部分實(shí)驗(yàn)部分講授內(nèi)容學(xué)時(shí)實(shí)驗(yàn)內(nèi)容類型學(xué)時(shí)緒論1順序表的建立驗(yàn)證性2線性表4單鏈表的建立驗(yàn)證性2棧和隊(duì)列4棧設(shè)計(jì)型2串、數(shù)組和廣義表2循環(huán)隊(duì)列的建立及入隊(duì)驗(yàn)證性2樹(shù)和二叉樹(shù)4求順序串的子串設(shè)計(jì)型2圖4用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)建立二叉排序樹(shù)設(shè)計(jì)型2查找2用非遞歸算法遍歷二叉樹(shù)設(shè)計(jì)型2排序3求哈夫曼編碼設(shè)計(jì)型2建立無(wú)向圖的鄰接表驗(yàn)證性2圖

4、的深度優(yōu)先搜索設(shè)計(jì)型2折半查找設(shè)計(jì)型2快速排序設(shè)計(jì)型2合計(jì)2424四、考核1.考核方式：理論考核（筆試）、平時(shí)考核。2.成績(jī)構(gòu)成：平時(shí)成績(jī)30%，理論考核70%。五、課程基本內(nèi)容【理論課部分】第一章 緒論（一）目的要求:1.了解數(shù)據(jù)結(jié)構(gòu)的基本概念，理解常用術(shù)語(yǔ)；2.重點(diǎn)：掌握數(shù)據(jù)元素間的3種結(jié)構(gòu)關(guān)系；3.掌握算法的定義及特性，掌握算法設(shè)計(jì)的要求；4.難點(diǎn)：初步掌握分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度的方法；5.掌握C語(yǔ)言中的數(shù)據(jù)類型。（二）教學(xué)時(shí)數(shù)：1學(xué)時(shí)（三）教學(xué)內(nèi)容：1.數(shù)據(jù)結(jié)構(gòu)的基本概念；2.算法和算法分析；3.算法描述與C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)；4.C語(yǔ)言知識(shí)點(diǎn)。（四）教學(xué)方法：課堂講授法。（五）教

5、學(xué)手段：多媒體+板書(shū)。第二章 線性表（一）目的要求:1.掌握線性表的基本概念；2.重點(diǎn)：掌握順序表的各種基本操作；3.重點(diǎn)：掌握單鏈表、雙向鏈表的各種基本操作；4.難點(diǎn)：會(huì)運(yùn)用線性表解決實(shí)際問(wèn)題。（二）教學(xué)時(shí)數(shù)：4學(xué)時(shí)（三）教學(xué)內(nèi)容：1.線性表的基本概念；2.線性表的順序存儲(chǔ)結(jié)構(gòu)及基本操作；3.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及基本操作；4.順序表和鏈表的比較；5.線性表的應(yīng)用。（四）教學(xué)方法：課堂講授法。（五）教學(xué)手段：多媒體+板書(shū)。第三章 棧和隊(duì)列（一）目的要求:1.理解棧的定義及其基本運(yùn)算；2.重點(diǎn)：掌握順序棧和鏈棧的各種操作實(shí)現(xiàn)；3.理解隊(duì)列的定義及其基本運(yùn)算；4.重點(diǎn)：掌握循環(huán)隊(duì)列和鏈隊(duì)列的各種

6、操作實(shí)現(xiàn)；5.難點(diǎn)：學(xué)會(huì)利用棧和隊(duì)列解決一些問(wèn)題。（二）教學(xué)時(shí)數(shù)：4學(xué)時(shí)（三）教學(xué)內(nèi)容：1.棧、隊(duì)列的基本概念；2.棧的順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及基本操作；3.隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及基本操作；4.應(yīng)用。（四）教學(xué)方法：課堂講授法。（五）教學(xué)手段：多媒體+板書(shū)。第四章 串、數(shù)組和廣義表（一）目的要求:1.掌握串、數(shù)組的基本概念；2.重點(diǎn)：掌握串的順序存儲(chǔ)表示及其實(shí)現(xiàn)算法；3.難點(diǎn)：掌握串的匹配算法；4.掌握二維數(shù)組的存儲(chǔ)結(jié)構(gòu)。（二）教學(xué)時(shí)數(shù)：2學(xué)時(shí)（三）教學(xué)內(nèi)容：1.串的基本概念；2.串的運(yùn)算及存儲(chǔ)；3.串的模式匹配；4.數(shù)組的基本概念；5.數(shù)組的順序表示和實(shí)現(xiàn)。（四）教學(xué)方法：課

7、堂講授法。（五）教學(xué)手段：多媒體+板書(shū)。第五章 樹(shù)和二叉樹(shù)（一）目的要求:1.掌握樹(shù)和二叉樹(shù)的概念與定義；2.重點(diǎn)：掌握二叉樹(shù)的性質(zhì)；3.重點(diǎn)：掌握二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)以及在該存儲(chǔ)結(jié)構(gòu)下各種基本操作的實(shí)現(xiàn)；4.重難點(diǎn)：掌握二叉樹(shù)的非遞歸遍歷；5.掌握哈夫曼樹(shù)的定義與應(yīng)用。（二）教學(xué)時(shí)數(shù)：4學(xué)時(shí)（三）教學(xué)內(nèi)容：1.樹(shù)的定義及基本術(shù)語(yǔ)；2.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)；3.二叉樹(shù)的性質(zhì)；4.二叉樹(shù)的基本操作及實(shí)現(xiàn)；5.二叉樹(shù)的遍歷；6.哈夫曼樹(shù)。（四）教學(xué)方法：課堂講授法。（五）教學(xué)手段：多媒體+板書(shū)。第六章 圖（一）目的要求:1.掌握?qǐng)D的基本概念；2.掌握?qǐng)D的鄰接矩陣和鄰接表的生成算法；3.掌握?qǐng)D的廣度、深度優(yōu)

8、先搜索算法的實(shí)現(xiàn)；4.重難點(diǎn)：掌握最小生成樹(shù)算法的實(shí)現(xiàn)；5.重難點(diǎn)：掌握最短路徑算法的實(shí)現(xiàn).（二）教學(xué)時(shí)數(shù)：4學(xué)時(shí)（三）教學(xué)內(nèi)容：1.圖的基本概念；2.圖的存儲(chǔ)結(jié)構(gòu)；3.圖的遍歷；4.圖的連通性；5.最短路徑。（四）教學(xué)方法：課堂講授法。（五）教學(xué)手段：多媒體+板書(shū)。第七章 查找（一）目的要求:1.理解查找的基本概念；2.重點(diǎn)：掌握順序查找、折半查找、分塊查找的查找方法；3.掌握哈希表的構(gòu)造和查找方法；4.難點(diǎn)：掌握二叉排序樹(shù)的構(gòu)造和查找方法。（二）教學(xué)時(shí)數(shù)：2學(xué)時(shí)（三）教學(xué)內(nèi)容：1.基本概念；2.靜態(tài)查找；3.動(dòng)態(tài)查找；4.哈希查找。（四）教學(xué)方法：課堂講授法。（五）教學(xué)手段：多媒體+板書(shū)。

9、第八章 排序（一）目的要求:1.了解內(nèi)部排序、外部排序等概念；2.重點(diǎn)：熟練掌握直接插入排序、冒泡排序、直接選擇排序等簡(jiǎn)單的排序方法；3.重難點(diǎn)：掌握希爾排序、快速排序、堆排序和歸并排序等高效排序方法；4.難點(diǎn)：掌握各種排序算法的時(shí)間復(fù)雜度分析方法和結(jié)果，學(xué)會(huì)根據(jù)實(shí)際問(wèn)題來(lái)選擇合適排序方法。（二）教學(xué)時(shí)數(shù)：3學(xué)時(shí)（三）教學(xué)內(nèi)容：1.排序基本概念；2.插入類排序；3.交換類排序；4.選擇類排序；5.歸并排序；6.各種排序方法比較。（四）教學(xué)方法：課堂講授法。（五）教學(xué)手段：多媒體+板書(shū)?！緦?shí)驗(yàn)課部分】實(shí)驗(yàn)一 順序表的建立（一）目的要求：了解順序表的結(jié)構(gòu)特點(diǎn)及有關(guān)概念，掌握順序表建立的基本操作算法

10、。（二）教學(xué)內(nèi)容：建立4個(gè)元素的順序表list=1,2,3,4，實(shí)現(xiàn)順序表的基本操作。實(shí)驗(yàn)二 單鏈表的建立（一）目的要求：了解單鏈表的結(jié)構(gòu)特點(diǎn)、描述方法及有關(guān)概念、掌握單鏈表建立的基本操作算法。（二）教學(xué)內(nèi)容：建立一個(gè)包括頭結(jié)點(diǎn)和3個(gè)結(jié)點(diǎn)(4,2,1）的單鏈表，實(shí)現(xiàn)單鏈表建立的基本操作。實(shí)驗(yàn)三 棧（一）目的要求：1.熟悉并能實(shí)現(xiàn)棧的定義和基本操作；2.了解和掌握棧在遞歸和非遞歸算法的應(yīng)用。（二）教學(xué)內(nèi)容：設(shè)計(jì)一個(gè)算法，判斷一個(gè)表達(dá)式中符號(hào)”(”、”)”、”、”、”、”是否匹配。若匹配，則返回1；否則返回0。實(shí)驗(yàn)四 循環(huán)隊(duì)列及入隊(duì)的建立（一）目的要求：了解順序隊(duì)列產(chǎn)生假溢出的原因及循環(huán)隊(duì)列的結(jié)構(gòu)

11、特點(diǎn)和有關(guān)概念，掌握循環(huán)隊(duì)列的建立及入隊(duì)的基本操作算法。（二）教學(xué)內(nèi)容：建立循環(huán)隊(duì)列，并實(shí)現(xiàn)元素（3,4,5,6,7）入隊(duì)，實(shí)現(xiàn)循環(huán)隊(duì)列的建立和入隊(duì)的基本操作。實(shí)驗(yàn)五 求順序串的子串（一）目的要求：了解串的有關(guān)概念及串和線性表的關(guān)系，掌握串的存儲(chǔ)結(jié)構(gòu)及串的基本運(yùn)算。（二）教學(xué)內(nèi)容：在順序結(jié)構(gòu)下，求主串S中從第i個(gè)字符起，長(zhǎng)度為k的子串。實(shí)驗(yàn)六 用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)建立二叉排序樹(shù)（一）目的要求：通過(guò)二叉排序樹(shù)的建立來(lái)了解二叉樹(shù)的定義及有關(guān)概念，熟悉二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及性質(zhì)。（二）教學(xué)內(nèi)容：建立一個(gè)二叉排序樹(shù)。實(shí)驗(yàn)七 用非遞歸算法遍歷二叉樹(shù)（一）目的要求：進(jìn)一步熟悉二叉樹(shù)的遍歷方法，掌握將遞歸遍歷算法轉(zhuǎn)換

12、為非遞歸遍歷算法的方法。（二）教學(xué)內(nèi)容：用非遞歸算法實(shí)現(xiàn)二叉樹(shù)的前序、中序和后序遍歷。實(shí)驗(yàn)八 求哈夫曼編碼（一）目的要求：了解哈夫曼樹(shù)的定義，掌握構(gòu)造哈夫曼樹(shù)的方法及哈夫曼編碼的生成。（二）教學(xué)內(nèi)容：輸入一串葉子結(jié)點(diǎn)的權(quán)值，建立一棵哈夫曼樹(shù)，并求出每個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼。實(shí)驗(yàn)九建立無(wú)向圖的鄰接表（一）目的要求：了解圖及無(wú)向圖的定義，熟悉無(wú)向圖的存儲(chǔ)結(jié)構(gòu)及鄰接矩陣和鄰接表等有關(guān)概念，掌握建立無(wú)向圖鄰接表的基本操作算法。（二）教學(xué)內(nèi)容：建立無(wú)向圖的鄰接表，并實(shí)現(xiàn)插入、刪除邊的功能。實(shí)驗(yàn)十 圖的深度優(yōu)先搜索（一）目的要求：進(jìn)一步熟悉圖的存儲(chǔ)結(jié)構(gòu)及鄰接矩陣和鄰接表等有關(guān)概念，掌握?qǐng)D的深度優(yōu)先搜索方法