スタック

先週書いた連結リストのコードをライブラリにして、スタックを実装してみた。

#include
#include

#include "linkedlist.h"

#define Stack Cell

Stack *Push(Stack *stack, int x);
int Pop(Stack **stack);

int main(void)
{
    Stack *stack;
    int n;

    stack = NULL;

    stack = Push(stack, 1);
    stack = Push(stack, 3);
    stack = Push(stack, 5);

    DisplayList(stack);

    n = Pop(&stack);
    printf("%d <- ", n);
    DisplayList(stack);
    FreeList(stack);

    return 0;
}

Stack *Push(Stack *stack, int x)
{
    Stack *list;
    list = Cons(x, stack);
    return list;
}

int Pop(Stack **stack)
{
    int x;
    x = Head(stack);
    return x;
}
typedef struct cell Cell;

Cell *NewCell(int val);
Cell *Cons(int val, Cell *list);
Cell *Insert(Cell *list, int pos, int val);
Cell *Delete(Cell *list, int pos);
int Head(Cell **list);
void DisplayList(Cell *list);
void FreeList(Cell *list);
#include

#include "linkedlist.h"

typedef struct cell {
    int value;
    struct cell *next;
} Cell;

Cell *NewCell(int val)
{
    Cell *data;

    data = (Cell *)malloc(sizeof(Cell));
    data->value = val;
    data->next = NULL;

    return data;
}

Cell *Cons(int val, Cell *list)
{
    Cell *data;

    data = NewCell(val);
    data->next = list;

    return data;
}

Cell *Insert(Cell *list, int pos, int val)
{
    Cell *cell1, *cell2;
    int i = 1;

    if (pos == 0) {
        list = Cons(val, list);
    } else {
        cell1 = list;
        while (i < pos) {
            cell1 = cell1->next;
            i++;
        }
        cell2 = NewCell(val);
        cell2->next = cell1->next;
        cell1->next = cell2;
    }

    return list;
}

Cell *Delete(Cell *list, int pos)
{
    Cell *cell1, *cell2;
    int i = 1;

    if (pos == 0) {
        cell2 = list;
        list = cell2->next;
        free(cell2);
    } else {
        cell1 = list;
        cell2 = cell1->next;
        while (i < pos) {
            cell1 = cell2;
            cell2 = cell1->next;
            i++;
        }
        cell1->next = cell2->next;
        free(cell2);
    }

     return list;
}

int Head(Cell **list)
{
    int val;

    val = (*list)->value;
    *list = Delete(*list, 0);

    return val;
}

void DisplayList(Cell *list)
{
    printf("%d", list->value);
    if (list->next == NULL) {
        printf("\n");
    } else {
        printf(", ");
        DisplayList(list->next);
    }
}

void FreeList(Cell *list)
{
    Cell *next = list->next;

    free(list);
    if (next != NULL) {
        FreeList(next);
    }
}

linkedlist.h で

typedef struct cell Cell;

とあるのは、構造体の中身を隠蔽して、その存在だけを公開する書き方。こうすることで、ライブラリを利用する側からは構造体を直接操作することはできなくなる(操作用の関数を使って操作する)。

実行結果:

takatoh@nightschool $ gcc -Wall main.c -c
takatoh@nightschool $ gcc -Wall linkedlist.c -c
takatoh@nightschool $ gcc -Wall main.o linkedlist.o -o stack
takatoh@nightschool $ ./stack
5, 3, 1
5 <- 3, 1

出力の1行目は値(整数)を3つ push したあとのスタックの状態。2行目の <- の左側は pop して取出した値で、右側がそのあとのスタックの状態。 期待通りに動いてるようだ。

連結リスト

連結リスト(linked list、リンクリスト)とは、構造体のメンバに「次の構造体へのポインタ」を持たせて、数珠つなぎにしたデータ構造。いちばん最後の構造体の持つポインタは NULL。ようするに Scheme のリストと同じ構造だと思って良さそう。

#include
#include

typedef struct cell {
    int value;
    struct cell *next;
} Cell;

