王道程序员求职宝典读书笔记

读书笔记 笔试 面试

---

第一篇、程序设计基础与数据结构基础

基本概念：内存分区

1. 堆：由程序员分配与释放，不同于数据结构中的堆，在C/C++中一般通过malloc/new，free/delete来分配与释放。
2. 栈：由编译器自动分配与释放，存放函数的参数值、局部变量。
3. 全局静态存储区：存放全局变量和静态变量。包括DATA段（全局初始化区）与BSS段（全局未初始化区）。其中，初始化的全局变量与静态变量存放在DATA段，未初始化的全局变量与静态变量存放在BSS段。
4. 文字常量区：常量字符串就是存放在这内存区
5. 程序代码区：存放函数体的二进制代码

第一章、数组

int& a[10];//定义错误，没有数组引用
int a[6] = {1,2,3,4,5,6};
int (&p)[6] = a;//定义了数组a的引用

1.1、数组初始化

数组元素初始化时若没有提供元素初值，则元素会被普通变量一样初始化：
　　
- 函数体外定义的内置类型数组，元素初始化为０，就是存放在DATA区
- 函数体内定义的内置类型数组，元素无初始化（注意，若只初始化部分元素，其后面的元素此时也会变初始化为0）
- 如果不是内置类型，不管在哪里定义，自动调用默认构造函数为其初始化，如没有默认构造函数，编译器则报错。

1.2、C风格字符串与字符数组

C风格字符串包括两种：
1. 字符串常量：以双引号括起来的字符串常量，为了兼容C语言，C++中所有字符串常量都由编译器自动在末尾添加一个空字符，'A'表示单个字符，"A"表示一个字符串常量。
2. 末尾添加'\0'的字符数组

1.3、二维数组的声明与初始化

二维数组声明时，必须指定行与列维数

int a[2][3];
int b[][3];//会编译器报错

只有当初始化时才允许不指定第一维的维数，因为编译器会根据初始化的元素与列数确定行数，同理对于高维数组也是如此。

1.4、数组指针、指针数组与数组名的指针操作

1. 指针数组：数组装的是指针
2. 数组指针：指向数组的指针，它还是指针，只不过是指向数组的指针，二维数组的数组名就是一个数组指针
3. 数组名是一个常量，不能进行赋值操作，如a++,++a等等，需要通过一个指向数组的指针，才能通过指针自增来迭代

int a[4][10];
int (*p)[10];
p = a;//a的类型是int(*)[10],数组指针

例2：针对int a[10];一下表达式不可以表示a1的地址的是 ？
A. a+sizeof(int) B.&a[0]+1 C.(int*)&a+1 D.(int*)((char*)&a+sizeof(int))
&a,&a[0]指向的地址单元都是一样的，在《深入探索C++对象模型》中讲到，指针类型的不一样使得它们如何解释这个地址单元的大小以及内容不一样，这里指向的单元是一样的，通过类型转换，譬如(int*),(char*)等转化到想要的类型

1.5、数组的应用

一维数组可以用来实现线性表的顺序存储
线性表是一个概念，顺序表是线性表的一个实现，链表也是线性表的一个实现

数组乘积
输入：一个长度为n的证书数组input，输出：一个长度为n的整数数组result，满足result[i]=input数组中除了input[i]之外所有数的乘积（假设不会溢出）。T(n)=O(n),S(n)=O(1)

void cal(int* input, int n, int* result){
    result[0] = 1;
    for(int i = 1; i < n; ++i){
        result[i] = result[i-1]*input[i-1];
    }
    result[0] = input[n-1]
    for(int i = n-2; i >=0; --i){
        result[i] *= result[0];
        result[0] *= input[i];
    }
}

主元素
输入：整型数组，输出：找出数组中出现次数超过数组长度一半的数字，（注意是严格大于数组长度一半，且所求数字必定存在）,

int mainElement(int* a, int n){
    int me = a[0];
    int meTimes = 1;
    for(int i = 1; i < n; ++i){
        if(me == a[i]){
            ++meTimes;
        }
        else{
            --meTimes;
            if(meTimes==0){
                me = a[++i];
                meTimes = 1;
            }
        }
    }
    return me;
}

