本帖最后由 xiaojie0513 于 2018-6-4 09:55 编辑 " O7 W/ e2 \% m/ m+ @ 队列的概念! F6 P" }3 x8 k" z. n( r 在此之前,我们来回顾一下队列的基本概念: 队列 (Queue):是一种先进先出(First In First Out ,简称 FIFO)的线性表,只允许在一端插入(入队),在另一端进行删除(出队)。 队列的特点 类似售票排队窗口,先到的人看到能先买到票,然后先走,后来的人只能后买到票 & h6 a1 u$ Z# Q$ Q+ X队列的常见两种形式 " T: [( D1 Y7 Q' R+ }' C 普通队列2 }' S8 p7 D4 u( V 8 X) t. T" p W' w7 F9 c% D 在计算机中,每个信息都是存储在存储单元中的,比喻一下吧,上图的一些小正方形格子就是一个个存储单元,你可以理解为常见的数组,存放我们一个个的信息。) K( m- n) X5 d. L 3 e8 f7 P. b o" o) B, ] f8 S 当有大量数据的时候,我们不能存储所有的数据,那么计算机处理数据的时候,只能先处理先来的,那么处理完后呢,就会把数据释放掉,再处理下一个。那么,已经处理的数据的内存就会被浪费掉。因为后来的数据只能往后排队,如过要将剩余的数据都往前移动一次,那么效率就会低下了,肯定不现实,所以,环形队列就出现了。 环形队列* ~. u; a) M& E F* X1 B$ M 它的队列就是一个环,它避免了普通队列的缺点,就是有点难理解而已,其实它就是一个队列,一样有队列头,队列尾,一样是先进先出(FIFO)。我们采用顺时针的方式来对队列进行排序。 队列头 (Head) :允许进行删除的一端称为队首。 队列尾 (Tail) :允许进行插入的一端称为队尾。 环形队列的实现:在计算机中,也是没有环形的内存的,只不过是我们将顺序的内存处理过,让某一段内存形成环形,使他们首尾相连,简单来说,这其实就是一个数组,只不过有两个指针,一个指向列队头,一个指向列队尾。指向列队头的指针(Head)是缓冲区可读的数据,指向列队尾的指针(Tail)是缓冲区可写的数据,通过移动这两个指针(Head) &(Tail)即可对缓冲区的数据进行读写操作了,直到缓冲区已满(头尾相接),将数据处理完,可以释放掉数据,又可以进行存储新的数据了。, @1 x/ r8 H3 i$ K 5 z) v1 }2 j# Y8 i _9 n 实现的原理:初始化的时候,列队头与列队尾都指向0,当有数据存储的时候,数据存储在‘0’的地址空间,列队尾指向下一个可以存储数据的地方‘1’,再有数据来的时候,存储数据到地址‘1’,然后队列尾指向下一个地址‘2’。当数据要进行处理的时候,肯定是先处理‘0’空间的数据,也就是列队头的数据,处理完了数据,‘0’地址空间的数据进行释放掉,列队头指向下一个可以处理数据的地址‘1’。从而实现整个环形缓冲区的数据读写。 看图,队列头就是指向已经存储的数据,并且这个数据是待处理的。下一个CPU处理的数据就是1;而队列尾则指向可以进行写数据的地址。当1处理了,就会把1释放掉。并且把队列头指向2。当写入了一个数据6,那么队列尾的指针就会指向下一个可以写的地址。0 g! o, m# J1 D* ~. d 如果你懂了环形队列,那就跟着歌曲来一步步用代码实现吧: 从队列到串口缓冲区的实现, n! d8 y1 B: X1 ] |串口环形缓冲区收发:在很多入门级教程中,我们知道的串口收发都是:接收一个数据,触发中断,然后把数据发回来。这种处理方式是没有缓冲的,当数量太大的时候,亦或者当数据接收太快的时候,我们来不及处理已经收到的数据,那么,当再次收到数据的时候,就会将之前还未处理的数据覆盖掉。那么就会出现丢包的现象了,对我们的程序是一个致命的创伤。 那么如何避免这种情况的发生呢,很显然,上面说的一些队列的特性很容易帮我们实现我们需要的情况。将接受的数据缓存一下,让处理的速度有些许缓冲,使得处理的速度赶得上接收的速度,上面又已经分析了普通队列与环形队列的优劣了,那么我们肯定是用环形队列来进行实现了。下面就是代码的实现:( k; n: _! S& W8 u1 G9 D# E ①定义一个结构体:7 h' b- n5 m0 a' ^( f. ?1 \ 1typedef struct8 C3 C# }' j0 s6 J s 2{4 V4 j& D |% G; T$ u 3 u16 Head; 4 u16 Tail; 5 u16 Lenght; 6 u8 Ring_Buff[RINGBUFF_LEN]; 7}RingBuff_t;. i) G( |0 `! X# |' X5 k3 u" J, y; @ 8RingBuff_t ringBuff;//创建一个ringBuff的缓冲区 ! F; o2 g9 n' c0 l ②初始化结构体相关信息:使得我们的环形缓冲区是头尾相连的,并且里面没有数据,也就是空的队列。 1/** 2* @brief RingBuff_Init 3* @param void 4* @return void3 r2 U3 K& r' n 5* @author 杰杰 6* @date 2018 7* @version v1.07 v. b* I3 f" o 8* @note 初始化环形缓冲区 9*/ 10void RingBuff_Init(void)+ j: |: y- d/ b9 u2 r- W 11{ 12 //初始化相关信息 13 ringBuff.Head = 0;' v5 S5 b0 W( {& ?: q% o# {6 { 14 ringBuff.Tail = 0;) d( ~( c& O2 L5 \! E& p" F" w/ x 15 ringBuff.Lenght = 0;, f j: ]: e% p4 R$ z. W8 e& b* U 16} 初始化效果如下: ) M* w4 a1 X; }6 `( e) T 写入环形缓冲区的代码实现: 1/** 2* @brief Write_RingBuff 3* @param u8 data 4* @return FLASE:环形缓冲区已满,写入失败;TRUE:写入成功; Z0 B& n% d- [" u 5* @author 杰杰 6* @date 2018 7* @version v1.0/ }2 w4 D5 m' V 8* @note 往环形缓冲区写入u8类型的数据3 N! z3 f# ^' k2 H5 }7 z3 p 9*/ 10u8 Write_RingBuff(u8 data)% F& s2 O3 r. L, E# { 11{ 12 if(ringBuff.Lenght >= RINGBUFF_LEN) //判断缓冲区是否已满- T |. O, v; I' b/ R7 f$ J 13 { 14 return FLASE;* {' p# E% ^( m/ @& T 15 }1 [* W$ }, V' ` 16 ringBuff.Ring_Buff[ringBuff.Tail]=data; 17// ringBuff.Tail++;$ Z( W8 `) ^: k: i) z" i4 w% K( B; ? 18 ringBuff.Tail = (ringBuff.Tail+1)%RINGBUFF_LEN;//防止越界非法访问4 P* W. o* s: a% ] T6 e 19 ringBuff.Lenght++; 20 return TRUE; 21}' K% H" B2 _4 g! |5 d 读取缓冲区的数据的代码实现: 1/** 2* @brief Read_RingBuff 3* @param u8 *rData,用于保存读取的数据 r# `" O' F2 S4 Z X 4* @return FLASE:环形缓冲区没有数据,读取失败;TRUE:读取成功 5* @author 杰杰: Q' \$ S0 a+ D) U3 Q$ V 6* @date 2018 7* @version v1.0 8* @note 从环形缓冲区读取一个u8类型的数据 9*/ 10u8 Read_RingBuff(u8 *rData) 11{ 12 if(ringBuff.Lenght == 0)//判断非空2 r3 s% D- M! M, v$ p7 X4 i 13 { 14 return FLASE;- e' G5 J/ K3 x9 N, d 15 }7 \4 ?4 F* k0 L% v4 N 16 *rData = ringBuff.Ring_Buff[ringBuff.Head];//先进先出FIFO,从缓冲区头出 17// ringBuff.Head++;, L, a- v2 r' y 18 ringBuff.Head = (ringBuff.Head+1)%RINGBUFF_LEN;//防止越界非法访问 19 ringBuff.Lenght--; 20 return TRUE;) E9 c8 F/ r$ _( N7 ^ 21}对于读写操作需要注意的地方有两个: 1:判断队列是否为空或者满,如果空的话,是不允许读取数据的,返回FLASE。如果是满的话,也是不允许写入数据的,避免将已有数据覆盖掉。那么如果处理的速度赶不上接收的速度,可以适当增大缓冲区的大小,用空间换取时间。 2:防止指针越界非法访问,程序有说明,需要使用者对整个缓冲区的大小进行把握。/ S& }! |1 {* {& y 那么在串口接收函数中: 1void USART1_IRQHandler(void) 2{2 T; ]6 j! j9 Z: W L2 c+ w 3 if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET) //接收中断 4 { 5 USART_ClearITPendingBit(USART1,USART_IT_RXNE); //清楚标志位: y0 k2 ]' C2 l 6 Write_RingBuff(USART_ReceiveData(USART1)); //读取接收到的数据2 x8 {6 d# v/ j: j, X- b, R 7 } 8}: q2 I" c! h6 w8 s6 q 测试效果 测试数据没有发生丢包现象 补充 对于现在的阶段,杰杰我本人写代码也慢慢学会规范了。所有的代码片段均使用了可读性很强的,还有可移植性也很强的。我使用了宏定义来决定是否开启环形缓冲区的方式来收发数据,移植到大家的代码并不会有其他副作用,只需要开启宏定义即可使用了。 1#define USER_RINGBUFF 1 //使用环形缓冲区形式接收数据3 B; G9 l# d8 t. s& ~ }2 a5 { 2#if USER_RINGBUFF 3/**如果使用环形缓冲形式接收串口数据***/ 4#define RINGBUFF_LEN 200 //定义最大接收字节数 200 5#define FLASE 1 6#define TRUE 0 # \4 I5 f; i B/ x6 N ?$ | 7void RingBuff_Init(void); 8u8 Write_RingBuff(u8 data);3 a2 h0 D$ y2 X7 M 9u8 Read_RingBuff(u8 *rData);$ n9 @1 T8 B n% |/ F' \0 |" ^ 10#endif9 ~" \0 z4 C e: J2 n" U- a& E 7 ]5 F3 T% E3 H- T 当然,我们完全可以用空闲中断与DMA传输,效率更高,但是某些单片机没有空闲中断与DMA,那么这种环形缓冲区的作用就很大了,并且移植简便。 说明:文章部分截图来源慕课网james_yuan老师的课程 小编:CK 往期精彩回顾创客: 创客飞梦空间是开源公众号欢迎大家分享出去 也欢迎大家投稿. w# P% [9 E |$ p9 o" m( O 1 _/ _$ H) W' f* E. Y |
å®éª4 串å£å®éª.zip
下载2.62 MB, 下载次数: 934
#include <kfifo.h>+ o( T8 E. n# s4 x3 D6 J- f9 i
& N: O+ W$ G: y3 f% w1 f* K. V3 f! s7 k
$ _2 X& w6 w6 W* t
int __kfifo_init(struct __kfifo *fifo, void *buffer, unsigned int size)7 N: M& K/ g# `' S. V
{
fifo->in = 0;
fifo->out = 0;
fifo->mask = 0;
fifo->data = buffer;
; n# B' `- M8 [
if (size < 2) {
return -1;0 E" i4 A1 u- f
}0 w6 e- ], G y. i) C! u
if ((size & (size-1)) != 0)
{
return -2; /*** Must be a power of 2 (2,4,8,16,32,64,128,256,512,...) ***/$ W. Q. @0 R0 C9 Y2 Q5 J; Z. J8 G: s
}8 v4 e8 h) i" E( c
4 F4 a: Y1 ]" X/ J0 ~7 R4 e
fifo->mask = size - 1;7 S" q. U/ N0 M4 s7 e! E. S
return 0;5 n3 x( p0 ]7 q# Z5 W P
}1 W( j* g3 N. `' w
$ A6 C, _! B5 B& z( T
+ a" C, C) s, P/ `6 G
- c V) G2 J3 l$ d' E
unsigned int __kfifo_push_char(struct __kfifo *fifo, const char *p)
{# ]2 y9 K- l. u; f& j, {
0 M0 N0 s0 }4 @* P+ N# \. U# P
if(( ( fifo->in - fifo->out ) & ( ~fifo->mask ) ) == 0 ) c( }+ a1 H# b5 l: F+ _0 V7 |& ^
{( @7 e; V; [3 G
*( (char*)fifo->data + (fifo->in++ & fifo->mask) ) = *p;( o5 M* v( ~' f' W3 Y! T
return 1;
}
return 0;
}/ I9 r) p6 S* q, W/ J& A4 b$ b
3 U3 K0 s8 \1 F8 `% f
# X7 z3 {2 J* t z% z
unsigned int __kfifo_pop_char(struct __kfifo *fifo, char* p )
{
if( fifo->in != fifo->out )
{
*p = *( (char*)fifo->data + (fifo->out++ & fifo->mask) ) ;8 Z3 Q( \- V; H7 r
! ^# [. Y' Q8 [0 `& q, H
return 1;
}2 |0 F' G/ ]$ e; X
7 w C" g' h% I' A
return 0;+ w% U* x- j1 W+ i9 k2 p
}( E% N6 e- U# w9 G+ \
* E* Q o- o6 a# j% Z- T* Q
' d* g& Q/ @ _
ok, 了解了解
=========================================& d$ [$ d' S* d5 w3 B: B
看了源代码,
4 R- A0 Z& v/ e4 r# M7 @+ V
串口接收与发送缓冲区FIFO 的实现 , 在 keil 51 里面 有一个简单例子, 非常好. 适用于单一资源提供者与资源消费者, 简单的代码里面就解决了资源提供者与消费者之间协调的问题. 可以去看看.* Q2 Z( m9 t1 `+ F+ p3 @8 Y
4 m/ [) _6 w8 i
) f! V7 x, [. ?/ q4 b# y
我也没正规学过数据结构,是考3级数据库时,数据结构是必须的。
一个暑假自学完一本数据结构课本,做完一本题库。" V7 {2 D d6 ?- I
) q9 ?! V9 S! v& A
最近让破总给我买了几本书,C++课本、习题、C++数据结构。
嘻嘻嘻我瞎搞的
新上任的版主们最近都很活跃
是吗是吗
自从考完试再没摸过,就记得个“二叉树”名字了
数据结构是个好东西,我还得去学
数据结构还是用处很大的!!!