第14章字符串

第14章

第14章

字符串

基本上求职者进行笔试时没有不考字符串的。字符串也是一种相对简单的数据结构，容易多次引起面试官反复发问。我曾不止一次在面试时被考官要求当场写出strcpy函数的表达方式。事实上，字符串也是一个考验程序员编程规范和编程习惯的重要考点。不要忽视这些细节，因为这些细节会体现你在操作系统、软件工程、边界内存处理等方面的知识掌控能力，也会成为企业是否录用你的参考因素。

14.1　整数字符串转化

面试例题1：怎样将整数转化成字符串数，并且不用函数itoa？

解析：整数转化成字符串，可以采用加'0'，再逆序的办法，整数加'0'就会隐性转化成char类型的数。

答案：程序代码如下：

alt

扩展知识

如果可以使用itoa函数的话，则十分简单，答案如下：

alt

面试例题2：编程实现字符串数转化成整数的办法。［中国某著名IT培训企业公司2005年面试题］

解析：字符串转化成整数，可以采用减'0'再乘10累加的办法，字符串减'0'就会隐性转化成int类型的数。

答案：程序代码如下：

alt

14.2　字符数组和strcpy

面试例题1：Write a function about string copy, the strcpy prototype is "char strcpy(char strDest, const char strSrc);". Here strDest is destination string, strSrc is source string.（已知strcpy函数的原型是char strcpy(char strDest, const char strSrc);，其中strDest是目的字符串，strSrc是源字符串。）

（1）Write the function strcpy, don't call C/C++ string library.（不调用C++/C的字符串库函数，请编写函数strcpy。）

（2）Here strcpy can copy strSrc to strDest, but why we use char as the return value of strcpy?（strcpy能把strSrc的内容复制到strDest，为什么还要char 类型的返回值？）［中国台湾某著名CPU生产公司2005年面试题］

解析：字符串拷贝函数问题。

答案：（1）代码如下：

alt

（2）为了实现链式表达式，返回具体值。

例如：

alt

面试例题2：下面的程序会出现何种问题？［美国某著名计算机软件公司面试题］

alt

解析：以上程序输出结果是123456789,56789。

没经验的程序员一定会在此大跌眼镜的，源字串竟然被截掉了一部分（截掉的长度恰是目标字串原来的长度。至于原因，应该是当初分配的内存地址是连续内存的问题，原来是1234\0123456789\0，strcpy后变成了123456789\06789\0），所以在分配空间的时候要给源字符串和目标字符串留足够的空间。

把目标字串定义在前，源字串定义在后，虽然可以看到正确的输出结果123456789，123456789。但会产生一个运行期错误，原因估计是越过了目标字串的实际空间，访问到了不可预知的地址。

微软在这里是写得非常简单的，代码如下：

alt

微软为什么这么写？它这样安全漏洞太多了，所以必须预先为目标字串分配足够的空间，并且使用这个函数的时候得小心翼翼才行。

为了提高性能，减去那些罗嗦的安全检查是必要的。况且程序员在使用时应该知道哪些条件下会发生访问违例，这种做法就是把责任推给了程序员，让他来决定安全与性能的取舍。

答案：123456789,56789。

拷贝函数的一个完整的标准写法如下：

alt

扩展知识（数组大小分配）

在使用数组的时候，总有一个问题困扰着我们：数组应该有多大？

在很多的情况下，你不能确定要使用多大的数组。你可能并不知道该班级的学生的人数，那么你就要把数组定义得足够大。这样，你的程序在运行时就申请了固定大小的、你认为足够大的内存空间。即使你知道该班级的学生数，但是如果因为某种特殊原因人数有增加或者减少，你又必须重新修改程序，扩大数组的存储范围。这种分配固定大小的内存分配方法称为静态内存分配。但是这种内存分配的方法存在比较严重的缺陷，特别是处理某些问题时，在大多数情况下会浪费大量的内存空间；在少数情况下，当你定义的数组不够大时，还可能引起下标越界错误，甚至导致严重后果。

那么有没有其他的方法来解决这样的问题呢？有，那就是动态内存分配。

所谓动态内存分配就是指在程序执行的过程中动态地分配或者回收存储空间的内存分配方法。动态内存分配不像数组等静态内存分配方法那样需要预先分配存储空间，而是由系统根据程序的需要即时分配，且分配的大小就是程序要求的大小。从以上动、静态内存分配比较可以知道动态内存分配相对于静态内存分配的特点：

●　不需要预先分配存储空间。

●　分配的空间可以根据程序的需要扩大或缩小。

