開発環境
- OS X Mavericks - Apple(OS)
- Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
- C (プログラミング言語)
- Clang (コンパイラ)
C実践プログラミング 第3版 (Steve Oualline (著)、 望月 康司 (監訳) (翻訳)、谷口 功 (翻訳)、オライリー・ジャパン)のⅢ部(高度なプログラミング概念)の17章(高度なポインタ)、17-12(プログラミング実習)、実習17-4.を解いてみる。
その他参考書籍
- プログラミング言語C 第2版 ANSI規格準拠 (B.W. カーニハン D.M. リッチー (著)、 石田 晴久 (翻訳)、共立出版)
- プログラミング言語Cアンサー・ブック 第2版 (クロビス・L．トンド、スコット・E．ギンペル(著)、矢吹 道郎(翻訳))
17-12(プログラミング実習)、実習17-4.
コード
sample.c
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
struct node{
struct node *left;
struct node *right;
char *word;
};
static struct node *root = NULL;
void memory_error(void)
{
fprintf(stderr, "Error:Out of memory\n");
exit (8);
}
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);
}
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);
}
}
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);
}
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 scan(char *name)
{
char word[100];
int index;
int ch;
FILE *in_file;
in_file = fopen(name, "r");
if(in_file == NULL){
fprintf(stderr, "Error:Unable to open %s\n", name);
exit (8);
}
while(1){
while(1){
ch = fgetc(in_file);
if(isalpha(ch) || (ch == EOF)){
break;
}
}
if (ch == EOF){
break;
}
word[0] = ch;
for(index = 1; index < sizeof(word); ++index){
ch = fgetc(in_file);
if(!isalpha(ch)){
break;
}
word[index] = ch;
}
word[index] = '\0';
enter(&root, word);
}
fclose(in_file);
}
void print_tree(struct node *top)
{
if(top == NULL){
return;
}
print_tree(top->left);
printf("%s\n", top->word);
print_tree(top->right);
}
int main(int argc, char *argv[])
{
if (argc != 2){
fprintf(stderr, "Error:Wrong number of parameters\n");
fprintf(stderr, " on the command line\n");
fprintf(stderr, "Usage is:\n");
fprintf(stderr, " words 'file'\n");
exit (8);
}
scan(argv[1]);
printf("二分探索木\n");
print_tree(root);
printf("最小値EOFを削除--------------------\n");
delete(&root, "EOF");
print_tree(root);
printf("最大値wordsを削除--------------------\n");
delete(&root, "words");
print_tree(root);
printf("includeを削除--------------------\n");
delete(&root, "include");
print_tree(root);
printf("存在しない単語を削除--------------------\n");
delete(&root, "Haskell");
print_tree(root);
return (0);
}
makefile
CC=cc CFLAGS=-g sample: sample.c $(CC) $(CFLAGS) -o sample sample.c clean: rm -f sample
入出力結果(Terminal)
$ make cc -g -o sample sample.c $ ./sample sample.c 二分探索木 EOF Error FILE Haskell NULL Out Unable Usage Wrong argc argv break ch char command ctype delete else enter error exit fclose fgetc file find fopen for fprintf free h if in include index int is isalpha left line main malloc memory min n name new node number of on open parameters print printf r result return right root s save scan sizeof static stderr stdio stdlib strcmp strcpy string strlen struct the to top tree unsigned void while word words 最小値EOFを削除-------------------- Error FILE Haskell NULL Out Unable Usage Wrong argc argv break ch char command ctype delete else enter error exit fclose fgetc file find fopen for fprintf free h if in include index int is isalpha left line main malloc memory min n name new node number of on open parameters print printf r result return right root s save scan sizeof static stderr stdio stdlib strcmp strcpy string strlen struct the to top tree unsigned void while word words 最大値wordsを削除-------------------- Error FILE Haskell NULL Out Unable Usage Wrong argc argv break ch char command ctype delete else enter error exit fclose fgetc file find fopen for fprintf free h if in include index int is isalpha left line main malloc memory min n name new node number of on open parameters print printf r result return right root s save scan sizeof static stderr stdio stdlib strcmp strcpy string strlen struct the to top tree unsigned void while word includeを削除-------------------- Error FILE Haskell NULL Out Unable Usage Wrong argc argv break ch char command ctype delete else enter error exit fclose fgetc file find fopen for fprintf free h if in index int is isalpha left line main malloc memory min n name new node number of on open parameters print printf r result return right root s save scan sizeof static stderr stdio stdlib strcmp strcpy string strlen struct the to top tree unsigned void while word 存在しない単語を削除-------------------- Error FILE NULL Out Unable Usage Wrong argc argv break ch char command ctype delete else enter error exit fclose fgetc file find fopen for fprintf free h if in index int is isalpha left line main malloc memory min n name new node number of on open parameters print printf r result return right root s save scan sizeof static stderr stdio stdlib strcmp strcpy string strlen struct the to top tree unsigned void while word $
短いテキストで確認。(それに合わせて削除する単語も変更。)
入出力結果(Terminal)
$ cat temp.txt c a b $ ./sample temp.txt 二分探索木 a b c 最小値aを削除-------------------- b c 最大値cを削除-------------------- b bを削除-------------------- 存在しない単語Zを削除--------------------
0 コメント:
コメントを投稿