c++ - 为什么此代码会出现段错误？

Question

我正在实现以下算法:

1.创建一个空队列。

2.将链表的第一个节点作为根，入队到队列中。

3.直到我们到达列表的末尾，执行以下操作。

• 从队列中取出一个节点。这是当前的父级。

• 遍历列表中的两个节点，将它们添加为当前父节点的子节点。

• 将两个节点入队。

---

#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) 

我无法理解为什么我会在函数开头遇到段错误!？

Answer 1

您的 while(head->next) 循环中似乎缺少一些检查。我认为您应该检查 next 和 next-to-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++ 风格混合，选择一种语言并尝试坚持使用它。我在这里谈论的是使用 malloc 和 typedef struct，尽管它们可以编译，但它们不是“普通的”C++。