数据结构教学大纲--医用信息本科.doc

《数据结构》教学大纲

前言
《数据结构》这门课程是计算机专业的必修课程。我院医学信息管理专业开设了这门课程，作为计算机核心课程之一。本科设置学时为72学时。
《数据结构》是计算机科学的算法理论基础，也是软件设计的技术基础，主要研究信息的逻辑结构及其基本操作在计算机中的表示和实现。是介于软件、硬件和数学三门学科之间的交叉学科，是计算机专业的核心课程，也是基础课程，所以面向我院信息医学专业开设了这门课程。通过学习，使学生掌握各种数据在计算机中的存储、传递和转换，能用简洁适用的数据结构来表示程序中的数据和变量。找出合适的算法来设计程序的流程，更好的去解决问题；训练学生程序设计技能并培养其良好的程序设计思想和风格。
本课程是理论性与实践性并重的课程，每节内容除适当的思考习题外，还应多多上机练习。
使用教材：黄国瑜 叶乃菁编，《数据结构》（C语言版），清华大学出版社
教学所使用的主要参考书：严蔚敏等编，《数据结构》（C 语言版），清华大学出版社

第一章 数据结构的基本概念
目的：掌握数据结构的相关概念、分类形式；掌握算法的构成、特点与效率评判；
了解程序的设计风格与结构化程序设计；掌握程序分析的两种口径，尤其是时间复杂度的概念、分类等级、表述形式及计算方式
学时：6学时
教学内容：
1、什么是数据结构
数据结构及其相关概念
数据结构的分类
2、算法
什么是算法
算法设计的要求
描述算法的方式
算法的效率分析
3、程序结构化与设计风格
软件设计的步骤
软件设计的方法
良好的程序编写风格
4、程序分析的方法
时间分析法与空间分析法
两种口径的应用
5、时间复杂度的分析
何谓时间复杂度：不同教材的观点阐述
理想状态的时间复杂度
渐进的时间复杂度
6、时间复杂度的等级
不同阶的时间复杂度
一些典型算法可达到的时间复杂度举例
7、时间复杂度的渐进式表示法
8、时间复杂度的计算
9、总结与练习

第二章 数组
目的：掌握数组的概念、表示法与存储特性；掌握一维数组的存储、使用、相关操作与算法实现；掌握一维数组的高级应用及算法实现；掌握二维数组的表示方法、存储方式；掌握几种特殊类型二维数组的存储方式及算法实现；了解广义表的概念、结构特性与存储方式。
学时：4学时
教学内容：
1、什么是数组
数组的表示方法；数组的存储特性
2、 一维数组的使用
一维数组的声明及其元素的表示方法
一维数组元素对应的内存位置
一维数组的基本操作（建立、查找、修改、插入、删除、输出、转置）、算法实现
3、 一维数组的高级使用
运用一维数组存储数据，以弥补C语言一些数据类型存储范围的限制
算法解决实际问题
4、二维数组
二维数组的表示方法
二维数组的存储方式
算法实现二维数组转换为一维数组
5、特殊类型的数组
稀疏数组及其存储表示
算法实现稀疏数组的压缩
上三角（下三角）数组及其存储表示
算法实现上三角（下三角）数组转换为一维数组
6、线性问题的数组解决
7、广义表的概念与结构特性、存储特性

第三章 链表
目的：掌握线性表的存储特性、单链表的特性、单链表的建立、相关操作及算法的实现；掌握单链表的三项基础操作、常用操作；掌握常见线性问题的链式存储及链式描述的算法实现；了解链式存储算法实现的时间复杂度。
学时：4学时
教学内容：
1、 线性表的存储特性概述
顺序存储结构
链式存储结构
2、什么是链表
链表的存储特性
与数组存储的比较
单链表的特性（节点映像）
3、链表的使用
单链表节点的声明及单链表的表示
单链表的基本操作特性
节点的配置、节点的删除、节点的释放
单链表的建立、单链表的节点输出、单链表的释放
4、单链表的三项基础操作：定位（查找）、插入和删除
单链表的定位操作、算法实现、时间复杂度分析
5、单链表的三项基本操作：
定位（节点的查找）、节点的插入、节点的删除
三项操作的时间复杂度问题
6、单链表的常用操作：
链表的反转、链表的链接、链表的比较
单链表常用操作的算法实现
7、线性问题的链表解决
8、总结与启发
根据逻辑图的指针设置和变换掌握相应子函数的设计思想
根据运行结果判断主函数的脉络

