插入C中的双链表

Question

我的程序不断崩溃。我认为我的逻辑有问题。请帮忙！谢谢

struct node{
    int data;
    struct node *prev,*next;
} *head = NULL;

void insert(){
    struct node* temp = (struct node*) malloc (sizeof (struct node*));
    int value;
    printf("Enter an element");
    scanf("%d",&value);
    temp -> data = value;
    temp -> next = NULL;
    temp -> prev = NULL;
    if(value < head -> data || head == NULL){
        temp -> next = head -> next;
        head = temp;
        return;
    }
    while(head->next != NULL && value > head -> next -> data)
        head = head -> next;
    temp -> next = head ->next->prev;
    head -> next = temp -> prev;
    while (head -> prev != NULL)
        head = head -> prev;
}

Answer 1

试试这个：

#include <stdio.h>
#include <stdlib.h>
struct node{
    int data;
    struct node *prev,*next;
} *head = 0;

void insert(int value){
    struct node* temp = (struct node*) malloc (sizeof (struct node));
    //int value;
    //printf("Enter an element");
    //scanf("%d",&value);
    temp -> data = value;
    temp -> next = 0;
    temp -> prev = 0;
    if(head == 0) {
        // no head, make temp the head
        head = temp;
    } else if(value > head->data) {
        // put temp in front of the head
        temp->next = head;
        head->prev = temp;
        head = temp;
    } else {
        // put temp after the head
        struct node *this = head;
        struct node *prev = 0;
        while(this && this->data > value) {
            prev = this;
            this = this->next;
        }
        temp->next = this;
        temp->prev = prev;
        prev->next = temp;
        if(this) {
            this->prev = temp;
        }
    }
}
int main() {
    insert(1);
    insert(3);
    insert(4);
    struct node *t = 0;
    for(t = head; t; t = t->next) {
        printf("%dn", t->data);
    }
}

这个按降序进行编译和排序。注意：我对您的扫描进行了注释并使insert取一个参数。

Answer 2

malloc的空间不够。

更改

struct node* temp = (struct node*) malloc (sizeof (struct node*));

至

struct node* temp = (struct node*) malloc (sizeof (struct node));

Answer 3

首先，考虑这两行以及如果head == NULL:会发生什么

if(value < head->data || head == NULL){
    temp->next = head->next;

具体来说，什么是head->next？

Answer 4

我看到了两个核心问题。

1. 您没有为节点结构分配足够的空间。sizeof(struct node *)返回节点指针的大小，而不是节点的大小。此：

   struct node* temp = (struct node*) malloc (sizeof (struct node*));`
   

   应该是这样的：

   struct node* temp = (struct node*) malloc (sizeof (struct node));
   

2. 小心指针：

    if (value < head -> data || head == NULL)
   

   如果您还没有初始化head，那么head->data的值是多少？（例如，它仍然是NULL）。您的程序将从地址NULL获取数据，字段data具有偏移量。地址NULL无效/是受保护内存空间的一部分，您的操作系统不会喜欢这样：）。

您应该首先检查head是否为NULL。如果是，则不能引用head的字段，因为它们无效（在任何情况下）。对于多部分条件表达式，也要小心在引用结构字段的后续部分之前检查结构指针NULL是否存在。