数据结构面试精华整理（考研、保研和工作）_1.有一个循环队列q,里面的编号是0到n-1,头尾指针分别是f,p,现在求q中元素的个数?

数据结构

1. O(n)的大O是什么意思？什么是时间复杂度？

O含义：大O表示同阶，同等数量级

时间复杂度： 时间复杂度是算法执行时间的度量。算法的时间复杂度又称为算法的渐进时间复杂度，它表示随着问题规模 n 的增大，算法执行时间的增长率和 f(n) 的增长率相同。其中，f (n) 表示基本语句重复执行的次数是问题规模 n 的某个函数。

2. 线性存储结构和链式存储结构的优缺点？

顺序存储：

优点：

1. 逻辑结构与物理结构是统一的，且其中的元素都是顺序存储的。
2. 方法简单，易于理解，各种语言中都有数组，易实现。
3. 不用为结点间的逻辑关系而增加额外的存储空间。
4. 表中数据元素可随机存取，顺序表具有按元素序号随机访问的特点。
5. 存储密度大，存储密度为1（存储密度是指数据元素本身所占用的存储量和整个结点结构所占用的存储量之比）。

缺点：

1. 做插入、删除操作时，需要移动大量元素，因此对很长的顺序表操作效率低，插入和删除操作不方便。
2. 要预先分配存储空间，预先估计过大，会导致存储空间浪费，估计过小，会造成数据溢出。

链式存储：

优点：

1. 做插入、删除操作时很方便，不需要移动数据元素，动态性强。
2. 不用预先估计存储空间的规模。

缺点：

1. 表中数据元素不可随机存取。
2. 链式存储的操作是基于指针的，但不是所有语言中都有指针类型。
3. 对每个数据元素而言，除了自身信息外，还需要一起存放其后继存储单元的地址，存储密度小，存储密度小于1。

3. 解释一下顺序存储和链式存储。

顺序存储： 线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。顺序表可以随机存取表中的任意一个元素，它的存储位置可以用一个简单直观的公式表示，但插入和删除操作需要移动大量元素。

链式存储： 线性表的链式存储又称为单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素，因此插入和删除操作不需要移动元素。利用单链表可以解决顺序表需要大量连续存储单元的缺点，但单链表附加指针域，也存在浪费存储空间的缺点。由于单链表的元素离散的分布在存储空间中，所以单链表是非随机存储的存储结构，即不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从头开始遍历，依次查找。

4. 头指针和头结点的区别？

区别： 不管是否带头结点，头指针都始终指向链表的第一个结点，而头结点是带头结点的链表中的第一结点，结点中通常不存储信息。

注： 头结点的指针域指向线性表的第一个元素结点。

引入头结点的优点：

① 由于第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作保持一致，无需进行特殊处理。

② 无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就得到了统一。

5. 栈和队列的内存结构和区别？

内存结构：

区别：

1. 栈是后进先出，而队列是先进先出。
2. 对插入和删除操作的"限定"不同。 栈是限定只能在表的一端进行插入和删除操作的线性表。而队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。
3. 遍历数据速度不同。 栈只能从头部取数据，也就最先放入的需要遍历整个栈最后才能取出来，而且在遍历数据的时候还需要为数据开辟临时存储空间，保持数据在遍历前的一致性。而队列则不同，它基于地址指针进行遍历，而且可以从头或尾部开始遍历，但不能同时遍历，无需开辟临时空间，因为在遍历的过程中不影响数据结构，速度要快的多。

6. 有一个循环队列 Q，里面的编号是 0 ~ n-1，头、尾指针分别是 r , p, 现在求 Q 中的元素个数？

元素个数： ( p - r + n ) / n

7. 如何区分循环队列是空队还是队满？

为了区分队空还是队满有三种处理方式：

① 牺牲一个存储单元来区分队空和队满，入队时少用一个队列单元。

队满条件：（Q.rear + 1) % MaxSize == Q.front

队空条件：Q.front == Q.rear

② 类型中增设表示元素个数的数据成员。

队满条件：Q.size == MaxSize

队空条件：Q.front == Q.rear

③ 类型中增设 tag 数据成员，以区分队满还是队空。

队满： tag == 1
队空： tag == 0

8. **堆、大根堆、小根堆的实现及应用 **

若 n 个关键字序列L[1…n] 满⾜下⾯某⼀条性质，则称为堆（Heap）：