第二章、字符串

2.1、标准库提供的字符串处理函数

stelen(s)
strcmp(s1,s2)//s1>s2返回1
strcat(s1,s2)
strcpy(s1,s2)
strncat(s1,s2,n)
strncpy(s1,s2,n)

要会能够实现这几个函数，注意assert(s1!=NULL)&&assert(s2!=NULL)

2.2、memset，memcpy

void memset(void s,int ch, size_t n);
功能：将s中的前n个字节用ch替换并返回s，注意，第二个参数是int型，实际上这里应该传入char型就好了，因为它是用于替代每一个字节的，所以大于1B的会被切割。
void *memcpy(void dest, const void src, size_t n);
功能：从源src所指的内存地址的起始位置开始拷贝n个字节到目标位置dest所指的内存地址的起始位置，返回dest的指针。

2.3、KMP算法

在长度为M的str中查找长度为N得吃日最好的时间复杂度KMP算法的O(M+N)，主要是利用了已经遍历过的字符串信息，用next数组来存储，不必在从头遍历，与找最长回文子串Manachar算法一样，利用了已经遍历了的字符串信息。

例3、输入两个很大的正数，输出它们的乘积，不考虑非法输入

void multiply(char const* a,char const* b, char* result){
}

例3、删除字符串开头语结尾空格，中间连续空格只保留一个

char* foo(char* a){
    assert(a!=NULL);
    int i = -1;
    while(a[++i]==' ');
    int j = i;
    i = 0;
    while(a[j] != '\0'){
        if(a[j] != ' '){
            if(i < j){
                a[i] = a[j];
            }
            ++i;
            ++j;
        }
        else{
            while(a[++j] == ' '){
            }
            a[i++] = ' ';
        }
    }
    a[i] = '\0';
    return a;
}

第三章、结构体、共同体与枚举

　　由于我是学C++的，更多的是用类，至于结构体比较少用，所以在这里只是蜻蜓点水，只是一些简单的概念。

3.1、结构体的定义：

struct 结构体类型名{
    类型名1 成员名1；
    ...
}

定义结构体与定义枚举一样，只是声明了类型的组成情况，并没有分配内存空间。只有当定义属于结构体的变量时，系统才会分配内存给该变量。注意以下几点

1. 结构体类型中不允许对结构体本身的递归定义，但是可以使用指针指向本类型
2. 结构体定义中可以包括其他结构体
3. 结构体变量定义时同时对对其初始化赋值
   如：

struct person{
    char name[20];
    int age;
} Tom{"Tom",18};

结构体变量初始化是，应将各成员所赋初值依照结构体类型说明中成员的顺序依次放入大括号，不得跳过，如只赋值前面若干，后面的成员中的数值与字符型则自动赋值为零

3.2、结构体中的位字段

struct reg{
    unsigned int a:1;
    unsigned int b:3;
    unsigned int c:4;
}

3.3、共用体union

任何时刻，共用体中只存放了一个被选中的成员，而结构体中的所有成员都存在。对共用体不同成员赋值将会对其他成员重写，原来成员的值就不存在了。
共用体占用内存为各成员中占用最大者内存

3.4、struct的空间计算

struct的空间计算总体上遵循以下两个原则

1. 整体空间是占用空间最大的成员所占字节的整数倍

2. 数据对齐原则，边界调整

   　　含结构体的结构体的空间计算
   在这里我的理解是往下深一层展开
   如

struct s3{
    char c;
    int i;
};
struct s4{
    char c1;
    s3 s;
    char c2;
};
//往下深一层展开就是
struct s4 等价于
struct s4{
    char c1;
    char c;
    int i;
    char c2;
}
sizeof(s4) = 16

　　含有数组的结构体的空间计算,并没有把数组看成一个整体。

    struct s1{
　　    char a[8];
　　    int b;
　　};
　　sizeof(s1) = 12;//不是8的整数倍，就是没有把数组看成一个整体，而且对于数组元素无需边界调整，对于整个数组才需要边界调整到最大成员的所占内存整数倍

