前奏
有網友向我反應，之前三章（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
