🎄teratailクリスマスプレゼントキャンペーン2024🎄』開催中!

\teratail特別グッズやAmazonギフトカード最大2,000円分が当たる!/

詳細はこちら
C

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

セグメンテーション違反

セグメンテーション違反とは、ソフトウェア実行時に発生するエラーのひとつであり、許可されていないメモリにアクセスしたときに起きます。しばしば、ポインタの不適切な使用、またはバッファオーバーフローによって起こります。

ソート

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

Q&A

解決済

2回答

2387閲覧

C言語での2分木ソートアルゴリズムでセグメンテーション違反が取り除けない

terym0421

総合スコア1

C

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

セグメンテーション違反

セグメンテーション違反とは、ソフトウェア実行時に発生するエラーのひとつであり、許可されていないメモリにアクセスしたときに起きます。しばしば、ポインタの不適切な使用、またはバッファオーバーフローによって起こります。

ソート

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

0グッド

0クリップ

投稿2020/11/24 13:48

C言語で2分木を使った昇順ソートアルゴリズムを作成しています。
小さい順に表示しようとするとセグメンテーション違反が起こってしまいます。原因がわからないので教えていただきたいです。

ソース

#include <stdio.h> #include <stdlib.h> #include <string.h> struct tree { int value; struct tree *left; struct tree *right; }; // ノードを追加 int append(int input, struct tree *current_node) { if (input < current_node->value) { if (current_node->left != NULL) { append(input, current_node->left); } else { struct tree new = {input, NULL, NULL}; current_node->left = &new; } } else { if (current_node->right != NULL) { append(input, current_node->right); } else { struct tree new = {input, NULL, NULL}; current_node->right = &new; } } } // 小さい順に表示 void sort(struct tree *current_node) { if (current_node->left != NULL) { sort(current_node->left); } printf("%d, ", current_node->value); if (current_node->right != NULL) { sort(current_node->right); } } int main() { int sequence[] = {2, 4, 6, 1, 8, 2, 10, 0}; int n = sizeof(sequence) / sizeof(int); struct tree root = { sequence[0], NULL, NULL }; for (int i = 1; i < n; i++) { append(sequence[i], &root); } sort(&root); printf("\n"); }

発生している問題・エラーメッセージ

sort()関数のところでセグメンテーション違反が起こっています。

試したこと

gdbでステップ実行をしてみたのですが、sort()にはいった段階でそれぞれのノードのvalueの値が-129660088のようにおかしくなっていました。

環境

WSL2, Ubuntu20.04LTS, gcc version9.3.0,

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

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

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

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

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

guest

回答2

0

ベストアンサー

append の struct tree new = { input, NULL, NULL }; の new は
自動変数で、この場でメモリが確保され input で初期化されますが、
current_node->left = &new; または current_node->right = &new; の
あとの } で、new のメモリが解放され、他の用途に使用されます。
current_node->left や current_node->right は、正しいデータの存在しない
メモリを指すことになります。

malloc でメモリ領域を確保しないといけません。

diff

1+struct tree *new_node(int input) 2+{ 3+ struct tree *new = malloc(sizeof(struct tree)); 4+ new->value = input; 5+ new->left = new->right = NULL; 6+ return new; 7+} 8+ 9 // ノードを追加 10-int append(int input, struct tree *current_node) { 11+void append(int input, struct tree *current_node) { 12 if (input < current_node->value) { 13 if (current_node->left != NULL) { 14 append(input, current_node->left); 15 } else { 16- struct tree new = {input, NULL, NULL}; 17- current_node->left = &new; 18+ current_node->left = new_node(input); 19 } 20 21 } else { 22 if (current_node->right != NULL) { 23 append(input, current_node->right); 24 } else { 25- struct tree new = {input, NULL, NULL}; 26- current_node->right = &new; 27+ current_node->right = new_node(input); 28 } 29 } 30 31+void freeAll(struct tree *p) 32+{ 33+ if (p->left) freeAll(p->left); 34+ if (p->right) freeAll(p->right); 35+ free(p); 36+} 37 38 int main() { 39 int sequence[] = {2, 4, 6, 1, 8, 2, 10, 0}; 40 int n = sizeof(sequence) / sizeof(int); 41- struct tree root = { 42- sequence[0], 43- NULL, 44- NULL 45- }; 46+ struct tree *root = new_node(sequence[0]); 47 for (int i = 1; i < n; i++) { 48- append(sequence[i], &root); 49+ append(sequence[i], root); 50 } 51- sort(&root); 52+ sort(root); 53 printf("\n"); 54+ freeAll(root); 55 }

投稿2020/11/24 16:11

kazuma-s

総合スコア8224

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

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

terym0421

2020/11/25 04:11

ありがとうございます!!解決しました!! 動的メモリ確保について勉強しなおそうと思います
guest

0

appendで入れられるstruct tree rootは、ローカル変数で、しかも全て同じ変数(アドレス)が入れられます
それをソートするというのは全くのナンセンスですね。

#おそらく質問の問題と言うのもそれに起因してるでしょうね

投稿2020/11/24 14:40

y_waiwai

総合スコア88040

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

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

terym0421

2020/11/24 15:19

ええと、rootはグローバルに宣言しないといけないということでしょうか。また、そーとするのはsequence配列であり、rootをソートするわけではないのですが。。。 試しにグローバルにrootを宣言しても全く同じ状況です。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.36%

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

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

質問する

関連した質問