《算法与数据结构》教学大纲课程名称：中文名称：算法与数据结构，英文名称：DataStructureandAlgorithms课程编码：151002学分：3总学时：56学时，其中，理论学时：46，上机学时：10适用专业：测控技术与仪器，自动化，电气工程及自动化先修课程：C语言程序设计执笔人：郑恭明审订人：杜红一、课程的性质、目的与任务：《算法与数据结构》是测控技术与仪器，自动化，电气工程及自动化专业的一门专业选修课。本课程主要介绍如何合理地组织各种数据、有效地存储和处理数据，正确地设计算法以及对算法进行分析和评价。本课程是计算机软件编程技术很重要的基础，尤其是培养高水平的应用程序人员和系统程序人员绝不可少的，通过该课程的学习，注重培养学生的数据抽象能力，使学生学会为实际应用所涉及的数据选择合适的逻辑结构、存储结构及其相应的操作算法，达到对实际问题的解决，使学生能够编写出正确、清晰和较高质量的算法和程序。二、教学内容、基本要求与学时分配：第一章绪论主要内容：1、什么是数据结构2、数据结构的基本概念和常用的术语3、数据结构发展的历史以及数据结构在计算机科学中地位4、算法描述和算法分析基本要求：了解数据结构的发展和地位：了解各种算法描述方法和算法设计的基本要求；理解数据结构、逻辑结构、存储结构和抽象数据类型的基本概念掌握对算法的评价标准和算法效率的度量方法；学时分配：2第二章线性表主要内容：1、线性表的逻辑结构2、线性表的顺序存储结构3、线性表的链式存储结构4、线性表应用举例基本要求：理解线性表的概念、逻辑结构特性以及两种存储结构特性，针对实际应用能从时间和空间复杂度的角度选用适当的存储结构；理解链表的应用一一稀疏多项式存储和运算：熟练掌握线性表的顺序存储结构及其各种基本运算：熟练掌握线性表的链式存储结构（单链表、循环链表、双向链表）及其各种基本运算，能在实际应用中选用适当的链表结构；学时分配：6第三章栈与队列
《算法与数据结构》教学大纲 课程名称：中文名称：算法与数据结构，英文名称： Data Structure and Algorithms 课程编码：151002 学 分：3 总 学 时：56 学时，其中，理论学时：46，上机学时：10 适用专业：测控技术与仪器，自动化，电气工程及自动化 先修课程：C 语言程序设计 执 笔 人：郑恭明 审 订 人：杜 红 一、课程的性质、目的与任务 课程的性质、目的与任务 课程的性质、目的与任务 课程的性质、目的与任务： 《算法与数据结构》是测控技术与仪器，自动化，电气工程及自动化专业的一门专业选修课。 本课程主要介绍如何合理地组织各种数据、有效地存储和处理数据，正确地设计算法以及对算 法进行分析和评价。本课程是计算机软件编程技术很重要的基础，尤其是培养高水平的应用程序人 员和系统程序人员绝不可少的，通过该课程的学习，注重培养学生的数据抽象能力，使学生学会为 实际应用所涉及的数据选择合适的逻辑结构、存储结构及其相应的操作算法，达到对实际问题的解 决，使学生能够编写出正确、清晰和较高质量的算法和程序。 二、教学内容、基本要求与学时分配 二、教学内容、基本要求与学时分配 二、教学内容、基本要求与学时分配 二、教学内容、基本要求与学时分配： 第一章 绪论 主要内容： 1、什么是数据结构 2、数据结构的基本概念和常用的术语 3、数据结构发展的历史以及数据结构在计算机科学中地位 4、算法描述和算法分析 基本要求： 了解数据结构的发展和地位； 了解各种算法描述方法和算法设计的基本要求； 理解数据结构、逻辑结构、存储结构和抽象数据类型的基本概念； 掌握对算法的评价标准和算法效率的度量方法； 学时分配：2 第二章 线性表 主要内容： 1、线性表的逻辑结构 2、线性表的顺序存储结构 3、线性表的链式存储结构 4、线性表应用举例 基本要求： 理解线性表的概念、逻辑结构特性以及两种存储结构特性，针对实际应用能从时间和空间复杂 度的角度选用适当的存储结构； 理解链表的应用——稀疏多项式存储和运算； 熟练掌握线性表的顺序存储结构及其各种基本运算； 熟练掌握线性表的链式存储结构（单链表、循环链表、双向链表）及其各种基本运算，能在实 际应用中选用适当的链表结构； 学时分配：6 第三章 栈与队列
主要内容：1、栈2、栈的应用3、栈与递归过程4、队列基本要求：了解递归的概念和递归过程的实现；掌握栈和队列的定义、表示、实现和应用：掌握栈的顺序存储结构和链式存储结构以及相应操作的实现掌握队列的顺序存储结构（循环队列）和链式存储结构的实现；熟练掌握链式栈和循环队列的操作算法；能够根据实际问题灵活使用栈和队列进行应用；学时分配：6第四章串主要内容：1、串类型的定义2、串的表示和实现3、串操作的应用举例基本要求：了解串的应用；掌握串的基本概念、顺序和链式存储结构；掌握串的各种基本运算：熟练掌握顺序存储结构上串的各种操作。学时分配：4第五章数组和广义表主要内容：1、数组的定义和运算2、数组的顺序存储结构3、矩阵的压缩存储4、广义表的定义5、广义表的存储结构基本要求：了解稀疏矩阵的三元组和十字链表存储结构和基本运算；理解稀疏矩阵和特殊矩阵进行压缩存储的方法及下标变换；理解广义表的基本概念，掌握广义表的特点及存储结构；掌握数组的两种存储表示方法，特别是以行为主的存储结构中的地址计算方法；学时分配：4第六章树与二叉树主要内容：1、树的定义2、二叉树3、遍历二叉树和线索二叉树4、数和森林5、哈夫曼树及其应用
主要内容： 1、栈 2、栈的应用 3、栈与递归过程 4、队列 基本要求： 了解递归的概念和递归过程的实现； 掌握栈和队列的定义、表示、实现和应用； 掌握栈的顺序存储结构和链式存储结构以及相应操作的实现； 掌握队列的顺序存储结构（循环队列）和链式存储结构的实现； 熟练掌握链式栈和循环队列的操作算法； 能够根据实际问题灵活使用栈和队列进行应用； 学时分配：6 第四章 串 主要内容： 1、串类型的定义 2、串的表示和实现 3、串操作的应用举例 基本要求： 了解串的应用； 掌握串的基本概念、顺序和链式存储结构； 掌握串的各种基本运算； 熟练掌握顺序存储结构上串的各种操作。 学时分配：4 第五章 数组和广义表 主要内容： 1、数组的定义和运算 2、数组的顺序存储结构 3、矩阵的压缩存储 4、广义表的定义 5、广义表的存储结构 基本要求： 了解稀疏矩阵的三元组和十字链表存储结构和基本运算； 理解稀疏矩阵和特殊矩阵进行压缩存储的方法及下标变换； 理解广义表的基本概念，掌握广义表的特点及存储结构； 掌握数组的两种存储表示方法，特别是以行为主的存储结构中的地址计算方法； 学时分配：4 第六章 树与二叉树 主要内容： 1、树的定义 2、二叉树 3、遍历二叉树和线索二叉树 4、数和森林 5、哈夫曼树及其应用
基本要求：理解树的基本概念及其存储结构：掌握线索二义树的概念、存储结构及线索化算法：掌握树和森林与二叉树间的转换，掌握树和森林的遍历算法；掌握哈夫曼树的概念、存储结构；掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算；熟练掌握二叉树的定义、性质、各种存储结构的特点及适用范围：熟练掌握二叉树的各种遍历算法；学时分配：6第七章图主要内容：1、图的定义和术语2、图的存储结构3、图的遍历4、图的连通性问题5、有向无环图及其应用6、最短路径基本要求：了解十字链表，邻接多重表等存储结构；理解图的基本概念，掌握图的存储结构：理解带权最短路径的概念，掌握几种最短路径的算法，熟练使用Dijkstra方法求最短路径；掌握构造最小生成树的方法及其算法；掌握求拓扑排序和关键路径的方法，理解其算法：熟练掌握图的深度优先和广度优先遍历算法：学时分配：6第八章查找主要内容：1、静态查找表2、动态查找表3、哈希表基本要求：理解查找及其算法的时间复杂度：理解静态查找表的概念：理解动态查找表的概念；理解哈希表的含义；掌握二叉排序树查找算法：掌握哈希函数的构造方法，哈希表的建立和查找以及处理冲突的基本方法；熟练掌握顺序查找、折半查找和分块查找算法，能对其性能进行分析；学时分配：4第九章内部排序主要内容：1、概述2、插入排序3、快速排序
基本要求： 理解树的基本概念及其存储结构； 掌握线索二叉树的概念、存储结构及线索化算法； 掌握树和森林与二叉树间的转换，掌握树和森林的遍历算法； 掌握哈夫曼树的概念、存储结构； 掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算； 熟练掌握二叉树的定义、性质、各种存储结构的特点及适用范围； 熟练掌握二叉树的各种遍历算法； 学时分配：6 第七章 图 主要内容： 1、图的定义和术语 2、图的存储结构 3、图的遍历 4、图的连通性问题 5、有向无环图及其应用 6、最短路径 基本要求： 了解十字链表，邻接多重表等存储结构； 理解图的基本概念，掌握图的存储结构； 理解带权最短路径的概念，掌握几种最短路径的算法，熟练使用 Dijkstra 方法求最短路径； 掌握构造最小生成树的方法及其算法； 掌握求拓扑排序和关键路径的方法，理解其算法； 熟练掌握图的深度优先和广度优先遍历算法； 学时分配：6 第八章 查找 主要内容： 1、静态查找表 2、动态查找表 3、哈希表 基本要求： 理解查找及其算法的时间复杂度； 理解静态查找表的概念； 理解动态查找表的概念； 理解哈希表的含义； 掌握二叉排序树查找算法； 掌握哈希函数的构造方法，哈希表的建立和查找以及处理冲突的基本方法； 熟练掌握顺序查找、折半查找和分块查找算法，能对其性能进行分析； 学时分配：4 第九章内部排序 主要内容： 1、概述 2、插入排序 3、快速排序
4、选择排序5、归并排序6、基数排序7、各种内部排序方法的比较讨论基本要求：了解内部排序的概念；了解归并排序、基数排序的算法：掌握插入类排序的算法，直接插入排序、希尔排序：掌握交换类排序的算法，冒泡排序、快速排序掌握选择类排序的算法，简单选择排序、树形选择类排序、堆排序：掌握各种排序方法的特点，能够对各种挂序算法进行评价，并能加以灵活应用学时分配：4第十章文件主要内容：1、文件的基本概念2、顺序文件3、索引文件基本要求：了解索引顺序文件、散列文件和多关键字文件的概念：理解文件的基本概念和基本操作；掌握顺序文件、索引文件的概念和组织方法：学时分配：4四、实验（上机）内容与学时分配本课程是理论性与实践性并重的课程，上机是该课实践教学环节的重要内容，它的内容覆盖了算法与数据结构的各个主要部分。通过上机可以加深对数据结构基本概念、基本理论的理解，学会如何把理论知识用于解决实际问题。将教材中所描述的抽象数据类型和算法，原则上要求学生针对实际应用进行C语言的描述，编程上机调试，获得运行结果，并作为课程考核内容的一部分。实验（上机）内容是由必做和选做两项组成，必做三个实验，共6学时；选做二个实验，共计10学时，其要求见“”其内容和学时安排分配如下：（一）必做1、线性表的存储结构定义及基本操作（2学时）（2学时）2、栈和队列的定义及基本操作（2学时）3、二叉树的定义及基本操作（二）选做（六选二）1、线性表的综合应用（2学时）2、栈和队列的综合应用（2学时）3、赫夫曼编码及其应用（2学时）4、图及其应用（2学时）5、最短路径和关键路径的研究与实现（2学时）6、查找和排序算法的实现（2学时）五、大纲说明本课程的教学由于抽象类型的描述及其算法的解析比较抽象，可配合使用动画来演示一些算法还可以配合开发的《数据结构网上课堂》进行辅助教学，其各类算法要求教师在C，C十十或VC+十环境下进行算法演示
4、选择排序 5、归并排序 6、基数排序 7、各种内部排序方法的比较讨论 基本要求： 了解内部排序的概念； 了解归并排序、基数排序的算法； 掌握插入类排序的算法，直接插入排序、希尔排序； 掌握交换类排序的算法，冒泡排序、快速排序； 掌握选择类排序的算法，简单选择排序、树形选择类排序、堆排序； 掌握各种排序方法的特点，能够对各种排序算法进行评价，并能加以灵活应用； 学时分配：4 第十章 文件 主要内容： 1、文件的基本概念 2、顺序文件 3、索引文件 基本要求： 了解索引顺序文件、散列文件和多关键字文件的概念； 理解文件的基本概念和基本操作； 掌握顺序文件、索引文件的概念和组织方法； 学时分配：4 四、实验（上机）内容与学时分配 四、实验（上机）内容与学时分配 四、实验（上机）内容与学时分配 四、实验（上机）内容与学时分配 本课程是理论性与实践性并重的课程，上机是该课实践教学环节的重要内容，它的内容覆盖了 算法与数据结构的各个主要部分。通过上机可以加深对数据结构基本概念、基本理论的理解，学会 如何把理论知识用于解决实际问题。将教材中所描述的抽象数据类型和算法，原则上要求学生针对 实际应用进行 C 语言的描述，编程上机调试，获得运行结果，并作为课程考核内容的一部分。实验 （上机）内容是由必做和选做两项组成，必做三个实验，共 6 学时；选做二个实验，共计 10 学时， 其要求见“”其内容和学时安排分配如下： （一）必做 1、线性表的存储结构定义及基本操作 （2 学时） 2、栈和队列的定义及基本操作 （2 学时） 3、二叉树的定义及基本操作 （2 学时） （二）选做（六选二） 1、线性表的综合应用 （2 学时） 2、栈和队列的综合应用 （2 学时） 3、赫夫曼编码及其应用 （2 学时） 4、图及其应用 （2 学时） 5、最短路径和关键路径的研究与实现 （2 学时） 6、查找和排序算法的实现 （2 学时） 五、大纲说明 本课程的教学由于抽象类型的描述及其算法的解析比较抽象，可配合使用动画来演示一些算法， 还可以配合开发的《数据结构网上课堂》进行辅助教学，其各类算法要求教师在 C，C＋＋或 VC＋ ＋环境下进行算法演示
六、教材及教学参考书教材：严蔚敏吴伟民著，数据结构(C语言版)。北京：清华大学出版社，2007教学参考书：1、严蔚敏吴伟民著，数据结构题集（C语言版）。北京：清华大学出版社，20032、谭浩强著，C语言程序设计（第三版）。北京：清华大学出版社，20053、徐孝凯，数据结构实用教程C/C十十描述。北京：清华大学出版社，20014、RobertL.Kruse,AlexanderJ.Ryba、DataStructuresandprogramDesigninC++(影印版)。北京：高等教育出版社，20015、Sara Baase,AllenVan Gelder，PrenticeHall,ComputerAlgorithms-IntroductiontoDesign andAnalysis。北京：高等教育出版社，2001
六、教材及教学参考书 六、教材及教学参考书 六、教材及教学参考书 六、教材及教学参考书 教材： 严蔚敏 吴伟民著，数据结构(C 语言版)。 北京：清华大学出版社，2007 教学参考书： 1、严蔚敏 吴伟民著，数据结构题集(C 语言版) 。北京：清华大学出版社，2003 2、谭浩强著，C 语言程序设计(第三版) 。北京：清华大学出版社，2005 3、徐孝凯，数据结构实用教程 C/C＋＋描述。北京：清华大学出版社，2001 4、Robert L. Kruse, Alexander J. Ryba、Data Structures and program Design in C++(影印版)。北京： 高等教育出版社，2001 5、Sara Baase, Allen Van Gelder，Prentice Hall，Computer Algorithms – Introduction to Design and Analysis。北京：高等教育出版社，2001