第2回 - 配列，ポインタ，構造体，再帰

課題1: 配列

整数値の集まり(コレクションと呼ぶ)を格納する int 型の配列 data[] に対して，以下に示す3つの関数を持つソースコード prog2-1.c を作成する．

(1) data[] に格納されている整数の値を画面に表示する．num は配列の大きさを指す．

void print(int data[], int num);

(2) data[] に格納されている index 番目(以降，先頭を 0 番目とする)の整数の値を取得する．num は配列の大きさを指す．index 番目の整数が存在しない場合は，-1 を返す．

int get(int data[], int num, int index);

(3) data[] に格納されている整数の値の合計を取得する．num は配列の大きさを指す．配列が空 (num の値が 0) の場合は，0 を返す．

int sum(int data[], int num);

上記の3つの関数を持つ prog2-1.c を作成せよ．

本課題では，2つのテスト関数 test1() と test2() がすでに用意されている．さらに，テスト関数を追加せよ．

今後は，関数の作成と同時にテストコードを必ず作成すること．ただし，標準出力への出力結果をテストすることは難しいので，prog2-1.c の print(int data[], int num) のような標準出力に書き出す関数のテストコードは作成しなくてよい．

課題2: 配列とポインタ

int 型の配列 data[] の先頭要素へのポインタ int *data (data は先頭要素のアドレス &data[0] を指す)に関して，以下に示す4つの関数を持つソースコード prog2-2.c を作成する．

(1) data から num 個分の領域に格納されている整数の値を画面に表示する．

void print(int *data, int num);

(2) data から num 個分の領域に格納されている整数値のうち，index 番目の整数の値を取得する．index 番目の整数が存在しない場合は，-1 を返す．

int get(int *data, int num, int index);

(3) data から num 個分の領域に格納されている整数の値の合計を表示する．num の値が 0 の場合は，0 を返す．

int sum(int *data, int num);

(4) data から num 個分の領域に格納されている整数の値を逆順に格納した領域へのポインタを取得する．num の値が 0 の場合は，NULL を返す．

int *reverse(int *data, int num);

上記の4つの関数とテストコードを含む prog2-2.c を作成せよ．print(int *data, int num) を除く3つの関数に対して，最低1つずつテスト関数を作成すること．

任意の大きさの領域を確保するためには，void *calloc(size_t nitems, size_t size) を利用するとよい．たとえば，大きさ num の int 型の領域(先頭アドレスを dataとする)を確保するためには，
int *data = (int *)calloc(num, sizeof(int)) と記述すればよい．

課題3: 構造体の配列(1)

以下に示す構造体を考える．

struct data {
    char key;
    int value;
};

(1) data[] に格納されている構造体のオブジェクト(実体)の key と value の値を画面に表示する．num は配列の大きさを指す．

void print(struct data data[], int num);

(2) data[] に格納されている index 番目(先頭を 0 番目とする)の構造体のオブジェクトを取得する．num は配列の大きさを指す．index 番目のオブジェクトが存在しない場合は，NULL を返す．

struct data *get(struct data data[], int num, int index);

上記の2つの関数を含む prog2-3.c を作成せよ．

本課題では，テスト関数 test1() がすでに用意されている．さらに，テスト関数を追加せよ．

課題4: 構造体の配列(2)

以下に示す構造体を考える．

struct data {
    char key;
    int value;
};

(1) data[] に格納されている構造体のオブジェクト(実体)の key と value の値を画面に表示する．num は配列の大きさを指す．

void print(struct data *data[], int num);

(2) data[] に格納されている構造体のオブジェクトの value の値に引数 value の値を加算する．

void plus(struct data *data[], int num, int value);

上記の2つの関数とテストコードを含む prog2-4.c を作成せよ．

課題5: 再帰

再帰(recursion)とは，ある事象が自分自身を含んでいたり，自分自身で定義されていることを指す．

また，関数の再帰呼び出し(recursive call)とは，自分自身を直接あるいは間接的に呼び出すことを指す．たとえば，以下に示す階乗を求める関数 factorial(int n)は再帰的である．

int factorial(int n)
{
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

ここでは，ユークリッドの互除法により2つの正の整数 p と q の値の最大公約数を求める関数

int gcd(int p, int q);

ユークリッドの互除法

2つの正の整数 p と q (p ≥ q) に対して，p を q で割った余りを mとすると，p と q の最大公約数は，q と m の最大公約数に等しいという性質が成り立つ．これを利用すると，p と q の最大公約数を求めるアルゴリズムは以下のようになる．

1. q が 0 のとき，p が最大公約数
2. q が 0 でないとき，もとの q を p，p を q で割った余りを q とし，1.に戻る．

関数 gcd(int p, int q) とテストコードを含む prog2-5.cを作成せよ．