Algoritmi E Strutture Dati Liste

PROGETTO DI ALGORITMI E STRUTTURE DATI

LISTE

IGNAZIO ALTOMARE

FABIO GADALETA

SERGIO CENTRONE

Altomare Ignazio, Centrone Sergio, Gadaleta Fabio Pag.1 di 12

ANALISI

Liste:

• Confronto sovrapposizione(Lista<Tipoelem> I1, Lista<Tipoelem> I2), dove class

Confronto {private: Lista<Tipoelem> C; int lunghezzaC; Lista<Tipoelem>R1; int

lunghezzaR1; Lista<Tipoelem>R2; int lunghezzaR2}: C contiene gli elementi iniziali in

comune fra I1 e I2, R1 contiene il resto degli elementi di I1 ed R2 contiene il resto degli

elementi di I2.

• <Tipoelem> intersezione(Lista<Tipoelem> I1, Lista<Tipoelem> I2), che restituisce

l'ultimo elemento in comune fra I1 e I2.

Esempio:

sovrapposizione((a b c d e f g), (a b c e l)) = {C: (a b c); lunghezzaC: 3; R1: (d e f g); lunghezzaR1:

4; R2: (e); lunghezzaR2: 2}

intersezione((a b c d e f g), (a b c e l)) = e

Dall'analisi della traccia emerge che si devono realizzare due funzioni che operino su due liste

distinte.

La prima effettuerà un'operazione di sovrapposizione sulle due liste che saranno fornite.

Lo scopo di questa sovrapposizione sarà quello di ottenere tre liste differenti nelle quali saranno

presenti :

LISTA C : conterrà gli elementi iniziali in comune tra le 2 liste che verranno date in input

alla funzione sovrapposizione

LISTA R1 : conterrà gli elementi non inseriti nella lista C facenti parte della prima lista

fornita in input alla funzione

LISTA R2 : conterrà gli elementi non inseriti nella lista C facenti parte della seconda lista


fornita in input alla funzione

Viene in oltre richiesto il calcolo della lunghezza di ciascuna delle liste definite in precedenza.

La seconda funzione avrà il compito di computare l'intersezione delle due liste date in input alla

funzione.

La funzione restituirà l'ultimo elemento computato.

Dall'analisi della traccia non risultano riferimenti relativi ai seguenti problemi:

1. Dimensioni massime delle liste date come input alle funzioni.

2. Tipo di elemento che sarà contenuto nelle liste.

3. Non è definito se le liste inserite saranno ordinate oppure no.

4. Non vi è accenno alla possibilità che una delle liste, o entrambe, possano essere vuote.

5. Comportamento della funzione in caso di mancanza di elementi di intersezione tra le due liste date

in input.

6. Comportamento della funzione in caso di presenza degli ultimi elementi di intersezione nelle stesse

posizioni all'interno delle due liste.

7. Non viene definito se all� interno delle liste possano essere presenti elementi duplicati.

8. Non viene definito se le due liste debbano essere di stessa dimensione oppure di dimensione

distinta.

Ai problemi risultati sono state prese le seguenti decisioni:

1. La dimensione massima delle liste verrà chiesta all� utente al momento della creazione delle stesse.

2. Visto che le funzioni implementate sono eseguibili su vari tipi di dati, le funzioni saranno

implementate in maniera generica.

3. Viene considerato che le liste non siano ordinate.

4. Quando viene chiesta la dimensione massima della lista vi sarà un opportuno controllo affinché

entrambe le liste contengano almeno un elemento.


5. La funzione di intersezione può essere applicata solo nel caso in cui tra le due liste sono presenti

degli elementi di intersezione.

6. Prendiamo l� elemento ultimo assoluto di entrambe le liste.

7. Nel caso in cui vi siano duplicati saranno considerati come normali elementi della lista.

8. Le due liste potranno avere sia una dimensione identica oppure dimensione diversa.


DEFINIZIONE DEI DATI

La struttura dati utilizzata per la risoluzione del problema è la seguente:

