1

FONDAMENTI DI INFORMATICA IIIngegneria Gestionale

a.a. 2001-2002 - 4° Ciclo

Strutture Dati

2

Strutture Dati

Le strutture Dati

Per strutture dati s’intendono generalmente insiemi di dati caratterizzati dalla modalità d’accesso e dalla dimensione.

Strutture Dati Statiche

Sono caratterizzate dalla dimensione fissa. Tipici esempi sono gli array e i record implementati attraverso le struct.

Strutture Dati Dinamiche

Sono quelle la cui dimensione può crescere o decrescere durante l’esecuzione del programma. Esempi di strutture dati dinamiche sono le liste concatenate in cui i dati sono suddivisi in sottoinsiemi (nodi) ciascuno dei quali è collegato ad uno o più altri sottoinsiemi per mezzo di puntatori. Una lista concatenata può crescere o decrescere aggiungendo o togliendo nodi.

3

Strutture Dati

Classi ricorsive

Una classe ricorsiva contiene un membro di tipo puntatore che punta ad una struttura dello stesso tipo di quella in cui è contenuto. In sostanza ricorre una situazione del tipo sotto indicato:

class Nome_Classe { …………..

…………………………………..

Nome_Classe *Nome_Puntatore;

…………………………………};

Gli oggetti istanziati da una classe ricorsiva costituiscono perciò la naturale implementazione dei nodi di una lista concatenata.

4

Strutture Dati

Esempio di classe ricorsiva.

Class Node {

public:

Node (int);

void setData (int);

int getData ( ) const;

void setNextPtr (const Node *);

const Node *getNextPtr ( ) const;

private:

int data;

Node *nextptr; // Puntatore di tipo Node

};

5

Strutture Dati

Liste concatenate

Una lista concatenata può quindi definirsi come una sequenza di oggetti di una classe ricorsiva, chiamati nodi, connessi attraverso i puntatori della classe. Se la sequenza è unica, ossia se ogni oggetto può puntare solo all’oggetto che lo precede e/o lo segue in sequenza, la lista viene detta lineare.

Esempi di liste lineari, che differiscono tra loro solo per le modalità di accesso, sono le pile (stack) e le code. Esempi di liste non lineari, ossia con più di un puntatore per ogni nodo che puntano a nodi non strettamente sequenziali, sono gli alberi.

Nel caso di liste lineari il primo oggetto della sequenza, che viene detto testa della sequenza, è individuato da un puntatore. L’ultimo oggetto della sequenza, o coda, ha il suo puntatore convenzionalmente inizializzato a 0. Anche la coda può essere individuata da un puntatore.

6

Strutture Dati

Rappresentazione grafica

La rappresentazione grafica di una lista lineare può quindi essere fatta come segue:

Oggetto B

Puntatore

Puntatore di testa Oggetto A

Puntatore

Oggetto C

Puntatore

Oggetto x

0

Puntatore di coda

7

Strutture DatiAncora sulle liste concatenate lineari

Le liste concatenate lineari possono essere ulteriormente caratterizzate come segue:

Liste concatenate semplici

Ogni nodo contiene un puntatore al successivo nodo, formando una sequenza che termina con un nodo il cui puntatore è 0.

Liste concatenate semplici circolari

Come sopra, tranne che il puntatore dell’ultimo nodo punta al primo nodo.

Liste concatenate doppie

Ogni nodo ha un puntatore sia al nodo precedente che al successivo, tranne l’ultimo che ha il puntatore al successivo uguale a 0 e il primo che ha il puntatore al precedente uguale a 0.

Liste concatenate doppie circolari

Come sopra tranne che il puntatore al successivo dell’ultimo nodo punta al primo nodo, mentre il puntatore al precedente del primo nodo punta all’ultimo nodo.

8

Strutture Dati

Programma di manipolazione liste lineari semplici

Il programma che ora consideriamo è un template di classe (di nome List), che manipola quindi liste con valori di un tipo da specificare, per mezzo delle seguenti opzioni selezionabili:

1 - Inserire un valore ad inizio lista (funzione insertAtFront)

2 - Inserire un valore alla fine della lista (funzione insertAtBack)

3 - Eliminare un valore dall’inizio della lista (funzione removeFromFront)

4 - Eliminare un valore dalla fine della lista (funzione removeFromBack)

5 - Terminare l’elaborazione eliminando tutti i nodi residui (funzione Distruttore)

