本帖最后由 xiaojie0513 于 2018-6-4 09:55 编辑 , g: I. Y `3 j2 b 4 r, Y- t: t" p2 e# C( m# m 队列的概念7 M4 X- E! ]2 W" G- b ]* I 在此之前,我们来回顾一下队列的基本概念:3 ]0 V. V6 C7 {) n }& s2 j& s 队列 (Queue):是一种先进先出(First In First Out ,简称 FIFO)的线性表,只允许在一端插入(入队),在另一端进行删除(出队)。 . O' P* F! X5 K# Q 队列的特点 类似售票排队窗口,先到的人看到能先买到票,然后先走,后来的人只能后买到票 # H: U# K; B) v7 K6 N/ p队列的常见两种形式& \' p6 N+ `* }3 f) j: k: V 普通队列 j" e" v. x6 o4 o B+ ~ : L: n& F! ? ~/ M- r1 r 在计算机中,每个信息都是存储在存储单元中的,比喻一下吧,上图的一些小正方形格子就是一个个存储单元,你可以理解为常见的数组,存放我们一个个的信息。8 e k% V& g6 \6 l 当有大量数据的时候,我们不能存储所有的数据,那么计算机处理数据的时候,只能先处理先来的,那么处理完后呢,就会把数据释放掉,再处理下一个。那么,已经处理的数据的内存就会被浪费掉。因为后来的数据只能往后排队,如过要将剩余的数据都往前移动一次,那么效率就会低下了,肯定不现实,所以,环形队列就出现了。$ E% I B( g: n: P* J) l3 R 环形队列 它的队列就是一个环,它避免了普通队列的缺点,就是有点难理解而已,其实它就是一个队列,一样有队列头,队列尾,一样是先进先出(FIFO)。我们采用顺时针的方式来对队列进行排序。8 o/ u0 U* f7 m5 `& | T( @ 队列头 (Head) :允许进行删除的一端称为队首。& B8 w6 ?! D. P4 L- L3 W$ r5 N4 I 队列尾 (Tail) :允许进行插入的一端称为队尾。- ?2 g E, F$ T9 Y1 R3 i 2 x! v) {$ V: b$ f$ y$ L, G 环形队列的实现:在计算机中,也是没有环形的内存的,只不过是我们将顺序的内存处理过,让某一段内存形成环形,使他们首尾相连,简单来说,这其实就是一个数组,只不过有两个指针,一个指向列队头,一个指向列队尾。指向列队头的指针(Head)是缓冲区可读的数据,指向列队尾的指针(Tail)是缓冲区可写的数据,通过移动这两个指针(Head) &(Tail)即可对缓冲区的数据进行读写操作了,直到缓冲区已满(头尾相接),将数据处理完,可以释放掉数据,又可以进行存储新的数据了。 实现的原理:初始化的时候,列队头与列队尾都指向0,当有数据存储的时候,数据存储在‘0’的地址空间,列队尾指向下一个可以存储数据的地方‘1’,再有数据来的时候,存储数据到地址‘1’,然后队列尾指向下一个地址‘2’。当数据要进行处理的时候,肯定是先处理‘0’空间的数据,也就是列队头的数据,处理完了数据,‘0’地址空间的数据进行释放掉,列队头指向下一个可以处理数据的地址‘1’。从而实现整个环形缓冲区的数据读写。 ' m" v& O6 } U; Q- {% S+ E 看图,队列头就是指向已经存储的数据,并且这个数据是待处理的。下一个CPU处理的数据就是1;而队列尾则指向可以进行写数据的地址。当1处理了,就会把1释放掉。并且把队列头指向2。当写入了一个数据6,那么队列尾的指针就会指向下一个可以写的地址。( w4 d+ V: {) _4 N% O 如果你懂了环形队列,那就跟着歌曲来一步步用代码实现吧: 从队列到串口缓冲区的实现串口环形缓冲区收发:在很多入门级教程中,我们知道的串口收发都是:接收一个数据,触发中断,然后把数据发回来。这种处理方式是没有缓冲的,当数量太大的时候,亦或者当数据接收太快的时候,我们来不及处理已经收到的数据,那么,当再次收到数据的时候,就会将之前还未处理的数据覆盖掉。那么就会出现丢包的现象了,对我们的程序是一个致命的创伤。4 d- k+ J. T; h4 b . y9 k X; l0 \' e2 B 4 F; R; d) ~# L. l5 G 那么如何避免这种情况的发生呢,很显然,上面说的一些队列的特性很容易帮我们实现我们需要的情况。将接受的数据缓存一下,让处理的速度有些许缓冲,使得处理的速度赶得上接收的速度,上面又已经分析了普通队列与环形队列的优劣了,那么我们肯定是用环形队列来进行实现了。下面就是代码的实现: 1 m& }! t% O, E2 h6 D ①定义一个结构体: 1typedef struct 2{7 h/ A, q! Q: H7 ]! ^7 Z 3 u16 Head; 4 u16 Tail; 5 u16 Lenght;% U7 F4 Y; h8 O: I7 U) N2 }6 E/ \ 6 u8 Ring_Buff[RINGBUFF_LEN];. I. U$ U. K5 L) R- V& R; m( a/ p4 R 7}RingBuff_t; 8RingBuff_t ringBuff;//创建一个ringBuff的缓冲区 / F2 o8 F& e9 A3 o' Z ②初始化结构体相关信息:使得我们的环形缓冲区是头尾相连的,并且里面没有数据,也就是空的队列。) q# b' _1 F9 L9 M1 h1 i 1/**/ k. W: U+ w. E4 X+ ~" O 2* @brief RingBuff_Init 3* @param void 4* @return void 5* @author 杰杰 6* @date 20183 o* J3 o9 B$ Q; M# B( ] 7* @version v1.05 u+ u# M. J! x% I5 n( I 8* @note 初始化环形缓冲区) v0 d3 _, Z! D/ P a0 |; P3 o 9*/, ^: q" m+ Y2 U- _8 ^ 10void RingBuff_Init(void) 11{ 12 //初始化相关信息 n2 {! {; n7 V- k 13 ringBuff.Head = 0; 14 ringBuff.Tail = 0; 15 ringBuff.Lenght = 0; 16} 初始化效果如下:* P4 m# B+ W; V, E9 I! T+ Q* U" P 5 g9 k7 b6 B; ?9 d! V 写入环形缓冲区的代码实现: 1/**. X+ j) U+ j( w, G! L 2* @brief Write_RingBuff 3* @param u8 data! I+ ^5 D Z- G# a% q- s# @! w9 b 4* @return FLASE:环形缓冲区已满,写入失败;TRUE:写入成功 5* @author 杰杰 6* @date 2018 7* @version v1.0 8* @note 往环形缓冲区写入u8类型的数据 9*/ 10u8 Write_RingBuff(u8 data) 11{8 I3 }9 U) H; u, d 12 if(ringBuff.Lenght >= RINGBUFF_LEN) //判断缓冲区是否已满6 G# m. D5 b Y" Z ]$ X 13 { 14 return FLASE;0 o* R, O3 ^5 S0 z- i2 K% D1 I8 Q 15 }" Z. _/ Z1 D' s4 Q( p/ n 16 ringBuff.Ring_Buff[ringBuff.Tail]=data; 17// ringBuff.Tail++; 18 ringBuff.Tail = (ringBuff.Tail+1)%RINGBUFF_LEN;//防止越界非法访问 19 ringBuff.Lenght++;% v3 ~. z, H) I; ? 20 return TRUE;1 N" m) d4 j1 u1 E/ [: A5 h. ~ 21} 读取缓冲区的数据的代码实现: 1/**: I0 v9 f" l1 G$ B" b( |- R 2* @brief Read_RingBuff 3* @param u8 *rData,用于保存读取的数据- }. V/ R5 f3 O( B/ G; J 4* @return FLASE:环形缓冲区没有数据,读取失败;TRUE:读取成功+ o) w q, z k% D) U. V4 G 5* @author 杰杰 6* @date 2018! x0 [1 w O5 i6 g2 G, _) d6 V0 d' c 7* @version v1.0 8* @note 从环形缓冲区读取一个u8类型的数据 9*/ 10u8 Read_RingBuff(u8 *rData) 11{! P2 ^$ t( J) B% ]& T0 w 12 if(ringBuff.Lenght == 0)//判断非空 13 { 14 return FLASE; 15 }$ S( g' J7 q$ r: N1 m 16 *rData = ringBuff.Ring_Buff[ringBuff.Head];//先进先出FIFO,从缓冲区头出5 c9 e- q- q2 h' f 17// ringBuff.Head++;/ h' @! b R7 Z! Y" x* i 18 ringBuff.Head = (ringBuff.Head+1)%RINGBUFF_LEN;//防止越界非法访问2 Q1 l3 E" z. a4 C( {$ l7 l, w 19 ringBuff.Lenght--; 20 return TRUE;$ b/ y. l5 ?+ E2 T+ n) c 21}对于读写操作需要注意的地方有两个:$ s: }+ a! j! ?0 z6 l! r: { 1:判断队列是否为空或者满,如果空的话,是不允许读取数据的,返回FLASE。如果是满的话,也是不允许写入数据的,避免将已有数据覆盖掉。那么如果处理的速度赶不上接收的速度,可以适当增大缓冲区的大小,用空间换取时间。2 Z) u8 G% m" {1 O! Z/ k7 A6 i9 h0 R 2:防止指针越界非法访问,程序有说明,需要使用者对整个缓冲区的大小进行把握。 那么在串口接收函数中: 1void USART1_IRQHandler(void) 2{% I; z! V4 R' b9 {# C5 U$ c 3 if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET) //接收中断 4 {' y9 b) k+ o- S( g3 u 5 USART_ClearITPendingBit(USART1,USART_IT_RXNE); //清楚标志位 6 Write_RingBuff(USART_ReceiveData(USART1)); //读取接收到的数据 7 } 8} 测试效果 测试数据没有发生丢包现象 补充 对于现在的阶段,杰杰我本人写代码也慢慢学会规范了。所有的代码片段均使用了可读性很强的,还有可移植性也很强的。我使用了宏定义来决定是否开启环形缓冲区的方式来收发数据,移植到大家的代码并不会有其他副作用,只需要开启宏定义即可使用了。4 s! p+ r$ N8 F+ t1 Z- h 1#define USER_RINGBUFF 1 //使用环形缓冲区形式接收数据 2#if USER_RINGBUFF 3/**如果使用环形缓冲形式接收串口数据***/ 4#define RINGBUFF_LEN 200 //定义最大接收字节数 200 5#define FLASE 1 4 X w, t3 k( L 6#define TRUE 0 $ w- K; U2 v6 z 7void RingBuff_Init(void); 8u8 Write_RingBuff(u8 data); 9u8 Read_RingBuff(u8 *rData); 10#endif3 A9 x: B9 n/ R! f( }$ N/ Y 5 {5 X3 `; Q; N( y1 o 当然,我们完全可以用空闲中断与DMA传输,效率更高,但是某些单片机没有空闲中断与DMA,那么这种环形缓冲区的作用就很大了,并且移植简便。+ z' }8 o5 ~: X' Z 说明:文章部分截图来源慕课网james_yuan老师的课程 小编:CK 往期精彩回顾【连载】从单片机到操作系统③——走进FreeRTOS& C: e3 O2 _4 s0 ?) |" m 创客: 创客飞梦空间是开源公众号( ]2 |7 S0 i+ N. Z. |欢迎大家分享出去1 `1 {6 F3 K9 o6 X2 a4 y 也欢迎大家投稿- r4 A, P$ P% H( m- {; U4 u + a7 A1 r. \9 i7 {/ m . z! Q' q& I! V* I |
å®éª4 串å£å®éª.zip
下载2.62 MB, 下载次数: 934
#include <kfifo.h>
8 X& W! y) p$ V P }" N
3 u1 P& N$ m- g c1 |6 ^9 v
1 R; w. L5 s% B: r, r
1 k) I, Y) x. _% |: V8 s
int __kfifo_init(struct __kfifo *fifo, void *buffer, unsigned int size)9 j. R* C1 M& B* c- r1 x
{
fifo->in = 0;
fifo->out = 0;
fifo->mask = 0;
fifo->data = buffer;
if (size < 2) {$ P* T1 U1 L5 }$ B
return -1;
}/ b5 f: | U6 L" L5 N9 H2 {
if ((size & (size-1)) != 0)) R8 V3 F& O: W2 a9 `( f& F, l3 H3 C
{( T/ H4 Q2 w, P5 x% R+ \) o, u- ?' e
return -2; /*** Must be a power of 2 (2,4,8,16,32,64,128,256,512,...) ***/9 s" ^ y7 N2 x9 ^" m- ]& }* e) P
}
fifo->mask = size - 1;
return 0;
}
, z0 g7 \0 j# {7 y" N" T
# M9 V2 `1 B# ?/ [
1 w: x/ A. ?# U
unsigned int __kfifo_push_char(struct __kfifo *fifo, const char *p)7 C2 u- X7 J/ f
{
if(( ( fifo->in - fifo->out ) & ( ~fifo->mask ) ) == 0 )5 }% K: Y% X4 m4 i* G! `2 ^2 k
{3 Z. u. ]; E! I) n
*( (char*)fifo->data + (fifo->in++ & fifo->mask) ) = *p;# m2 a' D2 M2 M3 ~' f% b, Z
return 1;
}
return 0;
}5 k1 A( J3 E) |% _
3 X/ W- d2 l$ h
2 l# v; i y* V8 j4 g' \
unsigned int __kfifo_pop_char(struct __kfifo *fifo, char* p )! k: i; g$ A) z4 d/ p
{5 |0 Y' R" h' y M6 H- k* p
if( fifo->in != fifo->out )
{) |4 ], e1 {3 @) U6 T; Z
*p = *( (char*)fifo->data + (fifo->out++ & fifo->mask) ) ;- [1 w, E( @2 H2 D
$ I- D6 p/ s4 z
return 1;
}
return 0;6 e: C* [) ]7 i& v- e
}
ok, 了解了解
=========================================0 e6 D, ?/ o: n+ x4 I
看了源代码,
/ _' f3 w- Z* w/ j
串口接收与发送缓冲区FIFO 的实现 , 在 keil 51 里面 有一个简单例子, 非常好. 适用于单一资源提供者与资源消费者, 简单的代码里面就解决了资源提供者与消费者之间协调的问题. 可以去看看.% z- o! a" H# _) s
V: P) d: T% t; X
我也没正规学过数据结构,是考3级数据库时,数据结构是必须的。: h: J4 b3 Z3 D, D$ N
一个暑假自学完一本数据结构课本,做完一本题库。+ C- d1 U' Y9 e# j3 o* h
最近让破总给我买了几本书,C++课本、习题、C++数据结构。
嘻嘻嘻我瞎搞的
: }/ G# o2 S6 z6 h$ K1 h% n, O# m
新上任的版主们最近都很活跃
是吗是吗
自从考完试再没摸过,就记得个“二叉树”名字了
数据结构是个好东西,我还得去学
数据结构还是用处很大的!!!