第112回 プログラミングについて『ハッシュ法 その3』

　　　　　　　　　　 プログラミングについて　第１１２回目

　　　　　　　　　　　　　　 『ハッシュ法　その３』

　今回は前回までのプログラムの結果を文字の小さい順で表示する様にします。
まずは前回までの全文です。

　#include <stdio.h>

　#define NEW(type,element)　(type *)malloc(sizeof(type)*(element))
　#define DELETE(addr)　　　 free(addr)

　struct node_strct{
　　char *word;
　　int　total;
　　struct node_strct *left,*right;
　};

　#define MAX_TABLE 100
　struct node_strct *table[MAX_TABLE];

　struct node_strct *new_node();

　main()
　{
　　char word[81];
　　int i,j;

　　for(i=0;i<MAX_TABLE;i++)table[i]=NULL;

　　while(1){
　　　scanf("%s",word);
　　　if(feof(stdin))break;

　　　add_word(word);
　　}

　　for(i=0;i<MAX_TABLE;i++){
　　　if(table[i]){
　　　　printf("----- %d -----\n",i);
　　　　display(table[i],0);
　　　}
　　}
　}

　add_word(word)
　char *word;
　{
　　unsigned char *s;
　　int v;

　　v=0;
　　s=(unsigned char *)word;
　　while(*s)v+= *s++;

　　v%=MAX_TABLE;

　　if(!table[v])table[v]=new_node(word);
　　else　　　　 add_node(table[v],word);
　}

　struct node_strct *new_node(word)
　char *word;
　{
　　struct node_strct *t;

　　t=NEW(struct node_strct,1);
　　t->word=NEW(char,strlen(word)+1);
　　strcpy(t->word,word);
　　t->total=1;
　　t->left =NULL;
　　t->right=NULL;

　　return t;
　}

　add_node(tree,word)
　struct node_strct *tree;
　char *word;
　{
　　int i;

　　i=strcmp(word,tree->word);
　　if(i==0){
　　　tree->total++;
　　}
　　else if(i<0){
　　　if(tree->left)add_node(tree->left,word);
　　　else　　　　　tree->left=new_node(word);
　　}
　　else{
　　　if(tree->right)add_node(tree->right,word);
　　　else　　　　　 tree->right=new_node(word);
　　}
　}

　display(tree,depth)
　struct node_strct *tree;
　int depth;
　{
　　int i;

　　if(tree->left)display(tree->left,depth+2);

　　for(i=0;i<depth;i++)putchar(' ');
　　printf("%5d %s\n",tree->total,tree->word);

　　if(tree->right)display(tree->right,depth+2);
　}

結果を表示してプログラムが終了しますので、ハッシュテーブルの各要素に分散している２分木を１つにまとめ、文字列の小さい順から表示するような改修を行ないましょう。

メイン関数を次のように変更します。

　main()
　{
　　char word[81];
　　int i,j;

　　for(i=0;i<MAX_TABLE;i++)table[i]=NULL;

　　while(1){
　　　scanf("%s",word);
　　　if(feof(stdin))break;

　　　add_word(word);
　　}

　　/* ここの部分は削除。
　　for(i=0;i<MAX_TABLE;i++){
　　　if(table[i]){
　　　　printf("----- %d -----\n",i);
　　　　display(table[i],0);
　　　}
　　}
　　*/

　　/* ここからが追加 */
　　　　　　　　　　　　　　/* テーブル内の最初の２分木の要素番号を取得する */
　　for(j=0;j<MAX_TABLE;j++){
　　　if(table[j])break;
　　}
　　　　　　　　　　　　　　/* ２番目以降の２分木を最初の２分木にまとめる */
　　for(i=j+1;i<MAX_TABLE;i++){
　　　if(table[i]){
　　　　reconnect(table[j],table[i]);
　　　　table[i]=NULL;
　　　}
　　}

　　display(table[j]);　　 /* 表示を行う */
　}

変更の意味は理解できると思います。

とにかく最も問題な２番目以降の２分木を最初の２分木にまとめるループ内の、関数reconnect です。

　reconnect(main_tree,tree)
　struct node_strct *main_tree;
　struct node_strct *tree;
　{
　　　　　　　　　　　　　/* 左にノードがあるときには左のノード（木）を指定して
　　　　　　　　　　　　　　 再び reconnect を呼び出す */
　　if(tree->left){
　　　reconnect(main_tree,tree->left);
　　　tree->left=NULL;
　　}
　　　　　　　　　　　　　/* 右にノードがあるときには右のノード（木）を指定して
　　　　　　　　　　　　　　 再び reconnect を呼び出す */
　　if(tree->right){
　　　reconnect(main_tree,tree->right);
　　　tree->right=NULL;
　　}
　　　　　　　　　　　　　/* 左右の処理が終わったら自分自身（ノード）をメイン
　　　　　　　　　　　　　　 の木にまとめる */
　　reconnect_task(main_tree,tree);
　}

この関数も良く見て下さい。としか言えません。関数 reconnect_task はメインの木に実際にノードを付加する関数で、次のものです。

