システムプログラミング序論 演習

演習5： 再帰呼び出しと木構造

課題1

ユークリッドの互除法と再帰呼び出しを使って2つの正の整数の最大公約数を求めるプログラムを作成しなさい． プログラムの実行ファイル名は ex5_1 とする． 2つの正の整数をコマンドラインの第1引数，第2引数として与えると，このプログラムは最大公約数のみが書かれた行を表示して終了する． 引数に0以下の整数が与えられた場合や，引数の数が2ではない場合には Invalid input. という1行を表示して終了する．

例題1： 二分探索木を用いたデータの探索

• このプログラムは以下の処理を順に実行する．
  • ファイルから100個の正の整数データを読み込み，二分探索木に存在しないデータを二分探索木に挿入する． 二分探索木に既に存在するデータは単に無視する．
  • 全てのノードの値を小さい順に表示し，さらに，ノードの数を表示する．
  • 端末から入力を受け取り，入力された整数がその二分探索木に含まれているかどうかを表示する処理を繰り返す． 入力された整数が0以下であれば，プログラムを終了する．
  なお，関数 int search_tree(int x, struct node *p) は，整数 x とノードへのポインタ p を受け取り，そのノードを根とする木構造の中に整数 x が含まれていれば1，含まれていなければ0を返す． 関数 int count_nodes(struct node *p) は，ノードへのポインタ p を受け取り，そのノードを根とする木構造の中に含まれるノードの数（根も数に含む）を返す．

#include <stdio.h> #include <stdlib.h> struct node { int data; struct node *left; struct node *right; }; struct node *insert_data(int x, struct node *p) { struct node *nd; if (p == NULL) { if ((nd = (struct node *)malloc(sizeof(struct node))) == NULL) { fprintf(stderr, "Out of memory\n"); exit(1); } nd->data = x; nd->left = NULL; nd->right = NULL; return nd; } if (x == p->data) { return p; } else if (x < p->data) { p->left = insert_data(x, p->left); return p; } else { p->right = insert_data(x, p->right); return p; } } void print_tree(struct node *p) { if (p == NULL) { return; } print_tree(p->left); printf("%d\n", p->data); print_tree(p->right); } int search_tree(int x, struct node *p) { /* Implement by yourself */ } int count_nodes(struct node *p) { /* Implement by yourself */ } void free_tree(struct node *p) { if (p == NULL) { return; } else { if (p->left != NULL) { free_tree(p->left); } if (p->right != NULL) { free_tree(p->right); } free(p); } } int main(int argc, char *argv[]) { FILE *fp; int i, x; struct node *root = NULL; if (argc != 2) { fprintf(stderr, "Missing file argument\n"); exit(1); } if ((fp = fopen(argv[1], "r")) == NULL) { fprintf(stderr, "Can't open %s\n", argv[1]); exit(1); } for (i = 0; i < 100; i++) { if (fscanf(fp, "%d", &x) != 1) { fprintf(stderr, "Can't read data\n"); exit(1); } if (x <= 0) { fprintf(stderr, "Invalid data: %d\n", x); exit(1); } root = insert_data(x, root); } fclose(fp); print_tree(root); printf("%d numbers read\n", count_nodes(root)); while (1) { printf("Input number "); if (scanf("%d", &x) == EOF) { fprintf(stderr, "Can't read input\n"); exit(1); } if (x <= 0) { break; } if (search_tree(x, root) == 1) { printf("%d: Found\n", x); } else { printf("%d: Not found\n", x); } } free_tree(root); return 0; }

課題2

関数 search_tree と count_nodes を作成し，プログラムを完成させなさい． プログラムの実行ファイル名は ex5_2 とする． 入力としてファイル ex5_numbers.txt を与えて ./ex5_2 ./ex5_numbers.txt を実行し，木のノード数（重複しない整数データの数）が正しく表示されることを確認しなさい．さらに，端末から適当な整数を入力し，入力された数字が木構造に含まれるかどうかが正しく判定されることを確認しなさい．

課題3

このプログラムを元に，木構造に含まれている全ての整数を1行に1個ずつ表示し，次の行にそれらの整数の和を表示するプログラムを作成しなさい． プログラムの実行ファイル名は ex5_3 とする． 入力として課題2と同じファイルを使って ./ex5_3 ./ex5_numbers.txt を実行し，木構造に含まれている整数の和をそのプログラムが正しく出力することを確認しなさい．

例題2： トライ木を用いたデータ探索

