Newsgroup: it.comp.lang.c
Titolo: Mergesort e liste doppiamente concatenate

Ciao a tutti...oggi vi scrivo per un problema che a molti di voi potrà
sembrare banale ( e sinceramente spero lo sia...così mi aiutate prima
:P) ma che mi sta facendo perdere un sacco di tempo prezioso:
Allora....
Ho creato una lista doppiamente concatenata per la creazione della mia
rubrica:
typedef struct nodo *pointer;
typedef struct nodo
{
   char nome[NOME_SIZE];
   char cognome[NOME_SIZE];
   char numero[NUM_SIZE];
   pointer linkdx;
   pointer linksx;
}contatto;
pointer rubrica = NULL;
i dati vengono inseriti in questo modo:
void aggiungi(void)
{
	system(pulisci);
	pointer nuovo;
   nuovo = (pointer)malloc(sizeof(contatto));
   if(!nuovo) exit(1); //problemi di allocazione
   printf("\n\t\t****************************\n");
	printf("\t\t**     NUOVO CONTATTO     **\n");
   printf("\t\t****************************\n\n\n");
   printf("\t\tNome\t-->\t");
   scanf("%[^\n]s", &nuovo->nome);
   getchar();
   printf("\t\tCognome\t-->\t");
   scanf("%s", &nuovo->cognome);
   getchar();
   printf("\t\tNumero\t-->\t");
   scanf("%s", &nuovo->numero);
   nuovo->linksx = NULL;
   nuovo->linkdx = NULL;
   inserisci(nuovo);
}
void inserisci(pointer nuovo)
{
   pointer aux;
	if(!rubrica)	rubrica = nuovo;  //se è il primo lo inserisco
all'inizio
   else
   {
   	/*confronto tra i dati memorizzati e il nuovo dato
        strcmp rende 0 se le 2 stringhe sono uguali
        <0 se la stringa1 è minore della stringa2
        >0 se la stringa è maggiore della stringa2*/
   	if(strcmp(nuovo->nome,rubrica->nome) < 0)
   	{
      	rubrica->linksx = nuovo;
         nuovo->linkdx = rubrica;
         rubrica = nuovo;
      }
      else
      {
         aux = rubrica;
         /*scorro la lista finchè ci sono elementi da confrontare e
finchè
         il confronto non dice che mi devo fermare*/
      	while(strcmp(nuovo->nome,aux->nome)>=0 && aux->linkdx)
         	aux = aux->linkdx;
         if(aux->linkdx)
         {
         	aux->linksx->linkdx = nuovo;
            nuovo->linksx = aux->linksx;
            aux->linksx = nuovo;
            nuovo->linkdx = aux;
         }
         else
         {
         	aux->linkdx = nuovo;
            nuovo->linksx = aux;
         }
      }
   }
}
Fin qui tutto bene (visto che vi è un controllo sull'ordine prima
dell'inserimento del nuovo dato)...se non fosse altro che i dati si
possono modificare (funzione che qui non ho inserito, se vi serve
fatemelo sapere)...
Una volta modificati "potrebbe" essere necessario riordinarli...ho
pensato di invocare la funzione MERGESORT..ma ho qualche problemino con
il codice (o meglio a riorganizzarlo per la mia lista)..
Io continuerò a sforzarmi da sola ma vi prego, se mi volete dare una
mano ve ne sarò davvero grata...anche perchè ho una scadenza di
presentazione progetto in breve..
GRAZIE MILLE a tutti...

 il codice (o meglio a riorganizzarlo per la mia lista)...
Allora spero di esserti d'aiuto...
Non avevo in mano l'algoritmo del mergesort in compenso ho trovato 
quello del quicksort (che in realtà mi piace anche di più)...spero che 
possa andar bene lo stesso.
Impostando primo come primo = rubrica->linksx e ultimo come un pointer 
all'ultimo elemento in coda alla tua lista
il quicksort e la rispettiva partition dovrebbbero venire all'incirca così:
void quicksort(pointer rubrica, pointer primo, pointer ultimo){
     pointer q;
     if(strcmp(primo->nome, ultimo->nome) != 0){
              q = partition(rubrica, primo, ultimo);
              quicksort(rubrica, primo, q);
              quicksort(rubrica, q->linksx, ultimo);
     }
}
pointer partition(pointer rubrica, pointer primo, pointer ultimo){
      pointer i, j, x;
      x = rubrica;
      i = primo->linkdx;
      j = ultimo->linksx;
      while(1){
               while(strcmp(primo->nome, x->nome) <= 0)
                   j = j->linkdx;
               while(strcmp(ultimo->nome, x->nome) >= 0)
                   i = i->linksx;
               if(strcmp(i->nome, j->nome) < 0)
                   scambia(i, j);
               else return j;
      }
}
Non ho provato, a dire il vero, se funziona, ma anche se non dovesse 
andare bene spero almeno di averti dato uno spunto.

Ciao Will...grazie di essere venuto in mio soccorso..
Mi è venuta un'altra illuminazione che ho già messo in pratica e
funziona..e ha una complessità lineare (cosa che con il quicksort non
ottengo ma con il mergesort si)...evisto di riordinare tutta la lista e
visto che si tratta solo di un elemento che potrebbe essere o non
essere già al posto giusto elimino tale elemento chiedo di inserire il
nuovo nome e lo inserisco con la funzione di inserimento
precedentemente creata...
Secondo te è una buona soluzione o sto facendo solo porcherie???

 
fai bene a fare così è inutile invocare un algoritmo di ordinamento; non 
so cosa intendi per "elimini tale elemento", ma se vai a fare un'altra 
malloc ricorda che questa potrebbe essere evitata tramite un semplice 
scambio di puntatori (è a questo che servono le liste).
Ciao, Alberto

In pratica il mio cervellino "pazzo" mi ha detto di fare così:
if(mod == UNO)
      	{
            pointer nuovo;
            nuovo = (pointer)malloc(sizeof(contatto));
            if(temp->linksx == NULL) //se è il primo
      	      cancellaTesta();
      		else if(temp->linkdx == NULL) //se è l'ultimo
         		cancellaUltimo(temp);
      		else
      			cancellaMezzo(temp);
   			printf("\n\n\t\tNuovo nome\t-->\t");
         	scanf("%s", &nuovo->nome);
            strcpy(nuovo->cognome,temp->cognome);
            strcpy(nuovo->numero,temp->numero);
            nuovo->linksx=NULL;
            nuovo->linkdx=NULL;
            inserisci(nuovo) ;

 Ciao Will...grazie di essere venuto in mio soccorso..
Prego, mi fa piacere se ti sono stato d'aiuto ;)

Praticamente vuoi evitare di fare l'ordinamento inserendo al posto 
giusto ogni volta l'elemento inserito?
Si, mi sembra un'ottima soluzione ;)
Per quanto riguarda il mergesort, non vorrei dire corbellerie, ma non 
credo che sia lineare...da quanto sapevo l'algoritmo di quicksort 
(magari implementato in maniera random) è il migliore in assoluto, tempo 
O(n log n).

Mmmm...per sicurezza mi sono andata a rivedere il libro:
<<Il mergesort ha SEMPRE complessità nlogn..mentre il quicksort nel
caso pessimo è n^2 e sia nel caso migliore e sia in quello medio ha
complessità nlogn...dunque quando si ha a cha fare con le liste è
decisamente meglio il mergesort>>
Ad ogni modo...per questo caso particolare non vanno bene nè l'uno nè
l'altro...c'è ancora da lavorarci un po' su ma credo che riuscirò a
consegnare il tutto nei tempi previsti...
Grazie ancora..mi stavo rassegnando e mi hai dato la forza di
continuare a "scervellarmi".... :)
ciaux

 continuare a "scervellarmi".... :)
Di nulla :)