Struttura dati Coda



Scaricare 68.77 Kb.
29.12.2017
Dimensione del file68.77 Kb.

Prof.Ing.S.Cavalieri

L’ADT Coda in Linguaggio C a.a.2009/2010



La Struttura Dati Astratta (ADT) Coda
La coda o queue è una struttura dati astratta in cui l'inserimento e l’estrazione sono consentite solo in specifiche posizioni; in particolare, l'inserimento è consentito solo ad un estremo, detto rear, e l’estrazione è consentita solo all'altro estremo, detto front. Questa gestione è anche chiamata FIFO (First In First Out), in quanto il primo elemento inserito è anche il primo ad essere estratto.

Sia data una coda composta dagli elementi a1, a2, a3, …., an e si supponga che la posizione rear sia rappresentata dalla posizione dell’elemento an. L'inserimento di un elemento x produce la nuova coda a1, a2, a3, …., an, x. L’elemento di posizione rear diviene x. L’estrazione di un elemento della coda si riferisce all’elemento di posizione front ossia a1; dopo l’operazione di estrazione la coda diviene a2, a3, …., an, x.



1.Operazioni Primitive sull’ADT Coda


La struttura dati Coda è caratterizzata da alcune operazioni fondamentali, che nel seguito verrano illustrate. Sia:

  • q una generica coda

  • x un generico elemento dello stesso tipo degli elementi presenti nella Coda q. Nel seguito il tipo degli elementi contenuti in una coda verrà chiamato tipobaseQueue.

Le seguenti operazioni primitive vengono definite per un ADT Coda:



  • MakeNullQueue(q). La funzione restituisce una Coda inizializzata, ossia pronta ad accogliere nuovi elementi.

  • EmptyQueue(q). La funzione restituisce il valore booleano vero se la Coda è vuota.

  • FullQueue(q). La funzione restituisce il valore booleano vero se la Coda è piena.

  • EnQueue(q,x). Questa funzione inserisce l'elemento x nella posizione rappresentata dal rear. Se q è la Coda a1, a2,…, an, e se il rear è rappresentato dalla posizione dell'ultimo elemento an, l'inserimento dell'elemento x avviene in posizione successiva a tale elemento, e la funzione EnQueue(q,x) restituisce la nuova Coda a1, a2,…, an,x.

  • DeQueue(q). Questa funzione elimina l'elemento della coda in posizione front. Se q è la Coda a1, a2,…, an e il front è rappresentato dalla posizione del primo elemento a1, la chiamata alla funzione DeQueue(q) restituisce la nuova coda a2,a3,…, an e il nuovo front è rappresentata dalla posizione dell'elemento a2.

  • Front(q). La funzione restituisce il primo elemento della coda (l’elemento viene solamente letto, non viene estratto).



2.Rappresentazione della Struttura Dati Coda


Per la Coda verranno considerate due rappresentazioni: quella sequenziale con vettore e quella collegata con puntatori.

2.1.Rappresentazione Sequenziale


La rappresentazione sequenziale di un ADT Coda con vettore può essere realizzata come mostrato dalla seguente figura.

Come si vede, vengono utilizzate due variabili, front e rear, che indicano rispettivamente la posizione del primo elemento della coda e dell'ultimo elemento della coda.

Inizialmente, quando la coda è vuota si assume che front=rear=-1.

Quando viene inserito il primo elemento, rear viene posto a 0 e l'elemento viene inserito nel vettore nella componente di indice rear (ossia 0). Anche front viene assegnato a 0, in quanto è necessario rappresentare la presenza dell’unico elemento in coda.

Quando un nuovo elemento deve essere inserito successivamente, rear viene incrementato di 1 e l'elemento viene inserito nella nuova posizione fornita da rear. Si noti che l'incremento dell’indice rear è circolare, come è mostrato nella seguente figura:

