數(shù)據(jù)結(jié)構(gòu) 課程大綱及學(xué)時(shí)安排 4學(xué)分

《數(shù)據(jù)結(jié)構(gòu)-C++語(yǔ)言描述》4學(xué)分課程教學(xué)大綱及學(xué)時(shí)安排

一、課程簡(jiǎn)介

課程名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)一C++語(yǔ)言描述

學(xué)時(shí)/學(xué)分：64

先修課程：C++語(yǔ)言程序設(shè)計(jì)，離散數(shù)學(xué)

面向?qū)ο螅弘婎?lèi)、信息類(lèi)專(zhuān)業(yè)、新工科本科生

教學(xué)目標(biāo)：本課程分析和討論了實(shí)際生活應(yīng)用中具有各種關(guān)系（包括集合關(guān)系、線(xiàn)性關(guān)

系、樹(shù)關(guān)系和圖關(guān)系）的數(shù)據(jù)集合的邏輯結(jié)構(gòu)、基本操作、物理結(jié)構(gòu)、基本

操作的算法實(shí)現(xiàn)和典型的應(yīng)用，目的是使學(xué)生學(xué)會(huì)分析、研究計(jì)算機(jī)所要加

工處理的數(shù)據(jù)的特征，掌握組織數(shù)據(jù)、存儲(chǔ)數(shù)據(jù)和處理數(shù)據(jù)的基本方法，培

養(yǎng)在實(shí)際應(yīng)用中選擇合適的數(shù)據(jù)結(jié)構(gòu)和設(shè)計(jì)相應(yīng)算法的能力

主要內(nèi)容：數(shù)據(jù)結(jié)構(gòu)和算法的基本概念、線(xiàn)性結(jié)構(gòu)、棧和隊(duì)列、樹(shù)形結(jié)構(gòu)、圖結(jié)構(gòu)、查

找和排序。本書(shū)對(duì)每一種結(jié)構(gòu)從存儲(chǔ)、算法、應(yīng)用等方面進(jìn)行了分析，所有

的算法都借助C++語(yǔ)言、利用面向?qū)ο蟮姆椒ㄟM(jìn)行了設(shè)計(jì)和實(shí)現(xiàn)。

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

第一章緒論

主要內(nèi)容：數(shù)據(jù)結(jié)構(gòu)基本概念，數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、基本操作、物理結(jié)構(gòu)、操作實(shí)現(xiàn)、

典型應(yīng)用。算法的定義及其基本要求，算法的時(shí)間復(fù)雜度計(jì)算，算法的空間復(fù)雜度計(jì)算。

C++語(yǔ)言實(shí)現(xiàn)（高級(jí)話(huà)題），含面向?qū)ο?、泛型機(jī)制、const機(jī)制、異常處理。

第二章線(xiàn)性表

主要內(nèi)容：線(xiàn)性表的定義及ADT,順序表及基本運(yùn)算實(shí)現(xiàn)，單鏈表及其基本運(yùn)算實(shí)現(xiàn),

單向循環(huán)鏈表、雙鏈表、雙向循環(huán)鏈表及基本操作實(shí)現(xiàn)，線(xiàn)性表典型應(yīng)用：一元多項(xiàng)式

加法、串及其基本操作、稀疏矩陣。

第三章棧和隊(duì)列

主要內(nèi)容：棧的定義及相關(guān)概念、順序棧、鏈?zhǔn)綏＜捌浠静僮鲗?shí)現(xiàn)、共享?xiàng)５母拍睢?/p>

棧的典型應(yīng)用（括號(hào)配對(duì)檢查、表達(dá)式計(jì)算）。隊(duì)列的定義及相關(guān)概念、順序隊(duì)列、順

序循環(huán)隊(duì)列、鏈?zhǔn)疥?duì)列及其基本操作的實(shí)現(xiàn)、優(yōu)先隊(duì)列。隊(duì)列的應(yīng)用-單服務(wù)窗口的模

擬。

第四章樹(shù)

主要內(nèi)容：樹(shù)的定義及相關(guān)術(shù)語(yǔ)，二叉樹(shù)的定義及性質(zhì)，二叉樹(shù)的順序、鏈?zhǔn)酱鎯?chǔ)（標(biāo)

準(zhǔn)和廣義標(biāo)準(zhǔn)存儲(chǔ)），二叉樹(shù)的標(biāo)準(zhǔn)存儲(chǔ)及其基本操作的實(shí)現(xiàn)，二叉樹(shù)遍歷的實(shí)現(xiàn)，包

括層次遍歷算法、前序、中序及后序三種遍歷的遞歸和非遞歸算法，線(xiàn)索樹(shù)的建立及遍

歷，根據(jù)遍歷序列確定二叉樹(shù)，二叉樹(shù)的應(yīng)用--包括表達(dá)式樹(shù)的建立及計(jì)算、哈夫曼樹(shù)、

