c - 广度优先搜索突然崩溃

Question

我正在尝试在 400x200 网格上实现 BFS，该网格输入一个包含有序起始对和有序结束对的文本文件。我使用一个队列来跟踪打开的节点，并使用一个数组来跟踪关闭的节点。在检查队列中打开的节点时，我的程序在同一输入上不断随机崩溃。

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>


typedef struct Node Node;
typedef struct Qnode Qnode;

struct Node{
    Node* up;
    Node* down;
    Node* left;
    Node* right;
    int xpos;
    int ypos;
    int marked;
};
struct Qnode{
    Qnode* next;
    Node* Gnode; 
};
Qnode* front = NULL;
Qnode* rear = NULL;
int queuesize = 0;
int solutioncost = 0;
Node* closednodes[80000];
int nodesclosed = 0;

void enqueue(Node* node){
    if (queuesize == 0){
        rear = (Qnode*)malloc(sizeof(Qnode*));
        rear->Gnode = node;
        rear->next = NULL;
        front = rear;
    }
    else{
        Qnode* temp = (Qnode*)malloc(sizeof(Qnode*));
        rear->next = temp;
        temp->Gnode = node;
        temp->next = NULL;
        rear = temp;
    }
        queuesize++;
}

Node* dequeue(){
    Qnode* temp = front;
    if (queuesize == 0){
        printf("Error!");
    }
    else{
        Node* temp1 = front->Gnode;
        temp = temp->next;
        free(front);
        front = temp;
        queuesize--;
        return temp1;
    }

}

Node* generate(int x, int y){
    printf("Generating node (%d,%d)...\n", x, y);
    if ((x >0 && x <=400) && (y >0 && y <=200)){
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->xpos = x;
    temp->ypos = y;
    temp->marked = 0;
    temp->up = NULL;
    temp->down = NULL;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
    }
    else{
        printf("Invalid starting point! \n");
    }
}

void expand(Node* node, int xend, int yend){
    int flag = 0;
    closednodes[nodesclosed] = node;
    nodesclosed++;
    dequeue();
    if(node->marked == 1){
        printf("already expanded");
    }

    else{
        printf("Expanding node (%d, %d)...\n", node->xpos, node->ypos);
        node->marked = 1;
        if (node->xpos == xend && node->ypos == yend){
            printf("Node reached!");
            queuesize = 0; 
            return;
        }
        if (node->xpos-1 >0 && node->left == NULL){
            int k = 0;
            int j = 0;
            Qnode* temp2 = front;
            printf("%d", queuesize);
            for(k; k<queuesize; k++){
                int xx = temp2->Gnode->xpos;
                int yy = temp2->Gnode->ypos;
                printf("%d, %d,\n", xx, yy);
                if (xx == node->xpos-1 && yy == node->ypos)
                    flag = 1;
                temp2 = temp2->next;
                }
            for(j; j<nodesclosed; j++){
                int xx = closednodes[j]->xpos;
                int yy = closednodes[j]->ypos;
                if (xx == node->xpos-1 && yy == node->ypos)
                    flag = 1;
            }
            if (flag == 0){
                node->left = generate(node->xpos-1, node->ypos);
                node->left->right = node->left;
                enqueue(node->left);
            }
            else{
                printf("(%d, %d) not generated.\n", node->xpos-1, node->ypos);
                flag = 0;
            }
        }
        if (node->xpos+1 <=400 && node->right ==NULL){
        int k = 0;
        int j = 0;
        Qnode* temp2 = front;
            for(k; k<queuesize; k++){
                int xx = temp2->Gnode->xpos;
                int yy = temp2->Gnode->ypos;
                printf("%d, %d,\n", xx, yy);
                if (xx == node->xpos+1 && yy == node->ypos)
                    flag = 1;
                temp2 = temp2->next;
                }

            for(j; j<nodesclosed; j++){
                int xx = closednodes[j]->xpos;
                int yy = closednodes[j]->ypos;
                if (xx == node->xpos+1 && yy == node->ypos)
                    flag = 1;
            }
            if (flag == 0){
                node->right = generate(node->xpos+1, node->ypos);
                node->right->left = node->right;
                enqueue(node->right);
            }
            else{
                printf("(%d, %d) not generated.\n", node->xpos+1, node->ypos);
                flag = 0;
            }
        }
        if (node->ypos+1 <=200 && node->up ==NULL){
        int k = 0;
        int j = 0;
        Qnode* temp2 = front;
        printf("%d", queuesize);
            for(k; k<queuesize; k++){
                int xx = temp2->Gnode->xpos;
                int yy = temp2->Gnode->ypos;
                if (xx == node->xpos && yy == node->ypos+1)
                    flag = 1;
                temp2 = temp2->next;
                }


            for(j; j<nodesclosed; j++){
                int xx = closednodes[j]->xpos;
                int yy = closednodes[j]->ypos;
                if (xx == node->xpos && yy == node->ypos+1)
                    flag = 1;
            }

            if (flag ==0){
                node->up = generate(node->xpos, node->ypos+1);
                node->up->down = node->up;
                enqueue(node->up);
            }
            else{
                printf("(%d, %d) not generated.\n", node->xpos, node->ypos+1);
            flag = 0;
            }
        }
        if (node->ypos-1 >0 && node->down ==NULL){
        int k = 0;
        int j = 0;
        Qnode* temp2 = front;
            for(k; k<queuesize; k++){
                int xx = temp2->Gnode->xpos;
                int yy = temp2->Gnode->ypos;
                printf("%d, %d,\n", xx, yy);
                if (xx == node->xpos && yy == node->ypos-1)
                    flag = 1;
                temp2 = temp2->next;
                }

            for(j; j<nodesclosed; j++){
                int xx = closednodes[j]->xpos;
                int yy = closednodes[j]->ypos;
                if (xx == node->xpos && yy == node->ypos-1)
                    flag = 1;
            }
            if (flag ==0){
                node->down = generate(node->xpos, node->ypos-1);
                node->down->up = node->down;
                enqueue(node->down);
            }
            else{
            printf("(%d, %d) not generated.\n", node->xpos, node->ypos-1);
            flag = 0;
            }
        }
        printf("EXPANSION ENDS\n");
        return;
    }

}

int main(){
    int x_start, y_start, x_end, y_end;
    FILE *fp;
    fp = fopen("testfile.txt", "r");
    if (fp == NULL)
        printf("Error printing output. \n");
    else
    fscanf(fp, "(%d,%d)\n", &x_start, &y_start);
    fscanf(fp, "(%d,%d)\n", &x_end, &y_end);
    printf("Starting point is (%d, %d)\n", x_start, y_start);
    printf("Ending point is (%d, %d)\n", x_end, y_end);

    Node* start = generate(x_start, y_start);
    enqueue(start);
    while(queuesize!=0){
    expand(front->Gnode, x_end, y_end);
    }

    fclose(fp);
}

使用测试文件.txt

(1,1)
(50,50)

这个输入会导致程序随机崩溃。我怀疑我的队列有问题。

Answer 1

在入队函数中，您应该将新节点分配为 (Qnode*)malloc(sizeof(Qnode)) (而不是 (Qnode*))。您编写的代码仅为每个结构分配指针的大小，因此对此类对象的任何写入都会占用其他对象的内存。