刪除自定義雙向鏈表

列表屬性：一個指針指向下一個節點，另一個指針指向列表中的任意任意節點。刪除自定義雙向鏈表

結構

struct node 
{ 
    int val; 
    node* link[2]; 
    node(int x); 
    ~node(); 
}; 
node :: node(int x) 
{ 
    val = x; 
    link[0] = NULL; 
    link[1] = NULL; 
} 
node :: ~node() 
    { 
     delete(link[0]); 
     delete(link[1]); 
    }

類

class List 
{ 
    node *head, *cloneHead; 
    node *stack[100]; 
    int childIndex[2][100]; 
    int stptr; 
public: 
    List(); 
    ~List(); 
    void createList(int[] , int[][2], int); 
    int createListStruct(node*); 
    void createCloneList(); 
    void clone(); 
    void printClone(); 
};

創建列表

void List::createList(int a[], int child[][2], int size) 
{ 
    node* linkedList[size]; 
    for(int i=0;i<size;i++) 
    { 
     linkedList[i] = new node(a[i]); 
    } 
    head = linkedList[0]; 
    for(int i=0;i<size;i++) 
    { 
     for(int j=0;j<2;j++) 
     { 
      if(child[i][j]!=-1) 
      { 
       linkedList[i]->link[j] = linkedList[child[i][j]]; 
      } 
     } 
    } 
}

主要

int main() 
{ 
    int a[]={10,1,3,7,2,8,20}; 
    int child[][2] = {{1,4},{1,2},{3,-1},{6,5},{6,5},{-1,0},{5,5}}; 
    int size = sizeof(a)/sizeof(a[0]); 
    List L; 
    L.createList(a,child,size); 
    L.clone(); 
    L.printClone(); 
    return 0; 
}

在正常情況下的析構函數的工作完美，但與上述列表屬性的失敗

列表

如：

節點：1

鏈接1：節點2

Link2：節點3

節點：2

鏈接1：節點3

鏈路2：節點1

在由時間析上述的情況下到達節點2，的鏈路2到節點哪個點1中，節點1已被刪除，所以該代碼是拋出分段錯誤。

我想出了：具有獨特的節點陣列中的列表，並逐個刪除

是否有任何其他方式做到這一點？

來源

2014-07-07 Sab

使用引用計數，我沒有你建立你的列表的方式的所有信息。因此，我無法給出準確的答案，但爲什麼要刪除第二個鏈接指針？看起來像你多次釋放節點。 –

它是一個不同的情況，如果第二個鏈接是唯一指向特定節點的東西。 – Sab

是否有多個節點不是某些其他節點的下一個節點（除了第一個節點，顯然不是，除非您正在考慮循環列表）。在這種情況下，shared_ptr，weak_ptr答案不適用於您。 –

你可以使用shared_ptr，當最後一個指針被銷燬或重新分配時，它們將釋放內存。唯一需要記住的是避免循環，這就是爲什麼任意節點ponter使用weak_ptr代替。

struct node; // forward declaration 

struct node 
{ 
    int val; 
    shared_ptr<node> next; 
    weak_ptr<node> other; 
};

來源

2014-07-07 11:25:51 MarekR

2的替代品，以列表的想法（這似乎確定）

對於每個節點保持父母的列表。當節點被刪除時，將所有父節點指向該節點的指針設爲nullptr。只要你喜歡，你可以安全地刪除nullptr。
如果你的圖是樹（即無週期）您可以使用共享指針或unique_pointers

來源

2014-07-07 11:29:47 Lanting

父母在時間被刪除，所以如果我嘗試將鏈接設置爲null，那麼它將是一個分段錯誤錯誤。 – Sab

因爲析構函數是遞歸調用的，所以在其子節點的析構函數被調用時，父節點仍然（但幾乎不存在）。包含指針的內存仍然是絕對分配的。 – Lanting

我想知道有沒有任何選項，沒有使用任何額外的空間 – Sab

刪除自定義雙向鏈表

回答

相關問題