计算机专业（本科）《数据结构》教学大纲.docVIP

数据结构教学大纲课程名称：数据结构课程编号：104300063总学时：54/18适用对象：计算机科学与技术本科专业一、教学目的与任务1、教学目的：数据结构是计算机应用专业的一门专业基础课，主要任务是讨论各种数据组织中的数据逻辑结构、存储结构以及相关操作的算法。目的是使学生学会分析研究计算机加工的数据的结构特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。另一方面，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。2、教学任务：数据结构是实践性很强的课程，不仅要学习基本理论知识，更要注重上机实践，通过上机实践验证算法的正确性，掌握和巩固所学理论知识。通过本课程的学习，要求学生熟练地掌握各种数据组织中的数据逻辑结构、存储结构以及相关操作的算法，掌握排序、查找的程序设计算法。二、教学基本要求教学要求在每章教学内容之后给出。大体分为三个层次：了解内容：正确理解概念。掌握内容：学会所讲知识。熟练掌握内容：会运用所学知识解决实际问题。三、教学内容及要求第一章 绪论（一）教学内容1 数据结构的一些基本概念：数据、数据元素、数据记录、数据的逻辑结构、数据的物理结构、数据对象、数据类型、抽象数据类型、算法等2 算法描述中所用的C语言中的一些相关知识3 算法的时间复杂度和空间复杂度分析（二）教学重点与难点算法的时间复杂度和空间复杂度的分析方法。（三）教学要求掌握数据结构的一些基本概念，掌握算法的时间复杂度和空间复杂度的分析方法，了解抽象数据类型的定义和使用，了解算法的描述方法。第二章 线性表（一）教学内容1 线性表的基本概念和类型定义2 线性表的顺序存储结构及其算法实现3 线性表的链接式存储结构及其算法实现（包括单链表、双链表和循环链表）4 一元多项式的表示及相加（二）教学重点与难点顺序表和单链表的基本操作算法及其程序实现；多项式求和的算法实现。（三）教学要求掌握线性表的基本概念和类型定义；熟练掌握对顺序表和单链表的基本操作算法及其程序实现；掌握循环链表和双向链表的定义及其插入、删除等算法的实现；掌握一元多项式的表示及相加算法。第三章 栈和队列（一）教学内容1 栈的概念和类型定义2 栈的顺序存储结构及其算法实现3 栈的链接式存储结构及其算法实现（包括双栈）4 栈的应用举例（表达式求值）5 队列的概念和类型定义6 队列的顺序存储结构及其算法实现（循环队列）7 队列的链接式存储结构及其算法实现8 队列的应用举例（打印杨辉三角）（二）教学重点与难点顺序栈和链栈、顺序队列和链队列的基本操作算法及其程序实现；利用堆栈实现表达式求值的算法；利用队列实现打印杨辉三角的算法。（三）教学要求掌握栈和队列的定义；熟练掌握顺序和链接存储的栈和队列的各种基本操作算法及其程序实现；掌握在表达式求值和打印杨辉三角的方法中堆栈和队列所起的作用，并了解其算法。第四章 串（一）教学内容串的定义、存储结构及其基本算法（二）教学重点与难点串的存储结构及其相应算法的实现；串的模式匹配。（三）教学要求掌握串的定义、存储结构及其相应算法的实现。第五章 数组和广义表（一）教学内容1 数组的定义和运算2 数组的顺序存储和实现3 特殊矩阵的压缩存储（1） 三角矩阵（2） 带状矩阵（3） 稀疏矩阵4 广义表（二）教学重点与难点数组的顺序存储结构算法实现；特殊矩阵的压缩存储。（三）教学要求掌握数组的基本概念、顺序存储结构的算法实现；掌握特殊矩阵的压缩存储结构；了解广义表的定义、存储结构和求广义表的长度及深度的算法；了解建立广义表和输出广义表的方法。第六章 树和二叉树（一）教学内容1 树的基本概念、性质和表示方法2 二叉树的定义、性质和存储结构3 二叉树的各种遍历方法及其算法实现4 树、森林和二叉树的关系5 哈夫曼树及其应用（1） 哈夫曼树（2） 哈夫曼编码（3） 哈夫曼编码算法的实现6 树的计数（二）教学重点与难点二叉树的基本概念、性质、存储结构及各种遍历算法；哈夫曼树的定义及构造方法；树、森林及二叉树间相互转换的方法；树的计数方法。（三）教学要求掌握树的基本概念、性质、存储结构及遍历算法；熟练掌握二叉树的基本概念、性质、存储结构及各种遍历算法；掌握二叉树的其它操作算法及实现；掌握哈夫曼树的定义及构造方法；了解哈夫曼编码的方法；了解树与二叉树相互转换的方法。第七章 图（一）教学内容1 图的定义与基本术语2 图的存储结构（1） 邻接矩阵（2） 邻接表（3） 十字链表表示3 图的遍历（1） 深度优先搜索（2） 广度优先搜索4 图的连通性问题（1） 无向图的连通分量（2） 最小生成树5 有向无环图的应用（1） 拓扑排序（2） 关键路径6 最短路径问题（二）教学重点与难点图的存储结构及遍历算法；图的连通性问题；有向无环图的应用；最短路径问题。（三）教学要求掌握图的定义和术语；熟练掌握图的存储结构及深度和广度优先搜索遍历方法及其算法实现；掌握图的生成树的概念和最小生成树概念及求解方法；了解图的最短路径问题及其求法；掌握拓扑排序的方法；了解有向无环图的应用。第八章 查找（一）教学内容1 查找的基本术语及查找算法的性能分析2 基于线性表的查找法（1） 顺序查找（2） 折半查找（3） 索引查找（分块查找）3 基于树的查找法（1） 二叉排序树（2） 平衡二叉树（3） B树4 计算式查找法哈希法（1） 哈希函数的构造方法（2） 处理冲突的方法（3） 哈希表的查找过程（4） 哈希法性能分析（二）教学重点与难点顺序查找、折半查找、分块查找的方法及其实现；二叉排序树插入和删除元素的方法；构造哈希函数及处理冲突的方法；进行哈希表查找、插入和删除的算法描述；平衡二叉树、B树的定义、查找、插入和删除元素的方法。（三）教学要求熟练掌握顺序查找和折半查找的方法及其实现；掌握分块查找的方法及其实现；掌握二叉排序树插入和删除元素的方法；掌握哈希表的定义，利用除留余数法构造哈希函数的方法，利用线性探测法和链地址法处理冲突的方法；了解构造哈希函数的其它方法，了解进行哈希表查找、插入和删除的算法描述；了解平衡二叉树和B树的定义、查找、插入和删除元素的方法。第九章 内部排序（一）教学内容1 排序的基本概念2 插入类排序（1） 直接插入排序（2） 折半插入排序（3） 表插入排序（4） 希尔排序3 交换类排序（1） 冒泡排序（2） 快速排序4 选择类排序（1） 直接选择排序（2） 树形选择排序（3） 堆排序5 归并排序6 分配类排序（1） 多关键字排序（2） 链式基数排序（3） 基数排序的顺序表结构7 各种排序方法的综合比较（二）教学重点与难点插入排序、选择排序、冒泡排序的算法及其程序实现；快速排序、堆排序、二路归并排序的算法及其程序实现；各种排序方法的稳定性、时间复杂度和空间复杂度。（三）教学要求熟练掌握直接插入排序、直接选择排序、冒泡排序的算法及其程序实现；掌握快速排序、堆排序、二路归并排序的算法及其程序实现；掌握各种排序方法的稳定性、时间复杂度和空间复杂度。四、学时分配与教学方式总学时：54/18章节学时实验第1章 绪论21第2章 线性表83第3章 栈和队列62第4章 串41第5章 数组和广义表61第6章 树和二叉树83第7章 图83第8章 排序62第9章 查找62合计5418五、考核方式考试与实验考核结合。六、本课程与其他课程的关系数据结构的先修课主要是C语言程序设计，本课程将以C语言作为算法描述和上机实践的工具。同时，本课程又是软件开发与设计等课程的基础。七、教材与参考书数据结构，严蔚敏、吴伟民编著，北京：清华大学出版社，1992年。数据结构题集（C语言版），严蔚敏、吴伟民编著，北京：清华大学出版社，1999年。数据结构习题与解析（C语言篇），李春葆编著，清华大学出版社。2000年。数据结构C语言描述，耿国华编著，西安：西安电子科技大学出版社，2002年。数据结构，王忠义主编，西安交通大学出版社，2003年8月。八、其他需要说明的问题由于数据是计算机处理的对象，使用计算机的过程就是对数据加工处理的过程，因而数据的组织与结构被确立为计算机科学中最基本的内容。通过对数据结构的学习，使学生能够以问题求解方法、程序设计方法、及一些典型的数据结构算法为研究对象，学会分析数据对象的特征，掌握数据组织的方法和计算机中的表示方法，为数据选择适当的逻辑结构、存储结构及相应的处理算法，初步掌握算法的时间复杂度、空间复杂度的分析技巧，培养良好的呈现设计风格以及进行复杂呈现设计的技能。数据结构是一门实践性很强的课程，应