C言語の研究・演習編4

第4章　データ構造

この章はついにC言語によるプログラムの佳境に入ったと言えよう。

C言語の誇る構造体やポインタを駆使したデータ構造について、じっくり味わって行こう。

1　スタック

データを一時的に保管するときによく用いられるデータ構造にスタック(stack)がある。

スタックは後から入れたたデータを先に出す、いわゆるLIFO(Last In First Out)構造の典型とされている。

空き領域の先頭をスタックポインタspで管理しており、スタックへデータを入れることをpush、スタックから出すことをpopと呼び、それぞれの動作は次のとおりである。

スタックの配列がMAX個あるとして、下から、stack(0),stack(1),・・・・・,stack(MAX-1) と表現できる。スタックポインタが示しているのは、データが満タンの場合stack(MAX-1)である。

(1) push(データを入れる)

スタックポインタspが上端のstack(MAX-1)を指している場合、これ以上pushすることはできないことを意味する。これをさらにpushしようとすると、スタック・オーバーフローとなる。

上端ではない場合は、spが指差す実体にデータをコピーする。

spの値を1増加させる。

(2) pop(データを取り出す)

スタックポインタspが下端のstack(0)を指している場合、スタックは空であることを意味する。この状態ではデータを取り出すことはできない。

下端ではない場合は、spの値を-1する。

spの指す実体を取り出す。

それでは実際の例を見てみよう。

スタックの上端を100とし、まず適当な整数をgets関数により入力させ整数配列に格納する。

これをpushしてpopする様子を表示させてみよう。

最初にスタックポインタと実体を設定しておこう。

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100
#define OK "OK"
#define NG "NG"

int stack[MAX_SIZE];
int *sp;
int *sp_max;
int *sp_min;
char buff[80];

void stack_ini(int *);
char *push(int *);
char *pop(int *);

void main()
{
    int akr[MAX_SIZE];
    int pell[MAX_SIZE];
    int *pa;
    int *pp;
    int i;
    int kosu = 0;
    pa = akr;
    pp = pell;

    stack_ini(stack);

    printf("スタックに入れる整数を100個以内入力してください(終わりはCTRL+Z)\n");

    while(gets(buff) != NULL){
        kosu++;
        *(pa + kosu -1) = atoi(buff);
    }

    printf("\n-----push-----\n");
    for(i = 0; i < kosu ; i++)
        printf("%d is %s\n",*(pa+i), push(pa+i) );
    printf("\n");

    printf("-----pop-----\n");
    for(i = 0; i < kosu ;i++)
        printf("%d is %s\n",*(pp+i), pop(pp+i));
}

void stack_ini(int *s)
{
    sp = s;
    sp_min = s;
    sp_max = s+(MAX_SIZE-1);
}

char *push(int *a)
{
    char *ret_code;

    if(sp == sp_max) ret_code=NG;
    else{
        *sp = *a;
        sp++;
        ret_code = OK;
    }
    return ret_code;
}

char *pop(int *p)
{
    char *ret_code;

    if(sp == sp_min) ret_code = NG;
    else{
        sp--;
        *p = *sp;
        ret_code=OK;
    }
    return ret_code;
}

いかがだろうか。pushした順番とは逆の順番でpopする様子がご覧いただけただろうか。これがLIFOである。

このスタックの典型的な例として「逆ポーランド記法」があるのでここで紹介しておこう。

逆ポーランド記法とは、演算子に先行してオペランドをならぺて書く方法で、たとえば

(3+10)/4-(105-102)×3=

は、3 10 + 4 / 105 102 - 3 × - = と書ける。

要するに、オペランドを書き、優先する演算子、という順番に書く。もっと簡単な例としては、

3 + 10 = は　3 10 + = と書ける。

この逆ポーランド記法は初期の電卓に採用されたアルゴリズムである。

これをスタックを利用してプログラムで表現してみよう。

式のはじめから順番に見て、NULLかエラーが発生するまで以下の処理を行う。

・数字はこれを数値に変換してpushする。

・演算子の '+'  '-'  '*'  '/'  については、２回popして2つのデータを取り出して演算した上でpushする。

・演算子の'=' は1回popしてこれを表示する。

・その他の文字は何もしない。

この4つの法則を守ってプログラムを書くだけでいい。さっそく見てみよう。

#include <stdio.h>
#include <stdlib.h>

#define OK 'Y'
#define NG 'N'
#define MAX_SIZE 100

int stack[MAX_SIZE];
int *sp;
int *sp_max;
int *sp_min;

void stack_ini(int *);
char push(int);
char pop(int *);

void main()
{
    char expr[80];
    char *p_expr;
    int data1;
    int data2;
    char ret_code=OK;

    stack_ini(stack);

    printf("逆ポーランド記法による式をスペースで区切って入れてください : ");
    gets(expr); /*scanf関数はスペースが入ると止まるので、ここでは使えない*/

    for(p_expr = expr; *p_expr != NULL && ret_code == OK ;){
        if(*p_expr >= '0' && *p_expr <= '9'){
            ret_code = push(atoi(p_expr));
            while(*p_expr >= '0' && *p_expr <= '9') p_expr++;
        }
        else if(*p_expr == '+'){
            ret_code = pop(&data1);
            if(ret_code == OK) ret_code = pop(&data2);
            if(ret_code == OK) ret_code = push(data1+data2);
            p_expr++;
        }
        else if(*p_expr == '-'){
            ret_code = pop(&data2);
            if(ret_code == OK) ret_code = pop(&data1);
            if(ret_code == OK) ret_code = push(data1-data2);
            p_expr++;
        }
        else if(*p_expr == '*'){
            ret_code = pop(&data1);
            if(ret_code == OK) ret_code = pop(&data2);
            if(ret_code == OK) ret_code = push(data1*data2);
            p_expr++;
        }
        else if(*p_expr == '/'){
            ret_code = pop(&data2);
            if(ret_code == OK) ret_code = pop(&data1);
            if(ret_code == OK) ret_code = push(data1/data2);
            p_expr++;
        }
        else if(*p_expr == '='){
            ret_code = pop(&data1);
            if(ret_code == OK){
                printf("-----Result-----\n");
                printf("%s %d\n",expr ,data1);
            }
            p_expr++;
        }
        else p_expr++;
    }

    if(ret_code == NG) printf("スタックエラー\n");
}

