数据结构与算法分析 Data Structure.doc

数据结构与算法分析 Data Structure 第一章、绪论 1、教学内容 （1）数据结构的一些基本概念：数据、数据元素、数据逻辑结构、数据存储结构、数据类型、算法等； （2）抽象数据类型； （3）描述算法所用的类C语言中的一些有关问题； （4）算法时间复杂度和空间复杂度的分析。 2、学习绪论的基本要求 了解本课程的性质、任务和目的，掌握数据结构的一些基本概念，掌握算法的时间复杂度和空间复杂度的分析方法，了解抽象数据类型的定义和使用，了解算法的描述方法。 第二章、线性表 1、教学内容 （1）线性表的基本概念和类型定义； （2）线性表的顺序存储结构； （3）线性表的链接存储结构 A、单链表的查找、插入和删除； B、循环链表； C、双向链表； D、一元多项式的表示及相加。 2、基本要求 掌握线性表的基本概念和类型定义；熟练掌握对顺序表和单链表的常用操作方法及其程序实现；掌握循环链表和双向链表的定义和它的插入、删除等操作方法；掌握一元多项式的表示及相加运算。 第三章、栈和队列 1、教学内容 （1）栈的类型定义； （2）栈的顺序存储和链接存储的表示； （3）在栈的顺序存储和链接存储上进行各种栈操作的算法； （4）栈的应用举例； （5）队列的类型定义； （6）队列的顺序存储(循环队列)和链接存储表示及各种操作的实现算法。 2、基本要求 掌握栈和队列的定义，熟练掌握顺序和链接存储的栈和队列的各种运算的方法及其程序实现，掌握表达式求值等方法并了解其算法。 第四章、串、数组和广义表 1、教学内容 （1）串的定义、存储结构和操作； （2）数组的定义、抽象数据类型以及顺序存储结构； （3）特殊矩阵和稀疏矩阵的定义、存储和运算； （4）广义表的定义和存储结构。 2、 基本要求 掌握串的定义、存储结构和操作；掌握数组的定义、抽象数据类型以及顺序存储结构；掌握特殊矩阵和稀疏矩阵的定义以及各种存储结构，掌握稀疏矩阵的转置和相加的方法并了解其算法；掌握广义表的定义、存储结构的表示方法。第五章、树和二叉树 1、教学内容 （1）树的定义、术语、表示形式、基本操作和抽象数据类型； （2）二叉树的定义、性质、基本操作和抽象数据类型以及存储结构； （3）遍历二叉树和线索二叉树； （4）哈夫曼树的定义、构造哈夫曼树的方法及哈夫曼编码的方法； （5）树和森林：树的存储结构，树、森林和二叉树的转换，树的遍历，森林的遍历。 2、基本要求 掌握树的定义、性质、存储结构以及树和森林的遍历算法，熟练掌握二叉树的定义、性质、存储结构、各种遍历方法及其实现，掌握二叉树的其他操作方法及实现，掌握树和二叉树的转换方法，掌握哈夫曼树应用。 第六章、图 1、教学内容 （1）图的定义、术语、基本操作和抽象数据类型； （2）图的各种存储结构； （3）图的深度优先遍历和广度优先遍历以及图的连通分量； （4）图的生成树和最小生成树； （5）有向无环图及其应用； （6）最短路径。 2、基本要求 掌握图的定义和术语；熟练掌握图的存储结构及深度和广度优先搜索方法及其实现；掌握图的生成树的概念，掌握求图的最小生成树的普里姆法和克鲁斯卡尔法并了解其实现算法；掌握拓扑排序的方法并了解其实现算法，了解AOE网络。 第七章、查找 1、教学内容 （1）查找的基本概念； （2）顺序表的查找、有序表的折半查找以及索引顺序表查找； （3）二叉排序树定义、查找、插入、删除以及查找性能的分析； （4）平衡二叉树的定义、平衡旋转以及B-树； （5）散列表的基本概念、散列函数、处理溢出的闭散列方法和开散列方法以及散列表分析。 2、基本要求 了解查找的基本思想及查找成功和不成功的概念，掌握在顺序表、有序表、索引表、二叉排序树、散列表等上的查找方法和算法，并能求出相应的平均查找长度，理解平衡二叉树、了解B-树。 第八章、排序 1、教学内容 （1）基本概念； （2）插入排序； （3）交换排序； （4）选择排序； （5）归并排序； （6）基数排序； （7）各种内部排序方法的比较