字符串处理

　　第一节、字符串查找
　　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); }