數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版教學(xué)大綱

1、 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）教學(xué)大綱湖南省郴州職業(yè)技術(shù)學(xué)院計(jì)算機(jī)系 編寫時(shí)間：2004年8月28日數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）教學(xué)大綱一、課程性質(zhì)、任務(wù)和基本要求本課程的教學(xué)目的和要求用計(jì)算機(jī)來(lái)解決實(shí)際問題時(shí)，就要涉及到數(shù)據(jù)的表示及數(shù)據(jù)的處理，而數(shù)據(jù)表示及數(shù)據(jù)處理正是數(shù)據(jù)結(jié)構(gòu)課程的主要研究對(duì)象，通過這兩方面內(nèi)容的學(xué)習(xí)，為后續(xù)課程，特別是軟件方面的課程打下了厚實(shí)的知識(shí)基礎(chǔ)，同時(shí)也提供了必要的技能訓(xùn)練。因此，數(shù)據(jù)結(jié)構(gòu)課程在計(jì)算機(jī)應(yīng)用中具有舉足輕重的作用。本課程的任務(wù)是：在基礎(chǔ)方面，要求學(xué)生掌握常用數(shù)據(jù)結(jié)構(gòu)的基本概念及其不同的實(shí)現(xiàn)方法；在技能方面，通過系統(tǒng)學(xué)習(xí)能夠在不同存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)不同的運(yùn)算，并對(duì)算法設(shè)計(jì)的方式

2、和技巧有所體會(huì)。本課程的主要內(nèi)容數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)的概念及其相互間的關(guān)系；數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的聯(lián)系與區(qū)別以及在數(shù)據(jù)結(jié)構(gòu)上施加的運(yùn)算及其實(shí)現(xiàn)。線性表的定義及其運(yùn)算；順序表和鏈表的定義、組織形式、結(jié)構(gòu)特征和類型說明以及在這兩種表上實(shí)現(xiàn)的插入、刪除和按值查找的算法。循環(huán)鏈表、雙(循環(huán))鏈表的結(jié)構(gòu)特點(diǎn)和在其上施加的插入、刪除等操作。棧和隊(duì)列的定義、特征及在其上所定義的基本運(yùn)算，在兩種存儲(chǔ)結(jié)構(gòu)上對(duì)棧和隊(duì)列所施加的基本運(yùn)算的實(shí)現(xiàn)。串的定義、存儲(chǔ)方式和常用的串運(yùn)算；多維數(shù)組的結(jié)構(gòu)特點(diǎn)和在內(nèi)存中的兩種順序存儲(chǔ)方式，矩陣和三角矩陣元素的存儲(chǔ)。樹的定義、性質(zhì)及其存儲(chǔ)方法；二叉樹的二叉鏈表存儲(chǔ)方式、結(jié)

3、點(diǎn)結(jié)構(gòu)和類型定義；二叉樹的遍歷算法；樹、森林與二叉樹間的相互轉(zhuǎn)換；哈夫曼樹的構(gòu)造方法。圖的基本概念及術(shù)語(yǔ)；圖的兩種存儲(chǔ)結(jié)構(gòu)(鄰接矩陣和鄰接表)的表示方法；圖的遍歷(深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷)算法；最小生成樹的構(gòu)造；拓?fù)渑判颉㈥P(guān)鍵路徑以及最短路徑算法。查找的基本思想及查找成功和不成功的概念；在順序表、有序表、索引表、散列表等上的查找方法和算法；二叉排序樹、平衡二叉樹以及B-樹的概念和有關(guān)算法；散列表的構(gòu)造。排序的基本思想和基本概念；插入排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序及基數(shù)排序的基本思想、步驟及算法。教學(xué)重點(diǎn)及難點(diǎn)領(lǐng)會(huì)數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)的概念及其相互間的關(guān)系

