以下のようなＡＶＬ木のコードを書いてみたのですがセグメンテーション違反が出てしまい原因が分からず困っています。
内容としては、ある数列をＡＶＬ木として挿入を行い、数列の数が50個までの場合は可視化を行っています。初心者であるため、かなり煩雑なコードになっていますが、アドバイスお願いいたします。なるべく早く返信を頂けると幸いです。
私の予想としてはinsert_nodeとrebalanceの中身でミスをしているのではないかという検討を立てています。
code=C
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#define VISION 50
#define AVL_BALANCED 0
#define AVL_LEFT 1
#define AVL_RIGHT 2
typedef struct node{
struct node *left;
struct node *right;
struct node *parent;
int element;
int balance;
}Node;
typedef struct{
Node *root;
}Tree;
static void destroy_node(Node *node)
{
if (node != NULL){
destroy_node(node->left);
destroy_node(node->right);
free(node);
}
}
void rebalance(Node *node, int direct)
{
Node *prev,*next;
if (node == NULL) return;
if ((node->balance == AVL_LEFT && direct == AVL_RIGHT)
|| (node->balance == AVL_RIGHT && direct == AVL_LEFT))
{
node->balance = AVL_BALANCED;
} else if (node->balance == AVL_BALANCED) {
node->balance = direct;
if ((prev = node->parent) != NULL)
rebalance(prev, node->element < prev->element ? AVL_LEFT : AVL_RIGHT);
} else if (node->balance == direct){
prev = node->parent;
if (node->left->balance == direct) {
next = (direct == AVL_LEFT) ? node->left : node->right;
node->parent = next;
next->parent = prev;
if (direct == AVL_LEFT) {
node->left = next->right;
next->right = node;
} else {
node->right = next->left;
next->left = node;
}
node->balance = AVL_BALANCED;
next->balance = AVL_BALANCED;
} else {
Node *dene;
if (direct == AVL_LEFT) {
dene = node->left;
next = dene->right;
} else {
dene = node->right;
next = dene->left;
}
node->parent = next;
dene->parent = next;
next->parent = prev;
if (direct == AVL_LEFT) {
node->left = next->right;
next->right = node;
dene->right = next->left;
next->left = dene;
dene->balance = (next->balance == AVL_RIGHT) ?
AVL_LEFT : AVL_BALANCED;
node->balance = (next->balance == AVL_LEFT) ?
AVL_RIGHT : AVL_BALANCED;
} else {
node->right = next->left;
next->left = node;
dene->left = next->right;
next->right = dene;
dene->balance = (next->balance == AVL_LEFT) ?
AVL_RIGHT : AVL_BALANCED;
node->balance = (next->balance == AVL_RIGHT) ?
AVL_LEFT : AVL_BALANCED;
}
next->balance = AVL_BALANCED;
}
if (prev->parent == NULL)
prev->left = prev->right = next;
else if (node->element < prev->element) prev->left = next;
else prev->right = next;
}
}
static Node *make_node(int element,Node *prev)
{
Node *node = malloc(sizeof(Node));
if (node != NULL){
node->element=element;
node->left=NULL;
node->right=NULL;
node->balance = 0;
node->parent = prev;
}
return node;
}
static Node *insert_node(int element,Node *node)
{
Node *prev = NULL;
while (node != NULL) {
if (element == node->element) return NULL;
prev = node;
if (element < node->element)
node->left = insert_node(element,node->left);
else
node->right = insert_node(element,node->right);
}
make_node(element,prev);
if (prev != NULL)
rebalance(prev, element < prev->element ? AVL_LEFT : AVL_RIGHT);
return node;
}
int depth_node(int element,Node *node)
{
int depth = 0;
while(node->element != element){
if(element < node->element){
node = node->left;
}else{
node = node->right;
}
depth++;
}
return depth;
}
int depth_tree(int element,Tree *tree)
{
return depth_node(element,tree->root);
}
Tree *make_tree(void)
{
Tree *tree = malloc(sizeof(Tree));
if (tree != NULL){
tree->root = NULL;
}
return tree;
}
void insert_tree(int elememt,Tree *tree)
{
tree->root = insert_node(elememt,tree->root);
}
void destroy_tree(Tree *tree)
{
destroy_node(tree->root);
free(tree);
}
int GetRandom(int min,int max)
{
return min + (int)(rand()*(max-min+1.0)/(1.0+RAND_MAX));
}
void shuffle(int *num,int n)
{
int s,m,tmp;
for(s = n - 1;s > 0;s--){
m = rand() % (s + 1);
tmp = num;
num = num[m];
num[m] = tmp;
}
}
int main(void)
{
int i,n,x,y,z,tree_number,*num,(*vision)[VISION],
depth,height,error,*height_tree;
double sum_height=0,sum2_height=0,real_number=0,average1,average2;
srand((unsigned int)time(NULL));
printf("!!");
fflush(0);
scanf("%d",&n);
int (*check_tree)[n];
tree_number = (int)((double)n/log2((double)n));
num = calloc(n,sizeof(int));
check_tree = calloc(tree_number * n,sizeof(int));
height_tree = calloc(n,sizeof(int));
for (i = 0;i < n;i++)
num=i+1;
for(x = 0;x < tree_number;x++){
Tree *tree =make_tree();
if(n <= VISION)
vision = calloc(VISION * VISION,sizeof(int));
height = 0;
error = 0;
shuffle(num,n);
for (i = 0;i < n;i++){
insert_tree(num,tree);
if(n <= VISION)
printf("%d ",num);
}
for(i = 0;i < n;i++){
depth=depth_tree(num,tree);
if(n <= VISION)
vision[depth][num-1]=num;
if(depth >= height)
height = depth;
check_tree[x][num-1]=depth;
}
for(y = 0;y < x;y++){
for(z = 0;z < n;z++){
if(check_tree[y][z]!=check_tree[x][z])
break;
}
if((z == n)&&(check_tree[y][z-1]==check_tree[x][z-1])){
error++;
break;
}
}
if(x != 0&&error == 1){
printf("this tree has been already created\n");
if(n <= VISION)
free(vision);
destroy_tree(tree);
continue;
}
if(n <= VISION){
printf("\n");
for(y = 0;y <= height;y++){
for(z = 0;z < n;z++){
if(vision[y][z] != 0)
printf("%2d",vision[y][z]);
else
printf(" ");
}
printf("\n");
}
printf("%d\n",height);
}
if(n <= VISION)
free(vision);
destroy_tree(tree);
height_tree[height]++;
}
for(i = 0;i < n;i++){
sum_height += (i * height_tree);
sum2_height += (i * i * height_tree);
real_number += height_tree;
}
average1 = sum_height / tree_number;
average2 = sum2_height /tree_number;
printf("%f\n%f\n",average1,average2 - average1 * average1);
free(check_tree);
free(height_tree);
return 0;
}
/code
ＡＶＬ木の実装で困っています
Re: ＡＶＬ木の実装で困っています
insert_node関数内でmake_node関数の返り値を捨てているため、メモリリークが発生します。
さらに、初期状態ではnode、すなわちtree->rootはNULLなのでnodeの操作をするコードは実行されず、
insert_nodeを呼び出してもtree->rootがNULLのまま更新されません。
また、prevもNULLなのでrebalance関数は呼び出されません。
その後depth_tree関数を呼び出すと、NULLであるtree->rootがdepth_node関数にnodeとして渡され、
node->element != elementという条件式でNULLがデリファレンスされ、未定義動作になります。
この結果、アクセス違反が発生するかもしれません。
さらに、初期状態ではnode、すなわちtree->rootはNULLなのでnodeの操作をするコードは実行されず、
insert_nodeを呼び出してもtree->rootがNULLのまま更新されません。
また、prevもNULLなのでrebalance関数は呼び出されません。
その後depth_tree関数を呼び出すと、NULLであるtree->rootがdepth_node関数にnodeとして渡され、
node->element != elementという条件式でNULLがデリファレンスされ、未定義動作になります。
この結果、アクセス違反が発生するかもしれません。
複雑な問題？マシンの性能を上げてOpenMPで殴ればいい！(死亡フラグ)
-
RIKU13
Re: ＡＶＬ木の実装で困っています
みけCATさん丁寧な解説ありがとうございます。
いろいろな参考を見ながら今回のソースを書いたためにあまり深い理解ができずに書いてしまいました。
もし、よろしければ手直しするところや改善点を教えてくださると助かります。
いろいろな参考を見ながら今回のソースを書いたためにあまり深い理解ができずに書いてしまいました。
もし、よろしければ手直しするところや改善点を教えてくださると助かります。
-
RIKU13
Re: ＡＶＬ木の実装で困っています
make_nodeの返り値を捨ててしまっていたため、return make_nodeに 変更したところ違反は出ませんでしたが、実行はされませんでした。
-
Math
Re: ＡＶＬ木の実装で困っています
私の環境ではエラーがでます。コードが見にくいしコメントがないのは可読性にかけます。私の双方向リストはコマンドライン・コンパイルが通ります。
//-----------------------------------------------------------------------------
#include <stdio.h> // for printf -
#include <stdlib.h> // for malloc
//-----------------------------------------------------------------------------
typedef struct ns {
int data; //構造体のデータ
struct ns *next;//構造体のポインター
} node;
//-----------------------------------------------------------------------------
node *list_add(node **p, int i) { // add head
node *n = malloc(sizeof(node)); // you normally don't cast a return value for malloc
n->next = *p; // 次ポインターの代入
*p = n;
n->data = i;
return n;
}
//-----------------------------------------------------------------------------
node *list_add_tail(node **p, int i) { // add tail
node *n;
node *ptr;
if (*p == NULL) {
n = list_add(p, i);
} else {
ptr = *p;
while (ptr->next != NULL) {
ptr = ptr->next;
}
n = malloc(sizeof(node));
n->next = NULL;
n->data = i;
ptr->next = n;
}
return n;
}
//-----------------------------------------------------------------------------
void list_remove(node **p) { // remove head
if (*p != NULL) {
node *n = *p;
*p = (*p)->next;
free(n);
}
}
//-----------------------------------------------------------------------------
void list_remove_tail(node **p) { // remove tail
if (*p != NULL) {
if( (*p)->next == NULL ) {
list_remove(p);
} else {
node *ptr = *p;
node *pre;
while (ptr->next != NULL) {
pre = ptr;
ptr = ptr->next;
}
pre->next = NULL;
free(ptr);
}
}
}
//-----------------------------------------------------------------------------
void list_remove_all(node **p) { // remove all node
while (*p != NULL) {
list_remove(p);
}
}
//-----------------------------------------------------------------------------
node **list_search(node **n, int i) {
while (*n != NULL) {
if ((*n)->data == i) {
return n;
}
n = &(*n)->next;
}
return NULL;
}
//-----------------------------------------------------------------------------
void list_print(node *n) {
if (n == NULL) {
printf("list is empty\n");
}
while (n != NULL) {
printf("print %p %p %d\n", n, n->next, n->data);
n = n->next;
}
}
//-----------------------------------------------------------------------------
int main(void) {
node *n = NULL;
//----------------------------list_add---STL---Generic---<---not!specific--
list_add(&n, 0); /* list: 0 */
list_add(&n, 1); /* list: 1 0 */
list_add(&n, 2); /* list: 2 1 0 */
list_add(&n, 3); /* list: 3 2 1 0 */
list_add(&n, 4); /* list: 4 3 2 1 0 */
list_print(n);
list_remove(&n); /* remove first (4) */
list_remove(&n->next); /* remove new second (2) */
list_remove(list_search(&n, 1)); /* remove cell containing 1 (first) */
list_remove(&n->next); /* remove second to last node (0) */
list_remove(&n); /* remove last (3) */
list_print(n);
return 0;
}
//-----------------------------------------------------------------------------
Re: ＡＶＬ木の実装で困っています
どうしていきなりほとんど関係ない双方向リストのプログラムを貼ったのですか？Math さんが書きました: 私の双方向リストはコマンドライン・コンパイルが通ります。
複雑な問題？マシンの性能を上げてOpenMPで殴ればいい！(死亡フラグ)
-
Math
Re: ＡＶＬ木の実装で困っています
機種、ＯＳ，コンパイラーは何を使ってますか。Windows１０、VS2015ではエラーがでます。make_nodeの双方向リストみたいなあたりもおかしかったですよ。
AVL木、など木構造（リスト構造）はC++/C#の基本にもなるので知りたいと思っていたので調べてみましょう。(ところで何に使われるのですか？）
重大度レベル コード 説明 プロジェクト ファイル 行 抑制状態
エラー C2440 '=': 'void *' から 'int (*)[50]' に変換できません。 ConsoleApplication2 重大度レベル
エラー (アクティブ) 型 "void *" の値を使用して型 "Node *" のエンティティを初期化すエラー C2440
エラー C2440 '初期化中': 'void *' から 'Node *' に変換できません。 ConsoleApplication2 エラー (アクテ
エラー C2440 '初期化中': 'void *' から 'Tree *' に変換できません。 ConsoleApplication2 エラー C2440
エラー C2131 式は定数に評価されませんでした ConsoleApplication2 c:\users\数彦\documentエラー C2440
エラー C2440 '=': 'void *' から 'int *' に変換できません。 ConsoleApplication2 c:\useエラー C2131
エラー C2440 '=': 'void *' から 'int (*)[n]' に変換できません。 ConsoleApplication2 エラー C2440
エラー C2440 '=': 'void *' から 'int *' に変換できません。 ConsoleApplication2 c:\useエラー C2440
エラー C3863 配列型 'int [n]' を割り当てることはできません。 ConsoleApplication2 c:\useエラー C2440
警告 C4996 'scanf': This function or variable may be unsafe. Consider using scanf_s insteエラー C3863
警告 C4996 'scanf': This function or variable may be unsafe. Consider using scanf_s insteエラー (アクティ
エラー C2440 '初期化中': 'void *' から 'Node *' に変換できません。 ConsoleAエラー C2440 '初期化中': '
エラー C2440 '初期化中': 'void *' から 'Tree *' に変換できません。 ConsoleAエラー C2440 '初期化中': '
エラー C2131 式は定数に評価されませんでした ConsoleApplication2 c:\usersエラー C2131 式は定数に評価
エラー C2440 '=': 'void *' から 'int *' に変換できません。 ConsoleApplicatiエラー C2440 '=': 'void *'
エラー C2440 '=': 'void *' から 'int (*)[n]' に変換できません。 ConsoleAエラー C2440 '=': 'void *'
エラー C2440 '=': 'void *' から 'int *' に変換できません。 ConsoleApplicatiエラー C2440 '=': 'void *'
エラー C3863 配列型 'int [n]' を割り当てることはできません。 ConsoleApplicatiエラー C3863 配列型 'int [
警告 C4996 'scanf': This function or variable may be unsafe. Consider using警告 C4996 'scanf': This
Re: ＡＶＬ木の実装で困っています
C++の仕様に基づくメッセージがあるようです。Math さんが書きました:Windows１０、VS2015ではエラーがでます。make_nodeの双方向リストみたいなあたりもおかしかったですよ。重大度レベル コード 説明 プロジェクト ファイル 行 抑制状態 エラー C2440 '=': 'void *' から 'int (*)[50]' に変換できません。 ConsoleApplication2 重大度レベル エラー (アクティブ) 型 "void *" の値を使用して型 "Node *" のエンティティを初期化すエラー C2440 エラー C2440 '初期化中': 'void *' から 'Node *' に変換できません。 ConsoleApplication2 エラー (アクテ エラー C2440 '初期化中': 'void *' から 'Tree *' に変換できません。 ConsoleApplication2 エラー C2440 エラー C2131 式は定数に評価されませんでした ConsoleApplication2 c:\users\数彦\documentエラー C2440 エラー C2440 '=': 'void *' から 'int *' に変換できません。 ConsoleApplication2 c:\useエラー C2131 エラー C2440 '=': 'void *' から 'int (*)[n]' に変換できません。 ConsoleApplication2 エラー C2440 エラー C2440 '=': 'void *' から 'int *' に変換できません。 ConsoleApplication2 c:\useエラー C2440 エラー C3863 配列型 'int [n]' を割り当てることはできません。 ConsoleApplication2 c:\useエラー C2440 警告 C4996 'scanf': This function or variable may be unsafe. Consider using scanf_s insteエラー C3863 警告 C4996 'scanf': This function or variable may be unsafe. Consider using scanf_s insteエラー (アクティ エラー C2440 '初期化中': 'void *' から 'Node *' に変換できません。 ConsoleAエラー C2440 '初期化中': ' エラー C2440 '初期化中': 'void *' から 'Tree *' に変換できません。 ConsoleAエラー C2440 '初期化中': ' エラー C2131 式は定数に評価されませんでした ConsoleApplication2 c:\usersエラー C2131 式は定数に評価 エラー C2440 '=': 'void *' から 'int *' に変換できません。 ConsoleApplicatiエラー C2440 '=': 'void *' エラー C2440 '=': 'void *' から 'int (*)[n]' に変換できません。 ConsoleAエラー C2440 '=': 'void *' エラー C2440 '=': 'void *' から 'int *' に変換できません。 ConsoleApplicatiエラー C2440 '=': 'void *' エラー C3863 配列型 'int [n]' を割り当てることはできません。 ConsoleApplicatiエラー C3863 配列型 'int [ 警告 C4996 'scanf': This function or variable may be unsafe. Consider using警告 C4996 'scanf': This
code=Cと書かれているので、C++ではなくC言語としてコンパイルするべきでしょう。
オフトピック
あれ？
No: 5のコードでも同様にC++だとエラーになるvoid*からオブジェクトへのポインタへの暗黙の変換を使っているのに、
こっちは「コンパイルが通ります」と主張している。
妙だな。
まさか、事実をゆがめて中傷をしようとしている！？
No: 5のコードでも同様にC++だとエラーになるvoid*からオブジェクトへのポインタへの暗黙の変換を使っているのに、
こっちは「コンパイルが通ります」と主張している。
妙だな。
まさか、事実をゆがめて中傷をしようとしている！？
複雑な問題？マシンの性能を上げてOpenMPで殴ればいい！(死亡フラグ)
-
Math
Re: ＡＶＬ木の実装で困っています
あ、すいません。また勘違いしていました。コマンドライン・コンパイルでは/TC で.cppでもCとしてコンパイルしてくれるのにIDEでは.cに戻すのを忘れてました。するとコンパイルはOKでしたか？
-
RIKU13
Re: ＡＶＬ木の実装で困っています
お二人ともありがとうございます。
インデント等雑ですいません。
insert_node関数のどこを治すとうまくいくのでしょうか？いろいろ試してはいるのですがどうしても実行できないのでお願いします。
インデント等雑ですいません。
insert_node関数のどこを治すとうまくいくのでしょうか？いろいろ試してはいるのですがどうしても実行できないのでお願いします。
-
RIKU13
Re: ＡＶＬ木の実装で困っています
このように大幅に変えてみたのですが、やはりうまくいきませんでした。
アドバイスお願いします。
static Node *insert_node(int element,Node *node)
{
Node *prev = NULL;
if (node == NULL)
node = make_node(element,prev);
else if (element < node->element){
prev = node->left = insert_node(element,node->left);
}
else if (element > node->element){
prev = node->right = insert_node(element,node->right);
}
if (prev != NULL)
rebalance(prev, element < prev->element ? AVL_LEFT : AVL_RIGHT);
return node;
}
アドバイスお願いします。
static Node *insert_node(int element,Node *node)
{
Node *prev = NULL;
if (node == NULL)
node = make_node(element,prev);
else if (element < node->element){
prev = node->left = insert_node(element,node->left);
}
else if (element > node->element){
prev = node->right = insert_node(element,node->right);
}
if (prev != NULL)
rebalance(prev, element < prev->element ? AVL_LEFT : AVL_RIGHT);
return node;
}
-
Math
Re: ＡＶＬ木の実装で困っています
インデントを直しビルド・エラーを送ります。231行目に心当たりはありませんか？
重大度レベル コード 説明 プロジェクト ファイル 行 抑制状態
----------------------------------------------------------------------------------
エラー C2466 サイズが 0 の配列を割り当てまたは宣言しようとしました。 ConsAVLtree d:\h\vs2015\001\consavltree\consavltree\c1.c 231
エラー C2057 定数式が必要です。 ConsAVLtree d:\h\vs2015\001\consavltree\consavltree\c1.c 231
エラー C2036 'int (*)[0]': サイズが不明です。 ConsAVLtree d:\h\vs2015\001\consavltree\consavltree\c1.c 308
エラー (アクティブ)式には定数値が必要です ConsAVLtree d:\h\vs2015\001\ConsAVLtree\ConsAVLtree\c1.c 231
#define _CRT_SECURE_NO_WARNINGS
/*以下のようなＡＶＬ木のコードを書いてみたのですがセグメンテーション違反が出てしまい
原因が分からず困っています。
内容としては、ある数列をＡＶＬ木として挿入を行い、数列の数が50個までの場合は可視化
を行っています。初心者であるため、かなり煩雑なコードになっていますが、アドバイス
お願いいたします。なるべく早く返信を頂けると幸いです。
私の予想としてはinsert_nodeとrebalanceの中身でミスをしているのではないかという
検討を立てています。
*/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#define VISION 50
#define AVL_BALANCED 0
#define AVL_LEFT 1
#define AVL_RIGHT 2
typedef struct node {
struct node *left;
struct node *right;
struct node *parent;
int element;
int balance;
}Node;
typedef struct {
Node *root;
}Tree;
static void destroy_node(Node *node)//-----------------------------------------
{
if (node != NULL) {
destroy_node(node->left);
destroy_node(node->right);
free(node);
}
}
void rebalance(Node *node, int direct)//---------------------------------------
{
Node *prev, *next;
if (node == NULL) return;
if ((node->balance == AVL_LEFT && direct == AVL_RIGHT)
|| (node->balance == AVL_RIGHT && direct == AVL_LEFT))
{
node->balance = AVL_BALANCED;
}
else if (node->balance == AVL_BALANCED) {
node->balance = direct;
if ((prev = node->parent) != NULL)
rebalance(prev, node->element < prev->element ? AVL_LEFT : AVL_RIGHT);
}
else if (node->balance == direct) {
prev = node->parent;
if (node->left->balance == direct) {
next = (direct == AVL_LEFT) ? node->left : node->right;
node->parent = next;
next->parent = prev;
if (direct == AVL_LEFT) {
node->left = next->right;
next->right = node;
}
else {
node->right = next->left;
next->left = node;
}
node->balance = AVL_BALANCED;
next->balance = AVL_BALANCED;
}
else {
Node *dene;
if (direct == AVL_LEFT) {
dene = node->left;
next = dene->right;
}
else {
dene = node->right;
next = dene->left;
}
node->parent = next;
dene->parent = next;
next->parent = prev;
if (direct == AVL_LEFT) {
node->left = next->right;
next->right = node;
dene->right = next->left;
next->left = dene;
dene->balance = (next->balance == AVL_RIGHT) ?
AVL_LEFT : AVL_BALANCED;
node->balance = (next->balance == AVL_LEFT) ?
AVL_RIGHT : AVL_BALANCED;
}
else {
node->right = next->left;
next->left = node;
dene->left = next->right;
next->right = dene;
dene->balance = (next->balance == AVL_LEFT) ?
AVL_RIGHT : AVL_BALANCED;
node->balance = (next->balance == AVL_RIGHT) ?
AVL_LEFT : AVL_BALANCED;
}
next->balance = AVL_BALANCED;
}
if (prev->parent == NULL)
prev->left = prev->right = next;
else if (node->element < prev->element) prev->left = next;
else prev->right = next;
}
}
static Node *make_node(int element, Node *prev)//------------------------------
{
Node *node = malloc(sizeof(Node));
if (node != NULL) {
node->element = element;
node->left = NULL;
node->right = NULL;
node->balance = 0;
node->parent = prev;
}
return node;
}
/*
static Node *insert_node(int element, Node *node)//----------------------------
{
Node *prev = NULL;
while (node != NULL) {
if (element == node->element) return NULL;
prev = node;
if (element < node->element)
node->left = insert_node(element, node->left);
else
node->right = insert_node(element, node->right);
}
make_node(element, prev);
if (prev != NULL)
rebalance(prev, element < prev->element ? AVL_LEFT : AVL_RIGHT);
return node;
}
*/
static Node *insert_node(int element, Node *node)//----------------------------
{
Node *prev = NULL;
if (node == NULL)
node = make_node(element, prev);
else if (element < node->element) {
prev = node->left = insert_node(element, node->left);
}
else if (element > node->element) {
prev = node->right = insert_node(element, node->right);
}
if (prev != NULL)
rebalance(prev, element < prev->element ? AVL_LEFT : AVL_RIGHT);
return node;
}
int depth_node(int element, Node *node)//--------------------------------------
{
int depth = 0;
while (node->element != element) {
if (element < node->element) {
node = node->left;
}
else {
node = node->right;
}
depth++;
}
return depth;
}
int depth_tree(int element, Tree *tree)//-------------------------------------
{
return depth_node(element, tree->root);
}
Tree *make_tree(void)//--------------------------------------------------------
{
Tree *tree = malloc(sizeof(Tree));
if (tree != NULL) {
tree->root = NULL;
}
return tree;
}
void insert_tree(int elememt, Tree *tree)//------------------------------------
{
tree->root = insert_node(elememt, tree->root);
}
void destroy_tree(Tree *tree)//------------------------------------------------
{
destroy_node(tree->root);
free(tree);
}
int GetRandom(int min, int max)
{
return min + (int)(rand()*(max - min + 1.0) / (1.0 + RAND_MAX));
}
void shuffle(int *num, int n)//------------------------------------------------
{
int s, m, tmp;
for (s = n - 1; s > 0; s--) {
m = rand() % (s + 1);
tmp = num[s];
num[s] = num[m];
num[m] = tmp;
}
}
int main(void)/////////////////////////////////////////////////////////////////
{
int i, n, x, y, z, tree_number, *num, (*vision)[VISION],
depth, height, error, *height_tree;
double sum_height = 0, sum2_height = 0, real_number = 0, average1, average2;
srand((unsigned int)time(NULL));
printf("!!");
fflush(0);
scanf("%d", &n);
int(*check_tree)[n]; ////////////////////////////////////////////////////// 231 --- n
tree_number = (int)((double)n / log2((double)n));
num = calloc(n, sizeof(int));
check_tree = calloc(tree_number * n, sizeof(int));
height_tree = calloc(n, sizeof(int));
for (i = 0; i < n; i++)
num[i] = i + 1;
for (x = 0; x < tree_number; x++) {
Tree *tree = make_tree();
if (n <= VISION)
vision = calloc(VISION * VISION, sizeof(int));
height = 0;
error = 0;
shuffle(num, n);
for (i = 0; i < n; i++) {
insert_tree(num[i], tree);
if (n <= VISION)
printf("%d ", num[i]);
}
for (i = 0; i < n; i++) {
depth = depth_tree(num[i], tree);
if (n <= VISION)
vision[depth][num[i] - 1] = num[i];
if (depth >= height)
height = depth;
check_tree[x][num[i] - 1] = depth;
}
for (y = 0; y < x; y++) {
for (z = 0; z < n; z++) {
if (check_tree[y][z] != check_tree[x][z])
break;
}
if ((z == n) && (check_tree[y][z - 1] == check_tree[x][z - 1])) {
error++;
break;
}
}
if (x != 0 && error == 1) {
printf("this tree has been already created\n");
if (n <= VISION)
free(vision);
destroy_tree(tree);
continue;
}
if (n <= VISION) {
printf("\n");
for (y = 0; y <= height; y++) {
for (z = 0; z < n; z++) {
if (vision[y][z] != 0)
printf("%2d", vision[y][z]);
else
printf(" ");
}
printf("\n");
}
printf("%d\n", height);
}
if (n <= VISION)
free(vision);
destroy_tree(tree);
height_tree[height]++;
}
for (i = 0; i < n; i++) {
sum_height += (i * height_tree[i]);
sum2_height += (i * i * height_tree[i]);
real_number += height_tree[i];
}
average1 = sum_height / tree_number;
average2 = sum2_height / tree_number;
printf("%f\n%f\n", average1, average2 - average1 * average1);
free(check_tree);
free(height_tree);
return 0;
}
///EOF///
Re: ＡＶＬ木の実装で困っています
変数を要素数とする配列はC99から対応しています。Math さんが書きました:インデントを直しビルド・エラーを送ります。231行目に心当たりはありませんか？重大度レベル コード 説明 プロジェクト ファイル 行 抑制状態 ---------------------------------------------------------------------------------- エラー C2466 サイズが 0 の配列を割り当てまたは宣言しようとしました。 ConsAVLtree d:\h\vs2015\001\consavltree\consavltree\c1.c 231 エラー C2057 定数式が必要です。 ConsAVLtree d:\h\vs2015\001\consavltree\consavltree\c1.c 231 エラー C2036 'int (*)[0]': サイズが不明です。 ConsAVLtree d:\h\vs2015\001\consavltree\consavltree\c1.c 308 エラー (アクティブ)式には定数値が必要です ConsAVLtree d:\h\vs2015\001\ConsAVLtree\ConsAVLtree\c1.c 231
このエラーの原因は、コンパイラの性能が悪い、または前の規格に従うモードであるため対応していないことでしょう。
「セグメンテーション違反が出てしまい」とあるので、実行できている、すなわちコンパイルはできていると読めるでしょう。Math さんが書きました:するとコンパイルはOKでしたか？
オフトピック
コンパイラの品質が悪く、コンパイラの方がセグメンテーション違反を出している可能性がないわけではありませんが…
複雑な問題？マシンの性能を上げてOpenMPで殴ればいい！(死亡フラグ)
-
Math
Re: ＡＶＬ木の実装で困っています
今回はVS2015Communityを使用してｃ１．ｃでビルド。最初からこの位置でVS2015のコードに波線が(nに）入って怪しかった。cにしてそのエラーだけになった。
-
metalg_taken
- 記事: 1
- 登録日時: 8年前
Re: ＡＶＬ木の実装で困っています
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#define VISION 50
#define AVL_BALANCED 0
#define AVL_LEFT 1
#define AVL_RIGHT 2
typedef struct node {
struct node *left;
struct node *right;
struct node *parent;
int element;
int balance;
}Node;
typedef struct {
Node *root;
}Tree;
static void destroy_node(Node *node)
{
if (node != NULL) {
destroy_node(node->left);
destroy_node(node->right);
free(node);
}
}
/*void rebalance(Node *node, int direct)
{
Node *prev, *next;
if (node == NULL) return;
if ((node->balance == AVL_LEFT && direct == AVL_RIGHT)
|| (node->balance == AVL_RIGHT && direct == AVL_LEFT))
{
node->balance = AVL_BALANCED;
}
else if (node->balance == AVL_BALANCED) {
node->balance = direct;
if ((prev = node->parent) != NULL)
rebalance(prev, node->element < prev->element ? AVL_LEFT : AVL_RIGHT);
}
else if (node->balance == direct) {
prev = node->parent;
if (node->left->balance == direct) {
next = (direct == AVL_LEFT) ? node->left : node->right;
node->parent = next;
next->parent = prev;
if (direct == AVL_LEFT) {
node->left = next->right;
next->right = node;
}
else {
node->right = next->left;
next->left = node;
}
node->balance = AVL_BALANCED;
next->balance = AVL_BALANCED;
}
else {
Node *dene;
if (direct == AVL_LEFT) {
dene = node->left;
next = dene->right;
}
else {
dene = node->right;
next = dene->left;
}
node->parent = next;
dene->parent = next;
next->parent = prev;
if (direct == AVL_LEFT) {
node->left = next->right;
next->right = node;
dene->right = next->left;
next->left = dene;
dene->balance = (next->balance == AVL_RIGHT) ?
AVL_LEFT : AVL_BALANCED;
node->balance = (next->balance == AVL_LEFT) ?
AVL_RIGHT : AVL_BALANCED;
}
else {
node->right = next->left;
next->left = node;
dene->left = next->right;
next->right = dene;
dene->balance = (next->balance == AVL_LEFT) ?
AVL_RIGHT : AVL_BALANCED;
node->balance = (next->balance == AVL_RIGHT) ?
AVL_LEFT : AVL_BALANCED;
}
next->balance = AVL_BALANCED;
}
if (prev->parent == NULL)
prev->left = prev->right = next;
else if (node->element < prev->element) prev->left = next;
else prev->right = next;
}
}
*/
static Node *make_node(int element, Node *prev)
{
Node *node = malloc(sizeof(Node));
if (node != NULL) {
node->element = element;
node->left = NULL;
node->right = NULL;
node->balance = 0;
node->parent = prev;
}
return node;
}
static Node *insert_node(int element, Node *node)
{
Node *prev = NULL;
if (node == NULL)
node = make_node(element, prev);
else if (element < node->element) {
prev = node->left = insert_node(element, node->left);
}
else if (element > node->element) {
prev = node->right = insert_node(element, node->right);
}
if (prev != NULL)
//rebalance(prev, element < prev->element ? AVL_LEFT : AVL_RIGHT);
return node;
}
int depth_node(int element, Node *node)
{
int depth = 0;
while (node->element != element) {
if (element < node->element) {
node = node->left;
}
else {
node = node->right;
}
depth++;
}
return depth;
}
int depth_tree(int element, Tree *tree)
{
return depth_node(element, tree->root);
}
Tree *make_tree(void)
{
Tree *tree = malloc(sizeof(Tree));
if (tree != NULL) {
tree->root = NULL;
}
return tree;
}
void insert_tree(int elememt, Tree *tree)
{
tree->root = insert_node(elememt, tree->root);
}
void destroy_tree(Tree *tree)
{
destroy_node(tree->root);
free(tree);
}
int GetRandom(int min, int max)
{
return min + (int)(rand()*(max - min + 1.0) / (1.0 + RAND_MAX));
}
void shuffle(int *num, int n)
{
int s, m, tmp;
for (s = n - 1; s > 0; s--) {
m = rand() % (s + 1);
tmp = num[s];
num[s] = num[m];
num[m] = tmp;
}
}
int main(void)
{
int i, n, x, y, z, tree_number, *num, **vision,
depth, height, error, *height_tree, **check_tree;
double sum_height = 0, sum2_height = 0, real_number = 0, average1, average2;
srand((unsigned int)time(NULL));
printf("Input n: ");
fflush(0);
scanf("%d", &n);
tree_number = (int)((double)n / log2((double)n));
num = calloc(n, sizeof(int));
if ((check_tree = (int **)calloc(tree_number, sizeof(int *))) == NULL) {
fprintf(stderr, "Error\n");
exit(1);
}
for (i = 0; i < tree_number; i++) {
if ((check_tree[i] = (int *)calloc(n, sizeof(int))) == NULL) {
fprintf(stderr, "Error\n");
exit(2);
}
}
height_tree = calloc(n, sizeof(int));
for (i = 0; i < n; i++)
num[i] = i + 1;
for (x = 0; x < tree_number; x++) {
Tree *tree = make_tree();
if (n <= VISION) {
if ((vision = (int **)
calloc(VISION, sizeof(int *))) == NULL) {
fprintf(stderr, "Error\n");
exit(1);
}
for (i = 0; i < VISION; i++) {
if ((vision[i] = (int *)calloc(VISION, sizeof(int))) == NULL) {
fprintf(stderr, "Error\n");
exit(2);
}
}
}
height = 0;
error = 0;
shuffle(num, n);
for (i = 0; i < n; i++) {
insert_tree(num[i], tree);
if (n <= VISION)
printf("%d ", num[i]);
}
for (i = 0; i < n; i++) {
depth = depth_tree(num[i], tree);
if (n <= VISION)
vision[depth][num[i] - 1] = num[i];
if (depth >= height)
height = depth;
check_tree[x][num[i] - 1] = depth;
}
for (y = 0; y < x; y++) {
for (z = 0; z < n; z++) {
if (check_tree[y][z] != check_tree[x][z])
break;
}
if ((z == n) && (check_tree[y][z - 1] == check_tree[x][z - 1])) {
error++;
break;
}
}
if (x != 0 && error == 1) {
printf("this tree has been already created\n");
if (n <= VISION)
free(vision);
destroy_tree(tree);
continue;
}
if (n <= VISION) {
printf("\n");
for (y = 0; y <= height; y++) {
for (z = 0; z < n; z++) {
if (vision[y][z] != 0)
printf("%2d", vision[y][z]);
else
printf("%2s", " ");
}
printf("\n");
}
printf("height = %d\n\n", height);
}
if (n <= VISION)
free(vision);
destroy_tree(tree);
height_tree[height]++;
}
for (i = 0; i < n; i++) {
sum_height += (i * height_tree[i]);
sum2_height += (i * i * height_tree[i]);
real_number += height_tree[i];
}
average1 = sum_height / tree_number;
average2 = sum2_height / tree_number;
printf("%f\n%f\n", average1, average2 - average1 * average1);
free(check_tree);
free(height_tree);
return 0;
}
１．木の表示の部分で%2dとしているのならば、見栄えをよくするために空白も2文字分入れるとよいと思います。
２．callocを2回用いることによって、2次元配列の領域を確保してみました。領域確保に関してはこれで大丈夫だと思います。
それと、領域確保できなかったときのエラーメッセージを入れておいた方が良いと思います。
このようにすると普通の木はちゃんと作れたので、おそらくrebalance関数内に問題があるのかと思われます。
Re: ＡＶＬ木の実装で困っています
それはたまたまでしょう。metalg_taken さんが書きました:このようにすると普通の木はちゃんと作れたので
insert_node関数において、引数nodeがNULLのとき、return文を通らずに関数が終了するので返される値は不定になり、その返り値を用いると未定義動作になります。
Wandboxで実験をしたところ、
最適化をかけない場合はたまたまうまく動いてしまいましたが、
最適化をかけるとSegnemtation Faultになりました。
複雑な問題？マシンの性能を上げてOpenMPで殴ればいい！(死亡フラグ)
Re: ＡＶＬ木の実装で困っています
みなさんありがとうございます。
みなさんのアドバイスを元にいろいろ試してみてはいるのですが、いまだ動作していません。
rebalance,もしくはinsertが異常を示しているのは確かとは思います。その手の改善点があればお願いします。
みなさんのアドバイスを元にいろいろ試してみてはいるのですが、いまだ動作していません。
rebalance,もしくはinsertが異常を示しているのは確かとは思います。その手の改善点があればお願いします。
Re: ＡＶＬ木の実装で困っています
闇雲にコードを書き換えて実行してみるだけでなく、デバッガやprintfデバッグなどによる解析はしていますか？
最新のコードがないと、こちらでデバッグをするのは難しいと思います。
最新のコードがないと、こちらでデバッグをするのは難しいと思います。
複雑な問題？マシンの性能を上げてOpenMPで殴ればいい！(死亡フラグ)
Re: ＡＶＬ木の実装で困っています
特にソースは変更する前の状態に戻しました。やはりrebalanceがおかしいのでしょうか。eclipseを使用していますが10を入力すると動作が停止してしまうためprintfデバックが使えません。
-
Math
Re: ＡＶＬ木の実装で困っています
（あ、私の双方向listのＰｒｏｇｒａｍは書き方が参考にならないのですね）
の4か所訂正で直ると思います。
Re: ＡＶＬ木の実装で困っています
C言語においては、malloc()系のメモリ確保関数の戻り値は自動で変換されるので、明示的にはキャストしないべきであるという主張があります。
c - Do I cast the result of malloc? - Stack Overflow
c - Do I cast the result of malloc? - Stack Overflow
どうしてそう思うのですか？Math さんが書きました: の4か所訂正で直ると思います。
複雑な問題？マシンの性能を上げてOpenMPで殴ればいい！(死亡フラグ)
Re: ＡＶＬ木の実装で困っています
「変更する前」とは、具体的にどういう状態ですか？RIKU13 さんが書きました:特にソースは変更する前の状態に戻しました。
確実に強制終了するコードに戻したら、確実に強制終了するのは当たり前でしょう。
そう思うなら、まずrebalanceの処理を無くしてみてそれでも落ちるかをチェックすることで、本当におかしそうかをチェックしましょう。RIKU13 さんが書きました:やはりrebalanceがおかしいのでしょうか。
GDBなどのデバッガは使えますか？RIKU13 さんが書きました:printfデバックが使えません。
複雑な問題？マシンの性能を上げてOpenMPで殴ればいい！(死亡フラグ)
-
Math
Re: ＡＶＬ木の実装で困っています
動作確認しました。[実行結果]Windows10,VC++2015Community(コマンドライン・コンパイル）
[c.bat]コマンドライン・コンパイル用バッチファイル
D:\h\z10\01\19\02>cl /EHsc c1.cpp
Microsoft(R) C/C++ Optimizing Compiler Version 19.00.24215.1 for x86
Copyright (C) Microsoft Corporation. All rights reserved.
c1.cpp
d:\h\z10\01\19\02\c1.cpp(136) : warning C4715: 'insert_node': 値を返さないコントロール パスがあります。
Microsoft (R) Incremental Linker Version 14.00.24215.1
Copyright (C) Microsoft Corporation. All rights reserved.
/out:c1.exe
c1.obj
D:\h\z10\01\19\02>rem -------------------------------- c1.exe
D:\h\z10\01\19\02>c1.exe
Start--->
Input n: 10
001:shuffle:24 2 6 8 1 7 5 10 9 3
4
2 6
1 3 5 8
7 10
9
height = 4
001:shuffle:87 8 1 10 6 3 4 2 5 9
7
1 8
6 10
3 9
2 4
5
height = 5
001:shuffle:88 5 2 3 9 10 1 6 4 7
8
5 9
2 6 10
1 3 7
4
height = 4
4.333333
0.222222
D:\h\z10\01\19\02>
-
Math
Re: ＡＶＬ木の実装で困っています
[c1.cpp]
#define _CRT_SECURE_NO_WARNING
#include<stdio.h>/////////////
#include<stdlib.h>////////////
#include<math.h>//////////////
#include<time.h>////////////// AVL Tree
#define VISION 50/////////////
#define AVL_BALANCED 0////////
#define AVL_LEFT 1 ////////
#define AVL_RIGHT 2 ////////
////////
typedef struct node {//Tree構造体
struct node *left;//////左///
struct node *right;////右////
struct node *parent;//親/////
int element;//メンバ[element]
int balance;//メンバ[balance]
}Node;//Node型///////////////////
//
typedef struct {//Nodeのポインター//
Node *root; //
}Tree;//Tree型////////////////////
static void destroy_node(Node *node)
{
if (node != NULL) {
destroy_node(node->left);
destroy_node(node->right);
free(node);
}
}
/*void rebalance(Node *node, int direct)
{
Node *prev, *next;
if (node == NULL) return;
if ((node->balance == AVL_LEFT && direct == AVL_RIGHT)
|| (node->balance == AVL_RIGHT && direct == AVL_LEFT))
{
node->balance = AVL_BALANCED;
}
else if (node->balance == AVL_BALANCED) {
node->balance = direct;
if ((prev = node->parent) != NULL)
rebalance(prev, node->element < prev->element ? AVL_LEFT : AVL_RIGHT);
}
else if (node->balance == direct) {
prev = node->parent;
if (node->left->balance == direct) {
next = (direct == AVL_LEFT) ? node->left : node->right;
node->parent = next;
next->parent = prev;
if (direct == AVL_LEFT) {
node->left = next->right;
next->right = node;
}
else {
node->right = next->left;
next->left = node;
}
node->balance = AVL_BALANCED;
next->balance = AVL_BALANCED;
}
else {
Node *dene;
if (direct == AVL_LEFT) {
dene = node->left;
next = dene->right;
}
else {
dene = node->right;
next = dene->left;
}
node->parent = next;
dene->parent = next;
next->parent = prev;
if (direct == AVL_LEFT) {
node->left = next->right;
next->right = node;
dene->right = next->left;
next->left = dene;
dene->balance = (next->balance == AVL_RIGHT) ?
AVL_LEFT : AVL_BALANCED;
node->balance = (next->balance == AVL_LEFT) ?
AVL_RIGHT : AVL_BALANCED;
}
else {
node->right = next->left;
next->left = node;
dene->left = next->right;
next->right = dene;
dene->balance = (next->balance == AVL_LEFT) ?
AVL_RIGHT : AVL_BALANCED;
node->balance = (next->balance == AVL_RIGHT) ?
AVL_LEFT : AVL_BALANCED;
}
next->balance = AVL_BALANCED;
}
if (prev->parent == NULL)
prev->left = prev->right = next;
else if (node->element < prev->element) prev->left = next;
else prev->right = next;
}
}
*/
static Node *make_node(int element, Node *prev)
{
Node *node = (Node *)malloc(sizeof(Node));//<<<-----(Node *)---------------
if (node != NULL) {
node->element = element;
node->left = NULL;
node->right = NULL;
node->balance = 0;
node->parent = prev;
}
return node;
}
static Node *insert_node(int element, Node *node)
{
Node *prev = NULL;
if (node == NULL)
node = make_node(element, prev);
else if (element < node->element) {
prev = node->left = insert_node(element, node->left);
}
else if (element > node->element) {
prev = node->right = insert_node(element, node->right);
}
if (prev != NULL)
//rebalance(prev, element < prev->element ? AVL_LEFT : AVL_RIGHT);
return node;
}
int depth_node(int element, Node *node)
{
int depth = 0;
while (node->element != element) {
if (element < node->element) {
node = node->left;
}
else {
node = node->right;
}
depth++;
}
return depth;
}
int depth_tree(int element, Tree *tree)
{
return depth_node(element, tree->root);
}
Tree *make_tree(void)
{
Tree *tree = (Tree *)malloc(sizeof(Tree));//<<<----------------------------
if (tree != NULL) {
tree->root = NULL;
}
return tree;
}
void insert_tree(int elememt, Tree *tree)
{
tree->root = insert_node(elememt, tree->root);
}
void destroy_tree(Tree *tree)
{
destroy_node(tree->root);
free(tree);
}
int GetRandom(int min, int max)
{
return min + (int)(rand()*(max - min + 1.0) / (1.0 + RAND_MAX));
}
void shuffle(int *num, int n)
{
int s, m, tmp;
for (s = n - 1; s > 0; s--) {
m = rand() % (s + 1);
tmp = num[s];
num[s] = num[m];
num[m] = tmp;
}printf("001:shuffle:%d", tmp);//------------------------------------------
}
int main(void)/////////////////////////////////////////////////////////////////①
{
int i, n, x, y, z, tree_number, *num, **vision,
depth, height, error, *height_tree, **check_tree;
double sum_height = 0, sum2_height = 0, real_number = 0, average1, average2;
srand((unsigned int)time(NULL));//乱数発生装置
printf("Start--->\n");
printf("Input n: ");//n入力
fflush(0);
scanf("%d", &n);
tree_number = (int)((double)n / log2((double)n));
num =(int *) calloc(n, sizeof(int));//<<<-------------------------------------
if ((check_tree = (int **)calloc(tree_number, sizeof(int *))) == NULL) {
fprintf(stderr, "Error\n");
exit(1);
}
for (i = 0; i < tree_number; i++) {
if ((check_tree[i] = (int *)calloc(n, sizeof(int))) == NULL) {
fprintf(stderr, "Error\n");
exit(2);
}
}
height_tree =(int *)calloc(n, sizeof(int));//<<<---------------------------------
for (i = 0; i < n; i++)
num[i] = i + 1;
for (x = 0; x < tree_number; x++) {
Tree *tree = make_tree();
if (n <= VISION) {
if ((vision = (int **)
calloc(VISION, sizeof(int *))) == NULL) {
fprintf(stderr, "Error\n");
exit(1);
}
for (i = 0; i < VISION; i++) {
if ((vision[i] = (int *)calloc(VISION, sizeof(int))) == NULL) {
fprintf(stderr, "Error\n");
exit(2);
}
}
}
height = 0;
error = 0;
shuffle(num, n);
for (i = 0; i < n; i++) {
insert_tree(num[i], tree);
if (n <= VISION)
printf("%d ", num[i]);
}
for (i = 0; i < n; i++) {
depth = depth_tree(num[i], tree);
if (n <= VISION)
vision[depth][num[i] - 1] = num[i];
if (depth >= height)
height = depth;
check_tree[x][num[i] - 1] = depth;
}
for (y = 0; y < x; y++) {
for (z = 0; z < n; z++) {
if (check_tree[y][z] != check_tree[x][z])
break;
}
if ((z == n) && (check_tree[y][z - 1] == check_tree[x][z - 1])) {
error++;
break;
}
}
if (x != 0 && error == 1) {
printf("this tree has been already created\n");
if (n <= VISION)
free(vision);
destroy_tree(tree);
continue;
}
if (n <= VISION) {
printf("\n");
for (y = 0; y <= height; y++) {
for (z = 0; z < n; z++) {
if (vision[y][z] != 0)
printf("%2d", vision[y][z]);
else
printf("%2s", " ");
}
printf("\n");
}
printf("height = %d\n\n", height);
}
if (n <= VISION)
free(vision);
destroy_tree(tree);
height_tree[height]++;
}
for (i = 0; i < n; i++) {
sum_height += (i * height_tree[i]);
sum2_height += (i * i * height_tree[i]);
real_number += height_tree[i];
}
average1 = sum_height / tree_number;
average2 = sum2_height / tree_number;
printf("%f\n%f\n", average1, average2 - average1 * average1);
free(check_tree);
free(height_tree);
return 0;
}
Re: ＡＶＬ木の実装で困っています
このコードは、insert_node関数に引数node=NULLを渡した時return文を通らずに戻るので戻り値が不定になり、Math さんが書きました:動作確認しました。
その不定の戻り値をtree->rootに代入して次回のinsert_node関数の呼び出しで使うので、未定義動作です。
No: 16のmetalg_takenさんのコードと同じバグです。
たまたま上手く動いているように見えてしまったのは、運が悪かったですね。
代入後のtree->rootの値を出力する処理を追加した所、
最適化をかけない場合はたまたまいい感じの値になってたまたまうまく動くように見えてしまうが、
最適化をかけるとたまたま変な値になってたまたまSegmentation Faultになるという現象が観測できました。
ちゃんと警告が出ていますね。無視してはいけません。
複雑な問題？マシンの性能を上げてOpenMPで殴ればいい！(死亡フラグ)
-
Math
Re: ＡＶＬ木の実装で困っています
なるほど。そういう警告だったのですか。（気にはなったけど..）
[雑談]javaFXはパラダイムシフトでswingとは（C#の）FormとWPFほど違っている。javaはswingを捨ててjavaFXにするらしい。mainがなくても動いたり..いままでと文法が違うらしい。とても分かりにくい...もう集中しないととても..
[雑談]javaFXはパラダイムシフトでswingとは（C#の）FormとWPFほど違っている。javaはswingを捨ててjavaFXにするらしい。mainがなくても動いたり..いままでと文法が違うらしい。とても分かりにくい...もう集中しないととても..
-
Math
Re: ＡＶＬ木の実装で困っています
まあ何度やっても正常に動作するので"printｆ”Debugなり通常のDebugが可能なのでそうすれば解決するでしょう。
（しかしeclipsでC/C++言語を何回かトライしたがVS2015に比べ難解で相当習熟しないとVS2015のようにいかないので”printf--Debugが有効でしょうね。(まあVS2015でも有効ですが））
（しかしeclipsでC/C++言語を何回かトライしたがVS2015に比べ難解で相当習熟しないとVS2015のようにいかないので”printf--Debugが有効でしょうね。(まあVS2015でも有効ですが））
メニュー
カレンダー
Clock
最新メンバー
投稿数
統計データ
Link to us
カウンター