Newsgroup: it.comp.lang.c
Titolo: Ordinamento Strutture

Dunque ho un problemino con l'ordinamento,ho una lista che parte da un
puntatore del tipo
Rubrica * Start;
dove rubrica è questa struct :
typedef struct rubricastruct
{
 int ID;
 char Nome[150];
 char TelUff[20];
 char TelCasa[20];
 char Fax[20];
 char Cell[20];
 char Indirizzo[200];
 char Citta[100];
 char Email[100];
 char Web[200];
 char CAP[10];
 char Varie[500];
 struct rubricastruct *next;
}Rubrica;
ora man mano che il mio bravo utente inserisce informazioni nella Rubrica io
alloco una nuova cella e la inserisco alla fine, avrei però bisogno di una
funzione che me la ordini come posso fare? Con le mie super conoscenze
infuse da Herbert Schilt (non sputatemi addosso subito) ho trovato questa
soluzione :
1) Mi creo un bel array con malloc e in ogni cella ci metto una delle celle
della mia lista
2) Passo il tutto alla mia brva funzione qs  che mi ordina il tutto (vedi
sotto):
3) Ricostruisco la lista facendo scorrere l'array che è ormai ordinato.
Il Problema è che non funziona e oltretutto peso faccia abbastanza schifo
come prestazioni perchè mi costringe ad allocare un sacco di spazio per
l'array da ordinare e mi fa scorrere più volte la mia lista. Penso ci sia un
metodo un po' più elegante per risolvere il tutto
Grazie
Wezzy
void qs(Rubrica items[], int left, int right)
{
 // This function order array
 register int i,j;
 char *x;
 Rubrica tmp;
 i = left;
 j = right;
 x = items[(left+right)/2].Nome;
 do
 {
  while((strcmp(items[i].Nome,x) < 0) && (i < right)) i++;
  while((strcmp(items[j].Nome,x) > 0) && (j > right)) j--;
  if(i <= j)
  {
   tmp = items[i];
   items[i] = items[j];
   items[j] = tmp;
   i++;
   j--;
  }
 }while(i <= j);
 if(left < j)
  qs(items,left,j);
 if(i<right)
  qs(items,i,right);
}

 metodo un po' piů elegante per risolvere il tutto
Rispetto alle liste, penso che l'algoritmo che hai mostrato sia uno
dei piu' efficienti.
Forse potresti passare a strutture piu' complesse, come gli alberi...
ciao
luca

Il problema non è l'efficenza del quicksort in se, il fatto è che per
poterlo usare devo prima copiare tutta la lista in un array, se la mia lista
contiene 50 celle la cosa non è banale, oltre tutto faccio un sacco di
accessi alla memoria che penso si possano risparmiare. Resta poi il problema
principale, l'algoritmo non so perchè non funziona!
Non sono troppo pratico con gli alberi ma come verrebbe? non è ancora più
complicato l'ordinamento?
Grazie
Wezzy

complicato l'ordinamento?
Se fai un albero binario di ricerca tu inserisci gia' in ordine, non
devi mai riordinare.
Ecco piu' o meno come diventa una procedura di inserimento in un
albero binario di ricerca:
<CODE>
if (root == NULL)
    /* inserisci come root */
else {
  tmp = root;
  while (tmp != NULL) {
    switch (result = compare(tmp, new_element)) {
      case MINORE:
        if (tmp->left == NULL) {
          tmp->left = new_element;
          tmp = NULL; /* arresta il ciclo */
        }
        else
          tmp = tmp->left;
        break;
      case UGUALI:
        /* boh, vedi un po' te cosa fare */
        break;
      case MAGGIORE:
        if (tmp->right == NULL) {
          tmp->right = new_element;
          tmp = NULL; /* arresta il ciclo */
        }
        else
          tmp = tmp->right;
        break;
      }
  }
</CODE>
Sta a te scrivere il confronto.
Nota che l'albero ben bilanciato avra' al massimo profondita' lgN e
nel peggiore dei casi N... se non hai una sfortuna nera hai sempre
tempi logaritmici di inserimento e ricerca.
-- 
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."

Ti ringrazio, in effetti ho visto che esiste una funzione standad di
ordinamento, ma dato che sto facendo il mio programmino piů per scopo
didattico che per altro ho tentato di farmene uno a mano. Nel frattempo ho
pensato un altra cosa, come ho scritto adesso il mio codice creo un array
con l'intera struttura Rubrica, ho pensato:
1)Creo un array con soltanto il campo nome della struttura Rubrica
2)Creo in parallelo un secondo array con i puntatori a ciascuna struttura
3)Ordino l'array con i nomi e contemporaneamente sposto i valori dei
puntatori nel secondo array
4)ricostruisco la lista senza reallocare nulla ma solo reimmpostando le
celle della lista nel novo ordine
Anche se questo comporta un nuovo array sicuramente risparimio memoria e
calcoli rispetto alla prima soluzione, cosa ne pensi ?
ora mi metterňa guardare il tuo codice sugli alberi
Grazie
Wezzy

