1

Java を使用して、このプロジェクトにしばらく取り組んできました。私のプログラムでは Linked List または Array List を使用することが推奨されましたが、これは完全に理にかなっています。しかし教授は、ノードを利用して独自のLinked Listを作成して使用する必要があると述べています。少し調べたりクラスで質問したりしたにもかかわらず、Nodes を使用することで私は非常に混乱しました。それは私が見逃している単純なものだと確信していますが、今は完全に途方に暮れています。ここにリストが格納されているクラスがあります(私は思います)。複数の航空機とそれらに関連するいくつかの詳細 (フライトの名前、速度、高度、飛行機の種類) を格納するためのリストを作成しているため、Aircraft というタイトルが付けられています。ユーザーが操作する Main クラス (リストにはありません) があります。そのクラスはほとんど処理されています。

package airTraffic;

public class Aircraft  {

public static String name;
public static String type;
public static int speed;
public static int alt;

Aircraft nextCraft;

public Aircraft (String n, String t, int s, int a) {
    name = n;
    type = t;
    speed = s;
    alt = a;
}

public Aircraft() {

}

public static void setName(String n) {
    name = n;
}

public static String getName (String lookUp) {
    return name;
}

public static void removeName () {
    //remove the flight - not sure what to place here
}

public static void setType (String t) {
    type = t;
}

public static String getType () {
    return type;
}

public static void setSpeed (int s) {
    speed = s;
}

public static int getSpeed () {
    return speed;
}

public static void setAlt(int a) {
    alt = a;
}

public static int getAlt () {
    return alt;
}

public Aircraft next = null;

//auto generated method from ATControl 
public static void add(String s) {

}

//auto generated methods from ATControl - what goes here???
public static void remove() {

}

public Object getNext() {
    // TODO Auto-generated method stub
    return null;
}

public void setNext(Object next2) {
    // TODO Auto-generated method stub

}
 }

以下に、ノードが作成されて格納されるクラスであると思われるものを示します。これは私が非常に混乱しているところであり、間違っていると思います。実際にノードにデータを追加して保存するためにノードを呼び出す方法がわかりません。また、(フライト名を介して) ノードを取得し、(フライト名を介して) ノードを削除できる必要があります。

package airTraffic;

import java.util.*;
import airTraffic.Aircraft;

public class ATControl {


static Main m = new Main ();
Aircraft aircraft = new Aircraft ();

//declare node names for list
public static Aircraft head = new Aircraft ();
public static Aircraft tail = new Aircraft ();

// stores data
private static final int INITIAL_ALLOCATION = 20;
private static int size = INITIAL_ALLOCATION; 

// tells list to add nodes
public static void Nodes (String s, int n) {
    n = size;
    head.next = tail;
    tail.next = tail;
    Aircraft temp = head;
    for (int i= 0; i < size; ++i) {
        temp.next = new Aircraft ();
        temp = temp.next;
    }
    temp.next = tail;
}

public static void addNodes (int n) {
    n = size;
    Aircraft temp = new Aircraft ();
    Aircraft current = head;
    for (int i = 1; i < n && current.getNext() != null; i++) {
        current = (Aircraft) current.getNext();
        temp.setNext(current.getNext());
        current.setNext (temp);
        size++;
    }
}

//add plane and details
public static void addToList (Scanner in) {
    // should add new aircraft to new node on linked list
    System.out.printf("Enter flight number: ");
    String add = in.next();
    Aircraft.setName (add);
    ATControl.addNodes (Integer.parseInt(add));

    //type of plane
    System.out.printf("Enter type of plane: ");
    String plane = in.next();
    Aircraft.setType (plane);

    //plane speed
    System.out.printf("Enter current speed: ");
    int speed = in.nextInt();
    Aircraft.setSpeed (speed);
    ATControl.addNodes (Integer.parseInt(add));


    //add Altitude 
    System.out.printf("Enter current altitude: ");
    int alt = in.nextInt();
    Aircraft.setAlt(alt);
    ATControl.addNodes (Integer.parseInt(add));  // I am fairly certain this is wrong
}

//show flight
public static void showFlight (Scanner in) {
    System.out.printf("Enter flight number for details: ");
    String lookUp = in.next();
    Aircraft.getName(lookUp);

}
// display all flights
public static void displayAll (Scanner in) {
    System.out.printf("All flights: " );

}
//remove flight
public static void removeFlight (Scanner in) {
    System.out.printf("Enter flight number to be removed: ");

}
}
4

5 に答える 5

2

あなたは近づいています。まず、リンクされたリストは、一般にノードと呼ばれるオブジェクトのリストであり、それぞれが他のオブジェクトへの 1 つ以上のリンクを持っています。あなたの場合、ノードは航空機です。

