構造体のお話

ポインタとセットで人気がないのがこの構造体。非常に便利でいろいろなことができるだけに、それなりの知識と経験を要求される部分でもあります。ここでは構造体の基礎を説明した後、実際にいくつか応用例を紹介します。

習うより慣れよ、案ずるより生むが易し、百聞は一見に如かず、です。早速、見てみましょう。

目次

• 基礎
  • 定義
  • 宣言
  • 構造体を使う
  • おまけ
  • まとめ -基礎-
• 応用への準備
  • 入れ子
  • 構造体とメモリ
  • 構造体とポインタ
  • 再帰的な定義
  • まとめ -応用への準備-
• データ構造（１）　〜連結リスト〜
  • 連結リストの構造
  • 連結リストの生成
  • リストを辿る
  • 要素を削除する
  • 要素を挿入する
  • まとめ -連結リスト-
• データ構造（２）　〜二分木〜
  • 二分木の構造
  • 二分探索木
  • 木を辿る
  • 二分探索木の生成
  • ノードの検索
  • ノードの削除
  • まとめ -二分木-

構造体（１）　〜基礎〜

なにはさておき、「構造体」とは何か。を説明します。

定義

厳密ではありませんが、構造体とは「複数のデータを格納できる、変数の親玉のようなもの」だと思ってください。この説明だけだと、配列とさして変わらない気もしますが、構造体には、違った型のデータも一緒に格納することができます。

各データを「引き出し」に持つ「タンス」のようなイメージをもってもらえばわかりやすいでしょうか。

構造体を利用することでデータの管理をわかりやすくしたり、特殊なアルゴリズムを使った計算などができるようになります。

宣言

構造体は通常の変数と異なり、あらかじめ定義しておく必要があります。こんな感じです。

struct person {
    char name[50];   /*名前*/
    int  age;        /*年齢*/
    double tall;     /*身長*/
};     /*←このセミコロンを忘れないように！*/

これで、name,age,tallの３つのデータ（メンバ）を持つ構造体「person」が定義されました。

しかし、構造体personにはまだ実体がありません。今定義したのはいわば「型」ですから、今度はその型の変数を宣言しなければいけないというわけです。

※正確には型ではなく「タグ名」となりますが、以下簡単のためタグ名も型と表記する場合があります。

例えば「student」という名前のperson構造体型変数を宣言するには、

struct person student;

とこのようにします。「struct」を忘れないようにしましょう。

またもちろん、配列として宣言することもできます。

struct person student[30];

構造体を使う

次は構造体のメンバにアクセスしてみましょう。「.（ドット）」演算子というものを使用します。

（構造体の使い方の流れをつかむためにソースを全て載せておきます。）

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

struct person {
    char name[50];
    int  age;
    double tall;
};

int main(){
    struct person student;

    strcpy(student.name,"haruno hibari");    /*それぞれのメンバに値を代入*/
    student.age = 20;
    student.tall = 170.3;

    printf("%sさんは%d歳で、身長は%.1lfセンチあります。\n",
       student.name,student.age,student.tall);
    return 0;
}

実行すると、

haruno hibariさんは20歳で、身長は170.3センチあります。

と表示されるはずです。

おまけ

構造体の定義の仕方は何種類かあるので、そちらを紹介しておきます。

その１　〜型として定義する〜

typedef struct person{
    char name[50];
    ...
};

構造体の定義の前に「typedef」とつけています。こうすることで、「person」は新たな型として定義されます。この場合、変数の宣言が少し簡単になります。

person student;

と、「struct」の部分が省略できます。

その２　〜定義と同時に宣言する〜

struct person{
    char name[50];
    ...
}student;

これで、struct person型の構造体型変数studentが宣言されました。コンマで区切ると、複数の変数を宣言できます。

※先ほどのtypedefと組み合わせて使うことは出来ません。

その３　〜変数宣言のみする〜

struct {
    char name[50];
    ...
}student;

こうすると、変数studentは宣言されるのですが、型が定義されないのでプログラム中で他にこの構造体を宣言することができません。その型の構造体を他に使わない場合などは、こうしておけばソースコードが多少シンプルになりますね。

構造体（２）　〜応用への準備〜

