BohYoh.comトップページへ

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

戻る  

演習9-3の解答

 下図のように、先頭ノードへの参照head に加えて末尾ノードへの参照tail を導入すると、末尾ノードが容易に探索できるようになる。このようにして実現する線形リストクラスLinkedListT <E >を作成せよ。
 LinkedList <E >が提供するメソッドと同じメソッドをすべて作成すること。



// 演習9-3 // 線形リストクラス(末尾ノードへのポインタも管理) import java.util.Comparator; public class LinkedListT<E> {    //--- ノード ---//    class Node<E> {       private E data;         // データ       private Node<E> next;   // 後続ポインタ(後続ノードへの参照)       //--- コンストラクタ ---//       Node(E data, Node<E> next) {          this.data = data;          this.next = next;       }    }    private Node<E> head;      // 先頭ノード    private Node<E> tail;      // 末尾ノード    private Node<E> crnt;      // 着目ノード    //--- コンストラクタ ---//    public LinkedListT() {       head = tail = crnt = null;    }    //--- ノードを探索 ---//    public E search(E o, Comparator<? super E> c) {       Node<E> ptr = head;                     // 現在走査中のノード       while (ptr != null) {          if (c.compare(o, ptr.data== 0) {   // 探索成功             crnt = ptr;             return ptr.data;          }          ptr = ptr.next;                     // 後続ノードに着目       }       return null;                           // 探索失敗    }    //--- 先頭にノードを挿入 ---//    public void addFirst(E o) {       boolean empty = (tail == null);       Node<E> ptr = head;            // 挿入前の先頭ノード       head = crnt = new Node<E>(o, ptr);       if (emptytail = crnt;    }    //--- 末尾にノードを挿入 ---//    public void addLast(E o) {       if (head == null)            // リストが空であれば          addFirst(o);            // 先頭に挿入       else {          tail.next = crnt = new Node<E>(o, null);          tail = crnt;       }    }    //--- 先頭ノードを削除 ---//    public void removeFirst() {       if (head != null) {               // リストが空でなければ          head = crnt = head.next;          if (head == nulltail = null;       }    }    //--- 末尾ノードを削除 ---//    public void removeLast() {       if (head != null) {          if (head.next == null)         // ノードが一つだけであれば             removeFirst();               // 先頭ノードを削除          else {             Node<E> ptr = head;         // 走査中のノード             Node<E> pre = head;         // 走査中のノードの先行ノード             while (ptr.next != null) {                pre = ptr;                ptr = ptr.next;             }             pre.next = null;            // preは削除後の末尾ノード             tail = crnt = pre;          }       }    }    //--- ノードpを削除 ---//    public void remove(Node<E> p) {       if (head != null) {          if (p == head)            // pが先頭ノードであれば             removeFirst();         // 先頭ノードを削除          else if (p == tail)      // pが末尾ノードであれば             removeLast();         // 末尾ノードを削除          else {             Node<E> ptr = head;             while (ptr.next != p) {                ptr = ptr.next;                if (ptr == nullreturn;   // pはリスト上に存在しない             }             ptr.next = p.next;             crnt = ptr;          }       }    }    //--- 着目ノードを削除 ---//    public void removeCurrentNode() {       remove(crnt);    }    //--- 全ノードを削除 ---//    public void clear() {       while (head != null)         // 空になるまで          removeFirst();            // 先頭ノードを削除       crnt = null;    }    //--- 着目ノードを一つ後方に進める ---//    public boolean next() {       if (crnt == null || crnt.next == null)          return false;                  // 進めることはできなかった       crnt = crnt.next;       return true;    }    //--- 着目ノードを表示 ---//    public void printCurrentNode() {       if (crnt == null)          System.out.println("着目ノードはありません。");       else          System.out.println(crnt.data.toString());    }    //--- 全ノードを表示 ---//    public void dump() {       Node<E> ptr = head;       while (ptr != null) {          System.out.println(ptr.data.toString());          ptr = ptr.next;       }    }    //------------------------------ 演習9-1 ------------------------------//    //--- コンパレータcによって互いに等しいとみなせるノードをすべて削除 ---//    public void purge(Comparator<? super E> c) {       Node<E> ptr = head;       while (ptr != null) {          int count = 0;          Node<E> ptr2 = ptr;          Node<E> pre = ptr;          while (pre.next != null) {             ptr2 = pre.next;             if (c.compare(ptr.data, ptr2.data== 0) {                pre.next = ptr2.next;                count++;             else                pre = ptr2;          }          if (count == 0)             ptr = ptr.next;          else {             Node<E> temp = ptr;             remove(ptr);             ptr = temp.next;          }       }       crnt = head;          }    //------------------------------ 演習9-2 ------------------------------//    //--- 先頭からn個後ろのノードのデータへの参照を返却 ---//    public E retrieve(int n) {       Node<E> ptr = head;       while (n >= && ptr != null) {          if (n-- == 0) {             crnt = ptr;             return (ptr.data);            /* 探索成功 */          }          ptr = ptr.next;            /* 後続ノードに着目 */       }       return (null);          } }


// 演習9-3 // 線形リストクラスLinkedListT<E>の利用例 import java.util.Scanner; import java.util.Comparator; public class LinkedListTTester {    static Scanner stdIn = new Scanner(System.in);    //--- データ(会員番号+氏名) ---//    static class Data {       static final int NO   = 1;      // 番号を読み込むか?       static final int NAME = 2;      // 氏名を読み込むか?       private Integer no;            // 会員番号       private String  name;         // 氏名       //--- 文字列表現を返す ---//       public String toString() {          return "(" + no + ") " + name;       }       //--- データの読込み ---//       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);          }       }    }    //--- メニュー列挙型 ---//    public enum Menu {       ADD_FIRST(   "先頭にノードを挿入"),       ADD_LAST(   "末尾にノードを挿入"),       RMV_FIRST(   "先頭ノードを削除"),       RMV_LAST(   "末尾ノードを削除"),       RMV_CRNT(   "着目ノードを削除"),       CLEAR(      "全ノードを削除"),       SEARCH_NO(   "番号で探索"),       SEARCH_NAME("氏名で探索"),       NEXT(         "着目ノードを進める"),       PRINT_CRNT(   "着目ノードを表示"),       PURGE_NO(   "同一番号のノードを削除"),       PURGE_NAME(   "同一氏名のノードを削除"),       RETRIEVE(   "任意のノードを表示"),       DUMP(         "全ノードを表示"),       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();      // 読込み用データ       LinkedListT<Data> list = new LinkedListT<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 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 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);    } }


戻る