配列と構造体の動的確保

目次

今回の講義では，静的配列の復習を出発点として，プログラムの実行時に配列の長さを決定するための「配列の動的確保」について触れ，その際に得られるポインタの概念について学びます．その後，C言語の重要な概念である「構造体」について触れて，ポインタと構造体の両方を含むようなプログラムを組んでみることを目標とします．

ポインタと配列の動的確保

通常の配列

初めに，これまでに習ってきた「通常の配列」について復習します．ここでいう「通常の配列」は次のようにして定義したのでした．例えばaという名前の要素数5個の配列を定義したければ，

double a[5];

とします．このように定義することで， a[0], a[1], a[2], a[3], a[4] として，配列の各要素にアクセスすることが可能となります (配列の番号が 0 から始まることに注意！)．このような配列の定義（領域確保）の仕方を静的確保と呼んでいます．

ここでの「静的」の意味は，プログラムが「コンパイル」された時に配列の長さが決定しているということで，例えば上記の配列の長さを規定している「5」という数字はプログラムの実行時に変化することはありません．

静的確保の問題点

このような静的配列の定義では，事前に配列の要素数がわかっていることが必要です．しかし，実際のプログラムでは，配列の要素数が事前にわからない場合も多くあります．

一例として，以下では\(n\)次多項式 $f(x) = a_0 + a_1 x + \ldots a_n x^n$ の係数 $a_i$ をキーボードから入力した場合に，ある $x$ に対して $f(x)$ の値を計算するプログラムを以下に示しています．

#define MAX_ORDER 20
double a[MAX_ORDER];
int order;

int main(int argc, char **argv) {
    int i;

    printf("方程式の次数を入力してください：");
    scanf("%d", &order);
    if (order > MAX_ORDER) {
        printf("次数が高すぎます\n");
        exit(-1);
    }
    for (i = 0; i <= order; i++) {
        printf("%d次の項を入力してください：", i);
        scanf("%lf", &a[i]);
    }
    .....
    .....
    .....
}

double f(double x) {
    double s = a[order];
    for (int i = order - 1; i >= 0; i--) {
        s = s * x + a[i];
    }
    return s;
}

このプログラムでは，方程式の最大の次数を19次として，20個の要素を持つ配列を確保しています．そして，方程式の次数が20次以上の場合には，エラーを表示して終了するようにしてあります．

さて，方程式の次数が20次未満であることが確実な場合はこれでも良いのですが，方程式の次数が全くわからず，100次であったり，1000次であったりする場合にはどうすれば良いでしょうか．例えば，プログラム中のMAX_ORDERを1000に変更すれば，999次までの方程式に対応できるようになりますが，その場合でも，1000次の方程式が入力された場合にはどうにもなりません．

また，1000個もの配列を確保しておいて，もし入力された方程式が2次方程式であったりした場合，997個もの配列の要素（メモリ）が無駄になってしまいます．プログラムの規模が大きくなったときに，そのような無駄を随所でしていると，全体の動作速度やメモリ使用量に支障をきたします

そこで，このような場合には，動的確保と呼ばれる方法が用いられます．動的確保とは，事前に配列の大きさを定めておくのではなく，プログラムの実行中に，必要なサイズのメモリ領域を確保し，配列として利用するものです．

この動的確保を行った際には，必然的に配列の先頭の位置を表すポインタが現れます．このポインタのC言語初学者の多くがつまづく概念ですので，基礎に立ち返って見ていきましょう．

ポインタと変数

ポインタを理解する上で重要となるのは，ポインタは「変数」の一つでありながらも，その指し示すものがアドレスであるということです．しかもこのアドレスには通常，別の「変数の値」が保存されていますので，そこが理解を難しくしています．

最初に通常の変数の宣言・定義について見てみましょう．

int a = 100;

と宣言した時，プログラムの裏側ではメモリ上のとあるアドレスに値「100」という値が格納されます．アドレスというのは，コンピュータのメインメモリ上のどこに実際のデータが格納されているかを表す「番地」のようなもので printf により，その場所を実際に確認することができます．

int a = 100;
printf("%p\n", &a);

上記のプログラムでは&aがprintfの引数に渡されていますが，これはポインタでない変数aの値が格納されているポインタのアドレスを表すものです．このように，今まで通り「変数」を定義した場合も，裏ではアドレスに変数が割り当てられており，変数とポインタは表裏一体であることが分かります．

実は，この&aのように変数が格納されているアドレスを取得するコードはscanfを使用するときにも現れていました．

int a;
scanf("%d", &a);

これは，ターミナル上で入力された文字列を整数型の数値 (%dで指定) に変換した後で， 変数aのアドレスにそれを代入してください，という命令になります．

ポインタが実際に用いられるのは変数の値ではなく，その値がどこに保存されているかが重要となるような場面です．例えば，配列に格納される変数は通常メモリ上の連続したアドレスに保存されるため，配列の先頭のアドレスだけを保存しておけば，欲しい値の配列上の位置と各要素のサイズから，その値が格納されているアドレスを計算できるというわけです．そのため，C言語における配列のデータはポインタを用いて表現されています．

