经典面试题之手撕字符串函数

经典面试题之手撕字符串函数

最近看到一些面试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 != '\0') {
        *d++ = *src++;
    }
    *d = '\0';
    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为字符串的长度,不包含\0。

实现如下:

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!='\0') {
        str1++;
        str2++;
    }
    return *str1-*str2;
}

4.strcat

将src字符串追加到dest中。

char* strcat(char* dest,const char* src) {
    char* d = dest;
    while(*d!='\0') ++d;

    while(*src!='\0') {
        *d++=*src++;
    }
    *d='\0';
    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 == '\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 s;//若s2先结束
        }
        if (*s2 != '\0' && *s1 == '\0') {
            return NULL;//若s1先结束而s2还没结束,则返回空
        }
        s++;
    }
    return NULL;
}

6.总结

手撕完毕!欢迎订阅公众号,转发与收藏!

原文发布于微信公众号 - 光城(guangcity)

原文发表时间:2019-08-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券