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

时间：2021-02-17 21:53:16

http://blog.csdn.net/liuqiyao_01/article/details/26967813

二、stl模板函数

1、strcpy

  1. char * strcpy( char *strDest, const char *strSrc )
  2. {
  3. if(strDest == strSrc) { return strDest; }
  4. assert( (strDest != NULL) && (strSrc != NULL) );
  5. char *address = strDest;
  6. while( (*strDest++ = * strSrc++) != '\0' );
  7. return address;
  8. }

2、strncpy

  1. <span style="font-size:18px;">char *strncpy(char *strDes, const char *strSrc, unsigned int count)
  2. {
  3. assert(strDes != NULL && strSrc != NULL);
  4. char *address = strDes;
  5. while (count-- && *strSrc != '\0')
  6. *strDes++ = *strSrc++;
  7. *strDes = '\0';
  8. return address;
  9. } </span>

3、strcmp

  1. int strcmp(const char *s, const char *t)
  2. {
  3. assert(s != NULL && t != NULL);
  4. while (*s && *t && *s == *t)
  5. {
  6. ++ s;
  7. ++ t;
  8. }
  9. return (*s - *t);
  10. }

4、strcat

  1. char *strcat(char *strDes, const char *strSrc)
  2. {
  3. assert((strDes != NULL) && (strSrc != NULL));
  4. char *address = strDes;
  5. while (*strDes != '\0')
  6. ++ strDes;
  7. while ((*strDes ++ = *strSrc ++) != '\0')
  8. NULL;
  9. return address;
  10. }

5、strlen

  1. int strlen(const char *str)
  2. {
  3. assert(str != NULL);
  4. int len = 0;
  5. while (*str ++ != '\0')
  6. ++ len;
  7. return len;
  8. }

6、strstr

  1. char *strstr(const char *strSrc, const char *str)
  2. {
  3. assert(strSrc != NULL && str != NULL);
  4. const char *s = strSrc;
  5. const char *t = str;
  6. for (; *strSrc != '\0'; ++ strSrc)
  7. {
  8. for (s = strSrc, t = str; *t != '\0' && *s == *t; ++s, ++t)
  9. NULL;
  10. if (*t == '\0')
  11. return (char *) strSrc;
  12. }
  13. return NULL;
  14. }

7、strncat

  1. char *strncat(char *strDes, const char *strSrc, unsigned int count)
  2. {
  3. assert((strDes != NULL) && (strSrc != NULL));
  4. char *address = strDes;
  5. while (*strDes != '\0')
  6. ++ strDes;
  7. while (count -- && *strSrc != '\0' )
  8. *strDes ++ = *strSrc ++;
  9. *strDes = '\0';
  10. return address;
  11. }

8、strncmp

  1. int strncmp(const char *s, const char *t, unsigned int count)
  2. {
  3. assert((s != NULL) && (t != NULL));
  4. while (*s && *t && *s == *t && count --)
  5. {
  6. ++ s;
  7. ++ t;
  8. }
  9. return (*s - *t);
  10. }

9、memcpy

  1. void *memcpy(void *dest, const void *src, unsigned int count)
  2. {
  3. assert((dest != NULL) && (src != NULL));
  4. void *address = dest;
  5. while (count --)
  6. {
  7. *(char *) dest = *(char *) src;
  8. dest = (char *) dest + 1;
  9. src = (char *) src + 1;
  10. }
  11. return address;
  12. }

10、memccpy

  1. void *memccpy(void *dest, const void *src, int c, unsigned int count)
  2. {
  3. assert((dest != NULL) && (src != NULL));
  4. while (count --)
  5. {
  6. *(char *) dest = *(char *) src;
  7. if (* (char *) src == (char) c)
  8. return ((char *)dest + 1);
  9. dest = (char *) dest + 1;
  10. src = (char *) src + 1;
  11. }
  12. return NULL;
  13. }