注意が必要なのはポインタが表すものはあくまでアドレスであって，ポインタの用途は配列には限らないということです．例えば，複数のポインタの間で変数の更新を共有することも可能です．実際に，下記のプログラムで，その挙動を確認してみましょう．

int main(int argc, char **argv) {
    int a, b;
    int *p;          // ポインタ宣言
    
    p = &a;          // ポインタにaのアドレス指定を代入
    *p = 100;        // ポインタの指すアドレスに値を代入
    b = *p + 1;
    
    printf("%d %d %d\n", a, b, *p);
    
    p = &b;          // ポインタにbのアドレスを代入
    printf("%d %d %d\n", a, b, *p);
}

ポインタの宣言はint *pのように行い，p = &aでアドレスを指定しています．また，アドレスを再指定すると，*pの値が変わります．このようにポインタは複数の場所で違う名前をつけて，同じ変数を参照するという用途にも使うことができます．それでは実際に下記の練習問題でアドレスの変化を見てください．

練習問題

上記プログラムにおいてprintfにおいて，値ではなく，a, b,*pのアドレスを表示して比較せよ．

出力結果例

0x7ffee1a9d6a4 0x7ffee1a9d6a0 0x7ffee1a9d6a4
0x7ffee1a9d6a4 0x7ffee1a9d6a0 0x7ffee1a9d6a0

なお，現代のコンピュータは64ビットのメモリアドレスを用いることが一般的であるため，上記のようにアドレスは大きな整数になることが多いです (最初の0x は数字が16進数であることを表しています)．通常の静的な変数の宣言 ( int a など) では，変数のアドレスは一定のルールにしたがって自動的に決定されます (決定方法が気になる人は「スタック」と「ヒープ」というメモリ管理の方式について調べてみましょう)．

静的配列とポインタ

変数の配列は，同時に複数変数を宣言するのと同様，ポインタにより，同時に複数のアドレスを宣言できます．int a [2]と宣言すると，a[0]とa[1]のアドレスができ，整数を代入することができるようになります．

この場合，aはint*型，すなわち整数型のポインタであり，aという名前は配列の先頭，すなわちa[0]が格納されたアドレスを指すポインタになります．

printf("%p\n", a);      // a[0]のアドレスが表示される
printf("%p\n", &a[0]);  // 上と同じ結果になる

以下は，配列のポインタを用いたシンプルなプログラムです．



1
2
3
4
5
6
7
8
9
10
11
12



# include <stdio.h>

int main(int argc, char **argv) {
    int a[2];     // aという変数名は配列の先頭のアドレスを意味するようになる
    int *p;

    p = a;        // aは配列の先頭を表すポインタ. そのままポインタに代入できる
    a[0] = 1;
    *(p+1) = a[0] + 1;

    printf("%d, %d, %d, %d", a[0], a[1], *p, *(p+1));
}

この実行結果は次のようになり，ポインタにより変数の更新が共有されていることが分かります．

1, 2, 1, 2

コード中のコメントにも示した通り，int a[2]のように定数の長さで配列を宣言すると，aという変数名は配列の先頭の値のアドレスを意味するようになります．このような長さが変わらない (変化しないことを別の言葉で静的という) 配列のことをプログラミングの用語では静的配列 (static array) と呼びます．

aが配列の先頭のアドレスを指すことを考えるとp = aの挙動はp = &a[0]と同じになります．また，ポインタに対する整数の足し算は，連続したアドレス上で次の変数が格納されたアドレスを指すポインタを得ることに対応します．今pはint型のポインタで宣言されているため，1を足したときにはアドレスがintの大きさである 4バイト分だけ移動します．この動作を以下の練習問題で実際に確認してみましょう．

練習問題

上記プログラムで printf を用い，値ではなく a[0], a[1], *p, *(p+1) のアドレスを表示して比較せよ．

この際，下記に値とポインタの宣言方法による，変数値とアドレスの取得方法をまとめたので参考にすること．

宣言方法 アドレスの表記方法 変数の表記方法
単一の変数 (int a) &a a
単一のポインタ (int *p) p *p
配列 (int a[10]) 先頭: a , 要素: a + 2, &a[2] a[2]

配列の動的確保とメモリ解放

ここまでのプログラムでは配列の個数を指定して int a[10] のような宣言を行ってきました． これを静的配列と呼ぶことは前述の通りですが，この静的配列にはいくつかの問題があります．

まず，静的配列はその名前の通り，要素の数を途中で変更することができません．そのため，何らかの計算結果を使って配列の要素数を，その時々に応じて決めることができず，あらかじめ大きめの要素数を指定しなくてはなりません． また，静的配列はメモリ管理のやり方の問題があり，極端に大きなサイズを取ることができません (気になる人は配列の要素数を大きなものに変更してみましょう)．

このような問題を解決するために用いられるのが「メモリの動的確保」です．また，配列に限らず動的にメモリ領域を確保することをメモリの「動的確保」と言ったりもします．

配列の動的確保

このような動的確保を行うための手順は，以下の通りです．

  1. <stdlib.h>をインクルードする（動的確保のための関数ヘッダが定義されている）．
  2. 配列の名前を定義する（正確には，配列用のポインタを宣言する）．
  3. 配列の要素数 \(n\) がわかったら calloc 関数を用いて配列を確保する．

