問題文:ヒープに新たなデータを挿入する関数insertを作成せよ。空の配列に複数回insertを行うことで
構成したヒープがヒープ条件を満たしていることをcheck_heapを用いることで確認せよ。プロトタイプ宣言は以下とする。
void insert(int val, int a[],int *n);
質問:
複数回はおいといてとりあえず1回insertしようと思って書いたんですが、ヒープの最後に新しいノードを
作って親より小さければ親の値と交換を繰り返してヒープを完成させようとしてるんですが、1回しか交換されません。
どうすればいいですか?check_heapは最小ヒープ条件が満たされていれば1を満たされていなければ0を返す関数です。
自分のソース
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int check_heap(int a[], int n);
void insert(int val, int a[], int *n);
int main(void) {
int a[11] = {1,13,71,14,15,80,91,24,60,63};
int n;
int i;
int b,c;
srandom(time(NULL));
b = random() % 100 + 1;
n = 10;
insert(b, a, &n);
printf("%d\n", check_heap(a, 11));
for(i = 0; i < 11; i++){
printf("%3d", a[i]);
}
return 0;
}
int check_heap(int a[], int n) {
int i;
int m;
m = (n - 1) / 2;
for(i = 0; i < m; i++)
{
if(a[i] >= a[i * 2 + 1])
{
return 0;
}
if(a[i] >= a[i * 2 + 2]){
return 0;
}
}
if(n % 2 == 0){
if(a[(n - 1)/2] > a[n - 1]){
return 0;
}
}
return 1;
}
void insert(int val, int a[], int *n) {
int temp;
a[*n] = val;
while(a[(*n-1) / 2] >= a[*n]){
temp = a[(*n-1) / 2];
a[(*n-1) / 2] = a[*n];
a[*n] = temp;
}
}
No.2ベストアンサー
- 回答日時:
> 1回しか交換されません。
この↓中で*nを更新していないから(while-loopが一回止まり)じゃないかしら。
void insert(int val, int a[], int *n)
int temp;
a[*n] = val;
while(a[(*n-1) / 2] >= a[*n]){
temp = a[(*n-1) / 2];
a[(*n-1) / 2] = a[*n];
a[*n] = temp;
}
}
No.1
- 回答日時:
操作しようとしているmain()の配列変数aは、ローカル変数であってヒープではありません。
現状で初期値が設定されているのが10個、配列のサイズが11個なのであと1つの値を入れることは可能ですが…課題の要件は満たさないでしょう。
# というかこの場合のヒープってなんでしょう??
で……
>while(a[(*n-1) / 2] >= a[*n]){
> temp = a[(*n-1) / 2];
> a[(*n-1) / 2] = a[*n];
> a[*n] = temp;
>}
のループでは*nの値(というか、アドレス渡しする必要あるんでしょうか?)は変化していません。
条件が真だったら1回入れ替えが実行され、後は条件から外れるのでループ終了するでしょう。
# 条件が「以上」となっているので、無限ループする可能性もありますが。
# 今回の場合、main()でbが15だったときに時に、a[(*n-1) / 2] >= a[*n]が真になり続けるので無限ループ。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
- ・ゆるやかでぃべーと タイムマシンを破壊すべきか。
- ・歩いた自慢大会
- ・許せない心理テスト
- ・字面がカッコいい英単語
- ・これ何て呼びますか Part2
- ・人生で一番思い出に残ってる靴
- ・ゆるやかでぃべーと すべての高校生はアルバイトをするべきだ。
- ・初めて自分の家と他人の家が違う、と意識した時
- ・単二電池
- ・チョコミントアイス
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
「指定されたキャストは有効で...
-
C言語 エラーの原因がわからな...
-
C言語での引数の省略方法
-
【C++】関数ポインタの使い方
-
C言語での奇数の和
-
#define _CRT_SECURE_NO_WARNIN...
-
int型の変数値をバイト列として...
-
CStringの配列要素を関数で受け...
-
C++でvectorにテキストファイル...
-
実数の整数部,小数部の取得
-
PowerShellがうまくいかない
-
「{ } で囲むだけ」は正しい?
-
system関数がうまくいかない
-
ColorをRGBで指定する方法
-
エラー 添字が付けられた値が、...
-
C言語で分からないところがあり...
-
入力を待たずにstdinの監視をし...
-
ラップ関数とはどんなものですか?
-
Arduinoのプログラムにエラーが...
-
【至急】プログラムにエラーが...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
「指定されたキャストは有効で...
-
C言語での引数の省略方法
-
#define _CRT_SECURE_NO_WARNIN...
-
AtCoderABC135の問題Cについて
-
C言語 エラーの原因がわからな...
-
複数桁10進数の*桁目だけを抽出...
-
【C++】関数ポインタの使い方
-
実数の整数部,小数部の取得
-
ラップ関数とはどんなものですか?
-
if と配列の組み合わせ
-
return 1L
-
read関数をノンブロッキングで...
-
(int *)の意味
-
std::set<int> で、ある値が何...
-
Win32APIで作るコンボボックス...
-
C++でvectorにテキストファイル...
-
「{ } で囲むだけ」は正しい?
-
足して100になるような乱数のア...
-
Arduinoのプログラムにエラーが...
-
課題でつまってます・・・
おすすめ情報