Add ordered item recursively
Why am I getting segmentation fault in this code?
void inserord(Lint *li, int x, Lint *k){
if(((*li)->value) > x){
Lint New;
New = (Lint) calloc(1,sizeof(Nodo));
New->value= x;
New->next = (*li);
(*k)->next = New;
return;
}else if(*li == NULL){
return;
}
*k = *li;
inserord( &((*li)->next), x, &(*k));
}
The problem is when I do * k = * li, they are pointers of the same type as Lint.
This is the data structure:
typedef struct slist *Lint;
typedef struct slist {
int value;
Lint next;
} Nodo;
The idea, in * k, is to pass the previous node to the next recursive call, so I can bind this old structure to the new one and the new one to the new one.
EDIT:
this is the complete code:
typedef struct slist *Lint;
typedef struct slist {
int value;
Lint next;
} Nodo;
void inserord(Lint *li, int x, Lint *k){
if(((*li)->value) > x){
Lint New;
New = (Lint) calloc(1,sizeof(Nodo));
New->value= x;
New->next = (*li);
(*k)->next = New;
return;
}else if(*li == NULL){
return;
}
*k = *li;
inserord( &((*li)->next), x, &(*k));
}
void insertend(Lint *l, int x){
Lint new, aux;
new = (Lint) calloc(1,sizeof(Nodo));
new->value = x;
new->next = NULL;
if(*l==NULL){
*l=new;
return;
}
else
{
for(aux=*l; aux!=NULL ; aux = aux->next){
if(aux->next == NULL){
aux->next = new;
return;
}
}
}
}
int main(){
Lint listinha;
printf("\n");
insertend(&listinha, 1);
insertend(&listinha, 2);
insertend(&listinha, 3);
insertend(&listinha, 4);
insertend(&listinha, 5);
insertend(&listinha, 7);
listVal(&listinha);
Lint k = NULL;
inserord(&listinha, 4, &k);
listVal(&listinha);
return 0;
}
source to share
You can write the function more simply like this
Lint inserord( Lint li, int x )
{
if ( ( li == NULL ) || !( li->value < x ) )
{
Lint new_li = malloc( sizeof( Nodo ) );
new_li->value = x;
new_li->next = li;
return new_li;
}
li->next = inserord( li->next, x );
return li;
}
and call it like
Lint listinha = NULL; listinha = inserord( listinha, 1 );
If using your approach, then the function can be written as follows (I used my own variable names because it is easy for me)
#include <stdio.h>
#include <stdlib.h>
struct Nodo
{
int value;
struct Nodo *next;
};
void inserord( struct Nodo **current, int x, struct Nodo **prev )
{
if ( ( *current == NULL ) || !( ( *current )->value < x ) )
{
struct Nodo *nodo = malloc( sizeof( struct Nodo ) );
nodo->value = x;
nodo->next = *current;
if ( *prev == *current ) *current = nodo;
else ( *prev )->next = nodo;
return;
}
prev = current;
current = &( *current )->next;
inserord( current, x, prev );
}
void display( struct Nodo *current )
{
for ( ; current != NULL; current = current->next )
{
printf( "%d ", current->value );
}
}
int main(void)
{
struct Nodo *head = NULL;
for ( int i = 10; i != 0; ) inserord( &head, --i, &head );
display( head );
printf( "\n" );
return 0;
}
Program output
0 1 2 3 4 5 6 7 8 9
Or if you want to call it the third parameter, as a pointer to NULL, then the function might look like
void inserord( struct Nodo **current, int x, struct Nodo **prev )
{
if ( ( *current == NULL ) || !( ( *current )->value < x ) )
{
struct Nodo *nodo = malloc( sizeof( struct Nodo ) );
nodo->value = x;
nodo->next = *current;
if ( *prev == NULL ) *current = nodo;
// ^^^^^^^^^^^^^
else ( *prev )->next = nodo;
return;
}
prev = current;
current = &( *current )->next;
inserord( current, x, prev );
}
and be called like
struct Nodo *head = NULL;
struct Nodo *prev = NULL;
for ( int i = 10; i != 0; ) inserord( &head, --i, &prev );
source to share
An error can occur if * li is NULL. Indeed, you check it, but you only do it after the check ((*li)->value) > x)
, which will be expanded to (NULL->value > x)
, which will segfault.
What you need to do is just change the if / else if, for example:
void inserord(Lint *li, int x, Lint *k){
/* This check must be done before attempting any other attempt to dereference (*li) */
if(*li == NULL){
return;
}
else if(((*li)->value) > x){
Lint New;
New = (Lint) calloc(1,sizeof(Nodo));
New->value= x;
New->next = (*li);
(*k)->next = New;
return;
}
*k = *li;
inserord( &((*li)->next), x, &(*k));
}
Segfault can also occur when trying to access (*k)->next
, which will segfault if * k is NULL.
Please provide a main or some snippet where you actually call inserord with both declarations li
and k
.
source to share