柔性数组和环形队列之间的故事
共 8972字,需浏览 18分钟
·
2021-05-20 20:53
之前的文章,讲解了柔性数组,有很多人留言,提到一些问题。刚好,之前发关于环形队列的文章有些问题,这次刚好拿出来一起说一下,并用柔性数组实现一个环形队列。
1、环形队列文章之前的代码有bug
/*插入数据*/
int ring_buff_insert(struct ring_buff * p_ring_buff,int data)
{
if(p_ring_buff == NULL)
{
printf("p null\n");
return (-1);
}
if(get_ring_buff_fullstate(p_ring_buff) == 1)
{
printf("buff is full\n");
return (-2);
}
//p_ring_buff->array[p_ring_buff->W%LEN] = data;
p_ring_buff->array[p_ring_buff->W&(LEN -1)] = data;
p_ring_buff->W ++;
//printf("inset:%d %d\n",data,p_ring_buff->W);
return (0);
}
这段代码
p_ring_buff->array[p_ring_buff->W&(LEN -1)] = data;
是有问题的,应该修改成
p_ring_buff->array[p_ring_buff->W%LEN] = data;
这里的想法是为了保证写的位置不会超过总长度,如果超过了总长度,就会从第一个位置重新开始写。
也欢迎大家对文章的内容提出质疑,如果正确还会有hb的哦,昨晚上的这个小帅哥就收到了我的专属hb。
在讨论中一起学习,会收获更多哦。
2、柔性数组关于arr[]和arr[0]补充内容
柔性数组的两种书写方式
struct starr{
int i;
int arr[0];
};
和
struct starr{
int i;
int arr[];
};
上面都是定义柔性数组的方式。需要注意两个问题
1、 结构体中必须存在至少一个除柔性数组以外的元素。
2、 柔性数组的必须在结构体的最后一个位置。
关于 arr[0]
和 arr[]
的写法问题,有如下英文解释
Flexible array members were officially standardized in C99,[4] however compilers accepted zero-sized array members with the same effect (e.g., GCC,[5] Microsoft Visual C[6]).
arr[]
的写法是C99标准引入的,叫做incomplete type,不完全类型,引入的原因是发现这样的写法非常实用。
arr[0]
是非标准扩展支持,也就是在C99出现之前的C89,就已经存在这种非标准扩展支持了,有些脑瓜子灵光的人,发现了这个机制,就用起来,然后C99才正式给他纳入正规军。
所以我们写成 arr[0]
也是没有问题的,编译器会自动解释为柔性数组。
在线编译网站
https://wandbox.org/
用两张图说明吧
如果写成这样呢?
我们现在接触到的编译器写成arr[]
肯定是没有问题的,但是那种特别特别古董的编译器,可能会提示出错。
但是写成 arr[0]肯定是没有问题的,
当然也是不标准的,不过虽然是不标准的,C语言至少是认识这个东西,不会编译出错的。
就酱紫~
3、柔性数组的地址和数组地址问题
我们知道,结构体在定义的时候就已经确定了地址位置,柔性数组实际上是不占用原结构体空间的,柔性数组的空间是使用malloc来申请的,既然是这样,他们的地址空间就不是在一个位置上的。柔性数组也就纯粹是挂羊头卖狗肉了。
测试地址空间
#include "stdio.h"
#include"malloc.h"
struct flex_array{
int i;
int arr[0];
};
int main()
{
int len = 10;
struct flex_array AAA;
struct flex_array * p_soft_arr = &AAA;
p_soft_arr = (struct flex_array *)malloc(sizeof(struct flex_array) + sizeof(int)*len);
printf("%p %p\n",&AAA,p_soft_arr);
printf("sizeof(struct flex_array)=%ld\n",sizeof(struct flex_array));
return 0;
}
代码输出
weiqifa@bsp-ubuntu1804:~/c$ gcc ringbuffer.c && ./a.out
0x7ffd52554514 0x55e3c0fa1260
sizeof(struct starr)=4
weiqifa@bsp-ubuntu1804:~/c$
结构体定义的地址和malloc出来的地址不是一个位置,至少他们不是连续的,而且使用malloc出来的内存后,使用完之后,需要使用free释放内存。
4、使用柔性数组实现环形队列
/* 实现的最简单的ringbuff 有更多提升空间,可以留言说明 */
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#define LEN 64
typedef int datatype;
/*环形队列结构体*/
typedef struct ring_buff{
int W;
int R;
int array[];
}*ring;
/*环形队列初始化*/
struct ring_buff * fifo_init(void)
{
struct ring_buff * p = NULL;
p = (struct ring_buff *)malloc(sizeof(struct ring_buff) + sizeof(datatype)*LEN);
if(p == NULL)
{
printf("fifo_init malloc error\n");
return NULL;
}
p->W = 0;
p->R = 0;
return p;
}
/*判断环形队列是否已经满了*/
int get_ring_buff_fullstate(struct ring_buff * p_ring_buff)
{
/*如果写位置减去读位置等于队列长度,就说明这个环形队列已经满*/
if((p_ring_buff->W - p_ring_buff->R) == LEN)
return (1);
else
return (0);
}
/*判断环形队列为空*/
int get_ring_buff_emptystate(struct ring_buff * p_ring_buff)
{
/*如果写位置和读的位置相等,就说明这个环形队列为空*/
if(p_ring_buff->W == p_ring_buff->R)
return (1);
else
return (0);
}
/*插入数据*/
int ring_buff_insert(struct ring_buff * p_ring_buff,int data)
{
if(p_ring_buff == NULL)
{
printf("p_ring_buff is null\n");
return (-1);
}
if(get_ring_buff_fullstate(p_ring_buff) == 1)
{
printf("buff is full\n");
return (-2);
}
p_ring_buff->array[p_ring_buff->W%LEN] = data;
p_ring_buff->W ++;
//printf("insert:%d %d\n",data,p_ring_buff->W);
return (0);
}
/*读取环形队列数据*/
int ring_buff_get(struct ring_buff * p_ring_buff)
{
int data = 0;
if(p_ring_buff == NULL)
{
printf("p null\n");
return (-1);
}
if(get_ring_buff_emptystate(p_ring_buff) == 1)
{
printf("buff is empty\n");
return (-2);
}
data = p_ring_buff->array[p_ring_buff->R%LEN];
p_ring_buff->R++;
return data;
}
/*销毁*/
int ring_buff_destory(struct ring_buff * p_ring_buff)
{
if(p_ring_buff == NULL)
{
printf("p null\n");
return (-1);
}
free(p_ring_buff);
return (0);
}
int main()
{
int i = 0;
int data;
/*设置种子*/
srand((int)time(0));
/*定义一个环形缓冲区*/
ring pt_ring_buff = fifo_init();
printf("write:\n");
/*向环形缓冲区中写入数据*/
for(i = 0;i<10;i++)
{
data = rand()%LEN;
ring_buff_insert(pt_ring_buff,data);
printf("%d ",data);
}
printf("\nread:\n");
printf("%d ",ring_buff_get(pt_ring_buff));
printf("\nread:\n");
/*从环形缓冲区中读出数据*/
for(i = 0;i<10;i++)
{
printf("%d ",ring_buff_get(pt_ring_buff));
}
printf("\n");
/*销毁一个环形缓冲区*/
ring_buff_destory(pt_ring_buff);
return (1);
}
输出结果
weiqifa@bsp-ubuntu1804:~/c$ gcc ringbuffer.c && ./a.out
write:
47 39 31 16 55 25 22 38 41 62
read:
47
read:
39 31 16 55 25 22 38 41 62 buff is empty
-2
weiqifa@bsp-ubuntu1804:~/c$
关于环形队列是否为空的判断,大家可以思考下,还有没有更好的判断方式,欢迎踊跃留言。