第1回バイナリ、アルゴリズム1

本日の講義内容

コンパイルとリンク
基本的なデータ構造: 木

コンパイルとリンク

これまで、プログラミングをするにあたっては、gccなどのコマンドを使いソースファイルをコンパイルして実行可能ファイルを作り、それを計算機に実行させてきたと思います。まず、こうした流れについてもう少し深堀りしてみましょう。

コンパイルの流れ

これまでのプログラムのコンパイルの流れを再確認します。例えばmain.cをコンパイルする場合、以下のようなコマンドでコンパイルしていたと思います。

# main.cをコンパイル
$ gcc main.c

実はこのコンパイルでは、以下に示すような2つの作業を一度におこなっていたのでした。

# 狭義のコンパイル: オブジェクトファイルmain.oを作成する
$ gcc -c main.c
# リンク: リンカを用いてオブジェクトファイルを結合し、実行可能ファイルを作成する
$ gcc main.o -o a.out

コンパイルの流れ

ここでオブジェクトファイルは、ソースコードを機械語に変換した中間ファイルです。機械語の断片にはなっているものの、まだ実行可能な形式にはなっていません。これは、オブジェクトファイルの段階では各関数や変数が実際に配置されるアドレスが未確定であり、また必要なライブラリ (オブジェクトファイルをまとめたもの) や他のオブジェクトファイルと結合されていないためです。

こうしたオブジェクトファイルに対して、リンクをおこなうことで、未確定だったアドレスが解決され、他のライブラリやオブジェクトファイルと結合されて一つの実行可能ファイルとなります。こうした作業をおこなうツールをリンカと呼びます。ライブラリについては、後ほどまた詳細に説明します。

コラム: アセンブラ

コンパイラやリンカの他にアセンブラ、というものがあることを知っていると、ここでアセンブラが出てこないのはなぜか、と思われたかもしれません。アセンブラは確かに存在していますが、上の説明の文脈では、コンパイル (狭義) のさらにその一部、として扱われているため名前が出てきていません。コンパイル (狭義) はソースコードからアセンブリコードへの変換、アセンブリコードからオブジェクトファイルへの変換という2つの工程に大別され、アセンブラは後者を担当します。この辺りの詳細については、また後の講義で再訪するかもしれません。

分割コンパイル

プログラムが大きくなると、複数のファイルに分けて管理することが重要になります。これまでは、main.cのような一つのファイルにすべての処理を記述し、必要な機能を詰め込んで実装していたと思います。しかし、プログラムが大きく複雑になっていくと、この方法では管理が難しくなりがちです。そこで役立つのが分割コンパイルという仕組みです。分割コンパイルでは、複数のソースファイルに関数などを分けて記述し、コンパイル時にそれらをまとめて一つのプログラムへと仕上げます。

分割コンパイル

ソースファイルを分割することで、汎用的な機能を別のプログラムでも再利用しやすくなるほか、バグが発生した際にも該当箇所だけ修正すればよいため、保守性が大きく向上します。今後ソフトウェア2ではこれまでよりやや複雑なプログラムを作っていきます。分割コンパイルはこうしたものに挑んでいくときに役立つ基本的な技術になっています。

ソースコードの分割

まずは以下のようなコードについて考えてみましょう。

main.c
// 四則演算のプログラム
#include <stdio.h>

double add(double a, double b);
double sub(double a, double b);
double mul(double a, double b);
double div(double a, double b);

int main() {
    double a = 1.2;
    double b = 1.4;

    printf("a+b: %f\n",add(a,b));
    printf("a-b: %f\n",sub(a,b));
    printf("a*b: %f\n",mul(a,b));
    printf("a/b: %f\n",div(a,b));
    return 0;
}

double add(double a, double b) {
    return a + b;
}

double sub(double a, double b) {
    return a - b;
}

double mul(double a, double b) {
    return a * b;
}

double div(double a, double b) {
    return a / b;
}

このコードについて、まずは関数の実装部分をcalc.cという別のファイルへと移してみましょう。

main.c
#include <stdio.h>

double add(double a, double b);
double sub(double a, double b);
double mul(double a, double b);
double div(double a, double b);

int main() {
    double a = 1.2;
    double b = 1.4;

    printf("a+b: %f\n",add(a,b));
    printf("a-b: %f\n",sub(a,b));
    printf("a*b: %f\n",mul(a,b));
    printf("a/b: %f\n",div(a,b));
    return 0;
}

calc.c
double add(double a, double b) {
    return a + b;
}

double sub(double a, double b) {
    return a - b;
}

double mul(double a, double b) {
    return a * b;
}

double div(double a, double b) {
    return a / b;
}

現状はmain.cにプロトタイプ宣言とmain関数が、calc.cに関数の実際の実装が記述されている状態です。この状態でコンパイルすると何が起きるでしょうか。

演習

上記を写経して、2つのソースコードmain.cとcalc.cを作ってましょう。
それぞれについてコンパイルして、どのような結果になるか見てみましょう。

さて、それぞれについてundefined referenceのようなエラーが得られたでしょうか。main.cのコンパイルについては、プロトタイプ宣言はあるものの関数の実体が定義されておらず、calc.cではmainの実体がないことがエラーの原因となっているはずです。

これを解消するために、まずは他の関数の実体が定義されていない状態でも個々のファイルをコンパイルできるようにしてみましょう。

# -c オプションを追加する
$ gcc -c main.c
$ gcc -c calc.c

上の例でも示したように、このようにするとmain.o、calc.oというオブジェクトファイルが生成されます。

その後で、これらのオブジェクトファイルをリンクすることで最終的な実行可能ファイルを作ることができます。

# -o オプションがないので a.out が生成される
$ gcc main.o calc.o
# 実行する
$ ./a.out

さらに、プロトタイプ宣言を別のファイルにまとめることができます。これが実は、これまで#includeで何度も読み込んできた.hヘッダファイルの基本形です。

calc.c
#include <stdio.h>
#include "calc.h"

int main(){
    double a = 1.2;
    double b = 1.4;

    printf("a+b: %f\n",add(a,b));
    printf("a-b: %f\n",sub(a,b));
    printf("a*b: %f\n",mul(a,b));
    printf("a/b: %f\n",div(a,b));
    return 0;
}

calc.h
// 実際は後ほど述べるインクルードガードがあった方がよいが、一旦省略
double add(double a, double b);
double sub(double a, double b);
double mul(double a, double b);
double div(double a, double b);

すなわち、

main.c: main関数に加えて、#include文でhogehoge.hを読み込む
hogehoge.h: 関数のプロトタイプ宣言
hogehoge.c: 関数の実際の実装

のようにそれぞれ記述して、

$ gcc main.c hogehoge.c

とすることで分割コンパイルができます。

演習

分割コンパイルに向けてmain.c、calc.h、calc.cを作成しましょう。
2つのソースコードmain.cとcalc.cを$ gcc main.c calc.cとして正しくコンパイルできることを確かめましょう。

うまくできたら、もう少し複雑に見えるソースコードについても同様の分割にチャレンジしてみましょう。

演習

以下に示したqsort.cをソースファイルmain.cおよびintlib.c、ヘッダファイルintlib.hへと適切に分割し、分割コンパイルを実行してみましょう。コンパイル後に実行して、

$ ./qsort 10
[359 966 105 115 81 255 74 236 809 205 ]
v[0] = 74
v[1] = 81
v[2] = 105
v[3] = 115
v[4] = 205
v[5] = 236
v[6] = 255
v[7] = 359
v[8] = 809
v[9] = 966

のように、ランダムな値が昇順に並べ替えされて表示されれば正しく動作しています。

qsort.c
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>

int comp_int(const void *x0, const void *x1) {
    const int *p0 = x0;
    const int y0 = *p0;
    const int *p1 = x1;
    const int y1 = *p1;

    if (y0 > y1) return 1;
    if (y0 < y1) return -1;
    return 0;
}

int load_int(const char *str) {
    errno = 0;
    char *e;
    long n = strtol(str, &e, 10);

    if (errno == ERANGE) {
        fprintf(stderr, "%s: %s\n", str, strerror(errno));
        exit(EXIT_FAILURE);
    }
    if (*e != '\0') {
        fprintf(stderr, "%s: an irregular character '%c' is detected.\n", str, *e);
        exit(EXIT_FAILURE);
    }
    return (int)n;
}

int main(int argc, char **argv) {
    if (argc != 2) {
        fprintf(stderr, "usage: %s <number of elements>\n", argv[0]);
        exit(EXIT_FAILURE);
    }

    int n = load_int(argv[1]);
    int v[n];

    for (int i = 0; i < n; i++) {
        v[i] = rand() % 1024;
    }

    printf("[");
    for (int i = 0; i < n; i++) {
        printf("%d ", v[i]);
    }
    printf("]\n");

    qsort(v, n, sizeof(int), comp_int);

    for (int i = 0; i < n; i++) {
        printf("v[%d] = %d\n", i, v[i]);
    }

    return 0;
}

こたえ

main.c
#include <stdio.h> 
#include <stdlib.h>
#include "intlib.h"

int main(int argc, char **argv) {
    if (argc != 2) {
        fprintf(stderr, "usage: %s <number of elements>\n", argv[0]);
        exit(EXIT_FAILURE);
    }

    int n = load_int(argv[1]);
    int v[n];

    for (int i = 0; i < n; i++) {
        v[i] = rand() % 1024;
    }

    printf("[");
    for(int i = 0; i < n; i++){
        printf("%d ", v[i]);
    }
    printf("]\n");

    qsort(v, n, sizeof(int), comp_int);

    for (int i = 0; i < n; i++) {
        printf("v[%d] = %d\n", i, v[i]);
    }

    return 0;
}

intlib.c
#include <stdio.h>
#include <stdlib.h>
#include <errno.h> 
#include <string.h>
#include "intlib.h"  // これはこのファイルのコンパイル自体には不要ですが、ライブラリとペアということで設置

int comp_int(const void *x0, const void *x1) {
    const int *p0 = x0;
    const int y0 = *p0;
    const int *p1 = x1;
    const int y1 = *p1;

    if (y0 > y1) return 1;
    if (y0 < y1) return -1;
    return 0;
}

int load_int(const char *str) {
    errno = 0;
    char *e;
    long n = strtol(str,&e,10);

    if (errno == ERANGE) {
    fprintf(stderr, "%s: %s\n", str, strerror(errno));
    exit(1);
    }
    if ( *e != '\0') {
    fprintf(stderr, "%s: an irregular character '%c' is detected.\n",str,*e);
    exit(EXIT_FAILURE);
    }
    return (int)n;
}

intlib.h
int comp_int(const void *x0, const void *x1);
int load_int(const char *str);

インクルードガード

さきほどはヘッダファイルに特に情報を加えませんでした。先ほどの例の場合、このヘッダファイルが仮に複数回呼ばれてしまったとしても、宣言しか存在しないため影響しません。

main.c
#include <stdio.h>
#include "calc.h"
#include "calc.h"
#include "calc.h"

int main() {
    double a = 1.2;
    double b = 1.4;

    printf("a+b: %f\n",add(a,b));
    printf("a-b: %f\n",sub(a,b));
    printf("a*b: %f\n",mul(a,b));
    printf("a/b: %f\n",div(a,b));
    return 0;
}