1．如何实现动态内存分配及其管理

要实现根据程序的需要动态分配存储空间，就必须用到以下几个函数。

1）malloc函数

malloc函数的原型为：

alt

其作用是在内存的动态存储区中分配一个长度为size的连续空间。其参数是一个无符号整型数，返回值是一个指向所分配的连续存储域的起始地址的指针。还有一点必须注意的是，若函数未能成功分配存储空间（如内存不足）就会返回一个NULL指针，所以在调用该函数时应该检测返回值是否为NULL并执行相应的操作。

下例是一个动态分配的程序：

alt

上例中动态分配了10个整型存储区域，然后进行赋值并打印。例中if((array(int ) malloc(10sizeof(int)))==NULL)语句可以分为以下几步：

（1）分配10个整型的连续存储空间，并返回一个指向其起始地址的整型指针。

（2）把此整型指针地址赋给array。

（3）检测返回值是否为NULL。

2）free函数

由于内存区域总是有限的，不能无限制地分配下去，而且一个程序要尽量节省资源，所以当所分配的内存区域不用时，就要释放它，以便其他的变量或者程序使用。这时我们就要用到free函数。其函数原型是：

alt

作用是释放指针p所指向的内存区域。

其参数p必须是先前调用malloc函数或calloc函数（另一个动态分配存储区域的函数）时返回的指针。给free函数传递其他的值很可能造成死机或其他灾难性的后果。

注意：这里重要的是指针的值，而不是用来申请动态内存的指针本身。例如：

alt

malloc返回值赋给p1，又把p1的值赋给p2，所以此时p1、p2都可作为free函数的参数。malloc函数对存储区域进行分配。free函数释放已经不用的内存区域。所以有这两个函数就可以实现对内存区域进行动态分配并进行简单的管理了。

面试例题3：编写一个函数，作用是把一个char组成的字符串循环右移n个。比如原来是“abcdefghi”，如果n=2，移位后应该是“hiabcdefgh”。

函数头是这样的：

alt

解析：这个试题主要考查面试者对标准库函数的熟练程度，在需要的时候引用库函数可以很大程度上简少程序编写的工作量。

最频繁被使用的库函数包括Strcpy、memcpy、memset。

答案：

解答1：

alt

解答2：

alt

14.3　数组初始化和数组越界

面试例题1：下面关于数组的初始化正确的是哪项？［中国著名网络企业XL公司面试题］

A．char str［2］={"a","b"};

B．char str［2］［3］={"a","b"};

C．char str［2］［3］={{'a','b'},{'e','d'},{'e','f'}};

D．char str[]={"a","b"};

解析：数组初始化问题。

答案：B

面试例题2：Find the defects in each of the following programs, and explain why it is incorrect.（找出下面程序的错误，并解释它为什么是错的。）［中国台湾某著名杀毒软件公司2005年面试题］

alt

解析：字符数组和strcpy问题。

对于函数test1，这里string数组越界。因为字符串长度为10，还有一个结束符'\0'，所以总共有11个字符长度。string数组大小为10，这里越界了。但是虽然越界但并不报错，整个程序无论编译还是运行都可以正常通过。字符数组并不要求最后一个字符为'\0'。是否需要加入'\0'，完全由系统需要决定。

使用strcpy函数的时候一定要注意前面目的数组的大小必须大于后面字符串的大小，否则便是访问越界。

对于函数test2，这里最大的问题还是str1没有结束符，因为strcpy的第二个参数应该是一个字符串常量。该函数就是利用第二个参数的结束符来判断是否复制完毕，所以在for循环后面应加上str1p［9］='\0'。

字符数组和字符串的最明显的区别就是字符串会被默认地加上结束符'\0'。

对于函数test3，这里的问题仍是越界问题。strlen函数得到字符串除结束符外的长度。如果这里是大于等于10的话，就很明显是越界了。

小结：上面的3个找错的函数，主要是考查对字符串和字符数组概念的掌握，以及对strcpy函数和strlen函数的理解。

字符数组并不要求最后一个字符为'\0'。是否需要加入'\0'，完全由系统需要决定。但是字符数组的初始化要求最后一个字符必须为'\0'，所以test2虽然能够编译通过，但是会出现运行时错误。类似于char c［5］={'C','h','i','n','a'}这样的定义是错误的。

答案：

可以编译通过的程序如下所示：

alt

面试例题3：本段代码有什么问题，如何修改？［中国台湾著名杀毒软件公司Q 2007年9月面试题］

alt

