环形缓冲区、链表及二叉树示例

亦凉 2024-04-03 08:06 58阅读 0赞

**目录**

一、环形缓冲区

二、链表

三、二叉树

--------------------

## 一、环形缓冲区 ##

循环队列一般是以**环形缓冲区（ring buffer）**的方式实现的，它是一种用于表示一种固定尺寸、头尾相连的缓冲区的数据结构，适合缓存数据流。假如我们用6个元素的数组来实现一个环形缓冲区，这时可以从起始位置开始有序的存储数据，然后再按照存储时的顺序把数据读出来。在数组的末尾写入数据后，后一个数据就会从缓冲区的头开始写，这样，数组的末尾和开头就连接起来了

环形缓冲区模型：

![64e9f341f0874e8186835f768618dbd1.png][]

## 二、链表 ##

**链表**是可以不用考虑索引的顺序就可以对元素进行读写的方式。通过链表，可以高效的对数据元素进行**添加**和**删除**操作。

在实现数组的基础上，除了数据的值之外，通过为其附带上下一个元素的索引，即可实现**链表**。数据的值和下一个元素的地址（索引）就构成了一个链表元素，如下所示：

链表的数据结构：

> ![6a42b0b2ff8b485aa0fe90fd6a836bad.png][]
> 
> 对链表的添加和删除都是非常高效的，假如我们要删除地址为p\[2\]的元素

链表的删除：

> ![40bccb4c26a441fba794adb11f2c5e6c.png][]
> 
> 删除地址为p\[2\]的元素后，直接将链表剔除，并把p\[2\]前一个元素p\[1\]的**指针域**指向p\[2\]下一个链表元素的数据区即可

链表的添加：

> ![e2ea3c6e21e14dc392c59ebbf1e8eaca.png][]
> 
> 对于新添加进来的链表，需要确定插入位置，比如要在p\[2\]和p\[3\]之间插入地址为p\[6\]的元素，需要将p\[6\]的前一个位置p\[2\]的指针域改为p\[6\]的地址，然后将p\[6\]的指针域改为p\[3\]的地址即可
> 
> 链表的添加不涉及到**数据的移动**，所以链表的添加和删除很快，而数组的添加设计到数据的移动，所以比较慢，通常情况下，使用数组来检索数据，使用链表来进行添加和删除操作

## 三、二叉树 ##

**二叉树**也是一种检索效率非常高的数据结构，二叉树是指在链表的基础上往数组追加元素时，考虑到数组的大小关系，将其分成左右两个方向的表现形式。假如我们把50这个值保存到了数组中，那么如果接下来要进行值写入的话，就需要和50比较，确定谁大谁小，比50数值大的放右边，小的放左边，下图是二叉树的比较示意图：

![7db8da6b104d45aaa16e8c7acb6753ab.png][]

二叉树是由链表发展而来，因此二叉树在追加和删除元素方面也是同样有效的

这一切的演变都是以内存为基础的。

[64e9f341f0874e8186835f768618dbd1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/32188837e88c4029a0d74a4298dbb287.png
[6a42b0b2ff8b485aa0fe90fd6a836bad.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/caef098f4ab34b619d35fd844fab0620.png
[40bccb4c26a441fba794adb11f2c5e6c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/b26cc7eda486487a844223ae30072d6e.png
[e2ea3c6e21e14dc392c59ebbf1e8eaca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/341d9769ee154b58b8e80a00d5ddf04b.png
[7db8da6b104d45aaa16e8c7acb6753ab.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/dd2d27d781564378a5224172d64f306c.png