数据结构重点

1、算法基础

时间复杂度O(？？？)的计算方法

O(1)

int n= 1000;
System.out.println("hello " + n);

O(n)

for(int i = 0; i<=n; i++) {
    System.out.println(i);
}

O(n^2)

for(int i = 0; i<=n; i++) {
    for(int j = 0; j<=n; j++) {
            System.out.println(i+j);
    }
}

O(log(n))

for(int i = 1; i<n; i = i*2) {
    System.out.println(i);
}

O(k^n)

for(int i = 1; i<= Math.pow(2, n); i++) {
    System.out.println(i);
}

O(n!)

for(int i = 1; i<=factorial(n); i++) {
    System.out.println(i);
}

2、线性表

顺序存储与链式存储的区别、特性、优缺点、一些操作的时间复杂度的计算结果

区别：
1、==顺序存储需要开辟一个定长的空间==，读写速度快（随机存取），缺点不可扩充容量(如果要扩充需要开辟一个新的足够大的空间把原来的数据重写进去)。
2、==链式存储无需担心容量问题==，读写速度相对慢些（不支持随机存取但灵活），由于要存储下一个数据的地址所以需要的存储空间比顺序存储大。

链表的优缺点、支持的操作、常见的类型

链表的优点
插入删除速度快
内存利用率高，不会浪费内存
大小没有固定，拓展很灵活。
链表的缺点
不能随机查找，必须从第一个开始遍历，查找效率低
操作顺序表链表
读取 O(1) O(n)
插入 O(n) O(1)
删除 O(n) O(1)
常见的类型

操作	顺序表	链表
读取	O(1)	O(n)
插入	O(n)	O(1)
删除	O(n)	O(1)

常用线性表存储结构（带或不带头结点、单向或双向链表），以及在相应存储结构上的常见线性表方法（判定满、空、取元素、查找元素等）的实现

链表没有满的状态
链表为空时表现为p.next==null
查找元素时使用循环，遍历next指针
取元素时不光要判断指针，还需要根据实际情况修改前一个元素的指针域（单链表）前后两个元素的指针域（双链表）
在不带头结点的链表0位置进行插入需要将此节点替换为首节点，其他位置的插入与带头结点的插入一致

栈、队列的区别、特性、优缺点

区别：栈和队列都是线性表，限定插入和删除的位置不同
特性：栈是先进后出或者后进先出，而队列是先进先出；
栈优点：由于栈中存放数据的结构是后放进去的数据先取出来(后进先出)，针对一些操作需要取最新数据时，选择栈作为数据结构是最合适的。
栈缺点：访问栈中的任意数据时，就需要从最新的数据开始取，效率较低。
队列优点：队列的特点是，最早添加进来的数据，先取出，对于需要获取最早添加的数据时，选择队列作为数据结构，将会大大的提升效率。
队列缺点：获取最新的数据就需要从最开始入队的数据开始查找，效率较低。

栈和队列的操作（遵循的规律是什么，结果是什么，特殊情况下的操作，如满、空等）

规律：栈只能在栈头插入和删除，队列在队尾插入，队头删除
栈的满空及操作
队列的满空及操作：
假溢出：假设这个队列的总个数不超过最大数，但目前如果接着入队的话，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做“假溢出”！！！！！！。
元素个数计算公式：==(rear-front+M)%M==

常用的栈和队列的存储结构（循环队列、共享空间的栈等等）

循环队列：在队列的基础结构上通过公式来变换font和rear的下一个位置，达到循环效果
当添加一个元素时,(rear+1)%MAXQSIZE; //理解为什么求余？
当删除一个元素时,(front+1)%MAXQSIZE；//理解为什么求余？
**当rear=front的时候，队列可能是满，也可能是空。
因为存在满和空两种情况，我们需要分别判断：
满：当队列添加元素到rear的下一个元素是head的时候，也就是转圈子要碰头了，我们就认为队列满了。(Q.rear+1)%MAXSIZE=Q.front
空：当队列删除元素到head=rear的时候，我们认为队列空了。Q.rear==Q.front,不一定为0
共享空间栈：利用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈顶为该数组的末端，每个栈从各自的端点向中间延伸。

数组的存储地址计算方法（计算公式、计算过程、计算结果）

