演習問題10解答例

問１　個人データの記述

問１　個人データの記述^(Java)

問２　3 次元空間上の点の記述

問２　3 次元空間上の点の記述^(Java)

問３　クラスメンバーの出力

問３　クラスメンバーの出力^(Java)

問４　待ち行列

問４　待ち行列^(Java)

問５　ハッシュ表

問５　ハッシュ表^(Java)

問６　英文のリスト構造（ 2 進木）

問６　英文のリスト構造（ 2 進木）^(Java)

［問１］名前（ char ），給与（ int ），及び，年齢（ int ）をクラスで表現し，そこへ入出力を行うプログラムを書け．

/********************************/
/*     名前，給与，年齢         */
/*          coded by Y.Suganuma */
/********************************/
#include <iostream>
					// クラスTestの定義
class Test {
		char name[20];
		int kyuyo, nenrei;
	public:
						// 入力
		void input()
		{
			std::cout << "名前は？ ";
			std::cin >> name;
			std::cout << "給与は？ ";
			std::cin >> kyuyo;
			std::cout << "年齢は？ ";
			std::cin >> nenrei;
		}
						// 出力
		void print()
		{
			std::cout << "名前 " << name;
			std::cout << " 給与 " << kyuyo;
			std::cout << " 年齢 " << nenrei << std::endl;
		}
};
					// main
int main()
{
	Test x;

	x.input();
	x.print();

	return 0;
}
    

＋＋＋ Ｊａｖａの場合 ＋＋＋

/********************************/
/*     名前，給与，年齢         */
/*          coded by Y.Suganuma */
/********************************/
import java.io.*;

class Test {
	private String name;
	private int kyuyo, nenrei;
					// 入力
	void input() throws IOException
	{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		System.out.print("名前は？ ");
		name = in.readLine();
		System.out.print("給与は？ ");
		kyuyo = Integer.parseInt(in.readLine());
		System.out.print("年齢は？ ");
		nenrei = Integer.parseInt(in.readLine());
	}
					// 出力
	void print()
	{
		System.out.print("名前 " + name);
		System.out.print(" 給与 " + kyuyo);
		System.out.println(" 年齢 " + nenrei);
	}
					// main
	public static void main(String args[]) throws IOException
	{
		Test x = new Test();
		x.input();
		x.print();
	}
}
    

［問２］n （入力）個の 3 次元空間の点の座標を入力した後，原点からの平均距離を計算し，平均距離以上離れた点の個数を出力するプログラムを，クラスを使用して書け．

/********************************/
/*     ３次元空間の点           */
/*          coded by Y.Suganuma */
/********************************/
#include <iostream>
#include <math.h>
					// クラスTestの定義
class Test {
		double x, y, z;
	public:
		double r;
						// 点の座標の入力
		void input()
		{
			std::cout << "   点の座標は（x y z）？ ";
			std::cin >> x >> y >> z;
		}
						// 原点までの距離の計算
		void range()
		{
			r = sqrt(x*x + y*y + z*z);
		}
};
					// main
int main()
{
	double mean = 0.0;
	int i1, kosu = 0, n;
						// 入力
	std::cout << "点の数は？ ";
	std::cin >> n;

	Test *p = new Test [n];

	for (i1 = 0; i1 < n; i1++) {
		p[i1].input();
		p[i1].range();
		mean += p[i1].r;
	}
						// 点の個数
	mean /= n;

	for (i1 = 0; i1 < n; i1++) {
		if (p[i1].r >= mean)
			kosu++;
	}

	std::cout << "      平均距離 " << mean;
	std::cout << " 個数は " << kosu  << std::endl;

	return 0;
}
    

＋＋＋ Ｊａｖａの場合 ＋＋＋

/********************************/
/*     ３次元空間の点           */
/*          coded by Y.Suganuma */
/********************************/
import java.io.*;
					// クラスTestの定義
