Home > OS >  Delete a node(or more nodes) between others in a linked list C
Delete a node(or more nodes) between others in a linked list C

Time:02-10

Hi I'm creating a program for school where I have to:

  1. Create structures
  2. Create functions to print my linked list
  3. Create functions to insert an element to the bottom of the list
  4. Delete duplicate elements.

I created all a part the last one step(delete function). Can you help me to know what is the right way? This is my code:

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

/*STRUCTURE*/
typedef struct punto {
    int x;
    int y;
} PUNTO;

typedef struct quadrato {
    PUNTO v;
    int lato;
} QUADRATO;

typedef struct nodo {
    QUADRATO q;
    struct nodo *next;
} NODO;

/*PRINT LIST*/
void stampaQuadrato(QUADRATO q) {
    printf("The square has the side equal to %d and coordinates of the lower left vertex (%d,%d)\n", q.lato, q.v.x, q.v.y);
}

void stampaLista(NODO *head) {
    if(head->next==NULL) {
        printf("List empty!\n");
    } else {
        while(head->next != NULL) {
            head = head->next;
            stampaQuadrato(head->q);
        }
    }
}

/*ADD*/
QUADRATO creaQuadrato() {
    
    QUADRATO nuovo;
    
    printf("Side measurement: ");
    scanf("%d", &nuovo.lato);
    printf("\n");
    printf("Coordinates of the lower left vertex\n");
    printf("x: ");
    scanf("%d", &nuovo.v.x);
    printf("\n");
    printf("y: ");
    scanf("%d", &nuovo.v.y);
    printf("\n");
    
    return nuovo;
    
}

void insert(NODO *head) {
    NODO* nuovoNodo = malloc(sizeof(NODO));
    nuovoNodo->q = creaQuadrato();
    if(head==NULL) {
        head = head->next;
        head = nuovoNodo;
    } else {
        while(head->next != NULL) {
            head = head->next;
        }
        head->next = nuovoNodo;
    }
}

/*DELETE*/
void deleteDuplicates(NODO *head) {
    if(head==NULL) {
        printf("There are no element in the list!\n");
    } else {
        while(head->next != NULL) {
            if(head->q.lato == head->next->q.lato &&
               head->q.v.x == head->next->q.v.x &&
               head->q.v.y == head->next->q.v.y) {
                   NODO* nodoQuad = head->next;
                   head->next = nodoQuad->next;
                   //head->next = head->next->next;
                   free(nodoQuad);
                   printf("Element deleted!\n");
               } else {
                   head = head->next;
               }
        }
    }
}

int main() {
    NODO *head = malloc(sizeof(NODO));
    head->next = NULL;
    int scelta = -1;
    
    while(scelta != 0) {
        printf("Choose one\n");
        printf("Press 1 --> See list\n");
        printf("Press 2 --> Insert new square(quadrato)\n");
        printf("Press 3 --> Delete duplicates\n");
        printf("Press 0 --> Stop program\n");
        scanf("%d", &scelta);
        
        if(scelta==1) {
            stampaLista(head);
        }
        else if(scelta==2) {
            insert(head);
        }
        else if(scelta==3) {
            deleteDuplicates(head);
        }
        else if(scelta==0) {
            printf("See you soon ;)\n");
        }
        
        }
    
}

CodePudding user response:

For starters initially the list should be empty. So you have to write

NODO *head = NULL;

instead of

NODO *head = malloc(sizeof(NODO));

This while loop

int scelta = -1;

while(scelta != 0) {
    //...
}

should be substituted for do while loop as for example

do
{
    //...
} while ( scelta != 0 );

Within the do while loop instead of using if statements it is better to use switch statement as for example

do
{
    scelta = 0;

    printf("Choose one\n");
    printf("Press 1 --> See list\n");
    printf("Press 2 --> Insert new square(quadrato)\n");
    printf("Press 3 --> Delete duplicates\n");
    printf("Press 0 --> Stop program\n");
    scanf("%d", &scelta);
    
    enum { Exit = 0, Stampa = 1, Insert = 2, Delete = 3 };

    switch ( scelta )
    {
    case Exit:
        puts( "See you soon" );
        break;

    case Stampa:
        stampaLista( head );
        break;

    case Insert:
        insert( &head );
        break;

    case Delete:
        deleteDuplicates( head );
        break;

    case default:
        puts( "Invalid input. Try anew." );
        break;
    }
} while ( scelta != 0 );

