《数据结构》刘大有教学大纲

《数据结构》教学大纲

一、 教学性质、目的与任务

《数据结构》是计算机学科的主干基础课，主要介绍基本的数据结构、典型算法及其应用。对计算机学科而言，《数据结构》是进一步学习和开展高层次研究的必修课。国际著名计算机科学家、图灵奖获得者D.E.Knuth教授指出：“程序就是用计算机所能接受的语言编写的算法，对于计算机程序设计而言，算法是最基本的”。数据结构与算法有着不可分割的关系，是计算机算法和计算机程序设计的理论基础。因此，《数据结构》课程在计算机科学中占有十分重要的地位。

《数据结构》课程的教学目标是使学生理解数据结构的基本概念、计算机内部数据对象的表示和特性，掌握数据的逻辑结构、存储结构及其差异，以及各种操作的实现，能够针对实际问题选择合适的数据结构和方法设计出结构清晰、正确易读、复杂性较优的算法，同时掌握对算法进行时间、空间复杂性分析的基本技能。

《数据结构》课程的主要任务是教授学生数据结构和算法的基本理论和方法，算法分析的基本方法，数据结构在计算机科学中的基本应用，为《程序设计》、《编译原理》、《操作系统》和《数据库》等课程的学习以及计算机软件的研发奠定理论基础和培养实践能力。同时，《数据结构》课程的学习过程也是复杂问题求解和规范化程序设计的训练过程，注重培养学生的问题分析、数据抽象和算法设计能力，同时训练学生按照软件工程规范编写程序的素养。

二、教学基本要求

1、了解数据结构及其分类、数据结构与算法的密切关系。

2、系统掌握线性表、树和图等基本数据结构的定义、性质和特点。

3、熟练掌握各种基本数据结构的存储结构、逻辑结构及相关算法，能够根据实际问题选择合适的数据结构。

4、掌握各种数据结构在排序和查找等常用算法中的应用。

5、掌握算法时空复杂性分析的基本技巧。

6、了解数据结构课程中各知识点的来龙去脉及相互关系。

7、注重培养学生利用算法语言和面向对象程序设计语言设计算法和编写程序的技巧与能力。

8、注重培养学生的创新能力，采用理论与实践相结合的方法，利用启发式教学方式，提高学生分析问题和解决问题的能力，使学生完成本门课程的学习任务之后，能够综合运用多种数据结构解决实际问题。

三、各章节内容及学时分配

整个课程内容可分为十一章，具体章节如下。

第一章 绪论 （理论教学4学时）

知识点：数据结构的的逻辑结构、存储结构及数据运算的含义及相互关系；算法时间和空间

复杂度分析；算法描述语言；复杂性函数渐进表示。

重点： 数据结构的的逻辑结构、存储结构及数据运算；算法时间和空间复杂度分析。

1.1 为什么要学习数据结构 （1.1与1.2共2学时）

1.2 数据结构概念

1.2.1 数据的逻辑结构

1.2.2 数据的存储结构

1.2.3 对数据结构的操作

1.2.4 数据结构示例

1.3 算法 （1.3至1.5共2学时）

1.3.1 算法及其特性

1.3.2 算法的描述

1.3.3 算法的评价准则

1.4 算法的正确性证明

1.5 算法分析基础

1.5 .1 算法时间复杂性的分析方法

1.5 .2 复杂性函数的渐进表示

1.5 .3 算法时间与空间分析

1.5.4 计算复杂性和算法的效率

第二章 线性表、堆栈、队列 （理论教学10学时，实验教学8学时）

知识点：线性表的定义；线性表的顺序和链接存储结构；单链表；循环链表；双向链表；堆栈的定义及应用、顺序栈、链式栈；队列的定义及应用、顺序队列、链式队列。

重点： 单链表；堆栈和队列的定义及其应用。

2.1 线性表的定义和基本操作（2.1与2.2共2学时）

2.2 线性表的顺序存储结构

2.3 线性表的链接存储结构 （2.3与2.4共3学时）

2.3.1 单链表

2.3.2 循环链表

2.3.3 双向链表

2.4 复杂性分析

2.5 堆栈 （3学时）

2.5.1 堆栈的定义和主要操作

2.5.2 顺序栈

2.5.3 链式栈

2.5.4 顺序栈与链式栈的比较

2.5.5 堆栈应用——括号匹配

2.6 队列 （2学时）

2.6.1 队列的定义和主要操作

2.6.2 顺序队列

2.6.3 链式队列

2.6.4 顺序队列与链式队列的比较

2.6.5 队列与堆栈的扩展

第三章 数组和字符串 （理论教学5学时）

知识点：高维数组的存储和寻址方式；特殊矩阵的压缩存储方式；稀疏矩阵的压缩存储表示及操作算法。

重点：稀疏矩阵的压缩存储表示及算法。

3.1 数组（2学时）

3.1.1 数组的存储和寻址

3.1.2 一维数组类

3.2 矩阵（2学时）

3.2.1 矩阵类

3.2.2 特殊矩阵

3.2.3 三元组表

3.2.4 十字链表

3.3 字符串（1学时）

3.3.1字符串的定义与字符串类

3.3.2 模式匹配算法

第四章 树 （理论教学14学时，实验教学8学时）

知识点：树的定义；二叉树定义和主要性质；二叉树链接存储及操作；线索二叉树定义、存储和基本算法；树与二叉树的转换、树的存储；树与森林的遍历；哈夫曼树。

重点：二叉树定义和主要性质；二叉树链接存储及操作；树与森林的遍历；哈夫曼树。

4.1 树的基本概念（1学时）

4.1.1 树的定义

4.1.2 树的相关术语

4.2 二叉树 （3学时）

4.2.1 二叉树定义和主要性质

4.2.2 二叉树顺序存储

4.2.3 二叉树链接存储

4.2.4 二叉树遍历

4.2.5 创建二叉树

4.2.6 复制建二叉树

4.3 线索二叉树（2学时）

4.3.1 线索二叉树定义

4.3.2 线索二叉树存储

4.3.3 线索二叉树基本算法

4.4 树和森林（4学时）

4.4.1 树与二叉树的转换

4.4.2 树的顺序存储

4.4.3 树的链接存储

4.4.4 树和森林的遍历

4.5 压缩与哈夫曼树（2学时）

4.5.1 文件编码

4.5.2 扩充二叉树

4.5.3 哈夫曼树和哈夫曼编码

4.6 树的应用（2学时）

4.6.1 表达式求值

4.6.2 分类与决策树

第五章 图 （理论教学13学时，实验教学8学时）

知识点：图的基本概念；图的邻接矩阵和邻接表存储；图的深度优先和广度优先遍历；拓扑

排序；关键路径；最短路径；普里姆算法和克鲁斯卡尔算法。

重点：图的邻接矩阵和邻接表存储；图的深度优先和广度优先遍历；最短路径问题。

5.1 图的基本概念（5.1与5.2共1学时）

5.2 图的存储结构与类定义

5.2.1 存储结构

5.2.2 Graph类

5.3 图的遍历算法（2学时）

5.3.1 深度优先遍历

5.3.2 广度优先遍历

5.4 拓扑排序（2学时）

5.5 关键路径（2学时）

5.6 最短路径问题（2学时）

5.6.1 无权最短路径问题

5.6.2 正权最短路径问题

5.6.3 每对顶点之间的最短路径

5.7 最小支撑树（2学时）

5.7.1 普里姆算法

5.7.2 克鲁斯卡尔算法

5.8 图的应用（2学时）

5.8.1 可及性与Warshall算法

5.8.2 连通分量

5.8.3 图在网络分析和信息检索中的应用

第六章 递归 （理论教学4学时）

知识点：递归的定义和基本过程；递归与堆栈关系；递归效率分析。

重点：递归基本过程；递归与堆栈关系。

6.1递归的定义 （6.1与6.2 共2学时）

6.2 基本递归过程

6.3 递归过程实现与堆栈（6.3至6.5 共2学时）

6.4 递归法求解问题

6.4.1 委员会问题

6.4.2 回溯

6.5 递归的效率

第七章 排序 （理论教学10学时，实验教学8学时）

知识点：直接插入排序；Shell排序；冒泡排序；快速排序；直接选择排序；堆排序；合并排序；基于关键词比较的排序算法分析；基数分布；值分布。

重点：Shell排序；快速排序；堆排序；合并排序。

7.1 排序的基本概念（7.1 和7.2 共2学时）

7.2 插入排序

7.2.1 直接插入排序

7.2.2 Shell排序

7.3 交换排序（2学时）

7.3.1 冒泡排序

7.3.2 快速排序

7.4 选择排序（2学时）

7.4.1 直接选择排序

7.4.2 堆排序

7.5 合并排序（1学时）

7.6 基于关键词比较的排序算法分析（1学时）

7.6.1 平方阶排序算法及改进算法

7.6.2 线性对数阶排序算法

7.6.3 分治排序的一般方法

7.6.4 基于关键词比较的排序算法下界

7.7 分布排序（1学时）

7.7.1 基数分布

7.7.2 值分布

7.8 外排序（1学时）

7.8.1 外存储器

7.8.2 磁带排序

7.8.3 磁盘排序

第八章 查找 （理论教学12学时，实验教学4学时）

知识点：有序表顺序查找；对半查找；斐波那契查找；二叉查找树概念和性质；二叉查找树的查找、插入和删除算法；最优二叉查找树；高度平衡树；B树及B+树；散列函数及冲突调解。

重点：有序表顺序查找；对半查找；二叉查找树概念和性质；二叉查找树的查找、插入和删除算法；散列函数及冲突调解。

8.1 顺序查找（1学时）

8.1.1 无序表的顺序查找

8.1.2 有序表的顺序查找

8.2 基于关键词比较的查找（2学时）

8.2.1 对半查找

8.2.2 一致对半查找

8.2.3 斐波那契查找

8.2.4 插值查找

8.3 二叉查找树（2学时）

8.3.1 基本概念和性质

8.3.2 查找、插入和删除

8.3.3 平均情况时间分析

8.4 最优二叉查找树（1学时）

8.4.1 访问频率

8.4.2 最优二叉查找树

8.4.3 近似最优树的构造

8.5平衡树（1学时）

8.5.1 高度平衡树

8.5.2 重量平衡树

8.6 红黑树 （1学时）

8.6.1 红黑树的性质

8.6.2 旋转

8.6.3 插入

8.6.4 删除

8.7 B树及其变形树（1学时）

8.7.1 多叉树

8.7.2 B树

8.7.3 B树变形树

8.8 数字查找（1学时）

8.9 散列（2学时）

8.9.1 散列函数

8.9.2 冲突调解

8.9.3 删除

8.9.4 重量平衡树的应用——按位置查找

由于课时所限，“内存管理”、“文件”和“随机数”作为选讲内容。

第九章 内存管理 （理论教学4学时）

9.1 概 述 （9.1和9.2 共2学时）

9.2 均匀大小记录的分配和回收算法

9.2.1 记录分配算法

9.2.2 访问计数器法

路过

雷人

握手

鲜花

鸡蛋