首页 > 代码库 > 几个常见字符串处理函数的实现原理

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

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

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

一、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;
    }
}
Wednesday,July 09, 2014