4、。清楚數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的聯(lián)系與區(qū)別，以及在數(shù)據(jù)結(jié)構(gòu)上施加的運(yùn)算及其實(shí)現(xiàn)。會(huì)進(jìn)行簡(jiǎn)單的算法分析。理解線性表的定義及其運(yùn)算。理解順序表和鏈表的定義、組織形式、結(jié)構(gòu)特征和類型說明，掌握在這兩種表上實(shí)現(xiàn)的插入、刪除和按值查找的算法。了解循環(huán)鏈表、雙(循環(huán))鏈表的結(jié)構(gòu)特點(diǎn)和在其上施加的插入、刪除等操作。了解串的定義、存儲(chǔ)方式和常用的串運(yùn)算。理解棧和隊(duì)列的定義、特征及在其上所定義的基本運(yùn)算，掌握在兩種存儲(chǔ)結(jié)構(gòu)上對(duì)棧和隊(duì)列所施加的基本運(yùn)算的實(shí)現(xiàn)。理解多維數(shù)組的結(jié)構(gòu)特點(diǎn)和在內(nèi)存中的兩種順序存儲(chǔ)方式，對(duì)矩陣和三角矩陣能推出給定元素在存儲(chǔ)區(qū)中的地址。深刻理解樹的定義、性質(zhì)及其存儲(chǔ)方法，熟練掌握二叉樹的

5、二叉鏈表存儲(chǔ)方式、結(jié)點(diǎn)結(jié)構(gòu)和類型定義，并能畫出給定二叉樹的二叉鏈表的結(jié)構(gòu)示意圖；理解并掌握二叉樹的三種遍歷方法，并能寫出該三種遍歷的算法；會(huì)完成樹、森林與二叉樹間的相互轉(zhuǎn)換；理解哈夫曼樹的構(gòu)造方法，并能對(duì)給定的數(shù)據(jù)集合構(gòu)造出哈夫曼樹。理解圖的基本概念及術(shù)語(yǔ)，掌握?qǐng)D的兩種存儲(chǔ)結(jié)構(gòu)(鄰接矩陣和鄰接表)的表示方法；熟練掌握?qǐng)D的兩種遍歷(深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷)的算法思想、步驟，并能列出在兩種存儲(chǔ)結(jié)構(gòu)上按上述兩種遍歷算法得到的序列；理解最小生成樹的概念，能按Prim算法構(gòu)造最小生成樹；了解并掌握拓?fù)渑判颉㈥P(guān)鍵路徑、最短路徑的算法思想。了解查找的基本思想及查找成功和不成功的概念，掌握在順序表

6、、有序表、索引表、散列表等上的查找方法和算法，并能求出相應(yīng)的平均查找長(zhǎng)度。了解排序的基本思想和基本概念，理解和掌握插入排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序和基數(shù)排序的基本思想、步驟及算法。4教材的選用嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）.北京：清華大學(xué)出版社.1999,2二、課程時(shí)數(shù)分配內(nèi) 容講課實(shí)驗(yàn)小計(jì)第一章緒論22第二章線性表12416第三章 棧和隊(duì)列628第四章 串628第五章 數(shù)組和廣義表66第六章 樹和二叉樹12416第七章 圖8412第九章 查找8412第十章 排序8412總 計(jì)681692三、課程內(nèi)容 第一章概論教學(xué)內(nèi)容1.1 數(shù)據(jù)結(jié)構(gòu)的概念1.2 抽象數(shù)據(jù)類

7、型1.3 算法和算法分析。教學(xué)目的及要求 領(lǐng)會(huì)數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)的概念及其相互間的關(guān)系；清楚數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的聯(lián)系與區(qū)別，以及在數(shù)據(jù)結(jié)構(gòu)上施加的運(yùn)算及其實(shí)現(xiàn)；理解抽象數(shù)據(jù)類型的概念；掌握進(jìn)行簡(jiǎn)單算法分析的方法。教學(xué)重點(diǎn)數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)；邏輯結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)在概念上的聯(lián)系與區(qū)別；運(yùn)算的概念；存儲(chǔ)結(jié)構(gòu)及其三個(gè)組成部分；抽象數(shù)據(jù)類型和數(shù)據(jù)抽象；評(píng)價(jià)算法優(yōu)劣的標(biāo)準(zhǔn)及方法。教學(xué)難點(diǎn)區(qū)別算法與程序；邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的聯(lián)系與區(qū)別；抽象數(shù)據(jù)類型與數(shù)據(jù)抽象；算法的時(shí)間復(fù)雜度分析。練習(xí)題1.1 1.7 1.16 第二章 線性表教學(xué)內(nèi)容2.1 線性表邏輯結(jié)構(gòu)2.1 線性表的順序存儲(chǔ)及運(yùn)算實(shí)現(xiàn)2

