程序员编程艺术：第四章、现场编写类似strstr/strcpy/strpbrk的函数
前奏
有网友向我反应，之前三章（http://t.cn/hgVPmH）的面试题目，是否有点太难了。诚如他所说，绝大部分公司的面试题不会像微软等公司的面试题目出的那么易做图，或复杂。
面试考察的是你对基础知识的掌握程度，及编程能力是否过硬的一种检测，所以，扎实基础知识，提高编程能力，比去看什么所谓的面经，或去背面试题目的答案强多了。
很多中、小型公司自己的创造能力，包括人力，物力资源都有限，所以，他们的面试题目除了copy一些大公司的题库之外（当然，考察你对基础知识的掌握情况，是肯定不会放过的），还有一个途径就是让你在限定时间内（如十分钟），当场实现一些类似strcpy/strcat/strpbrk等库函数，这个主要看你对细节的把握，以及编程能力是否之扎实了。
同时，本章里出现的代码（除了第4节的c标准库部分源码）都是个人限定在短时间内（正好，突出现场感）编写的，很多问题，难免有所考虑不周。所以，如果你发现本章任何一段代码有任何问题，恳请不吝指正。
第一节、字符串查找
1.1题目描述：
给定一个字符串A，要求在A中查找一个子串B。
如A="ABCDF"，要你在A中查找子串B=“CD”。
分析：比较简单，相当于实现strstr库函数，主体代码如下：
view plaincopy to clipboardprint?
//在字符串中查找指定字符串的第一次出现，不能找到则返回-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;
for (int i = 0; i <= len; i++) //复杂度为O(m*n)
{
for (int j = 0; j < lensub; j++)
{
if (string[i+j] != substring[j])
break;
}
if (j == lensub)
return i + 1;
}
return -1;
}
上述程序已经实现了在字符串中查找第一个子串的功能，时间复杂度为O（n*m），也可以用KMP算法，复杂度为O(m+n)。具体的，在此不再赘述。
希望此狂想曲系列能给各位带来的是一种方法，一种创造力，一种举一反三的能力，而不是机械的只是为大家提供答案。那样的话，一切永远都只是邯郸学步，你我都无从进步（而这同时却是许多所谓的面经或面试宝典之类的书很乐意做的事，有点不解）。
为人打通思路，提高他人创造力，我想，这是狂想曲与其它的面试解答所不同的地方，也是我们写狂想曲系列文章的意义与价值之所在。
1.2、题目描述
在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。
代码则可以如下编写：
view plaincopy to clipboardprint?
//查找第一个只出现一次的字符，
//copyright@ yansha
//July、updated，2011.04.24.
char FirstNotRepeatChar(char* pString)
{
if(!pString)
return ;
const int tableSize = 256;
//有点要提醒各位注意，一般常数的空间消耗，如这里的256，我们也认为此空间复杂度为O（1）。
int hashTable[tableSize] = {0}; //存入数组，并初始化为0
char* pHashKey = pString;
while(*(pHashKey) != )
hashTable[*(pHashKey++)]++;
while(*pString != )
{
if(hashTable[*pString] == 1)
return *pString;
pString++;
}
return ; //没有找到满足条件的字符，退出
}
代码二，bitmap：
view plaincopy to clipboardprint?
# 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("
");
return 0;
}
第二节、字符串拷贝
题目描述：
要求实现库函数strcpy，
原型声明：extern char *strcpy(char *dest,char *src);
功能：把src所指由NULL结束的字符串复制到dest所指的数组中。
说明：src和dest所指内存区域不可以重叠且dest必须有足够的空间来容纳src的字符串。
返回指向dest的指针。
分析：如果编写一个标准strcpy函数的总分值为10，下面给出几个不同得分的答案：
view plaincopy to clipboardprint?
//得2分
void strcpy( char *strDest, char *strSrc )
{
while( (*strDest++ = * strSrc++) != );
}
//得4分
void strcpy( char *strDest, const char *strSrc )
{
//将源字符串加const，表明其为输入参数，加2分
while( (*strDes
补充：软件开发 , C语言 ,
