C语言删除双向链表素数时无限输出随机值问题及修复

双向链表删除素数节点问题 #

我实现了一个双向链表，想要删除链表中所有值为素数的节点，但是运行代码时会无限输出随机值，问题出在删除素数的函数中，我自己找不到错误原因。

原始错误代码 #

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

struct node 
{
    int data;
    struct node *next;
    struct node *prev;
}*head=NULL;

int length(struct node *p)
{
    int len;
    while(p!=NULL)
    {
        len++;
        p = p->next;
    }
    return len;
}

void display(struct node *p)
{
    if(p == NULL)
    {
        printf("Linked List is empty\n");
    }
    else
    {
        printf("Linked List: ");
        while(p!=NULL)
        {
            printf("%d ", p->data);
            p = p->next;
        }
    }
}

void insert(struct node *p, int index, int x)
{
    struct node *t;
    if(index == 0)
    {
        t = (struct node *)malloc(sizeof(struct node));
        t->data = x;
        t->next = head;
        t->prev = NULL;
        if(head != NULL)
        {
            head->prev = t;
        }
        head = t;
    }
    else
    {
        t = (struct node *)malloc(sizeof(struct node));
        t->data = x;

        for(int i=0; i<index-1; i++)
        {
            p = p->next;
        }
        t->prev = p;
        t->next = p->next;
        if(p->next != NULL)
        {
            p->next->prev = t;
        }
        p->next = t;
    }
}

int checkprime(int n)
{
    int prime = 1;
    for(int i=2; i<n; i++)
    {
        if(n % 2 == 0)
        {
            prime = 0;
            break;
        }
    }
    if(prime == 0)
    {
        return 0; //非素数
    }
    else
    {
        return 1; //素数
    }
}

void delete_prime_number(struct node *p)
{
    struct node *q;
    while(p != NULL)
    {
        q = p;
        p = p->next;
        if((checkprime(q->data)) == 1)
        {
            free(q);
        }
    }
}

int main()
{
    insert(head, 0, 2);
    insert(head, 1, 3);
    insert(head, 2, 4);
    insert(head, 3, 7);
    insert(head, 4, 8);
    insert(head, 5, 12);
    insert(head, 6, 15);
    insert(head, 7, 23);
    display(head);
    delete_prime_number(head);
    display(head);
    return 0;
}

核心错误原因 #

• 删除节点时仅释放了对应内存，没有调整前后节点的prev和next指针关联，导致链表出现大量野指针，遍历时访问已释放的内存就会输出随机值
• 未处理头节点是素数的场景，头节点被释放后没有更新头指针指向，整个链表结构完全混乱
• checkprime函数逻辑错误：判断条件写死为n%2==0，只能过滤偶数，所有奇数都会被误判为素数；同时没有处理n小于2的边界情况
• length函数中计数变量len未初始化，返回的长度为随机垃圾值

修复后可运行代码 #

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

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

int length(struct node *p)
{
    int len = 0;
    while (p != NULL)
    {
        len++;
        p = p->next;
    }
    return len;
}

void display(struct node *p)
{
    if (p == NULL)
    {
        printf("Linked List is empty\n");
    }
    else
    {
        printf("Linked List: ");
        while (p != NULL)
        {
            printf("%d ", p->data);
            p = p->next;
        }
    }
}

void insert(struct node **p, int index, int x)
{
    struct node *t;
    
    if (index == 0)
    {
        t = (struct node *)malloc(sizeof(struct node));
        t->data = x;
        t->next = *p;
        t->prev = NULL;
        if ((*p) != NULL)
        {
            (*p)->prev = t;
        }
        (*p) = t;
    }
    else
    {
        t = (struct node *)malloc(sizeof(struct node));
        t->data = x;
        for (int i = 0; i < index - 1; i++)
        {
            if((*p) == NULL)
            {
                printf("Linked List is empty!\n");
            }
            else
            {
                p = &(*p)->next;
            }    
        }
        t->prev = (*p);
        t->next = (*p)->next;
        if ((*p)->next != NULL)
        {
            (*p)->next->prev = t;
        }
        (*p)->next = t;
    }
}

int checkprime(int n)
{
    int prime = 1;
    if(n == 0 || n == 1)
    {
        return 0;
    }
    else
    {
        for (int i = 2; i < n; i++)
        {
            if (n % i == 0)
            {
                prime = 0;
                break;
            }
        }
        if (prime == 0)
        {
            return 0; //非素数
        }
        else
        {
            return 1; //素数
        }
    }  
}

void delete_prime_number(struct node **p)
{
    while (*p != NULL)
    {
        if (checkprime((*p)->data) == 1)
        {
            struct node *q = *p;
            if ((*p)->next != NULL)
            {
                (*p)->next->prev = (*p)->prev;
            }
            *p = (*p)->next;
            free(q);
        }
        else
        {
            p = &(*p)->next;
        }
    }
}

int main()
{
    struct node *head = NULL;
    insert(&head, 0, 2);
    insert(&head, 1, 3);
    insert(&head, 2, 4);
    insert(&head, 3, 7);
    insert(&head, 4, 8);
    insert(&head, 5, 12);
    insert(&head, 6, 15);
    insert(&head, 7, 23);
    display(head);
    delete_prime_number(&head);
    printf("\n");
    display(head);
    return 0;
}

内容的提问来源于stack exchange，提问作者ranger