数组类型存储地址的计算（a是数组首地址，len是每个数组元素所占长度）
一维数组a[n] a[i]的存储地址：a+i*len
二维数组：a[m][n] 按行存储：a+(i * n+j) * len；按列存储：a+(j * m+i) * len

数组类型	存储地址的计算（a是数组首地址，len是每个数组元素所占长度）
一维数组`a[n]`	a[i]的存储地址：`a+i*len`
二维数组：`a[m][n]`	按行存储：`a+(i * n+j) * len`；按列存储：`a+(j * m+i) * len`

特殊矩阵的存储地址计算方法（特殊矩阵种类、计算公式、过程和结果）

对称矩阵
上三角、下三角矩阵
对角矩阵

特殊矩阵的压缩存储

（各种特殊矩阵的压缩存储_-CSDN博客_矩阵的压缩存储）

3、字符串

字符串的比较

(在两个串中选短串长度，从第一个字符到目标长度一个一个去比，直到两字符不一样时就可比较出大小)

字符串的常规操作方法及其应用

4、树

二叉树的先序、中序和后续遍历（算法思路、遍历结果）

先序遍历：首先访问根结点，然后遍历左子树，最后遍历右子树（根->左->右）
顺序：访问根节点->前序遍历左子树->前序遍历右子树
/* 以递归方式 前序遍历二叉树 */
void PreOrderTraverse(BiTree t)
{
     if (t == null)    
     {
         return ;
     }
    System.out.println(t.data); // 打印根节点
    PreOrderTraverse(t.lchild); // 访问左子树
    PreOrderTraverse(t.rchild); // 访问右子树
}
中序和后序的区别只是根在中和后，左右顺序不变，代码实现方式和上述代码差不多，就是三条的语句顺序不一样

二叉树的拓扑特性（叶子数量、节点数量、深度、节点的度等因素的相互关系、完全二叉树与满二叉树）

