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

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

教學(xué)大綱

課程編號320055適用專業(yè)計算機大類

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

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

審核人及審核日期______________________________

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

編印日期2017年6月

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

1.課程授課對象：

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

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

專業(yè)必修課。

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

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

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

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

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

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

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

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

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

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

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

學(xué)時分配表

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

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

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

第三講線性表實驗2實驗

第四講棧和隊列6講授、提問、討論

第五講棧和隊列實驗2實驗

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

第七講串實驗2實驗

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

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

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

第十一講樹實驗4實驗

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

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

第十四講查找實驗2實驗

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

第十六講綜合實驗2實驗

合計64

第一講緒論

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

2.重難點：數(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è)計中的作用。掌握抽象數(shù)據(jù)類型的表示與實現(xiàn)。

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

第二講線性表

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

2.重難點：線性表的順序存儲原理及順序存儲實現(xiàn)，線性表的鏈?zhǔn)酱鎯υ砑版準(zhǔn)酱鎯?/p>

現(xiàn)。

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

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

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

鏈?zhǔn)酱鎯υ砑版準(zhǔn)酱鎯Φ膶崿F(xiàn)，雙向鏈表定義與實現(xiàn)，循環(huán)鏈表定義與實現(xiàn)，約瑟夫環(huán)。

第三講線性表實驗

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

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

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

第四講棧和隊列

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

2.重難點：棧的鏈?zhǔn)酱鎯皩崿F(xiàn)，棧的遞歸應(yīng)用，順序隊列的實現(xiàn)，鏈?zhǔn)疥犃械膶崿F(xiàn)。

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

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

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

的遞歸應(yīng)用，隊列的概念，順序隊列的實現(xiàn)，鏈?zhǔn)疥犃械膶崿F(xiàn)，循環(huán)隊列。

第五講棧和隊列實驗

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

2.實驗?zāi)康模菏炀氄莆諚：完犃械幕臼褂梅椒ā?/p>

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

第六講串

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

2.重難點：串的存儲，串的模式匹配算法。

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

現(xiàn)。

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

第七講串實驗

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

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

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

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

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

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

廣義表的遞歸運算。

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

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

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

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

算。

第九講數(shù)組和廣義表實驗

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

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

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

第十講樹

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

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

線索二叉樹。

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

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

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

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

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

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

第十一講樹實驗

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

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

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

第十二講圖

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

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

解。

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

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

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

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

第十三講查找

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

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

操作。

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

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

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

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

和原理。

第十四講查找實驗

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

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

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

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

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

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

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

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

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

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

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

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

最佳歸并書。

第十六講綜合實驗

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

2.實驗?zāi)康模赫莆枕椖康姆治霾襟E及模塊劃分和項目開發(fā)流程。

3.實驗內(nèi)容：貪吃蛇

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

1.備課：

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

2.教學(xué)