Newsgroup: it.comp.lang.c
Titolo: liste, ordinamenti e ricerche

salve a tutto il gruppo. questo è il mio primo messaggio, salto i
convenevoli e vengo subito al dunque.
ho bisogno di ordinare col metodo
quicksort una lista e successivamete cercare in essa un elemento tramite
una ricerca binaria. qualcuno potrebbe passarmi degli algoritmi ad hoc?
grazie in antcipo, luca!
--------------------------------
Inviato via 
http://usenet.iol.it

 grazie in antcipo, luca!
Non c'e` bisogno di reinventare la ruota: la libreria standard mette a 
disposizione le funzioni qsort() e bsearch() che fanno proprio al caso 
tuo. Consulta la manualistica del tuo compilatore per il loro funzionamento.
-- 
Baci,
Mony

Mony
ciao Mony, innanzitutto grazie
per l'attenzione, cmq avevo già visto quelle funzioni, servono per ordinare
dei vettori, le posso usare anche per le liste? cose devo passare?
dall'help ho letto: void qsort(void *base, size_t nelem, size_t width, int
(*fcmp)(cost void *, cost void *));
ma sono alle prime armi e non so come
muovermi!
grazie ancora, ciao luca!


:

Un tip: crea un array grande come la tua lista, ad ogni elemento
assegna un nodo e poi chiama su questo le funzioni.
-- 
Mox
"Trust the programmer."
"Don't prevent the programmer from doing what needs to be done."
"Keep the language small and simple."
"Provide only one way to do an operation."

e questo per la ricerca binaria:
void *bsearch(const void *key, const void
*base, size_t nelem, size_t width, int (*cmp)(const void*, const void));
che faccio ora?


 dei vettori, le posso usare anche per le liste? 
No. Pero` le funzioni indicate... funzionano cosi` bene e risparmiano 
tanto lavoro da far prendere in seria considerazione quanto suggerito da 
max... ;)
-- 
Baci,
Mony

con una funzione conto il numero di nodi e lo metto in n_nodi, poi creo
l'array come da tips
int *v;
v=(void *)malloc(n_nodi*sizeof(n_nodi));
poi dovrei fare dei cicli di for per inserire i nodi negli elementi
dell'array in questo modo
for(i=0;i<n_nodi;i++)
  .....;
ma non ho
capito bene quale istruzione sostituire ai puntini
ancora grazie, luca


v=(void *)malloc(n_nodi*sizeof(n_nodi));
Sbagliato per vari motivi, ora cerco di spiegarmi.
Il cast non si mette come valore di ritorno della malloc perche'
avviene implicitamente (dallo standard noto come C89 in poi). E
comunque se proprio vuoi farlo (perche' hai un compilatore pre-ansi)
almeno fallo al tipo a cui assegnare la memoria, quindi (int *), non
void *  :)
Il cast serviva nelle vecchie versioni perche' la malloc ritornava un
char *, quindi divevi castare a meno che non dovessi assegnarlo
effettivamente a un char *.
Il programma dovrebbe essere piu' o meno cosi':
<CODE target="struttura dati">
typedef struct listnode {
	int key;
	struct listnode * next;
} listnode;
</CODE>
<CODE target="main code">
int lsize=0; 
listnode * l; /* la testa della tua lista */
listnode * aux; /* scorrere la lista senza perdere la testa */
listnode ** array; /* serve per memorizzare la lista */
aux = l;
while (aux != NULL) {
	lsize++;
	aux = aux->next;
}
if ( (array = malloc(lsize * sizeof(listnode))) == NULL)
	return EXIT_FAILURE;
for (i=0, aux = l; i<n_nodi; i++, aux = aux->next)
    array[i] = aux;
</CODE>
Sono stato chiaro? Se no chiedi :)


