Inserting a new node in an ordered linked list

F

francesco

This code doesn't always work, only in some cases, else, it gives me
segmentation fault. It has to insert a new node in a linked list
maintaining an ascending order

struct persona *inserimento_ordinato(struct persona *testa, struct
persona pers){
struct persona *p=NULL, *prec=NULL, *corrente=NULL;
prec=testa;
corrente=testa;
if(corrente==NULL || strcmp(corrente->cognome,pers.cognome)>=0)
{
testa=inserisci_contatto(testa,pers);
printf("\n Primo nodo della lista: testa");
}
else {
while(corrente!=NULL && strcmp(corrente->cognome,pers.cognome)<0){
prec=corrente;
corrente=corrente->next;
printf("prec %p corrente %p corrente->next %p
\n",prec,corrente,corrente->next);
}
p=crea_contatto(pers);// Crea un nuovo nodo da aggiungere alla
lista, nel posto opportuno, per mantenere l'ordinamento
p->next=corrente;
prec->next=p;
printf("\n Inserimento tra due nodi %s e %s",prec->cognome,corrente-
cognome);
stampa_rubrica(testa);
}
return testa;
}
 
H

Hans Vlems

This code doesn't always work, only in some cases, else, it gives me
segmentation fault. It has to insert a new node in a linked list
maintaining an ascending order

struct persona *inserimento_ordinato(struct persona *testa, struct
persona pers){
struct persona *p=NULL, *prec=NULL, *corrente=NULL;
 prec=testa;
 corrente=testa;
 if(corrente==NULL || strcmp(corrente->cognome,pers.cognome)>=0)
 {
   testa=inserisci_contatto(testa,pers);
  printf("\n Primo nodo della lista: testa");}

else {  
  while(corrente!=NULL && strcmp(corrente->cognome,pers.cognome)<0){
        prec=corrente;
        corrente=corrente->next;
        printf("prec %p corrente %p corrente->next %p
\n",prec,corrente,corrente->next);
      }
      p=crea_contatto(pers);// Crea un nuovo nodo da aggiungere alla
lista, nel posto opportuno, per mantenere l'ordinamento
      p->next=corrente;  
      prec->next=p;
      printf("\n Inserimento tra due nodi %s e %s",prec->cognome,corrente->cognome);

      stampa_rubrica(testa);



}
return testa;
}- Tekst uit oorspronkelijk bericht niet weergeven -

- Tekst uit oorspronkelijk bericht weergeven -

Under what conditions does it work and when does it fail?
Hans
 
I

Ike Naar

This code doesn't always work, only in some cases, else, it gives me
segmentation fault. It has to insert a new node in a linked list
maintaining an ascending order

struct persona *inserimento_ordinato(struct persona *testa, struct
persona pers){
struct persona *p=NULL, *prec=NULL, *corrente=NULL;
prec=testa;
corrente=testa;
if(corrente==NULL || strcmp(corrente->cognome,pers.cognome)>=0)
{
testa=inserisci_contatto(testa,pers);
printf("\n Primo nodo della lista: testa");
}
else {
while(corrente!=NULL && strcmp(corrente->cognome,pers.cognome)<0){
prec=corrente;
corrente=corrente->next;
printf("prec %p corrente %p corrente->next %p
\n",prec,corrente,corrente->next);
}

The above loop may terminate with corrente==NULL; see below.
p=crea_contatto(pers);// Crea un nuovo nodo da aggiungere alla
lista, nel posto opportuno, per mantenere l'ordinamento
p->next=corrente;
prec->next=p;
printf("\n Inserimento tra due nodi %s e %s",prec->cognome,corrente-

If the loop terminated with corrente==NULL, evaluation of
corrente->cognome is not allowed.
 
F

francesco

printf("prec %p corrente %p corrente->next %p
The above loop may terminate with corrente==NULL; see below.

Yes, you are right, I removed that line, and the program works now! Thank
you

Francesco
 
B

Ben Bacarisse

Richard said:
The run it in a debugger and see for your self in about 2 seconds.

Piggybacking (I doubt Richard is interested, but the others might be...)
so this is really for the OP.

There is another technique that can be even faster than using a
debugger. Every time you write a loop (it helps that C's for loops are
almost while loops in disguise) negate the condition and check that the
code that follows makes sense with this negated condition. You can do a
similar thing with ifs and elses, but it's most helpful with a while.

Your loop was

while (corrente != NULL && strcmp(corrente->cognome,pers.cognome) < 0)

so afterwards you can be sure that, if it terminates at all, you know
that

corrente is NULL or strcmp(corrente->cognome,pers.cognome) >= 0

is true. People who use formal methods will scoff at this because C has
all kinds of features (expressions with side-effects, short-circuit
logical operators) that makes the details very much more complex than
this, but I can't tell you how many times this simple piece of reasoning
has caught a miss-understanding before it became a bug. I do it every
single time I write a loop and I'll bet lots of other people do too. I
suggest it because many people learn programming without this ever
being suggested to them (or so it seems).

You can go a step further and check that the body of the loop always
does something that helps to bring the negation of the condition about.
This is harder because you have to test more complex ideas in your head
but the gain is greater. It can catch bugs that you might never test
for and so there may never a test case to debug. Can you (the OP) think
of such a problem for you loop?
 
G

Gene

This code doesn't always work, only in some cases, else, it gives me
segmentation fault. It has to insert a new node in a linked list
maintaining an ascending order

struct persona *inserimento_ordinato(struct persona *testa, struct
persona pers){
struct persona *p=NULL, *prec=NULL, *corrente=NULL;
 prec=testa;
 corrente=testa;
 if(corrente==NULL || strcmp(corrente->cognome,pers.cognome)>=0)
 {
   testa=inserisci_contatto(testa,pers);
  printf("\n Primo nodo della lista: testa");}

else {  
  while(corrente!=NULL && strcmp(corrente->cognome,pers.cognome)<0){
        prec=corrente;
        corrente=corrente->next;
        printf("prec %p corrente %p corrente->next %p
\n",prec,corrente,corrente->next);
      }
      p=crea_contatto(pers);// Crea un nuovo nodo da aggiungere alla
lista, nel posto opportuno, per mantenere l'ordinamento
      p->next=corrente;  
      prec->next=p;
      printf("\n Inserimento tra due nodi %s e %s",prec->cognome,corrente->cognome);

      stampa_rubrica(testa);
}
return testa;
}

FWIW and IMO, the lead+trail pointer idiom below is easy to envision,
so hard to get wrong:

LIST_NODE *head, *to_insert, *lead, *trail,;

... head is the list head and to_insert the new node

// Iterate lead and trail pointers to bracket the insertion point.
for (trail = NULL, lead = head; lead != NULL; trail = lead, lead =
lead->next)
if ( ... lead is just past insert point ... )
break;
// Insert either within list or at head of list.
if (trail)
trail->next = to_insert;
else
head = to_insert;
to_insert->next = lead;
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Singly Linked List in C 62
A doubly linked-list in C 216
Stack using doubly linked list 1
Problem with linked list and strings 0
Doubly linked list 6
linked list 8
My linked list 38
Linked list, no out put,help 8

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top