首页 > 代码库 > 几个常见字符串处理函数的实现原理
几个常见字符串处理函数的实现原理
字符串是一种常见的数据结构,对字符串的处理又可以十分灵活,所以在实际开发,尤其是非数值处理中,字符串的应用非常广泛。虽然很多字符串操作都封装在了函数库里,应用程序可以直接通过调用库函数来实现字符串处理,然而对于开发者而言,若能了解其底层实现原理,对于应用编程而言还是大有裨益的。
这篇文章主要介绍几种常用的字符串处理函数的实现原理。
一、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; } }