前言
笔者是读电子通信出身的，故数据结构与算法的基础比较差，而
在找互联网方面工作的时候往往对这方面要求较高，故笔者开始了几
个月的资料收集整理之旅。最初是整理在自己的 evernote 上，后来觉
得取于网络应该还之社区，就整理了这份文档，也许对某部分人还是
有点帮助的。
本文档由evernote打印后使用Acrobat拼接而成，出现部分英文描述
显示不完整，但基本不影响阅读，望包涵。
本文档参考了多个博客的内容，小部分原创，大部分来自下面的
博客，实际上我也很难记清参考的所有博客地址，不完全链接如下：
http://www.cnblogs.com/luxiaoxun/
http://blog.csdn.net/hackbuteer1
http://blog.csdn.net/luckyxiaoqiang
http://blog.csdn.net/v_july_v
http://blog.csdn.net/morewindows
http://zhedahht.blog.163.com/
http://www.cnblogs.com/graphics/
文档内容版权属于各博主，在这里表示感谢，转载请注明出处。
笔者博客：http://blog.csdn.net/jnu_simba
联系方式：dameng34@163.com
笔记本：
DS
创建时间：
2013/11/19 9:28
更新时间：
2014/5/18 21:32
实现标准库的字符串操作函数
strcpy
、
strncpy
、
memmove
、
memcpy
、
memset
、
strlen
、
strncat
、
strcmp
、
strncmp
、
strstr
、
strchr
的
实现
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// The strcpy() function copies the string pointed to by src, including the terminating null byte ('\0'), to the buf
// pointed to by dest. The strings may not overlap, and the destination string dest must be large enough to receive
copy.
char *strcpy(char *dest, const char *src)
{
assert((src != NULL) && (dest != NULL));
size_t i;
for (i = 0; src[i] != '\0'; i++)
dest[i] = src[i];
dest[i] = '\0';
return dest;
}
// The strncpy() function is similar, except that at most n bytes of src are copied. Warning: If there is no null byte am
the first n bytes of src,
// the string placed in dest will not be null-terminated. If the length of src is less than n, strncpy() pads the remainde
dest with null bytes.
char *strncpy(char *dest, const char *src, size_t n)
{
assert((src != NULL) && (dest != NULL));
size_t i;
for (i = 0; i < n && src[i] != '\0'; i++)
dest[i] = src[i];
for (; i < n; i++)
dest[i] = '\0';
return dest;
}
/*
在
32
位的
x86
平台上
,
每次拷贝
1
个字节需要一条指令
,
每次拷贝
4
个字节也只需要一条指
*
令
,memcpy
函数的实现尽可能
4
个字节
4
个字节地拷贝
*/
void *memcpy(void *dest, const void *src, size_t n)
{
assert((src != NULL) && (dest != NULL));
char *d = dest;
const char *s = src;
int *di;
const int *si;
int r = n % 4;
while (r--)
*d++ = *s++;
di = (int *)d;
si = (const int *)s;
n /= 4;
while (n--)
*di++ = *si++;
return dest;
}
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
借助于一个临时缓冲区
temp ,
即使
src
和
dest
所指的内存区间有重叠也能正确拷贝。
*/
void *memmove(void *dest, const void *src, size_t n)
{
assert((src != NULL) && (dest != NULL));
char *temp = (char *)malloc(sizeof(char) * n);
size_t i;
char *d = (char *)dest;
const char *s = (const char *)src;
for (i = 0; i < n; i++)
temp[i] = s[i];
for (i = 0; i < n; i++)
d[i] = temp[i];
free(temp);
return dest;
}
C++ Code
1
2
3
4
size_t strlen(const char *p)
{
assert(p != NULL);
4
5
6
7
assert(p != NULL);
size_t size = 0;
while (*p++ != '\0')
++size;
return size;
}
C++ Code
1
2
3
4
5
6
7
8
9
10
11
char *strncat(char *dest, const char *src, size_t n)
{
size_t dest_len = strlen(dest);
size_t i;
for (i = 0 ; i < n && src[i] != '\0' ; i++)
dest[dest_len + i] = src[i];
dest[dest_len + i] = '\0';
return dest;
}
不用临时空间的
memmove
实现：
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//src
可以不保留
void *memmove(void *dst, const void *src, size_t count)
{
byte *pbTo = (byte *)dst;
byte *pbFrom = (byte *)src;
assert(dst != NULL && src != NULL);//
不能存在空指针
if (dst <= src || pbTo >= pbFrom + count)//
{
while (count-- > 0)
{
*pbTo++ = *pbFrom++; //
按递增拷贝
}
}
else //
{
pbTo = pbTo + count - 1; //overlap
的情况，从高位地址向低位拷贝
pbFrom = pbFrom + count - 1;
while (count-- > 0)
{
*pbTo-- = *pbFrom--; //
按递减拷贝
}
}
return dst;
}
memset
的实现
:
C++ Code
1
2
3
4
5
6
7
8
void *memset(void *buffer, int c, int count)
{
char *buffer_p = (char *)buffer;
assert(buffer != NULL);
while(count-- > 0)
*buffer_p++ = (char)c;
return buffer;
}
C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//
查找字符串
s
中首次出现字符
c
的位置
char *strchr(char *str, int c)
{
assert(str != NULL);
for (; *str != (char)c; ++ str)
if (*str == '\0')
return NULL;
return str;
}
//
字符串连接
char *strcat(char *strDes, const char *strSrc)
{
assert((strDes != NULL) && (strSrc != NULL));
char *address = strDes;
while (*strDes != '\0')
++ strDes;
while ((*strDes ++ = *strSrc ++) != '\0')
NULL;
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
*StrDes = '\0';
return address;
}
//
查找字符串第一次出现的位置
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;
}
//
字符串比较
int strcmp(const char *s, const char *t)
{
assert(s != NULL && t != NULL);
while(*s && *t && *s == *t)
{
++ s;
++ t;
}
return (*s - *t);
}
int strncmp(const char *s, const char *t, int count)
{
assert((s != NULL) && (t != NULL));
while (count-- > 0 && *s && *t && *s == *t)
{
++ s;
++ t;
}
return(*s - *t);
}
请使用C语言完成strnicmp的编码实现，要求不能调用任何其它的函数。strcnicmp完成两个ascii字符串的比较，忽略大小写
（两个英文字母比较时，认为大小写无差别），最多比较n个字符（当两个字符串长度超过n时，就认为它们的长度都等于
n），返回<0表示第一个字符串小于第二个字符串，返回>0表示第一个字符串大于第二个字符串，返回等于0时表示两个字符
串相等。函数声明如下：int strnicmp(char const *s1, char const *s2, int n)
[cpp]
01. int strnicmp(char const *s1, char const *s2, int n)
02. {
03. int i;
04. for(i = 0; i < n; i++)
05. {
06. char a = s1[i], b = s2[i];
07. if(a >= 'A' && a <= 'Z')a = a - 'A' + 'a';
08. if(b >= 'A' && b <= 'Z')b = b - 'A' + 'a';
09. if(a == b)
10. continue;
11. return a - b;
12. }
13. return 0;
笔记本：
DS
创建时间：
2013/11/17 11:21
更新时间：
2014/4/16 21:13
hashtable
、
priority queue
、
Bloom filter
、
Bitmap
的简单实现
1.hashtable
：本文中采用开链法（
separate chaining
）来处理
“
冲突
”
（
collision
），而且
hashtable
只存储唯一的元素，不存在重复。
实现代码如下：
[cpp]
01. class hashtable
02. {
03. public:
04. //
构造函数，
n
为想要构造的
hashtable
的
bucket
数量
05. hashtable(size_t n);
06. ~hashtable();
07. //
插入元素。若元素不存在，插入成功返回
true
；若元素已存在则插入失败，返回
false
08. bool insert(const int val);
09. //
查找元素是否在表中出现
10. bool find(const int val);
11. //
删除元素。若元素存在，删除成功返回
true
；若元素不存在则删除失败，返回
false
12. bool erase(const int val);
13. //
清除所有元素
14. void clear();
15. //
返回已有元素数目
16. size_t size();
17. private:
18. // bucket
中的节点
19. struct hashtable_node
20. {
21. hashtable_node *next;
22. int val;
23. hashtable_node(int _val, hashtable_node *_next = NULL):val(_val), next(_next){}
24. };
25.
26. hashtable(const hashtable & h); //
暂时不允许拷贝和赋值
27. const hashtable & operator = (const hashtable & h);
28. // hash
函数
29. size_t hash(unsigned long x);
30. //
寻找大于等于
n
且最接近
n
的质数
31. unsigned long next_prime(unsigned long n);
32. // bucket
向量表
33. vector<hashtable_node*> buckets;
34. //
元素个数
35. size_t num_elements;
36. };
37. hashtable::hashtable(size_t n)
38. {
39. //
将
bucket
数量设置为大于等于
n
且最接近
n
的质数
40. const size_t n_buckets = next_prime(n);
41. buckets.reserve(n_buckets);
42. buckets.insert(buckets.end(), n_buckets, NULL);
43. num_elements = 0;
44. };
45. hashtable::~hashtable()
46. {
