C_函数

C_函数

函数是 C 语言的基本构建组件 (building blocks)，可以把一个大程序划分为小的组件，从而降低程序的复杂度。使用函数还可以避免编写重复的代码，从而提高程序的可维护性。

函数的定义

在C语言中，函数的定义：

  1. 返回类型：可以是基本数据类型，也可以是结构体、指针等复合数据类型。不能返回数组，除此之外，函数可以返回任意类型的值。如返回值类型为 void，则函数没有返回值。
  2. 函数名称：用于在程序中调用该函数。
  3. 参数列表：可以是零个或多个，需要在每个形式参数前面指定它的类型，并且参数之间用逗号分隔。如果函数没有形式参数，应该标明为 void。
  4. 函数体：包含声明和语句。在函数体内声明的变量只属于此函数，其它函数不能访问和修改这些变量。
1
2
3
4
5
return-type function-name (parameters) 
{
 declarations
 statements
}

函数调用

函数调用由函数名和实际参数 (argument) 列表组成。如：average(x, y)。

非 void 函数调用会产生一个值，该值可以存储在变量中，用于测试、显示，或者是用于其它用途：

1
2
3
4
avg = average(x, y);
if (average(x, y) > 0)
	printf("Average is positive\n");
printf("The average is %lf\n", average(x, y));

如果不需要函数的返回值，则可以丢弃；返回值类型为 void 的函数没有返回值，且必须紧跟分号;

函数声明

如果把函数定义放在函数调用之后:

1
2
3
4
5
6
7
8
9
10
#include<stdio.h>
int main(void) 
{
    double x, y;
    scanf("%lf%lf", &x, &y);
    printf("Average of %lf and %lf: %lf\n", x, y, average(x, y)); 
    return 0;
}
double average(double a, double b) 
{return (a + b) / 2; }

当编译器在 main 函数中遇到 average 函数调用时，没有 average 函数的信息。此时编译器会为 average 函数创建一个隐式声明：编译器会假定函数的返回值类型为 int。但不知道 average 的形参个数以及形参类型，编译器只能进行根据实际参数的类型和个数进行推断。当编译器后面遇到average 函数的定义时，发现函数的返回值类型是 double 而不是 int，从而会给出一条错误信息。

在调用之前声明函数。函数声明(function declaration) 使得编译器能够知道函数的概要信息。

1
return-type function-name ( parameters );

函数的声明必须和函数的定义一致。

函数声明中可以省略形参的名字，只要给定形参的类型即可。如：

1
double average(double, double);

实际参数

形式参数出现在函数定义中，表示在函数调用时应该提供哪些值；而实际参数出现在函数调用中。

实参是值传递 (passed by value) 的。调用函数时，计算每个实参的值并赋值给相应的形参。在函数调用过程中，对形参的改变不会影响到实参的值，形参中保留的是实参的副本。

  • 形参的改变不会影响到实参，可以把形参当作变量来使用，减少所需变量的数量。

    1
    2
    3
    4
    5
    6
    7
    int power(int x, int n) 
    {
     int i, result = 1;
     for (i = 1; i <= n; i++)
         result = result * x;
     return result; 
    }

  • n 只是原始指数的副本，可以在函数体内修改它的值，不需要变量 i 了。

1
2
3
4
5
6
7
int power(int x, int n) 
{
 int result = 1;
 while (n-- > 0)
     result = result * x;
 return result; 
}

  • 变量 a 和变量 b 的值是不会发生修改的。

    1
    2
    3
    4
    5
    6
    void swap(int a, int b)
    {
     int temp = a;
     a = b;
     b = temp; 
    }

数组作为参数

当形式参数为一维数组时，可以不指定数组的长度：

1
2
3
int f(int a[]) {
 ...
}

数组作为参数传递时，会退化成指向数组第一个元素的指针。

实参可以是元素类型匹配的任意一维数组。C 语言没有提供任何简便的方法供函数确定数组的长度。可以额外提供一个长度参数。

虽然可以使用 sizeof 运算符计算数组的长度，但在这种情况下不适用。

下面的函数说明了数组参数的常用用法：

1
2
3
4
5
6
7
int sum_array(int a[], int n) 
{
 int i, sum = 0;
 for (i = 0; i < n; i++)
     sum += a[i];
 return sum;
}

函数调用时，第一个参数是数组名，第二个参数是数组的长度。

1
2
3
4
5
6
7
8
#define LEN 100
int main(void) 
{
 int b[LEN], total;
 ...
 total = sum_array(b, LEN);
 ...
}

函数是无法确认数组的实际长度的。可以传入一个比实际长度小的值：

1
total = sum_array(b, 50);	//这就只会对数组的前 50 个元素求和。

注意：不能传入一个比数组长度更大的值，这会导致数组索引越界，从而发生未定义的行为。

