双向链表 - 段错误

Question

我有一个双向链表，

struct node 
{ 
    int data; 
    struct node *prev; 
    struct node *next; 
}; 

和deleteEnd功能我实现，

bool deleteEnd(struct node **head, int* value) { 
    if (*head == NULL) return false; 
    struct node* end = *head; 
    while (end->next != NULL) { 
     end = end->next; 
    } 

    if (end == *head) *head = NULL; 
    else end->prev->next = NULL; 

    *value = end->data; 
    free(end); 

    return true; 
} 

这给了我一个分段错误，但我想不出为什么。此时我的清单中有3个元素（1<->2<->5）和5应该被删除。

list.h

#pragma once 

#include <stdbool.h> 

/* doubly linked list structure */ 
struct node 
{ 
    int data; 
    struct node *prev; 
    struct node *next; 
}; 

struct node* create(int value); 
bool insertAtBeginning(struct node **head, int value); 
bool insertAtEnd(struct node **head, int value); 
bool insertAfter(struct node **head, int value, int preVal); 
bool deleteBeginning(struct node **head, int* value); 
bool deleteEnd(struct node **head, int* value); 
bool deleteSpecific(struct node **head, int value); 
void display(struct node *head); 

list.c

#include "list.h" 
#include <stdlib.h> 
#include <stdio.h> 

struct node* create(int value) { 
    struct node* n = malloc(sizeof(struct node)); 
    if (n == NULL) return NULL; 
    n->data = value; 
    n->prev = NULL; 
    n->next = NULL; 
    return n; 
} 
bool insertAtBeginning(struct node **head, int value) { 
    struct node* old_head = *head; 
    *head = create(value); 
    if (*head == NULL) return false; 
    (*head)->next = old_head; 
    return true; 
} 
bool insertAtEnd(struct node **head, int value) { 
    // Get last node 
    struct node* last = *head; 
    while (last->next != NULL) { 
     last = last->next; 
    } 
    // Insert after 
    last->next = create(value); 
    if (last->next == NULL) return false; 
    else return true; 
} 
bool insertAfter(struct node **head, int value, int preVal) { 
    // Get previous 
    struct node* prev = *head; 
    while (prev->data != preVal && prev->next != NULL) { 
     prev = prev->next; 
    } 
    // Not founnd ? 
    if (prev->next == NULL && prev->data != preVal) return false; 

    // Insert in between 
    struct node* nxt = prev->next; 
    struct node* insert = create(value); 
    if (insert == NULL) return false; 
    prev->next = insert; 
    insert->next = nxt; 
    return true; 
} 
bool deleteBeginning(struct node **head, int* value) { 
    struct node* hd = *head; 
    *value = hd->data; 
    *head = (*head)->next; 
    free(hd); 
    return true; 
} 
bool deleteEnd(struct node **head, int* value) { 
    if (*head == NULL) return false; 
    struct node* end = *head; 
    while (end->next != NULL) { 
     end = end->next; 
    } 

    if (end == *head) *head = NULL; 
    else end->prev->next = NULL; 

    *value = end->data; 
    free(end); 

    return true; 
} 
bool deleteSpecific(struct node **head, int value) { 
    // Find node 
    struct node* n = *head; 
    while (n->data != value && n->next != NULL) { 
     n = n->next; 
    } 
    // Not found ? 
    if (n->next == NULL && n->data != value) return false; 

    // Deleting head ? 
    if (n == *head) { 
     *head = (*head)->next; 
     free(n); 
    } 
    // Delete in between 
    else { 
     struct node* nxt = n->next; 
     struct node* prev = n->prev; 
     prev->next = nxt; 
     free(n); 
    } 
    return true; 
} 
void display(struct node *head) { 
    if (head == NULL) { 
     printf("List is Empty!!!"); 
    } 
    else { 
     printf("\nList elements are:\n"); 
     do { 
      printf("%d ", head->data); 
      head = head->next; 
     } 
     while(head != NULL); 
     printf("\n\n"); 
    } 
} 

的main.c

#include <stdio.h> 
#include "list.h" 

int main() 
{ 
    int value, preVal, retVal; 
    struct node *head = NULL; 


    /* insert data */ 
    value = 2; 
    printf("insert %d %s\n", value, insertAtBeginning(&head, value) ? "OK":"NOK"); 

    display(head); 

    value = 5; 
    printf("insert %d %s\n", value, insertAtEnd(&head, value) ? "OK":"NOK"); 

    display(head); // printf("blabla"); 

    value = 3; 
    printf("insert %d %s\n", value, insertAtBeginning(&head, value) ? "OK":"NOK"); 

    display(head); 

    value = 3; 
    preVal = 0; 
    printf("insert %d after %d %s\n", value, preVal, insertAfter(&head, value, preVal) ? "OK":"NOK"); 

    display(head); 

    value = 1; 
    preVal = 3; 
    printf("insert %d after %d %s\n", value, preVal, insertAfter(&head, value, preVal) ? "OK":"NOK"); 

    display(head); 

    /* delete data */ 
    retVal = deleteBeginning(&head, &value); 
    printf("delete %d %s\n", value, retVal ? "OK": "NOK"); 
    display(head); 
    retVal = deleteEnd(&head, &value); 
    printf("delete %d %s\n", value, retVal ? "OK": "NOK"); 
    display(head); 
    value = 3; 
    retVal = deleteSpecific(&head, value); 
    printf("delete %d %s\n", value, retVal ? "OK":"NOK"); 

    display(head); 

    return 0; 
} 

Answer 1

在情况下到底是等于头这一说法

end->prev->next = NULL; // <- segfault 

结果不确定的行为，因为end->prev等于NULL;

我会定义函数通过以下方式

bool deleteEnd(struct node **head, int *value) 
{ 
    bool success = *head != NULL; 

    if (success) 
    { 
     while ((*head)->next != NULL) head = &(*head)->next; 

     *value = (*head)->data; 

     struct node *last = *head; 

     *head = NULL; 

     free(last); 
    } 

    return success; 
} 

编辑：在您呈现更多的代码，那么它已经看到，至少这个功能

bool insertAtBeginning(struct node **head, int value) { 
    struct node* old_head = *head; 
    *head = create(value); 
    if (*head == NULL) return false; 
    (*head)->next = old_head; 
    return true; 
} 

是错误的，因为它不设置数据成员prev的old_head。

或本功能

bool insertAtEnd(struct node **head, int value) { 
    // Get last node 
    struct node* last = *head; 
    while (last->next != NULL) { 
     last = last->next; 
    } 
    // Insert after 
    last->next = create(value); 
    if (last->next == NULL) return false; 
    else return true; 
} 

没有检查磁头是否*等于NULL。并且新创建的节点的数据成员prev再次设置不正确。

这就是说，数据成员prev的值为NULL是函数deleteEnd不正确工作的原因。

你应该修改你的所有功能。

Answer 2

你必须检查是否结束元素有分组只有一个。如果它没有，则不能将下一个元素写入该前一个元素。

你是否缺少语句。

if (end->prev) 
    end->prev->next = NULL; // <- segfault