由于字符串非常灵活，因此面试中非常注重字符串操作的考察。本节列出了一些经常出现的字符串考题，例如有关字符串长度检测，查找子串，单向翻转，判断是否回文等的题目。
面试例题11：编程实现字符串的长度检测。
考点：strcpy库函数的实现细节。
出现频率：★★★★★
解析
这个题目非常简单，字符串是以'\0'作为结束符，所以只需要做一次遍历就可以了。但是需要注意的是要尽量把程序写得简单高效。看下面的示例代码：
1 #include
2 #include
3
4 int strlen1(const char* src)
5 {
6 assert( NULL != src); //src必须有效
7 int len = 0; //保存src的长度
8 while(*src++ != '\0') //遇到结束符'\0'退出循环
9 len++; //每循环一次len加1
10 return len;
11 }
12
13 int strlen2(const char* src)
14 {
15 assert( NULL != src); //src必须有效
16 const char *temp = src; //保存src首地址
17 while(*src++ != '\0'); //遇到结束符'\0'退出循环
18 return (src-temp-1); //返回尾部指针与头部指针之差即长度
19 }
20
21 int main()
22 {
23 char p[] = "Hello World!";
24 printf("strlen1 len: %d\n", strlen1(p)); //打印方法1得到的结果
25 printf("strlen2 len: %d\n", strlen2(p)); //打印方法2得到的结果
26
27 return 0;
28 }
|
strlen1和strlen2这两个函数用来计算字符串长度。它们的区别如下所示。
strlen1用局部变量len在遍历的时候做自增，然后返回len。因此每当while循环一次，就需要执行两次自增操作。
strlen2用局部变量temp记录src遍历前的位置。while循环一次只需要一次自增操作，最后返回指针之间的位置差。
当字符串较长的时候strlen2比strlen1的效率更高。下面是程序的输出结果：
strlen1 len: 12
strlen2 len: 12
|
面试例题12：编程实现字符串中子串的查找。
考点：strstr库函数的实现细节。
出现频率：★★★★★
编写实现strstr即一个函数，即从一个字符串中，查找另一个字符串的位置，如strstr("12345", "34")返回值为2，即在2号位置找到字符串34。
解析
程序如下所示：
1 #include
2 #include
3
4 const char *strstr(const char* src, const char* sub)
5 {
6 const char *bp;
7 const char *sp;
8
9 if (src == NULL || NULL == sub) //判断src与sub的有效性
10 {
11 return src;
12 }
13 while (*src) //遍历src字符串
14 {
15 bp = src; //用于src的遍历
16 sp = sub; //用于sub的遍历
17 do
18 { //遍历sub字符串
19 if (!*sp) //如果到了sub字符串结束符位置
20 return src; //表示找到了sub字符串，退出
21 } while (*bp++ == *sp++);
22 src += 1;
23 }
24
25 return NULL;
26 }
27 int main()
28 {
29 char p[] = "12345";
30 char q[] = "34";
31
32 char *r = strstr(p, q);
33 printf("r: %s\n", r);
34
35 return 0;
36 } |
main函数中的测试结果为：
代码第32行调用strstr结束之后，r指向了数组p的第3个元素。这里strstr函数的方法是循环取src的子串与sub比较。以本题中的"12345"和"34"为例，比较步骤如下所示。
"12345"和"34"比较，不满足匹配。
"2345"和"34"比较，不满足匹配。
"345"和"34"比较，满足匹配。
6.2.3 其他编程问题（2）
面试例题13：编程实现字符串中各单词的翻转。
考点：字符串相关的综合编程能力。
出现频率：★★★
编写函数，将"I am from Shanghai"倒置为"Shanghai from am I"，即将句子中的单词位置倒置，而不改变单词内部的结构。
解析
第1种方法代码如下：
1 #include
2 using namespace std;
3
4 void RevStr(char *src)
5 {
6 char *start = src, *end = src, *ptr = src;
7
8 while(*ptr++ != '\0') //遍历字符串
9 {
10 if(*ptr == ' ' || *ptr == '\0') //找到一个单词
11 {
12 end = ptr - 1; //end指向单词末尾
13 while(start < end)
14 swap(*start++, *end--); //把单词的字母逆置
15
16 start = end = ptr+1; //指向下一个单词开头
17 }
18 }
19 start = src, end = ptr-2; //start指向
字符串开头，end指向字符串末尾
20 while(start < end)
21 {
22 swap(*start++, *end--); //把整个字符串逆置
23 }
24 }
25
26 int main()
27 {
28 char src[] = "I am from Shanghai";
29 cout << src << "\n";
30 RevStr(src);
31 cout << src << "\n";
32
33 return 0;
34 } |
程序输出结果：
1 I am from Shanghai
2 Shanghai From am I |
RevStr函数有两个转换步骤：代码第8～18行将src中所有的单词进行翻转，其结果是src的内容变为"I ma morf iahgnahS"，然后代码第20～23行再进行全局翻转。
第2种方法代码如下：
1 #include
2 using namespace std;
3
4 void RevStr(char *src)
5 {
6 char *start = src, *end = src, *ptr = src;
7
8 while(*ptr++ != '\0');
9 end = ptr-2; //找到字符串末尾
10 while(start < end)
11 {
12 swap(*start++, *end--); //逆置整个字符串
13 }
14
15 start = src, end = ptr-2;
16 ptr = start;
17 while(*ptr++ != '\0')
18 {
19 if(*ptr == ' ' || *ptr == '\0') //找到单词
20 {
21 end = ptr - 1; //end指向单词末尾
22 while(start < end)
23 swap(*start++, *end--); //逆置单词
24
25 start = end = ptr+1; //指向下一个单词开头
26 }
27 }
28 }
29
30 int main()
31 {
32 char src[] = "I am from Shanghai";
33 cout << src << "\n";
34 RevStr(src);
35 cout << src << "\n";
36
37 return 0;
38 } |
程序输出结果：
I am from Shan ghai
Shanghai from am I |
RevStr函数转换步骤与第1种方法相反，即代码第10～11行将src进行全局翻转， src的内容变为"iahgnahS morf ma I"，然后代码第17～第27行再把所有的单词进行翻转。
从上面的代码分析可以看出，两种方法都是采用了两个步骤，即字符串全局翻转和各个单词局部翻转，只是步骤的顺序不同，但是得到的结果都是一致的。
6.2.3 其他编程问题（3）
面试例题14：编程判断字符串是否为回文。
考点：字符串相关的综合编程能力。
出现频率：★★★★
判断一个字符串是不是回文。
解析
根据题目要求，我们可以从一个字符串的两端进行遍历比较。例如对于"level"字符串，我们可以进行如下操作。
计算需要比较的次数。由于"level"字符串长度为5，是奇数，因此比较2次。
第1次比较：看"level"的第1个字符与最后1个字符是否相等，如果相等进行第2次比较。
第2次比较：看"level"的第2个字符与倒数第2个字符是否相等，如果相等则是回文。
只要在上面的比较过程中有一个不相等，则字符串不是回文。根据以上思路，程序代码如下所示：
1 #include
2 using namespace std;
3
4 int IsRevStr(char *str)
5 {
6 int i, len;
7 int found = 1; //1表示是回文字符串，0表示不是
8
9 if(str == NULL) //判断str的有效性
10 {
11 return -1;
12 }
13 len = strlen(str); //获得字符串长度
14 for(i=0; i15 {
16 if(*(str+i) != *(str+len-i-1)) //遍历中如果发现相应头尾字符不等
17 { //则字符串不是回文
18 found=0;
19 break;
20 }
21 }
22 return found;
23 }
24
25 int main()
26 {
27 char str1[10] = "1234321"; //回文字符串
28 char str2[10] = "1234221"; //非回文字符串
29
30 int test1 = IsRevStr(str1); //测试str1是不是回文
31 int test2 = IsRevStr(str2); //测试str2是不是回文
32
33 cout << "str1 is " << (test1 == 1 ? "": "not ")
34 << "reverse string." << endl;
35 cout << "str2 is " << (test2 == 1 ? "": "not ")
36 << "reverse string." << endl;
37
38 return 0;
39 } |
这个程序中的IsRevStr()函数用于判断字符串是否是回文字符串，如果是则返回1，否则返回0。输出结果：
str1 is reverse string.
str2 is not reverse string. |
面试例题15：编程实现stcmp库函数。
考点：库函数strcmp的实现细节。
出现频率：★★★★★
解析
此题实际上就是实现C/C++库函数中的strcmp函数。对于两个字符串str1和str2，若相等则返回0，若str1大于str2则返回1，若str1小于str2返回 1。
程序代码如下所示：
1 #include
2 using namespace std;
3
4 int mystrcmp(const char *src, const char *dst)
5 {
6 int ret = 0 ;
7 while( !(ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst)
8 { //循环比较两个字符是否相等
9 ++src; //如果不等或者到了dst字符串末尾
10 ++dst; //退出循环
11 }
12 if ( ret < 0 ) //ret保存着字符比较的结果
13 ret = -1 ;
14 else if ( ret > 0 )
15 ret = 1 ;
16 return( ret );
17 }
18
19 int main()
20 {
21 char str[10] = "1234567";
22 char str1[10] = "1234567"; //str1 == str
23 char str2[10] = "12345678"; //str2 > str
24 char str3[10] = "1234566"; //str3 < str
25
26 int test1 = mystrcmp(str, str1); //测试str与str1比较
27 int test2 = mystrcmp(str, str2); //测试str与str2比较
28 int test3 = mystrcmp(str, str3); //测试str与str3比较
29
30 cout << "test1 = " << test1 << endl;
31 cout << "test2 = " << test2 << endl;
32 cout << "test3 = " << test3 << endl;
33
34 return 0;
35 } |
mystrcmp()函数对src和dst两个字符串同时进行遍历，当发现它们存在不同值时停止循环，并根据它们的最后一个字符的大小，返回相应的结果。程序输出结果：
test1 = 0
test2 = -1
test3 = 1 |
6.2.3 其他编程问题（4）
面试例题16：编程查找两个字符串的最大公共子串。
考点：字符串相关的综合编程能力。
出现频率：★★★
解析
对于两个字符串A和B，如果A="aocdfe",B="pmcdfa",则输出"cdf"。
1 #include
2 #include
3 #include
4
5 char *commonstring(char *str1, char *str2)
6 {
7 int i, j;
8 char *shortstr, *longstr;
9 char *substr;
10
11 if (NULL == str1 || NULL == str2) //判断str1与str2的有效性
12 {
13 return NULL;
14 }
15
16 if (strlen(str1) <= strlen(str2)) //shortstr和
longstr分别指向较短和较长的字符串
17 {
18 shortstr = str1;
19 longstr = str2;
20 } else
21 {
22 shortstr = str2;
23 longstr = str1;
24 }
25
26 if(strstr(longstr, shortstr) != NULL) //如果在
长的字符串中能寻找短的字符串
27 { //返回短字符串
28 return shortstr;
29 }
30
31 substr = (char *)malloc(sizeof(char) *
(strlen(shortstr) + 1)); //申请堆内存存放返回结果
32
33 for(i=strlen(shortstr)-1; i>0; i--)
34 {
35 for(j=0; j<=strlen(shortstr)-i; j++)
36 {
37 memcpy(substr, &shortstr[j], i); //将短字
符串的一部分复制到substr，
38 substr[i] = '\0'; //其长
度逐渐减小
39 if(strstr(longstr, substr) != NULL) //如果
在longstr中能找到substr则返回substr
40 return substr;
41 }
42 }
43
44 return NULL;
45 }
46
47 int main()
48 {
49 char *str1 = (char *)malloc(256); //分配堆内
存存放字符串str1和str2
50 char *str2 = (char *)malloc(256);
51 char *common=NULL;
52
53 gets(str1); //从终端输入str1和str2
54 gets(str2);
55
56 common = commonstring(str2, str1); //取最大的相同子串
57
58 printf("the longest common string is: %s\n", common);
59
60 return 0;
61 } |
为了方便，可以利用库函数strstr寻找一个字符串中的子串。这个程序的步骤如下。
代码第11～第14行，检查参数str1和str2的有效性。
计算两个字符串的长短。
调用strstr直接进行两个字符串的整串比较，如果不为NULL，说明短串被长串所包含，直接返回短串即可，否则进行下一步。
申请一块大小为短串长度加1的堆内存，这块内存用于保存最大公共子串。
循环取短串的子串放入堆内存，调用strstr函数检查长串中是否包含这个子串，如果包含则返回堆内存。值得注意的是，短串的长度是不断减小的。
下面是程序执行结果：
aocdfe（输入）
pmcdfa（输入）
the longest common string is: cdf |
6.2.3 其他编程问题（5）
面试例题17：不能使用printf，将十进制数以二进制和十六进制的形式输出。
考点：用字符串表示十进制数。
出现频率：★★★
解析
不能使用printf系列库函数，可以通过位运算得到十进制数的二进制形式和十六进制形式的字符串，再将字符串打印。程序代码如下所示：
1 #include
2 #include
3 #include
4
5 char *get2String(long num) //得到二进制形式的字符串
6 {
7 int i=0;
8 char* buffer;
9 char* temp;
10
11 buffer = (char*)malloc(33);
12 temp = buffer; //temp
13 for (i=0; i < 32; i++)
14 { //给数组的32个元素赋0或1
15 temp[i] = num & (1 << (31 - i));
16 temp[i] = temp[i] >> (31 - i);
17 temp[i] = (temp[i] == 0) ? '0': '1';
18 }
19 buffer[32] = '\0'; //字符串结束符
20
21 return buffer;
22 }
23
24 char *get16String(long num) //得到十六进制形式的字符串
25 {
26 int i=0;
27 char* buffer = (char*)malloc(11);
28 char* temp;
29
30 buffer[0] = '0'; //"0x"开头
31 buffer[1] = 'x';
32 buffer[10] = '\0'; //字符串结束符
33 temp = buffer + 2;
34
35 for (i=0; i < 8; i++)
36 { //给数组的8个元素赋值
37 temp[i] = (char)(num<<4 * i>>28);
38 temp[i] = temp[i] >= 0 ? temp[i] : temp[i] + 16;
39 temp[i] = temp[i] < 10 ? temp[i] + 48 : temp[i] + 55;
40 }
41 return buffer;
42 }
43
44 int main()
45 {
46 char *p = NULL;
47 char *q = NULL;
48 int num = 0;
49
50 printf("input num: ");
51 scanf("%d", &num); //输入整数
52
53 p = get16String(num); //得到16进制形式的字符串
54 q = get2String(num); //得到2进制形式的字符串
55
56 printf("%s\n", p);
57 printf("%s\n", q);
58
59 return 0;
60
} |
这个程序中，get2String和get16String分别用于得到二进制字符串和十六进制字符串。
long型的整数是4个字节，即32位，每一位用0或1表示，get2String函数申请了33个字节（包括'\0'）的堆内存存放结果，get16String函数申请11个字节（包括'0'、'x'和'\0'）。然后把每位的值赋给堆内存的对应位置。程序执行结果：
input num: 456789（输入）
0x0006F855
00000000000000000000000001010101 |
6.2.3 其他编程问题（6）
面试例题18：在字符串中，插入字符统计的个数。
考点：字符串综合编程能力。
出现频率：★★★★
解析
根据题意，需要在字符串中插入字符统计的个数。例如字符串aaab，插入字符个数后变成aaa3b1。
程序代码如下所示。
1 #include
2 #include
3 #include
4
5 #define MAXCOUNT 2*100
6
7 char *transformation(char *str)
8 {
9 int len=strlen(str);
10 char *buf=new char[len+1];
11
12 char *p=str;
13 char *q=p+1;
14 int count=1;
15 while(*q)
16 {
17 if(*p==*q)
18 {
19 count++;
20 p++;
21 q++;
22 }
23 else
24 {
25 itoa(count,buf,10);
26 int nbits=strlen(buf);
27 strcat(buf,q);
28 *q=0;
29 strcat(str,buf);
30 q+=nbits;
31 p=q;
32 q=p+1;
33 count=1;
34 }
35 }
36
37 itoa(count,buf,10);
38 strcat(str,buf);
39
40 delete []buf;
41 buf=NULL;
42 return str;
43 }
44
45 int main()
46 {
47 char str[MAXCOUNT];
48
49 printf("please input a string:");
50 scanf("%s",&str);
51 printf("before transformation: %s\n",str);
52 char *pstr=transformation(str);
53 printf("after transformation: %s\n",pstr);
54
55 return 0;
56 } |
程序中的transformation()函数用来转换字符串。我们以字符串aaab为例来说明其执行过程。为了计算方便，首先申请了5字节的堆内存buf（aaab为4字节，加一个结束符为5字节）来存放字符串数字相关的信息。初始计数为1，然后进行下面的步骤。
遍历aaab直到找到不同的字符，然后在buf中保存3，把str变为aaa（即字符"b"位置内存设为0）。然后执行strcat(str,
buf)，此时str变为aaa3b，计数为1。如果到字符串末尾（碰到结束符"\0"），则退出循环，否则继续进行以上的步骤。
如果退出循环，最后一个字符个数存入buf（这里b的个数1），此时str为aaa3b，经过调用strcat(str, buf)，str变为aaa3b1。
释放buf堆内存并返回str。程序执行结果为：
please input a string:aaab
before transformation: aaab
after transformation: aaa3b1
阅读(503) | 评论(0) | 转发(0) |