Nella figura è chiaro che, prima dell'inserimento, rear corrisponde all'ultimo elemento del vettore. Il nuovo elemento può essere inserito nella prima posizione del vettore, ottenuta incrementando rear nella seguente maniera:


rear=(rear+1) % N, dove N è la dimensione del vettore
L'inserimento di un elemento è possibile solo se la coda non è piena. La condizione di coda piena è rappresentata dalle seguenti figure:

In questi esempi, è chiaro che il valore di rear non può essere più incrementato per inserire un nuovo elemento. La condizione di coda piena è dunque:
front = = (rear+1)%N
Per quanto riguarda la cancellazione dell'elemento di posizione front, essa viene semplicemente realizzata incrementando la variabile front. Dopo aver effettuato la cancellazione, è ovviamente necessario verificare che la coda non diventi vuota, perché in tal caso bisogna aggiornare la variabile rear. Se la coda diviene vuota, sia front che rear divengono pari a -1. La condizione di coda vuota viene controllata prima della cancellazione dell'elemento front. Se front e rear sono coincidenti, significa che la coda possiede un solo elemento, cioè quello che deve essere eliminato. Ciò significa che dopo l'inserimento la coda diverrà vuota.

L’incremento della variabile front deve avvenire in modo circolare, analogamente a quanto visto per la variabile rear. Ad esempio si consideri la seguente cancellazione di un elemento:



Analogamente a quanto visto per la variabile rear, l’incremento della variabile front deve avvenire nella seguente maniera:
front=(front+1) % N, dove N è la dimensione del vettore
Nel seguito verrà mostrata la rappresentazione sequenziale in C di un ADT Coda mediante il tipo di dato vettore.

Nella rappresentazione in C verrà utilizzato un tipo di nome tipobaseQueue per rappresentare il generico tipo di dato di ogni singolo elemento contenuto nella coda. La definizione del tipo tipobaseQueue avverrà in C tramite lo strumento typedef. Ad esempio se il tipo di dato di ogni singolo elemento fosse float, l’implementazione del tipo tipobaseQueue risulterebbe:


typedef float tipobaseQueue;
Visto che molte funzioni primitive sulla Coda restituiscono un valore booleano, converrà definire il tipo boolean, definito come alias del tipo di dato short, ossia:
typedef short boolean;
La coda verrà rappresentata in C da una struttura, di nome queue, composta da tre campi: il vettore info che contiene gli elementi della coda, gli interi front e rear che individuano la posizione del primo e dell'ultimo elemento della coda. La sua implementazione è:
#define N 10
typedef struct {

tipobaseQueue info[N];

int front,rear;

} queue;
Nell’implementazione in C della struttura coda, sarà necessario l’utilizzo di una costante per rappresentare la condizione di coda vuota. Tale condizione si verifica quando front e rear assumono il valore -1. La condizione di coda vuota può essere, dunque, rappresentata da una costante, denominata CODAVUOTA, pari al valore –1. La costante CODAVUOTA può essere rappresentata dalla seguente definizione:


#define CODAVUOTA –1

Rappresentazione delle Operazioni Primitive


Le seguenti procedure e funzioni realizzano le operazioni primitive della coda:
void MakeNullQueue(queue *q) {

q->front=q->rear=CODAVUOTA;

}
boolean EmptyQueue(queue q) {

return(q.front==CODAVUOTA);

}
boolean FullQueue(queue q) {

return(q.front==((q.rear+1)%N));

}
void EnQueue(queue *q, tipobaseQueue x) {

if (!FullQueue(*q)) {

q->rear=(q->rear+1)%N;

q->info[q->rear]=x;

if (q->front==CODAVUOTA) q->front=q->rear;

}

}


void DeQueue(queue *q) {

if (!EmptyQueue(*q)) {

if (q->front==q->rear) MakeNullQueue(q);

else q->front=(q->front+1)%N;

}

}
tipobaseQueue Front(queue q) {



if (!EmptyQueue(q))

return(q.info[q.front]);

}

2.2.Rappresentazione Collegata con Puntatori


