本次复习指导是基于我在21考研初试中我的王道考研数据结构这本书，加上【数据结构与算法设计】这本教材，书上和笔记本上都记满了笔记和重难点，所以在此回顾这些基本知识点，不能做到我当时的面面俱到，但是尽量完整，数据结构这部分我也几乎拿了满分，好好学，你也可以！
第 1 章 绪论
数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。
1.2 算法和算法评价程序=数据结构+算法
算法的五个特性：（1）有穷性（2）确定性（3）可行性（4）输入（5）输出
算法效率的度量：1、时间复杂度 2、空间复杂度
第 2 章 线性表 2.1 线性表的定义与基本操作线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列，其中n为表长，当n=0时线性表是一个空表。用L命名线性表，则其一般表示为： L=(a1,a2,…ai,ai+1,…,an)
式中，a1是唯一的“第一个”数据元素，又称为表头元素；an是唯一的“最后一个”数据元素，又称表尾元素。
2.2 线性表的顺序表示线性表的顺序存储又称顺序表，使得逻辑上相邻的两个元素在物理位置上也相邻。
顺序表最主要的特点就是随机访问，即通过首地址和元素符号可以在时间O(1)内找到指定的元素。
顺序表存储密度高，每个结点只存储数据元素。
顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。
2.3 线性表的链式表示线性表的链式存储又称为单链表，它是指通过一组任意存储单元来存储线性表中的数据元素。
单链表的结构是data数据域，存放数据元素，next指针域存放后继结点的地址。
typedef struct LNode{ //定义单链表结点类型ElemType data;//数据域struct LNode *next;//指针域}LNode,*LinkList;通常用头指针来标识一个单链表，如单链表L，头指针为NULL时表示一个空表。此外，为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头结点。
这部分内容很多，而且是重点，需要仔细比较顺序表和链表的特点。 第 3 章 栈和队列 3.1 栈
栈就和一个水桶一样，里面是一层层冰块，先进去的在桶底，后进来的在桶顶，只有上面的冰块出桶，后面的冰块才可以出桶。
栈的操作特性可以明显概括后进先出（Last In First Out，LIFO）。
栈的基本操作：进栈、出栈
3.2 队列
队列的操作特性可以明显概括先进先出（First In First Out，FIFO）。
队头：允许删除的一端，又称为队首。 队尾：允许插入的一端。 空队列：不含任何元素的空表。
循环队列和链式队列是重点
3.3 栈和队列的应用栈的应用： 括号匹配、后缀表达式 递归（递归表达式+边界条件）
队列的应用： 层次遍历二叉树、资源竞争队列
3.4 特殊矩阵的压缩存储数组是由n（n>=1）个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。
对称矩阵、三角矩阵、三对角矩阵、洗漱矩阵
第 4 章 串 4.1 串的定义和实现
串的模式匹配算法
改进的模式匹配算法——KMP算法
KMP算法进一步优化
第 5 章 树与二叉树 5.1 树的基本概念树的定义 
基本术语 
树的性质 
二叉树是另一种树形结构，其特点是每个结点至多只有两课子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。
特殊的二叉树: （1）满二叉树 （2）完全二叉树 （3）二叉排序树
二叉树的性质 
二叉树的遍历：
先序遍历（根左右）中序遍历（左根右）后序遍历（左右根） 5.4 树、森林树、森林与二叉树的转换，这些理解定义，多做题目就会熟练了。
5.5 树与二叉树的应用 二叉排序树平衡二叉树哈夫曼树 第 6 章 图 6.1 图的基本概念
广度优先搜索（BFS）类似于二叉树的层序遍历算法。算法借助一个辅助队列。 BFS求解单源最短路径，广度优先生成树
深度优先搜索类似于树的先序遍历。算法借助一个递归工作栈。
6.4 图的应用历年考察的重点。图的应用包括：最小生成树、最短路径、拓扑排序和关键路径。
最小生成树 1、普利姆（Prim）算法 2、克鲁斯卡尔（Kruskal）算法
最短路径 带权有向图G的最短路径问题一般分为两类： 一是单源最短路径，即求图中某一顶点到其他各顶点的最短路径，可以通过经典的Dijkstra算法求解。 二是求每对顶点间的最短路径，可通过Floyd算法求解。
拓扑排序 （1）每个顶点出现且仅出现一次 （2）若顶点A在序列中排在B的前面，则在图中不存在从顶点B到顶点A的路径。 ps:拓扑排序可能不唯一；若图中有环，则不存在拓扑排序序列。
关键路径 从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而关键路径上的活动称为关键活动。
第 7 章 查找 7.1 查找的基本概念在数据集合中寻找满足某种条件的数据元素的过程称为查找。 查找的结果分为两种：查找成功和查找失败。
7.2 顺序查找和折半查找顺序查找又称为线性查找，主要用于线性表中进行查找。
折半查找又称为二分查找，仅适用于有序的顺序表。二分查找的题目非常经典，必考题。
分块查找将查找表分为若干块，块内的元素可以无序，快间是有序的。吸取了顺序查找和折半查找各自的优点。
7.3 B树和B+树B树，又称为多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一般考察的就是B树的高度、B树的查找、插入和删除。
B+树是变形树。
7.4 散列表散列函数
直接定址法除留余数法数字分析法平方取中法处理冲突的方法
开放定址法 （1）线性探测再散列 （2）二次探测再散列拉链法 第 8 章 排序 8.1 排序的基本概念排序，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。
算法的稳定性，就是说排序前的两个相同的数的相对位置在排序后是否改变，若位置不变，则稳定，否则不稳定。
排序分为五大类：插入排序、交换排序、选择排序、归并排序和基数排序
8.2 插入排序 直接插入排序（顺序表和链表）折半插入排序（顺序表）希尔排序 8.3 交换排序 冒泡排序（顺序表和链表）快速排序（顺序和链式存储） 8.4 选择排序 简单选择排序堆排序（重点） 8.5 归并排序和基数排序 归并排序基数排序 8.6各种内部排序算法的比较及应用从时间复杂度的最好情况、平均情况、最坏情况和空间复杂度以及稳定性来比较。
稳定的排序算法：直接插入排序、冒泡排序、归并排序和基数排序。