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

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

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

Xcodeはソフトウェア開発のための、Appleの統合開発環境です。Mac OSXに付随するかたちで配布されています。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

配列

配列は、各データの要素(値または変数)が連続的に並べられたデータ構造です。各配列は添え字(INDEX)で識別されています。

Q&A

解決済

1回答

303閲覧

ヒープソートを作っているのですが動かなくなってしまいます。

GAKU_SAY

総合スコア23

Xcode

Xcodeはソフトウェア開発のための、Appleの統合開発環境です。Mac OSXに付随するかたちで配布されています。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

配列

配列は、各データの要素(値または変数)が連続的に並べられたデータ構造です。各配列は添え字(INDEX)で識別されています。

0グッド

0クリップ

投稿2020/07/01 22:03

編集2020/07/01 22:46

###したいこと
配列array_intをヒープ条件に合うように並び替えたい。

###条件
なるべく関数を書き換えたくないです。(名称は絶対に)
xcode
c++

###欲しい情報
解決方法に関する情報

###結果
1
0
0
0
1886912525
1835627109
1635020389
1634557804
1701535600
121

###コード

c++

1#include<iostream> 2 3int *array_int;//{1,13,14,60,15,91,24,71,80,63}; 4double *array_dob; 5int mode = 0; 6 7int size = 3; 8 9using namespace std; 10 11template <class X>void swap(X *a, X *b){ 12 X box = *a; 13 *a = *b; 14 *b = box; 15} 16 17int check_heap(){ 18 19 int j=0; 20 21 for (int i=1; i<size; i++) { 22 23 if (i%2 == 1) { 24 j = (i-1)/2; 25 }else{ 26 j=i/2-1; 27 } 28 29 if (mode == 0) { 30 if (array_int[i] < array_int[j]) { 31 return 0; 32 } 33 }else if (mode == 1){ 34 if (array_dob[i] < array_dob[j]) { 35 return 0; 36 } 37 } 38 39 } 40 41 return 1; 42} 43 44void shift_down(){ 45 46 int i=0,j=0; 47 48 if (mode == 0) { 49 50 51 while (!check_heap()) { 52 53 if (array_int[2*i+1] > array_int[2*i+2]) { 54 j = 2*i+2; 55 }else{ 56 j = 2*i+1; 57 } 58 59 swap(&array_int[i],&array_int[j]); 60 61 i = 2*i+1; 62 } 63 64 65 }else if (mode == 1){ 66 67 while (!check_heap()) { 68 69 if (array_dob[2*i+1] > array_dob[2*i+2]) { 70 j = 2*i+2; 71 }else{ 72 j = 2*i+1; 73 } 74 75 swap(&array_dob[i],&array_dob[j]); 76 77 i = 2*i+1; 78 } 79 } 80 81} 82 83template<typename var>void insert(var val){ 84 85 ///メモリ確保&代入 86 size++; 87 88 if (mode == 0) { 89 90 if ((array_int = (int*)realloc(array_int, sizeof(int)*size))==NULL) { 91 cout << "I can't get enough size memory. SORRY" << endl; 92 } 93 94 array_int[size-1] = val; 95 96 }else if (mode == 1){ 97 98 if ((array_dob = (double*)realloc(array_dob, sizeof(double)*size))==NULL) { 99 cout << "I can't get enough size memory. SORRY" << endl; 100 } 101 102 array_dob[size-1] = val; 103 104 } 105 ///メモリ確保終了&代入 106 107 int i=size-1,j = 0; 108 109 while (!check_heap()) { 110 111 if (i%2 == 1) { 112 j = (i-1)/2; 113 }else{ 114 j=(i-2)/2; 115 } 116 117 if (mode == 0) { 118 swap(&array_int[i], &array_int[j]); 119 }else if (mode == 1){ 120 swap(&array_dob[i], &array_dob[j]); 121 } 122 123 shift_down(); 124 125 i=j; 126 } 127 128} 129 130template <typename var>var deletemin(){ 131 132 var returner = 0.0; 133 134 if (mode == 0) { 135 reterner = array_int[0]; 136 swap(&array_int[0],&array_int[size-1]); 137 }else if(mode == 1){ 138 reterner = array_dob[0]; 139 swap(&array_dob[0],&array_dob[size-1]); 140 } 141 size--; 142 143 array_int = (int*)realloc(array_int, sizeof(int)*size); 144 145 shift_down(); 146 147 return returner; 148} 149 150int HeapSort(){ 151 152 int *aps = (int*)malloc(sizeof(int)*size); 153 int i=0; 154 int past = size; 155 156 size = 1; 157 aps[0] = array_int[0]; 158 159 for (i=size; i<past; i++) { 160 insert(aps[i]); 161 } 162 163 free(array_int); 164 array_int = aps; 165 166 return 0; 167} 168 169int main(){ 170 171 size = 10; 172 173 array_int = (int *)malloc(sizeof(int)*size); 174 array_int[0] = 1; 175 array_int[1] = 13; 176 array_int[2] = 14; 177 array_int[3] = 60; 178 array_int[4] = 15; 179 array_int[5] = 91; 180 array_int[6] = 24; 181 array_int[7] = 71; 182 array_int[8] = 80; 183 array_int[9] = 63; 184 185 HeapSort(); 186 187 for (int i=0; i<size; i++) { 188 printf("%d\n",array_int[i]); 189 } 190 191 192 free(array_int); 193 194 return 0; 195} 196

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

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

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

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

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

y_waiwai

2020/07/01 22:35

提示のコードではどういう動作になるんでしょうか。 エラーが出るならエラーメッセージを提示しましょう
guest

回答1

0

ベストアンサー

いろいろいろいろツッコミどころはありますが、とりあえずこれだけ。

free(array_int);

array_int = aps;

apsのナカミがどうなってるのか見てみよう。

投稿2020/07/01 22:53

y_waiwai

総合スコア87719

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

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

GAKU_SAY

2020/07/01 23:10

中身を見てみようのアドバイスで解決しました。ありがとうございます。このコードは別のコードをもとに試作のような形で作ったのでわざと突っ込みどころのあるようになってたりします。
GAKU_SAY

2020/07/01 23:15

後学のために、ツッコミどころを教えていただけるとありがたいです。変数の書く位置や引数の過不足以外の内容でお願いします。
episteme

2020/07/01 23:59

確認ですけど、標準C++に出来合いのヒープ関数群が用意されているんですが、あえてそれらを使わないって選択をしたんですよね?
GAKU_SAY

2020/07/02 00:01

それで間違い無いです。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問