遵義師范學(xué)院課程教學(xué)大綱《數(shù)據(jù)結(jié)構(gòu)課程》

遵義師范學(xué)院課程教學(xué)大綱

《數(shù)據(jù)結(jié)構(gòu)課程》

教學(xué)大綱

課程編號(hào)320055適用專業(yè)計(jì)算機(jī)大類

學(xué)時(shí)數(shù)64學(xué)分?jǐn)?shù)3.5

執(zhí)筆人及編寫日期楊茂強(qiáng)2017年5月

審核人及審核日期______________________________

院別信息工程學(xué)院教研室_軟件工程

編印日期2017年6月

一、課程性質(zhì)和教學(xué)目標(biāo)

1.課程授課對(duì)象：

計(jì)算機(jī)相關(guān)專業(yè)

2.課程性質(zhì)：（專業(yè)基礎(chǔ)課、專業(yè)選修課、公共選修課等）

專業(yè)必修課。

3.在人才培養(yǎng)過程中的地位及作用：

本課程是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的專業(yè)基礎(chǔ)課程之一，通過本課程的學(xué)習(xí)，使學(xué)生能夠

運(yùn)用數(shù)據(jù)結(jié)構(gòu)的思想，針對(duì)不同數(shù)據(jù)對(duì)象的特性，能夠選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)以及

相應(yīng)的算法，解決實(shí)際的問題。

4.課程教學(xué)目標(biāo)：

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)本科生的一門綜合性的專業(yè)基礎(chǔ)課。本課程主要介紹

如何合理地組織數(shù)據(jù)、有效地存儲(chǔ)和處理數(shù)據(jù)，正確地設(shè)計(jì)算法以及對(duì)算法的分析和評(píng)價(jià)。

通過本課程的學(xué)習(xí)，使學(xué)生深透地理解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的基本概念以及有關(guān)

算法，培養(yǎng)基本的、良好的程序設(shè)計(jì)技能，編制高效可靠的程序，為學(xué)習(xí)操作系統(tǒng)、編譯原

理和數(shù)據(jù)庫等課程奠定基礎(chǔ)。

二、課程教學(xué)內(nèi)容

學(xué)時(shí)分配表

講次內(nèi)容學(xué)時(shí)教學(xué)形式

第一講數(shù)據(jù)結(jié)構(gòu)與算法概述2講授、提問

第二講線性表6講授、提問、任務(wù)

第三講線性表實(shí)驗(yàn)2實(shí)驗(yàn)

第四講棧和隊(duì)列6講授、提問、討論

第五講棧和隊(duì)列實(shí)驗(yàn)2實(shí)驗(yàn)

第六講串4講授、討論、翻轉(zhuǎn)

第七講串實(shí)驗(yàn)2實(shí)驗(yàn)

第八講數(shù)組和廣義表6講授、問答、翻轉(zhuǎn)

第九講數(shù)組和廣義表實(shí)驗(yàn)2實(shí)驗(yàn)

第十講樹8講授、提問、討論

第十一講樹實(shí)驗(yàn)4實(shí)驗(yàn)

第十二講圖4講授、提問、討論

第十三講查找6講授、提問、討論

第十四講查找實(shí)驗(yàn)2實(shí)驗(yàn)

第十五講內(nèi)部排序6講授、提問、討論

第十六講綜合實(shí)驗(yàn)2實(shí)驗(yàn)

合計(jì)64

第一講緒論

1.學(xué)時(shí)：2學(xué)時(shí)

2.重難點(diǎn)：數(shù)據(jù)結(jié)構(gòu)概念與分類，抽象數(shù)據(jù)類型，算法復(fù)雜度

3.教學(xué)目標(biāo)：了解數(shù)據(jù)結(jié)構(gòu)的概念和基本術(shù)語，算法的特性及其與數(shù)據(jù)結(jié)構(gòu)的關(guān)系。理解

算法與數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)中的作用。掌握抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)。

4.教學(xué)內(nèi)容：數(shù)據(jù)結(jié)構(gòu)概念與分類，抽象數(shù)據(jù)類型，算法的概念與特性，算法復(fù)雜度

第二講線性表

1.學(xué)時(shí)：6學(xué)時(shí)

2.重難點(diǎn)：線性表的順序存儲(chǔ)原理及順序存儲(chǔ)實(shí)現(xiàn)，線性表的鏈?zhǔn)酱鎯?chǔ)原理及鏈?zhǔn)酱鎯?chǔ)實(shí)

現(xiàn)。

3.教學(xué)目標(biāo)：了解循環(huán)鏈表和雙向鏈表的操作實(shí)現(xiàn)。掌握線性表的邏輯結(jié)構(gòu)特性，順序存

儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的描述方法。

4.教學(xué)內(nèi)容：線性表的概念與性質(zhì)，線性表的順序存儲(chǔ)原理及順序存儲(chǔ)的實(shí)現(xiàn)，線性表的

