una - Fusionar ordenar en cadenas en Java-Lista enlazada

ordenar lista enlazada java

Question

Tengo un ejercicio en el que tengo que insertar en una lista vinculada una cadena. Supongamos que la cadena es la siguiente:

"Java Coding Is Great"

Después del Merge Sort, se supone que la lista vinculada debe verse así:

coding >>> great >>> is >>> java.

El problema es que en mi código Merge Sort recibo lo siguiente:

 great >> is >> java >> coding 

Todas las palabras están ordenadas, PERO LA PRIMERA PALABRA (Jefe de la lista original) no lo es.

Tengo dos clases: TextList y WordNode.

La clase WordNode tiene dos atributos:

String _word; WordNode _next; //an address to the next link

La clase TextList solo tiene un atributo: una dirección del encabezado de la lista vinculada:

WordNode _head;

Tengo un constructor en el que inserto el String al azar en una lista vinculada. al final, comienza a fusionarse en la lista. Este algorithem es para este ejercicio.

public TextList(String text){
String s=""; int index=text.length();
//we will stop at the end of the String.
for (int i=text.length()-1; i>=0; i--){
//if we reached a space, insert each string in appropriate order,
//the first word is the head of the string and last word points to null.
if (!(text.charAt(i)>=''a'' && text.charAt(i)<=''z'')){
s=text.substring(i,index);
_head=new WordNode(s,_head);
s="";
index=i;
}
if (i==1){
s=text.substring(i-1,index);
_head=new WordNode(s,_head);
}
}
//start merge sotring the list.
this._head=this._head.mergeSort();
}

Métodos de ordenación de fusión: mergeSort, merge y split: (Están en la clase WordNode):

Método de fusión de ordenación

public WordNode mergeSort(){
return mergeSort(this);
}
private WordNode mergeSort(WordNode h){
// Sort h by recursively splitting and merging
if (h==null || h._next==null)
return h;
else{
WordNode evens=h.splitOdds();
WordNode odds=h.splitEvens();
return mergeSort(odds).merge(mergeSort(evens));
}
}

Método de fusión

private WordNode merge(WordNode h){
//method merges this''s list with h''s list
//if h is null, just return this.
if (h==null){
return this;
}
if (this._word.compareTo(h._word)<0){
if (this._next==null)
return new WordNode(this._word,h);
else
return new WordNode(this._word,this._next.merge(h));
}
else
return new WordNode (h._word, merge(h._next));
}

Métodos divididos: uno para posiciones pares, uno para posiciones impares.

private WordNode splitOdds(){
boolean flag=true;
WordNode odds=null;
WordNode ptr=this;
while (ptr!=null){
if(flag)
odds=new WordNode(ptr._word,odds);
ptr=ptr.getNext();
flag=!flag;
}
return odds;
}
//MUST BE INITILIZED ON HEAD
private WordNode splitEvens(){
boolean flag=true;
WordNode evens=null;
WordNode ptr=this._next;
while (ptr!=null){
if (flag)
evens=new WordNode(ptr._word,evens);
ptr=ptr.getNext();
flag=!flag;
}
return evens;
}

Por favor, ayúdame a descubrir lo que está mal. Desafortunadamente, no puedo usar una tercera clase , y no puedo usar punteros al comienzo de la lista o al final de la lista.

Answer 1

¿Puedes usar tu depurador para pasar un solo paso por tu código? Eso te ayudará a identificar el problema. Incluso algunos puntos de interrupción juiciosamente ubicados ayudarán.

Comience con una lista que contenga solo una entrada: "Java". Mira qué pasa.

Luego intente con una lista de dos entradas: "Java Coding". Vea lo que sucede en ese caso.

Resuelva lo que está sucediendo en los casos simples y luego trabaje con los más complejos.

Answer 2

El problema aquí fue un poco gracioso.

En mi constructor, he llevado un espacio con cada palabra que he insertado en mi lista.

Lo arreglé por este código:

 s=text.substring(i+1,index);

en lugar de:

 s=text.substring(i,index);

El crédito es para NormR de DevForum por la respuesta.

Answer 3

Bien, pero no me gusta su solución para fusionar () en WordNode. Por un lado, puedes comparar cada nodo que prefieres para que te guste esto:

this._word.compareTo(h._word);

Pero en ese caso merge () y split () ambos privados, así que creo que la mejor manera es ponerlos en TextList y mergeSort () sin sobrecargarlos. Debe ordenar todos los nodos en la lista vinculada siempre que agregue un nodo, no solo una parte de él de todos modos. Es por eso que esto

this._head = this._head.mergeSort();

y esto

public WordNode mergeSort(){
return mergeSort(this);
}

parece inútil en WordNode.
Por otro lado, si pones tu llamada a mergeSort en TextList como esta

this._head = this.mergeSort(this._head);

y mergeSort en este en TextList

 public WordNode mergeSort(WordNode n){
}

ya es mejor, pero puede hacerlo mucho mejor al reducir la competencia de tiempo y espacio de la forma en que divide su lista en probabilidades y eveces como este

int counter = 1; // nodes counter helps to know if the current node is odd or even
WordNode L = null, // odd nodes
R = null; // even nodes
while(h != null)
{
if(counter%2 == 0)
R = new WordNode(h.getWord(), R, h.getWordCounter());
else
L = new WordNode(h.getWord(), L, h.getWordCounter());
//
h = h.getNext();
counter++;
}

Cuando lo juntas, obtienes algo como esto (no olvides el contador de palabras)

public WordNode mergeSort(WordNode h){
int counter = 1; // nodes counter helps to know if the current node is odd or even
WordNode L = null, // odd nodes
R = null; // even nodes
while(h != null)
{
if(counter%2 == 0)
R = new WordNode(h.getWord(), R, h.getWordCounter());
else
L = new WordNode(h.getWord(), L, h.getWordCounter());
//
h = h.getNext();
counter++;
}
return merge(mergeSort(L), (mergeSort(R)));
}

lo que queda ahora es terminar de fusionar () de esta manera y de nuevo no olvidar el contador de palabras

private WordNode merge(WordNode L, WordNode R)
{
while(L != null || R != null)
{
if(L != null && R != null)
if(L.getWord().compareTo(R.getWord()) <= 0)
return new WordNode(L.getWord(), merge(L.getNext(), R), L.getWordCounter());
else
return new WordNode(R.getWord(), merge(L, R.getNext()), R.getWordCounter());
else if(L != null)
return new WordNode(L.getWord(), merge(L.getNext(), R), L.getWordCounter());
else if(R != null)
return new WordNode(R.getWord(), merge(L, R.getNext()), R.getWordCounter());
}
return null;
}

saluda al profesor Rosenstein ;-)