C++在双向链表逻辑错误中插入元素

Question

我正在编写获取未排序元素列表并将它们排序为双向链表的代码。该代码在大多数情况下都有效，元素可以添加到列表的开头和结尾但是出于某种原因，如果添加的第一个元素将保留在头部（按字母顺序排列最高）头部的地址，我无法理解和 head->next 是一样的。如果顺序颠倒，尾巴也会发生这种情况。这跟28到50行的逻辑有关系

下面的代码是可编译和可运行的。任何关于我哪里出错的帮助将不胜感激。

注意：不使用 C++ 库或类，这是您自己的练习。

#include <iostream>
#include <cstring>

using namespace std;

struct node
{
    char value[15];
    node *next;
    node *prev;
};

void insert(node *&head, node *&tail, char *value){

    if(!head){
        // empty list create new node
        node* nn = new node;
        
        strcpy(nn->value, value);
        
        nn->next = NULL;
        nn->prev = NULL;
        
        head = nn;
        tail = nn;
    }
    else if(strcmp(value, head->value) < 0){
        // smaller than head.  Update head
        node* nn = new node;
        
        strcpy(nn->value, value);
        
        nn->next = head;
        nn->prev = NULL;
        nn->next->prev = head;
        
        head = nn;
    }
    else if(strcmp(value, tail->value) > 0){
        // larger than tail.  Update tail
        node* nn = new node;
        
        strcpy(nn->value, value);
        
        nn->next = NULL;
        nn->prev = tail;
        nn->prev->next = tail;
        
        tail = nn;
    }
    else{ 
        /* TODO: insert in the middle of the list */ 
    }
}

void printlinkedList(node *ll){
    node *curr = ll;

    while(curr){
        cout << "Value: " << curr->value << "\t";
        cout << "curr: " << curr << "\t";
        cout << "curr->prev " << curr->prev << "\n";
        curr = curr->prev;
    }
}

int main(){

    // Test code
    node *head = NULL;
    node *tail = NULL;

    insert(head, tail, (char*)"aa");
    insert(head, tail, (char*)"bb");
    insert(head, tail, (char*)"cc");
    insert(head, tail, (char*)"dd");

    cout << "\nhead:\t\t" << head << "\n";
    cout << "head->prev:\t" << head->prev << "\n";
    cout << "head->next:\t" << head->next << "\n\n";

    cout << "tail:\t\t" << tail << "\n";
    cout << "tail->prev:\t" << tail->prev << "\n";
    cout << "tail->next:\t" << tail->next << "\n\n\n";

    cout << "Linked List printed in reverse order: \n";
    printlinkedList(tail);

    return 0;
}

Answer 1

这个：

    nn->next = head;
    nn->prev = NULL;
    nn->next->prev = head;

应该是：

    nn->next = head;
    nn->prev = NULL;
    nn->next->prev = nn;

同样如此：

    nn->next = NULL;
    nn->prev = tail;
    nn->prev->next = tail;

应该是：

    nn->next = NULL;
    nn->prev = tail;
    nn->prev->next = nn;

Answer 2

你的 insert() 逻辑有问题。

当列表为空时，你没问题。

但是当在 head 前面插入时，您正在正确设置 nn->next 以指向旧的 head，但您随后设置的是旧的 head' s prev 指向旧的 head （即指向它自己）而不是指向新的 nn.

并且在 tail 之后插入时，您将 nn->prev 正确设置为指向旧的 tail，但是您随后设置了旧的 tail 的 next 指向旧的 tail （即指向它自己）而不是新的 nn.

这应该可以解决问题：

void insert(node *&head, node *&tail, char *value) {

    node* nn = new node;
    strncpy(nn->value, value, 15);
    nn->next = NULL;
    nn->prev = NULL;

    if (!head) {
        // empty list create new node
        
        head = tail = nn;
    }
    else if (strcmp(value, head->value) < 0) {
        // smaller than head.  Update head

        nn->next = head;
        head->prev = nn;
        head = nn;
    }
    else if (strcmp(value, tail->value) > 0) {
        // larger than tail.  Update tail
        
        nn->prev = tail;
        tail->next = nn;        
        tail = nn;
    }
    else { 
        /* TODO: insert in the middle of the list */ 
    }
}

C++在双向链表逻辑错误中插入元素

C++ Inserting elements in doubly linked list logic error

c++

doubly-linked-list