第四章 堆栈
目的：掌握堆栈的概念、特性；了解堆栈的应用；掌握堆栈的两种存储特性及算法实现、效率分析；掌握堆栈的典型应用---程序设计中表达式求值问题；掌握程序设计中表达式相互转换的规则、堆栈的使用；掌握表达式转换的设计思想及算法实现。
学时：6学时
教学内容：
1、何谓堆栈
堆栈的特性
堆栈的常见应用举例
2、堆栈的基本运算
3、堆栈的两种存储结构及实现
1） 数组仿真堆栈---堆栈数组
堆栈数组的声明及变量的使用
堆栈数组的基本操作（判断栈空、判断栈满、压栈、出栈、取栈顶值），算法实现
2）链表仿真堆栈---链栈
堆栈链表结构的声明及变量的使用
如何确定链表头尾与栈底、栈顶的对应关系
链栈的基本操作（判断栈空、判断栈满、压栈、出栈、取栈顶值）
常用链栈操作的算法实现
4、利用堆栈解决实际问题----堆栈的典型应用之一
1）表达式的形式与特性
中序表达式：算符优先法、表达式的形式
算符优先规则
前序与后序表达式：无符号表达式、形式与意义
2）表达式求值、算法实现
中序表达式的计算步骤、运算形式、算法实现
前序表达式的计算步骤、运算形式、算法实现
后序表达式的计算步骤、运算形式、算法实现
三种算法的比较与实际应用概述
5、利用堆栈解决实际问题------表达式的转换
1）前序、后序表达式转换为中序的规则（包括堆栈设置）、运算形式、意义
2）中序表达式向前序、后序转换
根据前序、后序表达式的特性进行手工转换
中序向前序转换的规则（包括堆栈）、运算形式、算法实现、意义
中序向后序转换的规则（包括堆栈）、运算形式、算法实现、意义
6、总结与练习、习题答疑

第五章 队列
目的：掌握队列的特性、应用、两种存储结构及算法实现；掌握双端队列的特性、限定形式、适用范围、存储方式及算法的实现
学时：4学时
教学内容：
1、何谓队列
队列的特性、队列的常见应用举例
2、队列的两种存储结构
1）数组仿真队列---线性队列数组与环状队列数组
线性队列数组的声明及变量的使用
线性队列数组的基本操作（判断队满、判断队空、入队、出队），算法实现
为什么要引入环状存储、环状队列的存储机制
环状队列数组的声明及变量的使用
环状队列数组的基本操作（判断队空、判断队满、入队、出队），算法实现
2）链表仿真队列---链队列
队列链表结构的声明及变量的使用
如何确定链表头尾与队头、队尾的对应关系
链队列的基本操作（判断队空、判断队满、入队、出队），算法实现
3、双向队列（输出受限或输入受限）
1）双端队列的概念、特性与应用举例
2）双端队列的设计方案
3）输入限制性双端队列
特性与基本操作
两种存储方式及算法实现---数组仿真、链表仿真
4）输出限制性双端队列
特性与基本操作
两种存储方式及算法实现---数组仿真、链表仿真
4、总结与习题解答

