《数据结构》教学大纲.doc

数据结构教学大纲适用专业：计算机信息管理、电子商务学 分：周 课 时：4总 学 时：68 （理论52 + 实践 16） 一、课程的性质与任务 数据结构是计算机应用专业的一门专业基础课，主要任务是讨论各种数据组织中的数据逻辑结构，存储结构以及有关操作的算法。目的是使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。另一方面，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力。二、课程的基本要求 先行课：计算机应用基础，C语言程序设计或C+语言程序设计。三、课程内容大纲内容（按章节详细列出）教学目的和要求：经过一学期的学习，掌握数据结构的一些基础知识和基本要点，掌握重要数据结构的概念、使用方法及实现技术，使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，学会做简单的算法分析，包括算法的时间代价和空间代价，为后续计算机专业课程的学习打下坚实的基础。数据结构是实践性很强的课程,不仅要学习基本理论知识,更要注重上机实践,通过上机实践验证算法的正确性,掌握和巩固所学理论知识，培养学生的数据抽象能力和程序设计的能力。第一章 绪论教学目的和要求：掌握数据结构的基本概念，了解抽象数据类型，了解算法时间复杂度和空间复杂度的分析，了解算法的描述方法。1.1概念和术语1.2 算法描述与分析第二章 线性表教学目的和要求：了解线性表的基本概念和类型定义，熟练掌握顺序存储的线性表和单链表的算法设计及其程序实现；掌握循环链表和双向链表的操作。2.1 线性表的基本概念和类型定义2.2 线性表的顺序存储结构2.3 顺序表上的基本运算 2.4 线性表的链接存储结构2.4.1单链表的查找、插入和删除2.4.2循环链表2.4.3双向链表2.4.4线性表顺序存储结构和链式存储结构 2.5 应用举例注：建议将字符串处理作例子加入教学内容。第三章 栈和队列教学目的和要求：掌握栈和队列的定义，熟练掌握顺序和链接存储的栈和队列的算法设计及其程序实现，了解栈和队的各种应用。3.1 栈3.1.1 栈的定义和操作3.1.2 栈的顺序存储结构3.1.3 栈的链式存储结构3.2 栈的应用举例3.2.1 表达式求值3.2.2 递归的实现3.3 队列3.3.1 队列的定义和操作3.3.2 队列的顺序存储结构3.3.3 队列的链式存储结构第四章 串教学目的和要求：掌握字符串的抽象数据类型；字符串操作的实现；字符串的模式匹配。4.1串的基本概念和存储结构4.2串的基本运算4.3串的模式匹配算法4.3.1求子串位置的定位函数4.3.2模式匹配的一种改进算法4.4 汉字串第五章 数组和广义表教学目的和要求：掌握稀疏矩阵的定义和各种存储结构，掌握广义表的定义、存储结构和求广义表的长度及深度的算法，掌握稀疏矩阵的转置和相加的方法并了解其算法，掌握建立广义表和输出广义表的方法并了解其算法。5.1 数组及其运算5.2 数组的顺序存储结构5.3 矩阵的压缩存储5.4 广义表5.4.1 广义表的定义5.4.2 广义表的存储结构5.4.3 广义表的运算第六章 树教学目的和要求：掌握树的定义、性质、存储结构；熟练掌握二叉树的遍历算法及其实现；了解树和二叉树的转换。 6.1 树的基本概念和术语6.2 二叉树6.2.1 二叉树的定义6.2.2 二叉树的性质6.2.3 二叉树的存储结构6.2.4 遍历二叉树6.2.4.1遍历二叉树的定义及递归算法6.2.4.2按前序序列建二叉数6.2.4.3遍历二叉树的非递归算法6.3 树和森林6.3.1 树的存储结构6.3.2 森林与二叉树的转换6.3.3 树和森林的遍历6.4 哈夫曼树6.4.1 基本术语6.4.2 构造哈夫曼树6.4.3 哈夫曼编码6.4.4 哈夫曼算法的实现第七章 图教学目的和要求：掌握图的定义和术语；熟练掌握图的存储结构及深度和广度搜索算法及其实现；了解最短路径算法；掌握拓扑排序算法。7.1 图的概念和术语7.2 图的存储结构 7.3 图的遍历7.3.1 深度优先搜索遍历7.3.2 广度优先搜索遍历7.4 图的应用7.4.1 生成树和最小生成树7.4.2 拓扑排序7.4.3 最短路径7.4.3.1求从一个顶点到其他各顶点的最短路径7.4.3.2 求每一对顶点之间的最短路径第八章 查找教学目的和要求：熟练掌握静态查找表的查找算法及其实现，熟练掌握二叉排序树的插入和查找算法及其实现；掌握哈希表的造表方法；了解各种哈希函数和处理冲突的方法。8.1 检索的基本概念8.2 线性表的检索（静态查找表）8.2.1 顺序检索8.2.2 折半检索8.2.3 分块检索8.3 树表的检索 （动态查找）8.3.1 二叉排序树8.3.2 平衡的二叉检索树8.4 散列表8.4.1 Hash检索技术8.4.2 哈希表的检索及分析第九章 排序教学目的和要求：熟练掌握简单的排序方法的算法设计及其实现；掌握快排序和堆排序算法；了解外排序方法；掌握各种排序的特点、时间复杂度和空间复杂度。9.1 排序的基本概念9.2 三种简单排序方法9.2.1 直接插入顺序9.2.2 冒泡排序9.2.3 简单选择排序9.3 快速排序9.4 堆排序9.5 归并排序9.6 基数排序9.7 内部排序方法的比较和选择 第十章 文件教学目的和要求：掌握各种文件的组织方式和操作方法。10.1 文件的基本概念10.2 顺序文件10.3 索引文件和索引顺序文件10.4 哈希文件10.5 倒排文件四、学时分配教学时间分配表章序课程内容理论课时实验课时习题课第一章绪论2第二章线性表84第三章栈和队列422第四章串2第五章数组和广义表42第六章树622第七章图622第八章查找42第九章排序62第十章文件2复习2总计46166五、作业内容 1