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

嵌入式学习日志——数据结构（一）

news 2025/8/4 8:18:40

1   学习单向链表

1  数据结构与算法的关系

        数据结构 描述数据的存储组织形式与操作逻辑，算法是 解决问题的步骤流程（操作数据的方法），二者协同支撑程序设计，是程序的 “骨架” 与 “灵魂”。

1.1 代码质量与效率的衡量（复杂度分析）

1、核心概念

  • 空间复杂度：程序运行时 临时占用的存储空间 随数据量增长的趋势（关注内存开销）。

  • 时间复杂度：程序 执行时间 随数据量（问题规模 n）增长的趋势（关注运行效率），反映算法的 “耗时增速”。

2、常见时间复杂度（由优到劣排序）

复杂度

含义与典型场景

效率对比（数据量大时）

O(1)

执行时间与数据量无关（如数组随机访问）

最优，耗时恒定

O(logn)

随数据量增长，耗时以 “对数级” 放缓（如二分查找）

次优，增速远慢于线性

O(n)

耗时随数据量线性增长（如数组遍历）

基础线性，数据量大时压力渐显

O(nlogn)

耗时增长介于线性与多项式之间（如归并排序）

优于多项式复杂度，适合较大数据规模

O(n2)

耗时随数据量平方级增长（如冒泡排序）

数据量大时急剧变慢，仅适用于小规模

O(n3)

耗时随数据量立方级增长（如三重嵌套循环）

比 O(n2) 更差，极少见实用场景

O(2n)

耗时指数级爆炸（如暴力枚举所有子集）

数据量稍大即无法运行，仅理论探讨

3、复杂度的本质：趋势与对比

  • 核心逻辑：复杂度描述的是 “数据量增长时，耗时 / 空间的增长趋势”，不是实际执行时间。

  • 对比示例（数据量 n 增大时）：

    • O(logn)≪O(n)（如 n=1000，log2​n≈10，耗时差距悬殊）

    • O(nlogn)<O(n2)（如 n=1000，nlogn≈10000，n2=1000000 ）

1.2 数据结构的分类

1、逻辑结构（数据元素的 “逻辑关系”）

类型

特点与典型结构

应用场景

线性结构

元素 “一对一” 排列（如数组、链表、队列）

需顺序 / 依次处理数据（如排队系统）

非线性结构

元素 “一对多” 或 “多对多” 关系

处理复杂关联数据

- 树结构

层级化 “一对多”（如二叉树、红黑树）

需快速查找、分层管理（如文件系统）

- 图结构

灵活 “多对多”（如社交网络关系图）

需表达复杂关联（如地图路径规划）

2、存储结构（数据在内存中的 “物理存储方式”）

类型

特点与优缺点

典型结构

顺序存储

元素连续存放（依赖数组）

优点：随机访问快（通过下标 O(1)）；
缺点：插入 / 删除需移动元素（O(n) 耗时）

链式存储

元素通过 “指针 / 引用” 分散连接（如链表）

优点：插入 / 删除只需修改指针（O(1)）；
缺点：随机访问需遍历（O(n) 耗时）

散列存储

用哈希函数映射存储位置（如哈希表 HashMap）

优点：插入、查询、删除接近 O(1)；
缺点：需处理哈希冲突，占用额外空间

索引存储

建立 “索引表” 加速查找（如数据库索引）

优点：大幅提升查询效率；
缺点：占用额外空间维护索引，插入 / 删除需同步更新索引

2  链表

2.1链表与数组对比

类型存储特性插入 / 删除效率访问效率空间利用
数组连续内存，需预分配固定空间O(n)（需移动元素）O(1)（随机访问）无碎片但可能有 “闲置空间浪费”
链表离散内存，动态按需分配节点O(1)（改指针即可）O(n)（需遍历）可利用小碎片，但额外存储指针（有空间开销）

  • 数组优势：适合 “读多写少” 场景（如高频查询）；

  • 链表优势：适合 “写多读少” 场景（如高频插入、删除）。

2.2 链表分类（按结构）

1、单向链表

  • 结构：节点含 数据域 + 指向下一节点的指针，只能单向遍历（从头→尾）；

  • 示意图：node1 → node2 → node3 → NULL（尾节点指针为 NULL ）。

2、双向链表

  • 结构：节点含 数据域 + 前驱指针（prev） + 后继指针（next），支持双向遍历（可向前、向后访问）；

  • 优势：删除节点时，若已知节点位置，无需遍历找前驱（比单向链表更高效）。

3、循环链表

  • 结构：尾节点指针指向头节点（形成环形）；

  • 典型场景：Linux 内核 “任务调度链表”（循环遍历所有任务，无明确首尾）。

3  单向链表操作（C 语言实现）

3.1 核心操作

        增（插入节点）、删（删除节点）、改（修改数据）、查（查找节点）、创建（初始化链表）、销毁（释放内存）。

3.2 链表节点定义（代码优化版）

// 1. 定义数据类型（灵活适配实际需求，如 int、float 等）
typedef int DataType;  

// 2. 定义链表节点结构体
typedef struct Node {  
DataType data;  // 数据域：存储实际数据  
struct Node *next;  // 指针域：存放下一个节点的地址（连接作用）  
} LinkNode;  

关键说明：

  • DataType：通过 typedef 抽象数据类型，后续若需修改数据类型（如换 float ），只需改一行代码；

  • next 指针：占 8Byte（64 位系统），是链表 “连接” 的核心。

3.3 “头节点” 设计（避坑关键）

  • 有头链表：
    第一个节点不存实际数据（作 “哨兵节点”），作用是统一操作逻辑（插入、删除时，无需判断 “链表是否为空”）。

LinkNode *head = (LinkNode*)malloc(sizeof(LinkNode));  
head->next = NULL;  // 初始时，链表无实际节点

  • 无头链表（需注意边界）：
    第一个节点存储实际数据，操作时需区分 “空链表”（head == NULL ）和 “非空链表”，容易出错。

3.4 单向链表操作

1、头文件规范（避重复定义）

// linklist.h
#ifndef LINKLIST_H  // 标准保护宏（比 __LINKLIST_H__ 更简洁）
#define LINKLIST_H  

#include <stdio.h>
#include <stdlib.h>  // malloc/free 依赖

// 数据类型抽象（灵活替换）
typedef int DataType;  

// 链表节点结构
typedef struct Node {  
DataType data;      // 数据域
struct Node *next;  // 指针域（指向下一节点）
} LinkNode;  

// 函数声明
LinkNode* createEmptyList();          // 创建空链表（返回头节点）
void insertHead(LinkNode *head, DataType data); // 头插法
void destroyList(LinkNode *head);     // 销毁链表（释放内存）

#endif

  • 保护宏用 LINKLIST_H（简洁且避免与系统宏冲突）；

  • 头文件直接包含 stdlib.h（malloc 依赖，防止 .c 文件漏引报错）。

2、空链表创建

// linklist.c
#include "linklist.h"

LinkNode* createEmptyList()

{  
LinkNode *pHead = (LinkNode*)malloc(sizeof(LinkNode));  
if (pHead == NULL)

    {  
// 错误细化：区分“内存不足”还是“其他错误”
perror("fail to malloc");
return NULL;  
}  
// 空链表：头节点 next 指向 NULL（无实际节点）
pHead->next = NULL;  
return pHead;  
}

  • 强调 pHead->next = NULL（空链表的核心标志）。

3、头插法实现

void insertHead(LinkNode *head, DataType data)

{  
// 1. 申请新节点内存
LinkNode *pNew = (LinkNode*)malloc(sizeof(LinkNode));  
if (pNew == NULL)

    {  
perror（"fail to malloc"）; 
return;  
}  

    // 2. 赋值：数据 + 指针
pNew->data = data;  
// 关键逻辑：新节点指向原头节点的后继
pNew->next = head->next;  
// 头节点指向新节点（完成插入）
head->next = pNew;  
}

  • 必须先让 pNew->next = head->next，再修改 head->next（否则原链表会 “断开”）。

4、尾插法实现

// 尾插法：在链表末尾插入新节点
// 参数：phead - 链表头节点（有头链表），tmpdata - 待插入的数据
// 返回值：0 - 成功，-1 - 失败
int insert_tail_linklist(linknode *phead, datatype tmpdata)

{

    // 1. 创建新节点
linknode *ptmpnode = malloc(sizeof(linknode));
if (ptmpnode == NULL)

    {
// 更明确的错误提示（perror会附加系统错误信息）
perror（"fail to malloc"）;
return -1;
}

    // 2. 初始化新节点数据和指针
ptmpnode->data = tmpdata;
ptmpnode->pnext = NULL;  // 尾节点的next必须为NULL

// 3. 找到链表末尾（最后一个节点的next为NULL）
linknode *pprenode = phead;
// 循环条件：当前节点的next不为NULL（继续向后找）
while (pprenode->pnext != NULL)

    {
pprenode = pprenode->pnext;
}

    // 4. 将新节点链接到末尾
pprenode->pnext = ptmpnode;

    return 0; 
}