La rappresentazione collegata con puntatori di una struttura dati Coda può avvenire secondo quanto mostrato dalla seguente figura.

Le variabili front e rear rappresentano i puntatori al primo e all'ultimo elemento della coda, rispettivamente. Ciascun elemento della coda è rappresentato da uno struct composto da due campi: il contenuto informativo (rappresentato da ciascun elemento della coda) e il puntatore al successivo elemento. Il campo puntatore dell'ultimo elemento viene messo a NULL per convenzione, al fine di distinguere l'ultimo elemento.

L'inserimento di un nuovo elemento viene realizzato attraverso il puntatore rear, come mostrato dalla seguente figura. Come visibile, rear assume il valore dell'indirizzo del nuovo elemento, e il campo puntatore dell'elemento che prima dell'inserimento era l'ultimo, assume anch'esso il valore dell'indirizzo del nuovo elemento. Ovviamente il campo puntatore (ossia il campo che contiene l’indirizzo del successivo elemento) del nuovo elemento inserito viene posto a NULL.

Nel caso la coda fosse vuota, tale condizione viene espressa dal valore NULL per entrambe le variabili front e rear. Nel caso di inserimento in una coda vuota, entrambe le variabili front e rear assumono l'indirizzo dell'unico elemento inserito, come mostrato dalla seguente figura.

L'estrazione di un elemento dalla coda viene realizzato tramite il puntatore front, come visibile dalla figura.

Come si vede, il primo elemento viene eliminato e il valore di front assume l'indirizzo del secondo elemento. Ovviamente nel caso in cui la coda ha un solo elemento, l'estrazione del primo elemento comporterà che sia front sia rear assumino il valore di NULL, al fine di indicare nuovamente la condizione di coda vuota.

La precedente rappresentazione può essere definita in C nella seguente maniera.

Innanzitutto, come già detto in precedenza, si farà uso del tipo tipobaseQueue, che rappresenta il tipo di dato di ogni singolo elemento contenuto nella coda. Il tipo tipobaseQueue verrà definito in C tramite il comando typedef. Ad esempio se il tipo di dato di ogni singolo elemento fosse uno struct contenente i campi: cognome, nome, età, l’implementazione del tipo tipobaseQueue risulterebbe:


#define S 15
typedef struct {

char cognome[S], nome[S];

unsigned short eta;

}tipobaseQueue;


L’implmentazione in C della struttura dati Coda realizzata con puntatori, farà uso del tipo boolean, per rappresentare i valori booleani forniti da alcune funzioni primitive. Il tipo boolean può essere implementato come alias del tipo di dato short, ossia:
typedef short boolean;
La struttura dati Coda è rappresentata dal tipo queue (mostrato nel seguito) che è una struct che contiene i puntatori al primo e all'ultimo elemento della coda stessa. Tali puntatori sono front e rear. Essi puntano ad elementi di tipo struct nodoQueue, composti da due campi: info e next. Il campo info contiene un elemento di tipo tipobaseQueue, mentre il campo next contiene il puntatore all’elemento successivo. L’implementazione della struttura dati Coda è composta, dunque, dalle seguenti due strutture:
struct nodoQueue {

tipobaseQueue info;

struct nodoQueue *next;

};

typedef struct {



struct nodoQueue * front, * rear;

} queue;
Nell’implementazione in C della Coda con puntatori, si farà uso di una costante per rappresentare la condizione di coda vuota. Tale condizione si verifica quando il puntatore al primo elemento della coda è NULL. Verrà, dunque, definita una costante, di nome CODAVUOTA, che può essere rappresentata da:


#define CODAVUOTA NULL

Rappresentazione delle Operazioni Primitive


Le seguenti procedure e funzioni realizzano le operazioni di base della Coda.
void MakeNullQueue(queue *q)

{

q->front=q->rear=CODAVUOTA;



}
boolean EmptyQueue(queue q)