void stack_ini(int *p)
{
    sp = stack;
    sp_min = stack;
    sp_max = stack + (MAX_SIZE-1);
}

char push(int a)
{
    char ret_code;

    if(sp == sp_max) ret_code=NG;
    else{
        *sp = a;
        sp++;
        ret_code = OK;
    }
    return ret_code;
}

char pop(int *p)
{
    char ret_code;

    if(sp == sp_min) ret_code = NG;
    else{
        sp = sp-1;
        *p = *sp;
        ret_code = OK;
    }
    return ret_code;
}

どうだろうか、今回push関数には整数を引数として与えることにした点が前回と異なっている点だろう。

また、式exprをスペースで区切って入力するため、scanf関数が使えなかったというところが残念だった。

加えて、文字列exprを実体とするポインタp_exp自体の値を変化させているため、結果を表示するprintf関数で式を表示するのにexprを使用したが、このように心ならずもポインタ自体の値を変化させなければならない時もあることを心の片隅に置いておこう。

2　キュー

データを一時的に保管するときによく用いられるデータ構造のもうひとつにキュー(queue)があり、待ち行列とも呼ばれている。

これは、先に待っていたデータから順番に取り出す、つまり先入れ先出し、FIFO(First In First OUT)の構造をとっている。

たとえば、a(0),a(1),・・・,a(n-1)というn個の配列があったとして、これにデータを入れていく場合、どこからどこまでデータが入っているか、一見しただけでは分からない。

というのは、仮にa(0)から順にデータが配列の最後a(n-1)まで入っていたが、a(0)からa(5)までが取り出されてしまっている場合、ポインタがデータの最後を示す配列a(n-1)だけを指しているとしたら、せっかくa(0)から6個の配列に空席があるのに、ここにはデータを入れることができなくなる。

もっとひどい場合は、a(n-1)にたった1つのデータがあるだけで、この配列は役立たずな配列になってしまうのだ。

これを避けるため、スタックポインタとは異なり、キューの場合は、格納されているデータの最後(tail)を指すポインタに加えて、データの先頭を示すポインタ(head)が必要になってくる。

こうすると、データを入れるのはtail、取り出すのはhead、とそれぞれポインタが案内してくれるという訳だ。

これを基本にしてキューへのデータ格納方法を考えていこう。

さっきのような場合、つまり先頭のa(0)からいくつかの配列が空いているのに、tail がa(n-1)を指している場合は、tail = n とする代わりに tail = 0 として先頭からデータ入力していけばいいわけだ。

それでは、この配列が空というのはheadとtailの状態はどうなっているのかというと、たとえば、a(i)がheadであり、a(i)が tailでもあるという状態である。　つまり、head = tail という関係である。

すると、配列がぎっしり詰まった状態というのはどうか、この配列に目一杯データを入れた状態では、やはり、head = tail という関係が成り立ってしまって、空の状態と区別がつかない。

そこで、データの1個分を残した状態が配列に一杯詰まったということにしよう。

それなら、頭から詰まっている場合は head = 0 で tail = n-1 のとき、

また配列の途中から詰まっている場合は tail = head - 1 の状態のとき

それぞれデータが満タンですということができる。　

キューへのデータ格納と取り出し方法は次のとおり、

・格納方法は、データが一杯でないとき、tailの指す実体にコピーする。tailの値を1増す、その結果 tail = n となった場合については tail = 0とする

・取りだし方法は、head = tail のときは空ということから取り出しはできない。データを取り出せるときは、head の指す実体からデータを取り出す。headの値を1増す。head = n となった場合は、head = 0 とする。

それでは実際例を見てみよう。

これはユーザにキューに入れる好きな文字列と文字数および取り出す文字数を計3回、入力させて結果を確認するプログラムである。

便宜上、最大何文字入力できるかを表示しているが、これにとらわれず制限以上の文字数等を入力すると、それぞれエラー表示を出すようにしている。

#include <stdio.h>

#define MAX_SIZE 8
#define OK 'y'
#define NG 'n'

    char queue[MAX_SIZE];
    char *head;
    char *tail;
    char *queue_min;
    char *queue_max;

void q_ini(char *);
char put_q(char *);
char get_q(char *);

void main()
{
    char akr[MAX_SIZE];
    char *pa;
    char pell[MAX_SIZE];
    char *pp;
    int i, a;
    int n = 0;
    int m = 0;
    int zan = MAX_SIZE -1;
    char ret_code;

    pa = akr;
    pp = pell;

    q_ini(queue);

    for(a =0; a < 3; a++){
        printf("-----%d/3回目-----\n",a+1);

        printf("キューに入れる文字列と文字数をスペースで区切って入力してください(%d文字以内)\n",zan);
        scanf("%s %d",pa, &n);
        for(i = 0; i < n; i++){
            ret_code = put_q(pa+i);
            if(ret_code == OK) printf("%d \'%c\'をpushしました\n",i+1,*(pa+i));
            else printf("pushエラー\n");
        }
        zan -= n;
        printf("\n");

        printf("キューから取り出す文字数を入力してください\n");
        scanf("%d", &m);
        for(i = 0; i < m; i++){
            ret_code = get_q(pp+i);
            if(ret_code == OK) printf("%d \'%c\'をpopしました\n",i+1,*(pp+i));
            else printf("popエラー\n");
        }
        zan += m;
    }
}

void q_ini(char *q)
{
    head = q;
    tail = head;
    queue_min = q;
    queue_max = q + (MAX_SIZE -1);
}

