PROBLEMA Algoritmo ricerca occorenze con lista concatenata - C

FiloRp

Utente Attivo
393
24
CPU
Intel Core i5 4690
Scheda Madre
Asus Z97 Deluxe
HDD
SSD 256GB + HDD 2TB
RAM
16GB
GPU
NVidea Geforce GTX 980
Monitor
DELL U2515H
PSU
Corsair CX750M Bronze
Case
Cooler Master N300
OS
Windows 10
-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.
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?
 

DispatchCode

Moderatore
Staff Forum
Utente Èlite
2,208
1,845
CPU
Intel I9-10900KF 3.75GHz 10x 125W
Dissipatore
Gigabyte Aorus Waterforce X360 ARGB
Scheda Madre
Asus 1200 TUF Z590-Plus Gaming ATX DDR4
HDD
1TB NVMe PCI 3.0 x4, 1TB 7200rpm 64MB SATA3
RAM
DDR4 32GB 3600MHz CL18 ARGB
GPU
Nvidia RTX 3080 10GB DDR6
Audio
Integrata 7.1 HD audio
Monitor
LG 34GN850
PSU
Gigabyte P850PM
Case
Phanteks Enthoo Evolv X ARGB
Periferiche
MSI Vigor GK30, mouse Logitech
Net
FTTH Aruba, 1Gb (effettivi: ~950Mb / ~480Mb)
OS
Windows 10 64bit / OpenSUSE Tumbleweed
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ì?
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
 

FiloRp

Utente Attivo
393
24
CPU
Intel Core i5 4690
Scheda Madre
Asus Z97 Deluxe
HDD
SSD 256GB + HDD 2TB
RAM
16GB
GPU
NVidea Geforce GTX 980
Monitor
DELL U2515H
PSU
Corsair CX750M Bronze
Case
Cooler Master N300
OS
Windows 10
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
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);
 

Andretti60

Utente Èlite
6,440
5,091
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.
 
  • Mi piace
Reazioni: fabio93 e FiloRp

FiloRp

Utente Attivo
393
24
CPU
Intel Core i5 4690
Scheda Madre
Asus Z97 Deluxe
HDD
SSD 256GB + HDD 2TB
RAM
16GB
GPU
NVidea Geforce GTX 980
Monitor
DELL U2515H
PSU
Corsair CX750M Bronze
Case
Cooler Master N300
OS
Windows 10
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.
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?
 

Andretti60

Utente Èlite
6,440
5,091
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
 
  • Mi piace
Reazioni: FiloRp

DispatchCode

Moderatore
Staff Forum
Utente Èlite
2,208
1,845
CPU
Intel I9-10900KF 3.75GHz 10x 125W
Dissipatore
Gigabyte Aorus Waterforce X360 ARGB
Scheda Madre
Asus 1200 TUF Z590-Plus Gaming ATX DDR4
HDD
1TB NVMe PCI 3.0 x4, 1TB 7200rpm 64MB SATA3
RAM
DDR4 32GB 3600MHz CL18 ARGB
GPU
Nvidia RTX 3080 10GB DDR6
Audio
Integrata 7.1 HD audio
Monitor
LG 34GN850
PSU
Gigabyte P850PM
Case
Phanteks Enthoo Evolv X ARGB
Periferiche
MSI Vigor GK30, mouse Logitech
Net
FTTH Aruba, 1Gb (effettivi: ~950Mb / ~480Mb)
OS
Windows 10 64bit / OpenSUSE Tumbleweed
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);

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.
 

FiloRp

Utente Attivo
393
24
CPU
Intel Core i5 4690
Scheda Madre
Asus Z97 Deluxe
HDD
SSD 256GB + HDD 2TB
RAM
16GB
GPU
NVidea Geforce GTX 980
Monitor
DELL U2515H
PSU
Corsair CX750M Bronze
Case
Cooler Master N300
OS
Windows 10
@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:

DispatchCode

Moderatore
Staff Forum
Utente Èlite
2,208
1,845
CPU
Intel I9-10900KF 3.75GHz 10x 125W
Dissipatore
Gigabyte Aorus Waterforce X360 ARGB
Scheda Madre
Asus 1200 TUF Z590-Plus Gaming ATX DDR4
HDD
1TB NVMe PCI 3.0 x4, 1TB 7200rpm 64MB SATA3
RAM
DDR4 32GB 3600MHz CL18 ARGB
GPU
Nvidia RTX 3080 10GB DDR6
Audio
Integrata 7.1 HD audio
Monitor
LG 34GN850
PSU
Gigabyte P850PM
Case
Phanteks Enthoo Evolv X ARGB
Periferiche
MSI Vigor GK30, mouse Logitech
Net
FTTH Aruba, 1Gb (effettivi: ~950Mb / ~480Mb)
OS
Windows 10 64bit / OpenSUSE Tumbleweed
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.
 
  • Mi piace
