C言語アルゴリズム-2分木 |
5 2分木(Binary Tree) (3)
変数名(文字列)とそのデータ(整数)を入力し、2分木に格納する。変数名にendを入力すると終了する。
(pro5-5.c)
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: |
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct binary { /* 2分木のデータ構造 */ char *key; /* 節(データ) */ int data; struct binary *left; /* 左の枝の節の番地 */ struct binary *right; /* 右の枝の節の番地 */ }BINARY; BINARY root = {NULL, 0, &root, &root}; /* 最初の節の番地 */ typedef struct hensuu{ char name[256]; int data; }HENSUU; void tree_print(BINARY *); int tree_insert(HENSUU); void main(void) { char buff[256]; HENSUU val; while(1){ printf("変数名 : "); gets(val.name); if(!strcmp(val.name, "end")) break; printf("整数データ : "); gets(buff); val.data = atoi(buff); tree_insert(val); tree_print(&root); } } void tree_print(BINARY *p) { static int depth = 0; if(p->right != NULL){ ++depth; tree_print(p->right); --depth; } printf("%*c%s(%d)\n", 5 * depth, ' ', p->key, p->data); if(p->left != NULL){ ++depth; tree_print(p->left); --depth; } } int tree_insert(HENSUU vv) /* 2分木構造に格納する */ { BINARY *pp, *new; int cmp; char *s; pp = &root; /* ルートの番地を格納 */ /* 文字列データを格納する領域を確保 */ if((s = (char *)malloc(sizeof(vv.name))) == NULL){ printf("領域を確保できません\n"); exit(1); } strcpy(s, vv.name); /* 確保した領域に文字列データを格納 */ if(pp->left == &root || pp->right == &root){ /* 最初のデータ格納 */ pp->key = s; pp->data = vv.data; pp->left = NULL; pp->right = NULL; return(1); } /* 領域確保(新しい節を作成) */ if((new = (BINARY *)malloc(sizeof(BINARY))) == NULL){ printf("領域を確保できません\n"); exit(1); } while(1){ /* 枝をたどって節を探す */ cmp = strcmp(pp->key, s); if(cmp == 0){ /* 登録済み */ free(s); /* 領域開放 */ free(new); /* 領域開放 */ return(0); }else if(cmp > 0){ if(pp->left == NULL){ pp->left = new; break; } pp = pp->left; /* 次の節を探す */ }else{ if(pp->right == NULL){ pp->right = new; break; } pp = pp->right; /* 次の節を探す */ } } new->key = s; /* 新しい節にデータを登録 */ new->data = vv.data; new->left = NULL; new->right = NULL; return(1); } |
変数名 : mnd 整数データ : 11 mnb(11) 変数名 : asd 整数データ : 22 mnb(11) asd(22) 変数名 : sdf 整数データ : 33 sdf(33) mnb(11) asd(22) 変数名 : ghj 整数データ : 44 sdf(33) mnb(11) ghj(44) asd(22) 変数名 : qwe 整数データ : 55 sdf(33) qwe(55) mnb(11) ghj(44) asd(22) 変数名 : end |
変数名とそのデータをあらかじめ2分木に格納し、入力した変数名を検索し、そのデータを表示する。endを入力すると終了する。 (pro5-6.c)
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: |
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct binary { /* 2分木のデータ構造 */ char *key; /* 節(データ) */ int data; struct binary *left; /* 左の枝の節の番地 */ struct binary *right; /* 右の枝の節の番地 */ }BINARY; BINARY root = {NULL, 0, &root, &root}; /* 最初の節の番地 */ typedef struct hensuu{ char name[256]; int data; }HENSUU; HENSUU tree_search(char *); void tree_print(BINARY *); int tree_insert(HENSUU); void main(void) { char buff[256]; int i = 0; static HENSUU vv, val[] = { "hensuu", 12, "joho", 38, "tree", 123, "start", 33, "first", 1, "abcd", 111, "goal", 99, "masuda", 121, "*", 0 }; while(1){ /* 変数名とデータの格納 */ if(val[i].name[0] == '*'){ tree_print(&root); break; } tree_insert(val[i]); ++i; } while(1){ printf("変数名 : "); gets(buff); if(!strcmp(buff, "end")) break; vv = tree_search(buff); if(vv.name[0] == '\0') printf("見つからない\n"); else printf("データ = %d\n", vv.data); tree_print(&root); } } HENSUU tree_search(char *hensuu) { BINARY *pp; int cmp; HENSUU vv; vv.name[0] = '\0'; vv.data = 0; pp = &root; while((cmp = strcmp(hensuu, pp->key)) != 0){ if(cmp < 0){ if(pp->left == NULL) /* データ終了 */ return(vv); pp = pp->left; }else{ if(pp->right == NULL) /* データ終了 */ return(vv); pp = pp->right; } } strcpy(vv.name, hensuu); vv.data = pp->data; return(vv); } |
tree(123) start(33) masuda(121) joho(38) hensuu(12) goal(99) first(1) abcd(111) 変数名 : tree データ = 123 tree(123) start(33) masuda(121) joho(38) hensuu(12) goal(99) first(1) abcd(111) 変数名 : end |
ユーザ関数tree_insertとtree_printはproc5-5.cと同じであるので省略している。
Copyright © 2001 Hiroshi Masuda |