STRUTTURE LINEARI DINAMICHE

pagine di Roberto Ricci L.S. "A. Righi", Bologna. Ultima revisione

 
 
 

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.


 
 

Liste


  Con una definizione ricorsiva, che viene naturale, una lista è Come ogni tipo di dato astratto, il tipo lista è definito concretamente in base a alle operazioni primitive che si possono eseguire sugli oggetti di quel tipo: costruzione (della lista vuota o della lista con data testa e data coda), selezione (della testa, della coda), valutazione (dell'essere vuota o meno).

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 è

Ad esempio per definire una lista di interi:
typedef struct elemento {
    int value;
    struct elemento *next;
} nodo;

typedef nodo *listaInt;
oppure 
typedef struct nodo *listaInt;

struct nodo {
    int value;
    listaInt next;
};
  1. Come introduzione alle liste, redigere ed eseguire un programma con il seguente blocco d'istruzioni 
    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");
}
  2. Realizzare un programma che, dopo aver letto il valore di n, costruisca una lista n di interi con inserimenti in fondo.
  3. Realizzare una function per la lettura di n interi con inserimento in fondo
  4. Aggiungere una function per ordinare una lista con metodo bubblesort 
    esegui
	scorrendo dal primo al penultimo nodo
		se un valore e il valore del nodo seguente sono in ordine sbagliato 
			scambiali 
fintantoché avvengono scambi
  5. Aggiungere una function per eliminare i doppioni da una lista ordinata 
    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

 
 
 

Pile


  Una pila è una struttura nella quale poter essenzialmente: inserire un elemento (push), togliere l'elemento inserito per ultimo (pop), vedere l'ultimo elemento inserito (top).
Come esempio concreto si può pensare a una pila di piatti: si può inserire un altro piatto sopra tutti gli altri, si può prelevarne a partire dalla sommità, si può vedere il piatto sopra tutti.
  1. Completare il seguente testo, che implementa mediante puntatori una pila di numeri interi, in un programma per leggere una pila di interi e visualizzarla. 
    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");
}
  2. Realizzare una function per invertire una pila
  3. Realizzare una function per sovrapporre una pila a un'altra pila
  4. Mediante una pila controllare se una data espressione algebrica ha parentesi inserite correttamente. Per questo inserire '(' nella pila ogni volta che lo si incontra e togliere quello appena inserito quando s'incontra ')'.

 
 
 

Code


  La coda è una struttura nella quale poter essenzialmente: inserire un valore in coda (enqueue), estrarre la testa (dequeue), leggere la testa.

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.

  1. Redigere, completare ed eseguire il seguente programma che implementa una coda mediante lo strattagemma degli 'array circolari' (si osservi che in questo modo la struttura non è dinamica). 
    #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)];
}
  2. Redigere ed eseguire un programma che rappresenti una coda mediante puntatori 
    typedef int tipoValore;

typedef struct elemento {
	 tipoValore value;
	 struct elemento *next;
} nodo;

typedef nodo *coda;
  3. Redigere ed eseguire un programma più efficiente che utilizzi, oltre a un puntatore alla testa della struttura, anche un puntatore all'ultimo nodo. 
    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;
}
  4. Redigere, completare ed eseguire il seguente programma per implementare la struttura coda mediante liste circolari: 
    #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;
}

 
 
 

Liste ordinate


  La sequenza è una struttura dati dinamica caratterizzata essenzialmente dalla possibilità di associare a ogni elemento una posizione, quindi rende possibile inserire un elemento in posizione data, eliminare l'elemento in posizione data, leggere l'elemento un posizione data.
In una sequenza ordinata -o lista ordinata- la posizione è implicita nella scelta del criterio d'ordinamento e quindi la struttura è caratterizzata dalla possibilità di inserire elementi ordinatamente ed eliminarli.
  1. Redigere ed eseguire un programma per leggere e visualizzare liste ordinate crescenti di numeri interi. E' suggerita nel seguito la modalità d'implementazione mediante puntatori e fornita una function per l'inserimento. 
    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;
}
  2. Realizzare un programma per effettuare la ricerca di un dato in una sequenza ordinata crescente ed eliminarlo.
pagine di Roberto Ricci L.S. "A. Righi", Bologna. Ultima revisione