char put_q(char *a)
{
    char ret_code;
    if( (head == queue_min && tail == queue_max) || tail == head - 1)
        ret_code = NG;
    else{
        *tail = *a;
        tail++;
        if(tail >queue_max) tail = queue_min;
        ret_code=OK;
    }
    return ret_code;
}

char get_q(char *p)
{
    char ret_code;
    if(tail == head)
        ret_code=NG;
    else{
        *p = *head;
        head++;
        if(head > queue_max) head = queue_min;
        ret_code = OK;
    }
    return ret_code;
}

いかがなものだろうか、与えられたアルゴリズムが正しければ、正しい結果が導き出されることがお分かりいただけただろうか。

プログラミングで一番こわいのは論理エラーで、文法上は正しいのにアルゴリズム自体に欠陥がある場合は、絶対に意図する結果は返ってこない。

3　リスト構造

データを配列に格納しておいて、後でリスト表示することは日常業務で多く用いられている。

データを物理的にも順番に配列に入れておくと、後になってデータを挿入したい場合は、それ以降のデータを全部後にずらさなければならない。これをリストの逐次配置という。

これに対し、各データが次のデータへのポインタを持っている場合はどうだろう。そのポインタを入れ換えるだけでOKとかなり便利である。これをリストの鎖状配置という。

(1) 単方向リストによるデータの表示

順不同に並んでいるデータがあったとして、これを順に表示するためには、各データが次のデータへのポインタを持つようにすればよい。

それと、そのリストへのポインタつまりリストヘッドがあれば、リストヘッドから順にリストをたどって全データを表示できる。最後のデータのポインタにはNULLを入れておこう。

早速見てみよう。

#include <stdio.h>

#define KOSU 8

typedef struct name_list{
    char *name;
    struct name_list *next;
}LIST;

void print_list(LIST *);
void main()
{
    LIST pell[KOSU]={
        {"Akira",NULL},
        {"Bruce",NULL},
        {"Computer",NULL},
        {"Dragon",NULL},
        {"English",NULL},
        {"Fortunately",NULL},
        {"Hideo",NULL},
        {"Independence",NULL}
    };
    LIST *head;
    LIST *p;
    int i;
    p = pell;
    head = p;
   
    for(i = 0; i < KOSU-1; i++) /*各データに次のデータへのポインタを代入する*/
        (p+i)->next = (p+i+1);

    print_list(head);
}

void print_list(LIST *head)
{
    LIST *p;
    int i;

    for(i = 1,p = head ; p != NULL ; p = p->next, i++ )
        printf("%d %s\n",i,p->name);
}

いかがだろうか、次のデータへのポインタをたどって次々と表示される様子がご覧になれただろうか。

(2) 単方向リストへのデータの挿入

単方向リストはポインタが次のデータを示しているだけなので、これにデータを挿入すること簡単である。

方法としては次の要領でやろう。

・データを書き込むための領域を確保する。これにはmalloc関数を使おう。

・確保した領域にデータを書き込む。

・挿入したデータの1つ前のデータのポインタを挿入したデータを指すように設定する。

・挿入したデータのポインタをその1つ後ろのデータを指すように設定する。

これだけの処理だ。ちょっとやってみよう。

仮に8つのデータがABC順にならんでいるとして、Godzillaという単語をこのリストにアルファベット順になるように挿入する場合を考えよう。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct name_list{
    char *name;
    struct name_list *next;
}LIST;