哈夫曼算法及哈夫曼編碼、等價(jià)類(lèi)問(wèn)題、樹(shù)和森林及其相關(guān)運(yùn)算。

第五章圖

主要內(nèi)容：圖的基本概念和術(shù)語(yǔ)，圖的鄰接矩陣、加權(quán)鄰接矩陣的存儲(chǔ)和基本操作實(shí)現(xiàn),

圖的鄰接表存儲(chǔ)及基本操作的實(shí)現(xiàn)，鄰接多重表和十字鏈表，圖的深度優(yōu)先遍歷的遞歸

和非遞歸算法，圖的廣度優(yōu)先遍歷算法，圖遍歷的應(yīng)用（無(wú)向圖的連通性、有向圖的連

通性），生成樹(shù)和最小代價(jià)生成樹(shù)、求最小生成樹(shù)的經(jīng)典算法（prim和kruskal算法），

最短路徑問(wèn)題（包括單源最短路徑、所有頂點(diǎn)間的最短路徑及其經(jīng)典算法），AOV網(wǎng)和

AOE網(wǎng)（包括拓?fù)渑判颉㈥P(guān)鍵路徑及其算法）。

第六章查找

主要內(nèi)容：靜態(tài)查找的概念，靜態(tài)查找表的存儲(chǔ)，順序查找、折半查找、插值查找、分

塊查找的實(shí)現(xiàn)。動(dòng)態(tài)查找和二叉查找樹(shù)的概念，二叉查找樹(shù)的查找、插入、刪除的遞歸

和非遞歸算法，找第i小元素的順序統(tǒng)計(jì)，二叉平衡查找樹(shù)（AVL樹(shù)）的定義、AVL

樹(shù)的插入、刪除及其調(diào)整方法，AVL樹(shù)的最大高度，紅黑樹(shù)的定義、紅黑樹(shù)的插入、

刪除及其調(diào)整方法，B樹(shù)和B+樹(shù)的概念，B及B+樹(shù)的插入、刪除及相關(guān)計(jì)算。哈希方

法及其相關(guān)概念、常見(jiàn)的哈希函數(shù)、哈希沖突解決方法，哈希方法的基本操作實(shí)現(xiàn)。

第七章排序

主要內(nèi)容：內(nèi)排序及相關(guān)概念，冒泡排序、簡(jiǎn)單插入排序、希爾排序、歸并排序、快速

排序、選擇排序、堆排序及優(yōu)先隊(duì)列、基數(shù)排序算法，各種排序算法的效率和穩(wěn)定性。

外部排序過(guò)程，歸并排序，K路歸并，初始?xì)w并段，最佳歸并樹(shù)。

三、教學(xué)進(jìn)度安排：

4學(xué)分共計(jì)64課時(shí)

第一章緒論（5學(xué)時(shí)）

1.1數(shù)據(jù)結(jié)構(gòu)定義（1學(xué)時(shí)）

1.1.1數(shù)據(jù)的邏輯結(jié)構(gòu)

1.1.2數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

1.1.3基本操作的實(shí)現(xiàn)

1.1.4典型應(yīng)用

1.2算法及算法分析（2學(xué)時(shí)）

1.2.1算法及其要求

1.2.2時(shí)間復(fù)雜性的度量

1.2.3空間復(fù)雜性的度量

1.3數(shù)據(jù)結(jié)構(gòu)的C++語(yǔ)言實(shí)現(xiàn)（2學(xué)時(shí)）

1.3.1面向?qū)ο?/p>

1.3.2泛型機(jī)制

1.3.3const機(jī)制

1.3.4異常處理

1.4小結(jié)

1.5習(xí)題

第二章線(xiàn)性表（8學(xué)時(shí)）

2.1線(xiàn)性表的定義及ADT（1學(xué)時(shí)）

2.2線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)（2學(xué)時(shí)）

2.2.1順序表

2.2.2順序表基本操作的實(shí)現(xiàn)

2.3線(xiàn)性表的鏈接存儲(chǔ)結(jié)構(gòu)（3學(xué)時(shí)）

2.3.1單鏈表

2.3.2單鏈表基本操作的實(shí)現(xiàn)

2.3.3單向循環(huán)鏈表

2.3.4雙鏈表、雙向循環(huán)鏈表

2.4線(xiàn)性表的應(yīng)用（2學(xué)時(shí)）

2.4.1一元多項(xiàng)式的加法

2.4.2字符串的存儲(chǔ)和實(shí)現(xiàn)

2.4.3稀疏矩陣

2.5小結(jié)

2.6習(xí)題

第三章棧和隊(duì)列（6學(xué)時(shí)）

3.1棧（2學(xué)時(shí)）

3.1.1棧的定義

3.1.2棧的順序存儲(chǔ)及實(shí)現(xiàn)

3.1.3棧的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn)

3.2棧的應(yīng)用（2學(xué)時(shí)）

3.2.1括號(hào)配對(duì)檢查

3.2.2表達(dá)式計(jì)算

