PROBLEMA Algoritmo ricerca occorenze con lista concatenata - C

Pubblicità
rodhellas ha detto:
-Fai il merge e ottieni una lista sola
-Contatore della struct_MAX impostato a 0
-Inizi il ciclo e modifichi la struct_TEMP con i valori del primo nodo
-Per ogni nodo uguale incrementi il contatore di TEMP
-Appena cambia, se TEMP.count > MAX.count allora MAX = TEMP, sennò non fai nulla. Resetti il valore di TEMP.count e TEMP.key sarà la key del nodo successivo
-Avanti cosi fino alla fine.
Clicca per espandere...
Riprendo anche la parte con la funzione vera e propria
Merge Sort c'è, è composto da tre funzioni.
Posso creare una sola funzione chiamata dal main contenente sia il merge sort che le altre che mi servono?
In seguito dovrei creare una nuova struct chiamata TEMP? Con quali elementi?
 
FiloRp ha detto:
Codice: 
tipo_risultato ContaRipetizioni(lista l) // guarda questa soluzione di esempio: se la completi, sarà abbastanza efficiente in tempo,
                                         // e tra le meno efficienti in spazio
{                                        // se presenti questa stessa soluzione sarà molto probabile che tu prenda un voto molto basso
    tipo_risultato risultato;
    int memoria = 0;
    int hash[MAX_CHIAVE];
    nodo *tempnodo = l.testa;
    int max=0;
    // usa hash come tabella HASH ad accesso diretto per contare quante volte si presenta una certa chiave

    for(i=0;i<MAX_CHIAVE;i++){
        hash[i] = 0; 
    }
    while (tempnodo){
        hash[tempnodo->chiave] += 1;
        tempnodo = tempnodo->next;
    }
    for (i=0; i<MAX_CHIAVE; i++) {
        if (max<hash[i]){
            max=hash[i];
        }
    }
    printf("%d\n", hash[i]);

    // esplora tutta la tabella alla fine per trovare il massimo numero di occorrenze di qualche chiave
    memoria = sizeof(hash) + sizeof(nodo) + sizeof(risultato) + sizeof(memoria);
    risultato.memoria = memoria;
    risultato.numero = max;
    return risultato;
    // osserva: non è necessario liberare spazio, qui. Se avessi utilizzato strutture dinamiche, avrei dovuto liberarle alla fine dell'esecuzione.
}
Può andare bene così?
Clicca per espandere...
Se vuoi ordinare, quell'ultimo for non ti servirà in quanto effettua una ricerca lineare.

Guarda il Merge Sort come si presenta esattamente, cerca di attenerti alla forma mostrata (testata e funzionante).


EDIT:
Prendi esempio da questo pseudo codice: https://en.m.wikipedia.org/wiki/Merge_sort
 
DispatchCode ha detto:
Se vuoi ordinare, quell'ultimo for non ti servirà in quanto effettua una ricerca lineare.

Guarda il Merge Sort come si presenta esattamente, cerca di attenerti alla forma mostrata (testata e funzionante).


EDIT:
Prendi esempio da questo pseudo codice: https://en.m.wikipedia.org/wiki/Merge_sort
Clicca per espandere...
No, questo non è il Merge Sort, ma la funzione che calcola l'occorenza.
Il merge sort che ho implementato è questo:
Codice: 
/* ordina la lista cambiando il puntatore successivo (not data) */
void MergeSort(lista **l){
  nodo *testa = l.testa;

  nodo *testa = *headRef;
  nodo *a;
  nodo *b;
  /* Euristica */
  if ((testa == NULL) || (testa->next == NULL)){
    return;
  }
  /* Divide testa in partizioni a e b */
  Partition(testa, &a, &b);
  /* ordina ricorsivamente le sottoliste */
  MergeSort(&a);
  MergeSort(&b);
  /* unisce le due liste insieme */
  *headRef = SortedMerge(a, b);
}