LIST pell[]={
        {"Akira",NULL},
        {"Bruce",NULL},
        {"Computer",NULL},
        {"Dragon",NULL},
        {"English",NULL},
        {"Fortunate
        ly",NULL},
        {"Hideo",NULL},
        {"Pell",NULL}
};

void print_list(LIST *);
int add_list(LIST *, char *, int *);

void main()
{
    LIST *head;
    LIST *p;
    int i;
    int max = 8;
    p = pell;
    head = pell;
   
    for(i = 0; i<max-1; i++)    
        (p+i)->next=(p+i+1);

    print_list(head);
    printf("挿入後の配列数は%2dです\n",max);

    printf("-----挿入後-----\n");

    max = add_list(head,"Godzilla", &max);
    printf("挿入後の配列数は%2dです\n",max);
}

void print_list(LIST *head)
{
    LIST *p;
    int i;

    for(i = 1,p = head; p != NULL; p=p->next,i++ )
        printf("%d %s\n",i,p->name);
}

int add_list(LIST *h, char *add_name, int *m)
{
    LIST *p_add;
    LIST *p;
    LIST *pb;
    int i;

    p_add = (LIST *)malloc(sizeof(LIST)); /*構造体の領域確保*/
    p_add->name = (char *)malloc(strlen(add_name)+1); /*文字列(構造体メンバの実体)の領域確保*/
    strcpy(p_add->name,add_name); /*実体である文字列のコピー*/
    p_add->next = NULL;

    p = h;
    i = 0;

    while(p != NULL && strcmp(add_name, p->name) >= 0 ){
        i++;
        pb = p;
        p = p->next;
    }

    if(i == 0) h = p_add;
    else pb->next = p_add;
   
    if(i < *m) p_add->next = p;
   
    for(i = 1,p = h ; p != NULL ; p=p->next, i++ )
        printf("%d %s\n",i ,p->name);
    return ++(*m);

    free(p_add); /*構造体の領域解放*/
    free(p_add->name); /*構造体メンバであるポインタの実体の領域解放*/
}

どうかな、malloc関数久しぶりに出たね。覚えているだろうか、忘れていてもどうってことはない。その都度解説書を見ればよい。たとえば平林雅英氏・著の「ANSI C言語辞典」(技術評論社)などを手元に置いておくと便利である。

(3) 単方向リストのデータ削除

今度は単方向リストのデータ削除を行ってみよう。方法は以下のとおりである。

・削除したいデータとその1つ前のデータを探す。

・1つ前のデータのポインタを、削除するデータの1つ後ろのデータを指すようにする。

・削除したいデータの領域を解放する。

それでは早速見てみよう。先ほどの追加処理の例題に削除処理ルーチンを加えて、追加する文字列をscanf関数で入力してもらい。それを削除した上で、追加したリストと削除後のリストを表示するようにしよう。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define OK 'y'
#define NG 'n'

typedef struct name_list{
    char *name;
    struct name_list *next;
}LIST;

LIST pell[]={
        {"Akira",NULL},
        {"Dragon",NULL},
        {"Hideo",NULL},
        {"Japan",NULL},
        {"Mashimo",NULL},
        {"Queue",NULL},
        {"Prince",NULL},
        {"Zoro",NULL}
};
LIST *p_add;
   

int add_list(LIST*, char *, int*);
char del_list(LIST*, char *);

void main()
{
    LIST *head;
    LIST *p;
    int i;
    int max = 8;
    char ret_code;
    char add[11];
    char *pa;

    pa = add;
    p=pell;
    head=pell;
   
    for(i=0; i < max-1; i++)     (p+i)->next = (p+i+1);

    printf("追加して削除する文字列を入れてください(10文字以内) :");
    scanf("%s",pa);
    max = add_list(head, pa, &max);

    printf("-----削除後-----\n");
    ret_code=del_list(head,pa);
}

int add_list(LIST *h, char *add_name, int *m)
{
    LIST *p;
    LIST *pb;
    int i;
    p_add = (LIST *)malloc(sizeof(LIST));
    p_add->name = (char *)malloc(strlen(add_name)+1);
    strcpy(p_add->name,add_name);
    p_add->next = NULL;

    p = h;
    i = 0;

    while(p != NULL && strcmp(add_name, p->name)>=0 ){
        i++;
        pb = p;
        p = p->next;
    }

    if(i == 0) h = p_add;
    else pb->next = p_add;
   
    if(i < *m) p_add->next = p;
   
    for(i = 1,p = h ; p != NULL ; p = p->next, i++ )
        printf("%d %s\n",i , p->name);

    return ++(*m);
}

char del_list(LIST *h, char *del_name)
{
    LIST *p;
    LIST *pb;
    int i;
    char ret_code;

    p = h;
    i = 0;

    while(p != NULL && strcmp(del_name, p->name) != 0 ){
        i++;
        pb = p;
        p = p->next;
    }

    if(p != NULL){
        if(i == 0) h = p->next;
        else pb->next = p->next;
        ret_code = OK;
    }
    else ret_code = NG;

    for(i = 1,p = h ; p != NULL ; p = p->next ,i++ )
        printf("%d %s\n",i ,p->name);

    if(ret_code == OK) printf("%sを削除しました\n",del_name);
    else printf("%sは該当なし\n",del_name);

    return ret_code;

    free(p_add);
    free(p_add->name);
}

削除処理も追加とほとんど同様で説明は特に必要ないだろう。ただ、free関数の使用する場所に注意してもらいたい。最後の処理が終わった時点で領域を開放するようにしよう。

(4) 双方向リストによるデータ表示

今までのは単方向リストで順番に表示した。これを各データが次のデータのポインタとともに前のデータを指すポインタも持っているとしたら逆の順序に表示することも可能になる。

この場合、リストヘッドをもう一つ、逆の順番を示すリストヘッドを用意しておけば便利である。

これも例題で確認しておこう。

#include <stdio.h>

#define KOSU 8

typedef struct name_list{
    char *name;
    struct name_list *next;
    struct name_list *before;
}LIST;

void print_list(LIST *, LIST *);
void main()
{
    LIST pell[KOSU]={
        {"Akira",NULL, NULL},
        {"Bruce",NULL, NULL},
        {"Computer",NULL, NULL},
        {"Dragon",NULL, NULL},
        {"English",NULL, NULL},
        {"Fortunately",NULL, NULL},
        {"Hideo",NULL, NULL},
        {"Pell",NULL, NULL}
    };
    LIST *n_head;
    LIST *b_head;
    LIST *p;
    int i;
    p = pell;

    n_head = p;
    b_head = (p+KOSU-1);

    for(i = 0; i < KOSU-1; i++)   
        (p+i)->next = (p+i+1);

    for(i = KOSU-1; i > 0 ; i--) /*逆順のポインタ設定*/
        (p+i)->before = (p+i-1);

    print_list(n_head, b_head);
}

void print_list(LIST *n_head, LIST *b_head)
{
    LIST *p;
    int i;

    for(i = 1,p = n_head ; p != NULL ; p = p->next ,i++ )
        printf("%d %s\n",i ,p->name);

    printf("\n");

    for(i = KOSU,p = b_head ; p != NULL ; p = p->before ,i-- )
        printf("%d %s\n",i ,p->name);

}

どうだろう。逆順のポインタ設定処理以外には特に目新しい処理はないだろう。

4　ハッシュ

ハッシュとは各データが持つキーを数値化して、データの格納場所を決定するデータ構造をいう。

キーを数値化する関数をハッシュ関数という。

(1) ハッシュ構造の数値データの検索

簡単な例からはじめると、学生番号、名前、年齢をデータ項目とするリストがあるとして、年齢をキーとすると、各年齢ごとのテーブルが出来る。この年齢テーブルの該当する年齢には、該当年齢の学生データへのポインタが格納されており、これによりデータを表示できる。

さらに、先ほどのように各データが次のデータへのポインタを持っているならば、次々とその年齢のデータが表示可能なわけである。

ちょっと見てみよう。

#include <stdio.h>
#include <stdlib.h>

#define MIN 18
#define MAX 20
#define NG -1
#define KOSU 3

typedef struct list{
    int no;
    char *name;
    struct list *next;
}DATA;

DATA a_18[3] = {
    {1001,"Akira",a_18+1},{1002,"Pell",a_18+2},{1003,"Dragon",NULL}
};
DATA a_19[2] = {
    {1004,"Tomato",a_19+1},{1005,"France",NULL}
};
DATA a_20[2] = {
    {1006,"Umi",a_20+1},{1007,"Godzilla",NULL}
};

DATA *tbl[KOSU] = {a_18, a_19, a_20};

int get_hash(int);

void main()
{
    int i, n, hash;
    char age[10];
    DATA **pt = tbl;
    DATA *p;
   

    printf("年齢を入れてください : ");
    n = atoi(gets(age));

    hash = get_hash(n);
   
    if(hash != NG){
        printf("-----Result-----\n");
        printf("    学番     名前\n");
        p = *(pt+hash);
        for(i =1 ; p != NULL; p=p->next, i++)
            printf("%d     %4.4d    %-15s\n",i ,p->no ,p->name);
    }
    else
        printf("該当データなし\n");
}

int get_hash(int a)
{
    int ret = NG;

    if(a >= MIN && a <= MAX) ret = a - MIN;
    return ret;
}

いかがだろうか。データをつくるのが面倒くさかったので、18〜20歳までの3つのテーブルだけ作ったが、大体こんな感じがハッシュ関数だということがお分かりいただけただろうか。この例では、年齢 - 18 をハッシュ値としている。

(2) 文字列データをキーとするハッシュ構造

今の例は、年齢という整数をキーにしていたため、ハッシュ値が簡単に出せたが、キーが文字列の場合はどういう計算をすればいいのだろう。

一般的な方法としては、各文字の内部コードを整数とみなして、その合計をハッシュテーブルの要素数で割った余りをハッシュ値としている。

例をいうと、"ito"は、i = 105   t = 116    o = 111、これらを合計すると332になる。

仮に、ハッシュテーブルの要素数を7とすると、 332 / 7 = 47 ...3    ハッシュ値は3となる。

それでは、ハッシュテーブルの要素数を7として例を見て行こう。

#include <stdio.h>
#include <string.h>

#define HASH_SIZE 7

typedef struct list{
    int no;
    char *name;
    struct list *next;
}DATA;

DATA h0[1] = {1001,"Bruce",NULL};
DATA h1[1] = {1008,"Dragon",NULL};
DATA h2[1] = {1009,"watanabe",NULL};
DATA h3[3] = {
        {1006,"ito",h3+1},
        {1002,"kobayashi",h3+2},
        {1010,"yamamoto",NULL}
};
DATA h4[2] = {
        {1006,"suzuki",h4+1},
        {1007,"tanaka",NULL}
};
DATA h5[3] = {
        {1234,"Pell",h5+1},
        {1000,"Akira",h5+2},
        {1005,"sato",NULL}
};
DATA h6[1] = {1004,"sasaki",NULL};

DATA *tbl[HASH_SIZE] = {h0, h1, h2, h3, h4, h5, h6};

int hash(char *, int);

void main()
{
    char nm[20];
    int n;
    DATA *p;
    DATA **pt;
    pt=tbl;

    printf("探索する名前を入れてください : ");
    gets(nm);

    n = hash(nm, HASH_SIZE);
    p = *(pt+n);

    while(p != NULL && strcmp(p->name,nm) != 0) p = p->next;
   
    printf("-----Result-----\n");
    if(p != NULL)
        printf("%4.4d     %s\n",p->no,p->name);
    else
        printf("該当なし\n");
}

int hash(char *s, int h)
{
    int total = 0;
   
    while(*s != NULL) total += *s++;
    printf("ハッシュ値は%d\n", total % h);
    return total % h;
}

どうだろうか、この例題もまた最初のデータ作成が大変なやつである。わざとハッシュ値の表示をさせて、後でデータを作成して行ったのが本音である。

(3) ハッシュ構造へのデータの挿入

ハッシュ構造もリスト構造と同様にデータがそれぞれ次のデータへのポインタを持っているので、データ挿入は簡単にできて助かる。手順としては次のとおりである。

・データを書き込むための領域をmalloc関数で確保する。

・確保した領域にデータを書き込む。

・ハッシュ値を求める。

・該当するハッシュ値のリストの先頭にデータを挿入する。

さっきの例をデータリストとして利用することとして、それでは見てみよう。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HASH_SIZE 7

typedef struct list{
    int no;
    char *name;
    struct list *next;
}DATA;

DATA h0[1] = {1001,"Bruce",NULL};
DATA h1[1] = {1008,"Dragon",NULL};
DATA h2[1] = {1009,"watanabe",NULL};
DATA h3[3] = {
        {1006,"ito",h3+1},
        {1002,"kobayashi",h3+2},
        {1010,"yamamoto",NULL}
};
DATA h4[2] = {
        {1006,"suzuki",h4+1},
        {1007,"tanaka",NULL}
};
DATA h5[3] = {
        {1234,"Pell",h5+1},
        {1000,"Akira",h5+2},
        {1005,"sato",NULL}
};
DATA h6[1] = {1004,"sasaki",NULL};

DATA *tbl[7] = {h0, h1, h2, h3, h4, h5, h6};

DATA add;
DATA *p_add;

char st[20];

int hash(char *, int);
void add_data(DATA **, DATA *);

void main()
{
    char nm[20];
    int n;
    DATA *p;
    DATA **pt;
    DATA *p_ad;

    pt = tbl;
    p_ad = &add;

    printf("追加するデータの番号を入力してください : ");
    scanf("%d",&p_ad->no);
    printf("追加するデータの名前を入力してください : ");
    scanf("%s",st);
    p_ad->next = NULL;

    add_data(pt, p_ad);

    printf("探索する名前を入れてください : ");
    scanf("%s",nm);

    n=hash(nm, HASH_SIZE);
    p = *(pt+n);

    while(p != NULL && strcmp(p->name,nm) != 0) p=p->next;
   
    printf("-----Result-----\n");
    if(p != NULL)
        printf("%4.4d     %s\n",p->no,p->name);
    else
        printf("該当なし\n");
   
    free(p_add->name);
    free(p_add);

}

int hash(char *s, int h)
{
    int total=0;
   
    while(*s != NULL) total += *s++;
    return total % h;
}

void add_data(DATA **pt, DATA *pa)
{
    int n;

    p_add = (DATA *)malloc(sizeof(DATA));
    *p_add = *pa;
    p_add->name = (char *)malloc(strlen(st)+1);

    strcpy(p_add->name, st);
    n = hash(p_add->name,HASH_SIZE);

    p_add->next = *(pt+n);
    *(pt+n) = p_add;
    printf("%d %sを追加しました\n",p_add->no, p_add->name);
}

追加した確認の意味でprintf関数で追加データを表示することとした。

先ほどのリスト構造でのmalloc関数もそうだったが、構造体へのポインタ型や文字列型へのポインタをそれぞれキャスト演算子て゜malloc関数に指示しておいてやる必要がある部分に注意していただきたい。

(3) ハッシュ構造でのデータの削除

ハッシュ構造もリスト構造と同様にデータ削除が楽である。方法としては次のとおり。

・削除したいデータのハッシュ値を求める。

・削除するハッシュ値の先頭から検索して削除したいデータを探す。

・削除したいデータが見つかったら、直前のデータのポインタを削除するデータの次のデータを指すように設定する。

・削除したいデータの領域を開放する。

さて例題を見てみよう。先ほどの例題の追加処理に削除処理を加えた例題である。

なお、削除処理時に領域を解放できるのは、追加処理で加えたデータを削除する場合に限ることにしたのでご了承願いたい。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HASH_SIZE 7
#define OK 'y'
#define NG 'n'

typedef struct list{
    int no;
    char *name;
    struct list *next;
}DATA;

DATA h0[1] = {1001,"Bruce",NULL};
DATA h1[1] = {1008,"Dragon",NULL};
DATA h2[1] = {1009,"watanabe",NULL};
DATA h3[3] = {
        {1006,"ito",h3+1},
        {1002,"kobayashi",h3+2},
        {1010,"yamamoto",NULL}
};
DATA h4[2] = {
        {1006,"suzuki",h4+1},
        {1007,"tanaka",NULL}
};
DATA h5[3] = {
        {1234,"Pell",h5+1},
        {1000,"Akira",h5+2},
        {1005,"sato",NULL}
};
DATA h6[1] = {1004,"sasaki",NULL};

DATA *tbl[7]={h0, h1, h2, h3, h4, h5, h6};

DATA add;
DATA *p_add;

char st[20];

int hash(char *, int);
void add_data(DATA **, DATA *);
char del_data(DATA **, char *);
void main(int argc, char **argv)
{
    char nm[20];
    DATA **pt;
    DATA *p_ad;
    char ret_code;

    pt = tbl;
    p_ad = &add;

    printf("-----追加処理-----\n");
    printf("追加データの番号を入力してください : ");
    scanf("%d",&p_ad->no);
    printf("追加データの名前を入力してください : ");
    scanf("%s",st);
    p_ad->next = NULL;

    add_data(pt,p_ad);

    printf("-----削除処理-----\n");
    printf("削除する名前を入れてください : ");
    scanf("%s",nm);
   
    ret_code = del_data(pt,nm);
    if(ret_code == OK) printf("%sを削除しました\n",nm);
    else    printf("%sは該当なし\n",nm);
}

int hash(char *s, int h)
{
    int total=0;
   
    while(*s != NULL) total += *s++;
    return total % h;
}

void add_data(DATA **pt, DATA *pa)
{
    int n;

    p_add = (DATA *)malloc(sizeof(DATA));
    *p_add = *pa;
    p_add->name = (char *)malloc(strlen(st)+1);

    strcpy(p_add->name,st);
    n = hash(p_add->name,HASH_SIZE);

    p_add->next = *(pt+n);
    *(pt+n) = p_add;
    printf("%d %sを追加しました\n",p_add->no, p_add->name);
}

char del_data(DATA **pt, char *s)
{
    int n;
    char ret_code;
    DATA *p, *pb;

    n = hash(s, HASH_SIZE);
    p = *(pt+n);

    while(p != NULL && strcmp(p->name,s) != 0){
        p = p->next;
        pb = p;
    }
   
    if(p != NULL){
        if(p == *(pt+n))
            *(pt+n) = p->next;
        else
            pb->next = p->next;
        printf("%d %sを削除中\n",p->no,p->name);
        ret_code = OK;
    }
    else
        ret_code = NG;

    return ret_code;
   
    free(p_add->name);
    free(p_add);
}

いかがだろうか。全部のデータを実行時に領域確保したわけではないので、このように中途半端な処理となって申し訳ないが、ハッシュ構造の使い方が分かっていただければありがたい。

5　2分探索木

リスト構造ではデータが1列に並んで、次のデータへのポインタを持っていた。これを次のデータへのポインタを2つ持つこととして、自分より大きいデータは右へ、自分より小さいデータは左へと分岐させるとツリー構造になるが、このツリーを2分木(binary tree)という。

これを左右2つのポインタで次々とつないだデータ構造を2分探索木(binary search tree)という。

このデータ構造の特徴は、1番最初のデータは左には自分より小さいデータへのポインタ(left)、右には自分より大きいデータへのポインタ(right)を持っており、このデータ自体はどこからも指差されることはない。このデータを根と呼んでいる。

やはり、リスト構造のheadと同様に、この１番最初のデータ・根を指すポインタのrootを用意しておけば便利である。

ずっとポインタをたどって行って、もはや次のデータがない場合は、leftかrightかあるいは両方のポインタがNULLとなっているわけである。

(1) 2分探索木によるデータの昇順表示

それでは簡単な例として、キーである整数値をデータと、自分より小さいデータへのポインタ(left)と自分より大きいデータへのポインタ(right)を持つデータがあったとして、これを昇順に表示してみよう。

方法は以下のとおりである。

・分岐点として根のデータを選ぶ。

・分岐点より左のデータはすべて分岐点のデータより小さいので、左のデータを表示する。

・分岐点のデータを表示する。

・分岐点より右のデータはすべて分岐点のデータより大きいので、右のデータを表示する。

・分岐点の左側のデータを表示する場合、分岐点のleftの指すデータが分岐点であった場合は、それを分岐点として赤色処理を繰り返す。

・分岐点の右側のデータを表示する場合、分岐点のrightの指すデータがやはり分岐点であった場合は、それを分岐点として赤色処理を繰り返す。

・左側はleftがNULL、右側はrightがNULLであらたな分岐点が設定できないとき処理を終了する。

これらの処理には私の苦手な再帰関数を用いなければならない。

それではレッツノート、いやレッツビギン。

#include <stdio.h>

typedef struct list{
    int key;
    struct list *left;
    struct list *right;
}DATA;

DATA pell[14]={
/* 0*/    {50, &pell[1], &pell[11]},
/* 1*/    {40, &pell[2], &pell[3]},
/* 2*/    {30, &pell[4], &pell[5]},
/* 3*/    {45, NULL, &pell[6]},
/* 4*/    {20, &pell[7], &pell[8]},
/* 5*/    {35, NULL, NULL},
/* 6*/    {47, &pell[9], &pell[10]},
/* 7*/    {10, NULL, NULL},
/* 8*/    {25, NULL, NULL},
/* 9*/    {46, NULL, NULL},
/*10*/    {48, NULL, NULL},
/*11*/    {60, NULL, &pell[12]},
/*12*/    {70, &pell[13], NULL},
/*13*/    {65, NULL, NULL}
};

void print_data(DATA *);

void main()
{
    DATA *p;
    p = pell;

    printf("-----Result of binary search tree-----\n");
    print_data(p);
    printf("\n");
}

void print_data(DATA *root)
{
    if(root == NULL) return;
    else{
        print_data(root->left);
        printf("%d ",root->key);
        print_data(root->right);
    }
}

いかがだろうか、これもデータ作成で頭が痛かった。データの左のコメント欄が努力の跡と言えるだろう。

表示させるのは構造体のkeyというメンバだけで、ポインタがNULLでないif文が成立する場合は再帰呼び出しするだけの話で、ポインタがNULLのときが再帰関数の脱出口だ。

(2) 2分探索木によるデータの検索

今度は、キーである整数値を持つデータを次の方法で検索してみよう。

・分岐点として根のデータを選ぶ。

・分岐点のデータのキーが指定された値と一致する場合、分岐点のデータが検索する値となる。

赤字にならない場合は次の処理を行う。

・指定データが分岐点のデータのキーより小なら、leftの指すデータを新たな分岐点として赤字の処理を行う。

・指定データが分岐点のデータのキーより大なら、rightの指すデータを新たな分岐点として赤字の処理を行う。

・左側はleftがNULL、右側はrightがNULLで、新しい分岐点が設定できないとき、指定されたデータはない。

これもまたまた、再帰関数でやってやろう。

それではさっきの苦労したデータを用いた例を見てみよう。

#include <stdio.h>

typedef struct list{
    int key;
    struct list *left;
    struct list *right;
}DATA;

DATA pell[14]={
/* 0*/    {50, &pell[1], &pell[11]},
/* 1*/    {40, &pell[2], &pell[3]},
/* 2*/    {30, &pell[4], &pell[5]},
/* 3*/    {45, NULL, &pell[6]},
/* 4*/    {20, &pell[7], &pell[8]},
/* 5*/    {35, NULL, NULL},
/* 6*/    {47, &pell[9], &pell[10]},
/* 7*/    {10, NULL, NULL},
/* 8*/    {25, NULL, NULL},
/* 9*/    {46, NULL, NULL},
/*10*/    {48, NULL, NULL},
/*11*/    {60, NULL, &pell[12]},
/*12*/    {70, &pell[13], NULL},
/*13*/    {65, NULL, NULL}
};

void get_data(DATA *, int);

void main(int atgc, char **argv)
{
    DATA *p;
    int atai;

    p = pell;
    printf("探索する値を入れてください: ");
    scanf("%d",&atai);
    printf("-----Result-----\n");
    get_data(p, atai);
}

void get_data(DATA *root, int a)
{
    if(root == NULL || root->key == a ){
        if(root != NULL) printf("%3dは該当あり\n",root->key);
        else printf("%3dは該当なし\n",a);
    }
    else{
        if(root->key < a) get_data(root->right, a);
        else get_data(root->left, a);
    }
}

どうだろうか、再帰関数の利点は、こんなにプログラムがコンパクトになるというところだろう。

ただし、if〜else〜文で、この場合は、if(root == NULL || root->key == a)だったが、このように再帰関数からの脱出条件がないと 無限ループに陥ってしまうから注意しよう。

(3) 2分探索木によるデータの追加

さて今度は、キーである整数値を持つデータを次の方法で追加してみよう。

・分岐点として根のデータを選ぶ

・追加したいデータのキーが分岐点のデータのキーより小であれば、leftの指すデータを新たな分岐点とする。

・追加したいデータのキーが分岐点のデータのキーより大であれば、rightの指すデータを新たな分岐点とする。

・赤色の2つを繰り返し、左側はleftがNULL、右側はrightがNULLで新たな分岐点が設定できないとき、追加データのリンク位置をこの分岐点の左(または右)に決定する。

そして、次のリンク処理をする。

・データを書き込む領域をmalloc関数で確保し、分岐点のポインタであるleft(またはright)がこの領域を指すように設定する。

・確保した領域にデータを書き込む。leftとrightはともにNULLにしておく。

これらの処理はまたまた再帰関数のお世話になる。

それではプログラムの方を見ることにしよう。最初に言っておくが、追加する関数が構造体リストテーブルを指すポインタ型のポインタと、追加する構造体を指すポインタを引数として用いなければならない点がかなりややこしくなっている。

それでは見て行こう。

#include <stdio.h>
#include <stdlib.h>

typedef struct list{
    int key;
    struct list *left;
    struct list *right;
}DATA;

DATA pell[14]={
/* 0*/    {50, &pell[1], &pell[11]},
/* 1*/    {40, &pell[2], &pell[3]},
/* 2*/    {30, &pell[4], &pell[5]},
/* 3*/    {45, NULL, &pell[6]},
/* 4*/    {20, &pell[7], &pell[8]},
/* 5*/    {35, NULL, NULL},
/* 6*/    {47, &pell[9], &pell[10]},
/* 7*/    {10, NULL, NULL},
/* 8*/    {25, NULL, NULL},
/* 9*/    {46, NULL, NULL},
/*10*/    {48, NULL, NULL},
/*11*/    {60, NULL, &pell[12]},
/*12*/    {70, &pell[13], NULL},
/*13*/    {65, NULL, NULL}
};

DATA *paa; /*確保して解放する構造体へのポインタ*/

void add_data(DATA **, DATA *);
void print_data(DATA **);

void main()
{
    DATA add;
    DATA *p_add;
    DATA **p_root;

    *p_root = pell; /*実体であるアドレスの設定*/
    p_add = &add;

    printf("追加するデータの値を入れてください: ");
    scanf("%d",&(p_add->key));

    add_data(p_root, p_add);

    printf("-----Result-----\n");
    print_data(p_root);
    printf("\n");
    free(paa);
}

void add_data(DATA **p_root, DATA *p_add)
{
    if(*p_root == NULL){
        *p_root = (DATA *)malloc(sizeof(DATA)); /*この時点で領域確保*/
        paa = *p_root; /*確保した領域を解放用にアドレス設定*/
        paa->key = p_add->key;
        paa->left = NULL;
        paa->right = NULL;
        *p_root = paa; /*前データのポインタに確保した領域のアドレスを設定*/
    }
    else{
        if((*p_root)->key < p_add->key)
            add_data( &((*p_root)->right) , p_add);
        else
            add_data( &((*p_root)->left) , p_add);
    }
}

void print_data(DATA **p_root)
{
    if(*p_root==NULL)
        return;
    else{
        print_data(&((*p_root)->left));
        printf("%d ",(*p_root)->key);
        print_data(&((*p_root)->right));
    }
}

どうだろうか、ちょっとややこしいかも知れない。特に赤字の部分でリストのleftないしrightをポインタ型へのポインタとして再帰関数の引数にしなければならないため、かなり理解するのに苦労すると思う。

要するに、(*p_root)->left とは、pell[i]->leftというポインタなので、これをさらにポインタ型を指すポインタとするために、&(pell[i]->left) とした訳である。これが許されるのは、最初の赤字の部分で実体であるアドレスの設定がなされているからである。

しかし、基本書としては珍しくややこしい例題であったね。頭が痛くなっちゃったね。でも大丈夫である。こんなややこしいのは実際には必要ないし、試験にも出題されない。またその場になって熟慮すれば、きっと理解できる。

さて試験と言えば、この章の最後もまた情報処理技術者試験を見ることにしよう。

この問題は、ハッシュ関数による文字列の検索問題で先にやった例とほとんど同様でたいしたことはない。

関数dnoは学生名を入力し、その学生の学生番号をハッシュ法により、すばやく検索して表示するプログラムである。

�@入力した名前からハッシュ値を求める。この場合、名前を表す文字列を構成する各文字のコードを整数とみなし、その総和をHASH_SIZE、ここでは7で割った余りnをそのハッシュ値とする。(前と同じ)

�Aハッシュ値はポインタの配列hashtabへの添字として使用する。学生名のハッシュ値がnである各学生のレコードは、学生番号(no)、名前を表す文字列へのポインタ(name)、次のレコードへのポインタ(next)からなる構造体である。配列hashtab[n]は、ハッシュ値がnであるレコードのリストの先頭を指している。nextの内容がNULLであるレコードはリストの終わりを示す。

�B同一の名前をもつ学生レコードは複数個存在しない。

�C表示の形式は、「学生の名前 = 学生番号」 とする。学生の名前がリスト中に見つからない場合は、「学生名該当なし」と表示する。

こんな問題である。さあ見てみようか。

#include <stdio.h>
#include <string.h>

#define HASH_SIZE 7

typedef struct list{
    int no;
    char *name;
    struct list *next;
}DATA;

DATA h0[1] = {1001,"Bruce",NULL};
DATA h1[1] = {1008,"Dragon",NULL};
DATA h2[1] = {1009,"watanabe",NULL};
DATA h3[3] = {
        {1006,"ito",h3+1},
        {1002,"kobayashi",h3+2},
        {1010,"yamamoto",NULL}
};
DATA h4[2] = {
        {1006,"suzuki",h4+1},
        {1007,"tanaka",NULL}
};
DATA h5[3] = {
        {1234,"Pell",h5+1},
        {1000,"Akira",h5+2},
        {1005,"sato",NULL}
};
DATA h6[1] = {1004,"sasaki",NULL};

DATA *tbl[HASH_SIZE] = {h0, h1, h2, h3, h4, h5, h6};

void dno(char *, DATA *[]);
unsigned hash(char *);
DATA *search(DATA *, char *);

void main()
{
    char nm[20];

    printf("探索する名前を入れてください : ");
    gets(nm);

    dno(nm, tbl);
}

void dno(char *sname, DATA *hashtbl[])
{
    unsigned i;
    DATA *srecp;

    i = hash(sname);

    srecp = search(hashtbl[i], sname);
   
    printf("-----Result-----\n");
    if(srecp != NULL)
        printf("%s = %4.4d番\n",sname ,srecp->no);
    else
        printf("%s該当なし\n",sname);
}


unsigned hash(char *s)
{
    unsigned i = 0;
   
    while(*s != NULL)
        i += (unsigned) *s++;
    return i % HASH_SIZE;
}

DATA *search(DATA *p, char *s)
{
    while(p != NULL && strcmp(p->name, s) != 0)
        p = p->next;
    return p;
}

いかがだろうか。例によって赤字部分が穴埋め式の問題である。ふと思うことだが、試験を作る側としてはどこの部分を穴埋めにするか迷うんじゃないだろうか。

さきにやった例を細かく関数に分けただけの内容だ。データは例と同じものを使用した。特に難解な点はないだろう。

HOME