3.3隊(duì)列（1學(xué)時(shí)）

3.3.1隊(duì)列的定義及ADT

3.3.2隊(duì)列的順序存儲(chǔ)及實(shí)現(xiàn)

3.3.3隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn)

3.3.4優(yōu)先隊(duì)列

3.4隊(duì)列的應(yīng)用（1學(xué)時(shí)）

3.5小結(jié)

3.6習(xí)題

第四章樹(shù)及二叉樹(shù)（14學(xué)時(shí)）

4.1樹(shù)的定義、術(shù)語(yǔ)及結(jié)構(gòu)（1學(xué)時(shí)）

4.2二叉樹(shù)（2學(xué)時(shí)）

4.2.1二叉樹(shù)的定義

4.2.2二叉樹(shù)的性質(zhì)

4.2.3二叉樹(shù)的存儲(chǔ)和實(shí)現(xiàn)

4.3二叉樹(shù)的遍歷（4學(xué)時(shí)）

4.3.1二叉樹(shù)的遍歷及實(shí)現(xiàn)

4.3.2二叉線(xiàn)索樹(shù)

4.3.3遍歷序列確定二叉樹(shù)

4.4表達(dá)式樹(shù)（2學(xué)時(shí)）

4.4.1基本概念

4.4.2表達(dá)式樹(shù)的建立

4.4.3表達(dá)式的計(jì)算

4.5最優(yōu)二叉樹(shù)及其應(yīng)用（2學(xué)時(shí)）

4.5.1.基本概念

4.5.2哈夫曼算法的實(shí)現(xiàn)

4.5.3哈夫曼編碼

4.6等價(jià)類(lèi)問(wèn)題（1學(xué)時(shí)）

4.6.1.等價(jià)關(guān)系及等價(jià)類(lèi)

4.6.2不相交集及其存儲(chǔ)

4.6.3不相交集的基本操作

4.7樹(shù)和森林（2學(xué)時(shí)）

4.7.1孩子兄弟表示法

4.7.2樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換

4.7.3樹(shù)和森林的遍歷

4.8小結(jié)

4.9習(xí)題

第五章圖（13學(xué)時(shí)）

5.1圖的基本概念（1學(xué)時(shí)）

5.1.1圖的概念及術(shù)語(yǔ)

5.1.2圖的抽象數(shù)據(jù)類(lèi)型

5.2圖的存儲(chǔ)表示（4學(xué)時(shí)）

5.2.1鄰接矩陣和加權(quán)鄰接矩陣

5.2.2鄰接表

5.2.3鄰接多重表

5.2.4十字鏈表

5.3圖的遍歷和連通性（2學(xué)時(shí)）

5.3.1深度優(yōu)先遍歷

5.3.2廣度優(yōu)先遍歷

5.3.3圖的連通性

5.4最小代價(jià)生成樹(shù)（2學(xué)時(shí)）

5.4.1普里姆（Prim）算法

5.4.2克魯斯卡爾（KruscaI）算法

5.5最短路徑問(wèn)題（2學(xué)時(shí)）

5.5.1單源最短路徑

5.5.2所有頂點(diǎn)對(duì)之間的最短路徑

5.6AOV網(wǎng)和AOE網(wǎng)（2學(xué)時(shí)）

5.6.1拓?fù)渑判?/p>

5.6.2關(guān)鍵路徑

5.7小結(jié)

5.8習(xí)題

第六章查找（12學(xué)時(shí)）

6.1靜態(tài)查找技術(shù)（1學(xué)時(shí)）

6.1.1順序查找

6.1.2折半查找

6.1.3插值查找

6.1.4分塊查找

6.2二叉查找樹(shù)（2學(xué)時(shí)）

6.2.1二叉查找樹(shù)的定義

6.2.2基本操作實(shí)現(xiàn)

6.2.3順序統(tǒng)計(jì)

6.3平衡二叉查找樹(shù)（AVL樹(shù)）（3學(xué)時(shí)）

6.3.1插入操作

6.3.2刪除操作

6.3.3最大高度

6.4紅黑樹(shù)（2學(xué)時(shí)）

6.4.1插入操作

6.4.2刪除操作

6.5B樹(shù)和B+樹(shù)（2學(xué)時(shí)）

6.5.1B樹(shù)

6.5.2B樹(shù)的查找分析

6.5.3B樹(shù)的插入

6.5.4B樹(shù)的刪除

6.5.5B+樹(shù)

6.6哈希（Hash）方法（2學(xué)時(shí)）

6.6.1常用的哈希函數(shù)

6.6.2線(xiàn)性探測(cè)法

6.6.3二次探測(cè)法

6.6.4鏈地址法

6.7小結(jié)

6.8習(xí)題

第七章排序（6學(xué)時(shí)）

7.1引言（7.1-7.32學(xué)時(shí)）

7.2冒泡排序

7.3插入排序

7.3.1簡(jiǎn)單插入排序

7.3.2折半插入排序

7.3.