当前位置：首页 > news >正文

嵌入式学习笔记DAY21（双向链表、Makefile)

news 来源：原创 2025/6/23 3:00:33

一、双向链表

1.概念

双向链表（Doubly Linked List） 是一种链式数据结构，每个节点包含 两个指针（前驱指针 prev 和后继指针 next），分别指向 前一个节点 和 后一个节点，形成双向连接。

头节点（Head）：链表的起始节点，prev 指针通常为 NULL（若链表不带头节点，则头节点直接指向第一个有效节点）。
尾节点（Tail）：链表的最后一个节点，next 指针为 NULL。

2. 节点结构

struct DATATYPE
{char name[10];char sex;int age;int score;};struct DOUNode
{
struct DATATYPE data;
struct DOUNode* next;
struct DOUNode* prev;
};struct DouLinkList
{struct DOUNode* head;int clen;
};// 定义DIR枚举类型
typedef enum {FORWARD,BACKWARD
} DIR;

3.特点

特点说明
双向遍历 可从头节点正向遍历（next），也可从尾节点反向遍历（prev）。
灵活删除 / 插入 修改节点的 prev 和 next 指针即可完成操作，无需像单链表一样依赖前驱节点。
空间开销 每个节点需额外存储 prev 指针，空间复杂度为 O(n)（n 为节点数）。
对称性 节点的前驱和后继指针形成对称结构，适合实现需要双向操作的场景（如双向队列）。

特点	说明
双向遍历	可从头节点正向遍历（`next`），也可从尾节点反向遍历（`prev`）。
灵活删除 / 插入	修改节点的 `prev` 和 `next` 指针即可完成操作，无需像单链表一样依赖前驱节点。
空间开销	每个节点需额外存储 `prev` 指针，空间复杂度为 O(n)（n 为节点数）。
对称性	节点的前驱和后继指针形成对称结构，适合实现需要双向操作的场景（如双向队列）。

4.练习

创建双向链表

struct DouLinkList* CreateDouLinkList()
{struct DouLinkList* dl = (struct DouLinkList* )malloc(sizeof(struct DouLinkList));if(NULL == dl){fprintf(stderr,"CreatDouLinkList malloc");return NULL;}dl->head = NULL;dl->clen = 0;return dl;}

头插法

int InsertHeadDouLinkList(struct DouLinkList* dl, struct DATATYPE* data)
{// 检查输入参数是否合法if (dl == NULL || data == NULL) {return 1;  // 输入参数无效}// 分配新节点内存struct DOUNode* newnode = (struct DOUNode*)malloc(sizeof(struct DOUNode));if (newnode == NULL) {fprintf(stderr, "inserthead malloc failed\n");return 1;  // 内存分配失败}// 复制数据到新节点memcpy(&newnode->data, data, sizeof(struct DATATYPE));// 初始化新节点的指针newnode->next = dl->head;  // 新节点的后继指向原头节点newnode->prev = NULL;      // 新节点的前驱为NULL（因为是头节点）// 更新原头节点的前驱指针（如果原链表不为空）if (dl->head != NULL) {dl->head->prev = newnode;}// 更新链表头指针dl->head = newnode;// 更新链表长度dl->clen++;return 0;  // 插入成功
}

遍历链表

int ShowDouLinkList(struct DouLinkList* dl, DIR dir) 
{// 检查链表是否为空if (dl == NULL || dl->head == NULL) {printf("链表为空\n");return 1;  // 链表为空，返回错误码}// 初始化临时指针，用于遍历链表struct DOUNode* tmp = dl->head;// 向前遍历（从头节点开始）if (FORWARD == dir){// 从头节点开始，沿next指针遍历至尾节点while(tmp){// 打印当前节点数据printf("%s %c %d %d\n",tmp->data.name,   // 姓名tmp->data.sex,    // 性别tmp->data.age,    // 年龄tmp->data.score); // 分数// 移动至下一个节点tmp = tmp->next;}}// 向后遍历（从尾节点开始）else if (BACKWARD == dir){// 1. 先找到尾节点：通过循环移动到最后一个节点while(tmp->next){tmp = tmp->next;} // 循环结束时，tmp指向尾节点// 2. 从尾节点开始，沿prev指针向前遍历至头节点while(tmp){// 打印当前节点数据printf("%s %c %d %d\n",tmp->data.name,tmp->data.sex,tmp->data.age,tmp->data.score);// 移动至上一个节点tmp = tmp->prev;}}// 其他情况（无效方向参数）else{printf("错误：未知的遍历方向\n");return 1;  // 方向参数错误，返回错误码}return 0;  // 成功遍历完成
}

