链表在MCU编程时的一个应用

发表于 2017-11-18 15:17

链表是一种很常见的数据结构，在uc/OS中有大量的应用。相比数组等数据结构而言其优势有以下几点
1：插入与删除效率高，只要操作一次就能完成
2：对数据的管理更加灵活与便捷，有利于编写逻辑清晰的程序。
关于数组在程序中的应用是很普遍的，下面说说我们MCU程序员如何应用链表这种数据结构来更好的设计程序。
先描述一下我们要做的事情：
主控系统中需要管理多种子设备，每个加入主控的子设备都有一个编号，每种子设备都有对应的事件，主控系统会根据子设备的事件来完成相应动作，主控系统的动作如下：
（1）如果主控接收到事件是报警事件则立刻报警
（2）如果主控接收事件是延时报警，那就等待延时完成后再报警
（3）如果主控接收到的是是电池低压事件，那就记录好事件并提示给用户
那么，如何利用链表来设计这些功能呢？

一：实现链表结构
在event_list.h中定义相关数据

#define RF_DEV_AMOUNT    50             //链表的节点数量
typedef enum
{
EVENT_UNKOWN,                         //未知事件
EVENT_BATTERY_LOW_VOLTAGE,          //电池低压事件
EVENT_ALAMR,                         //报警事件
EVENT_DELAY_ALARM                   //延时报警事件
}dev_event_type_t;

typedef struct _DEV_EVENT_
{
  unsigned char num;                   //子设备在主控内的编码
  unsigned char delay;                //子设备的报警延时时间
}dev_event_t;

typedef struct _DEV_LIST_
{
  dev_event_t          dev_event;
  struct _DEV_LIST_    *next_node; //下一个节点
}dev_list_node_t;

void dev_list_init(void );
void dev_list_add(dev_list_node_t **pdev_node, dev_event_t *pevent);
void dev_list_delete(dev_list_node_t **pdev_node, dev_event_t *pevent);

在event_list.c中实现相关函数

#include "event_list.h"

dev_list_node_t dev_event_list[RF_DEV_AMOUNT+1]; //事件数组，用于构建链表
dev_list_node_t  *dev_event_free_list;             //指向空闲链表的指针

///将事件数组连接成链表，该链表为自由链表。当有有事件需要登记时从该
//链表中拿出一个空闲节点就可以。
void dev_list_init(void )
{
  unsigned char i;
  dev_list_node_t *qlist,*plist;

  plist = &dev_event_list[0];
  qlist = &dev_event_list[1];
  for(i = 0; i < RF_DEV_AMOUNT; i++)
  {
plist->dev_event.num = 0x00;
    plist->dev_event.delay = 0x00;
    plist->next_node = qlist;
    qlist++;
    plist++;
  }
  plist->next_node = 0;
  dev_event_free_list = &dev_event_list[0];
}
//采用链表的头插法将事件插入对应的链表中
void dev_list_add(dev_list_node_t **pdev_node, dev_event_t *pevent)
{
dev_list_node_t *pevent_node,*pnode_save;

if(dev_event_free_list == 0  || pdev_node == 0 || *pdev_node == 0 || pevent == 0)
{
   return;
}

pnode_save = dev_event_free_list->next_node;
pevent_node = dev_event_free_list;
pevent_node->dev_event.delay = pevent->delay;
pevent_node->dev_event.num = pevent->num;

pevent_node->next_node = (*pdev_node)->next_node;
(*pdev_node)->next_node = pevent_node;

dev_event_free_list = pnode_save; //把自由链表中的指针后移一个
}
//删除某个链表中的某个事件
void dev_list_delete(dev_list_node_t **pdev_node, dev_event_t *pevent)
{
dev_list_node_t *pevent_node,*pnode_save;

if(pdev_node == 0 || *pdev_node == 0 || pevent == 0)
{
      return;
}
pevent_node = *pdev_node;
while(pevent_node->next_node != 0)
{
   if(pevent_node->next_node->dev_event.num == pevent->num)
   {
   break;
   }
   pevent_node = pevent_node->next_node;
}

if(pevent_node->next_node)
{
   pnode_save = pevent_node->next_node;
   pevent_node->next_node = pevent_node->next_node->next_node;
   pnode_save->next_node = dev_event_free_list;
   dev_event_free_list = pnode_save;
}
}

