Search code examples
clistlinked-listcircular-list

Append an element to the end of a Circular Linked List with this particular function

I'll try to be as clear as I can.

I have this struct (and I can't change it because of my teachers) in a file called "esercizio.h":

#ifndef ESERCIZIO_H
#define ESERCIZIO_H

struct ElemSCL{
    int info;
    struct ElemSCL* next;
};

typedef struct ElemSCL NodoSCL;
typedef NodoSCL* TipoSCL;

void accoda(TipoSCL* pscl, int i);
#endif

The function "accoda" must add an element (int i) to the end of a circular linked list (pointed by TipoSCL* pscl). I have tried to write the function body in a file called "esercizio.c":

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

void accoda(TipoSCL* pscl, int i){
    NodoSCL* temp = (NodoSCL*) malloc(sizeof(NodoSCL));
    temp->info = i;
    temp->next = temp;
    if (pscl == NULL){
        return;}
    while ((*pscl)->next != *pscl){
        *pscl = (*pscl)->next;}
    (*temp)->next = (*pscl)->next; //Problems starts here
    (*pscl)->next = *temp;
    }

As I let you notice in my code, everything is ok if I don't add the lasts two rows. If in the function there was not TypeSCL* but NodeSCL* I would use:

temp->next = pscl->next;
pscl->next = temp;}

But my teacher decided to use TypeSCL* pscl instead of NodeSCL* pscl.

I have a "test.h" file...

#include "esercizio.h"

#ifndef TEST_H
#define TEST_H

char* toString(TipoSCL scl);

#endif

... and a "test.c" file, with the main() function and all the inputs which let me check if my code is working:

#include <stdlib.h>
#include <string.h>
#include "../libtest/libtest.h"
#include "test.h"
#include "esercizio.h"


const int NTEST=5;

TipoSCL input[5];
int add[5] = {1,2,3,4,5};
TipoSCL expected[5];


int main(int argc, char** argv){


    input[0] = NULL;

    input[1] = (TipoSCL) malloc(sizeof(NodoSCL));
    input[1] -> info = 1;
    input[1] -> next = input[1];

    input[2] = (TipoSCL) malloc(sizeof(NodoSCL));
    input[2] -> info = 1;
    input[2] -> next = (TipoSCL) malloc(sizeof(NodoSCL));
    input[2] -> next -> info = 2;
    input[2] -> next -> next = input[2];

    input[3] = (TipoSCL) malloc(sizeof(NodoSCL));
    input[3] -> info = 1;
    input[3] -> next = (TipoSCL) malloc(sizeof(NodoSCL));
    input[3] -> next -> info = 2;
    input[3] -> next -> next = (TipoSCL) malloc(sizeof(NodoSCL));
    input[3] -> next -> next -> info = 3;
    input[3] -> next -> next -> next = input[3];

    input[4] = (TipoSCL) malloc(sizeof(NodoSCL));
    input[4] -> info = 1;
    input[4] -> next = (TipoSCL) malloc(sizeof(NodoSCL));
    input[4] -> next -> info = 2;
    input[4] -> next -> next = (TipoSCL) malloc(sizeof(NodoSCL));
    input[4] -> next -> next -> info = 3;
    input[4] -> next -> next -> next = (TipoSCL) malloc(sizeof(NodoSCL));
    input[4] -> next -> next -> next -> info = 4;
    input[4] -> next -> next -> next -> next = input[4];

    expected[0] = (TipoSCL) malloc(sizeof(NodoSCL));
    expected[0] -> info = 1;
    expected[0] -> next = expected[0];

    expected[1] = (TipoSCL) malloc(sizeof(NodoSCL));
    expected[1] -> info = 1;
    expected[1] -> next = (TipoSCL) malloc(sizeof(NodoSCL));
    expected[1] -> next -> info = 2;
    expected[1] -> next -> next = expected[1];

    expected[2] = (TipoSCL) malloc(sizeof(NodoSCL));
    expected[2] -> info = 1;
    expected[2] -> next = (TipoSCL) malloc(sizeof(NodoSCL));
    expected[2] -> next -> info = 2;
    expected[2] -> next -> next = (TipoSCL) malloc(sizeof(NodoSCL));
    expected[2] -> next -> next -> info = 3;
    expected[2] -> next -> next -> next = expected[2];

    expected[3] = (TipoSCL) malloc(sizeof(NodoSCL));
    expected[3] -> info = 1;
    expected[3] -> next = (TipoSCL) malloc(sizeof(NodoSCL));
    expected[3] -> next -> info = 2;
    expected[3] -> next -> next = (TipoSCL) malloc(sizeof(NodoSCL));
    expected[3] -> next -> next -> info = 3;
    expected[3] -> next -> next -> next = (TipoSCL) malloc(sizeof(NodoSCL));
    expected[3] -> next -> next -> next -> info = 4;
    expected[3] -> next -> next -> next -> next = expected[3];

    expected[4] = (TipoSCL) malloc(sizeof(NodoSCL));
    expected[4] -> info = 1;
    expected[4] -> next = (TipoSCL) malloc(sizeof(NodoSCL));
    expected[4] -> next -> info = 2;
    expected[4] -> next -> next = (TipoSCL) malloc(sizeof(NodoSCL));
    expected[4] -> next -> next -> info = 3;
    expected[4] -> next -> next -> next = (TipoSCL) malloc(sizeof(NodoSCL));
    expected[4] -> next -> next -> next -> info = 4;
    expected[4] -> next -> next -> next -> next = (TipoSCL) malloc(sizeof(NodoSCL));
    expected[4] -> next -> next -> next -> next -> info = 5;
    expected[4] -> next -> next -> next -> next  -> next = expected[4];




    test_reset();

    for (int i = 0; i < NTEST; i++) {
        print_test_start(i+1);
        printf("Funzione: accoda\n");
        printf("Input: %s\n", toString(input[i]));

        accoda(&input[i],add[i]);

        test_compare_strings(toString(expected[i]),toString(input[i]));

        print_test_end();
        print_n_success("#Test superati: ");
    }
    print_test_result("Percentuale test corretti:");
}