关于数组参数另一个值得注意的点是：函数通过传入的数组，可以改变数组的元素。

1
2
3
4
5
6
void clear(int a[], int n) 
{
 int i;
 for (i = 0; i < n; i++)
     a[i] = 0; 
}

数组的前 n个元素将会清零，因为数组作为参数传递时，会退化成指向数组第一个元素的指针。

注意!!!：形式参数是多维数组时，声明参数时只能省略第一个维度的长度。可以不指定行的数量，但是必须指定列的数量：

1
2
3
4
5
6
7
8
9
#define LEN 10                              
int sum_array(int a[][LEN], int n)
{        
 int i, j, sum = 0;
 for (i = 0; i < n; i++)
     for (j = 0; j < LEN; j++)
         sum += a[i][j];
 return sum; 
}

  1. 省略第一个维度时，表示函数可以接受任意行数的数组。如arr[][4]，可以接受 int[2][4] 、 int[5][4] 。

  2. 不省略第一个维度，表示函数明确指定了数组的行数，只能接受特定大小的数组。如 arr[3][4] ，必须接受一个 3×4 的二维数组。

局部变量全局变量

在函数体内声明的变量称为该函数的局部变量。

1
2
3
4
5
6
7
8
9
10
int sum_digits(int n) 
{
    int sum = 0;       /*local variable*/
    while (n > 0) 
    {
        sum += n % 10;
        n /= 10;
   }
    return sum; 
}

默认情况下，局部变量具有下列性质：

  1. 作用域（Scope）： 局部变量只在声明它们的函数或代码块内部可见和可用。超出范围，其它函数或代码块无法直接访问这些局部变量。块作用域通常与花括号 {} 内部的代码块相对应。
  2. 生存期（Lifetime）： 局部变量的生命周期仅限于声明它们的函数或代码块的执行过程中。一旦函数或代码块执行结束，这些局部变量就会被销毁，释放其所占用的内存空间。
  3. 不被默认初始化： 局部变量不会被默认初始化，它们的值是不确定的，除非显式地赋予初始值。在使用局部变量之前，必须先对其进行初始化操作，否则会导致未定义行为。
  4. 隐藏性（Shadowing）： 当在内部作用域中声明一个与外部作用域同名的局部变量时，内部作用域的变量会隐藏外部作用域的同名变量。意味着在内部作用域中使用该变量时，实际上使用的是内部作用域的变量，而不是外部作用域的。
  5. 栈上分配： 大多数编程语言中，局部变量通常在栈上分配内存。意味着内存分配和释放是自动进行的，无需程序员手动管理。

静态局部变量

在局部变量声明中使用 static 关键字，可以使局部变量具有静态存储期限。

静态局部变量具有以下特点：

  1. 具有静态存储期，生命周期与程序运行期间相同。
  2. 仅在第一次进入函数时被初始化，之后的调用不会重新初始化。
  3. 作用域仅限于声明它的函数内部，但在函数调用之间保持其值不变。
1
2
3
4
5
void foo(void) 
{
    static int i = 0;
    printf("%p: %d\n", &i, i++);
}

静态局部变量始终具有块作用域，它对其它函数是不可见的。

静态局部变量可以保存上一次函数调用时的状态，在某些应用中非常有用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 0, 1, 1, 2, 3, 5, 8, 13, 21...
long long next_fib(void) 
{
    static long long a = 0;	//仅在第一次进入函数时被初始化，之后的调用不会重新初始化。
    static long long b = 1;
    long long tmp = a;
    a = b;
    b = a + tmp;
    return a; 
}
int main(void) 
{
    printf("%lld\n", next_fib()); // 1
    printf("%lld\n", next_fib()); // 1
    printf("%lld\n", next_fib()); // 2
    printf("%lld\n", next_fib()); // 3
    return 0; 
}

全局变量

全局变量就是声明在任何函数体外的变量，全局变量的性质不同于局部变量：

  • 静态存储期限。具有静态存储期限的变量拥有永久的存储单元，所以在整个程序执行期间都会保留变量的值。
  • 文件作用域。从变量声明开始，一直到文件的末尾。在全局变量声明之后的函数都可以访问(并修改)它。

在多个函数必须共享一个变量时，全局变量是很有用的。但是函数之间通过形式参数进行通信会比共享外部变量更好。使用全局变量不利于程序的排错和维护。

return语句

非 void 函数必须使用 return 语句来指定函数要返回的值。

1
return expr;

如果 return 语句中表达式的类型和函数的返回值类型不匹配，系统将会把表达式的类型隐式转换为返回值类型。

void 函数也可以使用 return 语句，使函数立刻返回，只是 return 后面不能接表达式。

1
2
3
4
5
6
void print_positive(int n) 
{
 if (n <= 0)
     return ;
 printf("%d", i);
}

程序终止

