Быстрый поиск первого слоя начинается

Question

Я пытаюсь реализовать BFS на сетке 400x200, которая вводит текстовый файл с упорядоченной стартовой парой и упорядоченной конечной парой. Я использовал очередь для отслеживания открытых узлов и массива для отслеживания закрытых узлов. Моя программа постоянно рушится на одном и том же входе, проверяя открытые узлы в очереди.

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

использованием testfile.txt

(1,1) 
(50,50) 

этот вход приведет к аварийному завершению программы в случайном порядке. Я подозреваю, что у меня проблема с моей очередью.

Answer 1

В функции enqueue вы должны выделить новые узлы как (Qnode *) malloc (sizeof (Qnode)) (вместо (Qnode *)). Созданный вами код выделяет только размер указателя для каждой структуры, поэтому любая запись на такой объект будет топать в памяти другого объекта.