数据结构教学大纲--医用信息本科.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