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

This is the code I have tried for this. The problem is in the delete_prime_function. When I run it, it prints random values unlimited times. I created a checkprime function which will return 1 if the number is prime and return 0 if the number is not prime. Then in the delete_prime function, each time it would check the condition if((checkprime)==1), and if its true it would delete that node, and the process would go on until pointer "p" reaches NULL. I'm not getting where I am doing it wrong.

CodePudding user response：

Imagine this 3 nodes list:

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

When you remove the 2nd node in this list you want to get

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

But your code is getting this

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

Beware the special cases of the first and last nodes in the list.

CodePudding user response：

Your implementation of the list is incorrect and many functions can invoke undefined behavior.

For starters the functions shall not rely on the global variable head. In this case a program for example can not use two lists simultaneously.

The function length invokes undefined behavior because the local variable len is not initialized.

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

You need to write

    int len = 0;

In the function insert in this code snippet

    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;

you do not check whether p is equal to NULL. For example if the list is empty that is head is a null pointer and the user specified index equal to 1 then p also will be a null pointer. So using it in expressions like for example this p->next invokes undefined behavior.

The function checkprime is also incorrect. It shows that numbers 0, 1 and all odd numbers are prime numbers due to the if statement

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

that will not get the control for such numbers.

So at first you have to write the list (declaring head as a local variable) and all the mentioned functions correctly before writing the function delete_prime_number which naturally also incorrect because at least it does not change the pointer head when the pointed node contains a prime number.

As for the function delete_prime_number itself then it can be defined the following 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;
        }
    }
}

and can be called like

delete_prime_number( &head );