1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Exercise on adding elements to a list

  1. Sep 9, 2016 #1
    (mentor note: moved here from another forum hence no template)

    This is the code with also the explaination of the exercise. There is bit of italian, but everything is clear enough.
    I actually solved the exercise.

    Code (Text):

    /*

    Add an element of value n before each element of the list that satisfies the property P. count the elements added (return value). this function is recursive.

    example:
    l: 1 --> 1 --> -1 --> 2 --> -5 --> -4 --> -6 --> 3 --> 0 --> 5 --> //
    n=21
    P(n) is n>0
    result: 21 --> 1 --> 21 --> 1 --> -1 --> 21 --> 2 --> -5 --> -4 --> -6 --> 21 --> 3 --> 0 --> 21 --> 5 --> //
    number of items added: 5

    my approach:
    if (the second element of the list is P) then: add n between the first and the second, repeat with the sublist starting now by "second" (e->next, that now is actually the third...).
    else repeat with the sublist starting now by the second

    problem: I can't test the first element of the list. so I use a static variable to consider the "first call" of the funcion

    */
    int esercizio_2(Lista *l,int n)
    {
        static int i=0;
     
        ElementoLista *e;
     
        //list is empty
        if((*l)==NULL) {return 0;}
     
        //last call: reset i.
        if((*l)->next==NULL) {i=0;return 0;}
     
        //first call
        if(i==0){
         
            i=1;
         
            //first element satisfies P
            if(P(&((*l)->info))){
             
                //I add n before the first element
                e=malloc(sizeof(ElementoLista)); e->info=n; e->next=(*l);
                *l=e;
             
                //I count this element added, do the same thing to the sublist, the same as the initial list
                return 1+esercizio_2(&(e->next),n);
             
            }
        }
     
        //element satisfies P
        if(P(&((*l)->next->info))){
         
            //add n between the current element end the next
            e=malloc(sizeof(ElementoLista)); e->info=n; e->next=(*l)->next;
            (*l)->next=e;
         
            //I count this element added, do the same thing to the list starting by the next element
            return 1+esercizio_2(&(e->next),n);
         
        }
     
        //element does not satisfy P; do the same thing to the list starting by the next element
        return esercizio_2(&((*l)->next),n);
     
    }


     

    This is the entire code if you want to try (something is missing but it works; note the P takes a pointer as a parameter):

    Code (Text):

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

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

    typedef struct El ElementoLista;
    typedef ElementoLista *Lista;


    void lista_init(Lista *l);
    void lista_insert(Lista *l,int n);
    void lista_insert_array(Lista *l,int *v,int size);
    void lista_print(Lista l);



    int P(int *n);
    int esercizio_2(Lista *l,int n);



    int main(int argc,char **argv)
    {
     
        Lista l;
        int arr[]={1,1,-1,2,-5,-4,-6,3,-0,5};
        int r;
     
        lista_init(&l);
        lista_insert_array(&l,arr,10);
        lista_print(l);
     
        r=esercizio_2(&l,21);
     
        printf("%d\n",r);
        lista_print(l);
     
        return 0;
    }




    int P(int *n)
    {
        return *n>0;
    }

    /*

    Add an element of value n before each element of the list l that satisfies the property P. count the elements added (return value). this function is recursive.

    example:
    l: 1 --> 1 --> -1 --> 2 --> -5 --> -4 --> -6 --> 3 --> 0 --> 5 --> //
    n=21
    P(n) is n>0
    result: 21 --> 1 --> 21 --> 1 --> -1 --> 21 --> 2 --> -5 --> -4 --> -6 --> 21 --> 3 --> 0 --> 21 --> 5 --> //
    number of items added: 5

    my approach:
    if (the second element of the list is P) then: add n between the first and the second, repeat with the sublist starting now by "second" (e->next, that now is actually the third...).
    else repeat with the sublist starting now by the second

    problem: I can't test the first element of the list. so I use a static variable to consider the "first call" of the funcion

    */
    int esercizio_2(Lista *l,int n)
    {
        static int i=0;
     
        ElementoLista *e;
     
        //list is empty
        if((*l)==NULL) {return 0;}
     
        //last call: reset i.
        if((*l)->next==NULL) {i=0;return 0;}
     
        //first call
        if(i==0){
         
            i=1;
         
            //first element satisfies P
            if(P(&((*l)->info))){
             
                //I add n before the first element
                e=malloc(sizeof(ElementoLista)); e->info=n; e->next=(*l);
                *l=e;
             
                //I count this element added, do the same thing to the sublist, the same as the initial list
                return 1+esercizio_2(&(e->next),n);
             
            }
        }
     
        //element satisfies P
        if(P(&((*l)->next->info))){
         
            //add n between the current element end the next
            e=malloc(sizeof(ElementoLista)); e->info=n; e->next=(*l)->next;
            (*l)->next=e;
         
            //I count this element added, do the same thing to the list starting by the next element
            return 1+esercizio_2(&(e->next),n);
         
        }
     
        //element does not satisfy P; do the same thing to the list starting by the next element
        return esercizio_2(&((*l)->next),n);
     
    }




    void lista_init(Lista *l)
    {
        *l=NULL;
    }

    void lista_insert(Lista *l,int n)
    {
        if(*l==NULL){  
            *l=malloc(sizeof(ElementoLista));
            (*l)->info=n;
            (*l)->next=NULL;
            return;
        }
     
        lista_insert(&((*l)->next),n);
     
     
     
    }

    void lista_insert_array(Lista *l,int *v,int size)
    {
        int i;
     
        for(i=0;i<size;i++) lista_insert(l,v[i]);
     
    }

    void lista_print(Lista l)
    {
        while(l!=NULL){
            printf(" %d -->",l->info);
            l=l->next;
        }
        printf(" //\n");
     
    }

     

    I have a couple of questions: is there a better (recursive) algorithm to solve this exercise?
    I don't like things like &((*l)->next. What can I do about this?
    I once tried assigning *l to a variable, but I remember something didn't work.

    Thank you.
     
    Last edited by a moderator: Sep 9, 2016
  2. jcsd
  3. Sep 14, 2016 #2
    Thanks for the thread! This is an automated courtesy bump. Sorry you aren't generating responses at the moment. Do you have any further information, come to any new conclusions or is it possible to reword the post? The more details the better.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Exercise on adding elements to a list
  1. Adding phasors (Replies: 3)

  2. Linux listing (Replies: 7)

  3. Matlab exercises (Replies: 1)

Loading...