11、memcmp

  1. int memcmp(const void *s, const void *t, unsigned int count)
  2. {
  3. assert((s != NULL) && (t != NULL));
  4. while (*(char *) s && *(char *) t && *(char *) s == *(char *) t && count --)
  5. {
  6. s = (char *) s + 1;
  7. t = (char *) t + 1;
  8. }
  9. return (*(char *) s - *(char *) t);
  10. }

12、memmove

  1. //@big：
  2. //要处理src和dest有重叠的情况，不是从尾巴开始移动就没问题了。
  3. //一种情况是dest小于src有重叠，这个时候要从头开始移动，
  4. //另一种是dest大于src有重叠，这个时候要从尾开始移动。
  5. void *memmove(void *dest, const void *src, unsigned int count)
  6. {
  7. assert(dest != NULL && src != NULL);
  8. char* pdest = (char*) dest;
  9. char* psrc = (char*) src;
  10. //pdest在psrc后面，且两者距离小于count时，从尾部开始移动. 其他情况从头部开始移动
  11. if (pdest > psrc && pdest - psrc < count)
  12. {
  13. while (count--)
  14. {
  15. *(pdest + count) = *(psrc + count);
  16. }
  17. } else
  18. {
  19. while (count--)
  20. {
  21. *pdest++ = *psrc++;
  22. }
  23. }
  24. return dest;
  25. }

13、memset

  1. void *memset(void *str, int c, unsigned int count)
  2. {
  3. assert(str != NULL);
  4. void *s = str;
  5. while (count --)
  6. {
  7. *(char *) s = (char) c;
  8. s = (char *) s + 1;
  9. }
  10. return str;
  11. }

三、atoi && itoa

1、atoi

  1. //代码自己所写，不对地方请及时指正，谢谢！
  2. //inf用来标记作为判断是否越界
  3. //atoiFlag作为是否是正确结果的返回值
  4. const __int64 inf = (0x7fffffff);
  5. int atoiFlag;
  6. int atoi(const char* ch)
  7. {
  8. ASSERT(ch != NULL);
  9. atoiFlag = false;
  10. while (*ch == ' ' || *ch == '\t')
  11. ch ++;
  12. int isMinus = 1;
  13. if (*ch == '-')
  14. {
  15. isMinus = -1;
  16. ch ++;
  17. }
  18. else if (*ch == '+')
  19. {
  20. ch ++;
  21. }
  22. //判断非法
  23. if (!(*ch <= '9' && *ch >= '0'))
  24. return 0;
  25. __int64 ans = 0;
  26. while (*ch && *ch <= '9' && *ch >= '0')
  27. {
  28. ans *= 10;
  29. ans += *ch - '0';
  30. //判断越界
  31. if (ans > inf)
  32. {
  33. return inf;
  34. }
  35. ch ++;
  36. }
  37. ans *= isMinus;
  38. atoiFlag = true;
  39. return (int)ans;
  40. }
  41. //如何使用
  42. int main()
  43. {
  44. char a[100];
  45. while (scanf("%s", a) != EOF)
  46. {
  47. int ans = atoi(a);
  48. if (atoiFlag)
  49. printf("%d\n", ans);
  50. else if (ans == inf)
  51. puts("The data of crossing the line");
  52. else
  53. puts("Not is a integer");
  54. }
  55. return 0;
  56. }

