サイトマップ / Ｃ言語講座＞出入り口＞総目次＞目次：ヒープ領域＞ヒープというデータ構造
/* 今日は、ヒープ（heap）について学びます。ヒープには二つ意味があります。
ライブラリ関数 malloc( ) で確保するメモリブロックは、プログラム実行時にヒープ領域に割り付けられます。半順序木（partial ordered tree）というデータ構造を実現するものも、ヒープといいます。今回学ぶのは、こちらのデータ構造の方です。
下記に示すのは、２分木というデータ構造です。今回、node[ ] という配列の添字０は使いませんので、それは無視して下さい。数字を斜めの線で結んでいませんが、１と２、１と３、２と４、２と５、３と６、３と７、以下同様に線で結ばれているものとします。
int node[ ] = {0,
1,
2, 3,
4, 5, 6, 7,
0, 0, 0, 0, 0, 0, 0, 0};
このようなデータ構造を、枝が一度に二つに分かれる木に見立てて、２分木といいます。一つ下の二つの要素を子、一つ上の要素を親といいます。一番上の要素を根といいます。つまり、２分木は逆さに生えている木です。
数字の並び方を良く見て下さい。親の値を２倍すると、左下の子になります。親の値の２倍に１を足すと右下の子になります。一番下の要素には、０が入っていますが、配列の添字としては、左から８、９、- - - となり、この関係は成り立っています。従って、配列 node[ ] で、node[n] の左下の子は node[2 * n] で、右下の子は node[2 * n + 1] でアクセスできます。
もし、ポインタを使って２分木構造を実現しようとすれば、左下の子と右下の子へのポインタを持たせなければなりません。子から親へ移動するには、更に、親へのポインタも必要です。今回のヒープというデータ構造を使えば、２分木を配列で実現できます。
子から親へは、node[n / 2] で簡単にアクセスできます。なお、n は int 型のデータなので、n が奇数で余りが出ても、余りは切り捨てられるので、親の要素になります。
今回のソースプログラムでは、ShowNode( ) は、上記の配列の要素を再帰的に表示します。２分木の最下段のデータを全て０にしたのは、再帰をストップさせるためです。詳細はソースプログラム中のコメントを見て下さい。 */
#include <stdio.h>
void ShowNode(int r);
void main(void);
int node[ ] = {0,
1,
2, 3,
4, 5, 6, 7,
0, 0, 0, 0, 0, 0, 0, 0};
void ShowNode(int r)
{
printf("%d\t", node[r]); /* 要素を表示 */
if (node[2 * r]) /* 左下の要素が０でなければ */
ShowNode(2 * r); /* それを表示 */
if (node[2 * r + 1]) /* 右下の要素が０でなければ */
ShowNode(2 * r + 1); /* それを表示 */
}
void main(void)
{ /* ２分木の根を引数にして、関数を呼び出す */
ShowNode(1);
}
|
/*実行結果と、２分木の構造とを良く見比べて下さい。再帰呼び出しの結果、どの要素がどのような順序で表示されるか、確認して下さい。 */
/* (C) 2000- ＹＦプロ. All Rights Reserved. */ 提供：Ｃ言語講座−それ自体コンパイルできる教材を使った講座です−