0. 前言程序设计 数据结构 算法。数据结构负责组织、存储数据算法负责处理数据。本文梳理数据结构基础概念完整讲解单向链表结构体设计、创建、头插、尾插、尾删以及内存泄漏检测附带完整可运行代码适合 C 语言入门学习数据结构。环境Linux GCC valgrind 内存检测工具一、数据结构基本概念1. 什么是数据结构存储具有一种或多种特定关系的数据的集合核心解决如何组织和存储数据。2. 逻辑结构数据元素之间逻辑关系逻辑结构描述元素之间抽象关系和内存怎么存放无关集合元素之间关系平等无先后层级线性结构元素之间一对一代表顺序表 (数组)、链表、栈、队列树形结构元素之间一对多代表二叉树图形结构元素之间多对多代表网状图3. 物理结构内存中实际存储方式物理结构又叫存储结构描述数据在内存如何存放。①顺序存储连续内存空间代表数组 / 顺序表✅优点随机访问元素效率高❌缺点 1. 内存空间必须连续 2. 插入删除需要大量移动元素效率低 3. 需要预先分配空间分配不当造成内存浪费或者数组越界②链式存储非连续内存代表链表✅优点插入删除方便不需要预分配内存动态申请❌缺点不能随机访问查找元素必须遍历链表③索引存储构建关键字与存储位置的索引表查找先查索引表再定位真实数据地址。④散列存储哈希存储通过哈希函数建立关键字和存储位置映射存、取都依靠哈希函数计算位置哈希表就是这种存储。4. 本课程学习清单顺序表数组单向链表、双向链表、循环链表队列、栈二叉树哈希表5.C 语言前置知识储备想要手写链表必须掌握结构体指针动态内存分配malloc / free二、单向链表结构设计单向链表每个结点包含数据域指针域指针只指向后一个结点最后一个结点指针置NULL。本设计采用链表对象结构体把头指针、链表长度封装在一起方便管理链表。1. 结点结构体保存单个节点数据//链表结点类型 typedef struct node { int data; //数据域保存的数据 struct node *pnext; //指针域存下一个结点的地址 }Node_t;2. 链表对象结构体管理整个链表//链表对象类型 typedef struct link { Node_t *phead; //链表头节点指针 int clen; //链表当前结点的个数 }Link_t;单向链表 API 接口清单接口功能create_link()创建链表对象insert_link_head()链表头插insert_link_tail()链表尾插delete_link_tail()链表尾删查找按值查找结点修改修改指定结点数据链表遍历遍历打印全部结点链表销毁释放全部结点 链表对象防止内存泄漏三、单向链表基础功能实现1. 创建链表给链表对象Link_t申请堆内存初始化头指针为 NULL链表长度置 0。Link_t *create_link() { Link_t *plink malloc(sizeof(Link_t)); if (NULL plink) { printf(malloc error\n); return NULL; } plink-phead NULL; plink-clen 0; return plink; }2. 头插法链表头部插入结点执行步骤malloc创建新结点赋值数据新结点指针域指向原来头结点更新链表对象头指针指向新结点链表长度clen⚠️顺序不能颠倒如果先改头指针会丢失原来链表。int insert_link_head(Link_t *plink, int data) { Node_t *pinsert malloc(sizeof(Node_t)); if (NULL pinsert) { printf(malloc error\n); return -1; } pinsert-data data; pinsert-pnext NULL; //头插核心两行 pinsert-pnext plink-phead; plink-phead pinsert; plink-clen; return 0; }3. 尾插法链表尾部插入结点执行逻辑创建新结点pnext置NULL判断链表是否为空空链表直接把头指针指向新结点非空循环遍历找到最后一个结点最后结点pnext指向新结点链表长度clen//判断链表是否为空辅助函数 int is_empty_link(Link_t *plink) { return plink-clen 0; } int insert_link_tail(Link_t *plink, int data) { Node_t *pinsert malloc(sizeof(Node_t)); if (NULL pinsert) { printf(malloc error\n); return -1; } pinsert-data data; pinsert-pnext NULL; if (is_empty_link(plink)) { plink-phead pinsert; } else { Node_t *ptmp plink-phead; //循环找到最后一个结点 while (ptmp-pnext ! NULL) { ptmp ptmp-pnext; } ptmp-pnext pinsert; } plink-clen; return 0; }❗易错坑不能写while(NULL-pnext ! NULL)对空指针访问成员直接段错误。4. 尾删法删除链表最后一个结点边界情况链表为空直接返回错误链表只有 1 个结点释放头结点头指针置 NULL链表 2 个结点找到倒数第二个结点释放尾结点倒数第二个结点指针置 NULL长度减一int delete_link_tail(Link_t *plink) { if (is_empty_link(plink)) { return -1; } else if (plink-pnext NULL) //只有一个结点 { free(plink-phead); plink-phead NULL; } else { Node_t *ptmp plink-phead; //ptmp定位到倒数第二个结点 while (ptmp-pnext-pnext ! NULL) { ptmp ptmp-pnext; } free(ptmp-pnext); ptmp-pnext NULL; } plink-clen--; return 0; }四、内存泄漏与 valgrind 工具1. 什么是内存泄漏用户malloc向堆区申请内存使用完成后没有调用 free 释放这块堆内存程序结束前无法被系统回收造成内存泄漏。链表开发中如果销毁链表的时候忘记 free 结点就会大量内存泄漏。2.valgrind 内存检测工具 (Linux)valgrind 可以检测内存泄漏、野指针、越界访问。安装 valgrindsudo apt-get install valgrind使用#编译程序 gcc main.c -o a.out #简单检测 valgrind ./a.out #完整泄漏检测输出泄漏详情 valgrind --leak-checkfull ./a.out3.valgrind 输出字段解读definitely lost: 确定丢失必须修复没有任何指针指向这块堆内存 indirectly lost: 间接丢失一般链表结点头结点丢了后续结点全部间接丢失 possibly lost: 可能丢失 still reachable: 内存还存在有效指针程序结束没有释放不算严格泄漏出现definitely lost代表代码一定存在内存泄漏需要检查malloc有没有对应free。五、重点总结逻辑结构管关系物理结构管内存存放顺序存储连续内存随机访问快插入删除慢链式存储非连续内存插入删除快只能遍历访问。单向链表头插新结点先接旧链表再更新头指针顺序不能颠倒。尾插需要遍历找尾结点尾删需要找到倒数第二个结点。凡是malloc堆内存必须配对free否则内存泄漏使用 valgrind 工具排查。