【读书笔记】读《程序员面试宝典》

　　最近有幸拜读了《程序员面试宝典》（第五版）这本书，此书真乃良心之作，尤其对于我们这种未毕业的学生来说，更是一本不可多得的宝贵资料。

　　现将其中一些感觉比较重要的知识点摘抄成读书笔记，方便日后复习查阅。

一、知识要点

　　1.预处理、const与sizeof

　　（1）const 与 #define相比有什么不同？

　　 答：C++语言可以使用const定义常量，也可以使用#define定义常量，但是前者比后者有更多的优点：

　　　　 *const常量有数据类型，而宏常量没有数据类型。编译器可以对前者进行类型安全检查，而对后者只进行字符替换，没有类型安全检查，并且在字符替换中可能会产生意料不到的错误（边际效应）。

　　　　 *有些集成化调试工具可以对const常量进行调试，但是不能对宏常量进行调试。在C++程序中只使用const常量而不是用宏常量，即const常量完全取代宏常量。

　 （2）对比sizeof和strlen，并深入理解

　　答：（1）sizeof操作符的结果类型是size_t，，它在头文件中的typedef为unsigned int 类型。该类型保证能容纳实现所建立的最大对象的字节大小。

　　　　（2）sizeof是运算符，strlen是函数。

　　　　（3）sizeof可以用类型作为参数，strlen只能用char*作为参数，且必须是以"\0"结尾的。sizeof还可以用函数作为参数，比如：