main 函数的返回值类型为 int，表示程序返回时的状态码。如果程序正常终止，main 函数应该返回 0；如果程序异常终止，应该返回非 0 的值。

exit函数

exit函数包含在 <stdlib.h> 头文件中。传递给exit函数的参数和 main函数的返回值具有相同的含义：两种都表示程序终止时的状态。

正常结束时：

1
exit(0);

C 语言允许使用 EXIT_SUCCESS 来替代：

1
exit(EXIT_SUCCESS);

如果异常退出：

1
exit(EXIT_FAILURE);

EXIT_SUCCESS和EXIT_FAILURE都是定义在 <stdlib.h> 中的宏，值是由实现决定的，通常分别为 0 和 1。

return语句和exit函数之间的差异是：不管哪个函数调用exit函数都会导致程序终止，return语句仅当在main函数中执行时才会导致程序的终止。

Tips: 一些程序员仅使用 exit 函数终止程序，好处是方便以后定位程序的全部退出点。

递归

一个函数调用它本身，那么这个函数就是递归的。

递归使用

  1. 问题具有递归结构：
    • 大问题可以分解成若干个子问题，子问题的求解方式和大问题一致，只是问题规模不一致。
    • 子问题的解可以合并成大问题的解。
  2. 如果不存在重复计算问题，且递归的层次不是很深时，就可以使用递归。
  3. 写递归：边界条件、递归公式

动态规划

动态规划是一种自底向上的方法，通过存储已解决的子问题的解来避免重复计算。

基本思想：

  • 最优子结构： 原问题的最优解可以通过其子问题的最优解来构建。
  • 重叠子问题： 在解决问题的过程中，需要解决相同的子问题多次。

动态规划的解决步骤：

  1. 定义子问题： 确定问题的最优子结构，以及问题可以被分解成的子问题。
  2. 建立状态转移方程： 找到子问题之间的关系，建立递推式或状态转移方程。
  3. 确定边界条件： 确定递归或迭代过程中的边界条件，即最小的子问题的解。
  4. 自底向上求解： 使用迭代或递归方法自底向上求解问题，确保每个子问题的解只计算一次，并且以正确的顺序计算。

动态规划的特性：

  • 记忆化搜索： 使用数组或哈希表等数据结构来存储已解决的子问题的解，以避免重复计算。
  • 状态压缩： 在某些情况下，可以通过仅保留必要的状态信息来减少存储空间。

使用场景：

  1. 优化问题： 动态规划通常用于解决优化问题，例如找到最大值、最小值或最优解。
  2. 最短路径问题： 诸如最短路径或最短编辑距离之类的问题通常可以使用动态规划来解决。
  3. 组合优化问题： 动态规划可用于解决组合优化问题，如子集求和、子序列最大值等。
  4. 资源分配问题： 例如背包问题是动态规划经常用于解决的资源分配问题的一个示例。
  5. 排列组合问题： 当需要考虑元素之间的排列和组合时，动态规划可能是一个合适的选择。
  6. 树或图问题： 某些树形和图形问题可以使用动态规划来解决，例如最长递增子序列等。

使用条件：

  1. 重叠子问题： 原问题可以被分解成若干个规模较小的子问题，并且这些子问题之间存在重叠，即相同的子问题可能被多次求解。
  2. 最优子结构： 问题的最优解可以通过子问题的最优解来求解。换句话说，问题的最优解可以通过子问题的最优解进行组合而得到。
  3. 状态转移方程： 存在一个状态转移方程，用于描述如何从一个阶段的状态转移到下一个阶段的状态。这是动态规划问题的核心。
  4. 问题可分解： 原始问题可以被分解成几个子问题，这些子问题相对较小，可以被有效地求解。
  5. 问题具有确定性： 问题的状态和转移是可确定的，不存在随机因素或不确定性。

注意事项：

  • 状态定义： 状态的定义对问题的解决方案至关重要，需要仔细考虑问题的本质。
  • 状态转移方程： 建立正确的状态转移方程是解决动态规划问题的关键，需要深入理解问题的结构和特性。

Fibonacci数列

具体函数：F(n)=F(n-2)+F(n-1)，F(1)=1，F(0)=0

利用公式求解：

1
2
3
4
5
// 0, 1, 1, 2
long long fib(int n) {
    if (n == 0 || n == 1) return n;
    return fib(n-2) + fib(n-1);
}

这种求解方式的效率很低，会存在大量重复的计算。

动态规划：并不需要保存前面所有项的值，只需要保存最近两项即可。

1
2
3
4
5
6
7
8
9
10
long long fib(int n) {
    if (n == 0 || n == 1) return n;
    long long a = 0, b = 1;
    for (int i = 2; i <= n; i++) {// 计算fib(i)的值
        long long tmp = a + b;
        a = b;
        b = tmp;
	}
    return b;
}