《數據結構-C++語言描述》4學分課程教學大綱及學時安排

一、課程簡介

課程名稱：數據結構一C++語言描述

學時/學分：64

先修課程：C++語言程序設計，離散數學

面向對象：電類、信息類專業、新工科本科生

教學目標：本課程分析和討論了實際生活應用中具有各種關系（包括集合關系、線性關

系、樹關系和圖關系）的數據集合的邏輯結構、基本操作、物理結構、基本

操作的算法實現和典型的應用，目的是使學生學會分析、研究計算機所要加

工處理的數據的特征，掌握組織數據、存儲數據和處理數據的基本方法，培

養在實際應用中選擇合適的數據結構和設計相應算法的能力

主要內容：數據結構和算法的基本概念、線性結構、棧和隊列、樹形結構、圖結構、查

找和排序。本書對每一種結構從存儲、算法、應用等方面進行了分析，所有

的算法都借助C++語言、利用面向對象的方法進行了設計和實現。

二、教學內容

第一章緒論

主要內容：數據結構基本概念，數據結構的邏輯結構、基本操作、物理結構、操作實現、

典型應用。算法的定義及其基本要求，算法的時間復雜度計算，算法的空間復雜度計算。

C++語言實現（高級話題），含面向對象、泛型機制、const機制、異常處理。

第二章線性表

主要內容：線性表的定義及ADT,順序表及基本運算實現，單鏈表及其基本運算實現,

單向循環鏈表、雙鏈表、雙向循環鏈表及基本操作實現，線性表典型應用：一元多項式

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

第三章棧和隊列

主要內容：棧的定義及相關概念、順序棧、鏈式棧及其基本操作實現、共享棧的概念、

棧的典型應用（括號配對檢查、表達式計算）。隊列的定義及相關概念、順序隊列、順

序循環隊列、鏈式隊列及其基本操作的實現、優先隊列。隊列的應用-單服務窗口的模

擬。

第四章樹

主要內容：樹的定義及相關術語，二叉樹的定義及性質，二叉樹的順序、鏈式存儲（標

準和廣義標準存儲），二叉樹的標準存儲及其基本操作的實現，二叉樹遍歷的實現，包

括層次遍歷算法、前序、中序及后序三種遍歷的遞歸和非遞歸算法，線索樹的建立及遍

歷，根據遍歷序列確定二叉樹，二叉樹的應用--包括表達式樹的建立及計算、哈夫曼樹、

哈夫曼算法及哈夫曼編碼、等價類問題、樹和森林及其相關運算。

第五章圖

主要內容：圖的基本概念和術語，圖的鄰接矩陣、加權鄰接矩陣的存儲和基本操作實現,

圖的鄰接表存儲及基本操作的實現，鄰接多重表和十字鏈表，圖的深度優先遍歷的遞歸

和非遞歸算法，圖的廣度優先遍歷算法，圖遍歷的應用（無向圖的連通性、有向圖的連

通性），生成樹和最小代價生成樹、求最小生成樹的經典算法（prim和kruskal算法），

最短路徑問題（包括單源最短路徑、所有頂點間的最短路徑及其經典算法），AOV網和

AOE網（包括拓撲排序、關鍵路徑及其算法）。

第六章查找

主要內容：靜態查找的概念，靜態查找表的存儲，順序查找、折半查找、插值查找、分

塊查找的實現。動態查找和二叉查找樹的概念，二叉查找樹的查找、插入、刪除的遞歸

和非遞歸算法，找第i小元素的順序統計，二叉平衡查找樹（AVL樹）的定義、AVL

樹的插入、刪除及其調整方法，AVL樹的最大高度，紅黑樹的定義、紅黑樹的插入、

刪除及其調整方法，B樹和B+樹的概念，B及B+樹的插入、刪除及相關計算。哈希方

法及其相關概念、常見的哈希函數、哈希沖突解決方法，哈希方法的基本操作實現。

第七章排序

主要內容：內排序及相關概念，冒泡排序、簡單插入排序、希爾排序、歸并排序、快速

排序、選擇排序、堆排序及優先隊列、基數排序算法，各種排序算法的效率和穩定性。

外部排序過程，歸并排序，K路歸并，初始歸并段，最佳歸并樹。

三、教學進度安排：

4學分共計64課時

第一章緒論（5學時）

1.1數據結構定義（1學時）

1.1.1數據的邏輯結構

1.1.2數據的存儲結構

1.1.3基本操作的實現

1.1.4典型應用

1.2算法及算法分析（2學時）

