演習問題10解答例

問１　個人データの記述

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

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

問４　待ち行列

問５　ハッシュ表

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

［問１］名前（ 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;
}
		

［問２］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 */
/****************************/
#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;
}
		

［問４］最大待ち行列長を 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 */
/****************************/
#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;
}
		

［問６］英語の単語を入力し，それを 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;
}