教学大纲
一、课程名称：数据结构
二、课程目的和要求:
本课程是计算机及应用专业、计算机软件专业等各专业的重要专业基础课，它是一门技术性、实践性很强的课程。
本课程所介绍的数据结构有：线性表、栈、队列、链表、串、树、图；要求学生通过各种数据结构的学习，掌握其逻辑特性和物理表示，以及为这些结构所定义的各种算法，掌握它们在计算机科学中的应用；知道如何为某一应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，初步掌握算法的时间分析和空间分析的技术；要求熟练掌握应用广泛的各种排序技术和各种查找技术。
本课程是理论与实践紧密结合的一门课程，因此除要求学生掌握有关理论外，还要求基本掌握进行复杂程序设计的技能和培养良好程序设计的习惯，除完成书面作业外，学生还应完成若干课程设计（实习）。
三、课时：76学时，学分：4
四、修读对象：计算机系计算机科学与技术专业本科二年级学生。
五、先修课程：PASCAL语言程序设计，C语言程序设计，离散数学。
六、课程内容及要求与课时分配：
（一）内容：绪论 4学时
1．什么是数据结构；
2．基本概念和术语；
3．算法和算法分析。
要求：
掌握数据、数据元素、数据结构、数据类型等概念术语的确定含义、特别是数据结构的三个方面以及这三方面的相互关系；描述算法的类C语言与C语言的区别，抽象数据类型，算法设计的基本要求及算法的时间分析和空间分析的方法，掌握计算语句的频度和估算时间复杂度和方法。
（二）内容：线性表 12学时
1．线性表的类型定义；
2．线性表的顺序表示和实现；
3．线性表的链式表示和实现：线性链表，循环链表，双向链表；
4．一元多项式的表示和实现。
要求：
熟练掌握顺序表和链表的描述方法、特点及有关概念。
熟练掌握单链表。循环链表及双链表等多种形式，重点掌握顺序表上的插入和删除算法以及动态链表的建立，查找，插入和删除算法。
零握从时间和空间的角度综合比较顺序表和链表的不同特点及其适用场合。
（三）内容：栈和队列 6学时
1．栈：栈的定义，栈的表示和实现，栈的应用，栈与递归的实现；
2．队列：队列的定义，链队列，循环队列。
要求：
掌握栈和队列这两种数据结构的特点。懂得在什么样的问题中应该使用何种结构。
熟悉栈(队列)和线性表的关系；重点掌握在顺序栈和链栈上实现的栈的五种基本运算，特别注意栈满和栈空的条件及它们的描述。重点掌握在循环队列和链队列上实现的队列的五种基本运算，特别注意队满和队空的描述方法。
理解递妇算法执行过程中栈的状态变化过程。
（四*）内容：串 2～4学时
1．串的逻辑特性；
2．串的物理表示法；
3．有关串的算法。
（五*）内容：数组和广义表 4～6学时
1．数组的定义；
2．数组的顺序表示和实现；
3．矩阵的压缩存储；
4．广义表的定义；
5．广义表的存储结构。
（六）内容：树和二叉树 12学时
1．基本术语、树的逻辑结构及物理表示；
2．二叉树：二叉树的定义、性质、存储结构；
3．遍历二叉树；
4．索二叉树；
5．树的存储结构；
6．森林与二叉树间的转换与遍历；
7．赫夫曼树及其应用。
要求：
熟悉树和二叉树的递归定义，有关的术语及基本概念；熟练掌握二叉树的性质。熟练掌握二叉树的两种存储方法，特点及适用范围。
熟练掌握二叉树的各种次序的遍历算法，能灵活运用遍历算法实现二叉树的其它各种运算。掌握树、森林与二叉树之间的转换方法。熟悉树的二种存储结构及其特点；了解最优二叉树的特性，了解建立最优二叉树和哈夫曼编码的方法。
（七）内容：图 10学时
1．图的逻辑结构及有关术语；
2．图的物理表示法；
3．图的通历与求图的连通分量；
4．生成树与最小代价生成树；
5．拓扑排序；
6．关键路径；
7．最短路径问题。
要求：
熟练掌握基本概念和术语、图的存储结构（图的数组(邻接矩阵)存储表示、邻接表表示）、图的两种遍历方法（深度优先遍历、广度优先搜索）。求最小生成树的两种算法，拓扑排序和关键路径及最短路径的有关算法。
（八*）内容：存储管理 2～4学时
1．存储管理的若干问题；
2．可利用空间表及分配方法；
3．边界标识法和伙伴系统。
（九）内容：查找 8学时
1．静态查找表：顺序表的查找（顺序查找法），有序表的查找（折半查找法），索引顺序表的查找（分块查找法）；
2．动态查找表:二叉排序树和平衡二叉树；B＿树和B＋树；
3．哈希表；
要求：
熟练拿握顺序查找、二分查找和分块查找的方法，并能灵活应用；熟练掌握二又排序树的构造方法及查找过程；了解AVL树、了解B_树的特点；熟练掌握散列表的建表方法及其查找过程。理解它与其它结构的表的本质区别；熟练掌握按定义计算各种查我方法在等概率情况下查找的平均查找长度； 熟悉各种查找方法所需要的存储结构，以及各种查找方法的优缺点。
（十）内容：内部排序 8学时
1．概述；
2．插入排序：直接插入排序，折半插入排序，希尔排序；
3．快速排序；
4．选择排序：简单选择排序，树形选择排序，堆排序；
5．归并排序；
6．基数排序；
7．各种排序方法比较。
要求：
深刻理解各种内部排序方法的基本思想及其特点。
