Informatica I - Esercizi contenitore di parole

SOLUZIONE:

La classe Text.

La parte piu` impegnativa consiste nella realizzazione del metodo di ordinamento. Abbiamo usato

l'algoritmo mergeSort: notare l'uso del metodo ausiliario (e privato) mergeSort, in cui la presenza di

parametri espliciti consente di realizzare mergeSort in maniera ricorsiva (mentre il metodo sort, non

avendo parametri impliciti, non puo` realizzare direttamente mergeSort in maniera ricorsiva).

**CONTINUA**

import java.util.NoSuchElementException;

public class Text implements Container private static void merge(Comparable[] v,

{ Comparable[] v1, Comparable[] v2)

public Text() {

{ words = new String[1]; int i = 0, i1 = 0, i2 = 0;

wordsSize = 0; while (i1 < v1.length && i2 < v2.length)

} if (v1[i1].compareTo(v2[i2]) < 0)

// prima si usa i, poi lo si

/* incrementa...

verifica se l'elenco di parole e' vuoto. v[i++] = v1[i1++];

restituisce true se vuoto, false altrimenti else

*/ v[i++] = v2[i2++];

public boolean isEmpty() while (i1 < v1.length)

{ return wordsSize == 0; } v[i++] = v1[i1++];

while (i2 < v2.length)

/* v[i++] = v2[i2++];

restituisce il numero di elementi presenti nel }

contenitore /*

*/ restituisce l'ultima parola dell'elenco,

public int size() rimuovendola

{ return wordsSize; } Lancia NoSuchElementException se

l'elenco e' vuoto

/* */

aggiunge la parola aWord in coda all'elenco public String removeLast() throws

se l'elenco e' pieno, ridimensiona l'elenco. NoSuchElementException

*/ { if (isEmpty())

public void add(String aWord) throw new NoSuchElementException();

{ if (wordsSize == words.length) String value = words[wordsSize-1];

resize(); wordsSize--;

words[wordsSize] = aWord; return value;

wordsSize++; }

}

private void resize() // variabili di esemplare

{ String[] newAr = new String[2*wordsSize]; private String[] words;

for (int i = 0; i < wordsSize; i++) private int wordsSize;

newAr[i] = words[i]; }

words = newAr;

}

/* ordina per fusione l'elenco delle parole.

*/

public void sort()

{ mergeSort(words,wordsSize); }

private void mergeSort(Comparable[] v, int vSize)

{ if (vSize < 2) return; // caso base

int mid = vSize / 2; //dividiamo circa a meta`

Comparable[] left = new Comparable[mid];

Comparable[] right = new Comparable[vSize - mid];

System.arraycopy(v, 0, left, 0, mid);

System.arraycopy(v, mid, right, 0, vSize-mid);

// passi ricorsivi: ricorsione multipla (doppia)

mergeSort(left, mid);

mergeSort(right, vSize-mid);

// fusione (metodo ausiliario)

merge(v, left, right);

} **CONTINUA**