開発環境
- OS X Mavericks - Apple(OS)
- Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
- C (プログラミング言語)
- Clang (コンパイラ)
C実践プログラミング 第3版 (Steve Oualline (著)、 望月 康司 (監訳) (翻訳)、谷口 功 (翻訳)、オライリー・ジャパン)のⅢ部(高度なプログラミング概念)の18章(モジュールプログラミング)、18-14(プログラミング実習)、実習18-3.を解いてみる。
その他参考書籍
- プログラミング言語C 第2版 ANSI規格準拠 (B.W. カーニハン D.M. リッチー (著)、 石田 晴久 (翻訳)、共立出版)
- プログラミング言語Cアンサー・ブック 第2版 (クロビス・L．トンド、スコット・E．ギンペル(著)、矢吹 道郎(翻訳))
18-14(プログラミング実習)、実習18-3.
コード
symbol_table.h
extern struct node *symbol_table; extern void enter(char *name); extern int lookup(char *name); extern void delete(char *name); extern void print_symbol_table();
コード
symbol_table.c
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
struct node{
struct node *left;
struct node *right;
char *word;
};
struct node *symbol_table = NULL;
static void memory_error(void)
{
fprintf(stderr, "Error:Out of memory\n");
exit (8);
}
static char *save_string(char *string)
{
char *new_string;
new_string = malloc((unsigned) (strlen(string) + 1));
if(new_string == NULL){
memory_error();
}
strcpy(new_string, string);
return (new_string);
}
static void _enter(struct node **node, char *word)
{
int result;
char *save_string(char *);
if((*node) == NULL){
(*node) = malloc(sizeof(struct node));
if((*node) == NULL){
memory_error();
}
(*node)->left = NULL;
(*node)->right = NULL;
(*node)->word = save_string(word);
return;
}
result = strcmp((*node)->word, word);
if(result == 0){
return;
}
if(result < 0){
_enter(&(*node)->right, word);
} else {
_enter(&(*node)->left, word);
}
}
void enter(char *word)
{
_enter(&symbol_table, word);
}
static int _lookup(struct node **node, char *word)
{
int result;
if((*node) == NULL){
return 0;
}
result = strcmp((*node)->word, word);
if(result == 0){
return 1;
}
if(result < 0){
return _lookup(&(*node)->right, word);
}
return _lookup(&(*node)->left, word);
}
int lookup(char *word)
{
return _lookup(&symbol_table, word);
}
static struct node *find_min(struct node **node)
{
if((*node) == NULL){
fprintf(stderr, "Error: find_min\n");
exit (8);
}
if(((*node)->left) == NULL){
return (*node);
}
return find_min(&(*node)->left);
}
static void _delete(struct node **node, char *word){
int result;
struct node *min;
if((*node) == NULL){
return;
}
result = strcmp((*node)->word, word);
if(result == 0){
if((*node)->right == NULL && (*node)->left == NULL){
(*node) = NULL;
return;
}
if((*node)->right == NULL){
(*node) = (*node)->left;
return;
}
min = find_min(&(*node)->right);
_delete(&(*node)->right, min->word);
min->left = (*node)->left;
min->right = (*node)->right;
(*node) = min;
return;
}
if(result < 0){
_delete(&(*node)->right, word);
} else {
_delete(&(*node)->left, word);
}
}
void delete(char *word)
{
_delete(&symbol_table, word);
}
static void _print_tree(struct node *top)
{
if(top == NULL){
return;
}
_print_tree(top->left);
printf("%s\n", top->word);
_print_tree(top->right);
}
void print_symbol_table()
{
_print_tree(symbol_table);
}
コード
sample.c
#include "symbol_table.h"
#include <stdio.h>
int main(int argc, char *argv[])
{
char *names[] = {"int", "float", "char", "struct", "void"};
char *search_names[] = {"int", "double"};
int size = 5;
int size_search = 2;
int i;
print_symbol_table();
for(i = 0; i < size; i++){
printf("%sをシンボルテーブルに追加\n", names[i]);
enter(names[i]);
print_symbol_table();
}
for(i = 0; i < size_search; i++){
printf("「%s」がシンボルテーブルにあるか調べる\n", search_names[i]);
if(lookup(search_names[i])){
printf("見つかった\n");
} else {
printf("見つからなかった\n");
}
}
for(i = 0; i < size; i++){
printf("%sをシンボルテーブルから削除\n", names[i]);
delete(names[i]);
print_symbol_table();
}
return (0);
}
Makefile
CC=cc CFLAGS=-g OBJS=sample.o symbol_table.o all: sample sample: $(OBJS) $(CC) $(CFLAGS) -o sample $(OBJS) sample.o: symbol_table.h sample.c symbol_table.o: symbol_table.c clean: rm -f sample sample.o symbol_table.o
入出力結果(Terminal)
$ make cc -g -c -o sample.o sample.c cc -g -c -o symbol_table.o symbol_table.c cc -g -o sample sample.o symbol_table.o $ ./sample intをシンボルテーブルに追加 int floatをシンボルテーブルに追加 float int charをシンボルテーブルに追加 char float int structをシンボルテーブルに追加 char float int struct voidをシンボルテーブルに追加 char float int struct void 「int」がシンボルテーブルにあるか調べる 見つかった 「double」がシンボルテーブルにあるか調べる 見つからなかった intをシンボルテーブルから削除 char float struct void floatをシンボルテーブルから削除 char struct void charをシンボルテーブルから削除 struct void structをシンボルテーブルから削除 void voidをシンボルテーブルから削除 $
0 コメント:
コメントを投稿