本帖最后由 xiaojie0513 于 2018-6-4 09:55 编辑 # c8 T/ {9 O$ W7 w9 _+ c 队列的概念( D( q0 q$ s9 y" `, z# j5 ]$ N3 K3 S 在此之前,我们来回顾一下队列的基本概念:% C* M- A q/ `* {% _. @( q 队列 (Queue):是一种先进先出(First In First Out ,简称 FIFO)的线性表,只允许在一端插入(入队),在另一端进行删除(出队)。) O& P. |# g, s' {' q 队列的特点 类似售票排队窗口,先到的人看到能先买到票,然后先走,后来的人只能后买到票 队列的常见两种形式 2 }! Z! r- j+ w J 普通队列8 H; i( w; X7 B! A; M ; E9 m5 w- s% W( ~3 Y/ D8 b$ S& ]6 E 在计算机中,每个信息都是存储在存储单元中的,比喻一下吧,上图的一些小正方形格子就是一个个存储单元,你可以理解为常见的数组,存放我们一个个的信息。3 W7 D% X% u( `2 }: h ( T3 `* e9 c/ S1 c/ { 当有大量数据的时候,我们不能存储所有的数据,那么计算机处理数据的时候,只能先处理先来的,那么处理完后呢,就会把数据释放掉,再处理下一个。那么,已经处理的数据的内存就会被浪费掉。因为后来的数据只能往后排队,如过要将剩余的数据都往前移动一次,那么效率就会低下了,肯定不现实,所以,环形队列就出现了。0 q/ Z7 t' H1 F9 m1 V 环形队列 它的队列就是一个环,它避免了普通队列的缺点,就是有点难理解而已,其实它就是一个队列,一样有队列头,队列尾,一样是先进先出(FIFO)。我们采用顺时针的方式来对队列进行排序。 队列头 (Head) :允许进行删除的一端称为队首。5 m: V, N( \. O 队列尾 (Tail) :允许进行插入的一端称为队尾。: K w4 k" P% s1 h$ \, U! f) N4 d * o/ Y- Z( V- F$ f2 a. `6 ]* G7 m 环形队列的实现:在计算机中,也是没有环形的内存的,只不过是我们将顺序的内存处理过,让某一段内存形成环形,使他们首尾相连,简单来说,这其实就是一个数组,只不过有两个指针,一个指向列队头,一个指向列队尾。指向列队头的指针(Head)是缓冲区可读的数据,指向列队尾的指针(Tail)是缓冲区可写的数据,通过移动这两个指针(Head) &(Tail)即可对缓冲区的数据进行读写操作了,直到缓冲区已满(头尾相接),将数据处理完,可以释放掉数据,又可以进行存储新的数据了。6 ^4 h0 ~+ w7 p; j( N # {+ \7 }3 D5 y3 ?9 j' M2 y 实现的原理:初始化的时候,列队头与列队尾都指向0,当有数据存储的时候,数据存储在‘0’的地址空间,列队尾指向下一个可以存储数据的地方‘1’,再有数据来的时候,存储数据到地址‘1’,然后队列尾指向下一个地址‘2’。当数据要进行处理的时候,肯定是先处理‘0’空间的数据,也就是列队头的数据,处理完了数据,‘0’地址空间的数据进行释放掉,列队头指向下一个可以处理数据的地址‘1’。从而实现整个环形缓冲区的数据读写。 看图,队列头就是指向已经存储的数据,并且这个数据是待处理的。下一个CPU处理的数据就是1;而队列尾则指向可以进行写数据的地址。当1处理了,就会把1释放掉。并且把队列头指向2。当写入了一个数据6,那么队列尾的指针就会指向下一个可以写的地址。 - m/ ]; \ H+ b5 o2 ] 如果你懂了环形队列,那就跟着歌曲来一步步用代码实现吧: 从队列到串口缓冲区的实现& i4 r9 O8 q- r8 v6 ~, i( E7 _串口环形缓冲区收发:在很多入门级教程中,我们知道的串口收发都是:接收一个数据,触发中断,然后把数据发回来。这种处理方式是没有缓冲的,当数量太大的时候,亦或者当数据接收太快的时候,我们来不及处理已经收到的数据,那么,当再次收到数据的时候,就会将之前还未处理的数据覆盖掉。那么就会出现丢包的现象了,对我们的程序是一个致命的创伤。 . l( B7 [) k" E; b/ \) u 那么如何避免这种情况的发生呢,很显然,上面说的一些队列的特性很容易帮我们实现我们需要的情况。将接受的数据缓存一下,让处理的速度有些许缓冲,使得处理的速度赶得上接收的速度,上面又已经分析了普通队列与环形队列的优劣了,那么我们肯定是用环形队列来进行实现了。下面就是代码的实现: ①定义一个结构体:8 z9 W k1 g1 |# J 1typedef struct 2{+ S' p8 J! ?" F) O9 X; S4 V" x/ I 3 u16 Head; 4 u16 Tail; 5 u16 Lenght; u8 e( s( s4 _# `) d2 v 6 u8 Ring_Buff[RINGBUFF_LEN]; 7}RingBuff_t;% j& l+ ?* L1 p8 K: }5 h; `2 Y 8RingBuff_t ringBuff;//创建一个ringBuff的缓冲区 ②初始化结构体相关信息:使得我们的环形缓冲区是头尾相连的,并且里面没有数据,也就是空的队列。2 Q* J+ ^; J4 t5 i 1/** 2* @brief RingBuff_Init 3* @param void3 ~) i7 P& z6 [: m 4* @return void! _$ U6 d- q; M, F4 j 5* @author 杰杰: {7 ^% {- {5 o8 q# I 6* @date 20181 m1 P- U/ I( b; Z4 T2 A 7* @version v1.0' \: K; F) R! w! A: E) d+ z 8* @note 初始化环形缓冲区 9*/ 10void RingBuff_Init(void)& N" E5 m$ d' z+ w4 I% F; h! p 11{ 12 //初始化相关信息+ g3 T+ l$ L Z 13 ringBuff.Head = 0; 14 ringBuff.Tail = 0; 15 ringBuff.Lenght = 0;5 A5 g8 h8 F. G5 _+ ~5 T 16} 初始化效果如下: 写入环形缓冲区的代码实现: 1/**, f, e- L2 L3 K! b/ ]$ G1 ], w7 X 2* @brief Write_RingBuff* G' P+ J' b7 D* B/ o' q, \ 3* @param u8 data3 O0 H# I5 V$ g: q0 g3 N0 C5 G 4* @return FLASE:环形缓冲区已满,写入失败;TRUE:写入成功) V: S; E( s+ {) D v! x0 K6 K 5* @author 杰杰 6* @date 2018$ `; `5 Y4 a. C/ \0 J- k9 Q 7* @version v1.0( d( p; \" e! z; ^ 8* @note 往环形缓冲区写入u8类型的数据 9*/ 10u8 Write_RingBuff(u8 data)( S- t: n: Z$ }. _3 s9 E/ Z ^ 11{ 12 if(ringBuff.Lenght >= RINGBUFF_LEN) //判断缓冲区是否已满 13 {2 l% j( @3 j7 u- J$ [; l 14 return FLASE;' I$ y( N* R2 w4 n 15 } 16 ringBuff.Ring_Buff[ringBuff.Tail]=data; 17// ringBuff.Tail++; 18 ringBuff.Tail = (ringBuff.Tail+1)%RINGBUFF_LEN;//防止越界非法访问* D2 b7 y* W& y1 B4 H 19 ringBuff.Lenght++; 20 return TRUE; 21}. E5 O g, O) k: F2 b2 G- v% a 读取缓冲区的数据的代码实现: 1/**# w+ ^" O M }+ z$ K5 O 2* @brief Read_RingBuff1 [+ S) A ^3 H, _ 3* @param u8 *rData,用于保存读取的数据/ X8 F W# a) m 4* @return FLASE:环形缓冲区没有数据,读取失败;TRUE:读取成功 5* @author 杰杰 6* @date 20188 ^+ F" Z5 L* }% G) w. x 7* @version v1.04 s( X! N0 f; K: X 8* @note 从环形缓冲区读取一个u8类型的数据* I3 Q, M$ U" x. O; L# r 9*/ 10u8 Read_RingBuff(u8 *rData) 11{- y; \1 m( G& I( M8 m" R 12 if(ringBuff.Lenght == 0)//判断非空 13 { 14 return FLASE; 15 } 16 *rData = ringBuff.Ring_Buff[ringBuff.Head];//先进先出FIFO,从缓冲区头出. B& P" [1 ]8 F: m: ]$ Z9 z8 L; [2 b 17// ringBuff.Head++;, y7 W" b z7 q# n 18 ringBuff.Head = (ringBuff.Head+1)%RINGBUFF_LEN;//防止越界非法访问 19 ringBuff.Lenght--;3 N6 r% f& T/ M, L5 I7 j* G! K 20 return TRUE; 21}对于读写操作需要注意的地方有两个: 1:判断队列是否为空或者满,如果空的话,是不允许读取数据的,返回FLASE。如果是满的话,也是不允许写入数据的,避免将已有数据覆盖掉。那么如果处理的速度赶不上接收的速度,可以适当增大缓冲区的大小,用空间换取时间。 2:防止指针越界非法访问,程序有说明,需要使用者对整个缓冲区的大小进行把握。. o" |! y% n" E: ` 那么在串口接收函数中: 5 A, ]' a. h! k+ g3 e# @ 1void USART1_IRQHandler(void) 2{ 3 if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET) //接收中断 4 { 5 USART_ClearITPendingBit(USART1,USART_IT_RXNE); //清楚标志位2 [% b) n! q1 E W& |! y. w 6 Write_RingBuff(USART_ReceiveData(USART1)); //读取接收到的数据5 m4 W- c; [7 q9 d2 k7 k0 M" [7 L/ d 7 }6 p. M" p( c7 N 8}) j( X6 `( Q# v. L1 m: r6 p 测试效果! s: T" l! z& m; W' g 测试数据没有发生丢包现象 补充 对于现在的阶段,杰杰我本人写代码也慢慢学会规范了。所有的代码片段均使用了可读性很强的,还有可移植性也很强的。我使用了宏定义来决定是否开启环形缓冲区的方式来收发数据,移植到大家的代码并不会有其他副作用,只需要开启宏定义即可使用了。3 q4 V. u7 l C1 A 1#define USER_RINGBUFF 1 //使用环形缓冲区形式接收数据 2#if USER_RINGBUFF 3/**如果使用环形缓冲形式接收串口数据***/ 4#define RINGBUFF_LEN 200 //定义最大接收字节数 200/ p* J% q6 X1 _* A( [ 5#define FLASE 1 6#define TRUE 0 ! l8 n1 ^" Z) z* a2 e1 n; m 7void RingBuff_Init(void); 8u8 Write_RingBuff(u8 data); 9u8 Read_RingBuff(u8 *rData);. X3 x/ t) q) P ^9 } 10#endif* l& K) j) f, k2 R1 u 2 X( E5 y4 D' i. j8 t N- ^ 当然,我们完全可以用空闲中断与DMA传输,效率更高,但是某些单片机没有空闲中断与DMA,那么这种环形缓冲区的作用就很大了,并且移植简便。 说明:文章部分截图来源慕课网james_yuan老师的课程 小编:CK 往期精彩回顾【连载】从单片机到操作系统③——走进FreeRTOS) R. Y0 p, i0 F4 h4 e4 e. F0 X) K 创客: 创客飞梦空间是开源公众号7 Q1 q" w) W8 q& w: H欢迎大家分享出去 也欢迎大家投稿$ G( Z* Q2 X9 _3 e 0 W; [) R6 }$ ^) M1 A0 Y9 N I |
å®éª4 串å£å®éª.zip
下载2.62 MB, 下载次数: 934
#include <kfifo.h>
0 O' L4 | n& u# }" s+ {% ^2 E
int __kfifo_init(struct __kfifo *fifo, void *buffer, unsigned int size)
{
fifo->in = 0;, q' }# t9 [& {, r/ ?
fifo->out = 0;
fifo->mask = 0;: S2 q( [) f* ^' K" d2 D' T
fifo->data = buffer;
if (size < 2) {" W+ h L8 `7 |6 Y7 ?; z
return -1;
}
if ((size & (size-1)) != 0)
{
return -2; /*** Must be a power of 2 (2,4,8,16,32,64,128,256,512,...) ***/+ [% p" ~7 [; {* w% Y6 w# k
}% K3 q1 T) x- n( R
' t8 h" v$ }# N3 B* U- o
fifo->mask = size - 1;
1 i1 U+ Z. c$ e2 s- s
return 0;
}
* {) t8 N d2 }2 R" {
9 R- X6 V1 L2 q9 H& a7 E+ G
" G4 M2 C" v8 S2 v( U( _
unsigned int __kfifo_push_char(struct __kfifo *fifo, const char *p)* {2 l! D# ~5 H1 U, s2 G, u5 B
{
{- [& M0 d! K7 z, D/ `
if(( ( fifo->in - fifo->out ) & ( ~fifo->mask ) ) == 0 )
{
*( (char*)fifo->data + (fifo->in++ & fifo->mask) ) = *p;
return 1;& ^' Q2 {6 E3 |% F/ g
}) M2 L/ @+ h- w7 Y/ Z# ~+ v
/ D2 `( R0 g; u2 G
return 0;% s5 S; o3 G# P7 A
}
; g6 i* D& Z% o4 u3 {5 _# H
unsigned int __kfifo_pop_char(struct __kfifo *fifo, char* p )$ F, J& m1 K, r# Z. `0 x
{
if( fifo->in != fifo->out )
{
*p = *( (char*)fifo->data + (fifo->out++ & fifo->mask) ) ;
. ~# \) i; l2 e# [( N/ j7 r1 c. l* N
return 1;
}
+ k3 t+ l* w; o# v# K
return 0;
}: P* t' J- S5 X: l0 E. A
$ F* U$ V) F. g5 \' [( ~6 l" ?! J& X$ O
ok, 了解了解2 c+ k6 H8 B) q0 A* [9 Q
=========================================. v9 i. v* T6 P. h4 \% {) U
看了源代码, . z2 j# M6 T! s" e
2 X5 _- \) s4 L& q! a N3 n
串口接收与发送缓冲区FIFO 的实现 , 在 keil 51 里面 有一个简单例子, 非常好. 适用于单一资源提供者与资源消费者, 简单的代码里面就解决了资源提供者与消费者之间协调的问题. 可以去看看.6 c. ^" D3 C M! u. d `1 m8 H! f& Q
# a Q: N, y$ _# ~) \0 Z
- i4 A. f4 z8 ?9 w
我也没正规学过数据结构,是考3级数据库时,数据结构是必须的。% |2 I- t3 U& v: y1 ]# L
一个暑假自学完一本数据结构课本,做完一本题库。
最近让破总给我买了几本书,C++课本、习题、C++数据结构。
嘻嘻嘻我瞎搞的
$ ~) y" C+ ?3 S5 a, M
新上任的版主们最近都很活跃
是吗是吗
自从考完试再没摸过,就记得个“二叉树”名字了
数据结构是个好东西,我还得去学
数据结构还是用处很大的!!!