[C] Problema con le liste

[alberto.frz]

ciao, ho un piccolo problemino con le liste.

ho creato questo tipo di lista semplice di caratteri

typedef struct elemento {
		char info;
		struct elemento *next;
}Elemento;

typedef Elemento *Lista;

supponendo di avere una lista non vuota, come faccio a sapere se i caratteri al suo interno sono ordinati in maniera crescente o decrescente?

qualche dritta?

[thehuge]

Non la ho compilata e non sono perfettamente sicuro sia ANSI C, quindi non mi prendo nessuna responsabilità se ti fonderà la CPU ed espellerà i cd dai tuoi drive ottici a mo' di frisbee .
Comunque dovrebbe controllare se la lista è ordinata in modo crescente.

int isOrdered(Elemento* lista) {
if (lista->next == NULL)
return 1;
if (lista->info <= lista->next->info)
return isOrdered(lista->next);
return 0;
}

Naturalmente per controllare se è ordinata in modo decrescente basterà sostituire < con > nel secondo if

[alberto.frz]

ma la lista è di char...

[andbin]

Originariamente inviato da alberto.frz

supponendo di avere una lista non vuota, come faccio a sapere se i caratteri al suo interno sono ordinati in maniera crescente o decrescente?

Ok, allora innanzitutto stabiliamo di realizzare una funzione che possa ritornare, ad esempio, un int che possa avere i seguenti valori:

+1 = lista ordinata in modo crescente
-1 = lista ordinata in modo decrescente
0 = lista non ordinata o comunque con ordine non determinato (pensiamo ad una lista in cui ci sono, per ipotesi, tutte le informazioni uguali).

Il procedimento da seguire per ottenere questo è il seguente.

Alla funzione viene passato il puntatore alla 'root' della lista. Dentro la funzione è necessario avere 2 variabili, chiamiamole 'dir' e 'c'.

Si fa la scansione dell'intera lista, per ogni elemento si verifica se esiste un elemento successivo. Se esiste un elemento successivo, si fa una comparazione delle due informazioni adiacenti. Se info1 > info2 si mette c=-1, se info1 < info2 si mette c=+1, altrimenti si mette c=0.

A questo punto è necessario verificare se la comparazione "concorda" o meno con 'dir'. Se dir==0 e c != 0 si fa dir=c. Se invece sia 'dir' che 'c' sono diversi da 0 e non "concordano" (sono diversi), si fa immediatamente un return di 0.

Si continua così con gli elementi successivi. Alla fine si fa ritornare 'dir'.

Il risultato è appunto quello di ottenere un +1/-1/0 che indica l'ordinamento come spiegato all'inizio.

Spero di aver spiegato in modo chiaro.

[alberto.frz]

Originariamente inviato da andbin

...Se info1 > info2 si mette c=-1, se info1 < info2 si mette c=+1, altrimenti si mette c=0...

ma allora devo trattare i char come se fossero dei int per il confronto...?!

[andbin]

Originariamente inviato da alberto.frz

ma allora devo trattare i char come se fossero dei int per il confronto...?!

Certo .... un char lo puoi trattare nello stesso modo in cui tratti gli altri tipi base (short, int ....).

[alberto.frz]

hai proprio ragione...a volte mi perdo su un bicchier d'acqua.

grazie è già la seconda volta che mi aiuti!

ciao!!!