calloc 関数は以下のように二つの引数を取り，第1引数が配列の要素数，第2引数が一つの要素の大きさを表します．例えば int 型で要素数が10の配列を動的確保する場合には，

int *a = (int*)calloc(10, sizeof(int));

のように確保を行います．

またcalloc関数と似た関数にmalloc 関数があります．これは配列の要素の大きさとは関係なく，動的確保するメモリのサイズを直接指定するもので，

int *a = (int*)malloc(10 * sizeof(int));

とすると，上記の calloc を用いた例と ほぼ 同じ動作となります．この二つはどちらもメモリ領域を確保する，という点では同じですが calloc 関数はメモリを確保した後，配列の各要素を0で初期化するという違いがあります．ただし，ここでいう0での初期化はあくまでメモリ上のビットを0に初期化するもので，構造体などが要素の場合には必ずしも値が0になることは保証されていません．

なお，動的確保において，空いているメモリ量が足りずに，配列用のメモリ領域を確保できない場合もあります． 領域が確保できない場合に，配列に強引に書き込みを行うと，致命的な現象（OSの暴走など）を引き起こすので， 動的確保をした場合には，領域の確保が成功したかどうかを必ず確かめなくてはなりません

領域の確保に失敗すると，calloc関数は NULLポインタと呼ばれるものを返してきますので，上の例でaに代入されている calloc の返値が NULL であるかどうかを確認し， NULL である場合には，エラー処理を行うことが重要です．

エラー処理の例

if (a == NULL) {
    printf("[ ERROR ] メモリを確保できませんでした\n");
}

メモリの解放

通常利用している変数（配列に限らず，普通に定義して普通に使う変数）は，定義するとそのためのメモリ領域が自動的に確保され，変数が使い終われば 自動的に領域が解放されます．しかし，配列を動的に確保した場合，その配列用のメモリは，プログラム中で明示的に解放しない限り，決して解放されることはありません． そのため，動的確保したメモリは，使い終わったら必ず解放することが必要です．プログラム中で確保したメモリ領域を開放しないままプログラムを終了してしまうと，俗に言う「メモリリーク」の状態になります．OSが不調になる原因の一つです．

ポインタaが指すアドレスに確保されたメモリを解放するにはfree(a)と書きます．以下のプログラム例を参考に，配列の動的確保とメモリの解放について確認してください．

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

int main(int argc, char **argv) {
    int a[2];
    int *p;

    p = (int*)calloc(2, sizeof(int));
    a[0] = 1;
    a[1] = 2;
    *p = a[0];
    *(p+1)=a[1];
    printf("%d, %d, %d, %d", a[0], a[1], *p, *(p+1));
    free(p);
}

メモリの解放をせずに動的確保を続けていくと，メモリ不足に陥り悲惨な結果となることが多い．動的確保したらfree() することを絶対に忘れないようにすること．

練習問題

同じく上記プログラムのprintfにおいて，値ではなくa[0], a[1], *p, *(p+1)のアドレスを表示して比較する．

結果はaとpではまったく違うアドレスになっていると思います．これは静的配列が連続的な領域に順々に確保されていくのに対して， 動的確保が利用可能な離れたメモリ領域に，その都度メモリ確保を行っていることを示す一例と言えます．

次に前回の課題において，自由に次数を入力できるように改造しましょう．配列のポインタを使用することで，入力により，個数も指定できるようにしたものです．下記，参考にしてください．

//（主要部分のみ）
#include <stdio.h>
#include <stdlib.h>

// 関数のプロトタイプ宣言
double f(double x, double *a, int order);

int main(int argc, char **argv) {
    int order;

    printf("方程式の次数を入力してください：");
    scanf("%d", &order);
    
    double *a = (double*)calloc(order + 1, sizeof(double));
    if (a == NULL) {
        printf("配列用の領域が確保できませんでした\n");
        exit(-1);
    }
    
    for (int i = 0; i <= order; i++) {
        printf("%d次の項を入力してください：", i);
        scanf("%lf", &a[i]);
    }
    ...
    ...
    ...
    
    free(a);
}

double f(double x, double *a, int order) {
    double s = a[order];
    for (int i = order - 1; i >= 0; i--) {
        s = s * x + a[i];
    }
    return s;
}

配列の動的確保: まとめ

あらためて配列の動的確保の手順をまとめます：

その1: ファイル冒頭で stdlib.h をインクルードする（動的確保のための関数ヘッダが定義されている）．
その2: 配列の名前を定義する（正確には，配列用のポインタを定義する）．
その3: 配列の要素数 n がわかったら，要素数分の配列を確保する．メモリの確保に成功したかどうか確認する．
その4: 使い終わったら解放する

課題1 (配点：3点)

配列の動的確保の仕組みを利用して，任意の個数の実数値をキーボード (またはファイル) から読み込み，平均と標準偏差を計算するプログラムを作成せよ．

構造体

構造体は一言で言えば，複数の肩(int, float, char* など)をまとめた新しい型です． 構造体として定義された型は，原則，元々用意されている int などの型と同じように使うことができます． それでは，以下のプログラムで簡単な構造体の使い方について見てみましょう．

※自分でタイピングを行い写して動作確認のこと

#include <stdio.h>

