题目描述

请补充递归函数 void itostr(int num,char str[]) 的实现。其功能是将一个整数 num 转换为字符串 str，如整数 135，转换为字符串 “135”，-1 转为字符串 “-1”。

注意：非递归实现不得分。

输入
测试次数；
每组测试数据一行，一个整数。

输出
对每组测试数据，输出转换后的字符串。

输入样例：
4
135
0
-1110
78934012

输出样例：
135
0
-1110
78934012

填空代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <string.h>
#define SIZE 10
// 请补充itostr函数的实现
void itostr(int num, char str[])
/********** Write your code here! **********/

/*******************************************/
int main() {
    int t, num;
    char str[SIZE];

    scanf("%d", &t);
    while(t--) {
        scanf("%d", &num);
        itostr(num, str);
        printf("%s\n", str);
    }
}

题解

题目要求补充递归函数 itostr()，将整数 num 转为字符串 str，首先能想到的是分别取出 num 各位上的数字，再利用 ASCII 码计算转换为对应字符，然后依次填入字符数组 str。需要注意的是字符数组的最后一个元素应该是零终止符 '\0' 。

「递」是将问题拆解成子问题来解决， 子问题再拆解成子子问题，…，直到被拆解的子问题无需再拆分成更细的子问题（即可以求解），「归」是说最小的子问题解决了，那么它的上一层子问题也就解决了，上一层的子问题解决了，上上层子问题自然也就解决了，… ，直到最开始的问题解决。
引文来源：https://zhuanlan.zhihu.com/p/94748605

结合递归思想，假设 num 为 n 位数，如果要把这个问题拆解为子问题，应该能想到的是，假设前 n - 1 位已经填入字符数组，那我们可以很容易的在一次函数调用中填入第 n 位数字。所以原问题 将 n 位数字转为字符串 的子问题可以是 将 n - 1 位数字转为字符串，如此拆分下来，最后的子问题是 将 1 位数字转为字符（串）。这个拆分为最小子问题的过程即为「递」。

如此每一次函数的调用只完成一个数字的转换，从最小子问题开始，完成 num 的第 1 位（最高位）数字转为字符串，即解决了最小子问题，再利用最小子问题的解求解上一层子问题，即完成 num 的第 2 位数字转为字符串，… ，不断利用子问题的解来解决上一层子问题，最后原问题得以求解。这个从最小子问题开始不断向上求解子问题的过程即为「归」。

代码部分关键的一点就是利用 num / 10 实现子问题的拆解，如果 num / 10 == 0，即为不可拆分的子问题（最小子问题），这里也是递归调用的结束条件。又因为字符数组的最后一个元素应该是零终止符 '\0'，我们可以在「递」的过程中完成对字符数组的初始化，将所有元素填入 '\0' 即可。所以总的来说就是：数组在「递」的过程中从后往前依次填入零终止符 '\0' 完成初始化，在「归」的过程中从前往后依次填入各位数字对应的字符。

下面以 -1110 为例展示该递归函数的调用过程 （编不下去了，还是看图好理解一点） 。

最后需要注意的一点是，如果 num 的初始值为 0 ，那么我们用 while() 求得的位数 count 也为 0 ，但是实际上我们需要将这个 ‘0’ 填入字符数组，应当将它视作为一个 1 位数字。所以我们需要对 num 初始值为 0 的情况单独处理，或者将 count 赋值为 1 。这就是为什么要有这样的初始化赋值 count = num == 0 ? 1 : 0; 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void itostr(int num, char str[]) {
    // 考虑负数的情况，需要将 str 首位填入负号
    int flag = 0, sign = 1;
    if (num < 0) {
        str[0] = '-';
        flag = 1;
        sign = -1;
        }
        // 求当前 num 的位数
    int _num = num;
    int count = num == 0 ? 1 : 0;
    while(_num) {
        _num /= 10;
        count++;
    }
    // 在整个递归过程中，从后往前对 str 初始化
    str[count + flag] = '\0';
    if (num / 10)   // 递归结束条件
        itostr(num / 10, str);
    // 在整个递归过程中，从前往后依次将各位数字填入 str
    str[count - 1 + flag] = sign * num % 10 + '0';
}

如果你想对 num 初始值为 0 的情况单独处理，可以参考下面的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void itostr(int num, char str[]) {
    // 注意这里不是递归调用的结束条件
    if (num == 0) {
        str[0] = '0';
        str[1] = '\0';
        return;
    }

    int flag = 0, sign = 1;
    if (num < 0) {
        str[0] = '-';
        flag = 1;
        sign = -1;
    }

    int _num = num, count = 0;
    while(_num) {
        _num /= 10;
        count++;
    }

    str[count + flag] = '\0';
    if (num / 10)
        itostr(num / 10, str);
    str[count - 1 + flag] = sign * num % 10 + '0';
}