《数据结构》课程教学大纲(DataStructure)课程编号：030503适用专业：计算机科学与技术、网络工程总学时数：80—84学分：4—5编制单位(或执笔者)：计算机与电子信息学院软件工程教研室修订时间：2006年8月30日一、课程的地位、性质和任务（四号黑）《数据结构》是计算机学科重要的一门专业基础课。由于构成计算机科学的核心是数据结构、算法和程序设计，因此必须以本课程作为计算机专业核心课程，为学生的专业学习打下扎实深厚的基础。本课程以系统的观点研究数据组织和操作算法，必须在抽象思维、算法设计等方面加强学生的能力培养。同时，本课程内容是在计算机应用于数值的和非数值的领域中形成和发展的，其新思想和新方法不断产生，必须不断更新教学内容以拓宽学生的知识面，适应计算机应用和发展的需要。本课程又是一门实践性很强的课程，在《数据结构》的课程实验中不仅要训练计算机实验技能和操作能力，更应包括设计算法的创造性实验能力。二、本课程与其他专业课程的关系（本课程学习所必备的知识）先修课程：《高级语言程序设计》本课程中的数据结构定义和算法设计都是以一门高级语言为基础的。许多计算机学科的重点课程，例如《操作系统》、《编译原理》以及《数据库原理》都涉及到本课程所介绍的基本数据结构。三、教学内容、学时安排和基本要求（一）绪论（4学时）数据、数据元类、数据类型、数据结构、抽象数据类型和面向对象的概念，数据结构的层次；算法的定义，算法与数据结构的关系，模板，算法的性能分析与度量。1、基本要求（1）理解数据、数据元素和数据项的概念及其相互关系；理解逻辑结构和数据结构的概念；理解存储结构与逻辑结构的关系；理解抽象数据类型和面向对象的概念；（2）了解模板的使用，了解算法分析的基本概念、时间复杂性及其量级的概念。2、重点、难点重点：数据、数据元素和数据项的概念及其相互关系；理解逻辑结构和数据结构的概念、意义和分类；时间复杂性及其量级的概念；难点：存储结构与逻辑结构的关系；抽象数据类型的概念；算法分析的时间复杂性。3、说明：其它内容一般了解。（二）数组（6~8学时）数组的定义及其顺序存储方式；顺序表的定义及操作；矩阵的压缩存储；字符串的定义、操作，字符串的模式匹配算法。基本要求：掌握数组的定义，理解数组的顺序存储结构；掌握顺序表的定义方法及其操作算法的实现；（3）理解矩阵的压缩存储；（4）理解字符串的概念和相关术语。2．重点、难点重点：数组的顺序存储方式；顺序表的操作算法的实现；难点：字符串的模式匹配算法及其改进算法。3．说明：其它内容一般了解；教学方法主要采用讲授，并演示算法软件加深理解。（三）链表（6~8学时）单链表的结构、类定义及基本操作；循环链表的定义及操作；双向链表；用链表存储的稀疏矩阵；C++中的虚函数及动态联编。1．基本要求:（1）掌握单链表的结构、类定义及基本操作的算法；（2）理解循环链表的定义及操作；（3）理解双向链表的结构及关键语句的含义；（4）了解用链表存储的稀疏矩阵的类定义及基本操作；（5）理解C++中继承的概念，了解基类与派生类对象指针的转换、虚函数的概念，纯虚函数和抽象基类的关系和作用，多态性和动态联编的概念。2.重点、难点重点：单链表的结构、类定义及基本操作的算法；循环链表的定义及操作；难点：单链表的游标类，静态链表；稀疏矩阵；C++中的虚函数及动态联编。3．说明：其它内容一般了解；教学方法主要采用讲授，并演示算法软件加深理解。（四）栈和队列（6学时）栈的概念，栈的存储结构，顺序栈的操作算法，链栈的操作算法；队列的概念，队列的存储结构，队列的操作算法，优先级队列。基本要求：能够理解并掌握栈和队列的定义、特点及与线性表的异同；理解栈和队列的基本操作；（3）了解优先队列的定义、存储表示和实现。重点、难点重点：掌握顺序栈和链栈的组织方法，入栈和出栈的算法；难点：掌握循环队列的组织方法、队满、队空的判断条件。3．说明：重点说明两者异同，给学生留相应的问答题。(五).递归（4学时）递归的概念，递归过程与递归工作栈；广义表的定义及存储结构。1．基本要求:（1）理解递归的概念，了解递归过程与递归工作栈；理解广义表的概念，了解广义表的表示、操作及存储结构。2.重点、难点重点：递归的概念，广义表的概念；难点：递归过程与递归工作栈；广义表的表示、操作及存储结构。3．说明：其它内容一般了解；教学方法主要采用讲授，并演示算法软件加深理解。(六).树与森林（8~10学时）树的定义和术语；二叉树的定义和性质，二叉树的存储结构，遍历二叉树（先序、中序、后序）；树与森林、树与二叉树的相互转换及树的遍历；霍夫曼树。