《数据结构与算法》课程大纲。
课程编码。学分 2分。
总学时 32学时。
课堂教学学时：32学时。
实验（上机）学时：0学时。
适用专业计算机科学与技术专业、计算机软件工程专业、物联网工程。
先修课程计算机语言(c)
一、课程的性质、目的与任务（宋体五号粗体）：
数据结构与算法是计算机程序设计的重要理论基础。也是计算机专业教学中的核心专业基础课程。它所讨论的知识内容和提倡的技术方法，对进一步学习计算机领域的其他课程、从事软件工程的开发，都有着不可替代的作用。
是从事计算机科学研究及应用的科技人员必须具备的重要基础知识。
二、教学进程安排（宋体五号粗体）：
课外学习时数原则上按课堂教学时数1:1安排。
内容宋体五号）
注：纯理论教学，实验（上机）学时标注为0。
三、教学内容与要求。
第一章绪论。
1.教学目标：了解数据结构研究的主要内容，掌握数据结构中涉及的基本概念和术语，掌握算法的概念、描述方法以及评价标准。
2.教学重点和难点：数据结构的相关基本概念，算法的概念、描述方法以及评价标准；难点：adt，算法的评价方法。
3.教学内容和要求：
第一节什么是数据结构。
第二节数据结构的基本概念和术语。
第三节抽象数据类型的表示与实现。
第四节算法和算法分析。
一、算法。二、算法设计的要求。
三、算法效率的度量。
4.教学过程与方法：讲授。
5.课外阅读资料：
1）. 严蔚敏等著。 数据结构习题集（c语言版）.清华大学出版社，1999
2）. 俆孝凯编著。 数据结构辅导与提高 .清华大学出版社，2000
3). 张乃孝编著。 算法与数据结构-c语言描述（第2版）. 高等教育出版社，2006
4). 李春葆编著。 数据结构教程。 清华大学出版社，2005
5). 李春葆编著。 数据结构教程学习指导。 清华大学出版社，2005
6). 谭浩强编著。 c语言程序设计(第2版). 清华大学出版社。
6.作业：根据章节要求进行相应的作业布置，并在下次课提交作业。
第二章线性表。
1.教学目标：掌握线性表的定义和基本操作，掌握线性表的顺序存储结构、线性表的链式存储结构、循环链表，学会线性表的应用举例。
2.教学重点和难点：线性表的顺序存储结构、线性表的链式存储结构；难点：循环链表。
3.教学内容和要求：
第一节线性表的类型定义。
一、线性表的逻辑结构和相关基本概念。
二、线性表的抽象数据类型。
三、线性表的两个举例。
第二节顺序表。
一、顺序表的定义和数据元素的存储位置的计算。
二、顺序表的操作及性能评价。
三、顺序表的应用举例。
第三节线性链表。
一、线性单链表。
一）线性单链表定义及其存储结构。
二）线性单链表的运算操作及算法性能评价。
二、单循环链表。
一）单循环链表的定义及其存储结构。
二）单循环链表的运算操作。
三、双向链表。
一）双向链表的定义及其存储结构。
二）双向链表的运算操作及算法性能评价。
四、双向循环链表。
一）双向循环链表的定义及其存储结构。
二）双向循环链表的运算操作及算法性能评价。
第四节线性表的应用举例。
4.教学过程与方法：讲授。
5.课外阅读资料：
1）. 严蔚敏等著。 数据结构习题集（c语言版）.清华大学出版社，1999
2）. 俆孝凯编著。 数据结构辅导与提高 .清华大学出版社，2000
3). 张乃孝编著。 算法与数据结构-c语言描述（第2版）. 高等教育出版社，2006
4). 李春葆编著。 数据结构教程。 清华大学出版社，2005
5). 李春葆编著。 数据结构教程学习指导。 清华大学出版社，2005
6). 谭浩强编著。 c语言程序设计(第2版). 清华大学出版社。
6.作业：根据章节要求进行相应的作业布置，并在下次课提交作业。
第三章串。1.教学目标：掌握串的基本概念，掌握串的基本操作，掌握串的存储结构，熟悉串的模式匹配，学会串的应用。
2.教学重点和难点：重点：串的存储结构和基本操作；难点：串的模式匹配。
3.教学内容和要求：
第一节串类型的定义。
一、串的定义。
二、串的抽象类型。
第二节串的表示和实现。
一、定长顺序存储表示。
一）定长串的定义。
二）定长串的描述。
三）定长串的基本操作。
二、堆分配存储表示。
一）堆分配存储串的定义。
二）堆分配存储的描述。
三）堆分配存储串的基本操作。
三、块存储串的表示。
一）块存储串的定义。
二）块存储串的c语言描述。
三）块存储串的基本操作。
第三节串的模式匹配。
一、求子串的位置。
二、kmp模式匹配。
第四节串的应用举例。
4.教学过程与方法：讲授。
5.课外阅读资料：
1）. 严蔚敏等著。 数据结构习题集（c语言版）.清华大学出版社，1999
2）. 俆孝凯编著。 数据结构辅导与提高 .清华大学出版社，2000
3). 张乃孝编著。 算法与数据结构-c语言描述（第2版）. 高等教育出版社，2006
4). 李春葆编著。 数据结构教程。 清华大学出版社，2005
5). 李春葆编著。 数据结构教程学习指导。 清华大学出版社，2005
6). 谭浩强编著。 c语言程序设计(第2版). 清华大学出版社。
6.作业：根据章节要求进行相应的作业布置，并在下次课提交作业。
第四章树和二叉树。
1.教学目标：掌握树定义和存储结构，掌握二叉树的定义、性质、存储结构，掌握二叉树的遍历，了解线索算法，能够熟练的进行树和二叉树的转换，掌握哈夫曼树及其应用。
2.教学重点和难点：重点：二叉树的性质，二叉树的遍历，哈夫曼树及其应用；难点：二叉树线索算法，二叉树的非递归遍历算法。
3.教学内容和要求：
第一节树的定义和基本概念。
一、树的定义及其抽象类型。
二、树的表示方法。
三、树的相关概念。
第二节二叉树。
一）二叉树的定义及其相关概念。
二）二叉树的性质。
三）二叉树的存储。
第三节二叉树的遍历和线索二叉树。
一、遍历二叉树。
一）先序遍历二叉树。
二）中序遍历二叉树。
三）后序遍历二叉树。
二、线索二叉树。
一）线索二叉树的定义。
二）线索二叉树的存储结构。
三）线索二叉树的操作。
四）中序线索二叉树的遍历。
第四节树和森林。
一、树的存储结构。
一） 双亲表示法。
二）孩子表示法。
三）孩子兄弟法。
二、森林与二叉树的转换。
一）森林转换成二叉树。
二）二叉树转换成森林。
三、树和森林的遍历。
一）树和森林的前序遍历。
二）树和森林的中序遍历。
第四节哈夫曼树及其应用。
一、哈夫曼树定义及其相关概念。
二、构造哈夫曼树。
三、哈夫曼树编码及其算法。
4.教学过程与方法：讲授。
5.课外阅读资料：
1）. 严蔚敏等著。 数据结构习题集（c语言版）.清华大学出版社，1999
2）. 俆孝凯编著。 数据结构辅导与提高 .清华大学出版社，2000
3). 张乃孝编著。 算法与数据结构-c语言描述（第2版）. 高等教育出版社，2006
4). 李春葆编著。 数据结构教程。 清华大学出版社，2005
5). 李春葆编著。 数据结构教程学习指导。 清华大学出版社，2005
6). 谭浩强编著。 c语言程序设计(第2版). 清华大学出版社。
6.作业：根据章节要求进行相应的作业布置，并在下次课提交作业。
第五章图。1.教学目标：理解图的定义，掌握图的存储结构，掌握图的遍历操作，熟悉图的几个典型应用问题，了解图的贯通性、关节点。
2.教学重点和难点：重点：图的存储结构，图的遍历操作，图的几个典型应用问题的算法思想；难点：拓扑排序、关键路径、点与点之间的距离。
3.教学内容和要求：
第一节图的基本概念。
一、图的定义及其抽象类型。
二、图的相关概念。
第二节图的存储结构。
一、邻接矩阵。
一）邻接矩阵形式描述及求图顶点的度。
二）用邻接矩阵构造图。
二、邻接表。
一）邻接表的形式描述及求图图顶点的度。
二）用邻接表构造图。
三）逆邻接表。
三、十字链表。
四、邻接多重表。
第三节图的遍历。
一、图的深度遍历。
一）图的递归深度遍历。
二）图的非递归深度遍历。
三）图的深度遍历的算法性能。
二、图的广度遍历。
一）图的递归广度遍历。
二）图的非递归广度遍历。
三）图的广度遍历的算法性能。
第四节图的连通性问题。
一、无向图的连通分量和生成树。
二、有向图的连通分量。
三、最小生成树。
一）生成树和最小生成树的概念。
二）prim算法。
1．prim算法的基本思想。
2．prim算法的实现及其算法性能。
3．用prim算法生成最小生成树举例。
三）kruskal算法。
1．kruska算法的基本思想和与prim算法的不同用途。
2．kruska算法的实现及其算法性能。
3．用kruska算法生成最小生成树举例。
四）关节点*
第五节有向无环图（dag）及其应用。
一、有向无环图的基本概念。
二、拓扑排序。
一）拓扑排序的基本概念。
二）拓扑排序的算法思想及其算法性能。
三）拓扑排序的举例。
三、关键路径。
一）关键路径的基本概念。
二）关键路径的算法思想及其算法性能。
三）关键路径的举例。
第四节最短路径。
一、从某些源点到其余个顶点的最短路径。
一）dijkstra算法。
1．dijkstra算法思想描述。
2．dijkstra算法实现及其算法性能。
3．应用dijkstra算法求最短路径举例。
4.教学过程与方法：讲授。
5.课外阅读资料：
1）. 严蔚敏等著。 数据结构习题集（c语言版）.清华大学出版社，1999
2）. 俆孝凯编著。 数据结构辅导与提高 .清华大学出版社，2000
3). 张乃孝编著。 算法与数据结构-c语言描述（第2版）. 高等教育出版社，2006
4). 李春葆编著。 数据结构教程。 清华大学出版社，2005
5). 李春葆编著。 数据结构教程学习指导。 清华大学出版社，2005
6). 谭浩强编著。 c语言程序设计(第2版). 清华大学出版社。
6.作业：根据章节要求进行相应的作业布置，并在下次课提交作业。
数据结构与算法
本章知识要点 算法的基本概念 数据结构的定义 线性表的定义和存储 树 二叉树的定义和存储 查找与排序算法。算法 algorithm 是一组有穷的规则，规定了解决某一特定类型问题的一系列运算，是对解题方 与完整的描述。算法是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中...
算法与数据结构
学院专业姓名学号。实验1 线性表的操作 12学时 问题描述 假设一个班级内有n个学生，定义一个学生类和一个班级类。学生类中包括学号 姓名 性别 年龄 专业等属性 班级类包括一个学生对象链表。定义如下 class student class myclass student stu head 链表表头指...
算法与数据结构
1 简述算法的概念及其五个重要特性。2 下图是用邻接表存储的图，请画出此图，写出其邻接矩阵以及从c点开始分别按广度优先搜索和深度优先搜索遍历该图的结果。给定一棵用二叉链表表示的二叉树，其根指针为root，编写求此二叉树叶结点个数的算法，要求先写出二叉链表的类型定义。2.编写简单选择排序的算法。1 用...