これは少し役立つはずです: Wikipedia:Linked List

これまでの主な問題は、Aircraft クラスにリンクがないことです。これはリンクされたリストであるため、リスト内の次の要素への参照を含める必要があります。Aircraft クラス内にはnext、リスト内の次の Aircraft にリンクする Aircraft タイプのプロパティが必要です。これまでのコードと同様に、 を呼び出すことができます。これによりmyAircraft.next、リストを順番に下に移動できます。これは宿題ですが、さらに説明が必要な場合は、お気軽にコメントしてください。

于 2012-08-01T02:57:47.317 に答える
1

あなたはかなり近いと思いますが、ATControlクラスで何が起こっているのかを正確に知ることは困難です。通常、リンクリストのaddメソッドは、番号ではなくノード(この場合は航空機)を使用します。

リンクリストの鍵は、各ノードがリスト内の次のノードへのポインタを持っていることです。航空機のクラスには、次のものがあります。次の航空機。これがポインタとして機能します。

ATControlに次のメソッドを実装することをお勧めします。

public static Aircraft getUserInput(Scanner in)
{
  Aircraft aircraft = new Aircraft();

  // get your values from the user and set them in your new aircraft
  return aircraft;
}

public static void add(Aircraft aircraft) 
{
  // starting at head, walk through the list (repeatedly call next on 
  // the current Aircraft) until you reach the desired position 

  Aircraft temp = head;

  while (temp != null) // ...
}

public static void remove(String flightNum)
{
  // again, the same way you did in add, walk through the list until you find it
    if (current.getName().equals(flightNum))
      // we found it, so remove it
}
于 2012-08-01T02:47:25.343 に答える
1

OOP と参照型について十分に理解している場合を除き、LinkedList の実装を作成しようとすることはマゾヒズムの実践です。

以下は長くなり、おそらく苦痛/屈辱的になります。いいですね、いい勉強になります。徹底的なコメント付きで完全な実装を提供するために、私はこれに多大な努力を払っています。その目的を完全に理解するまで、詳細をよく読むことをお勧めします。

まず、Aircraftクラスを修正します。複数のインスタンスを作成する必要があるため、静的メンバーは機能しません。理由がわからない場合は、時間をかけて OOP の基礎を復習してください。

リスト ノードは、最小限のデータを格納するように設計する必要があります。あなたの場合、あなたはほとんどそこにいるようです。各ノードに固有のフライト データと、リスト内の次の項目への参照があります。それだけです。

余計な手間がなければ、次のようになります。

public class Aircraft  {
    public String name;
    public String type;
    public int speed;
    public int alt;
    Aircraft next;

    public Aircraft (String n, String t, int s, int a) {
        name = n;
        type = t;
        speed = s;
        alt = a;
        next = null;
    }
}

よさそうだ。これには必要な機能がすべて組み込まれていると考えて間違いありません。

必要に応じて、次を自由に追加してください。

  • setName()
  • getName()
  • setType()
  • getType()
  • setSpeed()
  • getSpeed()
  • setAlt()
  • getAlt()

注: これらは、静的に設定されていない場合にのみ機能します。呼び出すたびに変更されるAircraftインスタンスを引数の 1 つとして渡す予定がない限り。インスタンス メソッドを使用する方がはるかに簡単です。

変更点:

  • Aircraft()コンストラクターを削除しました。少なくとも、少なくともフライト番号 (またはその他の一意の識別子) を使用してAircraftノードを初期化する必要があります。そうしないと、後でリストで Aircraft を見つけることができなくなります。

  • removeName()は役に立ちません。個々のノードはリスト内の次の項目しか認識していないため、自分自身を削除することはできません。各ノードが前のノードと次のノードの両方への参照を格納する二重リンク リストを使用した場合、それは可能ですが、実際には必要ありません。add ()およびremove()* メソッドについても同様です。追加/削除は **ATControlクラスで処理されます。

  • getNext()setNext()もあまり必要ありません。ATControlはリストの状態 (サイズ、容量など) を維持するために使用されるため、getter/setter を介して nextCraft をパブリックにアクセス可能にしたくないでしょ

ATControl の場合:

public class ATControl {
    private Aircraft head; // stores the start of the chain
    private Aircraft tail; // stores the end of the chain
    private int size; // stores the length of the chain

    public ATControl() {
        // ♫ "Started from the bottom now we're herre' ♫
        // Seriously, the list should start with nothing
        head = null;
        tail = null;
        size = 0;
    }

    public void addFlight(String flight, String plane, int speed, int alt) {
        // TODO: Implement this
    }

    public void removeFlight(String name) {
        // TODO: Implement this 
    }

    public void displayFlight(String name) {
        // TODO: Use a foreach loop to find and display a flight
    }