{

return(q.front==CODAVUOTA);



}
boolean FullQueue(queue q)

{

return(0);



}

void EnQueue(queue *q, tipobaseQueue x)

{

struct nodoQueue * temp;


if (!FullQueue(*q)) {

temp=(struct nodoQueue *)malloc(sizeof(struct nodoQueue));

temp->info=x;

temp->next=CODAVUOTA;

if (EmptyQueue(*q)) q->front=q->rear=temp;

else {


q->rear->next=temp;

q->rear=temp;

}

}

}



void DeQueue(queue *q)

{

struct nodoQueue * temp;


if (!EmptyQueue(*q)) {

temp=q->front->next;

free (q->front);

q->front=temp;

if (q->front==CODAVUOTA) q->rear=CODAVUOTA;

}

}



tipobaseQueue Front(queue q)

{

if (!EmptyQueue(q))



return(q.front->info);

}

3.Un Esempio Applicativo della Coda


Il seguente programma si riferisce alla gestione di un ADT coda. Si suppone l’esistenza di un file di nome “Coda.h” contenente l’implementazione della coda (sequenziale con vettore o collegata con puntatore, come spiegato in precedenza) e la definizione del tipobaseQueue.

Come si vede il programma utilizza delle funzioni per leggere ciascun elemento dell’ADT Coda dalla tastiera (LeggiElemento) e visualizzare ciascun elemento dell’ADT Coda sul video (VisualizzaElemento). Queste funzioni sono strettamente legate alla definizione del tipobaseQueue, visto che le funzioni di input/output del linguaggio C dipendono dai tipi delle variabili da leggere/scrivere. Tali funzioni sono dunque definite nel file Coda.h, in dipendenza della codifica del tipobaseQueue.


#include
void flush(void);
#include "Coda.h"
queue c; /*Variabile Coda*/
main()

{

short s;



tipobaseQueue elem;

MakeNullQueue(&c);


do {

printf ("\nMenu di Operazioni \n");

printf ("\n1-Inserimento");

printf ("\n2-Cancellazione ");

printf ("\n3-Svuota Coda ");

printf ("\n4-Ispeziona Elemento in Testa ");

printf ("\n5-Fine ");

printf ("\nInserisci la scelta ");

scanf ("%d", &s);

flush();
switch(s){


case 1 : if (!FullQueue(c)) {

LeggiElemento(&elem);

EnQueue(&c,elem);

} else printf ("\nCoda Piena \n");

break;
case 2 : if (EmptyQueue(c)) printf ( "\nCoda Vuota\n");

else {


DeQueue(&c);

printf ( "\nPrimo Elemento Estratto\n");

}

break;



case 3 : while (!EmptyQueue(c)) DeQueue(&c);

break;


case 4 : if (EmptyQueue(c)) printf ( "\nCoda Vuota\n");

else {


elem=Front(c);

VisualizzaElemento(elem);

}

break;


}

} while (s<5);

}
void flush(void){

while(getchar()!='\n');

}


3.1. Implementazione Sequenziale con Vettore


Nel caso di Rappresentazione Sequenziale, supponendo che il tipobaseQueue sia un float, il file Coda.h è:
#define CODAVUOTA -1

#define N 10


typedef float tipobaseQueue;
typedef short boolean;
typedef struct {

tipobaseQueue info[N];

int front,rear;

} queue;
void LeggiElemento(tipobaseQueue * x){

printf("\nInserisci l'Elemento ");

scanf("%f",x);

flush();

}
void VisualizzaElemento(tipobaseQueue x){

printf("\n\nElemento = %f \n\n", x);

}
void MakeNullQueue(queue *q)

{

q->front=q->rear=CODAVUOTA;



}
boolean EmptyQueue(queue q)

{

return(q.front==CODAVUOTA);



}
boolean FullQueue(queue q)

{

return(q.front==((q.rear+1)%N));



}
void EnQueue(queue *q, tipobaseQueue x)

