数据结构与算法理论教学大纲.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 算法构造最小生成树；⑸领会并掌握拓扑排序、关键路径、最短路径的算法思想。

三、教学要求掌握图的基本概念及术语；图的两种存储结构(邻接矩阵和邻接表)的表示方法；图的遍历(深度优先搜索遍历和广度优先搜索遍历)算法；最小生成树的构造；拓扑排序、关键路径以及最短路径算法四、教学内容提要图是另一种重要的、比树复杂的非线性数据结构在树中，结点之间有着明显的层次关系，并且每个结点只与上层的双亲(只有一个结点)有联系、与下一层多个孩子。