软件水平考试程序员精选题汇总(下）
软件水平考试程序员精选题汇总(下）把字符串转换成整数题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。例如输入字符串"345"，则输出整数345。分析：这道题尽管不是很难，学过C/C+语言一般都能实现基本功能，但不同程序员就这道题写出的代码有很大区别，可以说这道题能够很好地反应出程序员的思维和编程习惯，因此已经被包括微软在内的多家公司用作面试题。建议读者在往下看之前自己先编写代码，再比较自己写的代码和下面的参考代码有哪些不同。首先我们分析如何完成基本功能，即如何把表示整数的字符串正确地转换成整数。还是以"345"作为例子。当我们扫描到字符串的第一个字符'3'时，我们不知道后面还有多少位，仅仅知道这是第一位，因此此时得到的数字是3。当扫描到第二个数字'4'时，此时我们已经知道前面已经一个3了，再在后面加上一个数字4，那前面的3相当于30，因此得到的数字是3*10+4=34。接着我们又扫描到字符'5'，我们已经知道了'5'的前面已经有了34，由于后面要加上一个5，前面的34就相当于340了，因此得到的数字就是34*10+5=345。分析到这里，我们不能得出一个转换的思路：每扫描到一个字符，我们把在之前得到的数字乘以10再加上当前字符表示的数字。这个思路用循环不难实现。由于整数可能不仅仅之含有数字，还有可能以'+'或者'-'开头，表示整数的正负。因此我们需要把这个字符串的第一个字符做特殊处理。如果第一个字符是'+'号，则不需要做任何操作;如果第一个字符是'-'号，则表明这个整数是个负数，在最后的时候我们要把得到的数值变成负数。接着我们试着处理非法输入。由于输入的是指针，在使用指针之前，我们要做的第一件是判断这个指针是不是为空。如果试着去访问空指针，将不可避免地导致程序崩溃。另外，输入的字符串中可能含有不是数字的字符。每当碰到这些非法的字符，我们就没有必要再继续转换。最后一个需要考虑的问题是溢出问题。由于输入的数字是以字符串的形式输入，因此有可能输入一个很大的数字转换之后会超过能够表示的最大的整数而溢出。现在已经分析的差不多了，开始考虑编写代码。首先我们考虑如何声明这个函数。由于是把字符串转换成整数，很自然我们想到：int StrToInt(const char* str);这样声明看起来没有问题。但当输入的字符串是一个空指针或者含有非法的字符时，应该返回什么值呢?0怎么样?那怎么区分非法输入和字符串本身就是”0”这两种情况呢?接下来我们考虑另外一种思路。我们可以返回一个布尔值来指示输入是否有效，而把转换后的整数放到参数列表中以引用或者指针的形式传入。于是我们就可以声明如下：bool StrToInt(const char *str, int& num);这种思路解决了前面的问题。但是这个函数的用户使用这个函数的时候会觉得不是很方便，因为他不能直接把得到的整数赋值给其他整形变脸，显得不够直观。前面的第一种声明就很直观。如何在保证直观的前提下当碰到非法输入的时候通知用户呢?一种解决方案就是定义一个全局变量，每当碰到非法输入的时候，就标记该全局变量。用户在调用这个函数之后，就可以检验该全局变量来判断转换是不是成功。下面我们写出完整的实现代码。参考代码：enum Status kValid = 0, kInvalid;int g_nStatus = kValid;/ Convert a string into an integer/int StrToInt(const char* str)g_nStatus = kInvalid;longlongnum = 0;if(str != NULL)const char* digit = str;/ the first char in the string maybe '+' or '-'bool minus = false;if(*digit = '+')digit +;else if(*digit = '-')digit +;minus = true;/ the remaining chars in the stringwhile(*digit != '0')if(*digit >= '0' && *digit <= '9')num = num * 10 + (*digit - '0');/ overflowif(num>std:numeric_limits:max()num = 0;break;digit+;/ if the char is not a digit, invalid inputelsenum = 0;break;if(*digit = '0')g_nStatus = kValid;if(minus)num = 0 - num;return static_cast(num);讨论：在参考代码中，我选用的是第一种声明方式。不过在面试时，我们可以选用任意一种声明方式进行实现。但当面试官问我们选择的理由时，我们要对两者的优缺点进行评价。第一种声明方式对用户而言非常直观，但使用了全局变量，不够优雅;而第二种思路是用返回值来表明输入是否合法，在很多API中都用这种方法，但该方法声明的函数使用起来不够直观。最后值得一提的是，在C语言提供的库函数中，函数atoi能够把字符串转换整数。它的声明是int atoi(const char *str)。该函数就是用一个全局变量来标志输入是否合法的。用两个栈实现队列题目：某队列的声明如下：template class CQueuepublic:CQueue() CQueue() void appendTail(const T& node); / append a element to tailvoid deleteHead(); / remove a element from headprivate:T>m_stack1;T>m_stack2;分析：从上面的类的声明中，我们发现在队列中有两个栈。因此这道题实质上是要求我们用两个栈来实现一个队列。相信大家对栈和队列的基本性质都非常了解了：栈是一种后入先出的数据容器，因此对队列进行的插入和删除操作都是在栈顶上进行;队列是一种先入先出的数据容器，我们总是把新元素插入到队列的尾部，而从队列的头部删除元素。我们通过一个具体的例子来分析往该队列插入和删除元素的过程。首先插入一个元素a，不妨把先它插入到m_stack1。这个时候m_stack1中的元素有a，m_stack2为空。再插入两个元素b和c，还是插入到m_stack1中，此时m_stack1中的元素有a,b,c，m_stack2中仍然是空的。这个时候我们试着从队列中删除一个元素。按照队列先入先出的规则，由于a比b、c先插入到队列中，这次被删除的元素应该是a。元素a存储在m_stack1中，但并不在栈顶上，因此不能直接进行删除。注意到m_stack2我们还一直没有使用过，现在是让m_stack2起作用的时候了。如果我们把m_stack1中的元素逐个pop出来并push进入m_stack2，元素在m_stack2中的顺序正好和原来在m_stack1中的顺序相反。因此经过两次pop和push之后，m_stack1为空，而m_stack2中的元素是c,b,a。这个时候就可以pop出m_stack2的栈顶a了。pop之后的m_stack1为空，而m_stack2的元素为c,b，其中b在栈顶。这个时候如果我们还想继续删除应该怎么办呢?在剩下的两个元素中b和c，b比c先进入队列，因此b应该先删除。而此时b恰好又在栈顶上，因此可以直接pop出去。这次pop之后，m_stack1中仍然为空，而m_stack2为c。从上面的分析我们可以总结出删除一个元素的步骤：当m_stack2中不为空时，在m_stack2中的栈顶元素是最先进入队列的元素，可以pop出去。如果m_stack2为空时，我们把m_stack1中的元素逐个pop出来并push进入m_stack2。由于先进入队列的元素被压到m_stack1的底端，经过pop和push之后就处于m_stack2的顶端了，又可以直接pop出去。接下来我们再插入一个元素d。我们是不是还可以把它push进m_stack1?这样会不会有问题呢?我们说不会有问题。因为在删除元素的时候，如果m_stack2中不为空，处于m_stack2中的栈顶元素是最先进入队列的，可以直接pop;如果m_stack2为空，我们把m_stack1中的元素pop出来并push进入m_stack2。由于m_stack2中元素的顺序和m_stack1相反，最先进入队列的元素还是处于m_stack2的栈顶，仍然可以直接pop。不会出现任何矛盾。我们用一个表来总结一下前面的例子执行的步骤：操作m_stack1m_stack2append aaappend ba,bappend ca,b,cdelete headb,cdelete headcappend ddcdelete headd总结完push和pop对应的过程之后，我们可以开始动手写代码了。参考代码如下：/ Append a element at the tail of the queue/template void CQueue:appendTail(const T& element)/ push the new element into m_stack1m_stack1.push(element);/ Delete the head from the queue/template void CQueue:deleteHead()/ if m_stack2is empty,and t
