几个常见字符串处理函数的实现原理

字符串是一种常见的数据结构，对字符串的处理又能够十分灵活，所以在实际开发，尤其是非数值处理中，字符串的应用非常广泛。尽管非常多字符串操作都封装在了函数库里，应用程序能够直接通过调用库函数来实现字符串处理，然而对于开发人员而言，若能了解其底层实现原理，对于应用编程而言还是大有裨益的。

这篇文章主要介绍几种经常使用的字符串处理函数的实现原理。

一、strlen函数

strlen函数：计算字符串的实际长度，不包含’\0’。

算法：从第一个字符開始扫描，直到遇见第一个’\0’，停止扫描，返回字符串长度。

代码例如以下：

int strlen(const char *str)
{	
        int n=0;
        assert(str!=NULL);
        while(*str++!='\0')
	        ++n;
        return n;
}

二、strcat函数

strcat函数：将源字符串str2加入到目的字符串str1的末尾，同一时候覆盖str1末尾的’\0’，并在新的str1末尾加入’\0’，返回指向str1的指针。

算法：扫描str1，直到遇见’\0’，将str2逐个字符加入到str1末尾，最后加入’\0’。

代码例如以下：

char *strcat(char *str1, const char *str2)
{
	char *p=str1;
	assert( (str1!=NULL) && (str2!=NULL) ); 
	while(*str1!='\0')
		str1++;
	while(*str1++=*str2++);
	return p;
}

三、strcmp函数

strcmp函数：比較str1和str2两个字符串的大小，若str1>str2，则返回正数；若str1<str2，则返回负数；若str1==str2，则返回0。

算法：逐个比較str1和str2的每一个字符，若相等且未遇见’\0’，则继续比較下一个字符，否则，返回*str1和*str2的差值。

代码例如以下：

int strcmp(const char *str1, const char *str2)
{	
	assert( (str1!=NULL) && (str2!=NULL) );
	while(*str1 && *str2&& (*str1==*str2)) 
	{
		str1++;
		str2++;
	}
	return *str1 - *str2;
}

四、strcpy函数

strcpy函数：将字符串str2（包含NULL）拷贝到字符串str1，返回指向str1的指针。

算法：将str2中逐个字符加入到str1指向的地址空间，必须保证str1指向的地址空间足够大。

代码例如以下：

char *strcpy(char *str1, const char *str2) 
{	
	char *p=str1;
	assert( (str1!=NULL) && (str2!=NULL) );
	while(*str1++=*str2++);
	return p; 
}

五、atoi函数

atoi函数：把字符串转换成整数。

算法：首先跳过空格或制表符，再推断符号，最后通过减去’0’转化整数，跳过非数值，返回转换后的整数。

代码例如以下：

int atoi(char *str)
{
	int sum=0,sign=1;
	char *p=str;
	assert(str!=NULL);
	if(' '==*p||'\t'==*p)
		p++;
	if('-'==*p)
		sign=-1;
	if('-'==*p||'+'==*p)
		p++;
	while(*p>='0' && *p<='9')
	{
		sum = sum*10 + *p-'0';
		p++;
	}
	return sign*sum;
}

六、itoa函数

itoa函数：将整数转化为字符串。

算法：先推断整数的符号，若为负，则将其转换为正；将整数从个位到最高位依次存放在暂时数组tmp中，假设是负整数，则再加入一个负号；逆序将暂时数组的各个元素放在str字符数组中，在最后加入一个空字符。

代码例如以下：

void itoa(int num, char str[])
{
	int i=0,j=0,sign=num;
	char tmp[10];
	if(num<0)
		num=-num;	
	do					
	{
		tmp[i++]=num%10 + '0';
		num/=10;
	}while(num>0);
	if(sign<0)
		tmp[i++]='-';
	tmp[i]='\0';
	i--;
	while(i>=0)	
	{
		str[j]=tmp[i];
		j++;
		i--;
	}
	str[j]='\0';
}

另：替换子串问题

非常多时候会碰到要求替换字符串中的子串，这时须要考虑几个问题：

1、  溢出问题

假设题目要求在原字符串中替换，这时就要考虑替换后字符串的长度是否会大于设定的长度；假设能够新建一个字符串，那么用户能够自行设定大小，这样一般不存在溢出问题。

2、  待替换子串和替换子串的长度比較，将终于影响字符串的长度变化。

这里以以下一个题目为例：

题目：请实现一个函数，把字符串中的每一个空格替换成“%20”，比如输入“We are happy.”，则输出“We%20are%20happy.”。

解法一：新建一个字符串来存放替换后的字符串；

代码例如以下：

#include<stdio.h>
int main()//直接main函数实现
{
	char str[20]="we are happy." ,str1[30]="\0";
	char *p=str;
	int i=0;
	while(*p!='\0')
	{
		if(*p!=' ')
			str1[i++]=*p++;
		else
		{
			str1[i++]='%';
			str1[i++]='2';
			str1[i++]='0';
			p++;
		}
	}
	printf("str1=%s\n",str1);
	return 0;
}

解法二：在原字符串上替换，从后往前替换空格；

代码例如以下：

void ReplaceBlank(char string[], int length)
{
    if(string == NULL && length <= 0)
        return;

    /*originalLength 为字符串string的实际长度*/
    int originalLength = 0;
    int numberOfBlank = 0;
    int i = 0;
    while(string[i] != '\0')
    {
        ++ originalLength;

        if(string[i] == ' ')
            ++ numberOfBlank;

        ++ i;
    }

    /*newLength 为把空格替换成'%20'之后的长度*/
    int newLength = originalLength + numberOfBlank * 2;
    if(newLength > length)
        return;

    int indexOfOriginal = originalLength;
    int indexOfNew = newLength;
    while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
    {
        if(string[indexOfOriginal] == ' ')
        {
            string[indexOfNew --] = '0';
            string[indexOfNew --] = '2';
            string[indexOfNew --] = '%';
        }
        else
        {
            string[indexOfNew --] = string[indexOfOriginal];
        }

        -- indexOfOriginal;
    }
}