short f();
printf("%d\n",sizeof( f() );

　　　　 输出的结果是sizeof(short),即2.

　　　　（4）数组做sizeof的参数不退化，传递给strlen就退化为指针。

　　　　（5）大部分编译程序在编译的时候，就把sizeof计算过了，是类型或者变量长度。这是sizeof(x)可以用来定义数组维度的原因：

char str[20]="0123456789";
int a=strlen(str); //a=10
int b=sizeof(str); //b=20;

　　　　（6）strlen的结果要在运行的时候才能计算出来，用于计算字符串的长度，而不是类型占内存的大小。

 　　　  （7）sizeof后如果是类型必须加括号，如果是变量名可以不加括号。这是因为sizeof是个操作符而不是个函数。

　　　　（8）当使用了一个结构类型或者变量时，sizeof返回实际的大小。当使用一静态的空间数组时，sizeof返回全部数组的尺寸。sizeof操作符不能返回被动态分配的数组或者是外部的数组的尺寸。

　　　　（9）数组作为参数传给函数的时候，传递的是指针而不是数组，传递的是数组的首地址，如func(char [8])、func(char [])都等价于func(char *)。在C++里传递数组永远都是传递指向数组首元素的指针，编译器不知道数组的大小。如果想要在函数内部知道数组的大小，需要这样做：进入函数后用memcpy将数组复制一份，长度由另一个参数传递进来。

func(char *p1,int len){
    char *buf=new char[len+1];
    memcpy(buf,p1,len);
}

　　　　(10)计算结构体变量的大小就必须讨论数据对齐的问题。为了使CPU存取的速度最快，C++在处理数据时经常把数据变量中的成员大小按照4或者8的倍数来计算，这就叫做数据对齐。这样做可能会浪费一些内存，但是在理论上CPU速度快了。当然这样的设置会在读写一些别的应用程序生成的数据文件或者交换数据时带来不便。

　　　 （11）sizeof操作符不能用于函数类型，不完全类型或者位字段。不完全类型指具有位置存储大小的数据类型，如未知存储大小的数组类型、未知内容的联合或者结构、void类型等。

　　（3）const成员函数是什么？

　　 答：我们定义的类的成员函数中，常常有一些成员函数不改变类的数据成员，也就是说，这些函数是“只读”函数，而有一些函数要修改类数据成员的值。如果把不改变数据成员的函数都加上const关键字进行标识，显然可以提高程序的可读性。其实，它还能提高程序的可靠性，已定义成const的成员函数，一旦企图修改数据成员的值，则编译器按错误处理。

class Point{
    int Xval,Yval;
    public:
    int GetX() const;
};
//关键字const必须用同样的方法重复出现在函数实现里，否则编译器会把它看成一个不同的函数

int Point::GetX() const{
    return Xval;
}

如果把cons放在函数声明的前面呢？因为这样意味着函数的返回值是常量，意义就完全不同了。

　　2.指针与引用

　　　　（1）指针与引用的差别？

　　　　　答：（1）非空引用。在任何情况下都不能使用指向空值的引用。一个引用必须总是指向某些对象。因此如果你使用一个变量并让它指向一个对象，但是该变量在某些时候也可能不指向任何对象，这时你应该把变量生命为指针，因为这样你可以赋空值给该变量。相反，如果变量肯定可以指向一个对象，例如你的设计不允许变量为空，这时你就可以把变量声明为引用。不存在指向空值的引用这个事实意味着使用引用的代码效率比使用指针要高。

　　　　　      （2）合法性区别。在使用引用之前不需要测试它的合法性。相反，指针则应该总是被测试，防止其为空。

　　　　　　　（3）可修改区别。指针和引用的另一个重要的区别是指针可以被重新赋值以指向另一个不同的对象。但是引用则总是指向在初始化时被指定的对象，以后不能改变，但是指向的对象其内容可以改变。

　　　　　　　（4）应用区别。总的来说，在以下情况下应该使用指针：一是考虑到存在不指向任何对象的可能（在这种情况下，能够设置指针为空），二是需要能够在不同的时刻指向不同的对象（在这种情况下，你能改变指针的指向）。如果总是指向一个对象并且一旦一个对象以后不会改变指向，那么你应该使用引用。

　　　  （2）写出函数指针、函数返回指针、const指针、指向const的指针、指向const的const指针。

　　　　　答：void (*f)()    void *f()       const int *  int * const         const int* const

　　　 （3）下列的数据声明都代表着什么？

　　　　　　1.float (**def) [10];

　　　　　　2.double *(*gh) [10];

　　　　　　3.double (*f[10])();

　　　　　　4.int *((*b)[10]);

　　　　　　5.Long(*fun) (int);

　　　　　　6.int (*(*f)(int,int))(int);

　　　　答：就像数组名是指向数组的第一个元素的常指针一样，函数名也是指向函数的常指针。可以声明一个指向函数的指针变量，并且用这个指针来调用其他的函数---只要这个函数和你的函数指针在签名、返回、参数值方面一致即可。

　　　　Long(*fun) (int)    这就是一个典型的函数指针，即指向函数的指针，这个指针的返回类型是Long。带有一个int类型的参数。如果去掉(*fun)的“()”，它就是一个指针函数，是一个带有整数形参，并且返回值是一个Long* 类型的函数。

　　　　int (*(*F)(int,int))(int)　　F是一个指向函数的指针，它指向的是一个函数（此函数参数为int,int 。返回值为一个指针），返回的这个指针指向的是另外一个函数（参数类型为int,返回值为int类型的函数）。

　　　　答案：（1）float (**def)[10]; def是一个二级指针，他指向的是一个一维数组的真是，数组元素都是float。

　　　　　　　（2）double *(*gh)[10]; gh是一个指针，他指向的是一个一维数组，数组元素都是double*。

　　　　　　　（3）double(*f[10])();　　f是一个数组，有10个元素，元素都是函数的指针，指向的函数类型是没有参数并且返回double的函数。

　　　　　　　（4）int *((*b)[10]);　　就和“int*(*b)[10]”一样，是一维数组的指针。

　　　　　　　（5）Long(*fun)(int)      函数指针

　　　　　　　（6）int (*(*F)(int,int))(int)  　　F是一个函数的指针，指向的函数的类型是有两个int参数并且返回一个函数指针的函数，返回的函数指针，指向有一个int参数并且返回int的函数。

　　3.new 和malloc的区别

　　　　（1）malloc分配的是内存使用free来释放，new分配的内存使用delete来释放。

　　　　（2）malloc和free是c/c++的标准库函数，new/delete是c/c++的操作符。

　　　　（3）malloc/free只分配、释放内存，new/delete还可以用来创建，释放对象，会自动执行对象的构造函数/析构函数。

　　　　（4）new/delete的写法比malloc/free简洁，如int *p=new int; int *p=(int)free(sizeof(int));

　　　　（5）new/delete在创建数组时，特别注意int *p=new int[100];在释放的时候也要加上[]，delete [] p;

　　4.下面哪个进制能表述13*16=244是正确的？

　　　　A.5　　B.7　　C.9　　D.11

　　　　解析：13如果是一个10进制的话，它可以用13=1*10^1+3*10^0来表示。现在我们不知道13是几进制，那么我们先假设它是X进制。X进制下的13转换成X进制可以用13=1*X^1+3*X^0表示。X进制下16转换成X进制可以用1*X^1+6*X^0,X进制下224转换成X进制可以用244=2*X^2+4*X^1+4*X^0表示，因此X进制下的13*16=244可以转换成10进制下的等式：(1*X^1+3*X^0)*(1*X^1+6*X^0)=2*X^2+4*X^1+4*X^0。 整理得到X*X+6*X+3*X+3*6=2*X*X+4*X+4，化简得：

X*X-5*x-14=0;最后解得X=-2或者7，-2舍弃，所以X=7。

　　5.内联函数和宏定义的差别是什么？

　　　　解析：内联函数和普通函数相比可以加快程序运行的速度，因为不需要中断调用，在编译的时候内联函数可以直接被镶嵌到目标代码中，而宏只是做一个简单的替换。宏不是函数，只是在编译前将程序中有关字符串替换成宏体。

　　　　内联函数要做参数类型检查，这是内联函数和宏相比的优势。　　

　　　　　　inline是指嵌入代码，就是在调用函数的地方不是跳转，而是把代码直接写到那里去。对于短小的代码来说，inline增加空间消耗换来的是效率的提高，这方面和宏是一模一样的。但是inline在和宏相比没有付出任何额外代价的情况下更安全。至于是否需要inline函数就要根据实际情况来取舍了。inline一般只用于以下的情况：

　　　　（1）一个函数不断被重复调用

　　　　（2）函数只有简单的几行，且不包含for\while\switch语句

　　6.链表相关知识复习

　　　　（1）给出一个单链表，但是不知道链表的N值（链表的长度），怎样只遍历一次就可以求出中间节点？

　　　　 解析：设立两个指针，比如说*p和*q，p每次移动两个位置，p=p->next->next,q每次移动一个位置，即q=q-next。这样，当P达到最后一个节点的时候，q就是中间节点了。

void search_mid(node *head,node *mid){
    node* temp=head;
    while(head->next->next!=NULL){
        head=head->next->next;
        temp=temp->next;
        mid=temp;
    }
}

　　　　（2）

　　7.请描述进程和线程的区别

　　答：进程是程序的一次执行。线程可以理解为进程中执行的一段程序片段。在一个多任务环境中下面的概念可以帮助我们理解两者之间的区别：

　　进程间是独立的，这表现在内存空间、上下文环境上；线程运行在进程空间内。一般来讲（不是用特殊技术），进程无法突破进程边界存取其他进程内的存储空间；而线程由于处于进程空间内，所以同一进程所产成的线程共享同一内存空间。

　　同一进程内的两段代码不能同时执行，除非引入线程。

　　线程是属于进程的，当进程退出时该进程所产生的线程都会被强制退出并清除。线程占用的资源要少于进程。进程线程都可以有优先级。

　　进程间可以通过IPC通信，但线程不可以。