    public void displayAll() {
        // TODO: Use a foreach loop to display the flights here
    }
}

変更点:

  • ここでどのように機能するのか少しもわからないため、main* メンバーを削除しました。いずれにせよ、これを使用するには、新しい **ATControlインスタンスを作成する必要があります。

  • コンストラクターでインスタンスメンバーを設定する必要があるため、インライン変数宣言を削除しました。

  • 航空機がまだ追加されていないため、は null に初期化されます。

  • 航空機のメンバーは使用しないため、取り外しました。

  • ATControlインスタンスを 1 つだけ作成することを想定している場合を除き、 headtailをあまり静的に設定しないでください。それらのいずれかが ATControl 以外によって変更された場合、リストの内部状態が台無しになるため、プライベートに設定する必要があります。

  • これを機能させる必要がないため、サイズの制約を削除しました。必要に応じて、後で元に戻すことができます。

  • Nodes()とaddNodes ()を廃止した理由は 2 つあります。まず、ノードとノードのコレクションを作成する責任があるため、どちらも SRP (Single Responsibility Principle) に違反しています。2 つ目はバグだと思いますが、作成したいノードの数としてフライト番号を渡していました。たとえば、フライト番号が 1457 の場合、1457 個の空のノードがリストに追加されます。

  • 一貫性を保つために、 addToList( ) の名前をaddFlight()に変更しました。また、一貫性を保つためにshowFlight( ) の名前を displayFlight()に変更しました。簡単にするために、またこのクラスをコマンドライン入力以外にも役立つようにするために、ユーザー入力部分も削除しました。


分かってる!私は無慈悲な肉屋ですが、今ではコードは必要な機能の構築を開始するのに適した位置にあります。

まず最初に。クラスを反復可能にする (つまり、foreach ループとして機能する) 方法がわからない場合は、すぐにわかります。ATControlにさらに何かを追加する必要がありますが、楽しいものになるでしょう。

public class ATControl implements Iterable {
    private Aircraft head;
    private Aircraft tail;
    private int size;

    public ATControl() {
        head = null;
        tail = null;
        size = 0;
    }

    public void addFlight(String flight, String plane, int speed, int alt) {
        // if the list is not currently empty
        if (!isEmpty()) {
            // store a reference to the last Aircraft in the list
            Aircraft prev = tail;
            // create a new aircraft and add it to the end of the list  
            tail = new Aircraft(flight, plane, speed, alt);
            // link the old tail to the new tail
            prev.next = tail;
        }
        // an empty list needs to be handled a little differently
        else {
            // notice, with no tail there's no tail to update
            tail = new Aircraft(flight, plane, speed, alt);
            // also, since there's only one item the head and tail are the same
            head = tail;
        }
        size++;
    }

    // The hard part. Lots of nasty edge cases.
    // Creating one of these from scratch will make your head hurt.
    // Note: Setting variables to null marks them for the garbage collector.
    // SideNote: With a doubly-linked list you can do removals within a foreach loop
    public void removeFlight(String flight) {
        Node prev = head;
        Node curr = head;
        // crawl the list looking for a match
        while (curr.next != null || curr == tail) {
            if (curr.flight.equals(flight)) {
                // if there is only one item left, null everything
                if (size == 1) { head = null; tail = null; }
                // reset the head to start at the second Aircraft
                else if (curr.equals(head)) { head = head.next; }
                // reset the tail to end at the 2nd-to-last Aircraft
                else if (curr.equals(tail)) { tail = prev; tail.next = null; }
                // if it's in the middle, re-connect the broken links on either end
                else { prev.next = curr.next; }
                size--;
                break;
            }
            prev = curr;
            curr = prev.next;
        }
    }