8、.3 線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)教學(xué)目的及要求理解線性表的定義及其運(yùn)算；理解順序表和鏈表的定義、組織形式、結(jié)構(gòu)特征和類型說明；掌握在這兩種表上實(shí)現(xiàn)的插入、刪除和按值查找的算法；了解循環(huán)鏈表、雙(循環(huán))鏈表的結(jié)構(gòu)特點(diǎn)和在其上施加的插入、刪除等操作。教學(xué)重點(diǎn)線性表的定義及邏輯上的特點(diǎn)；順序表上插入、刪除和定位運(yùn)算的實(shí)現(xiàn)；單鏈表的結(jié)構(gòu)特點(diǎn)及類型說明；頭指針和頭結(jié)點(diǎn)的作用及區(qū)別；指針操作；定位、刪除、插入運(yùn)算在單鏈表上的實(shí)現(xiàn)；循環(huán)鏈表、雙鏈表的結(jié)構(gòu)特點(diǎn)；循環(huán)鏈表、雙鏈表上刪除與插入運(yùn)算的實(shí)現(xiàn)。教學(xué)難點(diǎn)線性表與線性結(jié)構(gòu)的聯(lián)系與區(qū)別；頭結(jié)點(diǎn)在鏈表中的作用；指針操作；刪除、插入運(yùn)算中的指針操作順序；雙鏈表上指針

9、的操作順序練習(xí)題2.6 2.7 2.11 2.14 2.19 2.42第三章 棧和隊(duì)列教學(xué)內(nèi)容3.1 棧3.2 棧應(yīng)用舉例3.3 隊(duì)列3.4 隊(duì)列應(yīng)用舉例教學(xué)目的及要求理解棧的定義、特征及在其上所定義的基本運(yùn)算；掌握在兩種存儲(chǔ)結(jié)構(gòu)上對(duì)棧所施加的基本運(yùn)算的實(shí)現(xiàn)；理解隊(duì)列的定義、特征及在其上所定義的基本運(yùn)算；掌握在兩種存儲(chǔ)結(jié)構(gòu)上對(duì)隊(duì)列所施加的基本運(yùn)算的實(shí)現(xiàn)。教學(xué)重點(diǎn)棧的定義及邏輯特點(diǎn)；棧上的基本運(yùn)算；棧的順序存儲(chǔ)結(jié)構(gòu)及運(yùn)算實(shí)現(xiàn)；棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；入棧、出棧等運(yùn)算在鏈棧上的實(shí)現(xiàn)；隊(duì)列的定義及邏輯特點(diǎn)；隊(duì)列上的基本運(yùn)算；隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其上的運(yùn)算實(shí)現(xiàn)；隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；入隊(duì)、出隊(duì)等運(yùn)算在鏈隊(duì)列上

10、的實(shí)現(xiàn)。教學(xué)難點(diǎn) 順序棧的溢出判斷條件；循環(huán)隊(duì)列的隊(duì)空、隊(duì)滿判斷條件；循環(huán)隊(duì)列上的插入、刪除操作。練習(xí)題 3.2 3.3 3.17 第四章 串教學(xué)內(nèi)容4.1 串及其基本運(yùn)算4.2 串的定長(zhǎng)順序存儲(chǔ)及基本運(yùn)算4.3 串的堆存儲(chǔ)結(jié)構(gòu)教學(xué)目的及要求了解串的定義；理解和領(lǐng)會(huì)串的存儲(chǔ)方式；掌握常用的串運(yùn)算。教學(xué)重點(diǎn)串的基本概念、基本運(yùn)算；串的兩種存儲(chǔ)方式。串的模式匹配算法。教學(xué)難點(diǎn)串的模式匹配算法；串的基本運(yùn)算的綜合應(yīng)用練習(xí)題4.3 4.7 4.17 4.24第五章 數(shù)組、特殊矩陣和廣義表教學(xué)內(nèi)容5.1 多維數(shù)組5.2 特殊矩陣的壓縮存儲(chǔ)5.3 稀疏矩陣5.4 廣義表教學(xué)目的及要求理解多維數(shù)組的結(jié)構(gòu)特點(diǎn)