二：利用链表
（1）处理报警以及延时报警事件
首先定义报警链表，把所有报警事件登记到报警链表中。
dev_list_node_t  alarm_node_head;                //定义一个头节点,方便操作链表
dev_list_node_t *palarm_node = &alarm_node_head; //指向报警事件链表

定义好后，如果主控系统接收到某个编号的报警事件后首先把要把该编号的子设备以及事件登记到报警链表中。
dev_event_t test;
test.delay = 0;                   //延时为0
test.num = 0x02;                   //子设备在主控中的编号为2号
dev_list_add(&palarm_node, &test); //登记到报警链表中

增加到报警链表中后，我们可以扫描报警链表中是否有报警事件（注意这个是要放在比如10ms的定时器中）。
void alarm_scan(void )
{
  dev_list_node_t  *alarm_node;

  alarm_node = palarm_node->next_node;
  while(alarm_node  != 0)
  {
   if(alarm_node->dev_event.delay == 0)
   {
      printf("编号:%d ", alarm_node->dev_event.num);
         printf("报警\n");
   }
   else
   {
   alarm_node->dev_event.delay--;
   }
   alarm_node = alarm_node->next_node;
  }
}

当报警消除后
dev_list_delete(&palarm_node, &test);  //从报警链表中剔除，删除后的节点恢复到自由链表中

这样就完成了开头所要求的的（1）（2）两点要求。对于实现（3）其原理同（1），（2），这里简要说明一下。

（2）处理电池低压事件
首先定义低压事件链表，把所有的子设备的电池低压信息登记到低压事件链表中。
dev_list_node_t    batter_bat_low_vol_node; //同上
dev_list_node_t *pfault_node = &batter_bat_low_vol_node;

定义好后，主控设备收到子设备的低压事件后，我们先把事件登记到低压事件链表中
dev_event_t test;
test.num = 0x05;                      //子设备在主控中的编号为5号
test.delay = 0;
dev_list_add(&pfault_node , &test) ; //登记到故障链表中

如果低压恢复
dev_list_delete(&pfault_node , &test);  //从低压链表中剔除,删除后的节点恢复到自由链表中

以上就是链表在编程时的一个应用，希望对你有些帮助。顺便说一下，以上代码时测试过的。

发表于 2017-11-18 15:17

发表于 2018-5-15 11:08

楼主在哪里呀？在深圳吗？很想和楼主认识一下

发表于 2018-5-15 14:07

本帖最后由 dukedz 于 2018-5-15 14:13 编辑

你這個鏈表不通用，最好寫成 Linux 內核那樣的結構，比較優雅，不同的業務可共用同一份代碼，運行的開銷也比較小，我有單獨提取出適合 MCU 用的 list.c 和 list.h 文件，頭文件 list.h 部分摘錄如下：

复制

#ifndef __LIST_H__

#define __LIST_H__



typedef struct list_node {

   struct list_node *next;

} list_node_t;



typedef struct {

    list_node_t *first;

    list_node_t *last;

    uint32_t    len;

} list_head_t;





list_node_t *list_get(list_head_t *head);

void list_put(list_head_t *head, list_node_t *node);



list_node_t *list_get_last(list_head_t *head);

void list_put_begin(list_head_t *head, list_node_t *node);

void list_pick(list_head_t *head, list_node_t *pre, list_node_t *node);

void list_move_begin(list_head_t *head, list_node_t *pre, list_node_t *node);





#define list_entry(ptr, type)                                   \

    container_of(ptr, type, node)



#define list_entry_safe(ptr, type) ({                           \

        list_node_t *__ptr = (ptr);                             \

        __ptr ? container_of(__ptr, type, node) : NULL;         \

    })

完整文件在：https://github.com/dukelec/cdnet/tree/master/utils

链表在MCU编程时的一个应用

相关帖子

浏览过的版块

技术新星奖章