　reconnect_task(main_tree,tree)
　struct node_strct *main_tree;
　struct node_strct *tree;
　{
　　int i;

　　　　　　　　　　　　　　　　 /* 単語を比較する */
　　i=strcmp(tree->word,main_tree->word);

　　　　　　　　　　　　　　　　 /* 追加しようとする単語が小さいとき、
　　　　　　　　　　　　　　　　　　メイン木の左にノードがあれば、左のノード
　　　　　　　　　　　　　　　　　　を指定して再び reconnect_task を呼び出す。
　　　　　　　　　　　　　　　　　　ないときにはそのポインタを左に代入 */
　　if(i<0){
　　　if(main_tree->left)reconnect_task(main_tree->left,tree);
　　　else　　　　　　　 main_tree->left=tree;
　　}
　　　　　　　　　　　　　　　　 /* 追加しようとする単語が大きいとき、
　　　　　　　　　　　　　　　　　　メイン木の右にノードがあれば、右のノード
　　　　　　　　　　　　　　　　　　を指定して再び reconnect_task を呼び出す。
　　　　　　　　　　　　　　　　　　ないときにはそのポインタを右に代入 */
　　else{
　　　if(main_tree->right)reconnect_task(main_tree->right,tree);
　　　else　　　　　　　　main_tree->right=tree;
　　}
　}

関数 reconnect_task では同一の単語はありませんので大きいか小さいかの２通りしか処理を行ないません。

　そして表示する関数 display です。この関数は引数から段下げの値をなくし、次のようにします。

　display(tree)
　struct node_strct *tree;
　{
　　if(tree->left)display(tree->left);

　　printf("%5d %s\n",tree->total,tree->word);

　　if(tree->right)display(tree->right);
　}

これで完成です。試しに実行してみて下さい。

　#include <stdio.h>

　#define NEW(type,element)　(type *)malloc(sizeof(type)*(element))
　#define DELETE(addr)　　　 free(addr)

　struct node_strct{
　　char *word;
　　int　total;
　　struct node_strct *left,*right;
　};

　#define MAX_TABLE 100
　struct node_strct *table[MAX_TABLE];

　struct node_strct *new_node();

　main()
　{
　　char word[81];
　　int i,j;

　　for(i=0;i<MAX_TABLE;i++)table[i]=NULL;　　　/* テーブルの初期化 */

　　while(1){
　　　scanf("%s",word);
　　　if(feof(stdin))break;

　　　add_word(word);　　　　　　　　　　　　　 /* 単語を追加 */
　　}

　　for(j=0;j<MAX_TABLE;j++){
　　　if(table[j])break;
　　}

　　for(i=j+1;i<MAX_TABLE;i++){
　　　if(table[i]){
　　　　reconnect(table[j],table[i]);
　　　　table[i]=NULL;
　　　}
　　}

　　display(table[j]);
　}

　add_word(word)
　char *word;
　{
　　unsigned char *s;
　　int v;

　　v=0;
　　s=(unsigned char *)word;
　　while(*s)v+= *s++;

　　v%=MAX_TABLE;

　　if(!table[v])table[v]=new_node(word);
　　else　　　　 add_node(table[v],word);
　}

　struct node_strct *new_node(word)
　char *word;
　{
　　struct node_strct *t;

　　t=NEW(struct node_strct,1);
　　t->word=NEW(char,strlen(word)+1);
　　strcpy(t->word,word);
　　t->total=1;
　　t->left =NULL;
　　t->right=NULL;

　　return t;
　}

　add_node(tree,word)
　struct node_strct *tree;
　char *word;
　{
　　int i;

　　i=strcmp(word,tree->word);
　　if(i==0){
　　　tree->total++;
　　}
　　else if(i<0){
　　　if(tree->left)add_node(tree->left,word);
　　　else　　　　　tree->left=new_node(word);
　　}
　　else{
　　　if(tree->right)add_node(tree->right,word);
　　　else　　　　　 tree->right=new_node(word);
　　}
　}

　reconnect(main_tree,tree)
　struct node_strct *main_tree;
　struct node_strct *tree;
　{
　　if(tree->left){
　　　reconnect(main_tree,tree->left);
　　　tree->left=NULL;
　　}

　　if(tree->right){
　　　reconnect(main_tree,tree->right);
　　　tree->right=NULL;
　　}

　　reconnect_task(main_tree,tree);
　}

　reconnect_task(main_tree,tree)
　struct node_strct *main_tree;
　struct node_strct *tree;
　{
　　int i;

　　i=strcmp(tree->word,main_tree->word);

　　if(i<0){
　　　if(main_tree->left)reconnect_task(main_tree->left,tree);
　　　else　　　　　　　 main_tree->left=tree;
　　}
　　else{
　　　if(main_tree->right)reconnect_task(main_tree->right,tree);
　　　else　　　　　　　　main_tree->right=tree;
　　}
　}

　display(tree)
　struct node_strct *tree;
　{
　　int i;

　　if(tree->left)display(tree->left);

　　printf("%5d %s\n",tree->total,tree->word);

　　if(tree->right)display(tree->right);
　}

最後にプログラムの全文です。

３回に渡ってハッシュ法についてお話ししてきましたが、なんとなく分かりましたでしょうか。プログラム例が動的にメモリーを確保したり、ポインタを使用したり、再帰呼び出しを頻繁に使用したりしているのでかなりキツイかもしれませんが、そのうち慣れると思います。

プログラムを書くときには何らかのアルゴリズムを必ずと言っていいくらいに使用しますが、それを単独に使用することもあれば、組み合わせることで更に効果が大きくなることもあります。今回の例はハッシュ法と２分木でしたが、こうやって作ってみると意外に相性はいいみたいです。

それではまた次回。