c语言使用堆栈实现函数的嵌套调用、递归调用
时间: 2023-12-03 11:43:18 浏览: 57
在 C 语言中,可以使用堆栈(也称为栈)来实现函数的嵌套调用和递归调用。堆栈是一种数据结构,具有先进后出的特性,类似于一叠盘子,后放入的盘子必须先取出来。
在函数调用时,每次调用都会将当前函数的返回地址、参数和局部变量等信息压入堆栈中,然后跳转到被调用函数的入口地址执行。当被调用函数执行完毕后,会从堆栈中弹出之前保存的信息,恢复到调用该函数之前的执行状态,然后继续执行原来的函数。
下面是一个使用堆栈实现函数嵌套调用的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define STACK_SIZE 100
// 定义堆栈结构体
typedef struct {
int top;
int data[STACK_SIZE];
} Stack;
// 初始化堆栈
void initStack(Stack *stack) {
stack->top = -1;
}
// 压入元素
void push(Stack *stack, int value) {
if (stack->top >= STACK_SIZE - 1) {
printf("Stack overflow!\n");
exit(EXIT_FAILURE);
}
stack->data[++stack->top] = value;
}
// 弹出元素
int pop(Stack *stack) {
if (stack->top < 0) {
printf("Stack underflow!\n");
exit(EXIT_FAILURE);
}
return stack->data[stack->top--];
}
// 判断堆栈是否为空
int isEmpty(Stack *stack) {
return stack->top < 0;
}
// 函数嵌套调用
int foo(int x) {
printf("enter foo(%d)\n", x);
int y = x + 1;
int z = bar(y);
printf("exit foo(%d)\n", x);
return z;
}
int bar(int x) {
printf("enter bar(%d)\n", x);
int y = x * 2;
printf("exit bar(%d)\n", x);
return y;
}
int main() {
Stack stack;
initStack(&stack);
push(&stack, 1);
push(&stack, 2);
push(&stack, 3);
while (!isEmpty(&stack)) {
int value = pop(&stack);
printf("%d\n", value);
}
int result = foo(10);
printf("result=%d\n", result);
return 0;
}
```
在上面的示例代码中,我们定义了一个堆栈结构体,包含一个整型数组和一个指向栈顶的指针。然后实现了初始化堆栈、压入元素、弹出元素和判断堆栈是否为空等基本操作。
在 `main` 函数中,我们首先演示了如何使用堆栈来存储一些数据,并依次弹出输出。然后演示了函数嵌套调用的过程,其中函数 `foo` 调用了函数 `bar`。每次调用函数时,我们将当前函数的返回地址和参数压入堆栈中,然后跳转到被调用函数的入口地址执行。当被调用函数执行完毕后,我们从堆栈中弹出之前保存的信息,恢复到调用该函数之前的执行状态,然后继续执行原来的函数。
类似地,我们可以使用堆栈实现递归调用。下面是一个使用堆栈实现阶乘函数的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define STACK_SIZE 100
// 定义堆栈结构体
typedef struct {
int top;
int data[STACK_SIZE];
} Stack;
// 初始化堆栈
void initStack(Stack *stack) {
stack->top = -1;
}
// 压入元素
void push(Stack *stack, int value) {
if (stack->top >= STACK_SIZE - 1) {
printf("Stack overflow!\n");
exit(EXIT_FAILURE);
}
stack->data[++stack->top] = value;
}
// 弹出元素
int pop(Stack *stack) {
if (stack->top < 0) {
printf("Stack underflow!\n");
exit(EXIT_FAILURE);
}
return stack->data[stack->top--];
}
// 判断堆栈是否为空
int isEmpty(Stack *stack) {
return stack->top < 0;
}
// 阶乘函数
int factorial(int n) {
Stack stack;
initStack(&stack);
push(&stack, n);
int result = 1;
while (!isEmpty(&stack)) {
int value = pop(&stack);
if (value <= 1) {
break;
}
result *= value;
push(&stack, value - 1);
}
return result;
}
int main() {
int result = factorial(5);
printf("result=%d\n", result);
return 0;
}
```
在上面的示例代码中,我们定义了一个阶乘函数 `factorial`,使用堆栈实现了递归调用。在递归调用过程中,每次调用函数时,我们将当前函数的返回地址和参数压入堆栈中,然后跳转到被调用函数的入口地址执行。当被调用函数执行完毕后,我们从堆栈中弹出之前保存的信息,恢复到调用该函数之前的执行状态,然后继续执行原来的函数。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)