Cell *NewCell(int val);
Cell *Cons(int val, Cell *list);
Cell *Insert(Cell *list, int pos, int val);
Cell *Delete(Cell *list, int pos);
int Head(Cell **list);
void DisplayList(Cell *list);
void FreeList(Cell *list);

int main(void)
{
    Cell *list;
    int i, head;

    list = NewCell(0);
    for (i = 1; i < 10; i++) {
        list = Cons(i, list);
    }
    puts("before:");
    DisplayList(list);
    list = Insert(list, 5, 10);
    puts("insert 10 at 5th position:");
    DisplayList(list);
    list = Delete(list, 0);
    puts("delete 0th cell:");
    DisplayList(list);
    head = Head(&list);
    printf("pick up head value (and delete the cell): %d\n", head);
    DisplayList(list);
    FreeList(list);

    return 0;
}

Cell *NewCell(int val)
{
    Cell *data;

    data = (Cell *)malloc(sizeof(Cell));
    data->value = val;
    data->next = NULL;

    return data;
}

Cell *Cons(int val, Cell *list)
{
    Cell *data;

    data = NewCell(val);
    data->next = list;

    return data;
}

Cell *Insert(Cell *list, int pos, int val)
{
    Cell *cell1, *cell2;
    int i = 1;

    if (pos == 0) {
        list = Cons(val, list);
    } else {
        cell1 = list;
        while (i < pos) {
            cell1 = cell1->next;
            i++;
        }
        cell2 = NewCell(val);
        cell2->next = cell1->next;
        cell1->next = cell2;
    }

    return list;
}

Cell *Delete(Cell *list, int pos)
{
    Cell *cell1, *cell2;
    int i = 1;

    if (pos == 0) {
        cell2 = list;
        list = cell2->next;
        free(cell2);
    } else {
        cell1 = list;
        cell2 = cell1->next;
        while (i < pos) {
            cell1 = cell2;
            cell2 = cell1->next;
            i++;
        }
        cell1->next = cell2->next;
        free(cell2);
    }

    return list;
}

int Head(Cell **list)
{
    int val;

    val = (*list)->value;
    *list = Delete(*list, 0);

    return val;
}

void DisplayList(Cell *list)
{
    printf("%d", list->value);
    if (list->next == NULL) {
        printf("\n");
    } else {
        printf(", ");
        DisplayList(list->next);
    }
}

void FreeList(Cell *list)
{
    Cell *next = list->next;

    free(list);
    if (next != NULL) {
        FreeList(next);
    }
}

Head() がちょっと難儀したので説明しておこう。
main() の中で list は連結リストの先頭へのポインタだ。Head() の呼び出しは Head(&list) というふうにしている。で、Head() の定義は、Head(Cell **list) となっていて **list はポインタへのポインタを表している。&list というのは list のアドレスを表しているので、この関数の引数は「連結リストの先頭のアドレスを保持する変数のアドレス」を渡していることになる。
なんでこういうことをしているかというと、Head() はリストの先頭の値を返すだけじゃなくて先頭のセルを削除する。ということはリストの先頭のアドレスが変わるってこと。ポインタの値を変更するには、こういうふうにポインタのポインタを渡して、関数内でアドレスを書き換えてやるわけだ。
ちなみに、Delete() もリストの先頭を削除するので、先頭へのポインタの値が変化するけど、こっちは素直に変更されたアドレスを返している(ほかに返す値がないから)。

実行結果:

takatoh@nightschool $ ./linkedlist
before:
9, 8, 7, 6, 5, 4, 3, 2, 1, 0
insert 10 at 5th position:
9, 8, 7, 6, 5, 10, 4, 3, 2, 1, 0
delete 0th cell:
8, 7, 6, 5, 10, 4, 3, 2, 1, 0
pick up head value (and delete the cell): 8
7, 6, 5, 10, 4, 3, 2, 1, 0

終了ステータス(EXIT_SUCCESSとEXIT_FAILURE)

main() 関数での return 文や、exit() 関数でプログラムを終了するときに渡す値は、終了ステータスといって、プログラムからシステム(OS)に返される。プログラムにもよるけど、通常は正常終了なら 0、何らかのエラーが起これば 1 を返すようだ。

stdlib.h には、そのためのマクロ、EXIT_SUCCESS と EXIT_FAILURE が定義されている。

ちょっと使ってみよう。次のプログラムは、名前をひとつパラメータにとってあいさつを返す。パラメータが無かったり多すぎる場合には、使い方を表示して終了する。その際、EXIT_SUCCESS または EXIT_FAILURE を終了ステータスとして返している。

#include
#include

void Usage(char prog_name[]);

int main(int argc, char *argv[])
{
    if (argc != 2) {
        Usage(argv[0]);
        exit(EXIT_FAILURE);
    }

    printf("Hello, %s!\n", argv[1]);

    return EXIT_SUCCESS;
}

void Usage(char prog_name[])
{
    printf("Usage: %s \n", prog_name);
}

実行結果。終了ステータスは、特殊な変数 $? に格納されているので、それも表示してみる。まずは正常な使い方の場合:

takatoh@nightschool $ ./greeting Andy
Hello, Andy!
takatoh@nightschool $ echo $?
0

つぎに、パラメータがない、異常終了の場合:

takatoh@nightschool $ ./greeting
Usage: ./greeting <name>
takatoh@nightschool $ echo $?
1

正常な場合には、終了ステータスとして 0 が、そうでない場合には 1 が返されているのがわかる。

関数の引数として関数ポインタを渡す

関数の引数に、関数ポインタを渡すことによって、高階関数のようなことができる。

次のプログラムは、整数の配列にフィルタをかけてその結果を表示する。Filter() 関数は奇数だけを残すために Odd()、偶数だけを残すために Even() をそれぞれ受け取ることで、ひとつの関数で 2 種類のフィルタとして動作している。

#include

#define MAX 10

int Odd(int val);
int Even(int val);
int Filter(int (*func)(int), int items[], int results[], int n);

int main(void)
{
    int items[MAX] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int odds[MAX];
    int evens[MAX];
    int i, n;

    printf("before: ");
    for (i = 0; i < MAX; i++) {
        printf("%d ", items[i]);
    }
    printf("\n");
    n = Filter(Odd, items, odds, MAX);
    printf("odds: ");
    for (i = 0; i < n; i++) {
        printf("%d ", odds[i]);
    }
    printf("\n");
    n = Filter(Even, items, evens, MAX);
    printf("evens: ");
    for (i = 0; i < n; i++) {
        printf("%d ", evens[i]);
    }
    printf("\n");

    return 0;
}

int Odd(int val)
{
    if (val & 1) {
        return 1;
    } else {
        return 0;
    }
}

int Even(int val)
{
    if (!(val & 1)) {
        return 1;
    } else {
        return 0;
    }
}

int Filter(int (*func)(int), int items[], int results[], int n)
{
    int i, j = 0;

    for (i = 0; i < n; i++) {
        if ((*func)(items[i])) {
            results[j++] = items[i];
        }
    }

    return j;
} 
takatoh@nightschool $ gcc -Wall filter.c -o filter
takatoh@nightschool $ ./filter
before: 1 2 3 4 5 6 7 8 9 10 
odds:   1 3 5 7 9 
evens:  2 4 6 8 10

ところで、関数ポインタの型は引数名は書かなくてもいいんだな。つまり、

int (*func)(int val)

じゃなくて

int (*func)(int)

でいいということ。

staticな関数、変数

記憶クラス指定子のエントリで、関数内部の変数に static をつけるとその変数は関数を抜けても値を保持する、というようなことを書いた。

static にはもうひとつの使い方がある。
関数や、関数の外で宣言される変数に static をつけると、その関数や変数はファイルの中だけで有効になる。

これは、外部に公開したくない関数や変数をファイル内に隠蔽する効果がある。また、グローバル空間に公開されないので、関数や変数の名前が衝突することを避けることにもなる。

というわけで、ファイルの外部に公開しない関数や変数には static をつけておくのがいいようだ。

#include

#include "btree.h"

typedef struct tree {
    int value;
    struct tree *left;
    struct tree *right;
} Tree;

