C中的双向链表-删除节点函数

Question

双向链表节点是在主函数中创建的。定义了 Ender 和 header。在删除节点函数处中断 - ender 为空。

释放最后一个和第一个输入的内存的最佳方法是什么，即：删除：233，A和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);
    }
}   

Answer 1

您的删除函数使链接列表处于非法状态。在任何时候（除了暂时在插入和删除函数内），以下条件都必须正确：

• 如果 header 为空，则 ender 也必须为 null 并且列表为空。
• 如果一个节点 p 有一个非空链接 p->next, ， 然后 p->next->prev == p.
• 同样，如果一个节点 p 有一个非空链接 p->prev, ， 然后 p->prev->next == p.
• header没有前一个节点；End 没有下一个节点。

这些是链接列表的不变量。

如果您检查删除代码：

void deletenode()
{
    STUDENT *p = header, *q = ender;

    ender=ender->nextStudent;
    header=header->prevStudent;
    free(p); free(q);
}

你可以看到你刚刚设置了 header 和 ender 到 NULL, ，因为那就是 ender->nextStudent 和 header->prevStudent 是。但即使逆转也无济于事，因为您必须更新相邻节点的链接。

这里有两个有效的函数（每个任务一个）：

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);
    }
}