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

               第四章、现场编写类似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内所有任何内容享有版权及著作权。实要转载，请以链接形式注明出处。