c-出队时出现分段故障

Question

我对DS很陌生，我正在尝试使用队列实现二叉树级别的顺序遍历。算法如下。

1. 获取树的根
2. detached_node=根
3. 而detached_node：
   • 打印detached_node->数据
   • 排队detached_node->left和detached_node->对，如果不是NULL
   • detached_node=退出队列((

我在dequeue((中遇到分段错误。这是gdb核心转储。

gdb main core
GNU gdb (Ubuntu 8.1-0ubuntu3.2) 8.1.0.20180409-git
This GDB was configured as "x86_64-linux-gnu".
(gdb) r
Starting program: /home/runner/DryPartialNetbsd/main 
warning: Error disabling address space randomization: Operation not permitted
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/x86_64-linux-gnu/libthread_db.so.1".
Program received signal SIGSEGV, Segmentation fault.
0x00000000004006d3 in dequeue ()

我不确定我在这里遗漏了什么，我正在努力理解。

以下是代码

#include <stdio.h>
#include <stdlib.h>
struct t_node {
int data;
struct t_node* left;
struct t_node* right;
};
struct t_node* create_t_node(int value) {
struct t_node* node = (struct t_node*) malloc(sizeof(struct t_node));
node->data = value;
node->left = NULL;
node->right = NULL;
return node;
}
struct q_node {
struct t_node* data;
struct q_node* next;
};
struct q_node* rear = NULL;
struct q_node* front = NULL;
struct q_node* create_q_node(struct t_node* value) {
struct q_node* node = (struct q_node*) malloc(sizeof(struct q_node));
node->data = value;
node->next = NULL;
return node;
}
void create_queue(struct t_node* value) {
struct q_node* node = create_q_node(value);
front = node;
rear = node;
}
void enqueue(struct t_node* value) {
if (front == NULL && rear == NULL) {
create_queue(value);
} else {
struct q_node* node = create_q_node(value);
rear->next = node;
front->next = node;
rear = node;
}
}
struct t_node* dequeue() {
if(rear == NULL && front == NULL) 
return NULL;
else {
struct q_node* node = front;
front = front->next;
return node->data; 
}
}
void print_level_order(struct t_node* root) {
if(root == NULL) {
return;
}
struct t_node* detached_node = root;
while(detached_node != NULL) {
printf("%d ", detached_node->data);
if(detached_node->left != NULL) {
enqueue(detached_node->left);
}
if(detached_node->right != NULL) {
enqueue(detached_node->right);
}
detached_node = dequeue();
}
}
int main(void) {
struct t_node* root = create_t_node(1);
root->left = create_t_node(2);
root->right = create_t_node(3);
root->left->left = create_t_node(4);
root->left->right = create_t_node(5);
root->right->left = create_t_node(6);
root->right->right = create_t_node(7);

print_level_order(root);
}

Answer 1

您的问题来了，因为当入队时，您更新了后部和前部，但当出队时，您只更新前部，所以在dequeue中：

if(rear == NULL && front == NULL)

不可能为真，如果您在使后为非NULL之前至少将入队一次，然后在足够的出队之后执行：

front = front->next;

当前为空时

因此，将出队列修改为

struct t_node* dequeue() {
if(rear == NULL && front == NULL) 
return NULL;
else {
struct q_node* node = front;
front = front->next;
if (front == NULL)
rear = NULL;
struct t_node* result = node->data; 

free(node);
return result;
}
}

注意，你还需要释放内存以避免内存泄漏

修正后：

pi@raspberrypi:/tmp $ gcc -g -Wall c.c
pi@raspberrypi:/tmp $ ./a.out
1 2 3 5 7 pi@raspberrypi:/tmp $