社区首页 >专栏 >面试必会函数源代码 strcpy/memcpy/atoi/kmp/quicksort

面试必会函数源代码 strcpy/memcpy/atoi/kmp/quicksort

bear_fish

发布于 2018-09-14 02:55:20

1.1K0

文章被收录于专栏：用户2442861的专栏用户2442861的专栏

一、写在前面

继上一次发表了一片关于参加秋招的学弟学妹们如何准备找工作的博客之后，反响很大，顾在此整理一下，以便大家复习。好多源自july的这篇博客，也有很多是我自己整理的。希望大家能够一遍一遍的写，直到能够秒杀为止。

二、stl模板函数

1、strcpy

[cpp] view plaincopy

 char * strcpy( char *strDest, const char *strSrc )          
 {         
  if(strDest == strSrc) { return strDest; }      
     assert( (strDest != NULL) && (strSrc != NULL) );         
  char *address = strDest;          
  while( (*strDest++ = * strSrc++) != '\0' );          
  return address;         
 }

2、strncpy

[cpp] view plaincopy

 <span style="font-size:18px;">char *strncpy(char *strDes, const char *strSrc, unsigned int count)          
 {          
     assert(strDes != NULL && strSrc != NULL);          
  char *address = strDes;          
  while (count-- && *strSrc != '\0')          
         *strDes++ = *strSrc++;       
     *strDes = '\0';      
  return address;          
 } </span>

3、strcmp

[cpp] view plaincopy

 int strcmp(const char *s, const char *t)       
 {       
     assert(s != NULL && t != NULL);       
  while (*s && *t && *s == *t)       
     {       
         ++ s;       
         ++ t;       
     }       
  return (*s - *t);       
 }

4、strcat

[cpp] view plaincopy

 char *strcat(char *strDes, const char *strSrc)       
 {       
     assert((strDes != NULL) && (strSrc != NULL));       
  char *address = strDes;       
  while (*strDes != '\0')       
         ++ strDes;       
  while ((*strDes ++ = *strSrc ++) != '\0')       
         NULL;       
  return address;       
 }

5、strlen

[cpp] view plaincopy

 int strlen(const char *str)       
 {       
     assert(str != NULL);       
  int len = 0;       
  while (*str ++ != '\0')       
         ++ len;       
  return len;       
 }

6、strstr

[cpp] view plaincopy

 char *strstr(const char *strSrc, const char *str)       
 {       
     assert(strSrc != NULL && str != NULL);       
  const char *s = strSrc;       
  const char *t = str;       
  for (; *strSrc != '\0'; ++ strSrc)       
     {       
  for (s = strSrc, t = str; *t != '\0' && *s == *t; ++s, ++t)       
             NULL;       
  if (*t == '\0')       
  return (char *) strSrc;       
     }       
  return NULL;       
 }

7、strncat

[cpp] view plaincopy

 char *strncat(char *strDes, const char *strSrc, unsigned int count)       
 {       
     assert((strDes != NULL) && (strSrc != NULL));       
  char *address = strDes;       
  while (*strDes != '\0')       
         ++ strDes;       
  while (count -- && *strSrc != '\0' )       
         *strDes ++ = *strSrc ++;       
     *strDes = '\0';       
  return address;       
 }

8、strncmp

[cpp] view plaincopy

 int strncmp(const char *s, const char *t, unsigned int count)       
 {       
     assert((s != NULL) && (t != NULL));       
  while (*s && *t && *s == *t && count --)       
     {       
         ++ s;       
         ++ t;       
     }       
  return (*s - *t);       
 }

9、memcpy

[cpp] view plaincopy

 void *memcpy(void *dest, const void *src, unsigned int count)       
 {       
     assert((dest != NULL) && (src != NULL));       
  void *address = dest;       
  while (count --)       
     {       
         *(char *) dest = *(char *) src;       
         dest = (char *) dest + 1;       
         src = (char *) src + 1;       
     }       
  return address;       
 }

