• 微软原版系统

  • 一键重装系统

  • 纯净系统

  • 在线技术客服

魔法猪系统重装大师 一键在线制作启动 U 盘 PE 系统 用一键重装的魔法拯救失去灵魂的系统
当前位置:首页 > 教程 > 电脑教程

程序员面试宝典(第三版)笔记整理、指出了书中一些不足之处

时间:2015年04月02日 15:28:34    来源:魔法猪系统重装大师官网    人气:9944

      不怎样的一本书,具体表现为:1)该详细讲解的地方,或者一笔带过或者讲得不全面或者讲些不相关内容;2)该略过的地方,反而详细起来;3)有一部分错误,如sizeof不计算static变量的大小之类的。虽说如此,收获还是有的——知道了在笔试中常见的知识点。这里的笔记就是对我不熟悉或者理解不全面的知识点去Google和查书而来的。

C++的关键字

1. 使用extern "C"的理由

函数被C编译器编译后不带参数信息,被C++编译器编译后会带上参数信息。这是因为C++支持函数重载。所以函数被C编译器编译和被C++编译器编译是不同的。例如:void Zero(int lin),被C编译后,可能得到_Zero,被C++编译后,可能得到_Zero_int。那如果要在C++中使用被C编译过的库呢?使用extern "C"就可以!它会告诉C++编译器,被它修饰的函数是以C语言的编译方式编译的。

2. const的作用

a. 声明常量     
b. 声明函数形参     -> 提高自定义类型的调用效率。注意,如果是内部类型,如int,没必要写成const int&
c. 声明函数返回值
d. 修饰类成员函数     -> 防止成员函数对成员变量进行修改。注意,const成员函数内只能调用类的其他const成员函数

备注:如果要在const成员函数修改某个成员变量,那么可以给这个变量的声明加上mutable

3. static的作用

a. 用于函数内部的局部变量时,能保证函数退出作用域后不回收其空间(即其值保持不变)

b. 用于全局变量时,使变量的作用域限制在一个文件内

c. 用于函数时,使函数只在一个文件内可见

d. 用于类成员变量时,代表该变量属于类的(即所有对象共享这个变量)

e. 用于类成员函数时,代表该函数为整个类所有。注意,该函数不接收this指针,也意味着不能调用一般的成员函数或者变量

4. sizeof操作符

a. 作用:返回一个对象或者类型所占的内存

b. sizeof 不计算类/结构体的static成员 -> 因而可将a中提到所占的内存理解为存储某个类型的对象所需要空间

c. 对空类使用sizeof会返回1     -> 占用内存为0,无法实例化,所以编译器为了使空类也能实例化,就给其分配了1Byte

d. 如果类中有虚函数,那么最终结果要多加4Byte     -> 此时多出一个指针,指向虚函数表

e.g:

static int a;     //sizeof(a) = 4,因为这不是类内/结构体内的

class Zero {

int a;

static int b;

virtual void fun() {}

};    //sizeof(Zero) = 8

class Lin {

virtual void fun() {}

};     //sizeof(Lin) = 4,由d可知其为lin至少有4Byte,所以在这个例子中规则c不成立,因而最终结果为4Byte

class Child: public Zero {

     int a;

     virtual void fun() {}

};     //sizeof(Child) = 12

5. inline

a. inline只是一种建议,建议编译器将指定的函数在被调用点展开,因此编译器是可以忽略inline的(即不展开)

b. inline以代码膨胀(复制)为代价,省去了函数调用的开销,从而提高函数的执行效率
c. 每一处inline函数的调用都要复制代码,这将使得程序的总代码量增大,消耗更多的内存空间
d. inline必须与函数定义放在一起才能使函数成为内联,仅将inline 放在函数声明前面不起任何作用
e. 定义在类声明之中的成员函数将自动地成为内联函数

6. explicit

禁止单参数构造函数被用于隐式类型转换

class Zero {

public:

