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

单向链表应用查找结点 传统遍历结点返回结构体指针函数传入链表对象结构体指针查找结点的位置进行是否为空链表判断 进行传入的参数位置是否合理定义局部变量指针来指向查找结点 有循环跳出条件采用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); }