广西民族学院理学院2014-2015第一学期课程教学大纲之数据结构教学大纲的格式.doc

数据结构Data Structures【课程编号】BZ25153【课程类别】专业基础课【学分数】5【开设学期】4 【学时数】80(讲授56学时，上机24学时) 【编写日期】2014-5-22【适用专业】计算机科学与技术、软件工程、信息与计算科学【先修课程】计算机文化基础、离散数学、c语言程序设计一、教学目的、任务“数据结构”是介于数学、计算机软件、硬件三者之间的一门核心课程，是编译程序、操作系统、数据库系统及其它软件设计的重要技术基础，也是计算机科学的一门综合性的专业基础课。本课程向学生介绍各种常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论它们在计算机中的存储表示以及相关运算的算法实现方法，并对各种算法时间复杂度和空间复杂度进行分析；讨论几种基本的查找、排序算法，并对它们的时空效率进行分析比较。二、课程教学的基本要求通过本课程的学习，要求学生熟悉各种基本数据结构的特点、存储表示及相关运算的算法实现及典型应用，熟练掌握几种基本的查找、排序算法，培养同学根据实际问题的要求，选择合适的数据结构设计算法的能力；能够多做、多练、多见、多上机实践，融会贯通，掌握复杂程序设计的技巧和方法，并能够对一般算法进行时空效率的分析。三、教学学内容和学时分配（一）绪论（4学时） 主要内容：1 什么是数据结构2 基本概念和术语3 数据结构的发展史及它在计算机科学中所处的地位4 算法的描述和算法分析教学要求：了解数据结构的基本概念；掌握计算语句频度和估算算法时间复杂度的方法。（二）线性表（6学时+4学时） 主要内容：1.线性表的逻辑结构2.线性表的顺序存储结构3.线性表的链式存储结构4.一元多项式的表示及相加教学要求：了解线性表的逻辑结构特性，掌握在顺序表及各种链表结构中实现线性表操作的基本方法。实验内容：1.以顺序表为有序表L的存储结构，将x插入L中，要求保持该表的有序性。 2.以单链表为有序表L的存储结构，将X插入L中，要求保持该表的有序性。（三）栈和队列（4学时+2学时） 主要内容：1.栈2.表达式求值3.队列教学要求：熟练掌握栈和队列的顺序表示、链表表示以及相应操作的实现，并能正确应用它们解决实际问题。实验内容：利用顺序栈，判别表达式中(、)是否配对出现。（四）串（4学时+2学时） 主要内容：1.串及其操作2.串的存储结构3.串基本操作的实现4.串操作应用举例教学要求：理解串的基本操作的定义，掌握在串的顺序存储结构上实现串的各种操作的方法。实验内容：实现静态存储串的INSERT（S，POS，T）或DELETE（S，POS，LEN）操作。（五）数组和广义表（4学时）主要内容：1.数组的定义和运算2.数组的顺序存储结构3.矩阵的压缩存储4.广义表的定义5.广义表的存储结构教学要求：理解数组的概念，了解特殊矩阵的压缩存储方法。（六）树和二叉树（8学时+6学时）主要内容：1.树的结构定义和基本操作2.二叉树3.遍历二叉树和线索二叉树4.树和森林5.哈夫曼树及其应用教学要求：了解树和森林的概念和性质；熟练掌握二叉树的结构特性及二叉树的遍历方法；掌握建立哈夫曼树和哈夫曼编码的方法。实验内容：1.以二叉链表为存储结构，实现二叉树的建立及前、中、后遍历操作。 2.以二叉链表为存储结构，求二叉树每个结点的层次及总结点数。(七) 图（10学时+6学时）主要内容：1.图的定义和术语2.图的存储结构3.图的遍历4.图的连通性问题5.有向无环图及其应用 6.最短路径教学要求：理解图的基本概念，熟悉图的各种存储结构及其构造算法；熟练掌握图的两种搜索路径的遍历。实验内容：1.以数组表示法为图的存储结构，求图中顶点的度数。2.以邻接表为图的存储结构，实现图的广度或深度遍历操作。（八）查找（8学时+2学时）主要内容：1. 静态查找表2. 动态查找表3. 哈希表教学要求：熟练掌握顺序表、二叉排序树和哈希表的查找算法及其性能分析方法。实验内容：实现哈希表的建立与查找算法。（九）内部排序（8学时+2学时） 主要内容：1概述2插入排序3快速排序4选择排序5归并排序6基数排序5 各种内部排序方法的比较讨论教学要求：掌握插入排序、交换排序、选择排序、归并排序的方法及其性能分析方法；了解基数排序方法及其性能分析方法。 实验内容：实现快速排序算法。 四、教学重点、难点及教学方法教学重点、难点： 1绪论：重点是了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及其相互关系，难点是算法复杂度的分析方法。2线性表：重点是熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间复杂性分析，难点是能够使用所学到的基本知识设计有效算法解决与线性表相关的应用问题。3栈和队列：重点是掌握栈和队列在两种存储结构上实现的基本运算，难点是循环队列中对边界条件的处理。4串：重点是掌握串上实现的模式匹配算法，这也是本章的难点。5数组和广义表：重点是熟悉多维数组的存储、矩阵的压缩存储方式，难点是稀疏矩阵压缩存储方式下算法的实现。6树：重点是掌握二叉树的遍历算法及其应用，难点是利用二叉树的遍历算法思想设计解决与二叉树相关的应用问题。7图：重点是掌握图在邻接矩阵和邻接表上实现的遍历算法。难点是求图的最小生成树、最短路径、拓扑排序等应用算法及其时间性能分析。8查找：重点是掌握顺序查找、二分查找、二叉排序树上查找以及散列表上查找的基本思想和算法实现。9排序：重点是掌握各种排序方法的排序过程及其算法时间复杂度的分析。难点也是各种排序算法的实现思想和实现方法。教学方法：在课堂教学中以“逻辑结构存储结构基本运算的实现典型应用”为主线，贯穿于各种数据结构的讲授中。以“分析算法运用语言描述算法进行算法分析”为思路，解析各种算法。在讲授中运用动画演示算法的运行过程，使学生清楚理解算法。在课堂进行理论教学时，一定要以应用为目的，同时坚持实战教学，注重培养学生动手操作和创新的能力。五、考核方式及成绩评定方式考核方式：理论部分笔试，实践部分上机检查。成绩评定方式：作业%10+实验20%+段考20%+期考50%六、教材及参考书目1严蔚敏，吴伟民. 数据结构(c语言版). 清华大学出版杜1996 2严蔚敏，吴伟民. 数据结构题集(c语言版). 清华大学出版杜1996 3黄扬铭.数据结构.科