Reazioni: FiloRp

FiloRp

Utente Attivo
393
24
CPU
Intel Core i5 4690
Scheda Madre
Asus Z97 Deluxe
HDD
SSD 256GB + HDD 2TB
RAM
16GB
GPU
NVidea Geforce GTX 980
Monitor
DELL U2515H
PSU
Corsair CX750M Bronze
Case
Cooler Master N300
OS
Windows 10
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.
Quindi uso la funzione sizeof sommando le variabili che contengono il numero di elementi?

(pensavo di averti risposto ieri notte)
 

DispatchCode

Moderatore
Staff Forum
Utente Èlite
2,208
1,845
CPU
Intel I9-10900KF 3.75GHz 10x 125W
Dissipatore
Gigabyte Aorus Waterforce X360 ARGB
Scheda Madre
Asus 1200 TUF Z590-Plus Gaming ATX DDR4
HDD
1TB NVMe PCI 3.0 x4, 1TB 7200rpm 64MB SATA3
RAM
DDR4 32GB 3600MHz CL18 ARGB
GPU
Nvidia RTX 3080 10GB DDR6
Audio
Integrata 7.1 HD audio
Monitor
LG 34GN850
PSU
Gigabyte P850PM
Case
Phanteks Enthoo Evolv X ARGB
Periferiche
MSI Vigor GK30, mouse Logitech
Net
FTTH Aruba, 1Gb (effettivi: ~950Mb / ~480Mb)
OS
Windows 10 64bit / OpenSUSE Tumbleweed
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.
 

FiloRp

Utente Attivo
393
24
CPU
Intel Core i5 4690
Scheda Madre
Asus Z97 Deluxe
HDD
SSD 256GB + HDD 2TB
RAM
16GB
GPU
NVidea Geforce GTX 980
Monitor
DELL U2515H
PSU
Corsair CX750M Bronze
Case
Cooler Master N300
OS
Windows 10
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.

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."
 

DispatchCode

Moderatore
Staff Forum
Utente Èlite
2,208
1,845
CPU
Intel I9-10900KF 3.75GHz 10x 125W
Dissipatore
Gigabyte Aorus Waterforce X360 ARGB
Scheda Madre
Asus 1200 TUF Z590-Plus Gaming ATX DDR4
HDD
1TB NVMe PCI 3.0 x4, 1TB 7200rpm 64MB SATA3
RAM
DDR4 32GB 3600MHz CL18 ARGB
GPU
Nvidia RTX 3080 10GB DDR6
Audio
Integrata 7.1 HD audio
Monitor
LG 34GN850
PSU
Gigabyte P850PM
Case
Phanteks Enthoo Evolv X ARGB
Periferiche
MSI Vigor GK30, mouse Logitech
Net
FTTH Aruba, 1Gb (effettivi: ~950Mb / ~480Mb)
OS
Windows 10 64bit / OpenSUSE Tumbleweed
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ì.
 

FiloRp

Utente Attivo
393
24
CPU
Intel Core i5 4690
Scheda Madre
Asus Z97 Deluxe
HDD
SSD 256GB + HDD 2TB
RAM
16GB
GPU
NVidea Geforce GTX 980
Monitor
DELL U2515H
PSU
Corsair CX750M Bronze
Case
Cooler Master N300
OS
Windows 10
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ì.
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
 

FiloRp

Utente Attivo
393
24
CPU
Intel Core i5 4690
Scheda Madre
Asus Z97 Deluxe
HDD
SSD 256GB + HDD 2TB
RAM
16GB
GPU
NVidea Geforce GTX 980
Monitor
DELL U2515H
PSU
Corsair CX750M Bronze
Case
Cooler Master N300
OS
Windows 10
Esatto, quella e' l'istruzione da modificare.
Non sentirti imbarazzato, programmare non e' facile e le liste concanetanate sono ostiche.

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

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:

Entra

oppure Accedi utilizzando
Discord Ufficiale Entra ora!

Discussioni Simili