DOMANDA Problemino in c

Pubblicità
filoippo97 ha detto:
il mio prof di programmazione diceva sempre che nel caso non si conoscesse a prescindere il numero di elementi, la lista é sempre l'unica opzione plausibile, perché l'array puoi farlo anche di 1000 elementi, ma se poi lo usi per uno-due allochi memoria per niente, cosí come se vuoi memorizzare piú di 1000 numeri e allora non ti basta. Sinceramente la lista la vedo come l'opzione piú efficiente in termini di memoria proprio perché viene allocata dinamicamente.
Clicca per espandere...

@filoippo97

Allora mi trovo in disaccordo con il tuo docente, o comunque non così d'accordo.

A questo punto è d'uopo una mia spiegazione/motivazione in merito alla divergenza, visto che non siamo in politica (:D) e non è sufficiente, secondo me, non motivare la mia affermazione.


La lista non è l'unica struttura dati allocata dinamicamente, esistono anche gli array dinamici. Due esempi sono std::vector (C++) e java.utils.ArrayList (Java).
L'array viene inizializzato con un determinato numero di elementi (una decina) e poi, quando si raggiunge la dimensione allocata, viene espanso ulteriormente.

In inserimento o rimozione, la linked list è efficiente, considerando l'accesso in un tempo costante (tuttavia vi è dell'overhead dovuto al puntatore).
Le posizioni di un array sono contigue in memoria... quelle di una lista collegata molto probabilmente non lo sono. Questo ha impatti tanto sulla cache, quanto sulla pagine presenti in memoria (nel senso che gli elementi potrebbero trovarsi su più pagine di memoria, per altro anche distanti tra loro, e magari dover essere caricate in quanto non presenti nel TLB o nella MMU).

Ci sono situazioni dove è preferibile utilizzare l'una, ed altre dove è preferibile utilizzare l'altra (e le implementazioni di vector ed ArrayList ne sono una prova).

In questo caso la scelta migliore è un array allocato con calloc e poi l'utilizzo di realloc per allocare memoria aggiuntiva raddoppiando la dimensione precedente dell'array.
 
Ultima modifica:
Bonfi97 ha detto:
  • Beh, la diffrenza fra un'array dinamico e una listà è parecchia, anche in termini di prestazioni.
  • Il cast è implicito, è necessaio solo in caso si usino vecchissimi compilatori. Il "GNU C Library Reference" dice
  • Per qualcuo che sta imparando a programmare in C è sempre una buona cosa ricordarsi di mettere gli argomenti al main (proprio a livello di apprendiment, così, nel caso debba usarli in un qualche caso più avanti conosca già la sintassi corretta). Inoltre, non è che se non gli impieghi quegli argomenti non esistano...
  • Si preferisce dichiarare le varibili all'inizio delle funzioni proprio per questo caso: immagina di avere un funzione lunga qualche centinaia di righe, se dichiari una varibile in mezzo al programma impiegherai certamente più tempo a trovarla in caso tudebba farci qualcosa, rispetto ad averla all'inizio.
  • NULL è semplicemente una define dello 0, nulla di più. Non mi pareva il caso di introdurre il NULL quando poteva tranquillamente esserev evitato.
  • Tanto è un carattere ascii, lo puoi mettere tranquillamente nella stringa senza disturbare il %c.
  • Le parentesi graffe per i for, if ed else con un'istruzione sola si possono tranquillamente evitare, soprattutto se il codice è identato bene.
  • Ecco come non programare: l'heap non è infinito (tantmeno la memoria disponibile), quando finisci di usare una spazio allocato liberalo sempre.
PS: il codice l'ho provato e andava perfettamente.
PPS: il Deitel non l'ho mai letto, però una volta me l'hanno addirittura sconsigliato.
Clicca per espandere...
  • beh prestazioni... non é che lo dobbiamo far girare su uno zilog Z80 :asd: in entrambi i casi a livello operativo la differenza é minima.
  • non é assolutamente vero, tant'é che sia visual studio che dev C++ lo riportano come errore di compilazione e non riescono a compilarlo. E poi cioé, mi vieni a dire di aggiungere gli argomenti al main che in questo caso sono altamente inutili e dai per scontato cose fondamentali come il cast della malloc che senza di quello non funziona?
  • forse l'avró usato una volta nella mia vita :asd: La maggior parte dei programmi che ho scritto hanno main con argomento void.
  • auguri a leggere un grosso programma allora. Se per te andare sulla riga sopra é piú difficile di scrollare tutto il codice...
  • beh se restituisce null, va introdotto anche quello.
  • tant'é vero che mi stampa due barrette anziché il grado.
  • sempre meglio inserirle, alcuni ide lavorano meglio, specie visual studio. Comunque é vero che possono essere anche omesse, ma preferisco sempre aggiungerle, male non fa.
  • certo, ma visto che il programma finisce quando finisce la malloc stessa, non ha senso usare free dal momento che si libera comunque con il termine del programma.
PS: il codice l'ho provato e a me non funziona né in visual studio né in dev C++ :asd:
PPS: Il deitel é il libro di riferimento per il C :asd: ci ho studiato sopra e sono ben pochi i libri fatti cosí bene.
 
Finalmente riesco a rispondere, a distanza di una settimana.
A titolo esemplificativo, questo è un modo in cui può essere creato un array dinamico. Al fine di semplificarne la lettura ho evitato i controlli del caso sulla validità dei puntatori.

dynamic_array.h
C: 
#ifndef _DYNAMIC_ARRAY
#define _DYNAMIC_ARRAY 1


#define INITIAL_SIZE 10


typedef struct _dynamic_array
{
    int *array;
    int size;
    int tos;
} dynamic_array;


extern void insert(dynamic_array*, int);
extern int  get(dynamic_array*, int);
extern int  size(dynamic_array*);
extern int  capacity(dynamic_array*);

#endif

dynamic_array.c
C: 
#include <stdlib.h>

#include "dynamic_array.h"


void insert(dynamic_array *vector, int value)
{
    if(vector->tos >= vector->size)
    {
        int new_size  = vector->size << 1;
        vector->array = realloc(vector->array, new_size*sizeof(int));
        vector->size  = new_size;
    }
   
    vector->array[vector->tos++] = value;
}

int get(dynamic_array *vector, int index)
{
    if(index < vector->tos) return vector->array[index];
    return -1;
}

int size(dynamic_array *vector)
{
    return vector->tos;
}

int capacity(dynamic_array *vector)
{
    return vector->size;
}

dynamic_array_test.c
C: 
#include <stdio.h>
#include <stdlib.h>

#include "dynamic_array.h"


int main()
{
    dynamic_array vector;
    vector.array = calloc(INITIAL_SIZE, sizeof(int));
    vector.size  = INITIAL_SIZE;
    vector.tos   = 0;
   
    int i;
    for(i = 0; i<INITIAL_SIZE+9; i++)
    {
        insert(&vector,i);
    }
   
    for(i=0; i<size(&vector); i++)
    {
        printf("%d\n", get(&vector, i));
    }
   
    printf("\n\n");
    printf("Size: %d\n", size(&vector));
    printf("Capacity: %d", capacity(&vector));
   
    return 0;
}
 
Stefanokj ha detto:
Cosa intendi con "soluzione scolastica"?
Clicca per espandere...
Questa è la soluzione che a scuola o all'università si usa all'inizio del corso ( perchè non si è ancora visto puntatori, liste ecc. ) e principalmente per farti usare il for e gli array. Come detto nei commenti precedenti, se metti 51 valori ti darà errore.
 
Pubblicità
Pubblicità
Indietro
Top