百度网页版官方/优化推广公司哪家好

本系列为《编程之法：面试和算法心得》的读书笔记。

算法1.3：字符串转换成整数

• 题目描述

  输入一个由数字组成的字符串，把它转换成整数并输出。例如:输入字符串“123”，输出整数为123。给定函数原型 int StrToInt(const char *str)，实现字符串转换成整数的功能，不能使用库函数atoi。

• 分析与解法

思路分析：当扫描字符串的第一个字符“1“时，由于是第一位，故得到数字1；继续向后扫描到第二个字符”2“，之前已经得到数字1，在其后添加一个数字2，得到数字12，相当于前面的数字扩大了10倍然后加上刚扫描到的数字2，即：1×10+2=12。同理，扫描到第三个字符”3“，即可得到最终整数123为所求。故而，其基本思路就是：从左至右扫描字符串，把之前得到的数字乘以10，再加上当前字符表示的数字。 但是，在处理过程中，需要考虑以下问题：

1）空指针的输入：输入的是指针，在访问空指针时程序会崩溃，需要提前判空；
2）正负符号：整数不仅包括数字，还有可能包括以“+”或“-”开头表示正负整数，遇到负号“-”需要做转换；
3）非法字符：输入的字符串中可能有不是数字的字符（如误操作其他字符），需要预先判断，碰到非法字符程序应停止转换；
4）整型溢出：输入的数字是以字符串的形式输入，若输入一个很长的字符串可能导致溢出。

// 算法1.3：字符串转成整数
int StrToInt(const char* str)
{static const int MAX_INT = (int)((unsigned)~0 >> 1);static const int MIN_INT = -(int)((unsigned)~0 >> 1);unsigned int n = 0;// 判空if(str == 0){return 0;}// 处理空格while(isspace(*str)){++str;}// 处理正负int sign = 1;if(*str == '+' || *str == '-'){if(*str == '-'){sign = -1;}str++;}while(isdigit(*str)){int c = *str - '0';if(sign > 0 && (n > MAX_INT/10 || (n == MAX_INT/10 && c > MAX_INT%10))){n = MAX_INT;break;}else if(sign < 0 && (n > (unsigned)MIN_INT/10 || (n == (unsigned)MIN_INT/10 && c > (unsigned)MIN_INT%10))){n = MIN_INT;break;}n = n *10 + c;str++;}return sign > 0 ? n:-n;
}

算法分析：此算法难点在于处理数据溢出，其时间复杂度为 $O(n)$。

• 练习题

实现 string 到 double 的转换。