// studentという名前の型構造体を定義
typedef struct {
    int id;
    double score;
} student;

int main(int argc, char **argv) {
    student taro;         // taroをstudent型で定義
    taro.id =123;         // taroの要素であるidに代入
    taro.score = 0.75;    // taroの要素であるscoreに代入
    printf("%d, %lf", taro.id, taro.score); 
}

上のプログラムで使われている typedef は既存の型に新しい名前をつける役割を持っていて，例えば，

typedef int integer;

のようにして int 型に integer という新しい名前をつけることもできます．構造体に対しては，

typedef struct {
    ...
} name_of_struct;

のように書いて，名前を与えます．C言語の拡張であるC++では

struct name_of_struct {
    ...
};

のように書くこともできますが，この書き方はC言語では許されていないので注意しましょう．実際に，構造体を使用する際は，

student taro;

と宣言することで taro という名前の student 型変数が宣言され，その構成要素であるint型のidとdouble型のscoreが自動的に生成されます．プログラミングの用語では id や double などの構成要素のことをメンバ変数やフィールドなどと呼びます．

構造体のメンバ変数には

seimitsu.kakou
seimitsu.keisoku

というように，変数名と要素名をドットでつなげることでアクセスすることができます．また，構造体の型で宣言された変数には同じ構造体型の変数を代入することができます (メンバ変数にポインタを含む場合には注意が必要)．

student taro, hanako;
taro.id = 10;
taro.score = 20.0;
hanako = taro;  // hanako.idは10, hanako.scoreは20.0になる

ただし，全てが int などの型と同じように扱える訳ではなく，

if (taro == hanako) {
    ...
}

のような比較はコンパイル・エラーとなります．

構造体の配列

また構造体に対しては通常の型と同様に配列を定義することもできます．詳しくは解説しませんが以下の例を参考に動作を確認してみてください．

自分でタイピングを行い写して動作確認のこと

静的配列を用いる例

#include <stdio.h>

typedef struct {
    int id;
    double score;
} student;

// 静的配列の宣言
#define N 10
student students[N];

int main() {
    // 値を代入
    for (int i = 0; i < N; i++) {
        students[i].id = i;
        students[i].score = i * 10.0;
    }
    
    // 結果の出力
    for (int i = 0; i < N; i++) {
        printf("student #%d: %f\n", students[i].id, students[i].score);
    }
}

メモリの動的確保を用いる例

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

typedef struct {
    int id;
    double score;
} student;

int main() {
    // メモリの動的確保
    int n = 10;
    student *students = (student*)calloc(n, sizeof(student));

    // 値を代入
    for (int i = 0; i < n; i++) {
        students[i].id = i;
        students[i].score = i * 10.0;
    }

    // 結果の出力
    for (int i = 0; i < n; i++) {
        printf("student #%d: %f\n", students[i].id, students[i].score);
    }

    // メモリの解放
    free(students);
}

ポインタをメンバ変数とする構造体

(a) 構造体の中にポインタ (動的確保された配列) を持つ場合

構造体では，任意の型をのまとまりを定義できますので，構造体の中にポインタを入れることができます．この場合，構造体の中の要素の型，要素数を定義することができます．構造体を宣言するだけでは，構造体のメンバであるポインタまでは初期化されないことに注意してください．

自分でタイピングして動作確認をすること

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

typedef struct {
    char name[32];
    int *subjects;
} student;

int main() {
    student taro;
    sprintf(taro.name, "Taro");  // nameを"Taro"にする

    // subjectsのメモリ確保と値の代入
    int n = 2;
    taro.subjects = (int*)calloc(n, sizeof(int));
    taro.subjects[0] = 100;
    taro.subjects[1] = 80;

    // 結果の出力
    printf("Total (%s): %d\n", taro.name, taro.subjects[0] + taro.subjects[1]);

    // メモリの解放
    free(taro.subjects);
}

(b) 構造体をポインタで宣言した場合

structで宣言された型は，int, doubleなどと同じ扱いが可能なので，構造体のポインタを宣言することが可能です．この時にはメンバにアクセスする方法が先ほどと変わります．今まで構造体が値として宣言されていた場合には，

student taro;
taro.id = 10;

のようにドットを使ってアクセスをしていましたが，ポインタとして宣言された場合には，

student *taro = (student*)calloc(1, sizeof(student));
taro->id = 10;

のように -> (アロー演算子) を使ってアクセスをします．それでは，以下のコードで実際の動作を確認してみましょう．

自分でタイピングして動作確認をすること

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

typedef struct {
    char name[32];
    int *subjects;
} student;

int main() {
    // 構造体のポインタを準備
    student taro;
    student *taro_ptr;
    taro_ptr = &taro;

    // アクセス方法が値とポインタで異なることに注意
    sprintf(taro_ptr->name, "Taro");  // nameを"Taro"にする

    // subjectsのメモリ確保と値の代入
    const int n = 2;
    taro_ptr->subjects = (int*)calloc(n, sizeof(int));
    taro_ptr->subjects[0] = 100;
    taro_ptr->subjects[1] = 80;

    // 結果の出力
    printf("Total (%s): %d\n", taro_ptr->name, taro_ptr->subjects[0] + taro_ptr->subjects[1]);

    // メモリの解放
    free(taro.subjects);
}

