i have this recursive function:
struct singly* SetMinusRec(struct singly* shead1, struct singly* shead2){
struct singly* s2end;
s2end = shead2;
if(shead1 == NULL){
return NULL;
}else{
while(s2end != NULL && shead1->id < s2end->id){
s2end = s2end->next;
}
struct singly* new = (struct singly*)malloc(sizeof(struct singly));
if(shead1->id == s2end->id){
/* How can i not add this to the list, but just move on to the next node? */
}
printf("-%d %d-\n", shead1->id, s2end->id);
new->id = shead1->id;
new->next = SetMinusRec(shead1->next, shead2);
return new;
}
}
Basically, shead2 is sorted with decreasing order, and shead1 with increasing, and i want to create a new list, which has the elements of shead1 that dont exist in shead2. What am i supposed to do when they have the same id? How can i move on to the next node?
Thanks a lot.
CodePudding user response:
This memory allocation
struct singly* new = (struct singly*)malloc(sizeof(struct singly));
can produce a memory leak if shead1->id == s2end->id
.
On the other hand, if memory will not be allocated due to the equation and the pointer new
will be set to NULL
then this statement
new->next = SetMinusRec(shead1->next, shead2);
will invoke undefined behavior.
Also this if statement
if(shead1->id == s2end->id){
and this test output
printf("-%d %d-\n", shead1->id, s2end->id);
again can invoke undefined behavior if after the while loop the pointer s2end
is equal to NULL
.
The function can be declared and defined the following way
struct singly * SetMinusRec( const struct singly *shead1, const struct singly *shead2 )
{
struct singly *shead = NULL;
if ( shead1 != NULL )
{
const struct singly *current = shead2;
while ( current != NULL && shead1->id < current->id )
{
current = current->next;
}
if ( current == NULL || current->id < shead1->id )
{
shead = malloc( sizeof( struct singly ) );
shead->id = shead1->id;
shead->next = SetMinusRec( shead1->next, shead2 );
}
else
{
shead = SetMinusRec( shead1->next, shead2 );
}
}
return shead;
}