static Tree *Insert(Tree *root, int val);
static int Traverse(Tree *root, int ary[], int n);
static void FreeTree(Tree *root);

void BTreeSort(int ary[], const int n)
{
    int i;
    Tree *root = NULL;

    for (i = 0; i < n; i++) {
        root = Insert(root, ary[i]);
    }
    Traverse(root, ary, 0);
    FreeTree(root);
}

static Tree *Insert(Tree *root, int val)
{
    if (root == NULL) {
        root = (Tree *)malloc(sizeof(Tree));
        root->value = val;
        root->left = NULL;
        root->right = NULL;
    } else {
        if (val < root->value) {
            root->left = Insert(root->left, val);
        } else {
            root->right = Insert(root->right, val);
        }
    }

    return root;
}

static int Traverse(Tree *root, int ary[], int n)
{
    if (root->left != NULL) {
        n = Traverse(root->left, ary, n);
    }
    ary[n++] = root->value;
    if (root->right != NULL) {
        n = Traverse(root->right, ary, n);
    }

    return n;
}

static void FreeTree(Tree *root)
{
    if (root == NULL) {
        return;
    } else {
        FreeTree(root->left);
        FreeTree(root->right);
        free(root);
        return;
    }
}

ヘッダファイル

昨日は、btreesort を作るのに main.c と btree.c の 2つのファイルに分割した。main.c では btree.c の中で定義している BTreeSort() 関数を使うために、関数プロトタイプを記述した。
さて、例えばプログラムがもっと大規模になって、ソースファイルの数も増えるとしよう。BTreeSort() 関数もいくつかのソースファイルから使うようになるかもしれない。そうした場合、そのいくつかのソースファイル全てに関数プロトタイプを記述するのは効率が悪い。また、間違いのもとでもある。今回の例では関数ひとつしかないけど、一般的に考えればもっと多くの関数があるかもしれないし、構造体などの定義も必要かもしれない。そうなると、関数や構造体を使用するソースファイル全てに間違いなく記述するのは困難になってくる。
それを解決するのがヘッダファイル(*.h ファイル)だ。外部に公開したい関数のプロトタイプなどはヘッダファイルに記述しておき、それを使いたいソースファイルではそのヘッダファイルをインクルードすればいい。

早速やってみよう。今回の例では、btree.h というファイル名になる。

void BTreeSort(int ary[], const int n);

