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

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

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

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

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

Q&A

解決済

2回答

2073閲覧

バブルソート, シェルソート, クイックソートの実現

退会済みユーザー

退会済みユーザー

総合スコア0

C

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

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

0グッド

0クリップ

投稿2016/07/23 12:11

編集2016/07/24 10:49

###前提・実現したいこと
Cで三角形の構造体を面積(辺の和)でソートするプログラムを実現したいです。Segmentation faultが表示されるのですが原因がわからないのでご教授願いたいです。

[追記]
A[SIZE]をポインタを用いないものに変更しましたがどのソートを実行してもソートされません。

1 Side : 224.210646 Area : 2072.541918 2 Side : 200.143520 Area : 1352.474029 3 Side : 186.673849 Area : 1447.508549 4 Side : 240.090907 Area : 1719.078096 5 Side : 142.866303 Area : 967.710959 6 Side : 164.552194 Area : 935.697066 7 Side : 95.511362 Area : 172.333253 8 Side : 224.741866 Area : 1657.931090 9 Side : 185.111045 Area : 1389.912227 10 Side : 143.538119 Area : 446.386604

###発生している問題・エラーメッセージ
Segmentation fault: 11が表示されます。

###該当のソースコード

C

1#include<stdio.h> 2#include<stdlib.h> 3#include<time.h> 4#include<math.h> 5 6#define SIZE 100000 7#define XMAX 100 8#define YMAX 100 9#define ZMAX 100 10#define TEST_NUM 10 11 12typedef struct POINT { 13 int x; 14 int y; 15 int z; 16} point_t; 17 18typedef struct TRIANGLE { 19 point_t p[3]; 20} triangle_t; 21 22triangle_t A[SIZE]; 23 24//A[]の初期化 25void init_triangle(triangle_t t[], int n) 26{ 27 int i, j; 28 29 for (i = 0; i < n; i++) { 30 for (j = 0; j < 3; j++) { 31 t[i].p[j].x = 0; 32 t[i].p[j].y = 0; 33 t[i].p[j].z = 0; 34 } 35 } 36} 37 38//三角形の辺の和, 面積を出力 39void print_triangle(triangle_t t) 40{ 41 double ss, s[3]; //面積の和, 各辺 42 double a; //面積 43 44 s[0] = sqrt(pow((double)(t.p[1].x - t.p[0].x), 2) + pow((double)(t.p[1].y - t.p[0].y), 2) + pow((double)(t.p[1].z - t.p[0].z), 2)); 45 s[1] = sqrt(pow((double)(t.p[2].x - t.p[1].x), 2) + pow((double)(t.p[2].y - t.p[1].y), 2) + pow((double)(t.p[2].z - t.p[1].z), 2)); 46 s[2] = sqrt(pow((double)(t.p[0].x - t.p[2].x), 2) + pow((double)(t.p[0].y - t.p[2].y), 2) + pow((double)(t.p[0].z - t.p[2].z), 2)); 47 ss = s[0] + s[1] + s[2]; 48 49 printf("Side : %f\n", ss); 50 51 ss /= 2; 52 a = sqrt(ss * (ss - s[0]) * (ss - s[1]) * (ss - s[2])); 53 54 printf("Area : %f\n", a); 55} 56 57//三角形生成 58triangle_t create_triangle() 59{ 60 int x[3], y[3], z[3]; //各座標 61 double s[3]; //各辺の長さ 62 triangle_t tr; //三角形 63 int i; 64 65 66 for (i = 0; i < 3; i++) { 67 x[i] = rand() % XMAX; 68 y[i] = rand() % YMAX; 69 z[i] = rand() % ZMAX; 70 //printf("%4d %4d %4d\n", x[i], y[i], z[i]); 71 } 72 73 s[0] = sqrt(pow((double)(x[1] - x[0]), 2) + pow((double)(y[1] - y[0]), 2) + pow((double)(z[1] - z[0]), 2)); 74 s[1] = sqrt(pow((double)(x[2] - x[1]), 2) + pow((double)(y[2] - y[1]), 2) + pow((double)(z[2] - z[1]), 2)); 75 s[2] = sqrt(pow((double)(x[0] - x[2]), 2) + pow((double)(y[0] - y[2]), 2) + pow((double)(z[0] - z[2]), 2)); 76 //for (i = 0; i < 3; i++) printf("%f\n", s[i]); 77 78 //三角形成立条件 79 if (s[0] + s[1] > s[2] && s[1] + s[2] > s[0] && s[2] + s[0] > s[1]) { 80 for (i = 0; i < 3; i++) { 81 tr.p[i].x = x[i]; 82 tr.p[i].y = y[i]; 83 tr.p[i].z = z[i]; 84 } 85 //printf(" x y z\n"); 86 //for (i = 0; i < 3; i++) printf("%d %6d %6d %6d\n", i + 1, ptr.p[i].x, ptr.p[i].y, ptr.p[i].z); 87 return tr; 88 } 89 else { 90 for (i = 0; i < 3; i++) { 91 tr.p[i].x = x[i]; 92 tr.p[i].y = y[i]; 93 tr.p[i].z = z[i]; 94 } 95 return tr; 96 } 97} 98 99//三角形の面積(等しければ3辺の和)を比較し前者が小さければ負, 後者が小さければ正を返す 100int cmp_triangle(triangle_t t1, triangle_t t2) 101{ 102 double a1, a2; //各面積 103 double s1[3], s2[3]; //各辺 104 double ss1, ss2; //辺の和の1/2 105 106 s1[0] = sqrt(pow((double)(t1.p[1].x - t1.p[0].x), 2) + pow((double)(t1.p[1].y - t1.p[0].y), 2) + pow((double)(t1.p[1].z - t1.p[0].z), 2)); 107 s1[1] = sqrt(pow((double)(t1.p[2].x - t1.p[1].x), 2) + pow((double)(t1.p[2].y - t1.p[1].y), 2) + pow((double)(t1.p[2].z - t1.p[1].z), 2)); 108 s1[2] = sqrt(pow((double)(t1.p[0].x - t1.p[2].x), 2) + pow((double)(t1.p[0].y - t1.p[2].y), 2) + pow((double)(t1.p[0].z - t1.p[2].z), 2)); 109 ss1 = (s1[0] + s1[1] + s1[2]) / 2; 110 111 s2[0] = sqrt(pow((double)(t2.p[1].x - t2.p[0].x), 2) + pow((double)(t2.p[1].y - t2.p[0].y), 2) + pow((double)(t2.p[1].z - t2.p[0].z), 2)); 112 s2[1] = sqrt(pow((double)(t2.p[2].x - t2.p[1].x), 2) + pow((double)(t2.p[2].y - t2.p[1].y), 2) + pow((double)(t2.p[2].z - t2.p[1].z), 2)); 113 s2[2] = sqrt(pow((double)(t2.p[0].x - t2.p[2].x), 2) + pow((double)(t2.p[0].y - t2.p[2].y), 2) + pow((double)(t2.p[0].z - t2.p[2].z), 2)); 114 ss2 = (s2[0] + s2[1] + s2[2]) / 2; 115 116 //printf("%f\n", ss1); 117 //printf("%f\n", ss2); 118 119 //printf("The latter's side = %f\n", sqrt(ss2 (ss2 - s2[0]) (ss2 - s2[1]) (ss2 - s2[2]))); 120 121 //ヘロンの公式 122 a1 = sqrt(ss1 * (ss1 - s1[0]) * (ss1 - s1[1]) * (ss1 - s1[2])); 123 a2 = sqrt(ss2 * (ss2 - s2[0]) * (ss2 - s2[1]) * (ss2 - s2[2])); 124 printf("%f\n", a1); 125 printf("%f\n", a2); 126 127 if (a1 < a2) return -1; 128 else if (a1 > a2) return 1; 129 else { 130 if (ss1 < ss2) return -2; 131 else if (ss1 > ss2) return 2; 132 else return 0; 133 } 134} 135 136//cmp_triangleの結果を文字で出力するバージョン 137void print_cmp_triangle(triangle_t t1, triangle_t t2) 138{ 139 int cmp = cmp_triangle(t1, t2); 140 141 if (cmp == -1) printf("The former's area is smaller than the latter.\n"); 142 else if (cmp == 1) printf("The former's area is larger than the latter.\n"); 143 else if (cmp == -2) printf("The former's side is smaller than the latter.\n"); 144 else if (cmp == 2) printf("The former's side is larger than the latter.\n"); 145 else printf("Both of areas and sides are same.\n"); 146} 147 148//スワップ 149void swap(triangle_t *x, triangle_t *y) 150{ 151 triangle_t *tmp; 152 153 tmp = x; 154 x = y; 155 y = tmp; 156} 157 158//バブルソート 159void bubble_sort(triangle_t t[], int n) 160{ 161 int i, j; 162 163 for (i = 0; i < n; i++) 164 for (j = n - 1; j > i; j--) 165 if (cmp_triangle(t[j - 1], t[j]) > 0) swap(&t[j - 1], &t[j]); 166} 167 168//シェルソート 169//G:ギャップ列 170void shell_sort(triangle_t t[], int n) 171{ 172 int i, j, k = 0; 173 int K; 174 int G[n]; 175 176 //G[k] = 2^(k+1)-1 : Hibbardの方法 177 for (i = 0; G[i] < n; i++) G[i] = (pow(2, k + 1)) - 1; 178 K = i - 1; 179 180 for (k = K; k >= 0; k--) { 181 for (i = G[k]; i < n; i++) { 182 triangle_t tmp = t[i]; 183 j = i - G[k]; 184 while (j >= 0 && cmp_triangle(tmp, t[j]) < 0) { 185 t[j + G[k]] = t[j]; 186 j -= G[k]; 187 } 188 t[j + G[k]] = tmp; 189 } 190 } 191} 192 193//クイックソートにおける分割処理 194int partition(triangle_t t[], int pivot, int left, int right) 195{ 196 t[right] = t[pivot]; 197 int l = left; 198 int r = right; 199 200 while (1) { 201 while (cmp_triangle(t[l], t[right]) < 0) l++; 202 while (l <= r && cmp_triangle(t[r], t[right]) >= 0) r--; 203 if (l < r) swap(&t[l], &t[r]); 204 else break; 205 } 206 207 swap(&t[l], &t[right]); 208 return l; 209} 210 211//左端, 中央, 右端のうち真ん中の値の要素のインデックスを出力する 212int middle_value(triangle_t t[], int n) 213{ 214 triangle_t B[3] = {t[0], t[n / 2], t[n - 1]}; 215 triangle_t max = B[0], min = B[0], mid; 216 int i; 217 218 //最大の判定 219 for (i = 1; i <= 2; i++) 220 if (cmp_triangle(B[i], max) > 0) max = B[i]; 221 222 //最小の判定 223 for (i = 1; i <= 2; i++) 224 if (cmp_triangle(B[i], max) < 0) max = B[i]; 225 226 //中間値を求める 227 for (i = 0; i < 3; i++) 228 if (cmp_triangle(B[i], max) != 0 && cmp_triangle(B[i], min) != 0) mid = B[i]; 229 230 if (cmp_triangle(mid, t[0]) == 0) return 0; 231 else if (cmp_triangle(mid, t[n / 2])) return n / 2; 232 else if (cmp_triangle(mid, t[n - 1])) return n - 1; 233 else return -1; 234} 235 236//クイックソート 237void quick_sort(triangle_t t[], int left, int right, int n) 238{ 239 if (left < right) { 240 int pivot = middle_value(t, n); 241 242 int p = partition(t, pivot, left, right); //分割処理 243 //A[pivot]未満のデータをA[left],...,A[p-1]に集める 244 //A[pivot]以上のデータをA[p+1],...,A[right]に集める 245 //A[pivot]の値をA[p]に入れる 246 247 quick_sort(t, left, p - 1, n); 248 quick_sort(t, p + 1, right, n); 249 } 250} 251 252int main() 253{ 254 int i; 255 256 //ソートテスト 257 triangle_t T[TEST_NUM]; 258 //init_triangle(T, TEST_NUM); 259 srand((unsigned)time(NULL)); 260 for (i = 0; i < TEST_NUM; i++) T[i] = create_triangle(); 261 262 //bubble_sort(T, TEST_NUM); 263 shell_sort(T, TEST_NUM); 264 //quick_sort(T, 0, TEST_NUM - 1, TEST_NUM); 265 266 for (i = 0; i < TEST_NUM; i++) { 267 printf("%2d\n", i + 1); 268 print_triangle(T[i]); 269 } 270 271 return 0; 272} 273

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

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

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

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

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

