Fondamenti di Informatica 2 Ingegneria Informatica Docente: Giovanni Macchia a.a. 2002-2003.

transcript

Fondamenti di Informatica 2Ingegneria Informatica

Docente: Giovanni Macchiaa.a. 2002-2003

Strutture DatiStrutture Dati

Una struttura dati già studiata è l’array.L’array ha comunque delle grosse limitazioni:• l’ampiezza dell’array deve essere conosciuto durante la compilazione• i dati dell’array sono separati dalla stessa distanza nella memoria del computer : l’inserimento di un elemento all’interno dell’array richiede lo spostamento di altri dati

Per ovviare a queste limitazioni, si ricorre alle strutture dati dinamiche, ovvero a strutture le cui dimensioni possono modificarsi durante l’esecuzione del programma.

Strutture Dati: Linked ListStrutture Dati: Linked List

Una lista concatenata (linked list) è una sequenza lineare di oggetti detti nodi contenenti dati e puntatori ad oggetti della stessa classe dei nodi.L’accesso ad una linked list avviene tramite il puntatore al suo primo nodo. L’accesso agli altri nodi della lista avviene tramite il link al nodo successivo. Il puntatore al nodo successivo dell’ultimo elemento della lista viene posto uguale a NULL per convenzione.

Es:class IntNode {public:IntNode ( );IntNode(int i, IntNode * in = NULL) {.. } ;int info;IntNode *next;};IntNode *p = new IntNode(10);p->next = new IntNode(8);p->next->next = new IntNode(6);

a) IntNode *p = new IntNode(10);b) p->next = new IntNode(8);c) p->next->next = new IntNode(6);

10a)NULL

10b) 8

10c) 8 6

Una gestione molto elegante delle liste concatenate si ottiene con una implementazione ad oggetti. Si considerano due classi: una classe Nodo e una classe Lista. Gli attributi della classe Nodo sono :• i dati del nodo• il puntatore al nodo successivo Il metodo della classe Nodo è il costruttore. Quando un oggetto di classe Nodo viene creato, vengono inizializzati gli attributi del nodo.

Gli attributi della classe Lista sono due:• il puntatore al primo elemento della lista• il puntatore all’ultimo elemento della lista Quando un oggetto di classe Lista viene creato, i puntatori al primo e all’ultimo elemento vengono inizializzati a NULL.

Strutture Dati: Linked ListStrutture Dati: Linked ListI metodi della classe Lista coincidono con le operazioni che possono essere eseguite sulla lista.Le operazioni su una lista concatenata sono le seguenti:• addtofirst : aggiungi un nodo in cima alla lista• addtolast : aggiungi un nodo alla fine della

lista• deletefirst : rimuovi il primo nodo della lista• deletelast : rimuovi l’ultimo nodo della lista• isEmpty : verifica se la lista è vuota• deleteNode(el) : rimuove un nodo con elemento

el dalla listaI metodi della classe Lista usano i metodi della classe Nodo.

Strutture Dati: Linked ListStrutture Dati: Linked ListEs:class IntNode {public:IntNode *next;IntNode(int i, IntNode *ptr = NULL) {info =i; next =ptr; } ;int info;};class IntList {public:IntList( ) {first = last = NULL};~IntList( );bool isEmpty( ) {return (first == NULL) };void addtofirst (int );void addtolast (int );bool deletefirst( int &);bool deletelast( int &);void deleteNode(int &);private:IntNode *first, *last;};

L’algoritmo per aggiungere un elemento el in cima alla lista (addtofirst)è il seguente:CREA un nuovo nodo N (contente el ) con il primo nodo della lista come nodo successivo ad N;PONI N come primo elemento della lista ;SE l’ultimo elemento della lista non esiste ALLORA

PONI il primo elemento della lista come ultimo elemento della lista;

L’algoritmo per aggiungere un elemento el alla fine della lista (addtolast)è il seguente:SE la lista non è vuotaALLORA

CREA un nuovo nodo N (contente el ) con l’ultimo nodo della lista come nodo predecessore di N;PONI N come ultimo nodo della lista;

ALTRIMENTICREA un nuovo nodo N (contente el ) che non ha nodi successivi;PONI N come primo ed ultimo nodo della lista;

Strutture Dati: Linked ListStrutture Dati: Linked Listvoid addtofirst (int el){ first = new IntNode (el, first); if (last == NULL) last = first; }

