メモリの動的確保と自己参照構造体

■ 5-1 メモリの動的確保

これまでは、複数の学生のデータを管理するために構造体型の配列を用いました。これは、「学生の数は4名とする」などの条件が明らかであり、その数に大きな変動が無いためです。では、「ほとんどの場合は学生数は20名以内である。しかし、年に一度だけ10000名分のデータを扱うプログラム」を作成する場合はどうでしょう?配列の要素数を20にしてしまうと20名以上のデータが扱えないので年に一度問題が起こります。しかし、配列の要素数を10000とすると、普段は20名分のデータしか扱わないわけですからメモリの無駄になってしまいます。この問題は構造体の配列を使うところに原因があります。配列はプログラムソース中に「扱うデータの数」を決める必要があるのですが、 実際には「扱うデータの数」をあらかじめ決定出来ない、あるいは、場合によって数が異なることが多いのです。このような状況では、構造体を必要になった時に確保すれば問題を解決できるわけです。

このように、構造体や変数の領域をなどを、プログラムの実行中に必要になった時点で確保することをメモリの動的確保と呼びます。メモリを動的に確保するにはmalloc関数を用います。

void *malloc(size_t size);    
sizeバイト分のメモリ領域をプログラムに割り当て、割り当てられたメモリ領域のポインタ(メモリ領域の先頭アドレス)を返します。また、何らかの理由でメモリを割り当てることが出来なかった場合はNULLを返します。
使用例
#include <stdlib.h>   <--- このヘッダファイルが必要

char *p;   <--- 確保したメモリ領域のアドレスを格納するポインタ変数。
int *p2;

p = (char *)malloc(1000);  <--- 1000バイトのメモリ領域を確保。
p2 = (int *)malloc(4);     <--- 4バイトのメモリ領域を確保。

strcpy(p, "ABCDEFG");      <--- 確保したメモリ領域に文字列をコピー
*p2 = 100;                 <--- 確保したメモリ領域に数値をコピー

この例では1000バイトのメモリ領域と4バイトのメモリ領域を確保しています。ここで注意すべきは、(char *)などのキャスト演算子です。malloc関数の返り値はvoid *型、つまり、汎用ポインタ型です。汎用ポインタ型とは、「char型のポインタかint型のポインタかは分らないが、とりあえずポインタ型である」といった場合に用います。malloc関数はint型の変数のメモリ領域もchar型の変数のメモリ領域でも、あるいは、その他のデータ型の変数や配列のメモリ領域でも確保できます。従って、確保したメモリ領域のアドレスを返すこの関数の返り値のデータ型は汎用ポインタ型void *となります。

しかし、p = malloc(1000)では=の両辺のデータ型が異なるため、エラー(あるいは警告)となりコンパイルが正常に終了しません。そこで、malloc関数が返したポインタを(char *)というキャスト演算子を用いてchar型のポインタに変換するわけです。なお、図中の確保した領域の先頭アドレスはOSが自動的に決めるものであり、同じプログラムでも実行のたびに代わる可能性がありますし、プログラマーが指定することは出来ません。

確保した領域は、malloc関数の返り値を格納したポインタ変数を用いてアクセスします。strcpy(p, "ABCDEFG")は、ポインタpで指される領域に文字列"ABCDEFG"をコピーしますし、*p2=100はポインタp2で指される領域に100を代入します。

 

malloc関数を用いて確保した領域は不要になった時点で開放する必要があります。開放しなければ使用しないメモリ領域がプログラム中に残ってしまい、結局メモリの無駄遣いになります。動的に確保したメモリ領域の開放にはfree関数を用います。

void free(void *p);    
ポインタpで指された領域を開放します。この関数は返り値を持ちません。
使用例
#include <stdlib.h>   <--- このヘッダファイルが必要

char *p;   <--- 確保したメモリ領域のアドレスを格納するポインタ変数。

p  = (char *)malloc(1000);  <--- 1000バイトのメモリ領域を確保。

・・・・確保した領域を用いたプログラム・・・・

free(p);   <--- 確保した領域が必要なくなれば開放する。

