-
第一章绪论
课程绪论
-
●1.1为什么学习数据结构
数据结构是一门理论与实践并重的课程，既要掌握数据结构的基础理论知识，又要掌握运行和调试程序的基本技能。因此，数据结构课程在计算机学科本科培养过程中的地位十分重要。
-
●1.2数据结构基本概念
对数据，数据元素，数据项，关键字和主关键字进行详细的介绍。
-
●1.3数据结构的主要内容
数据的逻辑结构是指数据元素之间的逻辑关系，用一个数据元素的集合和定义在此集合上的若干关系来表示，常简称为数据结构
-
●1.4算法
算法
-
第二章线性表
线性表的抽象数据类型、将线性表的顺序和链式两种存储结构分别实现封装成顺序类和链式类、顺序表类和单链表类的设计与实现、双链表和循环链表插入、删除操作及线性表的应用。
-
●2.1线性表定义及其顺序存储
线性表及其特点、线性表的顺序存储结构及顺序表类。
-
●2.2顺序表的插入、删除和查找操作
顺序表的插入、删除过程及算法性能分析。
-
●2.3线性表链式存储及遍历
]链表概念、分类及单链表的遍历。
-
●2.4单链表的插入和删除操作
在单链表i位置处的插入、删除操作过程及算法分析
-
●2.5循环链表和双链表
循环链表、双链表及循环双链表上插入、删除操作及算法分析
-
●2.6线性表的应用
一元多项式的加运算过程及算法实现
-
第三章串
第三章
-
●3.1串及其存储和实现
串及其存储和实现
-
●3.2模式匹配算法
BF和KMP两个算法的子串匹配过程及算法实现、next数组的计算过程。
-
第四章栈和队列
栈和队列抽象数据类型及它们的实现和应用
-
●4.1栈
栈的定义、栈的顺序存储和链式存储、应用栈解决数制转换、括号匹配及表达式求值问题、
-
●4.2队列
队列、顺序队列、顺序循环队列类、链式队列、链式队列类、应用队列解决求解素数环问题及优先队列的实现
-
●4.3递归
递归特性问题、递归算法、单链表的递归算法
-
第五章数组和广义表
数组的存储结构、广义表的概念和存储结构
-
●5.1数组
二维数组的逻辑结构、二维数组的存储和遍历、Java语言的二维数组
-
●5.2特殊矩阵的压缩存储
三角矩阵、对称矩阵和对角矩阵的压缩存储、稀疏矩阵的压缩存储
-
●5.3广义表
广义表抽象数据类型、广义表的存储结构、广义表双链表示的实现
-
第六章树与二叉树
本章主要介绍树与二叉树的相关知识
-
●6.1章节引入
本章主要讨论树和二叉树的基本概念和存储结构，二叉树的二叉链表操作实现；线索二叉树的操作实现，以哈夫曼树为例介绍二叉树的应用；介绍树的孩子兄弟链表操作实现。
-
●6.2树及其抽象数据类型
树结构从自然界中的树抽象而来，有树根，从根发源类似枝杈的分支关系和作为终点的叶子等。生活中所见的家谱，Windows的文件系统等，虽然表现形式各异，本质上是树结构。
-
●6.3二叉树的定义与性质
二叉树是n(n>=0)个结点组成的有限集合，n=0时称为空二叉树；n>0的二叉树由一个根结点和两棵互不相交的，分别称为左子树和右子树的二叉树构成。二叉树的性质有：1.若根节点的层次为1，则二叉树第i层最多有2^i-1 (i>=1）个结点。2.在高度为h的二叉树中，最多有2^h -1个结点。（h>=0）
-
●6.4遍历二叉树的方法
二叉树的遍历是按照一定规则和次序访问二叉树中的所有结点，并且每个结点仅被访问一次。虽然二叉树是非线性结构，但遍历二叉树访问结点的次序是线性的，而且访问的规则和次序不止一种。二叉树的遍历规则有孩子优先和兄弟优先。
-
●6.5二叉树的存储结构
二叉树主要采用链式存储结构，顺序存储结构仅适用于完全二叉树（满二叉树）。
-
●6.6线索二叉树的使用
线索二叉树利用这些空链存储结点在某中遍历次序下的前驱和后继关系。意即原有非空的链保持不变，仍然指向该结点的左，右孩子结点；使空的left域指向前驱结点，空的right域指向后继结点。指向前驱和后继结点的链称为线索。
-
●6.7哈夫曼树及其应用
哈夫曼树是带权外路径长度最小的二叉树，又称最优二叉树。
-
●6.8树的表示和实现
主要讲解树的遍历规则，树的存储结构以及树的父母孩子兄弟链表实现。
-
第七章图
图的基本概念、分别以图的邻接矩阵和邻接表实现抽象数据类型，实现图的深度优先搜索和广度优先搜索，求解图的最小生成树和最短路径问题。
-
●7.1图的基本概念及其抽象数据类型描述
图的基本概念、图抽象数据类型
-
●7.2图的存储和实现
图的邻接矩阵存储及实现、图的邻接表、邻接多重表存储及实现
-
●7.3图的遍历
深度优先搜索、广度优先搜索过程举例及算法实现
-
●7.4最小生成树
普里姆算法和克鲁斯卡尔算法构造最小生成树的过程及算法实现
-
●7.5最短路径
狄杰斯特拉算法及实现、弗洛伊德算法及实现
-
第八章查找
本章主要介绍查找的内容及相关知识
-
●8.1查找的基本概念
查找是数据结构的一种基本操作，查找效率决定计算机某些应用系统的效率。查找算法依赖J数据结构，不同的数据结构需要采用不同的查找算法。因此，如何有效地组织数据，如何根据数据结构的特点快速、高效地获得查找结果，是数据处理的核心问题。
-
●8.2二分法查找
二分法查找(Binary Search)是一种典型的采用分治策略的算法，它将问题分解为规模更小的子问题，分而治之，逐一解决。二分法查找的两个条件是：顺序存储、数据元素排序。
-
●8.3基于索引的分块查找
当数据量较大时，建立索引(lndex)是一种有效的分治策略。为存储数据元素的主表创建索引表，其中的索引项(Index ltem)保存元素的关键字信息及存储位置。通过索引机制，缩小查找范围，以空间换取时间。例如，每本书正文前面的目录是一种索引表。各种字典也是建立索引的，并且可能建立多级索引。汉字字典有部首检字表和检字表，构成二级索引结构。
-
●8.4散列查找
如果根据元素的关键字就能够知道该元素的存储位置，那么只要花费O(1)时间就能得到查找结果，这是最理想的查找效率，散列存储就是基于这种思路实现的。散列(Hash)是一种按关键字编址的存储和查找技术，hash原意为杂凑。散列表(Hash Table)根据元素的关键字确定元素的存储位置，其查找、插入和删除操作效率接近O（l)，是目前查找效率最高的一种数据结构。散列技术的关键问题是设计散列函数和处理冲突。
-
●8.5二叉排序树和平衡二叉树
一个数据元素集合，如果既要排序、又要支持高效的查找、插入、删除操作，将其组织成什么样的数据结构能够满足要求?前述若干数据结构的排序、查找、插入、删除等操作性能分析如下：①排序顺序表，采用二分法查找，时间复杂度为O(log2n)；插入和删除操作的时间复杂度为O(n)，数据移动量大，效率较低。②排序单链表，顺序查找的时间复杂度为O(n)，不能采用二分法查找；插入和删除操作的时间复杂度为O(n)，虽然没有数据移动但因查找效率低，使得插入和删除的效率也较低。③散列表，虽然查找、插入和删除操作的效率较高，但是散表列不具有排序特性。 上述这几种数据结构都不能满足该问题的要求。能够满足该问题要求的是二叉排序树。
-
第九章排序导学
排序的应用实例
-
●9.1排序导学
有关排序的基本概念。
-
●9.2排序导学
直接插入排序、折半插入及折半插入排序的基本思想，算法的设计与实现、时空性能和稳定性分析。
-
●9.3交换排序
冒泡排序、快速排序的基本思想、算法设计、时空性能和稳定性分析。
-
●9.4选择排序
简单选择排序、堆排序的基本思想、算法设计、时空性能和稳定性分析。
-
●9.5归并排序
自底向上、自顶向下的二路归并排序算法的思想及时空性能分析。
-
●9.6排序总结
对内排序算法的时空复杂度和稳定性进行总结。
