数据结构教学大纲一、说明（一）课程性质《数据结构》是计算科学专业中一门重要的基础课程。当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，如编译原理、操作系统、数据库、人工智能等课程打下厚实的知识基础，同时也提供了必要的技能训练。另外，数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。因此，《数据结构》课程在计算机专业中具有举足轻重的作用，是一门专业基础课。(二)教学目的本课程是计算机专业的必修课。通过本课程的学习，培养学生设计算法、开发程序的能力，使学生能够根据实际问题的需要，选择适当的数据结构及设计出相应的算法：通过算法设计和分析，进一步锻炼学生的动手能力，培养学生分析和解决实际问题的能力。本课程首先从抽象数据类型的角度讨论各种基本类型的数据结构及其应用：然后讨论了查找和排序的各种实现方法及其综合分析比较。通过本课程的学习将为后续课程的学习及软件设计水平的提高打下良好的基础。（三）教学内容第1章绪论、第2章线性表、第3章栈和队列、第4章串、第5章数组与广义表、第6章树和二叉树第7章图、第8章查找、第9章内部排序四）教学时数课程教学总学时数为90学时（含课内实验），6学分，各章学时分配如下：讲授内容讲授学时4第1章绪论12第2章线性表10第3章栈和队列4第4章串8第5章数组与广义表14第6章树和二叉树第7章图14第8章查找1212第9章内部排序（五）教学方式以课堂讲授为主，课堂讨论和课下自学为辅。二、本文第一章绪论教学要点：了解数据结构的研究对象，理解数据结构有关概念的含义，掌握数据结构的分类及表示。熟悉类c语言的书写规范，理解算法的重要特性及算法设计的要求，掌握计算语句频度和估算时间复杂度
数据结构教学大纲 一、说明 (一)课程性质 《数据结构》是计算科学专业中一门重要的基础课程。当用计算机来解决实际问题时，就要涉及到数据的表 示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课 程，如编译原理、操作系统、数据库、人工智能等课程打下厚实的知识基础，同时也提供了必要的技能训练。另 外，数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。因此，《数据结构》课程 在计算机专业中具有举足轻重的作用，是一门专业基础课。 (二)教学目的 本课程是计算机专业的必修课。通过本课程的学习，培养学生设计算法、开发程序的能力，使学生能够根据实 际问题的需要，选择适当的数据结构及设计出相应的算法；通过算法设计和分析，进一步锻炼学生的动手能力，培 养学生分析和解决实际问题的能力。本课程首先从抽象数据类型的角度讨论各种基本类型的数据结构及其应用；然 后讨论了查找和排序的各种实现方法及其综合分析比较。通过本课程的学习将为后续课程的学习及软件设计水平的 提高打下良好的基础。 (三)教学内容 第1章 绪论、第2章 线性表、第3章 栈和队列、第4章 串、第5章数组与广义表、第6章 树和二叉树、 第7章 图、第8章 查找、第9章 内部排序 (四)教学时数 课程教学总学时数为90学时（含课内实验），6学分，各章学时分配如下： 讲授内容 讲授学时 第1章 绪论 4 第2章 线性表 12 第3章 栈和队列 10 第4章 串 4 第5章 数组与广义表 8 第6章 树和二叉树 14 第7章 图 14 第8章 查找 12 第9章 内部排序 12 (五)教学方式 以课堂讲授为主，课堂讨论和课下自学为辅。 二、本文 第一章 绪论 教学要点: 了解数据结构的研究对象，理解数据结构有关概念的含义，掌握数据结构的分类及表示。熟悉 类c语言的书写规范，理解算法的重要特性及算法设计的要求，掌握计算语句频度和估算时间复杂度
的方法。教学时数：4学时教学内容：1.1什么是数据结构（1学时)一、数值问题与非数值问题二、《数据结构》的发展史1.2基本概念和术语（1学时）一、数据、数据元素、数据对象、数据结构二、数据结构的形式定义三、逻辑结构、存储结构四、数据类型、抽象数据类型1.3抽象数据类型的表示与实现（1.3、1.4共1学时）一、类c语言二、抽象数据类型表示与实现示例1.4算法和算法分析一、算法二、算法设计的要求三、算法效率的度量四、算法的存储空间需求（1学时)考核要求：数据结构的三个方面、数据结构的四种基本存储方法、算法的五个要素及算法时间、空间复杂度的运算。第二章线性表教学要点：了解线性表逻辑结构的特征；重点掌握线性表的顺序存储结构和链式存储结构，它们如何表达线性表中数据元素之间的结构关系；如何用类C语言描述它们的类型定义；掌握在顺序存储结构下，线性表的基本操作的算法；掌握在链式存储结构下，线性表的基本操作的算法；能够从时间复杂度的角度，比较线性表两类存储结构的不同特点及适用场合。教学时数：12学时教学内容：2.1线性表的类型定义（1学时）一、线性表的概念二、抽象数据类型线性表List的定义2.2线性表的顺序表示和实现（5学时）一、线性表的顺序存储结构二、顺序表的类型定义
的方法。 教学时数：4学时 教学内容： 1.1什么是数据结构 （1学时） 一、数值问题与非数值问题 二、《数据结构》的发展史 1.2基本概念和术语（1学时） 一、数据、数据元素、数据对象、数据结构 二、数据结构的形式定义 三、逻辑结构、存储结构 四、数据类型、抽象数据类型 1.3抽象数据类型的表示与实现（1.3、1.4共1学时） 一、类c语言 二、抽象数据类型表示与实现示例 1.4算法和算法分析 一、算法 二、算法设计的要求 三、算法效率的度量 四、算法的存储空间需求（1学时） 考核要求： 数据结构的三个方面、数据结构的四种基本存储方法、算法的五个要素及算法时间、空间复杂度 的运算。 第二章 线性表 教学要点: 了解线性表逻辑结构的特征；重点掌握线性表的顺序存储结构和链式存储结构，它们如何表达线 性表中数据元素之间的结构关系；如何用类C语言描述它们的类型定义；掌握在顺序存储结构下，线 性表的基本操作的算法；掌握在链式存储结构下，线性表的基本操作的算法；能够从时间复杂度的 角度，比较线性表两类存储结构的不同特点及适用场合。 教学时数：12学时 教学内容： 2.1 线性表的类型定义（1学时） 一、线性表的概念 二、抽象数据类型线性表List的定义 2.2 线性表的顺序表示和实现（5学时） 一、线性表的顺序存储结构 二、顺序表的类型定义
三、顺序表的基本操作算法四、上机实验完成顺序表的基本操作2.3线性表的链式表示和实现（5学时）一、线性链表二、循环链表三、双向链表四、上机实验完成单链表的基本操作2.4一元多项式的表示及相加（1学时）一、抽象数据类型一元多项式的定义二、抽象数据类型一元多项式的实现三、一元多项式的相加考核要求：线性表的逻辑结构特征、常见的线性表的六种基本运算，并可以根据这些基本运算组合得到更复杂的运算；单链表的特征、图形表示法、单链表的各种算法实现，并能运用这些算法解决一些简单问题：循环链表的特征、双链表的特征以及它们的主要算法实现。第三章栈和队列教学要点：理解掌握栈与队列的结构特征和操作特点：掌握栈与队列的顺序存储结构和链式存储结构，以及如何用C语言描述它们的类型定义；掌握在两种存储结构下，栈与队列的基本操作的算法。理解栈的后进先出的特点及在程序设计中的应用。掌握循环队列的入队、出队算法以及循环队列队空、队满的判别条件。教学时数：10学时教学内容：3.1栈（3学时）一、抽象数据类型栈的定义二、栈的表示和实现3.2栈的应用举例（3学时）一、数制转换二、括号匹配的检验三、行编辑程序四、表达式求值五、上机实验栈的基本操作3.3队列（4学时)一、抽象数据类型队列的定义二、链队列三、循环队列
三、顺序表的基本操作算法 四、上机实验完成顺序表的基本操作 2.3 线性表的链式表示和实现（5学时） 一、线性链表 二、循环链表 三、双向链表 四、上机实验完成单链表的基本操作 2.4 一元多项式的表示及相加（1学时） 一、抽象数据类型一元多项式的定义 二、抽象数据类型一元多项式的实现 三、一元多项式的相加 考核要求： 线性表的逻辑结构特征、常见的线性表的六种基本运算，并可以根据这些基本运算组合得到更复 杂的运算；单链表的特征、图形表示法、单链表的各种算法实现，并能运用这些算法解决一些简单 问题；循环链表的特征、双链表的特征以及它们的主要算法实现。 第三章 栈和队列 教学要点: 理解掌握栈与队列的结构特征和操作特点；掌握栈与队列的顺序存储结构和链式存储结构，以及 如何用C语言描述它们的类型定义；掌握在两种存储结构下，栈与队列的基本操作的算法。理解栈的 后进先出的特点及在程序设计中的应用。掌握循环队列的入队、出队算法以及循环队列队空、队满 的判别条件。 教学时数：10学时 教学内容： 3.1栈（3学时） 一、抽象数据类型栈的定义 二、栈的表示和实现 3.2栈的应用举例（3学时） 一、数制转换 二、括号匹配的检验 三、行编辑程序 四、表达式求值 五、上机实验栈的基本操作 3.3队列（4学时） 一、抽象数据类型队列的定义 二、链队列 三、循环队列
四、上机实验队列的基本操作考核要求：理解栈的逻辑结构定义，掌握在顺序栈存储结构上如何实现栈的基本运算如入栈出栈等操作，了解链式栈上同样的操作如何实现第四章串教学要点：了解串的基本操作，了解利用基本操作实现串的其它操作的方法：掌握在串的堆分配存储结构下，串的基本操作算法。教学时数：4学时教学内容：4.1串类型的定义（1学时）一、什么是串、串的有关术语二、串的抽象数据类型定义4.2串的表示和实现（2学时）一、定长顺序存储表示二、堆分配存储表示4.3串的模式匹配算法（1学时）一、求子串位置的定位函数二、模式匹配的一种改进算法考核要求：串的逻辑结构及串上的基本运算第五章数组和广义表教学要点：了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。掌握对特殊矩阵进行压缩存储时的下标变换公式。领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。掌握广义表的结构特点及其存储表示方法，学会对非空广义表进行分解的分析方法。教学时数：8学时教学内容：5.1数组的定义（5.1、5.2共3学时）一、什么是数组二、数组的抽象数据类型定义5.2数组的顺序表示和实现一、以行为主序的方式数组的顺序存储结构二、以列为主序的方式数组的顺序存储结构5.3矩阵的压缩存储（2学时）一、特殊矩阵
四、上机实验队列的基本操作 考核要求： 理解栈的逻辑结构定义，掌握在顺序栈存储结构上如何实现栈的基本运算如入栈出栈等操作，了 解链式栈上同样的操作如何实现 第四章 串 教学要点: 了解串的基本操作，了解利用基本操作实现串的其它操作的方法；掌握在串的堆分配存储结构 下，串的基本操作算法。 教学时数：4学时 教学内容： 4.1 串类型的定义（1学时） 一、什么是串、串的有关术语 二、串的抽象数据类型定义 4.2 串的表示和实现（2学时） 一、定长顺序存储表示 二、堆分配存储表示 4.3串的模式匹配算法（1学时） 一、求子串位置的定位函数 二、模式匹配的一种改进算法 考核要求： 串的逻辑结构及串上的基本运算 第五章 数组和广义表 教学要点: 了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。掌握对特 殊矩阵进行压缩存储时的下标变换公式。领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方 法。掌握广义表的结构特点及其存储表示方法，学会对非空广义表进行分解的分析方法。 教学时数：8学时 教学内容： 5.1 数组的定义（5.1、5.2共3学时） 一、什么是数组 二、数组的抽象数据类型定义 5.2 数组的顺序表示和实现 一、以行为主序的方式数组的顺序存储结构 二、以列为主序的方式数组的顺序存储结构 5.3 矩阵的压缩存储（2学时） 一、特殊矩阵
二、稀疏矩阵5.4广义表的定义（1学时）一、广义表的概念二、广义表的抽象数据类型定义5.5广义表的存储结构（2学时)一、设定结点的结构二、广义表的头尾链表存储表示考核要求：掌握数组的类型定义和表示；了解特殊矩阵和稀疏矩阵存储方法：掌握广义表的结构特点第六章树和二叉树教学要点：理解树的逻辑结构与基本概念，掌握二叉树的结构特征，熟悉二叉树的各种存储结构，掌握二叉链表存储结构。掌握各种遍历策略的递归算法，能灵活运用遍历算法实现二叉树的其他操作。熟悉树的各种存储结构及其特点，掌握树和二叉树的转换方法，掌握树的遍历方法；了解哈夫曼树的特性，掌握构造哈夫曼树和哈夫曼编码的方法。教学时数：14学时教学内容：6.1树的定义和基本术语（1学时)一、树的概念、树的表示、树的基本术语二、树的抽象数据类型定义6.2二叉树（4学时)一、二叉树的定义二、二叉树的性质三、二叉树的存储结构6.3遍历二叉树和线索二叉树（3学时)一、遍历二叉树二、线索二叉树三、上机实验二叉树的基本操作6.4树和森林（4学时)一、树的存储结构二、森林与二叉树的转换三、树和森林的遍历6.5赫夫曼树及其应用（2学时)一、赫夫曼树二、赫夫曼编码考核要求：
二、稀疏矩阵 5.4 广义表的定义（1学时） 一、广义表的概念 二、广义表的抽象数据类型定义 5.5 广义表的存储结构（2学时） 一、设定结点的结构 二、广义表的头尾链表存储表示 考核要求： 掌握数组的类型定义和表示；了解特殊矩阵和稀疏矩阵存储方法；掌握广义表的结构特点 第六章 树和二叉树 教学要点: 理解树的逻辑结构与基本概念，掌握二叉树的结构特征，熟悉二叉树的各种存储结构，掌握二叉 链表存储结构。掌握各种遍历策略的递归算法，能灵活运用遍历算法实现二叉树的其他操作。熟悉 树的各种存储结构及其特点，掌握树和二叉树的转换方法，掌握树的遍历方法；了解哈夫曼树的特 性，掌握构造哈夫曼树和哈夫曼编码的方法。 教学时数：14学时 教学内容： 6.1 树的定义和基本术语（1学时） 一、树的概念、树的表示、树的基本术语 二、树的抽象数据类型定义 6.2 二叉树（4学时） 一、二叉树的定义 二、二叉树的性质 三、二叉树的存储结构 6.3 遍历二叉树和线索二叉树（3学时） 一、遍历二叉树 二、线索二叉树 三、上机实验二叉树的基本操作 6.4 树和森林（4学时） 一、树的存储结构 二、森林与二叉树的转换 三、树和森林的遍历 6.5 赫夫曼树及其应用（2学时） 一、赫夫曼树 二、赫夫曼编码 考核要求：