当前位置：网站首页>秋招之路-经典面试题之手写字符串函数

秋招之路-经典面试题之手写字符串函数

2022-07-29 18:26:00 【51CTO】

秋招之路-经典面试题之手写字符串函数_c++

[图]mac and coffe 2019-06-26

这是 herongwei 的第 69 篇原创

阅读本文大概需要 8 分钟

前言-手写代码必备手册

手写字符串处理相关函数是面试中极为常见的一类题。这里我将本人之前面试经历过的和网上高频的题目总结一下，希望能对你有所帮助。

经常面到的题目有以下几种：

1、strcpy；

2、strcat；

3、strcmp；

4、strstr；

5、memcpy；

6、memmove；

1、strcpy

函数作用：把 src 所指向的字符串复制到 dest。

注意：dest定义的空间应该比src大。

参考代码：

       
       char
       
       * 
       
       strcpy(
       
       char 
       
       *
       
       dest,
       
       const 
       
       char 
       
       *
       
       src){
       
       char 
       
       *
       
       ret 
       
       = 
       
       dest;
       
       assert(
       
       dest
       
       !=
       
       NULL);
       
       //优化点1：检查输入参数
       
       assert(
       
       src
       
       !=
       
       NULL);
       
       while(
       
       *
       
       src
       
       !=
       
       '\0'){
       
       *(
       
       dest
       
       ++)
       
       =*(
       
       src
       
       ++);
       
    }
       
       *
       
       dest
       
       =
       
       '\0';
       
       //优化点2：手动地将最后的'\0'补上
       
       return 
       
       ret;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.

优化：

       
       //考虑内存重叠的字符串拷贝函数 优化的点
       
       char
       
       * 
       
       strcpy(
       
       char 
       
       *
       
       dest,
       
       char 
       
       *
       
       src){
       
       char 
       
       *
       
       ret 
       
       = 
       
       dest;
       
       assert(
       
       dest
       
       !=
       
       NULL);
       
       assert(
       
       src
       
       !=
       
       NULL);
       
       memmove(
       
       dest,
       
       src,
       
       strlen(
       
       src)
       
       +
       
       1);
       
       return 
       
       ret;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.

2、strcat

函数作用：把 src 所指向的字符串追加到 dest 所指向的字符串的结尾。

参考代码：

       
       char
       
       * 
       
       strcat(
       
       char 
       
       *
       
       dest,
       
       const 
       
       char 
       
       *
       
       src){
       
       //1. 将目的字符串的起始位置先保存，最后要返回它的头指针
       
       //2. 先找到 dest 的结束位置,再把 src 拷贝到 dest中，记得在最后要加上'\0'
       
       char 
       
       *
       
       ret 
       
       = 
       
       dest;
       
       assert(
       
       dest
       
       !=
       
       NULL);
       
       assert(
       
       src
       
       !=
       
       NULL);
       
       while(
       
       *
       
       dest
       
       !=
       
       '\0'){
       
       dest
       
       ++;
       
    }
       
       while(
       
       *
       
       src
       
       !=
       
       '\0'){
       
       *(
       
       dest
       
       ++)
       
       =*(
       
       src
       
       ++);
       
    }
       
       *
       
       dest
       
       =
       
       '\0';
       
       return 
       
       ret;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.

3、strcmp

函数作用：把 str1 所指向的字符串和 str2 所指向的字符串进行比较。

该函数返回值如下：

如果返回值 < 0，则表示 str1 小于 str2。

如果返回值 > 0，则表示 str1 大于 str2。

如果返回值 = 0，则表示 str1 等于 str2。

参考代码：

       
       int 
       
       strcmp(
       
       const 
       
       char 
       
       *
       
       s1,
       
       const 
       
       char 
       
       *
       
       s2){
       
       assert(
       
       s1
       
       !=
       
       NULL);
       
       assert(
       
       s2
       
       !=
       
       NULL);
       
       while(
       
       *
       
       s1
       
       !=
       
       '\0' 
       
       && 
       
       *
       
       s2
       
       !=
       
       '\0'){
       
       if(
       
       *
       
       s1
       
       >*
       
       s2){
       
       return 
       
       1;
       
        }
       
       else 
       
       if(
       
       *
       
       s1
       
       <*
       
       s2){
       
       return 
       
       -
       
       1;
       
        }
       
       else{
       
       s1
       
       ++,
       
       s2
       
       ++;
       
        }
       
    }
       
       //当有一个字符串已经走到结尾
       
       if(
       
       *
       
       s1
       
       >*
       
       s2){
       
       return 
       
       1;
       
    }
       
       else 
       
       if(
       
       *
       
       s1
       
       <*
       
       s2){
       
       return 
       
       -
       
       1;
       
    }
       
       else{
       
       return 
       
       0;
       
    }
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.

4、strstr

函数作用：在字符串 str1 中查找第一次出现字符串 str2 的位置，不包含终止符 '\0'。

参考代码：

       
       char
       
       * 
       
       strstr(
       
       char 
       
       *
       
       str1,
       
       char 
       
       *
       
       str2){
       
       char
       
       * 
       
       s 
       
       = 
       
       str1;
       
       assert(
       
       str1
       
       !=
       
       '\0');
       
       assert(
       
       str2
       
       !=
       
       '\0');
       
       if(
       
       *
       
       str2
       
       ==
       
       '\0'){
       
       return 
       
       NULL;
       
       //若str2为空，则直接返回空
       
    }
       
       while(
       
       *
       
       s
       
       !=
       
       '\0'){
       
       //若不为空，则进行查询
       
       char
       
       * 
       
       s1 
       
       = 
       
       s;
       
       char
       
       * 
       
       s2 
       
       = 
       
       str2;
       
       while(
       
       *
       
       s1
       
       !=
       
       '\0'
       
       &&*
       
       s2
       
       !=
       
       '\0' 
       
       && 
       
       *
       
       s1
       
       ==*
       
       s2){
       
       s1
       
       ++,
       
       s2
       
       ++;
       
        }
       
       if(
       
       *
       
       s2
       
       ==
       
       '\0'){
       
       return 
       
       str2;
       
       //若s2先结束
       
        }
       
       if(
       
       *
       
       s2
       
       !=
       
       '\0' 
       
       && 
       
       *
       
       s1
       
       ==
       
       '\0'){
       
       return 
       
       NULL;
       
       //若s1先结束而s2还没结束，则返回空
       
        }
       
       s
       
       ++;
       
    }
       
       return 
       
       NULL;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.

5、memcpy

函数作用：模拟实现 memcpy 函数从存储区 src 复制 n 个字符到存储区 dst。

参考代码（版本一）：

       
       void
       
       * 
       
       memcpy(
       
       void
       
       * 
       
       dest, 
       
       const 
       
       void
       
       * 
       
       src, 
       
       size_t 
       
       num){
       
       void
       
       * 
       
       ret 
       
       = 
       
       dest ;
       
       size_t 
       
       i 
       
       = 
       
       0 ;
       
       assert(
       
       dest 
       
       != 
       
       NULL) ;
       
       assert(
       
       src 
       
       != 
       
       NULL) ;
       
       for(
       
       i 
       
       = 
       
       0; 
       
       i
       
       <
       
       num; 
       
       ++
       
       i){
       
       //因为void* 不能直接解引用，所以需要强转成char*再解引用
       
       //此处的void* 实现了泛型编程
       
       *(
       
       char
       
       *) 
       
       dest 
       
       = 
       
       *(
       
       char
       
       *) 
       
       src ;
       
       dest 
       
       = (
       
       char
       
       *)
       
       dest 
       
       + 
       
       1 ;
       
       src 
       
       = (
       
       char
       
       *) 
       
       src 
       
       + 
       
       1 ;
       
    }
       
       return 
       
       ret ;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.

注意了：面试中如问到 memcpy 的实现，那就要小心了，这里有陷阱。

先看下标准 memcpy() 的解释：

对于地址重叠的情况，该函数的行为是未定义的。

       
       void 
       
       *
       
       memcpy(
       
       void 
       
       *
       
       dst, 
       
       const 
       
       void 
       
       *
       
       src, 
       
       size_t 
       
       n);
       
       //If copying takes place between objects that overlap, the behavior is undefined.
      
1.
2.

事实上所说的陷阱也在于此，自己动手实现 memcpy() 时就需要考虑地址重叠的情况，而我们上面第一版的代码中并没有考虑到地址重叠的问题！

测试代码

       
       void 
       
       Test(){
       
       char 
       
       p [
       
       256]
       
       = 
       
       "hello,world!";
       
       memcpy(
       
       p
       
       +
       
       1,
       
       p,
       
       strlen(
       
       p)
       
       +
       
       1);
       
       printf(
       
       "%s\n",
       
       p);
       
}
      
1.
2.
3.
4.
5.

如果你身边有电脑，你可以试一下，你会发现输出并不是我们期待的“hhello,world!”（在“hello world！”前加个h）

而是“hhhhhhhhhhhhhh”！

这是什么原因呢？

仔细看下面这张图

秋招之路-经典面试题之手写字符串函数_c++_02

原因就出在源地址区间和目的地址区间有重叠的地方！我相信，如果你反应足够快，马上会说那我从高地址开始拷贝不就行了么？

粗略地看，似乎能解决这个问题，虽然区间是重叠了，但是在修改以前已经拷贝了，所以不影响结果。但是仔细一想，这其实是犯了和上面一样的思维不严谨的错误，因为如果这样调用还是会出错：

       
       void 
       
       Test(){
       
       char 
       
       p [
       
       256]
       
       = 
       
       "hello,world!";
       
       memcpy(
       
       p,
       
       p
       
       +
       
       1,
       
       strlen(
       
       p)
       
       +
       
       1);
       
       printf(
       
       "%s\n",
       
       p);
       
}
      
1.
2.
3.
4.
5.

所以比较推荐的解决方案还是判断源地址和目的地址的大小，才决定到底是从高地址开始拷贝还是低地址开始拷贝。

这个细节很重要！

其实，C 标准库也提供了地址重叠时的内存拷贝函数：memmove()，那么为什么还要考虑重写memcpy()函数呢?

原因在于：因为 memmove() 函数的实现效率问题，该函数把源字符串拷贝到临时 buf 里，然后再从临时 buf 里写到目的地址，增加了一次不必要的开销。

6、memmove

函数作用：相当于考虑内存重叠的 memcpy 函数，从存储区 src 复制 n 个字符到存储区 dst。

参考代码（版本二）：

       
       //考虑内存重叠的memcpy函数 优化的点
       
       void
       
       * 
       
       memmove(
       
       void
       
       * 
       
       dst, 
       
       const 
       
       void
       
       * 
       
       src, 
       
       size_t 
       
       n)  {  
       
       char
       
       * 
       
       s_dst;  
       
       char
       
       * 
       
       s_src;  
       
       s_dst 
       
       = (
       
       char
       
       *)
       
       dst;  
       
       s_src 
       
       = (
       
       char
       
       *)
       
       src;  
       
       if(
       
       s_dst
       
       >
       
       s_src 
       
       && (
       
       s_src
       
       +
       
       n
       
       >
       
       s_dst)) { 
       
       //第二种内存覆盖的情形。
       
       s_dst 
       
       = 
       
       s_dst
       
       +
       
       n
       
       -
       
       1;  
       
       s_src 
       
       = 
       
       s_src
       
       +
       
       n
       
       -
       
       1;  
       
       while(
       
       n
       
       --) {  
       
       *
       
       s_dst
       
       -- 
       
       = 
       
       *
       
       s_src
       
       --;  
       
        }  
       
    }
       
       else {  
       
       while(
       
       n
       
       --) {  
       
       *
       
       s_dst
       
       ++ 
       
       = 
       
       *
       
       s_src
       
       ++;  
       
        }  
       
    }  
       
       return 
       
       dst;  
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.