[C] Allocazione dinamica di un array senza saperne la dimensione

[ballatommy]

Ciao a tutti,

volevo sapere in che modo era possibile allocare dinamicamente un array (o una stringa) senza saperene precedentemente la dimensione. Posto un esercizio per spiegarvi meglio il mio dubbio:

Sidefiniscano le funzioni leggi e cerca,ed il relativo codice chiamante. La funzione leggi popola un array di interi leggendo una sequenza di valori terminata dal valore -99. La funzione cerca cerca un valore k in un array e ritorna gli indici corrispondenti alle posizioni in cui si trova tale valore.

In che modo il sottoprogramma leggi può popolare un array se non si sa la dimensione di esso?

Grazie a tutti

[minomic]

Semplicemente non può. Per allocare una certa quantità di memoria... devi sapere questa quantità! Quindi qui le strategie possibili sono principalmente due:
1. fai una prima passata per vedere quanti elementi devi memorizzare, poi allochi l'array, poi fai una seconda passata per memorizzare effettivamente i dati nell'array
2. allochi un po' di spazio (una tua stima delle dimensioni) e riempi l'array finché c'è posto. Quando lo spazio è esaurito, ne allochi dell'altro con la funzione realloc.

Vedi tu quale ti piace di più... Probabilmente ci sono anche altre idee, ma queste mi sembrano già un discreto punto di partenza.

[torn24]

Ciao, in un certo senso, è proprio lo scopo dell'allocazione dinamica risolvere questo problema.
Oltre la funzione malloc(), è disponibile la funzione realloc(), che consente di "aumentare" la dimensione dell'array, quindi ti basta tener conto degli elementi letti, e aumentare di un intero la dimensione dell'array ad ogni lettura.
Array=(*int)realloc(Array,(++elementi)*sizeof(int) ); //aumento gli elementi di uno, e calcolo la nuova memoria

[Scara95]

ecco, evita di allocare oggetto a oggetto. È il miglior modo per rendere inefficiente un programma

[minomic]

Esatto! Infatti nel mio post avevo scritto di allocare "dell'altro spazio", intendendo una certa quantità che stimiamo possa essere sufficiente.

[ballatommy]

Sapeva della realloc e avevo considerato i vari metodi, mi chiedevo appunto se ne esistesse uno più semplice e lineare.

grazie a tutti, siete stati davvero d'aiuto

[minomic]

No, direi di no. Se passiamo al C++ abbiamo contenitori che si espandono dinamicamente (i vector) ma in C dobbiamo fare tutto "a mano".

[MItaly]

Per inciso, in genere il metodo che si usa è raddoppiare sempre la dimensione dell'array, in modo da raggiungere la dimensione finale in O(log n) tentativi, lasciando inutilizzata nel caso peggiore la metà meno uno degli elementi allocati.

(anche se, oltre certe dimensioni, spesso per evitare di sprecare troppo si diminuisce il moltiplicatore o si passa ad una crescita lineare "a chunk")

[Scara95]

Puoi farti un ADT..
Una struct con dimensione, numero oggetti, array, primitive per inserimento e lookup

[ballatommy]

Qualcuno riuscirebbe a fornirmi quindi una soluzione dell'esercizio (solamente la parte Leggi usando malloc e realloc, altrimenti riuscireste a correggere il mio?
Grazie davvero a tutti!

 #include <stdio.h>#include <stdlib.h>
#include <malloc.h>


int* leggi()
{
    int *array, n, i;


    i=0;
    array=(int*)malloc(sizeof(int)*i);
    i++;
    scanf("%d", array);




    do{
        scanf("%d", &n);
        array=(int)realloc(sizeof(int)*i);        
        *(array+i)=n;        
        i++;
    }while(n!=-99);


    return;
}


int main (int argc, char*argv[])
{


    leggi();


    return 0;
}
}

Vi riscrivo l'esercizio: Si definiscano le funzioni leggi e cerca,ed il relativo codice chiamante. La funzione leggi popola un array di interi leggendo una sequenza di valori terminata dal valore -99. La funzione cerca cerca un valore k in un array e ritorna gli indici corrispondenti alle posizioni in cui si trova tale valore.


Grazie