字符串处理

　　第一节、字符串查找
　　1.1题目描述：
　　给定一个字符串A，要求在A中查找一个子串B。
　　如A="ABCDF"，要你在A中查找子串B="CD"。
　　分析：比较简单，相当于实现strstr库函数，主体代码如下：
　　//在字符串中查找指定字符串的第一次出现，不能找到则返回-1      
　　int strstr(char *string, char *substring)      
　　{     
　　if (string == NULL || substring == NULL)        
　　return -1;        
　　int lenstr = strlen(string);     
　　int lensub = strlen(substring);     
　　if (lenstr 字符串中查找第一个子串的功能，时间复杂度为O（n*m），也可以用KMP算法，复杂度为O(m+n)。具体的，在此不再赘述。
　　希望此狂想曲系列能给各位带来的是一种方法，一种创造力，一种举一反三的能力，而不是机械的只是为大家提供答案。那样的话，一切永远都只是邯郸学步，你我都无从进步（而这同时却是许多所谓的面经或面试宝典之类的书很乐意做的事，有点不解）。
　　为人打通思路，提高他人创造力，我想，这是狂想曲与其它的面试解答所不同的地方，也是我们写狂想曲系列文章的意义与价值之所在。
　　1.2、题目描述
　　在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。
　　代码则可以如下编写：
　　//查找第一个只出现一次的字符，        
　　char FirstNotRepeatChar(char* pString)     
　　{     
　　if(!pString)     
　　return'\0';     
　　constint tableSize = 256;    
　　//有点要提醒各位注意，一般常数的空间消耗，如这里的256，我们也认为此空间复杂度为O（1）。  
　　int hashTable[tableSize] = {0}; //存入数组，并初始化为0     
　　char* pHashKey = pString;     
　　while(*(pHashKey) != '\0')     
　　hashTable[*(pHashKey++)]++;     
　　while(*pString != '\0')     
　　{     
　　if(hashTable[*pString] == 1)     
　　return *pString;     
　　pString++;     
　　}     
　　return'\0';  //没有找到满足条件的字符，退出      }     代码二，bitmap：
　　# include  
　　# include  
　　constint N = 26;  
　　int bit_map[N];  
　　void findNoRepeat(char *src)  
　　{  
　　int pos;  
　　char *str = src;  
　　int i ,len = strlen(src);  
　　//统计  
　　for(i = 0 ; i 字符串开始遍历其bit_map==1 那么就是结果  
　　for(i = 0 ; i 字符串拷贝
　　题目描述：
　　要求实现库函数strcpy，
　　原型声明：externchar *strcpy(char *dest,char *src); 
　　功能：把src所指由NULL结束的字符串复制到dest所指的数组中。 
　　说明：src和dest所指内存区域不可以重叠且dest必须有足够的空间来容纳src的字符串。 
　　返回指向dest的指针。
　　分析：如果编写一个标准strcpy函数的总分值为10，下面给出几个不同得分的答案：
　　//得2分     
　　void strcpy( char *strDest, char *strSrc )     
　　{     
　　while( (*strDest++ = * strSrc++) != '\0' );     
　　}      
　　//得4分     
　　void strcpy( char *strDest, constchar *strSrc )      
　　{     
　　//将源字符串加const，表明其为输入参数，加2分     
　　while( (*strDest++ = * strSrc++) != '\0' );     
　　}      
　　//得7分      void strcpy(char *strDest, constchar *strSrc)       {          //对源地址和目的地址加非0断言，加3分     
　　assert( (strDest != NULL) && (strSrc != NULL) );     
　　while( (*strDest++ = * strSrc++) != '\0' );     
　　}      
　　//得9分     
　　//为了实现链式操作，将目的地址返回，加2分！     
　　char * strcpy( char *strDest, constchar *strSrc )      
　　{     
　　assert( (strDest != NULL) && (strSrc != NULL) );     
　　char *address = strDest;      
　　while( (*strDest++ = * strSrc++) != '\0' );      
　　return address;     
　　}    
　　//得10分，基本上所有的情况，都考虑到了  
　　//如果有考虑到源目所指区域有重叠的情况，加1分！     
　　char * strcpy( char *strDest, constchar *strSrc )      
　　{     
　　if(strDest == strSrc) { return strDest; }  
　　assert( (strDest != NULL) && (strSrc != NULL) );     
　　char *address = strDest;      
　　while( (*strDest++ = * strSrc++) != '\0' );      
　　return address;     
　　}    
　　第三节、小部分库函数的实现
　　考察此类编写同库函数一样功能的函数经常见于大大小小的IT公司的面试题目中，以下是常见的字符串库函数的实现，希望，对你有所帮助，有任何问题，欢迎不吝指正：
　　//@yansha:字串末尾要加结束符'\0'，不然输出错位结果  
　　char *strncpy(char *strDes, constchar *strSrc, unsigned int count)      
　　{      
　　assert(strDes != NULL && strSrc != NULL);      
　　char *address = strDes;      
　　while (count-- && *strSrc != '\0')      
　　*strDes++ = *strSrc++;   
　　*strDes = '\0';  
　　return address;      
　　}   
　　//查找字符串s中首次出现字符c的位置   
　　char *strchr(constchar *str, int c)   
　　{   
　　assert(str != NULL);   
　　for (; *str != (char)c; ++ str)   
　　if (*str == '\0')   
　　return NULL;   
　　return str;   
　　}   
　　int strcmp(constchar *s, constchar *t)   
　　{   
　　assert(s != NULL && t != NULL);   
　　while (*s && *t && *s == *t)   
　　{   
　　++ s;   
　　++ t;   
　　}   
　　return (*s - *t);   
　　}    char *strcat(char *strDes, constchar *strSrc)    {        assert((strDes != NULL) && (strSrc != NULL));        char *address = strDes;        while (*strDes != '\0')            ++ strDes;        while ((*strDes ++ = *strSrc ++) != '\0')            NULL;        return address;    }    int strlen(constchar *str)    {        assert(str != NULL);        int len = 0;        while (*str ++ != '\0')            ++ len;        return len;    }    //此函数，梦修改如下     
　　char *strdup_(char *strSrc)     
　　//将字符串拷贝到新的位置     
　　{     
　　if(strSrc!=NULL)     
　　{     
　　char *start=strSrc;     
　　int len=0;     
　　while(*strSrc++!='\0')     
　　len++;     
　　char *address=(char *)malloc(len+1);     
　　assert(address != NULL);  
　　while((*address++=*start++)!='\0');      
　　return address-(len+1);      
　　}     
　　return NULL;     
　　}     
　　//多谢laoyi19861011指正  
　　char *strstr(constchar *strSrc, constchar *str)   
　　{   
　　assert(strSrc != NULL && str != NULL);   
　　constchar *s = strSrc;   
　　constchar *t = str;   
　　for (; *strSrc != '\0'; ++ strSrc)   
　　{   
　　for (s = strSrc, t = str; *t != '\0' && *s == *t; ++s, ++t)   
　　NULL;   
　　if (*t == '\0')   
　　return (char *) strSrc;   
　　}   
　　return NULL;   
　　}   
　　char *strncpy(char *strDes, constchar *strSrc, unsigned int count)      
　　{      
　　assert(strDes != NULL && strSrc != NULL);      
　　char *address = strDes;      
　　while (count -- && *strSrc != '\0')      
　　*strDes ++ = *strSrc ++;      
　　*strDes = '\0';  
　　return address;      
　　}      
　　char *strncat(char *strDes, constchar *strSrc, unsigned int count)   
　　{   
　　assert((strDes != NULL) && (strSrc != NULL));   
　　char *address = strDes;   
　　while (*strDes != '\0')   
　　++ strDes;   
　　while (count -- && *strSrc != '\0' )   
　　*strDes ++ = *strSrc ++;   
　　*strDes = '\0';   
　　return address;   
　　}   
　　int strncmp(constchar *s, constchar *t, unsigned int count)   
　　{        assert((s != NULL) && (t != NULL));        while (*s && *t && *s == *t && count --)        {            ++ s;            ++ t;        }        return (*s - *t);    }    char *strpbrk(constchar *strSrc, constchar *str)    {        assert((strSrc != NULL) && (str != NULL));        constchar *s;        while (*strSrc != '\0')        {            s = str;            while (*s != '\0')            {                if (*strSrc == *s)                    return (char *) strSrc;                ++ s;            }            ++ strSrc;        }        return NULL;    }    int strcspn(constchar *strSrc, constchar *str)    {        assert((strSrc != NULL) && (str != NULL));        constchar *s;        constchar *t = strSrc;        while (*t != '\0')        {            s = str;            while (*s != '\0')            {                if (*t == *s)                    return t - strSrc;                ++ s;            }            ++ t;        }        return 0;    }    int strspn(constchar *strSrc, constchar *str)    {        assert((strSrc != NULL) && (str != NULL));        constchar *s;        constchar *t = strSrc;        while (*t != '\0')        {            s = str;            while (*s != '\0')            {                if (*t == *s)                    break;                ++ s;            }            if (*s == '\0')                return t - strSrc;            ++ t;        }        return 0;    }    char *strrchr(constchar *str, int c)    {        assert(str != NULL);        constchar *s = str;        while (*s != '\0')            ++ s;        for (-- s; *s != (char) c; -- s)            if (s == str)                return NULL;            return (char *) s;    }    char* strrev(char *str)    {        assert(str != NULL);        char *s = str, *t = str, c;        while (*t != '\0')            ++ t;        for (-- t; s = 'a' && *s = 'A' && *s  psrc && pdest - psrc  0 )           ret = 1 ;       return( ret );   }   size_t __cdecl strlen (constchar * str)   {       constchar *eos = str;       while( *eos++ ) ;       return( (int)(eos - str - 1) );   }   char * __cdecl strncat (char * front,constchar * back,size_t count)   {       char *start = front;       while (*front++)           ;       front--;       while (count--)           if (!(*front++ = *back++))               return(start);           *front = '\0';           return(start);   }   int __cdecl strncmp (constchar * first,constchar * last,size_t count)   {       if (!count)           return(0);       while (--count && *first && *first == *last)       {           first++;           last++;       }       return( *(unsigned char *)first - *(unsigned char *)last );   }   /* Copy SRC to DEST.  */   char *   strcpy (dest, src)   char *dest;   constchar *src;   {       reg_char c;       char *__unbounded s = (char *__unbounded) CHECK_BOUNDS_LOW (src);       const ptrdiff_t off = CHECK_BOUNDS_LOW (dest) - s - 1;       size_t n;       do       {           c = *s++;           s[off] = c;       }       while (c != '\0');       n = s - src;       (void) CHECK_BOUNDS_HIGH (src + n);       (void) CHECK_BOUNDS_HIGH (dest + n);       return dest;   }   char * __cdecl strncpy (char * dest,constchar * source,size_t count)   {       char *start = dest;       while (count && (*dest++ = *source++))    /* copy string */           count--;       if (count)                              /* pad out with zeroes */           while (--count)               *dest++ = '\0';            return(start);   }