以小见大:从小函数实现看应聘者的编程素质(atoi.strcmp...)

时间:2023-01-15 17:02:57

作者:hustwing         hustwing@126.com  MSN: hustwing@hotmail.com

在程序员面试的时候,面试官通常会让你实现一个或几个C语言里的库函数,以此来检查你的编程功底。类似的函数实现有atoi.itoa.atof.strcmp.strcpy.memset.memcpy等等。

在平时的编程中,我们可能极少有机会要自己实现这些函数。但是面试官却很喜欢用这些东西考察你。实际上所谓的"考察",永远是个伪命题。面试者其实不是用这个小函数的实现来考察"你行",而大部分寄希望于用这个小函数来"你不行"。随便在网上搜搜,就会发现很多讨论这个的帖子,其中大部分都有一些解答(用来证明你不行的理由),仔细琢磨就会发现其中的有一些还蛮有道理,但有一些解释实在是有点牵强。

说实话,这些函数实现的考察,作用还是有的,但是就我自己感觉,作用还不在单纯的编程能力上,在本文的最后,我会发表我自己的一点看法。还是先说说这些函数的一些实现,都是我自己比较认可的版本,肯定也不一定完全符合面试官的要求,但无论如何,如果我碰到面试官这样考我,我肯定拿下面的答案应付了:)。

首先来看看xtox系列的函数,这类函数涉及数类型和字符类型之间的转换,考察的一个知识点是如何将一个数字转化为对应的字符或者如何将对应的字符转化为数字(以下的代码演示了这些转换方法),在我知道这个方法以前,我都是写个函数,建立字符和数字的对应查询关系(相当于建立了一个数字和字符的查询快表)来匹配两者的对应关系。代码应该来说比较简单,就不加注释了,后文会提到需要额外说明的几点。(特别说明:为篇幅计,下面的代码出现了两行代码出现在一行的情况,真实的代码中可能不希望这样)

-------------------------------------------------------atoi----------------------------------------------------------

int atoi(const char* str)
{
    int sign = 0,num = 0;
    assert(NULL != str);
    while (*str == ' ')
    {
        str++;
    }
    if ('-' == *str)
    {
        sign = 1; str++;
    }
    while ((*str >= '0') && (*str <= '9'))
    {
        num = num*10 + (*str - '0'); //就是这一行,将对应字符转化为数字

        str++;
    }
    if(sign == 1)
        return -num;
    else
        return num;
}

-------------------------------------------------atof------------------------------------------------------------

double atof(const char* str)
{
    double val = 0.0,power = 0.0;
    int sign = 0;
    assert(NULL != str);
    while (*str == ' ')
    {
        str++;
    }
    sign = (*str == '-')? -1 : 1;
    if ('-' == *str || '+' == *str)
    {
        str++;
    }
    while ((*str >= '0')&&(*str <= '9'))
    {
        val = val* 10.0 + (*str - '0'); str++;
    }
    if ('.' == *str)
    {
        str++;
    }
    power = 1.0;
    while ((*str >= '0')&&(*str <= '9'))
    {
        val = val* 10.0 + (*str - '0');
        power *= 10; str++;
    }
    return sign*val/power;
}

---------------------------------------------itoa------------------------------------------------------------------------

char* itoa(int val,char* buf,unsigned int radix)
{
    char *bufptr;
    char *firstdig;
    char temp;
    unsigned int digval;
    assert(buf != NULL);
    bufptr = buf;
    if (val < 0)
    {
        *bufptr++ = '-'; val = (unsigned int)(-(int)val);
    }
    firstdig = bufptr;
    do
    {
        digval =(unsigned int) val % radix;    val /= radix;
        if (digval > 9)
        {
            *bufptr++ = (char)(digval - 10 + 'a');
        }
        else
        {
            *bufptr++ = (char)(digval + '0');
        }
    } while(val > 0);
    *bufptr-- = '/0';//设置字符串末尾,并将指针指向最后一个字符
    do //反转字符
    {
        temp = *bufptr;     *bufptr = *firstdig;  *firstdig = temp;
        --bufptr; ++firstdig;
    } while(firstdig < bufptr);
    return buf;
}

----------------------------------------------itoa.end-------------------------------------------------------------------

下面是strxxx和memxxx系列,下面的一些实现,有些我到现在还抱有一些疑问,比如说strcmp函数,为什么要强制转换成unisigned以及为什么要用*dst来判断循环终止而不用*src,还没有找到更好的答案或者彻底弄清楚这些问题,以后弄清楚了再补上。

-------------------------------------------------------strcmp------------------------------------------------------------