11、和在內(nèi)存中的兩種順序存儲(chǔ)方式；理解并掌握矩陣和特殊矩陣元素在存儲(chǔ)區(qū)中地址的計(jì)算；領(lǐng)會(huì)稀疏矩陣的壓縮方式和簡(jiǎn)單運(yùn)算；了解廣義表的定義和基本運(yùn)算。教學(xué)重點(diǎn)多維數(shù)組的邏輯結(jié)構(gòu)；多維組的兩種順序存儲(chǔ)方式；計(jì)算給定元素在存儲(chǔ)區(qū)中的地址；對(duì)稱矩陣、三角矩陣的壓縮存儲(chǔ)方式；計(jì)算給定元素在存儲(chǔ)區(qū)中的地址；稀疏矩陣的三元組表表示方法。教學(xué)難點(diǎn)稀疏矩陣的壓縮存儲(chǔ)表示下的運(yùn)算的實(shí)現(xiàn)練習(xí)題 5.1 5.4 5.9 5.13第六章 樹和二叉樹教學(xué)內(nèi)容6.1 定義與性質(zhì)6.2 存儲(chǔ)實(shí)現(xiàn)基本操作的實(shí)現(xiàn)6.3 二叉樹的遍歷6.4 線索二叉樹6.5 二叉樹的應(yīng)用教學(xué)目的及要求 深刻理解二叉樹的定義、性質(zhì)及其存儲(chǔ)方法；熟練掌握二

12、叉樹的二叉鏈表存儲(chǔ)方式、結(jié)點(diǎn)結(jié)構(gòu)和類型定義；理解并掌握二叉樹的三種遍歷算法；掌握二叉樹的線索化方法；靈活運(yùn)用二叉樹的遍歷方法解決相關(guān)的應(yīng)用問題。教學(xué)重點(diǎn)二叉樹的定義、邏輯特點(diǎn)及五種基本形態(tài)；二叉樹的五個(gè)性質(zhì)；在二叉樹上定義的基本運(yùn)算；二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其類型說明；二叉樹的順序存儲(chǔ)結(jié)構(gòu)及其類型說明；二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的組織方式；二叉樹的三種遍歷方法及其算法；以遍歷為基礎(chǔ)在二叉樹上實(shí)現(xiàn)的幾種運(yùn)算；哈夫曼樹和哈夫曼算法。教學(xué)難點(diǎn)二叉樹的遞歸定義；二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的組織方式；三種遍歷的主要區(qū)別；二叉樹上的復(fù)雜運(yùn)算；哈夫曼算法及其應(yīng)用。練習(xí)題 6.1 6.2 6.3 6.5 6.12 6.19 6

13、.23 6.27第七章 樹教學(xué)內(nèi)容7.1 樹的概念與表示7.2 基本操作與存儲(chǔ)7.3 樹、森林與二叉樹的轉(zhuǎn)換7.4 樹或森林的遍歷7.5 樹的應(yīng)用 教學(xué)目的及要求深刻理解樹的定義、術(shù)語(yǔ)；領(lǐng)會(huì)并掌握樹的各種存儲(chǔ)結(jié)構(gòu)；熟練掌握森林與二叉樹間的相互轉(zhuǎn)換；領(lǐng)會(huì)樹和森林的遍歷；了解樹的簡(jiǎn)單應(yīng)用。教學(xué)重點(diǎn)樹的存儲(chǔ)結(jié)構(gòu)；森林與二叉樹的轉(zhuǎn)換。教學(xué)難點(diǎn)森林與二叉樹的轉(zhuǎn)換；判定樹；等價(jià)關(guān)系與等價(jià)類問題。練習(xí)題第七章 圖教學(xué)內(nèi)容8.1 圖的基本概念 8.2 圖的存儲(chǔ)表示8.3 圖的遍歷8.4 圖的連通性 8.5 最小生成樹 8.6 最短路徑 8.7 有向無(wú)環(huán)圖及其應(yīng)用教學(xué)目的及要求理解圖的基本概念及術(shù)語(yǔ)；掌握?qǐng)D的兩

