如何使用 C 将值插入双向链表

Question

我只是想向 C 中的排序双向链表插入一个值。当我使用以下命令打印出来时，它从不显示新创建的节点。我创建了一个新节点，然后设置值，然后更新新节点和它前面的节点的 prev 和 next 指针。我确定它与引用传递有关，想了解为什么？

struct NodeType {
int data;
struct NodeType * prev;
struct NodeType * next;
}*head, *last;

void insert_double(int key);
void displayList();
void find_node(int key);


int main()
{

head = NULL;
last = NULL;
/* Create a list with one as value and set as head */
head = (struct NodeType *)malloc(sizeof(struct NodeType));
head->data = 3;
head->prev = NULL;
head->next = NULL;
last = head;

int value=1;

insert_double(value);
printf("0\n");
displayList();
printf("1\n");
value=2;
printf("2\n");
find_node(value);
printf("3\n");
displayList();

return 0;

}

void displayList()
{
struct NodeType * temp;
int n = 1;

if(head == NULL)
{
    printf("List is empty.\n");
}
else
{
    temp = head;
    printf("DATA IN THE LIST:\n");

    while(temp != NULL)
    {
        printf("DATA of %d node = %d\n", n, temp->data);

        n++;

        /* Move the current pointer to next node */
        temp = temp->next;
    }
}
}

void find_node(int key)
{
struct NodeType * temp;
struct NodeType * newnode;
newnode->data=key;
 if(head == NULL){
    printf("No nodes");
}
else{
    temp=head;
    while(temp!=NULL)
    {
        if((temp->data)< key){
            newnode->prev=temp->prev;
            newnode->next=temp;
            temp->prev=newnode;
            break;
        }
        else{
            temp=temp->next;
        }
    }

}


}

void insert_double(int key)
{
struct NodeType * newnode;

if(head == NULL)
{
    printf("Empty!\n");
}
else
{
    newnode = (struct NodeType *)malloc(sizeof(struct NodeType));

    newnode->data = key;
    newnode->next = head; // Point to next node which is currently head
    newnode->prev = NULL; // Previous node of first node is NULL

    /* Link previous address field of head with newnode */
    head->prev = newnode;

    /* Make the new node as head node */
    head = newnode;

}
}

Answer 1

您的插入函数工作正常，displayList。

但是，程序在 find_node 函数中有未定义的行为：

void find_node(int key)
{
    struct NodeType * temp;
    struct NodeType * newnode;
    newnode->data=key;            //<-- BOOM! (writing to uninitialized pointer)

    if(head == NULL){
        printf("No nodes");
    }
    else{
        temp=head;
        while(temp!=NULL)
        {
            if((temp->data)< key){
                newnode->prev=temp->prev; //<-- BOOM!
                newnode->next=temp;       //<-- BOOM!
                temp->prev=newnode;
                break;
            }
            else{
                temp=temp->next;
            }
        }
    }
}

不太清楚您要在那里实现什么。如果这真的是一个 find 函数，它不应该试图在节点上执行操作或复制任何数据。

你真正需要的是这样的东西：

struct NodeType* find_node(int key)
{
    for(struct NodeType* temp = head; temp != NULL; temp = temp->next)
    {
        if (temp->data == key)
            return temp;
    }
    return NULL;
}

Answer 2

你的代码基本正确。在处理链表时，您只是错过了两个重要的边缘案例。首先是当您使用 find_node 插入一些值时，但它会被添加到列表的开头。在这种情况下，您新创建的节点成为列表的新头，因此您必须更新 head 变量。第二种边缘情况有点相反，它发生在您将新节点插入到列表末尾时。然后它成为列表的末尾，因此您需要更新 tail.

第一次使用链表时经常会遗漏这两个边缘情况，所以不用担心。我认为几乎所有使用链表的人都在他的旅程开始时犯过这些错误。

此外，您正在使用指向 find_node 中 NodeType 结构的未初始化指针：

struct NodeType * newnode;

应该是：

struct NodeType * newnode = (struct NodeType *)malloc(sizeof(struct NodeType));

Answer 3

谢谢你们。这是我根据您的意见提出的解决方案：

void insert_sorted_node(int key){
struct NodeType * temp = (struct NodeType *)malloc(sizeof(struct NodeType));
struct NodeType * newnode = (struct NodeType *)malloc(sizeof(struct NodeType));
newnode->data=key;
/* no nodes at all*/
/* insert_sorted_node(value) can't start empty list, need to fix */
 if(head == NULL){
    printf("head =null");
    temp = head;
    head->data=key;
    head->prev=NULL;
    head->next=NULL;
    last = head;
}
else{
    temp=head;
    while(temp!=NULL)
    {
        printf("\n\ndata = %d\nkey = %d\n", temp->data, key);

        /* key is new head 
            1) check if key < head->data

        */
        if(key<head->data)
        {
            printf("\nnew head\n");
            newnode->prev = head->prev;
            newnode->next = temp;
            temp->prev = newnode;
            head = newnode;
            break;

        }

        /* key is tail 
            if temp->next = NULL
        */
        else if(temp->next == NULL)
        {
            printf("\ntail\n");
            newnode->prev = temp;
            newnode->next = NULL;
            temp->next = newnode;
            last = newnode;
            break;
        }

        /* key is middle head 
            if key > temp->data and key< temp->next->data 

        */
        else if((key>temp->data)&&(key<temp->next->data))
        {
            printf("\nmiddle\n");
            newnode->prev=temp;
            newnode->next=temp->next;
            temp->next=newnode;
            temp->next->prev=newnode;
            break;
        }


        else{
            printf("next\n");
            temp=temp->next;
        }
    }



}


 }

如何使用 C 将值插入双向链表

How to insert a value into a doubly linked list using C

c

doubly-linked-list