• このプログラムは，第一引数で指定されたファイルの中身を読み込み，第二引数で指定された文字列がその中に含まれるかどうかを検査する． 第一引数で指定されたファイルの中の文字列はすべて，トライ木（trie）に格納される． その後，第二引数で指定された単語がトライ木に含まれるかどうかを探索する．
• トライ木のノードには，trie_t 型へのポインタの配列が割り当てられている． このノード A の下に別のノード B が来る場合は，ノード A が表す文字のASCIIコードと同じインデックスの配列の位置にノード B へのポインタが入る． たとえば，文字 'a' の後の文字列に対応するノードへのポインタは array['a'] に格納される．
• 包含関係にある文字列（たとえば every と everyone）に対応するために，単語を格納する際には，最後に '.' を入れる． つまり、every という単語を格納する際には，root->'e'->'v'->'e'->'r'->'y'->'.' という形でノードが構成される． 同様に，探索の場合には，root->'e'->'v'->'e'->'r'->'y' と辿ることができても，'y' の後に '.' が無い場合には every が見つかったとは判定されない．
• なお，このプログラム中に含まれていない関数 trie_t *find_in_trie(char *str, trie_t *ptr) は，ポインタ ptr が指すトライ木に対し，ポインタ str が指す文字列が含まれるかどうかを調べる関数である． str が含まれている場合には，最終的に到達した '.' を表す trie_t 型の構造体へのポインタを返し，含まれていない場合には NULL を返す．

#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct trie { struct trie *array[256]; } trie_t; void init_trie(trie_t *ptr) { int i; for (i = 0; i < 256; ++i) { ptr->array[i] = NULL; } return; } trie_t *new_trie(void) { trie_t *ptr; if ((ptr = malloc(sizeof(trie_t))) == NULL) { fprintf(stderr, "Out of memory\n"); exit(1); } init_trie(ptr); return ptr; } void add_to_trie(char *str, trie_t *ptr) { unsigned char c; if (strlen(str) == 0) { ptr->array['.'] = new_trie(); return; } c = *str; if (ptr->array[c] == NULL) { ptr->array[c] = new_trie(); } add_to_trie(str + 1, ptr->array[c]); } trie_t *find_in_trie(char *str, trie_t *ptr) { /* Implement by yourself */ } void free_trie(trie_t *ptr) { int i; for (i = 0; i < 256; ++i) { if (ptr->array[i] != NULL) { free_trie(ptr->array[i]); } } free(ptr); } int main(int argc, char *argv[]) { FILE *f; char str[512]; trie_t *root; if (argc != 3) { fprintf(stderr, "Missing argument\n"); exit(1); } if ((f = fopen(argv[1], "r")) == NULL) { fprintf(stderr, "Can't open %s\n", argv[1]); exit(1); } root = new_trie(); while (fgets(str, 512, f)) { if (str[strlen(str) - 1] == '\n') { str[strlen(str) - 1] = '\0'; } add_to_trie(str, root); } fclose(f); if (find_in_trie(argv[2], root) != NULL) { printf("%s: \"%s\" is found in %s\n", argv[0], argv[2], argv[1]); } else { printf("%s: \"%s\" is not found in %s\n", argv[0], argv[2], argv[1]); } free_trie(root); return 0; }

課題4

関数 find_in_trie を作成し，プログラムを完成させなさい． プログラムの実行ファイル名は ex5_4 とする． 入力としてファイル ex5_words.txt を与えて ./ex5_4 ./ex5_words.txt word を実行する． レポートには，このファイルの中に下記の単語が含まれるかどうかをチェックした様子を含めること． the only strategy guarantee to fail is not take risk

課題5

発展課題： 単位取得のためには提出は必須ではないが，提出すれば加点する．

このプログラムは速く動作するが，メモリを無駄に使っている． そこで，二重連鎖木に基づいたトライ木を用いるように変更する． そのために，trie_t の定義を以下のように変更する． typedef struct trie { struct trie *child; struct trie *next; char c; } trie_t; この新しい trie_t に対応するには，init_trie, add_to_trie, find_in_trie, free_trie を書き換える必要がある． これらの関数を書き換えてプログラムを完成させなさい． なお，add_to_trie については以下にヒントを示す（ヒントを参考にせず最初から自力で作っても良い）． うまく行かない場合には，各ノードの関係を図に書いて考えると良い． void add_to_trie(char *str, trie_t *ptr) { if (strlen(str) == 0) { if (ptr->c == '\0') { ptr->c = '.'; return; } else if (ptr->c == '.') { return; } else if (ptr->next == NULL) { ptr->next = new_trie(); ptr->next->c = '.'; return; } else { add_to_trie(str, ptr->next); return; } } if (ptr->c == '\0') { /* Implement by yourself */ } else if (ptr->c == *str) { /* Implement by yourself */ } else if (ptr->next == NULL) { /* Implement by yourself */ } else { /* Implement by yourself */ } } プログラムの実行ファイル名は ex5_5 とし，課題4と同じチェックを実施した様子をレポートに含めること． 書き換える必要があるファイルにfree_trieが抜けていたので，free_trieを加えるという修正を行いました（2019年11月19日11:30）．