C 语言复习总结记录三
一 函数的定义
维基百科中对函数的定义：子程序
在计算机科学中，子程序（英语：Subroutine, procedure, function, routine, method, subprogram, callable unit），是一个大型程序中的某部分代码， 由一个或多个语句块组成。它负责完成某项特定任务，而且相较于其他代 码，具备相对的独立性。
一般会有输入参数并有返回值，提供对过程的封装和细节的隐藏。这些代码通常被集成为软件库。
//函数的一般形式
ret_type fun_name(para1, * )
{
statement; //语句项
}
ret_type 返回类型
fun_name 函数名
para1 函数参数
statement 函数体
二 库函数
为了支持可移植性和提高程序效率，C 语言基础库中提供了一系列的库函数，方便程序员进行软件开发。
学会查询工具的使用：
MSDN ( Microsoft Developer Network ) 索引 -> 输出查找
www.cplusplus.com 查阅所有库函数的原型和使用方法
http://en.cppreference.com（英文版）前面是 C++，后面是 C
http://zh.cppreference.com（中文版）
C 语言常用的库函数有：
- IO 函数
- 字符串操作函数
- 字符操作函数
- 内存操作函数
- 时间/日期函数
- 数学函数
学习如何通过文档学习库函数，使用库函数，必须包含 #include 对应的头文件
strcpy
char source[] = "Hello World!";
char destination[20];
strcpy(destination, source);
printf("%s\n", destination);
memset
char str[] = "almost every programmer should know memset!";
memset(str, '-', 6);
puts(str);
三 自定义函数
自定义函数和库函数一样，有函数名，返回值类型和函数参数，但由程序员自己设计
编写函数，找出两个整数中的最大值；编写函数，交换两个整形变量的内容
#include<stdio.h>
int max(int x,int y) {
return x > y ? x : y;
}
void swap(int* num1, int* num2) {
int tmp = *num1;
*num1 = *num2;
*num2 = tmp;
*num1 = *num1 ^ *num2; //原理, 两次异或的结果等于原值
*num2 = *num1 ^ *num2;
*num1 = *num1 ^ *num2;
}
int main() {
int num1 = 10, num2 = 5;
printf("%d\n", max(num1, num2));
printf("num1 = %d num2 = %d \n", num1, num2);
swap(&num1, &num2);
printf("num1 = %d num2 = %d \n", num1, num2);
return 0;
}
四 函数的参数
4.1 实际参数（实参）
真实传给函数的参数，叫实参。
实参可以是：常量、变量、表达式、函数等。
无论实参何种类型，在进行函数调用时，它们都必须有确定的值，以便把这些值传送给形参。
4.2 形式参数（形参）
形式参数是指函数名后括号中的变量，因为形式参数只有在函数被调用的过程中才实例化（分配内存单元），所以叫形式参数。形式参数当函数调用完成之后就自动销毁了。因此形式参数只在函数中有效
void swap(int* x, int* y) {
int tmp = *x;
*x = *y;
*y = tmp;
}
int main() {
int num1 = 10, num2 = 5;
swap(&num1, &num2);
}
调试->窗口->监视，打开监视窗口
例，上述代码中的 x，y 是形式参数，而 &num1 和 &num2 是实参
这里可以看到 swap 函数在调用的时候， x ， y 拥有自己的空间，同时拥有了和实参一模一样的内容。可以简单的认为：形参实例化之后其实相当于实参的一份临时拷贝
五 函数调用
5.1 传值调用
函数的形参和实参分别占有不同内存块，对形参的修改不会影响实参
5.2 传址调用
传址调用是把函数外部创建变量的内存地址传递给函数参数的一种调用函数的方式。这种传参方式可以让函数和函数外边的变量建立起真正的联系，也就是函数内部可以直接操作函数外部的变量
函数的嵌套调用：函数和函数之间可以互相调用，但是不能嵌套定义
函数的链式访问：把一个函数的返回值作为另外一个函数的参数
#include <stdio.h>
#include <string.h>
int main()
{
char arr[20] = "Hello";
int ret = strlen(strcat(arr," World"));
printf("%d\n", ret); //11 不包括末尾'\0'
return 0;
}
#include <stdio.h>
int main()
{
//int printf ( const char * format, ... );
//On success, the total number of characters written is returned
printf("%d", printf("%d", printf("%d", 43))); //4321
return 0;
}
5.3 练习
1、编写函数判断一个数是不是素数
未定义标识符 bool, 引入 <stdbool.h> 头文件
/*
素数即质数，指一个大于 1 的自然数，除了 1 和它本身外，不能被其他自然数（质数）整除。通俗来说就是这个数除了 1 和它自身外再也没有其他因数。例如2,3,5,7 等都是素数，它们除了 1 和本身外再无其他因子。2 是最小的质数。
1 既不是质数也不是合数。合数是与质数相对的数，合数是指除了 1 和它本身外还有其他因数的数。例如 2,4,6,8 等皆是合数。
*/
//排除法
bool isPrimeNum(int num) {
if (num <= 1) return false;
else if (num == 2) return true;
//注意平方根的 <= 号
//+= 2 这里是为了排除掉所有 2 的倍数
for (int i = 3; i <= sqrt(num); i += 2)
if (num % i == 0) return false;
return true;
}
//筛选法, 资料参考 https://blog.csdn.net/m0_66769266/article/details/136145809
//找出 1000 以内的所有素数并打印
void isPrimeNum() {
//bool 数组下标代表自然数, 值代表筛选标识
bool arr[MAX_NUM];
memset(arr, 1, MAX_NUM * sizeof(bool));
//将 0 , 1 排除, 该行可省略
arr[0] = false, arr[1] = false;
//遍历数组
for (int i = 2;i < MAX_NUM; ++i) {
//如果该数是素数, 则开始排除所有的倍数
if (arr[i])
{
//i * i, 避免重复的排除动作
// += i, 排除当前 i 的倍数, 减少循环次数
for (int j = i * i; j < MAX_NUM; j += i)
arr[j] = false;
}
}
//遍历数组
for (int i = 2;i < MAX_NUM;++i) {
if (arr[i])
printf("%d\n", i);
}
}
2、编写函数判断一年是不是闰年
// 闰年, 是 4 的倍数但不是 100 的倍数; 是 400 的整数倍
void isLeapYear(int year) {
if (year % 400 == 0 || (year % 4 == 0 && year % 100 != 0))
printf("%d 该年份是闰年 \n", year);
else
printf("%d 该年份不是闰年 \n", year);
}
3、编写函数，实现一个整形有序数组的二分查找
int binarySearch(int* arr, int len, int key) {
int index = -1, left = 0, right = len;
while (left <= right) {
index = (left + right) / 2;
if (key > arr[index])
left = index + 1;
else if (key < arr[index])
right = index - 1;
else
return index;
}
return -1;
}
4、编写函数，每调用一次这个函数，就会将 num 的值增加 1
void addNum(int* x)
{
++*x;
}
int main()
{
int num = 0;
addNum(&num); //调用函数，使得 num 每次增加 1
return 0;
}
6 函数的声明和定义
函数声明：仅提供函数名，参数和返回类型，不提供参数体，一般放在头文件中
函数定义：指函数的具体实现，交待函数的功能实现
#ifndef __TEST_H__
#define __TEST_H__
int Add(int x, int y); //函数声明
#endif //__TEST_H__
#include "test.h"
int Add(int x, int y) //函数实现
{
return x+y;
}
7 函数递归
7.1 递归定义
递归 ：程序调用自身的编程技巧称为递归（recursion）
递归作为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
递归的两个必要条件 ① 存在限制条件，当满足这个限制条件的时候，递归便不再继续 ② 每次递归调用之后越来越接近这个限制条件
递归的主要思考方式在于：把大事化小
7.2 递归练习
接受一个整型值（无符号），按照顺序打印它的每一位
例如：输入：1234，输出 1 2 3 4
void printNum(unsigned int num) {
if (num > 9)
printNum(num / 10);
printf("%u ", num % 10);
}
编写函数不允许创建临时变量，求字符串的长度
int strLen(char* str) {
if (*str == '\0') //因为没办法利用下标, 所以利用解引用 * 取到值
return 0;
else
return 1 + strLen(str + 1); //利用指针偏移 移动
}
7.3 递归与迭代
求 n 的阶乘（不考虑溢出）
int factorial(int n) {
if (n <= 1) return 1;
else return n * factorial(n - 1);
}
求第 n 个斐波那契数（不考虑溢出）
//斐波那契数是一种整数序列，其每个数是前两个数的和
int fabonacciNum(int n) {
if (n <= 2) return 1;
else return fabonacciNum(n - 1) + fabonacciNum(n - 2);
}
在调试 fabonacciNum 时，如果参数比较大，那就会报错： stack overflow（栈溢出）ERROR。因为系统分配给程序的栈空间是有限的，如果出现了死循环，或死递归，这会导致栈空间一直在开辟，最终空间耗尽，该现象称为栈溢出
如何解决递归函数的调用层级很深的问题 ：
1、将递归改写成非递归
2、使用 static 对象替代 nonstatic 局部对象，既减少每次递归调用和返回时产生和释放 nonstatic 对象的开销，而且 static 对象还可以保存递归调用的中间状态，为各个调用层所访问
非递归方式实现
int factorial(int n) {
int res = 1;
for (int i = 1; i <= n; ++i) {
res *= i;
}
/* while (n > 1)
{
result *= n ;
n -= 1;
} */
return res;
}
int fabonacciNum(int n) {
int fib_n = 1, fib_n_minus_one = 1, fib_n_minus_two = 1;
for (int i = 3; i <= n; ++i)
{
fib_n = fib_n_minus_one + fib_n_minus_two;
fib_n_minus_two = fib_n_minus_one;
fib_n_minus_one = fib_n;
}
/*int fib_n = 1, fib_n_minus_one = 1, fib_n_minus_two = 1;
while (n > 2)
{
fib_n = fib_n_minus_one + fib_n_minus_two;
fib_n_minus_two = fib_n_minus_one;
fib_n_minus_one = fib_n;
--n;
}*/
return fib_n;
}
注 ：许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。但这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销
函数递归经典题目 ：
1、汉诺塔问题
/*
一块板上有三根柱子 A、B、C。A 柱上套有 n 个大小不等的圆盘，按照大的在下、小的在上的顺序排列，要把这 n 个圆盘从 A 柱移动到 C 柱上，每次只能移动一个圆盘，移动过程可以借助 B 柱。但在任何时候，任何柱上的圆盘都必须保持大盘在下，小盘在上
从键盘输入需移动的圆盘个数，给出移动的过程
*/
//参考资料 https://blog.csdn.net/lllsure/article/details/135913834
//汉诺塔一样也是找一个 式子，不过这个式子是抽象的，可以理解成一个关键的步骤 ：一共 n 个圆盘，把 (n-1) 个圆盘从 A 移到 B，在把最大的圆盘从 A 移到 C，最后把 B 上的所有圆盘从 B 移到 C 。就是这么一个过程
#include<stdio.h>
//用于打印的函数
void move(char pos1, char pos2) {
printf("%c -> %c", pos1, pos2);
}
void hanoi(int n, char pos1, char pos2, char pos3) {
if (n == 1)
{
move(pos1, pos3);
}
else
{
hanoi(n - 1, pos1, pos3, pos2); //从 A 柱移动到 B 柱
move(pos1, pos3); //打印最大的判断从 A -> C
hanoi(n - 1, pos2, pos1, pos3); //从 B 柱移动到 C 柱
}
}
int main() {
int n;
scanf("%d", &n);
hanoi(n, 'A', 'B', 'C');
}
2、青蛙跳台阶
//青蛙跳台阶，一次一个台阶或者一次跳两个台阶，问跳 n 个台阶有多少次跳法
int jumpStairs(int n) {
/*if (n == 1) return 1;
else if (n == 2) return 2;
else return jumpStairs(n - 1) + jumpStairs(n - 2);*/
int res = 1, res_minus_one = 1,res_minus_two = 1;
while (n >= 2) {
res = res_minus_one + res_minus_two;
res_minus_two = res_minus_one;
res_minus_one = res;
--n;
}
return res;
}
t n;
scanf("%d", &n);
hanoi(n, 'A', 'B', 'C');
}
2、青蛙跳台阶
//青蛙跳台阶，一次一个台阶或者一次跳两个台阶，问跳 n 个台阶有多少次跳法
int jumpStairs(int n) {
/*if (n == 1) return 1;
else if (n == 2) return 2;
else return jumpStairs(n - 1) + jumpStairs(n - 2);*/
int res = 1, res_minus_one = 1,res_minus_two = 1;
while (n >= 2) {
res = res_minus_one + res_minus_two;
res_minus_two = res_minus_one;
res_minus_one = res;
--n;
}
return res;
}
