本帖最后由 xiaojie0513 于 2018-6-4 09:55 编辑 : ]8 a# _/ U# m8 a, Q * e3 M* t: e: r0 @- }, a4 c b 队列的概念7 b7 i* [! H; p) @; S 在此之前,我们来回顾一下队列的基本概念: 队列 (Queue):是一种先进先出(First In First Out ,简称 FIFO)的线性表,只允许在一端插入(入队),在另一端进行删除(出队)。8 ?0 k; z: o) ]( b 2 M) c/ o3 r# g$ d: E( f; w3 L 队列的特点 类似售票排队窗口,先到的人看到能先买到票,然后先走,后来的人只能后买到票 & s& d+ V! t! a4 \' O0 ^4 \- @* [队列的常见两种形式 & ?+ U& h) u8 r; b; R 普通队列1 Z1 D/ x2 x3 i( t9 ` 在计算机中,每个信息都是存储在存储单元中的,比喻一下吧,上图的一些小正方形格子就是一个个存储单元,你可以理解为常见的数组,存放我们一个个的信息。0 [% C3 j, S( X |7 G 当有大量数据的时候,我们不能存储所有的数据,那么计算机处理数据的时候,只能先处理先来的,那么处理完后呢,就会把数据释放掉,再处理下一个。那么,已经处理的数据的内存就会被浪费掉。因为后来的数据只能往后排队,如过要将剩余的数据都往前移动一次,那么效率就会低下了,肯定不现实,所以,环形队列就出现了。" C. d: [2 O# {3 m1 c" T# U! D 环形队列6 n% R3 p' O% @% v( O& x 它的队列就是一个环,它避免了普通队列的缺点,就是有点难理解而已,其实它就是一个队列,一样有队列头,队列尾,一样是先进先出(FIFO)。我们采用顺时针的方式来对队列进行排序。8 ?( z7 y, N0 e0 w! O' {) u8 B S; F! O0 `7 l0 U& | 队列头 (Head) :允许进行删除的一端称为队首。9 b) l4 q% ?- t$ r 队列尾 (Tail) :允许进行插入的一端称为队尾。! G Y. u/ E# F# I7 F( B 4 P! b. Y! O2 d9 N5 Y% w 环形队列的实现:在计算机中,也是没有环形的内存的,只不过是我们将顺序的内存处理过,让某一段内存形成环形,使他们首尾相连,简单来说,这其实就是一个数组,只不过有两个指针,一个指向列队头,一个指向列队尾。指向列队头的指针(Head)是缓冲区可读的数据,指向列队尾的指针(Tail)是缓冲区可写的数据,通过移动这两个指针(Head) &(Tail)即可对缓冲区的数据进行读写操作了,直到缓冲区已满(头尾相接),将数据处理完,可以释放掉数据,又可以进行存储新的数据了。 实现的原理:初始化的时候,列队头与列队尾都指向0,当有数据存储的时候,数据存储在‘0’的地址空间,列队尾指向下一个可以存储数据的地方‘1’,再有数据来的时候,存储数据到地址‘1’,然后队列尾指向下一个地址‘2’。当数据要进行处理的时候,肯定是先处理‘0’空间的数据,也就是列队头的数据,处理完了数据,‘0’地址空间的数据进行释放掉,列队头指向下一个可以处理数据的地址‘1’。从而实现整个环形缓冲区的数据读写。0 Z1 b/ V4 q( a 看图,队列头就是指向已经存储的数据,并且这个数据是待处理的。下一个CPU处理的数据就是1;而队列尾则指向可以进行写数据的地址。当1处理了,就会把1释放掉。并且把队列头指向2。当写入了一个数据6,那么队列尾的指针就会指向下一个可以写的地址。 如果你懂了环形队列,那就跟着歌曲来一步步用代码实现吧: 从队列到串口缓冲区的实现2 _ g# J9 x0 B8 `6 n3 @' e& s( S* q- g串口环形缓冲区收发:在很多入门级教程中,我们知道的串口收发都是:接收一个数据,触发中断,然后把数据发回来。这种处理方式是没有缓冲的,当数量太大的时候,亦或者当数据接收太快的时候,我们来不及处理已经收到的数据,那么,当再次收到数据的时候,就会将之前还未处理的数据覆盖掉。那么就会出现丢包的现象了,对我们的程序是一个致命的创伤。( `1 \+ S6 ~& C4 ? 2 i5 c7 u- N& H1 o4 _ 那么如何避免这种情况的发生呢,很显然,上面说的一些队列的特性很容易帮我们实现我们需要的情况。将接受的数据缓存一下,让处理的速度有些许缓冲,使得处理的速度赶得上接收的速度,上面又已经分析了普通队列与环形队列的优劣了,那么我们肯定是用环形队列来进行实现了。下面就是代码的实现:# g! w7 O" I- k9 K ①定义一个结构体: 1typedef struct1 U: }* F3 L0 [ 2{3 x% H7 T: |% V f 3 u16 Head; 4 u16 Tail;4 P T, j% n! F. q 5 u16 Lenght;' t& {5 l0 l0 A2 Z8 ` 6 u8 Ring_Buff[RINGBUFF_LEN];( h) |/ ^$ z0 y5 g 7}RingBuff_t;5 Q& d# Q" _' ?( \' n1 k2 B9 G 8RingBuff_t ringBuff;//创建一个ringBuff的缓冲区 ; r# X, v+ e' J ②初始化结构体相关信息:使得我们的环形缓冲区是头尾相连的,并且里面没有数据,也就是空的队列。 1/**% E8 G+ l9 r, t* p 2* @brief RingBuff_Init 3* @param void 4* @return void3 m& T7 M4 v" c1 T 5* @author 杰杰 6* @date 2018' @3 ?2 U! Q. b' S1 T 7* @version v1.0 8* @note 初始化环形缓冲区6 y' U5 h! `4 z" J! ] 9*/ 10void RingBuff_Init(void) 11{& h5 ~+ R m+ y1 y 12 //初始化相关信息5 V" E+ I' D( K$ _) k1 N/ g 13 ringBuff.Head = 0;2 ^# ^5 u q. p$ u: N3 a6 ~ 14 ringBuff.Tail = 0;5 b! E! w+ V; Q5 | 15 ringBuff.Lenght = 0; 16} 初始化效果如下: 写入环形缓冲区的代码实现: 1/**' X" b$ H: K, e$ k 2* @brief Write_RingBuff! T0 T6 M( u, G ?: ? 3* @param u8 data( I5 B- T7 P0 `, _ 4* @return FLASE:环形缓冲区已满,写入失败;TRUE:写入成功 5* @author 杰杰+ V2 L" h/ |& ] 6* @date 2018 7* @version v1.0 8* @note 往环形缓冲区写入u8类型的数据9 e' M6 F' u, C+ o: k1 k 9*/ 10u8 Write_RingBuff(u8 data) 11{8 C1 C4 [$ U; u6 E, L1 y! c. m 12 if(ringBuff.Lenght >= RINGBUFF_LEN) //判断缓冲区是否已满. T8 Z. L9 n0 i: B' F2 R 13 {) K, t& K# _! \. l6 y) w 14 return FLASE;% P' k& b9 T2 f6 L" O% @8 t0 E; w 15 }! B. H- H& d5 v1 Q& B4 j/ |5 Y% R 16 ringBuff.Ring_Buff[ringBuff.Tail]=data; 17// ringBuff.Tail++;3 Y" f$ T8 x' x% Z; w 18 ringBuff.Tail = (ringBuff.Tail+1)%RINGBUFF_LEN;//防止越界非法访问 19 ringBuff.Lenght++; 20 return TRUE; 21} 读取缓冲区的数据的代码实现: 1/**9 b# f' h4 ^/ m 2* @brief Read_RingBuff 3* @param u8 *rData,用于保存读取的数据; T* U$ k g% z 4* @return FLASE:环形缓冲区没有数据,读取失败;TRUE:读取成功 5* @author 杰杰 6* @date 2018 7* @version v1.0+ h0 v4 a! Y/ v4 g" B 8* @note 从环形缓冲区读取一个u8类型的数据; w: ], T3 x; g; r- K 9*/ 10u8 Read_RingBuff(u8 *rData)% @* m. q* x& q* ]& G5 k 11{ 12 if(ringBuff.Lenght == 0)//判断非空( W. ~( _/ l5 x6 L 13 { 14 return FLASE; 15 } 16 *rData = ringBuff.Ring_Buff[ringBuff.Head];//先进先出FIFO,从缓冲区头出 17// ringBuff.Head++;0 m2 I0 W7 ~5 r 18 ringBuff.Head = (ringBuff.Head+1)%RINGBUFF_LEN;//防止越界非法访问4 U6 q: c9 W7 i% T( L 19 ringBuff.Lenght--; 20 return TRUE;0 F1 {" w% ^% ~, L6 ^ 21}对于读写操作需要注意的地方有两个: 1:判断队列是否为空或者满,如果空的话,是不允许读取数据的,返回FLASE。如果是满的话,也是不允许写入数据的,避免将已有数据覆盖掉。那么如果处理的速度赶不上接收的速度,可以适当增大缓冲区的大小,用空间换取时间。 2:防止指针越界非法访问,程序有说明,需要使用者对整个缓冲区的大小进行把握。9 |. U& W Q. E! }9 z9 h 那么在串口接收函数中: 1void USART1_IRQHandler(void) . l6 ]0 p" a3 u: B, v. g5 I6 u 2{) B# s0 u$ ^" S# e0 I% l 3 if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET) //接收中断1 @! S c, X& A( F0 a$ q: L) D 4 { 5 USART_ClearITPendingBit(USART1,USART_IT_RXNE); //清楚标志位 6 Write_RingBuff(USART_ReceiveData(USART1)); //读取接收到的数据0 N E+ A4 h8 c( O& S F6 F9 C 7 } 8} 测试效果 w! i9 v6 Y% M5 P 测试数据没有发生丢包现象 补充 对于现在的阶段,杰杰我本人写代码也慢慢学会规范了。所有的代码片段均使用了可读性很强的,还有可移植性也很强的。我使用了宏定义来决定是否开启环形缓冲区的方式来收发数据,移植到大家的代码并不会有其他副作用,只需要开启宏定义即可使用了。# @& f- ~7 q+ S3 M# K/ R 1#define USER_RINGBUFF 1 //使用环形缓冲区形式接收数据 2#if USER_RINGBUFF: p/ Z0 e7 ?- ~: m9 L0 i 3/**如果使用环形缓冲形式接收串口数据***/' V# [0 k6 {8 y% y 4#define RINGBUFF_LEN 200 //定义最大接收字节数 200. t' @: a; w: g) \ 5#define FLASE 1 , G; c1 ~5 c( g 6#define TRUE 0 7void RingBuff_Init(void); 8u8 Write_RingBuff(u8 data); 9u8 Read_RingBuff(u8 *rData); 10#endif 当然,我们完全可以用空闲中断与DMA传输,效率更高,但是某些单片机没有空闲中断与DMA,那么这种环形缓冲区的作用就很大了,并且移植简便。' h# J K7 N3 o 说明:文章部分截图来源慕课网james_yuan老师的课程 小编:CK 往期精彩回顾【连载】从单片机到操作系统③——走进FreeRTOS, M) }2 v4 V& Q 创客: 创客飞梦空间是开源公众号7 V+ X+ z$ @( n) n( l; Z$ Q欢迎大家分享出去/ Q/ B' t6 Z O. w 也欢迎大家投稿 ' M7 y. [1 N* g# H . i5 ?$ f2 l* X' { " d+ g; D5 `# B4 B% Q, P& M( l |
å®éª4 串å£å®éª.zip
下载2.62 MB, 下载次数: 934
#include <kfifo.h>- f1 `. n1 P" j) j* i2 h
4 N7 B- _: K% Q
6 g% x& ^" u. c6 B( [: P9 a
int __kfifo_init(struct __kfifo *fifo, void *buffer, unsigned int size)) }0 j1 n6 W( X( t+ L7 w
{
fifo->in = 0;+ Z( B5 a/ c3 w6 Y9 ?
fifo->out = 0;7 s3 R5 d* Q u" b { m3 d
fifo->mask = 0;# g" G" e/ J% a# L3 c/ S5 K
fifo->data = buffer;
# T( S/ v) k5 n0 z
if (size < 2) {/ S y0 M" U$ u( |
return -1;, |1 }5 x: J( ?- [' @
}
if ((size & (size-1)) != 0)
{
return -2; /*** Must be a power of 2 (2,4,8,16,32,64,128,256,512,...) ***/) _& {7 x' `/ O" n; \5 y
}
fifo->mask = size - 1;4 F. c3 _+ j/ Z, g3 S% u6 t
return 0;9 i' Y% H; x' G7 ^( C1 M" u
}( q u- G4 Y0 [1 }
: i) k6 d2 T. m& X
* Q* m/ @1 b' X: a* Z
unsigned int __kfifo_push_char(struct __kfifo *fifo, const char *p)
{6 c' }% E9 _( j: `8 g, v
if(( ( fifo->in - fifo->out ) & ( ~fifo->mask ) ) == 0 )$ C5 ]5 @1 z9 G6 }$ X) k
{' y) F. A' V" H) J+ U: F) W# D
*( (char*)fifo->data + (fifo->in++ & fifo->mask) ) = *p;8 j( g+ @9 x/ S! `9 F. u. S5 N5 O- g& A
return 1;
}
3 Z+ Y1 q1 U+ X% x( [4 w: `- c
return 0; o, k) R, D. R" B3 M3 }
}! ~& G6 D2 r/ g' p4 \. Z
, @$ Z+ G+ w0 |0 ]% ~1 {5 }6 R7 ]
. A0 h' u# K: K
unsigned int __kfifo_pop_char(struct __kfifo *fifo, char* p )5 {% D% x; V; r* n, V
{
if( fifo->in != fifo->out )
{0 Q! h" } z4 ^9 c# Z
*p = *( (char*)fifo->data + (fifo->out++ & fifo->mask) ) ;
return 1;' V; H6 p& Z2 A) x
}$ B/ F' Q2 W: G2 @0 k8 e
return 0;
}* G; s/ I6 f& B0 h5 v2 D
( M* c$ G \" A3 w9 v# N
+ @; y; J$ c/ U/ G4 K1 c$ V
ok, 了解了解
=========================================: _% ]' P3 V t+ w! q- U
看了源代码, ! @7 L9 }; b F- N) w
3 }& h! B! x" S0 v% }) }0 w- C# [
串口接收与发送缓冲区FIFO 的实现 , 在 keil 51 里面 有一个简单例子, 非常好. 适用于单一资源提供者与资源消费者, 简单的代码里面就解决了资源提供者与消费者之间协调的问题. 可以去看看.
: A; J& D* s7 k! w
我也没正规学过数据结构,是考3级数据库时,数据结构是必须的。
一个暑假自学完一本数据结构课本,做完一本题库。) ~7 x0 x% _4 b* n% z+ l; F
8 L' G' ?3 T5 o7 c7 O* F
最近让破总给我买了几本书,C++课本、习题、C++数据结构。
嘻嘻嘻我瞎搞的
新上任的版主们最近都很活跃
是吗是吗
自从考完试再没摸过,就记得个“二叉树”名字了
数据结构是个好东西,我还得去学
数据结构还是用处很大的!!!