     Zero(int i): lin(i) {}

private:

     int lin;

};

int Fun(Zero z) {}     //如果不用explicit的话,可以这样调用Fun(1);

-------------------------------------------------------------------------------------------

C++的规则

1. 在声明赋值语句中,变量先声明,然后赋值

int i = 1;

int main() {

     int i = i;     //这里声明的i 覆盖了全局变量的i,之后的赋值就是局部变量的i 给自己赋值,因而其值是未定义的

     return 0;

}

2. 从右到左压参数

int main() {

     int i = 1;

     printf("%d, %d\n", i, ++i);     //VS2010输出2, 2

}

其它:

虽然压参数的顺序是固定的,但计算顺序是编译器相关的,因此最后的结果与编译器相关。

3. 写宏时要注意

a. 括号的使用

b. 不要使用分号

e.g: 写一个找出两者中较小的宏

#define MIN(a, b) ( (a) < (b) ? (a) : (b) )

4. 结构体对齐原则

 a. 数据成员对齐规则:结构(struct或union)的数据成员,第一个数据成员放在offset为0的地方,以后每个数据成员存储的起始位置要从该成员大小的整数倍开始(e.g: int在32位机为4字节,则要从4的整数倍地址开始存储)
b. 结构体作为成员:如果一个结构里有某些结构体成员,则结构体成员要从其内部最大元素大小的整数倍地址开始存(e.g: struct a里存有struct b,b里有char,int,double等元素,那b应该从8的整数倍开始存储)
c. 结构体的总大小,必须是内部最大成员的整数倍,不足的要补齐

备注:设计结构体,最好把占用空间小的类型排在前面,占用空间大的类型排在后面,这样可以相对节约一些对齐空间

struct Zero {

char b;

int a;     //a的起始位置要按4字节对齐,所以b之后要补3个字节

short c;

};     //sizeof(Zero) = 12

struct OreZ {

char b;

short c;     //c的起始位置要按2字节对齐,所以b之后要补1个字节

int a;

}     //sizeof(Orez) = 8

5. 结构体位制

a. 位段成员的类型仅能够为unsigned或者int, 并且指定的位数不能超过类型的长度

b. 存储规则:如果下一个位段能存放在之前的存储单元中(存储后长度不超过类型长度),则存储,否则,存储到新的存储单元中。因为位段不能跨单元存储

struct Zero {

     unsigned short a : 4;
     unsigned short b : 5;
     unsigned short c : 7;     //刚好16,符合unsigned short的长度,所以存放在同一单元中
}zero;

int main() {

     zero.a = 2;

     zero.b = 3;

     int i = *((short*)&zero);

     printf("%d", i);     //输出50(VS2010测试结果),这说明先声明的变量在低位

     return 0;

}

6. C++风格类型转换

a. const_cast(varible): 去掉变量的const或volatile属性

b. static_cast(varible): 类似C的强制转换,但功能上有所限制(如:不能去掉const属性)     -> 常用于基本类型转换,void指针与目标指针转换

c. dynamic_cast(varible): 有条件转换,运行时进行类型安全检查(如果失败则返回NULL)     -> 用于基类与子类之间的类型转换(必须要有虚函数)

d. reinterpret_cast(varible): 仅仅重新解释二进制内容    -> 常用于不同类型的指针转换

class Base {

public:

     virtual void fun() {}

};

class Zero: public Base {

public:

     virtual void fun() {}

};

int main() {

     Base *pb = new Base;

     (dynamic_cast(pb)) -> fun();     //由于实际指向的是基类,所以此转换失败,返回NULL,导致运行时错误

     delete pb;

     return 0;

}

7. 指针与引用的差异

a. 初始化:指针可以不初始化;引用必须在定义时初始化

b. 非空性:指针可以为NULL,因而指针可能是无效的;引用不能为空,因而引用总是有效的

