1、理论课程教学大纲课程名称 数 据 结 构英文名称 Data Structures课程编号 不填 总学时 60 学 分 不填预修课程 C 语言 开课学期 不填大纲撰写人 黄刘生一、教学目标和基本要求 目的：使学生较全面地掌握各种常用的数据结构，提高其数据抽象和程序设计能力,为学习后续软件课程提供坚实的基础。 基本要求：使学生能够从逻辑结构、存储结构和数据的运算三个方面去掌握各种数据结构的特性, 对算法的时、空复杂性有一定的分析能力，使之能够针对具体的应用问题，选择合适的数据结构及设计结构清晰、正确有效的算法解决之。二、课程简介数据结构是计算机学科一门重要的专业基础课，该课程系统地讨论各种常用的数
2、据结构及其应用，以及查找和排序的各种方法及其综合分析比较，培养学生数据抽象和程序设计的能力，算法时、空复杂性的分析能力。三、教学重点、难点1概论：重点是了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及其相互关系，难点是抽象数据类型和算法复杂度的分析方法。2线性表：重点是熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，难点是能够使用所学到的基本知识设计有效算法解决与线性表相关的应用问题。3栈和队列：重点是掌握栈和队列在两种存储结构上实现的基本运算，难点是循环队列中对边界条件的处理。4串：重点是掌握串上实现的模式匹配算法，这也是本章的难点。5树：重点掌握二叉树的遍历算法及
3、其有关应用，难点是使用本章所学到的有关知识设计出有效算法解决与树或二叉树相关的应用问题。6图：重点掌握图在邻接矩阵与邻近表上实现的遍历算法。难点是求图的最小生成树、最短路径、拓扑排序等应用算法及其时间性能分析。7动态存储管理: 重点是内存空间的分配与回收算法，以及可利用空间表的结构。本章难点是无用单元收集算法的理解与掌握。8查找：重点掌握顺序查找、二分查找、二叉查找树上查找以及散列表上查找的基本思想和算法实现。本章难点是二叉查找树的删除算法及 B-树上的插入和删除算法。9 文件：本章重点是介绍存储在外存上的数据结构（文件）的有关概念、各种文件的特点、组织方法及查询和更新操作。四、教材名称及主要
4、参考书数据结构 C 语言版严蔚敏、吴伟民，清华大学出版社，2000。数据结构第 2 版黄刘生、唐策善，中国科技大学出版社，2001。“Data Structures with C+“ Williaw Ford et al., Prentice Hall Inc., 1996.“Data Structures & Program Design in C, 2nd Ed.“ Robert Kruse et al., Prentice Hall Inc., 1997.五、课程章节主要内容及学时分配第一章 概 论（3 学时）第一节 基本概念和术语第二节 学习数据结构的意义第三节 抽象数据类型第四节 算
5、法的描述和分析第二章 线性表（6 学时）第一节 线性表的逻辑结构第二节 线性表的顺序存贮结构第三节 线性表的链式存贮结构第四节 顺序表和链表的比较第三章 栈和队列（6 学时）第一节 栈第二节 队列第三节 栈与队列的应用实例第四章 串（4 学时）第一节 串及其运算第二节 串的存贮结构第三节 串的模式匹配第六章 树（10 学时）第一节 树的概念第二节 二叉树第三节 二叉树的遍历第四节 线索二叉树第五节 树和森林第六节 哈夫曼树及其应用第七节 树与等价问题、树的计数第六章 图（10 学时）第一节 图的概念第二节 图的存贮结构第三节 图的遍历第四节 图的连通性问题第五节 最短路径第六节 有向无环图及其应用第七章 动态存储管理（5 学时）第一节 概述第二节 可利用空间表及分配算法第三节 边界标识法第四节 伙伴系统第五节 无用单元收集第八章 查找（8 学时）第一节 基本概念第二节 静态查找第三节 动态查找第四节 散列查找第九章 文件简介（2 学时）第一节 文件基本概念第二节 顺序文件与索引文件第三节 ISAM 和 VSAM 文件第四节 散列文件六、系教学委员会意见组长签字： 年 月 日七、系主任意见系主任签字： 年 月 日
