嵌入式学习的第九天

数据结构单向链表链表是动态数据结构基于堆内存实现无需固定大小可动态增删结点完美解决数组固定容量、内存连续的短板。单向链表核心组成每个结点分为两个域串联形成单向链式结构只能从头结点向后遍历无法反向遍历。数据域(data)存储当前结点的有效数据指针域(pnext)存储下一个结点的地址实现结点串联封装链表对象优势统一管理链表头地址、链表长度无需手动维护操作更便捷。链表结构体定义分为两层结构体结点结构体存储单个数据、链表对象结构体管理整个链表typedefintDatatype_t;// 1. 链表结点结构体存储单个结点数据与后继指针typedefstructnode{Datatype_t data;// 链表数据域存放有效数据structnode*pnext;// 链表指针域存放下一结点地址}Node_t;// 2. 链表对象结构体统一管理整个链表typedefstructlink{Node_t*phead;// 链表头结点地址intlen;// 链表当前有效结点个数}Link_t;基础工具函数封装链表判空函数供增删函数调用简化代码冗余// 判断链表是否为空intis_empty_link(Link_t*plink){// 空链表返回1非空返回0returnNULLplink-phead;}链表核心操作函数1. 创建空链表功能在堆区申请内存创建一个初始化完成的空链表参数无返回值成功返回链表对象指针失败返回NULL执行步骤调用malloc向堆区申请链表对象内存判断内存申请是否成功失败打印错误信息并返回NULL初始化头指针为NULL、链表长度为0返回初始化后的链表对象指针Link_t*create_link(){// 申请链表对象堆内存Link_t*plinkmalloc(sizeof(Link_t));if(NULLplink){printf(malloc error\n);returnNULL;}// 初始化空链表plink-pheadNULL;plink-len0;returnplink;}2. 头插法插入结点功能在链表头部插入新结点参数链表对象指针、待插入数据返回值成功返回0失败返回-1执行步骤申请新结点堆内存判断申请结果给新结点数据域赋值指针域初始化为NULL新结点指针域指向原链表头结点更新链表头指针指向新结点新结点成为新头结点链表长度1核心特性后插入的数据在链表头部先插入的数据在尾部插入效率极高无遍历操作intinsert_head(Link_t*plink,Datatype_t data){// 申请新结点内存Node_t*pnodemalloc(sizeof(Node_t));if(NULLpnode){printf(malloc error\n);return-1;}// 初始化新结点pnode-datadata;pnode-pnextNULL;// 头插核心逻辑pnode-pnextplink-phead;plink-pheadpnode;// 更新链表长度plink-len;return0;}3. 尾插法插入结点功能在链表尾部追加新结点参数链表对象指针、待插入数据返回值成功返回0失败返回-1执行步骤申请新结点堆内存判断申请结果初始化新结点数据域、指针域判断链表是否为空空链表则新结点直接作为头结点非空链表遍历找到最后一个尾结点让尾结点指针域指向新结点链表长度1核心特性先插入的数据在头部后插入的数据在尾部数据顺序与插入顺序一致intinsert_tail(Link_t*plink,Datatype_t data){// 申请新结点内存Node_t*pnodemalloc(sizeof(Node_t));if(NULLpnode){printf(malloc error\n);return-1;}// 初始化新结点pnode-datadata;pnode-pnextNULL;// 尾插核心逻辑if(is_empty_link(plink)){// 空链表新结点作为头结点plink-pheadpnode;}else{// 非空链表遍历找到尾结点Node_t*pplink-phead;while(NULL!p-pnext){pp-pnext;}p-pnextpnode;}// 更新链表长度plink-len;return0;}4. 遍历打印链表功能遍历链表所有结点打印所有有效数据参数链表对象指针返回值无执行逻辑从头部结点开始循环遍历指针不为空则打印数据向后偏移直到遍历完毕voidshow_node(Link_t*plink){// 临时指针从头部开始遍历Node_t*ptempplink-phead;// 遍历所有结点while(NULL!ptemp){printf(%d ,ptemp-data);ptempptemp-pnext;}printf(\n);}5. 头删法删除结点功能删除链表头部第一个结点参数链表对象指针返回值0执行步骤判断链表是否为空为空提示删除错误临时指针保存原头结点地址待删除结点更新头指针为原头结点的下一个结点释放原头结点堆内存防止内存泄漏链表长度-1intdelete_link_head(Link_t*plink){if(is_empty_link(plink)){printf(删除错误链表为空\n);}else{Node_t*pfree;// 保存待删除的头结点pfreeplink-phead;// 更新新的头结点plink-pheadpfree-pnext;// 释放内存free(pfree);// 更新长度plink-len--;}return0;}6. 尾删法删除结点功能删除链表最后一个尾结点参数链表对象指针返回值0执行步骤判断链表是否为空为空提示删除错误链表仅有1个结点直接调用头删函数简化逻辑多结点链表遍历找到尾结点的前驱结点释放尾结点内存将前驱结点指针域置空链表长度-1intdelete_link_tail(Link_t*plink){if(is_empty_link(plink)){printf(删除错误链表为空\n);}elseif(1plink-len){// 仅有一个结点复用头删逻辑delete_link_head(plink);}else{// 遍历找到倒数第二个结点尾结点前驱Node_t*pplink-phead;while(NULL!p-pnext-pnext){pp-pnext;}// 释放尾结点free(p-pnext);// 前驱结点置为尾结点p-pnextNULL;// 更新长度plink-len--;}return0;}