新・明解Javaで学ぶアルゴリズムとデータ構造
演習9-7の解答
循環リストを実現するクラスを作成せよ。線形リストクラスLinkedList <E >（List 9-1）が提供するメソッドと同じメソッドをすべて提供すること。
|
// 演習9-7
// 線形リストクラス
import java.util.Comparator;
public class CircLinkedList<E> {
//--- ノード ---//
class Node<E> {
E data; // データ
Node<E> next; // 後続ポインタ（後続ノードへの参照）
//--- コンストラクタ ---//
Node(E data) {
this.data = data;
this.next = this;
}
//--- コンストラクタ ---//
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 CircLinkedList() {
head = tail = crnt = null;
}
//--- ノードを探索 ---//
public E search(E o, Comparator<? super E> c) {
if (head != null) {
Node<E> ptr = head; // 現在走査中のノード
do {
if (c.compare(o, ptr.data) == 0) { // 探索成功
crnt = ptr;
return ptr.data;
}
ptr = ptr.next; // 後続ノードに着目
} while (ptr != head);
}
return null; // 探索失敗
}
//--- 先頭にノードを挿入 ---//
public void addFirst(E o) {
if (head == null)
head = tail = crnt = new Node<E>(o);
else {
Node<E> ptr = head;
head = crnt = new Node<E>(o, ptr);
tail.next = head;
}
}
//--- 末尾にノードを挿入 ---//
public void addLast(E o) {
if (head == null) // リストが空であれば
addFirst(o); // 先頭に挿入
else {
Node<E> ptr = tail;
ptr.next = crnt = tail = new Node<E>(o, head);
}
}
//--- 先頭ノードを削除 ---//
public void removeFirst() {
if (head != null) { // リストが空でなければ
if (head == tail)
head = tail = crnt = null;
else {
Node<E> ptr = head.next;
head = crnt = ptr;
tail.next = head;
}
}
}
//--- 末尾ノードを削除 ---//
public void removeLast() {
if (head != null) {
if (head == tail) // ノードが一つだけであれば
removeFirst(); // 先頭ノードを削除
else {
Node<E> ptr = head; // 走査中のノード
Node<E> pre = head; // 走査中のノードの先行ノード
while (ptr.next != head) {
pre = ptr;
ptr = ptr.next;
}
pre.next = head; // 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 == head) return; // 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 == head)
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() {
if (head != null) {
Node<E> ptr = head;
do {
System.out.println(ptr.data.toString());
ptr = ptr.next;
} while (ptr != head);
}
}
//--- コンパレータcによって互いに等しいとみなせるノードをすべて削除 ---//
public void purge(Comparator<? super E> c) {
if (head == null) return;
Node<E> ptr = head;
do {
int count = 0;
Node<E> ptr2 = ptr;
Node<E> pre = ptr;
while (pre.next != head) {
ptr2 = pre.next;
if (c.compare(ptr.data, ptr2.data) == 0) {
remove(ptr2);
count++;
} else
pre = ptr2;
}
if (count == 0)
ptr = ptr.next;
else {
Node<E> temp = ptr;
remove(ptr);
ptr = temp.next;
}
} while (ptr.next != head);
crnt = head;
}
//--- 先頭からn個後ろのノードのデータへの参照を返却 ---//
public E retrieve(int n) {
if (head != null) {
Node<E> ptr = head;
while (n >= 0) {
if (n-- == 0) {
crnt = ptr;
return (ptr.data); // 探索成功
}
ptr = ptr.next; // 後続ノードに着目
if (ptr == head) break;
}
}
return (null);
}
}
// 演習9-7
// 循環リストクラスCircLinkedList<E>の利用例
import java.util.Scanner;
import java.util.Comparator;
public class CircLinkedListTester {
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) ? 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);
}
}
}
//--- メニュー列挙型 ---//
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) == 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(); // 読込み用データ
CircLinkedList<Data> list = new CircLinkedList<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);
}
}