1.2.1算法及其要求

1.2.2時間復雜性的度量

1.2.3空間復雜性的度量

1.3數據結構的C++語言實現（2學時）

1.3.1面向對象

1.3.2泛型機制

1.3.3const機制

1.3.4異常處理

1.4小結

1.5習題

第二章線性表（8學時）

2.1線性表的定義及ADT（1學時）

2.2線性表的順序存儲結構（2學時）

2.2.1順序表

2.2.2順序表基本操作的實現

2.3線性表的鏈接存儲結構（3學時）

2.3.1單鏈表

2.3.2單鏈表基本操作的實現

2.3.3單向循環鏈表

2.3.4雙鏈表、雙向循環鏈表

2.4線性表的應用（2學時）

2.4.1一元多項式的加法

2.4.2字符串的存儲和實現

2.4.3稀疏矩陣

2.5小結

2.6習題

第三章棧和隊列（6學時）

3.1棧（2學時）

3.1.1棧的定義

3.1.2棧的順序存儲及實現

3.1.3棧的鏈式存儲及實現

3.2棧的應用（2學時）

3.2.1括號配對檢查

3.2.2表達式計算

3.3隊列（1學時）

3.3.1隊列的定義及ADT

3.3.2隊列的順序存儲及實現

3.3.3隊列的鏈式存儲及實現

3.3.4優先隊列

3.4隊列的應用（1學時）

3.5小結

3.6習題

第四章樹及二叉樹（14學時）

4.1樹的定義、術語及結構（1學時）

4.2二叉樹（2學時）

4.2.1二叉樹的定義

4.2.2二叉樹的性質

4.2.3二叉樹的存儲和實現

4.3二叉樹的遍歷（4學時）

4.3.1二叉樹的遍歷及實現

4.3.2二叉線索樹

4.3.3遍歷序列確定二叉樹

4.4表達式樹（2學時）

4.4.1基本概念

4.4.2表達式樹的建立

4.4.3表達式的計算

4.5最優二叉樹及其應用（2學時）

4.5.1.基本概念

4.5.2哈夫曼算法的實現

4.5.3哈夫曼編碼

4.6等價類問題（1學時）

4.6.1.等價關系及等價類

4.6.2不相交集及其存儲

4.6.3不相交集的基本操作

4.7樹和森林（2學時）

4.7.1孩子兄弟表示法

4.7.2樹、森林與二叉樹的轉換

4.7.3樹和森林的遍歷

4.8小結

4.9習題

第五章圖（13學時）

5.1圖的基本概念（1學時）

5.1.1圖的概念及術語

5.1.2圖的抽象數據類型

5.2圖的存儲表示（4學時）

5.2.1鄰接矩陣和加權鄰接矩陣

5.2.2鄰接表

5.2.3鄰接多重表

5.2.4十字鏈表

5.3圖的遍歷和連通性（2學時）

5.3.1深度優先遍歷

5.3.2廣度優先遍歷

5.3.3圖的連通性

5.4最小代價生成樹（2學時）

5.4.1普里姆（Prim）算法

5.4.2克魯斯卡爾（KruscaI）算法

5.5最短路徑問題（2學時）

5.5.1單源最短路徑

5.5.2所有頂點對之間的最短路徑

5.6AOV網和AOE網（2學時）

5.6.1拓撲排序

5.6.2關鍵路徑

5.7小結

5.8習題

第六章查找（12學時）

6.1靜態查找技術（1學時）

6.1.1順序查找

6.1.2折半查找

6.1.3插值查找

6.1.4分塊查找

6.2二叉查找樹（2學時）

6.2.1二叉查找樹的定義

6.2.2基本操作實現

6.2.3順序統計

6.3平衡二叉查找樹（AVL樹）（3學時）

6.3.1插入操作

6.3.2刪除操作

6.3.3最大高度

6.4紅黑樹（2學時）

6.4.1插入操作

6.4.2刪除操作

6.5B樹和B+樹（2學時）

6.5.1B樹

6.5.2B樹的查找分析

6.5.3B樹的插入

6.5.4B樹的刪除

6.5.5B+樹

6.6哈希（Hash）方法（2學時）

6.6.1常用的哈希函數

6.6.2線性探測法

6.6.3二次探測法

6.6.4鏈地址法

6.7小結

6.8習題

第七章排序（6學時）

7.1引言（7.1-7.32學時）

7.2冒泡排序

7.3插入排序

7.3.1簡單插入排序

7.3.2折半插入排序

7.3.