C语言之复杂链表的复制方法(图示详解)
什么是复杂链表?
复杂链表指的是一个链表有若干个结点,每个结点有一个数据域用于存放数据,还有两个指针域,其中一个指向下一个节点,还有一个随机指向当前复杂链表中的任意一个节点或者是一个空结点。今天我们要实现的就是对这样一个复杂链表复制产生一个新的复杂链表。
复杂链表的数据结构如下:
typedef int DataType; //数据域的类型 //复杂链表的数据结构 typedef struct ComplexNode { DataType _data ; // 数据 struct ComplexNode * _next; // 指向下个节点的指针 struct ComplexNode * _random; // 指向随机节点(可以是链表中的任意节点 or 空) }ComplexNode;
上图就是一个复杂链表的例子,那么我们应该如何实现复杂链表的复制呢?
1、首先我们应该根据已有的复杂链表创建一条新的复杂链表,但是这个新的复杂链表的所有的结点的random指针都指向空,这样是很好实现的,相当于我们创建了一条简单的单链表(newlist),我们要复制的链表不妨称之为oldlist。
2、接下来我们应该把新创建的这条复杂链表(newlist)与已有的复杂链表(oldlist)合并成如下的形式:
在这种情况下我们已经把两条复杂链表合并成了一条链表(称之为linklist),通过对这条链表(linklist)的观察,我们可以发现合并的链表(linklist)中属于newlist的结点pnew的上一个结点pold(属于oldlist的结点)的random指针所指向的结点的next指针就应该是pnew结点的randow指针所指向的结点。
这样我们让pold和pnew指针一直往后走最后就可以实现对所有属于新创建的复杂链表(newlist)的random指针指向相应的结点的操作。构成的复杂链表如下图
在完成以上的步骤之后我们所要做的工作就很简单了,我们只要把这一条链表linklist分开成我们的newlist链表和oldlist链表就可以了。
这样我们就完美的完成了复杂链表的复制工作下面就是具体实现的代码:
头文件complexnode.h:
#ifndef __COMPLEX__NODE__H__ #define __COMPLEX__NODE__H__ //包含头文件 #include <stdio.h> #include<stdlib.h> #include <assert.h> typedef int DataType; //数据域的类型 //复杂链表的数据结构 typedef struct ComplexNode { DataType _data ; // 数据 struct ComplexNode * _next; // 指向下个节点的指针 struct ComplexNode * _random; // 指向随机节点(可以是链表中的任意节点 or 空) }ComplexNode; //创建一个复杂链表的结点 ComplexNode * BuyComplexNode(DataType x); //打印复杂的单链表 void Display(const ComplexNode * cplist); //复杂链表的复制 ComplexNode * CopyComplexNode(ComplexNode * cplist); #endif//__COMPLEX__NODE__H__
具体功能实现complexnode.c
#include "complexnode.h" //创建一个复杂链表的结点 ComplexNode * BuyComplexNode(DataType x) { ComplexNode *cnode = (ComplexNode *)malloc(sizeof(ComplexNode)); if(cnode == NULL)//创建失败 { perror("BuyComplexNode()::malloc"); return NULL; } //创建成功 cnode->_data = x; cnode->_next = NULL; cnode->_random = NULL; return cnode; } //打印复杂的单链表 void Display(const ComplexNode * cplist) { ComplexNode *pnode = cplist; while (pnode) { printf("%d::%d -->",pnode->_data,pnode->_random->_data); pnode = pnode->_next; } printf("over\n"); } //复杂链表的复制 ComplexNode * CopyComplexNode(ComplexNode * cplist) { ComplexNode * pold = NULL; ComplexNode * pnew = NULL; ComplexNode * newlist = NULL;//指向新的复杂链表的头结点的指针 pold = cplist; //创建一条新的复杂链表 while(pold != NULL) { ComplexNode * new_node = BuyComplexNode(pold->_data); if(newlist == NULL)//当新的复杂链表中没有结点时 { newlist = new_node; } else//当新的复杂链表有结点时 { ComplexNode * node = newlist; while(node->_next != NULL)//找到最后一个结点 { node = node->_next; } node->_next = new_node;//插入新的结点 } pold = pold->_next; }//创建新的复杂链表结束 //合并两条复杂链表 pold = cplist; pnew = newlist; while (pold) { ComplexNode * curold = NULL; ComplexNode * curnew = NULL; curold = pold->_next; curnew = pnew->_next; if(pold->_next == NULL) { pold->_next = pnew; pold = curold; pnew = curnew; break; } pold->_next = pnew; pnew->_next = curold; pold = curold; pnew = curnew; }//合并两条复杂链表结束 //让新创建的那条复杂链表上的所有结点的random指针指向相应的结点 pold = cplist; pnew = newlist; while (pnew) { pnew->_random = pold->_random->_next; pold = pnew->_next; if(pold == NULL)//这是pnew的_next指针已经指向空 { break; } pnew = pold->_next; }//结束 //分离合并后的复杂链表 pold = cplist; pnew = newlist; while (pold) { ComplexNode * curold = NULL; ComplexNode * curnew = NULL; if(pnew->_next == NULL)//已经分离完成 { pold->_next = NULL; pnew->_next = NULL; break; } curold = pold->_next->_next; curnew = pnew->_next->_next; pold->_next = curold; pnew->_next = curnew; pold = curold; pnew = curnew; }//分离合并的复杂链表结束 return newlist; }
测试代码test.c:
#include "complexnode.h" // //复杂链表的复制。?个链表的每个节点,有?个指向next指针指向下?个节 //点,还有?个random指针指向这个链表中的?个随机节点或者NULL,现在要 //求实现复制这个链表,返回复制后的新链表。 //ps: 复杂链表的结构 void test() { ComplexNode * cplist; ComplexNode * copylist; ComplexNode * node1; ComplexNode * node2; ComplexNode * node3; ComplexNode * node4; cplist = BuyComplexNode(1); node1 = BuyComplexNode(2); node2 = BuyComplexNode(3); node3 = BuyComplexNode(4); node4 = BuyComplexNode(5); cplist->_next = node1; node1->_next = node2; node2->_next = node3; node3->_next = node4; cplist->_random = node3; node1->_random = node4; node2->_random = cplist; node3->_random = node1; node4->_random = node2; Display(cplist); copylist = CopyComplexNode(cplist); Display(copylist); } int main() { test(); return 0; }
程序的运行结果如下图:
以上这篇C语言之复杂链表的复制方法(图示详解)就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持猪先飞。
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- 某些时候,例如为了搭建一个测试环境,或者克隆一个网站,需要复制一个已存在的mysql数据库。使用以下方法,可以非常简单地实现。假设已经存在的数据库名字叫db1,想要复制一份,命名为newdb。步骤如下:1. 首先创建新的数据库newd...2015-10-21
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C# 复制与删除文件的实现方法的相关资料,希望通过本文能帮助到大家,让大家理解掌握这部分内容,需要的朋友可以参考下...2020-06-25
JavaScript深度复制(deep clone)的实现方法
本文给大家介绍JavaScript深度复制(deep clone)的实现方法,涉及到js深度复制相关知识,本文介绍的非常详细,特此分享脚本之家平台供大家参考...2016-02-21percona-toolkit对MySQL的复制和监控类操作教程
复制类工具 1. pt-heartbeat 功能介绍: 监控mysql复制延迟 用法介绍: pt-heartbeat [OPTION...] [DSN] --update|--monitor|--check|--stop 测量复制落后主mysql或者主PostgreSQL多少时间,你可以使用这个脚本去更新主或...2015-11-24- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C#中数组初始化与数组元素复制的方法,涉及C#中数组的创建、初始化及使用Array.Copy方法复制数组元素的技巧,需要的朋友可以参考下...2020-06-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
mysql(master/slave)主从复制原理及配置图文详解
这篇文章主要介绍了mysql(masterslave)主从复制原理及配置图文详解,以前脚本之家小编发过相关的内容,但这么好的非常少见特分享一下,需要的朋友可以参考下...2016-06-12- 采用全库复制的方案,方便管理mysql 5.5 + rhel5.810.4.11.12 master10.4.11.13 slave---Master端设置1, 创建复制帐号,需要复制和slave权限mysql> GRANT REPLICATION SLAVE, REPLICATION CLIENT ON *.* TO repl@'10....2013-10-04
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25