class Test {
	private double x, y, z;
	double r;
						// 点の座標の入力
	void input() throws IOException
	{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		System.out.print("   点の座標は（x）？ ");
		x = Double.parseDouble(in.readLine());
		System.out.print("   点の座標は（y）？ ");
		y = Double.parseDouble(in.readLine());
		System.out.print("   点の座標は（z）？ ");
		z = Double.parseDouble(in.readLine());
	}
						// 原点までの距離の計算
	void range()
	{
		r = Math.sqrt(x*x + y*y + z*z);
	}
					// main
	public static void main(String args[]) throws IOException
	{
		double mean = 0.0;
		int i1, kosu = 0, n;
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
						// 入力
		System.out.print("点の数は？ ");
		n = Integer.parseInt(in.readLine());

		Test p[] = new Test [n];   // C++との違いに注意してください
		for (i1 = 0; i1 < n; i1++)
			p[i1] = new Test ();

		for (i1 = 0; i1 < n; i1++) {
			p[i1].input();
			p[i1].range();
			mean += p[i1].r;
		}
						// 点の個数
		mean /= n;

		for (i1 = 0; i1 < n; i1++) {
			if (p[i1].r >= mean)
				kosu++;
		}

		System.out.print("      平均距離 " + mean);
		System.out.println(" 個数は " + kosu);
	}
}
    

［問３］名前，住所，電話番号をクラスを使用して記述し，名前を入力すると電話番号を出力するプログラムを書け．

/********************************/
/*     名前，住所，電話番号     */
/*          coded by Y.Suganuma */
/********************************/
#include <iostream>
#include <string.h>
					// クラスTestの定義
class Test {
		char name[20];
		char jusho[50];
		char tel[15];
	public:
						// 入力
		void input()
		{
			std::cout << "   名前は？ ";
			std::cin >> name;
			std::cout << "   住所は？ ";
			std::cin >> jusho;
			std::cout << "   電話番号は？ ";
			std::cin >> tel;
		}
						// 探索
		char *search(char *na)
		{
			int sw = strcmp(na, name);
			if (sw == 0)
				return tel;
			else
				return 0;
		}
};
					// main
int main()
{
	char *c, name[20];
	int i1, n, sw = 1;
/*
     入力（データベースの作成）
*/
	std::cout << "人数は？ ";
	std::cin >> n;

	Test *p = new Test [n];

	for (i1 = 0; i1 < n; i1++) {
		std::cout << std::endl;
		p[i1].input();
	}
/*
     探索
*/
	std::cout << "探索\n";

	while (sw > 0) {
		std::cout << "   名前は？（endで終了） ";
		std::cin >> name;
		sw = strcmp(name, "end");
		if (sw != 0) {
			for (i1 = 0; i1 < n && sw != 0; i1++) {
				c = p[i1].search(name);
				if (c != 0) {
					std::cout << "      電話番号は " << c << std::endl;
					sw = 0;
				}
			}
			if (sw != 0)
				std::cout << "      見つかりません\n";
			sw = 1;
		}
	}

	return 0;
}
    

＋＋＋ Ｊａｖａの場合 ＋＋＋

/********************************/
/*     名前，住所，電話番号     */
/*          coded by Y.Suganuma */
/********************************/
import java.io.*;
					// クラスTestの定義
class Test {
	private String name;
	private String jusho;
	private String tel;
						// 入力
	void input() throws IOException
	{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		System.out.print("   名前は？ ");
		name = in.readLine();
		System.out.print("   住所は？ ");
		jusho = in.readLine();
		System.out.print("   電話番号は？ ");
		tel = in.readLine();
	}
						// 探索
	String search(String na)
	{
		if (name.equals(na))
			return tel;
		else
			return null;
	}
					// main
	public static void main(String args[]) throws IOException
	{
		String c, name;
		int i1, n, sw = 1;
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	/*
	     入力（データベースの作成）
	*/
		System.out.print("人数は？ ");
		n = Integer.parseInt(in.readLine());

		Test p[] = new Test [n];

		for (i1 = 0; i1 < n; i1++) {
			System.out.println();
			p[i1] = new Test();
			p[i1].input();
		}
	/*
	     探索
	*/
		System.out.println("探索");

		while (sw > 0) {
			System.out.print("   名前は？（endで終了） ");
			name = in.readLine();
			if (!name.equals("end")) {
				for (i1 = 0; i1 < n && sw != 0; i1++) {
					c = p[i1].search(name);
					if (c != null) {
						System.out.println("      電話番号は " + c);
						sw = 0;
					}
				}
				if (sw != 0)
					System.out.println("      見つかりません");
				sw = 1;
			}
			else
				sw = 0;
		}
	}
}
    

