C語言中怎么復制復雜鏈表，相信很多沒有經驗的人對此束手無策，為此本文總結了問題出現的原因和解決方法，通過這篇文章希望你能解決這個問題。

成都創新互聯公司是一家網站設計公司，集創意、互聯網應用、軟件技術為一體的創意網站建設服務商，主營產品：成都響應式網站建設、成都品牌網站建設、網絡營銷推廣。我們專注企業品牌在網站中的整體樹立，網絡互動的體驗，以及在手機等移動端的優質呈現。成都網站建設、網站設計、移動互聯產品、網絡運營、VI設計、云產品.運維為核心業務。為用戶提供一站式解決方案，我們深知市場的競爭激烈，認真對待每位客戶，為客戶提供賞析悅目的作品，網站的價值服務。

什么是復雜鏈表？

復雜鏈表指的是一個鏈表有若干個結點，每個結點有一個數據域用于存放數據，還有兩個指針域，其中一個指向下一個節點，還有一個隨機指向當前復雜鏈表中的任意一個節點或者是一個空結點。今天我們要實現的就是對這樣一個復雜鏈表復制產生一個新的復雜鏈表。

復雜鏈表的數據結構如下：

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語言中怎么復制復雜鏈表的方法了嗎？如果還想學到更多技能或想了解更多相關內容，歡迎關注創新互聯網站建設公司行業資訊頻道，感謝各位的閱讀！

另外有需要云服務器可以了解下創新互聯建站www.yijiale78.com，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業上云的綜合解決方案，具有“安全穩定、簡單易用、服務可用性高、性價比高”等特點與優勢，專為企業上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

新聞標題：C語言中怎么復制復雜鏈表-創新互聯
網站路徑：http://www.yijiale78.com/article10/dpdpgo.html

成都網站建設公司_創新互聯，為您提供網站改版、動態網站、網頁設計公司、靜態網站、面包屑導航、網站建設

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