10、memccpy

[cpp] view plaincopy

 void *memccpy(void *dest, const void *src, int c, unsigned int count)       
 {       
     assert((dest != NULL) && (src != NULL));       
  while (count --)       
     {       
         *(char *) dest = *(char *) src;       
  if (* (char *) src == (char) c)       
  return ((char *)dest + 1);       
         dest = (char *) dest + 1;       
         src = (char *) src + 1;       
     }       
  return NULL;       
 }

11、memcmp

[cpp] view plaincopy

 int memcmp(const void *s, const void *t, unsigned int count)       
 {       
     assert((s != NULL) && (t != NULL));       
  while (*(char *) s && *(char *) t && *(char *) s == *(char *) t && count --)       
     {       
         s = (char *) s + 1;       
         t = (char *) t + 1;       
     }       
  return (*(char *) s - *(char *) t);       
 }

12、memmove

[cpp] view plaincopy

//@big：
//要处理src和dest有重叠的情况，不是从尾巴开始移动就没问题了。
//一种情况是dest小于src有重叠，这个时候要从头开始移动，
//另一种是dest大于src有重叠，这个时候要从尾开始移动。

 void *memmove(void *dest, const void *src, unsigned int count)       
 {      
     assert(dest != NULL && src != NULL);      
  char* pdest = (char*) dest;      
  char* psrc = (char*) src;      
  
  //pdest在psrc后面，且两者距离小于count时，从尾部开始移动. 其他情况从头部开始移动     
  if (pdest > psrc && pdest - psrc < count)       
     {      
  while (count--)       
         {      
             *(pdest + count) = *(psrc + count);      
         }      
     } else 
     {      
  while (count--)       
         {      
             *pdest++ = *psrc++;      
         }      
     }      
  return dest;      
 }

13、memset

[cpp] view plaincopy

 void *memset(void *str, int c, unsigned int count)       
 {       
     assert(str != NULL);       
  void *s = str;       
  while (count --)       
     {       
         *(char *) s = (char) c;       
         s = (char *) s + 1;       
     }       
  return str;       
 }

三、atoi && itoa

1、atoi

[cpp] view plaincopy

 //代码自己所写，不对地方请及时指正，谢谢！ 
 //inf用来标记作为判断是否越界 
 //atoiFlag作为是否是正确结果的返回值 
 const __int64 inf = (0x7fffffff);  
 int atoiFlag;  
 int atoi(const char* ch)  
 {  
     ASSERT(ch != NULL);  
     atoiFlag = false;  
  while (*ch == ' ' || *ch == '\t')  
         ch ++;  
  int isMinus = 1;  
  if (*ch == '-')  
     {  
         isMinus = -1;  
         ch ++;  
     }  
  else if (*ch == '+')  
     {  
         ch ++;  
     }  
  //判断非法 
  if (!(*ch <= '9' && *ch >= '0'))  
  return 0;  
  __int64 ans = 0;  
  while (*ch && *ch <= '9' && *ch >= '0')  
     {  
         ans *= 10;  
         ans += *ch - '0';  
  //判断越界 
  if (ans > inf)  
         {  
  return inf;  
         }  
         ch ++;  
     }  
     ans *= isMinus;  
     atoiFlag = true;  
  return (int)ans;  
 }  
  
 //如何使用 
 int main()  
 {  
  char a[100];  
  while (scanf("%s", a) != EOF)  
     {  
  int ans = atoi(a);  
  if (atoiFlag)  
             printf("%d\n", ans);  
  else if (ans == inf)  
             puts("The data of crossing the line");  
  else 
             puts("Not is a integer");  
     }  
  return 0;  
 }

2、itoa