［問４］最大待ち行列長を 10 として，待ち行列をクラスで表現するプログラムを書け．ただし，待ち行列は，配列に待ち行列に入っている要素−数字−を格納することによって表すものとする．メンバー関数としては，待ち行列に要素を入れる関数 put( int num )，待ち行列から要素を取り出す関数 get()，及び，待ち行列の状態を出力する関数 qprint() を用意せよ．

/********************************/
/*     待ち行列                 */
/*          coded by Y.Suganuma */
/********************************/
#include <iostream>
#include <stdlib.h>
					// クラスTestの定義
class Test {
		int *que;
		int size;
		int now;
	public:
						// コンストラクタ
		Test(int n = 10)
		{
			size = n;
			now  = 0;
			que  = new int [n];
		}
						// デストラクタ
		~Test(){delete [] que;};
						// 待ち行列に追加
		void put(int num)
		{
			now++;
			if (now > size) {
				std::cout << "***error  待ち行列オーバーフロー\n";
				exit(1);
			}
			que[now-1] = num;
		}
						// 待ち行列から取り除く
		int get()
		{
			int i1, num = 0;
			if (now > 0) {
				num = que[0];
				for (i1 = 1; i1 < now; i1++)
					que[i1-1] = que[i1];
				now--;
			}
			return num;
		}
						// 待ち行列の状態を出力
		void qprint()
		{
			int i1;
			std::cout << "   数 " << now;
			if (now > 0) {
				std::cout << " 内容";
				for (i1 = 0; i1 < now; i1++)
					std::cout << " " << que[i1];
			}
			std::cout << std::endl;
		}
};
					// main
int main()
{
	Test q(2);

	std::cout << "３を追加\n";
	q.put(3);
	q.qprint();
	std::cout << "１を追加\n";
	q.put(1);
	q.qprint();
	std::cout << "先頭を取り除く\n";
	q.get();
	q.qprint();
	std::cout << "２を追加\n";
	q.put(2);
	q.qprint();
	std::cout << "５を追加\n";
	q.put(5);
	q.qprint();

	return 0;
}
    

＋＋＋ Ｊａｖａの場合 ＋＋＋

/********************************/
/*     待ち行列                 */
/*          coded by Y.Suganuma */
/********************************/
import java.io.*;
					// クラスTestの定義
class Test {
	private int que[];
	private int size;
	private int now;
						// コンストラクタ
	Test(int n)
	{
		size = n;
		now  = 0;
		que  = new int [n];
	}
						// 待ち行列に追加
	void put(int num)
	{
		now++;
		if (now > size) {
			System.out.println("***error  待ち行列オーバーフロー");
			System.exit(1);
		}
		que[now-1] = num;
	}
						// 待ち行列から取り除く
	int get()
	{
		int i1, num = 0;
		if (now > 0) {
			num = que[0];
			for (i1 = 1; i1 < now; i1++)
				que[i1-1] = que[i1];
			now--;
		}
		return num;
	}
						// 待ち行列の状態を出力
	void qprint()
	{
		int i1;
		System.out.print("   数 " + now);
		if (now > 0) {
			System.out.print(" 内容");
			for (i1 = 0; i1 < now; i1++)
				System.out.print(" " + que[i1]);
		}
		System.out.println();
	}
						// main
	public static void main(String args[])
	{
		Test q = new Test (2);

		System.out.println("３を追加");
		q.put(3);
		q.qprint();
		System.out.println("１を追加");
		q.put(1);
		q.qprint();
		System.out.println("先頭を取り除く");
		q.get();
		q.qprint();
		System.out.println("２を追加");
		q.put(2);
		q.qprint();
		System.out.println("５を追加");
		q.put(5);
		q.qprint();
	}
}
    

［問５］レコードの格納と取り出しを文字列キーで行うハッシュ表のクラスを書け．その際，レコードの挿入，探索，及び，削除を行うメンバー関数も用意せよ．

/********************************/
/*     ハッシュテーブル         */
/*          coded by Y.Suganuma */
/********************************/
#include <iostream>
#include <string.h>
					// 前送りのクラス宣言
class Test;
					// クラスRecord
