0

我已经实现了一个二叉树及其 BFS 遍历。程序如下： 

struct elemq{
    int ele;
    struct elemq *left;
    struct elemq *right;
};

struct que{
    struct elemq *ss;
    struct que *next;
}; 

void qinsert(struct elemq *ptr){
    struct que *node;
    node = (struct que *)malloc(sizeof(struct que));
    if(front == NULL && rear == NULL){
            node->ss = ptr;
            node->next = NULL;
            front = node;
            rear = node;
    }
    else{
            node->ss = ptr;
            node->next = NULL;
            rear->next = node;
            rear = node;
    }
}

struct elemq *qdelete(){
    if(front == NULL && rear == NULL){
            cout << "No elements to delete\n";
            exit(0);
    }
    struct elemq *dd = front->ss;
    struct que *ddd = front;
    front = front->next;
    free(ddd);
return dd;
}

int isempty(){
    if(front == NULL && rear == NULL){
            return 1;
    }
    else{
            return 0;
    }
}

void bfs(){
    qinsert(root);
    struct elemq *fff;
    while(!isempty()){
            fff = qdelete();
            cout << fff->ele  << "\n";
            if(fff->left != NULL){
                    qinsert(fff->left);
            }
            if(fff->right != NULL){
                    qinsert(fff->right);
            }
    }
}

虽然代码很长，但是很容易理解。elemq 结构是树中节点的结构。que 是我用来实现 bfs 的队列。q insert 是将元素插入队列，qdelete 删除队列中的元素。isempty() 用于检查队列是否为空。程序显示根元素，然后给出分段错误。请帮忙。挣扎了一段时间。

4

1 回答 1

3

如果队列中只有一个元素，该qdelete函数将无法正常工作：

struct elemq *qdelete(){
    if(front == NULL && rear == NULL){
            cout << "No elements to delete\n";
            exit(0);
    }
    struct elemq *dd = front->ss;
    struct que *ddd = front;
    front = front->next;
    free(ddd);
return dd;
}

在这种情况下front设置为NULL，但rear仍指向 now freed 内存。

添加一个

if (front == rear) {
    struct elemq *dd = front->ss;
    free(front);
    front = rear = NULL;
} else {
   // what you have
}

要解决这个问题。

于 2012-10-29T21:00:29.467 回答