14、種存儲(chǔ)結(jié)構(gòu)(鄰接矩陣和鄰接表)的表示方法；熟練掌握?qǐng)D的兩種遍歷(深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷)的算法思想、步驟，并能列出在兩種存儲(chǔ)結(jié)構(gòu)上按上述兩種遍歷算法得到的序列；理解最小生成樹的概念，能按Prim算法構(gòu)造最小生成樹；領(lǐng)會(huì)并掌握拓?fù)渑判?、關(guān)鍵路徑、最短路徑的算法思想。教學(xué)重點(diǎn)理解圖的定義、術(shù)語(yǔ)及其含義；掌握各種圖的鄰接矩陣表示法及其類型說明；理解并掌握?qǐng)D的按深度優(yōu)先搜索遍歷方法和按廣度優(yōu)先搜索遍歷方法；領(lǐng)會(huì)生成樹和最小生成樹的概念；掌握由Prim算法思想構(gòu)造最小生成樹按Prim算法思想；領(lǐng)會(huì)拓?fù)湫蛄泻屯負(fù)渑判虻母拍睿焕斫獠⒄莆胀負(fù)渑判虻乃惴ㄋ枷?；理解并掌握關(guān)鍵路徑的算法思想；理解并掌握

15、最短路徑的算法思想。教學(xué)難點(diǎn) 正確理解與區(qū)別圖的常用術(shù)語(yǔ)；區(qū)別圖的兩種存儲(chǔ)結(jié)構(gòu)的不同點(diǎn)及其應(yīng)用場(chǎng)合；關(guān)鍵路徑的算法思想；最短路徑的算法思想。練習(xí)題 7.1 7.7 7.9 7.11 第九章 查找教學(xué)內(nèi)容9.1 基本概念與術(shù)語(yǔ)9.2 靜態(tài)查找表9.3 動(dòng)態(tài)查找表9.4 哈希表查找(雜湊法) 教學(xué)目的及要求了解查找的基本思想及查找成功和不成功的概念；掌握在順序表、有序表、索引表、散列表等上的查找方法和算法，并能求出相應(yīng)的平均查找長(zhǎng)度；理解并掌握二叉排序樹、平衡二叉樹B-樹的各種算法。教學(xué)重點(diǎn)查找表的基本概念及查找原理；查找表的順序存儲(chǔ)結(jié)構(gòu)、順序表及其類型說明；查找運(yùn)算在查找表和有序表上的實(shí)現(xiàn)；二叉

16、排序樹的定義、性質(zhì)及各結(jié)點(diǎn)間的鍵值關(guān)系；二叉排序樹的查找算法和基本思想；平衡二叉排序樹的概念；B-樹和B+樹的概念；散列表及散列存儲(chǔ)和散列查找的基本思想；各種散列表的組織、解決沖突的方法；在散列表上實(shí)現(xiàn)查找、插入和刪除運(yùn)算的算法。教學(xué)難點(diǎn)理解查找表的邏輯結(jié)構(gòu)是集合，它的運(yùn)算以查找為核心；二叉排序樹上的插入算法；平衡二叉樹的旋轉(zhuǎn)平衡算法；散列表上的有關(guān)算法練習(xí)題9.2 9.8 9.11 9.19 9.22第十章 排序教學(xué)內(nèi)容10.1 基本概念10.2 插入排序10.3 交換排序10.4 選擇排序10.5 二路歸并排序10.6 基數(shù)排序10.7 外排序教學(xué)目的及要求領(lǐng)會(huì)排序的基本思想和基本概念；理

17、解并掌握插入排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序和基數(shù)排序的基本思想、步驟、算法及時(shí)空效率分析；了解外排序的定義和基本方法。教學(xué)重點(diǎn)排序基本概念及內(nèi)排序和外排序、穩(wěn)定排序和非穩(wěn)定排序的區(qū)別；插入排序的基本思想、基本步驟和算法；冒泡排序的基本思想、基本步驟、算法和算法分析；快速排序的基本思想、基本步驟和算法；直接選擇排序的基本思想、基本步驟、算法和算法分析；堆排序的基本思想、基本步驟和算法；歸并排序的思想；兩個(gè)有序文件合并的方法和算法；二路歸并排序的算法和時(shí)空性能教學(xué)難點(diǎn) 快速排序算法； 堆排序方法練習(xí)題 10.1 10.4 10.7 10.12 10.21 10.38四、大綱說明本課程的先修課程為離散數(shù)學(xué)和高級(jí)語(yǔ)言程序設(shè)計(jì)。學(xué)習(xí)本課程必須