数据结构理论教学大纲数据结构的主要内容包括最常用的数据结构的逻辑特性、存储表示以及对这些数据结构的操作算法。通过课程学习，掌握从问题入手，分析研究计算机加工的数据结构的特性，为应用所涉及的数据，选择适当的逻辑结构、存储结构及相应操作的算法，并通过上机实习进行复杂程序设计的训练，进一步提高软件设计和编程的能力和水平，为学习后续课程做好必要的知识准备。课程名称：数据结构 英文名称：Data Structures课程编号： 课程类别：专业基础课 相关课程：先修课程为计算机高级语言、离散数学；后继课程：操作系统等 开课院系：管理学院（信息管理系、信息管理与信息系统等专业） 授课教师：戚桂杰 每学期学时：48学时 指定教材：严蔚民等.数据结构（C语言版）.北京：人民邮电出版社，2011一、课程简介：目的、要求和任务 数据结构作为一门独立的课程最早是美国的一些大学开设的，1968年美国唐欧克努特教授开创了数据结构的最初体系，他所著的计算机程序设计技巧第一卷基本算法是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。从20世纪60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们就越来越重视数据结构，认为程序设计的实质是对确定的问题选择一种好的结构，加上设计一种好的算法。从20世纪70年代中期到80年代初，各种版本的数据结构著作就相继出现。 目前在我国，数据结构也已经不仅仅是计算机专业的教学计划中的核心课程之一，而且是其它非计算机专业的主要选修课程之一。 数据结构在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及到计算机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。因此，可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，在计算机科学中，数据结构不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据系统及其它系统程序和大型应用程序的重要基础。 值得注意的是，数据结构的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型的观点来论论数据结构，已成为一种新的趋势，越来越被人们所重视。 数据结构是信息管理与信息系统专业的核心基础课程之一。学习本门课程要求掌握各种主要数据结构的特点、计算机内的表示方法，以及处理数据的算法实际，对于算法所花费的时间和空间代价的分析也要求有一定程度的了解和掌握。通过本门课程的学习，使学生透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养基本的良好的程序设计能力。 本课程主要内容有：数据结构和算法设计与分析的基本知识，各种基本数据结构的定义，存储结构、相应的算法以及应用，掌握基本的数据结构与算法的关系。培养学生结合实际应用，设计有效的算法和数据结构的能力。二、教学目的与要求 要求学生通过学习，掌握基本算法和数据结构，它是学习信息管理与信息系统专业核心核心课程的基础，掌握好这门课程的内容，是学习其他相关课程的必备条件。 三、教学方法与教学手段1课堂讲授 在多媒体教室中采用电子教案授课，上课时边讲边演示。2作业（每部分布置一次作业）四、教学内容及学时分配课程内容教学要求重点（）难点（）学时安排第一讲数据结构研究的主要内容数据结构中涉及的基本概念算法的概念、描述方法以及评价标准AADT、算法的概念、描述方法以及评价标准ADT3第二讲线性表的定义和基本操作、线性表的顺序存储结构、线性表的链式存储结构、循环链表、线性表的应用举例A线性表的顺序存储结构、线性表的链式存储结构、循环链表93(上机)第三讲栈的概念、存储结构及其基本操作队列的概念、存储结构及其基本操作栈与队列的应用举例串的定义、存储结构和基本运算、模式匹配A栈的存储结构及其基本操作、队列存储结构及其基本操作模式匹配33(上机)第四讲树的定义和存储结构二叉树的定义、性质、存储结构二叉树的遍历、线索算法树和二叉树的转换哈夫曼树及其应用A二叉树的遍历、线索算法、哈夫曼树及其应用线索算法、哈夫曼树及其应用93(上机)第五讲图的定义图的存储结构图的遍历操作图的几个典型应用问题B图的存储结构图的遍历操作图的几个典型应用问题93(上机)第六讲静态查找表及查找算法：顺序查找、折半查找动态查找表及查找算法：二叉排序树哈希表及查找算法A顺序查找、折半查找动态查找表及查找算法：二叉排序树哈希表及查找算法、二叉排序树62(上机)第七讲排序的概念，直接插入排序希尔排序、快速排序、，堆排序、归并排序A快速排序、堆排序、归并排序、希尔排序快速排序、堆排序62(上机)第八讲文件的相关概念、表示方法及各种运算的实现方法B文件的相关概念、表示方法各种运算的实现方法3（教学要求：A-熟练掌握；B-掌握；C-了解）五、建议实验项目及学时分配 1、线性表的基本操作(3个学时) 2、栈的基本操作(3个学时) 3、二叉树的遍历(3个学时) 4、图的遍历（3个学时） 5、查找排序算法实现(4个学时) 六、参考书目 教材：数据结构C语言版 严蔚敏 著 清华大学出版社 说明：该教材为部级优秀教材和高校推荐教材。内容新颖、概念清晰、通俗易懂、层次配套、实用性强。 七、课程内容与考核目标 第1章 概论（3学时） （一）课程内容 1.1 基本概念和术语 1.2 学习数据结构的意义 1.3 算法的描述和分析 （二）学习目的与要求 本章的目的是介绍数据结构中常用的基本概念和术语以及学习数据结构的意义，要求了解本章介绍的各种基本概念和术语，掌握算法描述和分析的方法。本章重点是了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系，难点是算法复杂度的分析方法。 （三）考核知识点与考核要求 1.数据结构的基本概念和术语、要求达到“识记”层次。 1.1 数据、数据元素、数据项、数据结构等基本概念。 1.2 数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。 1.3 数据结构的两大类逻辑结构和四种常用的存储表示方法。 2.数据结构在软件系统中的作用，要求达到“识记”层次。 2.1 数据结构在各种软件系统中所起的作用。 2.2 选择合适的数据结构是解决应用问题的关键步骤。 3.算法的描述和分析，要求达到“领会”层次。 3.1 算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。 3.2 算法的时间复杂度不仅仅依赖于问题的规模，也取决于输入实例的初始状态。 3.3 算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。 第2章 线性表（9学时） （一）课程内容 2.1 线性表的逻辑结构 2.2 线性表的顺序存储结构 2.3 线性表的链式存储结构 2.4 顺序表和链表的比较（二）学习目的与要求 本章目的是介绍线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。要求在熟悉这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。本章重点是熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，难点是能够使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。 （三）考核知识与考核要求 1.线性表的逻辑结构，要求达到“识记”层次。 1.1 线性表的逻辑结构特征。 1.2 线性表上定义的基本运算，并能利用基本运算构造出较复杂的运算。 2.线性表的顺序存储结构，要求达到“综合利用”层次。 2.1 顺序表的含义及特点，即顺序表如何反映线性表中元素之间的逻辑关系。 2.2 顺序表上的插入、删除操作及其平均时间性能分析。 2.3 利用顺序表设计算法解决简单的应用问题。 3.线性表的链式存储结构，要求达到“综合应用”层次。 3.1 链表如何表示线性表中元素之间的逻辑关系。 3.2 链表中头指针和头结点的使用。 3.3 单链表、双链表、循环链表链接方式上的区别。 3.4 单链表上实现的建表、查找、插入和删除等基本算法，并分析其时间复杂度。 3.5 循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。 3.6 双链表的定义及其相关的算法。 3.7 利用链表设计算法解决简单的应用问题。 4.顺序表和链表的比较，要求达到“领会”层次。 4.1 顺序表和链表的主要优缺点。 4.2 针对线性表上所需要执行的主要操作，知道选择顺序表还是链表作为其存储结构才能取得较优的时空性能。 第3章 栈和队列（3学时） （一）课程内容 3.1 栈 3.2 队列 3.3 栈和队列的应用 （二）学习目的与要求 本章目的是介绍栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算。要求在掌握栈和队列的特点的基础上，懂得在什么样的情况下能够使用栈或队列。本章重点是掌握栈和队列在两种存储结构上实现的基本运算，难点是循环队列中对边界条件的处理。 （三）考核知识与考核要求 1.栈的逻辑结构、存储结构及其相关算法，要求达到“综合应用”层次。 1.1 栈的逻辑结构特点，栈与线性表的异同。 1.2 顺序栈和链栈上实现的进栈、退栈等基本算法。 1.3 栈的“上溢”和“下溢”的概念及其判别条件。 1.4 利用栈设计算法解决简单的应用问题。 2.队列的逻辑结构、存储结构及其相关算法，要求达到“综合应用”层次。 2.1 队列的逻辑结构特点，队列与线性表的异同。 2.2 顺序队列（主要是循环队列）和链队列上实现的入队、出队等基本算法。 2.3 队列的“上溢”和“下溢”的概念及其判别条件。 2.4 使用数组实现的循环队列取代普通的顺序队列的原因。 2.5 循环队列中对边界条件的处理方法。 2.6 利用队列设计算法解决简单的应用问题。 3.栈和队列的应用，要求达到“领会”层次。 栈和队列的特点，什么样的情况下能够使用栈或队列。第4章 树和二叉树（9学时） （一）课程内容 4.1 树的概念 4.2 二叉树 4.3 二叉树的遍历 4.4 线索二叉树 4.5 树和森林 4.6 哈夫曼树及其应用 （二）学习目的与需求 本章目的是介绍二叉树的定义、性质、存储结构、遍历、线索化、树的定义、存储结构、遍历、树和森林与二叉树的转换，哈夫曼树及哈夫曼编码等内容。要求在熟悉这些内容的基础上，重点掌握二叉树的遍历算法及其相关应用，难点是使用本章所学到的有关知识设计出有效算法，解决与树或二叉树相关的应用问题。 （三）考核知识点与考核要求 1.树的概念，要求达到“领会”层次。 1.1 树的逻辑结构特征。 1.2 树的不同表示方法。 1.3 树的常用术语及含义。 2.二叉树，要求达到“简单应用”层次。 2.1