自己实现字符串操作函数
在C语言中，字符串有一个标准的C库来处理字符串操作。平时编程的时候，只需要调用它们而不用关心其具体实现。然而，很多知名的软件公司很爱考查大家一些字符串的问题，其中就包括了一些常见的C库字符串操作函数的具体实现。比如，笔者本人就被考查过strstr()、strtok()、reversestr()、strcpy()等。现在，就把这些典型的字符串操作函数提出来讨论和实现。大家会发现，如果能够自己去实现这些函数，对编程能力的提高有很大的帮助。顺便提及的是，在C语言中，字符串以’\
6.10.1 实现strstr()
在C语言里strstr()的原型为：char *strstr(char *s1, char *s2)，它的功能是从字符串s1中寻找s2第一次出现的位置（不比较结束符NULL)。
/* 算法1：普通算法 */
char * _strstr
(
const char * str1,
const char * str2
)
{
char *cp = (char *) str1;
char *s1, *s2;
if (str1== NULL || str2==NULL)
return NULL;
if ( !*str2 )
return((char *)str1);
while (*cp)
{
s1 = cp;
s2 = (char *) str2;
while ( *s1 && *s2 && !(*s1-*s2) )
s1++, s2++;
if (!*s2)
return(cp);
cp++;
}
return(NULL);
}
6.10.2 实现strtok()
在C语言中，strtok()的原型为：char *strtok(char *s, char *delim)，它的功能为：分解字符串为一组字符串。s为要分解的字符串，delim为分隔符字符串。由于此函数的功能比较难理解，在给出实现算法前先看看它的具体使用例子：
#include <string.h>
#include <stdio.h>
int main(void)
{
char s[]
= "Nice to meet you!";
char *d
= " ";
char *p
= NULL;
p=strtok(s,d);
while(p)
{
printf("%s\n",p);
p = strtok(NULL,d);
}
getchar();
return 0;
}
那么函数执行的结果是字符串s将会被空格字符分隔为”Nice” “to” “meet” “you!”4个字符串。下面来实现strtok()的算法：
char * strtok (char * string, const char * control)
{
char *str;
const char *ctrl
= control;
/* map为一个256位数组位图，用来标记分隔字符串中的每个字符 */
char map[32];
int count;
/*
* nextoken为static类型，static类型具有记忆功能，下此执行此函数时，
* 其值依然有效。因此它记住了程序执行过程中字符串的下一个位置
*/
static char *nextoken;
//将位图数组初始化为0
for (count = 0; count < 32; count++)
map[count] = 0;
//将分隔字符串对应的那位设置为1
do
{
map[*ctrl >> 3] |= (1 << (*ctrl & 7));
} while (*ctrl++);
if (string)
str = string;
else
str = nextoken;
//如果字符串开始都为分隔字符，忽略
while ( (map[*str >> 3] & (1 << (*str & 7))) && *str )
str++;
string = str;
for ( ; *str ; str++ )
{
//如果字符串中的字符为分隔字符，则进行分隔
if ( map[*str >> 3] & (1 << (*str & 7)) )
{
//在此位置用’\
*str++ = '\0';
break;
}
}
//用static变量记住下一个分隔的起始点
nextoken = str;
//返回分隔后的字符串
if ( string == str )
return NULL;
else
return string;
}
6.10.3 实现strcpy()
在C语言中，strcpy()的原型：char *strcpy(char *dest,char *src)，它的功能是把src所指由NULL结束的字符串复制到dest所指的数组中。下面是实现的strcpy()函数：
char *strcpy(char *strDest, const char *strSrc)
{
assert( (strDest!=NULL) && ( strSrc!=NULL));
if ( strDest == strSrc)
return strDest ;
char *pDest = strDest ;
char *pSrc =strSrc;
while( (*pDest ++ = *pSrc ++) != '\0')
;
//*pDest = ‘\
return strDest;
}
6.10.4 实现strcmp()
在C语言中strcmp()的原型：int strcmp(char *s1,char * s2)，它的功能：比较字符串s1和s2：
当s1<s2时，返回值<0
当s1=s2时，返回值=0
当s1>s2时，返回值>0
下面是对strcmp()的一个实现：
int strcmp(char* str1, char* str2)
{
while(*str1 && *str2 && *str1==*str2)
{
++str1;
++str2;
}
return *str1-*str2;
}
6.10.5 实现tolower()
在C语言中tolower()的原型：char tolower(char ch)，它的功能为：将大写字母转换为小写字母。下面给出它的实现算法：
/* 算法1
*/
char tolower(char ch)
{
/* 加入ASSERT断言，要求输入必须为大写字母 */
ASSERT(ch >= ‘A’ && ch <= ‘Z’);
return (ch + ‘a’ – ‘A’);
}
另外一种实现：当输入为大写字母时将其转换为小写字母。否则返回原来的字母。这更加符合函数的实际使用情况。
/* 算法2
*/
char tolower(char ch)
{
if (ch >= ‘A’ && ch <= ‘Z’)
return (ch + ‘a’ – ‘A’);
else
return ch;
}
6.10.6 删除特定字符或字符组
将一个字符串中某个特定字符删除。要求不能增加额外的存储和较高的效率。
void DeleteChar(char *str, char c)
{
assert(str != NULL);
int iDes = 0, iSrc = 0;
do
{
if (str[iSrc] != c)
str[iDes++] = str[iSrc];
} while(str[iSrc++] != ‘\
}
如果删除的为一个特定的字符组，那么算法又该如何写呢？
void DeleteChars(char *str, char chr[], int n)
{
assert(str != NULL);
char tmp[256] = {0};
for (int i = 0; i < n; i++)
{
tmp[chr[i]] = 1;
}
int iDes = 0, iSrc = 0;
do
{
if (!tmp[str[iSrc]])
str[iDes++] = str[iSrc];
} while(str[iSrc++] != ‘\
}
此算法的关键之一在于设置了标记读写位置的变量，这样不用增加额外的内存空间和重复的拷贝，直接在给定的空间实现了算法。关键之二在于用一个数组来记录待删除的字符组，有利于对待删除的字符进行查找和判定。
6.10.7 识别字符串中单词
int GetWordNum(const char *str)
{
asssert(str != NULL);
int num;
char *pChar = str;
while (*pChar != ‘\
{
if (*pChar != ‘\
char *pBegin = pChar;
while (*pChar != ‘
‘ && *pChar++ != ‘\
;
char *pEnd = pchar--;
num++;
pChar++;
}
return num;
}
英语单词是通过字母间的空格来进行区别的。因此，设置两个位置指针，一个为pBegin，一个为pEnd, pBegin与pEnd之间就是要统计的单词。
6.10.8 逆置字符串
将一个字符串逆置。比如将”hello, world”逆置后为”dlrow ,olleh”。
void ReverseString(char * str)
{
int n;
char
c;
n = strlen(str);
for
(int i = 0; i < n/2; i++)
{
c = str[i];
str[i] = str[n-1-i];
str[n-1-i] = c;
}
}
按照单词的顺序将字符串逆置
6.10.9 实现memcpy()
函数memcpy()与strcpy()不同，需要考虑内存重叠的可能。如图3-1所示，pSrc与pDst的位置可能存在4种可能关系。其中当(pSrc<pDst) && ((char*)pSrc+size > pDst)时，如果拷贝是从头开始正向拷贝，就会在拷贝过程中污染pSrc中还未拷贝的数据。因此，在这种情况下必须反向拷贝。
图 pSrc与pDst的相对位置关系
void memcpy(void *pDst,const void *pSrc, size_t size)
{
assert(pDst != NULL);
assert(pSrc != NULL);
/* pSrc与pDst共享同一块内存区域 */
if((pSrc<pDst) && ((char*)pSrc+size > pDst))
{
char *pstrSrc= (char *)pSrc + size -1;
char *pstrDst = (char *)pDst + size -1;
/ * 从尾部逆向拷贝 */
while(size--)
*pstrDst -- = *pstrSrc--;
}
else
{
char *pstrSrc= (char *)pSrc ;
char *pstrDst = (char *)pDst ;
/* 从起始部正向拷贝 */
while(size--)
*pstrDst++ = *pstrSrc++;
}
}
6.10.10 IP字符串与整数的转化
本人亲临的微软的面试题之一。题意为：将IP地址字符串与32位整数进行互相转化，其中不能应用strtok()等C库函数。下面为代码的实现：
//输入为一个常量IP字符串
//输出为一个32位整数
int ipstr2int(const char *ip, unsigned int *ipvalue)
{
if (ip == NULL || ipvalue==NULL)
return -1;
unsigned int result
= 0;
int tmp
= 0;
int shift
= 24;
const char *pEnd = ip;
const char *pStart = ip;
while(*pEnd != '\0')
{
//找到地址符里的’.’
while(*pEnd != '.' && *pEnd != '\0')
pEnd++;
tmp = 0;
//计算每个’.’之间的数值"192"-->192
//atoi
while(pStart < pEnd)
{
tmp = tmp * 10 + (*pStart - '0');
pStart++;
}
if(tmp<0 || tmp >255)
{
return -1;
}
//将计算好的数值分别左移24位，16位，8位，0位
result += (tmp << shift);
shift -= 8;
if (*pEnd == '\0')
break;
pStart = pEnd + 1;
pEnd++;
}
*ipvalue = result;
return 1;
}
32位整数中，每个字节对应了IP地址中的一个部分。因此，要实现IP整数对IP地址字符串的转换，只需要获得整数的每个字节并做相应的转换。
//不使用库函数将32位整数转化为IP字符串
//0x12 34 56 78-->“18.52.86.120”
int ip2str(unsigned int ip, char *buf, size_t len)
{
if(buf == NULL || len<16)
{
return -1;
}
size_t length = sizeof(ip);//32位ip地址的字节数
unsigned char *p = (unsigned char
*)&ip+sizeof(ip)-1;//指向ip地址最高字节
char *p1 = buf;
while(length)
{
unsigned char tmp = *p;
char *pstart= p1;
//18-->'81'
do
{
*p1++ = tmp%10 +'0';
tmp /= 10;
}while(tmp);
char *pend = p1-1;
//'81'-->'18'
for(;pstart<pend;pstart++,pend--)
{
char ch = *pstart;
*pstart = *pend;
*pend=ch;
}
if(length>1)
*p1++ = '.';
length--;
p--;
}
*p1 ='\0';
return 1;
}
int ip2str(unsigned int ip, char *buf, size_t len)
{
if(buf==NULL ||len<16)
{
return -1;
}
unsigned char *p = (unsigned char *)&ip;
sprintf(buf, "%u.%u.%u.%u",
*(p+3),*(p+2),*(p+1),*(p));
return 0;
}
int _tmain(int argc, _TCHAR* argv[])
{
char ip1[16];
char ip2[16];
ip2str(0x12345678, ip1, 16);
printf("ip:%s\n", ip1);
iptostr(0x12345678,ip2, 16);
printf("ip:%s\n", ip2);
ip2str(0xffffffff, ip1, 16);
printf("ip:%s\n", ip1);
return 0;