class Record {
	public:
		char *data;
						// コンストラクタ
		Record(char *str)
		{
			data = new char [strlen(str)+1];
			strcpy(data, str);
		}
						// デストラクタ
		~Record() {delete [] data;}
};
					// クラスClist（衝突リスト）
class Clist {
		Record *r;
		Clist *next;
	public:
						// コンストラクタ
	Clist () { next = 0; }
	friend Test;
};
					// クラスTest（ハッシュテーブル）
class Test {
		int size;                    // ハッシュテーブルの大きさ
		Clist **table;               // 衝突リストへのポインタ
						// ハッシュ関数
		int hash(char *s)
		{
			unsigned int hash = 0, g;
			int i1, len;

			len = strlen(s);
			for (i1 = 0; i1 < len; i1++ ) {
				hash = (hash << 4) + s[i1];   // 左に4ビットシフトし文字を加える
				g    = hash & 0xf0000000;   // ビット毎のＡＮＤ
				if (g != 0) {
					hash ^= g >> 24;   // 排他的論理和
					hash ^= g;
				}
			}

			return hash % size;
		}

	public:
						// コンストラクタ
		Test(int sz)
		{
			int i1;
			size  = sz;
			table = new Clist * [size];
			for (i1 = 0; i1 < size; i1++)
				table[i1] = 0;
		}
						// デストラクタ
		~Test()
		{
			int i1;
			Clist *p, *q;
			for (i1 = 0; i1 < size; i1++) {
				p = table[i1];
				while (p != 0) {
					q = p;
					p = p->next;
					delete q;
				}
			}
			delete [] table;
		}
						// レコードの探索
						//   成功：レコードへのポインタ，失敗：０
		Record *search(char *str)
		{
			Clist *p;
			for (p = table[hash(str)]; p != 0; p = p->next) {
				if (strcmp(str, (p->r)->data) == 0)
					return p->r;
			}
			return 0;
		}
						// レコードの追加
						//   成功：レコードへのポインタ，失敗：０
		Record *add(Record *rec)
		{
			if (search(rec->data) != 0)     // 既に存在
				return 0;
			else {                            // 付加
				int i    = hash(rec->data);
				Clist *p = new Clist;
				p->r     = rec;
				p->next  = table[i];
				table[i] = p;
				return rec;
			}
		}
						// レコードの削除
						//   成功：レコードへのポインタ，失敗：０
		Record *remove(char *str)
		{
			int i    = hash(str);
			Clist *p = table[i];
			Clist *q = 0;

			while ((p != 0) && (strcmp((p->r)->data, str) != 0)) {
				q = p;
				p = p->next;
			}

			if (p != 0) {
				if (q != 0)
					q->next = p->next;
				else
					table[i] = p->next;
				Record *r = p->r;
				delete p;
				return r;
			}
			else
				return 0;
		}
};
					// main
int main()
{
	Test H(100);
	Record rec1("test1"), rec2("test2"), *p1, *p2;
						// データ "test1", "test2" の追加
	p1 = H.add(&rec1);
	p2 = H.add(&rec2);
	if (p1 != 0)
		std::cout << "データ " << p1->data << " の追加\n";
	if (p2 != 0)
		std::cout << "データ " << p2->data << " の追加\n";
						// データ "test1" の削除
	std::cout << "データ test1 の削除\n";
	p1 = H.remove("test1");
						// データの検索
	std::cout << "データ test1 の検索\n";
	p1 = H.search("test1");
	if (p1 == 0)
		std::cout << "   データ test1 は見つかりません\n";
	std::cout << "データ test2 の検索\n";
	p2 = H.search("test2");
	if (p2 != 0)
		std::cout << "   データ " << p2->data << " は見つかりました\n";

	return 0;
}
    

＋＋＋ Ｊａｖａの場合 ＋＋＋

/********************************/
/*     ハッシュテーブル         */
/*          coded by Y.Suganuma */
/********************************/
import java.io.*;
					// クラスRecord
class Record {
	String data;
						// コンストラクタ
	Record(String str)
	{
		data = new String (str);
	}
}
					// クラスClist（衝突リスト）
class Clist {
	Record r;
	Clist next;
						// コンストラクタ
	Clist () { next = null; }
}
					// クラスTest（ハッシュテーブル）
