[C] Aggiunta nodo sentinella in lista lineare...ma come??

[Piojolopez2406]

Salve ragazzi ho fatto un programmino che gestisce una lista lineare senza nodo sentinella, ora vorrei inserire il nodo sentinella così da poter eliminare 1 function di inserimento ed 1 di eliminazione, ma non riesco propria capire cosa devo fare per creare sto nodo sentinella, mi dareste una mano...???


#include<stdio.h>
#include<stdlib.h>
#include<string.h>



/* Strutture autoriferente dinamica */
typedef struct {
char nome[20];
short age;
} INFO_FIELD;



/* Prototipi di funzione */
char *crea_lista();
void insert_testa(short, INFO_FIELD *, void **);
void insert_nodo(short, INFO_FIELD *, void **);
void delete_testa(void **);
void delete_nodo(void **);
INFO_FIELD legge_infonodo(struct PERSONA **);
void visualizza_lista(void **);
void messaggio_errore();

void main()
{
struct PERSONA {
INFO_FIELD info;
struct PERSONA *p_next;
};


struct PERSONA *head, *punt;
short scelta, n;
INFO_FIELD dato;


head = (struct PERSONA *) crea_lista();

do {
printf("QUESTO PROGRAMMA GESTISCE UNA LISTA GENERICA\n\n");
puts("[1] Aggiungi elemento nella lista");
puts("[2] Elimina elemento dalla lista");
puts("[3] Visualizza lista");
puts("[0] Esci dal programma");

printf("\nscelta: ");
scanf("%hd", &scelta);

switch(scelta) {
case 1:
printf("\n\nA G G I U N G I E L E M E N T O\n\n");
fflush(stdin);
printf("Inserire nome: ");
gets(dato.nome);
printf("Inserire eta': ");
scanf("%hd", &dato.age);

do {
puts("\n[ 1 ] Inserimento in testa alla lista");
puts("[ 2 ] Inserimento dopo nodo corrente (solo se la lista non e' vuota)");
printf("\nscelta: ");
scanf("%hd", &n);
} while (!(scelta == 1 || scelta == 2));


if(n == 1) {
insert_testa(sizeof(dato), &dato, &head);
punt = head;
}
else
insert_nodo(sizeof(dato), &dato, &punt);
printf("\n\n");
break;

case 2:
printf("\n\nE L I M I N A E L E M E N T O\n\n");
do {
puts("\n[1] Elimina nodo di testa");
puts("[2] Elimina nodo successore al nodo corrente");
printf("\nscelta: ");
scanf("%hd", &n);
switch(n) {
case 1:
delete_testa(&head);
break;
case 2:
delete_nodo(&punt);
break;
default:;
}

} while (!(scelta == 1 || scelta == 2));
case 3:
printf("\n\nVISUALIZZA LISTA\n\n");
visualizza_lista(&head);
printf("\n\n");
break;
}
} while(scelta != 0);
}


/*
* Questa function inizializza il nodo di testa della la lista lineare
*/
char *crea_lista()
{
char *testa;

testa = NULL;
return testa;
}


/*
* Questa function inserisce un nodo in testa ad una lista lineare.
* Prende in input la dimensione del elemento da inserire, l'elemento
* e il puntatore al nodo di testa.
* Definisce una struttura lista e con la funzione 'memcpy' copia
* nel nodo 'ptr' (appena creato) l'elemento dato di dimensione len_info,
* a questo punto fa puntare il nodo creato al nodo di testa e assegna
* al nodo appena creato il puntatore 'p_head'.
*/
void insert_testa(short len_info, INFO_FIELD *dato, void **p_head)
{
struct lista {
INFO_FIELD info;
struct lista *p_next;
} *ptr;


ptr = calloc(1, sizeof(struct lista));
memcpy(ptr, dato, len_info);

ptr->p_next = (struct lista *) *p_head;

(struct lista *) *p_head = ptr;
}


