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;
}
程序的运行结果如下图：
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持小牛知识库。
-
NowCoder 题目描述 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的 head。 // java public class RandomListNode { int label; RandomListNode next = null; RandomListNode random =
-
一、题目 请实现函数ComplexListNode clone(ComplexListNode head),复制一个复杂链表。在复杂链表中，每个结点除了有一个next 域指向下一个结点外，还有一个sibling 指向链表中的任意结点或者null。 二、解题思路 在不用辅助空间的情况下实现O(n)的时间效率。 第一步：仍然是根据原始链表的每个结点N 创建对应的N’。把N’链接在N的后面。 第二步：设
-
我需要制作一个可以进行三次操作的链表。所有这三个操作都必须具有 O（1） 复杂性。 有问题的操作是： < li >添加到尾部 < li >从头部移除 < li >返回中间节点 正在使用的节点结构如下： 为了移除头部，我通过通常对头部节点的引用实现了O(1) 为了添加到尾，我通过引用尾节点实现了O（1） 我的问题是返回中间节点。我知道如何通过遍历列表来实现这一点，但这意味着它将具有O（n）复杂度。我
-
本文向大家介绍C语言之双向链表详解及实例代码，包括了C语言之双向链表详解及实例代码的使用技巧和注意事项，需要的朋友参考一下 1，双向链表简介。 双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。 2，例子要求： 完成双向链表的插入、删除以及查找，将
-
有人知道为什么这个循环总是针对不同于1或0的值，以及如何避免在输入字符时出现无休止的循环吗？ }
-
本文向大家介绍C语言流程控制之switch语句详解，包括了C语言流程控制之switch语句详解的使用技巧和注意事项，需要的朋友参考一下 switch语句结构 表达式是选择条件，可以是单个变量也可以是组合的表达式，其最终的结果必须是一整数值，{}内的所有内容是switch语句的主体，内含多个case分支，判断值必须是一常量，case分支根据判断值标识条件选择的入口；break语句用于退出switch