第六章 递归
目的：掌握堆栈这种数据结构的应用—实现递归；掌握递归的概念、功用、解决问题的步骤与方式；了解递归函数的执行过程、递归工作栈的相关概念与工作方式，进一步明确递归函数的调用过程与参数的传递形式；了解几个典型数学问题与几个著名的实际问题的递归求解方法及算法的实现。
学时：4学时
教学内容：
1、描述线性表的几种常用数据结构概述
2、递归---堆栈的重要应用
何谓递归
递归的功用
递归解决问题的步骤
递归解决问题的基本算法格式
3、递归的执行过程—函数调用、信息传递
递归工作栈的描述
普通函数的调用过程
递归函数的调用过程
4、各类问题的递归解决
递归函数的几个典型的数学应用
利用递归工作栈分析递归函数的执行过程
递归算法与普通算法的比较
三个经典的递归问题
5、习题安排与解答

第七章 基础树状结构
目的：了解树状结构的递归定义、表示方法、相关的概念；掌握二叉树的定义与特性；掌握二叉树的存储结构、遍历方式及相关算法的实现；了解树与森林的结构表示、向二叉树的转换与遍历形式；了解引线二叉树的结构、特性、功用与算法实现；了解哈夫曼树的结构特性、相关概念与构建方法；掌握二叉树之应用—表达式求值的方法与算法实现。
学时：10学时
教学内容：
1、何谓数状结构
树的递归定义
树的表示方法及逻辑结构图
与树相关的名称及意义
2、 二叉树
二叉树的定义及其特性
二叉树的基本形态与特殊形态
二叉树的固有性质
3、二叉树的存储结构
1） 二叉树的顺序存储
①数组二叉树的声明
给定二叉树，确定需要的数组大小
二叉树中相关节点在数组中的对应关系
给定数组，能否给出对应二叉树
数组表示法的优缺点及适用范围
算法实现建立数组表示的二叉树
②二叉树的结构数组表示法
结构数组的声明、节点表示及其相互关系
2） 二叉树的链式存储结构------链表表示法
链表结构的声明
算法实现建立链表表示的二叉树
4、二叉树的遍历
何谓遍历
根据根节点的访问顺序，将遍历分类
算法实现二叉树的前序（中序、后序）遍历
给出二叉树，给出其某种遍历顺序
给定某些种遍历顺序，画出二叉树
5、算法实现二叉树的基本操作（递归建立、遍历查找、二分查找、节点插入、节点删除、二叉树的复制、二叉树的比较、二叉树的映像）
6、树和森林的结构表示
树的结构表示与向二叉树的转换
森林的结构表示与向二叉树的转换
树与森林的遍历
7、引线二叉树---线索二叉树
引入原因
结构声明
如何建立和遍历引线二叉树
8、二叉树实际应用举例
9、哈夫曼树
概念与特性、应用
构建规则、算法思想
10、习题解答

第八章 排序
目的：掌握排序的意义、特性与分类原则；掌握三类内部排序的设计思想、适用范围与算法实现，并对每一种简单算法与改进算法进行效率分析；掌握外部排序的特性、适用范围、二种设计思想（普通合并排序、败者树排序）；了解最佳归并树的概念与构建；了解对外部排序的效率分析。
学时：8学时
教学内容：
1、 何谓排序
排序的意义
排序的特性
排序的分类
2、 各种内部排序
交换式排序：冒泡排序、快速排序（二种设计思想）
选择式排序：简单选择排序、累堆排序--堆的概念、特性、应用、堆排序
插入式排序：直接插入排序、谢耳排序（需强调二者的关系、谢尔排序的增量划分状况）、二叉树排序
各种排序的基本思想及算法实现
各种排序的稳定性及时间复杂度和空间复杂度分析
各种排序效率的比较
3、 外部排序
合并排序：基本思想及算法实现、效率分析
败者树：特性、实现外排的应用及算法实现
最佳归并树：概念、特性及应用