class Test {
	private int size;                    // ハッシュテーブルの大きさ
	private Clist table[];               // 衝突リスト
						// ハッシュ関数
	int hash(String s) throws UnsupportedEncodingException
	{
		int hash = 0, g;
		int i1, len;
		byte bs[] = s.getBytes("ASCII");

		len = bs.length;
		for (i1 = 0; i1 < len; i1++ ) {
			hash = (hash << 4) + bs[i1];   // 左に4ビットシフトし文字を加える
			g    = hash & 0xf0000000;   // ビット毎のＡＮＤ
			if (g != 0) {
				hash ^= g >> 24;   // 排他的論理和
				hash ^= g;
			}
		}

		return hash % size;
	}
						// コンストラクタ
	Test(int sz)
	{
		int i1;
		size  = sz;
		table = new Clist [size];
		for (i1 = 0; i1 < size; i1++)
			table[i1] = null;
	}
						// レコードの探索
						//   成功：レコードへのポインタ，失敗：０
	Record search(String str) throws UnsupportedEncodingException
	{
		Clist p;
		for (p = table[hash(str)]; p != null; p = p.next) {
			if (str.equals(p.r.data))
				return p.r;
		}
		return null;
	}
						// レコードの追加
						//   成功：レコードへのポインタ，失敗：０
	Record add(Record rec) throws UnsupportedEncodingException
	{
		if (search(rec.data) != null)     // 既に存在
			return null;
		else {                            // 付加
			int i    = hash(rec.data);
			Clist p  = new Clist ();
			p.r      = rec;
			p.next   = table[i];
			table[i] = p;
			return rec;
		}
	}
						// レコードの削除
						//   成功：レコードへのポインタ，失敗：０
	Record remove(String str) throws UnsupportedEncodingException
	{
		int i    = hash(str);
		Clist p = table[i];
		Clist q = null;

		while ((p != null) && !str.equals(p.r.data)) {
			q = p;
			p = p.next;
		}

		if (p != null) {
			if (q != null)
				q.next = p.next;
			else
				table[i] = p.next;
			Record r = new Record (p.r.data);
			return r;
		}
		else
			return null;
	}
						// main
	public static void main(String args[]) throws UnsupportedEncodingException
	{
		Test H = new Test (100);
		Record rec1 = new Record("test1");
		Record rec2 = new Record("test2");
							// データ "test1", "test2" の追加
		Record p1 = H.add(rec1);
		Record p2 = H.add(rec2);
		if (p1 != null)
			System.out.println("データ " + p1.data + " の追加");
		if (p2 != null)
			System.out.println("データ " + p2.data + " の追加");
							// データ "test1" の削除
		System.out.println("データ test1 の削除");
		p1 = H.remove("test1");
							// データの検索
		System.out.println("データ test1 の検索");
		p1 = H.search("test1");
		if (p1 == null)
			System.out.println("   データ test1 は見つかりません");
		System.out.println("データ test2 の検索");
		p2 = H.search("test2");
		if (p2 != null)
			System.out.println("   データ " + p2.data + " は見つかりました");
	}
}
    

　　上のプログラムは，String からハッシュコードを生成する String クラスのメソッド hashCode を使用して以下のように書いても構いません．ただし，hashCode によるハッシュコードの生成方法は以下の通りです．

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

/********************************/
/*     ハッシュテーブル         */
/*          coded by Y.Suganuma */
/********************************/
import java.io.*;
					// クラスRecord
class Record {
	String data;
						// コンストラクタ
	Record(String str)
	{
		data = new String (str);
	}
}
					// クラスClist（衝突リスト）
class Clist {
	Record r;
	Clist next;
						// コンストラクタ
	Clist () { next = null; }
}
					// クラスTest（ハッシュテーブル）
