删除双向链表中的素数

Question

#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; //It is not a prime number.
    }
    else
    {
        return 1; //It is a prime number.
    }
}

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

这是我为此尝试过的代码。问题出在 delete_prime_function。当我运行它时，它会无限次打印随机值。我创建了一个 checkprime 函数，如果数字是素数，它将 return 1，如果数字不是素数，它将 return 0。然后在 delete_prime 函数中，每次检查条件 if((checkprime)==1)，如果为真则删除该节点，并且该过程将继续直到指针“p”到达 NULL . 我不知道我做错了什么。

编辑： 谢谢，我实现了@pmg 和@VladfromMoscow 指出的内容。这是工作代码。

#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; //It is not a prime number.
        }
        else
        {
            return 1; //It is a prime number.
        }
    }  
}

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

再次感谢:)

Answer 1

想象一下这个 3 节点列表：

NULL==p   /<==p   /<==p
      NODE    NODE    NODE
         n==>/   n==>/   n==NULL

当您删除此列表中的第二个节点时，您想要获得

NULL==p   /<==========p             // changed prev link in 3rd node
      NODE    ----    NODE          // deleted 2nd node
         n==========>/   n==NULL    // changed next link in 1st node

但是你的代码得到了这个

NULL==p    ----   /<==p             // prev links to deleted node
      NODE    ----    NODE
         n==>/   ----    n==NULL    // next links to deleted node

注意列表中第一个和最后一个节点的特殊情况。

Answer 2

您对列表的实现不正确，许多函数可以调用未定义的行为。

对于初学者来说，函数不应依赖于全局变量head。在这种情况下，一个程序不能同时使用两个列表。

函数 length 调用未定义的行为，因为局部变量 len 未初始化。

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

你需要写

    int len = 0;

在此代码段中的函数中插入

    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;

你没有检查 p 是否等于 NULL。例如，如果列表为空，即 head 是一个空指针，并且用户指定 index 等于 1，那么 p 也将是一个空指针。因此，在表达式中使用它，例如 p->next 会调用未定义的行为。

函数checkprime也不正确。由于 if 语句

，它表明数字 0、1 和所有奇数都是素数

    if(n % 2 == 0)
    {
        prime = 0;
        break;
    }

不会获得此类数字的控制权。

所以首先你必须在编写函数之前正确地编写列表（将 head 声明为局部变量）和所有提到的函数 delete_prime_number 这自然也不正确，因为至少它不会改变指针当指向的节点包含质数时为头。

至于函数delete_prime_number本身那么可以定义如下wat

void delete_prime_number( struct node **head )
{
    while ( *head != NULL )
    {
        if ( checkprime( ( *head )->data ) )
        {
            struct node *tmp = *head;

            if ( ( *head )->next != NULL )
            {
                ( *head )->next->prev = ( *head )->prev;
            }
            
            *head = ( *head )->next;
             
            free( tmp );
        }
        else
        {
            head = &( *head )->next;
        }
    }
}

可以这样称呼

delete_prime_number( &head );

删除双向链表中的素数

Delete a prime number in a doubly linked list

c

primes

linked-list

doubly-linked-list

function-definition