尾插

int InsertTailDouLinkList(struct DouLinkList* dl, struct DATATYPE* data) 
{// 检查输入参数合法性if (dl == NULL || data == NULL) {printf("错误：链表或数据指针为空\n");return 1;  // 输入无效，返回错误码}// 创建新节点并分配内存struct DOUNode* newNode = (struct DOUNode*)malloc(sizeof(struct DOUNode));if (newNode == NULL) {fprintf(stderr, "内存分配失败\n");return 1;  // 内存分配失败，返回错误码}// 复制数据到新节点memcpy(&newNode->data, data, sizeof(struct DATATYPE));newNode->next = NULL;  // 尾节点的next始终为NULLnewNode->prev = NULL;  // 初始化为NULL，后续可能更新// 1：链表为空，新节点直接成为头节点if (dl->head == NULL) {return InsertHeadDouLinkList(dl, data);}// 2：链表非空，找到尾节点并插入else {//先定义一个tail节点指向头struct DOUNode* tail = dl->head;// 遍历到尾节点（最后一个节点）while (tail->next != NULL) {tail = tail->next;}tail->next = newNode;  // 原来尾节点的next指向新节点newNode->prev = tail;  // 新节点的prev指向原来的尾节点}dl->clen++;return 0;  
}

按位置插入

