2015 百度笔试的一道经典题目
发布于 2014-10-27 06:37:58 | 186 次阅读 | 评论: 0 | 来源: 网友投递
百度(Baidu)中文搜索引擎
百度（Nasdaq简称：BIDU）是全球最大的中文搜索引擎，2000年1月由李彦宏、徐勇两人创立于北京中关村，致力于向人们提供“简单，可依赖”的信息获取方式。“百度”二字源于中国宋朝词人辛弃疾的《青玉案·元夕》词句“众里寻他千百度”，象征着百度对中文信息检索技术的执著追求。
请编码实现memcpy函数：void *memcpy（void *dst,const void *src,unsigned int count) 显然是内存复制函数
下面是本人结合memcpy的源代码实现的一个测试用例，请大家指点
- #include <stdio.h>
- void *memcpy(void *dst,const void *src,unsigned int count)
- {
- char *p_dst = (char *)(dst);
- char *p_src = (char *)(src);
- unsigned int i;
- if(p_dst>p_src && p_dst<=(p_src+count-1))
- {
- while(count)
- {
- *(p_dst+count-1) = *(p_src+count-1);
- count--;
- }
- }
- else
- {
- for(i=0;i<count;i++)
- {
- *(p_dst+i) = *(p_src+i);
- }
- }
- return dst;
- }
- int main()
- {
- int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
- memcpy(arr+4,arr,sizeof(int)*6);// 这样的拷贝 src<dst && src+count-1>dst,也就是说已经产生了覆盖，
- //所以用从后往前的复制，进入if
- for(int i=0;i<10;i++)
- printf("%d\t",arr[i]);
- // memcpy(arr,arr+4,sizeof(int)*6);// 这样的拷贝 src>dst && src<dst+count-1,
- // 这和正常的拷贝一样，进入else
- // for(int i=0;i<10;i++)
- // printf("%d\t",arr[i]);
- printf("\n");
- return 0;
- }
1 有人可能会问：你的算法保证了任何情况下都能够把数据正确的复制到目的地址，但是你有没有考虑过在复制的过程中，你有可能修改了原始数据呢？
修改了原始串这样的功能明确么？
回答：对，老兄你说的很对，的确会存在这个问题，举个例子吧,比如hello world，我们想把中间的空格去掉，滤掉空格就类似于操作系统中有一种内存分配方法，叫做可重地位分区分配，就是把小作业移动，去除中间的空隙，然后空出后面的一块大的内存地址，供其他程序使用。这样对原始数据不需要保存的情况下，可以应用这个函数。
2 可能你还有疑问：最后的dst+count = '\0' 假如传入的是char 型的数组，怎么办呢？你return dst如何判断空不空呢？ —— 好吧，这也是我的问题，请大神们帮助解答？？？？
3memcpy() 和 普通 strncpy() 复制函数的区别，看代码吧，不多说了：
- #include <iostream>
- #include <cstring> // for c style string manipulation
- using namespace std;
- int main ()
- {
- char str1[]= "To be or not to be";// 18 个字符（含空格）+ '\0' = 19 个字符，因为默认结尾有 '\0'
- cout << sizeof(str1) << endl;
- char str2[40];
- cout << str1 << endl;
- // copy to sized buffer (overflow safe):
- strncpy ( str2, str1, sizeof(str2) );
- cout << str2 << endl;
- // partial copy (only 5 chars):
- strncpy ( str2, str1, 5 );
- cout << str2 << endl;
- str2[5] = '\0'; // null character manually added
- cout << sizeof(str2) << " " << str2 << endl;
- strncpy(str1 + 3, str1, 6); // 出现内存覆盖问题
- cout << str1 ;
- return 0;
- }
- 总结：strcpy
- 源字串全部拷贝到目标字串中,包括'\0'，但是程序员必须保证目标串长度足够，且不与源串重叠。
- strncpy
- 如果目标长>=指定长>源长，则将源串全部拷贝到目标串，连同'\0'
- 如果指定长<源长，则将截取源串中按指定长度拷贝到目标字符串，不包括'\0',手动添加‘\0’，建议对于前两种都手动添加就可以了
- 如果指定长>目标长，错误!
- #include <iostream>
- #include <cstring> // for c style string manipulation
- using namespace std;
- const int maxn = 8;
- int main ()
- {
- int i;
- char dest[]="Hell99iam!";// 10个字符，占了11个空间，最后一个'\0'
- char src[]="abc\0def";
- strncpy(dest,src,maxn);
- dest[maxn] = '\0';
- for(i=0;i<sizeof(dest);i++)
- {
- if(*(dest+i) == '\0')
- cout << "* ";
- else
- cout << *(dest+i) << " ";
- }
- cout << endl << dest << endl;
- char str[maxn];
- strncpy(str,src,1);
- for(i=0;i<sizeof(str);i++)
- {
- if(*(str+i) == '\0')
- cout << "* ";
- else
- cout << *(str+i) << " ";
- }
- //str[1] = '\0'; 如果没有这句话，就是下图的结果了
- cout << endl << str << endl;
- return 0;
- }
- /*
- （c/c++）复制字符串src中的内容（字符，数字、汉字....）到字符串dest中，复制多少由size_t的
- 值决定，返回指向dest的指针。如果遇到空字符（'\0'）[1] ，则空字符后面全部为空（字符）,maxn 决定有多少个空格
- */
3 中第一个函数的结果：
3 中第二个函数的结果：
4 void * memset ( void * ptr, int ch, size_t num );
函数的作用是： fill the first num bytes(注意不是element) of block of memory(由空指针ptr指向） with value. 最后我们会解释这句话的含义。在C++中，设计 size_t 就是为了适应多个平台的 。size_t的引入增强了程序在不同平台上的可移植性。size_t是针对系统定制的一种数据类型，一般是整型（int），因为C/C++标准只定义一最低的位数，而不是必需的固定位数。
- /* memset example */
- #include <iostream>
- #include <cstring>
- using namespace std;
- const int maxn = 11;
- int main ()
- {
- int arr[maxn], i;
- char str[] = "almost every programmer should know memset!";
- memset(str, '-', 6);
- cout << str << endl;
- memset(arr,10,maxn*sizeof(int));
- for(i=0; i<maxn; i++) {
- cout << arr[i] << " ";
- }
- cout << endl;
- memset(arr,-1,maxn*sizeof(int));
- for(i=0; i<maxn; i++) {
- cout << arr[i] << " ";
- }
- cout << endl;
- return 0;
- }
问题来了： 对于上例子中， 对char 型数组的初始化， 输出符合预期。 但是对于整型数组却不符合预期， 为什么呢。 答案就是memset 是对于memory block 是一个字节一个字节的赋值。 由于int 型数组一个int元素就有4个bytes， 当然不符合预期了。 相信改为0后就可以了， 另外改为-1 也可以：
结果如下：