公開したい関数がひとつしかないので、ヘッダファイル(btree.h)もその関数プロトタイプだけだ。
一般的には、次のようなものをヘッダファイルに記述する。

  • 外部に公開するマクロの定義(関数型マクロの定義)
  • 外部に公開する定数の定義(#define や enum による定義)
  • 外部に公開する構造体、共用体の定義
  • 外部に公開する型の定義(typedef による型の定義)
  • グローバル関数のプロトタイプ宣言
  • グローバル変数の extern 宣言

5つ目のが今回の場合に当たる。

で、ソースファイル(main.c、btree.c)の方では、次のように btree.h をインクルードする。

#include
#include
#include

#include "btree.h"

#define MAX 10

void PrintArray(int ary[]);

int main(void)
{
    int i;
    int ary[MAX];

    srand((unsigned)time(NULL));

    for (i = 0; i < MAX; i++) {
        ary[i] = rand() % 100;
    }
    printf("unsorted: ");
    PrintArray(ary);
    BTreeSort(ary, MAX);
    printf("sorted: ");
    PrintArray(ary);

    return 0;
}

void PrintArray(int ary[])
{
    int i;

    for (i = 0; i < MAX; i++) {
        printf("%2d ", ary[i]);
    }
    printf("\n");
}
#include

#include "btree.h"

typedef struct tree {
    int value;
    struct tree *left;
    struct tree *right;
} Tree;

Tree *Insert(Tree *root, int val);
int Traverse(Tree *root, int ary[], int n);
void FreeTree(Tree *root);

void BTreeSort(int ary[], const int n)
{
    int i;
    Tree *root = NULL;

    for (i = 0; i < n; i++) {
        root = Insert(root, ary[i]);
    }
    Traverse(root, ary, 0); FreeTree(root);
}

Tree *Insert(Tree *root, int val)
{
    if (root == NULL) {
        root = (Tree *)malloc(sizeof(Tree));
        root->value = val;
        root->left = NULL;
        root->right = NULL;
    } else {
        if (val < root->value) {
            root->left = Insert(root->left, val);
        } else {
            root->right = Insert(root->right, val);
        }
    }

    return root;
}

int Traverse(Tree *root, int ary[], int n)
{
    if (root->left != NULL) {
        n = Traverse(root->left, ary, n);
    }
    ary[n++] = root->value;
    if (root->right != NULL) {
        n = Traverse(root->right, ary, n);
    }

    return n;
}

void FreeTree(Tree *root)
{
    if (root == NULL) {
        return;
    } else {
        FreeTree(root->left);
        FreeTree(root->right);
        free(root);

        return;
    }
}

うまくコンパイルできるかな?

takatoh@nightschool $ ls
btree.c  btree.h  main.c
takatoh@nightschool $ gcc -Wall main.c -c
takatoh@nightschool $ gcc -Wall btree.c -c
takatoh@nightschool $ ls
btree.c  btree.h  btree.o  main.c  main.o
takatoh@nightschool $ gcc main.o btree.o -o btreesort
takatoh@nightschool $ ls
btree.c  btree.h  btree.o  btreesort  main.c  main.o
takatoh@nightschool $ ./btreesort
unsorted: 89 46 78 22  0 23 82 86 84 64 
sorted:    0 22 23 46 64 78 82 84 86 89

出来た。

分割コンパイル

プログラムの規模が大きくなると、ソースファイルを複数に分割して記述するのが普通だ。
というわけで、試しに昨日の btreesort を分割してみた。ソートを実装する btree.c と main() 関数のある main.c だ。
まずは main.c。

#include
#include
#include

#define MAX 10

void PrintArray(int ary[]);
void BTreeSort(int ary[], const int n);

int main(void)
{
    int i;
    int ary[MAX];

    srand((unsigned)time(NULL));

    for (i = 0; i < MAX; i++) {
        ary[i] = rand() % 100;
    }
    printf("unsorted: ");
    PrintArray(ary);
    BTreeSort(ary, MAX);
    printf("sorted: ");
    PrintArray(ary);

    return 0;
}

void PrintArray(int ary[])
{
    int i;

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

10行目に注目。BTreeSort() の関数プロトタイプを記述して、このファイルの中で使えるようにしてある。 で、その BTreeSort() 本体は btree.c に記述する。

#include

typedef struct tree {
    int value;
    struct tree *left;
    struct tree *right;
} Tree;

void BTreeSort(int ary[], const int n);
Tree *Insert(Tree *root, int val);
int Traverse(Tree *root, int ary[], int n);
void FreeTree(Tree *root);

void BTreeSort(int ary[], const int n)
{
    int i;
    Tree *root = NULL;

    for (i = 0; i < n; i++) {
        root = Insert(root, ary[i]);
    }
    Traverse(root, ary, 0);
    FreeTree(root);
}

Tree * Insert(Tree *root, int val)
{
    if (root == NULL) {
        root = (Tree *)malloc(sizeof(Tree));
        root->value = val;
        root->left = NULL;
        root->right = NULL;
    } else {
        if (val < root->value) {
            root->left = Insert(root->left, val);
        } else {
            root->right = Insert(root->right, val);
        }
    }

    return root;
}

int Traverse(Tree *root, int ary[], int n)
{
    if (root->left != NULL) {
        n = Traverse(root->left, ary, n);
    }
    ary[n++] = root->value;
    if (root->right != NULL) {
        n = Traverse(root->right, ary, n);
    }

    return n;
}

void FreeTree(Tree *root)
{
    if (root == NULL) {
        return;
    } else {
        FreeTree(root->left);
        FreeTree(root->right);
        free(root);
        return;
    }
}

さて、分割コンパイルだ。
今まではソースファイルが1つだったので、ひとつの gcc コマンドでいっぺんに実行ファイルを作っていた。実際には、gcc は *.c ファイルから *.o ファイルを作り、*.o ファイルから実行ファイルを作る。*.o ファイルをオブジェクトファイルとよび、オブジェクトファイルを作ることをコンパイル、オブジェクトファイルから実行ファイルを作ることをリンクという。リンクは複数のオブジェクトファイルのほか、標準ライブラリなどもリンクする。
gcc では -c オプションをつけることで、上に書いたコンパイル、つまり実行ファイルじゃなくて *.o ファイルを作ることができる。複数のソースファイルに分けた場合、ひとつずつコンパイルすること(オブジェクトファイルを作ること)を分割コンパイルという。
オブジェクトファイルは実行ファイルではないので、最終的に実行ファイルを作るには、リンクする必要がある。じゃあなぜ分割コンパイルするのかといえば、例えばあるソースファイルだけ修正した場合、それだけコンパイルしなおせば、あとはコンパイル済みのオブジェクトファイルとリンクすればいい。つまりコンパイルの時間(と手間)が省力化できるってわけだ。

やってみよう。まずは main.c から。

takatoh@nightschool $ ls
btree.c  main.c
takatoh@nightschool $ gcc -Wall main.c -c
takatoh@nightschool $ ls
btree.c  main.c  main.o

オブジェクトファイル main.o が出来た(警告も出ていない)。
つぎ、btree.c。

takatoh@nightschool $ gcc -Wall btree.c -c
takatoh@nightschool $ ls
btree.c  btree.o  main.c  main.o

こちらもオブジェクトファイルが出来た。
これら2つのオブジェクトファイルをリンクするには次のようにする。

takatoh@nightschool $ gcc main.o btree.o -o btreesort
takatoh@nightschool $ ls -l
合計 28
-rw-rw-r-- 1 takatoh takatoh 1384  6月 27 08:01 btree.c
-rw-rw-r-- 1 takatoh takatoh 2360  6月 27 13:48 btree.o
-rwxrwxr-x 1 takatoh takatoh 9056  6月 27 13:49 btreesort
-rw-rw-r-- 1 takatoh takatoh  614  6月 27 08:00 main.c
-rw-rw-r-- 1 takatoh takatoh 2248  6月 27 13:47 main.o

これで実行ファイル btreesort が出来た。
うまく動くか試してみよう。

takatoh@nightschool $ ./btreesort
unsorted: 59 12 88 98 83 78  6 38 88 55 
sorted:    6 12 38 55 59 78 83 88 88 98

OK。大丈夫みたい。

gcc -Wallオプション

入門書「独習 C」を読み終わったので、今度は「C言語 入門書の次に読む本」というのを読み始めた。
で、gcc に -Wall オプションがあるのを知った。-Wall オプションは、コンパイル時にいろいろな警告を出すオプションのあらかた(全部じゃない)をまとめて指定するオプションで、これをつけてコンパイルすることでかなり細かい警告を出してくれる。この本では -Wall オプションをつけてコンパイルすることを強く薦めている。

じゃ、早速やってみよう。ネタは先日の btreesort.c。

takatoh@nightschool $ gcc -Wall btreesort.c -o btreesort
btreesort.c: In function ‘main’:
btreesort.c:28:5: warning: implicit declaration of function ‘time’ [-Wimplicit-function-declaration]
     srand((unsigned)time(NULL));
     ^
btreesort.c:26:11: warning: unused variable ‘root’ [-Wunused-variable]
     Tree *root = NULL;
           ^

コンパイルは出来たけど、警告が2つ出た。1つ目の implicit declaration of function ‘time’ は time 関数の暗黙の宣言という警告で、time.h をインクルードしていないのが原因のようだ。gcc は宣言のない関数を見つけると、その返り値が int だと仮定してコンパイルするらしい。とにかく、これは time.h をインクルードして解決。
2つ目の unused variable ‘root’ は使ってない変数があるってことだろう。これはこの変数の宣言を消せばOK。
次のように修正した。

takatoh@nightschool $ git diff
diff --git a/sandbox/btreesort.c b/sandbox/btreesort.c
index a96a16d..08da355 100644
--- a/sandbox/btreesort.c
+++ b/sandbox/btreesort.c
@@ -1,5 +1,6 @@
 #include <stdio.h>
 #include <stdlib.h>
+#include <time.h>
 
 
 #define MAX 10
@@ -23,7 +24,6 @@ int main(void)
 {
     int i;
     int ary[MAX];
-    Tree *root = NULL;
 
     srand((unsigned)time(NULL));
 

もう一度コンパイルしてみよう。

takatoh@nightschool $ gcc -Wall btreesort.c -o btreesort
takatoh@nightschool $ ./btreesort
unsorted: 55 57 58 63 86 24 12 74 84 29 
sorted:   12 24 29 55 57 58 63 74 84 86

今度は何も警告なしにコンパイルできた。

[amazonjs asin=”4774146129″ locale=”JP” title=”C言語 入門書の次に読む本 改訂新版 (プログラミングの教科書)”]

二分木を使ったソート

単純な二分木を使ったソート。
構造体で二分木を表現するのと、malloc() / free() の練習。

#include
#include

#define MAX 10

typedef struct tree {
    int value;
    struct tree *left;
    struct tree *right;
} Tree;

void PrintArray(int ary[]);
void BTreeSort(int ary[], const int n);
Tree *Insert(Tree *root, int val);
int Traverse(Tree *root, int ary[], int n);
void FreeTree(Tree *root);

int main(void)
{
    int i;
    int ary[MAX];
    Tree *root = NULL;

    srand((unsigned)time(NULL));

    for (i = 0; i < MAX; i++) {
        ary[i] = rand() % 100;
    }
    printf("unsorted: ");
    PrintArray(ary);
    BTreeSort(ary, MAX);
    printf("sorted: ");
    PrintArray(ary);

    return 0;
}

void PrintArray(int ary[])
{
    int i;

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

void BTreeSort(int ary[], const int n)
{
    int i;

    Tree *root = NULL;
    for (i = 0; i < n; i++) {
        root = Insert(root, ary[i]);
    }
    Traverse(root, ary, 0);
    FreeTree(root);
}

Tree *Insert(Tree *root, int val)
{
    if (root == NULL) {
        root = (Tree *)malloc(sizeof(Tree));
        root->value = val;
        root->left = NULL;
        root->right = NULL;
    } else {
        if (val < root->value) {
            root->left = Insert(root->left, val);
        } else {
            root->right = Insert(root->right, val);
        }
    }

    return root;
}

int Traverse(Tree *root, int ary[], int n)
{
    if (root->left != NULL) {
        n = Traverse(root->left, ary, n);
    }
    ary[n++] = root->value;
    if (root->right != NULL) {
        n = Traverse(root->right, ary, n);
    }

    return n;
}

void FreeTree(Tree *root)
{
    if (root == NULL) {
        return;
    } else {
        FreeTree(root->left);
        FreeTree(root->right);
        free(root);
        return;
    }
}
takatoh@nightschool $ ./btreesort
unsorted: 80 77 21 42 50 76 88 48 32 19 
sorted:   19 21 32 42 48 50 76 77 80 88

C99

以前コメントでもらったけど、現在の標準の C というのは、ANSI C ではなく C99(ISO/IEC 9899:1999)のことのようだ。入門書(「独習 C」)もひと通り読み終わったことだし、ここで C99 の新機能について主なところをまとめておこう。
参考にしたのはこのページ。

 cf. C99の仕様 – C言語最新事情

bool型

真偽値を表すブール型が追加された。標準では型名が _Bool となっているけど、stdbool.h を読み込むことで bool という型名と、値として true、false が使えるようになる。

#include
#include

bool isoctal(char c)
{
    return '0' <= c && c < '8';
}

int main(void)
{
    char c = '3';
    if (isoctal(c)) {
        printf("%c is octal.\n", c);
    }
    return 0;
}
takatoh@nightschool $ ./bool
3 is octal.

可変長配列

可変長といっても自由に長さを変えられるのではなくて、実行時に配列の長さを指定できるようになった。

#include

size_t fsize3(int n)
{
    char b[n + 3];

    return sizeof b;
}

int main(void)
{
    printf("%ld\n", fsize3(10));

    return 0;
}
takatoh@nightschool $ ./array
13

C++コメント

// 以降行末までがコメントとして扱われるようになった。

関数名マクロ

__func__ というマクロが追加された。これは現在の関数の名前を表す。

#include

void myfunc(void)
{
    printf("%s\n", __func__);
}

int main(void)
{
    myfunc();

    return 0;
}
takatoh@nightschool $ ./mfunc
myfunc

指示初期化子

指示初期化子を使うと、配列の特定の添字、構造体の特定のメンバを初期化できる。
まずは配列の場合:

#include

void PrintArray(int ary[]);

int main(void)
{
    int a[] = {
        [9] = 1
    };

    PrintArray(a);

    return 0;
}

void PrintArray(int *ary)
{
    int i;

    for (i = 0; i < 10; i++) {
        printf("%d ", ary[i]);
    }
    printf("\n");
}
takatoh@nightschool $ ./init1
0 0 0 0 0 0 0 0 0 1

上の例では、配列の添字9の要素を 1 に初期化している。この場合配列は次のように初期化される。

  • 配列のサイズが未知の場合、指示初期化子で指定された最大のものをもとにサイズが決定される。
  • 指示初期化子で指定されなかった添字の領域は、int型では 0 に初期化され、ポインタではヌルポインタに初期化される。

指示初期化子は複数指定することも可能。また、通常の初期化子と混ぜて使うことも可能で、通常の初期化子は指示初期化子の添字に続くものとして解釈される。

#include

void PrintArray(int ary[]);

int main(void)
{
    int a[] = {
        [3] = 1,
        2,
        [8] = 3,
        4
    };

    PrintArray(a);

    return 0;
}

void PrintArray(int *ary)
{
    int i;

    for (i = 0; i < 10; i++) {
        printf("%d ", ary[i]);
    }
    printf("\n");
}
takatoh@nightschool $ ./init2
0 0 0 1 2 0 0 0 3 4

構造体の指示初期化子は「.メンバー」。

#include

typedef struct {
    int x;
    int y;
    int width;
    int height;
} Rectangle;

int main(void)
{
    Rectangle r = { .x = 1 };

    printf("x = %d\n", r.x);
    printf("y = %d\n", r.y);
    printf("widht = %d\n", r.width);
    printf("height = %d\n", r.height);

    return 0;
}
takatoh@nightschool $ ./init3
x = 1
y = 0
widht = 0
height = 0

変数宣言

ANSI C では変数の宣言はブロックの先頭で行う必要があったけど、C99 ではブロックの途中でも宣言できるようになった。また、for 文に限ってループ変数の宣言が可能になった。このループ変数は for ブロックの中だけで有効。

#include
#include

int sum(int count, int a[])
{
    assert(count >= 0);

    int sum = 0;
    // Error in ANSI-C
    for (int i = 0; i < count; i++) {
        // Error in ANSI-C
        sum += a[i];
    }
    return sum;
}

int main(void)
{
    int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};

    printf("sum = %d\n", sum(sizeof(data) / sizeof(data[0]), data));

    return 0;
}
takatoh@nightschool $ ./localvar
sum = 45

複合リテラル

構造体や配列(ただし可変長配列を除く)をリテラルとして生成できるようになった。

#include

typedef struct {
    int x;
    int y;
} Point;

Point Center(const Point *p1, const Point *p2)
{
    return (Point) {
        .x = (p1->x + p2->x) / 2,
        .y = (p1->y + p2->y) / 2
    };
}

int main(void)
{
    Point p = Center(&(Point){1, 1}, &(Point){3, 3});
    printf("(%d, %d)\n", p.x, p.y);

    return 0;
}
takatoh@nightschool $ ./compound_literal
(2, 2)

上の例では、Center 関数の呼び出し時と、Center 関数が値を返すときに構造体の複合リテラルを使っている。
……ところで複合ってどういう意味だろう?

さて、こんなところだろうか。