Newsgroup: it.comp.lang.c
Titolo: Ancora le liste

Devo cercare di implementare una piccola libreria per le liste. Ora mi
stò concentrando sulla funzione "insert".
Vorrei che detta funzione inserisse alla posizione che desidero (in
testa, in coda, alla terza posizione ecc...) il valore "value". Ora mi
funziona solo nel caso dell'inserimento in testa.
Vorrei fare tutto in modo ricorsivo se possibile.. altrimenti anche un
metodo iterativo va bene lo stesso... :-)
Ringrazio anticipatamente chi mi risponderà.
#include <stdio.h>
#include <stdlib.h>
struct listNode
{
	char data;
	struct listNode *nextPtr;
};
typedef struct listNode LISTNODE;
typedef LISTNODE *LISTNODEPTR;
void insert(LISTNODEPTR *, char, int);
char delete(LISTNODEPTR *, char);
int isEmpty(LISTNODEPTR);
void printList(LISTNODEPTR);
void instructions(void);
int main(void)
{
LISTNODEPTR startPtr = NULL;
int choice;
char item;
instructions();
printf("? ");
scanf("%d", &choice);
while(choice != 3)
{
	switch (choice)
	{
		case 1:
			printf("Inserisci carattere: ");
			scanf("\n%c", &item);
			insert(&startPtr, item, 10);
			printList(startPtr);
			break;
		case 2:
			if (!isEmpty(startPtr))
			{
				printf("Inserisci carattere da
cancellare: ");
				scanf("\n%c", &item);
				if (delete(&startPtr, item))
				{
					printf("%c cancellato.\n",
item);
					printList(startPtr);
				}
				else
					printf("%c non trovato.\n",
item);
			}
			else
				printf("Lista vuota.\n");
			break;
		default:
			printf("Scelta non valida.\n");
			instructions();
			break;
	}
	printf("? ");
	scanf("%d", &choice);
}
printf("Fine!\n");
return(0);
}
void instructions(void)
{
printf("Scelta:\n"
	"1 inserisci\n"
	"2 cancella\n"
	"3 fine\n");
}
void insert(LISTNODEPTR *sPtr, char value, int posiz)
{
LISTNODEPTR newPtr, previousPtr, currentPtr;
if ((posiz == 0) || isEmpty(*sPtr)) /* sPtr == NULL */
{
	newPtr = malloc(sizeof(LISTNODE));
	if (newPtr != NULL)
	{
		newPtr->data=value;
		newPtr->nextPtr=*sPtr;
		*sPtr=newPtr;
		return;
	}
	else
	{
		printf("Errore di memoria.\n");
		return;
	}
}
else
{
	printf("*%d*%d\n",posiz, posiz-1);
	if ((*sPtr)->nextPtr != NULL)
		insert ((*sPtr)->nextPtr, value, --posiz);
	else
	{
		/* Inserisci in coda */
		newPtr=malloc(sizeof(LISTNODE));
		newPtr->data=value;
		newPtr->nextPtr=NULL;
		(*sPtr)->nextPtr=newPtr; 
		/**sPtr = newPtr;*/
	}
 
	/*insert(sPtr, value, posiz-1);*/
	/*lista->next=l;*/
	return;
}
}
char delete(LISTNODEPTR *sPtr, char value)
{
LISTNODEPTR previousPtr, currentPtr, tempPtr;
if (value == (*sPtr)->data)
{
	tempPtr = *sPtr;
	*sPtr = (*sPtr)->nextPtr;
	free (tempPtr);
	return(value);
}
else
{
	previousPtr = *sPtr;
	currentPtr = (*sPtr)->nextPtr;
	while(currentPtr != NULL && currentPtr->data != value)
	{
		previousPtr=currentPtr;
		currentPtr=currentPtr->nextPtr;
	}
	if (currentPtr != NULL)
	{
		tempPtr = currentPtr;
		previousPtr->nextPtr= currentPtr->nextPtr;
		free(tempPtr);
		return(value);
	}
}
return('\0');
}
int isEmpty(LISTNODEPTR sPtr)
{
return(sPtr == NULL);
}
void printList (LISTNODEPTR currentPtr)
{
if (currentPtr == NULL)
	printf("Lista vuota.\n");
else
{
	printf("Lista:\n");
	while (currentPtr != NULL)
	{
		printf("%c -->", currentPtr->data);
		currentPtr = currentPtr->nextPtr;
	}
	printf("NULL\n");
}
}


recentemente mi è capitato di vedere un sito dove facevano dei test in c/c++
http://dada.perl.it/shootout/lcc_allsrc.html
e c'è anche una piccola libreria per gestire una "a simple Double Linked
List"
prova a guardarci.
ciao.
Newbie.

 Ringrazio anticipatamente chi mi risponderà.
Il metodo iterativo, in questo caso, e' certamente migliore!
Ho preso la tua struttura e l'ho cambiata con interi visto che mi piacciono
di piu'!!! (preferenza stupida).
Avrei dovuto lasciare char, ma sono bambino in queste cose, tanto piu' che
ho lasciato char nella funzione!
struct listNode{
    int data;
    struct listNode *nextPtr;
};
Ho creato una funz. per inserire i valori, usando i parametri che volevi tu.
Infine ho creato un main ed una funzione di stampa in ordine di posizione.
<CODE>
#include<stdio.h>
#include<stdlib.h>
struct listNode{
    int data;
    struct listNode *nextPtr;
};
typedef struct listNode LISTNODE;
typedef LISTNODE *LISTNODEPTR;
int insert(LISTNODEPTR *sPtr,char value,int posiz)
{
    // UNA LISTA DI 10 ELEMENTI PARTE DA posiz 0
    // FINO A posiz 9.
    // FARE CONTROLLO if posiz<0
    LISTNODEPTR tmp=NULL;
    LISTNODEPTR scan=NULL;
    LISTNODEPTR prev=NULL;
    if((!*sPtr)||(posiz==0)){
        // LISTA VUOTA O PRIMO ELEMENTO:
        tmp=malloc(sizeof(LISTNODE));
        // CONTROLLARE ESITO ALLOCAZIONE!
        tmp->nextPtr=*sPtr;
        tmp->data=value;
        *sPtr=tmp;
    }else{
        // LISTA NON VUOTA E NON PRIMO ELEM.
        scan=*sPtr;
        while((scan)&&(posiz>0)){
            prev=scan;
            scan=scan->nextPtr;
            --posiz;
        }
        if(posiz>0){
            // posiz e' OLTRE la LISTA!
            // PER ORA IGNORA E SCRIVE COME
            // ULTIMO ELEMENTO.
            // VOLENDO SI PUO' RITORNARE ERRORE!
        }
        tmp=malloc(sizeof(LISTNODE));
        // CONTROLLARE ESITO ALLOCAZIONE!
        tmp->nextPtr=scan;
        tmp->data=value;
        prev->nextPtr=tmp;
    }
    return 1; // SUCCESS!
}
void stampa(LISTNODEPTR sPtr)
{
    while(sPtr){
        printf("%d ",sPtr->data);
        sPtr=sPtr->nextPtr;
    }
}
int main()
{
    LISTNODEPTR testa=NULL;
    // Inserisce in testa nonostante il 2!
    insert(&testa, 5, 2);
    insert(&testa, 4, 0);
    insert(&testa, 2, 0);
    insert(&testa, 7, 0);
    insert(&testa, 9, 40);
    insert(&testa, 8, 2);
    insert(&testa, 1, 4);
    insert(&testa, 11, 0);
    insert(&testa, 15, 3);
    insert(&testa, 12, 6);
    insert(&testa, 20, 40); // CODA
    insert(&testa, 19, 10);
    insert(&testa, 14, 12);
    // Ora lista dovrebbe essere:
    // --------------------------------------
    // 00 01 02 03 04 05 06 07 08 09 10 11 12
    // --------------------------------------
    // 11 07 02 15 08 04 12 01 05 09 19 20 14
    // --------------------------------------
    // STAMPIAMO E VERIFICHIAMO:
    stampa(testa);
    // ELIMINARE LISTA
    // CON FREE !!!
    return 0;
}
</CODE>
<OUTPUT>
11 7 2 15 8 4 12 1 5 9 19 20 14
</OUTPUT>
Ok, se seugi gli insert in ordine vedrai che provano tutti i possibili casi
e ti accorgerai che producono la sequenza dell'output. Seguo i primi 6:
insert(&testa, 5, 2);
// 00 01 02 03 04 05 06 07 08 09 10 11 12
// 05
insert(&testa, 4, 0);
// 00 01 02 03 04 05 06 07 08 09 10 11 12
// 04 05
insert(&testa, 2, 0);
// 00 01 02 03 04 05 06 07 08 09 10 11 12
// 02 04 05
insert(&testa, 7, 0);
// 00 01 02 03 04 05 06 07 08 09 10 11 12
// 07 02 04 05
insert(&testa, 9, 40);
insert(&testa, 8, 2);
// 00 01 02 03 04 05 06 07 08 09 10 11 12
// 07 02 08 04 05
Ok, se li seguei tutti ottieni 11 7 2 15 8 4 12 1 5 9 19 20 14 che e'
esattamente l'output prodotto.
Il programma e' incompleto:
- DEVI LIBERARE CON FREE LA LISTA PRIMA DI USCIRE.
- NON CI SONO CONTROLLI SE VIENE ALLOCATA LA MEMORIA O MENO
- NEL CASO IN CUI UNO VOGLIA SCRIVERE LA POS. 40 MENTRE CI SONO 5 ELEMENTI
STAMPA IN FONDO MA FORSE BISOGNEREBBE RITORNARE ERRORE.
- BISOGNA CONTROLLARE CHE POSIZ SIA > 0
- HO TENUTO CHAR NELLA FUNZIONE, MA SOLO PERCHE' IN QUESTO MODO CON COPY AND
PASTE DELLO SNIPPET VOLENDO E' GIA' PRONTA PER ESSERE MESSA NEL TUO CODICE
(PENSO).
- ETC...
Inoltre ho dato per scontato che la sequenza inizi da 0 a n-1 e NON da 1.
E' necessario che la prima volta che si chiama la funzione si passi un
puntatore inizializzato a NULL.
Ho implementato il metodo iterativo visto che il ricorsivo non e' per nulla
necessario (e ricordati che ricorsivo e' "sempre" piu' lento).
Una lista e' gestibile con un semplice ciclo che e' meglio di una ricorsione
semplice.
Il codice l'ho scritto al volo e testato il MINIMO indispensabile in pratica
non prendo responsabilita', eheh!
Ah, se rimuovi i commenti ti accorgi che la funzione e' corta anche se con
alcune modifiche potrebbe accorciarsi ancora!:
<SNIPPET>
void insert(LISTNODEPTR *sPtr,char value,int posiz)
{
    LISTNODEPTR tmp,scan,prev=NULL;
    if((!*sPtr)||(posiz==0)){
        tmp=malloc(sizeof(LISTNODE));
        tmp->nextPtr=*sPtr;
        tmp->data=value;
        *sPtr=tmp;
    }else{
        scan=*sPtr;
        while((scan)&&(posiz>0)){
            prev=scan;
            scan=scan->nextPtr;
            --posiz;
        }
        tmp=malloc(sizeof(LISTNODE));
        tmp->nextPtr=scan;
        tmp->data=value;
        prev->nextPtr=tmp;
    }
}
</SNIPPET>
Penso tu possa copiare ed incollare questo SNIPPET all'interno del tuo
codice (sempre che il tuo parta dalla pos 0, altrimenti devi modificarmi lo
SNIPPET leggermente).
Studiati il codice e spero ti possa essere di aiuto.
Tommy
P.S. aspetto commenti, suggerimenti, etc.. Se sono negativi (sono ben
accetti, ma...) che siano NON offensivi e costruttivi. Questo lo dico in
quanto mi sono accorto che molta gente si diverte a fare commenti NON
costruttivi, negativi, distruttivi e poco gentili nei confronti di chi
comunque perde tempo per aiutare gli altri.
Inoltre e' possibile che mi sia sbagliato qualche cosa, ma questo non
significa ne che sono scemo ne che non sono serio o altro come mi e'
capitato di sentire, semplicemente 1) ci si puo' sbagliare, 2) e'
mezzanotte, 3) ho fatto questo programma in un tempo record!.

     LISTNODEPTR tmp,scan,prev=NULL;