nodo* SortedMerge(nodo* a, nodo* b){
  nodo* result = NULL;
  /* Euristica */
  if (a == NULL)
     return(b);
  else if (b==NULL)
     return(a);
  /* Prende sia a che b ed entra nella fz ricorsiva */
  if (a->chiave <= b->chiave)
  {
     result = a;
     result->next = SortedMerge(a->next, b);
  }
  else
  {
     result = b;
     result->next = SortedMerge(a, b->next);
  }
  return(result);
}

void Partition( nodo* source, nodo** frontRef, nodo** backRef){
    nodo* fast;
    nodo* slow;
  if (source==NULL || source->next==NULL)
  {
    /* lunghezza < 2 casi */
    *frontRef = source;
    *backRef = NULL;
  }
  else
  {
    slow = source;
    fast = source->next;
    /* Avanza veloce due nodi, e avanza lento un nodo */
    while (fast != NULL)
    {
      fast = fast->next;
      if (fast != NULL)
      {
        slow = slow->next;
        fast = fast->next;
      }
    }
    /* 'lento' è prima della metà della listae lista, quindi si divide in due in questo punto */
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL;
/*EVENTUALMENTE STAMPARE CON STAMPALISTA LE PARTI DIVISE PER DEBUG*/
  }

Chiamato nel main così:
MergeSort(&l);
 
Si, l'idea è quella e mi pare corretto.

Un piccolo appunto su questa istruzione
Codice: 
while (tempnodo)
Che è tipica del linguaggio C e che personalmente odio, infatti dà errore di compilazione in quasi tutti i linguaggi (pure in C usando le giuste opzioni del compilatore).
L'istruzione "while" richiede una espressione booleana, quindi funziona solo perché in C il valore booleano False viene memorizzato come "zero".
Io preferisco sempre la più esplicita versione
Codice: 
while (tempnodo != NULL)
Che oltre a essere più leggibile e più portabile fa correre meno rischi di errori.
È comunque una buona abitudine, perché ripeto appena si passa ad altri linguaggi quella espressione non passa il compilatore.
 
Andretti60 ha detto:
Si, l'idea è quella e mi pare corretto.

Un piccolo appunto su questa istruzione
Codice: 
while (tempnodo)
Che è tipica del linguaggio C e che personalmente odio, infatti dà errore di compilazione in quasi tutti i linguaggi (pure in C usando le giuste opzioni del compilatore).
L'istruzione "while" richiede una espressione booleana, quindi funziona solo perché in C il valore booleano False viene memorizzato come "zero".
Io preferisco sempre la più esplicita versione
Codice: 
while (tempnodo != NULL)
Che oltre a essere più leggibile e più portabile fa correre meno rischi di errori.
È comunque una buona abitudine, perché ripeto appena si passa ad altri linguaggi quella espressione non passa il compilatore.
Clicca per espandere...
Mi trovo d'accordo con te, ma il codice che guardavo la utilizzava così e mi sono adeguato.

Riguardo al Merge Sort che ho postato nel penultimo messaggio?
 
Il MergeSort direi sia l'unico metodo che funziona con le liste connesse
Sono secoli che non ne ho scritto uno, quindi non ti saprei dire se sia corretto o meno, ne trovi molti esempi in rete. Comunque provalo
 
FiloRp ha detto:
No, questo non è il Merge Sort, ma la funzione che calcola l'occorenza.
Il merge sort che ho implementato è questo:
Codice: 
/* ordina la lista cambiando il puntatore successivo (not data) */
void MergeSort(lista **l){
  nodo *testa = l.testa;

  nodo *testa = *headRef;
  nodo *a;
  nodo *b;
  /* Euristica */
  if ((testa == NULL) || (testa->next == NULL)){
    return;
  }
  /* Divide testa in partizioni a e b */
  Partition(testa, &a, &b);
  /* ordina ricorsivamente le sottoliste */
  MergeSort(&a);
  MergeSort(&b);
  /* unisce le due liste insieme */
  *headRef = SortedMerge(a, b);
}

nodo* SortedMerge(nodo* a, nodo* b){
  nodo* result = NULL;
  /* Euristica */
  if (a == NULL)
     return(b);
  else if (b==NULL)
     return(a);
  /* Prende sia a che b ed entra nella fz ricorsiva */
  if (a->chiave <= b->chiave)
  {
     result = a;
     result->next = SortedMerge(a->next, b);
  }
  else
  {
     result = b;
     result->next = SortedMerge(a, b->next);
  }
  return(result);
}

void Partition( nodo* source, nodo** frontRef, nodo** backRef){
    nodo* fast;
    nodo* slow;
  if (source==NULL || source->next==NULL)
  {
    /* lunghezza < 2 casi */
    *frontRef = source;
    *backRef = NULL;
  }
  else
  {
    slow = source;
    fast = source->next;
    /* Avanza veloce due nodi, e avanza lento un nodo */
    while (fast != NULL)
    {
      fast = fast->next;
      if (fast != NULL)
      {
        slow = slow->next;
        fast = fast->next;
      }
    }
    /* 'lento' è prima della metà della listae lista, quindi si divide in due in questo punto */
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL;
/*EVENTUALMENTE STAMPARE CON STAMPALISTA LE PARTI DIVISE PER DEBUG*/
  }

Chiamato nel main così:
MergeSort(&l);
Clicca per espandere...

L'avrei scritto un pò differente (magari costruendo funzioni apposite per accedere alla lista alla i-esima posizione, così prendere le due metà in maniera differente rispetto alla tua (eg. una funzione che riceve la lista ed un indice, e restituisce un riferimento al nodo in posizione i).
Però concettualmente non sembra sbagliato; ora non riesco a farlo, ma dovresti valutare pure il lato complessità temporale. Se poi così com'è funziona e la complessità è quella propria di una buona versione ottimizzata di Merge, allora direi vada bene.
 
@Andretti60 @DispatchCode
Signori, I give up.
Prenderò (forse) un punto su cinque ma non importa. Non si può dare una consegna la seconda settimana di dicembre e obbligare a consegnarla nemmeno un mese dopo considerando che in mezzo ci sono altri esami.

Attulmente il codice confronta ogni numero presente nella lista, in modo disordinato, con una lista interna che viene ciclata n*n volte. Una pena.
Codice: 
tipo_risultato ContaRipetizioni(lista l){
    int MaxCount = 0;
    int memoria = 0;

    nodo *tempnodo2 = l.testa;                              //Crea testa del nodo2 collegato a tutti gli altri nodi tramite nodo
    while (tempnodo2!=NULL){                                //Finchè esiste tempnodo2

        nodo *tempnodo = l.testa;                           //Crea testa del nodo per confronto con tempnodo2
        int count = 0;                                      //Inizializza Counter a 0
        while (tempnodo!=NULL){                             //Finchè esiste tempnodo
            if (tempnodo->chiave == tempnodo2->chiave){     //Se la chiave ciclata da tempnodo è uguale alla chiave del nodo2
                count++;                                    //aumento il counter
            }
            tempnodo = tempnodo->next;                      //Passo al numero successivo della lista per verificarlo
        }
        // printf("count of %d is %d\n", tempnodo2->chiave, count);

        if (count > MaxCount){                              //Se il counter è maggiore di MaxCount (originarimente a 0)
            MaxCount = count;                               //settiamo MaxCount uguale al nuovo Count
        }
        tempnodo2 = tempnodo2->next;
    }
    printf("maxcount is %d\n", MaxCount);
    risultato.numero = Maxcount;
    risultato.memoria = ??? ;
}

A questo punto vi chiedo solamente una cosa: la funzione finale deve essere una variabile di tipo tipo risultato, dove nel campo numero ritorna il valore richiesto, e nel campo memoria ritorna il numero di bytes utilizzati dalle strutture dati principali interne alla funzione. Cosa scrivo in risultato memoria?
 
Ultima modifica:
Intendi dire che il tipo di ritorno della funzione deve essere di tipo tipo_risultato e che un attributo della struttura deve contenere il numero di bytes allocati dalle strutture nelle diverse istanze, suppongo.
In questo caso, se sai quante volte cicli, sai quali sono le strutture coinvolte (eg. sai quante volte ciascuna viene allocata) è sufficiente fare un sizeof di quella struttura e moltiplicarlo per il numero di elementi (così per tutte le strutture coinvotle), così da sapere la quantità di memoria totale allocata. Credo sia questo ciò che intendi, se ho ben capito.
 
DispatchCode ha detto:
Intendi dire che il tipo di ritorno della funzione deve essere di tipo tipo_risultato e che un attributo della struttura deve contenere il numero di bytes allocati dalle strutture nelle diverse istanze, suppongo.
In questo caso, se sai quante volte cicli, sai quali sono le strutture coinvolte (eg. sai quante volte ciascuna viene allocata) è sufficiente fare un sizeof di quella struttura e moltiplicarlo per il numero di elementi (così per tutte le strutture coinvotle), così da sapere la quantità di memoria totale allocata. Credo sia questo ciò che intendi, se ho ben capito.
Clicca per espandere...
Quindi uso la funzione sizeof sommando le variabili che contengono il numero di elementi?

(pensavo di averti risposto ieri notte)
 
Per sapere quanto occupa si, ma non ti serve sommarle tutte: ti è sufficiente sapere quante sono e quindi moltiplicare quel valore per il sizeof della struttura. Se ne hai più di una stesso discorso; poi sommerai questi risultati.
Questo vale se ho capito bene, ovvero se devi sapere quanto occupano tutte le tue strutture istanziate.
 
DispatchCode ha detto:
Per sapere quanto occupa si, ma non ti serve sommarle tutte: ti è sufficiente sapere quante sono e quindi moltiplicare quel valore per il sizeof della struttura. Se ne hai più di una stesso discorso; poi sommerai questi risultati.
Questo vale se ho capito bene, ovvero se devi sapere quanto occupano tutte le tue strutture istanziate.
Clicca per espandere...

In pratica, secondo il codice originale, mi basta fare sizeof di cardinalita alla fine, che sarebbe il numero di elementi totali presenti nella lista, giusto?
Il testo originale chiede "nel campo memoria contiene il numero di bytes utilizzati dalle strutture dati principali interne alla funzione."
 
Non so se questo:

C: 
memoria = sizeof(hash) + sizeof(nodo) + sizeof(risultato) + sizeof(memoria);

faceva parte dello scheletro che il docente vi ha assegnato, o se era codice tuo; nel primo caso è già corretto così.
 
DispatchCode ha detto:
Non so se questo:

C: 
memoria = sizeof(hash) + sizeof(nodo) + sizeof(risultato) + sizeof(memoria);

faceva parte dello scheletro che il docente vi ha assegnato, o se era codice tuo; nel primo caso è già corretto così.
Clicca per espandere...
Esatto, era nella funzione che aveva creato il docente ma che avevo mantenuto nel codice per valutare come utilizzare la struct tipo_risultato.
Memoria infatti contiene la quantità totale di hash, size of di nodo (perchè di un tipo di una struct teoricamente equivalente a int?), di risultato (anche se non è ancora stato usato?) e memoria che è a 0.
Mentre risultato.numero mi sembra corretto
 
Andretti60 ha detto:
Esatto, quella e' l'istruzione da modificare.
Non sentirti imbarazzato, programmare non e' facile e le liste concanetanate sono ostiche.
Clicca per espandere...

Scusami se ti riquoto su questo messaggio, ma riguardo alla linea di codice da modificare di Naive, con cosa bisogna sostituire
FiloRp ha detto:
il While esterno (nodo *tempnodo = l.testa)?
Clicca per espandere...

Ora compila ma dà Segmentation Fault

EDIT: Ho risolto il Segmentation Fault ma non compila correttamente, i numeri inseriti infatti sono sempre gli stessi. E' sbagliato il passaggio che dicevi!
 
Ultima modifica:
Pubblicità
Pubblicità
Indietro
Top