アルゴリズムとデータ構造試験問題

提出用プロジェクトを作成する。
プロジェクト名は「s16171xx_名前」とする。

0.準備
プロジェクトを作成し、C言語で使用するための設定を行う。

参考:Visual Studio 2012 でC言語を使うための設定

1.メニューを表示するプログラムを作成する。
メニューは0~4の数字で入力する。
0で終了する。

参考:再起呼び出し

(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 1
(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 2
(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 3
(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 4
(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 0
続行するには何かキーを押してください . . .

2.メニューで1が指定されたら階乗を表示するプログラムが動作するようにする。

参考:再起呼び出し

(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 1
整数を入力せよ:3
3の階乗は6です。
(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 1
整数を入力せよ:4
4の階乗は24です。
(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 0
続行するには何かキーを押してください . . .

3.メニューで2が指定されたらハノイの塔のプログラムが動作するようにする。

参考:再起呼び出し

(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 2
ハノイの塔
円盤の枚数: 2
円盤[1]をA軸からB軸へ移動
円盤[2]をA軸からC軸へ移動
円盤[1]をB軸からC軸へ移動
(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 2
ハノイの塔
円盤の枚数: 3
円盤[1]をA軸からC軸へ移動
円盤[2]をA軸からB軸へ移動
円盤[1]をC軸からB軸へ移動
円盤[3]をA軸からC軸へ移動
円盤[1]をB軸からA軸へ移動
円盤[2]をB軸からC軸へ移動
円盤[1]をA軸からC軸へ移動
(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 0
続行するには何かキーを押してください . . .

4.メニューで3が指定されたらハッシュテーブルのプログラムが動作するようにする。

参考:ハッシュ法

(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 3
(1)追加 (2)削除 (3)探索 (4)全削除 (5)ダンプ (0)終了: 1
追加するデータを入力してください。
番号:1
氏名:aaa
(1)追加 (2)削除 (3)探索 (4)全削除 (5)ダンプ (0)終了: 1
追加するデータを入力してください。
番号:2
氏名:bbb
(1)追加 (2)削除 (3)探索 (4)全削除 (5)ダンプ (0)終了: 1
追加するデータを入力してください。
番号:14
氏名:ccc
(1)追加 (2)削除 (3)探索 (4)全削除 (5)ダンプ (0)終了: 5
00
01  → 14 (ccc) → 1 (aaa)
02  → 2 (bbb)
03
04
05
06
07
08
09
10
11
12
(1)追加 (2)削除 (3)探索 (4)全削除 (5)ダンプ (0)終了: 3
探索するデータを入力してください。
番号:1
探索に成功しました。
1 aaa
(1)追加 (2)削除 (3)探索 (4)全削除 (5)ダンプ (0)終了: 0
(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 0

5.メニューで4が指定されたら作成したリンクリストが動作するようにする。

参考:線形リスト

(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 4
( 1) 先頭にノードを挿入  ( 2) 末尾にノードを挿入  ( 3) 先頭のノードを削除
( 4) 末尾のノードを削除  ( 5) 着目ノードを表示    ( 6) 着目ノードを削除
( 7) 番号で探索          ( 8) 氏名で探索          ( 9) 全ノードを表示
(10) 全ノードを削除      ( 0) 終了 :1
先頭に挿入するデータを入力してください。
番号:1
氏名:aaa
( 1) 先頭にノードを挿入  ( 2) 末尾にノードを挿入  ( 3) 先頭のノードを削除
( 4) 末尾のノードを削除  ( 5) 着目ノードを表示    ( 6) 着目ノードを削除
( 7) 番号で探索          ( 8) 氏名で探索          ( 9) 全ノードを表示
(10) 全ノードを削除      ( 0) 終了 :2
末尾に挿入するデータを入力してください。
番号:2
氏名:bbb
( 1) 先頭にノードを挿入  ( 2) 末尾にノードを挿入  ( 3) 先頭のノードを削除
( 4) 末尾のノードを削除  ( 5) 着目ノードを表示    ( 6) 着目ノードを削除
( 7) 番号で探索          ( 8) 氏名で探索          ( 9) 全ノードを表示
(10) 全ノードを削除      ( 0) 終了 :2
末尾に挿入するデータを入力してください。
番号:3
氏名:ccc
( 1) 先頭にノードを挿入  ( 2) 末尾にノードを挿入  ( 3) 先頭のノードを削除
( 4) 末尾のノードを削除  ( 5) 着目ノードを表示    ( 6) 着目ノードを削除
( 7) 番号で探索          ( 8) 氏名で探索          ( 9) 全ノードを表示
(10) 全ノードを削除      ( 0) 終了 :9
1 aaa
2 bbb
3 ccc
( 1) 先頭にノードを挿入  ( 2) 末尾にノードを挿入  ( 3) 先頭のノードを削除
( 4) 末尾のノードを削除  ( 5) 着目ノードを表示    ( 6) 着目ノードを削除
( 7) 番号で探索          ( 8) 氏名で探索          ( 9) 全ノードを表示
(10) 全ノードを削除      ( 0) 終了 :7
探索するデータを入力してください。
番号:2
2 bbb
( 1) 先頭にノードを挿入  ( 2) 末尾にノードを挿入  ( 3) 先頭のノードを削除
( 4) 末尾のノードを削除  ( 5) 着目ノードを表示    ( 6) 着目ノードを削除
( 7) 番号で探索          ( 8) 氏名で探索          ( 9) 全ノードを表示
(10) 全ノードを削除      ( 0) 終了 :8
探索するデータを入力してください。
氏名:ccc
3 ccc
( 1) 先頭にノードを挿入  ( 2) 末尾にノードを挿入  ( 3) 先頭のノードを削除
( 4) 末尾のノードを削除  ( 5) 着目ノードを表示    ( 6) 着目ノードを削除
( 7) 番号で探索          ( 8) 氏名で探索          ( 9) 全ノードを表示
(10) 全ノードを削除      ( 0) 終了 :6
( 1) 先頭にノードを挿入  ( 2) 末尾にノードを挿入  ( 3) 先頭のノードを削除
( 4) 末尾のノードを削除  ( 5) 着目ノードを表示    ( 6) 着目ノードを削除
( 7) 番号で探索          ( 8) 氏名で探索          ( 9) 全ノードを表示
(10) 全ノードを削除      ( 0) 終了 :9
1 aaa
2 bbb
( 1) 先頭にノードを挿入  ( 2) 末尾にノードを挿入  ( 3) 先頭のノードを削除
( 4) 末尾のノードを削除  ( 5) 着目ノードを表示    ( 6) 着目ノードを削除
( 7) 番号で探索          ( 8) 氏名で探索          ( 9) 全ノードを表示
(10) 全ノードを削除      ( 0) 終了 :0
(1)階乗 (2)ハノイの塔 (3)ハッシュテーブル (4)リンクリスト (0)終了 : 0
続行するには何かキーを押してください . . .

提出は、提出用フォルダ(X:\提出フォルダ\2016\提出\アルゴリズム試験解答)にプロジェクトをそのままコピーする。

発表方法

プロジェクタが使えないので中央の画面で表示する。
提出用フォルダの下にある「アルゴリズム発表用プログラム」フォルダに学籍番号と名前のフォルダを作成し、そこに作成したプロジェクトをコピーする。
実行ファイルが、プロジェクトの直下の Debug フォルダ内にあるので、発表時はそのexeファイルを起動する。

X:\提出フォルダ\2016\提出\アルゴリズム発表用プログラム\s1617100_名前

発表内容

  1. 名前
  2. 作成したプログラム名
  3. プログラムの説明
  4. プログラムを実行してデモを行う
  5. 工夫した点、苦労した点、感想など

2048ゲームのサンプル

C++で書かれた2048ゲーム(http://vivi.dyndns.org/tech/games/2048.html)をC言語に書き換えたもの。

コンソールアプリで文字色を変更する処理は省略。

//----------------------------------------------------------------------
//		2048
//		Copyright (C) 2048 by N.Tsuda
//		License: CDDL 1.0 (http://opensource.org/licenses/CDDL-1.0)
//----------------------------------------------------------------------
#include <conio.h>		//	_getch
#include <time.h>			//	time
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define		WALL			-1			//	番人
#define		BOARD_WD		4			//	ボード幅
#define		BOARD_HT		4			//	ボード高さ
#define		CELL_WIDTH	8			//	セル表示幅

#define		KEY_ARROW		0xe0
#define		KEY_UP			0x48
#define		KEY_LEFT		0x4b
#define		KEY_RIGHT		0x4d
#define		KEY_DOWN		0x50

int	g_score = 0;
//int	g_nBlank;		//	空欄箇所数
int	g_board[BOARD_WD+2][BOARD_HT+2];		//	番人付きボード2次元配列


#define swap(a, b) (a += b, b = a - b, a -= b)


//	最上位ビットの位置(0~31)を返す
//		v が0ならば0, 1ならば1,2ならば2, 4ならば3, 8ならば4,... を返す
//		v がマイナスならば -1 を返す
//	int は符号付き32ビット整数と仮定する
int msbPos(int v)
{
	int n = 31;
	int mask;
	if( v == 0 ) return 0;
	if( v < 0 ) return -1;
	mask = 1 << (n-1);
	while( (v & mask) == 0 ) {
		mask >>= 1;
		--n;
	}
	return n;
}
//----------------------------------------------------------------------
void	init_board()
{
	int x, y;
	//g_nBlank = BOARD_WD * BOARD_HT;		//	空欄箇所数
	for (x = 0; x < BOARD_WD+2; ++x) {
		for (y = 0; y < BOARD_HT+2; ++y) {
			if( x == 0 || x == BOARD_WD + 1 ||
				y == 0 || y == BOARD_HT + 1 )
			{
				g_board[x][y] = WALL;
			} else {
				g_board[x][y] = 0;
			}
		}
	}
}
void print_line(int y, int printVal)
{
	int x, v;
	char str[256];
	for (x = 1; x <= BOARD_WD; ++x) {
		str[0] = '\0';
		v = g_board[x][y];
		if( printVal ) {
			if( !v ) {
				strcat_s(str, sizeof(str), "   .   ");
			} else {
				char ss[16];
				sprintf_s(ss, sizeof(ss), "%4d   ", v);
				strcat_s(str, sizeof(str), ss);
			}
		}
		printf("%s", str);
	}
	printf("\n");
}
void print_board()
{
	int y;
	printf("SCORE: %d\n\n", g_score);
	for (y = 1; y <= BOARD_HT; ++y) {
		print_line(y, 0);
		print_line(y, 0);
		print_line(y, 1);
		print_line(y, 0);
		print_line(y, 0);
	}
	printf("\n");
}
int nBlank()
{
	int x, y;
	int nBlank = 0;
	for (y = 1; y <= BOARD_HT; ++y) {
		for (x = 1; x <= BOARD_WD; ++x) {
			if( g_board[x][y] == 0 ) ++nBlank;
		}
	}
	return nBlank;
}
//	空き箇所のどこかに 2(75%) または 4(25%) を配置する
void put_number()
{
	int pos, v, x, y;
	int n = nBlank();
	if( n == 0 ) return;
	pos = rand() % n;
	v = (rand() % 100) < 75 ? 2 : 4;		//	75% の確率で2,25%の確率で4
	for (y = 1; y <= BOARD_HT; ++y) {
		for (x = 1; x <= BOARD_WD; ++x) {
			if( g_board[x][y] == 0 ) {		//	空欄を探す
				if( !pos ) {
					g_board[x][y] = v;
					return;
				}
				--pos;
			}
		}
	}
}
//	盤面左右反転
void hrev_board()
{
	int x, y;
	for (y = 1; y <= BOARD_HT; ++y) {
		for (x = 1; x <= BOARD_WD/2; ++x) {
			swap(g_board[x][y], g_board[BOARD_WD + 1 - x][y]);
		}
	}
}
//	x, y 反転
void swapxy_board()
{
	int x, y;
	for (y = 1; y < BOARD_HT; ++y) {
		for (x = y + 1; x <= BOARD_WD; ++x) {
			swap(g_board[x][y], g_board[y][x]);
		}
	}
}
int move_right()
{
	int y, src, dst, v;
	int moved = 0;
	for (y = 1; y <= BOARD_HT; ++y) {
		dst = BOARD_WD;
		for(src = BOARD_WD; src >= 1; --src) {
			v = g_board[src][y];
			if( v != 0 ) {
				if( src == BOARD_WD ) continue;		//	右端の場合
				if( g_board[dst][y] == 0 ) {		//	移動先が空欄
					if( dst != src ) {
						g_board[src][y] = 0;
						g_board[dst][y] = v;
						moved = 1;
					}
				} else if( g_board[dst][y] == v ) {		//	同じ数字
					g_score += v * 2;
					g_board[src][y] = 0;
					g_board[dst][y] += v;
					--dst;
					moved = 1;
				} else {
					--dst;
					if( dst != src ) {
						g_board[src][y] = 0;
						g_board[dst][y] = v;
						moved = 1;
					}
				}
			}
		}
	}
	return moved;
}
int move_left()
{
	int rc;
	hrev_board();
	rc = move_right();
	hrev_board();
	return rc;
}
int move_up()
{
	int rc;
	swapxy_board();
	hrev_board();
	rc = move_right();
	hrev_board();
	swapxy_board();
	return rc;
}
int move_down()
{
	int rc;
	swapxy_board();
	rc = move_right();
	swapxy_board();
	return rc;
}
int isMovable()
{
	int x, y;
	for (y = 1; y <= BOARD_HT; ++y) {
		for (x = 1; x <= BOARD_WD; ++x) {
			if( g_board[x][y] == 0 ||
				g_board[x][y] == g_board[x+1][y] ||
				g_board[x][y] == g_board[x][y+1] )
			{
				return 1;
			}
		}
	}
	return 0;
}
int g2048()
{
	int moved, c;
	moved = 0;
	srand((int)time(0));
	for (;;) {
		g_score = 0;
		init_board();
		put_number();
		for(moved;;) {
			if( moved )
				put_number();
			print_board();
			if( !isMovable() ) break;
			printf("Type ←↑↓→     ");
			c = _getch();
			if( c == 'q' ) break;
			if( c == KEY_ARROW ) {
				c = _getch();
				switch( c ) {
					case KEY_LEFT:
						moved = move_left();
						break;
					case KEY_RIGHT:
						moved = move_right();
						break;
					case KEY_UP:
						moved = move_up();
						break;
					case KEY_DOWN:
						moved = move_down();
						break;
				}
			}
		}
		printf("Try again ? [y/n]   ");
		for (;;) {
			c = _getch();
			if( c == KEY_ARROW )
				_getch();
			if( c == 'y' || c == 'Y' ||
				c == 'n' || c == 'N' )
			{
				break;
			}
		}
		if( c != 'y' && c != 'Y' ) break;
	}
	return 0;
}

タイプ練習のサンプル

タイプ練習のサンプル

プログラム内に辞書を用意。

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

char *dic[] = {
	"int",
	"short",
	"long",
	"char",
	"float",
	"double",
	"void",
	"unsigned",
	"hello",
	"world",
	"include",
	"time",
	"struct",
	"return",
	"printf",
	"sizeof",
	"while",
	"main",
	"static",
	"extern",
	"switch",
	"case",
	"continue",
	"volatile",
	"default",
	"goto"
};

int typing()
{
	int c;
	int p;
	int size;
	int i;
	time_t start;
	time_t end;
	char buff[256];

	size = sizeof(dic) / sizeof(dic[0]);
	printf("キーを押すとスタート\n");
	c = _getch();
	start = time(NULL);
	srand(start);
	for (i = 0; i < 10; i++) {
		p = rand() % size;
		printf("%s\n", dic[p]);
		while (1) {
			scanf("%s", buff);
			if (strcmp(buff, dic[p])) {
				puts("再入力");
			} else {
				break;
			}
		}
	}
	end = time(NULL);
	printf("%d秒", end - start);
	return 0;
}

オセロゲームのサンプル

オセロゲームのサンプル
人間 VS コンピュータ(AI)対局 7行プログラミング (C言語)

#include <stdio.h>

int put, turn, all, done, pass, count, cur, i;
// 盤状態:横9*縦10で、使用は8*8
// 0:無し 1:1player 2:2player 3:改行
// y*9+xというイメージ。0行目と9行目は番兵
int map[90] = {0};
// 盤を走査する場合、縦横斜め方向に向かうために足されるべき数
int dir[] = { -10, -9, -8, -1, 1, 8, 9, 10 };

// putに駒を置いた場合ひっくり返せる枚数をallに足す
void check() 
{
	if (map[put] == 0) {
		for (i = 0; i < 8; i++) {
			// dir[i]の方向の相手のコマの数を確認
			for (count = 0, cur = put+dir[i]; map[cur] == 3 - turn; cur += dir[i]) {
				count++;
			}
			if (count && map[cur] == turn) {
				// 1枚以上存在し、その上端が自分のコマだったら
				all += count;
				cur = put;
				if (done) {
					// doneがtrueの場合は、実際にひっくり返す
					do {
						map[cur] = turn, cur += dir[i];
					} while (map[cur] != turn);
				}
			}
		}
	}
}

// mapに対応するオセロ駒&改行
char *h = "・○●\n";

int main() {
	// 初期化
	for (i = 1, map[41] = map[49] = 2; i < 10; map[i++*9] = 3) {
		map[40] = map[50] = turn = pass = 1;
	}
	for (;; all = done = 0) { // ループのたびにallとdoneを初期化(セミコロンを1つ削除するため)
		// 盤の表示。今回のデータ構造だとこれで表示できる
		for (put = 9; put < 82; ++put) {
			check();
			printf("%.2s", &h[map[put]*2]);
		}
		if (all) {
			for (done = all = pass = put = 8; all == 8; check()) {
				// コマを置く(人は入力し、コンピュータは左上から順に)
				turn - 2 ? (scanf("%d %d", &put, &i), put+=i*9) : ++put;
			}
		} else if (pass) {
			// コマを置けないのでパス
			pass = 0;
			printf("pass");
		} else {
			break;
		}
		// 交代
		turn = 3 - turn;
	}
	return 0;
}

ゲームを作ってみる

C言語(またはC++)でコンソールゲームを作成する。
どのゲームを作るのかは、各個人で選択する。
ネット上にあるサンプルを参照しながら作成すること。
例えば、以下のゲームは比較的簡単に作成できる。

  • タイプ練習
  • トランプゲーム
  • オセロ
  • 2048
  • テトリス
  • マインスイーパー

発表:2月21日
提出期限:2月22日

C言語で作成する人は、プロジェクトに対して以下の設定を行うこと。
Visual Studio 2012 でC言語を使うための設定

C++で作成する場合は設定不要。

キー入力を待ってその後の動作を決定するプログラムの作成方法。
‘q’が入力されるまで、入力された文字を表示する。

#include <stdio.h>
#include <conio.h>

int main(int argc, char* argv[])
{
	int c;
	while (1) {
		c = _getch();
		if (c == 'q') break;
		putchar(c);
	}
	printf("終了");
	return 0;
}

再帰呼び出しの演習問題

演習5-6
テキストp.188のList5-6を、軸の名前を数値ではなく名称(A軸・B軸・C軸)で表示するようにプログラムを変更せよ。

元のプログラム

#include <stdio.h>
 
void move(int no, int x, int y) 
{
    if (no > 1)
        move(no - 1, x, 6 - x - y);
    printf("円盤[%d]を%d軸から%d軸へ移動\n", no, x, y);
    if (no > 1)
        move(no - 1, 6 - x - y, y);
}
 
int hmain(void) 
{
    int n;
    printf("ハノイの塔\n円盤の枚数: ");
    scanf("%d", &n);
    move(n, 1, 3);
    return 0;
}

「1軸・2軸・3軸」を「A軸・B軸・C軸」に変更するには?
①「1軸・2軸・3軸」に対応する軸の名前を、文字列の配列で用意する。
②printf()で%dで出力している部分を文字列用の%sに置き換え、
③引数では文字列配列を渡すようにする。

void move(int no, int x, int y) 
{
    char name[3][4] = { "A", "B", "C" };  // ①
    if (no > 1)
        move(no - 1, x, 6 - x - y);
    printf("円盤[%d]を%s軸から%s軸へ移動\n", no, name[x - 1], name[y - 1]); // ②・③
    if (no > 1)
        move(no - 1, 6 - x - y, y);
}

再起呼び出し

階乗値を求めるプログラム factorial.c

#include <stdio.h>

int factorial(int n) 
{
	if (n > 0)
		return n * factorial(n - 1);
	else 
		return 1;
}

int main(void)
{
	int x;

	printf("整数を入力せよ:");
	scanf_s("%d", &x);
	printf("%dの階乗は%dです。\n", x, factorial(x));
	return 0;
}

最大公約数を求めるプログラム euclid.c

#include <stdio.h>

int gcd(int x, int y) 
{
	if (y == 0)
		return x;
	else
		return gcd(y, x % y);
}

int main(void)
{
	int x, y;
	puts("二つの整数の最大公約数を求めます。");
	printf("整数を入力せよ:");
	scanf_s("%d", &x);
	printf("整数を入力せよ:");
	scanf_s("%d", &y);
	printf("最大公約数は%dです。\n", gcd(x, y));
	return 0;
}

ひとつのプロジェクト内に複数のmain関数を作るとエラーになる。

複数の機能を扱いたい場合は、前にリストやハッシュで作ったものと同様に、メニューを作って呼び分けるようにする。

RecursiveTest.c

#include <stdio.h>
#include "recursive.h"

typedef enum {
	TERMINATE, FACTORIAL, EUCLID
} Menu;

Menu SelectMenu(void)
{
	int ch;
	do {
		printf("(1)階乗 (2)最大公約数 (0)終了");
		scanf_s("%d", &ch);
	} while (ch < TERMINATE || ch > EUCLID);
	return (Menu)ch;
}

int main(void)
{
	Menu menu;
	do {
		switch (menu = SelectMenu()) {
		case FACTORIAL:
			fmain();
			break;
		case EUCLID:
			emain();
			break;
		}
	} while (menu != TERMINATE);
	return 0;
}

recursive.h

#ifndef __RECURSIVE
#define __RECURSIVE

int fmain(void);
int emain(void);

#endif

factorial.c の main() を fmain() に変更し、euclid.c の main() を emain() に変更する。

テキストの演習問題をやってみよう!

ネットで検索してもOK!
ただし、動作をきちんと自分で理解すること。

演習5-1
再帰関数呼び出しを用いずに、関数factorialを実現せよ。

演習5-2
再帰関数呼び出しを用いずに、関数euclidを実現せよ。

作成済みの再帰呼び出し関数は、関数名の最後に _r をつけてエラー回避する。
factorial() → factorial_r()
euclid() → euclid_r()

演習5-1解答例

int factorial(int n)
{
	int i;
	int result = 1;
	for (i = 1; i <= n; i++) {
		result = result * i;
	}
	return result;
}

演習5-2解答例

int gcd(int x, int y)
{
	int v = (x < y) ? x : y;
	int i;

	for (i = v; i > 0; i--) {
		//printf("x=%d y=%d v=%d xv=%d yv=%d\n", x, y, i, x % i, y % i);
		if ((x % i == 0) && (y % i == 0)) {
			return i;
		}
	}
	return 1;
}

再帰アルゴリズムの解析
RecursiveTest.cに追加

#include <stdio.h>
#include "recursive.h"

typedef enum {
	TERMINATE, FACTORIAL, EUCLID, ANALYZE
} Menu;

Menu SelectMenu(void)
{
	int ch;
	do {
		printf("(1)階乗 (2)最大公約数 (3)解析 (0)終了 : ");
		scanf_s("%d", &ch);
	} while (ch < TERMINATE || ch > ANALYZE);
	return (Menu)ch;
}

int main(void)
{
	Menu menu;
	do {
		switch (menu = SelectMenu()) {
		case FACTORIAL:
			fmain();
			break;
		case EUCLID:
			emain();
			break;
		case ANALYZE:
			amain();
			break;
		}
	} while (menu != TERMINATE);
	return 0;
}

recur.c

#include <stdio.h>

void recur(int n)
{
	if (n > 0) {
		recur(n - 1);
		printf("%d\n", n);
		recur(n - 2);
	}
}

int amain(void)
{
	int x;
	printf("整数を入力せよ: ");
	scanf("%d", &x);
	recur(x);
	return 0;
}

recursive.h

#ifndef __RECURSIVE
#define __RECURSIVE

int fmain(void);
int emain(void);
int amain(void);

#endif

ハノイの塔
hanoi.c

#include <stdio.h>

void move(int no, int x, int y) 
{
	if (no > 1)
		move(no - 1, x, 6 - x - y);
	printf("円盤[%d]を%d軸から%d軸へ移動\n", no, x, y);
	if (no > 1)
		move(no - 1, 6 - x - y, y);
}

int hmain(void) 
{
	int n;
	printf("ハノイの塔\n円盤の枚数: ");
	scanf("%d", &n);
	move(n, 1, 3);
	return 0;
}

RecursiveTest.c

#include <stdio.h>
#include "recursive.h"

typedef enum {
	TERMINATE, FACTORIAL, EUCLID, ANALYZE, HANOI
} Menu;

Menu SelectMenu(void)
{
	int ch;
	do {
		printf("(1)階乗 (2)最大公約数 (3)解析 (4)ハノイの塔 (0)終了 : ");
		scanf_s("%d", &ch);
	} while (ch < TERMINATE || ch > HANOI);
	return (Menu)ch;
}

int main(void)
{
	Menu menu;
	do {
		switch (menu = SelectMenu()) {
		case FACTORIAL:
			fmain();
			break;
		case EUCLID:
			emain();
			break;
		case ANALYZE:
			amain();
			break;
		case HANOI:
			hmain();
			break;
		}
	} while (menu != TERMINATE);
	return 0;
}

recursive.h

#ifndef __RECURSIVE
#define __RECURSIVE

int fmain(void);
int emain(void);
int amain(void);
int hmain(void);

#endif

ハッシュ法

テキストp.112のハッシュ法の実装を行う。

 

ChainHash.h

#ifndef __ChainHash
#define __ChainHash

#include "Member.h"

typedef struct __node {
	Member  data;
	struct __node *next;
} Node;

typedef struct {
	int size;
	Node **table;
} ChainHash;

int Initialize(ChainHash *h, int size);

Node *Search(const ChainHash *h, const Member *x);

int Add(ChainHash *h, const Member *x);

int Remove(ChainHash *h, const Member *x);

void Dump(const ChainHash *h);

void Clear(ChainHash *h);

void Terminate(ChainHash *h);

#endif

ChainHash.c

#include <stdio.h>
#include <stdlib.h>
#include "Member.h"
#include "ChainHash.h"

static int hash(int key, int size) 
{
	return key % size;
}

static void SetNode(Node *n, const Member *x, const Node *next)
{
	n->data = *x;
	n->next = next;
}

int Initialize(ChainHash *h, int size)
{
	int i;

	if((h->table = calloc(size, sizeof(Node *))) == NULL) {
		h->size = 0;
		return 0;
	}
	h->size = size;
	for (i = 0; i < size; i++)
		h->table[i] = NULL;
	return 1;
}

Node *Search(const ChainHash *h, const Member *x)
{
	int key = hash(x->no, h->size);
	Node *p = h->table[key];

	while (p != NULL) {
		if (p->data.no == x->no)
			return p;
		p = p->next;
	}
	return NULL;
}

int Add(ChainHash *h, const Member *x)
{
	int key = hash(x->no, h->size);
	Node *p = h->table[key];
	Node *temp;
	while (p != NULL) {
		if (p->data.no == x->no)
			return 1;
		p = p->next;
	}
	if ((temp = calloc(1, sizeof(Node))) == NULL)
		return 2;
	SetNode(temp, x, h->table[key]);
	h->table[key] = temp;
	return 0;
}

int Remove(ChainHash *h, const Member *x)
{
	int key = hash(x->no, h->size);
	Node *p = h->table[key];
	Node **pp = &h->table[key];
	while (p != NULL) {
		if (p->data.no == x->no) {
			*pp = p->next;
			free(p);
			return 0;
		}
		pp = &p->next;
		p = p->next;
	}
	return 1;
}

void Dump(const ChainHash *h)
{
	int i;
	for (i = 0; i < h->size; i++) {
		Node *p = h->table[i];
		printf("%02d  ", i);
		while (p != NULL) {
			printf("→ %d (%s) ", p->data.no, p->data.name);
			p = p->next;
		}
		putchar('\n');
	}
}

void Clear(ChainHash *h)
{
	int i;
	for (i = 0; i < h->size; i++) {
		Node *p = h->table[i];
		while (p != NULL) {
			Node *next = p->next;
			free(p);
			p = next;
		}
		h->table[i] = NULL;
	}
}
 
void Terminate(ChainHash *h)
{
	Clear(h);
	free(h->table);
	h->size = 0;
}

ChainHashTest.c

#include <stdio.h>
#include "Member.h"
#include "ChainHash.h"

typedef enum {
	TERMINATE, ADD, DELETE, SEARCH, CLEAR, DUMP
} Menu;

Menu SelectMenu(void)
{
	int ch;
	do {
		printf("(1)追加 (2)削除 (3)探索 (4)全削除 (5)ダンプ (0)終了: ");
		scanf_s("%d", &ch);
	} while (ch < TERMINATE || ch > DUMP);
	return (Menu)ch;
}

int main(void)
{
	Menu menu;
	ChainHash hash;
	Initialize(&hash, 13);
	do {
		int result;
		Member x;
		Node *temp;
		switch (menu = SelectMenu()) {
		case ADD:
			x = ScanMember("追加", MEMBER_NO | MEMBER_NAME);
			result = Add(&hash, &x);
			if (result)
				printf("エラー:追加に失敗しました(%s)。\n", (result == 1) ? "登録済み" : "メモリ不足");
			break;
		case DELETE:
			x = ScanMember("削除", MEMBER_NO);
			result = Remove(&hash, &x);
			if (result == 1)
				printf("エラー:その番号のデータは存在しません。\n");
			break;
		case SEARCH:
			x = ScanMember("探索", MEMBER_NO);
			temp = Search(&hash, &x);
			if (temp == NULL)
				printf("探索に失敗しました。\n");
			else { 
				printf("探索に成功しました。\n");
				PrintLnMember(&temp->data);
			}
			break;
		case CLEAR:
			Clear(&hash);
			break;
		case DUMP:
			Dump(&hash);
			break;
		}
	} while (menu != TERMINATE);
	Terminate(&hash);
	return 0;
}