3

我正在尝试实现一个链表，所以我有一个带有头文件的 Node 类，如下所示：

@interface Node : NSObject

@property(nonatomic,assign)int data;
@property(nonatomic,strong) Node *right;
@property(nonatomic,strong) Node *left;

@end

然后在另一个类中，我分配它们，然后调用一个方法来销毁给定值的所有出现：

Node *node0 = [[Node alloc]init];
Node *node1 = [[Node alloc]init];
Node *node2 = [[Node alloc]init];
Node *node3 = [[Node alloc]init];
Node *node4 = [[Node alloc]init];
node0.data = 1;
node1.data = 2;
node2.data = 5;
node3.data = 5;
node4.data = 3;
node0.right = node1;
node1.right = node2;
node2.right = node3;
node3.right = node4;
node4.right = NULL;
[self removeNodeWithValue:node0 value:5];
NSLog(@"node %d, %d, %d, %d, %d", node0.data, node1.data, node2.data, node3.data, node4.data);

这是方法本身：

-(void)removeNodeWithValue:(Node *)head value:(int)value
 {
  Node *toDelete;
  while (head != NULL) {
    if (head.data == value)
    {
        toDelete = head;
        head = head.right;
        toDelete = nil;
    }
    else
    {
       head = head.right;
    }
  }
 }
 ==> 1, 2, 5, 5, 3

我知道我可以更改实例，因为如果我更改toDelete = nil为toDelete.data = 4，则输出为==> 1, 2, 4, 4, 3。我的问题是，我如何销毁这些实例？谢谢。

4

3 回答 3

5

看来您还没有理解 ARC 的工作原理。只要有指向对象的强指针，对象就不会被释放。在您的示例中，您的代码失败有两个原因：首先，您始终保持对以下内容的强烈引用node0： 

Node *node0 = [[Node alloc]init];

只要此指针未设置为nil（请记住，按照惯例NULL，它用于常规指针，nil用于对象指针），就不会释放该节点。

其次，如果要解除分配的节点不是第一个节点，那么还有另一个节点持有指向它的强指针，这也是该节点不会被解除分配的另一个原因。保留另一个指向node0（toDelete在您的情况下）的指针将增加节点的节点保留计数，并且当您将其设置为它时，nil它将返回到它的原始值。

要正确执行此操作，您还必须避免链删除（如果第一个节点被释放，它会丢失对第二个节点的强引用，如果没有指向它的强指针，它可能会被释放，并且还会导致第三个节点被释放，等等）。

最后，我建议不要只保存一堆指向每个节点的指针，而是实现一个链表类，它可以完成添加/删除节点的工作： 

@interface List : NSObject

@property (nonatomic, strong) Node* first;
@property (nonatomic, weak) Node* last;

@end

// Inside the class implementation

- (void) addNodeWithValue: (int) value
{
    Node* node= [[Node alloc]init];
    node.data= value;
    if(!first)
    {
        last= first= node;
    }
    else
    {
        last.right= node;
        node.left= last;   // left should be a weak property
        last= node;
    }
}

- (void) removeNodeWithValue: (int) value  // O(n) method
{
    Node* ptr= first;
    while(ptr) 
    {
        if(ptr.data== value)
        {
            if(ptr== first)
            {
                first= last= nil;
            }
            else
            {
                ptr.left.right= ptr.right;
                ptr.right.left= ptr.left;
            }
            break;  // Remove the break if you want to remove all nodes with that value
        }
        ptr= ptr.right;
    }
}

我没有测试过这段代码，我不能保证它有效。

于 2013-08-18T16:44:10.007 回答
0

因此，您要清除具有指定值的所有节点。首先，您的测试无效，因为您对所有节点都有明确的引用，因此即使它们已从您的节点结构中清除，您的测试日志仍会将它们打印出来。其次，当你的移除方法没有发现被测节点具有指定值时，需要通过节点结构递归调用。第三，节点不应该测试自己，它应该测试left和right节点的值（节点不能删除自己，因为它不知道它的父节点）。

所以，像：

-(void)removeNodeWithValue:(Node *)head value:(int)value
{
    if (head.right.data == value)
    {
       head.right = nil;
    }
    else
    {
        [self removeNodeWithValue:head.right value:value];
    }

    if (head.left.data == value)
    {
       head.left = nil;
    }
    else
    {
        [self removeNodeWithValue:head.left value:value];
    }
}

这不会测试根节点本身，因为这应该在开始之前检查，然后从控制器本身中删除头项。

于 2013-08-18T16:39:13.073 回答
0

您的问题不是删除对象，而是指针。

指针就像指向带有内容（内存位置）的盒子的箭头。当你这样做

toDelete = head;
head = head.right;
toDelete = nil;

您只是删除指向某个框的“箭头”之一，而不是删除框本身。

韦恩的回答应该给出正确的方法。

于 2013-08-18T16:40:00.710 回答