《数据结构与算法（C）》课程教学大纲（2021版）课程编码：UY401204课程名称：数据结构与算法（C）2学分：总学时：3232实验学时0理论学时适用专业：计算机科学与技术、电子信息工程、物联网工程、网络工程等先修课程：C语言程序设计后续课程：操作系统、数据库原理、人工智能导论等一、课程简介《数据结构》是介于数学、计算机硬件和计算机软件之间的一门计算机科学与技术专业的核心课程，是操作系统、数据库原理、编译原理、软件工程、人工智能等课程的基础。数据结构技术广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。通过本课程的学习，使学生了解软件分析阶段、设计阶段、编码阶段的若干基本问题，明确数据结构的内容包括抽象、实现和评价三个层次，即五个基本组成“要素”逻辑结构，存储结构、基本运算、算法及不同数据结构的比较与算法分析，初步具备分析问题、解决问题的能力，养成良好的程序设计风格。为学生在此领域中继续学习和研究打下坚实的基础。二、课程目标及要求本课程主要讲授内容有线性表、树、图、查找、排序和文件。目标1：掌握数据结构基本原理；撑握线性表、树、图、查找和排序。目标2：了解广义表、文件及外排序。目标3：要求学生应能够灵活运用基本数据结构及算法，学会分析研究计算机加工数据对象的特性，掌握数据结构的基本原理，在实际应用中正确运用数据结构的思路与方法，提高分析问题和解决问题的能力，三、教学内容及安排第1章概论（2学时）教学目的：（1）领会数据、数据元素和数据项的概念及其相互间的关系（2）清楚数据结构的逻辑结构、存储结构的联系与区别，以及在数据结构上施加的运算及其实现（3）理解抽象数据类型的概念（4）掌握进行简单算法分析的方法。教学重点（1）数据、数据元素、数据项（2）逻辑结构和数据结构在概念上的联系与区别1
1 《数据结构与算法（C）》课程教学大纲 （2021 版） 课程编码： UY401204 课程名称： 数据结构与算法（C） 学分： 2 总学时： 32 理论学时 32 实验学时 0 适用专业： 计算机科学与技术、电子信息工程、物联网工程、网络工程等 先修课程： C 语言程序设计 后续课程： 操作系统、数据库原理、人工智能导论等 一、课程简介 《数据结构》是介于数学、计算机硬件和计算机软件之间的一门计算机科学与技术 专业的核心课程，是操作系统、数据库原理、编译原理、软件工程、人工智能等课程的 基础。数据结构技术广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。 通过本课程的学习，使学生了解软件分析阶段、设计阶段、编码阶段的若干基本问题， 明确数据结构的内容包括抽象、实现和评价三个层次，即五个基本组成“要素”逻辑结 构，存储结构、基本运算、算法及不同数据结构的比较与算法分析，初步具备分析问题、 解决问题的能力，养成良好的程序设计风格。为学生在此领域中继续学习和研究打下坚 实的基础。 二、课程目标及要求 本课程主要讲授内容有线性表、树、图、查找、排序和文件。 目标 1：掌握数据结构基本原理；撑握线性表、树、图、查找和排序。 目标 2：了解广义表、文件及外排序。 目标 3：要求学生应能够灵活运用基本数据结构及算法，学会分析研究计算机加工 数据对象的特性，掌握数据结构的基本原理，在实际应用中正确运用数据结构的思路与 方法，提高分析问题和解决问题的能力。 三、教学内容及安排 第 1 章 概论 （2 学时） 教学目的： （1）领会数据、数据元素和数据项的概念及其相互间的关系 （2）清楚数据结构的逻辑结构、存储结构的联系与区别，以及在数据结构上施加的 运算及其实现 （3）理解抽象数据类型的概念 （4）掌握进行简单算法分析的方法。 教学重点 （1）数据、数据元素、数据项 （2）逻辑结构和数据结构在概念上的联系与区别
（3）运算的概念（4）存储结构及其三个组成部分（5）抽象数据类型和数据抽象（6）评价算法优劣的标准及方法教学难点（1）区别算法与程序（2）逻辑结构、存储结构的联系与区别（3）抽象数据类型与数据抽象（4）算法的时间复杂度分析1.1数据结构的概念1.2抽象数据类型1.3算法和算法分析第2章线性表（6学时）教学目的：（1）理解线性表的定义及其运算（2）理解顺序表和链表的定义、组织形式、结构特征和类型说明（3）掌握在这两种表上实现的插入、删除和按值查找的算法（4）了解循环链表、双（循环）链表的结构特点和在其上施加的插入、删除等操作教学重点：（1）线性表的定义及逻辑上的特点（2）顺序表上插入、删除和定位运算的实现（3）单链表的结构特点及类型说明（4）头指针和头结点的作用及区别（5）指针操作（6）定位、删除、插入运算在单链表上的实现（7）循环链表、双链表的结构特点（8）循环链表、双链表上删除与插入运算的实现教学难点：（1）线性表与线性结构的联系与区别（2）头结点在链表中的作用：指针操作（3）删除、插入运算中的指针操作顺序（4）双链表上指针的操作顺序2.1线性表逻辑结构（2学时）2.1线性表的顺序存储及运算实现（2学时2.3线性表的链式存储和实现（2学时）2
2 （3）运算的概念 （4）存储结构及其三个组成部分 （5）抽象数据类型和数据抽象 （6）评价算法优劣的标准及方法 教学难点 （1）区别算法与程序 （2）逻辑结构、存储结构的联系与区别 （3）抽象数据类型与数据抽象 （4）算法的时间复杂度分析 1.1 数据结构的概念 1.2 抽象数据类型 1.3 算法和算法分析 第 2 章 线性表 （6 学时） 教学目的： （1）理解线性表的定义及其运算 （2）理解顺序表和链表的定义、组织形式、结构特征和类型说明 （3）掌握在这两种表上实现的插入、删除和按值查找的算法 （4）了解循环链表、双(循环)链表的结构特点和在其上施加的插入、删除等操作 教学重点： （1）线性表的定义及逻辑上的特点 （2）顺序表上插入、删除和定位运算的实现 （3）单链表的结构特点及类型说明 （4）头指针和头结点的作用及区别 （5）指针操作 （6）定位、删除、插入运算在单链表上的实现 （7）循环链表、双链表的结构特点 （8）循环链表、双链表上删除与插入运算的实现 教学难点： （1）线性表与线性结构的联系与区别 （2）头结点在链表中的作用；指针操作 （3）删除、插入运算中的指针操作顺序 （4）双链表上指针的操作顺序 2.1 线性表逻辑结构（2 学时） 2.1 线性表的顺序存储及运算实现（2 学时） 2.3 线性表的链式存储和实现（2 学时）
第3章栈和队列（4学时）教学目的：（1）理解栈的定义、特征及在其上所定义的基本运算（2）掌握在两种存储结构上对栈所施加的基本运算的实现（3）理解队列的定义、特征及在其上所定义的基本运算（4）了解在两种存储结构上对队列所施加的基本运算的实现教学重点：（1）栈的定义及逻辑特点（2）栈上的基本运算（3）栈的顺序存储结构及运算实现（4）栈的链式存储结构（5）入栈、出栈等运算在链栈上的实现（6）队列的定义及逻辑特点（7）队列上的基本运算（8）队列的顺序存储结构及其上的运算实现（9）队列的链式存储结构（10）入队、出队等运算在链队列上的实现教学难点：（1）顺序栈的溢出判断条件（2）循环队列的队空、队满判断条件（3）循环队列上的插入、删除操作3.1栈3.2栈应用举例3.3队列3.4队列应用举例第4章串（2学时）教学目的：（1）了解串的定义（2）理解和领会串的存储方式（3）掌握常用的串运算教学重点：（1）串的基本概念、基本运算（2）串的两种存储方式（3）串的模式匹配算法教学难点：3
3 第 3 章 栈和队列 （4 学时） 教学目的： （1）理解栈的定义、特征及在其上所定义的基本运算 （2）掌握在两种存储结构上对栈所施加的基本运算的实现 （3）理解队列的定义、特征及在其上所定义的基本运算 （4）了解在两种存储结构上对队列所施加的基本运算的实现 教学重点： （1）栈的定义及逻辑特点 （2）栈上的基本运算 （3）栈的顺序存储结构及运算实现 （4）栈的链式存储结构 （5）入栈、出栈等运算在链栈上的实现 （6）队列的定义及逻辑特点 （7）队列上的基本运算 （8）队列的顺序存储结构及其上的运算实现 （9）队列的链式存储结构 （10）入队、出队等运算在链队列上的实现 教学难点： （1）顺序栈的溢出判断条件 （2）循环队列的队空、队满判断条件 （3）循环队列上的插入、删除操作 3.1 栈 3.2 栈应用举例 3.3 队列 3.4 队列应用举例 第 4 章 串 （2 学时） 教学目的： （1）了解串的定义 （2）理解和领会串的存储方式 （3）掌握常用的串运算 教学重点： （1）串的基本概念、基本运算 （2）串的两种存储方式 （3）串的模式匹配算法 教学难点：
（1）串的模式匹配算法（2）串的基本运算的综合应用4.1串及其基本运算4.2串的定长顺序存储及基本运算第5章数组和广义表（2学时）教学目的：（1）理解多维数组的结构特点和在内存中的两种顺序存储方式（2）理解并掌握矩阵和特殊矩阵元素在存储区中地址的计算（3）领会稀疏矩阵的压缩方式和简单运算（4）了解广义表的定义和基本运算教学重点：（1）多维数组的逻辑结构（2）多维组的两种顺序存储方式（3）计算给定元素在存储区中的地址（4）对称矩阵、三角矩阵的压缩存储方式（5）计算给定元素在存储区中的地址（6）稀疏矩阵的三元组表表示方法教学难点：稀疏矩阵的压缩存储表示下的运算的实现5.1多维数组5.2特殊矩阵的压缩存储5.3稀疏矩阵5.4广义表第6章树和二叉树（6学时）教学目的：（1）深刻理解二叉树的定义、性质及其存储方法（2）熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义（3）理解并掌握二叉树的三种遍历算法（4）了解二叉树的线索化方法（5）运用二叉树的遍历方法解决相关的应用问题教学重点：（1）二叉树的定义、逻辑特点及五种基本形态（2）二叉树的五个性质（3）在二叉树上定义的基本运算（4）二叉树的链式存储结构及其类型说明4
4 （1）串的模式匹配算法 （2）串的基本运算的综合应用 4.1 串及其基本运算 4.2 串的定长顺序存储及基本运算 第 5 章 数组和广义表 （2 学时） 教学目的： （1）理解多维数组的结构特点和在内存中的两种顺序存储方式 （2）理解并掌握矩阵和特殊矩阵元素在存储区中地址的计算 （3）领会稀疏矩阵的压缩方式和简单运算 （4）了解广义表的定义和基本运算 教学重点： （1）多维数组的逻辑结构 （2）多维组的两种顺序存储方式 （3）计算给定元素在存储区中的地址 （4）对称矩阵、三角矩阵的压缩存储方式 （5）计算给定元素在存储区中的地址 （6）稀疏矩阵的三元组表表示方法 教学难点： 稀疏矩阵的压缩存储表示下的运算的实现 5.1 多维数组 5.2 特殊矩阵的压缩存储 5.3 稀疏矩阵 5.4 广义表 第 6 章 树和二叉树 （6 学时） 教学目的： （1）深刻理解二叉树的定义、性质及其存储方法 （2）熟练掌握二叉树的二叉链表存储方式、结点结构和类型定义 （3）理解并掌握二叉树的三种遍历算法 （4）了解二叉树的线索化方法 （5）运用二叉树的遍历方法解决相关的应用问题 教学重点： （1）二叉树的定义、逻辑特点及五种基本形态 （2）二叉树的五个性质 （3）在二叉树上定义的基本运算 （4）二叉树的链式存储结构及其类型说明
（5）二叉树的顺序存储结构及其类型说明（6）二叉树链式存储结构的组织方式（7）二叉树的三种遍历方法及其算法（8）以遍历为基础在二叉树上实现的几种运算（9）哈夫曼树和哈夫曼算法教学难点：（1）二叉树的递归定义（2）二叉树链式存储结构的组织方式（3）三种遍历的主要区别（4）二叉树上的复杂运算（5）哈夫曼算法及其应用6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4.树和森林6.5树与等价问题6.6赫夫曼树及其应用第7章图（6学时）教学目的：（1）理解图的基本概念及术语（2）掌握图的两种存储结构（邻接矩阵和邻接表）的表示方法（3）熟练掌握图的两种遍历（深度优先搜索遍历和广度优先搜索遍历）的算法思想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列（4）理解最小生成树的概念，能按Prim算法构造最小生成树（5）了解拓扑排序、关键路径、最短路径的算法思想教学重点：（1）理解图的定义、术语及其含义（2）了解各种图的邻接矩阵表示法及其类型说明（3）理解并掌握图的按深度优先搜索遍历方法和按广度优先搜索遍历方法（4）领会生成树和最小生成树的概念（5）掌握由Prim算法思想构造最小生成树按Prim算法思想（6）领会拓扑序列和拓扑排序的概念（7）了解拓扑排序的算法思想（8）了解关键路径的算法思想（9）了解最短路径的算法思想教学难点：（1）正确理解与区别图的常用术语5
5 （5）二叉树的顺序存储结构及其类型说明 （6）二叉树链式存储结构的组织方式 （7）二叉树的三种遍历方法及其算法 （8）以遍历为基础在二叉树上实现的几种运算 （9）哈夫曼树和哈夫曼算法 教学难点： （1）二叉树的递归定义 （2）二叉树链式存储结构的组织方式 （3）三种遍历的主要区别 （4）二叉树上的复杂运算 （5）哈夫曼算法及其应用 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 树与等价问题 6.6 赫夫曼树及其应用 第 7 章 图 （6 学时） 教学目的： （1）理解图的基本概念及术语 （2）掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法 （3）熟练掌握图的两种遍历(深度优先搜索遍历和广度优先搜索遍历)的算法思 想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列 （4）理解最小生成树的概念，能按 Prim 算法构造最小生成树 （5）了解拓扑排序、关键路径、最短路径的算法思想 教学重点： （1）理解图的定义、术语及其含义 （2）了解各种图的邻接矩阵表示法及其类型说明 （3）理解并掌握图的按深度优先搜索遍历方法和按广度优先搜索遍历方法 （4）领会生成树和最小生成树的概念 （5）掌握由 Prim 算法思想构造最小生成树按 Prim 算法思想 （6）领会拓扑序列和拓扑排序的概念 （7）了解拓扑排序的算法思想 （8）了解关键路径的算法思想 （9）了解最短路径的算法思想 教学难点： （1）正确理解与区别图的常用术语