/*
* Questa function inserisce un nodo dopo il nodo corrente di una lista
* lineare. Prende in input la dimensione del dato, il dato da inserire
* nel nodo creato e il punatatore al nodo corrente.
* Con la funzione memcpy, copia il contenuto di dato nel nodo appena creayto
* creato. Fa diventare successore del nodo creato, il nodo successore
* del nodo corrente, fa diventare il nodo creato successore
* del nodo corrente. Fa puntare il puntatore al nodo corrente al nodo
* appena creato.
* Se si tenta di aggiungere un elemento dopo il nodo corrente quand la lista
* è vuota si originerà un errore di windows nell' esecuzione.
*/
void insert_nodo(short len_info, INFO_FIELD *dato, void **p_punt)
{
struct lista {
INFO_FIELD info;
struct lista *p_next;
} *ptr;

ptr = calloc(1, sizeof(struct lista));
if(ptr == NULL)
messaggio_errore();

memcpy(ptr, dato, len_info);
ptr->p_next = ((struct lista *)*p_punt)->p_next;

((struct lista *)*p_punt)->p_next = ptr;

(struct lista *)*p_punt = ptr;
}


/*
* Questa function elimina il nodo di testa in una lista lineare.
* Prende in input il puntatore alla testa della lista, controlla che la
* lista non sia vuota, e in caso negativo inserisce nel nodo 'temp'
* il successore del nodo di testa, libera il nodo di testa e fa puntare
* dal puntatore p_head il nodo temp.
*/
void delete_testa(void **p_head)
{
struct lista {
INFO_FIELD info;
struct lista *p_next;
} *temp;


if(!(struct lista *)*p_head) {
printf("\n\n\n *** L I S T A V U O T A ***\n\n\n");
return;
}

temp = ((struct lista *)*p_head)->p_next;

free((struct lista *)*p_head);

*p_head = temp;
}


/*
* Questa function elimina il nodo corrente in una lista lineare.
* Prende in input il nodo corrente, controlla se la lista non è
* vuota e se il nodo corrente ha un successore.
* Se la lista non è vuota e il nodo corrente ha un successore,
* fa puntare da ptr il nodo successore del nodo corrente, fa diventare
* il successore di 'ptr', successore del nodo corrente, elimina il nodo
* puntato da ptr.
*/
void delete_nodo(void **p_punt)
{
struct lista {
INFO_FIELD info;
struct lista *p_next;
} *ptr;


if(!(struct lista *)*p_punt) {
printf("\n\n\n *** L I S T A V U O T A ***\n\n\n");
return;
} else if(!((struct lista *)*p_punt)->p_next) {
printf("\n\n\n *** NON ESISTE SUCCESSORE ***\n\n\n");
return;
}

ptr = ((struct lista *)*p_punt)->p_next;
((struct lista *)*p_punt)->p_next = ptr->p_next;

free(ptr);
}


//Questa function visualizza a schermo la lista lineare
void visualizza_lista(void **p_head)
{
struct lista {
INFO_FIELD info;
struct lista *p_next;
} *temp;

temp = (struct lista *)*p_head;


while (temp != NULL){
printf("[%s, %d] -> ", temp->info.nome, temp->info.age);
temp = temp->p_next;
}
printf("NULL\n\n");
}


// Questa function visualizza un messaggio di errore.
void messaggio_errore()
{
printf("Memoria insufficiente\n");
exit(1);
}

[Piojolopez2406]

non c'è nessuno che sappia aiutarmi?

[Furla]

ciao, a fondamenti 1 mi è capitato spesso di avere a che fare con le liste (anche se in c++, comunque dovremmo riuscire a capirci anche in c), ma non capisco cosa intendi per nodo sentinella... spiegati che ti aiuto volentieri ;)

poi un favore: renditi "leggibile", indentando e scrivendo tutto nei tag "code"


while(1)
if(!0)
{
printf("ciao");
scanf();
}
else
printf("non mi vedrai mai");

[Piojolopez2406]

#include<stdio.h>
#include<stdlib.h>
#include<string.h>



/* Strutture autoriferente dinamica */
typedef struct {
char nome[20];
short age;
} INFO_FIELD;



/* Prototipi di funzione */
char *crea_lista();
void insert_testa(short, INFO_FIELD *, void **);
void insert_nodo(short, INFO_FIELD *, void **);
void delete_testa(void **);
void delete_nodo(void **);
INFO_FIELD legge_infonodo(struct PERSONA **);
void visualizza_lista(void **);
void messaggio_errore();