guest

回答2

0

ベストアンサー

こんにちは。

取り敢えず、shell_sort()関数のローカル変数k(小文字の方)が初期化されていないようですが、これは現在のフォルトとは無関係のようです。

bubble_sort()関数で呼び出したcmp_triangle()関数内の下記行で落ちてました。

s1[0] = sqrt(pow((double)(t1->p[1].x - t1->p[0].x), 2) + pow((double)(t1->p[1].y - t1->p[0].y), 2) + pow((double)(t1->p[1].z - t1->p[0].z), 2));

t1がNULLでした。
確かに、A[]変数が初期化されていないです。

triangle_t *A[SIZE];

は、triangle_t型へのポインタの配列です。Axにtriangle_t変数へのポインタを設定する必要が有ります。
簡単に対処するなら、下記がお薦めです。

triangle_t A[SIZE];として、cmp_triangle(&A[j - 1], &A[j])で呼び出す。

これに合わせてAを直接アクセスしている関数の修正が必要です。
例えば、init_triangle()A[i]->p[j].x = 0;A[i].p[j].x = 0;などです。

他にも似たような不具合が幾つかありそうな感じがします。
私はVisual Studio 2015を使ってやってみました。IDEを使えば、例外が発生したタイミングで一旦停止し、そこまでの呼び出し履歴が表示されるので、簡単に原因をつかむことができます。

