spContent=《数据结构与算法》是计算机专业的一门专业必修课程。它系统地介绍线性表、栈、队列、字符串、数组、广义表、树、二叉树、图、查找表等常用数据结构的基本概念、操作及其典型应用例子。在知识方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法，使学生了解数据对象的特性，数据组织的基本方法。在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。通过学习，初步具备分析问题、解决问题的能力，养成良好的程序设计风格，积聚和提高基本的分析设计能力，为后续课程的学习打下坚实的基础。
《数据结构与算法》是计算机专业的一门专业必修课程。它系统地介绍线性表、栈、队列、字符串、数组、广义表、树、二叉树、图、查找表等常用数据结构的基本概念、操作及其典型应用例子。在知识方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法，使学生了解数据对象的特性，数据组织的基本方法。在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。通过学习，初步具备分析问题、解决问题的能力，养成良好的程序设计风格，积聚和提高基本的分析设计能力，为后续课程的学习打下坚实的基础。
—— 课程团队
课程概述
在课程体系上，本课程还是一门承上启下的核心课程，是学好《操作系统原理》、《数据库系统原理》、《软件工程》、《计算机网络技术》、《人工智能与专家系统》等后续课程的关键，是培养提高学生程序设计能力的基础。其先导课程有《离散数学》、《C语言程序设计》等。
授课目标
通过本课程的教学，应使学生达到下列要求：
(一) 了解数据结构及其分类、数据结构与算法的密切关系。
(二) 熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构。
(三) 掌握设计算法的步骤和算法分析方法。
(四) 掌握数据结构在排序和查找等常用算法中的应用。
(五) 初步掌握文件组织方法和索引技术。
成绩 要求
本课程采用理论教学与实验教学相结合的方式。理论与实际应用相结合，使学生具备解决实际问题的能力。通过实验教学，培养学生实际动手能力和编写程序的能力，达到学以致用目的。
该课程的考试形式为：期末闭卷考试占总成绩的60%，平时成绩（作业、上机实验和课堂考勤等）占总成绩的40%。
课程大纲
绪论
课时目标：1、了解数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系 2、了解数据类型、抽象数据类型、数据抽象和信息隐蔽原则。 3、了解算法的定义、算法的特性、算法的时间代价、算法的空间代价 4、掌握：用C++语言描述算法的方法，能够使用C++语言编写程序
1.1 什么是数据结构
1.1.1数据结构定义
1.1.2逻辑结构
1.1.3存储结构
1.1.4数据类型和数据结构
1.2算法及其描述
1.2.1算法定义
1.2.2算法描述
1.3算法分析
1.3.1算法设计的目标
1.3.2算法效率分析
1.3.3算法存储空间分析
线性表
课时目标：（1）掌握线性表的逻辑特性和两类不同的存储结构； （2）两类存储结构（顺序和链式存储结构）的描述方法，以及单链表、循环链表、双向链表的特点； （3）线性表在顺序存储结构中实现基本运算（查找、插入、删除、合并等）的算法及分析； （4）线性表在链式存储结构中实现基本运算（查找、插入、删除、合并等）的算法及分析，并学会何时选用何种链表的方法；
2.1线性表及其逻辑结构
2.1.1线性表的定义
2.1.2抽象数据类型描述
2.2线性表顺序存储结构
2.2.1顺序表
2.2.2顺序表基本运算的实现
2.3线性表的链式存储结构
2.3.1链表
2.3.2单链表
2.3.3双链表
2.3.4循环链表
2.4 有序表
2.4.1有序表抽象数据类型
2.4.2有序表的存储结构
2.4.3有序表的基本运算
2.4.4有序表的归并算法
栈和队列
课时目标：（1）掌握栈的特点、表示和实现； （2）熟悉栈的典型应用并编程实现（如：语法检查、回朔算法、递归算法、表达式求值）； （3）掌握队列的特点、表示和实现； （4）了解离散事件模拟。
3.1栈
3.1.1栈的定义
3.1.2栈的顺序存储及其基本运算
3.1.3栈的链式存储结构及其基本运算
3.2队列
3.2.1队列的定义
3.2.2队列的顺序存储结构及其运算
3.2.3队列的链式存储结构及其运算
串
4.1串的基本概念
4.2串的存储结构
4.2.1串的顺序存储结构
4.2.2串的链式存储结构
4.3模式匹配
4.3.1BF算法
4.3.2KMP算法
数组和广义表
5.1数组
5.1.1数组的基本概念
5.1.2存储结构
5.1.3特殊矩阵的压缩存储
5.2稀疏矩阵
5.2.1稀疏矩阵三元组表示
5.2.2十字链表表示
5.3广义表
5.3.1广义表的定义
5.3.2广义表的存储结构
5.3.3广义表的运算
树和二叉树
课时目标：（1）掌握树的定义和基本术语； （2）掌握二叉树的结构特性及相应的证明方法； （3）了解二叉树的各种存储结构特点及使用范围； （4）重点掌握二叉树的各种遍历算法的递归和非递归算法；能灵活应用遍历算法实现二叉树的其他操作； （5）了解二叉树的前序、中序、后序线索化，掌握中序线索化过程以及在中序线索树上找出给定结点的前驱和后继的方法； （6）了解树的定义和存储结构及树的应用举例，掌握树和二叉树的转换方法； （7）了解最优树的特性，掌握建立最优树和实现Huffman编码的方法。
6.1树的基本概念
6.1.1树的定义
6.1.2树的逻辑表示方法
6.1.3树的基本术语
6.1.4树的性质
6.1.5树的基本运算
6.1.6树的存储结构
6.2二叉树的基本概念
6.2.1二叉树的定义
6.2.2二叉树的性质
6.2.3二叉树与树、森林之间的转换
6.3二叉树的存储结构
6.3.1二叉树的顺序存储结构
6.3.2二叉树的链式存储结构
6.4二叉树的基本运算及其实现
6.4.1二叉树的基本运算概述
6.4.2二叉树的基本运算算法实现
6.5二叉树的遍历
6.5.1二叉树遍历的基本概念
6.5.2遍历的递归算法和非递归算法
6.6二叉树的构造
6.7哈夫曼树
6.7.1哈夫曼树概述
6.7.2哈夫曼树的构造算法
6.7.3哈夫曼编码
图
课时目标：（1）了解图的定义和术语 （2）掌握图的四种存储结构极其构造算法； （3）重点掌握图的两种遍历策略； （4）了解图的连通性问题极其判断； （5）有向无环图极其应用（拓扑排序和关键路径） （6）掌握两类最短路径问题的解法。
7.1图的基本概念
7.1.1图的定义
7.1.2图的基本术语
7.2图的存储结构
7.2.1图的邻接矩阵存储
7.2.2图的邻接表存储
7.3图的遍历
7.3.1图的遍历的概念
7.3.2深度优先遍历
7.3.3广度优先遍历
7.3.4非连通图的遍历
7.4生成树
7.4.1生成树的概念
7.4.2无向图的连通分量和生成树
7.5最小生成树算法
7.5.1普利姆算法
7.5.2克鲁斯卡尔算法
7.6最短路径
7.6.1路径的概念
7.6.2狄克斯特拉算法
7.6.3弗洛伊德算法
7.7拓扑排序
7.8关键路径
查找
课时目标：（1）掌握静态查找表的四种查找方法（顺序查找、折半查找、静态树表、索引查找）的实现； （2）掌握动态查找表（二叉排序树、二叉平衡树、B-和B+树、键树）的构造和查找方法； （3）掌握哈希表构造方法，哈希表的查找以及衡量查找效率的平均查找长度的讨论。
8.1查找的基本概念
8.2线性表的查找
8.2.1顺序查找
8.2.2折半查找
8.3.1二叉排序树
8.3.2平衡二叉树
8.4.1哈希表基本概念
8.4.2哈希表的构造方法
8.4.3哈希冲突解决方法
8.4.4哈希表上的运算
内排序
课时目标：（1）了解排序的定义和基本术语； （2）掌握各种内部排序方法的基本思想、算法特点、排序过程以及它们的时间复杂度分析； （3）了解稳定排序方法和不稳定排序方法的定义及判断。
9.1排序的基本概念
9.2.1直接插入排序
9.2.2折半插入排序、
9.2.3希尔排序
9.3.1冒泡排序
9.3.2快速排序
9.4.1直接选择排序
9.4.2堆排序
展开全部
预备知识
数学基本知识：高等数学 离散数学
编程基本技能：C++语言 C语言
参考资料
主要参考书：
1．李春葆等. 《数据结构教程(第5版)》,清华大学出版社，2017.
2．李春葆等. 《数据结构简明教程(第2版)》,清华大学出版社，2019.
3．殷人昆.《数据结构（用面向对象方法与C++语言描述）（第2版）》，清华大学出版社，2007.
4．陈卫卫等.《数据结构与算法》，高等教育出版社，2015.
5．[美]Clifford A.Shaffer 著，张铭 刘晓丹译.《数据结构与算法分析（Java版）》，电子工业出版社，2001.
6．徐孝凯.《数据结构实用教程（第2版）》，清华大学出版社，2006.
浙公网安备 33010802012594号
