以下はヒープソートのプログラムです。それに以下の関数を追加するという問題がでました。
increase_key(H, i, a)
「ヒープH(ヒープ性を満たす)の指定をした頂点iに対し、H[i]の値をaに変更した後、失われた可能性のあるヒープ性を取り戻すように修正する。ただしaはa≧H[i]を満たす値とする」
この問題の意味がいまいちわかりません。
頂点iやaは標準入力から指定するということでしょうか?
また、やるべきことを教えていただけると幸いです。
#include <stdio.h> #include <stdlib.h> #include <string.h> /* 文字列関数を扱えるようにする */ #define maxN 50 int parent(int i); void heapsort(int*H, int *A, int n); void buildheap(int *H, int *A, int n); void insert(int *H, int i, int *a); void upheapsort(int *H, int i); void downheapsort(int *H, int i); int main(void) { int Data[maxN]; /* 数値を格納する配列は Data */ int Heap[maxN]; /* ヒープを表す補助配列 */ int i,N=0; /* N やループで用いる int 型変数 */ char fname[128]; FILE *fp; /* ファイル名の変数など必要なものを宣言 */ printf("input filename: "); /* ファイル名の入力を要求 */ fgets(fname, sizeof(fname), stdin); fname[strlen(fname)-1] = '\0'; fflush(stdin); fp = fopen(fname, "r"); /* ファイルを読み込みモードで開く */ fscanf(fp, "%d", &N); /* N をファイルから読み込む */ if (N > maxN){ printf("N is too large, setting N = %d\n", maxN); N = maxN; /* N が max Nを超えるときは警告をした上で */ } /* N =maxN に設定する */ for (i=0; i<N; i++){ fscanf(fp, "%d", &Data[i]); } fclose(fp); /* 開いたファイルを閉じる */ for (i=0; i<N; i++){ printf("% d", Data[i]); /* ソート前の数値の出力 */ } printf("\n"); heapsort(Heap, Data, N); /* ヒープソートを呼ぶ */ for (i=0; i<N; i++){ printf("% d", Data[i]); /* ソート後の数値の出力 */ } printf("\n"); return (0); } void heapsort(int*H, int *A, int n) { int i; buildheap(H, A, n); for(i=1; i<n; i++) { A[n-i] = H[0]; H[0] = H[n-i]; downheapsort(H, n-i-1); } A[0] = H[0]; } void buildheap(int *H, int *A, int n) { int i; for(i=0; i<n; i++) { insert(H, i, A); } } void insert(int *H, int i, int *a) { H[i] = a[i]; upheapsort(H,i); /* 入れ替え */ } void upheapsort(int *H, int i) { int u; int p; int j=0; int tmp[j]; u = i; p = parent(i); /*親の設定*/ while(u > 0 && H[p] < H[u]) { tmp[j] = H[p]; H[p] = H[u]; H[u] = tmp[j]; u = p; p = parent(p); } } int parent(int i) { int parent; parent = (i-1)/2; return parent; } void downheapsort(int *H, int i) { int l,r; int u = 0; int j=0; int tmp[j]; int a = 1; while(a == 1) { if(2*u+1 < i) { l = 2 * u + 1; } else { l = u; } if(2*u+2 < i) { r = 2 * u + 2; } else { r = u; } if(H[u] < H[r] || H[u] < H[r]) { if(H[l] < H[r]) { tmp[j] = H[u]; H[u] = H[r]; H[r] = tmp[j]; u = r; } else { tmp[j] = H[u]; H[u] = H[l]; H[l] = tmp[j]; u = l; } } else { a = 0; } } }
回答2件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。