class Test {
	private int size;                    // ハッシュテーブルの大きさ
	private Clist table[];               // 衝突リスト
						// ハッシュ関数
	int hash(String s)
	{
		return s.hashCode() % size;
	}
						// コンストラクタ
	Test(int sz)
	{
		int i1;
		size  = sz;
		table = new Clist [size];
		for (i1 = 0; i1 < size; i1++)
			table[i1] = null;
	}
						// レコードの探索
						//   成功：レコードへのポインタ，失敗：０
	Record search(String str)
	{
		Clist p;
		for (p = table[hash(str)]; p != null; p = p.next) {
			if (str.equals(p.r.data))
				return p.r;
		}
		return null;
	}
						// レコードの追加
						//   成功：レコードへのポインタ，失敗：０
	Record add(Record rec)
	{
		if (search(rec.data) != null)     // 既に存在
			return null;
		else {                            // 付加
			int i    = hash(rec.data);
			Clist p  = new Clist ();
			p.r      = rec;
			p.next   = table[i];
			table[i] = p;
			return rec;
		}
	}
						// レコードの削除
						//   成功：レコードへのポインタ，失敗：０
	Record remove(String str)
	{
		int i    = hash(str);
		Clist p = table[i];
		Clist q = null;

		while ((p != null) && !str.equals(p.r.data)) {
			q = p;
			p = p.next;
		}

		if (p != null) {
			if (q != null)
				q.next = p.next;
			else
				table[i] = p.next;
			Record r = new Record (p.r.data);
			return r;
		}
		else
			return null;
	}
						// main
	public static void main(String args[])
	{
		Test H = new Test (100);
		Record rec1 = new Record("test1");
		Record rec2 = new Record("test2");
							// データ "test1", "test2" の追加
		Record p1 = H.add(rec1);
		Record p2 = H.add(rec2);
		if (p1 != null)
			System.out.println("データ " + p1.data + " の追加");
		if (p2 != null)
			System.out.println("データ " + p2.data + " の追加");
							// データ "test1" の削除
		System.out.println("データ test1 の削除");
		p1 = H.remove("test1");
							// データの検索
		System.out.println("データ test1 の検索");
		p1 = H.search("test1");
		if (p1 == null)
			System.out.println("   データ test1 は見つかりません");
		System.out.println("データ test2 の検索");
		p2 = H.search("test2");
		if (p2 != null)
			System.out.println("   データ " + p2.data + " は見つかりました");
	}
}
    

［問６］英語の単語を入力し，それを 2 進木として記憶するプログラムをクラスを利用して書け．ただし，新しい単語が入力されたとき，記憶されている単語よりアルファベット順で前にあるなら左，そうでなければ右の枝をたどるものとする．例えば，11 個の単語が，「 network parameters are optimized from empirical data and the optimal number 」 という順に入力された場合は以下のようになる．

/********************************/
/*     リスト処理               */
/*          coded by Y.Suganuma */
/********************************/
#include <iostream>
#include <string.h>

/**************/
/* クラスTest */
/**************/
class Test {
		char *name;
		Test *mae;
		Test *ato;
	public:
		static Test *head;

		/******************/
		/* コンストラクタ */
		/******************/
		Test() { head = 0; };

		Test(char *tango)
		{
			int len;
			len  = strlen(tango) + 1;
			name = new char [len];
			mae  = 0;
			ato  = 0;
			strcpy(name, tango);
		}

		/***************************************************************/
		/* 単語の探索                                                  */
		/*   tango : 入力された単語                                    */
		/*   base : 単語が入っているオブジェクトのアドレスへのポインタ */
		/*   same : =0 : 単語を追加                                    */
		/*          =1 : 既に同じ単語がリスト上にある                  */
		/*   return : 追加するオブジェクトのアドレスに対するポインタ   */
		/***************************************************************/
		Test **search(char *tango, Test **base, int *same)
		{
			Test **add_a;
			int sw;

			*same = 0;
		/*
		     最初の単語
		*/
			if (*base == 0)
				return base;
		/*
		     単語の比較
		*/
			sw = strcmp(tango, (*base)->name);
					// 同じ単語
			if (sw == 0) {
				*same = 1;
				return base;
			}
					// 異なる単語
			else {
				if (sw < 0)
					add_a = search(tango, &((*base)->mae), same);   // 左
				else
					add_a = search(tango, &((*base)->ato), same);   // 右
				return add_a;
			}
		}

		/***************************************************************/
		/* 単語の追加                                                  */
		/*   tango : 入力された単語                                    */
		/*   base : 単語が入っているオブジェクトのアドレスへのポインタ */
		/***************************************************************/
		void add(char *tango, Test **base)
		{
			*base = new Test(tango);
		}

