1.Scrivere un algoritmo ricorsivo per riorganizzare una array di interi in modo tale che tutti i valori pari occorrano prima di tutti quelli dispari; tranne che per questa proprietà, l’ordine dei valori deve rimanere invariato. Per esempio, l’array [1, 2, 3, 4, 5. 6] deve essere riorganizzata nell’array [2, 4, 6, 1, 3, 5]. Evitare di usare altre array.
2.Usando la classe Insieme e la classe Character, sviluppare una applicazione che legge in input due stringhe e visualizza l’insieme dei caratteri che compaiono in almeno una delle due stringhe, e l’elenco dei caratteri che compaiono in ambedue le stringhe. L'output deve prima riportare i caratteri nell’ordine in cui appaiono nelle due stringhe, e poi in ordine lessicografico.
3.Per i problemi seguenti, sviluppare codice Java per manipolare liste linkate, usando le seguenti interfacce Node e LinkedList. Implementeremo queste interfacce in classe.
public class Node {
// Constructor.
public Node
(int value)
{...}
// Get the value
in the node.
public int
getValue () {..}
// Set a new value for the node.
public void
setValue (int newValue) {..}
// Set the reference
to the next
node.
public void
setNext (Node nextNode) {..}
// Get the reference
to the next
node. May be “null”
public Node
getNext () {..}
// The following are for doubly
linked
lists only!
// Set the reference
to the previous
node.
public void
setPrevious (Node
previousNode) {..}
// Get the reference
to the previous
node. May be “null”
public Node
getPrevious () {..}
}
public class
LinkedList {
// Constructor.
public LinkedList
() {..}
// Get the first node.
public Node
getFirstNode () {..}
// Insert a node
after some other
node. Sets links
appropriately.
// Throws an
exception if
the insertAfter node
is not in the list.
// Pass null to insertAfter
to insert at
the head of the list.
public void
insertNode (Node
newNode, Node insertAfter)
throws Exception
{..}
// Remove a node.
Sets links appropriately.
// Throws an
exception if
the node is not
in the list.
public void
removeNode (Node
deadNode) throws
Exception {..}
// Returns the current size of
the list.
public int
size () {..}
}
a) Scrivere codice per implementare insertNode<() come descritto sopra, sia per liste (i) singolarmente linkate, sia per liste (ii) doppiamente linkate. Ignorare inizialmente la sostituzione del nodo di testa (cioè ignorare il caso dove insertAfter ha valore null). Concentrarsi sul mantenere l’integrità della lista (cioè la correttezza dei collegamenti da nodo a nodo).
b)Date due liste, L1 and L2, implementare il metodo public LinkedList interpolate (LinkedList list1, LinkedList list2) che restituisce una nuova lista costruita intervallando i nodi delle due liste (cominciare con il primo elemento di L1, poi il primo di L2, poi il secondo di L1 e così via fino all’esaurimento delle due liste che possono NON avere la stessa lunghezza). Sviluppare prima il metodo per liste singolarmente linkate, e poi per liste doppiamente linkate. (Suggerimento: si può usare il metodo insert , implementato in precedenza, oppure inserire i nodi ‘manualmente’, ma i nodi nelle liste originali non devono essere duplicati)
c) Implementare un metodo booleano public boolean areEquivalent (LinkedList L1, LinkedList L2) che prende due liste circolari linkate singolarmente e stabilisce se sono ‘equivalenti’, cioè se hanno la stessa sequenza di valori anche se ruotata (diverso ‘primo’ elemento). Attenzione: le liste potrebbero avere valori ripetuti.
d) Sviluppare una classe per implementare uno stack (pila) con liste singolarmente linkate (invece che una array) con i metodi push(int), pop() e size () che restituiscono interi, non >Nodes, che sono usati internamente. Quali sono i vantaggi e gli svantaggi rispetto ad uno stack implementato con array?
e) Implementare un metodo public bool isPalindrome (Queue letters) che usa iterazione, non ricorsione, ed uno stack (con i metodi standard) per stabilire se una stringa è palindroma La stringa è data inizialmente in una coda (queue) di caratteri, accessibili sequenzialmente invocando il metodo dequeue().
f) Sviluppare una classe che implementa l’interfaccia queue (con metodi enqueue(), dequeue() e size() su int , per esempio) usando due stack .