Strutture dati

Da Bioingegneria Elettronica e Informatica.

Vitoantonio Bevilacqua vitoantonio.bevilacqua@poliba.it

Antonio Brunetti antonio.brunetti@poliba.it

Gianpaolo Francesco Trotta gianpaolofrancesco.trotta@poliba.it

Pagina in lavorazione

Introduzione

Le strutture dati astratte sono strutture dati che non specificano il modo in cui i dati vengono memorizzati in memoria, ma ciascuna definisce un particolare comportamento di tipo logico nell'organizzazione dei dati. La rappresentazione di una struttura di dati astratta fatta mediante strutture dati concrete è detta "implementazione". Le strutture astratte che qui di seguito definiremo e implementeremo sono la Pila, la Coda.

Pila

La pila (o stack) è una struttura di dati astratta, monodimensionale, costituita da elementi omogenei, ad esempio di tipo intero, ordinati in una sequenza. La pila segue la logica di gestione dei dati LIFO (Last In First Out): le operazioni di inserimento ed eliminazione/estrazione di un elemento della pila sono effettuale dallo stesso estremo della sequenza, detto "testa della pila", dunque l'ultimo elemento inserito è quello che per primo viene estratto/eliminato.

Per implementare la struttura dati astratta PILA con un vettore, bisogna innanzitutto decidere (o conoscere) la sua profondità, ovvero la massima dimensione del vettore che la rappresenta. Poiché si vuole fare in modo che il vettore si comporti come una pila, deve essere possibile aggiungere ed estrarre elementi dal vettore seguente la logica desiderata; per far ciò sono state implementate due funzioni: inserisciElemento() ed estraiElemento(). Per la gestione della pila è necessaria una variabile intera che rappresenti l’indice, ovvero la testa della pila (head). Questa variabile ha il compito quindi di indicare la posizione nella quale inserire il prossimo elemento. È ovvio che dopo aver inserito un elemento, questa debba essere incrementata; ma nell’estrazione necessita decrementarla prima, perché a quell’indice nella pila non esiste ancora nulla in quanto l'ultimo elemento inserito si trova all'indice precedente.


Pila.png

Implentazione della Pila

  1. import java.util.Scanner;
  2.  
  3. public class Pila {
  4.  
  5. 	private int[] pila;
  6. 	private int head;
  7. 	private int length;
  8.  
  9. 	public Pila(int len) {
  10. 		length = len;
  11. 		pila = new int[length];
  12. 		head = 0;
  13. 	}
  14.  
  15. 	public void run() {
  16. 		Scanner s = new Scanner(System.in);
  17. 		int scelta = -1;
  18.  
  19. 		while (scelta != 0) {
  20. 			System.out.print("Inserisci scelta (1 per inserire, 2 per estrarre, 3 per visualizzare, 0 per uscire): ");
  21. 			scelta = s.nextInt();
  22.  
  23. 			if (scelta == 1) {
  24. 				// Inserimento
  25. 				if (head >= length) {
  26. 					System.out.println("La pila è piena");
  27. 				} else {
  28. 					System.out.println("Inserisci elemento: ");
  29. 					inserisciElemento(s.nextInt());
  30. 				}
  31. 			}
  32. 			else if (scelta == 2) {
  33. 				// Estrazione
  34. 				if (head == 0) {
  35. 					System.out.println("La pila è vuota");
  36. 				} else {
  37. 					int ele = estraiElemento();
  38. 					System.out.println("L'elemento estratto vale: " + ele );
  39. 				}
  40. 			}
  41. 			else if (scelta == 3) {
  42. 				// Visualizzazione
  43. 				if (head== 0) {
  44. 					System.out.println("La pila è vuota");
  45. 				} else {
  46. 					stampaPila();
  47. 				}
  48. 			}
  49. 		}
  50.  
  51. 		System.out.println("Ciao");
  52.  
  53. 	}
  54.  
  55. 	public void inserisciElemento(int ele) {
  56. 		pila[head] = ele;
  57. 		head++;
  58. 	}
  59.  
  60. 	public int estraiElemento() {
  61. 		head--;
  62. 		return pila[head];
  63. 	}
  64.  
  65. 	public void stampaPila() {
  66. 		int i = 0;
  67. 		System.out.println("Gli elementi nella pila sono: ");
  68. 		for (i = 0; i < head; i++) {
  69. 			System.out.print(pila[i] + " ");
  70. 		}
  71. 		System.out.println();
  72. 	}
  73. }


  1. import java.util.Scanner;
  2.  
  3. public class Principale {
  4.  
  5. 	public static void main(String[] args) {
  6.  
  7. 		Scanner s = new Scanner(System.in);
  8. 		System.out.print("Inserisci lunghezza pila: ");
  9. 		Pila p = new Pila(s.nextInt());
  10. 		p.run();
  11. 	}
  12. }