{

if (!FullQueue(*q)) {



q->rear=(q->rear+1)%N;

q->info[q->rear]=x;

if (q->front==CODAVUOTA) q->front=q->rear;

}

}


void DeQueue(queue *q)

{

if (!EmptyQueue(*q)) {



if (q->front==q->rear) MakeNullQueue(q);

else q->front=(q->front+1)%N;

}

}

tipobaseQueue Front(queue q)



{

if (!EmptyQueue(q))

return(q.info[q.front]);

}


3.2. Implementazione Collegata con Puntatori


Nel caso di rappresentazione collegata, supponendo che il tipobaseQueue sia uno struct contenente i campi: cognome, nome ed età, il file Coda.h è:
#include
#define CODAVUOTA NULL
#define S 15

typedef struct {

char cognome[S], nome[S];

unsigned short eta;

}tipobaseQueue;
typedef short boolean;
struct nodoQueue {

tipobaseQueue info;

struct nodoQueue *next;

};

typedef struct {



struct nodoQueue * front, * rear;

} queue;
void LeggiStringa(char s[],unsigned short dim){

unsigned short i;

for (i=0; (s[i]=getchar())!='\n' && i

s[i]='\0';

}
void LeggiElemento(tipobaseQueue * x){

printf("\nInserisci l'Elemento ");

printf("\nInserisci il Cognome ");

LeggiStringa(x->cognome, S);

printf("\nInserisci il Nome ");

LeggiStringa(x->nome, S);

printf("\nInserisci l'eta' ");

scanf("%d",&x->eta);

flush();


}
void VisualizzaElemento(tipobaseQueue x){

printf("\n\nElemento ");

printf("\nCognome = %s ", x.cognome);

printf("\nNome = %s ", x.nome);

printf("\nEta' = %d \n\n",x.eta);

}
void MakeNullQueue(queue *q) {

q->front=q->rear=CODAVUOTA;

}
boolean EmptyQueue(queue q) {

return(q.front==CODAVUOTA);

}
boolean FullQueue(queue q) {

return(0);

}
void EnQueue(queue *q, tipobaseQueue x) {

struct nodoQueue * temp;
if (!FullQueue(*q)) {

temp=(struct nodoQueue *)malloc(sizeof(struct nodoQueue));

temp->info=x;

temp->next=CODAVUOTA;

if (EmptyQueue(*q)) q->front=q->rear=temp;

else {


q->rear->next=temp;

q->rear=temp;

}

}

}



void DeQueue(queue *q){

struct nodoQueue * temp;


if (!EmptyQueue(*q)) {

temp=q->front->next;

free (q->front);

q->front=temp;

if (q->front==CODAVUOTA) q->rear=CODAVUOTA;

}

}



tipobaseQueue Front(queue q)

{

if (!EmptyQueue(q))



return(q.front->info);

}






: users -> scava -> dispense -> FdINO
FdINO -> 1. Definizione di Albero
users -> La montagna incantata, IL Purgatorio di Dante e IL pellegrino–viator alla rovescia, cioè lo statico residente Hans Castorp
users -> La geografia (giochi di tragitti, di percorsi, di territori e confini, cacce al tesoro, idee di distanze, di lunghezze) La psicomotricità
users -> Una possibile sequenza di attività (anche di tipo ludico) su questo tema può essere la seguente, sperimentata in una classe 5
users -> Le indagini più recenti del Ministero dell’Istruzione sui dati della dispersione scolastica arrivano a concludere che la dispe
users -> Lezione 2 L'italiano d'oggi: le varietà funzionali, situazionali e strutturali
users -> Distinguiamo tra dimostrazione ed argomentazione; la prima ha carattere di certezza e di incontrovertibilità è usata nella ri
FdINO -> La Struttura Dati Astratta (adt) Lista
FdINO -> Abstract Data Type (adt) pila
dispense -> Università degli studi di catania facoltà di Ingegneria




©astratto.info 2017
invia messaggio

    Pagina principale