跪求C语言中字符串函数实现原理

    小弟最近参加一个C语言软件设计师的面试，让自己编写关于字符串操作的一些库函数，比如：字符串拷贝strcpy(),内存拷贝memcpy(),字符串连接函数strcat，等等。希望给我大虾给予相关的函数实现，最好是有注释或者算法实现的原理。
   小弟定感激不尽！

17 个解决方案

#1

建议LZ可以去看看《数据结构》

#2

搜google code

// strcpy
#include <string.h>

char *
strcpy(char *to, const char *from)
{
	char *save = to;

	for (; (*to = *from) != '\0'; ++from, ++to);
	return(save);
}

#3

char * strcat(char * dest, const char * src)
{
        char *tmp = dest;

        while (*dest)
                dest++;
        while ((*dest++ = *src++) != '\0')
                ;

        return tmp;
}

#4

引用 2 楼 delphiwcdj 的回复:

搜google code

C/C++ code

// strcpy
#include <string.h>

char *
strcpy(char *to, const char *from)
{
    char *save = to;

    for (; (*to = *from) != '\0'; ++from, ++to);
    return(save……

或者下个glibc的源码看看；或者装上VS2005找它的C:\Program Files\Microsoft Visual Studio 8\VC\crt\src目录，下面有常见库函数的实现。

#5

char * __cdecl strcat (
        char * dst,
        const char * src
        )
{
        char * cp = dst;

        while( *cp )
                cp++;                   /* find end of dst */

        while( *cp++ = *src++ ) ;       /* Copy src to end of dst */

        return( dst );                  /* return dst */

}


/***
*char *strcpy(dst, src) - copy one string over another
*
*Purpose:
*       Copies the string src into the spot specified by
*       dest; assumes enough room.
*
*Entry:
*       char * dst - string over which "src" is to be copied
*       const char * src - string to be copied over "dst"
*
*Exit:
*       The address of "dst"
*
*Exceptions:
*******************************************************************************/

char * __cdecl strcpy(char * dst, const char * src)
{
        char * cp = dst;

        while( *cp++ = *src++ )
                ;               /* Copy src over dst */

        return( dst );
}


char * __cdecl strchr (
        const char * string,
        int ch
        )
{
        while (*string && *string != (char)ch)
                string++;

        if (*string == (char)ch)
                return((char *)string);
        return(NULL);
}



int __cdecl strcmp (
        const char * src,
        const char * dst
        )
{
        int ret = 0 ;

        while( ! (ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst)
                ++src, ++dst;

        if ( ret < 0 )
                ret = -1 ;
        else if ( ret > 0 )
                ret = 1 ;

        return( ret );
}

size_t __cdecl strnlen(const char *str, size_t maxsize)
{
    size_t n;

    /* Note that we do not check if s == NULL, because we do not
     * return errno_t...
     */

    for (n = 0; n < maxsize && *str; n++, str++)
        ;

    return n;
}



size_t __cdecl strlen (
        const char * str
        )
{
        const char *eos = str;

        while( *eos++ ) ;

        return( eos - str - 1 );
}


errno_t __cdecl strcpy_s(_CHAR *_DEST, size_t _SIZE, const _CHAR *_SRC)
{
    _CHAR *p;
    size_t available;

    /* validation section */
    _VALIDATE_STRING(_DEST, _SIZE);
    _VALIDATE_POINTER_RESET_STRING(_SRC, _DEST, _SIZE);

    p = _DEST;
    available = _SIZE;
    while ((*p++ = *_SRC++) != 0 && --available > 0)
    {
    }

    if (available == 0)
    {
        _RESET_STRING(_DEST, _SIZE);
        _RETURN_BUFFER_TOO_SMALL(_DEST, _SIZE);
    }
    _FILL_STRING(_DEST, _SIZE, _SIZE - available + 1);
    _RETURN_NO_ERROR;
}





#ifdef _DEBUG

#include <crtdbg.h>

char * __cdecl _strdup (
        const char * string
        )
{
        return _strdup_dbg(string, _NORMAL_BLOCK, NULL, 0);
}

char * __cdecl _strdup_dbg (
        const char * string,
        int nBlockUse,
        const char * szFileName,
        int nLine
        )

#else  /* _DEBUG */

char * __cdecl _strdup (
        const char * string
        )

#endif  /* _DEBUG */

{
        char *memory;
    size_t size = 0;

        if (!string)
                return(NULL);

    size = strlen(string) + 1;
#ifdef _DEBUG
        if (memory = _malloc_dbg(size, nBlockUse, szFileName, nLine))
#else  /* _DEBUG */
        if (memory = malloc(size))
#endif  /* _DEBUG */
        {
                _ERRCHECK(strcpy_s(memory, size, string));
        return memory;
        }

        return(NULL);
}


char * __cdecl strncpy (
        char * dest,
        const char * 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);
}



char * __cdecl strstr (
        const char * str1,
        const char * str2
        )
{
        char *cp = (char *) str1;
        char *s1, *s2;

        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);

}









char * __cdecl _strrev (
        char * string
        )
{
        char *start = string;
        char *left = string;
        char ch;

        while (*string++)                 /* find end of string */
                ;
        string -= 2;

        while (left < string)
        {
                ch = *left;
                *left++ = *string;
                *string-- = ch;
        }

        return(start);
}



char * __cdecl strrchr (
        const char * string,
        int ch
        )
{
        char *start = (char *)string;

        while (*string++)                       /* find end of string */
                ;
                                                /* search towards front */
        while (--string != start && *string != (char)ch)
                ;

        if (*string == (char)ch)                /* char found ? */
                return( (char *)string );

        return(NULL);
}

#6

这都不会别面试了。。。

#7

GOOGLE一大把

#8

引用 7 楼 nanchangniat 的回复:

GOOGLE一大把

你就先g一把吧，多得很。先死记硬背下来再说。

#9

char * strcat(char * dest, const char * src)
{
  char *mydest = dest;  
  char *myscr = src;

  while (*mydest++ = *mysrc++)

  return dest;  
 }

#10

C语言中strcpy,strcmp,strlen,strcat函数原型
今天去文思创新面试，考官问了我一个简单的实现，即：自己编写strcpm的实现，IBM曾经也考过写strcpy原型，这几个函数在面试的时候经常被考到，很具有代表性，突然被问起还真有点措手不及呢。现在记下供大家学习和以后温习：（下面的程序经本人通过）

1、Strcat函数原型如下：
char *strcat(char *strDest, const char *strScr) //将源字符串加const，表明其为输入参数
{
       char * address = strDest;             //该语句若放在assert之后，编译出错
       assert((strDest != NULL) && (strScr != NULL)); //对源地址和目的地址加非0断言
       while(*strDest)             //是while(*strDest!=’\0’)的简化形式
       {                        //若使用while(*strDest++)，则会出错，因为++是不受循环
              strDest++;               //约束的。所以要在循环体内++；因为要是*strDest最后指
       }                        //向该字符串的结束标志’\0’。
       while(*strDest++ = *strScr++) 
       {
              NULL;                 //该循环条件内可以用++，
       }                          //此处可以加语句*strDest=’\0’;有无必要？
return address;               //为了实现链式操作，将目的地址返回
}
以下是在VC6.0中调试的例子，函数名用strcata代替。
#include <stdio.h>
#include <assert.h>
char *strcata(char *strDest,const char *strScr)
{
       char * address = strDest;
       assert((strDest != NULL) && (strScr != NULL));
       while(*strDest)
       {
              strDest++;
       }
       while(*strDest++ = *strScr++)
       {
              NULL;
       }
       return address;
}

void main()
{
       char str1[100]={"i love"};
       char str2[50]={"China"};
       printf("%s\n",strcata(str1,str2));
}
2、Strcpy函数原型如下：
char *strcpy(char *strDest, const char *strScr)
{
       char *address=strDest;
       assert((strDest != NULL) && (strScr != NULL));
       while(*strScr)                   //是while(*strScr != ’\0’)的简化形式；
       {
              *strDest++ = *strScr++;
       }
       *strDest = '\0';                       //当strScr字符串长度小于原strDest字符串长度
       return address;                      //时，如果没有改语句，就会出错了。
}
以下是在VC6.0中调试的例子，函数名用strcpya代替。
#include <stdio.h>
#include <assert.h>
char *strcpya(char *strDest, const char *strScr)
{
       char *address = strDest;
       assert((strDest != NULL) && (strScr != NULL));
       while(*strScr)
       {
              *strDest++ = *strScr++;
       }
       *strDest = '\0';
       return address;
}

void main()
{
       char str1[100]={"i love"};
       char str2[50]={"China"};
       printf("%s\n",strcpya(str1,str2));
}
3、Strcmp函数原型如下：
int strcmp (const char *str1,const char *str2)
{           
       int len = 0;
       assert((str1 != '\0') && (str2 != '\0'));
       while(*str1 && *str2 && (*str1 == *str2))
       {
              str1++;
              str2++;
       }
       return *str1-*str2;
}
以下是在VC6.0中调试的例子，函数名用strcmpa代替。
#include <stdio.h>
#include <assert.h>
int strcmpa (const char *str1,const char *str2)
{           
       int len = 0;
       assert((str1 != '\0') && (str2 != '\0'));
       while(*str1 && *str2 && (*str1==*str2))
       {
              str1++;
              str2++;
       }
       return *str1-*str2;
}

void main()
{
       char str1[100] = {"i love"};
       char str2[50] = {"China "};
       printf("%d\n",strcmpa(str1,str2));
}
4、Strlen函数原型如下：
int strlen(const char *str)
{
    int len = 0;
       assert(str != NULL);
       while(*str++)
       {
              len++;
       }
       return len;
}
以下是在VC6.0中调试的例子，函数名用strlena代替。
#include <stdio.h>
#include <assert.h>
int strlena(const char *str)
{
    int len = 0;
       assert(str != NULL);
       while(*str++)
       {
              len++;
       }
       return len;
}
void main()
{
       char str1[100] = {"i love"};
       char str2[50] = {"China "};
       printf("%d\n",strlena(str1));
}

#11

C语言字符串操作函数 - strcpy、strcmp、strcat、反转、回文
C语言字符串操作函数 

1. 字符串反转 - strRev
2. 字符串复制 - strcpy
3. 字符串转化为整数 - atoi
4. 字符串求长 - strlen
5. 字符串连接 - strcat
6. 字符串比较 - strcmp
7. 计算字符串中的元音字符个数
8. 判断一个字符串是否是回文

1. 写一个函数实现字符串反转

版本1 - while版

void strRev(char *s)
{
    char temp, *end = s + strlen(s) - 1;
    while( end > s)
    {
        temp = *s;
        *s = *end;
        *end = temp;
        --end;
        ++s;
    }
}

版本2 - for版

void strRev(char *s)
{
    char temp;
    for(char *end = s + strlen(s) - 1; end > s ; --end, ++s)
    {
        temp = *s;
        *s = *end;
        *end = temp;
    }
}

版本3 - 不使用第三方变量

void strRev(char *s)
{
    for(char *end = s + strlen(s) - 1; end > s ; --end, ++s)
    {
        *s ^= *end;
        *end ^= *s;
        *s ^= *end;
    }
} 

版本4 - 重构版本3

void strRev(char *s)
{
    for(char *end = s + strlen(s) - 1; end > s ; --end, ++s)
    {
        *s ^= *end ^= *s ^= *end;
    }
}

版本5 - 重构版本4

void strRev(char *s)
{
    for(char *end = s + strlen(s) - 1; end > s ; *s++ ^= *end ^= *s ^= *end--);
}

版本6 - 递归版

void strRev(const char *s)
{
    if(s[0] == '\0')
        return;
    else
        strRev(&s[1]);
    printf("%c",s[0]);
}


2. 实现库函数strcpy的功能

strcpy函数位于头文件<string.h>中

版本1

strcpy(char * dest, const char * src)
{
    char *p=dest;
    while(*dest++ = *src++)
        ;
    dest=p;
}

版本2

char * __cdecl strcpy(char * dst, const char * src)
{
    char *p = dst;
    while( *p ++ = *src ++ )
        ;
    return dst;
}


版本3

strcpy(char * dest, const char * src)
{
    int i=0;
    for(; *(src+i)!='\0'; i++)
        *(dest+i) = *(src+i);
    *(dest+i) = '\0';
}


3. 实现库函数atoi的功能

atoi函数位于头文件<stdlib.h>中

版本1 - 附说明

int power(int base, int exp)
{
    if( 0 == exp )
        return 1;
    return base*power(base, exp-1);
}

int __cdecl atoi(const char *s)
{
    int exp=0, n=0;
    const char *t = NULL;
    
    for(; *s == ' ' || *s == '\t' || *s == '\n'; s++) //找到第一个非空字符
        ;
    if( *s >'9' || *s <'0' ) //如果第一个非空字符不是数字字符，返回0
        return 0;
    
    for(t=s; *t >='0' && *t <='9'; ++t) //找到第一个非数字字符位置 - 方法1
        ;
    t--;

    /* 找到第一个非数字字符位置 - 方法2
    t=s;
    while(*t++ >='0' && *t++ <='9')
        ;
    t -= 2;
    */

    while(t>=s)
    {
        n+=(*t - 48)*power(10, exp); //数字字符转化为整数
        t--;
        exp++;
    }
    return n;
}

版本2

int __cdecl atoi(const char *s)
{
    int exp=0, n=0;
    const char *t = NULL;
    
    for(; *s == ' ' || *s == '\t' || *s == '\n'; s++) //略过非空字符
        ;
    if( *s >'9' || *s <'0' )
        return 0;
    
    for(t=s; *t >='0' && *t <='9'; ++t)
        ;
    t--;

    while(t>=s)
    {
        n+=(*t - 48)*pow(10, exp);
        t--;
        exp++;
    }
    return n;
}


4. 实现库函数strlen的功能

strlen函数位于头文件<string.h>中

版本1 - while版

size_t  __cdecl strlen(const char * s)
{
    int i = 0;
    while( *s )
    {
        i++;
        s++;
    }
    return i;
}

版本2 - for版

size_t  __cdecl strlen(const char * s)
{
    for(int i = 0; *s; i++, s++)
        ;
    return i;
}

版本3 - 无变量版

size_t  __cdecl strlen(const char * s)
{
    if(*s == '\0')
        return 0;
    else
        return (strlen(++s) + 1);
}

版本4 - 重构版本3

size_t  __cdecl strlen(const char * s)
{
    return *s ? (strlen(++s) + 1) : 0;
}


5. 实现库函数strcat的功能

strcat函数位于头文件<string.h>中

版本1 - while版

char * __cdecl strcat(char * dst, const char * src)
{
    char *p = dst;
    while( *p )
        p++;
    while( *p ++ = *src ++ )
        ;
    return dst;
}



6. 实现库函数strcmp的功能

strcmp函数位于头文件<string.h>中

版本1 - 错误的strcmp

int strcmp(const char * a, const char * b)
{
    for(; *a !='\0' && *b !='\0'; a++, b++)
        if( *a > *b)
            return 1;
        else if ( *a==*b)
            return 0;
        else
            return -1;
}

版本2

int __cdecl strcmp (const char * src, const char * dst)
{
        int ret = 0 ;

        while( ! (ret = *(unsigned char *)src - *(unsigned char *)dst) && *src)
                ++src, ++dst;

        if ( ret < 0 )
                ret = -1 ;
        else if ( ret > 0 )
                ret = 1 ;

        return( ret );
}



7. 计算字符串中元音字符的个数


#include <stdio.h>

int is_vowel(char a)
{
    switch(a)
    {
    case 'a': case 'A':
    case 'e': case 'E':
    case 'i': case 'I':
    case 'o': case 'O':
    case 'u': case 'U':
        return 1; break;
    default: 
        return 0; break;
    }
}

int count_vowel(const char *s)
{
    int num;
    if(s[0] == '\0')
        num = 0;
    else
    {
        if(is_vowel(s[0]))
            num = 1 + count_vowel(&s[1]);
        else
            num = count_vowel(&s[1]);
    }
    return num;
}

int main()
{
    char *s=" AobCd ddudIe";
    printf("%d \n", count_vowel(s));
    return 0;
}


8. 判断一个字符串是否回文：包含一个单词，或不含空格、标点的短语。如：Madam I'm Adam是回文

版本1

/*
 * 程序功能：判断一个单词，或不含空格、标点符号的短语是否为回文(palindrome)
 */
#include <stdio.h>
#include <ctype.h>

int is_palindrome(const char *s)
{
    bool is_palindrome=0;
    const char *end=s;

    if(*end == '\0') /* 如果s为空串，则是回文 */
        is_palindrome=1;

    while(*end) ++end; /* end指向串s最后一个字符位置 */
    --end;

    while(s<=end)
    {
        while(*s==' ' || !isalpha(*s)) /* 略去串s中的非字母字符 */
            ++s;
        while(*end==' ' || !isalpha(*end))
            --end;
        if(toupper(*s) == toupper(*end)) /* 将s中的字母字符转换为大字进行判断 */
        {
            ++s;
            --end;
        } 
        else 
        {
            is_palindrome=0; break;
        } /* 在s<=end的条件下，只要出现不相等就判断s不是回文 */
    }
    if(s>end)
        is_palindrome=1;
    else
        is_palindrome=0;
    return (is_palindrome);

}

int main()
{
    const char *s ="Madam  I' m   Adam";
    printf("%s %s \n", s, is_palindrome(s) ? "is a palindrome!": "is not a palindrome!");
    return 0;
}

有趣的回文：He lived as a devil, eh?


Don't nod
Dogma: I am God
Never odd or even
Too bad – I hid a boot
Rats live on no evil star
No trace; not one carton
Was it Eliot's toilet I saw?
Murder for a jar of red rum
May a moody baby doom a yam?
Go hang a salami; I'm a lasagna hog!
Satan, oscillate my metallic sonatas!
A Toyota! Race fast... safe car: a Toyota
Straw? No, too stupid a fad; I put soot on warts
Are we not drawn onward, we few, drawn onward to new era?
Doc Note: I dissent. A fast never prevents a fatness. I diet on cod
No, it never propagates if I set a gap or prevention
Anne, I vote more cars race Rome to Vienna
Sums are not set as a test on Erasmus
Kay, a red nude, peeped under a yak
Some men interpret nine memos
Campus Motto: Bottoms up, Mac
Go deliver a dare, vile dog!
Madam, in Eden I'm Adam
Oozy rat in a sanitary zoo
Ah, Satan sees Natasha
Lisa Bonet ate no basil
Do geese see God?
God saw I was dog
Dennis sinned 

世界之最：世界上最长的回文包含了17,259个单词

说明：__cdecl,__stdcall是声明的函数调用协议.主要是传参和弹栈方面的不同.一般c++用的是__cdecl,windows里大都用的是__stdcall(API) 

#12

char *strcpy(char *dest,char *src)
{
    while(*src)
    {
        *dest = *src;
        *src++;
        *dest++;
    }
    *dest = '\0';
    
    return dest;
}


int strcmp(const char *string1, const char *string2)
{
    while (*string1 || *string2)
    {
        
        if(*string1 == *string2)
            return 0;
        if(*string1 < *string2)
            return -1;
        if(*string1 > *string2)
            return 1;
    }
    return 0;
}

char *strcat(char *strDestination, const char *strSource)
{
    while(*strDestination)
    {
        strDestination++;
    }
    while(*strSource)
    {
        *strDestination = *strSource;
        strSource++;
        strDestination++;
    }
    *strDestination = '\0';
    return strDestination;  
}

char *strupr( char *string )
{
    while(*string)
    {
     if (*string<'a' && *string>'z')
    *string-=32;
    string++;
    }
    return string;
}


size_t strlen( const char *string)
{
    int count = 0;
    while(*string)
    {
        count++;
        string++;
    }
    return count;
}


char *strlwr( char *string )
{
    while(*string)
    {
        if (*string<'A' && *string>'Z')
            *string+=32;
        string++;
    }
    return string;
}

#13

size_t strlen(const char *s)
{
	__asm
	{
		mov		eax, s
	len_align:
		test	eax, 3
		jz		len_loop
		test	byte ptr[eax], 0ffh
		jz		len_end
		inc		eax
		jmp		len_align
	len_loop:
		mov		edx, [eax]
		add		eax, 4
		mov 	ecx, edx
		sub 	edx, 01010101h
		and		edx, 80808080h
		jz		len_loop		// > 0 and <= 128 continue
		not		ecx
		and		edx, ecx
		jz		len_loop		// > 128 continue
		bsf		ecx, edx
		shr		ecx, 3
		add		eax, ecx
		sub		eax, 4
	len_end:
		sub		eax, s
	end:
	}
}

#14

void strcpy(char *dest, const char *src)
{
    while (*dest++ = *src++);
}

#15

C:\Program Files\Microsoft Visual Studio 8\VC\crt\src目录，下面有常见库函数的实现。

#16

memcpy貌似使用汇编实现的，每个cpu都是不一样的。

#17

神贴………………