9

Strutture Dati - Esempio

// ListNode template definition#ifndef LISTND_H#define LISTND_H

template< class NODETYPE > class List; // forward declaration

template<class NODETYPE>class ListNode { friend class List< NODETYPE >; // make List a friendpublic: ListNode( const NODETYPE & ); // constructor NODETYPE getData() const; // return data in the nodeprivate: NODETYPE data; // data ListNode< NODETYPE > *nextPtr; // next node in the list};

10

Strutture Dati - Esempio

// Constructortemplate<class NODETYPE>ListNode< NODETYPE >::ListNode( const NODETYPE &info ) : data( info ), nextPtr( 0 ) { }

// Return a copy of the data in the nodetemplate< class NODETYPE >

NODETYPE ListNode< NODETYPE >::getData() const { return data; }

#endif

11

Strutture Dati - Esempio// Template List class definition#ifndef LIST_H#define LIST_H#include <iostream>#include <cassert>#include "listnd.h"using std::cout;

template< class NODETYPE >class List {public: List(); // constructor ~List(); // destructor void insertAtFront( const NODETYPE & ); void insertAtBack( const NODETYPE & ); bool removeFromFront( NODETYPE & ); bool removeFromBack( NODETYPE & ); bool isEmpty() const; void print() const;

12

Strutture Dati - Esempio

private: ListNode< NODETYPE > *firstPtr; // pointer to first node ListNode< NODETYPE > *lastPtr; // pointer to last node

// Utility function to allocate a new node ListNode< NODETYPE > *getNewNode( const NODETYPE & );};

// Default constructortemplate< class NODETYPE >List< NODETYPE >::List() : firstPtr( 0 ), lastPtr( 0 ) { }

13

Strutture Dati - Esempio

// Is the List empty?template< class NODETYPE > bool List< NODETYPE >::isEmpty() const { return firstPtr == 0; }

// Return a pointer to a newly allocated nodetemplate< class NODETYPE >ListNode< NODETYPE > *List< NODETYPE >::getNewNode

( const NODETYPE &value ){

ListNode< NODETYPE > *ptr = new ListNode< NODETYPE >( value );

assert( ptr != 0 ); return ptr;

}

14

Strutture Dati - Esempio

12

newPtr

7 11

firstPtrb)

12

newPtr

firstPtra)

7 11

15

Strutture Dati - Esempio

// Insert a node at the front of the listtemplate< class NODETYPE >void List< NODETYPE >::

insertAtFront( const NODETYPE &value){ ListNode< NODETYPE > *newPtr = getNewNode( value );

if ( isEmpty() ) // List is empty firstPtr = lastPtr = newPtr; else { // List is not empty newPtr->nextPtr = firstPtr; firstPtr = newPtr; }}

16

Strutture Dati - Esempio

5

a)

7 1112

newPtrlastPtrfirstPtr

lastPtrb)

7 1112

newPtrfirstPtr

5

17

Strutture Dati - Esempio

// Insert a node at the back of the listtemplate< class NODETYPE >void List< NODETYPE >::

insertAtBack( const NODETYPE &value ){ ListNode< NODETYPE > *newPtr = getNewNode( value );

if ( isEmpty() ) // List is empty firstPtr = lastPtr = newPtr; else { // List is not empty lastPtr->nextPtr = newPtr; lastPtr = newPtr; }}

18

Strutture Dati - Esempio

a)

7 1112

firstPtr lastPtr

5

b)

7 1112

firstPtr lastPtr

5

tempPtr

19

Strutture Dati - Esempio// Delete a node from the front of the list

template< class NODETYPE >bool List< NODETYPE >::removeFromFront( NODETYPE &value ){ if ( isEmpty() ) // List is empty return false; // delete unsuccessful else { ListNode< NODETYPE > *tempPtr = firstPtr;

if ( firstPtr == lastPtr ) firstPtr = lastPtr = 0; else firstPtr = firstPtr->nextPtr;

value = tempPtr->data; // data being removed delete tempPtr; return true; // delete successful }}

20

Strutture Dati - Esempio

a)

7 1112

firstPtr lastPtr

5

b)

7 1112

firstPtr lastPtr

5

currentPtr

tempPtr

21

Strutture Dati - Esempio// Delete a node from the back of the list

