C++ 列表逻辑之间的节点删除

Question

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

在学习并构建了几个四叉树和八叉树之后，并且非常喜欢 segmentation ，我决定在我的服务器中使用 segmentation 。但是，只将节点放置在它们自己内部。我的问题是，如果节点位于中间，我无法弄清楚如何将前一个节点链接到下一个节点。我想知道我这样做是否正确。下面是我的代码，我评论了问题所在。任何帮助都会很棒!

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

Answer 1

因此，如果我答对了你的问题，那么你将无法在链表中插入一个项目。我真的希望这就是问题所在，否则我所做的所有输入都是徒劳的。

我并没有真正理解您的所有代码(因为它有点断章取义)，但我会通过示例向您展示逻辑。我将使用具有以下结构的节点:

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

因此我们将创建一个链表，其中每个项目都有指向上一个和下一个项目的指针。更复杂结构的逻辑(例如，left + right + child + parent指针)是一样的，唯一的区别是你必须设置所有的指针。它实际上并没有太大变化。

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

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

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

如果您不在同一个vay中输出值，您将只看到零，这意味着该节点已成功删除。

如果你的节点中有更多的指针，你所要做的就是以相同的方式正确处理它们。另一个提示是避免像 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;

然后使用您获得的指针进行操作。