我正在尝试编写一个程序来查找节点 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;
}
最佳答案
正如评论中所指出的,您现有的代码存在几个问题。在它真正发挥作用之前,您应该解决这些问题。
此答案仅解决您询问的无限循环...
评论中还指出:
如果语句中有 i 或 j: if(vBelongsToUSubtree(M, &i, &j))printf("yes");
如果控制不当,它们可能永远无法满足 for(int i=1;i<=MAXSIZE;i++)
中的退出条件或 for(int j=i;j<=MAXSIZE;j++)
已关注 i
直到执行流程结束,它(也许j)
)似乎从未改变。
传递的调用链 i
:
if(vBelongsToUSubtree(M, &i, &j))printf("yes");
这又调用:
enqueue(q, *u);
其中有原型(prototype):
void enqueue(Queue *q, int element)
哪里int element
是 i
的值,并且没有改变。 (也不可能使用这个原型(prototype)。)
关于c - BFS 上的无限循环,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57710117/