C语言算法-解答字符串转换整数（atoi）算法问题的C语言实现

题目

实现一个函数 int myAtoi(char* str)，将字符串转换为整数。

引言

字符串转换整数（atoi）是一个常见的字符串处理问题。给定一个字符串，我们需要将其转换为对应的整数。解决这个问题需要处理字符串中的各种情况，并注意溢出的情况。

算法思路

我们将使用一种逐字符处理的方法来解决字符串转换整数（atoi）问题。

算法的步骤如下：

1. 跳过字符串开头的空格字符。
2. 判断第一个非空格字符的符号，如果是 '+' 或 '-'，则记录符号，并将指针后移一位。

3. 遍历字符串中的字符：

   • 如果当前字符不是数字字符，则跳出循环。
   • 将当前字符转换为数字，并判断是否溢出。
   • 计算转换后的整数。
4. 根据符号和溢出情况，返回最终的整数值。

代码实现

下面是使用C语言实现的代码：

#include <stdio.h>
#include <ctype.h>
#include <limits.h>

int myAtoi(char* str) {
    int sign = 1;
    long result = 0;
    int i = 0;

    // 跳过开头的空格字符
    while (str[i] == ' ')
        i++;

    // 判断符号
    if (str[i] == '+' || str[i] == '-') {
        sign = (str[i] == '-') ? -1 : 1;
        i++;
    }

    // 转换数字字符为整数
    while (isdigit(str[i])) {
        result = result * 10 + (str[i] - '0');

        // 溢出判断
        if (result * sign > INT_MAX)
            return INT_MAX;
        if (result * sign < INT_MIN)
            return INT_MIN;

        i++;
    }

    return (int)(result * sign);
}

int main() {
    char input[] = "   -42";
    int result = myAtoi(input);

    printf("Input: %s\n", input);
    printf("Converted Integer: %d\n", result);

    return 0;
}

算法分析

该算法的时间复杂度为 O(n)，其中 n 是字符串的长度。在循环中，我们每次处理一个字符，因此循环的次数取决于字符串的长度。

空间复杂度为 O(1)。

示例和测试

示例输入1:

Input: "42"

示例输出1:

Converted Integer: 42

示例输入2:

Input: "   -42"

示例输出2:

Converted Integer: -42

示例输入3:

Input: "4193 with words"

示例输出3:

Converted Integer: 4193

示例输入4:

Input: "words and 987"

示例输出4:

Converted Integer: 0

示例输入5:

Input: "-91283472332"

示例输出5:

Converted Integer: -2147483648

总结

本文使用C语言实现了解答字符串转换整数（atoi）算法问题的代码。通过逐字符处理字符串，并进行符号判断和溢出检查，我们能够将字符串转换为对应的整数。该算法的时间复杂度为 O(n)，空间复杂度为 O(1)。