《数据结构》课程大纲分析

《数据结构》课程教学大纲本课程教学大纲依据网工专业2015级人才培养方案制定。一、课程说明课程名称：数据结构课程编号：1261D03总学时：80学时总学分：5.5学分学时分配：理论56学时，上机24学时课程性质：专业必修课先修课程：C语言程序设计适用专业：网工开课学期：第二学期二、教学目标与要求教学目标：通过本课程教学，使学生了解计算机科学各领域的数据结构知识，及有关的应用软件所要用到的各种数据结构知识，理解常用的数据结构及内在的逻辑关系，掌握计算机软件设计中的算法知识，熟悉软件设计和编程技能，旨在培养初步对不同的存储结构和相应算法的对比，有一定的算法改进能力，并为学生日后从事软件开发和程序员奠定基础。同时，作为编译程序、操作系统、数据库系统课程学习的理论基础，也为学生后续课程的顺利学习提供条件。教学要求:通过本课程的学习，在基础方面，要求学生能够掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。总言之，使应用者较全面的掌握各种常用的数据结构，提高运用数据结构解决实际问题的能力。学习本课程必须具备高级语言程序设计（如C语言）的基础知识与基本技能。它的后续课程为操作系统、数据库原理等。数据结构中存储结构及基本运算的实现需要程序设计的基本知识和编程的经验及能力，本课程的大部分实例均是用C语言实现的，故要求较熟练地掌握C语言。通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。教学重点：1.掌握数据结构的概念及术语。2.掌握线性表（栈、队列）的存储结构（顺序和链式存储）、算法描述及应用。3.掌握数组的顺序存储和特殊矩阵的压缩存储。4.掌握树的基本概念和术语，掌握二叉树的基本性质和特点、存储结构及算法描述、二叉树的遍历、树、森林与二叉树的转换。掌握最优二叉树（哈夫曼树）的特点及应用。5.掌握图的基本概念和术语、存储结构（邻接矩阵、邻接表、十字链表、邻接多重表）、图的遍历、图的连通性（最小生成树）。6.掌握查找的基本概念、基于线性表的查找方法（顺序、折半）。7.掌握插入类排序（直接、折半、表、希尔等插入排序）、交换类排序（冒泡、快速排序）。教学难点：1.掌握算法时间复杂度。2.掌握线性表的顺序和链式存储存储结构、算法描述及应用。3.掌握数组的顺序存储和特殊矩阵的压缩存储。4.掌握二叉树的基本性质和特点、存储结构及算法描述、二叉树的遍历、树、森林与二叉树的转换。掌握最优二叉树（哈夫曼树）的特点及应用。5.掌握图的邻接矩阵、邻接表、十字链表、邻接多重表的存储结构、图的遍历、图的连通性（最小生成树）。7.掌握哈希表的构造、查找方法（顺序、折半、快速）。三、教学内容与目的（一）绪论1、什么是数据结构2、基本概念和术语3、抽象数据类型的表示与实现4、算法和算法分析教学目的：介绍数据结构课程的研究对象，基本术语，掌握算法的要领，描述算法的类语言。了解数据结构的发展概况及其在计算机中的地位。教学重点：1、熟悉各名词、术语的含义，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质；2、了解抽象数据类型的定义、表示和实现方法；3、理解算法五个要素的确切含义：①动态有穷性（能执行结束）；②确定性（对于相同的输入执行相同的路径）；③有输入；④有输出；⑤可行性（用以描述算法的操作都是足够基本的）；4、掌握计算语句频度和估算算法时间复杂度的方法。教学难点：1、掌握数据结构的意义及数据结构的基本内容；2、掌握数据结构及数据、数据元素等相关概念；3、掌握算法描述的方法；4、算法时间复杂度的计算。教学方法与手段：讲授式、讨论式、案例教学作业形式：作业，辅导答疑（二）线性表1、线性表的类型定义2、线性表的顺序表示和实现3、线性表的链式表示和实现4、一元多项式的表示及相加教学目的：掌握线性表的逻辑结构、顺序存储结构和链式存储结构。掌握在线性表上实现基本运算的算法。教学重点：1、线性表的定义及逻辑上的特点；2、顺序表上插入、删除和定位运算的实现；3、单链表的结构特点及类型说明；4、头指针和头结点的作用及区别；指针操作；5、定位、删除、插入运算在单链表上的实现；6、循环链表、双链表的结构特点；及其删除与插入运算的实现。教学难点：1、线性表与线性结构的联系与区别；2、线性表的顺序存储结构及其运算；3、头结点在链表中的作用和指针的操作；4、单链表存储结构定义，删除、插入运算中的指针操作顺序；5、单链表的基本运算的实现；6、循环链表、双链表上指针的操作顺序及其相关运算。教学方法与手段：讲授式、讨论式、案例教学作业形式：作业，辅导答疑（三）栈和队列1、栈的类型定义2、栈的应用举例3、栈与递归的实现4、队列的类型定义教学目的：掌握栈和队列的逻辑结构定义，掌握在两种存储结构上如何实现栈和队列的基本运算，掌握栈在程序设计中的应用。教学重点：1、栈的定义及逻辑特点；栈上的基本运算；2、栈的顺序存储结构及运算实现；链式存储结构；3、入栈、出栈等运算在链栈上的实现；4、队列的定义及逻辑特点；队列上的基本运算；5、队列的顺序存储结构及其上的运算实现；6、队列的链式存储结构；7、入队、出队等运算在链队列上的实现。教学难点：1、顺序栈基本运算的实现；2、顺序栈的溢出判断条件；3、栈的应用；4、循环队列的队空、队满判断条件；循环队列上的插入、删除操作。教学方法与手段：讲授式、讨论式、案例教学作业形式：作业，辅导答疑（四）串1、串类型的定义2、串的表示和实现3、串的模式匹配算法4、串操作应用举例教学目的：掌握字符串的存储结构，以及字符串的操作算法。教学重点：1、熟悉串的定义及串的基本操作；2、串的两种存储方式；3、字符串的运算；4、串的模式匹配算法。教学难点：1、串的基本运算的综合应用；2、串的模式匹配算法。教学方法与手段：讲授式、讨论式、案例教学作业形式：作业，辅导答疑（五）数组和广义表1、数组的定义2、数组的顺序表示和实现3、矩阵的压缩存储4、广义表的定义和存储结构5、广义表的递归算法教学目的：掌握数组的顺序存储和特殊矩阵的压缩存储。了解广义表的应用。教学重点：1、多维组的逻辑结构，两种顺序存储方式；2、计算给定元素在存储区中的地址；3、对称矩阵、三角矩阵的压缩存储方式；4、计算给定元素在存储区中的地址；5、稀疏矩阵的三元组表表示方法；6、了解广义表的定义、表示及存储。教学难点：1、了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法；2、稀疏矩阵的压缩存储表示下的运算的实现；3、了解稀疏矩阵的三类压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法；4、了解广义表的结构特点及其存储表示方法。教学方法与手段：讲授式、讨论式、案例教学作业形式：作业，辅导答疑（六）树和二叉树1、树的定义和基本术语2、二叉树3、遍历二叉树和线索二叉树4、树和森林5、回溯法与树的遍历6、赫夫曼树及其应用教学目的：掌握树的基本概念和术语，掌握二叉树的基本性质和特点、存储结构及算法描述、二叉树的遍历、树、森林与二叉树的转换。掌握最优二叉树（哈夫曼树）的特点及应用。教学重点：1、二叉树的定义、性质、逻辑特点及五种基本形态、基本运算；2、二叉树的链式存储结构、顺序存储结构及其类型说明；3、二叉树链式存储结构的组织方式；4、二叉树的三种遍历方法及其算法，以遍历为基础在二叉树上实现的几种运算；5、哈夫曼树和哈夫曼算法；森林与二叉树的转换。教学难点：1、二叉树的递归定义；2、二叉树链式存储结构的组织方式；3、三种遍历的主要区别；二叉树上的复杂运算4、森林与二叉树的转换；5、哈夫曼算法及其应用。教学方法与手段：讲授式、讨论式、案例教学作业形式：作业，辅导答疑（七）图1、图的定义和术语2、图的存储结构3、图的遍历4、图的连通性问题5、有向无环图及其应用6、最短路径教学目的：掌握图的基本概念和术语、存储结构（邻接矩阵、邻接表、十字链表、邻接多重表）、图的遍历、图的连通性（最小生成树）。理解拓扑排序及关键路径和最短路径的应用及意义。教学重点：1、理解图的定义、术语及其含义，各种图的邻接矩阵表示法及其类型说明；2、理解并掌握图的按深度优先搜索遍历方法和按广度优先搜索遍历方法；3、领会生成树和最小生成树的概念；4、掌握由Prim算法思想构造最小生成树按Prim算法思想；5、掌握拓扑序列和拓扑排序的概念，拓扑排序、关键路径、最短路径的算法思想。教学难点：1、正确理解与区别图的常用术语；2、区别图的两种存储结构的不同点及其应用场合；3、关键路径的算法思想；最短路径的算法思想。教学方法与手段：讲授式、讨论式、案例教学作业形式：作业，辅导答疑（八）查找1、静态查找表2、动态查找表3、哈希表教学目的：掌握查找的基本概念、基于线性表的查找方法（顺序、折半）。理解基于树的查找方法（二叉排序树、平衡二排序叉树）。教学重点：1、查找表的基本概念及查找原理；顺序存储结构、顺序表及其类型说明；2、查找运算在查找表和有序表上的实现；3、二叉排序树的定义、性质及各结点间的键值关系，查找算法和基本思想；4、平衡二叉排序树的概念；B-树和B+树的概念；5、散列表及散列存储和散列查找的基本思想；各种散列表的组织、解决冲突的方法；教学难点：1、理解查找表的逻辑结构是集合，它的运算以查找为核心；2、二叉排序树上的插入算法；平衡二叉树的旋转平衡算法；3、散列表上的有关算法。教学方法与手段：讲授式、讨论式、案例教学作业形式：作业，辅导答疑（九）内部排序1、插入排序2、快速排序3、选择排序4、归并排序5、基数排序6、各种内部排序方法的比较讨论教学目的：掌握插入类排序（直接、折半、表、希尔等插入排序）、交换类排序（冒泡、快速排序）。理解选择类排序、归并类排序和基数类排序。教学重点：1、排序基本概念及内排序和外排序、稳定排序和非稳定排序的区别；2、插入排序、冒泡排序、快速排序、直接选择排序、堆排序的基本思想、基本步骤和算法；3、归并排序的思想；两个有序文件合并的方法和算法；4、二路归并排序的算法和时空性能；教学难点：1、快速排序算法；2、堆排序方法。教学方法与手段：讲授式、讨论式、案例教学作业形式：作业，辅导答疑章节学时分配表章节学时分配理论实践（一）绪论1、什么是数据结构2、基本概念和术语3、抽象数据类型的表示与实现4、算法和算法分析22（二）线性表1、线性表的类型定义2、线性表的顺序表示和实现3、线性表的链式表示和实现4、一元多项式的表示及相加86（三）栈和队列1、栈的类型定义2、栈的应用举例3、栈与递归的实现4、队列64（四）串1、串类型的定义2、串的表示和实现3、串的模式匹配算法4、串操作应用举例2（五）数组和广义表1、数组的定义2、数组的顺序表示和实现3、矩阵的压缩存储4、广义表的定义和存储结构5、广义表的递归算法4（六）树和二叉树1、树的定义和基本术语2、二叉树3、遍历二叉树和线索二叉树4、树和森林5、回溯法与树的遍历6、赫夫曼树及其应用104（七）图1、图的定义和术语2、图的存储结构3、图的遍历4、图的连通性问题1045、有向无环图及其应用6、最短路径（八）查找1、静态查找表2、动态查找表3、哈希表62（九）内部排序1、插入排序2、快速排序3、选择排序4、归并排序5、基数排序6、各种内部排序方法的比较讨论82合计80四、教学方法与手段1、理论部分以讲授法为主，结合讨论及课堂练习实现教学目的。2、传统教学手段与多媒体等现化手段相结合。3、重视实验教学，要求学生利用一切可利用的时间和机会去实验室，实现并验证书本上的各种算法，达到真正实现教学目的。五、考核与成绩评定方式本课程为考试科目，课程结束后采用闭卷考试。考核总成绩中，平时成绩占30%（出勤占20%，学习态度占10%），期末考试占70%；考核范围为本大纲规定的基本要求教学内容。六、教材与主要参考书目（一）教