int strcmp(const char* src,const char* dst)
{
    int ret = 0;
    if (src == dst)
    {
        return 0;
    }
    assert(NULL != src);//期待源字符串不为空
    if (dst == NULL)
    {
        return -1;
    }
    while (!(ret = *(unsigned char*)src - *(unsigned char*)dst)&& *dst)
    {
        ++src,++dst;
    }
    if (ret < 0)
    {
        ret = -1;
    }
    else if (ret > 0)
    {
        ret = 1;
    }
    return ret;
}

-------------------------------------------strcpy------------------------------------------------------------------------

char* strcpy(char* dst,const char* src)
{
    char* strDst = dst;
    assert(src != NULL && dst != NULL);//拷贝空串被认为是没有意义的,使用assert检查
    while ((*dst++ = *src++) != '/0')
    {
        NULL;
    }
    return strDst;
}

--------------------------------------memcpy-------------------------------------------------------------------------

void* memcpy(void* dst,const void* src,size_t count)
{
    char* pbTo = (char*)dst;
    char* pbFrom = (char*)src;
    assert(dst!= NULL && src != NULL);
    assert(pbTo >= pbFrom+count || pbFrom >= pbTo + count);//防止内存重叠(overlap)
    while (count-- > 0)
    {
        *pbTo++ = *pbFrom++;
    }
    return dst;
}

--------------------------------------memmove---------------------------------------------------------------------

void* memmove(void* dst,const void* src,size_t count)
{
    char* pbTo = (char*)dst;
    char* pbFrom = (char*)src;
    assert(dst != NULL && src != NULL);
    if (dst <= src || pbTo >= pbFrom + count)//没有overlap的情况,直接拷贝
    {
        while (count-- > 0)
        {
            *pbTo++ = *pbFrom++;
        }
    }
    else
    {
        pbTo = pbTo + count -1;//overlap的情况,从高位地址向低位拷贝
        pbFrom = pbFrom + count -1;
        while (count-- > 0)
        {
            *pbTo-- = *pbFrom--;
        }
    }
    return dst;
}

--------------------------------------memset-------------------------------------------------------------------------

void* memset(void* buf,int c,size_t count)
{
    char* pvTo = (char*)buf;
    assert(buf != NULL);
    while (count-- >0)
    {
        *pvTo++ = (char)c;
    }
    return buf;
}

--------------------------------------memset.end---------------------------------------------------------------------

这些函数的代码都很短小,但是面试官对你这几行短小的代码抱有很高的期望。

首先,正确性!实现得都不正确,那还搞毛啊,其他的小问题肯定谈都不用谈了,直接out!正确性要注意的地方,每个函数的功能起码要了解(memmove等),边界的检查不能出错;返回值也是要注意的地方。

其次,assert不能少!对指针有效性的检查是非常必要的,特别是在memcpy中,存在两个assert,分别检查指针的有效性以及内存是否交叠。针对第二个assert还要加上必要注释(因为代码的维护者并不是一眼就能看出这个assert的涵义,搞不好可能直接在维护代码中删掉这么重要的一个assert检查)。

然后要注意的有:指针的有效性检验,最好是与NULL进行比较。最后,空语句(strcpy)、大括号一个都不能少。

我自己的想法,其实这些函数(包含其他小的函数),难度不算太大,当然要写得完全正确也非常不易。但是,在正确性的基础上,面试官期望从你的代码中发现你身上作为程序员的素质和态度!当我们编程的时候,我们的脑海里真的想的是手里敲的代码吗?当我们正在实现一个函数或者一个类的时候,我们真的认真考虑了它应该怎样被实现吗?针对这些小函数(当然,大函数更一样了),参数的有效性检查是always必要的(不要相信任何输入!),边界的有效性检查是很容易出错的!每一行代码都要想清楚为什么要这么实现,我想,只要你脑子所想是你手上所要做的,我手"写"我心,自然是不会出错了,起码也应该知道自己错在哪里,下次改正就好。《微软C编程精粹》最后一句话话告诉我们:成功地书写无错代码的关键可以总结为一个总的原则,即绝不允许同样的错误出现两次!

最后,推荐一些参考书,就我自己的阅读经验来看,这些参考书对如何写好这些小函数还是很有借鉴意义的,按重要性排序:

1.《编程精粹—微软编写优质无错C程序秘诀》,Writing Clean Code——Microsoft Techniques for Developing Bug-free C Programs;

2.《高质量C/C++编程指南》,一本书,也是林锐编的,网上广为流传的同名小册子算是精简版;

3.《程序员面试宝典》;

提供1和2(小册子)的电子版,以后有时间的时候上传上来。等不及的email知会一声:hustwing@126.com