二分查找的代码. 
int bfind(int* a,int len,int val) 
{ 
    int m = len/2; 
    int l = 0; 
    int r = len; 
    while(l!=m && r!= m) 
    { 
        if(a[m] > val) 
        { 
            r = m; 
            m = (m+l)/2; 
        } 
        else if(a[m] < val) 
        { 
            l = m; 
            m = (m+r)/2; 
        } 
        else 
            return m; 
    } 
    return -1;  //没有找到 
} 

写出在母串中查找子串出现次数的代码. 
int count1(char* str,char* s) 
{ 
    char* s1; 
    char* s2; 
    int count = 0; 
    while(*str!=‘\0‘) 
    { 
        s1 = str; 
        s2 = s; 
        while(*s2 == *s1&&(*s2!=‘\0‘)&&(*s1!=‘0‘)) 
        { 
            s2++; 
            s1++; 
        } 
        if(*s2 == ‘\0‘) 
            count++; 
        str++; 
    } 
    return count; 
} 

查找第一个匹配子串位置,如果返回的是s1长度len1表示没有找到 
size_t find(char* s1,char* s2) 
    { 
        size_t i=0; 
        size_t len1 = strlen(s1) 
        size_t len2 = strlen(s2); 
        if(len1-len2<0) return len1; 
        for(;i        { 
            size_t m = i; 
            for(size_t j=0;j            { 
                if(s1[m]!=s2[j]) 
                    break; 
                m++; 
            } 
            if(j==len) 
                break; 
        } 
        return i    } 

写出快速排序或者某种排序算法代码 
快速排序: 
int partition(int* a,int l,int r) 
{ 
    int i=l-1,j=r,v=a[r]; 
    while(1) 
    { 
        while(a[++i]        while(a[--j]>v) if(j<=i) break; 
        if(i>=j) 
            break; 
        swap(a,a[j]); 
    } 
    swap(a,a[r]); 
    return i; 
} 

void qsort(int* a,int l,int r) 
{ 
    if(l>=r) return; 
    int i = partition(a,l,r); 
    qsort(a,l,i-1); 
    qsort(a,i+1,r); 
} 

冒泡排序: 
void buble(int *a,int n) 
{ 
    for(int i=0;i    { 
        for(int j=1;j        { 
            if(a[j]           { 
                int temp=a[j]; 
                a[j] = a[j-1]; 
                a[j-1] = temp; 
            } 
        } 
    } 
} 
插入排序： 
void insertsort(int* a,int n) 
{ 
    int key; 
    for(int j=1;j    { 
        key = a[j]; 
        for(int i=j-1;i>=0&&a>key;i--) 
        { 
            a[i+1] = a; 
        } 
        a[i+1] = key; 
    } 
} 

出现次数相当频繁 

实现strcmp函数 
int strcmp11(char* l,char* r) 
{ 
    assert(l!=0&&r!=0); 
    while(*l == *r &&*l != ‘\0‘) l++,r++; 
    if(*l > *r) 
        return 1; 
    else if(*l == *r) 
        return 0; 
    return -1; 
} 

实现字符串翻转 
void reserve(char* str) 
{ 
    assert(str != NULL); 
    char * p1 = str; 
    char * p2 = str-1; 
    while(*++p2);        //一般要求不能使用strlen 
    p2 -= 1; 
    while(p1    { 
        char c = *p1; 
        *p1++ = *p2; 
        *p2-- = c; 
  } 
} 

将一个单链表逆序 
struct list_node 
{ 
    list_node(int a,list_node* b):data(a),next(b) //这个为了测试方便 
    {} 
    int data; 
    list_node* next; 
}; 

void reserve(list_node* phead) 
{ 
        list_node* p = phead->next; 
        if(p == NULL || p->next == NULL) return; //只有头节点或一个节点 
        list_node* p1=p->next; 
        p->next=NULL; 
        while(p1!=NULL) 
        { 
            p = p1->next; 
            p1->next = phead->next; 
            phead->next = p1; 
            p1 = p; 
        } 
} 

测试程序： 
    list lt; 
    lt.phead = new list_node(0,0); 
    lt.phead->next = new list_node(1,0); 
    lt.phead->next->next = new list_node(2,0); 
    lt.phead->next->next->next = new list_node(3,0); 
    lt.reserve(); 
    list_node * p = lt.phead; 
    while(p) 
    { 
        cout<data<        p = p->next; 
    } 


循环链表的节点对换和删除。 

//双向循环 
list_node* earse(list_node* node) 
{ 
    // if(node == rear) return node->next;    //对于头节点可判断也可不判断。最好加上 
    list_node* next = node->next; 
    next->prev = node->prev; 
    node->prev->next = next; 
    delete node; 
    retrun next; 
} 
//单项循环 
list_node* earse(list_node* node) 
{ 
    // if(node == rear) return node->next;    //对于头节点可判断也可不判断。最好加上 
    list_node* p = rear; 
    while(p->next != node) p=p->next; 
    p->next = node->next; 
    delete node; 
    retrun p->next; 
} 


将一个数字字符串转换为数字."1234" -->1234 
int atoii(char* s) 
{ 
    assert(s!=NULL); 
    int num = 0; 
    int temp; 
    while(*s>‘0‘ && *s<‘9‘) 
    { 
        num *= 10; 
        num += *s-‘0‘; 
        s++; 
    } 
    return num; 
} 
出现次数相当频繁 


.实现任意长度的整数相加或者相乘功能。 
void bigadd(char* num,char* str,int len) 
{ 
    for(int i=len;i>0;i--) 
    { 
        num += str; 
        int j = i; 
        while(num[j]>=10) 
        { 
            num[j--] -= 10; 
            num[j] += 1; 
        } 
    } 
} 


.写函数完成内存的拷贝 
void* memcpy( void *dst, const void *src, unsigned int len ) 
{ 
    register char *d; 
    register char *s; 
    if (len == 0) 
        return dst; 
    if ( dst > src )  //考虑覆盖情况 
    { 
        d = (char *)dst + len - 1; 
        s = (char *)src + len - 1; 
        while ( len >= 4 )  //循环展开，提高执行效率 
        { 
            *d-- = *s--; 
            *d-- = *s--; 
            *d-- = *s--; 
            *d-- = *s--; 
            len -= 4; 
        } 
        while ( len-- ) 
        { 
            *d-- = *s--; 
        } 
    } 
    else if ( dst < src ) 
    { 
        d = (char *)dst; 
        s = (char *)src; 
        while ( len >= 4 ) 
        { 
            *d++ = *s++; 
            *d++ = *s++; 
            *d++ = *s++; 
            *d++ = *s++; 
            len -= 4; 
        } 
        while ( len-- ) 
        { 
            *d++ = *s++; 
        } 
    } 
    return dst; 
} 
出现次数相当频繁 

编写类String的构造函数、析构函数和赋值函数，已知类String的原型为： 

class String 
{    
public:    
String(const char *str = NULL); // 普通构造函数  
String(const String &other); // 拷贝构造函数 
~ String(void); // 析构函数 
String & operate =(const String &other); // 赋值函数    
private:    
char *m_data; // 用于保存字符串    
}; 

解答： 
//普通构造函数 
String::String(const char *str) 
{ 
      if(str==NULL) 
      { 
              m_data = new char[1]; // 得分点：对空字符串自动申请存放结束标志‘\0‘的空 
                                 　//加分点：对m_data加NULL 判断 
              *m_data = ‘\0‘; 
      }  
      else 
      { 
        int length = strlen(str); 
        m_data = new char[length+1]; // 若能加 NULL 判断则更好 
        strcpy(m_data, str); 
      } 
} 
// String的析构函数 
String::~String(void) 
{ 
      delete [] m_data; // 或delete m_data; 
} 
//拷贝构造函数 
String::String(const String &other) 　　　// 得分点：输入参数为const型 
{    
      int length = strlen(other.m_data); 
      m_data = new char[length+1]; 　　　　//加分点：对m_data加NULL 判断 
      strcpy(m_data, other.m_data);  
} 

//赋值函数 
String & String::operate =(const String &other) // 得分点：输入参数为const型 
{    
      if(this == &other)               　　//得分点：检查自赋值 
              return *this; 
      delete [] m_data;          　　　　//得分点：释放原有的内存资源 
      int length = strlen( other.m_data );    
      m_data = new char[length+1]; 　//加分点：对m_data加NULL 判断 
      strcpy( m_data, other.m_data ); 
      return *this;    　　　　　　　　//得分点：返回本对象的引用 
} 
剖析： 
能够准确无误地编写出String类的构造函数、拷贝构造函数、赋值函数和析构函数的面试者至少已经具备了C++基本功的60%以上！ 
在这个类中包括了指针类成员变量m_data，当类中包括指针类成员变量时，一定要重载其拷贝构造函数、赋值函数和析构函数，这既是对C++程序员的基本要求，也是《Effective　C++》中特别强调的条款。 

实现strcpy 

char * strcpy( char *strDest, const char *strSrc ) 
{ 
assert( (strDest != NULL) && (strSrc != NULL) ); 
char *address = strDest; 
while( (*strDest++ = * strSrc++) != ‘\0’ ); 

return address; 
} 

编写一个函数，作用是把一个char组成的字符串循环右移n个。比如原来是“abcdefghi”如果n=2，移位后应该是“hiabcdefgh” 
函数头是这样的： 

//pStr是指向以‘\0‘结尾的字符串的指针 
//steps是要求移动的n 
void LoopMove ( char * pStr, int steps ) 
{ 
//请填充... 
} 

解答： 
正确解答1： 
void LoopMove ( char *pStr, int steps ) 
{ 
    int n = strlen( pStr ) - steps; 
    char tmp[MAX_LEN];  
    strcpy ( tmp, pStr + n ); 
    strcpy ( tmp + steps, pStr);  
    *( tmp + strlen ( pStr ) ) = ‘\0‘; 
    strcpy( pStr, tmp ); 
} 

正确解答2： 
void LoopMove ( char *pStr, int steps ) 
{ 
    int n = strlen( pStr ) - steps; 
    char tmp[MAX_LEN];  
    memcpy( tmp, pStr + n, steps ); 
    memcpy(pStr + steps, pStr, n );    
    memcpy(pStr, tmp, steps );  
}

C/C++ 经典算法实例,布布扣,bubuko.com

C/C++ 经典算法实例