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

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

web 2025/5/16 6:57:59

一、双向链表

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 为节点数）。
对称性节点的前驱和后继指针形成对称结构，适合实现需要双向操作的场景（如双向队列）。

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 个指针）。
物理地址连续离散
逻辑连接通过数组下标隐式表示顺序关系。通过指针显式连接节点。
http://www.xdnf.cn/news/6415.html

相关文章：

  • C++11（2）
  • MySQL DBA数据运维管理经验分享：新手入门快速提升效率的新工具与技巧
  • 基于AH1101芯片的5V升18.6V LED恒流背光供电方案设计
  • 【免费分享】虚拟机VM（适用于 Windows）17.6.3
  • 【优化算法】协方差矩阵自适应进化策略（Covariance Matrix Adaptation Evolution Strategy，CMA-ES）
  • 35页AI应用PPT《DeepSeek如何赋能职场应用》DeepSeek本地化部署与应用案例合集
  • React19源码系列之 Diff算法
  • 国产数据库工具突围：SQLynx如何解决Navicat的三大痛点？深度体验报告
  • OpenCV计算机视觉实战（5）——图像基础操作全解析
  • Apache RocketMQ ACL 2.0 全新升级
  • LabVIEW的CAN通讯测试程序
  • 第 83 场周赛：较大分组的位置、隐藏个人信息、连续整数求和、统计子串中的唯一字符
  • 2025长三角杯数学建模A题思路模型代码：智能手机产品设计优化与定价问题
  • 增强 HTNN 服务网格功能：基于 Istio 的BasicAuth 与 ACL 插件开发实战
  • 本地部署Firecrawl+Dify调用踩坑记录
  • 由于复制槽导致wal大量堆积的处理方案
  • LeetCode LCR 015. 找到字符串中所有字母异位词 (Java)
  • 机器学习第十二讲：特征选择 → 选最重要的考试科目做录取判断
  • React 第四十二节 Router 中useLoaderData的用途详解
  • 【常用算法：排序篇】7.算法魔法与面试秘籍：从趣味排序到实战通关
  • 架空防静电地板材质全解析：选对材质，守护精密空间的“安全卫士”
  • 常用的关系性统计方法
  • 【物联网】基于树莓派的物联网开发【4】——WIFI+SSH远程登录树莓派
  • 2505C++,py和go调用雅兰亭库的协程工具
  • 2025年渗透测试面试题总结-阿里云[实习]阿里云安全-安全工程师（题目+回答）
  • 2025认证杯第二阶段数学建模B题：谣言在社交网络上的传播思路+模型+代码
  • 贝叶斯优化Transformer融合支持向量机多变量回归预测，附相关性气泡图、散点密度图，Matlab实现
  • 【Python 正则表达式】
  • PostgreSQL 联合索引生效条件
  • 揭秘LLM：矩阵运算揭秘LLM单词生成机制