void main()
{
struct PERSONA {
INFO_FIELD info;
struct PERSONA *p_next;
};


struct PERSONA *head, *punt;
short scelta, n;
INFO_FIELD dato;


head = (struct PERSONA *) crea_lista();

do {
printf("QUESTO PROGRAMMA GESTISCE UNA LISTA GENERICA\n\n");
puts("[1] Aggiungi elemento nella lista");
puts("[2] Elimina elemento dalla lista");
puts("[3] Visualizza lista");
puts("[0] Esci dal programma");

printf("\nscelta: ");
scanf("%hd", &scelta);

switch(scelta) {
case 1:
printf("\n\nA G G I U N G I E L E M E N T O\n\n");
fflush(stdin);
printf("Inserire nome: ");
gets(dato.nome);
printf("Inserire eta': ");
scanf("%hd", &dato.age);

do {
puts("\n[ 1 ] Inserimento in testa alla lista");
puts("[ 2 ] Inserimento dopo nodo corrente (solo se la lista non e' vuota)");
printf("\nscelta: ");
scanf("%hd", &n);
} while (!(scelta == 1 || scelta == 2));


if(n == 1) {
insert_testa(sizeof(dato), &dato, &head);
punt = head;
}
else
insert_nodo(sizeof(dato), &dato, &punt);
printf("\n\n");
break;

case 2:
printf("\n\nE L I M I N A E L E M E N T O\n\n");
do {
puts("\n[1] Elimina nodo di testa");
puts("[2] Elimina nodo successore al nodo corrente");
printf("\nscelta: ");
scanf("%hd", &n);
switch(n) {
case 1:
delete_testa(&head);
break;
case 2:
delete_nodo(&punt);
break;
default:;
}

} while (!(scelta == 1 || scelta == 2));
case 3:
printf("\n\nVISUALIZZA LISTA\n\n");
visualizza_lista(&head);
printf("\n\n");
break;
}
} while(scelta != 0);
}


/*
* Questa function inizializza il nodo di testa della la lista lineare
*/
char *crea_lista()
{
char *testa;

testa = NULL;
return testa;
}


/*
* Questa function inserisce un nodo in testa ad una lista lineare.
* Prende in input la dimensione del elemento da inserire, l'elemento
* e il puntatore al nodo di testa.
* Definisce una struttura lista e con la funzione 'memcpy' copia
* nel nodo 'ptr' (appena creato) l'elemento dato di dimensione len_info,
* a questo punto fa puntare il nodo creato al nodo di testa e assegna
* al nodo appena creato il puntatore 'p_head'.
*/
void insert_testa(short len_info, INFO_FIELD *dato, void **p_head)
{
struct lista {
INFO_FIELD info;
struct lista *p_next;
} *ptr;


ptr = calloc(1, sizeof(struct lista));
memcpy(ptr, dato, len_info);

ptr->p_next = (struct lista *) *p_head;

(struct lista *) *p_head = ptr;
}


/*
* Questa function inserisce un nodo dopo il nodo corrente di una lista
* lineare. Prende in input la dimensione del dato, il dato da inserire
* nel nodo creato e il punatatore al nodo corrente.
* Con la funzione memcpy, copia il contenuto di dato nel nodo appena creayto
* creato. Fa diventare successore del nodo creato, il nodo successore
* del nodo corrente, fa diventare il nodo creato successore
* del nodo corrente. Fa puntare il puntatore al nodo corrente al nodo
* appena creato.
* Se si tenta di aggiungere un elemento dopo il nodo corrente quand la lista
* è vuota si originerà un errore di windows nell' esecuzione.
*/
void insert_nodo(short len_info, INFO_FIELD *dato, void **p_punt)
{
struct lista {
INFO_FIELD info;
struct lista *p_next;
} *ptr;

ptr = calloc(1, sizeof(struct lista));
if(ptr == NULL)
messaggio_errore();

memcpy(ptr, dato, len_info);
ptr->p_next = ((struct lista *)*p_punt)->p_next;

((struct lista *)*p_punt)->p_next = ptr;

(struct lista *)*p_punt = ptr;
}


/*
* Questa function elimina il nodo di testa in una lista lineare.
* Prende in input il puntatore alla testa della lista, controlla che la
* lista non sia vuota, e in caso negativo inserisce nel nodo 'temp'
* il successore del nodo di testa, libera il nodo di testa e fa puntare
* dal puntatore p_head il nodo temp.
*/
void delete_testa(void **p_head)
{
struct lista {
INFO_FIELD info;
struct lista *p_next;
} *temp;


if(!(struct lista *)*p_head) {
printf("\n\n\n *** L I S T A V U O T A ***\n\n\n");
return;
}

temp = ((struct lista *)*p_head)->p_next;

free((struct lista *)*p_head);

*p_head = temp;
}


