新・明解Javaで学ぶアルゴリズムとデータ構造
演習9-10の解答
線形リストLinkedList <E >に対する演習9-2（p.299）と同じ課題を、循環・重連結リストDblLinkedList <E >に対して行え。
|
//--- 先頭からn個後ろのノードのデータへの参照を返却 ---//
public E retrieve(int n) {
Node<E> ptr = head.next;
while (n >= 0 && 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) ? 1 : (d1.no < d2.no) ? -1 : 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) == 2 &&
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);
}
}
