Skip to content

Latest commit

 

History

History
257 lines (210 loc) · 7.38 KB

04.0.md

File metadata and controls

257 lines (210 loc) · 7.38 KB
Raw

第四章：现场编写类似strstr/strcpy/strpbrk的函数

第一节、字符串查找

1.1题目描述：

给定一个字符串A，要求在A中查找一个子串B。 如A="ABCDF"，要你在A中查找子串B=“CD”。

分析：比较简单，相当于实现strstr库函数，主体代码如下：

//在字符串中查找指定字符串的第一次出现，不能找到则返回-1
int strstr(char *string, char *substring)
{
    if (string == NULL || substring == NULL)
        return -1;

    int lenstr = strlen(string);
    int lensub = strlen(substring);

    if (lenstr < lensub)
        return -1;

    int len = lenstr - lensub;
    int i,j;
    for (i = 0; i <= len; i++)   //复杂度为O(m*n)
    {
        for (j = 0; j < lensub; j++)
        {
            if (string[i+j] != substring[j])
                break;
        }
        if (j == lensub)
            return i + 1;
    }
    return -1;
}

读者反馈@xiaohui5319：楼主啊，对于你那个strstr的函数，我觉得有点小问题。我查了一下C标准库的源码，它给的声明是这样的，两个参数都有const。

    char *
    STRSTR (const char *haystack_start, const char *needle_start)

而且标准库中没有调用strlen函数，因为假如你是标准库的设计者，strlen()函数还没设计出来，你怎么去计算两个字符串的长度？是不是只能通过指针移动来实现，我觉得这些都是微软要考察的地方。

此外：还有int lenstr=strlen(string);这是不安全的？ strlen函数的返回类型是size_t型，也就是无符号整型，假如我的数组长度很长（假如是用堆分配的，可以很大很大），长过2的31次方减1的话，会发生溢出，你这lenstr就会变成负值了用size_t类型最保险。

以后，本编程艺术系列中有任何问题，暂未来得及及时修正，请读者多加思考，多加辨明。

上述程序已经实现了在字符串中查找第一个子串的功能，时间复杂度为O(n*m)，也可以用KMP算法，复杂度为O(m+n)。为人打通思路，提高他人创造力，我想，这是狂想曲与其它的面试解答所不同的地方，也是我们写狂想曲系列文章的意义与价值之所在。

1.2、题目描述

在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。

代码则可以如下编写：

//查找第一个只出现一次的字符，
//copyright@ yansha
//July、updated，2011.04.24.
char FirstNotRepeatChar(char* pString)
{
    if(!pString)
        return '\0';

    const int tableSize = 256;
    //有点要提醒各位注意，一般常数的空间消耗，如这里的256，我们也认为此空间复杂度为O（1）。
    int hashTable[tableSize] = {0}; //存入数组，并初始化为0

    char* pHashKey = pString;
    while(*(pHashKey) != '\0')
        hashTable[*(pHashKey++)]++;

    while(*pString != '\0')
    {
        if(hashTable[*pString] == 1)
            return *pString;

        pString++;
    }
    return '\0';  //没有找到满足条件的字符，退出
}

代码二，bitmap：

# include<stdio.h>
# include<string.h>

const int N = 26;
int bit_map[N];

void findNoRepeat(char *src)
{
    int pos;
    char *str = src;
    int i ,len = strlen(src);

    //统计
    for(i = 0 ; i < len ;i ++)
        bit_map[str[i]-'a'] ++;

    //从字符串开始遍历 其bit_map==1 那么就是结果
    for(i = 0 ; i < len ; i ++)
    {
        if(bit_map[str[i]-'a'] == 1)
        {
            printf("%c", str[i]);
            return;
        }
    }
}

int main()
{
    char *src = "abaccdeff";
    findNoRepeat(src);
    printf("\n");
    return 0;
}

第二节、字符串拷贝

题目描述：

要求实现库函数strcpy

原型声明: extern char *strcpy(char *dest, char *src);

功能: 把src所指由NULL结束的字符串复制到dest所指的数组中。

说明: src和dest所指内存区域不可以重叠且dest必须有足够的空间来容纳src的字符串。 　

返回: 指向dest的指针。

分析: 如果编写一个标准strcpy函数的总分值为10，下面给出几个不同得分的答案:

//得2分
void strcpy( char *strDest, char *strSrc )
{
    while( (*strDest++ = * strSrc++) != '\0' );
}

//得4分
void strcpy( char *strDest, const char *strSrc )
{
    //将源字符串加const，表明其为输入参数，加2分
    while( (*strDest++ = * strSrc++) != '\0' );
}

//得7分
void strcpy(char *strDest, const char *strSrc)
{
    //对源地址和目的地址加非0断言，加3分
    assert( (strDest != NULL) && (strSrc != NULL) );
    while( (*strDest++ = * strSrc++) != '\0' );
}

//得9分
//为了实现链式操作，将目的地址返回，加2分！
char * strcpy( char *strDest, const char *strSrc )
{
    assert( (strDest != NULL) && (strSrc != NULL) );
    char *address = strDest;
    while( (*strDest++ = * strSrc++) != '\0' );
    return address;
}

//得10分，基本上所有的情况，都考虑到了
//如果有考虑到源目所指区域有重叠的情况，加1分！
char * strcpy( char *strDest, const char *strSrc )
{
    if(strDest == strSrc) { return strDest; }
    assert( (strDest != NULL) && (strSrc != NULL) );
    char *address = strDest;
    while( (*strDest++ = * strSrc++) != '\0' );
    return address;
}

第三节、其余库函数的实现

考察此类编写同库函数一样功能的函数经常见于大大小小的IT公司的面试题目中，以下是常见的字符串库函数的实现，希望，对你有所帮助，有任何问题，欢迎不吝指正：

//@heyaming
//对原 strtok 的修改，根据MSDN,strToken可以为NULL.实际上第一次call strtok给定一字串，
//再call strtok时可以输入NULL代表要接着处理给定字串。
//所以需要用一 static 保存没有处理完的字串。同时也需要处理多个分隔符在一起的情况。
char *strtok(char *strToken, const char *str)
{
    assert(str != NULL);
    static char *last;

    if (strToken == NULL && (strToken = last) == NULL)
        return (NULL);

    char *s = strToken;
    const char *t = str;
    while (*s != '\0')
    {
        t = str;
        while (*t != '\0')
        {
            if (*s == *t)
            {
                last = s + 1;
                if (s - strToken == 0) {
                    strToken = last;
                    break;
                }
                *(strToken + (s - strToken)) = '\0';
                return strToken;
            }
            ++ t;
        }
        ++ s;
    }
    return NULL;
}

//@big：
//要处理src和dest有重叠的情况，不是从尾巴开始移动就没问题了。
//一种情况是dest小于src有重叠，这个时候要从头开始移动，
//另一种是dest大于src有重叠，这个时候要从尾开始移动。
void *memmove(void *dest, const void *src, unsigned int count)
{
    assert(dest != NULL && src != NULL);
    char* pdest = (char*) dest;
    char* psrc = (char*) src;

    //pdest在psrc后面，且两者距离小于count时，从尾部开始移动. 其他情况从头部开始移动
    if (pdest > psrc && pdest - psrc < count)
    {
        while (count--)
        {
            *(pdest + count) = *(psrc + count);
        }
    } 
    else
    {
        while (count--)
        {
            *pdest++ = *psrc++;
        }
    }
    return dest;
}

测试：以上所有的函数，都待进一步测试，有任何问题，欢迎任何人随时不吝指出。