再起呼び出し

階乗値を求めるプログラム 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;
}

線形リスト

Member.h は、テキストp.114に掲載。
Member.c は、テキストp.115に掲載。

LinkedList.h は、テキストp.337に掲載。

#ifndef ___LinkedList
#define ___LinkedList

#include "Member.h"

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

typedef struct {
	Node *head;
	Node *crnt;
} List;

void Initialize(List *list);

Node *Search(List *list, const Member *x, int compare(const Member *x, const Member *y));

void InsertFront(List *list, const Member *x);

void InsertRear(List *list, const Member *x);

void RemoveFront(List *list);

void RemoveRear(List *list);

void RemoveCurrent(List *list);

void Clear(List *list);

void PrintCurrent(const List *list);

void PrintLnCurrent(const List *list);

void Print(const List *list);

void Terminate(List *list);

#endif

LinkedList.c

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

static Node *AllocNode(void)
{
	return calloc(1, sizeof(Node));
}

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

void Initialize(List *list)
{
	list->head = NULL;
	list->crnt = NULL;
}

Node *Search(List *list, const Member *x, int compare(const Member *x, const Member *y))
{
	Node *ptr = list->head;
	while (ptr != NULL) {
		if (compare(&ptr->data, x) == 0) {
			list->crnt = ptr;
			return ptr;
		}
		ptr = ptr->next;
	}
	return NULL;
}

void InsertFront(List *list, const Member *x)
{
	Node *ptr = list->head;
	list->head = list->crnt = AllocNode();
	SetNode(list->head, x, ptr);
}

void InsertRear(List *list, const Member *x)
{
	if (list->head == NULL)
		InsertFront(list, x);
	else {
		Node *ptr = list->head;
		while (ptr->next != NULL)
			ptr = ptr->next;
		ptr->next = list->crnt = AllocNode();
		SetNode(ptr->next, x, NULL);
	}
}

void RemoveFront(List *list)
{
	if (list->head != NULL) {
		Node *ptr = list->head->next;
		free(list->head);
		list->head = list->crnt = ptr;
	}
}

void RemoveRear(List *list)
{
	if (list->head != NULL) {
		if ((list->head)->next == NULL)
			RemoveFront(list);
		else {
			Node *ptr = list->head;
			Node *pre;
			while (ptr->next != NULL) {
				pre = ptr;
				ptr = ptr->next;
			}
			pre->next = NULL;
			free(ptr);
			list->crnt = pre;
		}
	}
}

void RemoveCurrent(List *list)
{
	if (list->head != NULL) {
		if (list->crnt == list->head)
			RemoveFront(list);
		else {
			Node *ptr = list->head;
			while (ptr->next != list->crnt)
				ptr = ptr->next;
			ptr->next = list->crnt->next;
			free(list->crnt);
			list->crnt = ptr;
		}
	}
}

void Clear(List *list)
{
	while (list->head != NULL)
		RemoveFront(list);
	list->crnt = NULL;
}

void PrintCurrent(const List *list)
{
	if (list->crnt == NULL)
		printf("着目ノードはありません。");
	else 
		PrintMember(&list->crnt->data);
}

void PrintLnCurrent(const List *list)
{
	PrintCurrent(list);
	putchar('\n');
}

void Print(const List *list)
{
	if (list->head == NULL)
		puts("ノードがありません。");
	else {
		Node *ptr = list->head;
		while (ptr != NULL) {
			PrintLnMember(&ptr->data);
			ptr = ptr->next;
		}
	}
}

void Terminate(List *list)
{
	Clear(list);
}

LinkedListTest.c

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

typedef enum {
	TERMINATE, INS_FRONT, INS_REAR, RMV_FRONT, RMV_REAR, PRINT_CRNT,
	RMV_CRNT, SRCH_NO, SRCH_NAME, PRINT_ALL, CLEAR
} Menu;

Menu SelectMenu(void)
{
	int i, ch;
	char *mstring[] = {
		"先頭にノードを挿入", "末尾にノードを挿入", "先頭のノードを削除",
		"末尾のノードを削除", "着目ノードを表示", "着目ノードを削除",
		"番号で探索", "氏名で探索", "全ノードを表示",
		"全ノードを削除",
	};

	do {
		for (i = TERMINATE; i < CLEAR; i++) {
			printf("(%2d) %-18.18s  ", i+1, mstring[i]);
			if ((i % 3) == 2) putchar('\n');
		}
		printf("( 0) 終了 :");
		fflush(stdin);
		scanf_s("%d", &ch);
	} while (ch < TERMINATE || ch > CLEAR);
	return (Menu)ch;
}

int main(void)
{
	Menu menu;
	List list;

	Initialize(&list);
	do{
		Member x;
		switch(menu = SelectMenu()) {
		case INS_FRONT :
			x = ScanMember("先頭に挿入", MEMBER_NO | MEMBER_NAME);
			PrintMember(&x);
			InsertFront(&list, &x);
			break;
		case INS_REAR:
			x = ScanMember("末尾に挿入", MEMBER_NO | MEMBER_NAME);
			InsertRear(&list, &x);
			break;
		case RMV_FRONT:
			RemoveFront(&list);
			break;
		case PRINT_CRNT:
			PrintLnCurrent(&list);
			break;
		case RMV_REAR:
			RemoveRear(&list);
			break;
		case RMV_CRNT:
			RemoveCurrent(&list);
			break;
		case SRCH_NO:
			x = ScanMember("探索", MEMBER_NO);
			if (Search(&list, &x, MemberNoCmp) != NULL)
				PrintLnCurrent(&list);
			else
				puts("その番号のデータはありません。");
			break;
		case SRCH_NAME:
			x = ScanMember("探索", MEMBER_NAME);
			if (Search(&list, &x, MemberNameCmp) != NULL)
				PrintLnCurrent(&list);
			else
				puts("その名前のデータはありません。");
			break;
		case PRINT_ALL:
			Print(&list);
			break;
		}
	} while (menu != TERMINATE);
	Terminate(&list);
	return 0;
}

Member.c

scanf() を scanf_s()に変更しているため、30行目の呼び出し部分に文字数上限の引数を追加する。

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

int MemberNoCmp(const Member *x, const Member *y)
{
	return x->no < y->no ? -1 : x->no > y->no ? 1 : 0;
}

int MemberNameCmp(const Member *x, const Member *y)
{
	return strcmp(x->name, y->name);
}

void PrintMember(const Member *x)
{
	printf("%d %s", x->no, x->name);
}

void PrintLnMember(const Member *x) 
{
	printf("%d %s\n", x->no, x->name);
}

Member ScanMember(const char *message, int sw) 
{
	Member temp;
	printf("%sするデータを入力してください。\n", message);
	if (sw & MEMBER_NO)   { printf("番号:"); scanf_s("%d", &temp.no); }
	if (sw & MEMBER_NAME) { printf("氏名:"); scanf_s("%s", temp.name, 20); }
	return temp;
}

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

Visual Studio 2012でC言語を使うための設定箇所をまとめました。

プロジェクトプロパティを開き、C/C++の部分を展開し、以下の設定を行う。

コンパイル言語の選択は「Cコードとしてコンパイル」に設定する。

 

プリコンパイル済みヘッダーを「使用しない」に設定する。

 

SDLチェックを「いいえ」にする。

 

メニューバーから[ツール]-[オプション]を選択し、IntelliSenseの無効化を「True」に設定する。