① 若满⾜：L(i)≥L(2i)且L(i)≥L(2i+1) （1 ≤ i ≤n/2 ）—— ⼤根堆（⼤顶堆）
② 若满⾜：L(i)≤L(2i)且L(i)≤L(2i+1) （1 ≤ i ≤n/2 ）—— ⼩根堆（⼩顶堆）

⑴ 堆的应用

① 堆排序

② 优先队列

③ 快速找最值

⑵ 大根堆的 C++ 代码实现

//将以k为根结点的树调整为大根堆 
void HeadAdjust(int a[], int k, int len){//注：除k结点外其他已经有序 
	a[0] = a[k];//a[0]暂存子树根节点 
	for(int i = 2 * k; i <= len; i *= 2){//沿较大子结点筛选 
		if(i < len && a[i] < a[i + 1]) i ++;//i为较大子结点下标 （i<len表示k有右孩子） 
		if(a[0] >= a[i]) break;//筛选结束 
		else{
			a[k] = a[i];//递归处理子结点 
			k = i;
		}
	}
	a[k] = a[0];
}

//建大根堆 时间复杂度---O(n)  
void BuildHeap(int a[], int len){//从下往上建堆,从最后一个叶子结点的根节点开始 
	for(int i = len / 2; i > 0; i --){//处理所有非终端结点 
		HeadAdjust(a, i , len);
	}
}//建堆过程关键字的比较次数不超过4n(定理) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

⑶ 小根堆的 C++ 代码实现

//将以k为根结点的树调整为小根堆 
void HeadAdjust(int a[], int k, int len){//注：除k结点外其他已经有序 
	a[0] = a[k];//a[0]暂存子树根节点 
	for(int i = 2 * k; i <= len; i *= 2){//沿较小子结点筛选 
		if(i < len && a[i] > a[i + 1]) i ++;//i为较大子结点下标 （i<len表示k有右孩子） 
		if(a[0] <= a[i]) break;//筛选结束 
		else{
			a[k] = a[i];//递归处理子结点 
			k = i;
		}
	}
	a[k] = a[0];
}

//建小根堆 时间复杂度---O(n)  
void BuildHeap(int a[], int len){//从下往上建堆,从最后一个叶子结点的根节点开始 
	for(int i = len / 2; i > 0; i --){//处理所有非终端结点 
		HeadAdjust(a, i , len);
	}
}//建堆过程关键字的比较次数不超过4n(定理) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

9. 哈希表的概念、构造方法、哈希有几种类型？哈希冲突的解决办法？

⑴ 概念： 哈希表又称散列表，是根据关键字而直接进行访问的数据结构。也就是说，哈希表建立了关键字和存储地址之间的一种直接映射关系。

⑵ 构造方法:

① 直接定址法 —— 直接取关键字的某个线性函数值为哈希地址。

② 除留余数法 —— 假定哈希表长度为 m ，取一个不大于 m 但最接近或等于 m 的质数 p ，利用如下公式把关键字转化为哈希地址 , H(key) = key % p

③ 数字分析法 —— 设关键字是 r 进制数，选取数码分布较为均匀的若干位作为哈希地址。

④ 平方取中法 —— 取关键字的平方值的中间几位作为哈希地址。

⑶ 类型: 链接

⑷ 哈希冲突的解决方法：

① 开放寻址法 —— 可存放新表项的空闲地址，既向它的同义词表项开放，又向它的非同义词表项开放。

② 拉链法 —— 对于不同的关键字可能会通过哈希函数映射到同一地址，为避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性表由其哈希地址唯一标识。

10. 如何判断链表是否有环? （非常重要）

[四种方法]

① 穷举遍历

思路：

设一个检测指针 k 和一个遍历指针 q，count 记录遍历指针 q 走的步数。
遍历指针每走一步，检测指针 k 就走遍历指针 q 之前走过的节点，若发现相同的节点便说明有环
直到遍历节点 q 遍历完整个链表，即q = NULL 为止。

$$时间复杂度：O(n^2)$$

