Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 面试 » 

面试中经典函数的实现

很多经典的库函数如strcpy,memcpy等虽然思想并不复杂,但要写出一个比较完善甚至是完全正确的程序非常考验一个程序员思维的严谨性和编程的风格,因而非常受面试官的青睐。
本文主要使用C/C++语言实现strcpy、strncpy、memcpy、memmove、memset、strlen等函数,仅供参考。

一 字符串复制strcpy

strcpy函数把一个字符串的内容复制到另一个字符串里,以’\0′作为结束符。实现时需要注意对const参数、参数检验,返回指针等几个方面。

char* strcpy(char *dst, const char *src) //const约束,内容不可变
{
	assert((src != NULL) && (dst != NULL)); //参数非0检验
	char *add = dst; //保存dst
	while ((*dst++ = *src++) != '\0')
	{
		/*do nothing*/
	}
	return add; //返回dst,允许链式表达式
}

另外还有一个跟strcpy类似的函数strncpy。strncpy在字符串复制时最多复制size个字符,即使没有遇到src的终止符’\0′。当src长度不够size时,效果跟strcpy完全一样。strncpy的实现跟strcpy类似,如下所示:

char* strncpy(char *dst, const char *src, size_t size)
{
	assert((src != NULL) && (dst != NULL));
	char *add = dst;
	int i = 0; // 控制复制的个数
	while (i++ < size && (*dst++ = *src++)!='\0')
	{
		/*do nothing*/
	}
	if (*(--dst) != '\0') //注意字符串以'\0'结尾
	{
		*dst = '\0';
	}
	return add;
}

二 内存拷贝memcpy

关于内存拷贝的库函数有memcpy和memmove,二者均可以把src内存复制到dst内存中,并且一共复制size个字节。但是memcpy不考虑内存区域重叠的问题,当二者内存冲突时,函数的行为是未定义的。memmove是则考虑了这个问题,保证了复制之后的dst一定跟复制之前的src一致。

当自己实现memcpy时需要注意函数对内存重叠的情况有什么要求,必要时直接使用更完整的memmove的实现方式。

下面是没有检查内存重叠的实现:

void* memcpy1(void *dst, const void *src, size_t size) //const约束,内容不可变
{
	assert((src != NULL) && (dst != NULL)); //参数非0检验
	char *pDst = (char *)dst;
	const char *pSrc = (const char *)src;
	while (size-- > 0)
	{
		*pDst++ = *pSrc;
	}
	return dst; //返回dst,允许链式表达式
}

下面是考虑了内存重叠之后的实现,也就是memmove的实现:

void *memcpy2(void *dst, const void *src, size_t size) //const约束,内容不可变
{
	assert((src != NULL) && (dst != NULL)); //参数非0检验
	if (src < dst && (char *)src + size >  (char *)dst) //地址重叠
	{
		char *pDst = (char *)dst + size - 1; //从后向前复制
		const char *pSrc = (const char *)src + size - 1;
		while (size-- > 0)
		{
			*pDst-- = *pSrc--;
		}
	}
	else
	{
		char *pDst = (char *)dst; //从前向后复制
		const char *pSrc = (char *)src;
		while (size-- > 0)
		{
			*pDst++ = *pSrc++;
		}
	}
	return dst; //返回dst,允许链式表达式
}

三 内存初始化memset

memset把buffer开始的连续size个字节全部初始化为字符c。使用时注意这里是以字节为单位进行的。

注意不要在类的构造函数里使用memset函数,因为有些类中含有虚表虚指针,使用memset会改变他们的值,造成程序运行的错误。

void*  memset(void *src, int c, size_t size)
{
	assert(src != NULL);
	char *pSrc = (char *)src;
	while (size--)
	{
		*pSrc++ = (char)c; //转化为char
	}
	return src;
}

四 字符串长度strlen

strlen求取一个字符串的长度,以’\0′作为结束符,以下介绍几种简单的实现方法。

int strlen1(const char* src)
{
	assert(src != '\0');
	int len = 0; //长度计数
	while ((*src++) != '\0')
	{
		len++;
	}
	return len;
}

int strlen2(const char* src)
{
	assert(src != '\0');
	const char *pSrc = src;
	while ((*pSrc++) != '\0')
	{
		/*Do nothing*/
	}
	return pSrc - src - 1;//使用指针计算长度
}<p>&nbsp;</p>

下面是不使用任何其他变量实现的版本,使用递归实现。

int strlen3(const char* src)
{
	assert(src != NULL);
	return *src=='\0' ? 0 : (1 + strlen3(++src));
}
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论