So löschen Sie den Knoten aus der doppelt verknüpften Liste

Question

Ich versuche gerade, einen Knoten aus einer doppelt verknüpften Liste zu löschen, aber wenn nur ein Element übrig ist, löst es eine Zugriffsverletzungsausnahme beim Versuch, es in Zeile 11 (*sPtr)->prevPtr = NULL; zu löschen. Dies ist meine aktuelle Löschfunktion:

char del(ListNodePtr *sPtr, char value) 
{ 
    ListNodePtr previousPtr; /* pointer to previous node in list */ 
    ListNodePtr currentPtr; /* pointer to current node in list */ 
    ListNodePtr tempPtr; /* temporary node pointer */ 

    /* delete first node */ 
    if (value == (*sPtr)->data) { 
     tempPtr = *sPtr; /* hold onto node being removed */ 
     *sPtr = (*sPtr)->nextPtr; /* de-thread the node */ 
     (*sPtr)->prevPtr = NULL; 
     if ((*sPtr)->nextPtr != NULL) { 
      free(tempPtr); /* free the de-threaded node */ 
     } 
     return value; 
    } /* end if */ 
    else { 
     previousPtr = *sPtr; 
     currentPtr = (*sPtr)->nextPtr; 

     /* loop to find the correct location in the list */ 
     while (currentPtr != NULL && currentPtr->data != value) { 
      previousPtr = currentPtr; /* walk to ... */ 
      currentPtr = currentPtr->nextPtr; /* ... next node */ 
     } /* end while */ 

      /* delete node at currentPtr */ 
     if (currentPtr != NULL) { 
      tempPtr = currentPtr; 
      previousPtr->nextPtr = currentPtr->nextPtr; 
      free(tempPtr); 
      return value; 
     } /* end if */ 
    } /* end else */ 

    return '\0'; 
} 

EDIT: Ich werde meine Hauptfunktion und meine Druckfunktion in dieser Reihenfolge hinzufügen unten für eine besseren Rahmen das, was ich versuche, so zu tun, dass meine Frage wieder geöffnet werden kann:

hier ist meine Hauptfunktion mit meiner listNode Struktur:

struct listNode { 
    char data; /* each listNode contains a character */ 
    struct listNode *nextPtr; /* pointer to next node*/ 
    struct listNode *prevPtr; /* pointer to previous node*/ 
}; /* end structure listNode */ 

typedef struct listNode ListNode; /* synonym for struct listNode */ 
typedef ListNode *ListNodePtr; /* synonym for ListNode* */ 

     /* prototypes */ 
void insert(ListNodePtr *sPtr, char value); 
char del(ListNodePtr *sPtr, char value); 
int isEmpty(ListNodePtr sPtr); 
void printList(ListNodePtr currentPtr); 
void printReverse(ListNodePtr currentPtr); 
void instructions(void); 

int main(void) 
{ 
    ListNodePtr startPtr = NULL; /* initially there are no nodes */ 
    int choice; /* user's choice */ 
    char item; /* char entered by user */ 

    instructions(); /* display the menu */ 
    printf("? "); 
    scanf("%d", &choice); 

    /* loop while user does not choose 3 */ 
    while (choice != 3) { 

     switch (choice) { 
     case 1: 
      printf("Enter a character: "); 
      scanf("\n%c", &item); 
      insert(&startPtr, item); /* insert item in list */ 
      printList(startPtr); 
      printReverse(startPtr); 
      break; 
     case 2: 
      /* if list is not empty */ 
      if (!isEmpty(startPtr)) { 
       printf("Enter character to be deleted: "); 
       scanf("\n%c", &item); 

       /* if character is found, remove it */ 
       if (del(&startPtr, item)) { /* remove item */ 
        printf("%c deleted.\n", item); 
        printList(startPtr); 
        printReverse(startPtr); 
       } /* end if */ 
       else { 
        printf("%c not found.\n\n", item); 
       } /* end else */ 
      } /* end if */ 
      else { 
       printf("List is empty.\n\n"); 
      } /* end else */ 

      break; 
     default: 
      printf("Invalid choice.\n\n"); 
      instructions(); 
      break; 
     } /* end switch */ 

     printf("? "); 
     scanf("%d", &choice); 
    } /* end while */ 

    printf("End of run.\n"); 
    return 0; /* indicates successful termination */ 
} /* end main */ 

und hier meine printReverse und drucken Funktionen sind:

void printList(ListNodePtr currentPtr) 
{ 

    /* if list is empty */ 
    if (currentPtr == NULL) { 
     printf("List is empty.\n\n"); 
    } /* end if */ 
    else { 
     printf("The list is:\n"); 

     /* while not the end of the list */ 
     while (currentPtr != NULL) { 
      printf("%c --> ", currentPtr->data); 
      currentPtr = currentPtr->nextPtr; 
     } /* end while */ 

     printf("NULL\n\n"); 
    } /* end else */ 
} /* end function printList */ 

void printReverse(ListNodePtr currentPtr) 
{ 
    /* if list is empty */ 
    if (currentPtr == NULL) { 
     printf("List is empty.\n\n"); 
    } /* end if */ 
    else { 
     printf("The list in reverse is:\n"); 

     while (currentPtr->nextPtr != NULL) 
      currentPtr = currentPtr->nextPtr; 

     /* while not the beginning of the list */ 
     while (currentPtr != NULL) { 
      printf("%c --> ", currentPtr->data); 
      currentPtr = currentPtr->prevPtr; 
     } /* end while */ 

     printf("NULL\n\n"); 
    } /* end else */ 
} /* end function printList */ 

Ich hoffe wirklich, dies macht es klarer über alles, was passiert, weil ich seit 3 ​​Tagen daran festhalte und es gibt wenig bis keine Themen, die ich online finden kann, die darüber reden, wie ich das mache , weil die Liste beim Einfügen und Löschen alphabetisch sortiert ist.

Also wenn jemand versuchen kann, mir zu sagen, was falsch ist und warum es eine Zugriffsverletzung Ausnahme in Zeile 11 löst, wenn ich versuche, das letzte Element in der Liste zu löschen, wäre ich so dankbar. Vielen Dank!

Answer 1

Ich denke, Sie haben die Dinge zu kompliziert gemacht. Sie trennen den "list" -Typ nicht vom "node" -Typ, aber ich denke, dass Sie ohne Zeiger-Zeiger-Vertauschung auskommen, wenn Sie nur einen Ersatz zurückgeben.

Sie könnten eine "Find" -Methode schreiben, um nach dem Zeichen zu suchen und einen Zeiger auf diesen Knoten zurückzugeben.

/** 
    Delete the node containing value from the list starting with start. 
    If value is not found in list, then the list is unchanged. Returns 
    a replacement value for start, which may be needed if the value is 
    contain in the start node. 
*/ 

ListNodePtr del(ListNodePtr start, char value) 
{ 
    ListNodePtr curr; 

    for (curr = start; curr && curr->data != value; curr = curr->nextPtr) { 
     // skip this node 
    } 

    if (!curr) { 
     // Value not found in list. List is unchanged. 
     return start; 
    } 

    /* Compute return value */ 

    if (curr == start) { 
     start = start->nextPtr; 
    } 

    /* Remove curr node from chain */ 

    if (curr->prevPtr) { 
     curr->prevPtr->nextPtr = curr->nextPtr; 
    } 

    if (curr->nextPtr) { 
     curr->nextPtr->prevPtr = curr->prevPtr; 
    } 

    free(curr); 
    return start; 
} 

Answer 2

Ich endete mein Problem zu erkennen. Visual Studio ließ mich keine Breakpoints verwenden, aber das war, weil ich nicht wusste, dass ich es auf "Release" und nicht auf "Debug" gesetzt hatte. Dadurch, dass ich die Zeiger verfolgt, um herauszufinden, wo sie auf die falschen unlinked oder verknüpft wurde und kam mit dieser Lösung:

/* Delete a list element */ 
char del(ListNodePtr *sPtr, char value) 
{ 
    ListNodePtr previousPtr; /* pointer to previous node in list */ 
    ListNodePtr currentPtr; /* pointer to current node in list */ 
    ListNodePtr tempPtr; /* temporary node pointer */ 

    /* delete first node */ 
    if (value == (*sPtr)->data) { 
      tempPtr = *sPtr; /* hold onto node being removed */ 
      *sPtr = (*sPtr)->nextPtr; /* de-thread the node */ 
      if(*sPtr != NULL) /* if the list is not empty */ 
       (*sPtr)->prevPtr = NULL; /* the previos pointer is null*/ 
      free(tempPtr); /* free the de-threaded node */ 
      return value; 
    } /* end if */ 
    else { 
     previousPtr = *sPtr; 
     currentPtr = (*sPtr)->nextPtr; 

     /* loop to find the correct location in the list */ 
     while (currentPtr != NULL && currentPtr->data != value) { 
      previousPtr = currentPtr; /* walk to ... */ 
      currentPtr = currentPtr->nextPtr; /* ... next node */ 
     } /* end while */ 

      /* delete node at currentPtr */ 

     if (currentPtr != NULL) { 
      tempPtr = currentPtr; 
      previousPtr->nextPtr = currentPtr->nextPtr; 
      if(previousPtr->nextPtr != NULL) /* if the next pointer isn't null */ 
       previousPtr->nextPtr->prevPtr = currentPtr->prevPtr; /* the previous pointer of the next pointer is the previous pointer of the current pointer */ 
      free(tempPtr); 
      return value; 
     } /* end if */ 

    } /* end else */ 
    return '\0'; 
} /* end function delete */ 

Answer 3

Ihr Code wird nicht überprüft, ob der neue Kopfknoten die letzte nach dem Löschen null ist Knoten, so dass der Code abstürzt, wenn Sie versuchen, den nächsten Zeiger des Kopfknotens auf Null zu setzen.

Festcode (läuft leckagefreien und fehlerfrei unter valgrind):

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

struct listNode 
{ 
    char data; 
    struct listNode *nextPtr; 
    struct listNode *prevPtr; 
}; 

typedef struct listNode ListNode; 
typedef ListNode *ListNodePtr; 

void insert(ListNodePtr *sPtr, char value); 
char del(ListNodePtr *sPtr, char value); 
int isEmpty(ListNodePtr sPtr); 
void printList(ListNodePtr currentPtr); 
void printReverse(ListNodePtr currentPtr); 

static void ins_check(ListNode **list, char c) 
{ 
    printf("Inserting [%c] (%p)\n", c, (void *)*list); 
    insert(list, c); 
    printList(*list); 
    printReverse(*list); 
} 

static void del_check(ListNode **list, char c) 
{ 
    printf("Deleting [%c] (%p)\n", c, (void *)*list); 
    if (del(list, c) != c) 
     printf("Did not find [%c] in list.\n", c); 
    printList(*list); 
    printReverse(*list); 
} 

int main(void) 
{ 
    ListNodePtr startPtr = NULL; 

    printList(startPtr); 
    printReverse(startPtr); 

    ins_check(&startPtr, 'a'); 
    ins_check(&startPtr, 'b'); 
    ins_check(&startPtr, 'c'); 

    del_check(&startPtr, 'c'); 
    del_check(&startPtr, 'a'); 
    del_check(&startPtr, 'b'); 

    assert(startPtr == 0); 

    printf("End of run.\n"); 
    return 0; 
} 

void printList(ListNodePtr currentPtr) 
{ 
    if (currentPtr == NULL) 
     printf("List is empty.\n"); 
    else 
    { 
     printf("The list is: "); 
     while (currentPtr != NULL) 
     { 
      printf("%c --> ", currentPtr->data); 
      currentPtr = currentPtr->nextPtr; 
     } 
     printf("NULL\n"); 
    } 
} 

void printReverse(ListNodePtr currentPtr) 
{ 
    if (currentPtr == NULL) 
     printf("List is empty (even in reverse).\n"); 
    else 
    { 
     printf("The list in reverse is: "); 
     while (currentPtr->nextPtr != NULL) 
      currentPtr = currentPtr->nextPtr; 
     while (currentPtr != NULL) 
     { 
      printf("%c --> ", currentPtr->data); 
      currentPtr = currentPtr->prevPtr; 
     } 
     printf("NULL\n"); 
    } 
} 