4、链表销毁（彻底释放内存）

void destroyList(LinkNode *head)

{  
LinkNode *pCur = head->next;  // 指向第一个实际节点
LinkNode *pTemp = NULL;  

    // 遍历释放所有节点（含头节点）
while (pCur != NULL)

    {  
pTemp = pCur;        // 暂存当前节点
pCur = pCur->next;   // 移动到下一个节点
free(pTemp);         // 释放当前节点内存
}  
free(head);  // 释放头节点
head = NULL; // 防止野指针（上层需同步置空）
}

  • 若不释放内存，程序结束前会一直占用内存（内存泄漏），长期运行可能崩溃。

5、链表遍历（两种核心模式对比）

1. 完整遍历（覆盖所有节点）

// 适用场景：访问链表所有实际节点（从头节点后继开始）
LinkNode *p = pHead->next;  // pHead 为头节点（有头链表）
while (p != NULL)

{  
// 操作当前节点：如打印数据、修改值等
printf("当前节点数据：%d\n", p->data);  
p = p->next;  // 移动到下一个节点  
}  

优势：

  • 逻辑清晰，严格遍历所有实际节点（头节点不存数据时，从 pHead->next 开始）；

  • 终止条件 p != NULL 确保处理到链表末尾（最后一个节点 next 为 NULL ）。

2. 遍历到倒数第二个节点（找尾节点前驱）

LinkNode *p = pHead->next;  
// 条件：当前节点存在，且下一个节点存在（非空）
while (p->next != NULL)

{  
// 操作逻辑：如记录前驱、判断尾节点等
p = p->next;  
}  
// 循环结束后，p 指向「倒数第二个节点」（若链表长度 ≥2）

典型应用：

  • 删除尾节点时，需通过前驱修改 next = NULL；

  • 终止条件 p->next != NULL 避免访问 NULL->next（防止程序崩溃）。

6、链表删除操作

     核心目标：从链表中删除指定元素（或满足条件的节点），需完成：

  • 找前驱：定位待删除节点的前一个节点；

  • 改指针：跳过待删除节点，维护链表连续性；

  • 释内存：释放节点空间，避免内存泄漏。

// 假设：pHead 为头节点（有头链表），删除数据等于 target 的节点
void deleteTargetNode(LinkNode *pHead, DataType target)

{  
LinkNode *pPrev = pHead;  // 前驱指针（从头节点开始，统一处理边界）  

    // 遍历找待删除节点的前驱
while (pPrev->next != NULL)

    {  
if (pPrev->next->data == target)

        {  
// 1. 标记待删除节点
LinkNode *pDel = pPrev->next;  

            // 2. 跳过待删除节点（维护链表连接）
pPrev->next = pDel->next;  

            // 3. 释放内存（避免泄漏）
free(pDel);  
pDel = NULL;  // 置空，防止野指针

            // （若只删第一个匹配项，可加 break；删所有则继续遍历）
// break;  
}

        else

        {  
// 无匹配，移动前驱指针
pPrev = pPrev->next;  
}  
}  
}  

1. 前驱指针的作用（pPrev）

  • 从头节点开始（pPrev = pHead），统一处理「删除首节点」场景（无需区分空链表或首节点，逻辑更简洁）；

  • 若直接从 pHead->next 开始，删除首节点时需单独判断（易出错）。

2. 指针修改的顺序（pPrev->next = pDel->next）

  • 必须先修改前驱的 next，再释放节点 → 确保链表连接不中断；

  • 错误顺序：先 free(pDel) 再改指针 → 访问 pDel->next 触发未定义行为。

3. 内存管理（free 与置空）

  • free(pDel) 释放节点占用的内存（避免内存泄漏）；

  • pDel = NULL 防止后续代码误操作 pDel->data（触发段错误，提醒指针已失效）。

 4. 边界场景处理

        1. 链表为空

  • 表现：pHead->next == NULL；

  • 处理：pPrev->next != NULL 条件不满足，函数直接退出（安全无操作）。

        2. 待删除节点是首节点

  • 逻辑：pPrev 为头节点，pPrev->next 是第一个实际节点；

  • 处理：修改头节点的 next = pDel->next（自动跳过首节点，无需特殊判断）。

        3. 多个相同值节点（删除所有匹配项）

  • 需求：删除链表中所有值等于 target 的节点；

  • 实现：找到匹配节点后，不执行 break，继续遍历（pPrev 不移动，因 pPrev->next 已更新）：

    while (pPrev->next != NULL)

    {  
    if (匹配条件)

        {  
    // 执行删除逻辑（不 break）  
    }

        else

        {  
    pPrev = pPrev->next;  // 仅无匹配时移动  
    }  
    }  