c. 内存占用:指针要占用内存,引用不占     -> 引用只是一个逻辑概念,通常在编译时就优化掉了

d. 可修改性:指针可以重新指向其它变量;引用不可以

《Effective C++》:在一般情况下,引用和指针是一样的,但是根据条款23:在返回一个对象时,尽量不要用引用,而是用指针

8. 指针与句柄(handle)

指针标记一个内存的地址

句柄是Windows用来标识被应用程序建立或使用的对象(窗口,菜单,内存等)的唯一整数。从构造上看,句柄是一个指针,但其不指向存储对象的内存位置,而是一个包含了对象所在的内存位置的结构(结构的复杂度由所指的对象决定)

9. 指针与浅拷贝

浅拷贝在复制指针时,只是单纯地将指针指向同一内存,并不对所指向的内容进行复制。因而,当成员变量有指针时,最好考虑是否要写深拷贝函数和赋值函数

class Zero {

public:

     Zero(): ptr(NULL) {}

     ~Zero() { if( ptr )     delete[] ptr; }

     char* ptr;

};

int main() {

     Zero z;

     z.ptr = new char[100];

     strcpy(z.ptr, "zero");

     vector * vz = new vector();

     vz->push_back(z);

     delete vz;

     return 0;

}   //退出main时会出现运行时错误

由于Zero没有定义拷贝函数,所以有一个默认的浅拷贝函数。在main函数中,delete vz已经释放过一次ptr指向的内存,然后在离开main的作用域时z的析构函数启动,再次释放该内存

10. 迭代器失效

在容器中增加/删除元素时,可能会使部分或者全部的迭代器失效

11. C++编译器默认产生的成员函数

构造函数,析构函数,拷贝函数,赋值函数

12. 类中静态成员变量与常量

a. 静态成员变量一定要在类外初始化

b. 成员常量一定要在初始化列表初始化

c. 静态成员常量一定要初始化,初始化时可以直接在声明时写上,也可以像一般的静态成员变量那样写

class Zero {

public:

     Zero():lin2(1) {}

private:

     static int lin;

     const int lin2;

     static const int lin3 = 1;

};

int Zero::lin = 0;

13. 初始化列表的初始化顺序根据成员变量的声明顺序执行

class Zero {     //不要写这样的代码

public:

     Zero(int i):lin2(i), lin1(lin2) {}     //此时先初始化lin1,再初始化lin2,因而最后的结果是lin1的值是随机数,lin2的值是i

private:

     int lin1;

     int lin2;

};

14. 构造函数不可以为virtual,析造函数有时必须为virtual

虚函数在运行时动态绑定,动态绑定需要知道动态类型才能进行绑定。而一个类的对象在没有运行构造函数前,其动态类型不完整,因而无法进行动态绑定

delete指向子类对象的基类指针时,如果析构函数不是virtual,则只会调用基类的析构函数,从而造成内存泄漏

15. C++编译的程序占用的内存
a. stack(栈区): 由OS自动分配释放空间,主要用来存放函数的参数,局部变量等
b. heap(堆区): 一般由程序员分配释放空间, 若程序员不释放,程序结束时可能由OS回收
c. static(全局/静态区): 存放全局变量和静态变量。值得注意的是,初始化和未初始化的这两种变量是分开存放的。
d. 文字常量区: 存放常量字符串
e. 程序代码区: 存放函数的二进制代码

-------------------------------------------------------------------------------

杂项

1. 不用循环,判断一个数X是否为2的N的次方(N >= 0)

X & (X - 1)     //最后结果为0,则是2的N次方

分析:2,4,8的二进制式为10, 100, 1000,当其与1, 3, 7的二进制式相与时,其结果为0

2. 不用判断语句,找出两个数中的最大值

((a + b) + abs(a - b)) / 2

3. 不用中间变量,交换两者的值

a = a ^ b;     //得到a与b的哪些位不相同(即一共有多少位不同)

