なぜこのコードはセグメンテーションフォルトを示していますか？

Question

次のアルゴリズムを実装しています。

1.空のキューを作成します。

2.リストの最初のノードをルートとして作成し、キューにエンキューします。

3.リストの末尾に達するまで、以下を実行してください。

• キューから1つのノードをデキューします。これは現在の親です。

• リスト内の2つのノードをトラバースし、それらを現在の親の子として追加します。

• キューに2つのノードをエンキューします。

---

#include <iostream> 
#include <string.h> 
#include <stdlib.h> 
#include <queue> 
using namespace std; 

struct Node{ 
    int data; 
    struct Node* next; 
}; 

typedef struct Node* NODE; 

NODE createNode(int data){ 
    NODE newNode = (NODE) malloc (sizeof(struct Node)); 
    newNode->data = data; 
    newNode->next = NULL; 
    return (newNode); 
} 

void insertAtEnd(NODE* head, int data){ 
    NODE newNode = createNode(data); 
    if(*head == NULL){ 
     *head = newNode; 
     return ; 
    } 

    NODE temp = *head; 
    while(temp->next){ 
     temp = temp->next; 
    } 
    temp->next = newNode; 
    newNode->next = NULL; 
    return; 
} 


struct tree_node{ 
    int data; 
    struct tree_node* left; 
    struct tree_node* right; 
}; 

typedef struct tree_node* T_NODE; 

T_NODE createTreeNode(int data){ 
    T_NODE newNode = new tree_node; 
    newNode->right = NULL; 
    newNode->left = NULL; 
    newNode->data = data; 
    return newNode; 
} 

void inorderTraversal(){} 


T_NODE convertListIntoCBT(NODE head){ 


    T_NODE root; 

    if(head){ 
     queue<T_NODE>q; 
     root=createTreeNode(head->data); 

     if(!root){ 
      cout << "Error creating root"<<endl; 
      exit(-1); 
     } 
     q.push(root); 

     T_NODE temp=NULL , parent=NULL; 
     while(head->next){ 
      temp = q.front(); 
      q.pop(); 
      parent = temp; 
      head = head->next; 
      parent->left = createTreeNode(head->data); 
      q.push(parent->left); 
      head = head->next; 
      parent->right = createTreeNode(head->data); 
      q.push(parent->right); 
     } 

     return root; 
    } 
} 

int main(){ 

    NODE head = NULL; 
    insertAtEnd(&head,36); 
    insertAtEnd(&head,30); 
    insertAtEnd(&head,25); 
    insertAtEnd(&head,15); 
    insertAtEnd(&head,12); 
    insertAtEnd(&head,10); 

    //convert the given linked list into complete binary tree 
    T_NODE new_root = convertListIntoCBT(head); 

    return 0; 
} 

私は、GDBを使用してデバッグしようと、私は次のような結果だ：私はの初めにセグメンテーションフォールトを取得しています理由として理解することはできませんよ

Program received signal SIGSEGV, Segmentation fault. 
0x0000000000400e5a in convertListIntoCBT(Node*)() 
(gdb) backtrace 
0 0x0000000000400e5a in convertListIntoCBT(Node*)() 
1 0x0000000000400fa2 in main() 
(gdb) 

を関数！？ -gで構築された場合

Answer 1

あなたのwhile(head->next)ループに何らかの欠落チェックがあるようです。

while(head->next && head->next->next) 
{ 
    //... 
} 

または可能性ループ内で二度目を進める前に再度確認してください：

while(head->next){ 
     temp = q.front(); 
     q.pop(); 
     parent = temp; 
     head = head->next; 
     parent->left = createTreeNode(head->data); 
     q.push(parent->left); 

     if(head->next) // <-- check again here 
     { 
      head = head->next; 
      parent->right = createTreeNode(head->data); 
      q.push(parent->right); 
     } 
    } 

私はあなたが両方のループ内で使用しているので、あなたが次と次のツー隣の両方にチェックを置くべきだと思います

また、コメントに記載されているように、CスタイルとC++スタイルを混在させないで、1つの言語を選択してそれに固執しようとします。私はここでmallocとtypedef structを使って話していますが、コンパイルされていても「普通の」C++ではありません。

while(head->next){ 
    temp = q.front(); 
    q.pop(); 
    parent = temp; 
    head = head->next; 
    parent->left = createTreeNode(head->data); 
    q.push(parent->left); 
    head = head->next; 
    parent->right = createTreeNode(head->data); 
    q.push(parent->right); 
} 

最後の3行は、ヘッドがNULLであるか否かを確認することなく繰り返される。

Answer 2

あなたはデバッグバイナリを持っている必要があります。

% lldb 1 
(lldb) target create "1" 
Current executable set to '1' (x86_64). 
(lldb) r 
Process 44386 launched: '/Users/paul/src/cpp/1' (x86_64) 
Process 44386 stopped 
* thread #1: tid = 0xb6153, 0x0000000100001217 1`convertListIntoCBT(head=0x0000000000000000) + 887 at 1.cpp:81, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x0) 
    frame #0: 0x0000000100001217 1`convertListIntoCBT(head=0x0000000000000000) + 887 at 1.cpp:81 
    78         parent->left = createTreeNode(head->data); 
    79         q.push(parent->left); 
    80         head = head->next; 
-> 81         parent->right = createTreeNode(head->data); 
    82         q.push(parent->right); 
    83       } 
    84 
(lldb) bt 
* thread #1: tid = 0xb6153, 0x0000000100001217 1`convertListIntoCBT(head=0x0000000000000000) + 887 at 1.cpp:81, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x0) 
    * frame #0: 0x0000000100001217 1`convertListIntoCBT(head=0x0000000000000000) + 887 at 1.cpp:81 
    frame #1: 0x0000000100001484 1`main + 116 at 1.cpp:100 
    frame #2: 0x00007fff9cffe5ad libdyld.dylib`start + 1 
    frame #3: 0x00007fff9cffe5ad libdyld.dylib`start + 1 
(lldb) p parent 
(T_NODE) $0 = 0x0000000100300320 
(lldb) p head 
(NODE) $1 = 0x0000000000000000 

ので、ライン80であなたがhead = head->nextを行うことによってnullptrことheadします。 81行目ではhead->dataにアクセスし、head == nullptrではsegfaultにアクセスします。

Answer 3

キーエラーコードのこの部分です。この場合、関数は関数が期待する前にリストを終了し、nullptrを逆参照しようとするとプログラムがクラッシュします。 convertListIntoCBTのチェックを追加して中止したり、リスト内の正しい数の要素をinsertAtHead関数に強制する方法を構築することができます。

Answer 4

他の答えとして、問題はwhileステートメントにあります。

convertListIntoCBTの別の問題は、head == nullptrの場合、returnがないことです。