$$空间复杂度：O(1)$$

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == NULL || head->next == NULL)
            return false;
        ListNode *k = head;//检测节点
        ListNode *q = head->next;//遍历节点
        int count = 0;//记录检测节点走了多少步
        while(q){
            for(int i = count;i > 0;i --){
                k = k-> next;
                if(k == q)
                    return true;
            }
            k = head;//还原
            q = q->next;
            count ++;
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

② 标记法

思路：在结点中设置一个标记变量，每走一个结点，就判断一次。若 visit == true，则说明有环。反之，说明无环。
$$时间复杂度:O(n)$$

$$空间复杂度:O(n)$$

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     bool visit;//标记
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *q = head;
        while(q)
        {
            if(q->visi t== true)//有环
                return true;
            else
                q->visit = true;
        }
        return false;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

③ 快慢指针

思路：

设置两个指针，一个慢指针 low 和一个快指针 fast。初始值 慢指针 low 指向第一个结点，快指针 fast 指向第二个结点。只要快指针不为空，则慢指针slow就先向后走一个。然后两轮处理快指针。只要未遍历完链表，则将快指针向后移动一个，并判断快慢指针是否相遇。一旦快慢指针相遇，则说明有环。反之，则说明无环。
$$时间复杂度：O(n)$$

$$空间复杂度:O(1)$$

class Solution {
public:
    bool hasCycle(ListNode *head) {//有头结点
        if(head == NULL||head->next == NULL)
            return false;
        ListNode *slow = head->next;//慢指针
        ListNode *fast = head->next->next;//快指针
        while(fast){//快指针不为空, 即未遍历到表尾
            slow = slow->next;//慢指针往后走一个
            for(int i = 0;i < 2;i ++){//未遍历完或者快慢指针未相遇，则快指针往后走两个
                if(fast->next == NULL){//链表未遍历完
                    return false;
                }
                fast = fast->next;//快指针往后走一个
                if(fast == slow){//快慢指针未相遇
                    return true;
                }
            }
        }
        return false;//无环
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

④ set 集合大小变化

思路：
根据集合的去重特性来判断。每遍历一个结点，就将该结点加入集合。若加入该新结点后，集合大小不再发生变化，则说明集合中的该元素已存在，即说明存在环。倘若，遍历完所有结点，集合大小都能正常判断，则无环。
$$时间复杂度：O(n)$$

$$空间复杂度：O(n)$$

class Solution {
public:
    bool hasCycle(ListNode *head) {
        set<ListNode*> a;
        ListNode *q = head;
        int count = 0;//记录set的大小
        while(q){
            a.insert(q);//讲结点插入集合
            if(count == a.size()){//集合大小未发生变化,说明该元素有重复,即有环
                return true;
            }
            q = q->next;//往下走一个
            count = a.size();// 更新count值
        }
        return false;//无环
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

11. 平衡二叉树、二叉排序树、完全二叉树、二叉搜索树的区别及如何构造？

⑴ 平衡二叉树：

为避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差的绝对值不超过 1，将这样的二叉树成为平衡二叉树。

⑵ 二叉排序树：

二叉排序树（也称 二叉查找树、 二叉搜索树 ) 或者是一课空树，或者是具有如下特性的二叉树：
① 若左子树非空，则左子树上所有结点的值均小于根节点的值。

②若右子树非空，则右子树上所有结点的值均大于根结点的值。

③ 左、右子树也分别是一课二叉排序树

即要求：左子树结点的值 < 根节点的值 < 右子树结点的值

⑶ 完全二叉树：

满二叉树：一棵高度为 h ,且含有 2^h - 1 个结点的二叉树称为满二叉树

完全二叉树：高度为 h 、有 n 个结点的二叉树，当且仅当其所有结点都与高度为 h 的满二叉树中编号为 1 ~ n 的结点一 一对应时，称为完全二叉树。

12. 如何由遍历序列构造一棵二叉树？已知先序序列和后序序列能否重现二叉树？（笔试经常考）

由遍历序列构造一个二叉树：

① 前序 + 中序遍历序列

② 后序 + 中序遍历序列

③ 层序 + 中序遍历序列

由先序序列和后序序列不能重现二叉树

**结论1： ** 若只给出一棵二叉树的 前 / 中 / 后 / 层序遍历序列中的一种，则不能唯一确定一棵二叉树。

结论2： 前序、后序、层序序列的两两组合无法唯一确定一棵二叉树。

13. B 树是什么？ B +树是什么？B+ 树在数据库中有什么应用？B 树和 B+ 树有什么区别？（非常重要）

B 树： B 树又称多路平衡查找树（绝对平衡）。一棵 m 阶 B 树或为空树，或为满足如下特性的 m 叉树：

① 树中每个结点至多有 m 棵子树，即至多含有 m - 1 个关键字

② 若根节点不是终端结点，则至少含有两棵子树。

③ 除根结点外的所有非叶结点至少 m / 2 （上取整）棵子树，即至少含有 m / 2 - 1（上取整）个关键字。

④ 所有⾮叶结点的结构如下：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NCHhGV64-1629253685579)(C:\Users\LJM\AppData\Roaming\Typora\typora-user-images\image-20210817191106742.png)]

其中，Ki（i = 1, 2,…, n）为结点的关键字，且满⾜K1 < K2 <…< Kn；Pi（i = 0, 1,…, n）为指向⼦树根结点的指针，且指针Pi-1所指⼦树中所有结点的关键字均⼩于Ki，Pi所指⼦树中所有结点的关键字均⼤于Ki，n（ m / 2 - 1 ≤ n ≤ m - 1）为结点中关键字的个数。

⑤ 所有的叶结点都出现在同⼀层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）。

B+ 树： 一课 m 阶的 B+ 树需要满足下列条件：( B+ 树是应数据库所需而出现的一种 B 树的变形 )

① 每个分支结点最多有 m 棵子树（孩子结点）

② 非叶根结点至少有两棵子树，其他每个分支结点至少有 m/2 上取整棵子树

③ 结点的子树个数与关键字个数相等

④ 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。

⑤ 所有分支结点（可视为索引的索引）中仅包含它的各个子结点（下一级的索引块）中关键字的最大值及指向其子结点的指针。

B + 树的应用： 关系型数据库的 “索引”（如MySQL）

B 树和 B+ 树的区别：

① 结点的子树个数不同

在 m 阶 B 树中，结点中的 n 个关键字对应 n + 1 棵子树。

在 m 阶 B+ 树中，结点中的 n 个关键字对应 n 个子树。

② 结点的关键字个数不同

在 m 阶 B 树中，根节点的关键字数 n∈[1, m - 1]，其他结点的关键字数 n∈[ m/2 - 1, m - 1] （上取整）

在 m 阶 B+ 树中，根节点的关键字数 n∈[1, m]，其他结点的关键字数n∈[m/2 , m] （上取整）

③ 关键字是否重复不同

在 m 阶 B 树中，各结点中包含的关键字是不重复的。

在 m 阶 B+ 树中，叶结点包含全部关键字，⾮叶结点中出现过的关键字也会出现在叶结点中。

④ 关键字所含信息不同

在 m 阶 B 树中，B树的结点中都包含了关键字对应的记录的存储地址

在 m 阶 B+ 树中，叶结点包含信息，所有⾮叶结点仅起索引作⽤。⾮叶结点中的每个索引项只含有对应⼦
树的最⼤关键字和指向该⼦树的指针，不含有该关键字对应记录的存储地址。

14. 红黑树的原理是什么？请描述一下建立过程。

红黑树原理和建立过程链接1

红黑树原理和建立过程链接2

15. 二叉搜索和单纯的线性搜索的区别？时间复杂度如何？

二者的区别：

① 二叉搜索要求对输入数据进行排序，而线性搜索则不需要。

② 二叉搜索需要排序比较，而线性搜索只需要相等比较即可。

③ 二叉搜索需要随机访问数据，而线性搜索仅需要顺序访问即可。

时间复杂度：

二叉搜索的复杂度为 O(log n)， 线性搜索的复杂度为 O(n)

16. 插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序（必考）、堆排序、基数排序等排序算法的基本思想？时间复杂度？稳定性？给出一个例子，问冒泡排序和快速排序在最坏情况下比较几次？（排序必考）

史上超全排序大全总结:

① 直接插入排序

② 折半插入排序

③ 希尔排序

④ 冒泡排序

⑤ 快速排序

⑥ 归并排序

⑦ 简单选择排序

⑧ 堆排序

⑨ 计数排序

⑩ 桶排序

⑪ 基数排序

17. 最小生成树和最短路径用什么算法来实现？ 迪杰斯特拉、弗洛伊德、普利姆、克鲁斯卡尔算法的基本思想是什么？时间复杂度如何？如何优化？（必考）

⑴ 最小生成树

生成树： 连通图的生成树是包含图中全部顶点的一个极小连通子图。（即边尽可能的少，但要保持连通）

最小生成树: 对于⼀个带权连通⽆向图 G = (V, E)，⽣成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设 R 为 G 的所有⽣成树的集合，若T为R中边的权值之和最⼩的⽣成树，则T称为 G 的最⼩⽣成树（Minimum-Spanning-Tree, MST）。

① Prim 算法： —— 用来求最小生成树

**普里姆算法基本思想：**从联通网络 N = {V,E} 中某一顶点 u0 出发，选择与他关联的最小权值的边，将其顶点加入到顶点集 S 中，此后就从一个顶点在 S 集中，另一个顶点不在 S 集中的所有顶点中选择出权值最小的边，把对应顶点加入到 S 集中，直到所有的顶点都加入到 S 集中为止。简言之，就是从某⼀个顶点开始构建⽣成树，每次将代价最⼩的新顶点纳⼊⽣成树，直到所有顶点都纳⼊为⽌。

时间复杂度：O(V^2) ，不依赖于边 | E |，适于求解边稠密的图。

② Kruskal 算法： —— 用来求最小生成树

**克鲁斯卡尔算法基本思想：**设有一个有 N 个顶点的联通网络 N = {V,E}, 初试时建立一个只有 N 个顶点，没有边的非连通图 T，T 中每个顶点都看作是一个连通分支，从边集 E 中选择出权值最小的边且该边的两个端点不在一个联通分支中，则把该边加入到 T 中，否则就再从新选择一条权值最小的边，直到所有的顶点都在一个联通分支中为止。简言之，就是每次选择⼀条权值最小的边，使这条边的两头连通（原本已经连通的就不选）直到所有结点都连通。

时间复杂度：O(|E|log|E|)，适合于边稀疏而顶点较多的图。

⑵ 最短路径

① Dijkstra算法

**迪杰斯特拉算法：**迪杰斯特拉算法是经典的单源最短路径算法，用于求某一顶点到其他顶点的最短路径，它的特点是以起始点为中心，层层向外扩展，直到扩展到终点为止。迪杰斯特拉算法要求边的权值不能为负权。

时间复杂度：O(V^2)

② Floyd 算法

**弗洛伊德算法：**弗洛伊德算法是经典的求任意顶点之间的最短路径，其边的权值可为负权。使⽤动态规划思想，将问题的求解分为多个阶段。
对于 n 个顶点的图 G，求任意⼀对顶点 Vi —> Vj 之间的最短路径可分为如下几个阶段：
#初始：不允许在其他顶点中转，最短路径是？
#0：若允许在 V0 中转，最短路径是？
#1：若允许在 V0、V1 中转，最短路径是？
#2：若允许在 V0、V1、V2 中转，最短路径是？
…
#n-1：若允许在 V0、V1、V2 …… Vn-1 中转，最短路径是？

时间复杂度：O(V^3)

空间复杂度：O(V^2)

核心代码：

//首先初始化矩阵 a[][]和 path[]···
for(int k = 0; k < n; k ++){//考虑以 Vk作为中转点
    for(int i = 0; i < n; i ++){//遍历整个矩阵
        for(int j = 0;  j < n; j ++){
            if(a[i][j] > a[i][k] + a[k][j]){//以Vk为中转点的路径更短
                a[i][j] = a[i][k] + a[k][j];//更新最短路径
                path[i][j] = k;//记录中转点
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

18. 简述一下邻接表和邻接矩阵，二者的联系和区别是什么？如何存储大数据？

邻接矩阵：

所谓邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵。

邻接表：

所谓邻接表，是指对图 G 中的每个顶点 V 建立一个单链表，第 i 个单链表中的结点表示依附于顶点 v 的边（对于有向图则是以顶点 v， 为尾的弧），这个单链表就称为顶点 vi 的边表（对于有向图则称为出边表）。边表的头指针和顶点的数据信息采用顺序存储（称为顶点表），所以在邻接表中存在两种结点：顶点表结点和边表结点。

19. 介绍一下深度优先搜索和广度优先搜索是如何实现的？

广度优先搜索：

**基本思想：**类似于二叉树的层序遍历算法。首先访问起始顶点 V,，接着由 V 出发，依次访问 V 的各个未访问过的邻接顶点 W1, W2,… Wn, 然后依次访问 W1, W2,…, Wn 的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为初始点，重复上述过程。
应用举例： Dijkstra 单源最短路径算法和 Prim 最小生成树算法也应用了类似的思想。

bool visited[MAX_VERTEX_NUM];//访问标记数组

void BFSTraverse(Graph G){//对图G进行广度优先遍历
    for(int i = 0; i < G.vexnum; i ++){
        visited[i] = false;//初始化标记数组
        InitQueue(Q);//初始化辅助队列
        for(int i = 0; i < G.vexnum; i ++){//遍历所有结点
            if(!visited[i]){//若该结点未被访问过
                BFS(G, i);//从当前结点开始BFS
            }
        }
    }
}

void BFS(Graph G, int v){//从顶点V出发，广度优先遍历图G
    visit(v);//访问初始顶点v
    visited[v] = true;//已访问该顶点
    Enqueue(Q, v);//顶点v入队
    while(!isEmpty(Q)){
        DeQueue(Q, v);//顶点v出队
        for(w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)){//遍历v的所有临接点
            if(!visited(w)){//w为v的尚未访问的邻接点
                visit(w);//访问顶点w
                visited[w] = true;//当前结点已经被访问
                EnQueue(Q, w);//顶点w入队
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

深度优先搜素：

**基本思想：**首先访问图中某一起始顶点V, 然后由v 出发，访问与v 邻接且未被访问的任一顶点 W1，再访问与W1邻接且未被访问的任一顶点 W2 …重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

bool visited[MAX_VERTEX_NUM];//访问标记数组

void DFSTraverse(Graph G){//对图G进行深度度优先遍历
    for(int v = 0; v < G.vexnum; v ++){
        visited[v] = false;//初始化标记数组
    }
    for(int v = 0; v < G.vexnum; v ++){//遍历所有结点
        if(!visited[v]){//若该结点未被访问过
            DFS(G, v);//从当前结点开始DFS
        }
    }
}

void DFS(Graph G, int v){
    visit(v);
    visited[v] = true;
    for(w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)){//遍历v的所有临接点
            if(!visited(w)){//w为v的尚未访问的邻接点
                DFS(G, w);
            }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

20. 介绍一下字符串匹配算法：朴素的匹配算法和 KMP 算法，它们的实现过程如何？

朴素模式匹配算法：

将主串中所有⻓度为 m 的⼦串依次与模式串对⽐，直到找到⼀个完全匹配的⼦串，或所有的⼦串都不匹配为⽌。

(⼀旦发现当前这个⼦串中某个字符不匹配，就只能转⽽匹配下⼀个⼦串（从头开始）, 最多对比 n - m + 1 个子串 )

设主串⻓度为 n，模式串⻓度为 m，则
最坏时间复杂度 = O( nm )
最好时间复杂度 = O( n )

int Index_BF(SString S, SString T, int pos){
    int i = pos, j = 1;
    while(i <= S.length && j <= T.length){// 两个串均未比较到串尾
        if(S.ch[i] == T.ch[i]){// 继续比较后续字符
            i ++;
            j ++;
        }
        else{// 指针后退重新开始匹配
            i = i - j + 2;
            j = 1;
        }
    }
    if(j > T.length) return i - T.length;//匹配成功
    else return 0;//匹配失败
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

KMP 算法：

KMP算法精髓： 利⽤好已经匹配过的模式串的信息,利⽤next数组进⾏匹配（主串指针不回溯）

KMP 算法，最坏时间复杂度 O( m + n )
其中，求 next 数组时间复杂度 O( m )
模式匹配过程最坏时间复杂度 O( n )

int index_KMP(SString S, SString T, int pos){
    int i = pos, j = 1;
    while(i <= S.length && j <= T.length){// 两个串均未比较到串尾
        if(j == 0 || S.ch[i] == T.ch[i]){// 继续比较后续字符
            i ++;
            j ++;
        }
        else{
            j = next[j];// 模式串向右移动
        }
    }
    if(j > T.length) return i - T.length;// 匹配成功
    else return 0;// 匹配失败
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

next数组：

next 数组的作⽤： 当模式串的第 j 个字符失配时，从模式串的第 next[j] 的继续往后匹配

next 函数意义： 当第 j 个字符匹配失败，由前 1 ~ j - 1个字符组成的串即为 S，则 next [ i ] = S 的最长相等前后缀长度 + 1 。

串的前缀： 包含第一个字符，且不包含最后一个字符的子串。

串的后缀： 包含最后一个字符，且不包含第一个字符的子串。

void get_next(SString T, int next[]){//朴素版next函数
    int i = 1, j = 0; 
    next[1] = 0;//初始化next函数值
    while(i < T.length){
        if(j == 0 || T.ch[i] == T.ch[j]){
            i ++;
            j ++;
            next[i] = j;
        }
        else j = next[j];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

void get_nextval(SString T, int nextval[]){//改进版next函数
    int i = 1, j = 0;
    nextval[1] = 0;//初始化next函数值
    while(i < T.length){
        if(j == 0 || T.ch[i] == T.ch[j]){
            i ++;
            j ++;
            if(T.ch[i] ！= T.ch[j]) nextval[i] = j;
            else nextval[i] = nextval[j];
        }
        else j = nextval[j];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

谢谢观看， 欢迎交流、支持点赞和收藏哦~