c - BFS 上的无限循环

问题描述

我正在尝试制作一个程序来查找节点 B 是否属于从节点 A 开始的子树。我用 C 编写代码并自行实现了队列机制，因为我使用 BFS 来遍历树。问题是我的代码进入了一个无限循环，说我的队列已满，甚至没有。

代码：

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


#define MAXSIZE 6
typedef struct Queue
{
    int capacity;
    int size;
    int front;
    int rear;
    int * elements;
}Queue;
Queue * createQueue(int maxElements)
{
    Queue *q;
    if (NULL != (q = (Queue *)malloc(sizeof(Queue))))
    {
        q->elements = (int*)malloc(maxElements * sizeof(int));
        q->size = 0;
        q->capacity = maxElements;
        q->front = 0;
        q->rear = -1;
        return q;
    }
}


void dequeue(Queue *q)
{
    if (0 == q->size)
    {
        printf("Queue is empty\n");
        return;
    }
    else
    {
        q->size--;
        q->front++;
        if (q->front == q->capacity)
        {
            q->front = 0;
        }
    }
}


int front(Queue *q)
{
    if (q->size == 0)
    {
        printf("queue is empty\n");
        exit(0);
    }
    return q->elements[q->front];
}


void enqueue(Queue *q, int element)
{
    if (q->size == q->capacity)
    {
        printf("queue is full \n");
    }

    else
    {
        q->size++;
        q->rear++;
        if (q->rear == q->capacity)
        {
            q->rear = 0;
        }
        q->elements[q->rear] = element;
    }
    return;
}



void readInput(int A[],int B[],int M[][MAXSIZE],int N)
{
    FILE * fp;
    int row, col;
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            M[i][j] = 0;
    if (0 == fopen_s(&fp,"input.txt", "r")) 
    {
        fscanf_s(fp, "%d", &N);
        for (int i = 0; i < N; i++)
            fscanf_s(fp,"%d ", &A[i]);
        for (int i = 0; i < N; i++)
            fscanf_s(fp,"%d ", &B[i]);


        for (int i = 0; i < N; i++)
        {
            fscanf_s(fp, "%d %d", &row,&col);
            M[row][col] = 1;
        }

    }

}

bool vBelongsToUSubtree(int M[][MAXSIZE], int *u, int* v)
{
    bool belongs = false, visited[MAXSIZE];
    for (short i = 0; i < MAXSIZE; i++)visited[i] = false;
    visited[*u] = true;
    Queue *q = createQueue(MAXSIZE);
    enqueue(q, *u);
    printf("%d\n", front(q));
    int node;
    while (0 != q->size)
    {
        node = front(q);
        dequeue(q);
        for (int i = 1; i < MAXSIZE; i++)
        {
            if (1 == M[node][i] and false == visited[i])
            {
                enqueue(q, node);
                visited[node] = true;
                if (node == *v)return true;
            }
            //printf("!\n");
        }
        //printf("%d\n", node);

    }
    /*for (int i = 0; i < q->size; i++)
    {
        printf("%d \n", front(q));
    }

*/
    return belongs;
}

int main()
{
    int A[100], B[100], M[MAXSIZE][MAXSIZE], N=0;
    readInput(A, B, M, N);
    for(int i=1;i<=MAXSIZE;i++)
        for(int j=i;j<=MAXSIZE;j++)
             if(vBelongsToUSubtree(M, &i, &j))printf("yes");
             else printf("not");
    system("pause");

    return 0;
}

标签： cinfinite-loopbreadth-first-search

解决方案

正如评论中所指出的，您现有的代码存在几个问题。在它完全起作用之前，您应该解决它们。

该答案仅解决您询问的无限循环...

评论中还指出：

如果语句中的 i 或 j if(vBelongsToUSubtree(M, &i, &j))printf("yes"); 没有得到适当的控制，它们可能永远不会满足 for(int i=1;i<=MAXSIZE;i++) or中的退出条件 for(int j=i;j<=MAXSIZE;j++)

一直i到它的执行流程结束，它看起来（并且可能j)永远不会改变。

调用链传递i：

if(vBelongsToUSubtree(M, &i, &j))printf("yes");

依次调用：

enqueue(q, *u);

其中有原型：

void enqueue(Queue *q, int element)

int element的值在哪里i，并且没有改变。（也不能使用这个原型。）

c - BFS 上的无限循环

问题描述

解决方案

推荐阅读