2

了解しました。私の教授(データ構造クラス)はこれを割り当てました。あなたのタスクは、二重リンクリストの文字アクセス頻度を更新できるプログラムを作成することです。プログラムは、多くの文字を含むテキストファイルから一度に1文字を読み取る必要があります。簡単にするために、スペースを数えないでください。文字にアクセスするたびに、リストのノードでそのアクセス頻度を1ずつ増やします。現在のノードの頻度が前のノードよりも高い場合は、リスト内で2つのノードを交換する必要があります。以前のノードのアクセス頻度が低くなるまで、以前のすべてのノードに対してこれを続けます。最終的に、頻度が最も高い文字がリストの先頭に表示され、次に高い文字が次のノードに表示されます。プログラムは、リスト内の文字をリストの順序に従って印刷する必要もあります。

これが私がこれまでに作ったプログラムです。現在のところ、これは二重にリンクされたリストです。私の主な質問は、「キャラクターがアクセスされるたびに、リストのノードでそのアクセス頻度を1つ増やします。現在のノードの頻度が前のノードよりも高い場合、2つのノードはリストで交換されます。」?

ファイルから情報を取得する行がないことはわかっています。後で追加します。どんな助けでも大歓迎です!

public class DoublyLinkedList {
private class Node {
    String value;
    Node next,prev;

    public Node(String val, Node n, Node p) {
        value = val;
        next = n;
        prev=p;
    }

    Node(String val) {
        this(val, null, null);
    }
}
private Node first;
private Node last;

public DoublyLinkedList() {
    first = null;
    last = null;
}
public boolean isEmpty(){
    return first==null;
}
public int size(){
    int count=0;
    Node p=first;
    while(p!=null){
        count++;
        p=p.next;
    }
    return count;
}
public void add(String e) {

    if(isEmpty()){
        last=new Node(e);
        first=last;
    }
    else{
        last.next=new Node(e, null, last);
        last=last.next;
    }
}
public void add(int index, String e){
    if(index<0||index>size()){
        String message=String.valueOf(index);
        throw new IndexOutOfBoundsException(message);
    }
    if(index==0){
        Node p=first;
        first=new Node(e,p,null);
        if(p!=null)
            p.prev=first;
        if(last==null)
            last=first;
        return;
    }
    Node pred=first;
    for(int k=1; k<=index-1;k++){
        pred=pred.next;
    }
    Node succ=pred.next;
    Node middle=new Node(e,succ,pred);
    pred.next=middle;
    if(succ==null)
        last=middle;
    else
        succ.prev=middle;
}
public String toString(){
    StringBuilder strBuilder=new StringBuilder();
    Node p=first;
    while(p!=null){
        strBuilder.append(p.value+"\n");
        p=p.next;
    }
    return strBuilder.toString();
}
public String remove(int index){
    if(index<0||index>=size()){
        String message=String.valueOf(index);
        throw new IndexOutOfBoundsException(message);
    }
    Node target=first;
    for(int k=1; k<=index;k++){
        target=target.next;
    }
    String element=target.value;
    Node pred=target.prev;
    Node succ=target.next;
    if(pred==null)
        first=succ;
    else
        pred.next=succ;
    if(succ==null)
        last=pred;
    else
        succ.prev=pred;
    return element;
}
public boolean remove(String element){
    if(isEmpty())
        return false;
    Node target=first;
    while(target!=null&&!element.equals(target.value))
        target=target.next;
    if(target==null)
        return false;
    Node pred=target.prev;
    Node succ=target.next;
    if(pred==null)
        first=succ;
    else
        pred.next=succ;
    if(succ==null)
        last=pred;
    else
        succ.prev=pred;
    return true;
}
public static void main(String[] args){
    DoublyLinkedList list1=new DoublyLinkedList();
    String[] array={"a","c","e","f"};
    for(int i=0; i<array.length; i++){
        list1.add(array[i]);
    }
    list1.add(1,"b");
    list1.add(3,"d");
    System.out.println(list1);

}


}
4

3 に答える 3

4

これは宿題なので、ヒントだけをあげます。

  • クラスNodeには、カウンター用の追加フィールドが必要です。

  • リストを反復処理して、アクセスされた文字を見つけ、そのカウンター値をインクリメントする必要があります。

  • Nodeノードを交換するには一時オブジェクトが必要です。最初に自分で試してから、グーグルで検索してください。これは、すべてのプログラマーが知っておく必要のある重要なプロセスです。

于 2013-03-24T00:06:25.650 に答える
0

助言:

「ファイルから情報を取得する行がないことはわかっています。」。すでに書いたものをテストできるように、今すぐそのコードを書くほうがよいでしょう。

もう1つの問題は、これまでに作成したものが一般的なリンクリストであり、リストの使用方法を示す要件を無視していることです。その結果、次のようになります。

  • 不要と思われる一連のメソッドを実装し、
  • 要件に対してNodeクラスが正しく実装されていません。

戻って要件を確認し、実際に必要なメソッドを見つけて、それらを実装します。(これまでに行ったことは、トップレベルが必要とするものをほとんど無視する「ボトムアップ」設計です。「トップダウン」アプローチを使用した方がよいでしょう。)

解決するように求められる問題は、「汎用」リンクリストデータ構造を作成するのではなく、文字を照合することです。

于 2013-03-24T00:18:02.037 に答える
0

手順を構成要素に分解することをお勧めします。セバスチャンが上で言ったように、あなたはあなたがカウントを維持して更新する必要があることを知っています。また、ランキングでノードの数をその上のノードの数と比較できる必要があることも知っています。2つのノードを交換できる必要があることはわかっています。あなたはそれらのための方法を持っているべきです。それぞれの分解された方法で何が起こる必要があるかを考えてください。

私は常に、これらの種類の問題の感触をつかむために、物理的なアプローチをお勧めします。一連のノートカードまたはポストイットノートを使用してこれを実行してみてください。それぞれに、オブジェクト名とNodeオブジェクトのフィールドを記述します。フィールド値を鉛筆で書きます。他のフィールド(最初の要素への参照など)を紙に書き留めます。次に、アルゴリズムをステップ実行し、更新ごとに何を変更する必要があるかを確認します。(注:これは二重にリンクされたリストであるため、変更はカードのスタックをシャッフルしても存続するはずです。それを試してみてください)

割り当てで頑張ってください!

于 2013-03-24T00:18:38.043 に答える