b = a ^ b;     //去掉b的不同位,换上a的不同位,从而得到a

a = a ^ b;

4. 写一个宏FIND,求结构体struc里某个变量相对struc的偏移量

#define FIND(struc, e) (size_t)&(((struc*)0)->e)

解析:(struc*)0将0强制转换为struc*的指针类型,然后再取(struc*)0的成员e的地址,从而得到e离结构体首地址的偏移量

5. 数组名再取地址

int a[] = {1, 2, 3};

int *ptr = (int*)(&a + 1);     //&a相当于得到二维数组指针,因而&a + 1相当于移动一行

printf("%d\n", *(ptr - 1));    //输出3

6. 指针的移动

int main() {

     int *pi = NULL;

     pi += 15;

     printf("%d\n", pi);     //输出60

     return 0;

}

7. 整数超范围

如果是有符号数,那么最大正整数 + 1 等于最小负整数

如果是无符号数,那么最大正整数 + 1 等于零

bool IsOdd(int i) {

     return (i & 1) == 1;    //不要写成(i % 2) == 1,因为这样写判断负数时会出问题

}

int main() {

     for(int i = 0xFFFFFFFF; i <= 0x7FFFFFFF; ++i) {     //这会陷入死循环,因为最大正整数 + 1 等于最小负数

          cout<

     }

     return 0;

}

8. 基类指针与子类指针

class Base {

     int a;

};

class Zero: public Base {

     int b;

};

int main() {

     Zero *pz = new Zero();

     Base *pb = dynamic_cast(pz);

     (pz == pb) ? (cout<<"Yes\n") : (cout<<"No\n");     //VS2010输出"Yes"

     (int(pz) == int(pb)) ? (cout<<"Yes\n") : (cout<<"No\n");     //VS2010输出"Yes"

     return 0;

}

9. strcpy的写法

char* strcpy(char* dst, const char* src) {     //返回char*是为了方便链式调用

     assert( (src != NULL) && (dst != NULL) );     //特别注意检查

     char* tmp = dst;

     while( *dst++ = *src++ );     //后缀++优先级高

     return tmp;

}

10. 概率题

int main() {

     int cnt = 0;

     for(int i = 0; i < 10000; ++i) {

          int x = rand();

          int y = rand();

          if( x * x + y * y < RAND_MAX * RAND_MAX )     ++cnt;     //实质上是1/4圆与正方形的面积的比较

     }

     printf("%d\n", cnt);     //结果约为PI/4 * 10000

}

11. 以下程序在编译时,哪句会出错

struct Zero {

     void Lin() {}

};

int main() {

     Zero z();     //这样写会被编译器认为是声明一个函数,而不是调用构造函数

     z.lin();     //这句会出错,因为此时的z被认为是未声明的变量

     return 0;

12. 各种排序总结

算法稳定性时间复杂度空间复杂度备注
选择排序FO(n^2)O(1) 
插入排序TO(n^2)O(1)当序列有序时,时间复杂度为O(n)
冒泡排序TO(n^2)O(1)当序列有序时,时间复杂度为O(n)
希尔排序FO(nlogn)O(1)具体的时间复杂度与所选的增量序列有关
归并排序TO(nlogn)O(n) 
堆排序FO(nlogn)O(1) 
快速排序FO(nlogn)O(logn)当序列有序时,时间复杂度恶化为O(n^2)
桶排序TO(n)O(k) 
程序员,面试,宝典,第三,版,笔记,整理,、,指,
栏目:电脑教程 阅读:1000 2023/12/27
Win7教程 更多>>
U盘教程 更多>>
Win10教程 更多>>
魔法猪学院 更多>>

Copyright © 2015-2023 魔法猪 魔法猪系统重装大师

本站发布的系统仅为个人学习测试使用,请在下载后24小时内删除,不得用于任何商业用途,否则后果自负,请支持购买微软正版软件。

在线客服 查看微信 返回顶部