なお，このアロー演算子は，実際には (*taro).id のように書くことと同様の働きをしますが，より短く表記できるアロー演算子が一般的に用いられます．

(c) ポインタをメンバに持つ構造体の動的確保

それでは，ここまでの総まとめとして，構造体がメンバにポインタ (動的確保された配列) を持つ場合に，その構造体の動的確保を行ってみましょう．メモリ確保やメモリ解放のコードが多くなり，やや煩雑になってはいますが，基本はこれまでに学んだことの組み合わせであることが分かります．

自分でタイピングして動作確認をすること

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

typedef struct {
    char name[32];
    int *subjects;
} student;

int main() {
    int n_student = 2;
    int n_subject = 2;

    // メモリ領域の確保
    student *students = (student*)calloc(n_student, sizeof(student));
    for (int i = 0; i < n_student; i++) {
        students[i].subjects = (int*)calloc(n_subject, sizeof(int));
    }

    // 名前の設定
    sprintf(students[0].name, "Taro");
    sprintf(students[1].name, "Hanako");

    // subjectsのメモリ確保と値の代入
    students[0].subjects[0] = 60;
    students[0].subjects[1] = 90;
    students[1].subjects[0] = 75;
    students[1].subjects[1] = 95;

    // 計算
    int sum = 0;
    for (int i = 0; i < n_student; i++) {
        for (int j = 0; j < n_subject; j++) {
            sum += students[i].subjects[j];            
        }
    }

    // 結果の出力
    printf("Total : %d\n", sum);
    
    // メモリの解放
    for (int i = 0; i < n_student; i++) {
        free(students[i].subjects);
    }
    free(students);
}

課題2 (配点：3点)