さて、一通り構造体の使い方を学んだわけですが、ここではもうすこし細々した知識をお教えします。主に後述の「データ構造」でよく用いられるものです。

入れ子

構造体は入れ子にすることができます。簡単に言うと、構造体の中に別の構造体を入れることが出来るわけです。つまり、

struct quantity{
    double tall;
    double weight;
    double foot;    /*足のサイズ*/
}

struct person{
    char name[50];
    int age;
    struct quantity body;
};

こういうことです。ここで例えばperson型の変数studentがあったとすると、足のサイズ「foot」にアクセスするには

student.body.foot

となります。ここは直感的に理解できるかと思います。

構造体とメモリ

さて、構造体はメモリ中でどのような姿をしているのでしょうか。例えば下のように定義、宣言されているとしましょう。

struct person{
    char name[50];
    int age;
    double tall;
}student;

このとき、構造体型変数studentは、

こんな風になっています。見て解るように、「&」演算子によって構造体そのものや、各メンバのアドレスを参照することもできます。

構造体とポインタ

構造体は、後述する「データ構造」との関係上、ポインタによりアクセスすることが多いものです。例えば

struct{
    char name[50];
    int age;
    double tall;
};

...

    struct person student;
    struct person *ptr_student = &student;

となっているとき、studentへのポインタptr_studentを用いてそれぞれのメンバ（例えばage）にアクセスするには、

(*ptr_student).age

このようにするわけですが、実はこれは省略できて、

ptr_student->age

とすることでもageメンバにアクセスすることが出来ます。（「->」をアロー演算子と言います）

再帰的な定義

こういうと難しく聞こえますが、要は「構造体は自分と同じ型の構造体へのポインタを格納できる」ということです。これでも難しいかもしれないので、実際の例を示しておきます。

struct linked_list{
    int data;
    struct linked_list *next;
};

今は、この事実だけがわかっていればそれで十分です。後に「データ構造」と言うものを扱いますが、そのときに使い方をお教えします。（因みに、上の例は「連結リスト」と呼ばれるものです。）

さて、ここからが構造体のメイン部分です。大量のデータを格納する場合、配列を使ったのでは不具合を生じる場合があります。例えば、データを配列中から削除したり、配列に新たなデータを追加したり、配列のサイズを変えたり…といった時にやたら複雑、或いは冗長な操作が必要になってしまいます。これは配列のサイズが固定であり、メモリ内の連続した部分を占めなければいけないことから発生する問題です。ここから扱うデータ構造は、要はサイズが可変で、何かしら便利な特徴を持ったデータ格納システムです。プログラミングをやっていく上で非常に重要な概念ですので、丁寧に解説していこうと思います。

データ構造１　〜連結リスト〜

連結リストの構造

「連結リスト」と呼ばれるデータ構造は、「メンバ中に自分と同じ型へのポインタを持った構造体」で表されます。例えば、

struct linked_list{
    int index;    /*要素につける通し番号（必要とは限らない）*/
    int data;     /*データ*/
    struct linked_list *next;    /*次の要素へのポインタ*/
};

このようになります。「first」がリストの先頭を指すポインタとして、図で示すと

こんな感じになります。

※連結リストには他にも種類があります。

配列と違って、それぞれの構造体はメモリの何処にあっても構いませんが、直接データの場所を指定できないので、例えば

first->next->next->…->data

と、ポインタを辿ることでデータを参照します。

特徴

連結リストの長所と短所を挙げておきます

長所

• メモリを動的に確保することでサイズが伸縮自在
• 定義が再帰的なため、再帰関数やループを使ったプログラムが簡単に書ける
• メモリ中の連続した領域を占めるわけではなく、大きなデータも扱いやすい。
• データ構造の中では扱いが比較的容易
• 要素の挿入、削除が容易。

短所

• 先頭から順に走査しなければならないので、要素へのアクセスが遅い。
• 次の要素へのポインタを格納する分、メモリ領域が余分に必要となる。
• 配列と比べてこれといった特殊な機能はない。

ここから先は、具体的にリストを扱う方法について解説します。

連結リストの生成