poterlo usare devo prima copiare tutta la lista in un array
Non è necessario.
Invece di copiare la lista in un array, puoi semplicemente tenere il
conto degli elementi della lista, e generare un array di puntatori ad
elementi della struttura che usi.
A quel punto potrai usare tutti gli algoritmi di ordinamento che vuoi,
e lo swap consisterà semplicemente nell'inversione di due puntatori,
invece che di due elementi della lista, con evidenti vantaggi di
velocità.
Inoltre, se definisci una funzione di confronto di due elementi
dell'array così generato (tipo lo strcmp, insomma, che restituisce un
numero negativo, nullo o positivo a seconda della posizione relativa
dei due argomenti della funzione), puoi passare il puntatore a questa
funzione di confronto alla funzione di libreria qsort, e non dovrai
neppure sprecare tempo per scrivere il quicksort. ;-)
Certo se devi imparare a scrivere un quicksort, sarà un esercizio
utile, ma lo sarà anche imparare ad usare le librerie senza imparare
ogni volta l'acqua calda. :-)
Magari potresti scrivere due sorgenti usando entrambe le soluzioni.
Su questo vettore potrai anche utilizzare il merge sort, che ti ha
spiegato Mox, evitando però di dover swappare tutti i campi della
struttura, visto che potrai limitarti ad invertire solo due puntatori.
:-)
Questo trucchetto velocizza moltissimo l'esecuzione, ma spreca anche
memoria (un puntatore per ogni elemento della lista), quindi se il
problema è la limitatezza della memoria, la soluzione migliore che mi
venga in mente a parità di semplicità è quella del post di Mox.
-- 
Cordiali saluti
  Artemio

celle della lista nel novo ordine
Se dovessi scriverlo io (che sono un signor nessuno, quindi leggi
quanto scrivo con senso critico), lo farei in un altro modo.
Puoi mantenere benissimo la tua struttura 'Rubrica' originale (piů
facile da gestire, e con meno puntatori), e fare come segue.
Dichiari un puntatore a Rubrica, che userai per mettervi un array di
puntatori di dimensione ancora ignota.
Rubrica *array_rubricastruct;
Nel corso dell'uso del programma, potresti gestire una variabile
globale, che chiamo per esempio tot_record, che venga aggiornata
(incrementata, decrementata) in caso di inserimento/cancellazione di
elementi della lista.
Usando questi due elementi, potrai effettuare un sort nel modo
seguente: come prima cosa allochi lo spazio per il vettore di
puntatori, vale a dire semplicemente lo spazio di tot_record puntatori
a Rubrica.
array_rubricastruct = malloc(sizeof(*Rubrica) * tot_record);
Dopodiché colleghi il vettore di puntatori agli elementi della lista
con un semplice ciclo for (*temp si intende come puntatore a Rubrica)
array_rubricastruct[0] = Start;
temp =  (*Start)->next;
for(i = 1; i < tot_record; i++)
{
  array_rubricastruct[i] = temp;
  temp = (*temp)->next;
}
A questo punto avrai un array di puntatori ad elementi della lista.
Potrai ordinare questo vettore, usando uno dei tanti algoritmi, e
stamparlo ordinato, senza minimamente toccare la lista di partenza.
;-)
Spero di esserti stato utile.
-- 
Cordiali saluti
  Artemio

Grazie mille tenterň!
Grazie
Wezzy