演習問題5-1

以下の仕様を満たすプログラムを作成せよ。

(1) はじめに、入力する文字列の文字数を質問する。
(2)指定された数の文字を格納するメモリ領域をmalloc関数を用いて確保する。
(3)確保した領域に文字列を標準入力(キーボード)から読み込む。
(4)入力された文字列を表示する。

演習問題5-1の解答


malloc関数はint型やchar型だけではなく、構造体型(構造体)の領域も割り当て可能です。

使用例
......

typedef struct gakusei {
  char name[21];
  int kokugo;
  int suugaku;
  int rika;
  int syakai;
  int eigo;
} GAKUSEI;

GAKUSEI *ptr;

ptr = (GAKUSEI *)malloc(sizeof(GAKUSEI));
......

ここで、sizeof(GAKUSEI)は、GAKUSEI型のサイズをsizeof演算子を用いて求めています。sizeof演算子とはデータやデータ型のバイト数を求める演算で、例えば、sizeof(int)とすればint型のバイト数を、sizeof(x)とすれば変数xのバイト数を返します。


■ 5-2 自己参照構造体

構造体のリスト構造

構造体の配列ではなくmalloc関数を用いれば、必要になった時点で構造体のメモリ領域を確保できますのでメモリの使用に無駄がありません。しかし、5-1で述べたように、malloc関数を用いて確保したメモリ領域は、malloc関数の返り値を格納したポインタ変数を用いてアクセスします。とすると、1000個の領域を動的に確保する可能性があるときは1000個のポインタ変数をあらかじめ用意しておかなければならないのでしょうか?もし、そうであれば結局メモリの無駄になりますよね。

このような時は、自分自身を指すポインタを含む構造体である「自己参照構造体」を用います。自己参照構造体は同じ構造体型の変数を次々とつないでいき、データの鎖(リスト、あるいはチェイン)を作る時に用います。これにより、データをメモリの許す限り、かつ、効率的に管理できるだけでなく、データの追加や削除が非常に簡単に行えるようになります。

自己参照構造体を用いた構造体のリストを利用すれば、あらかじめ用意しておくメモリ領域は最初のデータに対応する分のみです。後は、必要になった時点でmalloc関数を用いて動的に確保すればよいわけです。自己参照構造体は以下のように定義します。

使用例
typedef struct gakusei {
  char name[21];
  int kokugo;
  int suugaku;
  int rika;
  int syakai;
  int eigo;
  struct gakusei *next;   <---- 次の要素へのポインタをメンバとしてもたせる。
} GAKUSEI;

この構造体型の変数を用いれば、下図のような構造体のリストが作成できます。これにより、「メモリが許す限り、学生のデータを効率的に管理する」ことが可能となります。最後の要素のメンバnextはNULLポインタ(ゼロを意味する)になります。

次のプログラムは、自己参照構造体を用いて構造体のリスト構造を実現したプログラムです。氏名、5教科の点数をキーボードから入力します。このプログラムではメモリが許す限り学生のデータを管理することが出来ます。データの入力は名前に"Q"を入力した時点で終了します。

