I tipi di dati implementati in C con l'allocazione dinamica della memoria heap si dicono strutture dinamiche: insiemi,
liste, pile, code, sequenze, alberi, grafi, stringhe senza limiti di lunghezza, numeri interi
il cui numero delle cifre non è fissato a priori, ...
La function della libreria stdlib.h (o anche alloc.h)
void *malloc(int n);è essenziale per la costruzione di strutture dinamiche poiché restituisce un puntatore a un blocco di n bytes nella memoria heap oppure NULL se non c'è abbastanza spazio.
Mentre gli "array" sono dati ad accesso casuale, è cioè possibile accedere in maniera diretta a un singolo elemento, una lista è un dato ad accesso sequenziale, cioè bisogna scorrere necessariamente tutti gli elementi che lo precedono. In C le liste non sono strutture predefinite ma si usano array o, meglio ancora, puntatori. Usando questi ultimi si può dire che una lista è
typedef struct elemento { int value; struct elemento *next; } nodo; typedef nodo *listaInt; |
oppure |
typedef struct nodo *listaInt; struct nodo { int value; listaInt next; }; |
main() { // creazione della lista lst vuota listaInt lst=NULL; visualizza(lst); // inserimento in lst di un nodo con valore 1 lst=(listaInt) malloc(sizeof(nodo)); lst->value=1; lst->next=NULL; visualizza(lst); // inserimento in lst di un nodo in fondo con valore 2 listaInt lstAus=lst; lstAus->next=(listaInt) malloc(sizeof(nodo)); lstAus=lstAus->next; lstAus->value=2; lstAus->next=NULL; visualizza(lst); // inserimento in lst di un nodo in testa con valore 3 lstAus=(listaInt) malloc(sizeof(nodo)); lstAus->value=3; lstAus->next=lst; lst=lstAus; visualizza(lst); }dove la procedura visualizza è definita da
void visualizza(listaInt lst){ // visualizzazione della lista lst printf("\n\n"); while (lst!=NULL){ printf("[%d|_]---> ", lst->value); lst = lst->next; } printf(" NULL"); }
esegui scorrendo dal primo al penultimo nodo se un valore e il valore del nodo seguente sono in ordine sbagliato scambiali fintantoché avvengono scambi
punta con P1 al primo nodo della lista ordinata data fintantoché P1 non punta a NULLA punta con P2 al nodo che segue quello puntato da P1 fintantoché P2 non punta a NULLA e i valori puntati da P1 e P2 sono uguali fai scorrere P2 al prossimo nodo elimina dalla lista i doppioni ponendo il nodo puntato da P2 come seguente del nodo puntato da P1 fai scorrere P1 ponendolo uguale a P2
typedef struct elemento { int value; struct elemento *next; } nodo; typedef nodo *pilaInt; pilaInt push(int e, pilaInt p) { pilaInt pAus; pAus = (pilaInt) malloc(sizeof(nodo)); pAus->value = e; pAus->next = p; return pAus; } pilaInt pop(pilaInt p) { return (p!=NULL)? p->next: NULL; } int top(pilaInt p) { return p->value; } void visualizza(pila p){ printf("\n\n\n"); while(p!=NULL){ printf("\n%d",p->value); p=p->next; } printf("\nNULL"); }
Anche questa come le precedenti strutture si può realizzare mediante array
piuttosto che con puntatori.
In questo caso un uso "ingenuo" degli array comporta una certa inefficienza. In particolare
l'estrazione consiste semplicemente nel rendere inutilizzabili i primi elementi
dell'array, con inutile occupazione di memoria.
#include <stdio.h> #define N 50 typedef int tipoValore; typedef struct { int inizio; tipoValore valore[N]; int fine; } coda; typedef enum{false,true} boolean; boolean vuota(coda); boolean piena(coda); coda insert(coda, tipoValore); coda extract(coda); tipoValore testa(coda); coda legge(); void visualizza(coda); main(){ coda p; p = legge(); visualizza(p); printf("\nprimo: %d",testa(p)); printf("\nrimanenti: "); visualizza(extract(p)); } boolean vuota(coda c){ return ((c.inizio+1)%(N+1)==c.fine)? true: false; } boolean piena(coda c){ return (c.inizio==c.fine)? true: false; } coda insert(coda c, tipoValore elem) { if (!piena(c)){ c.valore[c.fine]=elem; c.fine=(c.fine+1)%(N+1); } return c; } coda extract(coda c) { if (!vuota(c)) c.inizio=(c.inizio+1)%(N+1); return c; } tipoValore testa(coda c) { return c.valore[(c.inizio+1)%(N+1)]; }
typedef int tipoValore; typedef struct elemento { tipoValore value; struct elemento *next; } nodo; typedef nodo *coda;
typedef int tipoValore; typedef struct elemento { tipoValore value; struct elemento *next; } nodo; typedef struct{ nodo *first; nodo *last; } coda; coda insert(coda pc, tipoValore elem) { nodo *pnAus; pnAus=(nodo *) malloc(sizeof(nodo)); pnAus->value=elem; pnAus->next=NULL; if (pc.first==NULL){ pc.first=pnAus; pc.last=pnAus; } else{ (pc.last)->next=pnAus; pc.last=pnAus; } return pc; } coda extract(coda p) { p.first=(p.first)->next; return p; } tipoValore primo(coda p){ return (p.first)->value; } tipoValore ultimo(coda p){ return (p.last)->value; }
#include <stdio.h> #include <stdlib.h> typedef int tipoValore; typedef struct elemento { tipoValore value; struct elemento *next; } nodo; typedef nodo *queue; tipoValore first(queue c){ return (c->next)->value; } tipoValore last(queue c){ return c->value; } queue enqueue(queue c,tipoValore elem) { queue pAus=(queue) malloc(sizeof(nodo)); pAus->value=elem; if (c!=NULL){ pAus->next=c->next; c->next=pAus; c=c->next; }else{ pAus->next=pAus;; c=pAus; } return c; } queue dequeue(queue c) { if (c!=NULL) if (c!=c->next) c->next=(c->next)->next; else c=NULL; return c; }
typedef int tipoValore; typedef struct elemento { tipoValore value; struct elemento *next; } nodo; typedef nodo *seqOrd; seqOrd ins(tipoValore ele, seqOrd lst){ seqOrd lstAus=(seqOrd) malloc(sizeof(nodo)); lstAus->value=ele; if (lst!=NULL && ele>lst->value){ seqOrd lst1=lst, lst2=lst->next; while (lst2!=NULL && ele>lst2->value){ lst1=lst2; lst2=lst2->next; } lstAus->next=lst2; lst1->next=lstAus; }else{ lstAus->next=lst; lst=lstAus; } return lst; }