数据结构课程教学大纲课程代码：0306207（总学时数：64，学分数：4）课程的性质、目的与任务“数据结构”是大学专科计算机专业必修的一门专业基础课。随着计算机软件和硬件的发展，计算机应用已经深入到社会的各个领域，各行各业都需要对大量的非数值数据进行存储、加工和管理。如何根据实际应用的要求，对数据进行有效地组织、存储和处理，进而编制出相应的高效率算法，这是“数据结构”这门课所要研究并加以解决的问题。通过“数据结构”课程的学习，使学生能了解应用数据结构在程序设计中的作用，熟练掌握各种数据结构的存储和处理方法，并能利用数据结构的知识和技巧设计出更好的算法和程序。为今后从事计算机软件的开发和应用提供必要的技术基础，并为进一步学习“操作系统”和“数据库”等后继课程打下良好的基础。本课程要求通过对各种数据的逻辑结构的描述，阐述在计算机的内存空间中实现数据的逻辑结构的各种方法，即数据的存储结构，并在各种存储结构下讨论数据运算和数据应用，同时对各种运算和应用给出相应的算法。其主要任务是为计算机科学和工程技术人员在处理非数值型数据时，能利用数据结构的知识和技巧更有效地组织好、管理好和处理好数据，设计出高效率的算法。教学内容主要内容对各种类型数据结构在计算机中进行存储、加工和处理和方法，并给出了各种方法在计算机中实现的算法。本课程共分８个部分。第1部分绪论，在本部分中主要介绍数据结构的基本概念，并对算法的度量进行举例说明；在第2部分至第7部分分别讨论了线性表、栈和队列、串、树以及图等几种基本类型的数据结构，内容包括它们的逻辑结构和存储结构以及在各种结构下相应运算和算法，并在讨论基本运算的基础上给出一些应用实例；第７部分和第８部分讨论查找和排序，并介绍了常用的几种排序和查找的方法。教学基本要求对“数据结构”这门课程，要求学生掌握以下几个方面的知识与技能线性表、树、图的基本结构。线性表、树、图的基本算法。对算法时间复杂度、空间复杂度的计算。查找、排序的主要算法及比较。线性表、树、图的应用算法。了解若干算法在计算机领域中的应用实例。其中（1）~（4）为基本要求，必须牢固掌握。（5）为较高层次要求，能加深学生对数据结构基本概念、基本算法的理解。（6）为知识性要求，为开拓学生思路，加强与其他课程间的联系而设。与其他课程的关系“数据结构”是一门专业基础课程，需要有一定的编程能力为基础。尤其需要学生在高级语言的学习时，掌握指针类型和结构类型的用法。另外，学生调试程序的能力也对数据结构的学习效率有很大影响。“数据结构”是学习大多数专业课程必要的基础，比如“操作系统”、“数据库系统”、“计算机网络”等。可以说，许多后续课程相当于数据结构在特定领域中的深入实践。没有数据结构的基础，学生很难对这些后续课程产生深刻的体会。目的与要求第一部分：数据结构基础1．掌握什么是数据结构2．掌握数据结构的概念、术语3．算法的描述与分析掌握算法的描述方法能对算法的时间复杂性和空间复杂性进行分析第二部分：线性表掌握线性表的逻辑结构熟悉线性表的顺序存储结构和链式存储结构掌握单向循环链表和双向循环链表掌握栈的定义和基本运算熟悉栈的表示和实现熟练掌握栈的应用掌握队列的定义和运算掌握队列的存储结构稀疏矩阵第三部分：串1．掌握串的定义及其基本运算2．掌握串的存储结构3．熟悉串的匹配运算第四部分：树掌握树的定义和基本术语掌握二叉树的定义及其性质熟悉二叉树的存储结构熟悉并掌握普通树与二叉的转换掌握二叉树的遍历了解线索二叉树掌握树的应用：着重是二叉排序树和哈夫曼树的应用第五部分：图掌握图的定义和基本术语掌握图的存储方式掌握图的两种遍历方法，即深度优先搜索DFS和广度优先搜索BFS掌握生成树的概念和最小生成树掌握图的最短路径掌握拓补排序第六部分：排序掌握常用的简单排序方法掌握堆排序了解快速排序了解归并排序了解基数排序第七部分：查找掌握线性表的查找掌握树表的查找了解散列法实验内容线性表及其运算通过这部分实验：掌握线性表的逻辑特征，掌握线性表顺序存储结构的特点，熟练掌握线性表的基本运算，掌握栈和队列的特点及其运算。链表及其运算通过这部分实验：掌握链表存储结构的特点，熟悉链表的指针操作（插入、删除、遍历），熟悉集合的链表存储结构以及集合运算与链表变换的对应关系。二叉树的存储与遍历通过这部分实验：熟悉遍历二叉树的递归算法，灵活运用二叉树的遍历算法，加深对二叉树结构和遍历序列对应关系的理解，熟悉二叉排序树结构的应用，熟悉哈夫曼树的结构及其中操作。图的存储与遍历通过这部分实验：熟悉图的主要存储结构及其基本运算。排序对数组采用以下算法排序：（1）插入排序（2）