本帖最后由 xiaojie0513 于 2018-6-4 09:55 编辑 3 d* E: l" }0 k' q+ b 队列的概念 在此之前,我们来回顾一下队列的基本概念:$ n* u% ?; f* r, R: V' c C! g1 g5 v 队列 (Queue):是一种先进先出(First In First Out ,简称 FIFO)的线性表,只允许在一端插入(入队),在另一端进行删除(出队)。: A5 i8 ]! |' }0 ~) T& W+ G & |1 B" P+ k- i% |6 s& c 队列的特点 类似售票排队窗口,先到的人看到能先买到票,然后先走,后来的人只能后买到票 队列的常见两种形式8 v2 ?6 y+ d. L 4 h& s7 e% }5 m8 p 普通队列' I8 T# Y1 d) r {5 G% A$ v* j p5 } D 在计算机中,每个信息都是存储在存储单元中的,比喻一下吧,上图的一些小正方形格子就是一个个存储单元,你可以理解为常见的数组,存放我们一个个的信息。! @+ Q# u& y6 u5 H 当有大量数据的时候,我们不能存储所有的数据,那么计算机处理数据的时候,只能先处理先来的,那么处理完后呢,就会把数据释放掉,再处理下一个。那么,已经处理的数据的内存就会被浪费掉。因为后来的数据只能往后排队,如过要将剩余的数据都往前移动一次,那么效率就会低下了,肯定不现实,所以,环形队列就出现了。 环形队列7 ^+ X' [& I5 n0 x* ?, j 它的队列就是一个环,它避免了普通队列的缺点,就是有点难理解而已,其实它就是一个队列,一样有队列头,队列尾,一样是先进先出(FIFO)。我们采用顺时针的方式来对队列进行排序。 队列头 (Head) :允许进行删除的一端称为队首。 队列尾 (Tail) :允许进行插入的一端称为队尾。9 V0 u g% V/ Y# u: I 环形队列的实现:在计算机中,也是没有环形的内存的,只不过是我们将顺序的内存处理过,让某一段内存形成环形,使他们首尾相连,简单来说,这其实就是一个数组,只不过有两个指针,一个指向列队头,一个指向列队尾。指向列队头的指针(Head)是缓冲区可读的数据,指向列队尾的指针(Tail)是缓冲区可写的数据,通过移动这两个指针(Head) &(Tail)即可对缓冲区的数据进行读写操作了,直到缓冲区已满(头尾相接),将数据处理完,可以释放掉数据,又可以进行存储新的数据了。 ( L+ R# ?! [: c4 p 实现的原理:初始化的时候,列队头与列队尾都指向0,当有数据存储的时候,数据存储在‘0’的地址空间,列队尾指向下一个可以存储数据的地方‘1’,再有数据来的时候,存储数据到地址‘1’,然后队列尾指向下一个地址‘2’。当数据要进行处理的时候,肯定是先处理‘0’空间的数据,也就是列队头的数据,处理完了数据,‘0’地址空间的数据进行释放掉,列队头指向下一个可以处理数据的地址‘1’。从而实现整个环形缓冲区的数据读写。& _ A5 R @3 a' h, g2 J , }8 H0 Z0 D2 c1 L/ s; L 看图,队列头就是指向已经存储的数据,并且这个数据是待处理的。下一个CPU处理的数据就是1;而队列尾则指向可以进行写数据的地址。当1处理了,就会把1释放掉。并且把队列头指向2。当写入了一个数据6,那么队列尾的指针就会指向下一个可以写的地址。 如果你懂了环形队列,那就跟着歌曲来一步步用代码实现吧: 从队列到串口缓冲区的实现( i+ H* ^$ q! Y9 L8 L3 O7 Y串口环形缓冲区收发:在很多入门级教程中,我们知道的串口收发都是:接收一个数据,触发中断,然后把数据发回来。这种处理方式是没有缓冲的,当数量太大的时候,亦或者当数据接收太快的时候,我们来不及处理已经收到的数据,那么,当再次收到数据的时候,就会将之前还未处理的数据覆盖掉。那么就会出现丢包的现象了,对我们的程序是一个致命的创伤。) l/ T: F4 E8 f 那么如何避免这种情况的发生呢,很显然,上面说的一些队列的特性很容易帮我们实现我们需要的情况。将接受的数据缓存一下,让处理的速度有些许缓冲,使得处理的速度赶得上接收的速度,上面又已经分析了普通队列与环形队列的优劣了,那么我们肯定是用环形队列来进行实现了。下面就是代码的实现: ①定义一个结构体:( z g3 k9 m/ E" r0 } 1typedef struct 2{ 3 u16 Head; 4 u16 Tail;4 T {2 U& `# y4 t4 c 5 u16 Lenght; 6 u8 Ring_Buff[RINGBUFF_LEN];/ f4 ^4 x- I E 7}RingBuff_t; W' R. P r! `/ S% j9 t a 8RingBuff_t ringBuff;//创建一个ringBuff的缓冲区 ②初始化结构体相关信息:使得我们的环形缓冲区是头尾相连的,并且里面没有数据,也就是空的队列。 1/** 2* @brief RingBuff_Init# y5 B( y! I; k, T0 {( D$ y 3* @param void- y9 s0 A1 Q$ u4 D+ w0 `4 V$ t 4* @return void 5* @author 杰杰 6* @date 2018 7* @version v1.0 8* @note 初始化环形缓冲区/ g& j( Z$ Q6 s, } 9*/ 10void RingBuff_Init(void)- P2 d. i1 S% |4 M; h1 U% ^6 k. m 11{ 12 //初始化相关信息+ i7 \# ~7 `8 Z4 \ 13 ringBuff.Head = 0; 14 ringBuff.Tail = 0; 15 ringBuff.Lenght = 0;& B; K% u3 q9 m; I8 \8 T 16}2 c# W; m2 L- C 初始化效果如下: + D8 n1 P# O! r) |( p1 U$ t ' Q2 @; P/ `5 m0 @ 写入环形缓冲区的代码实现: 1/** 2* @brief Write_RingBuff/ \9 s. T, B" l5 e( B+ @ 3* @param u8 data1 x* E7 O* N: n# B: D 4* @return FLASE:环形缓冲区已满,写入失败;TRUE:写入成功 5* @author 杰杰 6* @date 20182 h2 s! H( e9 n5 ? 7* @version v1.0 8* @note 往环形缓冲区写入u8类型的数据4 D' c/ `; [) t/ J: A/ t 9*/* x; I3 L! K8 h/ V7 | d 10u8 Write_RingBuff(u8 data)6 w5 S9 L, y* F0 o 11{' ?) R. }) z; D9 ?& M3 G% T 12 if(ringBuff.Lenght >= RINGBUFF_LEN) //判断缓冲区是否已满/ Q" z, W4 B* P* K- _" V 13 {+ U0 N+ S$ ]" {! O9 r 14 return FLASE;9 U/ Z) O ^' j# s 15 } 16 ringBuff.Ring_Buff[ringBuff.Tail]=data; 17// ringBuff.Tail++; 18 ringBuff.Tail = (ringBuff.Tail+1)%RINGBUFF_LEN;//防止越界非法访问8 |; k5 _3 h" H' D; f 19 ringBuff.Lenght++;1 i1 l F0 A$ Y A; ?; _2 M; K 20 return TRUE; 21} 读取缓冲区的数据的代码实现: 1/**; Y B0 s$ ~$ L4 Y 2* @brief Read_RingBuff 3* @param u8 *rData,用于保存读取的数据 4* @return FLASE:环形缓冲区没有数据,读取失败;TRUE:读取成功+ Z% h! e q8 n 5* @author 杰杰 6* @date 2018 7* @version v1.09 w! G7 v, a' ^3 G" z& _ 8* @note 从环形缓冲区读取一个u8类型的数据 9*/) z5 R. Y# m% \, o& d0 B s \3 u8 m 10u8 Read_RingBuff(u8 *rData) 11{ 12 if(ringBuff.Lenght == 0)//判断非空 13 {9 |. b0 i# d% J; E9 Q' u0 F& S# Y 14 return FLASE; 15 }6 l* Z2 t' s+ B/ T1 y# J 16 *rData = ringBuff.Ring_Buff[ringBuff.Head];//先进先出FIFO,从缓冲区头出 17// ringBuff.Head++;" x! L" T, ~8 {# U- W 18 ringBuff.Head = (ringBuff.Head+1)%RINGBUFF_LEN;//防止越界非法访问: D* p, g1 M* L! Q 19 ringBuff.Lenght--;# G' s/ ? R S: f( T! q 20 return TRUE;% ?5 i' y5 N ? 21}对于读写操作需要注意的地方有两个: S; B+ n( e8 s& l5 d( |# ~ 1:判断队列是否为空或者满,如果空的话,是不允许读取数据的,返回FLASE。如果是满的话,也是不允许写入数据的,避免将已有数据覆盖掉。那么如果处理的速度赶不上接收的速度,可以适当增大缓冲区的大小,用空间换取时间。 2:防止指针越界非法访问,程序有说明,需要使用者对整个缓冲区的大小进行把握。4 A9 A# p0 m% m! b* s3 j* ~ 那么在串口接收函数中: ^8 [5 \% D. X; X0 L 2 z5 g$ k1 ]9 c' v, h5 I 1void USART1_IRQHandler(void) 5 ]' c4 n! t! t/ G; W 2{ 3 if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET) //接收中断 4 { 5 USART_ClearITPendingBit(USART1,USART_IT_RXNE); //清楚标志位 6 Write_RingBuff(USART_ReceiveData(USART1)); //读取接收到的数据, ~7 x3 X: c) l( {: E- q 7 } 8}. a- ^* G: V' y6 @* h 测试效果; _7 X7 {# h* e; j: ?# u 测试数据没有发生丢包现象 补充 对于现在的阶段,杰杰我本人写代码也慢慢学会规范了。所有的代码片段均使用了可读性很强的,还有可移植性也很强的。我使用了宏定义来决定是否开启环形缓冲区的方式来收发数据,移植到大家的代码并不会有其他副作用,只需要开启宏定义即可使用了。. q( \- s7 A! e 1#define USER_RINGBUFF 1 //使用环形缓冲区形式接收数据 2#if USER_RINGBUFF6 t) g" Z9 w- R* d; N, |1 h 3/**如果使用环形缓冲形式接收串口数据***/ 4#define RINGBUFF_LEN 200 //定义最大接收字节数 200 5#define FLASE 1 6#define TRUE 0 W% a& [, S7 C1 L) Z& [ 7void RingBuff_Init(void); 8u8 Write_RingBuff(u8 data);" Q3 t% x" X, t+ @6 a1 s 9u8 Read_RingBuff(u8 *rData); 10#endif$ ]4 Q. d% V$ r, Q: p% S+ F% Z - Z. w R `" h) z 当然,我们完全可以用空闲中断与DMA传输,效率更高,但是某些单片机没有空闲中断与DMA,那么这种环形缓冲区的作用就很大了,并且移植简便。 说明:文章部分截图来源慕课网james_yuan老师的课程 小编:CK 往期精彩回顾创客: 创客飞梦空间是开源公众号欢迎大家分享出去 也欢迎大家投稿+ R4 A; U' s: {8 ]* c/ V / a8 `: q* N# |; q. n3 k5 N |
å®éª4 串å£å®éª.zip
下载2.62 MB, 下载次数: 934
#include <kfifo.h>
8 c1 G, |6 p" b" \- e8 u" u
9 [. i) y- A* I8 @2 R% `
( c8 t1 @- Y' M8 H3 k# o6 P
int __kfifo_init(struct __kfifo *fifo, void *buffer, unsigned int size)/ M; x6 y4 g( |0 _4 L, U; i/ l3 x& t
{
fifo->in = 0;+ B* m# P+ ]- t& c
fifo->out = 0;
fifo->mask = 0;$ q5 a* f4 u3 W- x- x. @; \0 K
fifo->data = buffer;) C- z$ b9 |8 `2 @- J
6 h5 Z8 l! L8 ^
if (size < 2) {
return -1;
} G6 j j$ G* ^$ [7 V9 R
if ((size & (size-1)) != 0)2 n% t8 L, ^3 L D; P
{
return -2; /*** Must be a power of 2 (2,4,8,16,32,64,128,256,512,...) ***/" z; _$ B+ p% M
}" m" l: K' p$ R2 j6 ^# ~
fifo->mask = size - 1;5 x2 D8 |- ^) s* o0 T
9 d) [7 _" {6 r5 P
return 0;$ r& L H: V$ Z- ?
}
' Q! v; j$ W5 t5 m& V6 n$ `
- _/ m5 I" `) a; G2 K, p0 v
, @& i c/ O* Q+ p4 j# s. s6 a
$ W$ m1 \& ~" G' A U' ~
unsigned int __kfifo_push_char(struct __kfifo *fifo, const char *p)3 U- x9 U+ {& |) t2 h9 c( \
{1 c5 h6 Y+ c" y P$ p8 O2 \
if(( ( fifo->in - fifo->out ) & ( ~fifo->mask ) ) == 0 ); i- c h1 d4 x% S8 S5 D
{( u2 U! j! ? _1 ~
*( (char*)fifo->data + (fifo->in++ & fifo->mask) ) = *p;$ ^* [3 g: C U- x/ _" F
return 1;
}
* l$ i0 H3 o q8 f
return 0;# K( B! O1 A. m
}
' \$ \, D( U& q* t( L
( p2 S; S& M# |( Y% v6 k/ R
3 s3 {3 t- n1 C# A( F. p) H: j6 O
unsigned int __kfifo_pop_char(struct __kfifo *fifo, char* p )
{
if( fifo->in != fifo->out )
{
*p = *( (char*)fifo->data + (fifo->out++ & fifo->mask) ) ;& u) Y. b! y5 I. P( v
return 1;
}
return 0;. M7 d4 B# R2 x. q7 _
}; p/ y) b0 D7 @& {
& R$ D- r" ]) }4 q5 }4 K- m
* i7 g& Y% R9 s- s7 e! k }
8 u4 I1 Q8 a1 w0 f, I$ {& ]# B; W
ok, 了解了解
=========================================% ~: w2 k# V3 @# E; {
看了源代码, 6 ~$ \$ q/ i n; Q: T3 D" L$ T
串口接收与发送缓冲区FIFO 的实现 , 在 keil 51 里面 有一个简单例子, 非常好. 适用于单一资源提供者与资源消费者, 简单的代码里面就解决了资源提供者与消费者之间协调的问题. 可以去看看.2 h5 _% C; G6 _. y/ i
4 _; p! _% F: U
我也没正规学过数据结构,是考3级数据库时,数据结构是必须的。3 c( v$ L/ s+ G- f
一个暑假自学完一本数据结构课本,做完一本题库。
) L' f! J/ Q9 b4 b: u) g
最近让破总给我买了几本书,C++课本、习题、C++数据结构。
嘻嘻嘻我瞎搞的
- w# T2 o- k" J! i2 `
新上任的版主们最近都很活跃
是吗是吗
自从考完试再没摸过,就记得个“二叉树”名字了
数据结构是个好东西,我还得去学
数据结构还是用处很大的!!!