Doppelt verknüpfte Liste in C – Funktion zum Löschen von Knoten
-
21-12-2019 - |
Frage
In der Hauptfunktion werden doppelt verknüpfte Listenknoten erstellt.Ender und Header definiert.Unterbricht die Funktion „Knoten löschen“ – der Ender ist null.
Was ist der beste Weg, um den Speicher der letzten und ersten Eingabe freizugeben, d. h.:löschen:233,A und 888,F?
#include <stdafx.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
typedef struct record {
int idnumber;
char initial;
struct record *prevStudent;
struct record *nextStudent;
} STUDENT;
STUDENT *header = NULL; //pointer to the start of linked list
STUDENT *ender = NULL; //pointer to the end of the linked list
void Makenode(int x, char y);
void deletenode();
int main() {
Makenode(233, 'A');
Makenode(456, 'H');
Makenode(746, 'G');
Makenode(888, 'F');
deletenode();
fflush(stdin);
getchar();
return 0;
}
void Makenode(int x, char y) {
STUDENT *ptr;
ptr = (STUDENT *)malloc(sizeof(STUDENT));
if (ptr != NULL) {
ptr->idnumber = x;
ptr->initial = y;
ptr->nextStudent = header;
ptr->prevStudent = NULL;
if (header == NULL)
ender = ptr;
else
header->prevStudent = ptr;
header = ptr;
} else {
printf("Memory not allocated\n");
}
}
void deletenode() {
//delete the first and the last node of the linked list
STUDENT *p = header, *q = ender;
char c;
printf("Are you sure you want to delete Y/N:\n");
fflush(stdin); c=getchar();
while (c == 'Y' || c == 'y') {
ender=ender->nextStudent;
header=header->prevStudent;
free(p); free(q);
}
}
Lösung
Ihre Löschfunktion hinterlässt die verknüpfte Liste in einem illegalen Zustand.Zu jedem Zeitpunkt (außer vorübergehend innerhalb Ihrer Einfüge- und Löschfunktionen) muss Folgendes zutreffen:
- Wenn die
header
ist null, dasender
muss ebenfalls null sein und die Liste ist leer. - Wenn ein Knoten
p
hat einen Nicht-Null-Link zup->next
, Dannp->next->prev == p
. - Ebenso, wenn ein Knoten
p
hat einen Nicht-Null-Link zup->prev
, Dannp->prev->next == p
. - Der Header hat keinen vorherigen Knoten;Der Ender hat keinen nächsten Knoten.
Dies sind die Invarianten Ihrer verknüpften Liste.
Wenn Sie Ihren Code zum Löschen überprüfen:
void deletenode()
{
STUDENT *p = header, *q = ender;
ender=ender->nextStudent;
header=header->prevStudent;
free(p); free(q);
}
Sie können sehen, dass Sie gerade das eingestellt haben header
Und ender
Zu NULL
, denn das ist es ender->nextStudent
Und header->prevStudent
Sind.Aber selbst das Umkehren hilft nicht, da Sie die Verknüpfungen der benachbarten Knoten aktualisieren müssen.
Hier sind zwei Funktionen – eine für jede Aufgabe – die funktionieren:
void delete_first()
{
STUDENT *p = header;
if (p) {
if (p->nextStudent == NULL) {
header = ender = NULL;
} else {
p->nextStudent->prevStudent = NULL;
header = p->nextStudent;
}
free(p);
}
}
void delete_last()
{
STUDENT *p = ender;
if (p) {
if (p->prevStudent == NULL) {
header = ender = NULL;
} else {
p->prevStudent->nextStudent = NULL;
ender = p->prevStudent;
}
free(p);
}
}