int InserAtPosDouLinkList(struct DouLinkList* dl,int pos,struct DATATYPE* data)
{int len = GetSizeDouLinkList(dl);if(pos < 0 || pos > len){return 1;}if(0 == pos){return InsertHeadDouLinkList(dl, data);}else if(pos == len){return InsertTailDouLinkList(dl, data);}else{struct DOUNode* newnode = (struct DOUNode*)malloc(sizeof(struct DOUNode));if (NULL == newnode) {fprintf(stderr, "内存分配失败\n");return 1;  // 内存分配失败，返回错误码}memcpy(&newnode->data, data, sizeof(struct DOUNode));newnode->prev = NULL;  newnode->next = NULL;//节点初始化struct DOUNode* tmp = dl->head;int i = 0;for(i = 0;i < pos;++i){tmp = tmp -> next;}newnode->next = tmp;newnode->prev = tmp->prev;tmp->prev = newnode;newnode->prev->next = newnode;dl->clen++;}return 0;}

查找

struct DOUNode* FindDouLinkList(struct DouLinkList* dl, char* name)
{if (dl == NULL || dl->head == NULL) {return NULL;  // 链表为空，直接返回NULL}struct DOUNode* tmp = dl->head;while (tmp != NULL) {if (strcmp(tmp->data.name, name) == 0) {return tmp;  // 找到匹配节点，返回数据指针}tmp = tmp->next;  // 移动到下一个节点}return NULL;  // 未找到匹配节点
}

修改

nt ModifyDouLinkList(struct DouLinkList* dl,char *name,struct DATATYPE* data)
{struct DOUNode* ret = FindDouLinkList(dl,name);if(NULL == ret){return 1;}memcpy(&ret->data,data,sizeof(struct DATATYPE));return 0;ModifyDouLinkList(dl,"zhang",&data[5]);printf("---------modify-------------\n");ShowDouLinkList(dl,FORWARD);}

二、makefile

Makefile 是一种由 make 工具 读取和执行的脚本文件，主要用于 自动化编译和构建程序。它通过定义文件间的依赖关系和编译规则，让开发者只需一个简单的命令（如 make）就能完成复杂的项目编译过程，避免手动输入大量编译命令。

自动化编译：只需要make命令，自动根据文件修改时间决定哪些文件需要重新编译，哪些不需要，提高编译效率；
管理依赖关系：明确指定源文件、头文件和目标文件之间的依赖关系，确保编译顺序正确；
简化编译流程：避免手动输入冗长复杂的编译命令

一个Makefile由多个规则组成，基本格式为：

目标(Target): 依赖(Prerequisites)
命令(Command)

目标（Target）：通常是要生成的文件（如可执行文件、库文件）或执行的操作（如 clean）。

依赖（Prerequisites）：生成目标所需的文件或其他目标。

命令（Command）：生成目标需要执行的 shell 命令，必须以 Tab 键 开头。

示例：

# 代表源文件列表

SRC += main.c // +=表示追加变量值
SRC += doulink.c

# 可执行文件

DST = app //代表最终你想要生成的可执行文件名，后续运行时输入./app即可

#编译器名称
CC = gcc

#调试
FLAG = -g
LIB = -lm

#代表引用变量

$(DST):$(SRC)
$(CC) $(SRC) $(FLAG) $(LIB) -o $(DST)

//等价于手动执行：gcc main.c doulink.c -g -ln -o app

clean:
rm $(DST)

# ---------------------------
# 隐含规则与执行逻辑
# ---------------------------# 当执行 `make` 时，默认执行第一个目标（此处为 $(DST)）
# 流程：
# 1. 检查是否存在可执行文件 `app`
# 2. 检查依赖文件（main.c、doulink.c）的修改时间是否比 `app` 新
# 3. 若文件更新或不存在，执行编译命令重新生成### **关键知识点解析**1. **变量定义**：- **变量名**：习惯用大写字母（如 `SRC`、`DST`），提高可读性。- **赋值符号**：- `=`：延迟赋值（变量值在使用时展开）。- `+=`：追加赋值（等价于 `SRC = $(SRC) main.c`）。- **预定义变量**：- `$(CC)`：默认值为 `cc`，此处显式指定为 `gcc`。- `$(CFLAGS)`：默认用于传递编译选项，此处用 `FLAG` 代替。2. **编译选项**：- `-g`：生成调试信息，允许使用 `gdb` 调试程序。- `-lm`：链接数学库（如 `sqrt()`、`sin()` 等函数需此库）。3. **目标与依赖**：- **目标**：可以是文件或操作（如 `clean`）。- **依赖**：生成目标所需的文件或其他目标（如 `$(SRC)` 是 `$(DST)` 的依赖）。- **命令缩进**：必须使用 **Tab 键** 缩进，不能用空格（否则会报错）。4. **伪目标（Phony）**：- 虽然 `clean` 不生成实际文件，但建议添加

三、存储结构对比

1. 顺序表（Sequential List）

本质：用 连续的内存空间 存储数据元素，逻辑上相邻的元素在物理地址上也相邻。
实现方式：通常用数组实现，通过数组下标访问元素。
例子：C 语言中的数组 int arr[10]，Java 中的 ArrayList。

2. 链表（Linked List）

本质：用 离散的内存节点 存储数据元素，节点通过 指针（或引用） 连接，逻辑上相邻的元素在物理地址上不一定相邻。
实现方式：每个节点包含 数据域 和 指针域（指向下一个节点），分为单向链表、双向链表、循环链表等。
例子：C 语言中的 struct Node 结构体链表，Java 中的 LinkedList。

特性	顺序表	链表
内存分配	静态分配（编译时确定大小）或动态分配（运行时分配连续空间，如`malloc`）。	动态分配（节点空间单独申请，地址离散）。
节点结构	元素直接存储在数组中，无额外指针开销。	每个节点包含数据域和指针域（单向链表需 1 个指针，双向链表需 2 个指针）。
物理地址	连续	离散
逻辑连接	通过数组下标隐式表示顺序关系。	通过指针显式连接节点。

一、双向链表

二、makefile

1. 顺序表（Sequential List）

2. 链表（Linked List）

相关文章：