数据结构 课程大纲及学时安排 4学分

《数据结构-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.