为什么我在 C 程序中找到无限循环来搜索链表？该程序有效

Question

这是我在链表中搜索元素的程序。有人告诉我我的代码中有一个无限循环。我不知道在哪里。该程序对我有用，并且不会一直循环播放。我真的想不通。如果有人对我应该查看代码的哪一部分来解决问题有任何建议或想法，请告诉我。我真的被难住了。

struct node
{
int a;
struct node *next;
};

void generate(struct node **head, int num)
{
int i;
struct node *temp;
for (i = 0; i < num; i++)
{
temp = (struct node *)malloc(sizeof(struct node));
temp->a = rand() % num;
if (*head == NULL)
{
*head = temp;
temp->next = NULL;
}
else
{
temp->next = *head;
*head = temp;
}
printf("%d    ", temp->a);
}
}
void search(struct node *head, int key, int index)
{
while (head != NULL)
{
if (head->a == key)
{
printf("Key found at Position: %dn", index);
}
search(head->next, key, index - 1);
}
}
void delete(struct node **head)
{
struct node *temp;
while (*head != NULL)
{
temp = *head;
*head = (*head)->next;
free(temp);
}
}
int main()
{
struct node *head = NULL;
int key, num;
printf("Enter the number of nodes: ");
scanf("%d", &num);
generate(&head, num);
printf("nEnter key to search: ");
scanf("%d", &key);
search(head, key, num);
delete(&head);
}

Answer 1

看看你的search函数：

void search(struct node *head, int key, int index)
{
while (head != NULL)
{
if (head->a == key)
{
printf("Key found at Position: %dn", index);
}
search(head->next, key, index - 1);
}
}

现在，暂时忽略while循环中发生的两个"操作"，只考虑是什么阻止了循环执行。假设(在第一次调用函数时(，head的值不NULL，循环何时停止？当然，当head变得NULL时 - 但你永远不会改变该循环中head的值！对search的递归调用不会在当前正在运行的函数中更改它！所以这是一个无限循环。

您需要做的是将head->next分配给循环内的head，如下所示：

void search(struct node *head, int key, int index)
{
while (head != NULL)
{
if (head->a == key)
{
printf("Key found at Position: %dn", index);
}
head = head->next; // If list is properly formed, this will get to NULL
search(head, key, index - 1); // Now we don't need to use the ->next here
}
}

此外，如果你只想找到键的第一个出现，你可以在printf后面添加一个return语句;就目前而言，你将打印所有匹配项 - 但这可能是你想要的。

Answer 2

正如另一个答案中提到的，问题是因为你循环head不是空指针，但你永远不会修改head所以它永远不会成为空指针。

但是search函数还有另一个问题：你需要决定是要使用循环还是使用递归来迭代列表。您不应同时使用两者。

要么使用循环

while (head != NULL)
{
if (head->a == key)
{
printf("Key found at Position: %dn", index--);
}
head = head->next;
}

或使用递归

if (head != NULL)
{
if (head->a == key)
{
printf("Key found at Position: %dn", index);
}
search(head->next, key, index - 1);
}

我猜你真的想做最后一种选择，但错误地使用了while而不是if.