はじめての C

lang

C programming note*1

プログラムは、必ず 何らかの データを 扱う。 重要なのは、処理の 流れだけでは ない。

その処理で 扱う データが どういう 形式で 保持されるか ということ、つまり 処理のしかたに 合った 内部の データ構造 data structure を 考えることも 重要なのだ。(p184)

という理由で、「基本的な データ構造」 のうち、マトリックス、スタック、キューと それに ヒープについて 取り上げていきます。
はじめの 3つは むずかしく ありません。
まず マトリックスから、

マトリックス matrix とは 2次元以上の 配列のことである。

C では、「2次元以上の 配列」 を 表わす 手段は 直接は 準備されていない。 そのため、2次元の 配列は いわば 「配列を要素とした 配列」 で 表現する。

例えば int型の 2次元配列だと、

 int a[4][5];

これは 「a[5] という 1次元の配列」 という 要素を 4つ もつ 配列として 表現しているわけだ。(p167)

説明は 以上で すべてです。
実際に どのように 使われるかは、K&R 2nd の p136 - p137 に 載っています。
http://d.hatena.ne.jp/sekiyo/20051105
次は スタック、

スタック stack は、最後に 追加した データが 最初に 取り出される データ構造だ (Last-In-First-Out)。

(すなわち) スタックは、先に 入れた データを 後回しにし、最も 最近に 入れた データから 新しい順に 取り出す 場合に 使う。(p188)

スタックの 説明も わずか これだけです。
スタックには push と pop という 2つの 基本的な 操作があり、そこでは 配列が 用いられています。

int x[MAX];

int sp = 0; /* stack pointer((← 配列の添字)) */
void push(int n)

{

    if (sp < MAX)

        x[sp++] = n;

    else

        fputs("stack full\n", stdout); /* overflow */

}
int pop(void)

{

    if (sp > 0)

        return x[--sp];

    else {

        fputs("stack empty\n", stdout); /* underflow */

        return 0;

    }

}

データを 引数にして push 関数を 呼び出すことにより、データが スタック (← 配列) に 格納される。 また、pop 関数を 呼び出すことにより、戻り値として スタックから データを 取り出すことが できる。(p189)

スタックを 使った 特殊な 例として、

たとえば、プログラム言語の 内部などでも、関数の 呼び出し時の 引数などは 一時的に スタックに 置かれる場合が 多い。 (また) 関数の中で さらに 関数を 呼び出しても、その新しい 呼び出しの 引数が 一時 スタックに 保存される。

呼び出した 関数から 戻るときには 一時的に 保存された 引数が スタックから 取り出されるので、効率よく 参照できるわけだ。(p188)

*1:「作ってわかる Cプログラミング」