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语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- 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语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 本文给大家简单介绍下c实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25
- 这篇文章主要介绍了python无序链表删除重复项的方法,本文给大家介绍的非常详细,具体一定的参考借鉴价值,需要的朋友可以参考下...2020-04-27
- 这篇文章主要介绍了c语言实现找最大值最小值位置查找,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-04