Coda

La "coda" o "queue" è una struttura dati monodimensionale e costituita da elementi omogenei ordinati in sequenza. Essa segue la logica FIFO (First In First Out), ovvero le operazioni vengono effettuate su due estremi differenti.

Analogamente alla struttura PILA, per implementare la struttura dati astratta CODA attraverso un vettore, bisogna innanzitutto decidere (o conoscere) la sua lunghezza, che quindi sarà la massima dimensione del vettore che la rappresenta. Inoltre, per gestire la coda sono necessari due indici, ovvero il puntatore d’inserimento (tail) e puntatore d’estrazione (head), che indicano i due estremi della coda. Verosimilmente, quando inserisco un elemento nella coda, il puntatore d’inserimento deve essere incrementato, mentre quando estraggo un elemento dalla coda è il puntatore d’estrazione ad incrementare. Quando il puntatore d’inserimento ha raggiunto il valore massimo, ovvero quello della lunghezza della coda, si potrebbe pensare che questa sia piena; tuttavia, se durante l'esecuzione è stato estratto almeno un elemento, allora è possibile inserirne un altro (“si è liberato un posto”), gestendo il vettore ciclicamente. Effettuare la gestione ciclica della coda significa che i puntatori, quando raggiungono la lunghezza della coda devono essere riportati all’inizio della stessa, il che vuol dire che l’incremento si traduce nel resto della divisione per la lunghezza.

Coda.png

Implementazione della Coda

  1. import java.util.Scanner;
  2.  
  3. public class Coda {
  4.  
  5. 	private int[] coda;
  6. 	private int head;
  7. 	private int tail;
  8. 	private int length;
  9. 	private int size = 0;
  10.  
  11. 	public Coda(int len) {
  12. 		length = len;
  13. 		coda = new int[length];
  14. 		head = 0;
  15. 		tail = 0;
  16. 	}
  17.  
  18. 	public void run() {
  19. 		Scanner s = new Scanner(System.in);
  20. 		int scelta = -1;
  21.  
  22. 		while (scelta != 0) {
  23. 			System.out.print("Inserisci scelta (1 per inserire, 2 per estrarre, 3 per visualizzare, 0 per uscire): ");
  24. 			scelta = s.nextInt();
  25.  
  26. 			if (scelta == 1) {
  27. 				if (size == length) {
  28. 					System.out.println("La coda è piena");
  29. 				} else {
  30. 					System.out.print("Inserisci il prossimo elemento elemento in coda: ");
  31. 					inserisciElemento(s.nextInt());
  32. 				}
  33. 			}
  34. 			else if (scelta == 2) {
  35. 				// 
  36. 				if (size == 0) {
  37. 					System.out.println("La coda è vuota");
  38. 				} else {
  39. 					int ele = estraiElemento();
  40. 					System.out.println("L'elemento estratto vale: " + ele );
  41. 				}
  42. 			}
  43. 			else if (scelta == 3) {
  44. 				// stampa
  45. 				if (size == 0) {
  46. 					System.out.println("La coda è vuota");
  47. 				} else {
  48. 					stampaCoda();
  49. 				}
  50. 			}
  51. 		}
  52. 		System.out.println("Fine Programma");
  53.  
  54. 	}
  55.  
  56. 	public void inserisciElemento(int ele) {
  57. 		coda[tail] = ele;
  58. 		tail = (tail + 1) % length;
  59. 		size++;
  60.  
  61. 	}
  62.  
  63. 	public int estraiElemento() {
  64. 		int ele = coda[head];
  65. 		head = (head + 1) % length;
  66. 		size--;
  67. 		return ele;
  68. 	}
  69.  
  70. 	public void stampaCoda() {
  71. 		int i = 0;
  72. 		System.out.print("Gli elementi nella coda sono:");
  73. 		for (i = 0; i < size; i++) {
  74. 			System.out.print(" " + coda[(head + i) % length]);
  75. 		}
  76. 		System.out.println();
  77. 	}
  78. }


  1. import java.util.Scanner;
  2.  
  3. public class Principale {
  4.  
  5. 	public static void main(String[] args) {
  6.  
  7. 		Scanner s = new Scanner(System.in);
  8. 		System.out.println("Inserisci lunghezza coda: ");
  9. 		Coda p = new Coda(s.nextInt());
  10. 		p.run();
  11. 	}
  12. }
Estratto da "http://www.vitoantoniobevilacqua.it/wiki/index.php?title=Strutture_dati&oldid=504"