经典面试题之手撕字符串函数
- 2019 年 10 月 6 日
- 筆記
经典面试题之手撕字符串函数
最近看到一些面试C/C++的一个问题：手撕字符串函数，包括：
- strcpy
- memcpy
- memmove
- strcat
- strcmp
- strstr
下面一起来手撕。
1.strcpy
功能：把 src 所指向的字符串复制到 dest。
看到这个需求你一想，这还不简单，就写出了下面代码，可惜啊，你挂了！
char *strcpy(char *dest, const char *src) { if (!dest || !src) return NULL; char *d = dest; while (*src != ' ') { *d++ = *src++; } *d = ' '; return dest; }
考虑一个场景，现在测试程序调用如下：
char src[66] = "lightcity"; strcpy(src + 1, src, strlen(src) + 1);
你跑一下你的代码发现运行结果是：lllllllll。失败吧！什么原因呢？
这里有个重要的点：内存重叠！
在上述代码中：
src+1指向的是i这个位置src指向的是l这个位置
当指针dst赋值为l的时候，前面的i已经被改为l，依次类推，就输出了lllllllll。
我们分析一下内存重叠的位置：
内存重叠：当 src<dst<src+n n为字符串的长度，不包含 。
实现如下：
char *strcpy1(char *dest, const char *src) { if (!dest || !src) return NULL; char *d = dest; int size = strlen(src) + 1; if (d > src && d < src + size) { d = d + size - 1; src = src + size - 1; while (size--) { *d-- = *src--; } } else { while (size--) { *d++ = *src++; } } }
2.memcpy与memmove
功能：从存储区 src 复制 n 个字符到存储区 dest。
如果写出的代码如下：同strcpy一样你也失败了！
void *memcpy(void *dest, const void *src, size_t n) { if (!dest || !src) return NULL; char *d = (char *) dest; const char *s = (const char *) src; size_t i = 0; for (i = 0; i < n; i++) { *d++ = *s++; } return dest; }
优化也是消除内存重叠！
我们看一下man手册中的memcpy函数：
The memcpy() function copies n bytes from memory area src to memory area dest. The memory areas must not overlap. Use memmove(3) if the memory areas do overlap。
翻译一下就是，memcpy函数从存储区 src 复制 n 个字符到存储区 dest。存储区不能重叠！
如果重叠了，需要使用memmove。
实现如下：
void *memcpy1(void *dest, const void *src, size_t n) { if (!dest || !src) return NULL; char *d = (char *) dest; const char *s = (const char *) src; if (d > s && d < s + n) { d = d + n - 1; s = s + n - 1; while (n--) *d-- = *s--; } else { while (n--) *d++ = *s++; } return dest; }
上述也是memmove函数实现！
3. strcmp
比较两个字符串，正数就是srt1大，负数就是srt2大，反之相等！
int strcmp(const char* str1,const char* str2) { while(*str1==*str2&&*str1!=' ') { str1++; str2++; } return *str1-*str2; }
4.strcat
将src字符串追加到dest中。
char* strcat(char* dest,const char* src) { char* d = dest; while(*d!=' ') ++d; while(*src!=' ') { *d++=*src++; } *d=' '; return dest; }
5.strstr
在str1中查找str2，并返回str2在str1中的起始位置后的所有字符串。
char* strstr(char *str1, char *str2) { if (str1 == NULL || str2 == NULL) return NULL; char *s = str1; if (*str2 == ' ') { return NULL;//若str2为空，则直接返回空 } while (*s != ' ') {//若不为空，则进行查询 char *s1 = s; char *s2 = str2; while (*s1 != ' ' && *s2 != ' ' && *s1 == *s2) { s1++, s2++; } if (*s2 == ' ') { return s;//若s2先结束 } if (*s2 != ' ' && *s1 == ' ') { return NULL;//若s1先结束而s2还没结束，则返回空 } s++; } return NULL; }
6.总结
手撕完毕！欢迎订阅公众号，转发与收藏！