template< class NODETYPE >bool List< NODETYPE >::removeFromBack( NODETYPE &value ){if ( isEmpty() ) return false; // delete unsuccessful else { ListNode< NODETYPE > *tempPtr = lastPtr; if ( firstPtr == lastPtr ) firstPtr = lastPtr = 0; else {ListNode< NODETYPE > *currentPtr = firstPtr; while ( currentPtr->nextPtr != lastPtr ) currentPtr = currentPtr->nextPtr; lastPtr = currentPtr; currentPtr->nextPtr = 0;}

value = tempPtr->data; delete tempPtr; return true; // delete successful }}

22

Strutture Dati - Esempio// Destructor

template< class NODETYPE >List< NODETYPE >::~List(){ if ( !isEmpty() ) { // List is not empty cout << "Destroying nodes ...\n";

ListNode< NODETYPE > *currentPtr = firstPtr, *tempPtr;

while ( currentPtr != 0 ) { // delete remaining nodes tempPtr = currentPtr; cout << tempPtr->data << '\n'; currentPtr = currentPtr->nextPtr; delete tempPtr; } } cout << "All nodes destroyed\n\n";}

23

Strutture Dati - Esempio// Display the contents of the List

template< class NODETYPE >void List< NODETYPE >::print() const{ if ( isEmpty() ) { cout << "The list is empty\n\n"; return; } ListNode< NODETYPE > *currentPtr = firstPtr;

cout << "The list is: "; while ( currentPtr != 0 ) { cout << currentPtr->data << ' '; currentPtr = currentPtr->nextPtr; } cout << "\n\n";}#endif

24

Strutture Dati - Esempio// List class test

#include <iostream>#include "list.h"using std::cin;using std::endl;

// Function to test an integer Listtemplate< class T >void testList( List< T > &listObject, const char *type ){ cout << "Testing a List of " << type << " values\n";

instructions( ); int choice; T value;

25

Strutture Dati - Esempio

do { cout << "? "; cin >> choice; switch ( choice ) { case 1: cout << "Enter " << type << ": "; cin >> value; listObject.insertAtFront( value ); listObject.print(); break; case 2: cout << "Enter " << type << ": "; cin >> value; listObject.insertAtBack( value ); listObject.print(); break;

26

Strutture Dati - Esempio case 3: if ( listObject.removeFromFront( value ) ) cout << value << " removed from list\n"; listObject.print(); break; case 4: if ( listObject.removeFromBack( value ) ) cout << value << " removed from list\n";

listObject.print(); break; } } while ( choice != 5 );

cout << "End list test\n\n";}

27

Strutture Dati - Esempio

void instructions(){ cout << "Enter one of the following:\n" << " 1 to insert at beginning of list\n" << " 2 to insert at end of list\n" << " 3 to delete from beginning of list\n" << " 4 to delete from end of list\n" << " 5 to end list processing\n";}

int main(){ List< int > integerList; testList( integerList, "integer" ); // test integerList List< double > doubleList; testList( doubleList, "double" ); // test doubleList return 0;}

28

Strutture Dati - EsempioTesting a List of integer valuesEnter one of the following:

1 to insert at beginning of list2 to insert at end of list3 to delete from beginning of list4 to delete from end of list5 to end list processing

? 1Enter integer: 1The list is: 1

? 1Enter integer: 2The list is: 2 1

? 2Enter integer: 3The list is: 2 1 3

? 2Enter integer: 4The list is: 2 1 3 4

29

Strutture Dati - Esempio? 32 removed from listThe list is: 1 3 4

? 31 removed from listThe list is: 3 4

? 44 removed from listThe list is: 3

? 43 removed from listThe list is empty

? 5End list test

30

Strutture Dati - EsempioTesting a List of float valuesEnter one of the following:

1 to insert at beginning of list2 to insert at end of list3 to delete from beginning of list4 to delete from end of list5 to end list processing

? 1Enter float: 1.1The list is: 1.1

? 1Enter float: 2.2The list is: 2.2 1.1

? 2Enter float: 3.3The list is: 2.2 1.1 3.3

? 2Enter float: 4.4The list is: 2.2 1.1 3.3 4.4

31

Strutture Dati - Esempio

? 32.2 removed from listThe list is: 1.1 3.3 4.4

? 31.1 removed from listThe list is: 3.3 4.4

? 44.4 removed from listThe list is: 3.3

? 43.3 removed from listThe list is empty

? 5End list test

All nodes destroyedAll nodesd destroyed