Come unire due liste ADT Ordinati

September 8

Un elenco tipo di dato astratto (ADT), o lista collegata come è più comunemente chiamato, è una delle strutture dati fondamentali in informatica e una delle prime alternative al semplice array appreso da uno studente di informatica. Anche se sacrifica la possibilità di spostare al centro della lista senza la ricerca attraverso l'elenco prima, l'elenco ADT rende banalmente facile per espandere e ridurre i dati memorizzati. Questo codice è implementato in Java, in quanto struttura di dati Lista Linked built-in di Java ci permette di arrivare direttamente al punto, ma la stessa logica potrebbe essere attuato con la minima modifica in qualsiasi altra lingua C-like.

istruzione

1 Crea le tue due liste collegate e inizializzare con alcuni dati allineati secondo incollando il seguente in un file Java:

LinkedList<Double> list1 = new LinkedList<Double>();
LinkedList<Double> list2 = new LinkedList<Double>();

for (int x = 0; x & lt; 100; x ++) {
list1.add (Math.random ());
list2.add (Math.random ());
}

Collections.sort (list1);
Collections.sort (list2);

Ora, ci sono due liste collegate piene di numeri casuali che sono stati ordinati.

2 Creare una nuova lista concatenata che contenga l'elenco unito incollando il seguente:

LinkedList<Double> merged = new LinkedList<Double>();

3 Impostare un semplice ciclo while. Questo ciclo procede finché entrambi gli elenchi hanno almeno un elemento in essi, e si muoverà il più piccolo degli elementi migliori all'elenco unito:

// Anche se entrambe le liste non sono vuoti.

while (!list1.isEmpty() && !list2.isEmpty()) {
if (list1.peek() <= list2.peek()) {
merged.add(list1.pop());
} else {
merged.add(list2.pop());
}
}

Il comando "Peek" guarda l'elemento nella parte anteriore della lista, mentre "pop" sia guarda dell'elemento e rimuove. Quando il confronto è fatto, si desidera solo sbirciare in cima alla lista per vedere quale è più piccolo. Quando arriva il momento di unire le liste, si vuole togliere il valore superiore e metterlo sui nuovi elenchi.

4 Finire il lavoro. Appena una lista è vuoto, non c'è bisogno di continuare a fare confronti. Pertanto, il vecchio ciclo termina, e un altro loop viene creato per riempire il resto della lista unito con i rimanenti dati dell'ultima lista:

// Mentre il primo elenco non è vuoto

while (!list1.isEmpty()) {
merged.add(list1.pop());
}

// Mentre il secondo elenco non è vuoto.

while (!list2.isEmpty()) {
merged.add(list2.pop());
}

5 Stampare i risultati in modo da poter controllare la lista fuse e garantire ha funzionato correttamente:

int x = 1;
for (Double y : merged) {
System.out.println(x + " " + y);
x++;
}


Articoli Correlati