# Exercise on adding elements to a list

Tags:
1. Sep 9, 2016

### RaamGeneral

(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 --> //

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 --> //

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 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. Sep 14, 2016