avviene implicitamente (dallo standard noto come C89 in poi)
Il mio prof di programmazione lo mette :-(
Sono disperato, è uno che considera sbagliate le cose che non sa e
l'assistente è ancora peggio...
-- 
Marco Barisione (ICQ 84277092)



Compilando con il visual c++, il cast viene richiesto, mentre col
borland c++ no (Sebbene il file sia lo stesso). Inoltre, se il file
viene salvato con estensione .cpp entrambi i compilatori richiedono il
cast (perchè con c++ il cast da void a altro tipo non è automatico).

 Il mio prof di programmazione lo mette :-(
Infatti non è sbagliato. In C++ è obbligatorio. In C è di troppo e potrebbe
essere pericoloso, ma sbagliato no. C'è pure chi ama vivere pericolosamente.
Per esempio a me piace tanto scrivere:
    if (x = a) ...
quando tutti consigliano:
    if ((x = a) != 0) ...
So che rischio l'errore, che il codice è meno leggibile... ma in fondo è
solo questione di gusti. Quel cast inutile, poi, ho visto che lo usano anche
fior di programmatori.
Maurizio.

Compilando con il visual c++, il cast viene richiesto
Con VC++6 se l'estensione è .c non richiede il cast.


essere pericoloso, ma sbagliato no
Tu insegneresti a degli studenti che magari non hanno mai programmato
una cosa pericolosa?


cast (perchè con c++ il cast da void a altro tipo non è automatico).
Compilando con il VC++ verra' richiesto perche' lo interpreta come C++
spero, il C NON ti deve segnare errore (a meno che tu non ti sia
dimenticato di includere i prototipi delle funzioni, allora li te lo
segnala, ma tutto dipende dall'assunzione del C89 per cui le funzioni
se non specificato altrimenti ritornino int).
In C++ il discorso e' diverso: il linguaggio e' fortemente tipizzato e
il cast (anzi, uno dei possibili cast) lo devi mettere.


 hanno mai programmato una cosa pericolosa?
Che c'entra questo? Io ho detto che non è errore, non che sia consigliabile
farlo. Sono due cose nettamente differenti.
Io insegno a usare la testa, a tirare fuori le antenne quando si incontra
una cosa pericolosa, anche ad evitarla se non se la sentono di affrontarla;
ma non obbligo nessuno ad evitarla o ad affrontarla. In fondo se il C lo
permette e non dà nemmeno un warning un motivo ci sarà?
Il C è bello perché lascia la massima libertà al programmatore, gli permette
di fare quello che altri linguaggi gli impediscono. Anche la libertà è
pericolosa. Hai visto mai un linguaggio che permette di dichiarare un char e
trattarlo come un int senza una conversione esplicita? Hai visto mai un
linguaggio che permette di eseguire del codice macchina contenuto in una
stringa senza che ci sia un'istruzione inline? È pericoloso anche questo?  È
il C stesso che è pericoloso per chi non ha mai programmato. Se poi le
gabbie ce le vogliamo mettere da soli ognuno è libero di farlo.
Maurizio.

     if ((x = a) != 0) ...
   Oh, bella... E chi consiglierebbe una cosa del genere? Nota che, se a 
e` diverso da zero, (x=a) e` comunque diverso da zero. Tanto varrebbe 
scrivere direttamente
	if(a!=0)
   Secondo me, il discorso era un po' diverso... ;)
-- 
Alla prossima,
Marco

 gabbie ce le vogliamo mettere da soli ognuno è libero di farlo.
   Il C non e` piu` pericoloso di un frullatore: puo` produrre frullati 
per anni, fino a quando non decidi di metterci dentro la mano mentre e` 
acceso per vedere che succede.
   Tuttavia, non essendo un linguaggio di alto livello, alcune sue 
specificita` possono nascondere accuratamente le cause di sgradevoli 
errori che si presentano in esecuzione o in compilazione. Il cast sul 
valore ritornato da malloc() e` un grande classico del genere.
   E, comunque, e` inutile. Ed i buoni programmatori tendono a scoprire 
rapidamente cosa si puo` evitare senza problemi. ;)
-- 
Alla prossima,
Marco

 Il C non e` piu` pericoloso di un frullatore
Dipende da cosa ci metti in my_code. Se ci metti le istruzioni per
formattare l'hard disk, forse fa un po' piů male di un frullatore.
Maurizio.

 formattare l'hard disk, forse fa un po' piů male di un frullatore.
   Se sei cosi` folle da fare una cosa del genere, forse non e` il caso 
che ti mettano in mano un calcolatore elettronico. Ripeto quanto detto 
nel mio articolo precedente: "non essendo (il C) un linguaggio di alto 
livello, alcune sue specificita` possono nascondere accuratamente le 
cause di sgradevoli errori che si presentano in esecuzione o in 
compilazione". Ricercare ed applicare senza necessita` queste 
specificita` e`, a mio avviso, insano.
-- 
Alla prossima,
Marco

     (* (void (*) (void) ) my_code)();
questo codice e` tanto standard quanto questo:
int* p = 1234;
*p = 4321;
Sintatticamente e formalmente corretto, ma undefined behaviour a 
run-time.
ciao Anto
-- 
Antonio Cuni, 20 anni, studente
Brainbench C++ Master: 4.73, higher than 99% of all previous test takers.
C Language: 3.79, higher than 92% of all previous test takers.
Guida C/C++ di Programmazione.it: 
http://cpp.programmazione.it

 *p = 4321;
Non è la stessa cosa. Tu prendi una locazione a caso e ci vai a scrivere un
numero a caso. Avresti ragione se io avessi scritto così:
    int *p = 1234;
    (* (void (*) (void) ) p)();
Io ho invece detto che alloco lo spazio di memoria necessario, vi
trasferisco una routine in linguaggio macchina (preventivamente assemblata)
e non dei codici a caso come erano riportati nell'esempio; infine la mando
in esecuzione con istruzioni standard C. Era stato detto da Marco che non
esisteva alcun modo standard del C per fare quest'ultima cosa. Invece
riconosci anche tu che il codice è "Sintatticamente e formalmente corretto"
e solo questo mi interessava.
Solo per informazione, questo codice l'ho trovato in un sorgente C di una
importante software house, nota in tutto il mondo.
Poi ha ragione Marco a dire che il codice è "implementation dependant".  Ma
questo è un discorso diverso che porterebbe lontano e non vuol dire che il
codice non sia standard. È implementation dependant, ad esempio, anche il
file di dati in cui sono stati scritti degli int o dei float; ma nessuno si
sogna di dire che non esiste un modo standard per scrivere in un file. Ma
adesso non allarghiamo il discorso anche alla scrittura dei file, vi prego;
era solo un esempio.
Maurizio.

 Poi ha ragione Marco a dire che il codice è "implementation dependant".
no, e` undefined behaviour.