二叉树的性质
n0 = n2 + 1
总结点数 =n0 + n1 + n2 (度为0、1、2的结点数之和)
总结点数 = n1 + 2n2 + 1 （度为1、2的结点的分支+根节点）
相减得：n0 = n2 + 1
包含n个结点的二叉树的高度至少为 ![[公式]](https://www.zhihu.com/equation?tex=log_%7B2%7D%28n%2B1%29)
重构二叉树
已知前序遍历序列和中序遍历序列，可以唯一确定一颗二叉树
已知后序遍历序列和中序遍历序列，可以唯一确定一颗二叉树
已知前序遍历序列和后序遍历序列，无法确定一颗二叉树
前序为父节点-左节点-右节点，后序为左节点-右节点-父节点，两者的拓扑序列是一样的，所以无法建立
特殊的二叉树
1. 斜树
定义：
所有结点都只有左子树的二叉树 -----> 左斜树
所有结点都只有右子树的二叉树 -----> 右斜树
特点：每层只有一个结点，结点个数等于二叉树深度
2. 满二叉树
定义：
所有分支结点都存在左子树和右子树
所有叶子都在同一层上
特点：
叶子只出现在最下一层
非叶子节点度一定为2
同样深度二叉树中，满二叉树结点个数最多，叶子树最多
叶子结点数为2^h
第k层的结点数是：2^(k-1)
3. 完全二叉树
定义：对于具有n个结点的二叉树按层序编号，如果每个结点的编号与同样深度的满二叉树中对应编号的结点在二叉树中位置完全相同，则该二叉树称为完全二叉树。
特点：
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
叶子结点只出现在最下两层
最下层的叶子一定集中在左部连续位置
倒数二层若有叶子节点一定集中在右部连续位置
如果结点度为1，则该结点只有左孩子
同样结点数的二叉树，完全二叉树的深度最小
4. Huffman Tree
定义：带权路径长度最小的二叉树
构建算法：
根据给定的n个权值{w1,w2,...,wn}构成n棵二叉树的集合F={T1,T2,...,Tn},其中每棵二叉树Ti只有一个带权为wi根节点，左右子树均为空。
在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根节点的权值为其左右子树上根节点的权值之和。
在F中删除这两棵树，同时将新得到的二叉树加入F中。
重复2和3步骤，知道F只含一棵树为止。得到的便是Huffman Tree

二叉树与森林的互相转换

首先要知道二叉树转树：(把右孩子当兄弟)
二叉树转森林：(从根节点开始，把所有能找到的又孩子都删除，在分离后的二叉树中将二叉树转为树)
其他：数据结构——树、森林和二叉树之间的转换 - 王陸 - 博客园 (cnblogs.com)

霍夫曼树的构建方法

二叉树的应用（递归方法的应用）

创建二叉树，删除二叉树，遍历二叉树，和打印二叉树的深度(希冀平台)

5、图

图的遍历方法（算法思想、结果）

图的存储方法（各自的结构、特性），能完成存储结果与图的互相转换（给出图画存储结果，给出存储结果画图）

图的储存-邻接矩阵实现思路
创建一个数组用来存储图中设计的所有顶点
创建一个二维数组用来存储顶点之间的关系
用二维数组定义：int g[ N ][ N ];
无向图：g[i][j]=g[j][i];
有向图：g[i][j]!=g[j][i];
权值：g[i][j]存结点i到节点j的权值
优点：适合稠密图，对边的增删改查操作简单
缺点：
存储复杂度高，可能会造成空间浪费
一般情况下不能存重边
图的存储-邻接表实现思路
创建一个顶点数组用于存储顶点信息（数组中的结点一个是data用于存储顶点内的数据还一个是指针用于指向关系链表中的额第一个结点）
创建一个关系链表用于存储所有和当前顶点有关系的顶点信息(链表中的结点信息大概有index当前顶点的索引，data当前顶点的内容，next用于指向下一个和对应顶点数组中的顶点有关系的结点)
优点：适用于稀疏图，存储效率比较高，存储时间复杂度O(V+E).可以存重边。
缺点：编程比邻接矩阵麻烦、访问和修改慢。

最小生成树的构造（不同算法的名称与思想、过程、结果）

最小生成树是一副连通加权无向图中一棵权值最小的生成树。
最小生成树是图论算法中比较经典的问题，在现实生活中也有非常多的应用。有两种比较经典的算法,都是使用了贪心的思想解决：
Prim算法（普利姆算法）
Prim算法的每一步都会为一棵生长中的树添加一条边，该树最开始只有一个顶点，然后会添加{V-1}个边。每次总是添加生长中的树和树中除该生长的树以外的部分形成的切分的具有最小权值的横切边。Prim算法的时间复杂度为{O(E + VlogV)}。
### 普里姆算法示例

根据上面加权连通图找到最小生成树。

首先选择顶点 A 作为起点。顶点 D、F、B 与 A 相连，且 AD 之间的权值最小，因此选择这条边。此时 A、D 为已选择顶点，E、F、B 为待选择顶点，H、G 为未选择顶点。

下一个顶点应选择离 A、D 权值最小的顶点，因此选择 AB 这条边。此时 A、D、B 为已选择顶点，E、F、G 为待选择顶点，H 为未选择顶点。

下一个顶点应选择离 A、D、B 权值最小的顶点，因此选择 DE 这条边。此时 A、D、B、E 为已选择顶点，F、G、H 为待选择顶点，没有未选择顶点。

下一个顶点应选择离 A、D、B、E 权值最小的顶点，因此选择 EH 这条边。此时 A、D、B、E、H 为已选择顶点，F、G 为待选择顶点，没有未选择顶点。

下一个顶点应选择离 A、D、B、E、H 权值最小的顶点，因此选择 FH 这条边。此时 A、D、B、E、H、F 为已选择顶点，G 为待选择顶点，没有未选择顶点。

最后，只剩下一个顶点 G，到顶点 G 的权值最小的是 HG。现在图中所有顶点都连接了，红色连接的边就是最小生成树，最小生成树的权值之和为 42。
### 总结
普里姆算法就是通过一个顶点扩散开找权值最小的边，所经过的顶点和边就是这个图的最小生成树。通过不用的数据结构存储图会导致时间复杂度不一致，用邻接矩阵的时间复杂度是 $O(V^{2})$ )，二叉堆和邻接表的时间复杂度是 $O(E log V )$ )。
Kruskal算法（克鲁斯卡尔算法）
按照边的权重顺序（从小到大）将边加入生成树中，但是若加入该边会与生成树形成环则不加入该边。直到树中含有{V-1}条边为止。这些边组成的就是该图的最小生成树。Kruskal算法的时间复杂度为{ElogE}
值得注意的是，在判断生成树是否有环时使用了并查集这样的数据结构
### 克鲁斯克尔算法
克鲁斯克尔算法（Kruskal's algorithm）跟普里姆算法一样，是一种用来查找最小生成树的算法，但算法的实现不一样，它是通过对权值从小到大顺序排列来查找最小生成树的。
### 克鲁斯克尔算法步骤
1.将原图中所有的边按权值从小到大排序。
2.从权值最小的边开始，如果这条边连接的两个节点于图中不在同一个已连接的边中，则记录该顶点为已选择。
3.重复步骤2，直至图中所有的节点都连通，就找到了连通图的最小生成树。
### 克鲁斯克尔算法时间复杂度
假如我们有 V 表示图中的顶点数，E 表示图中的边数。平均时间复杂度为 $O(E log V )$ )。
### 克鲁斯克尔算法示例

