程序员编程艺术:第四章、现场编写类似strstr/strcpy/strpbrk的函数

时间:2023-02-12 10:29:53

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

 

作者:July。
    说明: 如果在博客中代码使用了\n,csdn blog系统将会自动回给我变成/n。据后续验证,可能是原来旧blog版本的bug,新版已不存在此问题。至于,本文代码,日后统一修正。July、2012.05.02。  
    微博:http://weibo.com/julyweibo  。
    出处:http://blog.csdn.net/v_JULY_v 
    wiki:http://tctop.wikispaces.com/
----------------------------------------------


前奏

    有网友向我反应,之前三章(http://t.cn/hgVPmH)的面试题目,是否有点太难了。诚如他所说,绝大部分公司的面试题不会像微软等公司的面试题目出的那么变态,或复杂。

    面试考察的是你对基础知识的掌握程度,及编程能力是否过硬的一种检测,所以,扎实基础知识,提高编程能力,比去看什么所谓的面经,或去背面试题目的答案强多了。

    很多中、小型公司自己的创造能力,包括人力,物力资源都有限,所以,他们的面试题目除了copy一些大公司的题库之外(当然,考察你对基础知识的掌握情况,是肯定不会放过的),还有一个途径就是让你在限定时间内(如十分钟),当场实现一些类似strcpy/strcat/strpbrk等库函数,这个主要看你对细节的把握,以及编程能力是否之扎实了。

    同时,本章里出现的代码(除了第4节的c标准库部分源码)都是个人限定在短时间内(正好,突出现场感)编写的,很多问题,难免有所考虑不周。所以,如果你发现本章任何一段代码有任何问题,恳请不吝指正。


第一节、字符串查找
1.1题目描述:
给定一个字符串A,要求在A中查找一个子串B。
如A="ABCDF",要你在A中查找子串B=“CD”。

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

  1. //在字符串中查找指定字符串的第一次出现,不能找到则返回-1      
  2. int strstr(char *string, char *substring)      
  3. {     
  4.     if (string == NULL || substring == NULL)        
  5.         return -1;        
  6.       
  7.     int lenstr = strlen(string);     
  8.     int lensub = strlen(substring);     
  9.       
  10.     if (lenstr < lensub)        
  11.         return -1;         
  12.       
  13.     int len = lenstr - lensub;  
  14.     for (int i = 0; i <= len; i++)   //复杂度为O(m*n)     
  15.     {     
  16.         for (int j = 0; j < lensub; j++)     
  17.         {     
  18.             if (string[i+j] != substring[j])     
  19.                 break;     
  20.         }     
  21.         if (j == lensub)     
  22.             return i + 1;     
  23.     }     
  24.     return -1;     
  25. }    

    读者反馈@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。 

代码则可以如下编写:

  1. //查找第一个只出现一次的字符,     
  2. //copyright@ yansha     
  3. //July、updated,2011.04.24.     
  4. char FirstNotRepeatChar(char* pString)     
  5. {     
  6.     if(!pString)     
  7.         return '/0';     
  8.       
  9.     const int tableSize = 256;    
  10.     //有点要提醒各位注意,一般常数的空间消耗,如这里的256,我们也认为此空间复杂度为O(1)。  
  11.     int hashTable[tableSize] = {0}; //存入数组,并初始化为0     
  12.       
  13.     char* pHashKey = pString;     
  14.     while(*(pHashKey) != '/0')     
  15.         hashTable[*(pHashKey++)]++;     
  16.       
  17.     while(*pString != '/0')     
  18.     {     
  19.         if(hashTable[*pString] == 1)     
  20.             return *pString;     
  21.           
  22.         pString++;     
  23.     }     
  24.     return '/0';  //没有找到满足条件的字符,退出     
  25. }    

代码二,bitmap:

  1. # include<stdio.h>  
  2. # include<string.h>  
  3.   
  4. const int N = 26;  
  5. int bit_map[N];  
  6.   
  7. void findNoRepeat(char *src)  
  8. {  
  9.     int pos;  
  10.     char *str = src;  
  11.     int i ,len = strlen(src);  
  12.       
  13.     //统计  
  14.     for(i = 0 ; i < len ;i ++)  
  15.         bit_map[str[i]-'a'] ++;  
  16.       
  17.     //从字符串开始遍历 其bit_map==1 那么就是结果  
  18.     for(i = 0 ; i < len ; i ++)  
  19.     {  
  20.         if(bit_map[str[i]-'a'] == 1)  
  21.         {  
  22.             printf("%c",str[i]);  
  23.             return ;  
  24.         }  
  25.     }  
  26. }  
  27.   
  28. int main()  
  29. {     
  30.     char *src = "abaccdeff";  
  31.     findNoRepeat(src);  
  32.     printf("/n");  
  33.     return 0;  
  34. }  
  

第二节、字符串拷贝
题目描述:
要求实现库函数strcpy,
原型声明:extern char *strcpy(char *dest,char *src); 
功能:把src所指由NULL结束的字符串复制到dest所指的数组中。  
说明:src和dest所指内存区域不可以重叠且dest必须有足够的空间来容纳src的字符串。  
返回指向dest的指针。

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

  1. //得2分     
  2. void strcpy( char *strDest, char *strSrc )     
  3. {     
  4.     while( (*strDest++ = * strSrc++) != '/0' );     
  5. }      
  6.   
  7. //得4分     
  8. void strcpy( char *strDest, const char *strSrc )      
  9. {     
  10.     //将源字符串加const,表明其为输入参数,加2分     
  11.     while( (*strDest++ = * strSrc++) != '/0' );     
  12. }      
  13.   
  14. //得7分     
  15. void strcpy(char *strDest, const char *strSrc)      
  16. {     
  17.     //对源地址和目的地址加非0断言,加3分     
  18.     assert( (strDest != NULL) && (strSrc != NULL) );     
  19.     while( (*strDest++ = * strSrc++) != '/0' );     
  20. }      
  21.   
  22. //得9分     
  23. //为了实现链式操作,将目的地址返回,加2分!     
  24. char * strcpy( char *strDest, const char *strSrc )      
  25. {     
  26.     assert( (strDest != NULL) && (strSrc != NULL) );     
  27.     char *address = strDest;      
  28.     while( (*strDest++ = * strSrc++) != '/0' );      
  29.     return address;     
  30. }    
  31.   
  32. //得10分,基本上所有的情况,都考虑到了  
  33. //如果有考虑到源目所指区域有重叠的情况,加1分!     
  34. char * strcpy( char *strDest, const char *strSrc )      
  35. {     
  36.     if(strDest == strSrc) { return strDest; }  
  37.     assert( (strDest != NULL) && (strSrc != NULL) );     
  38.     char *address = strDest;      
  39.     while( (*strDest++ = * strSrc++) != '/0' );      
  40.     return address;     
  41. }    

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

  1. //@yansha:字串末尾要加结束符'/0',不然输出错位结果  
  2. char *strncpy(char *strDes, const char *strSrc, unsigned int count)      
  3. {      
  4.     assert(strDes != NULL && strSrc != NULL);      
  5.     char *address = strDes;      
  6.     while (count-- && *strSrc != '/0')      
  7.         *strDes++ = *strSrc++;   
  8.     *strDes = '/0';  
  9.     return address;      
  10. }   
  11.   
  12. //查找字符串s中首次出现字符c的位置   
  13. char *strchr(const char *str, int c)   
  14. {   
  15.     assert(str != NULL);   
  16.     for (; *str != (char)c; ++ str)   
  17.         if (*str == '/0')   
  18.             return NULL;   
  19.         return str;   
  20. }   
  21.   
  22. int strcmp(const char *s, const char *t)   
  23. {   
  24.     assert(s != NULL && t != NULL);   
  25.     while (*s && *t && *s == *t)   
  26.     {   
  27.         ++ s;   
  28.         ++ t;   
  29.     }   
  30.     return (*s - *t);   
  31. }   
  32.   
  33. char *strcat(char *strDes, const char *strSrc)   
  34. {   
  35.     assert((strDes != NULL) && (strSrc != NULL));   
  36.     char *address = strDes;   
  37.     while (*strDes != '/0')   
  38.         ++ strDes;   
  39.     while ((*strDes ++ = *strSrc ++) != '/0')   
  40.         NULL;   
  41.     return address;   
  42. }   
  43.   
  44. int strlen(const char *str)   
  45. {   
  46.     assert(str != NULL);   
  47.     int len = 0;   
  48.     while (*str ++ != '/0')   
  49.         ++ len;   
  50.     return len;   
  51. }   
  52.   
  53. //此函数,梦修改如下     
  54. char *strdup_(char *strSrc)     
  55. //将字符串拷贝到新的位置     
  56. {     
  57.     if(strSrc!=NULL)     
  58.     {     
  59.         char *start=strSrc;     
  60.         int len=0;     
  61.         while(*strSrc++!='/0')     
  62.             len++;     
  63.           
  64.         char *address=(char *)malloc(len+1);     
  65.         assert(address != NULL);  
  66.           
  67.         while((*address++=*start++)!='/0');      
  68.         return address-(len+1);      
  69.     }     
  70.     return NULL;     
  71. }     
  72.   
  73. //多谢laoyi19861011指正  
  74. char *strstr(const char *strSrc, const char *str)   
  75. {   
  76.     assert(strSrc != NULL && str != NULL);   
  77.     const char *s = strSrc;   
  78.     const char *t = str;   
  79.     for (; *strSrc != '/0'; ++ strSrc)   
  80.     {   
  81.         for (s = strSrc, t = str; *t != '/0' && *s == *t; ++s, ++t)   
  82.             NULL;   
  83.         if (*t == '/0')   
  84.             return (char *) strSrc;   
  85.     }   
  86.     return NULL;   
  87. }   
  88.   
  89. char *strncat(char *strDes, const char *strSrc, unsigned int count)   
  90. {   
  91.     assert((strDes != NULL) && (strSrc != NULL));   
  92.     char *address = strDes;   
  93.     while (*strDes != '/0')   
  94.         ++ strDes;   
  95.     while (count -- && *strSrc != '/0' )   
  96.         *strDes ++ = *strSrc ++;   
  97.     *strDes = '/0';   
  98.     return address;   
  99. }   
  100.   
  101. int strncmp(const char *s, const char *t, unsigned int count)   
  102. {   
  103.     assert((s != NULL) && (t != NULL));   
  104.     while (*s && *t && *s == *t && count --)   
  105.     {   
  106.         ++ s;   
  107.         ++ t;   
  108.     }   
  109.     return (*s - *t);   
  110. }   
  111.   
  112. char *strpbrk(const char *strSrc, const char *str)   
  113. {   
  114.     assert((strSrc != NULL) && (str != NULL));   
  115.     const char *s;   
  116.     while (*strSrc != '/0')   
  117.     {   
  118.         s = str;   
  119.         while (*s != '/0')   
  120.         {   
  121.             if (*strSrc == *s)   
  122.                 return (char *) strSrc;   
  123.             ++ s;   
  124.         }   
  125.         ++ strSrc;   
  126.     }   
  127.     return NULL;   
  128. }   
  129.   
  130. int strcspn(const char *strSrc, const char *str)   
  131. {   
  132.     assert((strSrc != NULL) && (str != NULL));   
  133.     const char *s;   
  134.     const char *t = strSrc;   
  135.     while (*t != '/0')   
  136.     {   
  137.         s = str;   
  138.         while (*s != '/0')   
  139.         {   
  140.             if (*t == *s)   
  141.                 return t - strSrc;   
  142.             ++ s;   
  143.         }   
  144.         ++ t;   
  145.     }   
  146.     return 0;   
  147. }   
  148.   
  149. int strspn(const char *strSrc, const char *str)   
  150. {   
  151.     assert((strSrc != NULL) && (str != NULL));   
  152.     const char *s;   
  153.     const char *t = strSrc;   
  154.     while (*t != '/0')   
  155.     {   
  156.         s = str;   
  157.         while (*s != '/0')   
  158.         {   
  159.             if (*t == *s)   
  160.                 break;   
  161.             ++ s;   
  162.         }   
  163.         if (*s == '/0')   
  164.             return t - strSrc;   
  165.         ++ t;   
  166.     }   
  167.     return 0;   
  168. }   
  169.   
  170. char *strrchr(const char *str, int c)   
  171. {   
  172.     assert(str != NULL);   
  173.     const char *s = str;   
  174.     while (*s != '/0')   
  175.         ++ s;   
  176.     for (-- s; *s != (char) c; -- s)   
  177.         if (s == str)   
  178.             return NULL;   
  179.         return (char *) s;   
  180. }   
  181.   
  182. char* strrev(char *str)   
  183. {   
  184.     assert(str != NULL);   
  185.     char *s = str, *t = str, c;   
  186.     while (*t != '/0')   
  187.         ++ t;   
  188.     for (-- t; s < t; ++ s, -- t)   
  189.     {   
  190.         c = *s;   
  191.         *s = *t;   
  192.         *t = c;   
  193.     }   
  194.     return str;   
  195. }   
  196.   
  197. char *strnset(char *str, int c, unsigned int count)   
  198. {   
  199.     assert(str != NULL);   
  200.     char *s = str;   
  201.     for (; *s != '/0' && s - str < count; ++ s)   
  202.         *s = (char) c;   
  203.     return str;   
  204. }   
  205.   
  206. char *strset(char *str, int c)   
  207. {   
  208.     assert(str != NULL);   
  209.     char *s = str;   
  210.     for (; *s != '/0'; ++ s)   
  211.         *s = (char) c;   
  212.     return str;   
  213. }   
  214.   
  215. //@heyaming  
  216. //对原 strtok 的修改,根据MSDN,strToken可以为NULL.实际上第一次call strtok给定一字串,  
  217. //再call strtok时可以输入NULL代表要接着处理给定字串。  
  218. //所以需要用一 static 保存没有处理完的字串。同时也需要处理多个分隔符在一起的情况。  
  219. char *strtok(char *strToken, const char *str)  
  220. {  
  221.     assert(str != NULL);  
  222.     static char *last;  
  223.       
  224.     if (strToken == NULL && (strToken = last) == NULL)  
  225.         return (NULL);  
  226.       
  227.     char *s = strToken;  
  228.     const char *t = str;  
  229.     while (*s != '/0')  
  230.     {  
  231.         t = str;  
  232.         while (*t != '/0')  
  233.         {  
  234.             if (*s == *t)  
  235.             {  
  236.                 last = s + 1;  
  237.                 if (s - strToken == 0) {  
  238.                     strToken = last;  
  239.                     break;  
  240.                 }  
  241.                 *(strToken + (s - strToken)) = '/0';  
  242.                 return strToken;  
  243.             }  
  244.             ++ t;  
  245.         }  
  246.         ++ s;  
  247.     }  
  248.     return NULL;  
  249. }  
  250.   
  251. char *strupr(char *str)   
  252. {   
  253.     assert(str != NULL);   
  254.     char *s = str;   
  255.     while (*s != '/0')   
  256.     {   
  257.         if (*s >= 'a' && *s <= 'z')   
  258.             *s -= 0x20;   
  259.         s ++;   
  260.     }   
  261.     return str;   
  262. }   
  263.   
  264. char *strlwr(char *str)   
  265. {   
  266.     assert(str != NULL);   
  267.     char *s = str;   
  268.     while (*s != '/0')   
  269.     {   
  270.         if (*s >= 'A' && *s <= 'Z')   
  271.             *s += 0x20;   
  272.         s ++;   
  273.     }   
  274.     return str;   
  275. }   
  276.   
  277. void *memcpy(void *dest, const void *src, unsigned int count)   
  278. {   
  279.     assert((dest != NULL) && (src != NULL));   
  280.     void *address = dest;   
  281.     while (count --)   
  282.     {   
  283.         *(char *) dest = *(char *) src;   
  284.         dest = (char *) dest + 1;   
  285.         src = (char *) src + 1;   
  286.     }   
  287.     return address;   
  288. }   
  289.   
  290. void *memccpy(void *dest, const void *src, int c, unsigned int count)   
  291. {   
  292.     assert((dest != NULL) && (src != NULL));   
  293.     while (count --)   
  294.     {   
  295.         *(char *) dest = *(char *) src;   
  296.         if (* (char *) src == (char) c)   
  297.             return ((char *)dest + 1);   
  298.         dest = (char *) dest + 1;   
  299.         src = (char *) src + 1;   
  300.     }   
  301.     return NULL;   
  302. }   
  303.   
  304. void *memchr(const void *buf, int c, unsigned int count)   
  305. {   
  306.     assert(buf != NULL);   
  307.     while (count --)   
  308.     {   
  309.         if (*(char *) buf == c)   
  310.             return (void *) buf;   
  311.         buf = (char *) buf + 1;   
  312.     }   
  313.     return NULL;   
  314. }   
  315.   
  316. int memcmp(const void *s, const void *t, unsigned int count)   
  317. {   
  318.     assert((s != NULL) && (t != NULL));   
  319.     while (*(char *) s && *(char *) t && *(char *) s == *(char *) t && count --)   
  320.     {   
  321.         s = (char *) s + 1;   
  322.         t = (char *) t + 1;   
  323.     }   
  324.     return (*(char *) s - *(char *) t);   
  325. }   
  326.   
  327. //@big:  
  328. //要处理src和dest有重叠的情况,不是从尾巴开始移动就没问题了。  
  329. //一种情况是dest小于src有重叠,这个时候要从头开始移动,  
  330. //另一种是dest大于src有重叠,这个时候要从尾开始移动。  
  331. void *memmove(void *dest, const void *src, unsigned int count)   
  332. {  
  333.     assert(dest != NULL && src != NULL);  
  334.     char* pdest = (char*) dest;  
  335.     char* psrc = (char*) src;  
  336.       
  337.     //pdest在psrc后面,且两者距离小于count时,从尾部开始移动. 其他情况从头部开始移动  
  338.     if (pdest > psrc && pdest - psrc < count)   
  339.     {  
  340.         while (count--)   
  341.         {  
  342.             *(pdest + count) = *(psrc + count);  
  343.         }  
  344.     } else   
  345.     {  
  346.         while (count--)   
  347.         {  
  348.             *pdest++ = *psrc++;  
  349.         }  
  350.     }  
  351.     return dest;  
  352. }  
  353.   
  354. void *memset(void *str, int c, unsigned int count)   
  355. {   
  356.     assert(str != NULL);   
  357.     void *s = str;   
  358.     while (count --)   
  359.     {   
  360.         *(char *) s = (char) c;   
  361.         s = (char *) s + 1;   
  362.     }   
  363.     return str;   
  364. }  
          
   测试:以上所有的函数,都待进一步测试,有任何问题,欢迎任何人随时不吝指出。

第四节、c标准库部分源代码

    为了给各位一个可靠的参考,以下,我摘取一些c标准框里的源代码,以飨各位:

  1. char * __cdecl strcat (char * dst,const char * src)  
  2. {  
  3.     char * cp = dst;  
  4.       
  5.     while( *cp )  
  6.         cp++;                   /* find end of dst */  
  7.       
  8.     while( *cp++ = *src++ ) ;       /* Copy src to end of dst */  
  9.       
  10.     return( dst );                  /* return dst */  
  11.       
  12. }  
  13.   
  14. int __cdecl strcmp (const char * src,const char * dst)  
  15. {  
  16.     int ret = 0 ;  
  17.       
  18.     while( ! (ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst)  
  19.         ++src, ++dst;  
  20.       
  21.     if ( ret < 0 )  
  22.         ret = -1 ;  
  23.     else if ( ret > 0 )  
  24.         ret = 1 ;  
  25.       
  26.     return( ret );  
  27. }  
  28.   
  29. size_t __cdecl strlen (const char * str)  
  30. {  
  31.     const char *eos = str;  
  32.       
  33.     while( *eos++ ) ;  
  34.       
  35.     return( (int)(eos - str - 1) );  
  36. }  
  37.   
  38. char * __cdecl strncat (char * front,const char * back,size_t count)  
  39. {  
  40.     char *start = front;  
  41.       
  42.     while (*front++)  
  43.         ;  
  44.     front--;  
  45.       
  46.     while (count--)  
  47.         if (!(*front++ = *back++))  
  48.             return(start);  
  49.           
  50.         *front = '/0';  
  51.         return(start);  
  52. }  
  53.   
  54. int __cdecl strncmp (const char * first,const char * last,size_t count)  
  55. {  
  56.     if (!count)  
  57.         return(0);  
  58.       
  59.     while (--count && *first && *first == *last)  
  60.     {  
  61.         first++;  
  62.         last++;  
  63.     }  
  64.       
  65.     return( *(unsigned char *)first - *(unsigned char *)last );  
  66. }  
  67.   
  68. /* Copy SRC to DEST.  */  
  69. char *  
  70. strcpy (dest, src)  
  71. char *dest;  
  72. const char *src;  
  73. {  
  74.     reg_char c;  
  75.     char *__unbounded s = (char *__unbounded) CHECK_BOUNDS_LOW (src);  
  76.     const ptrdiff_t off = CHECK_BOUNDS_LOW (dest) - s - 1;  
  77.     size_t n;  
  78.       
  79.     do  
  80.     {  
  81.         c = *s++;  
  82.         s[off] = c;  
  83.     }  
  84.     while (c != '/0');  
  85.       
  86.     n = s - src;  
  87.     (void) CHECK_BOUNDS_HIGH (src + n);  
  88.     (void) CHECK_BOUNDS_HIGH (dest + n);  
  89.       
  90.     return dest;  
  91. }  
  92.   
  93. char * __cdecl strncpy (char * dest,const char * source,size_t count)  
  94. {  
  95.     char *start = dest;  
  96.       
  97.     while (count && (*dest++ = *source++))    /* copy string */  
  98.         count--;  
  99.       
  100.     if (count)                              /* pad out with zeroes */  
  101.         while (--count)  
  102.             *dest++ = '/0';  
  103.           
  104.         return(start);  
  105. }  

有关狂想曲的修订

程序员面试题狂想曲-tctop(the crazy thinking of programers)的修订wiki(http://tctop.wikispaces.com/)已于今天建立,我们急切的想得到读者的反馈,意见,建议,以及更好的思路,算法,和代码优化的建议。所以,

  • 如果你发现了狂想曲系列中的任何一题,任何一章(http://t.cn/hgVPmH)中的错误,问题,与漏洞,欢迎告知给我们,我们将感激不尽,同时,免费赠送本blog内的全部博文集锦的CHM文件1期;
  • 如果你能对狂想曲系列的创作提供任何建设性意见,或指导,欢迎反馈给我们,并真诚邀请您加入到狂想曲的wiki修订工作中;
  • 如果你是编程高手,对狂想曲的任何一章有自己更好的思路,或算法,欢迎加入狂想曲的创作组,以为千千万万的读者创造更多的价值,更好的服务。
    Ps:狂想曲tctop的wiki修订地址为:
    http://tctop.wikispaces.com/。欢迎围观,更欢迎您加入到狂想曲的创作或wiki修订中。

版权所有,本人对本blog内所有任何内容享有版权及著作权。实要转载,请以链接形式注明出处。