The function insert is incorrect

void insert(NODO *head) {
    NODO* nuovoNodo = malloc(sizeof(NODO));
    nuovoNodo->q = creaQuadrato();
    if(head==NULL) {
        head = head->next;
        head = nuovoNodo;
    } else {
        while(head->next != NULL) {
            head = head->next;
        }
        head->next = nuovoNodo;
    }
}

because it does not change the original pointer head declared in main because it deals with a copy of the value of the passed pointer. Changing the copy does not influence on the original pointer.

Also you forgot to set the data member next to NULL of the created node.

The function can be declared and defined the following way

int insert( NODO **head ) 
{
    NODO *nuovoNodo = malloc( sizeof( NODO ) );
    int success = nuovoNodo != NULL;

    if success )
    {
        nuovoNodo->q = creaQuadrato();
        nuovoNodo->next = NULL;

        while ( *head != NULL ) head = &( *head )->next;

        *head = nuovoNodo;
    }

    return success;
}

The parameter of the function stampaLista should have the qualifier const

void stampaLista( const NODO *head ) 
{
    if ( head == NULL ) 
    {
        puts( "List empty!" );
    } 
    else 
    {
        for ( ; head != NULL; head = head->next )
        {
            stampaQuadrato( head->q );
        }
    }
}

As for the function deleteDuplicates then it removes only adjacent duplicated nodes. If you want to remove all duplicated nodes (not only adjacent) then the function can be defined the following way

void deleteDuplicates( NODO *head ) 
{
    if ( head == NULL ) 
    {
        puts( "There are no element in the list!" );
    } 
    else 
    {
        for ( ; head != NULL; head = head->next )
        {
            for ( NODO *current = head; current->next != NULL; )
            {
                if ( head->q.lato == current->next->q.lato &&
                     head->q.v.x  == current->next->q.v.x  &&
                     head->q.v.y  == current->next->q.v.y ) 
                {
                    NODO *nodoQuad = current->next;
                    current->next = nodoQuad->next;
                    free(nodoQuad);
                    puts( "Element deleted!" );
                } 
                else 
                {
                    current = current->next;
                }
            }
        }
    }
}

CodePudding user response:

You can do something like this:

    /* removeDuplicate() will remove duplicate nodes from the list */
void removeDuplicate(NODO *self) {
    /* Node current will point to head  */
    NODO *current = self->head;  
    NODO *index = NULL;  
    NODO *temp = NULL;  
          
    if(self->head == NULL) {
        return;
    } else {
        while(current != None) {
            /* Node temp will point to previous node to index */
            temp = current;  
            /* Index will point to node next to current */
            index = current->next;  
                  
            while(index != NULL) {
                /* If current node's data is equal to index node's data */
                if(current->data == index->data) {
                    /* Here, index node is pointing to the node which is duplicate of current node */
                    /* Skips the duplicate node by pointing to next node */
                    temp->next = index->next;  
                } else { 
                    /* Temp will point to the previous node of the index. */
                    temp = index;  
                }
                index = index->next;
            }
            current = current->next;
        }
    }
}

You need to write similar as above for your code's needs.

CodePudding user response:

I found a good function to delete duplicates also with the help of other users. This is the code:

void deleteDuplicates(NODO* head) {
        while(head != NULL && head->next != NULL) {
            NODO* nodoQuad = head;
            while(nodoQuad->next != NULL) {
            if(head->q.lato == nodoQuad->next->q.lato &&
               head->q.v.x == nodoQuad->next->q.v.x &&
               head->q.v.y == nodoQuad->next->q.v.y) {
                   NODO* dealloca = nodoQuad->next;
                   nodoQuad->next = nodoQuad->next->next
                   free(dealloca);
                   printf("Element deleted!\n");
               } else {
                   nodoQuad = nodoQuad->next;
               }
        }
        head = head->next;
        }
}
  • Related