删除自定义双链表

Question

List属性:一个指针指向下一个节点，另一个指针指向列表中的任意节点。

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;
}

在正常情况下，析构函数工作得很好，但对于具有上述list属性的列表，它会失败

,

节点:1

Link1: Node 2

Link2: Node 3

节点:2

Link1: Node 3

Link2: Node 1

在上面的例子中，当析构函数到达指向节点1的Node2的Link2时，节点1已经被删除，因此代码抛出分段错误。

我想到了:在列表中有一个唯一节点的数组，并逐个删除

还有其他方法吗?

Answer 1

您可以使用shared_ptr's，当最后一个指针被销毁或重新分配时，它们将释放内存。你唯一要记住的就是避免循环，这就是为什么对于任意节点，使用weak_ptr来代替。

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

Answer 2

你的列表想法的两个替代方案(看起来不错)

1. 为每个Node保留父节点列表。当一个节点被删除时，将指向该节点的所有父节点的指针设置为nullptr。您可以随时安全地删除nullptr。

2. 如果你的图形是一个树(即没有循环)，你可以使用引用计数使用共享指针或unique_指针