部分C库函数重写(经典c/c++面试题)

#include
#include
#include

////////////////////////////////////////////////////
//Convert character to uppercase.
const char *toupper(char *s)
{
 for(char *t=s;*t!='\0';t++)
 {
  if(*t>='a'&&*t<='z')
   *t-='a'-'A';
 }
 return s;
}

////////////////////////////////////////////////////
//Copies characters between buffers.
//
// 函数说明: memcpy()用来拷贝src所指的内存内容前n个字节到dest所指的内存地址上。
//           与strcpy()不同的是,memcpy()会完整的复制n个字节,不会因为遇到字符串结束'\0'而结束
//           memcpy功能和memmove相同，但是memcpy中dest和source中的区域不能重叠，否则会出现未知结果。
//
// 返回值说明：返回指向dest的void *指针
// 附加说明: 指针src和dest所指的内存区域不可重叠
//
void *memcpy(void *dest, const void *src, size_t count)
{
 assert( (dest!=NULL)&&(src!=NULL) );
 char *tmp_dest = (char*)dest;
 char *tmp_src = (char*)src;
 while( count--)//不对是否存在重叠区域进行判断
  *tmp_dest++ = *tmp_src++;
 return dest;
}

////////////////////////////////////////////////////
//Moves one buffer to another.
//
// 函数说明：memmove用于从source拷贝count个字符到dest，如果目标区域和源区域有重叠的话，
//           memmove能够保证源串在被覆盖之前将重叠区域的字节拷贝到目标区域中。
// 返回值说明：返回指向dest的void *指针
void *memmove(void *dest, const void *src, size_t count)
{
 assert( (dest!=NULL)&&(src!=NULL) );
 char *tmp_dest=(char*)dest;
 char *tmp_src=(char*)src;

 if( tmp_dest+count {// 如果没有重叠区域
  while(count--)
   *tmp_dest++=*tmp_src;
 }
 else
 {// 如果有重叠区域
  tmp_dest+=count-1;
  tmp_src+=count-1;
  while(count--)
   *--tmp_dest=*--tmp_src;
 }
 return dest;
}

////////////////////////////////////////////////////
//Sets buffers to a specified character.
void *memset(void *src, int c, size_t count)
{
 assert(src!=NULL);
 char *tmpsrc=(char*)src;
 while(count--)
  *tmpsrc++ =(char)c;
 return src;
}
////////////////////////////////////////////////////
//Finds characters in a buffer.
void* memchr(const void* src, int c, size_t count)
{
 assert(src!=NULL);
 char *tempsrc=(char*)src;
 while(count&&*tempsrc!=(char)c)
 {
  count--;
  tempsrc++;
 }
 if(count!=0)
  return tempsrc;
 else
  return NULL;
}

////////////////////////////////////////////////////
//Get the length of a string
int strlen(const char *str)
{
 assert( str!=NULL );
 int length = 0;
 while( *str++!='\0' )
  length++;
 return length;
}

////////////////////////////////////////////////////
// Copy a string
/*void strcpy(char *strDest, const char *strSrc)
{
 assert( (strSrc!=NULL)&&(strDest!=NULL) );
 while( *strSrc!='\0' )
  *strDest++ = *strSrc++;
 *strDest = '\0';
}*/
// 标准库函数
char *strcpy(char *strDest, const char *strSrc)
{
 assert( (strSrc!=NULL)&&(strDest!=NULL) );
 char *address = strDest;
    while( (*address++ = *strSrc++)!='\0' );
 return address;
}

////////////////////////////////////////////////////
//Append a string
char *strcat(char *str1, const char *str2)
{
 assert( (str1!=NULL)&&(str2!=NULL) );
 while( *str1!='\0' )
  str1++;
 while( (*str1++ = *str2++)!='\0' );
 return str1;
}

////////////////////////////////////////////////////
//Compare strings
int strcmp(const char *str1, const char *str2)
{
 while( *str1!='\0' && *str2!='\0' && *str1==*str2 )
 {
   str1++;
   str2++;
 }

 if( *str1 =='\0' )
 {
  if( *str2 =='\0' )
   return 0;
  else
   return -1;
 }
 else if( *str2 =='\0' )
 {
  if( *str1 =='\0' )
   return 0;
  else
   return 1;
 }
 else
 {
  if( *str1<*str2 )
   return -1;
  else
   return 1;
 }
}
////////////////////////////////////////////////////
//Find a character in a string.
char *strchr(const char *str, int ch)
{
 while( *str!='\0' && *str!=(char)ch )
  str++;
 if( *str==(char)ch )
  return (char*)str;
 else
  return NULL;
}

////////////////////////////////////////////////////
//Find a substring.
char *strstr(const char *src, const char *strCharSet)
{
 char *tempStr=(char*)src;
 while( (*tempStr++!=*strCharSet)!='\0' );

 char *temp=--tempStr;
 if( *tempStr=='\0' )
  return NULL;
 else
 {
  while(*tempStr==*strCharSet&&*tempStr!='\0'&&*strCharSet!='\0')
  {
   tempStr++;
   strCharSet++;
  }
  if(*strCharSet=='\0')
   return temp;
  else
   return NULL;
 }
}

c/c++面试题集

1、 如何判断一个单链表是有环的？（注意不能用标志位，最多只能用两个额外指针）

   struct node { char val; node* next;}

   bool check(const node* head) {} //return false : 无环；true: 有环

一种O（n）的办法就是（搞两个指针，一个每次递增一步，一个每次递增两步，如果有环的话两者必然重合，反之亦然）：

bool check(const node* head)

{

    if(head==NULL)  return false;

    node *low=head, *fast=head->next;

    while(fast!=NULL && fast->next!=NULL)

    {

        low=low->next;

        fast=fast->next->next;

        if(low==fast) return true;

    }

    return false;

}

2、 写一个函数找出一个整数数组中，第二大的数 （Microsoft）

答案：

    const int MINNUMBER = -32767 ;

    int find_sec_max( int data[] , int count)

    {

        int maxnumber = data[0] ;

        int sec_max = MINNUMBER ;

        for ( int i = 1 ; i < count ; i++)

        {

            if ( data > maxnumber )

            {

                sec_max = maxnumber ;

                maxnumber = data ;

            }

            else

            {

                if ( data > sec_max )

                sec_max = data ;

            }

        }

        return sec_max ;

    }

3、 链表题：一个链表的结点结构

struct Node

{

    int data ;

    Node *next ;

};

typedef struct Node Node ;

(1)已知链表的头结点head,写一个函数把这个链表逆序 ( Intel)

Node * ReverseList(Node *head) //链表逆序

{

    if ( head == NULL || head->next == NULL )

        return head;

    Node *p1 = head ;

    Node *p2 = p1->next ;

    Node *p3 = p2->next ;

    p1->next = NULL ;

    while ( p3 != NULL )

    {

        p2->next = p1 ;

        p1 = p2 ;

        p2 = p3 ;

        p3 = p3->next ;

    }

    p2->next = p1 ;

    head = p2 ;

    return head ;

}

(2)已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序。(保留所有结点，即便大小相同）

Node * Merge(Node *head1 , Node *head2)

{

    if ( head1 == NULL)

        return head2 ;

    if ( head2 == NULL)

        return head1 ;

    Node *head = NULL ;

    Node *p1 = NULL;

    Node *p2 = NULL;

    if ( head1->data < head2->data )

    {

        head = head1 ;

        p1 = head1->next;

        p2 = head2 ;

    }

    else

    {

        head = head2 ;

        p2 = head2->next ;

        p1 = head1 ;

     }

    Node *pcurrent = head ;

    while ( p1 != NULL && p2 != NULL)

    {

        if ( p1->data <= p2->data )

        {

             pcurrent->next = p1 ;

             pcurrent = p1 ;

             p1 = p1->next ;

        }

        else

        {

             pcurrent->next = p2 ;

             pcurrent = p2 ;

             p2 = p2->next ;

        }

    }

    if ( p1 != NULL )

        pcurrent->next = p1 ;

    if ( p2 != NULL )

        pcurrent->next = p2 ;

    return head ;

}

(3)已知两个链表head1 和head2 各自有序，请把它们合并成一个链表依然有序，这次要求用递归方法进行。 (Autodesk)

答案：

Node * MergeRecursive(Node *head1 , Node *head2)

{

    if ( head1 == NULL )

        return head2 ;

    if ( head2 == NULL)

        return head1 ;

    Node *head = NULL ;

    if ( head1->data < head2->data )

    {

        head = head1 ;

        head->next = MergeRecursive(head1->next,head2);

    }

    else

    {

        head = head2 ;

        head->next = MergeRecursive(head1,head2->next);

     }

    return head ;

}

4、 如何判断一段程序是由C 编译程序还是由C++编译程序编译的？

答案：

    #ifdef __cplusplus

    cout<<"c++";

    #else

    cout<<"c";

    #endif

5、There are two int variables: a and b, don’t use “if”, “? :”, “switch”or other judgement statements, find out the biggest one of the two numbers.

答案：

    ( ( a + b ) + abs( a - b ) ) / 2

6、如何定义和实现一个类的成员函数为回调函数

    A.什么是回调函数?

        简而言之，回调函数就是被调用者回头调用调用者的函数。

        使用回调函数实际上就是在调用某个函数（通常是API函数）时，将自己的一个函数（这个函数为回调函数）的地址作为参数传递给那个被调用函数。而该被调用函数在需要的时候，利用传递的地址调用回调函数。

        回调函数，就是由你自己写的，你需要调用另外一个函数，而这个函数的其中一个参数，就是你的这个回调函数名。这样，系统在必要的时候，就会调用你写的回调函数，这样你就可以在回调函数里完成你要做的事。

 

    B.如何定义和实现一个类的成员函数为回调函数

        要定义和实现一个类的成员函数为回调函数需要做三件事：

        a．声明；

        b．定义；

        c．设置触发条件，就是在你的函数中把你的回调函数名作为一个参数，以便系统调用

        如：

            一、声明回调函数类型

                typedef void (*FunPtr)(void);

            二、定义回调函数

                class A 

                {

                public:

                    A();

                    static void callBackFun(void)   //回调函数，必须声明为static

                    {

                        cout<<"callBackFun"<

                    }

                    virtual ~A();

                };

 

            三、设置触发条件

                void Funtype(FunPtr p)

                {

                   p();

                }

                void main(void)

                {

                    Funtype(A::callBackFun);

                }

 

    C. 回调函数与API函数

    回调和API非常接近，他们的共性都是跨层调用的函数。但区别是API是低层提供给高层的调用，一般这个函数对高层都是已知的；而回调正好相反，他是高层提供给底层的调用，对于低层他是未知的，必须由高层进行安装，这个安装函数其实就是一个低层提供的API，安装后低层不知道这个回调的名字，但它通过一个函数指针来保存这个回调函数，在需要调用时，只需引用这个函数指针和相关的参数指针。

 

其实：回调就是该函数写在高层，低层通过一个函数指针保存这个函数，在某个事件的触发下，低层通过该函数指针调用高层那个函数。