解析：这是char数值问题。char值范围为-128~127，由于char ch;的执行，程序会在栈中开辟一个大小为256的char空间，而第256个char就是我们声明的ch。

当执行ch++，而使ch=128时，这会改变第256个空间的值，也就是ch的值，改变的结果是ch重新变成-128，那么就持续小于255，继续进行循环，从而陷入死循环。

如果把char修改成unsigned char还是会有问题，因为ch <=MAX;这个等号的存在，所以在等于255的时候一样执行循环，然后255加1，一样溢出，ch的值变为0，然后不停地循环。唯一的解决方法是将“<=”变成“<”，循环结束后单独给数组最后一个元素p［255］赋值。

答案：程序陷入死循环。

正确代码如下：

alt

14.4　数字流和数组声明

面试例题1：Which is not the standard I/O channel?（下面哪一个不是标准输入／输出通道？）［中国某著名综合软件公司2005年面试题］

A．std::cin

B．std::cout

C．std::cerr

D．stream

解析：I/O stream问题。头文件iostream中含有cin、cout、cerr几个对象，对应于标准输入流、标准输出流和标准错误流。

答案：D

面试例题2：Which definition is correct?（下面哪个数组的声明是正确的？）［中国台湾某著名杀毒软件公司2005年9月面试题］

A．int a[];

B．int n=10,a［n］;

C．int a［10+1］={0};

D．int a［3］={1,2,3,4};

解析：数组定义问题。

int a[]是错误的，不允许建立空数组。

int n=10,a［n］;是可以的。

int a［10+1］={0};也是允许的。

int a［3］={1,2,3,4};会造成越界问题，因此不允许。

答案：B，C。

14.5　字符串其他问题

面试例题1：求一个字符串中连续出现次数最多的子串，请给出分析和代码。［中国著名IT培训企业2008年3月面试题］

解析：这里首先要搞清楚子串的概念，1个字符当然也算字串，注意看题目，是求连续出现次数最多的子串。如果字符串是abcbcbcabc，这个连续出现次数最多的子串是bc，连续出现次数为3次。如果类似于abcccabc，则连续出现次数最多的子串为c，次数也是3次。这个题目可以首先逐个子串扫描来记录每个子串出现的次数。比如：abc这个字串，对应子串为a/b/c/ab/bc/abc，各出现过一次，然后再逐渐缩小字符子串来得出正确的结果。

答案：完整代码如下：

alt

面试例题2：编程：输入一行字符串，找出其中出现的相同且长度最长的字符串，输出它及其首字符的位置。例如“yyabcdabjcabceg”，输出结果应该为abc和3。［中国著名IT培训企业2008年3月面试题］

解析：可以将字符串yyabcdabjcabceg分解成：

alt

对这几个字符串排序，然后比较相邻字符串的前驱就可以了，很容易求出最长的公共前驱。

答案：完整代码如下：

alt

面试例题3：Please implement the function strstr() (Find a substring, returns a pointer to the first occurrence of strCharSet in string), DO NOT use any C run-time functions. const char strstr(const char string, const char* strCharSet);（请写一个函数来模拟C++中的strstr()函数：该函数的返回值是主串中字符子串的位置以后的所有字符。请不要使用任何C程序已有的函数来完成。）［中国台湾某著名杀毒软件公司2005年面试题］

解析：string字符串问题。做一个程序模拟C++中的strstr()函数。strstr()函数是把主串中子串及以后的字符全部返回。比如主串是“12345678”，子串是“234”，那么函数的返回值就是“2345678”。

答案：正确程序如下：

alt

面试例题4：将一句话里的单词进行倒置，标点符号不倒换。比如一句话“i come from tianjin.”倒换后变成“tianjin. from come i”。

解析：解决该问题可以分为两步：第一步全盘置换将该句变成“.nijnait morf emoc i”，第二步进行部分翻转，如果不是空格，则开始翻转单词。

答案：

具体代码如下：

alt

面试例题5：Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n.For example, f(1)=1，f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n? n≤4000000000.

e.g. f(13)=6 because the number of “1” in 1,2,3,4,5,6,7,8,9,10,11,12,13 is 6. (1, 11, 12, 13)

（现在要我们写一个函数，计算4000000000以内的最大的那个f(n)=n的值，函数f的功能是统计所有0到n之间所有含有数字1的数字和。

比如：f(13)=6

因为“1”在“1,2,3,4,5,6,7,8,9,10,11,12,13”中的总数是6（1，11，12，13））［美国著名搜索引擎公司G 2008年4月面试题］

解析：字符串数字统计问题。

答案：完整代码如下：

alt