BohYoh.comトップページへ

C言語によるアルゴリズムとデータ構造

戻る  

演習6-17の解答

           01
         / \
      03        05
    /   \    /\
  07      09  02  04
 /\   /
06  08  10
 関数downheap を呼び出すたびに、ヒープの内容を右図のように表示するように、関数heapsort を書きかえよ。

/* 演習6-17 ヒープソート(ソートの過程をグラフで表示) */ #include <stdio.h> #define swap(type, x, y) do { type t = x; x = y; y = t; } while (0) /*--- 2のn乗を求める ---*/ int pow2(int n) { int k = 1; while (n--) k *= 2; return (k); } /*--- ヒープを表示 ---*/ static void disp_heap(int a[], int n) { int i, w, level; int height = 1; /* 木の高さ */ i = n; while (i /= 2) height++; i = 0; w = 1; for (level = 0; level < height; level++) { int k; printf("%*s", pow2(height - level) - 2 , ""); for (k = 0; k < w; k++) { printf("%02d", a[i++]); if (i >= n) goto Exit; printf("%*s", pow2(height - level + 1) - 2, ""); } putchar('\n'); printf("%*s", pow2(height - level) - 3 , ""); for (k = 0; k < w; k++) { if (2 * k + i < n) printf("/"); if (2 * k + i + 1 < n) printf("\"); printf("%*s", pow2(height - level + 1) - 4, ""); } putchar('\n'); w *= 2; } Exit: putchar('\n'); putchar('\n'); } /*--- a[left]~a[right]をヒープ化 ---*/ static void downheap(int a[], int left, int right) { int temp = a[left]; /* 根 */ int child; int parent; for (parent = left; parent < (right + 1) / 2; parent = child) { int cl = parent * 2 + 1; /* 左の子 */ int cr = cl + 1; /* 右の子 */ child = (cr <= right && a[cr] > a[cl]) ? cr : cl; /* 大きい方 */ if (temp >= a[child]) break; a[parent] = a[child]; } a[parent] = temp; } /*--- ヒープソート ---*/ void heapsort(int a[], int n) { int i; for (i = (n - 1) / 2; i >= 0; i--) { disp_heap(a, n); downheap(a, i, n - 1); } for (i = n - 1; i > 0; i--) { swap(int, a[0], a[i]); disp_heap(a, n); downheap(a, 0, i - 1); } } int main(void) { int i; int x[100]; int n; int nx = sizeof(x) / sizeof(x[0]); do { printf("要素数(1~%d)は:", nx); scanf("%d", &n); } while (n < 1 || n > nx); printf("%d個の整数を入力せよ。\n", n); for (i = 0; i < n; i++) { printf("x[%d] : ", i); scanf("%d", &x[i]); } heapsort(x, n); /* 配列xをヒープソート */ puts("昇順にソートしました。"); for (i = 0; i < n; i++) printf("x[%d] = %d\n", i, x[i]); return (0); }


戻る