non sono la stessa cosa! nel metterli su di una riga sola per lo SNIPPET ho
dato troppo gas e sono partito in deparata!
Beh, riga a parte che inizializza a NULL un solo valore, funziona uguale
visto che il programma poi non si basa assolutamente sul quel valore. Se usi
lo snippet inizializza tutti a nulla anche li (sempre su di una riga sola se
vuoi), e' programmazione piu' elegante in questo modo.
Tommy

mezzanotte, 3) ho fatto questo programma in un tempo record!.
Non ti preoccupare, i commenti sono positivi... :-)

};
[snip]
La funzione insert ora va... ma la funzione delete nel caso
particolare di un solo elemento nella lista non lo cancella...
credo sia un errore dovuto alla fretta... fammi sapere... ciao!
#include<stdio.h>
#include<stdlib.h>
struct listNode{
    int data;
    struct listNode *nextPtr;
};
typedef struct listNode LISTNODE;
typedef LISTNODE *LISTNODEPTR;
int insert(LISTNODEPTR *sPtr, int value, unsigned int posiz, int
oltre);
void stampa(LISTNODEPTR sPtr);
int delete(LISTNODEPTR *sPtr, int *value, unsigned int posiz, int
oltre);
int insert(LISTNODEPTR *sPtr, int value, unsigned int posiz, int
oltre)
{
LISTNODEPTR tmp=NULL;
LISTNODEPTR scan=NULL;
LISTNODEPTR prev=NULL;
if((!*sPtr)||(posiz==0))
{
	/* LISTA VUOTA O PRIMO ELEMENTO: */
	tmp=malloc(sizeof(LISTNODE));
	if (tmp == NULL)
	{
		return(1);
	}
	tmp->nextPtr=*sPtr;
	tmp->data=value;
	*sPtr=tmp;
}
else
{
	/* LISTA NON VUOTA E NON PRIMO ELEM. */
	scan=*sPtr;
	while((scan)&&(posiz>0))
	{
		prev=scan;
		scan=scan->nextPtr;
		--posiz;
        }
	if ((posiz>0) && (oltre == 0))
	{
		return(2);
	}
	tmp=malloc(sizeof(LISTNODE));
	if (tmp == NULL)
	{
		return(1);
	}
	tmp->nextPtr=scan;
	tmp->data=value;
	prev->nextPtr=tmp;
}
return (0); /* Nessun errore */
}
void stampa(LISTNODEPTR sPtr)
{
while(sPtr)
{
	printf("%d ",sPtr->data);
	sPtr=sPtr->nextPtr;
}
printf("\n");
}
int delete(LISTNODEPTR *sPtr, int *value, unsigned int posiz, int
oltre)
{
LISTNODEPTR ptemp=NULL;
LISTNODEPTR scan=NULL;
LISTNODEPTR temp=NULL;
LISTNODEPTR prev=NULL;
LISTNODEPTR pen=NULL;
if(!*sPtr)
{
	printf("Lista vuota niente da cancellare.\n");
	return(1);
}
if (posiz==0)
{
	*value=(*sPtr)->data;
	ptemp=*sPtr;
	*sPtr=(*sPtr)->nextPtr;
	free(ptemp);
	/*return(0);*/
}
else
{
	scan=*sPtr;
	while((scan)&&(posiz>0))
	{
		pen=prev;
		prev=scan;
		scan=scan->nextPtr;
		--posiz;
        }
	if ((posiz>0) && (oltre == 0))
	{
		return(2);
	}
	/* in prev ho precedente in scan il successivo (è null?)*/
	if (scan != NULL)
	{
		*value=scan->data;
		temp=prev->nextPtr;
		scan=scan->nextPtr;
		prev->nextPtr=scan;
		free(temp);
	}
	else
	{
		if (pen != NULL)
		{
			*value=prev->data;
			temp=pen->nextPtr;
			pen->nextPtr=NULL;
			free(temp);
		}
		else
		{
			/* Ultimo caso un solo elemento CONTROLLARE */
			*value=(*sPtr)->data;
			temp = *sPtr;
			(*sPtr)->nextPtr=NULL;
			free(temp);
		}
	}
}
return(0);
}
int main(void)
{
LISTNODEPTR testa=NULL;
int x;
insert(&testa, 10, 0, 1);
insert(&testa, 4, 0, 1);
insert(&testa, 2, 0, 1);
insert(&testa, 100, 0xFFFFFFFF, 1);
insert(&testa, 50, 3, 1);
stampa(testa);
/*delete(&testa, &x, 0, 1);
printf("X è %d.\n",x);
delete(&testa, &x, 0, 1);
printf("X è %d.\n",x);
delete(&testa, &x, 0, 1);
printf("X è %d.\n",x);*/
delete(&testa, &x, 2, 1);
printf("X è %d.\n",x);
printf("%d",delete(&testa, &x, 3, 1));
printf("X è %d.\n",x);
stampa(testa);
delete(&testa, &x, 0, 1);
printf("X è %d.\n",x);
stampa(testa);
delete(&testa, &x, 4, 1);
printf("X è %d.\n",x);
stampa(testa);
delete(&testa, &x, 8778, 1);
printf("X è %d.\n",x);
stampa(testa);
// ELIMINARE LISTA
// CON FREE !!!
return (0);
}

 credo sia un errore dovuto alla fretta... fammi sapere... ciao!