鏈?zhǔn)酱鎯?chǔ)原理及鏈?zhǔn)酱鎯?chǔ)的實(shí)現(xiàn)，雙向鏈表定義與實(shí)現(xiàn)，循環(huán)鏈表定義與實(shí)現(xiàn)，約瑟夫環(huán)。

第三講線性表實(shí)驗(yàn)

1.學(xué)時(shí)：2學(xué)時(shí)

2.實(shí)驗(yàn)?zāi)康模赫莆站€性表的基本操作和應(yīng)用。

3.實(shí)驗(yàn)內(nèi)容：編寫程序，實(shí)現(xiàn)鏈表的插入、刪除、查找等操作。

第四講棧和隊(duì)列

1.學(xué)時(shí)：6學(xué)時(shí)

2.重難點(diǎn)：棧的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn)，棧的遞歸應(yīng)用，順序隊(duì)列的實(shí)現(xiàn)，鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)。

3.教學(xué)目標(biāo)：理解循環(huán)隊(duì)列的概念和實(shí)現(xiàn)方。掌握棧和隊(duì)列的特點(diǎn)，棧和隊(duì)列的邏輯結(jié)構(gòu)

和存儲(chǔ)結(jié)構(gòu)，能利用棧實(shí)現(xiàn)簡(jiǎn)單的四則運(yùn)算，棧的遞歸應(yīng)用。

4.教學(xué)內(nèi)容：棧的概念，棧的順序存儲(chǔ)和實(shí)現(xiàn)，棧的連式存儲(chǔ)和實(shí)現(xiàn)，棧的四則運(yùn)算，棧

的遞歸應(yīng)用，隊(duì)列的概念，順序隊(duì)列的實(shí)現(xiàn)，鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)，循環(huán)隊(duì)列。

第五講棧和隊(duì)列實(shí)驗(yàn)

2.學(xué)時(shí)：2學(xué)時(shí)

2.實(shí)驗(yàn)?zāi)康模菏炀氄莆諚：完?duì)列的基本使用方法。

3.實(shí)驗(yàn)內(nèi)容：編寫程序，實(shí)現(xiàn)棧的入棧和出棧等操作。

第六講串

1.學(xué)時(shí)：4學(xué)時(shí)

2.重難點(diǎn)：串的存儲(chǔ)，串的模式匹配算法。

3.教學(xué)目標(biāo)：了解串的順序/鏈?zhǔn)酱鎯?chǔ)。掌握字符串的特點(diǎn)與處理方法，串的基本運(yùn)算和實(shí)

現(xiàn)。

4.教學(xué)內(nèi)容：串的概念，串的存儲(chǔ)，串的模式匹配算法。

第七講串實(shí)驗(yàn)

3.學(xué)時(shí)：2學(xué)時(shí)

2.實(shí)驗(yàn)?zāi)康模赫莆兆址幕具\(yùn)算和實(shí)現(xiàn)。

3.實(shí)驗(yàn)內(nèi)容：編寫程序，實(shí)現(xiàn)串的模式匹配操作。

第八講數(shù)組和廣義表

1.學(xué)時(shí)：6學(xué)時(shí)

2.重難點(diǎn)：數(shù)據(jù)的邏輯結(jié)構(gòu)定義和存儲(chǔ)方式，矩陣的存儲(chǔ)結(jié)構(gòu)，廣義表的定義與存儲(chǔ)結(jié)構(gòu)，

廣義表的遞歸運(yùn)算。

3.教學(xué)目標(biāo)：理解特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)原理。掌握二維數(shù)組的邏輯結(jié)構(gòu)定義和

存儲(chǔ)方式，廣義表的定義、存儲(chǔ)結(jié)構(gòu)及相關(guān)操作。

4.教學(xué)內(nèi)容：數(shù)組的邏輯結(jié)構(gòu)定義與存儲(chǔ)方式，矩陣的數(shù)據(jù)類型定義與分類，矩陣的存儲(chǔ)

結(jié)構(gòu)，稀疏矩陣的創(chuàng)建、存儲(chǔ)及運(yùn)算，廣義表的定義，廣義表的存儲(chǔ)結(jié)構(gòu)，廣義表的遞歸運(yùn)

算。

第九講數(shù)組和廣義表實(shí)驗(yàn)

4.學(xué)時(shí)：2學(xué)時(shí)

2.實(shí)驗(yàn)?zāi)康模赫莆斩S數(shù)組的邏輯結(jié)構(gòu)定義和存儲(chǔ)方式，廣義表的定義和遞歸運(yùn)算。

3.實(shí)驗(yàn)內(nèi)容：編寫程序，實(shí)現(xiàn)稀疏矩陣的各種操作。

第十講樹

1.學(xué)時(shí)：8學(xué)時(shí)

2.重難點(diǎn)：二叉樹的分類、性質(zhì)、存儲(chǔ)結(jié)構(gòu)，二叉樹的遍歷方式，二叉樹基于遞歸的運(yùn)算

線索二叉樹。

3.教學(xué)目標(biāo)：了解霍夫曼編碼在數(shù)據(jù)壓縮中的實(shí)際意義。掌握樹的基本概念，二叉樹的分