第九章 查找
目的：掌握查找的意义、分类；掌握几类典型的对于无序序列以及对于有序序列的查找方式、设计思想、适用范围及算法实现；能够对各类查找进行效率分析和比较。
学时：6学时
教学内容：
1、何谓查找
查找的目的
查找的分类
2、 线性查找
线性查找的基本思想及算法实现、效率分析
3、 折半查找
折半查找的基本思想、普通算法和递归算法实现及效率分析
4、 费式查找
费式树的概念、特性与构建
基于费式树的费式查找的算法实现
5、 插补查找与增强型插补查找
两种查找的意义、设计思想与算法实现、效率比较
6、 杂凑查找
为何引入杂凑查找
什么是杂凑表---哈希表
各种杂凑函数（哈希函数）的构建
好的哈希函数应具备的特性
各种杂凑碰撞解决法
根据杂凑函数和杂凑碰撞解决法构造杂凑表
杂凑查找的几个典型算法实现与效率分析
7、二叉查找
二叉查找的基本思想及算法实现

第十章 高级链表
目的：掌握循环链表的结构特性以及相关基本操作的算法实现；掌握双链表的结构特性以及相关基本操作的算法实现。
学时：4学时
教学内容：
1、 循环链表
与线性链表（单链表）的比较
循环链表结构的声明
各类基本操作（建立、释放、插入、删除）
2、 双链表
特性分析
链表结构的声明
各类基本操作（建立、释放、插入、删除）
3、习题解答与答疑

第十一章 字符串结构
目的：掌握字符串的概念、应用范围与结构特性；掌握字符串的基本输入输出形式与传递方式；掌握相关字符串的一些常规操作及算法实现；了解常用的串处理函数及向数值转换的方式、算法。
学时：4学时
教学内容：
1、 串的概念与应用
2、 字符串的结构声明
定长的顺序存储表示：串的数组表示
不定长的顺序存储表示：串的结构数组表示
字符串的块链存储表示：链表表示
3、 字符串的基本输入输出
各种输入输出函数及其使用时的注意事项
4、 字符串的传递方式
5、 字符串的基本操作
算法实现（计算长度、复制、结合、取代、插入、删除、比较、抽取、比较、分割）
6、 常用字符串处理函数介绍
7、 字符串转换数值的应用介绍

第十二章 图形结构
目的：掌握图形结构的相关概念、特性；掌握图形的两种基本存储结构的表示方式、相关概念和特性；掌握有向图形和无向图形的几种典型存储的算法实现；掌握图形的遍历方式及算法实现；掌握图形的连通特性、最小生成树的特性及算法实现；掌握图形最短路径和关键路径的概念、意义与求解方法，了解相关算法的实现。
学时：10学时
教学内容：
1、 何谓图形结构
图的定义
与图相关的名称及意义
2、 图形的存储结构
1） 图形的数组结构描述
什么是邻接数组（邻接矩阵）、适用范围
有向图、无向图、网的邻接矩阵
2）图形的链表结构描述
①什么是邻接列表（链表）表示法，适用范围
有向图、无向图、网的邻接列表
②有向图形的其它链式结构
逆邻接列表、正交列表、十字链表
③无向图形的其它表示法
邻接列表循序表示法、多重邻接列表表示法
3、 图形存储的算法实现
1） 有向图形
邻接数组、邻接链表
2） 无向图形
多重邻接链表
4、 图形的遍历（深度优先、广度优先）
图形遍历的定义
深度优先遍历的基本思想、遍历方法、算法实现
广度优先遍历的基本思想、遍历方法、算法实现
对应图形，求解其某种遍历顺序
5、 图形的连通性问题
连通图形、连通组件、强连通分量的特性与判断方法
6、 图形的生成树问题
生成树的概念及其需要满足的条件
什么是最小生成树
用Kruskal算法和Prims算法构造最小生成树
Kruskal算法和Prims算法的基本思想描述及书写
两种算法的时间复杂度分析
实际应用举例
7、 最短路径问题
什么是最短路径问题
用Dijkstra算法求解最短路径
Dijkstra算法的基本思想描述及书写
实际应用举例
最短路径的时间复杂度问题
8、 关键路径问题
关键路径的描述及应用范围
9、习题与答疑

15