从双向链表中删除节点会导致分段错误 - C

Question

我编写了一个程序，可以将char 字符添加到双向链表的开头。现在，一旦我有了这个列表，我的程序的目的就是从列表中完全删除某些 char 字符。例如（仅出于代表性目的使用大括号）：如果列表由 { a, b, b, a, c } 组成，那么我的程序可以从列表中删除所有“b”使其成为 { a, a, c}。此外，如果我的列表是 {b, a, c, a} 或 {a, c, a, b} 并且如果我想删除“b”然后程序在这两种情况下都能正常工作并给我 {a, c, a}.

但是有很多问题（对于所有情况，假设我想删除“b”）：

如果我的列表是 {b, a, b, a, c}（“b”在前面和中间某处），我得到分段错误（我认为是与在 while 循环中使用游标有关，但我不知道确切原因以及如何修复它）
如果我的列表是 {a, b, b, a, c, b}（“b”在中间和最后）然后输出给我奇怪的符号（我我假设它是内存错误，不知道为什么）

这是我使用的代码：

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

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

struct list* head; // global variable - pointer to head node of list.
struct list* last; // global variable - pointer to last node of list

//Creates a new list and returns pointer to it.
struct list* GetNewNode(char x)
{
   struct list* newNode
       = malloc(sizeof(struct list));
   newNode->data = x;
   newNode->prev = NULL;
   newNode->next = NULL;
   return newNode;
}

//Inserts a list at head of doubly linked list
void InsertAtHead(char x)
{
   struct list* newNode = GetNewNode(x);
   if(head == NULL)
   {
       head = newNode;
       return;
   }

   head->prev = newNode;
   newNode->next = head;
   head = newNode;
   struct list* temp = head;

   while (temp->next != NULL) temp = temp->next;
   last = temp;
}

void remove_element (char character)
{
   struct list * cursor, *previous, *store_el;
   //int boolean = 0;

   if (head == NULL) return;
   else
   {
       cursor = head;
       while(cursor != NULL)
       {
           if (cursor->data == character)
           {
               if (cursor->prev == NULL)
               {
                  // printf("deleting from front\n");
                   previous = head;
                   head = head->next;
                   head->prev = NULL;
                   //boolean = 1;
                   //free(previous);
               }
               if (cursor->next == NULL)
               {
                   //printf("deleting from back\n");
                   previous = last;
                   last = last->prev;
                   last->next = NULL;
                   //boolean = 1;
                   //free(previous);
               }
               else
               {
                  // printf("deleting from middle\n");
                   previous = cursor;
                   cursor = cursor->next;
                   cursor->prev = previous->prev;
                   store_el = previous->prev;
                   store_el->next = cursor;
                   cursor = head;

               }
               free(previous);
               //printf("head data = %c\n", cursor->data);
           }
           cursor = cursor->next;
       }
   }
}

//Prints all the elements in linked list in forward traversal order
void Print()
{
   struct list* temp = head;
   printf("Forward: ");
   while(temp != NULL)
   {
       printf("%c ",temp->data);
       temp = temp->next;
   }
   printf("\n");
}

int main()
{

   char character;
   /*Driver code to test the implementation*/
   head = NULL; // empty list. set head as NULL.

   // Calling an Insert and printing list before and after deletion of character
   InsertAtHead('c');
   InsertAtHead('a');
   InsertAtHead('b');
   InsertAtHead('b');
   InsertAtHead('a');
   Print();
   printf("After deletion:\n");
   remove_element ('b');
   Print();
}

Answer 1

尝试更新游标

cursor = head;

你从前面删除后。

Answer 2

Ellothere 我认为你的程序中的问题是你在之前分配了节点的地址但你没有并排释放它。

       if (cursor->prev == NULL)
       {
          // printf("deleting from front\n");
           previous = head;
           head = head->next;
           head->prev = NULL;
           //boolean = 1;
           //free(previous);
       }
       if (cursor->next == NULL)
       {
           //printf("deleting from back\n");
           previous = last;
           last = last->prev;
           last->next = NULL;
           //boolean = 1;
           //free(previous);
       }