Segmentation fault: 11ということはgcc系のコンパイラをお使いと思います。
gccの方のIDEもいくつかあるようですので、使うと便利ですよ。
(gccの方が具体的には把握してないので紹介できません。ごめんなさい。)

投稿2016/07/23 12:37

Chironian

総合スコア23272

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

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

退会済みユーザー

退会済みユーザー

2016/07/24 07:57

回答ありがとうございます。 triangle_t A[SIZE]; として他の関数を修正しましたが結果は変わりませんでした。 今IDEを使える環境に無いのでIDEを使わず修正したいです。
Chironian

2016/07/24 08:12

では、printf("(1)\n");fflush(stdout);などと要所要所に書いて、落ちるところを特定しましょう。 例えば、下記のようにすると、(1)のみ出力されて(2)が出ませんので、間で落ちていることが分かります。 printf("(1)\n");fflush(stdout); int *p=NULL;*p=1; printf("(2)\n");fflush(stdout); なお、fflush(stdout);がないとバッファに溜まって出力されないことがありますので落ちた場所を特定できません。 しかし、fflush(stdout);しておけばすぐに出力されますので直後に落ちても表示されます。 また、必要に応じて重要な変数の値をprintf()で出力するとデバッグに有用です。
退会済みユーザー

退会済みユーザー