/*
* Questa function elimina il nodo corrente in una lista lineare.
* Prende in input il nodo corrente, controlla se la lista non è
* vuota e se il nodo corrente ha un successore.
* Se la lista non è vuota e il nodo corrente ha un successore,
* fa puntare da ptr il nodo successore del nodo corrente, fa diventare
* il successore di 'ptr', successore del nodo corrente, elimina il nodo
* puntato da ptr.
*/
void delete_nodo(void **p_punt)
{
struct lista {
INFO_FIELD info;
struct lista *p_next;
} *ptr;


if(!(struct lista *)*p_punt) {
printf("\n\n\n *** L I S T A V U O T A ***\n\n\n");
return;
} else if(!((struct lista *)*p_punt)->p_next) {
printf("\n\n\n *** NON ESISTE SUCCESSORE ***\n\n\n");
return;
}

ptr = ((struct lista *)*p_punt)->p_next;
((struct lista *)*p_punt)->p_next = ptr->p_next;

free(ptr);
}


//Questa function visualizza a schermo la lista lineare
void visualizza_lista(void **p_head)
{
struct lista {
INFO_FIELD info;
struct lista *p_next;
} *temp;

temp = (struct lista *)*p_head;


while (temp != NULL){
printf("[%s, %d] -> ", temp->info.nome, temp->info.age);
temp = temp->p_next;
}
printf("NULL\n\n");
}


// Questa function visualizza un messaggio di errore.
void messaggio_errore()
{
printf("Memoria insufficiente\n");
exit(1);
}

Per nodo sentinella intendo quel nodo fittizio che si crea in testa alla lista e lo si sostituisce al puntatore alla testa, in modo tale da poter usare una sola funztion per l'inserimanto(che sia in testa o in coda) e non più 2 , e 1 per l'eliminazione...

[turibbio]

In pratica un nodo sentinella e' un nodo che viene applicato all'inizio e alla fine di una lista per evitare di avere due funzioni per l'inserimento e due per l'eliminazione. In tal modo, infatti, si ha bisogno solo della funzione per l'inserimento/cancellazione di nodo successivo rispetto al nodo corrente, e non quelle per inserimento/eliminazione della testa. In realtà è più difficile da immaginare che da implementare. Devi inizializzare il tutto con un nodo "fittizio", che sia di tipo NULL, e che punti alla prima componente (anch'essa per il momento null). Nell'inserimento basterà passare head = nodo_sentinella, che provvederà da solo a inserire nel nodo successivo il nuovo elemento.
SE hai bisogno puoi chiedermi altro! :D

[Piojolopez2406]

bhe quindi in sostanza cosa dovrei aggiungere nel codice...?

[Furla]

ma la struttura del nodo non potevi dichiararla globalmente al posto di ridichiararla in ogni funzione?

a parte questo, quello che cambia è che la funzione crealista passerà al puntatore a testa non più un valore nullo, ma l'indirizzo del nodo sentinella allocato dinamicamente appena prima. a quel punto le funzioni di inserimento ed eliminazione in testa non hanno più senso di esistere, basterà chiamare le altre funzioni di inserimento/eliminazione passando head come nodo attuale. questo per quanto riguarda il nodo di testa... in coda mi sembra che tu non ne abbia bisogno visto che la lista è unidirezionale.

[turibbio]

Per creare il nodo sentinella bisogna procedere in questo modo:

struct PERSONA *head, *punt, sentinella;
short scelta, n;
INFO_FIELD dato;

sentinella = {0};
punt = &sentinella; /*& e' necessario perchè i tipi sono differenti*/

Questo dovrebbe essere il modo più semplice ed intuitivo. Altrimenti si potrebbe modoficare la funzione crealista(), affinche crei la sentinella e restituisca come valore di ritorno l'indirizzo in memoria della sentinella. Esempio:

/*ATTENZIONE char * == void *, si tratta di un puntatore*/
char *crea_lista()
{
struct persona sentinella;

sentinella = {0};
return sentinella;
}


nel main...
...
head = (cast x il tipo *)crealista();
...

Una attenzione molto importante è che quando bisogna controllare se la lista è vuota bisogna procedere analizzando il puntatore p_next di head e non head stesso:
...
if(head -> p_next == NULL)
printf("La lista e' vuota\n");
...

di conseguenza bisogna apportare anche opportune modifiche affinché non vi troviate in un classico caso error-runtime.