char* toString(TipoSCL scl){
    char* res = (char*) malloc(200*sizeof(char));
    res[0] = '[';
    res[1] = '\0';
    TipoSCL aux = scl;
    if (aux != NULL) {
        char buf[10];
        do{
            sprintf(buf,"%d->",aux -> info);
            strcat(res,buf);
            aux = aux -> next;
        }
        while(aux != scl);
        sprintf(buf,"|%d",aux -> info);
        strcat(res,buf);
        aux = aux -> next;
    }
    strcat(res,"]");
    return res;
}

What I mean with "everything is ok if I don't add the lasts two rows" to my code? When I run my program (thanks to terminal and cd and make ) without

(*temp)->next = (*pscl)->next; //Problems starts here
(*pscl)->next = *temp;

the test run without problem (but of course, it say me that I have no one right result. But if I add this two rows to my code, I got "Segmentation fault: 11".

Solution

  • Try changing your add function to this ::

    void add(TypeSCL* pscl, int i){
    NodeSCL* temp = (NodeSCL*) malloc(sizeof(NodeSCL));
    temp->info = i;
    temp->next = temp;
    if (*pscl == NULL){
    *pscl = temp;
        return;} 
    NodeSCL *tempCheck = *pscl;
    while(tempCheck->next != *pscl) {
        tempCheck = tempCheck->next;
    }
    tempCheck->next = temp;
    temp->next = (*pscl); 
}

    Things you do wrong :: You need to realize everything in C is passed by value, so if you pass a pointer, that pointer is also passed by value. So, when you teacher tells you to use TypeSCL* pscl it means NodeSCL **pscl, and she is right, because you cannot do it with NodeSCL *pscl, this might help you understand why I say this :: What is the reason for using a double pointer when adding a node in a linked list?

    Further, in your case when pscl == NULL first it should be *pscl == NULL you need to set your *pscl to you new node.

    Next, if you want to add a new node at the end, you shall use a while loop, as mentioned by @Neha Chauhan.

    Next, the last two statements that you used ::

    (*temp)->next = (*pscl)->next;
(*pscl)->next = *temp;

    You are setting the next of your newly added node to the 2nd element of you linked list, which doesn't make any sense.

    I have used the variable NodeSCL *tempCheck to move to the last node of the linked list!

    So, the last 2 lines shall look like 

    tempCheck->next = temp;
temp->next = (*pscl);

    Lastly, bro you need to work up on your basics with pointers. (Don't Mind!)

    EDIT::

    Why your test works without the last 2 lines :: Because, with the code you have written, your linked list is always of size 1, no elements are added after the first element! So, the test runs, but it fails!