連結リストは、最初先頭ポインタのみを変数で宣言し、mallocなどで実体の領域を確保。そして要素を追加するたびにやはりmallocなどでメモリを割り当てて生成していくのが一般的です。具体的には、

struct linked_list *first;
first = (struct linked_list *)malloc(sizeof(linked_list));

first->next = (struct linked_list *)malloc(sizeof(linked_list));
first->next->next = ....
...

※実際にプログラムを作るときは割り当てのチェックを忘れずに行いましょう。（cf:ポインタの項）

のようにします。実際のプログラミングでは、「リストの末尾に要素を追加する関数」を作っておけばよいですね。

また、リストの末尾のnextメンバは値をNULL(=0)にしておくのを忘れないようにしましょう。

リストを辿る

これはループや再帰関数を使うことで簡単に実装できます。例えば再帰を使ってリストの中身を全て表示するには下のようにします。

struct linked_list *tmp = first;

while(tmp){
    printf("index:%d\ndata:%d",tmp->index,tmp->data);
    tmp = tmp->next;
}

tmpは今現在何処までリストを辿ったかを記憶する変数です。中身を表示した後に、tmpにtmp->nextつまり、リストの次の要素へのポインタを代入し、末尾まで（tmpがNULLになるまで）繰り返し処理をしています。下はtmpの動きの例です。

このように、一時変数を使ってデータ構造の中を辿っていくというテクニックは頻繁に使われるので覚えておきましょう。

要素を削除する

これもそれほど難しいものではありません。実は削除というよりは、ポインタを繋ぎかえる作業がメインとなります。今回はindexメンバを指定して削除を行ってみます。

void delete_item(struct linked_list **first,int target){
/*firstはリストの先頭ポインタを指すポインタ、
  targetは削除したい要素のindexメンバ*/

    struct linked_list *tmp = *first, *hit;

    if((*first)->index == target){    /*先頭を削除する場合*/
        (*first) = (*first)->next;
        free(tmp);
        return;
    }

    while(tmp->next){    /*先頭から順にtargetを探す。*/
        if(tmp->next->index == target) {
            hit = tmp->next;    /*hitには削除対象のポインタを代入*/
            tmp->next = tmp->next->next;
            free(hit);
            break;
        }
        tmp = tmp->next;
    }
}

多少複雑になりましたが、やっていることは簡単です。まず削除の対象が先頭かどうか判断し、先頭ならfirstを更新して終了。そうでなければ対象を探して、対象の前のポインタを対象の後のポインタに繋ぎかえています。また、削除した要素はfree関数で開放しています。

要素を挿入する

こちらも、ポインタを繋ぎかえる作業が主となります。早速見てみましょう。targetで指定したindexの前に、ポインタitemが指す要素を挿入します。

void insert_item(struct linked_list **first,struct linked_list *item,int target){
    struct linked_list *tmp = *first;

    if((*first)->index == target){    /*先頭の前に挿入する場合*/
        item->next = *first;
        *first = item;
        return;
    }

    while(tmp->next){
        if(tmp->next->index == target) {
            item->next = tmp->next;
            tmp->next = item;
            break;
        }
        tmp = tmp->next;
    }
}

削除とプログラムの構造が似ていますね。先頭に挿入する場合はfirstの更新が必要で、それ以外の場合はポインタを繋ぎ換えています（上の図参照）。

データ構造（２）　〜二分木〜

もう一つだけ有名なデータ構造を挙げておきましょう。こちらは二分木と言い、その名の通り「木」のような構造をしています。連結リストに比べて少し操作が繁雑になりますが、なかなか強力なデータ構造です。

二分木の構造

二分木は、「メンバ中に自分と同じ型へのポインタを２つ含んだ構造体」で定義されます。

struct btree{     /*binary treeの略*/
    int index;    /*通し番号（必要とは限らない）*/
    int data;     /*データ*/
    struct btree *left;
    struct btree *right;
};

※二つのポインタの名前は、慣用的に「left」、「right」とされます。

下は、木の根元を表すポインタを「root」としたときの二分木のイメージ図です。

用語の説明をしておきましょう。先ずそれぞれの要素の事をノード（節点）と呼びます。あるノードからrightまたはleftで参照できるノードを、「子」と呼び、その逆の関係を「親」と呼びます。また子を持たないノードを「葉」、親を持たないノードを「根」（上の図の「root」）といいます。