		/*************************************************************/
		/* 単語の出力                                                */
		/*   base : 対象とする単語が入っているオブジェクトのアドレス */
		/*   dep : リストの深さ                                      */
		/*************************************************************/
		void output(Test *base, int dep)
		{
			int i1;
			if (base != 0) {
				for (i1 = 0; i1 < dep; i1++)
					std::cout << "   ";
				std::cout << base->name << std::endl;
				dep++;
				output(base->mae, dep);
				output(base->ato, dep);
			}
		}
};
					// static変数の定義
Test *Test::head;

/********/
/* main */
/********/
int main()
{
	Test tree, **add_a;
	int sw = 1, same;
	char tango[50];
/*
     単語の入力とリストの作成
*/
	while (sw != 0) {
					// 単語入力
		std::cout << "単語を入力して下さい（終了はピリオド） ";
		std::cin >> tango;
					// 終了判定
		sw = strcmp(tango, ".");
					// リスト作成
		if (sw != 0) {
			add_a = tree.search(tango, &(Test::head), &same);   // 探索
			if (same == 0)
				tree.add(tango, add_a);   // 追加
		}
	}
/*
     リストの出力
*/
	tree.output(Test::head, 0);

	return 0;
}
    

＋＋＋ Ｊａｖａの場合 ＋＋＋

/********************************/
/*     リスト処理               */
/*          coded by Y.Suganuma */
/********************************/
import java.io.*;

/**************/
/* クラスTest */
/**************/
class Test {
	private String name;
	private Test mae;
	private Test ato;
	static Test head = null;

	/******************/
	/* コンストラクタ */
	/******************/
	Test()
	{
		mae  = null;
		ato  = null;
	}

	/**********************************************/
	/* 単語の探索                                 */
	/*   tango : 入力された単語                   */
	/*   base : 単語が入っているオブジェクト      */
	/*   same : =0 : 単語を追加                   */
	/*          =1 : 既に同じ単語がリスト上にある */
	/*   return : 追加するオブジェクト            */
	/**********************************************/
	Test search(String tango, Test base, int same[])
	{
		Test add_a;
		int sw;
		same[0] = 0;
	/*
	     単語の比較
	*/
		sw = tango.compareTo(base.name);
					// 同じ単語
		if (sw == 0) {
			same[0] = 1;
			return base;
		}
					// 異なる単語
		else {
			if (sw < 0) {   // 左
				if (base.mae == null) {
					add_a    = new Test();
					base.mae = add_a;
				}
				else
					add_a = search(tango, base.mae, same);
			}
			else {   // 右
				if (base.ato == null) {
					add_a    = new Test();
					base.ato = add_a;
				}
				else
					add_a = search(tango, base.ato, same);
			}
			return add_a;
		}
	}

	/*****************************************/
	/* 単語の追加                            */
	/*   tango : 入力された単語              */
	/*   base : 単語が入っているオブジェクト */
	/*****************************************/
	void add(String tango, Test base)
	{
		base.name = new String (tango);
	}

	/***************************************************/
	/* 単語の出力                                      */
	/*   base : 対象とする単語が入っているオブジェクト */
	/*   dep : リストの深さ                            */
	/***************************************************/
	void output(Test base, int dep)
	{
		int i1;
		if (base != null) {
			for (i1 = 0; i1 < dep; i1++)
				System.out.print("   ");
			System.out.println(base.name);
			dep++;
			output(base.mae, dep);
			output(base.ato, dep);
		}
	}

	/********/
	/* main */
	/********/
	public static void main(String args[]) throws IOException
	{
		Test tree = new Test ();
		Test add_a;
		int sw = 1;
		int same[] = new int [1];
		String tango;
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	/*
	     単語の入力とリストの作成
	*/
		while (sw != 0) {
						// 単語入力
			System.out.print("単語を入力して下さい（終了はピリオド） ");
			tango = in.readLine();
						// 終了判定とリスト作成
			if (!tango.equals(".")) {
				if (head == null) {   // 最初の単語
					tree.add(tango, tree);   // 追加
					head = tree;
				}
				else {
					add_a = tree.search(tango, head, same);   // 探索
					if (same[0] == 0)
						tree.add(tango, add_a);   // 追加
				}
			}
			else
				sw = 0;
		}
	/*
	     リストの出力
	*/
		tree.output(head, 0);
	}
}