-
第一章绪论
绪论
-
●1.1数据结构总览
课程学习的三个问题（why,what,how)，课程学习目标
-
●1.2数据与数据结构
数据、数据元素、数据对象、数据结构、逻辑结构、存储结构、数据运算
-
●1.3数据类型及抽象数据类型
数据类型、抽象数据类型、数据结构求解问题的过程
-
●1.4算法及其描述
算法的基本概念、算法的描述
-
●1.5算法时间复杂度分析
算法分析、时间复杂度、算法时间复杂度的计算、最好、最坏和平均时间复杂度、常见的时间复杂度
-
●1.6算法空间复杂度分析
空间复杂度、空间复杂度的示例
-
●1.7Java提供的泛型方法
Java提供的泛型机制、使用Object表示泛型、使用Comparable接口类型表示泛型
-
第二章线性表
线性表
-
●2.1线性表的基本概念及抽象数据类型描述
线性表的基本概念、特性、接口的定义
-
●2.2线性表的顺序存储及顺序表类的定义和实现
线性表的链式存储的基本情况，单链表类中的简单成员函数的定义和实现、单链表类中其他成员函数的定义和实现，以及对单链表类的测试
-
●2.3线性表的链式存储及其实现
线性表的链式存储的基本情况，单链表类中的简单成员函数的定义和实现、单链表类中其他成员函数的定义和实现，以及对单链表类的测试
-
●2.4顺序表与链表的比较
顺序表与单链表的比较，各自的优缺点以及应用场景
-
第三章栈和队列
栈和队列
-
●3.1栈的基本概念和顺序栈类的定义和实现
栈的基本概念和特性，顺序栈类的定义和实现
-
●3.2链式栈类的定义和实现
栈的链式存储，链式栈类的定义和实现
-
●3.3队列的基本概念和顺序循环队列类的定义和实现
顺序队列的基本情况，循环顺序队列类的定义和实现
-
●3.4链队列类的定义和实现
队列的链式存储，链式队列类的定义和实现
-
第四章串
串抽象数据类型、串的存储和实现、串的模式匹配
-
●4.1串抽象数据类型
串的概念、串抽象数据类型描述、串和线性表的区别和联系
-
●4.2串的存储和实现
串的两种存储结构、顺序串类的定义和实现、顺序串基本操作的实现、基本操作的应用
-
●4.3模式匹配
模式匹配的概念、BF算法的基本思想、算法实现、算法性能、KMP算法的基本原理、算法实现、算法的时间复杂度
-
第五章数组和广义表
数组、特殊矩阵的压缩存储、广义表
-
●5.1数组的概念与顺序存储
多维数组的概念、数组的特点、数组的行主序、列主序存储和寻址
-
●5.2压缩存储
对称矩阵、三角矩阵、对角矩阵的压缩存储方案，矩阵元素在压缩数组中的位置、稀疏矩阵三元组顺序表的存储结构、三元组顺序表的基本操作、稀疏矩阵的转置操作、稀疏矩阵的十字链表存储结构
-
●5.3广义表抽象数据类型与双链存储
广义表的概念、广义表抽象数据类型、广义表的双链存储及实现
-
第六章树和二叉树
树和二叉树
-
●6.1树的概念
树的定义，树的术语（父母、孩子与兄弟结点、度、结点层次、树的高度、边、路径、路径长度、无序树、有序树）
-
●6.2树的表示、遍历与存储结构
树的表示、遍历与存储结构
-
●6.3二叉树的定义与性质
二叉树的定义与性质
-
●6.4二叉树与树、森林之间的转换
二叉树与树、森林之间的转换
-
●6.5二叉树的存储结构
二叉树的顺序存储结构、二叉树的链式存储结构
-
●6.6二叉树的二叉链表实现
二叉树的二叉链表实现
-
●6.7二叉树的遍历
先根遍历、中根遍历、后根遍历、二叉树先根遍历的非递归算法、层次遍历
-
●6.8二叉树的构造
二叉树的构造
-
●6.9哈夫曼树与哈夫曼编码
哈夫曼树的定义、哈夫曼树的构造、哈夫曼编码
-
第七章图
图
-
●7.1图的概述
图的逻辑结构、图的基本概念、图的抽象数据类型描述
-
●7.2图的存储结构
图的类型、图的常见存储结构、邻接矩阵定义、邻接矩阵优缺点、图的邻接矩阵类的描述、图的邻接矩阵类基本操作实现、邻接表定义、邻接表的优缺点、邻接表与邻接矩阵比较、图的邻接表类的描述、图的邻接表类基本操作实现
-
●7.3图的遍历
算法描述、广度优先遍历算法的实现、深度优先遍历算法的实现
-
●7.4最小生成树
最小生成树的基本概念、Kruskal算法的基本思想、Prim算法的基本思想、Prim算法构造最小生成树
-
●7.5最短路径
Dijkstra算法的基本思想、Dijkstra算法构造最短路径、Floyd算法的基本思想、Floyd算法构造最短路径
-
●7.6拓扑排序
拓扑排序的基本概念、拓扑排序的实现
-
●7.7关键路径
关键路径的基本概念、求关键活动的步骤
-
第八章查找
查找
-
●8.1查找概述
查找概述
-
●8.2静态表查找
顺序查找定义、查找过程及性能分析、二分查找定义、查找过程及性能分析、分块查找定义、查找过程及性能分析
-
●8.3动态表查找
二叉排序树定义、查找、插入、删除算法及性能分析、平衡二叉树定义、查找、插入、删除算法及性能分析
-
●8.4哈希表
哈希表的定义、常用的哈希函数、处理冲突的方法
-
第九章排序
排序算法
-
●9.1排序的基本概念
排序的定义、分类、内排序的方法、算法的性能评价及待排序记录的类描述
-
●9.2插入排序
直接插入排序基本思想、算法的主要步骤、代码实现及性能分析、希尔排序基本思想、算法的主要步骤、代码实现及性能分析
-
●9.3交换排序
冒泡排序基本思想、算法的主要步骤、代码实现及性能分析、快速排序基本思想、算法的主要步骤、代码实现及性能分析
-
●9.4选择排序
直接选择排序基本思想、算法的主要步骤、代码实现及性能分析、树型选择排序基本思想、算法的主要步骤、代码实现及性能分析、堆排序基本思想、算法的主要步骤、代码实现及性能分析
-
●9.5归并排序
归并排序基本思想、算法的主要步骤、代码实现及性能分析