0

配列ではなくリンク リストに BubbleSort アルゴリズムを実装する必要があります。私はJavaが初めてなので、コードに入れる方法がよくわかりません。しかし、私はそれを試してみました。ここに私が得たものがあります：

SinglyNode.java

public class SinglyNode
{
public Object names;
public SinglyNode next;

public SinglyNode (Object name1)
{
    names = name1;
}

public SinglyNode (Object name2, SinglyNode next1)
{
    names = name2;
    next = next1;
}

Object getObject()
{
    return names;
}

SinglyNode getNext()
{
    return next;
}

void displayLink()
{
    System.out.print("{" + names + "}");
}
}

LinkList.java私の問題はここのメソッドにあると思います。オブジェクト名を昇順でソートするように BubbleSort を実装する方法がわかりません。

public class LinkList
{
SinglyNode first;

public boolean isEmpty()
{
    return (first == null);
}

void insertFirst(Object name1)
{
    SinglyNode newNode1 = new SinglyNode(name1);
    newNode1.next = first;
    first = newNode1;
}

SinglyNode delete(Object name2)
{
    SinglyNode temp = first;
    first = first.next;
    return temp;
}

void display()
{
    System.out.print("LIST: \n");
    SinglyNode current = first;
    while(current != null)
    {
        current.displayLink(); // print data
        current = current.next; // move to next link
    }
    System.out.println("\n");
}
//////////////////////////////////////////////////////    
void bubbleSort()
{ 
    Object n = first;
    Object temp = first;

    if (na.compareTo(first) < first.compareTo(na))
    {
        temp = na.compareTo(first);
    } else {
        temp = first.compareTo(na);
    }
    System.out.println(temp);

}

private void swap(Object one, Object two)
{ 
    Object temp = one.names;
    one.names = two.names;
    two.names = temp; 
}
}

SinglyLinkList.java

public class SinglyLinkList
{
public static void main (String args[])
{
    LinkList list = new LinkList();

    list.insertFirst("Squirtle");
    list.insertFirst("Bulbasaur");
    list.insertFirst("Charmander");
    list.insertFirst("Pichu");
    list.insertFirst("Ghastly");
    list.insertFirst("Mewtwo");
    list.insertFirst("Dialga");

    list.display();
    list.bubbleSort();
    list.display();

}
}
4

6 に答える 6

2

あなたのリストでは、リスト内の要素の数を保存するために、サイズ フィールドを持つことが役立ちます。SinglyNode implement Comparableまた、メソッドが希望どおりに動作するようにクラスを作成compareToします。Single LinkedList の 2 つの要素のインプレース スワップは、実際には非常に複雑であり、パフォーマンスは非常に悪いです。

public void bubbleSort
{
  for (int i = 0; i < size; i++)
  {
    for (int j = i; j < size; j++)
    {
       if (elementAt(j).compareTo(elementAt(j+1)) > 0)
       {
          swap(j, j + 1);
       }
    }
  }
}

public SinglyNode elementAt(int index)
{
   SinglyNode temp = first;

   for (int i = 0, i < index; i++)
   {
      temp = temp.getNext();
   }

   return temp;
}

public void swap(int firstIndex, int secondIndex)
{
   SinglyNode secondNext = elementAt(secondIndex).getNext();       
   SinglyNode second = elementAt(secondIndex);
   SinglyNode first = elementAt(first);
   SinglyNode firstPrevious = elementAt(first - 1);


   firstPrevious.setNext(second);
   first.setNext(secondNext);
   second.setNext(first);
}
于 2013-04-16T10:08:14.740 に答える
0

宿題・宿題なので、直接の解決ではなくヒントを出します。バブル ソートは、コレクションの反復と要素の交換という 2 つの操作に抽象化できます。これらの操作は、配列または連結リストで異なる方法で実装されますが、アルゴリズムは同じです。に反復処理がdisplayあり、スワッピングを実装してから実行する必要があります (非常に抽象的な擬似コード:

iterate {
 iterate {
  if el.Compare(elNext) > 0 {
    swap(el, el.Next);
  }
 }
}
于 2013-04-16T09:57:13.183 に答える
0

Comparable インターフェイスを SinglyNode に実装し、実装内で文字列比較メソッドを使用する必要があります。何かのようなもの：

public void compareTo(SinglyNode node){
    return this.names.toString.compareTo(node.getNames().toString());
}

またはより良いだけthis.names.compareTo(node.getNames());

ただし、Object クラスを使用するだけでなく、それらのワイルドカード オブジェクトに Comparable インターフェイスを使用します。

于 2013-04-16T09:51:58.550 に答える