BohYoh.comトップページへ

新・明解Javaで学ぶアルゴリズムとデータ構造

戻る  

演習9-10の解答

 線形リストLinkedList <E >に対する演習9-2(p.299)と同じ課題を、循環・重連結リストDblLinkedList <E >に対して行え。

   //--- 先頭からn個後ろのノードのデータへの参照を返却 ---//    public E retrieve(int n) {       Node<E> ptr = head.next;       while (n >= && ptr.next.next != head) {          if (n-- == 0) {             crnt = ptr;             return ptr.data;         // 探索成功          }          ptr = ptr.next;            // 後続ノードに着目       }       return (null);          } }


// 演習9-9~演習9-10 // 循環・重連結リストクラスDblLinkedList<E>の利用例 import java.util.Scanner; import java.util.Comparator; class DblLinkedListTester {    static Scanner stdIn = new Scanner(System.in);    //--- データ(会員番号+氏名) ---//    static class Data {       public static final int NO   = 1;   // 番号を読み込むか?       public static final int NAME = 2;   // 氏名を読み込むか?       Integer no;               // 会員番号       String  name;            // 氏名       //--- 文字列表現を返す ---//       public String toString() {          return "(" + no + ") " + name;       }       //--- データの読込み ---//       public void scanData(String guide, int sw) {          System.out.println(guide + "するデータを入力してください。");          if ((sw & NO== NO) {             System.out.print("番号:");             no = stdIn.nextInt();          }          if ((sw & NAME== NAME) {             System.out.print("名前:");             name = stdIn.next();          }       }       //--- 会員番号による順序付けを行うコンパレータ  ---//       public static final Comparator<Data> NO_ORDER =                                   new NoOrderComparator();       private static class NoOrderComparator implements Comparator<Data> {          public int compare(Data d1, Data d2) {             return (d1.no > d2.no?  (d1.no < d2.no? -0;          }       }       //--- 氏名による順序付けを行うコンパレータ  ---//       public static final Comparator<Data> NAME_ORDER =                                   new NameOrderComparator();       private static class NameOrderComparator implements Comparator<Data> {          public int compare(Data d1, Data d2) {             return d1.name.compareTo(d2.name);          }       }    }    //--- メニュー列挙型 ---//    enum Menu {       ADD_FIRST(  "先頭にノードを挿入"),       ADD_LAST(   "末尾にノードを挿入"),       ADD(        "着目ノードの直後に挿入"),       RMV_FIRST(  "先頭ノードを削除"),       RMV_LAST(   "末尾ノードを削除"),       RMV_CRNT(   "着目ノードを削除"),       CLEAR(      "全ノードを削除"),       SEARCH_NO(  "番号で探索"),       SEARCH_NAME("氏名で探索"),       NEXT(       "着目ノードを後方へ"),       PREV(       "着目ノードを前方へ"),       PRINT_CRNT"着目ノードを表示"),       DUMP(       "全ノードを表示"),       PURGE_NO(   "同一番号のノードを削除"),       PURGE_NAME(   "同一氏名のノードを削除"),       RETRIEVE(   "任意のノードを表示"),       TERMINATE(   "終了");       private final String message;         // 表示用文字列       static Menu MenuAt(int idx) {         // 序数がidxである列挙を返す          for (Menu m : Menu.values())             if (m.ordinal() == idx)                return m;          return null;       }       Menu(String string) {               // コンストラクタ          message = string;       }       String getMessage() {               // 表示用文字列を返す          return message;       }    }    //--- メニュー選択 ---//    static Menu SelectMenu() {       int key;       do {          for (Menu m : Menu.values()) {             System.out.printf("(%d) %s  ", m.ordinal(), m.getMessage());             if ((m.ordinal() 3== &&                  m.ordinal() != Menu.TERMINATE.ordinal())                System.out.println();          }          System.out.print(":");          key = stdIn.nextInt();       while (key < Menu.ADD_FIRST.ordinal() ||                                   key > Menu.TERMINATE.ordinal());       return Menu.MenuAt(key);    }    public static void main(String[] args) {       Menu menu;               // メニュー       Data data;               // 追加用データ参照       Data ptr;               // 探索用データ参照       Data temp = new Data();      // 読込み用データ       DblLinkedList<Data> list = new DblLinkedList<Data>()// リストを生成       do {          switch (menu = SelectMenu()) {           case ADD_FIRST :                  // 先頭にノードを挿入                data = new Data();                 data.scanData("先頭に挿入", Data.NO | Data.NAME);                list.addFirst(data);                 break;           case ADD_LAST :                  // 末尾にノードを挿入                data = new Data();                 data.scanData("末尾に挿入", Data.NO | Data.NAME);                 list.addLast(data);                 break;           case ADD :                        // 着目ノードの直後にノードを挿入                data = new Data();                 data.scanData("着目ノードの直後に挿入", Data.NO | Data.NAME);                 list.add(data);                 break;           case RMV_FIRST :                  // 先頭ノードを削除                list.removeFirst();                break;           case RMV_LAST :                  // 末尾ノードを削除                list.removeLast();                break;           case RMV_CRNT :                  // 着目ノードを削除                list.removeCurrentNode();                break;           case SEARCH_NO :                  // 会員番号で探索                 temp.scanData("探索", Data.NO);                ptr = list.search(temp, Data.NO_ORDER);                if (ptr == null)                   System.out.println("その番号のデータはありません。");                else                   System.out.println("探索成功:" + ptr);                 break;           case SEARCH_NAME :               // 氏名で探索                 temp.scanData("探索", Data.NAME);                ptr = list.search(temp, Data.NAME_ORDER);                if (ptr == null)                   System.out.println("その名前のデータはありません。");                else                   System.out.println("探索成功:" + ptr);                 break;           case NEXT :                     // 着目ノードを後方に進める                list.next();                 break;           case PREV :                     // 着目ノードを前方に進める                list.prev();                 break;           case PRINT_CRNT :               // 着目ノードのデータを表示                list.printCurrentNode();                 break;           case DUMP :                     // 全データをリスト順に表示                list.dump();                 break;           case CLEAR :                     // 全ノードを削除                list.clear();                 break;           case PURGE_NO :            // 同一番号のノードを削除                 list.purge(Data.NO_ORDER);                 break;           case PURGE_NAME :            // 同一氏名のノードを削除                 list.purge(Data.NAME_ORDER);                 break;           case RETRIEVE : {            // 任意のノードを表示                 System.out.print("先頭から何番目:");                 int no = stdIn.nextInt() 1;                 ptr = list.retrieve(no);                 if (ptr == null)                    System.out.println("データは存在しません。");                 else                    System.out.println("データは" + ptr.toString() "です。");              }          }       while (menu != Menu.TERMINATE);    } }


戻る