网站栏目合理性,订货商城小程序源码,企业网站上海 优帮云,管理系统主页写在前面#xff0c;2023年11月开始进入岗位#xff0c;工作岗位是嵌入式软件工程师。2024年是上班的第一年的#xff0c;希望今年收获满满#xff0c;增长见闻。
数据结构—环形缓冲区
为什么要使用环形数组#xff0c;环形数组比起原来的常规数组的优势是什么#xf…写在前面2023年11月开始进入岗位工作岗位是嵌入式软件工程师。2024年是上班的第一年的希望今年收获满满增长见闻。
数据结构—环形缓冲区
为什么要使用环形数组环形数组比起原来的常规数组的优势是什么
环形数组Circular Array是一种特殊类型的数组其元素在内存中首尾相接形成一个环形。环形数组具有一些独特的优势和用途使其在某些应用场景中比常规数组更为适用。以下是一些使用环形数组的原因和优势
空间利用率高由于环形数组的元素在内存中是首尾相接的因此不需要为数组的头部和尾部留出额外的空间。这使得环形数组的空间利用率比常规数组更高。
高效的数据访问在环形数组中可以通过简单的模运算来确定一个元素在数组中的位置。这使得数据访问操作更加高效。
连续的数据结构环形数组保持了数据的连续性这有助于提高数据访问的局部性从而优化CPU缓存的性能。
避免数组越界问题由于环形数组的特性当索引超出数组的界限时会自动回到数组的开头或结尾避免了常规数组越界访问导致的错误。
循环队列和缓冲区实现环形数组可以方便地实现循环队列或缓冲区无需移动大量数据即可进行队首和队尾的添加与删除操作。
减少内存碎片由于环形数组的连续存储特性它可以更有效地利用内存空间减少内存碎片的产生。 易于实现动态扩展当需要增加更多元素时环形数组可以通过简单地扩展现有数组的大小来实现动态扩展而无需重新分配和复制原有数据。
c代码实现
#include stdio.h
#include stdlib.h
#include stdbool.h #define BUFFER_SIZE 5 // 定义环形缓冲区的大小 typedef struct { int buffer[BUFFER_SIZE]; // 缓冲区数组 int head; // 指向缓冲区中第一个元素的位置 int tail; // 指向缓冲区中下一个要写入元素的位置
} CircularBuffer; // 初始化环形缓冲区
void init_circular_buffer(CircularBuffer *cb) { cb-head 0; cb-tail 0; for (int i 0; i BUFFER_SIZE; i) { cb-buffer[i] 0; // 可以选择性地初始化缓冲区的内容 }
} // 检查环形缓冲区是否为空
bool is_circular_buffer_empty(CircularBuffer *cb) { return cb-head cb-tail cb-buffer[cb-head] 0; // 如果头和尾相等且头部元素为空则认为缓冲区为空
} // 检查环形缓冲区是否已满
bool is_circular_buffer_full(CircularBuffer *cb) { return (cb-tail 1) % BUFFER_SIZE cb-head; // 如果下一个要写入的位置是头部则认为缓冲区已满
} // 向环形缓冲区中插入一个元素
bool insert_into_circular_buffer(CircularBuffer *cb, int value) { if (is_circular_buffer_full(cb)) { return false; // 缓冲区已满无法插入新元素 } cb-buffer[cb-tail] value; // 在尾部插入新元素 cb-tail (cb-tail 1) % BUFFER_SIZE; // 更新尾部指针到下一个位置 return true; // 插入成功
} // 从环形缓冲区中移除一个元素并返回它
int remove_from_circular_buffer(CircularBuffer *cb) { if (is_circular_buffer_empty(cb)) { return -1; // 缓冲区为空无法移除元素返回错误代码或特殊值 } int value cb-buffer[cb-head]; // 获取头部元素的值 cb-buffer[cb-head] 0; // 可选将移除的元素置零根据具体需求决定是否需要这一步 cb-head (cb-head 1) % BUFFER_SIZE; // 更新头部指针到下一个位置 return value; // 返回被移除的元素值
} int main() { CircularBuffer cb; // 声明一个环形缓冲区变量 init_circular_buffer(cb); // 初始化环形缓冲区 // 向缓冲区中插入一些元素并检查其状态 for (int i 1; i 6; i) { // 尝试插入6个元素但缓冲区大小只有5所以会有一个插入失败 if (!insert_into_circular_buffer(cb, i)) { printf(Failed to insert element %d because the buffer is full.\n, i); } } // 从缓冲区中移除一些元素并打印它们的值 for (int i 0; i 6; i) { // 尝试移除6个元素但只插入了5个所以会有一个移除返回特殊值这里是-1 int value remove_from_circular_buffer(cb); if (value -1) { printf(Failed to remove element because the buffer is empty.\n); } else { printf(Removed element: %d\n, value); } } return 0;
}运行结果
