恋花蝶的博客

[原创]两条笔试题和参考答案

关键词： 笔试    编程                                          

最近看到几个笔试题，我的blog还有些师弟妹在看的，可能大家用得着，我就写了个参考答案，大家提提意见。

题目如下：

　　1 编程：

　　用C语言实现一个revert函数，它的功能是将输入的字符串在原串上倒序后返回。

　　2 编程：

　　用C语言实现函数void * memmove(void *dest,const void *src,size_t n)。memmove

　　函数的功能是拷贝src所指的内存内容前n个字节

　　到dest所指的地址上。

题目不难，但有些限制和陷阱，如第一题隐含一个条件就是空间复杂度不能太高；第二题就是有个陷阱就是当目的内存块与源内存块相交的时候的情况。相信很多粗心的人都会中这个陷阱的。

我的参考答案如下：

char* revert( char* p, size_t n )
{
 char* s = p;
 char* e = p+n-1;
 while( s < e )
 {
  *s ^= *e;
  *e ^= *s;
  *s ^= *e;
  ++s,--e;
 }
 return p;
}

void * memmove(void *dest,const void *src,size_t n)
{
 if( dest == src )
 {
  return dest;
 }
 unsigned int* s = (unsigned int*)src;
 unsigned int* d = (unsigned int*)dest;
 
 void* e = (void*)((const char*)src + n);

 if( dest > src && dest < e )
 {
  char* se = (char*)e;
  char* de = ((char*)dest)+n;
  while( se >= src )
   *de-- = *se--;
 }
 else
 {
  while( (void*)(s+1) <= e )
  {
   *d++ = *s++;
  }
  char* cd = (char*)d;
  char* cs = (char*)s;
  while( cs < e )
  {
   *cd++ = *cs++;
  }
 }

 return dest;
}

这两天又看到一个很牛的内存拷贝算法，效率上没有作优化，但想象力惊人，可惜也中了那个源内存与目的内存相交的陷阱，大家来学学吧。

void* mymemcpy( void* dest, const void* src, size_t count )
{
    char* d = (char*)dest;
    const char* s = (const char*)src;
    int n = (count + 7) / 8; // count > 0 assumed

    switch( count & 7 )
    {
    case 0:  do {  *d++ = *s++;
    case 7:        *d++ = *s++;
    case 6:        *d++ = *s++;
    case 5:        *d++ = *s++;
    case 4:        *d++ = *s++;
    case 3:        *d++ = *s++;
    case 2:        *d++ = *s++;
    case 1:        *d++ = *s++;
               } while (--n > 0);
    }

    return dest;
}

更多关于这个算法的东西请查看：http://www.cppblog.com/christanxw/archive/2005/10/11/624.html

呵呵，其实那里也没有说啥。

【作者: 恋花蝶】【访问统计:】【2006年04月7日 星期五 18:39】【注册】【打印】