更に、あるノードAから別のノードBを辿ることが出来るとき、AをBの「祖先」、BはAの「子孫」といいます。

これらの語は後々使っていきます。恐らく直感的に解ると思うので無理に覚えておく必要もないでしょう。

二分探索木

二分木にもいくつかあるのですが、今回はその中でも「二分探索木」と呼ばれるものを扱ってみます。

二分探索木とは、以下のルールを適用した二分木のことです。

• あるノードＡの左の祖先は皆、値がＡより小さい
• あるノードＢの右の祖先は皆、値がＡより大きい

これだけです。構造体ですから、「値」なんてものはないのですが、これはある一つのメンバについて成り立っていればよいので、今回は「data」にしましょう。さらに上の定義には要素の値が同じ場合が含まれていませんので、

• あるノードＡの左の祖先は皆、値がＡより小さい
• あるノードＢの右の祖先は皆、値がＡ以上

とでもしておきましょう。

因みに二分探索木の最たる特徴は、ソートが非常に簡単（もとい、ソートの必要がない）で、連結リストよりもある要素にアクセスする時間が短いことです。

二分探索木の生成

さて、それでは二分探索木を作ってみましょう。二分探索木では、ノードを挿入する関数がそのまま木を作る関数に使えますので、関数の名前は「insert」としましょう。

で、挿入の方法なのですが、先に述べた「二分探索木の定義」を満たすように、値を比べながら木を辿るだけです。

今回は先に例を示しておきましょう。下の図は、既存の木に値が６のノードが挿入される様子です。

void insert(struct btree **root,struct btree *item){
    /*引数は、根を指すポインタへのポインタと、ノードする要素へのポインタ*/

    struct btree *tmp=*root;    /*tmpは木を辿るための変数*/
    
    if(!(*root)){    /*根がないときはitemを根にして終了*/
        *root = item;
        return;
    }

    while(1){
        if(item->data < tmp->data){    /*itemのdataがtmpのdataよりも小さければ*/
            if(tmp->left) tmp = tmp->left;  /*左の子があれば今度はそちらと比較*/
            else{
                tmp->left = item;           /*なければ、左の子をitemにする*/
                break;
            }
        }else{                         /*itemがtmp以上のときも同様*/
            if(tmp->right) tmp = tmp->right;
            else{
                tmp->right = item;
                break;
            }
        }
    }
}

少し長いですが、難しいところは引数にポインタのポインタを使うところくらいでしょうか。これは根を指すポインタを関数の中で更新する必要があるためです。

因みに先の図のような木を作るには、root(=NULL)に例えば値が5,2,9,1,4,7,9,11,8の要素をこの順にinsertしていけばよいでしょう。

木を辿る

二分木の辿り方はいくつかあるのですが、今回はその中で「通りがけ順」と呼ばれる走査方法を見てみたいと思います。この方法だと、自動的に値の小さい順に木を辿ることになります。（上の図の場合、1,2,4,5,6,7,8,9（上）,9（下）,11の順）

さて、プログラムは連結リストと同じく、再帰関数やループを使って容易に作ることができます。今回は再帰を使って木のノード全てを小さい順に表示してみましょう。

void walk(struct btree *node){
    if(node->left) walk(node->left);
    printf("index:%d,\tdata:%d\n",node->index,node->data);
    if(node->right) walk(node->right);
}

えー、これだけです。二分探索木の定義を上手く利用するとこのように簡単なコードで実現できます。

証明は「数学的帰納法」を使うと出来るはずです。興味のある方のために載せておきます。

ノードの検索

こちらも再帰関数を使って書いて見ましょう。dataをキー（検索する対象）として検索を行い、見つかったらそのノードへのポインタを返します。

struct btree *search_btree(struct btree *node,int target){
    if(!node){
        printf("can't find.");
        return NULL;
    }else if(node->data == target) return node;
    else if(node->data > target) return search_btree(node->left,target);
    else return search_btree(node->right,target);
}

二分探索木の特徴を利用して、現在のノードのdataの値と検索対象の値targetを比べながら、targetの方が小さければ左、そうでなければ右の子をnodeに指定して再帰しています。