2016/07/24 11:00

回答ありがとうございます。 アドバイスしていただいたおかげでfaultは表示されなくなりました。 が今度はソートされない
退会済みユーザー

退会済みユーザー

2016/07/24 11:01

すみません、途中送信してしまいました。 今度はソートがされないです。
Chironian

2016/07/24 11:56

ソート対象を3つくらいにして、ソート関数のループの中で、その3つの状態を全てprintf()で表示してみて下さい。 ソートアルゴリズムに比べて、想定外の動作をしている部分がある筈です。 それを見つけて修正しましょう。
退会済みユーザー

退会済みユーザー

2016/07/26 00:14

解決しました。 ありがとうございました。
guest

0

落ちているところはChironianさんの言うとおりです。宗教的な理由でWindowsではなくMacを使わなければならないなら、XcodeでもVisual Studio 2015のような事はできるはずですので、お試しください。

たぶん、一番おかしな所はtriangle_t *create_triangle()です。理由は「ポインタを返しているが、予め確保された領域を引数として渡しているわけでも、malloc等で動的に確保されているわけでもない」からです。C言語では、関数内部のローカル変数で確保された領域は、関数の終了と共にすべて破棄されます(staticなローカル変数を除く)。そして、returnで返されるのはのみであり、もしそれがポインタであれば、ポインタ値そのものだけです。ポインタの先は渡されず、もし、それがローカル変数の領域なら、関数の終了と共に破棄されます。つまり、次のようなコードはおかしな動作になります。

C

1int *hoge(void) 2{ 3 int a; 4 int *p; 5 a = 0; 6 p = &a; 7 return p; 8}

上の関数hoge()を呼び出して得る返り値のポインタが全くの使い物にならない理由はわかりますか?上と同じ事をtriangle_t *create_triangle()はしています。これを理解の上、どのようにメモリが確保されているのか、全体を見直してみてください。

投稿2016/07/23 13:52

raccy

総合スコア21733

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

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問