LISTA

Specifica sintattica:

TIPI:

Lista

Posizione

Boolean

Tipoelem

OPERATORI:

CREALISTA : ( ) Lista

LISTAVUOTA: ( Lista) Boolean

LEGGILISTA : (Posizione, Lista) Tipoelem

SCRIVILISTA : (Tipoelem, Posizione ,Lista) Lista

PRIMOLISTA : (Lista) Posizione

FINELISTA : (Posizione, Lista) Boolean

SUCCLISTA : (Posizione, Lista) Posizione

PREDLISTA : (Posizione, Lista) Posizione

INSLISTA : (Tipoelem, Posizione, Lista) Lista

CANCLISTA : (Posizione, Lista) Lista


Specifica semantica:

TIPI:

Lista: insieme delle sequenze L = < a1, a2, & , an >, n ≥ 0, di elementi di tipo Tipoelem, dove

l'elemento i-esimo ha valore ai e posizione pos(i)

Boolean: insieme dei valori di verità

OPERATORI:

CREALISTA = L'

POST: L' = L, L = < > (sequenza vuota)

LISTAVUOTA(L) = b

POST: b = true se L= < >, b = false altrimenti

LEGGILISTA(p,L) = a

PRE: L = < a1, a2, & , an >, p = pos(i), 1 ≤ i ≤ n

POST: a = ai

SCRIVILISTA(a,p,L) = L'


POST: L' = < a1, a2, & , ai-1, a, ai+1, & , an >

PRIMOLISTA(L) = p

POST: p = pos(1)

FINELISTA(p,L) = b

PRE: L = < a1, a2, & , an >, p = pos(i), 1 ≤ i ≤ n + 1

POST: b = true se p = pos(n+1), b= false altrimenti

SUCCLISTA(p,L) = q


POST: q = pos(i+1)

PREDLISTA(p,L) = q



POST: q = pos(i-1)

INSLISTA(a,p,L) = L'

PRE: L = < a1, a2, & , an >, p = pos(i), 1 ≤ i ≤ n + 1

POST: L' = < a1, a2, & , ai-1, a, ai, ai+1, & , an >, se 1 ≤ i ≤ n

L' = < a1, a2, & , an, a > , se i = n+1 (e quindi L' = < a > se i = 1 e L = < >)

CANCLISTA(p,L) = L'


POST: L' = < a1, a2, & , ai-1, ai+1, & , an >

Realizziamo, oltre alla specifica sintattica e semantica della lista, anche quella delle funzione che

andranno realizzate:

CONFRONTO

Specifica sintattica:

TIPI:

ListaC

ListaR1

ListaR2

Boolean

Tipoelem

Intero

LunghezzaC

LunghezzaR1

LunghezzaR2


OPERATORI:

incC : (Confronto) (confronto)

incR1 : (Confronto) (confronto)

incR2: (Confronto) (confronto)

prendiC(Confronto) (Lista);

prendiR1(Confronto) (Lista);

prendiR2(Confronto) (Lista);

lunghC(Confronto) (Intero)

lunghR1(Confronto) (Intero);

lunghR2(Confronto) (Intero);

Specifiche semantiche:

TIPI:

Lista C: Lista i cui elementi sono di tipoelem che conterrà gli elementi presenti in entrambe

le liste fornite alla funzione.

Lista R1: Lista i cui elementi sono di tipoelem che conterrà gli elementi non presenti il C e

facenti parte della prima lista data alla funzione.

Lista R2: Lista i cui elementi sono di tipoelem che conterrà gli elementi non presenti il C e

facenti parte della seconda lista data alla funzione.

LunghezzaC: intero che rappresenta la dimensione della lista C

LunghezzaR1: intero che rappresenta la dimensione della lista R1

LunghezzaR2: intero che rappresenta la dimensione della lista R2

OPERATORI

inc C (temp) temp' : denota dinamicamente la dimensione della lista C

inc R1 (temp) temp' : denota dinamicamente la dimensione della lista R1

