【考研408常用数据结构】C/C++实现代码汇总

àì夳堔傛蜴生んèń 2024-02-24 02:58 13阅读 0赞

#### 文章目录 ####

*  前言
 *  排序算法（代码简短好记版）
 *  数组
 *   *  多维数组的原理、作用
     *  稀疏数组
 *  链表
 *   *  单向链表的增删改查的具体实现思路
     *  约瑟夫环问题（可不学）
     *  双向链表
 *  树
 *   *  二叉搜索树
     *  中序线索二叉树
     *  哈夫曼树的编码与译码
     *  红黑树
     *  B树
     *  B+树
 *  堆
 *   *  顺序与链式结构队列实现
     *  优先队列排序算法（重点）
 *  栈
 *   *  顺序存储结构与链式存储结构栈
     *  单调栈算法（可不学）
 *  图
 *   *  邻接矩阵与邻接表的深度优先遍历

## 前言 ##

[Github代码仓库地址][Github]  
这一篇文章是因为有几个玩的比较好的朋友觉得我DS学的还行，然后他们也要准备考研了（有24也有25的），就希望我出一篇讲DS的文章，所以就有了这篇文章。  
（毕竟现在的互联网好像是不论是小中大厂好像都喜欢问算法哈哈哈，也算给自己复习一下）  
其实掌握这些数据结构最快速的方法就是先了解基础，自己动手实现一边，然后分析这些结构可以用在什么场景下。  
然后基于他们的特性去刷题。  
比如我做树的题的时候，一定最先想到的就是递归，左子树递归，右子树递归等操作。  
要求O(1)时间复杂度想到的就是Hash表，要求无额外空间使用，那就是原地算法。  
字符串顺序颠倒，反转，想到手摇算法等等。  
附一张LeetCode刷题情况（哈哈哈，很多都是补卡的）。  
![在这里插入图片描述][2455f249500c44dc8f407ad94f90421f.png]  
反正刷算法，最重要的应该就是perseverance。  
![在这里插入图片描述][31899b4efa9e4c2385443a6347411af5.png]

## 排序算法（代码简短好记版） ##

这部分的文章我会简单的讲解一下这些排序算法的实现思路，并且用尽可能短的代码实现排序功能，减少记忆。负担，当然，算法最重要的还是理解人家的思想。所以我会用尽可能详细的语言去描述这些算法的实现思路。  
[排序算法][Link 1]

## 数组 ##

### 多维数组的原理、作用 ###

[多维数组的原理与作用][Link 2]

### 稀疏数组 ###

[稀疏数组][Link 3]

## 链表 ##

### 单向链表的增删改查的具体实现思路 ###

[详解单链表的增删改查的实现][Link 4]  
[单向链表的CRUD][CRUD]

### 约瑟夫环问题（可不学） ###

[约瑟夫环问题][Link 5]

### 双向链表 ###

[双向链表的CRUD][CRUD 1]

## 树 ##

### 二叉搜索树 ###

[顺序与链式存储结构，前中后序以及层序遍历][Link 6]

### 中序线索二叉树 ###

[中序线索二叉树的实现][Link 7]

### 哈夫曼树的编码与译码 ###

[哈夫曼树的编码实现][Link 8]  
[哈夫曼树的译码实现][Link 9]

### 红黑树 ###

### B树 ###

### B+树 ###

## 堆 ##

### 顺序与链式结构队列实现 ###

[顺序与链式存储结构队列实现][Link 10]

### 优先队列排序算法（重点） ###

优先队列排序算法我第一次见到是再MySQL中。  
对于MySQL5.6之后，会有一个算法叫做优先队列排序算法，大概方式就是维护一个大小为limit X中X数量的大顶堆，然后遍历所有数据并替换大顶堆的值，这样子就不需要对无用的数据进行排序了。并且我也在2023的考研题目中一眼就看到了基于优先队列排序算法的题目，所以我感觉这个算法思路还是很妙的。

[优先队列][Link 11]

## 栈 ##

### 顺序存储结构与链式存储结构栈 ###

[顺序栈和链栈详解][Link 12]  
[代码实现与讲解][Link 13]

### 单调栈算法（可不学） ###

## 图 ##

### 邻接矩阵与邻接表的深度优先遍历 ###

[图操作之邻接矩阵与邻接表的深度优先遍历][Link 14]

[Github]: https://github.com/ZhangBlossom/408DataStructure
[2455f249500c44dc8f407ad94f90421f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/24/c269d323db464c2fbb6c654b3d5ff78e.png
[31899b4efa9e4c2385443a6347411af5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/24/96d0dc194ad64066b013cd3c4b620b9e.png
[Link 1]: https://blog.csdn.net/Zhangsama1/article/details/133840046?csdn_share_tail=%7B%22type%22:%22blog%22,%22rType%22:%22article%22,%22rId%22:%22133840046%22,%22source%22:%22Zhangsama1%22%7D
[Link 2]: https://blog.csdn.net/Zhangsama1/article/details/133708730?spm=1001.2014.3001.5502
[Link 3]: https://blog.csdn.net/Zhangsama1/article/details/133710992?csdn_share_tail=%7B%22type%22:%22blog%22,%22rType%22:%22article%22,%22rId%22:%22133710992%22,%22source%22:%22Zhangsama1%22%7D
[Link 4]: https://blog.csdn.net/Zhangsama1/article/details/119245504
[CRUD]: https://blog.csdn.net/Zhangsama1/article/details/133675993?csdn_share_tail=%7B%22type%22:%22blog%22,%22rType%22:%22article%22,%22rId%22:%22133675993%22,%22source%22:%22Zhangsama1%22%7D
[Link 5]: https://blog.csdn.net/Zhangsama1/article/details/119547481
[CRUD 1]: https://blog.csdn.net/Zhangsama1/article/details/133709835?spm=1001.2014.3001.5502
[Link 6]: https://blog.csdn.net/Zhangsama1/article/details/133744258?csdn_share_tail=%7B%22type%22:%22blog%22,%22rType%22:%22article%22,%22rId%22:%22133744258%22,%22source%22:%22Zhangsama1%22%7D
[Link 7]: https://blog.csdn.net/Zhangsama1/article/details/121362652
[Link 8]: https://blog.csdn.net/Zhangsama1/article/details/121333589
[Link 9]: https://blog.csdn.net/Zhangsama1/article/details/121621128
[Link 10]: https://blog.csdn.net/Zhangsama1/article/details/119685628
[Link 11]: https://blog.csdn.net/Zhangsama1/article/details/133869234?csdn_share_tail=%7B%22type%22:%22blog%22,%22rType%22:%22article%22,%22rId%22:%22133869234%22,%22source%22:%22Zhangsama1%22%7D
[Link 12]: https://blog.csdn.net/Zhangsama1/article/details/119581560?utm_source%20=%20uc_fansmsg
[Link 13]: https://blog.csdn.net/Zhangsama1/article/details/133706490?csdn_share_tail=%7B%22type%22:%22blog%22,%22rType%22:%22article%22,%22rId%22:%22133706490%22,%22source%22:%22Zhangsama1%22%7D
[Link 14]: https://blog.csdn.net/Zhangsama1/article/details/121595451