一、递归
递归 --- 1. 是一种特殊的循环
2. 如果不加结束条件,最终也会结束 ----函数调用-- 栈空间耗尽
用累加求和举例1+2+3+ ...+100
递归解决问题的思路:
1.要解决问题n,
要看问题n-1的解决
2.当一个函数需要被自身重复调用时---可以考虑递归
1.递归实现编程: 两个要素
要素1：递推关系：问题n 和 问题n-1之间关系
sum(100) = sum(99) + 100
|--- sum(98) + 99
sum(n) = sum(n-1) + n
要素 2：递归结束条件
n = 1
递归结束
2.递归程序的代码逻辑
int sum(int n) //sum(n) { //判断是否到达递归结束条件 //是 --- 则返回 //否 --- 继续往下递归 (自己调用自己) if(n == 1) { return 1; }else //递归结束调剂不满足 { return sum(n-1) + n; } }//递归的限制
1.层次不能太深 //栈空间不够
2.有些问题的解决 --- 确实需要通过递归实现
汉诺塔就是经典的递归问题：
汉诺塔思路:
1、将n-1个盘子从A->B
2、将剩下的那个盘子从A->C
3、将n-1个盘子从B->C
代码：
#include <stdio.h> void move(int n ,int pole1,int pole2) { static int step = 1; printf("%03d:[disk %d] : %c --> %c\n",step++,n,pole1,pole2); } //起始柱 辅助柱 目标柱 void hanoi(int n, int A, int B, int C) { if (1==n) { move(n,A,C); }else { hanoi(n-1,A,C,B);//n-1 先挪走 puts("-------"); move(n,A,C); // 将第n个 挪到 目标柱 puts("-------"); hanoi(n-1,B,A,C); } } //n = 3; //hanoi(2,'A','C','B') // | --------------------> hanoi(1,'A','B','C') // move(2,'A','B'); [2:A->B] // |----------------------->move(1,'A','C') [1:A->C] // move(3,'A','C'); -----> [3:A->C] // hanoi(2,'B','A','C'); int main(void) { int n = 0; printf("Input numbers of disk: "); scanf("%d",&n); hanoi(n,'A','B','C'); return 0; }递归计算斐波那契数列的第 n 项：
// 递归计算斐波那契数列的第 n 项 int fib(int n) { if (n == 0) return 0; if (n == 1) return 1; return fib(n - 1) + fib(n - 2); }递归求n！（n的阶乘）：
// 递归求 n 的阶乘 // 定义：0! = 1, n! = n * (n-1)! int factorial(int n) { if (n == 0 || n == 1) return 1; return n * factorial(n - 1); }二、一维数组在函数中作为参数
//1.数组元素作为函数参数 void printArrayEle(int ele) { } //2.数组做函数参数 main() { int a[10] = {1,2,3,4,5}; } printArray() { }//传递整个数组的数据 给 函数使用
1.如果要传 整个数组数据 给 函数
本质上传的不是整个数组
传的是 首元素地址
2.为什么函数中 只是接收了首元素地址,却可以访问到数组所有元素
原因:
数组特点
a.连续性
b.单一性
c.有序性
3. 整个数组做函数参数
本质上 ,只需要把首元素地址传过去 即可
函数的形参 形式上可以写成数组
printArray(int a[]); //形式上
printArray(int *a); //本质上 是 一个指针变量 (后面指针部分会再说)
所以,函数内部 通过sizeof(a) 算出来的是 指针大小,而不是数组大小
练习:
实现一个函数,从数组中找出最大值实现一个函数,实现数组逆序
实现一个函数，实现数组排序
实现一个函数，实现数组查找
#include <stdio.h> void printArray(int *a,int len) { int i =0; for( i=0;i<len;i++) { printf("%d ",a[i]); } putchar('\n'); } int printArrayMax(int *a,int len) { int i; int max = 0; for (i=0;i<len;i++) { if(a[i]>max) { max = a[i]; } } return max; } void reverseArray(int *a,int len) { int n,i; for(i=0;i<len/2;i++) { n = a[i]; a[i] = a[len-1-i]; a[len-1-i] = n; } printArray(a,len); } void inputArray(int *a,int len) { int i =0; for(i=0;i<len;i++) { scanf("%d",&a[i]); } } void xuanPai(int *a,int len) { int i,j,num; for(i=0;i<len-1;i++) { for(j=i+1;j<len;j++) { if(a[i]>a[j]) { num = a[i]; a[i] = a[j]; a[j] = num; } } } printf("选择排序："); printArray(a,len); } void maoPai(int *a,int len) { int i,j,num; for(i=0;i<len-1;i++) { for(j=0;j<len-1-i;j++) { if(a[j+1]<a[j]) { num = a[j]; a[j] = a[j+1]; a[j+1] = num; } } } printf("冒泡排序："); printArray(a,len); } void chaPai(int *a,int len) { int i,j,num; for(i=0;i<len;i++) { j=i; while(j>0 && a[i]<a[j-1]) { a[j] = a[j-1]; j--; } a[j] = a[i]; } printf("插入排序："); printArray(a,len); } void erCha(int *a,int len) { int begin,end,mid,i; int k; printf("请输入要查找的值："); scanf("%d",&k); begin = 0; end = len-1; i=0; while(begin <=end) { mid = (begin+end)/2; if(k<a[mid]) { end = mid-1; }else if(k>a[mid]) { begin = mid+1; }else break; } if(begin<=end) { printf("found,a[%d]\n",a[mid]); }else { printf("not found\n"); } } int main(void) { int a[10]; int len = sizeof(a)/sizeof(a[0]); inputArray(a,len); //printArray(a,10); printf("max = %d\n",printArrayMax(a,len)); reverseArray(a,len); xuanPai(a,len); // maoPai(a,len); // chaPai(a,len); erCha(a,len); return 0; }注意：一维字符型数组做函数参数的话
一维字符型数组 --- 用来存放字符串
1.形参 只需要 数组形式,不需要数组长度 //原因,因为字符串有自己结束标志
2.实参 只需要 传数组名即可
自己尝试实现头文件中string.h的函数把
三、二维数组作为函数的参数
二维数组:
整型二维数组
做函数参数
printArray(int a[][4],int row); //形式上
printArray(int (*a)[4],int row); //本质上 a起始还是指针变量
下面用二维数组作为函数的参数实现输入输出排序查找比大小等函数：
#include <stdio.h> #include <string.h> void putStr(char (*s)[10],int row) { int i =0; for (i = 0;i<row;i++) { puts(s[i]); } } void getStr(char (*s)[10],int row) { int i; for (i = 0; i<row;i++) { scanf("%s",s[i]); } } void Maxstr(char (*s)[10],int row) { int i; int m =0; char max[10]; strcpy(max,s[0]); for(i=0;i<row;i++) { if(strcmp(s[i],max)>0) { strcpy(max,s[i]); } } printf("max = %s\n",max); } void xuanPai(char (*s)[10],int row) { int i,j; char max[10]; for(i=0;i<row -1;++i) { for(j=i+1;j<row;j++) { if(strcmp(s[j],s[i]) < 0) { strcpy(max,s[i]); strcpy(s[i],s[j]); strcpy(s[j],max); } } } putStr(s,row); } void maoPai(char (*s)[10],int row) { int i,j; char max[10]; for(i=0;i<row-1;++i) { for(j=0;j<row-1-i;j++) { if(strcmp(s[j],s[j+1]) >0) { strcpy(max,s[j]); strcpy(s[j],s[j]+1); strcpy(s[j+1],max); } } } putStr(s,row); } void chaPai(char (*s)[10],int row) { //插入排序 int i,j; for(i=1;i<row;i++) { j=i; char k[10];//这里的k不能替换成str[i] strcpy(k,s[i]); while(j>0 && (strcmp(k,s[j-1]) < 0) ) { strcpy(s[j],s[j-1]); j--; } strcpy(s[j],k); } putStr(s,row); } void chazhao(char (*s)[10],int row) { //二分查找 int begin= 0; int end = row; int mid; char n[10]; printf("请输入要查找的字符串："); scanf("%s",n); int i =0; while(begin<=end) { mid = (begin+end)/2; if(strcmp(s[mid],n)>0) { end = mid -1; }else if(strcmp(s[mid],n)<0) { begin = mid +1; }else break; } if(begin<=end) { printf("found\n"); }else { printf("not found\n"); } } int main(void) { char s[3][10]; int row = 3; getStr(s,row); // putStr(s,row); Maxstr(s,row); printf("选择排序:\n"); xuanPai(s,row); printf("冒泡排序:\n"); maoPai(s,row); printf("插入排序\n"); chaPai(s,row); chazhao(s,row); return 0; }四、标识符
标识符
名字
变量名
函数名
作用域
指的是标识符起效的范围
//局部作用域
{}
//全局作用域
不在任何一个{}范围内
可见性
站在程序角度看,执行到某句代码时,哪些标识符可见
例如：
int a=10; main() { int a=20; printf("a = %d\n",a); } printf("a = %d\n",a); 输出a=20 a=10标识符的可见性的规则:
1.先定义，后使用
2.同一作用域中，不能有同名标识符
3.在不同的作用域，同名标识符，相互之间没有影响
4.如果是不同的作用域，但是作用域之间存在嵌套关系，
则，
内层的作用域的同名标识符，会屏蔽外层的作用域的同名标识符。
(就近原则)
1.变量：
变量:
局部变量
放在 {} 范围内的 就是局部变量
全局变量
不在任何一个{} 范围内的,就是全局变量
变量的生命周期：
(无到有再到无)
局部变量
生命周期
当程序运行到对应的定义数据时,才创建
当程序运行到标识符,所在作用域结束时,销毁
全局变量
生命周期
从程序运行开始,就存在
到程序运行结束,销毁
存储类别的关键字
auto --- 数据存储在 栈上 ---自动申请 自动释放
static --- 静态 表示数据存储在 静态区
静态区变量初始化, 不能用变量初始化,只能用常量初始化
static 修饰的局部变量,值具有继承性,只需要初始化一次
register
extern//五个区
栈
堆
静态区/全局区
字符串常量区
antu：
int main() { auto int a; //局部变量 --- 一般空间开在栈上，不写的话默认前面补auto }static：
void func1(void) { static int a = 10; a++; printf("a = %d(n”,a); } int main(void) { int i= 0; for (i = 0; i < 10;++i) func1(); } 输出结果 11 12 13 14 15 16 17 18 19/////可以看出用了static后，a值在过了它的作用域后没有销毁五、小结
今天的学习，哈诺塔这个代码还没有完全搞懂。
知识点总结：
//总结: 1.函数 递归 //1.递归过程 //2.递归思想 //3.递归函数的实现 // a.递推关系 // b.结束条件 //4.递归的优缺点 // 2.数组 做函数参数 形参 实参 整型 一维数组 数组形式+长度 数组名+长度 字符型 一维数组 数组形式 数组名 整型 二维数组 数组形式+行数 数组名+行数 字符型 二维数组 数组形式+行数 数组名+行数 ---------------------- //介绍新的语法 + 用新语法实现旧功能 3.函数 标识符 作用域 和 可见性 //空间 局部作用域 ---- 局部变量 全局作用域 ---- 全局变量 //时间 生命周期 static 变量 static 的局部变量 1.只能用常量初始化 2.值只需要初始化一次 3.值具有继承性