2、itoa

  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. char *myitoa(int num,char *str,int radix);
  4. int main()
  5. {
  6. int number = -123456;
  7. char string[25];
  8. myitoa(number, string, 16);
  9. printf("integer = %d string = %s\n", number, string);
  10. return 0;
  11. }
  12. /* 实现itoa函数的源代码 */
  13. char *myitoa(int num,char *str,int radix)
  14. {
  15. /* 索引表 */
  16. char index[]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  17. unsigned unum; /* 中间变量 */
  18. int i=0,j,k;
  19. /* 确定unum的值 */
  20. if(radix==10&&num<0) /* 十进制负数 */
  21. {
  22. unum=(unsigned)-num;
  23. str[i++]='-';
  24. }
  25. else unum=(unsigned)num; /* 其他情况 */
  26. /* 逆序 */
  27. do
  28. {
  29. str[i++]=index[unum%(unsigned)radix];
  30. unum/=radix;
  31. }while(unum);
  32. str[i]='\0';
  33. /* 转换 */
  34. if(str[0]=='-') k=1; /* 十进制负数 */
  35. else k=0;
  36. /* 将原来的“/2”改为“/2.0”，保证当num在16~255之间，radix等于16时，也能得到正确结果 */
  37. char temp;
  38. for(j=k;j<=(i-k-1)/2.0;j++)
  39. {
  40. temp=str[j];
  41. str[j]=str[i-j-1];
  42. str[i-j-1]=temp;
  43. }
  44. return str;
  45. }

四、kmp  &&  quicksort

1、kmp

http://www.cnblogs.com/dolphin0520/archive/2011/08/24/2151846.html

  1. void getNext(const char* p, int next[])
  2. {
  3. next[0] = -1;
  4. int index = 0;
  5. int p_l = strlen(p);
  6. for (int i=1; i<p_l; i++)
  7. {
  8. index = next[i-1];
  9. while (index >= 0 && p[index+1] != p[i])
  10. {
  11. index = next[index];
  12. }
  13. if (p[index+1] == p[i])
  14. {
  15. next[i] = index + 1;
  16. }
  17. else
  18. {
  19. next[i] = -1;
  20. }
  21. }
  22. }
  23. int kmp(const char* t, const char* p)
  24. {
  25. const int t_l = strlen(t);
  26. const int p_l = strlen(p);
  27. int Next = new int[p_l + 1];
  28. getNext(p, Next);
  29. int p_index = 0, t_index = 0;
  30. int cnt = 0;
  31. while (p_index < p_l && t_index < t_l)
  32. {
  33. if (t[t_index] == p[p_index])
  34. {
  35. t_index ++;
  36. p_index ++;
  37. }
  38. else if (p_index == 0)
  39. {
  40. t_index ++;
  41. }
  42. else
  43. {
  44. p_index = Next[p_index-1] + 1;
  45. }
  46. if (p_index == p_l)
  47. {
  48. cnt ++;
  49. p_index = Next[p_index-1] + 1;
  50. }
  51. }
  52. delete[] Next;
  53. return cnt;
  54. }

2、quicksort

    1. #include <stdio.h>
    2. #include <stdlib.h>
    3. #include <time.h>
    4. int partion(int a[], int p, int r)
    5. {
    6. srand((unsigned)time(NULL));
    7. int e = rand()%(r-p+1)+p;
    8. int tmp = a[e];
    9. a[e] = a[r];
    10. a[r] = tmp;
    11. int x = a[r];
    12. int i, j;
    13. i = p;
    14. for (j=p; j<r; j++)
    15. {
    16. if (a[j] <= x)
    17. {
    18. tmp = a[i];
    19. a[i] = a[j];
    20. a[j] = tmp;
    21. i ++;
    22. }
    23. }
    24. tmp = a[r];
    25. a[r] = a[i];
    26. a[i] = tmp;
    27. return i;
    28. }
    29. void QuickSort(int a[], int p, int r)
    30. {
    31. if (p < r)
    32. {
    33. int q = partion(a, p, r);
    34. QuickSort(a, p, q-1);
    35. QuickSort(a, q+1, r);
    36. }
    37. }
    38. int main()
    39. {
    40. int a[] = {1,2,3,-1,5,-9,10,33,0};
    41. QuickSort(a, 0, 8);
    42. for (int i=0; i<9; i++)
    43. {
    44. printf("%d\t", a[i]);
    45. }
    46. return 0;
    47. }

相关文章