这里你正在存储节点但在最后释放它然后这里有 2 个 if 语句然后发生的是 'b' 在 {a b b a c} 中彼此相邻所以首先 previous variable 存储第一个 'b' 的地址然后它存储 next [=30] 的地址=] 并且它只是释放 'b' 并且那个 'b' 保留在那里。简而言之，您应该并排释放节点。我做了这个小改动，效果很好。

if (cursor->prev == NULL)
               {
                  // printf("deleting from front\n");
                   previous = head;
                   head = head->next;
                   head->prev = NULL;
                   free(previous);
                   //boolean = 1;
                   //free(previous);
               }
               if (cursor->next == NULL)
               {
                   //printf("deleting from back\n");
                   previous = last;
                   last = last->prev;
                   last->next = NULL;
                   free(previous);
                   //boolean = 1;
                   //free(previous);
               }
               else
               {
                  // printf("deleting from middle\n");
                   previous = cursor;
                   cursor = cursor->next;
                   cursor->prev = previous->prev;
                   store_el = previous->prev;
                   store_el->next = cursor;
                   cursor = head;

               }

我刚刚在两个 if 语句中添加了一个 free 函数。

Answer 3

/* 
*I changed the name of your variable 'last' to 'tail'
*I removed the code at the end of your InsertAtHead function
*I added "tail = newNode;"
*I changed the name of your variable 'previous' to 'garbage'
*I removed your variable 'store_el' completely.
*I could have changed the whole code in your remove element function because the 3 cases are unnecessary but anyway.
*/
//Inserts a list at head of doubly linked list
void InsertAtHead(char x){
    struct list* newNode = GetNewNode(x);

    if (head == NULL){
        head = newNode;
        tail = newNode;
        return;
    }

    head->prev = newNode;
    newNode->next = head;
    head = newNode;
}

void remove_element (char character){
    struct list * cursor,  *garbage;

    cursor = head;
    while(cursor != NULL){
        if (cursor->data == character){
                garbage = cursor;

                if (cursor->prev == NULL){
                    head = head->next;
                    If (head!=NULL) head->prev = NULL;
                    cursor=head;
                }else if (cursor->next == NULL){
                    tail = tail->prev;
                    tail->next = NULL;
                    cursor=NULL;
                }else{
                    garbage->prev->next = garbage->next;
                    garbage->next->prev = garbage->prev;
                    cursor=cursor->next;
                }

                free(garbage);
        } else cursor=cursor->next;
    }
}

立即尝试。

您的代码的问题在于您正在使用释放的内存。

/*
*cursor and previous point to the same memory address
*you free the memory that the variable previous points so the cursor points to that freed memory 
*when you save the next address to the cursor using that freed memory you create an undefined behaviour (your code may work or may not)
*/
cursor = head;
        while(cursor != NULL)
        {
            if (cursor->data == character)
            {
                if (cursor->prev == NULL)
                {
                    previous = head;
                    head = head->next;
                    head->prev = NULL;
                    free(previous);
...
cursor=cursor->next;

改进后的代码：

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

//The type of your variable data was wrong. I changed it to char
struct list{
    char data;
    struct list *prev, *next
};

void remove_element (char character){
    struct list * cursor,  *garbage;

    cursor = head;
    while(cursor != NULL){
        if (cursor->data == character){
                garbage = cursor;

                if (garbage->prev!=NULL ) garbage->prev->next = garbage->next;
                if (garbage->next!=NULL ) garbage->next->prev = garbage->prev;
                cursor=cursor->next;

                if (head==garbage) head=cursor;
                //Basically the tail variable has no use for your current program.
                //if (tail==garbage) tail=garbage->prev;

                free(garbage);
        } else cursor=cursor->next;
    }
}

从双向链表中删除节点会导致分段错误 - C

Removing node from doubly linked list gives segmentation fault - C

c

doubly-linked-list