3.5、union空间计算

共用体的内存大小是最大成员所占内存的大小

union{
    char b[9];
    int bh[2];
}c;
sizeof(c) = 12;//原因是union把数组看成一个成员，其实结构体也是看成一个成员，只是在算空间时可以当做单个来算。c再加上边界调整，size = 12

3.6、枚举类型的空间计算

enum只是定义了常量集合，里面没有“元素”，而枚举类型是用int整型来存储的，故枚举的sizeof值都是4

enum day{monring,noon,afternoon} today;
sizeof(today) = 4;
sizeof(day_ = 1;//它不占内存，但是为了1B表示占位字节，就像空类一样，也占1B的内存占位字节

第五章、C预处理器、作用域、static、const以及内存管理

5.1、条件编译

#if/ifdef/ifndef
#elif
#else
#endif

如：

#ifndef HEAD_H
#define HEAD_H
...文件内容
#endif

5.2、static作用

1. 隐藏全局变量，当全部变量不加static修饰时，其他源文件都能访问，加了static修饰时，仅是当前源文件能够访问static修饰的全局变量，可以防止命名冲突

2. 默认初始化为0，包括未初始化的全局静态变量与局部静态变量，如：

   static int arr0[10];//这里arr0存放在BSS区，即便没有static，也会初始化为0
   void f(){
   int arr1[10];//不会初始化为0
   static int arr2[10];//会初始化为0
   }

3. 保持局部变量内容的持久性，在函数体内的局部变量调用时就存在，函数退出时就小时，但是使用static修饰的局部变量的生存期为这个源程序，特点是只需要一次初始化且具有记忆性。

类中的static作用：

1. 静态数据成员，只能在类中声明，定义必须在类定义体外部，通常在类的实现文件中进行初始化，static关键词只能出现在声明中，定义时不能出现static
2. 静态成员函数，static成员函数不能声明为const，因为const是承诺不修改this指向的内容，但是static成员函数本来就不属于任何对象，所以加上const是没有任何作用的。同样，static成员函数不能声明为虚函数，也是如此，因为虚函数是通过对象指针调用的，static成员函数不属于任何对象，所以也无法使用指针调用。

5.4、const

　　C++中const限定符把一个对象转换成员一个常量
　　
　　指向const的指针与const指针

int const *p;//星号在const右表示指向的对象是常量
int* const p;//星号在const左边表示指针是常量

　　修饰函数参数与返回值　　　　

void foo(const Person&　p);//传入p的const引用，成本低

　　　　
　　const在类中的应用

1. const成员函数，限定不能修改this指针内容
2. const数据成员，必须在构造函数的初始化列表中进行初始化
   　　

5.5、内存管理与释放

int *p1 = new int[10];//未初始化
int *p2 = new int[10]();//调用默认构造函数初始化为0

第六章、函数

6.1、参数传递

　　传递指针的引用

void ptrSwp(int *&ptr1,int *&ptr2){
    int *t = ptr1;
    ptr1 = ptr2;
    ptr2 = t;
}

6.2、内联函数

　　成员函数成为内联函数，在类中定义的成员函数默认为内联，加上inline时只是建议编译器将它编译成内联函数，但是具体还是看编译器权衡。
　　普通函数成为内联函数，通常是在声明前加入inline，我还是认同上述观点，这仅仅是告诉编译器的一个建议，接不接受是编译器的事情。
　　

第七章、指针与引用

7.1、指针

　　自增优先级比解引用优先级高

*p++ 等价于 *(p++) 

　　void*可以保存任何对象的地址，但是仅仅是保存对象的地址而已，不不能解释对象，因为解释对象还是得靠类型，所以还是得转型，具体可以看到《深入探索Ｃ＋＋对象模型》
　　
　　函数指针，这个太他妈麻烦了，我没有用到过，所以还是忽略算了，等用到再接触，对于函数指针我有我的看法，我认为java面向接口编程传递接口比传递函数指针舒服多了。
　　

7.2、引用

　　引用就是有对象的另一个名字，本质上来说，引用是有限定的指针，只不过这个指针不能被修改，所以C++规划一旦定义了引用，必须接着初始化，之后也不能再修改这个引用。
　　
　　引用与指针的区别
1. 引用不能为空，定义并要初始化，指针可以为空值
2. 引用不能修改，指针可以修改
3. 不能有NULL引用，可以有指向NULL的指针
4. sizeof(引用)得到的引用指向对象的大小，sizeof(指针)得到的是指针的大小
5. 对引用操作时，实际上是对引用绑定的对象进行操作
6. 引用使用时跟原变量一样直接使用，不需要像指针一样需要解引用。

　　引用做类的数据成员时

1. 不能直接在构造函数中初始化，必须在初始化列表当中初始化引用
2. 凡是有引用类型的数据成员的类必须定义构造函数

第八章、类

8.1、成员初始化列表

在构造函数的冒号与之间成为构造函数的初始化列表，初始化列表可以为一个或者多个数据成员指定初值，包括const成员、引用成员，如：

class A{
private:
    int i;
    const int j;
    int& k;
public:
    A(int x, int y, int z):i(x),j(y),z(k){
        ...
    }
};

　　尽量使用初始化列表初始化数据成员，这个比在构造函数体中赋值高效，因为在初始化列表指定了初始化，在初始化成员数据时已经调用了对用的构造函数，而不是默认构造函数，然后再赋值，很明显一步到位调用对应的构造函数更好。
　　在C++中，成员变量的初始化顺序与变量在类型中的声明顺序相同，而与它们在构造函数中的初始化列表的顺序无关。
　

8.2、析构函数

　　一般来说，如果类中定义了虚函数，就说明了这个类是有多态性，这样子就应该把析构函数声明为虚函数，防止在多态使用过程中资源释放失败，造成内存泄露。

8.3、派生类的构造函数与析构函数

　　派生时，构造函数与析构函数时不能够继承的，为了对基类成员进行初始化，必须在派生类重新定义构造函数与析构函数，并且在派生类构造函数的初始化列表调用基类的构造函数。
　　由于派生类函数基类的数据成员，因此，创建派生类对象时，系统首先通过派生类的构造函数调用基类的构造函数完成基类成员的初始化，然后再初始化派生类中新增加的数据成员。
　　析构函数的调用顺序与构造函数的调用顺序相反，先派生类的析构函数然后再基类的析构函数。

8.4、拷贝构造函数与赋值构造函数的区别

　　拷贝构造函数从无到有构造了一个对象，而赋值构造函数仅是改变了一个现成的对象。

Car benz("benz",200);//车子牌子benz，价格200万
Car b(benz);//从无到有拷贝构造了一个新的benz
Car lam("Lamborghini",300);
Car l = lam;//这里虽然是赋值拷贝函数，其实它也是一个从无到有的过程，编译器会自动优化调用拷贝构造函数
l = ben;//修改现成的一个对象，调用赋值构造函数

8.5、成员函数的重载、覆盖与隐藏

　　重载：横向，成员函数的重载与普通函数的重载一样，只是参数列表不一样
　　覆盖：纵向，在派生类中覆盖了基类的同名函数，要求基类函数必须是虚函数，与基类的虚函数有相同的参数列表与返回值，简单来说，覆盖针对虚函数。
　　隐藏：纵向，派生类覆盖了基类的同名函数，只需要同名就会覆盖，不一定是同参数列表，简单来说，凡是基类中与派生类新增的同名函数都会被覆盖。
　　
第九章、面向对象编程

9.1、类型转换函数

class Integer{
public:
    Integer(int i = 0)//int型可隐式转换为Integer型
    {
        n = i;
    }
    operator int()//Intege型可隐式转换为int型，括号前面的int就是目标类名
    {
        return n;
    }
private:
    int n;
};
int main(){
    Integer i = 1;//等价于Integer i = Integer(1);
    int j = i;//调用了operator int()转换函数，等价于int j = i.operator int();
}

9.2、动态运行时类型识别与显示转换

　　通过运行时类型识别RTII，程序能够使用基类的指针或者引用来检索指针或者引用所指对象的实际类型

1. typeid操作符，返回指针或者引用所指对象的实际类型
2. dynamic_cast操作符，将基类类型的指针或者引用安全地向下转型
   　　

Base* b;
Derived* d;
if(typeid(*b) == typeid(*d)){...}
if(typeid(*b) == typeid(Derived)){...}

第十章、动态规划与贪心算法

10.1、动态规划

　　LCS最长公共子序列问题
　　它不要求所求得的字符串是连续的，例如ABCBDAB与BDCABA的最长公共子序列是BCBA或者BDAB，最长公共子序列是一道非常经典的动态规划问题，因此很多重视算法的公司都会用它来当做笔试、面试题
　　例1、请编写一个函数，输入两个字符串，求它们的最长公共子序列，输出最长公共子序列长度

c[i][j]表示xStr的前i个字符与yStr的前j个字符的最长公共子序列长度
int LCS_length(const char* xStr, const char* yStr, int c[][maxSize]){
    if(xStr==NULL||yStr==NULL){
        return 0;
    }
    int xLen = strlen(xStr), yLen = strlen(yStr);
    for(int i = 0; i <= xLen; ++i){
        c[i][0] = 0;
    }
    for(int j = 0; j <= yLen; ++j){
        c[0][j] = 0;
    }
    for(int i = 0； i < xLen; ++i){
        for(int j = 0; j < yLen; ++j){
            if(xStr[i] == yStr[j]){
                c[i+1][j+1] = c[i][j] + 1;
            }
            else{
                c[i+1][j+1] = max(c[i+1][j],c[i][j+1]);
            }
        }
    }
    return c[xLen][yLen];
}

　
　　例2、给定一个源串和目标串，能够对串进行如下操作：
　　1. 在给定位置插入一个字符
　　2. 替换任意一个字符
　　3. 删除任意字符
　　写一个程序，返回最小操作数，使得进行这些操作之后源串与目标串一样，源串与目标串的长度均小于2000
　　考虑如何将问题转换为规模较小的同样的子问题：
　　1. 一步之后使得src[0~sLen-2]与des[0~dLen-1]一样
　　2. 一步之后使得src[0~sLen-1[与des[0~dLen-2]一样
　　3. 一步之后使得src[0~sLen-2]与des[0~dLen-2]一样
　　按照这思路写出函数

d[i][j]表示src的前i个字符组成的字符串与des前j个字符组成的字符串的距离
int dist(const char* src, const char* des, int d[][maxSize]){
    int sLen = strlen(src0, dLen = strlen(des);
    for(int i = 0; i <= sLen; ++i){
        d[i][0] = i;
    }
    for(int j = 0; j < dLen; ++j){
        d[0][j] = j;
    }
    for(int i = 0; i < sLen; ++i){
        for(int j = 0; j < dLen; ++j){
            if(src[i] == des[j]){
                d[i+1][j+1] = d[i][j];
            }
            else{
                d[i+1][j+1] = min(d[i+1][j],d[i][j+1]) + 1;
            }
        }
    }
    return d[sLen][dLen];
}

10.2、贪心算法

根据以下步骤来设计贪心算法：

1. 将优化问题转化成这样的一个问题，先做选择，然后再解决剩下的一个子问题
2. 证明原问题总是有一个最优解是做贪心选择得到的，从而证明贪心选择是安全

3. 说明在做出贪心选择之后，剩余的子问题具有这样的一个性质：子问题的最优解和贪心选择做联合一起，可以得到原问题的最优解

   　　贪心算法通常是自顶下下的，一个一个地做出贪心选择，不断地给定问题实例规划为更小的问题，最小生成树以及dijstra的单元最短路径算法都可以视为贪心算法的应用

第十一章、链表

10.1、单链表

通常用头指针来标致一个单链表，头指针指向单链表中的第一个结点的指针

10.2、顺序表与链表的比较

1. 存取方式：顺序表可以随机存取，链表只能从表头顺序存取元素
2. 查找、插入和删除操作：按值查找，在无序的情况下，二者都是O(n)，有序时可以使用二分查找，顺序表达到O(logn)时间复杂度；插入语删除顺序表需要移动元素的时间复杂度(n)，而链表则是O(1)，当然这是得给定位置的指针。
3. 空间分配：这个链表的分配比较灵活

10.2、快慢指针

判断单向链表是否存在环
寻找循环链表的入口，这里涉及一个数学问题，我是想不起来的，我只能翻查资料。在有序链表中查找中位数
判断两个单向链表是否相交，如果相交找出第一个公共结点（注意有环）
判断两个带环的单向链表是否相交（提示，判断相遇点是否在另一链表上即可）

第十二章、栈与队列

12.1、栈

Catalan数
有效出栈序列
例1：图书馆没有某本书了，现在有6个人排队，有3个人借此书，3人还此书，且弱到某人借书时，若书便马上离开，问有多少种排队方法保证3个人都能借到书？

12.2、队列

head == tail 表示空
head == (tail+1)%m,m是数组大小
队列存放元素个数为(tail-head+m)%m

第十三章、树

12.1、二叉树

深度是根结点开始自顶向下逐层累加的
高度是自叶结点子底下上逐层累加的，但是从哪一个叶子结点算，我认为是最深那一个
求二叉树中结点的最大距离
两个结点的距离定义为两个结点之间边的个数，思路求出当前左子树、右子树结点的最大距离，并且求出左子树、右子树的深度，然后就可以写出递归源代码了。

例1、一棵二叉树每一个结点包含一个整数，请设计一个算法输出所有满足条件的路径：此路径上所有结点之和等于给定的值，注意路径不需要从根结点出发。@P223

例2、判断一棵二叉树是不是二叉排序树（考虑中序遍历）

13.2、哈佛曼树与编码

第十四章、图

14.1、最小生成树

Prim算法与Kruskal算法都基于贪心算法的策略
Prim是找最近点，找够n个相连的点即可
Kruskal是找最小权边，边数等于n-1时自然会相连

14.2、最短路径

单源到各点的最短路径使用Diskstra算，基于贪心算法
各点之间的最短路径使用Floyd算法求解，基于动态规划

第十五章、排序

15.1、希尔排序

基本思想：先将待排序表分割子表，分别进行直接插入排序，当整个表呈现“基本有序”时，再对全体记录进行一次插入排序，增长序列不好确定，通常是每一次二分之一的幂

15.2、冒泡排序、快速排序

　　冒泡排序的基本思想：从后往前（或者从前往后，看需要升序还是降序），若为逆序，则交换它们，直到序列比较完。当升序时，从后遍历，每一次将当前的最小上浮
　　快速排序的基本思想：基本思想基于分治法：关键是划分算法partition()，有一种方法就是取首尾加中间的数的平均数作为基准来获得好的二分效果。

15.3、简单选择排序

每一次选出当前序列最小（大）值与当前序列的首尾交换

15.4、堆排序

堆排序时一种属性选择排序法，利用完全二叉树中双亲结点与孩子结点之间的内在关系，在当前无序区选择最大或者最小元素
初始化堆需要O(n)，恢复堆结构需O($log_2n$)
平均时间复杂度O($nlog_2n$)

15.5、归并排序

假定排序表含有n个记录，则可以视为n个有序子表，然后不断两两合并，直到剩下一个长度为n的有序表。

15.6、多路归并排序

基本思想将源文件分解成多个能够一次性装入内存，分别把每一部分调入内存完成排序，然后使用多人打擂台的方法选出当前最小值或者最大值放入输出文件中，多人打擂台就是一个败者树。

16、查找

16.1、折半查找：

int binSearch(int* a, int begin, int end, int k){
    int mid = begin + ( (end - begin)>>1 ),index;
    index = a[mid] < k && begin + 1 < end ? binSearch(a,mid+1,end,k) : 
          ( a[mid] > k && begin + 1 < end ? binSearch(a,begin,mid,k) : 
            mid * (a[mid] == k) + (a[mid] != k)*(-1));
    return index;    
}

16.2、键树、字典树

如果以树的多重链表表示键树，则树的每一个结点中包含d个指针域，d=26时，成为Trie树（26个字母嘛）
Tire树思想是利用字符串的公共前缀降低时空开销
Trie树的典型应用是用于统计和排序大量字符串，经常被搜索引擎系统用于文本词频统计

16.3、后缀树与后缀数组

后缀树实现比较复杂，通常用其变形的后缀数组代替
例1、有串abcdabcd，最长重复子串是abcd。
使用后缀数组表示
a[0]:abcdabcd,
a1:bcdabcd,
a[2]:cdabcd,
a[3]:dabcd,
a[4]:abcd,
a[5]:bcd,
a[6]:cd,
a[7]:d
然后对后缀数组排序，将后缀相邻的子串集中在一起就可以找到最长重复子串。

16.4、哈希表处理冲突的方法：

1. 链地址法
2. 开放地址法$H_i=(H(key)+d_i)$%$m$,当$d_i$是1,...,m-1时，线性探测法，当$d_i$为1，$2^2$,$3^2$,$(m-1)^2$时称为二次探测法
3. 再散列法
4. 简历一个公共溢出区

16.5、海量数据处理

hash映射
位图bitmap

第二篇、计算机网络基础

第一章、计算机网络模型

1.1、OSI模型

OSI有七层：物理层、数据链路层、网络层、传输层、会话层、表示层与应用层
每一张网卡都一个全球唯一固定的48位的MAC地址

1.2、TCP/IP模型

TCP/IP有四层：网络接口层、网络层、传输层与应用层
传输层主要使用
传输控制协议（TCP），面向连接的，可靠传输
用户数据报协议（UDP），面向无连接的，不可靠传输

第二章、传输层

2.1、TCP与UDP协议

UDP是一种无连接协议，UDP不可靠，不能保证最终达到它们的目的地，不能保证每一个数据包的先后顺序不变
TCP是一种面向连接的协议

• 提供客户与服务器之间的连接
• 提供可靠性，要求有确认
• TCP通过给数据包每一个字节管理一个序列号进行排序
• 提供流量控制
• 连接是双工的
  UDP与TCP主要区别在于UDP不一定提供可靠的数据传输。事实上，该协议不能保证数据准确无误地到达目的地。UDP在许多方面非常有效，快速性、实时性、网络开销小。

2.2、TCP的建立与终止

三次握手建立连接
客户端向服务器发送一个同步序列号SYN J
服务器响应一个同步序列号SYN K，并对SYN J进行确认 ACK J+1
客户端在想服务器发送一个确认ACK K+1
为了保证服务端能收接受到客户端的信息并能做出正确的应答而进行前两次(第一次和第二次)握手，为了保证客户端能够接收到服务端的信息并能做出正确的应答而进行后两次(第二次和第三次)握手。

四次挥手释放连接
客户端发送FIN，客户端接受ACK，服务端发送FIN，服务端接受ACK，连接释放
由于TCP连接是全双工的，因此每个方向都必须单独进行关闭。这原则是当一方完成它的数据发送任务后就能发送一个FIN来终止这个方向的连接。收到一个 FIN只意味着这一方向上没有数据流动，一个TCP连接在收到一个FIN后仍能发送数据。首先进行关闭的一方将执行主动关闭，而另一方执行被动关闭。

第三章、网络层

3.1、IPv4地址与网络地址转换NAT

IP地址，网络类型+网络地址+主机地址
A类：0+7+24 子网掩码是255.0.0.0
B类：10+14+16 子网掩码是255.255.0.0
C类：110+21+8 子网掩码是255.255.255.0
D类：1110+多目的广播地址28位
E类：11110+保留实验和将来用途27位

主机号全为0表示本网络本身
主机号全为1表示本网络的广播地址
127.0.0.1表示任意主机本身,Hadoop伪分布中的localhost

NAT与私有地址
私有地址段：
10.0.0.0~10.255.255.255
172.16.0.0~172.31.255.255
192.168.0.0~192.168.255.255

第三篇、操作系统基础

操作系统有四个特征：并发，共享，异步，虚拟
并发，两个或者多个时间在同一时间间隔内发生，单处理器系统中任何一个时刻只有一个占用处理器。宏观上程序是并发执行的，微观上看程序是分时交替执行。操作系统的并发性通过分时得以实现。
共享，系统中的资源（硬件资源和信息资源）可以被多个并发执行的程序共同使用，而不是被任何一个独占。资源共享有两种方式：互斥访问和同时访问。并发与共享是操作系统的最基本特征，互为依存。并发执行的要求引出了资源的共享；资源共享的管理又影响到程序的并发执行。
异步，在多道程序环境下，程序并发执行，但是由于资源有限，进程不是一贯到底，而是走走停停，以不可预知的速度向前推进。
虚拟，虚拟性是一种管理技术，把物理上的实体变成逻辑上的多个对应物，或把物理上的多个实体变成逻辑上的一个对应物的技术。

操作系统的功能包括：处理器管理、存储器管理、文件管理、设备管理

第一章、进程管理

1.1、进程与线程概念

进程，计算机中已运行程序的实体，是系统进行资源分配和调度的一个独立单位
进程有3个基本状态，运行状态、就绪状态与阻塞状态
线程，进程的一个实体,是处理器调度和分派的基本单位,它是比进程更小的能独立运行的基本单位，只拥有一点点必不可少的资源，与当前进程下所有线程共享进程的资源、
可以参考阮一峰的博文《进程与线程的一个简单解释》

1.2、进程通信与进程同步

进程同步机制有四种方式：临界区、互斥量、信号量与事件四种方式

• 1、临界区：通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。在任意时刻只允许一个线程对共享资源进行访问，如果有多个线程试图访问公共资源，那么在有一个线程进入后，其他试图访问公共资源的线程将被挂起，并一直等到进入临界区的线程离开，临界区在被释放后，其他线程才可以抢占
• 2、互斥量：采用互斥对象机制。 只有拥有互斥对象的线程才有访问公共资源的权限，因为互斥对象只有一个，所以能保证公共资源不会同时被多个线程访问。互斥不仅能实现同一应用程序的公共资源安全共享，还能实现不同应用程序的公共资源安全共享.互斥量比临界区复杂。因为使用互斥不仅仅能够在同一应用程序不同线程中实现资源的安全共享，而且可以在不同应用程序的线程之间实现对资源的安全共享。
• 3、信号量：它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目.信号量对象对线程的同步方式与前面几种方法不同，信号允许多个线程同时使用共享资源，这与操作系统中的PV操作相同。它指出了同时访问共享资源的线程最大数目。它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目。
• 4、事 件： 通过通知操作的方式来保持线程的同步，还可以方便实现对多个线程的优先级比较的操作 .

1.3、死锁

死锁是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将无法向前推进。
死锁产生的四个必要条件：互斥条件、不剥夺条件、请求与保持条件与循环等待条件死锁处理策略，预防死锁、避免死锁，银行家算法就是避免死锁算法
死锁的解除主要方法如下：
资源剥夺法
撤销进程法
进程回退法

第二章、内存管理

2.1、内管管理方式

内存分配管理方式包括连续分配管理方式与非连续分配管理方式

基本分页存储管理方式
分页存储的几个基本概念：

• 页面与页面大小，进程中的块称为页
• 地址结构，高位是页号，地位是页内偏移量
• 页表，为了便于在内存中找到进程的每一个页面所对应的物理块，系统为每一个进程建立一个页表，页表记录内存中对应的物理块号。
  基本分段储存管理方式
  段页式管理方式，先查段号再查页号找到物理块号，通过偏移量找到内存的内容。

2.2、虚拟内存

基于局部性原理，在程序装入时，可以将程序的一部分装入，而其他留在外存，就可以启动执行程序了，在执行过程中，当访问的信息不在内存中时，由操作系统将所需的部分调入内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容调出到外存，腾出内存空间。这样子操作系统好像为用户提供了一个比实际内存要大得多的存储器，称为虚拟存储器。
虚拟存储器有三种实现方式：
请求分页存储管理，请求分段存储管理，请求段页式存储管理
请求分页存储管理方式：
最佳值换算法置换OPT
FIFO置换算法
最近最近未使用置换算法（LRU）

抖动，就是内存换出去不久有换进来，反反复复。