Java의 문자열 병합 정렬 - 연결된 목록

Question

나는 연결된 목록에 문자열을 삽입해야하는 연습장이 있습니다. 문자열은 다음과 같다 가정 : 병합 정렬 후

"Java Coding Is Great" 

은, 링크 된 목록은 그 같이 가정한다 :

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

문제는 내 병합 분류 코드에서 나는 다음을받을 것입니다 :

great >> is >> java >> coding 

모든 단어가 정렬되지만 모든 단어는 정렬됩니다 (원래 목록의 헤드).

두 가지 클래스가 있습니다 : TextList와 WordNode. 연결리스트의 머리의 주소 :

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

TextList 클래스는 하나의 속성이 있습니다

WordNode 클래스는 두 개의 속성이 있습니다

WordNode _head; 

나는 생성자가있는 I 문자열을 링크 된 목록에 임의로 삽입하십시오. 결국 그것은 목록을 병합 시작합니다. 이 알고리즘은이 훈련에 사용됩니다.

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(); 
} 

병합 정렬 방법 : 머지 소트가 합병 및 분할 (이들은 WordNode 클래스에)

병합 정렬 방법

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)); 
    } 
} 

가

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)); 

    } 

방법 병합

분할 방법 : 짝수 위치에 하나, 홀수 위치에 하나씩.

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; 
    } 

무엇이 잘못 되었나요? 불행히도 세 번째 클래스 인, 을 사용할 수 없으며 목록 시작 부분이나 끝 부분에 포인터를 사용할 수 없습니다.

Answer 1

코드를 통해 단계별로 디버거를 사용할 수 있습니까? 그러면 문제를 정확히 찾아내는 데 도움이됩니다. 현명하게 배치 된 몇 개의 중단 점조차도 도움이 될 것입니다.

"Java"라는 단일 항목 만 포함하는 목록으로 시작하십시오. 무슨 일이 일어나는지보십시오.

그런 다음 "Java 코딩"두 항목 목록을보십시오. 이 경우 어떤 일이 일어나는 지보십시오.

단순한 경우에 무슨 일이 일어나고 있는지, 그리고 더 복잡한 문제는 해결하십시오.

Answer 2

여기의 문제는 약간 재미있었습니다.

내 생성자에서 나는 내 목록에 삽입 한 각 단어가있는 공간을 가지고 있습니다.

는이 코드에 의해 그 고정 :

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

대신 :

  s=text.substring(i,index); 

크레딧은 대답을 DevForum에서 NormR이다.

Answer 3

니스,하지만 WordNode에서 병합() 솔루션을 좋아하지 않아.) 민간

this._word.compareTo(h._word); 

그러나이 경우 병합에

() 및 분할 (그래서 더 좋은 방법은 TextList와 머지 소트 (에 넣어하는 것입니다 생각 : 한 손으로 당신은 당신이 좋아하는 것을 선호 각 노드를 비교할 수 있습니다) 과부하없이. 어쨌든 노드의 일부가 아닌 노드를 추가 할 때마다 링크 된 목록의 모든 노드를 정렬해야합니다. 이

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

이

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

이 WordNode에 쓸모 보이는 이유입니다. 당신이 TextList이 하나에이

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

와 머지 소트처럼 TextList에 머지 소트에 전화를 넣으면 한편
는

public WordNode mergeSort(WordNode n){ 

} 

이미 더 나은하지만 당신은 감소하여도 훨씬 더 잘 할 수 당신의리스트를 확률과 확률로 나누는 방법의 시간과 공간의 복잡성이

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++; 
} 

만약 당신이 함께하면 당신은 somet 이 같은 힝 지금 남아있는 것을

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))); 
} 

단어가

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; 
} 

안녕하세요이 로젠 스타를 proffessor하는 말을 대응 잊지 말고 다시 다음과 같이 병합()를 완료하는 것입니다 (단어 대응 잊지 마세요) ;-)