22考研计算机专业课——数据结构【❤️考研复习指导❤️】

阳光穿透心脏的1/2处 2022-09-12 08:47 134阅读 0赞

> 本次复习指导是基于我在21考研初试中我的王道考研数据结构这本书，加上【数据结构与算法设计】这本教材，书上和笔记本上都记满了笔记和重难点，所以在此回顾这些基本知识点，不能做到我当时的面面俱到，但是尽量完整，数据结构这部分我也几乎拿了满分，好好学，你也可以！

# 第 1 章 绪论 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16]

# 1.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时表示一个空表。此外，为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头结点。

<table> 
 <thead> 
  <tr> 
   <th>这部分内容很多，而且是重点，需要仔细比较顺序表和链表的特点。</th> 
  </tr> 
 </thead> 
 <tbody></tbody> 
</table>

# 第 3 章 栈和队列 #

## 3.1 栈 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
栈就和一个水桶一样，里面是一层层冰块，先进去的在桶底，后进来的在桶顶，只有上面的冰块出桶，后面的冰块才可以出桶。

栈的操作特性可以明显概括**后进先出**（Last In First Out，LIFO）。

栈的基本操作：**进栈、出栈**

## 3.2 队列 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
队列的操作特性可以明显概括**先进先出**（First In First Out，FIFO）。

**队头**：允许删除的一端，又称为队首。  
**队尾**：允许插入的一端。  
**空队列**：不含任何元素的空表。

循环队列和链式队列是重点

## 3.3 栈和队列的应用 ##

**栈的应用**：  
括号匹配、后缀表达式  
递归（递归表达式+边界条件）

**队列的应用**：  
层次遍历二叉树、资源竞争队列

## 3.4 特殊矩阵的压缩存储 ##

数组是由n（n>=1）个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。

对称矩阵、三角矩阵、三对角矩阵、洗漱矩阵

## 第 4 章 串 ##

## 4.1 串的定义和实现 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

## 4.2 串的模式匹配 ##

串的模式匹配算法

改进的模式匹配算法——KMP算法

KMP算法进一步优化

# 第 5 章 树与二叉树 #

## 5.1 树的基本概念 ##

树的定义  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
基本术语  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
树的性质  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 5]

## 5.2 二叉树的概念 ##

二叉树是另一种树形结构，其特点是每个结点至多只有两课子树，并且二叉树的子树有左右之分，其次序不能任意颠倒。

**特殊的二叉树:**  
（1）满二叉树  
（2）完全二叉树  
（3）二叉排序树

**二叉树的性质**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 6]

## 5.3 二叉树的遍历和线索二叉树 ##

**二叉树的遍历：**

1.  先序遍历（根左右）
2.  中序遍历（左根右）
3.  后序遍历（左右根）

## 5.4 树、森林 ##

树、森林与二叉树的转换，这些理解定义，多做题目就会熟练了。

## 5.5 树与二叉树的应用 ##

1.  二叉排序树
2.  平衡二叉树
3.  哈夫曼树

# 第 6 章 图 #

## 6.1 图的基本概念 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 7]

## 6.2 图的存储及基本操作 ##

*  邻接矩阵法（适合稠密图）
 *  邻接表法（适合稀疏图）
 *  十字链表（存储有向图）
 *  邻接多重表（存储无向图）

## 6.3 图的遍历 ##

广度优先搜索（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.  除留余数法
3.  数字分析法
4.  平方取中法

**处理冲突的方法**

1.  开放定址法  
    （1）线性探测再散列  
    （2）二次探测再散列
2.  拉链法

# 第 8 章 排序 #

## 8.1 排序的基本概念 ##

排序，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。

算法的稳定性，就是说排序前的两个相同的数的相对位置在排序后是否改变，若位置不变，则稳定，否则不稳定。

排序分为五大类：插入排序、交换排序、选择排序、归并排序和基数排序

## 8.2 插入排序 ##

*  直接插入排序（顺序表和链表）
 *  折半插入排序（顺序表）
 *  希尔排序

## 8.3 交换排序 ##

*  冒泡排序（顺序表和链表）
 *  快速排序（顺序和链式存储）

## 8.4 选择排序 ##

*  简单选择排序
 *  堆排序（重点）

## 8.5 归并排序和基数排序 ##

*  归并排序
 *  基数排序

## 8.6各种内部排序算法的比较及应用 ##

从时间复杂度的最好情况、平均情况、最坏情况和空间复杂度以及稳定性来比较。

**稳定的排序算法：直接插入排序、冒泡排序、归并排序和基数排序。**

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/901344b6daed4c42b269eac49a214acd.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/e548b9cf428048668a380f45968afc48.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/11db5205d74e43bc9c8dfbccfc4a23de.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/0396bc68335243e38fdb23fedfdce66c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/d38c762bc15140eab9a8a11c83f73d2d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/d03de7f9e1984840a92c0daf36204ecf.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/556f6e5071704db49f49eb642ab9563c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/8f6675ddb30840fcbc097da75f509f57.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oyv5Y2OT1BQTw_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/8d2f87e7fad24d2dbfdb9fb131a9bdc1.png