inc R2 (temp) temp' : denota dinamicamente la dimensione della lista R2


prendiC(temp) L : rende possibile eseguire sulla lista C tutte le operazioni eseguibili su

una lista

prendiR1(temp) L : rende possibile eseguire sulla lista R1 tutte le operazioni eseguibili su

una lista

prendiR2(temp) L : rende possibile eseguire sulla lista R2 tutte le operazioni eseguibili su

una lista

lunghC(temp) Int : indica la lunghezza della lista C

lunghR1(temp) Int : indica la lunghezza della lista R1

lunghR2(temp) Int : indica la lunghezza della lista R2

ALGORITMO RISOLUTIVO DELLA

SOVRAPPOSIZIONE

confronto sovrapposizione (lista lista1, lista lista2)

confronto temp;

indice1 lista1.primolista();

indice2 lista2.primalista();

indiceC temp.prendiC().primolista();

indiceR1 temp.prendiR1().primolista();

indiceR2 temp.prendiR2().primolista();

Fintanto che (not lista1.finelista(indice1) AND not lista2.finelista(indice2) AND

(lista1.leggiLista(indice1) == (lista2.leggiLista(indice2))

temp.prendiC().insLista(lista1.leggiLista(indice1),indiceC);

indice1 lista1.succLista(indice1);


indiceC temp.prendiC().succLista(indiceC);


Fintanto che (not lista1.finelista(indice1))

temp.prendiR1().insLista(lista1.leggiLista(indice1),indiceR1);

indiceR1 temp.listaR1().succLista(indiceR1);


Fintanto che (not lista2.finelista(indice2))

temp.prendiR2().insLista(lista2.leggiLista(indice2),indiceR2);

indiceR2 temp.listaR2().succLista(indiceR2);


restituisci (temp);

ALGORITMO RISOLUTIVO PER IL CALCOLO

DELL� INTERSEZIONE

Tipoelem intersezione (Lista lista1, Lista lista2);


tipoelem temp1;

tipoelem temp2;

intero contatore 1;

intero numero1 0;

intero numero2 0;

Fintanto che (not lista1.fineLista(indice1))

posizione indice2 lista2.primoLista();

Fintanto che (not lista2.finelista(indice2)

Se (lista1.leggiLista(indice1) == (lista2.leggiLista(indice2)


temp1 lista1.leggiLista(indice1);

numero1 contatore;



contatore contatore+1;


contatore 1;

Fintanto che (not lista2.fineLista(indice2) AND (not numero1 == 0))

posizione indice1 lista1.primoLista();

Fintanto che (not lista1.finelista(indice1)

Se (lista1.leggiLista(indice1) == (lista2.leggiLista(indice2)

temp2 lista2.leggiLista(indice2);

numero2 contatore;



contatore contatore+1;

Se(numero1 == 0)

avvisa l' utente che non c� è intersezione tra le due liste;

altrimenti

Se (numero1 >= numero2)

restituisci(temp1);

altrimenti

restituisci(temp2);


REALIZZAZIONE

Le realizzazioni effettuate per l� implementazione della funzione definita nella progettazione

saranno le seguenti:

• Realizzazioni con Vettore

• Realizzazione con Puntatori

Da notare che nella realizzazione con vettore la dimensione massima della lista consentita sarà di

1023 elementi.

TEST

Classi di equivalenza:

1. La dimensione di una delle due liste date in input, o di entrambe, è pari a 0.

2. Le due liste sono composte da elementi non omogenei.

3. Le due liste non sono della stessa dimensione.

4. Le due liste sono della stessa dimensione.

5. L� intersezione delle due liste produce un valore.

6. La sovrapposizione delle due liste risulta nulla.

7. La sovrapposizione delle due liste produce risultati.

8. La sovrapposizione e l� intersezione non producono entrambi risultati.

9. La sovrapposizione e l� intersezione producono entrambi risultati.


Algoritmi E Strutture Dati Liste

Documents

Transcript of Algoritmi E Strutture Dati Liste