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

《数据结构》教学大纲 前言 《数据结构》这门课程是计算机专业的必修课程。我院医学信息管理专业开设了这门课程，作为计算机核心课程之一。本科设置学时为72学时。 《数据结构》是计算机科学的算法理论基础，也是软件设计的技术基础，主要研究信息的逻辑结构及其基本操作在计算机中的表示和实现。是介于软件、硬件和数学三门学科之间的交叉学科，是计算机专业的核心课程，也是基础课程，所以面向我院信息医学专业开设了这门课程。通过学习，使学生掌握各种数据在计算机中的存储、传递和转换，能用简洁适用的数据结构来表示程序中的数据和变量。找出合适的算法来设计程序的流程，更好的去解决问题；训练学生程序设计技能并培养其良好的程序设计思想和风格。 本课程是理论性与实践性并重的课程，每节内容除适当的思考习题外，还应多多上机练习。 使用教材：黄国瑜 叶乃菁编，《数据结构》（C语言版），清华大学出版社 教学所使用的主要参考书：严蔚敏等编，《数据结构》（C 语言版），清华大学出版社 数据结构的基本概念 目的：掌握数据结构的相关概念、分类形式；掌握算法的构成、特点与效率评判； 了解程序的设计风格与结构化程序设计；掌握程序分析的两种口径，尤其是时间复杂度的概念、分类等级、表述形式及计算方式 学时：6学时 教学内容： 1、什么是数据结构 数据结构及其相关概念 数据结构的分类 2、算法 什么是算法 算法设计的要求 描述算法的方式 算法的效率分析 3、程序结构化与设计风格 软件设计的步骤 软件设计的方法 良好的程序编写风格 4、程序分析的方法 时间分析法与空间分析法 两种口径的应用 5、时间复杂度的分析 何谓时间复杂度：不同教材的观点阐述 理想状态的时间复杂度 渐进的时间复杂度 6、时间复杂度的等级 不同阶的时间复杂度 一些典型算法可达到的时间复杂度举例 7、时间复杂度的渐进式表示法 8、时间复杂度的计算 9、总结与练习 第二章 数组 目的：掌握数组的概念、表示法与存储特性；掌握一维数组的存储、使用、相关操作与算法实现；掌握一维数组的高级应用及算法实现；掌握二维数组的表示方法、存储方式；掌握几种特殊类型二维数组的存储方式及算法实现；了解广义表的概念、结构特性与存储方式。 学时：4学时 教学内容： 1、什么是数组 数组的表示方法；数组的存储特性 一维数组的使用 一维数组的声明及其元素的表示方法 一维数组元素对应的内存位置 一维数组的基本操作（建立、查找、修改、插入、删除、输出、转置）、算法实现 一维数组的高级使用 运用一维数组存储数据，以弥补C语言一些数据类型存储范围的限制 算法解决实际问题 4、二维数组 二维数组的表示方法 二维数组的存储方式 算法实现二维数组转换为一维数组 5、特殊类型的数组 稀疏数组及其存储表示 算法实现稀疏数组的压缩 上三角（下三角）数组及其存储表示 算法实现上三角（下三角）数组转换为一维数组 6、线性问题的数组解决 7、广义表的概念与结构特性、存储特性 第三章 链表 目的：掌握线性表的存储特性、单链表的特性、单链表的建立、相关操作及算法的实现；掌握单链表的三项基础操作、常用操作；掌握常见线性问题的链式存储及链式描述的算法实现；了解链式存储算法实现的时间复杂度。 学时：4学时 教学内容： 线性表的存储特性概述 顺序存储结构 链式存储结构 2、什么是链表 链表的存储特性 与数组存储的比较 单链表的特性（节点映像） 3、链表的使用 单链表节点的声明及单链表的表示 单链表的基本操作特性 节点的配置、节点的删除、节点的释放 单链表的建立、单链表的节点输出、单链表的释放 4、单链表的三项基础操作：定位（查找）、插入和删除 单链表的定位操作、算法实现、时间复杂度分析 5、单链表的三项基本操作： 定位（节点的查找）、节点的插入、节点的删除 三项操作的时间复杂度问题 6、单链表的常用操作： 链表的反转、链表的链接、链表的比较 单链表常用操作的算法实现 7、线性问题的链表解决 8、总结与启发 根据逻辑图的指针设置和变换掌握相应子函数的设计思想 根据运行结果判断主函数的脉络 第四章 堆栈 目的：掌握堆栈的概念、特性；了解堆栈的应用；掌握堆栈的两种存储特性及算法实现、效率分析；掌握堆栈的典型应用---程序设计中表达式求值问题；掌握程序设计中表达式相互转换的规则、堆栈的使用；掌握表达式转换的设计思想及算法实现。 学时：6学时 教学内容： 1、何谓堆栈 堆栈的特性 堆栈的常见应用举例 2、堆栈的基本运算 3、堆栈的两种存储结构及实现 数组仿真堆栈---堆栈数组 堆栈数组的声明及变量的使用 堆栈数组的基本操作（判断栈空、判断栈满、压栈、出栈、取栈顶值），算法实现 2）链表仿真堆栈---链栈 堆栈链表结构的声明及变量的使用 如何确定链表头尾与栈底、栈顶的对应关系 链栈的基本操作（判