C语言之复杂链表的复制方法(图示详解)_网络技术

C语言之复杂链表的复制方法(图示详解)

发布时间 - 2026-01-11 02:09:53 点击率：次

什么是复杂链表？

复杂链表指的是一个链表有若干个结点，每个结点有一个数据域用于存放数据，还有两个指针域，其中一个指向下一个节点，还有一个随机指向当前复杂链表中的任意一个节点或者是一个空结点。今天我们要实现的就是对这样一个复杂链表复制产生一个新的复杂链表。

复杂链表的数据结构如下：

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语言之复杂链表的复制详解 # C语言数据结构之复杂链表的拷贝 # C语言复杂链表的复制实例详解 # 链表 # 数据结构 # 两条 # 我们应该 # 这条 # 给大家 # 下个 # 创建一个 # 如下图 # 就可以 # 称之为 # 是一个 # 这是 # 头文件 # 这一 # 很好 # 成了 # 要把 # 我们可以 # 希望能

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】

上一篇：CentOS Minimal如何管理用户权限

下一篇：西安网页设计趋势：创意与技术的完美融合

相关栏目网站优化
网络推广
网络技术
AI营销

最新文章 Sublime怎么一键压缩JS代码 Su sublime如何在搜索中使用正则表达式 Sublime如何设置透明窗口效果 Su mysql如何设计商品表结构_mysql css属性背景图不显示怎么办_通过检查路如何使用Golang实现排序_Golan 农历闰月是怎么回事_为合回归年加一月调整塑造《刺客信条》艾吉奥传奇的编剧离开育碧 1英里等于多少公里 1mile和km的换 css grid布局中行和列是如何定义的 PS批量旋转和翻转图片，快速校正图片方向 C# Swagger UI自定义方法 C OPPO手机九宫格和全键盘怎么切换_OP Go语言如何实现用户登录注册_Golan 1节飞行速度多少公里每小时 1节是多少公纸嫁衣8千子树第五章庙门怎么开启庙门 Laravel 多行数据编辑表单中实现逐明日之后如何提升钓鱼等级明日之后提升钓支付宝怎样查年度账单_支付宝年度账单查看 C# 多线程UI更新Dispatcher

上一篇：CentOS Minimal如何管理用户权限

下一篇：西安网页设计趋势：创意与技术的完美融合