c - 在c中递归搜索链表

Question

我是数据结构的新手。我编写了一个相当简单的程序来搜索链接列表中的整数。函数应该返回指向相关位置的指针，但是在 main() 中调用时它返回 null(或者可能只是垃圾)。 (插入 printf 消息用于诊断。)

链接列表:

struct list
{
        int data;
        struct list * link;
};

搜索功能:

struct list * search_list(struct list * head_ptr, int x)
{
        printf("\nfunc search head addr : 0X%x ",head_ptr);
        if(head_ptr==NULL)
        {
                printf("Null found.\n");
                return NULL;
        }

        else if (head_ptr->data == x)
        {
                printf("element found returing : 0X%x ",head_ptr);
                return head_ptr;
        }
        else
        {
                printf("not found , next");
                search_list(head_ptr->link,x);
        }

}

在 main () 中调用:

tmp_list_ptr = list_head_ptr;
tmp_list_ptr = search_list(list_head_ptr,15);
if(tmp_list_ptr == NULL)
        printf("main : Not found : 0X%x\n",tmp_list_ptr);
else
        printf("main : found at : 0X%x\n",tmp_list_ptr);

返回0；

程序输出:

[0X1dd33250 : 19,]
[0X1dd33230 : 18,]
[0X1dd33210 : 17,]
[0X1dd331f0 : 16,]
[0X1dd331d0 : 15,]
[0X1dd331b0 : 14,]
[0X1dd33190 : 13,]
[0X1dd33170 : 12,]
[0X1dd33150 : 11,]
[0X1dd33130 : 1,]
[0X1dd33110 : 2,]
[0X1dd330f0 : 3,]
[0X1dd330d0 : 4,]
[0X1dd330b0 : 5,]
[0X1dd33090 : 6,]
[0X1dd33070 : 7,]
[0X1dd33050 : 8,]
[0X1dd33030 : 9,]
[0X1dd33010 : 10,]
Searching for 15. 
func search head addr : 0X1dd33250 not found , next
func search head addr : 0X1dd33230 not found , next
func search head addr : 0X1dd33210 not found , next
func search head addr : 0X1dd331f0 not found , next
func search head addr : 0X1dd331d0 element found returing : 0X1dd331d0 main : Not found : 0X0

为什么它返回 NULL 到 main ？ 请问你能帮帮我吗？ 注意:示例取自:算法设计手册，Steven S. Skiena，第 2 版 http://i.stack.imgur.com/uhEZC.png

Answer 1

search_list() 的递归调用实际上应该返回 结果。相反，您的函数递归调用 search_list()，然后隐式丢弃其返回值。

这应该会生成一个编译器警告，例如“控件到达非空函数的末尾。”

根据您计算机的架构，您最终可能会得到垃圾结果。这就是我们所说的“未定义行为”!例如，在 32 位 Intel 处理器上，函数的返回值存储在 eax 寄存器中。根据编译器如何决定您的程序将使用处理器的寄存器，您的函数可能返回了一些其他计算的结果。