递归搜索链表

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%xn",tmp_list_ptr);
else
        printf("main : found at : 0X%xn",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，第二版https://i.stack.imgur.com/uhEZC.png

Answer 1

对search_list()的递归调用实际上应该是return的结果。相反，你的函数正在递归地调用search_list()，然后隐式地丢弃它的返回值。

这应该会生成一个编译器警告，比如"控制到达非空函数的末端"。

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