02-链表
概述链表作为 C 语言中一种基础的数据结构，在平时写程序的时候用的并不多，但在操作系统里面使用的非常多。理解链表及其在 RTOS 中的应用，这对后续深入学习 RTOS 内核机制非常重要。
一、什么是链表？
链表是一种动态数据结构，由多个「节点」通过指针连接而成。每个节点包含两部分：
[*]数据域：存储实际数据（如整数、结构体等）；
[*]指针域：存储下一个（或上一个）节点的地址，用于连接节点。
与数组的核心区别：
[*]数组需要预先分配固定大小的连续内存，大小不可动态调整；
[*]链表的节点在内存中可以不连续，通过指针关联，大小可动态增减，插入 / 删除操作更灵活（无需移动大量元素）。
二、C 语言中链表的基础实现
在 C 语言中，链表通过「结构体 + 指针」实现。我们先从最基础的单链表开始讲解。
1. 定义节点结构
单链表的每个节点包含「数据」和「指向下一节点的指针」：
// 单链表节点结构
typedef struct Node {
int data; // 数据域（可替换为任意类型，如结构体）
struct Node* next; // 指针域：指向 next 节点
} Node;如果是双向链表（在RTOS 中更常用），还会增加一个「指向前一节点的指针」，方便双向遍历和操作：
// 双向链表节点结构
typedef struct DNode {
int data;
struct DNode* prev; // 指向 prev 节点
struct DNode* next; // 指向 next 节点
} DNode;2. 基础操作（以单链表为例）
链表的核心操作包括：创建节点、初始化链表、插入、删除、遍历、释放内存。
（1）创建节点
通过 malloc 动态分配节点内存，并初始化数据和指针：
// 创建新节点（返回节点指针，失败返回NULL）
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
return NULL; // 内存分配失败
}
newNode->data = data;
newNode->next = NULL; // 新节点默认指向NULL
return newNode;
}（2）初始化链表（头节点）
通常用一个「头节点」作为链表的起点（头节点可不含实际数据，仅用于简化操作）：
// 初始化链表（返回头节点）
Node* initList() {
Node* head = createNode(0); // 头节点数据可忽略
return head;
}（3）插入节点（尾部插入为例）
在链表末尾添加新节点：
// 向链表尾部插入节点
void insertTail(Node* head, int data) {
if (head == NULL) return;
Node* newNode = createNode(data);
if (newNode == NULL) return;
// 遍历到链表尾部
Node* cur = head;
while (cur->next != NULL) {
cur = cur->next;
}
// 插入新节点
cur->next = newNode;
}（4）删除节点（按值删除为例）
找到目标节点并释放其内存，同时调整指针连接：
// 从链表中删除首个值为data的节点
void deleteNode(Node* head, int data) {
if (head == NULL || head->next == NULL) return;
Node* cur = head->next; // 当前节点
Node* prev = head; // 前序节点
while (cur != NULL) {
if (cur->data == data) {
prev->next = cur->next; // 跳过当前节点
free(cur); // 释放内存
return;
}
prev = cur;
cur = cur->next;
}
}（5）遍历链表
从头节点开始，通过指针依次访问每个节点：
// 遍历并打印链表所有数据
void traverseList(Node* head) {
if (head == NULL || head->next == NULL) {
printf("链表为空\n");
return;
}
Node* cur = head->next;
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}（6）释放链表
避免内存泄漏，需要手动释放所有节点：
// 释放整个链表
void freeList(Node* head) {
if (head == NULL) return;
Node* cur = head;
Node* temp;
while (cur != NULL) {
temp = cur;
cur = cur->next;
free(temp);
}
}三、链表在 RTOS 中的核心应用
RTOS的核心是任务管理、资源调度、事件处理等，而链表是实现这些功能的「基础设施」。原因是：
[*]RTOS 需要频繁添加 / 删除任务、消息、定时器等对象；
[*]链表的动态性和高效操作（尤其是双向链表的插入 / 删除）能满足实时性要求。
1. 任务管理（最核心的应用）
RTOS 中每个任务由「任务控制块（TCB）」描述（包含任务优先级、状态、栈指针等信息）。这些 TCB 通常通过链表组织，常见场景：
[*]按任务状态分组：就绪态、阻塞态、挂起态的任务分别组成独立链表（如「就绪链表」「阻塞链表」）。
例如：当一个任务等待信号量时，会从「就绪链表」移到「阻塞链表」；当信号量释放时，再从「阻塞链表」移回「就绪链表」。
[*]按优先级排序：同状态的任务（如就绪态）可能按优先级组成链表，调度器只需从链表头部取最高优先级任务运行。
2. 消息队列
RTOS 中任务间通信常用「消息队列」，消息通常以链表形式存储：
[*]新消息通过「尾部插入」加入队列；
[*]接收消息时从「头部取出」，避免内存拷贝（直接通过指针传递）。
这种方式比数组实现的队列更灵活（无需预设最大长度）。
3. 定时器管理
RTOS 中的软件定时器（如延时、定时回调）通常用链表管理：
[*]所有定时器组成一个「定时器链表」，按超时时间排序；
[*]系统时钟中断触发时，遍历链表检查是否有定时器超时，若超时则执行回调函数。
4. RTOS 中链表的特殊设计
为满足实时性，RTOS 的链表实现与通用链表有差异：
[*]双向循环链表：几乎所有 RTOS 都用双向循环链表，每个节点有prev和next指针，且尾节点指向头节点，插入 / 删除操作可在 O (1) 时间完成。
[*]静态内存：避免使用malloc/free（可能导致内存碎片和不确定的执行时间），而是预先从内存池分配节点，操作时仅调整指针。
[*]宏定义简化操作：通过宏封装链表操作（如LIST_INSERT_AFTER LIST_REMOVE），减少代码冗余，保证高效性。
四、总结
[*]链表是 C 语言中重要的动态数据结构，通过指针连接节点，适合频繁插入 / 删除的场景；
[*]掌握链表是理解 RTOS 内核的基础 ——RTOS 用链表管理任务、消息、定时器等核心对象，其高效的操作特性是实时性的保障。
如下为链表操作demo例子，方便学习理解：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 单向链表节点结构体
typedef struct student {
// 数据域
int num; // 学号
int score; // 分数
char name;// 姓名
// 指针域
struct student *next;
} STU;
// 双向链表节点结构体
typedef struct double_student {
// 数据域
int num; // 学号
int score; // 分数
char name;// 姓名
// 指针域
struct double_student *front;// 保存上一个节点的地址
struct double_student *next; // 保存下一个节点的地址
} DSTU;
// ==================== 单向链表操作函数 ====================
// 单向链表创建（尾插法）
void link_creat_head(STU **p_head, STU *p_new) {
STU *p_mov = *p_head;
if (*p_head == NULL) {// 当第一次加入链表为空时，head指向p_new
*p_head = p_new;
p_new->next = NULL;
} else {// 第二次及以后加入链表
while (p_mov->next != NULL) {
p_mov = p_mov->next;// 找到原有链表的最后一个节点
}
p_mov->next = p_new;// 将新申请的节点加入链表
p_new->next = NULL;
}
}
// 单向链表遍历
void link_print(STU *head) {
STU *p_mov;
p_mov = head;
printf("\n=== 单向链表遍历结果 ===\n");
while (p_mov != NULL) {
printf("学号=%d 分数=%d 姓名:%s\n", p_mov->num, p_mov->score, p_mov->name);
p_mov = p_mov->next;
}
printf("========================\n");
}
// 单向链表释放
void link_free(STU **p_head) {
STU *pb = *p_head;
while (*p_head != NULL) {
pb = *p_head;
*p_head = (*p_head)->next;
free(pb);
pb = NULL;
}
}
// 按学号查找节点
STU *link_search_num(STU *head, int num) {
STU *p_mov;
p_mov = head;
while (p_mov != NULL) {
if (p_mov->num == num) {// 找到了
return p_mov;
}
p_mov = p_mov->next;
}
return NULL;// 没有找到
}
// 按姓名查找节点
STU *link_search_name(STU *head, char *name) {
STU *p_mov;
p_mov = head;
while (p_mov != NULL) {
if (strcmp(p_mov->name, name) == 0) {// 找到了
return p_mov;
}
p_mov = p_mov->next;
}
return NULL;// 没有找到
}
// 删除指定学号的节点
void link_delete_num(STU **p_head, int num) {
STU *pb, *pf;
pb = pf = *p_head;
if (*p_head == NULL) {// 链表为空，不用删
printf("链表为空，没有您要删的节点\n");
return;
}
while (pb->num != num && pb->next != NULL) {// 循环找要删除的节点
pf = pb;
pb = pb->next;
}
if (pb->num == num) {// 找到了一个节点的num和num相同
if (pb == *p_head) {// 要删除的节点是头节点
*p_head = pb->next;
} else {
pf->next = pb->next;
}
free(pb);
pb = NULL;
printf("删除学号为 %d 的节点成功\n", num);
} else {// 没有找到
printf("没有您要删除的节点\n");
}
}
// 按学号顺序插入节点
void link_insert_num(STU **p_head, STU *p_new) {
STU *pb, *pf;
pb = pf = *p_head;
if (*p_head == NULL) {// 链表为空链表
*p_head = p_new;
p_new->next = NULL;
return;
}
while ((p_new->num >= pb->num) && (pb->next != NULL)) {
pf = pb;
pb = pb->next;
}
if (p_new->num < pb->num) {// 找到一个节点的num比新来的节点num大，插在pb的前面
if (pb == *p_head) {// 找到的节点是头节点，插在最前面
p_new->next = *p_head;
*p_head = p_new;
} else {
pf->next = p_new;
p_new->next = pb;
}
} else {// 没有找到pb的num比p_new->num大的节点，插在最后
pb->next = p_new;
p_new->next = NULL;
}
}
// 链表排序（按学号从小到大）
void link_order(STU *head) {
STU *pf, *pb, temp;
pf = head;
if (head == NULL) {
printf("链表为空,不用排序\n");
return;
}
if (head->next == NULL) {
printf("只有一个节点，不用排序\n");
return;
}
while (pf->next != NULL) {// 以pf指向的节点为基准节点
pb = pf->next;// pb从基准元素的下个元素开始
while (pb != NULL) {
if (pf->num > pb->num) {
// 交换数据域，不改变指针结构
temp.num = pb->num;
temp.score = pb->score;
strcpy(temp.name, pb->name);
pb->num = pf->num;
pb->score = pf->score;
strcpy(pb->name, pf->name);
pf->num = temp.num;
pf->score = temp.score;
strcpy(pf->name, temp.name);
}
pb = pb->next;
}
pf = pf->next;
}
}
// ==================== 双向链表操作函数 ====================
// 双向链表创建（尾插法）
void double_link_creat_head(DSTU **p_head, DSTU *p_new) {
DSTU *p_mov = *p_head;
if (*p_head == NULL) {// 当第一次加入链表为空时，head指向p_new
*p_head = p_new;
p_new->front = NULL;
p_new->next = NULL;
} else {// 第二次及以后加入链表
while (p_mov->next != NULL) {
p_mov = p_mov->next;// 找到原有链表的最后一个节点
}
p_mov->next = p_new;// 将新申请的节点加入链表
p_new->front = p_mov;
p_new->next = NULL;
}
}
// 双向链表遍历（正向和反向）
void double_link_print(DSTU *head) {
DSTU *pb;
pb = head;
printf("\n=== 双向链表正向遍历 ===\n");
while (pb != NULL) {
printf("学号=%d 分数=%d 姓名:%s\n", pb->num, pb->score, pb->name);
if (pb->next == NULL) break;// 记录最后一个节点
pb = pb->next;
}
printf("\n=== 双向链表反向遍历 ===\n");
while (pb != NULL) {
printf("学号=%d 分数=%d 姓名:%s\n", pb->num, pb->score, pb->name);
pb = pb->front;
}
printf("========================\n");
}
// 双向链表删除节点
void double_link_delete_num(DSTU **p_head, int num) {
DSTU *pb, *pf;
pb = *p_head;
if (*p_head == NULL) {// 链表为空，不需要删除
printf("链表为空，没有您要删除的节点\n");
return;
}
while ((pb->num != num) && (pb->next != NULL)) {
pb = pb->next;
}
if (pb->num == num) {// 找到了一个节点的num和num相同，删除pb指向的节点
if (pb == *p_head) {// 找到的节点是头节点
if ((*p_head)->next == NULL) {// 只有一个节点的情况
*p_head = NULL;
} else {// 有多个节点的情况
*p_head = pb->next;// main函数中的head指向下个节点
(*p_head)->front = NULL;
}
} else {// 要删的节点是其他节点
if (pb->next != NULL) {// 删除中间节点
pf = pb->front;// 让pf指向找到的节点的前一个节点
pf->next = pb->next;// 前一个节点的next保存后一个节点的地址
(pb->next)->front = pf;// 后一个节点的front保存前一个节点的地址
} else {// 删除尾节点
pf = pb->front;
pf->next = NULL;
}
}
free(pb);// 释放找到的节点
printf("删除学号为 %d 的节点成功\n", num);
} else {// 没找到
printf("没有您要删除的节点\n");
}
}
// ==================== 主函数和菜单系统 ====================
void print_menu() {
printf("\n========== 链表操作演示程序 ==========\n");
printf("1. 单向链表操作\n");
printf("2. 双向链表操作\n");
printf("0. 退出程序\n");
printf("====================================\n");
printf("请选择操作: ");
}
void print_single_menu() {
printf("\n========== 单向链表操作菜单 ==========\n");
printf("1. 创建链表\n");
printf("2. 遍历链表\n");
printf("3. 查找节点（按学号）\n");
printf("4. 查找节点（按姓名）\n");
printf("5. 插入节点（按学号排序）\n");
printf("6. 删除节点（按学号）\n");
printf("7. 链表排序\n");
printf("8. 释放链表\n");
printf("0. 返回主菜单\n");
printf("====================================\n");
printf("请选择操作: ");
}
void print_double_menu() {
printf("\n========== 双向链表操作菜单 ==========\n");
printf("1. 创建链表\n");
printf("2. 遍历链表（正向+反向）\n");
printf("3. 删除节点（按学号）\n");
printf("0. 返回主菜单\n");
printf("====================================\n");
printf("请选择操作: ");
}
void single_list_operations() {
STU *head = NULL, *p_new = NULL, *result = NULL;
int choice, num, score, delete_num;
char name, search_name;
while (1) {
print_single_menu();
scanf("%d", &choice);
switch (choice) {
case 1:// 创建链表
printf("请输入链表初始个数: ");
scanf("%d", &num);
for (int i = 0; i < num; i++) {
p_new = (STU*)malloc(sizeof(STU));
printf("请输入第%d个节点的学号、分数、姓名: ", i+1);
scanf("%d %d %s", &p_new->num, &p_new->score, p_new->name);
link_creat_head(&head, p_new);
}
printf("链表创建成功！\n");
break;
case 2:// 遍历链表
link_print(head);
break;
case 3:// 按学号查找
printf("请输入要查找的学号: ");
scanf("%d", &num);
result = link_search_num(head, num);
if (result != NULL) {
printf("找到节点: 学号=%d 分数=%d 姓名=%s\n",
result->num, result->score, result->name);
} else {
printf("未找到学号为 %d 的节点\n", num);
}
break;
case 4:// 按姓名查找
printf("请输入要查找的姓名: ");
scanf("%s", search_name);
result = link_search_name(head, search_name);
if (result != NULL) {
printf("找到节点: 学号=%d 分数=%d 姓名=%s\n",
result->num, result->score, result->name);
} else {
printf("未找到姓名为 %s 的节点\n", search_name);
}
break;
case 5:// 插入节点
p_new = (STU*)malloc(sizeof(STU));
printf("请输入要插入节点的学号、分数、姓名: ");
scanf("%d %d %s", &p_new->num, &p_new->score, p_new->name);
link_insert_num(&head, p_new);
printf("节点插入成功！\n");
break;
case 6:// 删除节点
printf("请输入要删除的学号: ");
scanf("%d", &delete_num);
link_delete_num(&head, delete_num);
break;
case 7:// 链表排序
link_order(head);
printf("链表排序完成！\n");
break;
case 8:// 释放链表
link_free(&head);
printf("链表已释放！\n");
break;
case 0:// 返回主菜单
if (head != NULL) {
link_free(&head);
}
return;
default:
printf("无效选择，请重新输入！\n");
}
}
}
void double_list_operations() {
DSTU *head = NULL, *p_new = NULL;
int choice, num, delete_num;
while (1) {
print_double_menu();
scanf("%d", &choice);
switch (choice) {
case 1:// 创建链表
printf("请输入链表初始个数: ");
scanf("%d", &num);
for (int i = 0; i < num; i++) {
p_new = (DSTU*)malloc(sizeof(DSTU));
printf("请输入第%d个节点的学号、分数、姓名: ", i+1);
scanf("%d %d %s", &p_new->num, &p_new->score, p_new->name);
double_link_creat_head(&head, p_new);
}
printf("双向链表创建成功！\n");
break;
case 2:// 遍历链表
double_link_print(head);
break;
case 3:// 删除节点
printf("请输入要删除的学号: ");
scanf("%d", &delete_num);
double_link_delete_num(&head, delete_num);
break;
case 0:// 返回主菜单
// 释放双向链表内存
while (head != NULL) {
DSTU *temp = head;
head = head->next;
free(temp);
}
return;
default:
printf("无效选择，请重新输入！\n");
}
}
}
int main() {
int choice;
printf("欢迎使用链表基础知识演示程序！\n");
printf("本程序实现了博客中介绍的所有链表操作功能\n");
while (1) {
print_menu();
scanf("%d", &choice);
switch (choice) {
case 1:
single_list_operations();
break;
case 2:
double_list_operations();
break;
case 0:
printf("感谢使用，程序退出！\n");
return 0;
default:
printf("无效选择，请重新输入！\n");
}
}
return 0;
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 这个好，看起来很实用
页:
[1]