[cpp] view plaincopy

 #include <stdlib.h>  
 #include <stdio.h>  
 char *myitoa(int num,char *str,int radix);  
 int main()   
 {   
  int number = -123456;   
  char string[25];   
     myitoa(number, string, 16);   
     printf("integer = %d string = %s\n", number, string);   
  return 0;   
 }   
 /* 实现itoa函数的源代码 */ 
 char *myitoa(int num,char *str,int radix)   
 {    
  /* 索引表 */ 
  char index[]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";   
     unsigned unum; /* 中间变量 */ 
  int i=0,j,k;   
  /* 确定unum的值 */ 
  if(radix==10&&num<0) /* 十进制负数 */ 
     {   
         unum=(unsigned)-num;   
         str[i++]='-';   
     }   
  else unum=(unsigned)num; /* 其他情况 */ 
  /* 逆序 */ 
  do 
     {   
         str[i++]=index[unum%(unsigned)radix];   
         unum/=radix;   
     }while(unum);   
     str[i]='\0';   
  /* 转换 */ 
  if(str[0]=='-') k=1; /* 十进制负数 */ 
  else k=0;   
  /* 将原来的“/2”改为“/2.0”，保证当num在16~255之间，radix等于16时，也能得到正确结果 */ 
  char temp;   
  for(j=k;j<=(i-k-1)/2.0;j++)   
     {   
         temp=str[j];   
         str[j]=str[i-j-1];   
         str[i-j-1]=temp;   
     }   
  return str;   
 }

四、kmp && quicksort

1、kmp

[cpp] view plaincopy

 void getNext(const char* p, int next[])  
 {  
     next[0] = -1;  
  int index = 0;  
  int p_l = strlen(p);  
  for (int i=1; i<p_l; i++)  
     {  
         index = next[i-1];  
  while (index >= 0 && p[index+1] != p[i])  
         {  
             index = next[index];  
         }  
  if (p[index+1] == p[i])  
         {  
             next[i] = index + 1;  
         }  
  else 
         {  
             next[i] = -1;  
         }  
     }  
 }  
  
 int kmp(const char* t, const char* p)  
 {  
  const int t_l = strlen(t);  
  const int p_l = strlen(p);  
  int Next = new int[p_l + 1];  
     getNext(p, Next);  
  int p_index = 0, t_index = 0;  
  
  int cnt = 0;  
  
  while (p_index < p_l && t_index < t_l)  
     {  
  if (t[t_index] == p[p_index])  
         {  
             t_index ++;  
             p_index ++;  
         }  
  else if (p_index == 0)  
         {  
             t_index ++;  
         }  
  else 
         {  
             p_index = Next[p_index-1] + 1;  
         }  
  if (p_index == p_l)  
         {  
             cnt ++;  
             p_index = Next[p_index-1] + 1;  
         }  
     }  
  delete[] Next;  
  return cnt;  
 }

2、quicksort

[cpp] view plaincopy

 #include <stdio.h> 
 #include <stdlib.h> 
 #include <time.h> 
  
 int partion(int a[], int p, int r)  
 {  
     srand((unsigned)time(NULL));  
  int e = rand()%(r-p+1)+p;  
  int tmp = a[e];  
     a[e] = a[r];  
     a[r] = tmp;  
  int x = a[r];  
  int i, j;  
     i = p;  
  for (j=p; j<r; j++)  
     {  
  if (a[j] <= x)  
         {  
             tmp = a[i];  
             a[i] = a[j];  
             a[j] = tmp;  
             i ++;  
         }  
     }  
     tmp = a[r];  
     a[r] = a[i];  
     a[i] = tmp;  
  return i;  
 }  
  
 void QuickSort(int a[], int p, int r)  
 {  
  if (p < r)  
     {  
  int q = partion(a, p, r);  
         QuickSort(a, p, q-1);  
         QuickSort(a, q+1, r);  
     }  
 }  
  
 int main()  
 {  
  int a[] = {1,2,3,-1,5,-9,10,33,0};  
     QuickSort(a, 0, 8);  
  for (int i=0; i<9; i++)  
     {  
         printf("%d\t", a[i]);  
     }  
  return 0;  
 }