    public boolean isEmpty() {
        return size == 0; // only returns true if size is 0

    // The fun part. The following are necessary to make the list iterable
    // Like magic, this class will now be callable as a foreach loop
    public Iterator<Aircraft> iterator() { return new ATCIterator(); }

    // This iterator code can be reused on any linked-list implementation
    // Keep this handy in case you need to implement Iterable in the future
    private class ATCIterator implements Iterator<Aircraft> {
        private Aircraft current = head;

        public Aircraft next() {
            if (!hasNext()) { throw new NoSuchElementException(); }
            Aircraft aircraft = current;
            current = current.next;
            return aircraft;
        }

        public boolean hasNext() { return current != null; }

        // inline removals require a doubly linked list. To reconnect the break 
        // in the chain the node has to be aware of both the previous and next nodes.
        public void remove() { throw new UnsupportedOperationException(); }
    }

    // lets put that foreach loop functionality to good use now.

    // Bonus: use this to retrieve the matching Aircraft instance
    // Once you have a reference to the Aircraft instance you can do things like
    // get/set it's internal values.
    public aircraft getFlight(String flight) {
        for (Aircraft aircraft : this)
            if (this.flight == flight) {
                return this;
    }


    // displays the flight number of the first match
    public void displayFlight(String flight) {
        for (Aircraft aircraft : this)
            if (this.flight == flight) {
                System.out.printf("Flight: " + flight);
                // Note: you can access the Aircraft details here via the 'this' keyword
                return;
    }

    // crawls the whole list and displays the flight number of every aircraft
    public void displayAll() {
        for (Aircraft aircraft : this)
            System.out.printf("Flight: " + flight);
            // Note: you can access the flight details here via the 'this' keyword
    }
}

そのため、むさぼり食うコメントがたくさんあるコードの壁があります。いくつかの理論の時間です。

とにかくLinkedListをLinkedListにするのは何ですか?

これは文字通り、ヒープ上にランダムに配置され、参照 (または C クラウドのポインター) を介してリンクされたオブジェクト インスタンスの集まりです。

LinkedList をSamba Lineと想像してください。

サンバライン

出典: The Traveling Eye ブログ

注: 二重にリンクされたリストは、線が方向を変えることができることを除いて同じです。

人は皆、前の人にしがみついていますが、後ろにいる人は見えません。リストに追加することは、列の先頭に人を追加するようなものです。技術的には、私が書いた LinkedList は反対方向に機能し、追加は前に追加され、削除は最後から切り取られますが、概念は同じです。

リストからアイテムを取得/削除することは、リンボ ポールを追加するようなものです。最初のヒットはチェーンから取り除かれ、ブレークの端を再接続することでブレークが修復されます。

LinkedList を使用する利点は、好きなだけ大きくしたり小さくしたりできることです。必要に応じてノードを自由に追加/削除できます。

欠点は、配列とは異なり、最初にリンクのチェーンをたどらないと、リスト内からアイテムをフェッチする方法がないことです。また、リストが非常に大きくなると、これらすべてのクラス インスタンスと参照のオーバーヘッドが高くなり始めます。

パフォーマンスの面では、アイテムを追加するのに O(1) (つまり一定時間) かかります。O(N) (つまり、線形時間) を使用して、リストからアイテムを取得/削除します。また、リストがシングル/ダブルおよび/またはジャンプ リンクであるかどうかに応じて、顕著なメモリ オーバーヘッドが関係します。

ArrayLists、HashMaps などの他のデータ構造は、あなたのようなユースケースに対してより優れたパフォーマンスまたはメモリ特性を備えていますが、書き込み/管理がさらに複雑です。

手間をかけずに高レベルのデータ構造の優れた機能をすべて利用する最も簡単な方法は、既存の実装をラップして拡張することです。たとえば、ArrayList を内部的にデータ ストレージに使用するクラスを作成できます。上で示した方法を使用して、反復可能にすることもできます。ただし、ジェネリック型用に作成する代わりに、Aircraft データ型を使用するようにカスタマイズできます。

注: データ構造の書き方を学びたい場合は、アルゴリズム I クラスをオンラインで受講することをお勧めします (または別の方法で)。

于 2014-02-24T09:02:42.127 に答える
0

パブリック クラス ノード {

   public int item;
   public Node next;
   public Node tail;


   Node() {                 
      item = 0; 
      next = null; 
       tail = null ;    
   } 

   Add Node(node tail, node new) {

      tail.next = new;
        tail.tail = new
        new.tail =null

   }

};

私はそれを悪化させなかったことを願っています。幸運を。

飛行機クラスはノード クラスを拡張できます。Java の childfactory クラスを見てください。ノードクラスで使用するメソッドのタイプの例を示します。クラスを再考してください。おそらく、remove Airplane は remove node のようなノード クラスのメソッドになります。挿入または新規追加、削除、並べ替えなど、ノードで機能するものはすべて、ノード クラスに追加できます。その後、さらにクラスを追加するときに、このクラスを再利用できます。

http://docs.oracle.com/javase/tutorial/java/IandI/subclasses.html

于 2012-08-01T02:14:34.450 に答える
0

これは、回答者がリストを言うときに参照しているものへのリンクです。リストを説明するリンクhttp://www.algolist.net/Data_structures/Singly-linked_list/Traversalがあります。ただし、これがJavaの代表であるかどうかはわかりません。あなたが書いたコードは、並べ替えではなく、すべての飛行機をリストの最後に追加しているように見えます。したがって、リストはソートされません。temp.next = tail を作成すると、リスト内の最後の飛行機が null ではなくそれ自体を指すようになります。しかし、リスト内の平面の数を数えているnullをチェックしていません。次のノードを持つノードクラスがあるJavaの例を投稿しました。コードがそれを使用しているため、ノードテールも追加する必要があります。

于 2012-08-01T04:09:48.750 に答える