雙向鏈表 - 段錯誤

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