本帖最后由 xiaojie0513 于 2018-6-4 09:55 编辑 0 H, ~: S* i$ |0 A8 W, { 队列的概念7 n$ C# ^- h- ], W! t# m+ z; O 在此之前,我们来回顾一下队列的基本概念: Q' R3 f+ n( O( ^$ I& b5 } 队列 (Queue):是一种先进先出(First In First Out ,简称 FIFO)的线性表,只允许在一端插入(入队),在另一端进行删除(出队)。 ; J+ K# x4 J, E: D 队列的特点 类似售票排队窗口,先到的人看到能先买到票,然后先走,后来的人只能后买到票 队列的常见两种形式( D* G/ L( R( ^ 3 w; y u# A; b: i- v$ P. ^ 普通队列4 o/ _5 T+ x' A% ]. Q & {: m6 a6 i C5 f: \- `# w 在计算机中,每个信息都是存储在存储单元中的,比喻一下吧,上图的一些小正方形格子就是一个个存储单元,你可以理解为常见的数组,存放我们一个个的信息。 ` ?, M) t, l! y 当有大量数据的时候,我们不能存储所有的数据,那么计算机处理数据的时候,只能先处理先来的,那么处理完后呢,就会把数据释放掉,再处理下一个。那么,已经处理的数据的内存就会被浪费掉。因为后来的数据只能往后排队,如过要将剩余的数据都往前移动一次,那么效率就会低下了,肯定不现实,所以,环形队列就出现了。 环形队列9 E5 l, d! l0 ?( T; y 它的队列就是一个环,它避免了普通队列的缺点,就是有点难理解而已,其实它就是一个队列,一样有队列头,队列尾,一样是先进先出(FIFO)。我们采用顺时针的方式来对队列进行排序。% w- p9 I, D* r % Z9 P; d4 U9 I% u% [5 m" N 队列头 (Head) :允许进行删除的一端称为队首。 队列尾 (Tail) :允许进行插入的一端称为队尾。8 i) i8 C4 G; l- k. e1 x4 Z0 M3 |% B 环形队列的实现:在计算机中,也是没有环形的内存的,只不过是我们将顺序的内存处理过,让某一段内存形成环形,使他们首尾相连,简单来说,这其实就是一个数组,只不过有两个指针,一个指向列队头,一个指向列队尾。指向列队头的指针(Head)是缓冲区可读的数据,指向列队尾的指针(Tail)是缓冲区可写的数据,通过移动这两个指针(Head) &(Tail)即可对缓冲区的数据进行读写操作了,直到缓冲区已满(头尾相接),将数据处理完,可以释放掉数据,又可以进行存储新的数据了。' Y0 G$ [; m) `) o' q4 y 实现的原理:初始化的时候,列队头与列队尾都指向0,当有数据存储的时候,数据存储在‘0’的地址空间,列队尾指向下一个可以存储数据的地方‘1’,再有数据来的时候,存储数据到地址‘1’,然后队列尾指向下一个地址‘2’。当数据要进行处理的时候,肯定是先处理‘0’空间的数据,也就是列队头的数据,处理完了数据,‘0’地址空间的数据进行释放掉,列队头指向下一个可以处理数据的地址‘1’。从而实现整个环形缓冲区的数据读写。0 {) Q0 J! i5 D- A& Y' Y. h2 G% n ' C8 t8 v. | U( ~8 Y6 _8 m8 N. |* u' } 看图,队列头就是指向已经存储的数据,并且这个数据是待处理的。下一个CPU处理的数据就是1;而队列尾则指向可以进行写数据的地址。当1处理了,就会把1释放掉。并且把队列头指向2。当写入了一个数据6,那么队列尾的指针就会指向下一个可以写的地址。 如果你懂了环形队列,那就跟着歌曲来一步步用代码实现吧: 从队列到串口缓冲区的实现串口环形缓冲区收发:在很多入门级教程中,我们知道的串口收发都是:接收一个数据,触发中断,然后把数据发回来。这种处理方式是没有缓冲的,当数量太大的时候,亦或者当数据接收太快的时候,我们来不及处理已经收到的数据,那么,当再次收到数据的时候,就会将之前还未处理的数据覆盖掉。那么就会出现丢包的现象了,对我们的程序是一个致命的创伤。3 x0 B9 {5 N) R, f + Z$ E- Y. V5 c+ f0 }: { k- g 那么如何避免这种情况的发生呢,很显然,上面说的一些队列的特性很容易帮我们实现我们需要的情况。将接受的数据缓存一下,让处理的速度有些许缓冲,使得处理的速度赶得上接收的速度,上面又已经分析了普通队列与环形队列的优劣了,那么我们肯定是用环形队列来进行实现了。下面就是代码的实现:. y8 v# N3 ~ W/ f o+ p7 G 3 ?3 v' Q% C+ O/ c; u7 t3 t- S, Z ①定义一个结构体:, C+ q8 \8 y1 D5 i2 N 1typedef struct, M. O. H7 E' k, `- `' Y 2{) G" o8 |# }1 f2 U4 e 3 u16 Head; 4 u16 Tail;2 _8 q/ [3 M5 l5 ]& x 5 u16 Lenght; 6 u8 Ring_Buff[RINGBUFF_LEN];$ |% u+ q5 m! @ 7}RingBuff_t;2 L3 y6 l' s! t( p$ Q/ n7 R( D' y& V 8RingBuff_t ringBuff;//创建一个ringBuff的缓冲区 ②初始化结构体相关信息:使得我们的环形缓冲区是头尾相连的,并且里面没有数据,也就是空的队列。* ~& n1 D# A: |9 D( k, v 1/**' b% e/ J# t# c! \$ t K 2* @brief RingBuff_Init 3* @param void' i. O4 r" F' f4 {5 E 4* @return void* j1 e; [+ m6 h8 { 5* @author 杰杰 6* @date 2018 7* @version v1.0) ~8 i) r& i1 q2 f 8* @note 初始化环形缓冲区6 r8 G* h- v& `+ l 9*/ 10void RingBuff_Init(void) 11{( Q, J$ F. v }' h+ b, }* p 12 //初始化相关信息. b/ @% W: ^% M+ V) q% K3 P7 | 13 ringBuff.Head = 0;5 q$ w7 I- {3 Y- e* T 14 ringBuff.Tail = 0; 15 ringBuff.Lenght = 0; 16}* e6 A1 E) s1 Z: F9 _/ m 初始化效果如下: ! J; B9 g B/ x. A6 q; p ) u7 E& H% ^; \6 a# b# @ 写入环形缓冲区的代码实现: 1/**4 l g7 D7 E0 C; y 2* @brief Write_RingBuff 3* @param u8 data, ?# `) V9 `: s f! r7 Y* |( }7 k# L 4* @return FLASE:环形缓冲区已满,写入失败;TRUE:写入成功 5* @author 杰杰4 |% m7 g( }2 b: K- Z' M3 u E 6* @date 20183 U- Y6 v# ?% h 7* @version v1.0 x8 ]3 n- O" N' R+ [$ V8 B 8* @note 往环形缓冲区写入u8类型的数据2 o& [: {; B* m7 M 9*/ 10u8 Write_RingBuff(u8 data) 11{) C& C$ K2 {6 F# N- } 12 if(ringBuff.Lenght >= RINGBUFF_LEN) //判断缓冲区是否已满 13 { 14 return FLASE; 15 }$ _3 v9 w6 q7 N# c 16 ringBuff.Ring_Buff[ringBuff.Tail]=data; 17// ringBuff.Tail++;0 J$ q; ~$ i: i& p2 s/ _, h( z+ } 18 ringBuff.Tail = (ringBuff.Tail+1)%RINGBUFF_LEN;//防止越界非法访问7 k# ~# a) ]3 C) f) ~/ ? 19 ringBuff.Lenght++;" }8 H& J8 H1 ?* q 20 return TRUE; 21} 读取缓冲区的数据的代码实现: 1/**2 m6 F2 b2 R* p | 2* @brief Read_RingBuff 3* @param u8 *rData,用于保存读取的数据 i7 s4 G2 e _0 I6 T 4* @return FLASE:环形缓冲区没有数据,读取失败;TRUE:读取成功 5* @author 杰杰 6* @date 2018' Z* O* N3 Y! _ 7* @version v1.0+ Q0 n1 B1 s* |. y( r/ ^ 8* @note 从环形缓冲区读取一个u8类型的数据 `7 A* ^5 k; S/ W4 U 9*/ 10u8 Read_RingBuff(u8 *rData) 11{7 F" \7 c6 p! q; V* r 12 if(ringBuff.Lenght == 0)//判断非空6 [8 g# `* p3 l# b; [ 13 { 14 return FLASE;! ]* @8 R& [! b& \& F' e 15 } 16 *rData = ringBuff.Ring_Buff[ringBuff.Head];//先进先出FIFO,从缓冲区头出 17// ringBuff.Head++; 18 ringBuff.Head = (ringBuff.Head+1)%RINGBUFF_LEN;//防止越界非法访问$ b4 v# \7 u/ X$ i' m 19 ringBuff.Lenght--;4 v- N1 |3 B3 [6 o& q7 L 20 return TRUE;: [/ `0 @4 h6 S0 X; z' [ 21}对于读写操作需要注意的地方有两个: 1:判断队列是否为空或者满,如果空的话,是不允许读取数据的,返回FLASE。如果是满的话,也是不允许写入数据的,避免将已有数据覆盖掉。那么如果处理的速度赶不上接收的速度,可以适当增大缓冲区的大小,用空间换取时间。 2:防止指针越界非法访问,程序有说明,需要使用者对整个缓冲区的大小进行把握。 那么在串口接收函数中: 7 d7 q7 ]3 R+ }7 \# v& r& Y 1void USART1_IRQHandler(void) & x( \# s$ f; b- D 2{) l. @# `% f9 x/ d* ~2 D 3 if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET) //接收中断 4 {, m( Q) R% F, y" n9 o5 J' b 5 USART_ClearITPendingBit(USART1,USART_IT_RXNE); //清楚标志位 6 Write_RingBuff(USART_ReceiveData(USART1)); //读取接收到的数据* _; d0 d7 U% B4 f d, U+ G 7 }6 K) j/ y( R; Z/ d `3 t9 { 8}. @1 Y, N. U! c: R$ K8 V) T 测试效果 测试数据没有发生丢包现象 补充 对于现在的阶段,杰杰我本人写代码也慢慢学会规范了。所有的代码片段均使用了可读性很强的,还有可移植性也很强的。我使用了宏定义来决定是否开启环形缓冲区的方式来收发数据,移植到大家的代码并不会有其他副作用,只需要开启宏定义即可使用了。7 f) @( J' O K1 T4 [ 1#define USER_RINGBUFF 1 //使用环形缓冲区形式接收数据8 ~' g3 R. `. E5 P, A' F 2#if USER_RINGBUFF 3/**如果使用环形缓冲形式接收串口数据***/ 4#define RINGBUFF_LEN 200 //定义最大接收字节数 200 C3 M( C$ X8 h' N0 Y 5#define FLASE 1 6#define TRUE 0 1 z4 F- e/ R" j2 @( S 7void RingBuff_Init(void); 8u8 Write_RingBuff(u8 data); 9u8 Read_RingBuff(u8 *rData);- @, a, ?% Y" `% h7 ~" U/ J* P$ v 10#endif 当然,我们完全可以用空闲中断与DMA传输,效率更高,但是某些单片机没有空闲中断与DMA,那么这种环形缓冲区的作用就很大了,并且移植简便。 说明:文章部分截图来源慕课网james_yuan老师的课程 小编:CK 往期精彩回顾【连载】从单片机到操作系统③——走进FreeRTOS3 b4 B. I3 A g# J 创客: 创客飞梦空间是开源公众号- i& K8 ]9 R0 y x" X: ?# \) L欢迎大家分享出去 也欢迎大家投稿/ S6 j7 L9 Z% P: h/ B6 C ' y1 `! T, x% v7 k6 m |
å®éª4 串å£å®éª.zip
下载2.62 MB, 下载次数: 934
#include <kfifo.h>
z- }4 x) r+ \8 m. N7 c
int __kfifo_init(struct __kfifo *fifo, void *buffer, unsigned int size)
{) i7 \! i7 w6 `' ]6 F
fifo->in = 0;
fifo->out = 0;7 |; [, U7 b. X' e _
fifo->mask = 0;" ^ r1 b' v. S" z- L
fifo->data = buffer;0 i0 R( u- c$ [# i! _
' \/ u, S: V/ n0 [ p/ W7 }) c u
if (size < 2) {
return -1;
}: ] z3 Y: l$ z+ G/ n' A6 y
* V& G# u9 K8 U/ t+ e% E5 k
if ((size & (size-1)) != 0)
{
return -2; /*** Must be a power of 2 (2,4,8,16,32,64,128,256,512,...) ***// `6 Z% U) k2 f' N3 d
}
fifo->mask = size - 1;
return 0;) u! f4 h' N7 V7 L( `9 l
}
1 b7 P h/ n' H% k
" v J- y% l6 L( V1 M& A
$ L6 w: ]* B4 T R; f2 o; D
6 s ?: I; L. h( G$ }0 q E
unsigned int __kfifo_push_char(struct __kfifo *fifo, const char *p)5 A' Z3 P' E( J
{0 v# |( Z6 ^7 Q- l3 ^2 v! e+ s
9 u0 M" Q4 J! O3 i% X0 k: Q4 {
if(( ( fifo->in - fifo->out ) & ( ~fifo->mask ) ) == 0 )
{
*( (char*)fifo->data + (fifo->in++ & fifo->mask) ) = *p;
% p* O+ b" c: L' p- }3 }
return 1;
}4 {+ U9 F: Q' e2 j0 F6 W+ {
" h3 v8 A) u# Z' R! r4 O
return 0;
}- l: h# V4 D" E, q
# K* j3 {* b9 @) R1 M# I1 l
) ^, G' o. F3 T, y; i
, D) H* Y2 o' ~! k+ f4 `8 j
) p3 [6 k. T0 I" L% f z3 U
3 G7 m5 O, V* U& e. a) U
unsigned int __kfifo_pop_char(struct __kfifo *fifo, char* p )& z' N: `, C% ?% U, D
{$ ?! D+ v p% j# a
if( fifo->in != fifo->out )
{
*p = *( (char*)fifo->data + (fifo->out++ & fifo->mask) ) ;( Q. k& b$ I/ l/ y- Q' m
' A: x/ t" j# _( Q% N+ G
return 1;: F# {: b8 o( J
}# `* Y( T" C5 Z- i Y
* K5 ^ }1 x( P1 r
return 0;
}
* G; t* ?/ `' d4 n
* L: v& N l1 f$ m" V
& c _3 q, Y/ \- [2 W" v- p* ]$ E
ok, 了解了解
=========================================/ f& B7 [- u% |0 M! I |
看了源代码, 4 E4 Y3 _0 @& r3 ^
6 F# S- Y8 R7 v* |! I2 ?
串口接收与发送缓冲区FIFO 的实现 , 在 keil 51 里面 有一个简单例子, 非常好. 适用于单一资源提供者与资源消费者, 简单的代码里面就解决了资源提供者与消费者之间协调的问题. 可以去看看.
% G3 W( g B/ ?' K
我也没正规学过数据结构,是考3级数据库时,数据结构是必须的。: ], \8 Z% K# R# f% m7 |
一个暑假自学完一本数据结构课本,做完一本题库。' d2 q; ~0 K+ K! a
最近让破总给我买了几本书,C++课本、习题、C++数据结构。
嘻嘻嘻我瞎搞的
新上任的版主们最近都很活跃
是吗是吗
自从考完试再没摸过,就记得个“二叉树”名字了
数据结构是个好东西,我还得去学
数据结构还是用处很大的!!!