数据结构与算法理论教学大纲.doc

数据结构与算法理论教学大纲 适用专业：计算机科学与技术课程学习对象：全日制二年级学生课时安排：48/16学时 理论/实验课程选用教材：数据结构（C语言版）严蔚敏,吴伟民编 北京：清华大学出版社 一、课程性质，目的与地位数据结构计算机科学与技术专业一门重要的专业基础课程。当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打下了厚实的知识基础，同时也提供了必要的技能训练。因此，数据结构课程在计算机应用专业中具有举足轻重的作用。本课程的任务是：在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。二、教学基本要求 掌握数据、数据元素和数据项的概念及其相互间的关系；数据结构的逻辑结构、存储结构的联系与区别以及在数据结构上施加的运算及其实现。掌握线性表的定义及其运算；顺序表和链表的定义、组织形式、结构特征和类型说明以及在这两种表上实现的插入、删除和按值查找的算法。循环链表、双(循环)链表的结构特点和在其上施加的插入、删除等操作。掌握栈和队列的定义、特征及在其上所定义的基本运算，在两种存储结构上对栈和队列所施加的基本运算的实现。掌握串的定义、存储方式和常用的串运算；多维数组的结构特点和在内存中的两种顺序存储方式，矩阵和三角矩阵元素的存储。掌握树的定义、性质及其存储方法；二叉树的二叉链表存储方式、结点结构和类型定义；二叉树的遍历算法；树、森林与二叉树间的相互转换；哈夫曼树的构造方法。掌握图的基本概念及术语；图的两种存储结构(邻接矩阵和邻接表)的表示方法；图的遍历(深度优先搜索遍历和广度优先搜索遍历)算法；最小生成树的构造；拓扑排序、关键路径以及最短路径算法。掌握查找的基本思想及查找成功和不成功的概念；在顺序表、有序表、索引表、散列表等上的查找方法和算法；二叉排序树、平衡二叉树以及B-树的概念和有关算法；散列表的构造。掌握排序的基本思想和基本概念；插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序及基数排序的基本思想、步骤及算法。(9)领会文件的基本概念；理解并掌握记录的逻辑结构和物理结构；了解文件的读写操作、检索和修改操作；了解文件组织方式的三种基本形式：顺序组织、随机组织和链组织。第一章 绪论一、教学内容相关章节1.1数据结构的发展简史 1.2什么是数据结构 1.3算法和算法的描述二、教学目标领会数据、数据元素和数据项的概念及其相互间的关系；清楚数据结构的逻辑结构、存储结构的联系与区别以及在数据结构上施加的运算及其实现；理解抽象数据类型的概念；掌握进行简单算法分析的方法。三、教学要求掌握数据、数据元素和数据项的概念及其相互间的关系；数据结构的逻辑结构、存储结构的联系与区别以及在数据结构上施加的运算及其实现。四、教学内容提要本章介绍了数据结构这门学科产生的背景、发展简史以及在计算机科学中所处的地位，重点介绍了数据结构相关的概念与术语。其中包括：数据、数据元素、逻辑结构、存储结构、数据处理、数据结构、算法设计等基本概念，同时还介绍了本书所用的算法描述语言以及介绍了如何评价算法基本方法。五、教学重点、难点教学重点：数据、数据元素、数据项；运算的概念；逻辑结构和数据结构在概念上的联系与区别；存储结构及其三个组成部分；抽象数据类型和数据抽象；评价算法优劣的标准及方法教学难点：区别算法与程序；逻辑结构、存储结构的联系与区别；抽象数据类型与数据抽象；算法的时间复杂度分析。六、课时安排（共2学时）1.1数据结构的发展简史 1.2什么是数据结构（1学时）1.3算法和算法的描述（1学时）第二章 线性表一、教学内容相关章节2.1线性表的概念及运算 2.2线性表的顺序存储 2.3线性表的链式存储2.4循环链表和双向链表 2.5应用举例二、教学目标理解线性表的定义及其运算；理解顺序表和链表的定义、组织形式、结构特征和类型说明；掌握在这两种表上实现的插入、删除和按值查找的算法；了解循环链表、双(循环)链表的结构特点和在其上施加的插入、删除等操作。三、教学要求理解线性表的定义及其运算。理解顺序表和链表的定义、组织形式、结构特征和类型说明，掌握在这两种表上实现的插入、删除和按值查找的算法。了解循环链表、双(循环)链表的结构特点和在其上施加的插入、删除等操作。四、教学内容提要线性表是数据结构课程中介绍的第一种数据结构，是软件设计中的最常用也是最基本的一种线性结构。本章是整个课程的基础，首先给出线性表的定义，相关概念和基本的运算，再分别讨论采用顺序存储方式和链式存储方式存储线性表，以及实现线性表基本运算的算法性能比较等，并通过实例说明线性表的应用。五、教学重点、难点教学重点：线性表的定义及逻辑上的特点；顺序表上插入、删除和定位运算的实现；单链表的结构特点及类型说明；头指针和头结点的作用及区别；指针操作；定位、删除、插入运算在单链表上的实现；循环链表、双链表的结构特点；及其删除与插入运算的实现。教学难点：线性表与线性结构的联系与区别；头结点在链表中的作用；指针操作；删除、插入运算中的指针操作顺序；双链表上指针的操作顺序 六、课时安排（共8学时）2.1线性表的概念及运算 （1学时） 2.2线性表的顺序存储（1学时）2.3线性表的链式存储 （2学时） 2.4循环链表和双向链表 （2学时） 2.5应用举例（2学时）第三章 栈和队列一、教学内容相关章节3.1栈 3.2栈的应用 3.3队列 3.4队列的应用二、教学目标掌握栈和队列的定义、特征及在其上所定义的基本运算，在两种存储结构上对栈和队列所施加的基本运算的实现。三、教学要求理解栈的定义、特征及在其上所定义的基本运算；掌握在两种存储结构上对栈所施加的基本运算的实现；理解队列的定义、特征及在其上所定义的基本运算；掌握在两种存储结构上对队列所施加的基本运算的实现。四、教学内容提要栈和队列是软件设计中常用的两种数据结构，它们的逻辑结构和线性表相同，其特点在于运算受到了限制：栈按“后进先出”的规则进行操作，队按“先进先出”的规则进行操作，故栈和队列也称操作受限制的线性表。本章将介绍栈和队列的逻辑结构定义、如何在两种存储结构(顺序存储结构和链式存储结构)上实现栈和队列的基本运算及栈和队列的应用。五、教学重点、难点教学重点：栈的定义及逻辑特点；栈上的基本运算；栈的顺序存储结构及运算实现；链式存储结构；入栈、出栈等运算在链栈上的实现；队列的定义及逻辑特点；队列上的基本运算；队列的顺序存储结构及其上的运算实现；队列的链式存储结构；入队、出队等运算在链队列上的实现。教学难点：顺序栈的溢出判断条件；循环队列的队空、队满判断条件；循环队列上的插入、删除操作。六、课时安排（共6学时）3.1栈（1学时） 3.2栈的应用（1学时） 3.3队列（2学时） 3.4队列的应用（2学时）第四章 串及数组一、教学内容相关章节4.1串及其运算 4.2串的存储结构 4.3串运算的实现 4.4矩阵的压缩存储 4.5应用举例应用举例 二、教学目标了解串的定义；串的存储方式；常用的串运算。理解多维数组的结构特点和在内存中的两种顺序存储方式；理解并掌握矩阵和特殊矩阵元素在存储区中地址的计算；领会稀疏矩阵的压缩方式和简单运算；三、教学要求掌握串的定义、存储方式和常用的串运算；多维数组的结构特点和在内存中的两种顺序存储方式，矩阵和三角矩阵元素的存储。四、教学内容提要随着计算机技术的发展，字符串数据成为计算机非数值处理的主要对象之一。如管理信息系统中，用户的姓名、地址、及商品的名称、价格、产地等都是字符串数据。数组是相同类型数据元素的序列，是几乎所有高级程序设计语言都支持的一种数据类型。在数据结构中，数组是一种数据结构。矩阵问题是科学计算中常遇到的问题，矩阵在程序设计中通常采用数组结构存储。一些特殊矩阵也可采用一些特殊方法存储。五、教学重点、难点教学重点：串的基本概念、基本运算，串的两种存储方式，串的模式匹配算法多维组的逻辑结构，两种顺序存储方式计算给定元素在存储区中的地址；对称矩阵、三角矩阵的压缩存储方式；计算给定元素在存储区中的地址；稀疏矩阵的三元组表表示方法。教学难点： 串的模式匹配算法；串的基本运算的综合应用稀疏矩阵的压缩存储表示下的运算的实现六、课时安排（共6学时）4.1串及其运算（1学时） 4.2串的存储结构（1学时） 4.3串运算的实现（2学时）4.4矩阵的压缩存储（1学时） 4.5应用举例（1学时）第五章 树与二叉树一、教学内容相关章节5.1树的基本概念 5.2二叉树 5.3二叉树的遍历 5.4线索二叉树5.5二叉树的应用 5.6树与二叉树的转换 5.7哈夫曼树及其应用 二、教学目标深刻理解二叉树的定义、性质及其存储方法；熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义；理解并掌握二叉树的三种遍历算法；二叉树的线索化方法；灵活运用二叉树的遍历方法解决相关的应用问题。熟练掌握森林与二叉树间的相互转换；了解树的简单应用。三、教学要求掌握树的定义、性质及其存储方法；二叉树的二叉链表存储方式、结点结构和类型定义；二叉树的遍历算法；树、森林与二叉树间的相互转换；哈夫曼树的构造方法。四、教学内容提要数据结构可以分为线性结构和非线性结构两大类。所谓非线性结构，是指在结构中至少存在一个数据元素，它具有两个或两个以上的直接后继或直接前驱。树型结构是一种非常重要的非线性结构，它用于描述数据元素之间的层次关系。本章将着重讨论二叉树的有关概念、存储结构以及二叉树的遍历、介绍了二叉树与树之间的转换方法，最后介绍了哈夫曼树及其应用。五、教学重点、难点教学重点：二叉树的定义、性质、逻辑特点及五种基本形态、基本运算；二叉树的链式存储结构、顺序存储结构及其类型说明；二叉树链式存储结构的组织方式；二叉树的三种遍历方法及其算法，以遍历为基础在二叉树上实现的几种运算；哈夫曼树和哈夫曼算法；森林与二叉树的转换。教学难点：二叉树的递归定义；二叉树链式存储结构的组织方式；三种遍历的主要区别；二叉树上的复杂运算哈夫曼算法及其应用；森林与二叉树的转换。六、课时安排（共8学时）5.1树的基本概念（1学时） 5.2二叉树（1学时） 5.3二叉树的遍历（2学时）5.4线索二叉树（1学时） 5.5二叉树的应用（1学时） 5.6树与二叉树的转换（1学时）5.7哈夫曼树及其应用（1学时）第六章 图一、教学内容相关章节6.1图的概念 6.2图的存储 6.3图的遍历 6.4最小生成树 6.5最短路径 二、教学目标理解图的基本概念及术语；掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法；熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法思想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列；理解最小生成树的概念，能按Prim算法构造最小生成树；领会并掌握拓扑排序、关键路径、最短路径的算法思想。三、教学要求掌握图的基本概念及术语；图的两种存储结构(邻接矩阵和邻接表)的表示方法；图的遍历(深度优先搜索遍历和广度优先搜索遍历)算法；最小生成树的构造；拓扑排序、关键路径以及最短路径算法。四、教学内容提要图是另一种重要的、比树复杂的非线性数据结构。在树中，结点之间有着明显的层次关系，并且每个结点只与上层的双亲(只有一个结点)有联系、与下一层多个孩子(多个结点)有联系，而同一层结点之间没有任何横向联系。但在图中，结点之间关系具有任意性，每个结点都可能与其它的结点相联系。图已经应用于众多的科技领域，如电子线路分析、寻找最短路径、工程计划分析、遗传学、社会科学等等。在计算机的应用领域，如逻辑设计、人工智能、形式语言、操作系统、编译程序以及信息检索等，图的知识都起着重要的作用。即使在我们的日常生活中，关于图的例子也随处可见，如各种交通图、线路图、结构图、流程图等实际问题的处理都可以归结为图的问题。本章将简要介绍图的基本概念、存储结构以及图的遍历，最后利用图求解最短距离间题。五、教学重点、难点教学重点：理解图的定义、术语及其含义，各种图的邻接矩阵表示法及其类型说明；理解并掌握图的按深度优先搜索遍历方法和按广度优先搜索遍历方法；领会生成树和最小生成树的概念；掌握由Prim算法思想构造最小生成树按Prim算法思想；掌握拓扑序列和拓扑排序的概念，拓扑排序、关键路径、最短路径的算法思想。教学难点： 正确理解与区别图的常用术语；区别图的两种存储结构的不同点及其应用场合；关键路径的算法思想；最短路径的算法思想。六、课时安排（共6学时）6.1图的概念 6.2图的存储（1学时）6.3图的遍历（1学时） 6.4最小生成树（2学时）6.5最短路径（2学时）第七章 查找一、教学内容相关章节7.1概述 7.2顺序查找 7.3二分法查找 7.4哈希法 二、教学目标了解查找的基本思想及查找成功和不成功的概念；掌握在顺序表、有序表、索引表、散列表等上的查找方法和算法，并能求出相应的平均查找长度；理解并掌握二叉排序树、平衡二叉树B-树的各种算法。三、教学要求掌握查找的基本思想及查找成功和不成功的概念；在顺序表、有序表、索引表、散列表等上的查找方法和算法；二叉排序树、平衡二叉树以及B-树的概念和有关算法；散列表的构造。四、教学内容提要查找是我们经常用到的一个词语，本章给出了在数据结构当中查找的含义。在了解查找的概述和一些术语的基础上，分别讨论了顺序查找和二分法查找，并通过举例比较了两种查找方法的平均查找长度。最后介绍了另一种完全不同的查找方法哈希法，讲解如何构造哈希函数和如何解决冲突问题。五、教学重点、难点教学重点：查找表的基本概念及查找原理；顺序存储结构、顺序表及其类型说明；查找运算在查找表和有序表上的实现；二叉排序树的定义、性质及各结点间的键值关系，查找算法和基本思想；平衡二叉排序树的概念；B-树和B+树的概念；散列表及散列存储和散列查找的基本思想；各种散列表的组织、解决冲突的方法；在散列表上实现查找、插入和删除运算的算法。教学难点：理解查找表的逻辑结构是集合，它的运算以查找为核心；二叉排序树上的插入算法；平衡二叉树的旋转平衡算法；散列表上的有关算法六、课时安排（共4学时）7.1概述 7.2顺序查找（1学时） 7.3二分法查找（1学时） 7.4哈希法（2学时）第八章 排序一、教学内容相关章节8.1基本概念 8.2插入排序 8.3交换排序 8.4选择排序8.5各种内排序方法的比较和选择 8.6外部排序简介 二、教学目标领会排序的基本思想和基本概念；理解并掌握插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序和基数排序的基本思想、步骤、算法及时空效率分析；了解外排序的定义和基本方法。三、教学要求掌握排序的基本思想和基本概念；插入排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序及基数排序的基本思想、步骤及算法。四、教学内容提要排序是计算机程序设计中的一种重要操作，本章介绍了排序可以分成内排序和外排序。并且详细讲解了内排序当中的插入排序、交换排序、选择排序，以及他们各自的算法思想、算法实现和算法分析。并对比的学习了对于不同的要求应该选择何种算法。最后简单介绍了一下外排序。五、教学重点、难点教学重点：排序基本概念及内排序和外排序、稳定排序和非稳定排序的区别；插入排序、冒泡排序、快速排序、直接选择排序、堆排序的基本思想、基本步骤和算法；归并排序的思想；两个有序文件合并的方法和算法；二路归并排序的算法和时空性能；教学难点：快速排序算法； 堆排序方法六、课时安排（共6学时）8.1基本概念 8.2插入排序（2学时） 8.3交换排序（1学时）8.4选择排序（1学时）8.5各种内排序方法的比较和选择（1学时）8.6外部排序简介（1学时）第九章 文件一、教学内容相关章节9.1文件的基本概念 9.2文件的操作 9.3文件的组织二、教学目标领会文件的基本概念；理解并掌握记录的逻辑结构和物理结构；了解文件的读写操作、检索和修改操作；了解文件组织方式的三种基本形式：顺序组织、随机组织和链组织。三、教学要求领会文件的基本概念；理解并掌握记录的逻辑结构和物理结构；了解文件的读写操作、检索和修改操作；了解文件组织方式的三种基本形式：顺序组织、随机组织和链组织。四、教学内容提要文件是存储在外部介质上的由大量性质相同的记录组成的集合。文件的读操作和写操作，这两种操作与具体的设备及操作系统有关，在此我们假定有专门的程序完成其功能。除此之外，还可以对文件进行检索和修改。文件在存储介质（如磁盘或磁带）上的组织方式称为物理结构。常用的文件组织方式有三种基本形式：顺序组织、随机组织和链组织。五、教学重点、难点教学重点：领会文件的基本概念；理解并掌握记录的逻辑结构和物理结构；了解文件的读写操作、检索和修改操作；了解文件组织方式的三种基本形式：顺序组织、随机组织和链组织。教学难点：理解并掌握记录的逻辑结构和物理结构；了解文件的读写操作、检索和修改操作。六、课时安排（共2学时）9.1文件的基本概念 9.2文件的操作（1学时） 9.3文件的组织（1学时）