3.5 常见错误与解决方案

1、野指针访问（程序崩溃）

  • 错误行为：删除节点后，未 free 或未置空，后续代码误操作 pDel->data；

  • 解决：严格执行 free(pDel) 并置 pDel = NULL。

2、内存泄漏（长期运行崩溃）

  • 错误行为：删除节点时，只改指针但未 free 内存；

  • 解决：删除节点后必须调用 free 释放空间。

3、遍历死循环（链表无法终止）

  • 错误行为：删除节点后，pPrev 仍移动（如 pPrev = pPrev->next），导致跳过有效节点；

  • 解决：删除节点时，仅无匹配时移动 pPrev（匹配时不移动，因 pPrev->next 已更新）。

4  Makefile 高效编译

4.1 核心作用

  • 自动编译：根据文件依赖关系（如 main.c 依赖 func.c ），只编译修改过的文件（比手动 gcc 高效）；

  • 简化命令：把复杂编译指令（如 gcc -o main main.c func.c -Iinclude ）写进 Makefile，执行 make 即可编译。

4.2 基础语法

# 目标: 依赖文件列表
main: main.c func.c  
gcc -o main main.c func.c  # 编译命令（必须以 [Tab] 开头！）

关键规则：

  • make 会检查 “依赖文件” 的修改时间，只重新编译变化的文件；

  • 适合多文件项目（如链表实现中，list.c + main.c 分离时，用 Makefile 管理更方便）。

5  学习总结

  1. 指针操作错误：

    • 未初始化指针（如 LinkNode *p; p->next = ... ）→ 程序崩溃；

    • 忘记更新 next 指针（插入 / 删除后，链表 “断开”）→ 数据丢失或遍历异常。

  2. 内存泄漏：

    • 删除节点时，只修改指针，未释放内存（free(node) ）→ 长期运行会耗尽内存。

http://www.xdnf.cn/news/1236115.html

相关文章：

  • Supergateway教程
  • 使用DrissionPage实现xhs笔记自动翻页并爬取笔记视频、图片
  • Day22--回溯--77. 组合，216. 组合总和 III，17. 电话号码的字母组合
  • Kafka 是什么？
  • 《汇编语言：基于X86处理器》第11章 MS-Windows编程(3)
  • 【stm32】按键控制LED以及光敏传感器控制蜂鸣器
  • OSPF知识点整理
  • 实战《从0开始使用SwiftUI搭建记账软件》- 2、SwiftUI 知识点详解与使用场景
  • 6.1、Redis多级缓存原理和优化、Redis部分参数优化调整
  • 【超分辨率专题】PiSA-SR：单步Diff超分新突破，即快又好，还能在线调参
  • Linux 摄像头实时抓取：V4L2、FFmpeg 与 GStreamer 全面讲解
  • python工具方法51 视频数据的扩充（翻转、resize、crop、re_fps）
  • Transformer模型用于MT信号相关性预测与分析
  • 《深入浅出RabbitMQ：从零基础到面试通关》
  • 渗透作业4
  • wordpress登陆前登陆后显示不同的顶部菜单
  • 数据结构代码
  • 08.Redis 持久化
  • AOP动态代理
  • #C语言——刷题攻略：牛客编程入门训练（四）：运算
  • 大屏项目展示
  • 面向智能体的上下文工程：策略、实现与 LangGraph 实践
  • 09.Redis 常用命令
  • STM32-ESP8266通过MQTT与阿里云通讯
  • Coze 打通飞书多维表格，实现数据增删改查操作实战详解
  • Java线程安全类设计思路总结
  • kafka 是一个怎样的系统？是消息队列（MQ）还是一个分布式流处理平台？
  • RabbitMQ死信队列与消息幂等性实践指南
  • Rust：如何访问 *.ini 配置文件？
  • 关于车位引导及汽车乘梯解决方案的专业性、系统性、可落地性强的综合设计方案与技术实现说明，旨在为现代智慧停车楼提供高效、安全、智能的停车体验。