FRETTA?
Se e' un errore dovuto alla fretta risolvilo tu, no?!?
E' bello aiutare le persone che si sforzano ma non riescono, non quelle che
non vogliono perderci tempo, fanno in fretta e poi spediscono il codice se
non funziona.
Concentrati e risolvilo! Se poi non riesci riposta....
Beh, dai ti spedisco una versione afFRETTAta che non ho testato, visto che
anche tu vai di FRETTA, allora mi permetto anche io di andare di FRETTA!
Dovrebbe funzionare sul programma che ti ho inviato:
<CODE>
void elimina_at(LISTNODEPTR *sPtr, int pos)
{
    LISTNODEPTR prev=NULL;
    LISTNODEPTR scan=NULL;
    if(sPtr) scan=*sPtr; else return;
    if(pos<0) return;
    while((scan)&&(pos>0)){
        prev=scan;
        scan=scan->nextPtr;
        --pos;
    }
    if(scan){
        if(prev){
            prev->nextPtr=scan->nextPtr;
            free(scan);
        }else{
            *sPtr=(*sPtr)->nextPtr;
            free(scan);
        }
    }
}
</CODE>
Va chiamata in questo modo: elimina_at(&testa,4);
Il tuo prototipo era: int delete(LISTNODEPTR *sPtr, int *value, unsigned int
posiz, int oltre), ho fatto di FRETTA e non ho voluto cercare di capire cosa
fossero *value, e oltre. Inoltre, sempre avendo FRETTA non ho cercato di
capire cosa tu possa aver sbagliato.
Per finire, sempre avendo molta FRETTA, non ho commentato il codice, oltre a
non averlo scritto in modo elegante.
Tommy
P.S. ti saluto, vado di FRETTA.

Concentrati e risolvilo! Se poi non riesci riposta....
In effetti intendevo che dopo qualche ora di "stallo" non riuscivo a
sbloccarmi e che forse nella fretta di scrivere il codice avevo
inserito del codice sbagliato. Finalmente ho trovato l'errore ed ora
va bene.
Non te la prendere, ma io ho "perso" intere giornate a testare i
programmi e chiedo aiuto solo quando si presentano problemi nuovi o di
difficile soluzione.