TOP

C語言之復雜鏈表的復制(圖示詳解)(一)
2017-10-11 15:44:13 】 瀏覽:10313
Tags:

什么是復雜鏈表?

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

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

 1 typedef int DataType;        //數據域的類型
 2 
 3 //復雜鏈表的數據結構
 4 
 5 typedef struct ComplexNode
 6 
 7 {
 8 
 9 DataType _data ;                     // 數據
10 
11 struct ComplexNode * _next;          // 指向下個節點的指針
12 
13 struct ComplexNode * _random;        // 指向隨機節點(可以是鏈表中的任意節點 or 空)
14 
15 }ComplexNode;

 

 

上圖就是一個復雜鏈表的例子,那么我們應該如何實現復雜鏈表的復制呢?

1、首先我們應該根據已有的復雜鏈表創建一條新的復雜鏈表优乐棋牌app下载,但是這個新的復雜鏈表的所有的結點的random指針都指向空,這樣是很好實現的,相當于我們創建了一條簡單的單鏈表(newlist),我們要復制的鏈表不妨稱之為oldlist。

 

 

 

2、接下來我們應該把新創建的這條復雜鏈表(newlist)與已有的復雜鏈表(oldlist)合并成如下的形式:

 

 

 

在這種情況下我們已經把兩條復雜鏈表合并成了一條鏈表(稱之為linklist)优乐棋牌app下载,通過對這條鏈表(linklist)的觀察,我們可以發現合并的鏈表(linklist)中屬于newlist的結點pnew的上一個結點pold(屬于oldlist的結點)的random指針所指向的結點的next指針就應該是pnew結點的randow指針所指向的結點。

這樣我們讓pold和pnew指針一直往后走最后就可以實現對所有屬于新創建的復雜鏈表(newlist)的random指針指向相應的結點的操作。構成的復雜鏈表如下圖

 

 

在完成以上的步驟之后我們所要做的工作就很簡單了,我們只要把這一條鏈表linklist分開成我們的newlist鏈表和oldlist鏈表就可以了。

 

這樣我們就完美的完成了復雜鏈表的復制工作下面就是具體實現的代碼:

 頭文件complexnode.h:

 1 #ifndef __COMPLEX__NODE__H__
 2 
 3 #define __COMPLEX__NODE__H__
 4 
 5  
 6 
 7 //包含頭文件
 8 
 9 #include <stdio.h>
10 
11 #include<stdlib.h>
12 
13 #include <assert.h>
14 
15  
16 
17  
18 
19 typedef int DataType;        //數據域的類型
20 
21  
22 
23 //復雜鏈表的數據結構
24 
25 typedef struct ComplexNode
26 
27 {
28 
29 DataType _data ;                                // 數據
30 
31 struct ComplexNode * _next;                // 指向下個節點的指針
32 
33 struct ComplexNode * _random;        // 指向隨機節點(可以是鏈表中的任意節點 or 空)
34 
35 }ComplexNode;
36 
37  
38 
39 //創建一個復雜鏈表的結點
40 
41 ComplexNode * BuyComplexNode(DataType x);
42 
43  
44 
45 //打印復雜的單鏈表
46 
47 void Display(const ComplexNode * cplist);
48 
49  
50 
51 //復雜鏈表的復制
52 
53 ComplexNode * CopyComplexNode(ComplexNode * cplist);
54 
55  
56 
57 #endif//__COMPLEX__NODE__H__

具體功能實現complexnode.c

  1 #include "complexnode.h"
  2 
  3  
  4 
  5 //創建一個復雜鏈表的結點
  6 
  7 ComplexNode * BuyComplexNode(DataType x)
  8 
  9 {
 10 
 11 ComplexNode *cnode = (ComplexNode *)malloc(sizeof(ComplexNode));
 12 
 13 if(cnode == NULL)//創建失敗
 14 
 15 {
 16 
 17 perror("BuyComplexNode()::malloc");
 18 
 19 return NULL;
 20 
 21 }
 22 
 23 //創建成功
 24 
 25 cnode->_data = x;
 26 
 27 cnode->_next = NULL;
 28 
 29 cnode->_random = NULL;
 30 
 31 return cnode;
 32 
 33 }
 34 
 35  
 36 
 37 //打印復雜的單鏈表
 38 
 39 void Display(const ComplexNode * cplist)
 40 
 41 {
 42 
 43 ComplexNode *pnode = cplist;
 44 
 45 while (pnode)
 46 
 47 {
 48 
 49 printf("%d::%d -->",pnode->_data,pnode->_random->_data);
 50 
 51 pnode = pnode->_next;
 52 
 53 }
 54 
 55 printf("over\n");
 56 
 57  
 58 
 59 }
 60 
 61  
 62 
 63 //復雜鏈表的復制
 64 
 65 ComplexNode * CopyComplexNode(ComplexNode * cplist)
 66 
 67 {
 68 
 69  
 70 
 71 ComplexNode * pold = NULL;
 72 
 73 ComplexNode * pnew = NULL;
 74 
 75 ComplexNode * newlist = NULL;//指向新的復雜鏈表的頭結點的指針
 76 
 77 pold = cplist;
 78 
 79 //創建一條新的復雜鏈表
 80 
 81 while(pold != NULL)
 82 
 83 {
 84 
 85 ComplexNode * new_node = BuyComplexNode(pold->_data);
 86 
 87 if(newlist == NULL)//當新的復雜鏈表中沒有結點時
 88 
 89 {
 90 
 91 newlist = new_node;
 92 
 93 }
 94 
 95 else//當新的復雜鏈表有結點時
 96 
 97 {
 98 
 99 ComplexNode * node = newlist;
100 
101 while(node->_next != NULL)//找到最后一個結點
102 
103 {
104 
105 node = node->_next;
106 
107 }
108 
109 node->_next = new_node;//插入新的結點
110 
111 }
112 
113 pold = pold-&g  
		

請關注公眾號獲取更多資料



首頁 上一頁 1 2 下一頁 尾頁 1/2/2
】【打印繁體】【】【】 【】【】【】 【關閉】 【返回頂部
上一篇P1474 貨幣系統 Money Systems 下一篇逆序的三位數(第一日習題)