[C] Contare le presenze di un elemento in array

[torejx]

ciao ragazzi la domanda può sembrarvi banale ma non riesco a venirne fuori... Ho una funzione che deve restituire il numero che si ripete più volte all'interno di una matrice... Non vi chiedo il codice ma vorrei capire come "pensare" la risoluzione di questo problema... in poche parole l'algoritmo per contare le presenze di un elemento all'interno di array..grazie mille...

[MItaly]

Il concetto è lo stesso di questa discussione... solo che qui non hai né la certezza di quanti elementi diversi sono contenuti nell'array (e quindi devi considerare l'ipotesi più pessimistica, ossia che possano essere tutti diversi, ossia creare un array in cui vengono contati gli elementi di ciascun tipo delle stesse dimensioni di quello da elaborare) né una corrispondenza diretta elemento->indice dell'array delle presenze. Di che tipo di dato è l'array su cui devi lavorare?

[torejx]

nel mio caso una matrice di interi...

[kentaromiura]

devi usare un array a dimensione variabile,
nei 15 header standard c'e' la funzione realloc che ti può aiutare nel tuo scopo

void *realloc(void *block, size_t size);
rialloca memoria gia' allocata ritornando l'indirizzo della
nuova memoria allocata

ecco un esempio pratico
http://www.eng.cam.ac.uk/help/tpl/la..._C/node52.html

quindi crei due array dinamici, uno che contiene tutti gli elementi che trovi nella matrice,
l'altro che contiene le occorrenze dell'elemento che stai controllando.

[MItaly]

Secondo me riallocare l'array delle presenze ogni volta che si trova un nuovo elemento è uno spreco di cicli di CPU inutile, a meno che l'array da elaborare non sia veramente grande (diciamo oltre 5 MB di array, ossia oltre i 1310720 interi).

[kentaromiura]

in caso fosse troppo lento può sempre allocare un buffer di 10 elementi o 100 elementi,
invece che 1 a 1,
:rollo:

[MItaly]

Ecco una soluzione che non usa nessun array aggiuntivo, così siamo tutti più contenti:

#include <stdlib.h>
int getFashion(int * inarray, int elements);
int compFunction(const void * elem1, const void * elem2);
void main()
{
     int intarray[]={16, 51, 84, 83, 15, 15, 15, 15, 15, 10, 84};
     printf("%d",getFashion(intarray,sizeof(intarray)/sizeof(int)));
     getch();
     return;
}
int getFashion(int * inarray, int elements)
{
     int pivotelem=0;
     int pivotoccur=1;
     int curoccur=1;
     int c;
     qsort(inarray, elements, sizeof(int), compFunction);
     pivotelem=inarray[0];
     for(c=1; c<elements; c++)
     {
             if(inarray[c]==inarray[c-1])
                 curoccur++;
             else
             {
                 if(curoccur>pivotoccur)
                 {
                     pivotoccur=curoccur;
                     pivotelem=inarray[c-1];
                 }
                 curoccur=1;
             }                        
     }
     if(curoccur>pivotoccur)
     {
          pivotoccur=curoccur;
          pivotelem=inarray[c-1];
     }
     return pivotelem;
}
int compFunction(const void * elem1, const void * elem2)
{
    int int1=*((int *)elem1);
    int int2=*((int *)elem2);
    if (int1>int2) return 1;
    else if (int2>int1) return -1;
    else return 0;
}

L'algoritmo che ho scritto in primo luogo ordina l'array (richiamando qsort), così da compattare i valori in blocchi omogenei; quindi scorre l'array individuando il salto da un blocco all'altro, contando di quanti elementi consta ciascun blocco e confrontando tale valore con le occorrenze dell'elemento "pivot" (quello che, fino a questo momento, aveva il numero maggiore di occorrenze). Se l'ultimo blocco ha più occorrenze del pivot allora diventa il nuovo pivot; dopo aver scorso tutto l'array viene restituito il pivot.

[torejx]

ehm...scusate la mia inesperienza ma prima di leggere i vostri post avevo provato a farlo in questa maniera: ho creato una matrice di ugale dim e in ogni cella della seconda matrice ho inserito il numero di occorrenze dell'elemento della stessa posizione nella prima matrice.. ad esempio se in mat1[0][0] ho il numero 2 in mat2[0][0] ho il numero di occorrenze di due... naturalmente ciò porta ad avere ridondanza, nel senso che nel caso di valori uguali l'occorrenza sarà memorizzata ogni volta che viene incontrato lo stesso valore...poi ho trovato il max nella seconda matrice e quindi il numero che corrispondeva al max nella prima matrice...
vi posto il codice (non so se ci siano errori):

int occorre_piu_volte(Tabella t){

int conta(Tabella t,int valore);

    int i,j,max=0,occorre=0;
    Tabella t2={0};
    for (i=0;i<N;i++){
        for (j=0;j<M;j++){
            t2[i][j]=conta(t,t[i][j]);
            if (t2[i][j]>max){
               max=t2[i][j];
               occorre=t[i][j];
            }
        }
    }
    return occorre;
}
        
        
int conta(Tabella t,int valore){
    int i,j,conta=0;
    for (i=0;i<N;i++){
        for (j=0;j<M;j++){
            if (t[i][j]==valore)
               conta++;
        }
    }
    return conta;
}