類、性質(zhì)、存儲(chǔ)結(jié)構(gòu)和相關(guān)操作的實(shí)現(xiàn)方法，二叉樹的遍歷算法，并能使用遞歸方式實(shí)現(xiàn)樹

的遍歷，霍夫曼樹的構(gòu)造方法。

4.教學(xué)內(nèi)容：樹的基本概念，二叉樹的分類、性質(zhì)、存儲(chǔ)結(jié)構(gòu)，二叉樹的遍歷方式，二叉

樹基于遞歸的運(yùn)算，二叉樹的非遞歸遍歷，二叉樹與樹、森林之間的轉(zhuǎn)換，二叉樹的構(gòu)建

線索二叉樹，霍夫曼樹的定義與構(gòu)造，霍夫曼編碼。

第十一講樹實(shí)驗(yàn)

5.學(xué)時(shí)：4學(xué)時(shí)

2.實(shí)驗(yàn)?zāi)康模赫莆斩鏄涞膭?chuàng)建、遍歷等相關(guān)操作。

3.實(shí)驗(yàn)內(nèi)容：編寫程序，實(shí)現(xiàn)二叉樹的建立、遍歷、求深度等相關(guān)操作。

第十二講圖

1.學(xué)時(shí)：4學(xué)時(shí)

2.重難點(diǎn)：圖的深度/廣度優(yōu)先遍歷，最小生成樹的求解算法，最短路徑求解，關(guān)鍵路徑求

解。

3.教學(xué)目標(biāo)：理解的定義與基本術(shù)語。掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)，圖的深度/廣度優(yōu)先遍歷算法，

最小生成樹和最短路徑的求解步驟。

4.教學(xué)內(nèi)容：圖的定義與基本術(shù)語，圖的基本操作，圖的存儲(chǔ)結(jié)構(gòu)，圖的遍歷，最小生成

樹，最短路徑的定義與求解，拓?fù)渑判?，關(guān)鍵路徑。

第十三講查找

1.學(xué)時(shí)：6學(xué)時(shí)

2.重難點(diǎn)：順序查找算法的原理與實(shí)現(xiàn)，折半查找算法的原理與實(shí)現(xiàn)，二叉排序樹的相關(guān)

操作。

3.教學(xué)目標(biāo)：了解其它樹表的查找原理，哈希表的相關(guān)概念和原理。掌握順序查找算法的

原理與實(shí)現(xiàn)，折半查找算法的原理與實(shí)現(xiàn)，二叉排序樹的相關(guān)操作。

4.教學(xué)內(nèi)容：順序查找算法的原理與實(shí)現(xiàn)，折半查找算法的原理與實(shí)現(xiàn)，索引順序查找，

二叉排序樹的相關(guān)操作，平衡二叉樹的概念及操作，B樹的概念及操作，哈希表的相關(guān)概念

和原理。

第十四講查找實(shí)驗(yàn)

6.學(xué)時(shí)：2學(xué)時(shí)

2.實(shí)驗(yàn)?zāi)康模赫莆栈跀?shù)據(jù)結(jié)構(gòu)的多種查找方式。

3.實(shí)驗(yàn)內(nèi)容：編寫程序，實(shí)現(xiàn)順序查找和二分查找等常見的查找算法。

第十五講內(nèi)部排序

1.學(xué)時(shí)：6學(xué)時(shí)

2.重難點(diǎn)：冒泡排序，快速排序，希爾排序，堆排序，歸并排序算法的原理及實(shí)現(xiàn)

3.教學(xué)目標(biāo)：了解外部排序算法的實(shí)現(xiàn)方式。理解各種排序算法的特點(diǎn)。掌握各種排序算

法的原理及實(shí)現(xiàn)方式。

4.教學(xué)內(nèi)容：冒泡排序算法的原理及實(shí)現(xiàn)，快速排序算法的原理及實(shí)現(xiàn)，直接插入排序算

法的原理及實(shí)現(xiàn)，折半插入排序算法的原理及實(shí)現(xiàn)，希爾排序算法的原理及實(shí)現(xiàn)，簡(jiǎn)單選擇

排序算法的原理及實(shí)現(xiàn)，堆排序算法的原理及實(shí)現(xiàn)，歸并排序算法的原理及實(shí)現(xiàn)，基數(shù)排序

算法的原理及實(shí)現(xiàn)，內(nèi)部排序算法的性能比較，外部排序的存儲(chǔ)原理與結(jié)構(gòu)，外部排序算法

最佳歸并書。

第十六講綜合實(shí)驗(yàn)

7.學(xué)時(shí)：2學(xué)時(shí)

2.實(shí)驗(yàn)?zāi)康模赫莆枕?xiàng)目的分析步驟及模塊劃分和項(xiàng)目開發(fā)流程。

3.實(shí)驗(yàn)內(nèi)容：貪吃蛇

三、教學(xué)基本要求

1.備課：

獨(dú)立備課與集體備課相結(jié)合。

2.教學(xué)