数据结构教学大纲.docx

数据结构学 分：30学 时：48（其中：讲课学时：48 实验学时：另行安排）先修课程：大学计算机基础、C语言程序设计等课程适用专业：计算机科学与技术、通信工程、自动化、电子信息工程等专业教 材：数据结构C语言版（第1版），严蔚敏、吴伟民编，清华大学出版社，1997开课系部：计算机科学与工程系撰 写 人：李 宁审 定 人：徐守坤 批准人：杨长春一、课程的性质与任务本课程是一门专业技术基础课，通过本课程的学习，要求学生学会分析、研究计算机加工的数据对象特性，以便选择适当的数据以及相应的算法，并初步掌握算法的时间分析和空间分析技巧。学习过程中，应注意培养学生的数据抽象能力和复杂程序设计能力。二、课程的教学内容及要求（一）绪论1教学内容（1）什么是数据结构；（2）基本概念和术语；（3）抽象数据类型的表示和实现；（4）算法和算法分析。2基本要求掌握什么是数据结构，数据结构的基本概念和术语；了解数据结构发展简史及在计算机科学中的地位；理解算法的描述和算法分析。（二）线性表1教学内容（1）线性表的类型定义；（2）线性表的顺序表示和实现；（3）线性表的链式表示和实现；（4）一元多项式的表示及相加。2基本要求理解线性表的逻辑结构，线性表的顺序存储结构，线性表的链式存储结构；掌握线性表的顺序存储结构和线性表的链式存储结构的基本操作和算法；了解一元多项式的表示及相加的算法。（三）栈和队列1教学内容（1）栈；（2）栈的应用举例；（3）栈与递归的实现；（4）队列。2基本要求掌握什么是栈、队列，以及栈和队列的基本操作的算法；理解栈与递归过程的关系。了解栈和队列的应用。（四）串1教学内容（1）串类型的定义；（2）串的表示和实现；（3）串的模式匹配；（4）串操作应用举例。2基本要求理解串的基本概念；掌握串的基本操作的算法，以及串的存储结构；了解串操作应用举例。（五）数组和广义表1教学内容（1）数组的定义；（2）数组的顺序表示和实现；（3）矩阵的压缩存储；（4）广义表的定义及存储结构。2基本要求掌握数组的顺序存储,矩阵的压缩存储，广义表的定义及存储结构。（六）树和二叉树1教学内容（1）树的定义和基本术语；（2）二叉树；（3）遍历二叉树和线索二叉树；（4）树和森林；（5）哈夫曼树及应用。2基本要求掌握树的结构定义和基本操作；掌握二叉树的基本概念、基本性质，以及树和二叉树的关系；掌握遍历二叉树的几种方法和线索二叉树的概念；掌握二叉树和树、森林之间的相互转换；掌握哈夫曼树的创建及其应用。（七）图1教学内容（1）图的定义及术语；（2）图的存储结构；（3）图的遍历；（4）图的连通性问题；（5）有向无环图及其应用；（6）最短路径。2基本要求掌握图的定义及术语，图的存储结构，图的遍历，图的连通性问题；了解有向无环图及其应用；掌握最短路径和关键路径的求解过程和算法。（八）查找1教学内容（1）静态查找表；（2）动态查找表；（3）哈希表。2基本要求掌握静态查找表、动态查找表中各自查找方法的实现过程；理解哈希表的基本概念；掌握解决哈希冲突的几种方法。（九）内部排序1教学内容（1）概述；（2）插入排序；（3）快速排序；（4）选择排序；（5）归并排序；（6）基数排序；（7）各种内部排序方法的讨论。2基本要求掌握插入排序，快速排序，选择排序，归并排序，基数排序等内部排序方法的实现过程了；了解顺序文件、索引文件、ISAM文件、直接存取文件、多关键字文件。三、课程学时分配章 节讲 课实 验上 机第一章 绪论4第二章 线性表4第三章 栈和队列4第四章 串4第五章 数组和广义表4 第六章 树和二叉树8第七章 图8 第八章 查找8 第九章 内部排序4 四、参考书目 高一凡数据结构算法实现及解析西安：西安电子科技大学出版社 1996 徐孝凯