C語言之復(fù)雜鏈表的復(fù)制詳解
什么是復(fù)雜鏈表？
復(fù)雜鏈表指的是一個鏈表有若干個結(jié)點(diǎn)，每個結(jié)點(diǎn)有一個數(shù)據(jù)域用于存放數(shù)據(jù)，還有兩個指針域，其中一個指向下一個節(jié)點(diǎn)，還有一個隨機(jī)指向當(dāng)前復(fù)雜鏈表中的任意一個節(jié)點(diǎn)或者是一個空結(jié)點(diǎn)。今天我們要實(shí)現(xiàn)的就是對這樣一個復(fù)雜鏈表復(fù)制產(chǎn)生一個新的復(fù)雜鏈表。
復(fù)雜鏈表的數(shù)據(jù)結(jié)構(gòu)如下：
typedef int DataType; //數(shù)據(jù)域的類型
//復(fù)雜鏈表的數(shù)據(jù)結(jié)構(gòu)
typedef struct ComplexNode
{
DataType _data ; // 數(shù)據(jù)
struct ComplexNode * _next; // 指向下個節(jié)點(diǎn)的指針
struct ComplexNode * _random; // 指向隨機(jī)節(jié)點(diǎn)（可以是鏈表中的任意節(jié)點(diǎn) or 空）
}ComplexNode;
上圖就是一個復(fù)雜鏈表的例子，那么我們應(yīng)該如何實(shí)現(xiàn)復(fù)雜鏈表的復(fù)制呢？
1、首先我們應(yīng)該根據(jù)已有的復(fù)雜鏈表創(chuàng)建一條新的復(fù)雜鏈表，但是這個新的復(fù)雜鏈表的所有的結(jié)點(diǎn)的random指針都指向空，這樣是很好實(shí)現(xiàn)的，相當(dāng)于我們創(chuàng)建了一條簡單的單鏈表（newlist），我們要復(fù)制的鏈表不妨稱之為oldlist。
2、接下來我們應(yīng)該把新創(chuàng)建的這條復(fù)雜鏈表（newlist）與已有的復(fù)雜鏈表（oldlist）合并成如下的形式：
在這種情況下我們已經(jīng)把兩條復(fù)雜鏈表合并成了一條鏈表（稱之為linklist），通過對這條鏈表（linklist）的觀察，我們可以發(fā)現(xiàn)合并的鏈表（linklist）中屬于newlist的結(jié)點(diǎn)pnew的上一個結(jié)點(diǎn)pold（屬于oldlist的結(jié)點(diǎn)）的random指針?biāo)赶虻慕Y(jié)點(diǎn)的next指針就應(yīng)該是pnew結(jié)點(diǎn)的randow指針?biāo)赶虻慕Y(jié)點(diǎn)。
這樣我們讓pold和pnew指針一直往后走最后就可以實(shí)現(xiàn)對所有屬于新創(chuàng)建的復(fù)雜鏈表（newlist）的random指針指向相應(yīng)的結(jié)點(diǎn)的操作。構(gòu)成的復(fù)雜鏈表如下圖
在完成以上的步驟之后我們所要做的工作就很簡單了，我們只要把這一條鏈表linklist分開成我們的newlist鏈表和oldlist鏈表就可以了。
這樣我們就完美的完成了復(fù)雜鏈表的復(fù)制工作下面就是具體實(shí)現(xiàn)的代碼：
頭文件complexnode.h：
#ifndef __COMPLEX__NODE__H__
#define __COMPLEX__NODE__H__
//包含頭文件
#include <stdio.h>
#include<stdlib.h>
#include <assert.h>
typedef int DataType; //數(shù)據(jù)域的類型
//復(fù)雜鏈表的數(shù)據(jù)結(jié)構(gòu)
typedef struct ComplexNode
{
DataType _data ; // 數(shù)據(jù)
struct ComplexNode * _next; // 指向下個節(jié)點(diǎn)的指針
struct ComplexNode * _random; // 指向隨機(jī)節(jié)點(diǎn)（可以是鏈表中的任意節(jié)點(diǎn) or 空）
}ComplexNode;
//創(chuàng)建一個復(fù)雜鏈表的結(jié)點(diǎn)
ComplexNode * BuyComplexNode(DataType x);
//打印復(fù)雜的單鏈表
void Display(const ComplexNode * cplist);
//復(fù)雜鏈表的復(fù)制
ComplexNode * CopyComplexNode(ComplexNode * cplist);
#endif//__COMPLEX__NODE__H__
具體功能實(shí)現(xiàn)complexnode.c
#include "complexnode.h"
//創(chuàng)建一個復(fù)雜鏈表的結(jié)點(diǎn)
ComplexNode * BuyComplexNode(DataType x)
{
ComplexNode *cnode = (ComplexNode *)malloc(sizeof(ComplexNode));
if(cnode == NULL)//創(chuàng)建失敗
{
perror("BuyComplexNode()::malloc");
return NULL;
}
//創(chuàng)建成功
cnode->_data = x;
cnode->_next = NULL;
cnode->_random = NULL;
return cnode;
}
//打印復(fù)雜的單鏈表
void Display(const ComplexNode * cplist)
{
ComplexNode *pnode = cplist;
while (pnode)
{
printf("%d::%d -->",pnode->_data,pnode->_random->_data);
pnode = pnode->_next;
}
printf("over\n");
}
//復(fù)雜鏈表的復(fù)制
ComplexNode * CopyComplexNode(ComplexNode * cplist)
{
ComplexNode * pold = NULL;
ComplexNode * pnew = NULL;
ComplexNode * newlist = NULL;//指向新的復(fù)雜鏈表的頭結(jié)點(diǎn)的指針
pold = cplist;
//創(chuàng)建一條新的復(fù)雜鏈表
while(pold != NULL)
{
ComplexNode * new_node = BuyComplexNode(pold->_data);
if(newlist == NULL)//當(dāng)新的復(fù)雜鏈表中沒有結(jié)點(diǎn)時
{
newlist = new_node;
}
else//當(dāng)新的復(fù)雜鏈表有結(jié)點(diǎn)時
{
ComplexNode * node = newlist;
while(node->_next != NULL)//找到最后一個結(jié)點(diǎn)
{
node = node->_next;
}
node->_next = new_node;//插入新的結(jié)點(diǎn)
}
pold = pold->_next;
}//創(chuàng)建新的復(fù)雜鏈表結(jié)束
//合并兩條復(fù)雜鏈表
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;
}//合并兩條復(fù)雜鏈表結(jié)束
//讓新創(chuàng)建的那條復(fù)雜鏈表上的所有結(jié)點(diǎn)的random指針指向相應(yīng)的結(jié)點(diǎn)
pold = cplist;
pnew = newlist;
while (pnew)
{
pnew->_random = pold->_random->_next;
pold = pnew->_next;
if(pold == NULL)//這是pnew的_next指針已經(jīng)指向空
{
break;
}
pnew = pold->_next;
}//結(jié)束
//分離合并后的復(fù)雜鏈表
pold = cplist;
pnew = newlist;
while (pold)
{
ComplexNode * curold = NULL;
ComplexNode * curnew = NULL;
if(pnew->_next == NULL)//已經(jīng)分離完成
{
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;
}//分離合并的復(fù)雜鏈表結(jié)束
return newlist;
}
測試代碼test.c：
#include "complexnode.h"
//
//復(fù)雜鏈表的復(fù)制。?個鏈表的每個節(jié)點(diǎn)，有?個指向next指針指向下?個節(jié)
//點(diǎn)，還有?個random指針指向這個鏈表中的?個隨機(jī)節(jié)點(diǎn)或者NULL，現(xiàn)在要
//求實(shí)現(xiàn)復(fù)制這個鏈表，返回復(fù)制后的新鏈表。
//ps: 復(fù)雜鏈表的結(jié)構(gòu)
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;
}
程序的運(yùn)行結(jié)果如下圖：
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
以位為單位來定義結(jié)構(gòu)體中的成員變量所占的空間內(nèi)存,含有位段的結(jié)構(gòu)體稱為位段結(jié)構(gòu),這篇文章主要給大家介紹了關(guān)于C/C++位段的相關(guān)資料,需要的朋友可以參考下2024-01-01
C++ 11允許開發(fā)者們以標(biāo)準(zhǔn)的、不依賴于平臺的方式編寫多線程程序。這篇文章概述了標(biāo)準(zhǔn)庫對于線程和同步操作機(jī)制的支持。這些都是非常重要的知識，希望讀者們可以認(rèn)真看一下2021-06-06
C語言實(shí)現(xiàn)紙牌計算24點(diǎn)小游戲
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)紙牌計算24點(diǎn)小游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-10-10
C++中const、volatile、mutable使用方法小結(jié)
這篇文章主要介紹了C++中const、volatile、mutable使用方法小結(jié),需要的朋友可以參考下2020-01-01
C++ LibCurl實(shí)現(xiàn)Web指紋識別功能
Web指紋識別是一種通過分析Web應(yīng)用程序的特征和元數(shù)據(jù),以確定應(yīng)用程序所使用的技術(shù)棧和配置的技術(shù),本文將通過C++中LibCurl庫實(shí)現(xiàn)簡單是指紋識別功能,感興趣的可以了解下2023-11-11
QML中動態(tài)與靜態(tài)模型應(yīng)用詳解
QML是一種描述性的腳本語言，文件格式以.qml結(jié)尾。語法格式非常像CSS（參考后文具體例子），但又支持javascript形式的編程控制。QtDesigner可以設(shè)計出·ui界面文件，但是不支持和Qt原生C++代碼的交互2022-08-08
這篇文章主要為大家詳細(xì)介紹了C語言學(xué)籍管理系統(tǒng)源代碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-03-03
本文主要解析了C/C++中數(shù)組和指針的區(qū)別，文章簡單易懂，對各位的工作學(xué)習(xí)有所幫助，有需求的朋友可以了解下2020-05-05
Clion配置opencv開發(fā)環(huán)境的詳細(xì)過程
這篇文章主要介紹了Clion配置opencv開發(fā)環(huán)境的詳細(xì)過程，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考的下2022-04-04
詳解如何在VS2019和VScode中配置C++調(diào)用python接口
這篇文章主要介紹了詳解如何在VS2019和VScode中配置C++調(diào)用python接口，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12