char del(ListNodePtr *sPtr, char value) 
{ 
    ListNodePtr previousPtr; 
    ListNodePtr currentPtr; 
    ListNodePtr tempPtr; 

    assert(*sPtr != 0); 
    if (value == (*sPtr)->data) 
    { 
     tempPtr = *sPtr; 
     printf("Deleting 1: [%c] (node = %p, next = %p, prev = %p\n", tempPtr->data, 
       (void *)tempPtr, (void *)tempPtr->nextPtr, (void *)tempPtr->prevPtr); 
     *sPtr = (*sPtr)->nextPtr; 
     if (*sPtr != 0) // Crucial change! 
      (*sPtr)->prevPtr = NULL; 
     free(tempPtr); 
     return value; 
    } 
    else 
    { 
     previousPtr = *sPtr; 
     currentPtr = (*sPtr)->nextPtr; 

     while (currentPtr != NULL && currentPtr->data != value) 
     { 
      previousPtr = currentPtr; 
      currentPtr = currentPtr->nextPtr; 
     } 

     if (currentPtr != NULL) 
     { 
      assert(previousPtr != 0); 
      tempPtr = currentPtr; 
      printf("Deleting 2: [%c] (node = %p, next = %p, prev = %p\n", tempPtr->data, 
        (void *)tempPtr, (void *)tempPtr->nextPtr, (void *)tempPtr->prevPtr); 
      previousPtr->nextPtr = currentPtr->nextPtr; 
      free(tempPtr); 
      return value; 
     } 
     else 
      printf("Did not find [%c]\n", value); 
    } 

    return '\0'; 
} 

void insert(ListNode **list, char value) 
{ 
    ListNode *node = malloc(sizeof(*node)); 
    if (node == 0) 
    { 
     fprintf(stderr, "Out of memory\n"); 
     exit(EXIT_FAILURE); 
    } 
    node->data = value; 
    node->nextPtr = 0; 
    node->prevPtr = 0; 
    if (*list != 0) 
    { 
     node->nextPtr = *list; 
     assert((*list)->prevPtr == 0); 
     (*list)->prevPtr = node; 
    } 
    *list = node; 
} 

Beispiel auszuführen:

List is empty. 
List is empty (even in reverse). 
Inserting [a] (0x0) 
The list is: a --> NULL 
The list in reverse is: a --> NULL 
Inserting [b] (0x7fccc3503070) 
The list is: b --> a --> NULL 
The list in reverse is: a --> b --> NULL 
Inserting [c] (0x7fccc3503090) 
The list is: c --> b --> a --> NULL 
The list in reverse is: a --> b --> c --> NULL 
Deleting [c] (0x7fccc35030b0) 
Deleting 1: [c] (node = 0x7fccc35030b0, next = 0x7fccc3503090, prev = 0x0 
The list is: b --> a --> NULL 
The list in reverse is: a --> b --> NULL 
Deleting [a] (0x7fccc3503090) 
Deleting 2: [a] (node = 0x7fccc3503070, next = 0x0, prev = 0x7fccc3503090 
The list is: b --> NULL 
The list in reverse is: b --> NULL 
Deleting [b] (0x7fccc3503090) 
Deleting 1: [b] (node = 0x7fccc3503090, next = 0x0, prev = 0x0 
List is empty. 
List is empty (even in reverse). 
End of run. 

Notiere die Verwendung von Wrapperfunktionen (ins_check() und del_check()) und die Verwendung von festen Daten, um es einfach zu testen (keine Eingabe erforderlich). Beachten Sie auch das Drucken von dem, was vor sich geht.

Ich hoffe, Ihr insert() ist etwas ähnlich wie die, die ich erfunden - eine wahre MCVE (How to create a Minimal, Complete, and Verifiable Example?) oder SSCCE (Short, Self-Contained, Correct Example) würde diese Funktion zur Verfügung gestellt haben.

Beachten Sie, dass der "neue" Code die von Is it a good idea to typedef pointers vorgeschlagenen Strikturen befolgt - die prägnante Antwort ist "Nein" (für nicht-opake Datenzeiger).

Beachten Sie, dass Ihre Löschfunktion so kompliziert ist, wie für eine einfach verknüpfte Liste erforderlich, aber viel einfacher sein kann, da jeder Knoten in einer doppelt verketteten Liste seinen eigenen Vorgänger kennt. Diese Version funktioniert auch sauber:

char del(ListNodePtr *sPtr, char value) 
{ 
    assert(*sPtr != 0); 
    ListNode *curr = *sPtr; 
    while (curr != NULL) 
    { 
     if (curr->data == value) 
     { 
      if (curr->prevPtr != NULL) 
       curr->prevPtr->nextPtr = curr->nextPtr; 
      if (curr->nextPtr != NULL) 
       curr->nextPtr->prevPtr = curr->prevPtr; 
      if (*sPtr == curr) 
       *sPtr = curr->nextPtr; 
      free(curr); 
      return value; 
     } 
     curr = curr->nextPtr; 
    } 

    printf("Did not find [%c]\n", value); 
    return '\0'; 
}