用克鲁斯克尔算法找到加权连通图的最小生成树。

通过对图中所有边的权值进行排序，得到 AD 边的权值最小为 5，并高亮标记。

然后下一条权值最小的边是 FH，权值为 6，并高亮标记。（注意不要构成环）

然后下一条权值最小的边有两条 AB 和 EH，权值为 7，我们任意选一条边 AB，并高亮标记。（注意不要构成环）

然后下一条权值最小的边是 EH，权值为 7，并高亮标记。（注意不要构成环）

然后下一条权值最小的边是 HG，权值为 8，并高亮标记。（注意不要构成环）

最后一条权值最小的边是 DE，权值为 9，并高亮标记。现在图中所有顶点都连接了，红色连接的边就是最小生成树，最小生成树的权值之和为 42。
注意：在权值相同的边，我们可以任意选择一条边，但选择的边不能跟以前的边构成环。如果当权值最小的边跟已选择的边构成了环，就跳过当前的边，继续下一条权值最小的边。
### 总结
克鲁斯克尔算法跟普里姆算法一样，是一种用来查找最小生成树的算法。
对比两个算法，克鲁斯卡尔算法主要是针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大的优势；而普里姆算法对于稠密图，即边数非常多的情况会更好一些。

AOE图（拓扑排序方法、关键路径的概念与计算方法）

6、排序

各个排序方法的算法思想（核心代码实现）
各排序方法的时间复杂度与空间复杂度
各排序方法的特性（最好情况、最坏情况、平均情况、稳定性等）以及比较（给定数据特点，选择最佳排序方法等）
堆排序：初始化、排序过程中的调整方法

往这看十大经典排序算法总结（JavaScript描述） - 掘金 (juejin.cn)

7、查找

折半查找的算法思想（核心代码实现）、所使用的数据结构（逻辑结构、存储结构）特点、

也叫二分查找。是在特定的有序列表中查找指定的值。返回改值在数组中的索引。优点是比较次数少，查找速度快，平均性能好。
方法：
从数组的中间元素查找该值，如果该值大于或小于中间元素，则在数组大于或小于的那块区域查找；
如果该元素恰好等于该值，则返回；
重复以上过程，直到找到目标元素的索引，查找成功;或者直到子数组为空，查找失败。
必须为有序顺序表。
核心代码：
  let arr = [2, 5, 6, 7, 8, 9, 10, 15];
  let key = 5;
  function mySearch(arrSort) {
      var low = 0;
      let high = arrSort.length - 1;
      while (low <= high) {
         let mid = parseInt((high + low) / 2);
         if (key > arrSort[mid]) {
            low = mid + 1
         } else if (key < arrSort[mid]) {
            high = mid - 1
         }
         else if (key == arrSort[mid]) {
            return mid;
         }
      }

   }
   console.log('mySearch', mySearch(arrSort))

散列法(哈希)存储的思想（常用构造方法思路以及冲突解决方法）

Alipay
Wechat

手机上阅读

最后一次更新于2022-01-27

What's Blog.

程序猿，给社会主义造 Bug

数据结构复习重点