专业网站定制平台,人网站设计与制作,怎么打开手机app,网站建设接单/* 理解和记忆递归的关键在于把握递归的本质和函数调用的过程。递归函数在每次调用时会把当前状态压入调用栈#xff0c;直到满足终止条件后开始回溯。理解基准条件和递归步骤#xff1a;每个递归函数都需要有基准条件#xff08;如节点为空时返回#xff09;#xff0c;并…/* 理解和记忆递归的关键在于把握递归的本质和函数调用的过程。递归函数在每次调用时会把当前状态压入调用栈直到满足终止条件后开始回溯。理解基准条件和递归步骤每个递归函数都需要有基准条件如节点为空时返回并在每一步中递归调用自身处理子问题。
*/ main.c
#includestdio.h
#includestdlib.h#define NAMESIZE 32struct score_st
{int id;char name[NAMESIZE];int math;int chinese;
};struct node_st
{struct score_st data;struct node_st *l,*r;
};print_s(struct score_st *d)
{printf(%d %s %d %d\n,d-id,d-d.name,d-math,d-chinese);
}int insert(struct node_st **root,struct score_st *data)
{struct node_st *node;if(*root NULL){node malloc(sizeof(*node));if(node NULL)return -1;node-data *data;node-l NULL;node-r NULL;*root node;return 0;}if(data-id (*root)-data.id)return insert((*root)-l,data);elsereturn insert((*root)-r,data);
}
struct score_st *find(struct node_st *root,int id)
{if(root NULL)return NULL;if(id root-data.id)return root-data;if(id root-data.id)return find(root-l,id);elsereturn find(root-r,id);
}
void draw_(struct node_st *root,in level)
{int i;if(root NULL)return ;draw_(root-t,level1);for(i 0;ilevel;i)printf( );print_s(root-data);draw_(root-l,level1);
}
void draw(struct node_st *root)
{draw_(root,0);
}int main()
{int arr[] {1,2,3,7,6,5,9,8,4};int i;struct score_st tmp,*datap;struct node_st *tree NULL;for(i 0;isizeof(arr)/sizeof(*arr);i){tmp.id arr[i];snprintf(tmp.name,NAMESIZE,stu%d,arr[i]);tmp.math rand()%100;tmp.chinese rand()%100;insert(tree,tmp);}draw(tree);#if 0int tmpid 2;datap find(tree,tmpid);if(datap NULL)printf(can not find the id %d\n,tmpid);elseprint_s(datap);
#endifexit(0);
}
补充说明1
为了理解二级指针的一级目标我们需要明确指针和二级指针的概念。
指针和二级指针
指针一个指针变量保存了另一个变量的地址。通过指针我们可以访问或修改这个变量的值。例如int *p 是一个指向整数的指针变量。二级指针一个二级指针变量保存了另一个指针变量的地址。通过二级指针我们可以访问或修改这个指针变量的值。例如int **pp 是一个指向指针变量的指针。
二级指针的一级目标
一级目标是指二级指针所指向的那个指针变量。
举个具体的例子假设我们有以下定义
int a 10; // 普通变量
int *p a; // 指向变量 a 的指针
int **pp p; // 指向指针 p 的指针在这个例子中
p 是一个指向 a 的指针。pp 是一个指向 p 的指针。
我们可以这样理解
pp 保存了 p 的地址。*pp 解析出 pp 所指向的内容即 p。**pp 解析出 *pp 所指向的内容即 a 的值。 当然可以以下是一个图形示例来说明 *aa b 的含义
假设
aa 是一个指向指针的指针。a 是一个指针它最初指向一个地址。b 是另一个指针指向另一个地址。
初始状态
------ ------ ------
| aa | - | a | - | x | (假设 x 是 a 所指向的值)
------ ------ ------------ ------
| b | - | y | (假设 y 是 b 所指向的值)
------ ------执行 *aa b 后的状态
------ ------
| aa | - | b | - | y | (aa 现在指向 b而 b 仍然指向 y)
------ ------这样做后aa 所指向的指针 a 不再指向原来的地址而是指向了 b 所指向的地址。
以下是更详细的图示
初始状态
aa - a - [地址1: x]
b - [地址2: y]执行 *aa b 后
aa - b - [地址2: y]这意味着aa 原本指向的指针 a现在指向了 b即 a 的地址已经被 b 的地址覆盖。
希望这个图形示例能帮助你更好地理解 *aa b 的含义。如果还有其他问题请随时告诉我
补充说明2
你提到的情况是正确的。A 不出栈的原因是递归调用还没有完成。为了更清楚地解释递归调用的过程让我们重新逐步分析每一个递归调用和返回的过程并使用栈来跟踪函数调用。
示例二叉树
假设有如下二叉树 A/ \B C/ \D E使用栈模拟执行过程
我们以栈的方式逐步模拟 draw 函数调用 draw_ 的过程。 初始状态 栈为空。调用 draw(root)进入 draw_(root, 0)。 处理根节点 A 调用 draw_(A, 0)。栈[ draw_(A, 0) ] 递归处理右子树 C 调用 draw_(C, 1)。栈[ draw_(A, 0), draw_(C, 1) ] 处理 C 节点 右子树为空返回。打印 C缩进 4 空格。左子树为空返回。返回 draw_(A, 0)。栈[ draw_(A, 0) ] 输出 C打印根节点 A 打印 A无缩进。栈[ draw_(A, 0) ] 输出 C
A递归处理左子树 B 调用 draw_(B, 1)。栈[ draw_(A, 0), draw_(B, 1) ] 处理 B 节点 调用 draw_(E, 2)递归处理右子树。栈[ draw_(A, 0), draw_(B, 1), draw_(E, 2) ] 处理 E 节点 右子树为空返回。打印 E缩进 8 空格。左子树为空返回。返回 draw_(B, 1)。栈[ draw_(A, 0), draw_(B, 1) ] 输出 C
AE打印 B 节点 打印 B缩进 4 空格。栈[ draw_(A, 0), draw_(B, 1) ] 输出 C
AEB递归处理左子树 D 调用 draw_(D, 2)。栈[ draw_(A, 0), draw_(B, 1), draw_(D, 2) ] 处理 D 节点 右子树为空返回。打印 D缩进 8 空格。左子树为空返回。返回 draw_(B, 1)。栈[ draw_(A, 0), draw_(B, 1) ] 输出 C
AEBD完成 B 节点的处理 返回 draw_(A, 0)。栈[ draw_(A, 0) ] 完成 A 节点的处理 返回 draw(root)。栈为空。
最终输出 C
AEBD在这个过程中A 不出栈的原因是因为它的递归调用还没有完成。只有当左子树 B 的所有处理完成后A 才会出栈回到 draw(root)表示递归完全结束。这样我们可以准确地跟踪每一步的递归调用和返回理解栈的作用。
希望这个解释能帮助你更好地理解代码的递归逻辑如果还有其他问题请随时告诉我。
