- #1
RaamGeneral
- 50
- 1
(mentor note: moved here from another forum hence no template)
This is the code with also the explanation of the exercise. There is bit of italian, but everything is clear enough.
I actually solved the exercise.
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):
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.
This is the code with also the explanation of the exercise. There is bit of italian, but everything is clear enough.
I actually solved the exercise.
Code:
/*
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);
}
Code:
#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 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: