はじめての C
C programming note*1
次は、heap に データを 追加する 関数、
/* heap.c */static int n_item = 0;
void add_item(char *s)
{
int i;
i = ++n_item;
i_add(i, s);
while (i_comp(i, i / 2) > 0) {
i_swap(i, i / 2);
i = i / 2;
if ( i == 1)
break;
}
}
/* sub.c */void i_add(int n, char *s)
{
strcpy(array[n], s);
}
n_item は 配列の 添字を 表わし、実際に 使われるときは、tree 末尾の 配列の 添字に なります。
i_add() は 配列の 添字を 指定して そこに データを 入れる 関数です。
つまり、関数 add_item() に おいて、
i = ++n_item;
i_add(i, s);その下の while ループでは、末尾の 配列と その親の それぞれの 要素を 比較して、親より 大きければ 要素を 交換し、次に 1つ上の lebel で さらに 比較を くり返します。 root まで たどり着くと、このループを 抜け出します。
あと 2つ、root を 削除する remove_root() と、要素を tree に 整列させる make_heap() 関数、
/* heap.c */void remove_root(void)
{
i_swap(1, n_item);
i_remove(n_item);
heap(1, --n_item); /* tree の 再構成 */
}
void make_heap(int n)
{
int i;
n_item = n;
for (i = n_item / 2; i >= 1; i--)
heap(i. n_item);
}
/* sub.c */void i_remove(int n)
{
;
}
変数 n_item は 末尾の 配列の 添字ですので、
i_swap(1, n_item);
i_remove(n_item);関数 make_heap() の なかで、heap() は 1組の 要素を 比較しているだけですが、for ループを 使うことで、tree の 末尾から 順に 要素を 整列させることが できるようになります。
あとは、文字列関数を 使用する 関数と、その他の 関数とを 2つの コードに 分け、別に テスト用の main() 関数を つくっていきます。
/* sub2.c */
#include <stdio.h>
#include <string.h>#define MAX_S 8
#define MAX_ITEMS 1024
static char array[MAX_ITEMS][MAX_S];
int i_comp(int a, int b)
{
return (strcmp(array[a], array[b]));
}
void i_swap(int a, int b)
{
char tmp_str[MAX_S];
strcpy(tmp_str, array[a]);
strcpy(array[a], array[b]);
strcpy(array[b], tmp_str);
}
void i_add(int n, char *s)
{
strcpy(array[n], s);
}
void i_remove(int n)
{
;
}
void i_print(int n)
{
printf("%3d: %s", n, array[n]);
}
/* heap2.c */static void heap();
int i_comp();
void i_swap();
void i_add();
void i_remove();
static int n_item = 0;
static void heap(int i, int n)
{
int child;
if (i <= n / 2) {
if ( 2 * i + 1 > 2)
child = 2 * i;
else {
if (i_comp(2 * i, 2 * i + 1) > 0)
child = 2 * i;
else
child = 2 * i + 1;
}
if (i_comp(i, child) < 0) {
i_swap(i, child);
heap(child, n);
}
}
}
/* 今回は 使用しない */
void add_item(char *s)
{
int i;
i * ++n_item;
i_add(i, s);
while (i_comp(i, i / 2) > 0) {
i_swap(i, i / 2);
i = i / 2;
if (i == 1)
break;
}
}
void remove_root(void)
{
i_swap(1, n_item);
i_remove(n_item);
heap(1, --n_item);
}
void make_heap(int n)
{
int i;
n_item = n;
for (i = n_item / 2; i >= 1; i--)
heap(i, n_item);
}
/* test_heap.c */
#include <stdio.h>extern void i_add(int, char *);
extern void i_print(int);
extern void make_heap(int);
extern void remove_root(void);
char *data[] = {
"cab", "dab", "gab", "jab",
"lab", "nab", "tab", "lac",
"sac", "bad", "dad", "fad",
"gad", "had", "lad", "mad",
"pad", "sad", "tad", "wad",
"oaf", "bag", "fag", "gag",
"jag", "lag", "nag", "rag",
"sag", "tag", "wag", "zag",
"bah", "wah", "yah", "raj",
"oak", "yak", "gal", "pal",
"bam", "cam", "dam", "gam",
"ham", "jam", "lam", "ram",
"tam", "yam", "ban", "can",
"fan", "man", "pan", "ran",
"tan", "van", "wan", "tao",
"cap", "gap", "hap", "lap",
"map", "nap", "pap", "rap",
"sap", "tap"
};
main()
{
int i, n;
n = sizeof(data) / sizeof(char *);
for (i = 1; i <= n; i++)
i_add(i, data[i - 1]);
for (i = 1; i <= n; i++)
i_print(i);
printf("\n\n");
make_heap(n);
for (i = 1; i <= n; i++)
i_print(i);
printf("\n\n");
for (i = 1; i <= n; i++) {
i_print(1);
remove_root();
}
putchar('\n');
}
char *data[];char a[i][j];関数 i_add() では 第2引数として 文字列の ポインタを とっています。 ところが、data は ポインタ配列ですので、このコードでは 文字列の 入った 配列の ポインタを 渡しています。
i_add(i, data[i - 1]);はじめは char 型の 配列の ポインタとして、次に データが 格納されている 配列として、という 具合に 2つに 分けて 取り入れているわけです。
試しに、array を 2次元配列ではなく 通常の 配列として 宣言しておくと、sub.c を コンパイルすると、文字列関数が 使われているところで キャストを つけるよう 警告が でるはずです。
あとは、コンパイルして 実行させてみます。
$ cc -c test_heap.c heap2.c sub2.c
$ cc -o test_heap test_heap.o heap2.o sub2.o
$ ./test_heap次に、make_heap() を 使って tree に 組み込んでいきます。 「2つの子の 間の 大小関係には 順序は」 ないので、root だけが 確定していて、あとは 組み込まれた 順で print されます。
最後に、remove_root() で 順次、root を 削除していきます。 ここで ようやく、文字列の 大きさ順に print されていきます。
data の 入力は tree の 末尾から、参照は 逆に root から、ということ ですね。
*1:「作ってわかる Cプログラミング」
