-
第一章绪论
数据结构是计算机及相关专业课程体系中非常重要的一门专业基础课，是计算机存储、组织数据的方式。精心选择的数据结构可以带来更高的运行或存储效率。数据结构的研究内容是构造复杂软件系统的基础。本章介绍数据结构的研究内容、逻辑结构和存储结构的定义与分类，以及数据结构的描述方法，并介绍算法效率的度量方法及用大O表示法表示算法的时间和空间复杂度。
-
●1.1数据结构研究的内容
数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，主要研究内容是现实世界实体（非数值计算）及其上的操作在计算机中的表示与实现。
-
●1.2概念与术语
数据结构中常用的概念与术语包括数据、数据元素、数据项和数据结构等。数据结构分为逻辑结构和存储结构，逻辑结构是数据元素间抽象化的相互关系，分为线性与非线性两大类。存储结构是元素及其关系在存储器中的存储方式，常用的有顺序存储和链接存储。
-
●1.3抽象数据类型
抽象数据类型是用户进行软件系统设计时，从问题的数学模型中抽象出来的链接结构和其上的运算。抽象数据类型可以用数据对象、数据对象上的关系和运算三元组表示。
-
●1.4算法与算法分析
数据结构不仅要研究逻辑结构和存储结构，也要研究在确定结构下的算法。算法研究的目的是为了更有效地处理数据，提高数据运算效率。算法分析完成对算法的运行时间效率和所占用的存储空间大小的估计，并采用渐进复杂度，用大O表算法表示。
-
第二章线性表
介绍线性表的抽象数据类型定义、顺序表示和链式表示以及各类操作在两种存储结构上的实现算法，分析各算法时间复杂度和空间复杂度。
-
●2.1线性表的类型定义
线性表是n个数据元素的有限序列，其抽象数据类型定义含有三个要素：数据对象、数据关系和基本操作集。数据对象是具有相同数据类型的数据元素的有限集合，相邻数据元素之间具有一对一的序偶关系，数据操作集中的各个基本操作可以被其它算法所调用，以完成实际应用中更加复杂的操作。
-
●2.2线性表的顺序表示和实现
采用顺序存储结构存储的线性表称为顺序表，其用物理位置的相邻来表示线性表中数据元素之间逻辑位置的相邻。将介绍顺序表中的主要操作：查找元素、插入元素、删除元素在顺序表上的实现算法，并分析算法的效率。
-
●2.3线性表的链式表示和实现
线性表的链式表示也称为链表，链表分为单链表、循环链表和双向链表。单链表的n个结点由后继指针域链接成表；循环链表中表最后一个结点的后继指针域指向头结点，整个链表形成一个环；双向链表为了克服单链表单向性缺点，在每个结点中增设前驱指针域。分别介绍线性表的主要操作：创建链表、插入元素、删除元素在各链表的实现算法。并从时间角度和空间角度比较线性表的链式表示和顺序表示的不同。
-
第三章栈和队列
两种操作受限的特殊线性表——栈和队列，介绍其定义、存储表示及一般操作算法，并讲解应用实例。
-
●3.1栈
本节主要给出栈这种特殊线性表的定义及特点，讲解其基本操作。重点讲述栈的顺序存储结构，基于顺序栈的基本操作算法。
-
●3.2队列
本节讲解队列的定义及特点，给出队列的基本操作，重点讲解链队列和循环队列的表示方法和基本操作的算法描述。
-
第四章串
串作为非数值数据在计算机数据处理中占有重要地位，本节将介绍串的基本概念及串的存储结构，并讲解串在实际问题中的应用.
-
●4.1串的基本概念及应用
本节介绍串的定义和基本操作，以及3中存储表示方式——1.定长顺序存储；2.堆分配存储；3.块链存储，并讲解串的实际应用例子。
-
第五章数组和广义表
数组和广义表可以看成是线性表的扩展，表中元素不再是原子型，其数据元素本身也是一个数据结构，本章介绍这两种数据结构的定义和存储结构。
-
●5.1数组
数组是具有相同类型的数据元素的有限序列，可以看做线性表的推广。本节讲解数组的一般表示方式以及其顺序存储方式。
-
●5.2矩阵压缩存储和广义表
本节讲解特殊矩阵和稀疏矩阵及其压缩方法，以及广义表的定义及存储结构。
-
第六章树和二叉树
本章介绍树的定义、基本术语，二叉树的定义、性质、存储结构，遍历二叉树，线索二叉树，树和森林，赫夫曼树及赫夫曼编码等内容。本章重点是二叉树及二叉树遍历。
-
●6.1树的定义和基本术语
本节介绍树的概念，以及树的一些基本术语：结点、度、层次、路径、深度、森林等。
-
●6.2二叉树
本节介绍二叉树的定义、二叉树的性质以及二叉树的存储结构。
-
●6.3遍历二叉树和线索二叉树
本节介绍遍历二叉树：先序遍历、中序遍历、后序遍历和层次遍历，还介绍遍历线索二叉树。
-
●6.4树和森林
本节介绍树的存储结构：双亲表示法、孩子表示法和孩子兄弟表示法，还介绍森林与二叉树的互相转换。
-
●6.5赫夫曼树与其应用
本节介绍赫夫曼树、构造赫夫曼树及赫夫曼树的应用：赫夫曼编码。
-
第七章图
图是一种较线性表和树更为复杂的数据结构，在实际生活中应用十分广泛。在这一章，我们将主要介绍图这种逻辑结构及其应用。首先介绍图的类型定义；然后讲解图的各种存储结构及其构造算法，各种存储结构的特点及其选用的原则；最后介绍图的两种遍历算法和图的各种应用问题的算法。
-
●7.1图的定义和术语
本节介绍了图的定义，着重介绍了图中所涉及的各种术语，如：有向图，无向图，顶点，边，弧，稀疏图，稠密图，连通分量，生成树，生成树等概念，为后续图存储表示和应用的学习打下基础。
-
●7.2图的存储结构
图结点关系比较复杂，因此没有顺序存储表示方法。本节将介绍四种图的存储表示方法，分别是图的数组表示法，又叫做图的邻接矩阵表示法，图的邻接表表示法，有向图的十字链表表示法和无向图的邻接多重表表示法。
-
●7.3图的遍历
与树的遍历类似，我们希望从图的某一顶点出发，遍历图中其余顶点，且使每个顶点仅被访问一次。这一过程就叫做图的遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。本节将介绍两条遍历图的路径：深度优先搜索和广度优先搜索，它们对于有向图和无向图都使用。
-
●7.4图的连通性问题
在无向图中，从任意顶点出发都能到图中的任一顶点，我们称这样的图就是连通图。在这一节，我们将利用遍历图的算法求解图的连通性问题，理解并掌握图的最小生成树概念，讲解两种最小生成树构造方法：普里姆算法和克鲁斯卡尔算法。
-
●7.5有向无环图及其应用
有向无环图是描述工程或系统进行过程的有效工具。本节介绍了有向无环图的定义，详细介绍当有向无环图作为工程进行过程描述工具时，人们最关心的两个问题，以及如何使用拓扑排序算法和求关键路径的算法解决来这两个问题。
-
●7.6最短路径
最短路径问题是图论研究中的一个经典算法问题，旨在寻找图中两结点之间的最短路径。本节将介绍最短路径中的两种情况：从某一个源点到其余各顶点的最短路径和每一对顶点之间的最短路径。
-
第八章查找
查找是现实生活中经常使用的操作。本章介绍查找的定义及分类，静态查找表的存储方式及其查找算法，动态查找表的存储方式及其查找、插入、删除的算法，哈希表的定义，构造哈希表的方法，处理冲突的算法。
-
●8.1查找的基本概念
介绍查找的定义、分类及平均查找长度。
-
●8.2静态查找表
静态查找表的定义及其查找算法，包括顺序表、有序表和索引顺序表的查找算法。
-
●8.3动态表的查找
动态查找表的定义，二叉排序树、平衡二叉树的定义、存储结构、查找、插入、删除的算法。
-
●8.4哈希表
介绍哈希表的定义、特点、查找效率等，构造哈希函数的方法，处理冲突的方法。
-
第九章内部排序
内部排序、外部排序的定义，各种内部排序算法的描述，包括插入排序、选择排序、归并排序、基数排序等。
-
●9.1排序概述
排序、内部排序、外部排序的定义，内部排序的方法。
-
●9.2插入排序
插入排序的定义，直接插入排序、折半插入排序、希尔排序的算法描述及示例。
-
●9.3交换排序
交换排序的定义，冒泡排序、快速排序的算法描述及示例。
-
●9.4选择排序
选择排序的定义，简单选择排序、堆排序的算法描述及示例，堆排序包括建堆及筛选的过程。
-
●9.5归并排序
归并排序的定义及算法描述。
-
●9.6基数排序
基数排序的定义，多关键字的排序方法，链式基数排序的方法及算法描述。
-
第十章生活中的数据结构
生活中存在着各种数据结构，让我们去发现它吧。电影院找座位、排队、乘坐电梯、家族的族谱、公司的组织架构、计算机中文件的组织，都蕴藏着哪些数据结构呢？
-
●10.1生活中的数据结构
生活中存在着各种数据结构，让我们去发现它吧。电影院找座位、排队、乘坐电梯、家族的族谱、公司的组织架构、计算机中文件的组织，都蕴藏着哪些数据结构呢？
