《数据结构》课程教学大纲

所有的限制，几乎都是从自己的内心开始的。
《数据结构 A》课程教学大纲
Data Structure A
课程代码： 课程性质：专业基础理论课/必修 适用专业：信息计算、信息安全 开课学期：5 总学时数：72 总学分数：4.5 编写年月：2003年7月 修订年月：2007年7月 执 笔：高学军、刘科峰、李小英 一、课程的性质和目的
数据结构是信息与计算科学专业的一门重要专业基础课程。当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下了厚实的知识基础，同时也提供了必要的技能训练。因此，数据结构课程在信息与计算科学专业中具有举足轻重的作用。
二、课程教学内容及学时分配
第1章　绪论　（4学时）
理解数据、数据元素和数据项的概念及其相互间的关系。理解数据结构的逻辑结构、存储结构的联系与区别，以及在数据结构上施加的运算及其实现。掌握简单的算法分析方法。
本章知识点为：数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义；抽象数据类型的定义、表示和实现方法；描述算法的类C语言；算法设计的基本要求以及从时间和空间角度分析算法的方法。
第2章　线性表　（10学时，2个学时实验上机）
理解线性表的定义及其运算。理解顺序表和链表的定义、组织形式、结构特征和类型说明，掌握在这两种表上实现的插入、删除和按值查找的算法。了解循环链表、双向(循环)链表的结构特点和在其上施加的插入、删除等操作。掌握稀疏多项式在线性表的两种存储结构上的实现方法。
本章知识点为：线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法；在线性表的两类存储结构(顺序的和链式的) 上实现基本操作；稀疏多项式的抽象数据类型定义、表示和加法的实现。
第3章　栈和队列　（6学时，2个学时实验上机）
理解栈和队列的定义、特征及在其上所定义的基本运算。掌握在两种存储结构上对栈和队列所施加的基本运算的实现。熟练掌握循环队列和链队列的基本操作实现算法，尤其是队满和队空的描述方法。
本章知识点为：抽象数据类型栈的定义；栈的表示和实现；栈的应用；抽象数据类型队列的定义；链队列；循环队列。
第4章　串　（4学时，2个学时实验上机）
熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。熟

练掌握在串的定长顺序存储结构上实现串的各种操作的方法。掌握串的堆存储结构以及在其上实现串操作的基本方法。
本章知识点为：串的数据类型定义；串的三种存储表示：定长顺序存储结构、块链存储结构和堆分配存储结构；串的各种基本操作的实现及其应用；
第5章　数组和广义表　（6学时，2个学时实验上机）
了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。掌握对特殊矩阵进行压缩存储时的下标变换公式。了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。掌握广义表的结构特点及其存储表示方法。
本章知识点为：数组的类型定义和表示方式；特殊矩阵和稀疏矩阵的压缩存储方法及运算的实现；广义表的逻辑结构和存储结构和广义表的操作。
第6章　树和二叉树　（12学时，2个学时实验上机）
深刻理解树的定义、性质及其存储方法，熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义，并能画出给定二叉树的二叉链表的结构示意图；理解并掌握二叉树的三种遍历方法，并能写出该三种遍历的算法；会完成树、森林与二叉树间的相互转换；理解哈夫曼树的构造方法，并能对给定的数据集合构造出哈夫曼树。
本章知识点为：二叉树的定义、性质和存储结构；二叉树的遍历和线索化以及遍历算法的各种描述形式；树和森林的定义、存储结构、与二叉树的转换、遍历；树的多种应用。
第7章　图　（12学时，2个学时实验上机）
理解图的基本概念及术语，掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法；熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法思想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列；理解最小生成树的概念，能按Prim算法构造最小生成树；了解并掌握拓扑排序、关键路径、最短路径的算法思想。
本章知识点为：图的定义和术语；图的四种存储结构：数组表示法、邻接表、十字链表和邻接多重表；图的两种遍历策略：深度优先搜索和广度优先搜索；图的连通性：连通分量和最小生成树；拓扑排序和关键路径；两类求最短路径问题的解法。
第8章　查找　（10学时，2个学时实验上机）
了解查找的基本思想及查找成功和不成功的概念，掌握在顺序表、有序表、索引表、散列表等上的查找方法和算法，并能求出相应的平均查找长度。
本章知识点为：讨论查找表(包括静态查找表和动态查找表)的各种实

现方法：顺序表、有序表、树表和哈希表；平均查找长度的讨论。
第9章　内部排序　（8学时，2个学时实验上机）
　了解排序的基本思想和基本概念，理解和掌握插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序的基本思想、步骤及算法。
本章知识点为：讨论比较各种内部排序方法，插入排序、交换排序、选择排序、归并排序和基数排序的基本思想、算法特点、排序过程以及它们的时间复杂度分析。在每类排序方法中，又从简单方法入手，重点讨论性能先进的高效方法。
三、课程教学的基本要求
本课程是信息与计算科学专业的重要专业基础课，计算机科学各领域及有关的系统和应用软件都要用到各种数据结构。在教学方法上采用课堂讲授，课后自学，课堂讨论等教学形式。
(一)课堂讲授
本课程属于基础理论课程。在传授知识原理的前提下，配合实际应用例子，由浅入深善于诱导，使学生从被动吸收知识的状态下，转化到主动索取知识的状态中来，并采用多媒体辅助教学，加大课堂授课的知识含量。注重培养学生的学习兴趣，提高学生的基本素质。
（二）课后自学
为了培养学生整理归纳，综合分析和处理问题的能力，每章都安排一部分内容，课上教师只给出自学提纲，不作详细讲解，课后学生自学。
（三）课堂讨论
课堂讨论的目的是活跃学习气氛，开拓思路。教师应认真组织，安排重点发言，充分调动每一名同学的学习积极性，做好总结。
（四）课外作业
　为了让学生巩固所学的知识，每章都布置一定数量课外作业。
（五）实验
用C语言或C++语言完成一些算法设计题。培养学生的算法设计能力和程序设计能力。
总评成绩：平时作业占30%，闭卷考试占70%。
四、本课程与其它课程的联系与分工
先修课程：离散数学，C++面向对象程序设计等。
后续课程：操作系统，数据库原理等。
五、建议教材与教学参考书
[1] 严蔚敏 吴伟民编著，数据结构(C语言版)，北京:清华大学出版社, 2004
[2] 严蔚敏 吴伟民编著，数据结构题集(C语言版)，北京:清华大学出社，2004
[3] Willan Ford,Willian Topp. Data Structures with C++. New Jersey:Prentice Hall Inc, Adivision Simon & Schuster Company，1996(数据结构--C++语言描述.北京:清华大学出版社，1997)
[4] 徐孝凯，数据结构实用教程（C/C++描述），北京:清华大学出版社，1999
[5] 陈慧南.数据结构（使用C++语言描述），南京:东南大学出版社，2001
[6] 殷人昆,陶永雷,谢

若阳等.数据结构（用面向对象方法与C++描述），北京:清华大学出版社，1999

所有的限制，几乎都是从自己的内心开始的。