BohYoh.comトップページへ

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

戻る  

演習9-8の解答

 循環リストを実現する配列カーソル版のクラスを作成せよ。線形リストクラスAryLinkedList <E >(List 9-3)が提供するメソッドと同じメソッドをすべて提供すること。

// 演習9-8 // 循環リストクラス(配列カーソル版) import java.util.Comparator; public class AryCircLinkedList<E> {    //--- ノード ---//    class Node<E> {       private E data;      // データ       private int next;      // リストの後続ポインタ(後続ノードのインデックス)       private int dnext;   // フリーリストの後続ポインタ(後続ノードのインデックス)       //--- dataとnextを設定 ---//       void set(E data, int next) {          this.data = data;          this.next = next;       }    }    private Node<E>[] n;      // リスト本体    private int size;         // リストの容量(最大データ数)    private int max;         // 利用中の末尾レコード    private int head;         // 先頭ノード    private int tail;         // 末尾ノード    private int crnt;         // 着目ノード    private int deleted;      // フリーリストの先頭ノード    private static final int NULL = -1;      // 後続ノードは存在しない/リストが満杯    //--- コンストラクタ ---//    public AryCircLinkedList(int capacity) {       head = tail = crnt = max = deleted = NULL;       try {          n = new Node[capacity];          for (int i = 0; i < capacity; i++)             n[inew Node<E>();          size = capacity;       }       catch (OutOfMemoryError e) {      // 配列の生成に失敗          size = 0;       }    }    //--- 次に挿入するレコードのインデックスを求める ---//    private int getInsertIndex() {       if (deleted == NULL) {            // 削除レコードは存在しない          if (max < size)             return ++max;               // 新しいレコードを利用          else             return NULL;               // 容量オーバ       else {          int rec = deleted;            // フリーリストから          deleted = n[rec].dnext;         // 先頭recを取り出す          return rec;       }    }    //--- レコードidxをフリーリストに登録 ---//    private void deleteIndex(int idx) {       if (deleted == NULL) {            // 削除レコードは存在しない          deleted = idx;                  // idxをフリーリストの          n[idx].dnext = NULL;            // 先頭に登録       else {          int rec = deleted;            // idxをフリーリストの          deleted = idx;                  // 先頭に挿入          n[idx].dnext = rec;       }    }    //--- ノードを探索 ---//    public E search(E o, Comparator<? super E> c) {       if (head != NULL) {          int ptr = head;               // 現在走査中のノード              do {             if (c.compare(o, n[ptr].data== 0) {                crnt = ptr;                return n[ptr].data;      // 探索成功             }             ptr = n[ptr].next;         // 後続ノードに着目          while (ptr != head);       }       return null;                     // 探索失敗    }    //--- 先頭にノードを挿入 ---//    public void addFirst(E o) {       if (head == NULL) {          int rec = getInsertIndex();          if (rec != NULL) {             head = tail = crnt = rec;             n[head].set(o, rec);          }       else {          int ptr = head;               // 挿入前の先頭ノード          int rec = getInsertIndex();          if (rec != NULL) {             head = crnt = rec;         // 第recレコードに挿入             n[head].set(o, ptr);             n[tail].next = head;          }       }    }    //--- 末尾にノードを挿入 ---//    public void addLast(E o) {       if (head == NULL)               // リストが空であれば          addFirst(o);               // 先頭に挿入       else {          int rec = getInsertIndex();          if (rec != NULL) {             n[tail].next = crnt = rec;             n[rec].set(o, head);             tail = rec;          }       }    }    //--- 先頭ノードを削除 ---//    public void removeFirst() {       if (head != NULL) {               // リストが空でなければ          if (head == tail) {             deleteIndex(head);             head = tail = crnt = NULL;          else {             int ptr = n[head].next;             deleteIndex(head);             head = crnt = ptr;             n[tail].next = head;          }       }    }    //--- 末尾ノードを削除 ---//    public void removeLast() {       if (head != NULL) {          if (head == tail)            // ノードが一つだけであれば             removeFirst();            // 先頭ノードを削除          else {             int ptr = head;         // 走査中のノード             int pre = head;         // 走査中のノードの先行ノード             while (n[ptr].next != head) {                pre = ptr;                ptr = n[ptr].next;             }             n[pre].next = head;      // preは削除後の末尾ノード             deleteIndex(ptr);             tail = crnt = pre;          }       }    }    //--- レコードpを削除 ---//    public void remove(int p) {       if (head != NULL) {          if (p == head)               // pが先頭ノードであれば             removeFirst();            // 先頭ノードを削除          else if (p == tail)         // pが末尾ノードであれば             removeLast();            // 末尾ノードを削除          else {             int ptr = head;             while (n[ptr].next != p) {                ptr = n[ptr].next;                if (ptr == headreturn;   // pはリスト上に存在しない             }             n[ptr].next = n[p].next;             deleteIndex(p);             crnt = ptr;          }       }    }    //--- 着目ノードを削除 ---//    public void removeCurrentNode() {       remove(crnt);    }    //--- 全ノードを削除 ---//    public void clear() {       while (head != NULL)         // 空になるまで          removeFirst();            // 先頭ノードを削除       crnt = NULL;    }    //--- 着目ノードを一つ後方に進める ---//    public boolean next() {       if (crnt == NULL || n[crnt].next == head)          return false;                  // 進めることはできなかった       crnt = n[crnt].next;       return true;    }    //--- 着目ノードを表示 ---//    public void printCurrentNode() {       if (crnt == NULL)          System.out.println("着目ノードはありません。");       else          System.out.println(n[crnt].data.toString());    }    //--- 全ノードを表示 ---//    public void dump() {       if (head != NULL) {          int ptr = head;              do {             System.out.println(n[ptr].data.toString());             ptr = n[ptr].next;          while (ptr != head);       }    }    //--- コンパレータcによって互いに等しいとみなせるノードをすべて削除 ---//    public void purge(Comparator<? super E> c) {       if (head == NULLreturn;       int ptr = head;       do {          int count = 0;          int ptr2 = ptr;          int pre = ptr;          while (n[pre].next != head) {             ptr2 = n[pre].next;             if (c.compare(n[ptr].data, n[ptr2].data== 0) {                remove(ptr2);                count++;             else                pre = ptr2;          }          if (count == 0)             ptr = n[ptr].next;          else {             int temp = n[ptr].next;             remove(ptr);             ptr = temp;          }       while (n[ptr].next != head);       crnt = head;    }    //--- 先頭からn個後ろのノードのデータへの参照を返却 ---//    public E retrieve(int n) {       if (head != NULL) {          int ptr = head;              while (n >= 0) {             if (n-- == 0) {                crnt = ptr;                return this.n[ptr].data;      // 探索成功             }             ptr = this.n[ptr].next;            // 後続ノードに着目             if (ptr == headbreak;          }       }       return (null);          } }


// 演習9-8 // 循環リストクラスCircLinkedList<E>の利用例 import java.util.Scanner; import java.util.Comparator; public class AryCircLinkedListTester {    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();      // 読込み用データ       AryCircLinkedList<Data> list = new AryCircLinkedList<Data>(100);      // リストを生成       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);    } }


戻る