《数据结构》教学大纲

PAGEPAGE11《数据结构》教学大纲一、课程名称《数据结构》二、课程性质信息与计算科学专业必修课，数学及应用数学专业限选课。三、课程教学目的使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，学会分析研究计算机加工的数据对象的特征，以便选择适当的数据结构和存储结构以及相应的算法，并初步掌握算法的时间分析和空间分析的技巧。另一方面，学习本课程的过程也是进行复杂程序设计的训练过程，要求学生书写的程序结构清楚、正确易读。培养基本的、良好的程序设计技能，编制高效可靠的程序，为掌握数据结构在其他学科中的广泛应用奠定良好的基础。通过本课程的学习，应达到知识和技能两方面的目的：1.知识方面：从数据结构及其实现这两个层次及其相互关系的角度，系统学习和掌握常用数据结构（线性表、栈、队列、二叉树、图、查找表和文件）及其不同的实现（不同的存储结构和算法），了解并掌握分析、比较和选择不同数据结构及不同存储结构、不同运算实现的原则和方法，为后继课程的学习打好基础。2.技能方面：系统学习和掌握在不同存储结构上实现的不同的算法及其设计思想，从中体会并掌握结构选择和算法设计的思维方式和技巧，提高分析问题和解决问题的能力。四、课程教学原则与教学方法学生往往感到数据结构课程的内容多、难度大。努力做到以下几点有助于改善学习效果。1.注意知识体系。数据结构课程中的知识本身具有良好的结构性。从总体上说，课程的主要内容是围绕着线性表、栈、队列、二叉树、图、查找表和文件这九种常用的数据结构和排序这种常用的运算来组织的，对每种数据结构又是从定义（逻辑结构和基本运算）和实现（存储结构和运算实现）这两个层次以及他们之间的联系的角度加以介绍的。对排序算法，讨论了它的各种典型、常见的实现算法。按上述体系对课程中的具体内容加以分类，有助于整体上的全面把握。2.注意比较。正由于本课程中的知识具有如上所述的体系，教学中应注意从纵向和横向两个方面比较有关内容以加深学生的理解。纵向对比包括将一种数据结构与它的各种不同的实现加以比较；横向对比包括具有相同逻辑结构的不同数据结构的比较，同一数据结构的不同存储结构和实现同一运算的不同算法的比较，等等。3.注意循序渐进。在具体讲解存储结构和算法之前，首先讲清楚基本概念和基本思想。特别是讲算法之前，讲清楚基本思想和基本步骤是极其重要的。4.要求学生做大量的练习。习题是本课程的重要组成部分，只看书不做题是不可能真正学会有关知识、更不能达到技能培养的目的。在做算法设计习题时要求学生独立设计出完整的算法，不要调用书上已有的算法，以利于编程能力的提高。5.以课堂讲授和学生上机实践相结合的方法，教学内容重点突出基本知识和基本技能，注意培养学生分析问题和解决问题的能力。五、课程总学时66学时，习题课占1/5。（蒙语授课适当增加学时）六、课程教学内容要点课程教学内容要点及建议学时分配章节序号教学内容学时1绪论42线性表103栈和队列104串5广义表自学6树和二叉树107图108自学9查找810内部排序1411外部排序自学12文件自学合计66第一章绪论（计划学时4）一、教学目的通过本章的学习，了解数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系。了解数据类型、抽象数据类型、数据抽象和信息隐蔽原则。了解算法的定义、算法的特性、算法的时间代价、算法的空间代价。能够使用C++语言编写程序二、课程内容第一节什么是数据结构了解数据结构的定义。第二节基本概念和术语1.掌握数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、结点、数据域、顺序存储结构、链式存储结构、指针、数据类型、抽象数据类型、算法的概念。理解四种基本逻辑结构的不同特点。2.了解数据结构的形式定义、抽象数据类型的实现。3.掌握算法的特性。第三节数据结构的发展简史及它在计算机科学中所处的地位了解数据结构的发展简史及它在计算机科学中所处的地位。第四节算法的描述和算法分析熟悉算法的描述方法。掌握算法设计的要求。了解算法效率的度量。三、重点、难点提示和教学手段教学重点：基本概念和术语。算法的特点。教学难点：算法效率的度量。教学手段：传统教学手段，注意讲练结合.第二章线性表（计划学时10）一、教学目的通过本章的学习，掌握线性表的逻辑特性和两类不同的存储结构，两类存储结构（顺序和链式存储结构）的描述方法，以及单链表、循环链表、双向链表的特点，线性表在顺序存储结构中实现基本运算（查找、插入、删除、合并等）的算法及分析。线性表在链式存储结构中实现基本运算（查找、插入、删除、合并等）的算法及分析，并学会何时选用何种链表的方法。二、课程内容第一节线性表的逻辑结构熟悉线性表的基本操作。了解两类归并算法的实现。第二节线性表的顺序存储结构掌握线性表顺序存储结构的特点，顺序表的表示法、基本思想、特点。区别顺序表的容量和表长。掌握插入、删除、定位、归并算法，了解时间复杂度分析。第三节线性表的链式存储结构了解顺序表的优缺点、链表的优缺点。掌握线性表链式存储结构的特点。掌握数据域、指针域、头指针、链表、单链表的概念，单链表的表示法、基本思想、特点。掌握插入、删除、取元素、归并算法，了解时间复杂度分析。了解循环链表及双向链表中基本操作的实现。第四节一元多项式的表示及其相加了解一元多项式的表示及其相加算法。三、重点、难点提示和教学手段教学重点：不同存储结构中，实现基本操作的算法。教学难点：时间复杂度分析。一元多项式的表示及其相加算法。第三章栈和队列（计划学时12）一、教学目的通过本章的学习，掌握栈的特点、表示和实现。熟悉栈的典型应用并编程实现（如：语法检查、回朔算法、递归算法、表达式求值）。掌握队列的特点、表示和实现。了解离散事件模拟。二、课程内容第一节栈了解抽象数据类型栈的定义。熟悉栈的表示和实现。掌握栈的顺序存储结构的表示，栈的初始化、入栈、出栈操作在顺序栈中的实现。第二节表达式求值熟悉语法检查、表达式求值算法。了解回朔算法、递归算法。第三节队列了解抽象数据类型队列的定义。掌握链队列的表示，初始化、入列、出列操作的实现。掌握循环队列的表示初始化、入列、出列操作的实现。三、重点、难点提示和教学手段教学重点：顺序栈中基本操作的实现。链队列中基本操作的实现。教学难点：回朔算法、递归算法。教学手段：传统教学手段，注意讲练结合.第四章串（计划学时12）一、教学目的通过本章的学习，熟悉串的七种基本操作的定义，并能利用这些基本操作实现串的其它各种操作的方法。熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。掌握串的存储结构以及在其上实现串操作的基本方法；了解串匹配的KMP算法，熟悉next函数的定义，学会手工计算给定模式串的next函数值和改进的next函数值。二、课程内容第一节串及其操作了解串的逻辑结构定义。掌握串的基本操作。第二节串的存储结构了解串的静态存储结构，动态存储结构。三、重点、难点提示和教学手段教学重点：串的逻辑结构定义。掌握串的基本操作。教学难点：解串的静态存储结构，动态存储结构。教学手段：传统教学手段，注意讲练结合.第五章数组与广义表（自学）第六章树和二叉树（自学）一、教学目的通过本章的学习，掌握树的定义和基本术语。掌握二叉树的结构特性及相应的证明方法。了解二叉树的各种存储结构特点及使用范围；掌握二叉树的各种遍历算法的递归和非递归算法。了解应用遍历算法实现二叉树的其他操作。了解二叉树的前序、中序、后序线索化，理解中序线索化过程以及在中序线索树上找出给定结点的前驱和后继的方法。了解树的定义和存储结构及树的应用举例，掌握树和二叉树的转换方法。了解最优树的特性，掌握建立最优树的方法。了解实现Huffman编码的方法。二、课程内容第一节树的结构定义和基本操作掌握树的定义，树形结构的有关术语及其含义。第二节二叉树1.掌握二叉树的逻辑结构、特点和五种基本形态。2.了解二叉树的基本运算。3.掌握二叉树性质及其证明。了解二叉链表的结点形式及其描述，二叉链表中各结点的联系方法及根指针的作用。掌握满二叉树和完全二叉树的概念。了解二叉树顺序存储结构的基本思想。第三节遍历二叉树和线索二叉树1.掌握二叉树的前序、中序、后序遍历算法。2.了解二叉树的前序、中序、后序线索化。3.理解中序线索化过程以及在中序线索树上找出给定结点的前驱和后继的方法。第四节树和森林1.了解树和森林的定义。2.掌握树和二叉树的转换方法。第五节哈夫曼树及其应用1.了解最优树的特性。2.掌握建立最优树的方法。3.了解实现Huffman编码的方法。三、重点、难点提示和教学手段教学重点：二叉树的逻辑结构、特点和五种基本形态。遍历二叉树的方法。树与二叉树的转换。建立最优树的方法。二叉树性质及其证明。教学难点：索引二叉树。教学手段：传统教学手段，注意讲练结合.第七章图（计划学时12）一、教学目的通过本章的学习，了解图的定义和术语。掌握图的四种存储结构及其构造算法。重点掌握图的两种遍历策略。了解图的连通性问题极其判断。有向无环图极其应用（拓扑排序和关键路径）。掌握两类最短路径问题的解法。二、课程内容第一节图的定义和术语了解图的定义和术语。第二节图的存储结构1.掌握图的四种存储结构。2.了解思忠存储结构的构造算法。第三节图的遍历1.掌握图的两种遍历策略。2.了解两种策略的算法实现。第四节图的连通性问题了解图的连通性问题极其判断。第五节无向图的连通分量和生成树1.了解无向图联通分量的概念。2.掌握生成树的概念。第六节最小生成树1.掌握最小生成树的概念，构造最小生成树的普里姆算法。2.了解构造最小生成树的克鲁斯卡尔算法。第五节有向无环图及其应用掌握拓扑排序及关键路径的算法。第六节最短路径掌握迪杰斯特拉算法及弗洛伊德算法。三、重点、难点提示和教学手段教学重点：四种存储结构。教学难点：遍历图的递归和非递归算法。迪杰斯特拉算法及弗洛伊德算法。克鲁斯卡尔算法。普里姆算法。教学手段：传统教学手段，注意讲练结合.第九章查找（计划学时8）一、教学目的通过本章的学习，掌握静态查找表的顺序查找和折半查找的实现。了解静态查找表的静态树表和索引查找的实现。掌握动态查找表的二叉排序树和二叉平衡树的构造和查找方法。了解B-和B+树和键树的构造和查找方法。掌握哈希表构造方法，哈希表的查找。了解衡量查找效率的平均查找长度的讨论。二、课程内容第一节静态查找表1.掌握静态查找表的顺序查找和折半查找的实现。2.了解静态查找表的静态树表和索引查找的实现。第二节动态查找表1.掌握动态查找表的二叉排序树和二叉平衡树的构造和查找方法。2.了解B-和B+树和键树的构造和查找方法。第三节哈希表1.掌握哈希表构造方法，哈希表的查找。2.了解衡量查找效率的平均查找长度的讨论。三、重点、难点提示和教学手段教学重点：静态查找表的顺序查找和折半查找的实现。动态查找表的二叉排序树和二叉平衡树的构造和查找方法。教学难点：B-和B+树和键树的构造和查找方法，教学手段：传统教学手段，注意讲练结合.第十章内部排序（计划学时8）一、教学目的通过本章的学习，了解排序的定义和基本术语。掌握各种内部排序方法的基本思想、算法特点。了解排序过程以及它们的时间复杂度分析。了解稳定排序方法和不稳定排序方法的定义及判断。二、课程内容第一节插入排序1.掌握排序的定义和基本术语。第二节快速排序1.掌握快速排序方法的基本思想、算法特点、排序过程。2.了解快速排序方法的时间复杂度分析方法。第三节选择排序1.掌握选择排序方法的基本思想、算法特点、排序过程。2.了解选择排序方法的时间复杂度分析方法。第四节归并排序了解归并排序方法的基本思想、算法特点、排序过程以及归并排序方法的时间复杂度分析方法。三、重点、难点提示和教学手段教学重点：插入、快速以及选择排序的思想和算法。教学难点：归并排序方法的时间复杂度分析方法。教学手段：传统教学手段，注意讲练结合.第十一章外部排序（自学）第十二章文件（自学）七、课程的实践教学环节要求《数据结构》的学习过程，也是进行复杂的程序设计的训练过程，上机操作、调试，以及观察算法的具体实现均是必不可少的环节。其主要目的是锻炼和培养考生实际操作技能和解决实际问题的能力