数据结构单向链表应用双向链表-北京尧图网络

单向链表应用查找结点传统遍历结点返回结构体指针函数传入链表对象结构体指针查找结点的位置进行是否为空链表判断进行传入的参数位置是否合理定义局部变量指针来指向查找结点有循环跳出条件采用for循环遍历查找时间复杂度高Node_t * find_node(Link_t *plink,Datatype_t pos) { if(is_empty_link(plink)) { printf(空链表查找错误\n); return NULL; } if(pos0 || pos plink-len) { printf(位置错误查找链表失败\n); return NULL; } Node_t*p plink-phead; for(int i 1;i pos;i) { p p-pnext; } return p; }查找结点快慢指针返回结构体指针的函数传入链表对象结构体指针进行是否为空链表的判断定义两个局部变量指针快指针慢指针以快指针指向不为空为条件进行while循环快指针走两步慢指针走一步快指针的下一个不为空时快指针走其第二步慢指针走一步。时间复杂度低Node_t*find_mid(Link_t*plink) { if(is_empty_link(plink)) { printf(empty link error\n); return NULL; } Node_t*pfast plink-phead; Node_t*pslow pfast; while(NULL! pfast) { pfast pfast-pnext; if(NULL pfast) { break; } pfast pfast-pnext; pslow pslow-pnext; } return pslow; }查找倒数第k个结点返回结构体指针的函数传入链表对象结构体指针要查找的位置进行是否为空链表判断定义局部变量快指针先指向链表头结点让其先走k步定义局部变量慢指针指向链表头结点Node_t *find_oppsite(Link_t*plink,Datatype_t num) { if(is_empty_link(plink)) { printf(empty link error); return 0; } Node_t*pfast plink-phead; for(int i 0;inum;i) { if(NULL pfast-pnext) { return NULL; } pfast pfast-pnext; } Node_t*pslow plink-phead; while(NULL!pfast) { pfast pfast-pnext; pslow pslow-pnext; } return pslow; }倒置链表传入链表对象指针进行是否为空指针判断单向链表只能从头到尾倒置时需要借助局部指针变量定义两个局部变量指针从头结点处断开链表原链表头置空作为新链表的结束标志把原链表的每个结点依次插到新链表的最前面算法当前结点拿出来指针后移准备下一个结点当前结点的pnext指向新链表的头把当前链表设置为新链表的头。int oppsite_link(Link_t*plink) { if(is_empty_link(plink)) { printf(empty node,error\n); return -1; } Node_t*pinsert NULL; Node_t*ptmp plink-phead; plink-phead NULL; while(NULL ! ptmp) { pinsert ptmp; ptmp ptmp-pnext; pinsert-pnext plink-phead; plink-phead pinsert; } return 0; }链表排序先进行是否为空链表判断链表是否只有一个结点判断为真直接返回定义局部变量指针并初始化为指向链表头结点的下一个结点从链表头结点的下一个结点处断开链表把链表分为已排序部分和待排序部分每次从待排序部分拿一个结点插入已排序部分的合理位置插入时进行两次判断时间复杂度O(n^2)和数组直接插入排序一样适合数据量不大的情况void sort_link_insert(Link_t*plink) { if((is_empty_link(plink)) || 1 plink-len) { return ; } Node_t*pinsert NULL; Node_t*ptmp plink-phead-pnext; plink-phead-pnext NULL; while(ptmp!NULL) { pinsert ptmp; ptmp ptmp-pnext; if(plink-phead-data pinsert-data) { pinsert-pnext plink-phead; plink-phead pinsert; } else { Node_t*p plink-phead; while(p-pnext!NULL p-pnext-data pinsert-data) { p p-pnext; } pinsert-pnext p-pnext; p-pnext pinsert; } } }判断链表是否有环利用快慢指针法如果链表有环快指针一定会在环内追上慢指针就行操场跑步快的人最终会套圈追上慢的人如果没有环快指针会先走到链表末尾的NULLint is_loop_link(Link_t*plink) { Node_t*pfast plink-phead; Node_t*pslow pfast; while(pfast!NULL) { pfast pfast-pnext; if(NULL pfast) { return 0; } pfast pfast-pnext; pslow pslow-pnext; if(pfast pslow) { return 1; } } return 0; }双向链表创建双向链表对象结构体包含链表头结点地址链表长度typedef struct dlink { Dnode_t*phead; int clen; }DLink_t;创建双向链表结点结构体包含双向链表存储的值指向前驱结点的指针指向后继结点的指针typedef struct dnode { Datatype_t data; struct dnode *ppre;//指向前驱结点的指针 struct dnode *pnext;//指向后继结点的指针 }Dnode_t;双向链表头插创建新结点调用create_node函数并判断是否调用成功进行是否为空链表判断链表为空直接把链表头指针指向新结点不为空新结点的next指向原头结点原头结点指向新结点链表头指针更新为新结点链表长度1int insert_doublelink_head(DLink_t*pdlink,Datatype_t data) { Dnode_t*pnode create_node(data); if(NULL pnode) { return -1; } if(is_empty_dlink(pdlink)) { pdlink-phead pnode; } else { pnode-pnext pdlink-phead; pdlink-phead-ppre pnode; pdlink-phead pnode; } pdlink-clen; return 0; }双向链表尾插创建新结点调用create_node函数并判断是否调用成功进行是否为空链表判断为空把链表头指针指向新结点不为空定义局部变量结点指针指向链表头结点寻找尾结点新结点的指向前驱结点的指针指向尾结点尾结点的指向后继结点的指针指向新结点。链表长度1int insert_doublelink_tail(DLink_t*pdlink,Datatype_t data) { Dnode_t*pnode create_node(data); if(NULL pnode) { return -1; } Dnode_t*p pdlink-phead; if(is_empty_dlink(pdlink)) { pdlink-phead pnode; } else { while(p-pnext!NULL) { p p-pnext; } pnode-ppre p; pnode-pnext NULL; p-pnext pnode; } pdlink-clen; return 0; }双向链表头删头删进行链表是否为空判断定义局部变量指针指向头结点保存原头结点方便后续释放更新原链表头指针指向原头结点的下一个结点如果删除后头结点不是NULL说明链表还有其他结点把新头结点的前驱指针置空与原头结点断开释放被删除的头结点链表在堆内存申请删除要释放空间链表长度-1int delete_dlink_head(DLink_t*pdlink) { if(is_empty_dlink(pdlink)) { return -1; } Dnode_t*ptmp pdlink-phead; pdlink-phead ptmp-pnext; if(ptmp-pnext!NULL) { ptmp-pnext-ppre NULL; } free(ptmp); pdlink-clen--; return 0; }双向链表尾删尾删进行链表是否为空判断定义局部变量结点指针指向链表头结点借助循环寻找尾结点要被删除的结点如果删除后尾结点的前驱指针指向不为空说明链表不是只有一个结点将尾结点的前一个结点的后继指针置空即断开尾结点和尾结点的上一个结点如果删除后尾结点的前驱指针指向为空说明链表是只有一个结点将链表的头指针置空即断开链表的唯一一个结点释放被删除的尾结点链表在堆内存申请删除要释放空间链表长度-1int delete_dlink_tail(DLink_t*pdlink) { if(is_empty_dlink(pdlink)) { return -1; } Dnode_t*ptmp pdlink-phead; while(ptmp-pnext ! NULL) { ptmp ptmp-pnext; } if(ptmp-ppre ! NULL) { ptmp-ppre-pnext NULL; } else { pdlink-phead NULL; } free(ptmp); pdlink-clen--; return 0; }双向链表遍历传入链表对象指针参数遍历方向参数进行是否为空链表判断不为空定义局部遍历指针将链表头指针赋值给其让其指向头结点如果方向为从左向右从头结点开始循环遍历输出结点内容循环体为指针每次更新为指向下一个结点如果方向为从右向左寻找尾节点从尾结点开始循环遍历输出结点内容指针每次更新为指向上一个结点void show_doublelink(DLink_t*pdlink,int dir) { if(is_empty_dlink(pdlink)) { return; } Dnode_t*ptmp pdlink-phead; if(dir) { while(ptmp) { printf(%d %s %d\n,ptmp-data.id,ptmp-data.name,ptmp-data.score); ptmp ptmp-pnext; } } else { while(ptmp-pnext) { ptmp ptmp-pnext; } while(ptmp) { printf(%d %s %d\n,ptmp-data.id,ptmp-data.name,ptmp-data.score);; ptmp ptmp-ppre; } } }查找双向链表根据值修改链表返回结点指针的函数传入查找的数据定义局部变量指向头结点从头结点开时以传入的数据为条件循环查找结点返回找到结点的指针修改链表函数调用查找函数进行数据修改。Dnode_t*find_node(DLink_t*pdlink,char*name) { Dnode_t*ptmp pdlink-phead; while(ptmp!NULL) { if(0 strcmp(ptmp-data.name,name)) { return ptmp; } ptmp ptmp-pnext; } return NULL; } int change_data(DLink_t*pdlink,char*name,int score) { Dnode_t*ptmp NULL; ptmp find_node(pdlink, name); if(ptmp!NULL) { ptmp-data.score score; return 0; } return -1; }销毁双向链表进行是否为空链表判断不为空定义局部变量结点指针指向链表头结点调用头删函数循环进行逐个删除最后是否链表对象指针即是否头结点空间void destory_dlink(DLink_t*pdlink) { if(is_empty_dlink(pdlink)) { return; } Dnode_t*p pdlink-phead; while(p-pnext!NULL) { p p-pnext; delete_dlink_head(pdlink); } free(pdlink); }

数据结构单向链表应用双向链表

相关推荐

FluentRead 文档翻译实战指南：从本地文件批量导入到双语对照、校订与保真导出

网页设计公司哪家值得推荐最佳实践

2026最新设计大型网站建设避坑指南

更多资讯

Enhancing Japanese Large Language Models with Reasoning Vectors

STM32+Air780E+OLED：按键触发中文短信发送终端实战

STM32+Air780E短信发送终端：按键触发与OLED状态显示实战

求个网站或者app源码下载

strands-agents Python SDK v1.32.0 发布解读：事件循环 OTel 指标补全、Mistral 依赖上界与双向流式 stop reason 修复

Program-as-Weights: A Programming Paradigm for Fuzzy Functions

今日更新

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？