上記のプログラムを改造し，人数，科目数を入力し，その後，名前，各科目の点数を入力すると，それぞれの学生あたりの合計，平均点と全体の合計，平均点を計算するプログラムを作成せよ．(名前を読み込む部分は，各自で考えること．入力する名前の文字数が多い場合については考慮せず，最大8文字ぐらいであると考えて良い）

出力例 (出力の仕方は工夫すること）

Input number of students: 2
Input number of subjects: 2
Input name of No. 1: taro
Input name of No. 2: hana
Input score of taro's subject0: 60
Input score of taro's subject1: 90
Input score of hana's subject0: 75
Input socre of hana's subject1: 95
(ここまで入力部分）

taro: Sum 150, Average=75.000
hana: Sum 170, Average=85.000
Total: Sum 320, Average=80.000

可変長配列

冒頭では静的配列の問題点を述べた上で，配列の動的確保について紹介をしました．配列の動的確保はプログラムを実行中に配列の長さが変わらない場合に有効で，例えば，$N$次方程式を解くプログラムなら，方程式を解いている最中に式の次数が変化することはありません．

ところが，実際の応用においては，プログラムを実行している最中に配列の長さを変化させなければならない場合があります．例えば，「しりとり」のプログラムを作っていて，最後に今までに入力された言葉を表示するようなものを作りたいとします．この場合，しりとりがいつまで続くかは分からないので，最初に$N = 1000$のように適当な長さで配列を静的確保しておくわけにも行きません．かといって方程式の例のように「これからはじまるしりとりは100語で勝敗が付きます」と最初に宣言するわけにも行きません．

このような場合には，長さが動的に変化し，要素を任意の数だけ (メモリが許す限り)追加できるような配列があれば便利で，このような配列のことを可変長配列 (variable length array)と呼びます．一方で，静的配列や動的確保された配列は長さが固定なので固定長配列と呼ばれます．

以下ではここまでに学んだポインタと構造体を利用して可変長配列を作成してみましょう．

可変長配列の種類

可変長配列には，その実装の仕方によって，配列リスト (array list)と連結リスト (linked list)の二つに分けられます．例えば，C++においては配列リストは std::vector型で，連結リスト (の一種である単方向リスト)はstd::forward_list型として与えられています．なお，配列リストと言う呼び方についてはJavaにおける実装であるArrayListから説明のためにつけた名称であり，あまり一般的な呼び名ではないことに注意してください．

配列リスト

配列リストは，内部に長さを仮決めした配列を備えていて，もし要素数が仮決めした長さより大きくなったら，配列をより大きいサイズで動的確保し直すことで可変長配列を実現します．

例えば，最大32文字の文字列 (char[32]型)を格納する配列リストを構造体で表すとすると

typedef char word[32];

typedef struct {
    int size;  // 現在の配列の要素数
    int length;  // メモリが確保されている要素数
    word *data;  // 配列の本体
} array_list;

のようになります．上記の例では予めchar[32]型をtypedefによって別名wordとしていることに注意してください．配列を初期化する関数 array_list_initは，上記構造体のdataに対して適当な長さでメモリを動的確保しして，その時の長さをlengthに保存するというものです．一方で，sizeは現在の要素数を表すものとして，最初は0で初期化しておきます．

void array_list_init(array_list *list) {
    int init_length = 4;
    list->data = (word*)malloc(sizeof(word) * init_length);
    list->size = 0;
    list->length = init_length;
}

C言語のようなクラスという機能を持たない手続き型のプログラミング言語 (クラス機能を持つものを対比としてオブジェクト指向型言語という)では，構造体を操作する関数は必ず構造体を引数に取らなくてはなりません．この場合，引数として与えられた構造体自体を変化させる必要があるので，引数の型は値型ではなくポインタ型で与えられなければならないことに注意してください．

例えば，配列リストを初期化する目的でarray_list_init関数を呼び出すには，以下のように&を使って値型の変数をポインタ型として関数に入力する必要があります．

array_list list;         // 宣言だけで初期化されていない
array_list_init(&list);  // 初期化処理を呼び出す

次に要素を追加する関数array_list_addについて見てみます．今，配列中に$N$個の要素が格納されているとすると，次に加えられる要素は$N+1$番目の要素になります．通常C言語の配列は0から配列の番号が始まりますので，$N+1$番目の要素が挿入される配列の番号は長さと同じ$N$になります．

一方で，もしsizeがlengthと同じになっていたら，それ以上は現在確保されているメモリには要素が入りませんので，新たに配列を確保し直す必要があります．そこで，別の変数としてサイズを大きくして動的確保した配列に対して，現在の要素を移動し，その上で dataのメモリを置き換えます．この際，元々動的確保されていたメモリを解放するのを忘れないようにしてください．

void array_list_add(array_list *list, word item) {
    if (list->size >= list->length) {
        // 2倍の大きさの配列を確保
        word *new_data = (word*)malloc(list->length * 2 * sizeof(word));
        // データを移行する
        memcpy(new_data, list->data, list->length * sizeof(word));
        // メモリの解放
        free(list->data);
        // ポインタの付け替え
        list->data = new_data;
        list->length *= 2;
    }

    // 文字列は = ではコピーできないことに注意する
    memcpy(list->data[list->size], item, sizeof(word));
    list->size += 1;
}

最後に，使い終わった配列リストに対しては，次のarray_list_free関数により，その構造体のdataに動的確保されたメモリを解放しておきます．

void array_list_free(array_list *list) {
    free(list->data);
    list->size = 0;
    list->length = 0;
}

課題3 (配点:3点)

上記の配列リストの説明を基にして，簡単な「しりとり」プログラムを作成せよ．このプログラムでは，

なお，ここでいう「しりとりが成立している」とは，次の3つの条件を満たすこととする

入出力の例

next word?
apple
next word?
elephant
next word?
train
ERROR: your word "train" ended with "n"!
WORDS: apple -> elephant -> train

補足

文字列の最後の文字を調べるときには，strlen関数を使って文字列の長さ$n$を調べて，その上で$n-1$番目の文字を取り出せば良い (0から文字のインデックスが始まっているとする)．

また，文字同士 (文字列同士ではなく)を比較するにはchar型での比較，例えば，

// char型はシングルクオーテーション
if (str[n - 1] == 'n') {
    // 最後の文字が「n」だったときの処理
}

のように書けば良く，また文字列同士の比較については strcmp関数を使って

// strcmpの戻り値が0の時に文字列が等しい
if (strcmp(str1, str2) == 0) {
    // str1とstr2が同じ時の処理
}

のように書けば良い．

ヒント

どうしてもできない場合は下のボタンをクリックして，テンプレートコードを確認する．必要な箇所(????となっている部分)を埋めてプログラムを作成する

int main() {
    array_list list;
    array_list_init(&list);

    word w;
    for (;;) {
        bool valid = true;
        printf("next word?\n");
        scanf("%s", w);

        // 単語が空なら単語入力からやり直す
        // ????

        // 単語が「n」で終わっていたら終了
        // ????

        // 最後の単語の最後の文字と新しい単語の最初の文字が一致するか？
        if (list.size > 0) {
            // ????
        }

        // 同じ単語がないか？
        // ????

        // 単語を追加
        array_list_add(&list, w);        

        // しりとりが上手くいかなければループを抜ける
        if (!valid) {
            break;
        }
    }

    printf("WORDS: ");
    for (int i = 0; i < list.size; i++) {
        printf("%s", list.data[i]);
        if (i != list.size - 1) {
            printf(" -> ");
        }
    }
    printf("\n");

    // メモリ解放
    array_list_free(&list);
}

発展: 連結リスト

先ほど紹介した配列リストはプログラムが比較的単純であり，それでいて通常の配列のように直接配列要素にアクセスできる(専門的な言葉でランダムアクセス可能，という)という大変優れた性質を持っています．

その一方で弱点もあって，配列リストは要素の削除が苦手です．配列リストは，その先頭でも末尾でもない要素を削除する際，削除される要素より後ろの要素を前に詰める処理をする必要があります．

例えば，安直には以下のような関数により要素の削除を行う必要があります．

// n番目の要素を削除する関数
void array_list_remove(array_list *a, int n) {
    // 指定されたインデックスが不正
    if (a->size <= n) {
        return false;
    }

    // n番目以降の要素を1つずつ詰める
    for (int j = n + 1; j < s->size; j++) {
        list->data[j - 1] = list->data[j];
    }
    list->size -= 1;
}

ですが，このプログラムを見て分かる通り，この処理には最大で配列の長さの回数のコピー処理が発生するため，配列要素が巨大な構造体である場合などには非常に効率が悪くなります．また，データを中間に挿入する場合も同じで，最大で配列長さ分のコピーが必要になるため，配列リストは頻繁にデータの挿入や削除が起こるようなケースには向いていません．

そこで，データの追加と削除をバランス良く高速に行える配列として連結リストを使います．連結リストにはいくつかの種類がありますが，ここでは最も単純 (といっても配列リストよりは複雑) な単方向リストについて見ていきます．

連結リストの定義

単方向リストは配列の要素が「ノード」に対応しており，各ノードは配列に格納される値と，次のノードへのポインタを備えるものとします．

typedef struct list_node_ {
    word value;
    struct list_node_ *next;
} list_node;

このノードを初期化を簡単にするため，以下のようなノード作成用の関数を用意しておくと良いかもしれません．

list_node *create_node(word w) {
    // メモリの確保
    list_node *node = (list_node*)malloc(sizeof(list_node));
    // 値をノードにコピーする
    memcpy(node->value, w, sizeof(word));
    // 次のノードへのポインタはまだない
    node->next = NULL;

    return node;
}

このノードを後ろに要素が付け加えられることに連結して増やしていくことで，連結リストが定義されます．そのため，単方向リスト自体 (ノードではなく)を表す構造体は，リストの最初の要素 (ルートと呼ぶ)とはリストの長さだけを持つ構造体として定義されます．

typedef struct {
    int size;
    list_node *root;
} linked_list;

リストに何も入っていない状態ではrootがNULLになっていて，サイズは0であると考えられますので，初期化関数は次のようになります．

void linked_list_init(linked_list *list) {
    list->size = 0;
    list->root = NULL;
}

ここまでで連結リストの定義と初期化は完了です．

連結リスト: 要素の追加，削除，メモリの解放

ここからは連結リストに対する要素の追加，要素の削除，そしてメモリの解放について見ていきます．おそらく，これまでにみなさんが見てきたプログラムの中でも複雑な部類に入ると思いますので，ひとつひとつ注意深く見てみてください．

まず，リストに要素を追加するlinked_list_add関数を次のように定義できます．

void linked_list_add(linked_list *list, word w) {
    // 新しい要素を作成して，値をコピーする
    list_node *new_node = create_node(w);
    
    // 終端の要素を探して，値を設定後，ポインタを付け替える
    if (list->root == NULL) {
        list->root = new_node;
    } else {
        list_node *node = list->root;
        while (node->next != NULL) {
            node = node->next;
        }
        node->next = new_node;
    }
    list->size += 1;
}

この関数では，先ほど定義しておいたcreate_node関数を使って，新しく付け加えるノードを作成し，その後でノードの末尾に当たるポインタにそのノードを付け加えています．

この際，list->rootがNULLである場合とそうでない場合とで，プログラムが分かれています．一見，これはelse文の方にある内容だけで十分のようにも見えますが，

list_node *node = list->root;  // rootはNULLであるとする
printf("%p\n", node);          // 「000...0」と出力される
node = new_node;               // ポインタの付け換え
printf("%p\n", node);          // 0でない値が出力される
printf("%p\n", list->root);    // 「000...0」と出力される
list->root = new_node;         // ポインタを直接付け替え
printf("%p\n", list->root);    // 0でない値が出力される

のように，list->rootに格納されるアドレスを変更するためには，C言語においてはポインタを別の変数に取ることなくlist->root = new_nodeの形で変更する必要があります (C++には参照という考え方があり，この部分をもっと簡単に書ける)．

次に，配列要素が特定の値である場合に，その要素をリストから取り除くlinked_list_remove関数を見てみましょう (2つ以上同じ値が存在しないことを仮定している)．

void linked_list_remove(linked_list *list, word w) {
    if (list->root == NULL) {
        // 要素が存在しない
        return;
    }

    if (strcmp(list->root->value, w) == 0) {
        // 最初の要素を削除するならrootを置き換える
        list_node *rem = list->root;
        list->root = list->root->next;
        list->size -= 1;
        free(rem);
        return;
    }

    list_node *node = list->root;    
    while (node->next != NULL) {
        // 次の要素が該当の値を持つかをチェック
        if (strcmp(node->next->value, w) == 0) {
            // ポインタを付け替える
            list_node *rem = node->next;
            node->next = node->next->next;
            free(rem);
            list->size -= 1;
            break;
        }
        node = node->next;
    }
}

ここでも最初の要素が存在する場合と，そうでない場合で処理が分かれています．このように分けている理由は linked_list_addのときと同じです．もし要素が1つしかなければ，list->rootをNULL，サイズを0にすることで，要素が何も入っていない状態に戻します．

そうでない場合には，「削除するノードをnextに持つノード」を見つけ出して，そのノードのnextを「削除するノードのnext」に置き換えれば，連結リスト内のノードの接続関係の変化により，ノードが削除されたことになります．この際，削除するノードのメモリ解放を忘れないようにしてください．

最後に連結リストのメモリ解放linked_list_freeでは，以下の要領で各ノード構造体に対するメモリを順々に解放します．

void linked_list_free(linked_list *list) {
    list_node *node = list->root;
    while (node != NULL) {
        // 処理の順番に注意すること
        list_node *curr = node;
        node = node->next;
        free(curr);
    }
}

上記のプログラムにおいては，各ノードを一時変数currにとって，次のノードが分かる状態にしたあとで，各ノードのメモリを解放していることに注意してください．

課題4 (配点:1点)

課題3で作成した「しりとり」プログラムと同様のものを連結リストでも作成し，以下の機能を付け加えよ．

入出力の例

next word?
apple
next word?
elephant
next word?
tomato
next word?
olive
next word?
elephant
next word?
train
ERROR: your word "train" ended with "n"!
WORDS: apple -> tomato -> olive -> elephant -> train

上記の例ではelephantという単語が2回登場しているが，1回目に登場した箇所 (appleとtomatoの間)から2回目に出現した箇所に単語が移動していることが分かる．

補足: プログラミングスタイル（書式）について

自分一人でプログラムを書き，それを自分一人で利用するだけであるならば，どのようなスタイルでプログラムを書いてもかまいません．しかし，他人と共同で作業する場合や，自分が書いたプログラムを他人が利用，もしくは，変更するような場合には，標準的なスタイルで書いておかないと，読む人がとても苦労します．もちろん，その人なりの書き方があっても構いませんが，あまりに独特な書き方をすると，他の人が読めなくなってしまうので注意が必要です． 以下に，プログラムを書く上で（スタイルに関して）守るべき事項をあげておきます．

基本的なルール

1. プログラムの中では書式は統一する

自分なりに書き方を決めたら，その書き方で統一する．プログラムの場所によって，書き方が違うと，他人が読むときに負担となる．代表的な書き方にはK&R方式, GNU方式, Google方式などの方式 (coding conventionという) があるので，インターネット等で調べてみると良い．

2. インデントとブレースのスタイルは統一する

処理単位ごとに，インデント（字下げ）を施す．この際の字下げの文字数などは統一する．また，処理単位の始まりと終わりを示すブレース ({ }) を書く位置なども統一する．

3. 分かりやすく簡潔な変数名，関数名を用いる

局所的にしか使われない変数などをのぞいて，なるべく見て意味のわかるような変数名をつけておくことが望ましい．かといって，変数名が長すぎると，逆に読みづらくなるので，その辺のバランスを考えること．

4. マジックナンバーは使わない

プログラム中に直接書き込まれた定数は，マジックナンバーと呼ばれる．マジックナンバーの存在は，プログラムの可読性や保守性を著しく低下させる．特殊な場合をのぞいて，定数には必ず意味があるはずなので，define 文などを使って，定数に名前をつけて定義しよう．

5. 適切なコメントをつける．

プログラムには，適切なコメントをつけることが理想である．各関数の意味や動作，変数の意味，処理の流れなどに対してコメントをつけることで，プログラムが大幅に読みやすくなる．ただし，コメントをつけすぎると，かえって読みづらくなるので，ほどほどに．

Cプログラムの書き方で，最も標準的とされるスタイルは，カーニハン＆リッチー著「プログラミング言語Ｃ」第２版に則ったスタイルです．「プログラミング言語C」から抜粋したプログラム（findというプログラムです）の一例を以下に示します (このコードは不完全なためコンパイルできないことに注意)．

#include <stdio.h>
#include <string.h>
#define MAXLINE 1000

int getline(char *line, int max);

/* find: 最初の引数にあるパターンとマッチする行を表示する */
main(int argc, char *argv[])
{
    char line[MAXLINE];
    int found = 0;

    if (argc != 2)
        printf("Usage: find pattern\n");
    else
        while (getline(line, MAXLINE) > 0)
            if (strstr(line, argv[1]) != NULL) {
                printf("%s", line);
                found++;
            }
    return found;
}

参考までに，この書き方の特徴を列挙すると，おおよそ以下の通りです．

  1. 関数の始まりと終わりのブレースは，行頭に書く．
  2. if文などのブレースのうち，開始のブレース（｛）は，if文に続けて行末に書く．
  3. 関数の前には，関数の説明をコメントする．
  4. 関数の場合は，関数名の後に空白を入れずに()を書く．ifやwhileなどの制御文の条件式は，if の後に空白を入れて()を書く．
  5. 処理単位が明確にわかるように，字下げを施す．
  6. if文やwhile文の後に続く処理が一つだけの場合は，ブレースは不要なので省略する (ただし，このやり方は慣れていないと，間違いを引き起こしやすいので注意)

参考

上記のK&RのプログラムはC90準拠のプログラムですが，これをC99対応にして，初学者にも優しいように書き直したものが以下になります．コーディングの際の参考にしてください (上記と同様，このコードは不完全なのでコンパイルできません)．

#include <stdio.h>
#include <string.h>
#define MAXLINE 1000

int getline(char *line, int max);

// find: 最初の引数にあるパターンとマッチする行を表示する
int main(int argc, char **argv) {
    int found = 0;
    if (argc != 2) {
        printf("Usage: find pattern\n");
    } else {
        char line[MAXLINE];
        while (getline(line, MAXLINE) > 0) {
            if (strstr(line, argv[1]) != NULL) {
                printf("%s", line);
                found++;
            }
        }
    }
    return found;
}