01.思维导图
02.地址传递和值传递
#include <stdio.h>
void swap(int **p1,int **p2)
{
int *temp;
temp = *p1;
*p1 = *p2;
*p2 = temp;
}
void swap2(int *p1,int *p2)
{
int temp;
temp = *p1;
*p1 = *p2;
*p2 = temp;
}
int main(int argc, const char *argv[])
{
int a = 90,b=7;
int *p1 = &a,*p2=&b;
swap(&p1,&p2);
swap2(p1,p2);
printf("a=%d b=%d",a,b);
return 0;
}
输出结果：a=7,b=90
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int swap(int **p1,int **p2)
{
// 将 p1 指向的变量的值加 1
(**p1)++;
// 将 p1 指向的变量的值赋给 p2 指向的变量
**p2 = **p1;
// 将 p2 指向的变量的值加上 p1 指向的变量的值
**p2 = **p2 + **p1;
return **p2;
}
int main(int argc, const char *argv[])
{
int a=90,b=7;
int *p1=&a,*p2=&b;
printf("%d\n",swap(&p1,&p2));
printf("a=%d\tb=%d\n",a,b);
return 0;
}
03.栈和递归的联系
利用今天实现的栈，完成输出一个数的二进制。可以利用条件判断，完成指定进制的输出
main.c
#include "binary.h"
int main()
{
int number=255;
int bases[]={2,8,16};
int num_bases=sizeof(bases)/sizeof(bases[0]);
for(int i=0;i<num_bases;i++)
{
printf("%d 的 %d进制是:",number,bases[i]);
converToBinary(number,bases[i]);
}
return 0;
}
binary.c
#include "binary.h"
//1.创建栈
stack_p createstack(int capacity)
{
stack_p S=(stack_p)malloc(sizeof(stack));
S->items=(int*)malloc(capacity*sizeof(int));
S->top=-1;
S->capacity=capacity;
return S;
}
//2.判空
int empty_stack(stack_p S)
{
if(S==NULL){
printf("入参为空.\n");
return -1;
}
return S->top==-1?1:0;
}
//3.入栈操作
void push(stack_p S,int item)
{
if(S==NULL){
printf("入参为空.\n");
return;
}
S->items[++S->top]=item;
}
//4.出栈操作
int pop(stack_p S)
{
if(S==NULL){
printf("入参为空.\n");
return -1;
}
if(empty_stack(S)){
printf("空栈无法输出.\n");
return -2;
}
return S->items[S->top--];
}
void converToBinary(int num,int base)
{
if(num==0){
printf("0\n");
return;
}
//假设最大32位整数
stack_p S=createstack(32);
char digits[]="0123456789ABCDEF";
while(num>0){
int remainder=num%base;
push(S,remainder);
num/=base;
}
while(!empty_stack(S)){
int digit=pop(S);
printf("%c",digits[digit]);
}
printf("\n");
free(S->items);
free(S);
}
binary.h
#ifndef __BINARY_H__
#define __BINARY_H__
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct stack
{
int *items;
int top;
int capacity;
}stack,*stack_p;
stack_p createstack(int capacity);
int empty_stack(stack_p S);
void push(stack_p S,int item);
int pop(stack_p S);
void converToBinary(int num,int base);
#endif
2. 栈模拟递归计算阶乘
#include <stdio.h>
#include <stdlib.h>
// 定义栈结构
typedef struct Stack {
int *items;
int top;
int capacity;
} Stack;
// 创建栈
Stack* createStack(int capacity) {
Stack* stack = (Stack*)malloc(sizeof(Stack));
stack->items = (int*)malloc(capacity * sizeof(int));
stack->top = -1;
stack->capacity = capacity;
return stack;
}
// 判断栈是否为空
int isEmpty(Stack* stack) {
return stack->top == -1;
}
// 入栈操作
void push(Stack* stack, int item) {
stack->items[++stack->top] = item;
}
// 出栈操作
int pop(Stack* stack) {
if (isEmpty(stack)) {
return -1;
}
return stack->items[stack->top--];
}
// 释放栈内存
void freeStack(Stack* stack) {
free(stack->items);
free(stack);
}
// 使用栈模拟递归计算阶乘
int factorial_stack(int n) {
Stack* stack = createStack(n);
int result = 1;
// 将参数依次压入栈
while (n > 0) {
push(stack, n);
n--;
}
// 从栈中弹出元素并计算阶乘
while (!isEmpty(stack)) {
result *= pop(stack);
}
freeStack(stack);
return result;
}
// 递归计算阶乘
int factorial_recursive(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return n * factorial_recursive(n - 1);
}
}
int main() {
int num = 5;
printf("使用栈计算 %d 的阶乘: %d\n", num, factorial_stack(num));
printf("使用递归计算 %d 的阶乘: %d\n", num, factorial_recursive(num));
return 0;
}3.递归调用过程中系统栈的使用：斐波那契数列
#include <stdio.h>
#include <stdlib.h>
// 定义栈结构
typedef struct Stack {
int *items;
int top;
int capacity;
} Stack;
// 创建栈
Stack* createStack(int capacity) {
Stack* stack = (Stack*)malloc(sizeof(Stack));
stack->items = (int*)malloc(capacity * sizeof(int));
stack->top = -1;
stack->capacity = capacity;
return stack;
}
// 判断栈是否为空
int isEmpty(Stack* stack) {
return stack->top == -1;
}
// 入栈操作
void push(Stack* stack, int item) {
stack->items[++stack->top] = item;
}
// 出栈操作
int pop(Stack* stack) {
if (isEmpty(stack)) {
return -1;
}
return stack->items[stack->top--];
}
// 释放栈内存
void freeStack(Stack* stack) {
free(stack->items);
free(stack);
}
// 使用栈计算斐波那契数列的第 n 项
int fibonacciStack(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
Stack* stack = createStack(n);
// 先将 n 压入栈
push(stack, n);
int result = 0;
while (!isEmpty(stack)) {
int current = pop(stack);
if (current == 0) {
result += 0;
} else if (current == 1) {
result += 1;
} else {
// 模拟递归调用，先压入较小的参数
push(stack, current - 1);
push(stack, current - 2);
}
}
freeStack(stack);
return result;
}
int main() {
int n = 6;
printf("斐波那契数列的第 %d 项是: %d\n", n, fibonacciStack(n));
return 0;
}课堂重点
