質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.35%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

プログラミング言語

プログラミング言語はパソコン上で実行することができるソースコードを記述する為に扱う言語の総称です。

Q&A

解決済

2回答

1776閲覧

ヒープソートのプログラム

退会済みユーザー

退会済みユーザー

総合スコア0

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

プログラミング言語

プログラミング言語はパソコン上で実行することができるソースコードを記述する為に扱う言語の総称です。

0グッド

0クリップ

投稿2021/05/13 13:06

以下はヒープソートのプログラムです。それに以下の関数を追加するという問題がでました。

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; } } }

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

ベストアンサー

やるべきことを教えていただけると幸いです。

ヒープは「親は(高々二人の)子より小さくない」を維持せにゃなりません。
H[i] が a に変更されるとき、”ただしaはa≧H[i]を満たす値とする”んだから、大きな値に変更されるってこと。
その変更がされてもH[i]とその子との間ではヒープ性は壊れません。

壊れる可能性があるなら H[i]とその親:H[p]との間、H[p] < H[i] となり得ます。
そのとき、H[p]とH[i]を交換してヒープ性を取り戻します。
するとH[p]とその親との間でヒープ性が壊れるかも...で、以下同文。

投稿2021/05/13 23:28

episteme

総合スコア16612

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

それはその問題を出したひとに聞くべき事柄ですね

投稿2021/05/13 21:41

y_waiwai

総合スコア88042

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.35%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問