ノードの削除

さて、これまでのプログラムは比較的簡単なものでしたが、削除に関しては一筋縄ではいきません。基本はポインタのつなぎかえなのですが、二分木の構造上、親を辿るのが難しいため、プログラムも繁雑になります。

まずは、場合分けをする必要があります。１つ目は、削除するノードが子を持たない場合。２つ目は、子を１つ持つ場合。最後は２つの子を持つ場合です。それぞれ、下図のような操作を行うことになります。

子を持たない場合、ノードを解放し、親のポインタをNULLにします。

子を一つ持つ場合、連結リストの削除と同じように、対象の親から対象の子へとポインタをつなぎ、対象を解放します。

こちらは少し理解が難しいかも知れません。子を二つ持つ場合、先ず対象となるノードの次に大きな要素と削除対象とを交換し、再び削除関数を呼び出します。

下にソースの例を載せておきますが、解説は省かせていただきます。な、長いので…

/*
 *検索用関数の改良版。目的のノードの親ノードも返す。ただし、
 *検索の結果見つかったものが根である(＝親が存在しない)ときは、親ノードも根を返す。
 */
struct btree *search_btree_p(struct btree *root,int target,struct btree **parent){
/*parentは、親ノードへのポインタのポインタが格納される。*/

    struct btree *tmp = root;
    *parent = root;

    while(tmp){
        if(tmp->data == target) return tmp;
        else if(tmp->data > target) {
            *parent = tmp;
            tmp = tmp->left;
        }else if(tmp->data < target) {
            *parent = tmp;
            tmp = tmp->right;
        }
    }
    printf("can't find.");
    return NULL;
}

/* 値が最小のノードと、その親へのポインタを返す関数*/
struct btree *minimum(struct btree *root,struct btree **parent){
    while(1){            /*最も左の要素を探す。*/
        if(root->left){
            *parent = root;
            root = root->left;
        }else return root;
    }
}

/* 二つの構造体の「値（ここではdataとindex）」を入れ替える*/
void bt_swap(struct btree *one,struct btree *another){
    int tmp;
    tmp = one->data;
    one->data = another->data;
    another->data = tmp;

    tmp = one->index;
    one->index = another->index;
    another->index = tmp;
}

/*
 * ノードを削除する関数（本体）
 * 引数：削除対象とその親へのポインタ、根を指すポインタへのポインタ、
 * 注：nodeがrootのときは、parentもrootを指していないといけない。
 */
void del_node(struct btree *node, struct btree *parent,struct btree **root){
    struct btree **l_or_r;
    
    if (*root == node) l_or_r = root;
    else if(parent->left == node) l_or_r = &parent->left;
    else if(parent->right == node) l_or_r = &parent->right;
    else {
        printf("error: 'node' is not a child of 'parent'\n");
        return;
    }
/* l_or_rには、nodeがparentの左の子か右の子かによって
 * parentのleftまたはrightメンバ（struct btree構造体のポインタ）へのポインタを与える。
 * nodeが根であった場合は、根を指すポインタへのポインタを与える*/
    
    if(!node->left && !node->right){        /*子を持たない*/
        free(node);
        *l_or_r = NULL;
        
    }else if(node->left && node->right){    /*子を二つ持つ*/
        struct btree *min,*parent_min=node;
        min = minimum(node->right,&parent_min);
                /*自分の次に大きいノードと、その親を探す*/

        bt_swap(node,min);
        del_node(min,parent_min,root);
        
    }else{                                  /*子を一つ持つ*/
        if(node->left) *l_or_r = node->left;
        else *l_or_r = node->right;
        free(node);
    }
}

/*
 * 削除関数を呼び出す関数。
 * 与えられた条件から削除対象のノードとその親を検索し、
 * del_nodeに渡している。
 */
void exe_del_node(struct btree **root,int target){
    struct btree *parent,*tmp;
    tmp = search_btree_p(*root,target,&parent);
    del_node(tmp,parent,root);
}

以上で二分木に関する説明は終わります。難しかったと思いますが、理解できたでしょうか？

←ポインタ

home　　「C言語のはなし」トップ　　「パソコンのはなし」トップ