15. 双向链表¶
15.1. 双向链表的基本概念¶
双向链表也叫双链表,是链表的一种,是在操作系统中常用的数据结构,它的每个数据结点中都有两个指针,分别指向 直接后继和直接前驱,其头指针head是唯一确定的。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它 的前驱结点和后继结点,这种数据结构形式使得双向链表在查找时更加方便,特别是大量数据的遍历。由于双向链表具 有对称性,能方便地完成各种插入、删除等操作,但需要注意前后方向的操作。
15.2. 双向链表的函数接口讲解¶
RT-Thread为我们提供了很多操作链表的函数,如链表的初始化、添加节点、删除节点等。
RT-Thread的链表节点结构体中只有两个指针,一个是指向上一个节点的指针,另一个是指向下一个节点的指针,具体见
1 2 3 4 5 | struct rt_list_node {
struct rt_list_node *next; /**< 指向下一个节点的指针. */
struct rt_list_node *prev; /**< 指向上一个节点的指针. */
};
typedef struct rt_list_node rt_list_t;
|
15.2.1. 链表初始化函数rt_list_init()¶
在使用链表的时候必须要进行初始化,将链表的指针指向自己,为以后添加节点做准备 ,链表的数据结构也是需 要内存空间的,所以也需要进行内存的申请,链表初始化函数rt_list_init()的源码具体见 代码清单:双向链表-2, 其结果具体见 链表初始化示意图。
1 2 3 4 5 6 7 8 9 | /**
* @brief 初始化一个链表
*
* @param
*/
rt_inline void rt_list_init(rt_list_t *l)
{
l->next = l->prev = l;
}
|
其初始化完成后可以检查一下链表初始化是否成功,判断链表是不是空的就行了,因为初始化完成的时 候,链表肯定是空的,注意,在初始化链表的时候其实链表就是链表头,需要申请内存,链表的初始化 实例具体见 代码清单:双向链表-3。
1 2 3 4 5 6 7 8 9 10 | head = rt_malloc(sizeof(rt_list_t));/* 申请动态内存 */
if (RT_NULL == head) /* 没有申请成功 */
rt_kprintf("动态内存申请失败!\n");
else
rt_kprintf("动态内存申请成功,头结点地址为%d!\n",head);
rt_kprintf("\n双向链表初始化中......\n");
rt_list_init(head);
if (rt_list_isempty(head))
rt_kprintf("双向链表初始化成功!\n\n");
|
15.2.2. 向链表中插入节点¶
15.2.2.1. 向链表指定节点后面插入节点rt_list_insert_after()¶
插入节点需要先申请节点大小的内存,然后根据插入的位置(在某个节点(rt_list_t *l)后面)进行插入操作,具体见 代码清单:双向链表-4。
1 2 3 4 5 6 7 8 | rt_inline void rt_list_insert_after(rt_list_t *l, rt_list_t *n)
{
l->next->prev = n; (1)
n->next = l->next; (2)
l->next = n; (3)
n->prev = l; (4)
}
|
这是数据结构的基本使用方法,其过程具体见 插入节点的过程示意图。
15.2.2.2. 向链表指定节点前面插入节点rt_list_insert_before()¶
插入节点需要先申请节点大小的内存,然后根据插入的位置(在某个节点(rt_list_t *l)前面)进行插入操作,具体见 代码清单:双向链表-5。
1 2 3 4 5 6 7 8 | rt_inline void rt_list_insert_before(rt_list_t *l, rt_list_t *n)
{
l->prev->next = n; (1)
n->prev = l->prev; (2)
l->prev = n; (3)
n->next = l; (4)
}
|
这是数据结构的基本使用方法,其过程具体见 插入节点的过程示意图1。
插入节点的实例也很简单,但是要注意的是要申请内存,具体见 代码清单:双向链表-6 高亮部分。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | /* 插入节点:顺序插入与从末尾插入 */
rt_kprintf("添加节点和尾节点添加......\n");
/* 动态申请第一个结点的内存 */
node1 = rt_malloc(sizeof(rt_list_t));
/* 动态申请第二个结点的内存 */
node2 = rt_malloc(sizeof(rt_list_t));
rt_kprintf("添加第一个节点与第二个节点.....\n");
/* 因为这是在某个节点后面添加一个节点函数
为后面的rt_list_insert_before(某个节点之前)
添加节点做铺垫,两个函数添加完之后的顺序是
head -> node1 -> node2 */
rt_list_insert_after(head,node2);
rt_list_insert_before(node2,node1);
if ((node1->prev == head) && (node2->prev == node1))
rt_kprintf("添加节点成功!\n\n");
else
rt_kprintf("添加节点失败!\n\n");
|
15.2.3. 从链表删除节点函数rt_list_remove()¶
删除节点与添加节点一样,其实删除节点更简单,只需要知道删除哪个节点即可, 把该节点前后的节点链接起来,那它就删除了,然后该节点的指针指向节点本身即 可,不过要注意的是也要讲该节点的内存释放掉,因为该节点是动态分配内存的, 否则会导致内存泄漏,源码具体见 代码清单:双向链表-7,其实现过程具体见 节点删除过程示意图。
1 2 3 4 5 6 7 | rt_inline void rt_list_remove(rt_list_t *n)
{
n->next->prev = n->prev; (1)
n->prev->next = n->next; (2)
n->next = n->prev = n; (3)
}
|
删除节点的用法也是简单,具体见
1 2 3 4 5 | rt_kprintf("删除节点......\n"); /* 删除已有节点 */
rt_list_remove(node1);
rt_free(node1);/* 释放第一个节点的内存 */
if (node2->prev == head)
rt_kprintf("删除节点成功\n\n");
|
15.3. 双向链表的实验¶
双向链表实验实现如下功能:
调用rt_list_init初始双向链表。
调用rt_list_insert_after与rt_list_insert_ before向链表中增加节点。
调用rt_list_remove删除指定节点。
调用rt_list_isempty判断链表是否为空。
测试操作是否成功。
删除节点的时候要注意释放掉内存,具体见 代码清单:双向链表-9 高亮部分。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 | /**
*********************************************************************
* @file main.c
* @author fire
* @version V1.0
* @date 2018-xx-xx
* @brief RT-Thread 3.0 + STM32 双向链表实验
*********************************************************************
* @attention
*
* 实验平台:基于野火STM32全系列(M3/4/7)开发板
* 论坛 :http://www.firebbs.cn
* 淘宝 :https://fire-stm32.taobao.com
*
**********************************************************************
*/
/*
*************************************************************************
* 包含的头文件
*************************************************************************
*/
#include "board.h"
#include "rtthread.h"
/*
******************************************************************
* 变量
******************************************************************
*/
/* 定义线程控制块 */
static rt_thread_t test1_thread = RT_NULL;
static rt_thread_t test2_thread = RT_NULL;
/************************* 全局变量声明 ****************************/
/*
* 当我们在写应用程序的时候,可能需要用到一些全局变量。
*/
/*
*************************************************************************
* 函数声明
*************************************************************************
*/
static void test1_thread_entry(void* parameter);
static void test2_thread_entry(void* parameter);
/*
*************************************************************************
* main 函数
*************************************************************************
*/
/**
* @brief 主函数
* @param 无
* @retval 无
*/
int main(void)
{
/*
* 开发板硬件初始化,RTT系统初始化已经在main函数之前完成,
* 即在component.c文件中的rtthread_startup()函数中完成了。
* 所以在main函数中,只需要创建线程和启动线程即可。
*/
rt_kprintf("这是一个[野火]- STM32全系列开发板-RTT双向链表操作实验!\n");
test1_thread = /* 线程控制块指针 */
rt_thread_create( "test1", /* 线程名字 */
test1_thread_entry, /* 线程入口函数 */
RT_NULL, /* 线程入口函数参数 */
512, /* 线程栈大小 */
2, /* 线程的优先级 */
20); /* 线程时间片 */
/* 启动线程,开启调度 */
if (test1_thread != RT_NULL)
rt_thread_startup(test1_thread);
else
return -1;
test2_thread = /* 线程控制块指针 */
rt_thread_create( "test2", /* 线程名字 */
test2_thread_entry, /* 线程入口函数 */
RT_NULL, /* 线程入口函数参数 */
512, /* 线程栈大小 */
3, /* 线程的优先级 */
20); /* 线程时间片 */
/* 启动线程,开启调度 */
if (test2_thread != RT_NULL)
rt_thread_startup(test2_thread);
else
return -1;
}
/*
*************************************************************************
* 线程定义
*************************************************************************
*/
static void test1_thread_entry(void* parameter)
{
rt_list_t *head; /* 定义一个双向链表的头节点 */
rt_list_t *node1; /* 定义一个双向链表的头节点 */
rt_list_t *node2; /* 定义一个双向链表的头节点 */
head = rt_malloc(sizeof(rt_list_t));/* 申请动态内存 */
if (RT_NULL == head) /* 没有申请成功 */
rt_kprintf("动态内存申请失败!\n");
else
rt_kprintf("动态内存申请成功,头结点地址为%d!\n",head);
rt_kprintf("\n双向链表初始化中......\n");
rt_list_init(head);
if (rt_list_isempty(head))
rt_kprintf("双向链表初始化成功!\n\n");
/* 插入节点:顺序插入与从末尾插入 */
rt_kprintf("添加节点和尾节点添加......\n");
/* 动态申请第一个结点的内存 */
node1 = rt_malloc(sizeof(rt_list_t));
/* 动态申请第二个结点的内存 */
node2 = rt_malloc(sizeof(rt_list_t));
rt_kprintf("添加第一个节点与第二个节点.....\n");
/* 因为这是在某个节点后面添加一个节点函数
为后面的rt_list_insert_before(某个节点之前)
添加节点做铺垫,两个函数添加完之后的顺序是
head -> node1 -> node2 */
rt_list_insert_after(head,node2);
rt_list_insert_before(node2,node1);
if ((node1->prev == head) && (node2->prev == node1))
rt_kprintf("添加节点成功!\n\n");
else
rt_kprintf("添加节点失败!\n\n");
rt_kprintf("删除节点......\n"); /* 删除已有节点 */
rt_list_remove(node1);
rt_free(node1);/* 释放第一个节点的内存 */
if (node2->prev == head)
rt_kprintf("删除节点成功\n\n");
/* 线程都是一个无限循环,不能返回 */
while (1) {
LED1_TOGGLE;
rt_thread_delay(500); //每500ms扫描一次
}
}
static void test2_thread_entry(void* parameter)
{
/* 线程都是一个无限循环,不能返回 */
while (1) {
rt_kprintf("线程运行中!\n");
LED2_TOGGLE;
rt_thread_delay(1000); //每1000ms扫描一次
}
}
/*****************************END OF FILE****************************/
|