使用例

     1  #include <stdio.h>
     2  
     3  /* 構造体型GAKUSEIの定義 */
     4  typedef struct gakusei{
     5    char name[11];
     6    int kokugo;
     7    int suugaku;
     8    int rika;
     9    int syakai;
    10    int eigo;
    11    struct gakusei *next;
    12  } GAKUSEI;
    13  
    14  
    15  main(){
    16    GAKUSEI start_dmy;            /* リストの先頭の構造体変数(データは入らない) */
    17    GAKUSEI *ptr;                 /* 作業用のポインタ */
    18    GAKUSEI *new_ptr;             /* 新しく確保した領域を指すポインタ */
    19    
    20    ptr = &start_dmy;             /* 作業用のポインタを先頭の要素を指すようにする */
    21    ptr->next = NULL;             /* 最初の要素のメンバnextをNULLに設定する */
    22    while(1){
    23  
    24      /*** 構造体1個分の領域を確保する ***/
    25      new_ptr = (GAKUSEI *)malloc(sizeof(GAKUSEI));
    26      if(new_ptr == NULL){
    27        printf("メモリを確保できませんでした。\n");
    28        exit(1);
    29      }
    30  
    31      /*** キーボードからの学生データの入力 ***/
    32      printf("氏名を入力してください:");
    33      scanf("%s", new_ptr->name);
    34      if(strcmp(new_ptr->name, "Q")==0){ /* 名前の入力がQだったら入力終了 */
    35        break;
    36      }
    37      printf("国語の点数:");
    38      scanf("%d", &new_ptr->kokugo);
    39      printf("数学の点数:");
    40      scanf("%d", &new_ptr->suugaku);
    41      printf("理科の点数:");
    42      scanf("%d", &new_ptr->rika);
    43      printf("社会の点数:");
    44      scanf("%d", &new_ptr->syakai);
    45      printf("英語の点数:");
    46      scanf("%d", &new_ptr->eigo);
    47  
    48      /*** 新しく確保した領域をリストの最後に繋げる ***/
    49      ptr->next = new_ptr;        /* これまでの最後の構造体のメンバnextを
    50                                     新しく確保した領域を指すように変更 */
    51      new_ptr->next = NULL;       /* 新しく確保した構造体のメンバnextを
    52                                     NULLに設定 */
    53      ptr = new_ptr;              /* 作業用のポインタを新し領域を指すよ
    54                                     うに変更 */
    55    }
    56  
    57    printf("\n\n\n");
    58    for(ptr = start_dmy.next ; ptr!=NULL ; ptr=ptr->next){
    59      printf("氏名:%10s   ", ptr->name);
    60      printf("国語:%3d   ", ptr->kokugo);
    61      printf("数学:%3d   ", ptr->suugaku);
    62      printf("理科:%3d   ", ptr->rika);
    63      printf("社会:%3d   ", ptr->syakai);
    64      printf("英語:%3d\n", ptr->eigo);
    65    }
    66  }

16行目〜18行目は、構造体のリストの最初の要素の構造体変数start_dmy、作業用のポインタptr、malloc関数で確保した領域を指すためのポインタnew_ptrを定義しています。start_dmy変数には実際に入力されたデータは格納されません。

20行目は作業用のポインタptrが先頭の要素start_dmyを指すようにしています。21行目はstart_dmyのメンバnextをNULLにしています。構造体変数のメンバnextがNULLであることにより、その要素の後にデータがないことを表しています。なお図中では、ポインタが構造体を指す様子を矢印で、NULLを斜線で表記しています。

22行目のループはこのままでは永遠に回りつづける無限ループですが、名前に"Q"が入力された時に終了します(34行目〜36行目)。

24行目〜29行目で一つの新しい構造体の領域を確保し、そのアドレスをポインタnew_ptrに代入しています。ここで、何らかの理由でメモリ領域を確保できなかった場合はエラーメッセージを表示してプログラムは終了します。

32行目〜46行目は、新しく確保した領域にキーボードからデータを入力しています。

48行目〜53行目は、上図の二つの構造体をつないでいます。具体的には、start_dmyの次の要素として新しく確保した領域を登録するために、ポインタptrで指された構造体変数のnextをnew_ptrとし、ポインタnew_ptrで指される構造体のnextをNULLにしています。さらに、次のデータの入力に備えてポインタptrをnew_ptrに変更しています。

このあと、23行目に戻ってもう一つ構造体の領域を確保します。

このようにして、"Q"が入力されるまで構造体を確保しつつデータを格納していきます。

58行目〜65行目のループは、上図のように格納されたデータをすべて表示するループです。まず、ポインタptrを構造体変数start_dmyuの次の要素(ichiroのデータが入っている構造体)を指すように変更して、その内容を表示し、ptrをptr->nextに更新します。この処理をptrがNULLになるまで繰り返します。


レポート課題5-1

上記の例題のプログラムは、データを入力された順番で構造体のリストに登録している。これを名前のアルファベット順に構造体のリストに登録するように変更せよ。