面试必会函数源代码 strcpy/memcpy/atoi/kmp/quicksort
面试必会函数源代码 strcpy/memcpy/atoi/kmp/quicksort
bear_fish
发布于 2018-09-14 10:55:20
发布于 2018-09-14 10:55:20
一、写在前面
继上一次发表了一片关于参加秋招的学弟学妹们如何准备找工作的博客之后，反响很大，顾在此整理一下，以便大家复习。好多源自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;
} 本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2014年12月16日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录