1

编辑：问题：删除两个节点之间的一个节点，然后将外部节点相互链接。

在学习和构建了几个四叉树和八叉树之后，我非常喜欢细分，我决定在我的服务器中使用细分。但是，仅将节点放置在自身内部。我的问题是，如果节点在中间，我不知道如何将前一个节点链接到下一个节点。我想知道我这样做是否正确。下面是我的代码，我评论问题区域在哪里。任何帮助都会很棒！

bool deleteNode ( SOCKET s , client_information_class *prev ) {
          bool return_value = false;
          if ( node[0]->client_socket != s ) {
               if ( node[0]->node != NULL ) {
                    return_value = node[0]->deleteNode ( s , *node );
               } else {
                    cout << endl << "Can not call deleteNode anymore ... Did not find the node to delete ... " << endl;
                    return return_value;
               }
          } else {
               if ( node[0]->client_state == 1 )
                    InterlockedDecrement(&connection_count);
               if ( node[0]->node != NULL ) {          // there is a next node
                    client_information_class **next = node[0]->node;
                    if ( next[0]->node != NULL ) {
                         // problem area
                         cout << endl << "next[0]->node is not null" << endl;
                         prev->node = next[0]->node[0]->node; // ??? I know its wrong
                    } else {
                         // problem area
                         cout << endl << "next[0]->node is null" << endl;
                         prev->node = next[0]->node;  // ??? I know its wrong
                    }
                    delete node;
               } else {                                   // its the last one
                    prev->node = NULL;
                    delete node;
               }
               InterlockedDecrement(&socket_count);
               return_value = true;
          }
          return return_value;
}
4

2 回答 2

2

因此，如果我解决了您的问题，那么您将无法在链接列表中插入项目。我真的很希望这是问题所在，否则我所做的所有打字都是徒劳的。

我并没有真正得到你所有的代码（因为它有点脱离上下文），但我会通过一个例子向你展示逻辑。我将使用具有以下结构的节点：

class Node
{
public:
    Node * next_;
    Node * prev_;
    int i;//we need this to tell nodes apart. 
    //And whatever data you want.
}

所以我们将创建一个链表，其中每个项目都有指向前一个项目和下一个项目的指针。更复杂结构的逻辑（例如，如果你有左+右+子+父指针）是相同的，唯一的区别是你必须设置所有这些。它实际上并没有太大变化。

因此，要构造列表，我们需要几个构造函数来处理不同的操作：

创建空节点的默认构造函数：

Node()//default constructor
{
    prev_ = nullptr;
    next_ = nullptr;
    i = 0;
}

一个构造函数，它接受指向列表中最后一项的指针，并将自身附加到列表的末尾：

Node( Node * prev )//constructor for appending to the end of the list
{
    prev_ = prev;
    next_ = nullptr;//we append to the end, so there is no "next" element
prev->next_ = this;
    i = 0;
}

最后在中间插入一个构造函数（我相信这就是你想要的）：

Node( Node * prev, Node * next)//Inserting between prev and next nodes
{
    prev->next_ = this;
    next->prev_ = this;
    this->prev_ = prev;
    this->next_ = next;
    i = 0;
}

现在我们拥有全套工具来做我们想做的任何事情。最后一件事是删除一个节点：

void deleteNode( Node * deleteMe )
{
    deleteMe->prev_->next_ = deleteMe->next;
    deleteMe->next_->prev_ = deleteMe->prev;
    delete deleteMe;
}

或者，更易读的语法：

void deleteNode( Node * deleteMe )
{
    Node * prevNode = deleteMe->prev_;
    Node * nextNode = deleteMe->next_;
    prevNode->next_ = deleteMe->next;
    nextNode->prev_ = deleteMe->prev;
    delete deleteMe;
}

让我们制作一个包含 10 个元素的示例列表：

int main()
{
    Node * root =  new Node();//the root of the list. it never changes.
    Node * last = root;//The pointer to the last element
    for(int i = 0; i < 10; i++)
    {
        Node * tmp = new Node( last );
        last = tmp;
    }
}

在这里，列表中的所有元素都正确链接，并且它们的i字段包含 0 值。让我们在中间的某处插入另一个元素，例如，在第三个和第四个元素之间：

Node * thirdNode = root->next_->next_;//I know this sucks, but it's just an example.
Node * insertMe = new Node(thirdNode, thirdNode->next_);//inserting between the third and the fourth.
insertMe->i = 9;//this will indicate the one we inserted, since all the others will have this as 0.

现在我们可以轻松检查插入是否正确。让我们输入所有元素的数据：

for( Node * it = root; it!= last; it = it->next_)
{
    std::cout << it->i << " ";
}

结果将是0 0 0 9 0 0 0 0 0 0 0。

最后，让我们删除刚刚插入的节点：

deleteNode( insertMe );

如果您不以相同的方式输出值，您将只看到零，这意味着该节点已成功删除。

如果您的节点中有更多指针，您所要做的就是以相同的方式正确处理它们。对您的另一个提示是避免像this->next->next->prev. 很难说您指的是当前元素的第三个元素的“prev”指针。相反，使用类似的东西：

Node * target = this->next->next;//easy to read

或许

Node * target = this;
for(int i = 0; i < 5; i++)
    target = target->next;

然后使用你得到的指针。

于 2012-07-20T06:36:17.177 回答
0

如果您想轻松地从单链表中删除元素，请使用指向如下指针的指针：

在此处输入图像描述 在此处输入图像描述 在此处输入图像描述 在此处输入图像描述

代码示例：

// Remove the node from the list:
Node* node_to_remove = *pointer_to_next_pointer;
*pointer_to_next_pointer = node_to_remove->next;

// Destroy the node.
destroy(node_to_remove);

这可以在不检查您是否从头部移除或类似的东西的情况下完成。

完整示例：

// ------------------------------------------------------------------
// Start by pointing to the head pointer.
// ------------------------------------------------------------------
//    (next_ptr)
//         |
//         v
// [head]----->[..]----->[..]----->[..]----->[to_remove]----->[....]
Node** next_ptr = &list->head;

// ------------------------------------------------------------------
// Search the list for the matching entry.
// After searching:
// ------------------------------------------------------------------
//                                  (next_ptr)
//                                       |
//                                       v
// [head]----->[..]----->[..]----->[..]----->[to_remove]----->[next]
while (*next_ptr != to_remove) // or (*next_ptr)->val != to_remove->val
{
    Node* next_node = *next_ptr
    next_ptr = &next_node->next;
}

// ------------------------------------------------------------------
// Dereference the next pointer and set it to the next node's next
// pointer.
// ------------------------------------------------------------------
//                                           (next_ptr)
//                                                |
//                                                v
// [head]----->[..]----->[..]----->[..]---------------------->[next]
*next_ptr = to_remove->next;

简化这一点的诀窍是，大多数人错过了导致他们编写 2 或 3 倍代码的额外分支的方法是使用指向节点指针的指针，而不是指向节点的指针。

此外，如果您不希望在遍历链表时出现大量缓存未命中，请确保以一种可以重新获得链表通常缺乏的空间局部性的方式分配它们。在不使用自定义内存分配器的情况下执行此操作的一种简单方法是std::vector使用索引而不是指针将数组（或，例如）中的节点链接在一起。如果 32 位索引就足够了，这也可以将 64 位链接的内存使用量减半。

于 2017-12-27T06:04:39.863 回答