void addtolast (int el){ if (last != NULL) // se la lista non è vuota { last->next = new IntNode (el); last = last->next; } else first = last = new IntNode(el); }

L’algoritmo per rimuovere il primo elemento della lista (deletefirst) è il seguente:SE la lista non è vuotaALLORA

SE la lista ha un solo nodo ALLORA

ELIMINA il nodo;ALTRIMENTI

PONI il nodo successivo al primo come primo nodo della lista;

Strutture Dati: Linked ListStrutture Dati: Linked Listbool deletefirst (int &el){ if (isEmpty()) return false; else { IntNode *tmp = first; if (first == last) { delete first; first = last = NULL; } else first = first->next; el = tmp->info; delete tmp; return true; }}

L’algoritmo per rimuovere l’ultimo nodo della lista (deletelast) è il seguente:SE la lista non è vuotaALLORA

SE la lista ha un solo nodoALLORA

ELIMINA il nodo;ALTRIMENTI

TROVA il nodo N immediatamente precedente all’ultimo nodo della lista;PONI N come ultimo nodo della lista;

Strutture Dati: Linked ListStrutture Dati: Linked Listbool deletelast (int &el){ if (isEmpty()) return false; else { IntNode *tmp = last; if (first == last) { delete first; first = last = NULL; } else { IntNode *curr =first; while (curr->next != last) curr = curr->next; last = curr; curr->next = NULL; }; el = tmp->info; delete tmp; return true; } }

Strutture Dati: Linked ListStrutture Dati: Linked ListL’algoritmo per rimuovere un elemento el della lista (deleteNode) è il seguente:SE la lista non è vuotaALLORA

SE ( la lista ha un solo nodo E l’elemento del nodo è uguale a el) ALLORA ELIMINA il nodoALTRIMENTI

SE il primo nodo N1 ha elemento uguale a elALLORA

PONI il secondo nodo come primo nodo della lista;ELIMINA N1;

ALTRIMENTICERCA il predecessore P e il successore S del nodo N con elemento el;SE P ed S esistono ALLORA

PONI S come successore di P;ELIMINA il nodo N;

Strutture Dati: Linked ListStrutture Dati: Linked Listvoid deleteNode (int &el){ if (!isEmpty()) { if (first ==last && el == first->info) { delete first; first = last = NULL; } else if (el == first->info) { IntNode *tmp =first;

first = first->next; delete tmp; }

else {IntNode *pred, *succ; for(pred=first,succ=first->next; succ !=NULL && !(succ->info =el); pred =pred->next,succ=succ->next);

if (succ != NULL) { pred->next=succ->next; if (succ == last) last = pred; delete succ;} } } }

E’ possibile generalizzare le liste concatenate tramite i template. In questo caso, il template della classe Node è:

template <class TIPONODO> class Node {public:Node<TIPONODO> *next;Node (TIPONODO, Node<TIPONODO> *) ;TIPONODO info;};

template <class TIPONODO>Node<TIPONODO>::Node(TIPONODO i, Node<TIPONODO> *ptr = NULL):info(i) {next = ptr; }

Strutture Dati: Linked ListStrutture Dati: Linked ListIl template della classe List è:template <class TIPONODO>class List {public:List( );~List( );bool isEmpty( );void addtofirst (TIPONODO );void addtolast (TIPONODO );bool deletefirst( TIPONODO &);bool deletelast( TIPONODO &);void deleteNode(TIPONODO &);private:Node<TIPONODO> *first, *last;};

Strutture Dati: Linked ListStrutture Dati: Linked ListAnche i metodi della classe vengono ridefiniti per renderli dei template:template <class TIPONODO>void List<TIPONODO>:: addtofirst (TIPONODO el){ first = new Node<TIPONODO> (el, first); if (last == NULL) last = first; }

template <class TIPONODO>void List<TIPONODO>:: addtolast (TIPONODO el){ if (last != NULL) // se la lista non è vuota { last->next = new Node<TIPONODO>(el); last = last->next; } else first = last = new Node<TIPONODO>(el); }

template <class TIPONODO>bool List<TIPONODO>:: deletefirst (TIPONODO &el){ if (isEmpty()) return false; else { Node<TIPONODO> *tmp = first; if (first == last) { delete first; first = last = NULL; } else first = first->next; el = tmp->info; delete tmp; return true; }}

Strutture Dati: Linked ListStrutture Dati: Linked Listtemplate <class TIPONODO>bool List<TIPONODO>::deletelast (TIPONODO &el){ if (isEmpty()) return false; else { Node<TIPONODO> *tmp = last; if (first == last) { delete first; first = last = NULL; } else { Node<TIPONODO> *curr =first; while (curr->next != last) curr = curr->next; last = curr; curr->next = NULL; }; el = tmp->info; delete tmp; return true; } }

1addtofirst(1)

1addtofirst(5) 5

addtolast(4) 1

deletefirst1

addtofirst(8)1

1deletelast

addtofirst(6)

Strutture Dati: StackStrutture Dati: Stack

Una pila (stack) è una struttura lineare di oggetti che possono essere aggiunti o rimossi soltanto dalla sua cima (top). Pertanto, l’ultimo oggetto posto sulla cima dello stack è il primo ad essere rimosso. Per questa ragione, uno stack è chiamato una struttura LIFO (last-in/first-out).Le operazioni che possono essere eseguite su uno stack sono:• push(el) : mette el sulla cima della pila• pop( ) : prende l’elemento dalla cima della pila•clear( ) : azzera lo stack•isEmpty( ) : verifica se lo stack è vuoto

STACKpush( )pop( )

Strutture Dati: StackStrutture Dati: StackUno Stack si ottiene considerando una classe Nodo, Lista e Stack che usa i metodi forniti dalla classe Lista. Es:#include “IntList.h”class IntStack {public:IntStack( ) ;~IntStack( );bool isEmpty( );void push ( int &el) { IntList. addtofirst (int el);};bool pop (int &el) {return IntList. deletefirst (int el); };void clear();};

Così come per le liste concatenate, è possibile generalizzare lo stack tramite i template. In questo caso, il template della classe Stack è:

template <class TIPONODO>class Stack {public:Stack( );~Stack( );bool isEmpty( );void push (TIPONODO & );bool pop (TIPONODO &);void clear();};

template <class TIPONODO>void Stack<TIPONODO>::push(TIPONODO &el) {List<TIPONODO>.addfirst(TIPONODO el); };

template <class TIPONODO>bool Stack<TIPONODO>::pop(TIPONODO &el) {List<TIPONODO>.deletefirst(TIPONODO el); };

L’implementazione dello stack in maniera tradizionale si ottiene tramite delle operazioni su puntatori. Per esempio, la funzione push per inserire un elemento nello stack dove il top della pila è riferito al puntatore lis:

tmpp ->next = lis; lis = tmpp;

tmpp ->next = lis

lis = tmpp

Strutture Dati: QueueStrutture Dati: Queue

Una coda (queue) è una struttura lineare di oggetti in cui si può inserire un oggetto solo alla fine della coda ed eliminare un oggetto solo dalla cima della coda. Per questa ragione, una coda è chiamata una struttura FIFO (first-in/first-out).Le operazioni che possono essere eseguite su una coda sono:• enqueue(el) : mette el sul fondo della coda• dequeue( ) : prende il primo elemento dalla coda•clear( ) : azzera la coda•isEmpty( ) : verifica se la coda è vuota

dequeue( )

enqueue( )

Una Queue si ottiene considerando una classe Nodo, Lista e Queue che usa i metodi forniti dalla classe Lista. Es:#include “IntList.h”class IntQueue {public:IntQueue( ) ;~IntQueue( );bool isEmpty( );void enqueue ( int &el) { IntList. addtolast (int el);};bool dequeue (int &el) {return IntList. deletefirst (int el); };void clear();};

Strutture Dati: TreeStrutture Dati: Tree

Un albero (tree) è una struttura non lineare di archi e nodi. Questi ultimi contengono due o più membri di link ad altri nodi. Un albero con esattamente due link si chiama albero binario.Il primo nodo della struttura ad albero si chiama radice (root) ed ha la proprietà di non discendere da altri nodi. Un nodo dal quale discendono altri nodi si chiama nodo padre. I nodi che discendono dal nodo padre si chiamano nodi figlio.Un nodo senza figli è chiamato nodo foglia (leaf) Un nodo di un albero binario può avere da 0 a 2 figliUn nodo di un albero n-ario può avere da 0 a n figli.

Un albero è definito in maniera ricorsiva in base alle seguenti regole:

1. un insieme vuoto di nodi è un albero vuoto

2. se t1, t2,…,tk sono alberi disgiunti, allora la struttura la cui radice ha come figli le radici di t1,t2, …, tk è anche un albero

3. Solo strutture generate dalle regole 1 e 2 sono alberi

Ogni nodo è raggiungibile dalla radice attraverso una sequenza unica di archi, chiamata path.

Il numero di archi in un path è chiamata lunghezza del path.

Si definisce livello di un nodo la lunghezza del path dalla radice al nodo stesso aumentata di uno.

La altezza di un albero è la lunghezza massima di un nodo nell’albero.

...........................................................

LI VELLO 1

LI VELLO 2

LI VELLO 3

LI VELLO n

La figura rappresenta la struttura di un albero binario dove ogni nodo ha 2 figli.

Nella implementazione, faremo riferimento ad un particolare albero binario, detto albero binario di ricerca (search binary tree). Un albero binario di ricerca ha la proprietà che il valore di ogni nodo è:• maggiore del valore dei nodi del suo sottoalbero sinistro• minore del valore dei nodi del suo sottoalbero destro 40

18 34 50 77

In un albero binario di ricerca dove ogni nodo ha 2 figli, il numero di nodi presenti al livello k-mo è pari a 2k-1. Il numero di nodi totali presenti in un albero di ricerca ben bilanciato è pertanto pari a n = 20 + 21 + 22 + ... 2k-1= 2k - 1 Il numero di livelli di un albero ben bilanciato contenente n nodi è pertanto k=log2(n+1) .Per effettuare una ricerca su 1024 elementi occorrono pertanto 10 confronti, mentre per effettuare una ricerca su 1048576 elementi (220) occorrono 20 confronti

I metodi che devono essere implementati come pubblici sono relativi all’inserimento di un nodo e all’estrazione di un nodo.Per estrarre un nodo da un albero, si usano le operazioni di visita (tree traversal) ovvero si procede in un certo ordine per l’estrazione di un elemento. I più comuni tipi di visita sono:visita in preordine (preorder tree traversal)visita in postordine (postorder tree traversal)visita in ordine simmetrico (inorder tree traversal)

Strutture Dati: TreeStrutture Dati: Treeclass IntTreeNode {friend class IntTree; public:IntTreeNode(const int &el ): leftPtr(NULL), data (el), rightPtr(NULL) { } ;int getData ( ) const { return data; } ;private:IntTreeNode *leftPtr;IntTreeNode *rightPtr;int data;};

Strutture Dati: TreeStrutture Dati: Treeclass IntTree {public:IntTree( ) { rootPtr = NULL;};~IntTree( );void insertNode ( const int &); //inserimento di un nodovoid preordertraversal( ) const; // visita in preordinevoid inordertraversal( ) const; // visita in ordine simmetricovoid postordertraversal( ) const; //visita in postordineprivate:IntTreeNode *rootPtr;void insertNodeHelper (IntTreeNode **, const int &);void preorderHelper (IntTreeNode * ) const;void inorderHelper (IntTreeNode * ) const;void postorderHelper (IntTreeNode * ) const;void visit (IntTreeNode * ) const;};

L’inserimento di un nodo avviene con il seguente algoritmo: void IntTree::insertNode (const int &el ) {insertNodeHelper(&rootPtr,el); };

void IntTree::insertNodeHelper (IntTreeNode **p, const int &el ) { if (*p == NULL) { *p = new IntTreeNode(el); } else if (el < (*p)->data ) insertNodeHelper (&((*p)->leftPtr), el); else if (el > (*p)->data ) insertNodeHelper (&((*p)->rightPtr), el); };

Se l’albero è vuoto creo la radice

La visita in preordine avviene con il seguente algoritmo: se l’albero non è vuoto, visita in preordine il sottoalbero sinistro e poi visita in preordine il sottoalbero destro. void IntTree::preordertraversal ( ) const {preorderHelper(rootPtr); }; void IntTree::preorderHelper (IntTreeNode *p) const { if (p != NULL) { visit(p); preorderHelper (p->leftPtr); preorderHelper (p->rightPtr); }; };

10 1422 27

Visita in preordine

1o sottoalberoad essere visitato

I nodi sono visitati nel seguente ordine:18

13 10 1425 22 27

La visita in postordine avviene con il seguente algoritmo: se l’albero non è vuoto, visita in postordine il sottoalbero sinistro e poi visita in postordine il sottoalbero destro. void IntTree::postordertraversal ( ) const {postorderHelper(rootPtr); }; void IntTree::postorderHelper (IntTreeNode *p) const { if (p != NULL) { postorderHelper (p->leftPtr); postorderHelper (p->rightPtr); visit(p); }; };

10 1422 27

Visita in postordine

I nodi sono visitati nel seguente ordine:10 14 1322 27 25

La visita in ordine simmetrico avviene con il seguente algoritmo: se l’albero non è vuoto, visita in ordine simmetrico il sottoalbero sinistro e poi visita in ordine simmetrico il sottoalbero destro. void IntTree::inordertraversal ( ) const {inorderHelper(rootPtr); }; void IntTree::inorderHelper (IntTreeNode *p) const { if (p != NULL) { inorderHelper (p->leftPtr); visit(p); inorderHelper (p->rightPtr); }; };

10 1422 27

Visita in ordine simmetrico

I nodi sono visitati nel seguente ordine:10 13 14

18 22 25 27

Fondamenti di Informatica 2 Ingegneria Informatica Docente: Giovanni Macchia a.a. 2002-2003.

Documents