上記のコードをコンパイルした際、プリプロセッサが展開した状態のコードからdouble add(という部分を抜き出してみましょう。

# コンパイルせずにプリプロセッサだけ実行するには
# -E オプションをつける
$ gcc -E main.c | grep "double add("

プロトタイプ宣言が3回出てきているのがわかります。

しかし定義ファイルが含まれる場合には後述のように事情が異なるため、一般にはインクルードガードというテクニックで、ヘッダファイルが複数回呼ばれるのを抑制します。

calc.h
#ifndef _CALC_H_
#define _CALC_H_
double add(double a, double b);
double sub(double a, double b);
double mul(double a, double b);
double div(double a, double b);

#endif

上記の例ではプリプロセッサマクロの_CALC_H_が定義されていなければ、これを定義して#endifまでのブロックを読み込むという意味になります。一度このブロックに入ると必ずマクロが定義されるので、もう一度calc.h がincludeされても読み込まれません。

演習

インクルードガードの有無に応じてプロトタイプ宣言の回数が変化することを確かめましょう。

なお上記は昔からよく利用されている記述方法ですが、最近では以下のような書き方も多くのコンパイラで対応しています。

calc.h
#pragma once
double add(double a, double b);
double sub(double a, double b);
double mul(double a, double b);
double div(double a, double b);

定義を含む場合の分割コンパイル

インクルードガードが必要になる例として行列とベクトルの演算を考えてみましょう。例えばベクトルの掛け算だけであればベクトルの定義だけで十分ですが、行列とベクトルの掛け算などの場合、両方の定義が必要となります。簡単のためここでは2次元の演算のみを考えます。構造体ポインタを使わないようにハードコーディングされています。

いま、

vector.c : ベクトル関係の関数実装
matrix.c : 行列関係の関数実装
vector.h : ベクトルの構造体定義とプロトタイプ宣言
matrix.h : 行列の構造体定義とプロトタイプ宣言 (行列とベクトルの積を含む)

のような分割を考えます。

main.c
#include "matrix.h"
#include "vector.h"

int main() {
    Vector x = (Vector){ .v = { 1.0, 2.0 } };
    Vector y = (Vector){ .v = { 3.0, 4.0 } };
    Matrix A = (Matrix){ .v = { 1.0, -1.0, -1.0, 1.0} };

    // c = 2.0 x + y
    Vector c = axpy(2.0, x, y);
    // d = 2.0 Ax + y
    Vector d = gemv(2.0, A, x, 1.0, y);

    print_vector(c);
    print_vector(d);
    return 0;
}

vector.c
#include <stdio.h>
#include "vector.h"

Vector axpy(double alpha, Vector a, Vector b) {
    return (Vector){ .v = { alpha * a.v[0] + b.v[0], alpha * a.v[1] + b.v[1]}};
}

void print_vector(Vector a) {
    printf("[%f %f]\n",a.v[0],a.v[1]);
}

matrix.c
#include <stdio.h>
#include "matrix.h"
#include "vector.h"

Vector gemv(double alpha, Matrix A, Vector x, double beta, Vector y) {
    return (Vector){ .v = {alpha * (A.v[0]*x.v[0]+A.v[1]*x.v[1]) + beta * y.v[0], alpha * (A.v[2]*x.v[0]+A.v[3]*x.v[1]) + beta * y.v[1]}};
}

void print_matrix(Matrix m) {
    printf("[%f %f ;%f %f]\n",m.v[0],m.v[1],m.v[2],m.v[3]);    
}

vector.h
typedef struct {
    double v[2];
} Vector;

// ax + y の形 (BLAS level1と同じ命名)
Vector axpy(double alpha, Vector a, Vector b);
void print_vector(Vector a);

matrix.h
#include "vector.h"

typedef struct{
    double v[4]; // 2 x 2
} Matrix;

// プロトタイプ宣言でVector型を知っている必要がある
// alpha * Ax + beta * y (BLAS level2と同じ命名)
Vector gemv(double alpha, Matrix A, Vector x, double beta, Vector y);
void print_matrix(Matrix m);

演習

上記を写経して、main.cをコンパイルしてみましょう。
どのような結果になるか見てみましょう。

エラーの原因は、vector.hが複数回呼ばれていることにあります。これはmatrix.hでVector型の宣言が必要になるために、vector.hをincludeしているためです。結果的にVector型が複数回定義されてしまっています。

ヘッダファイルを呼び出す側としては、matrix.hを呼べばvector.hは呼ばれるので呼ぶ必要がないという考え方でコードを書いていくのは困難です。そのため、複数回呼ばれても大丈夫なように衝突回避する必要があります。

演習

matrix.hおよびvector.hにインクルードガードを施して全てのコードをコンパイルしてみましょう。

宣言と定義の分離

これまで構造体の宣言と定義は一緒に行うことが多かったと思います。この場合、ヘッダファイルをインクルードすることで各プログラムは構造体の定義を知ることができ、そのメンバへのアクセス等が可能になっていました。しかしモジュールを細かく分割していった場合、究極的には対象となる構造体がどのようなメンバを持つかはわからないほうが望ましいです。そのようにすると構造体のメンバーはその構造体を使う別の関数からは見えなくなります。どうやって使うのかという話になりますが、メンバー変数にアクセスするための関数のプロトタイプをヘッダファイルに記載してあげます。

今回の例の場合、

matrix.h, vector.h ではtypedefにより構造体の宣言のみ行う。
matrix.c, vector.cにて構造体の定義を行い、それぞれのファイル内ではメンバを直接参照可能。他の関数にはアクセスできる関数を提供する。
Matrix, Vectorは基本的にポインタだけでやりとりする。

とすることで、モジュールを隠蔽することができます。

参考

高難度ですが、適切に関数を追加することで、構造体の定義部分をヘッダファイルから隠蔽することができます。構造体の定義をmatrix.c、vector.c内でおこないます。matrix.c内でVectorの値を取り出したい場合は、定義の情報がないので、vector.hでアクセスのための関数を提供します。

こたえ

main.c
#include "matrix.h"
#include "vector.h"

int main() {
    // 複合リテラルでdouble型配列を用意して引数とする。
    // 配列が引数の場合は、関数内部ではポインタ扱いで処理される。
    Vector *x = init_vector((double []){1.0, 2.0});
    Vector *y = init_vector((double []){3.0, 4.0});
    Matrix *A = init_matrix((double []){1.0, -1.0, -1.0, 1.0});

    // c = 2.0 x + y
    Vector *c = axpy(2.0, x, y); 

    // d = 2.0 Ax + y
    Vector *d = gemv(2.0, A, x, 1.0, y);

    print_vector(c);
    print_vector(d);

    // 以下のfree関数群の結果、ポインタにはNULLが代入されるので、init関数でmallocされたときのアドレス情報は残らない
    free_vector(&x);
    free_vector(&y);

    free_vector(&c);
    free_vector(&d); 
    free_matrix(&A); 

    return 0;
}

vector.h
#pragma once
#include <stddef.h> // size_t
// 宣言のみ行う
typedef struct vector Vector;

// ax + y の形（BLASレベル1と同じ名前のつけかた）
// ポインタでのやり取りに変更
Vector* axpy(double alpha, const Vector *a, const Vector *b);
void print_vector(const Vector *a);

// Vector型を動的に確保して初期化する関数
Vector *init_vector(const double v[]);
// Vector 用の free / Vector型ポインタへのポインタとすることで、nullリセット可能にする
void free_vector(Vector **v);
// 要素の取り出し
double get_vec_element(const Vector *v, size_t i);

vector.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "vector.h"

// ここで構造体の定義をかく。このメンバーに直接触れるのはこのファイルの中の関数だけ
struct vector {
    double v[2];
};

Vector* axpy(double alpha, const Vector *a, const Vector *b)
{
    Vector *v = malloc(sizeof(Vector));

    // このvector.c 内に限り、アロー演算子が有効（構造体の定義を知っているため）
    *v = (Vector){ .v = { alpha * a->v[0] + b->v[0], alpha * a->v[1] + b->v[1]} };

    // 以下は上記の置き換えパターンのうち、かなり裏技的な書き方。Vector型は配列のみのメンバなので、doubleのポインタにキャストして
    // バナナをつけると、doubleとして値を取り出せる。
    // memcpy(v,(double []){alpha *  *(double*)a + *(double*)b, alpha * *((double*)a + 1) + *((double*)b + 1)}, sizeof(double)*2);

    return v;
}

void print_vector(const Vector *a)
{
    printf("[%f %f]\n",a->v[0],a->v[1]);
}

Vector *init_vector(const double v[]){
    Vector *ret = malloc(sizeof(Vector));
    memcpy(ret->v, v, sizeof(double)*2);
    return ret;
}

void free_vector(Vector **v){
    free(*v);
    *v = NULL;
}

double get_vec_element(const Vector *v, size_t i){
    // 不正なインデックスアクセスを抑制
    if ( i != 0 && i != 1) {
        fprintf(stderr, "%s: index should be 0 or 1.",__func__);
        exit(1);
    }
    return v->v[i];
}

matrix.h
#pragma once

#include <stddef.h> // size_t
#include "vector.h"
typedef struct matrix Matrix;

// プロトタイプ宣言ではVector型があることをを知っていればよい
// alpha * Ax + beta * y
Vector* gemv(double alpha, const Matrix *A, const Vector *x, double beta, const Vector *y);
void print_matrix(const Matrix *m);

// Matrix型を動的確保し、初期化する関数
Matrix *init_matrix(const double m[]);
// Matrix用の free / 引数をMatrix型ポインタへのポインタとすることで、nullリセット可能にする
void free_matrix(Matrix **m);
double get_mat_element(const Matrix *m, size_t i, size_t j);

matrix.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "matrix.h"
#include "vector.h"

struct matrix{
    double v[4];
};

Vector *gemv(double alpha, const Matrix *A, const Vector *x, double beta, const Vector *y)
{
    double xx, xy, yx, yy; // x = [xx, xy], y = [yx, yy];
    xx = get_vec_element(x, 0);
    xy = get_vec_element(x, 1);
    yx = get_vec_element(y, 0);
    yy = get_vec_element(y, 1);

    double axx, axy, ayx, ayy;
    axx = get_mat_element(A, 0, 0);
    axy = get_mat_element(A, 0, 1);
    ayx = get_mat_element(A, 1, 0);
    ayy = get_mat_element(A, 1, 1);

    double a = alpha * (axx * xx + axy * xy) + beta * yx; 
    double b = alpha * (ayx * xx + ayy * xy) + beta * yy;

    return init_vector((double []){a,b});
}

void print_matrix(const Matrix *m)
{
    printf("[%f %f ;%f %f]\n",m->v[0],m->v[1],m->v[2],m->v[3]);    
}

Matrix *init_matrix(const double m[]){
    Matrix *ret = (Matrix *)malloc(sizeof(Matrix));
    memcpy(ret->v, m, sizeof(double) * 4);
    return ret;
}

void free_matrix(Matrix **m){
    free(*m);
    *m = NULL;
}

double get_mat_element(const Matrix *m, size_t i, size_t j){
    if ( i != 0 && i != 1){
        fprintf(stderr, "%s: index out of range %zu. It should be [0 1].\n",__func__,i);
        exit(1);
    }
    if ( j != 0 && j != 1){
        fprintf(stderr, "%s: index out of range %zu. It should be [0 1].\n",__func__,j);
        exit(1);
    }
    return m->v[2 * i + j];
}

ライブラリ

ライブラリとは複数のオブジェクトファイルを一つに固めたものです。ライブラリには基本的に以下の2種類があります。

静的ライブラリ (.a)
- ビルド時に実行ファイルへ組み込まれる
- 実行ファイルは大きくなる
- ライブラリを更新したら再リンクが必要
共有ライブラリ (.so)
- 実行時にロードされ、リンクされる
- 実行バイナリは比較的小さい
- ライブラリが更新されても再コンパイルは不要
- ライブラリの配置場所を実行時に解決する必要がある

前者の静的ライブラリは全ての関数オブジェクトがライブラリに含まれており、コンパイル時にそれらをリンクします。一方で後者の共有ライブラリではコンパイル時には、ファイルレベルでどこにライブラリがあるかをコンパイル時に教えておき、実行時にそれを探します。

たとえばオープンソースのプログラムを自分の環境で無事にコンパイルできたと思いきや、最終的に実行時にerror while loading shared librariesのようなエラーと遭遇することはよくあります。これは後者の共有ライブラリが置かれているとされるところにうまくアクセスできていないことが原因です。

コラム: ヘッダファイルとライブラリ

これまでさまざまな.hのヘッダファイルを読み込むことでライブラリを利用していました。したがってなんとなくヘッダファイル=ライブラリと思っていた方も多いかもしれません。ヘッダファイルには多くの場合関数の宣言のみが書かれています。関数の本体については、上で示した静的ライブラリや共有ライブラリとしてまとめられています。たとえば数学関数ライブラリのmath.hを#includeするだけでは数学関数の実体は含まれません。実際の処理はlibmというライブラリにあります。以前の説明では、math.hを利用するときgcc -lmのようなコマンドが必要、ということになっていたと思います。これが、ライブラリのリンクのために必要なオプションだったのだ、ということが今日の講義内容からわかることと思います。

静的ライブラリの作成と利用

静的ライブラリの作成をおこなってみましょう。ライブラリの作成にはarというコマンドを用います。

$ ar rsv libinteger.a intlib.o

ここで、それぞれのオプションは、

r: 既存ファイルの更新 or 新規作成
s: 複数のオブジェクトファイルをランダムアクセス可能にする
v: 詳細を表示

という意味です。このように作成したライブラリをコンパイル時に使用する方法は2通りあります。ひとつはオブジェクトファイルと同様に直接指定する方法です。

$ gcc main.c libinteger.a -o qsort

もう一つはgcc において、-lというオプションを用いることでリンクするライブラリを指定する方法です。これはlib????.aのリンクを-l????という形式で指定します。

$ gcc main.c -L. -linteger -o qsort

適切なディレクトリ構成

分割コンパイルを行うことで、プログラム中の役割に応じて異なるファイルが生成されることになります。これを単一のディレクトリで扱うと非常にごちゃごちゃします。オープンソースのプロジェクトなどでもそうですが、ヘッダファイル、ソースコード、ライブラリ、実行可能ファイルを階層的に配置しておくことで、保守性を高めることができます。

src: ソースコードを格納
include: ヘッダファイルを格納 (-I./include で参照)
lib: ライブラリファイルを格納 (-L./lib で参照)
bin: 実行可能ファイルを格納

分割コンパイル時、gcc -cはデフォルトでは実行したディレクトリにオブジェクトファイルを出力します。-oは-cと組み合わせても用いることが可能で、この場合はオブジェクトファイル名を指定できます。そのため例えば、src以下にオブジェクトを生成したい場合は

$ gcc -c -I./include src/intlib.c -o src/intlib.o

のようになります。あくまでオブジェクトの生成なので、-cを忘れないのが重要です。

最終的にはライブラリをlibに作成した上で、以下のコードでコンパイルします。

$ gcc -I./include src/main.c -L./lib -linteger -o bin/qsort

演習

qsort.h、main.c、intlib.cを

.
├── bin
├── include
│   └── qsort.h
├── lib
└── src
    ├── main.c
    └── intlib.c

のように適切に配置した上で、ライブラリlibinteger.aおよび実行可能ファイルqsortを作成してみてください。

こたえ

# オブジェクトファイルの生成
$ gcc -I./include -c src/intlib.c -o src/intlib.o 
# ar でライブラリにする
$ ar rsv lib/libinteger.a src/intlib.o
# コンパイル
$ gcc -I./include src/main.c -L./lib -linteger -o bin/qsort
# 実行
$ bin/qsort 10

木構造

木構造は、データを階層的に整理して扱うための基本的なデータ構造です。言葉としては「木のような形」を指しますが、グラフ理論では「連結で、かつ閉路を持たないグラフ」と定義されます。一般にプログラムで扱う場合は、一番上にあたるノードを根 (root) として定め、そこから下方向に枝が分かれる根付き木 (rooted tree) を考えます。

木構造におけるノードは、再帰的な親子関係で結ばれています。根以外のすべてのノードはちょうど 1 つの親を持ち、0 個以上の子ノードを持つことができます。親が同じノード同士は兄弟 (siblings) と呼ばれ、子ノードを持たないものは葉 (leaf) と呼ばれます。このような規則によって、木構造は階層的で明確な関係性を持ちながらデータを表現することができます。

木構造

コラム: グラフ

グラフは、平易な言葉では、いくつかの点（頂点、vertex）の集まりと、それらの点を結ぶ線（辺、edge）の集まりで構成されるデータ構造のことです。このうち連結 (すなわち、全部の点がつながっている) ・非巡回/無閉路 (すなわち、サイクルがない、acyclic) なものを木と呼びます。たとえばソフトウェアにおける依存関係や計算機のネットワーク、さらにはソーシャルネットワークなど、ものとものとの関係を汎用的に表現することができます。実はテキストや画像もグラフとして考えることができます (!)

二分木

木構造の中で特にアルゴリズム的に重要なものの一つが二分木（binary tree）です。二分木は各ノードが最大でも2つの子ノードしか持たない木です。アルゴリズムを考える際の全ての木は二分木に変換して考えることができるため、非常に重要な概念です。

二分木のなかでも完全二分木というものがあります。これは最下段以外のノードが全て埋まっており、最下段については左から隙間なくうまっている状態の二分木を指します。

二分木をプログラムで扱う際には、自己参照構造体と呼ばれる仕組みを用いてデータを表現します。自己参照構造体とは、自分自身と同じ型を指すポインタをメンバとして持つ構造体のことです。これにより、あるノードからさらに別のノードへとリンクをたどれるようになります。

木構造実装

struct node {
    int value;  // データ
    struct node *parent;
    struct node *left;
    struct node *right;
}

なお親か子のどちらかのポインタしか持たないことも多いです。一方対応するノードが存在しない場合はポインタでNULLを指定するようにします。

木構造データの走査

木構造に含まれる全てのノードを訪れることを考えます。このとき木に含まれる全てのデータを表示することを考えましょう。この全てのノードへの訪問を走査（traversal）といいます。走査の順序として、まずは以下の3種類が考えられます。

行きがけ順 (preorder): データを表示 -> 左の子ノードに移動 -> 右の子ノードに移動という優先順位の探索を再帰的に実施
通りがけ順 (inorder): 左の子ノードに移動 -> データを表示 -> 右の子ノードに移動という優先順位の探索を再帰的に実施
帰りがけ順 (postorder): 左の子ノードに移動 -> 右の子ノードに移動 -> データを表示という優先順位の探索を再帰的に実施

ここで、出力済のノードには積極的に移動せず、移動できなくなったときはひとつ戻ってまた探索することとします。これらによって、木の深さ優先の探索 (depth-first search, DFS) を行うことができます。

では実際に、木構造の走査をおこなってみましょう。

main.c
#include <stdio.h>
#include <stdlib.h>
#include "traverse.h"


int main(int argc, char **argv) {
    // ノードを10個ほど定義
    Node n1  = { .value = 1, .left = NULL, .right = NULL};
    Node n2  = { .value = 2, .left = NULL, .right = NULL };
    Node n3  = { .value = 3, .left = NULL, .right = NULL };
    Node n4  = { .value = 4, .left = NULL, .right = NULL };
    Node n5  = { .value = 5, .left = NULL, .right = NULL };
    Node n6  = { .value = 6, .left = NULL, .right = NULL };
    Node n7  = { .value = 7, .left = NULL, .right = NULL };
    Node n8  = { .value = 8, .left = NULL, .right = NULL };
    Node n9  = { .value = 9, .left = NULL, .right = NULL };
    Node n10 = { .value =10, .left = NULL, .right = NULL };

    // 木を繋いでみる。木の形はページ参照


    // 走査する
    traverse(&n1);

    return EXIT_SUCCESS;
}

traverse.c
#include <stdio.h>
#include "traverse.h"

void traverse(const Node *n) {
    if (n == NULL) return;

    // 以下に木を操作する手順を実装する
    // 表示は printf("value = %d\n", n->value); のような形で良い

}

traverse.h
#pragma once

typedef struct node{
    int value;
    struct node *left;
    struct node *right;
} Node;

// 木のルートを与えて操作する
void traverse(const Node *n);

上の例では、10個のノードを考えています。まだ連結はしていません。以下のような木のサンプルを考えます。

二分木サンプル

演習

上図のような木が作成されるようにmain.cを修正してみましょう。
traverse()関数を行きがけ順で走査するように完成させて実行してみましょう（ヒント: 再帰を用います、つまり、traverse()内でtraverse()を呼び出します）。
- 数字が 1 から順に 10 まで表示されれば成功です

こたえ

main.c
#include <stdio.h>
#include <stdlib.h>
#include "traverse.h"


int main(int argc, char **argv) {
    // ノードを10個ほど定義
    Node n1  = { .value = 1, .left = NULL, .right = NULL};
    Node n2  = { .value = 2, .left = NULL, .right = NULL };
    Node n3  = { .value = 3, .left = NULL, .right = NULL };
    Node n4  = { .value = 4, .left = NULL, .right = NULL };
    Node n5  = { .value = 5, .left = NULL, .right = NULL };
    Node n6  = { .value = 6, .left = NULL, .right = NULL };
    Node n7  = { .value = 7, .left = NULL, .right = NULL };
    Node n8  = { .value = 8, .left = NULL, .right = NULL };
    Node n9  = { .value = 9, .left = NULL, .right = NULL };
    Node n10 = { .value =10, .left = NULL, .right = NULL };

    // 木を繋いでみる。木の形はページ参照
    n1.left = &n2; n1.right = &n7;

    n2.left = &n3; n2.right = &n6;
    n7.left = &n8; n7.right = &n10;

    n3.left = &n4; n3.right = &n5;

    n8.left = &n9;

    // 走査する
    traverse(&n1);

    return EXIT_SUCCESS;
}

traverse.c
void traverse(const Node *n)　{
    if (n == NULL) return;

    printf("value=%d\n", n->value);
    traverse(n->left);
    traverse(n->right);

}

二分木は重要なデータ構造であり、様々な応用先が存在します。

構文解析: 例えば3+4-2*3 のような式を解析する場合に、数字をリーフノード、途中のノードに演算子を考えることで、数式を木構造で表現できます。このような木を構文解析木と呼びます。
二分探索木: 二分木のデータ間に制約条件を与えることで、効率的なデータ管理を実現できます。二分探索木では全てのノードで左の子孫の値<親の値<右の子孫の値の関係が成り立つようにすることで、ある値を持つノードをO(log n)の平均計算量でみつけることができます。
二分ヒープ: 二分ヒープでは全てのノードで親の値>=子の値の関係が成り立つように木を構成します。これによりあるデータ群（部分木に相当）の中での最大値をすぐに取り出すことが可能になります。

アプリケーション: ハフマン符号

二分木を用いたアプリケーションとして、文字データのハフマン符号化について考えてみましょう。

符号

コンピュータで文字を扱う場合、各文字に整数が割り当てられているのでした。こうしたはすでに皆さん何度もやってきたと思います。文字シンボル (char型) の場合は、正の整数が割り当てられているので全てのシンボルは実質7ビットで表されていることになります。ASCIIコードはこの対応関係を記述したものになります。

シンボルの例	16進数	2進数
[空白]	0x20	0100000
A	0x41	1000001
B	0x42	1000010
z	0x7a	1111010

符号化

実際のシンボルには使われる頻度に基づく偏りが存在します。一旦ASCIIコードから離れて、あるシンボル系列ABACABAADを考えてみましょう。出現する4つのシンボルに符号語として01の値を付与することを考えます。まず最初に、以下の符号化を行うとします。

シンボル	符号語
A	00
B	01
C	10
D	11

このとき与えられたシンボル系列は000100100001000011と表現され18ビットです。次に以下の符号表を考えます。

シンボル	符号語
A	0
B	10
C	110
D	111

この表を用いた場合はシンボル系列は010011001000111と表現され15ビットとなり効率的に表現することができます。これは多く出現するシンボルに短い符号長を割り当て、出現頻度の少ないシンボルに長い符号長を割り当てることで実現されます。

接頭符号

各シンボルの符号語の先頭に着目します。どの符号語も他の符号語の語頭になっていない符号を接頭符号 (prefix code) といいます。接頭符号でないと、大量のビット列からシンボルを復号する際に問題となります。先程の短い符号長を実現した符号表は接頭符号の条件を満たします。一方以下の符号は符号語の一部が別の符号語の語頭となっており、条件を満たしません。

シンボル	符号語
A	0
B	10
C	100
D	111

ハフマン符号

ハフマン符号は出現頻度の高いシンボルに短い符号語を割り当てていく接頭符号であり、整数の符号長の制約のもとでは最適な符号を構成できます。さきほどの例では下図のような木構造（ハフマン木）を通して、符号を得ることができます。

ハフマン木

ハフマン符号の構成手順は以下のようになります。

木の作成

各シンボルの出現回数を数える
出現回数が最も小さい２つのシンボルを統合し、新たな（ダミー）シンボルを作成
- 新たなシンボルの出現回数は、統合された２つのシンボルの出現回数の和とする
シンボルが１つになるまで 2 に戻り繰り返す

符号の作成

すべての枝別れに対して、 0 (左の枝) と 1 (右の枝) のビットを割り振る
- このとき左右と0/1の対応はどちらでも構わない
個々のシンボルに対して、ルートからの経路のビット列として符号語が得られる

サンプルプログラム

ハフマン木を構成するサンプルプログラムの雛形を見てみましょう。英文のテキストが記述された.txtファイルを入力としてハフマン木を構成するものです。

main.c
#include <stdio.h>
#include <stdlib.h>
#include "encode.h"

int main(int argc, char **argv) {
    if (argc != 2) {
        fprintf(stderr, "usage: %s <filename>\n",argv[0]);
        exit(1);
    }

    Node *root = encode(argv[1]);
    traverse_tree(0,root);

    return EXIT_SUCCESS;
}

encode.c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include "encode.h"

// 構造体定義
struct node{
    int symbol;
    int count;
    Node *left;
    Node *right;
};

#define NSYMBOLS 256

static int symbol_count[NSYMBOLS];

// 以下このソースで有効なstatic関数のプロトタイプ宣言

// ファイルを読み込み、static配列の値を更新する関数
static void count_symbols(const char *filename);

// symbol_count をリセットする関数
static void reset_count(void);

// 与えられた引数でNode構造体を作成し、そのアドレスを返す関数
static Node *create_node(int symbol, int count, Node *left, Node *right);

// Node構造体へのポインタが並んだ配列から、最小カウントを持つ構造体をポップしてくる関数
// n は 配列の実効的な長さを格納する変数を指している（popするたびに更新される）
static Node *pop_min(int *n, Node *nodep[]);

// ハフマン木を構成する関数
static Node *build_tree(void);


// 以下 static関数の実装
static void count_symbols(const char *filename) {
    FILE *fp = fopen(filename, "rb");
    if (fp == NULL) {
        fprintf(stderr, "error: cannot open %s\n", filename);
        exit(1);
    }

    // 1Byteずつ読み込み、カウントする
    /*
      write a code for counting
    */

    fclose(fp);
}

static void reset_count(void) {
    for (int i = 0 ; i < NSYMBOLS ; i++) symbol_count[i] = 0;
}

static Node *create_node(int symbol, int count, Node *left, Node *right) {
    Node *ret = (Node *)malloc(sizeof(Node));
    *ret = (Node){ .symbol = symbol, .count = count, .left = left, .right = right};
    return ret;
}

static Node *pop_min(int *n, Node *nodep[]) {
    // Find the node with the smallest count
    // カウントが最小のノードを見つけてくる
    int argmin = 0;
    for (int i = 0; i < *n; i++) {
        if (nodep[i]->count < nodep[argmin]->count) {
            argmin = i;
        }
    }

    Node *node_min = nodep[argmin];

    // Remove the node pointer from nodep[]
    // 見つかったノード以降の配列を前につめていく
    for (int i = argmin; i < (*n) - 1; i++) {
        nodep[i] = nodep[i + 1];
    }
    // 合計ノード数を一つ減らす
    (*n)--;

    return node_min;
}

static Node *build_tree(void) {
    int n = 0;
    Node *nodep[NSYMBOLS];

    for (int i = 0; i < NSYMBOLS; i++) {
        // カウントの存在しなかったシンボルには何もしない
        if (symbol_count[i] == 0) continue;
        nodep[n++] = create_node(i, symbol_count[i], NULL, NULL);
    }

    const int dummy = -1; // ダミー用のsymbol を用意しておく
    while (n >= 2) {
        Node *node1 = pop_min(&n, nodep);
        Node *node2 = pop_min(&n, nodep);

        // Create a new node
        // 選ばれた2つのノードを元に統合ノードを新規作成
        // 作成したノードはnodepにどうすればよいか?

    }

    // なぜ以下のコードで木を返したことになるか少し考えてみましょう
    return (n==0)?NULL:nodep[0];
}



// Perform depth-first traversal of the tree
// 深さ優先で木を走査する
// 現状は何もしていない（再帰してたどっているだけ）
void traverse_tree(const int depth, const Node *np) {             
    if (np == NULL || np->left == NULL) return;

    traverse_tree(depth + 1, np->left);
    traverse_tree(depth + 1, np->right);
}

// この関数は外部 (main) で使用される (staticがついていない)
Node *encode(const char *filename) {
    reset_count();
    count_symbols(filename);
    Node *root = build_tree();

    if (root == NULL){
        fprintf(stderr,"A tree has not been constructed.\n");
    }

    return root;
}

encode.h
#pragma once

typedef struct node Node;

// ファイルをエンコードし木のrootへのポインタを返す
Node *encode(const char *filename);
// Treeを走査して表示する
void traverse_tree(const int depth, const Node *root);

演習

まず、encode.cをざっと読んでどんなことをしたいプログラムなのか把握してみましょう。
count_symbols()を完成させて、シンボルの出現回数を数えるように修正しましょう。
build_tree()を完成させましょう。
- ダミーノードのデータはダミー用のシンボル (-1) としましょう。

なお冒頭のハフマン符号の構成例では次々とリーフノードを追加していましたが、実際のデータではリーフ同士の統合やダミーノード同士の統合など全てのケースがあり得ることに注意してください。

こたえ

C言語の場合、特定の文字要素の出現回数を数える際によく使うテクニックにその文字を整数型のインデックスとして、配列の値をインクリメントしていく方法があります。今回はそれで実装します。この例では改行込みの1Byte単位なので、読み込みはシンプルにfgetcを用いています。この書き方の場合、バイナリデータも単純に1バイトずつ切り出されます。 最初のfopenでバイナリモードを指定している理由は、Windowsでテキストモードの場合、ファイル中に0x1aがあると、これをEOFとして止まってしまうことによります。

static void count_symbols(const char *filename) {
    FILE *fp = fopen(filename, "rb");
    if (fp == NULL) {
        fprintf(stderr, "error: cannot open %s\n", filename);
        exit(1);
    }
    int c;
    while( ( c = fgetc(fp)) != EOF ){
        symbol_count[c]++;
    }

    fclose(fp);
}

build_tree()のwhile文内を示します。ポイントは別途実装しているpop_minにより、用意している配列nodepの末尾の位置（n）が変わることと、統合ノードを作成後、その末尾に統合ノード追加することです。一回のループでnの値は結局1つずつ小さくなるので、いずれはwhile文の終了条件に到達します。

const int dummy = -1; // ダミー用のsymbol を用意しておく
while (n >= 2) {
    Node *node1 = pop_min(&n, nodep);
    Node *node2 = pop_min(&n, nodep);

    // Create a new node
    // pop_min によりnはnodep終端を変更しているので、終端に突っ込んで一つ増やす
    nodep[n++] = create_node(dummy, node1->count + node2->count, node1, node2);

}

レポート

本日はここまでです。宿題として以下をお願いします。

UTOLのアンケートの「アカウント申告」に答えて、GitHubアカウント名を門本まで教えてください。
- ソフトウェア1で報告済かと思うのですが、改めてお願いします。
- GitHubアカウントを登録してもらわないと、成績がつきませんので注意してください。
UTOLの課題の「第1回レポート」から、レポートを提出してください。
- 締切は次の授業の前日の夜23:59までです（今回の場合、2025/12/10, 23:59）
- 全てのプログラム/ファイルをまとめ、zip またはtar.gzで圧縮し提出
- ファイル名はweek1-1-NNNNNNNN.zipまたはweek1-1-NNNNNNNN.tar.gzとする
  - NNNNNNNN部分は学籍番号 (ハイフンは除く)
    - J0123456のようにする
- レポートの内容は以下になります

week1_1

最後の演習のencode.cにおけるtraverse_tree()関数を修正し、各シンボルに対するハフマン符号語を求められるようにしてみましょう。

符号語はまずは文字列（01の列）として表示するだけでよいです。
ツリー構造がわかるように表示を工夫すること。
- 改行についてはそのまま表示すると表示が崩れるため、LFや\nを表示するなどすること。

ツリー構造の表示は例えば、UNIXでディレクトリ構造を表示するtreeコマンドの以下のような表示を参考にするとよいです。ただし以下ではUnicode文字が用いられているので、これを避ける場合は例えば+や-を駆使して表示することが考えられます。

.
├── bin
├── include
│   └── qsort.h
├── lib
└── src
    ├── main.c
    └── qsort_lib.c

第1回 バイナリ、アルゴリズム1

コンパイルとリンク

コンパイルの流れ

分割コンパイル

ソースコードの分割

インクルードガード

定義を含む場合の分割コンパイル

宣言と定義の分離

ライブラリ

静的ライブラリの作成と利用

適切なディレクトリ構成

木構造

二分木

木構造データの走査

アプリケーション: ハフマン符号

符号

符号化

接頭符号

ハフマン符号

木の作成

符号の作成

サンプルプログラム

レポート

第1回バイナリ、アルゴリズム1