本帖最后由 xiaojie0513 于 2018-6-4 09:55 编辑 队列的概念 在此之前,我们来回顾一下队列的基本概念:- W+ M7 r0 _( O, s* R6 C) H. _ 队列 (Queue):是一种先进先出(First In First Out ,简称 FIFO)的线性表,只允许在一端插入(入队),在另一端进行删除(出队)。 9 s! ^3 n6 s( i$ K 队列的特点 类似售票排队窗口,先到的人看到能先买到票,然后先走,后来的人只能后买到票 8 b; z( y8 Q1 {! F) m& } m, n( R队列的常见两种形式 7 R. j( o0 {* \ T8 F% Q 普通队列 3 b5 L# P; a7 I1 m4 N) m& u+ k ] 在计算机中,每个信息都是存储在存储单元中的,比喻一下吧,上图的一些小正方形格子就是一个个存储单元,你可以理解为常见的数组,存放我们一个个的信息。 * T0 J* ]9 n1 m$ v 当有大量数据的时候,我们不能存储所有的数据,那么计算机处理数据的时候,只能先处理先来的,那么处理完后呢,就会把数据释放掉,再处理下一个。那么,已经处理的数据的内存就会被浪费掉。因为后来的数据只能往后排队,如过要将剩余的数据都往前移动一次,那么效率就会低下了,肯定不现实,所以,环形队列就出现了。 环形队列- E: a+ j- a/ F# s' y( b( B# | 它的队列就是一个环,它避免了普通队列的缺点,就是有点难理解而已,其实它就是一个队列,一样有队列头,队列尾,一样是先进先出(FIFO)。我们采用顺时针的方式来对队列进行排序。 队列头 (Head) :允许进行删除的一端称为队首。# v: x4 h! [3 h$ S, ]% {2 u( O. x 队列尾 (Tail) :允许进行插入的一端称为队尾。0 H7 A& B9 O2 O9 L8 R# L/ [ 5 j8 z; h9 V$ s8 A1 Z 环形队列的实现:在计算机中,也是没有环形的内存的,只不过是我们将顺序的内存处理过,让某一段内存形成环形,使他们首尾相连,简单来说,这其实就是一个数组,只不过有两个指针,一个指向列队头,一个指向列队尾。指向列队头的指针(Head)是缓冲区可读的数据,指向列队尾的指针(Tail)是缓冲区可写的数据,通过移动这两个指针(Head) &(Tail)即可对缓冲区的数据进行读写操作了,直到缓冲区已满(头尾相接),将数据处理完,可以释放掉数据,又可以进行存储新的数据了。- ]* t$ O' O' G0 m# } / G# \# w# v& m+ U6 }9 j 实现的原理:初始化的时候,列队头与列队尾都指向0,当有数据存储的时候,数据存储在‘0’的地址空间,列队尾指向下一个可以存储数据的地方‘1’,再有数据来的时候,存储数据到地址‘1’,然后队列尾指向下一个地址‘2’。当数据要进行处理的时候,肯定是先处理‘0’空间的数据,也就是列队头的数据,处理完了数据,‘0’地址空间的数据进行释放掉,列队头指向下一个可以处理数据的地址‘1’。从而实现整个环形缓冲区的数据读写。" g' f, S) e( _, \8 w 5 a$ P7 e3 c; ~1 b" o/ f( J/ c 看图,队列头就是指向已经存储的数据,并且这个数据是待处理的。下一个CPU处理的数据就是1;而队列尾则指向可以进行写数据的地址。当1处理了,就会把1释放掉。并且把队列头指向2。当写入了一个数据6,那么队列尾的指针就会指向下一个可以写的地址。3 P4 E: l" g# k, c' w" h 如果你懂了环形队列,那就跟着歌曲来一步步用代码实现吧: 从队列到串口缓冲区的实现串口环形缓冲区收发:在很多入门级教程中,我们知道的串口收发都是:接收一个数据,触发中断,然后把数据发回来。这种处理方式是没有缓冲的,当数量太大的时候,亦或者当数据接收太快的时候,我们来不及处理已经收到的数据,那么,当再次收到数据的时候,就会将之前还未处理的数据覆盖掉。那么就会出现丢包的现象了,对我们的程序是一个致命的创伤。/ c, }9 L1 V! Q ' [" x7 ]" L# I2 ?: F% N) Y 那么如何避免这种情况的发生呢,很显然,上面说的一些队列的特性很容易帮我们实现我们需要的情况。将接受的数据缓存一下,让处理的速度有些许缓冲,使得处理的速度赶得上接收的速度,上面又已经分析了普通队列与环形队列的优劣了,那么我们肯定是用环形队列来进行实现了。下面就是代码的实现:% |* j/ v2 q0 s! Z7 p# w! z ( g0 N; C: l' Q2 j; u K ①定义一个结构体: 1typedef struct, O# R. j1 {9 m6 m7 p, N8 r( a 2{: }3 k4 p/ o6 p) ?- m5 D 3 u16 Head; + [% {* k/ R7 T4 [' F 4 u16 Tail; 5 u16 Lenght; 6 u8 Ring_Buff[RINGBUFF_LEN];# a. m8 g* r1 f& y6 M" C) ? 7}RingBuff_t;1 ]0 x4 k5 W I2 L* e7 W 8RingBuff_t ringBuff;//创建一个ringBuff的缓冲区& C3 }* X1 m+ L- O- R$ e , B3 X6 E5 H/ j) A7 n9 d p ②初始化结构体相关信息:使得我们的环形缓冲区是头尾相连的,并且里面没有数据,也就是空的队列。 1/** ?& B# i5 R1 H 2* @brief RingBuff_Init) O: R* ~: g) ]0 H. ^% J5 X 3* @param void$ P; {& e& k' Q Y8 w% | 4* @return void 5* @author 杰杰# b9 t' [+ z. J7 v2 H4 G' z 6* @date 2018 7* @version v1.0- t, V! e: {4 x. s7 B, {! b 8* @note 初始化环形缓冲区 9*/ 10void RingBuff_Init(void) 11{ 12 //初始化相关信息 13 ringBuff.Head = 0; 14 ringBuff.Tail = 0;, w2 E! D1 P) l) O8 q 15 ringBuff.Lenght = 0; 16} 初始化效果如下:8 B+ ^. \3 f4 | 2 ^' Z; _. |) c3 f8 y , O/ e( D" p$ P) K( f 写入环形缓冲区的代码实现: 1/** 2* @brief Write_RingBuff( g: m2 J4 m$ m% a J6 T) M 3* @param u8 data 4* @return FLASE:环形缓冲区已满,写入失败;TRUE:写入成功4 M% g9 O* X* _9 P 5* @author 杰杰 6* @date 2018& m7 @7 i; f1 u0 u/ j2 K 7* @version v1.0 8* @note 往环形缓冲区写入u8类型的数据 9*/( C5 a0 p$ T+ A- u- ?" f0 Q 10u8 Write_RingBuff(u8 data) 11{9 n; y) f* O& ~' t 12 if(ringBuff.Lenght >= RINGBUFF_LEN) //判断缓冲区是否已满( c7 d7 |5 F& A) s- u 13 {( H5 l% X# t0 X4 V+ B& b 14 return FLASE;5 f# ^1 e0 l% F5 z6 T 15 }7 A! N/ \. X4 N 16 ringBuff.Ring_Buff[ringBuff.Tail]=data; 17// ringBuff.Tail++;( m5 b) W8 P, \ 18 ringBuff.Tail = (ringBuff.Tail+1)%RINGBUFF_LEN;//防止越界非法访问- @" z9 h p1 n6 M% Y3 S% ]% N& V 19 ringBuff.Lenght++;9 t% X1 b8 k( I% K3 K 20 return TRUE;8 b% C/ F, I2 ^! l 21}4 X! j8 [7 X8 | @6 g 读取缓冲区的数据的代码实现: 1/** 2* @brief Read_RingBuff& e/ x" r# `/ ~% b" [- f4 V 3* @param u8 *rData,用于保存读取的数据( A9 G! l4 c' f3 \ 4* @return FLASE:环形缓冲区没有数据,读取失败;TRUE:读取成功 5* @author 杰杰 6* @date 2018 7* @version v1.0 8* @note 从环形缓冲区读取一个u8类型的数据 9*/; D/ ?; f! m; q+ { 10u8 Read_RingBuff(u8 *rData) 11{- p' Q. o6 |5 ~% T- s 12 if(ringBuff.Lenght == 0)//判断非空 13 { 14 return FLASE;( a; J$ @4 F1 F! h) ` i 15 } 16 *rData = ringBuff.Ring_Buff[ringBuff.Head];//先进先出FIFO,从缓冲区头出3 q2 Q) b8 o7 @! P8 g, o 17// ringBuff.Head++; 18 ringBuff.Head = (ringBuff.Head+1)%RINGBUFF_LEN;//防止越界非法访问, o! c# @ M/ V6 J" p 19 ringBuff.Lenght--; 20 return TRUE; 21}对于读写操作需要注意的地方有两个: 1:判断队列是否为空或者满,如果空的话,是不允许读取数据的,返回FLASE。如果是满的话,也是不允许写入数据的,避免将已有数据覆盖掉。那么如果处理的速度赶不上接收的速度,可以适当增大缓冲区的大小,用空间换取时间。 2:防止指针越界非法访问,程序有说明,需要使用者对整个缓冲区的大小进行把握。8 m5 ?) u! J, h" S" B7 [! M5 F 那么在串口接收函数中: 9 q! V# s: S) N) A 1void USART1_IRQHandler(void) 2{- H ?/ }/ B* @" e+ u$ W 3 if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET) //接收中断/ h3 \7 n! @ L- U' t 4 {( D6 y( e. g& S. b9 V 5 USART_ClearITPendingBit(USART1,USART_IT_RXNE); //清楚标志位 6 Write_RingBuff(USART_ReceiveData(USART1)); //读取接收到的数据 7 }+ _; T! g7 H8 N$ @0 i 8} 测试效果 测试数据没有发生丢包现象 补充 对于现在的阶段,杰杰我本人写代码也慢慢学会规范了。所有的代码片段均使用了可读性很强的,还有可移植性也很强的。我使用了宏定义来决定是否开启环形缓冲区的方式来收发数据,移植到大家的代码并不会有其他副作用,只需要开启宏定义即可使用了。 1#define USER_RINGBUFF 1 //使用环形缓冲区形式接收数据! B! d% N( J; l7 L, X 2#if USER_RINGBUFF 3/**如果使用环形缓冲形式接收串口数据***/ 4#define RINGBUFF_LEN 200 //定义最大接收字节数 200 5#define FLASE 1 6 U; b- v+ s3 {7 P6 Z% k 6#define TRUE 0 8 ~% Y; ]) ?7 T& c2 B/ u( p' s$ m 7void RingBuff_Init(void);+ q' u0 @, ?" O, t# d) l) X 8u8 Write_RingBuff(u8 data);" p( x4 C" g& `0 J0 c) G0 E' A 9u8 Read_RingBuff(u8 *rData);9 h7 d: y, m. r- t# A 10#endif. H' Q1 h/ @3 e, |9 x. N8 T 当然,我们完全可以用空闲中断与DMA传输,效率更高,但是某些单片机没有空闲中断与DMA,那么这种环形缓冲区的作用就很大了,并且移植简便。# ]* J" r6 G% X# w+ i! ~ 说明:文章部分截图来源慕课网james_yuan老师的课程 小编:CK 往期精彩回顾【连载】从单片机到操作系统③——走进FreeRTOS7 H1 s U0 I: \- k; s 创客: 创客飞梦空间是开源公众号% o; j! [9 T' ?/ {; x; r" m( L欢迎大家分享出去 也欢迎大家投稿 , Y+ Y0 e. @' _& E( f 7 ~; h' ?& h2 p! l7 _8 D |
å®éª4 串å£å®éª.zip
下载2.62 MB, 下载次数: 933
#include <kfifo.h>* U9 c }/ w9 j/ c
9 d* _( y# t3 }& I
int __kfifo_init(struct __kfifo *fifo, void *buffer, unsigned int size)
{- n* f* `* P# [( h( S: T
fifo->in = 0;
fifo->out = 0;
fifo->mask = 0;: b$ h6 A) M5 R; R$ G
fifo->data = buffer;' c: h! U. S* Z* W. g8 ^
+ Z8 G D' |: b# _: i& M0 J$ [ G1 p
if (size < 2) {0 k! A! a# ^/ T
return -1;4 u g) \6 y3 M4 Z$ y
}! Y7 H3 z' v/ E% I
if ((size & (size-1)) != 0)
{' R4 M$ j; c* a7 Q. J
return -2; /*** Must be a power of 2 (2,4,8,16,32,64,128,256,512,...) ***/9 K. O- k6 e6 N1 \
}
/ a) `# x7 S4 v9 m$ `! ~0 T
fifo->mask = size - 1;
return 0;
}( R# y; h% H3 e6 j2 \
! D- ?7 Y2 c6 h0 M6 f( h* I; K
9 v$ m# M; e, I7 s# [1 g% `8 j% f
9 D" O& l. ^" K( E9 k* _
unsigned int __kfifo_push_char(struct __kfifo *fifo, const char *p)
{
$ g# G" b( ]7 H2 @) w+ v
if(( ( fifo->in - fifo->out ) & ( ~fifo->mask ) ) == 0 )" v- S9 B9 ~. J n
{
*( (char*)fifo->data + (fifo->in++ & fifo->mask) ) = *p;
return 1;
}! r2 q4 q" a4 C
return 0;* T% R& Q. k6 e) k
}9 J% j7 d) W5 U' [
\7 e" F6 a4 C! ]! G& ]. I
unsigned int __kfifo_pop_char(struct __kfifo *fifo, char* p )
{
if( fifo->in != fifo->out ): ~" x9 P7 X* Q" `; g3 ~7 G$ t
{ Z8 o4 f) O# M8 w, X' _+ T, F
*p = *( (char*)fifo->data + (fifo->out++ & fifo->mask) ) ;9 [2 u! K2 | F& P. ]& J( g6 }
return 1;& D/ @, h0 ]) V! z" x8 _. e* D
}2 P/ ^$ S# H* T6 a- |: ]5 m$ T5 }
( R8 b* b% y1 B
return 0;
}
, ]* U+ ]8 Y; G+ E7 J
$ d' B( F3 }$ w/ ~3 ], D
ok, 了解了解
=========================================
看了源代码, $ N$ _% d: b6 E" ]/ g
7 f! o; X' n" P# T& r$ @
串口接收与发送缓冲区FIFO 的实现 , 在 keil 51 里面 有一个简单例子, 非常好. 适用于单一资源提供者与资源消费者, 简单的代码里面就解决了资源提供者与消费者之间协调的问题. 可以去看看.1 D/ U/ s7 Y/ w/ V- D7 d3 i1 v
4 `# Z8 Z- z6 I2 M2 Q7 G
我也没正规学过数据结构,是考3级数据库时,数据结构是必须的。
一个暑假自学完一本数据结构课本,做完一本题库。
, t* u2 H: L" t! b8 c! z/ Q: c
最近让破总给我买了几本书,C++课本、习题、C++数据结构。
嘻嘻嘻我瞎搞的
新上任的版主们最近都很活跃
是吗是吗
自从考完试再没摸过,就记得个“二叉树”名字了
数据结构是个好东西,我还得去学
数据结构还是用处很大的!!!