文章目录一、单向链表的使用与进阶练习1.1 单向链表中间结点的查找1.2 单向链表倒数K个结点的查找1.3 删除单向链表中的某个值1.4 单向链表逆序1.5 单向链表排序1.6 单向链表的环状链表1.6.1 创建环状链表1.6.2 判断是否为环状链表1.6.3 找出环状链表的入口1.6.4 环状链表的长度1.6.5 约瑟夫环链表二、双向链表2.1 双向链表的创建2.2 双向链表结点的插入2.3 双向链表的遍历2.4 双向链表结点的删除2.5 双向链表结点的查找2.6 双向链表结点的修改2.7 双向链表结点的销毁三、内核链表在上篇文章【数据结构学习1】数据结构基本概念及单向链表初步了解数据结构的概念和单向链表的基本操作之后这篇文章主要是对单向链表的进一步学习与巩固并在此基础上对双向链表及内核链表进行学习。一、单向链表的使用与进阶练习1.1 单向链表中间结点的查找以我们昨天创建的链表为例来看看这段代码Node*find_midnode(Link*plink){if(is_empty_link(plink)){returnNULL;}Node*midnode_addrplink-phead;intcnt0;while(cnt!plink-clen/2){midnode_addrmidnode_addr-pnext;cnt;}returnmidnode_addr;}通过定义一个计数变量cnt遍历找到cnt clen/2的结点返回其地址。这个做法有极大的局限性一定需要clen这个链表长度参数在某些情况下我们是没有clen这个参数的若通过遍历来求时间复杂度就会特别大。还有没有别的方法呢这里就要引入快慢指针法了。快慢指针法通过不同的指针移动速度或不同的开始位置由此来对链表中的数据进行操作可以大大减少代码的时间复杂度。来看下面这段代码Node*find_midnode_fs(Link*plink){Node*pfastplink-phead;Node*pslowpfast;while(pfast!NULL){pfastpfast-pnext;if(pfastNULL){break;}pfastpfast-pnext;pslowpslow-pnext;}returnpslow;}我们可以借助上面这张图帮助理解当慢指针向后移动一个结点时快指针就向后移动了两个结点。由此我们就制造一个循环当快指针指向的结点的指针域为NULL时循环停止此时慢指针刚好指在了链表长度的一半即指向了链表的中间结点。1.2 单向链表倒数K个结点的查找上篇文章是在链表中查找一个值已知值查看有没有这个是在链表中的一个位置读取值已知位置不知值大家不要混淆咯查找倒数K个结点我们依然用到快慢指针法在查找中间结点中我们借助速度的不同来实现查找在这次K点的查找中我们将借助开始位置的不同来实现。来看代码Node*find_k_node(Link*plink,intk){if(kplink-clen){returnNULL;}Node*pfastplink-phead;Node*pslowpfast;for(inti0;ik;i){//if(pfast NULL)return NULL;pfastpfast-pnext;}while(pfast!NULL){pfastpfast-pnext;pslowpslow-pnext;}returnpslow;}当快指针移动到最后一个结点时慢指针刚好与快结点的距离为K。1.3 删除单向链表中的某个值intdel_data_link(Link*plink,intdata){if(is_empty_link(plink)){return-1;}Node*ptmpplink-phead;Node*ptmp_lastptmp;if(ptmp-datadata){del_head_link(plink);return0;}ptmpptmp-pnext;while(ptmp){if(ptmp-datadata){ptmp_last-pnextptmp-pnext;free(ptmp);return0;}ptmpptmp-pnext;ptmp_lastptmp_last-pnext;}return-1;}接收链表指针与目标数据先判断链表是否为空为空则返回‑1接着检查头结点是否为待删元素若是调用删头函数完成删除否则使用双指针从第二个结点开始向后遍历链表找到第一个数据匹配的结点后修改前驱结点的后继指针、释放当前结点内存并返回 0遍历结束未找到目标元素则返回‑1。1.4 单向链表逆序voidreverse_link(Link*plink){if(is_empty_link(plink)1||plink-phead-pnextNULL){return;}Node*pinsertplink-phead;Node*ptmppinsert-pnext;plink-phead-pnextNULL;while(ptmp){pinsertptmp;ptmpptmp-pnext;pinsert-pnextplink-phead;plink-pheadpinsert;}}先判断链表为空或仅有一个结点时直接结束定义pinsert指向原头结点、ptmp指向其后继结点并将原头结点的后继置为空随后进入循环不断取出ptmp所指结点先更新pinsert为当前ptmp结点、ptmp向后移动至下一结点再将pinsert结点指向当前链表头部最后更新链表头指针为pinsert循环直至所有结点完成头插实现链表整体反转。1.5 单向链表排序voidsort_link(Link*plink){if(is_empty_link(plink)1||plink-phead-pnextNULL){return;}Node*pinsertplink-phead;Node*ptmppinsert-pnext;plink-phead-pnextNULL;Node*ptemp_linkNULL;while(ptmp!NULL){pinsertptmp;ptmpptmp-pnext;if(pinsert-dataplink-phead-data){pinsert-pnextplink-phead;plink-pheadpinsert;}else{ptemp_linkplink-phead;while(ptemp_link-pnext!NULLptemp_link-pnext-datapinsert-data){ptemp_linkptemp_link-pnext;}pinsert-pnextptemp_link-pnext;ptemp_link-pnextpinsert;}}return;}先判断链表为空或仅有一个结点则直接返回将原链表第一个结点取出作为有序链表初始节点随后循环依次摘下剩余待排序结点若当前结点数据小于等于有序链表头结点则采用头插法插入链表头部否则遍历有序链表找到第一个大于当前结点的位置将结点插入该位置之前直至所有结点完成插入最终得到升序排列的单链表。1.6 单向链表的环状链表1.6.1 创建环状链表将最后一个结点的指针域修改为前面某个结点的地址这样就可以形成一个环状结点。下面代码以指向头结点为例voidlink_loop(Link*plink){if(is_empty_link(plink)){returnNULL;}Node*ptmpplink-phead;while(ptmp-pnext){ptmpptmp-pnext;}ptmp-pnextplink-phead;}1.6.2 判断是否为环状链表intis_loop_link(Link_t*plink){Node_t*pfastplink-phead;Node_t*pslowpfast;while(pfast!NULL){pfastpfast-pnext;if(NULLpfast){return0;}if(pfastpslow){return1;}pfastpfast-pnext;pslowpslow-pnext;if(pfastpslow){return1;}}return0;}1.6.3 找出环状链表的入口Node_t*get_loop_enter(Link_t*plink){if(NULLplink-phead){returnNULL;}Node_t*pfastplink-phead;Node_t*pslowpfast;while(1){pfastpfast-pnext;if(pfastpslow){break;}pfastpfast-pnext;pslowpslow-pnext;if(pfastpslow){break;}}pslowplink-phead;pfastpfast-pnext;while(pslow!pfast){pfastpfast-pnext;pslowpslow-pnext;}returnpslow;}1.6.4 环状链表的长度1.6.5 约瑟夫环链表Node_t*Josep_loop(Link_t*plink){Node_t*pprevplink-phead;Node_t*pfreepprev;while(plink-clen1){pfreepfree-pnext-pnext;pprevpprev-pnext;pprev-pnextpfree-pnext;free(pfree);plink-clen--;pfreepprev-pnext;pprevpfree;}returnpprev;}二、双向链表2.1 双向链表的创建与单向链表的方法基本相同唯一不同的点在与双向链表的结点具有两个指针域一个指向前结点一个指向后结点。因此后续的相关操作就与单向链表没有什么区别了。Dlink*creat_dlink(){Dlink*pdlinkmalloc(sizeof(Dlink));if(pdlinkNULL){printf(malloc error!\n);return0;}pdlink-pheadNULL;pdlink-clen0;returnpdlink;}2.2 双向链表结点的插入头插函数传入双向链表头指针与待插入的数据先调用malloc创建一个新结点若内存分配失败则打印错误信息并返回随后给新结点填充数据前驱、后继指针初始化为空若链表为空则直接将新结点作为链表头结点链表不为空时把原头结点的前驱指针指向新结点、新结点后继指向原头结点再更新链表头指针至新结点最后链表长度计数器加一函数返回 0。int*insert_head_dlink(Dlink*pdlink,Data data){Dnode*pinsertmalloc(sizeof(Dnode));if(pinsertNULL){printf(malloc error!\n);return0;}pinsert-datadata;pinsert-pnextNULL;pinsert-ppreNULL;if(is_empty_dlink(pdlink)){pdlink-pheadpinsert;}else{pdlink-phead-pprepinsert;pinsert-pnextpdlink-phead;pdlink-pheadpinsert;}pdlink-clen;return0;}尾插首先动态开辟一个新结点内存分配失败则打印错误并返回 0给新结点赋值数据前驱、后继指针置空若链表为空直接将新结点设为头结点不为空则从头结点开始循环遍历找到链表最后一个结点将尾结点的后继指针指向新结点链表长度计数器自增完成尾部插入并返回 0。intinsert_end_dlink(Dlink*pdlink,Data data){Dnode*pinsertmalloc(sizeof(Dnode));if(pinsertNULL){printf(malloc error!\n);return0;}pinsert-datadata;pinsert-pnextNULL;pinsert-ppreNULL;if(is_empty_dlink(pdlink)){pdlink-pheadpinsert;return0;}Dnode*ptmppdlink-phead;while(ptmp-pnext){ptmpptmp-pnext;}ptmp-pnextpinsert;pdlink-clen;return0;}2.3 双向链表的遍历传入链表头指针与方向标识参数 dir首先判断链表是否为空为空则返回‑1dir 非零时从表头出发顺着后继指针正向遍历输出每个结点内姓名、年龄、分数的数据dir 为零时先遍历找到链表尾结点再沿着前驱指针反向遍历输出结点数据打印结束后换行并返回 0。intpr_dlink(Dlink*pdlink,intdir){if(is_empty_dlink(pdlink)){return-1;}Dnode*ptmppdlink-phead;if(dir){while(ptmp){printf(%s %d %d\n,ptmp-data.name,ptmp-data.age,ptmp-data.score);ptmpptmp-pnext;}}else{while(ptmp-pnext){ptmpptmp-pnext;}while(ptmp){printf(%s %d %d\n,ptmp-data.name,ptmp-data.age,ptmp-data.score);ptmpptmp-ppre;}}printf(\n);return0;}2.4 双向链表结点的删除头删传入链表头指针先判断链表是否为空为空则返回‑1保存当前头结点地址将链表头指针更新为原头结点的下一个结点若新的头结点不为空则将其前驱指针置空释放被删除结点的内存空间链表长度计数器减一删除成功后返回 0。intdel_head_dlink(Dlink*pdlink){if(is_empty_dlink(pdlink)){return-1;}Dnode*ptmppdlink-phead;pdlink-pheadptmp-pnext;if(pdlink-phead!NULL){pdlink-phead-ppreNULL;}free(ptmp);pdlink-clen--;return0;}尾删传入链表头指针首先判断链表是否为空为空返回‑1若链表仅存在单个结点则将链表头指针置空、释放结点内存并结束结点数量大于一时循环遍历找到尾结点修改尾结点前驱结点的后继指针为空释放尾结点占用的内存链表长度计数器减一删除完成后返回 0。intdel_end_dlink(Dlink*pdlink){if(is_empty_dlink(pdlink)){return-1;}Dnode*ptmppdlink-phead;if(ptmp-pnextNULL){pdlink-pheadNULL;free(ptmp);return0;}while(ptmp-pnext){ptmpptmp-pnext;}ptmp-ppre-pnextNULL;free(ptmp);pdlink-clen--;return0;}2.5 双向链表结点的查找传入链表头指针与待比对的 Data 结构体先判断链表是否为空为空直接返回空指针从表头开始顺着后继指针依次遍历每一个结点同时比对结点与目标数据的姓名、年龄、分数三项内容全部相等则返回当前匹配结点的地址遍历结束未找到匹配结点则返回 NULL。Dnode*find_data_dlink(Dlink*pdlink,Data data){if(is_empty_dlink(pdlink)){return0;}Dnode*ptmppdlink-phead;while(ptmp){if(strcmp(data.name,ptmp-data.name)0data.ageptmp-data.agedata.scoreptmp-data.score){returnptmp;}ptmpptmp-pnext;}returnNULL;}2.6 双向链表结点的修改传入链表头指针、原始查找数据src和新数据des调用查找函数根据src完整匹配目标结点若未找到对应结点返回‑1查找成功后将结点内姓名、年龄、分数更新为新的数据修改完成返回 0。intmodify_dnode(Dlink*pdlink,Data src,Data des){Dnode*psrcfind_data_dlink(pdlink,src);if(psrcNULL){return-1;}strcpy(psrc-data.name,des.name);psrc-data.agedes.age;psrc-data.scoredes.score;return0;}2.7 双向链表结点的销毁循环调用头删函数不断删除链表结点直至链表为空释放完所有数据结点后再释放链表管理结构体pdlink所占内存完成链表的彻底销毁最后返回 0表示销毁成功。intdestroy_dlink(Dlink*pdlink){while(!is_empty_dlink(pdlink)){del_head_dlink(pdlink);}free(pdlink);return0;}三、内核链表Linux内核中使用到的一种链表形式。本质:双向循环链表和普通链表得区别:1. 普通链表将数据存储在结点中程序中一点确定了结点中存储得数据得数据类型该链表再无法存储其他类型的数据。2. 内核链表将结点嵌入到要存储的数据结构体中在项目工程中一套链表操作可以用来存储不同类型的数据。内核提供宏:offsetof:获取链表结点首地址到结构体开头的偏移量。container_of:利用结点的首地址-偏移量获得结构体首地址。