数组

什么是大O

n表示数据规模，则表示运行算法所需要执行的指令数，和成正比。

一个算法有多个步骤，每个步骤规模相同但时间复杂度不同，最终的时间复杂度以最高的那个为准。

对数据规模的概念

如果想要在1s之内解决问题：

• 的算法可以处理大约级别的数据；
• 的算法可以处理大约级别的数据；
• 的算法可以处理大约级别的数据；

这个结论只是执行简单的数据操作，实际还需要再低估一下。

空间复杂度

• 多开一个辅助数组：;
• 多开一个辅助的二维数组：
• 多开常数空间：;

需要注意：递归调用是有空间代价的，递归的深度就是空间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

//计算n以内数据的和

//空间复杂度O(1)
int sum1(int n)
{
    assert(n >= 0);
    int ret = 0;
    for(int i=0;i<=n;i++)
    {
        ret += i;
    }
    return ret;
}

//递归调用：空间复杂度O(n)
int sum2(int n)
{
    assert(n>=0);
    if(n == 0)
        return 0;

    return n + sum2(n-1);
}

简单的时间复杂度分析

O(1)

常数级的算法很简单，没有数据规模的变化

1
2
3
4
5
6
7

// O(1)
void swapTwoInts(int &a , int &b){
    int temp = a;
    a = b;
    b = temp;
    return;
}

O(n)

O(n)的算法典型的特征就是有个循环，并且循环的次数和n相关。

其实正常来说，应该是，其中C是个常数，且不一定大于1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// O(n)
int sum(int n){

    assert(n >= 0);

    int ret = 0;
    for( int i = 0 ; i <= n ; i ++ )
        ret += i;
    return ret;
}

//字符串反转，只需要进行1/2次的swap操作即可
void reverse(string &s){

    int n = s.size();
    for(int i = 0 ; i < n/2 ; i ++)
        swap( s[i] , s[n-1-i] );
    return;
}

O(n^2)

见到算法内部有双重循环，每层循环都是n相关基本就八九不离十了。

1
2
3
4
5
6
7
8
9
10
11
12

//选择排序算法
void selectionSort(int arr[], int n){

    for(int i = 0 ; i < n ; i ++){
        int minIndex = i;
        for( int j = i + 1 ; j < n ; j ++ )
            if( arr[j] < arr[minIndex] )
                minIndex = j;

        swap( arr[i] , arr[minIndex] );
    }
}

千万要注意两层循环都要和n相关，不要看到双重循环就认为是

1
2
3
4
5
6
7
8
9
10

//第二重循环哪怕循环300w次，这个也是O(n)
void printInformation(int n){

    for( int i = 1 ; i <= n ; i ++ )
        for( int j = 1 ; j <= 30 ; j ++ )
            cout << "Class " << i << " - " << "No. " << j << endl;
    return;
}

O(logn)

经典的二分查找法：

1
2
3
4
5
6
7
8
9
10
11
12

//二分查找法
int binarySearch(int arr[], int n, int target){

    int l = 0, r = n-1;
    while( l <= r ){
        int mid = l + (r-l)/2;
        if(arr[mid] == target) return mid;
        if(arr[mid] > target) r = mid - 1;
        else l = mid + 1;
    }
    return -1;
}

将数字整形转化为字符串：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

string intToString(int num){

    string s = "";
    string sign = "+";
    if(num < 0){
        num = -num;
        sign = "-";
    }

    while(num){
        s += '0' + num % 10;
        num /= 10;
    }

    if(s == "")
        s = "0";

    reverse(s);
    if(sign == "-")
        return sign + s;
    else
        return s;
}

分析算法思想，核心在" num /= 10"步中，就是n经过几次“除以10”操作后等于0，那么就是;

虽然上面两个例子，一个是以2为底，一个是以10为底，但都是，这个可以通过对数函数的换底公式来理解：有换底公式，可见和之间只相差一个常数，在时间复杂度下可以直接理解为

还需要注意，双重循环也可能出现logN的复杂度，需要注意量增长的规模：

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

//复杂度:O(nlogn)
void hello(int n){

    for( int sz = 1 ; sz < n ; sz += sz )
        for( int i = 1 ; i < n ; i ++ )
            cout << "Hello, Algorithm!" << endl;
}

//外层循环每次增长可以理解为sz*2
//其实就可以理解为n经过几次“除以2”的操作后等于1，外层循环复杂度O(logn)
//内层循环复杂度是O(n)
//合起来是O(nlogn)



//判断是否为素数
// O(sqrt(n))
bool isPrime(int num){

    if( num <= 1 ) return false;
    if( num == 2 ) return true;
    if( num % 2 == 0 ) return false;

    for(int x = 3 ; x * x <= num ; x += 2)
        if( num%x == 0 )
            return false;

    return true;
}

//

递归算法的复杂度分析

面对递归算法需要具体问题具体分析。

递归中只会进行一次递归调用

如果递归函数中只进行一次递归调用，递归深度为depth，在每个递归函数中的时间复杂度为T，则总体的时间复杂度为，既只需关注递归的深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//递归调用的二分查找法
int binarySearch(int arr[], int l, int r, int target){

    if(l > r)
        return -1;

    int mid = l + (r - l) / 2;
    if(arr[mid] == target)
        return mid;
    else if(arr[mid] > target)
        return binarySearch(arr, l, mid - 1, target);
    else
        return binarySearch(arr, mid + 1, r, target);

}

  二分查找法很容易用递归实现，上述代码每次调用时，内部要么直接返回，要么数组左半边调用递归，要么数组右半边调用递归，只会调用一次，所以分析时间复杂度只有看递归的深度即可。

  每次调用数组减少一半，是典型的logn情况，所以复杂度为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// sum,O(n)
int sum(int n){

    assert(n >= 0);

    if(n == 0)
        return 0;
    return n + sum(n - 1);
}

// 求x的n次方：O(logn)
double pow(double x, int n){

    assert(n >= 0);

    if(n == 0)
        return 1.0;

    double t = pow(x, n / 2); //每次减半，logn
    if(n % 2)
        return x * t * t;

    return t * t;
}

递归中进行多次递归调用

当递归中有多次递归调用时，就需要关注递归调用的次数了。如果递归中只调用一次，深度就是次数，但如果调用了多次，那么深度和次数就是两个概念了。

1
2
3
4
5
6
7
8
9
10
11

//O(2^n)
//这个是指数级的算法，是个非常慢的算法
int f(int n)
{
    assert(n >= 0);

    if(n == 0)
        return 1;

    return f(n-1) + f(n-1);
}

均摊复杂度分析

  有时候会遇到这种情况：解决某个问题时运用了一系列算法，某个算法的复杂度很高，但这个算法可以降低其他算法的复杂度，这时候就需要计算分摊复杂度。

  均摊复杂度的经典问题就是动态数组vector。

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

template <typename T>
class MyVector{

private:
    T* data;
    int size;       // 存储数组中的元素个数
    int capacity;   // 存储数组中可以容纳的最大的元素个数

    // 复杂度为 O(n)
    void resize(int newCapacity){

        assert(newCapacity >= size);
        T *newData = new T[newCapacity];
        for( int i = 0 ; i < size ; i ++ )
            newData[i] = data[i];
        delete[] data;

        data = newData;
        capacity = newCapacity;
    }

public:
    MyVector(){

        data = new T[100];
        size = 0;
        capacity = 100;
    }

    ~MyVector(){

        delete[] data;
    }

    // 平均复杂度为 O(1)
    void push_back(T e){
        //当元素到达容量上限时，需要调用resize扩大空间
        if(size == capacity)
            resize(2 * capacity);

        data[size++] = e;
    }

    // 平均复杂度为 O(1)
    T pop_back(){

        assert(size > 0);
        size --;

        return data[size];
    }

};

  上面的代码只在push操作时resize了空间，但是没有在pop操作时resize空间。我们当然可以参考push操作，在pop到capacity一半时resize容量，但这里涉及一个问题，就是要防止复杂度震荡。

  考虑这个问题：当push到临界点时resize一倍空间，然后立即pop，此时又resize为一半，然后立即push，这种极端场景下时间复杂度无法均摊，会退化为。

  如果想避免这种场景，可以不再临界点处resize，当pop操作到达capacity的1/4处时，resize为1/2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 平均复杂度为 O(1)
T pop_back(){

    assert(size > 0);
    T ret = data[size-1]; //这里一定要提前拿出来，resize操作会修改data
    size --;

    // 在size达到静态数组最大容量的1/4时才进行resize
    // resize的容量是当前最大容量的1/2
    // 防止复杂度的震荡
    if(size == capacity / 4)
        resize(capacity / 2);

    return ret;
}

基本厨具

• 锅具
  • 炒锅：万能的，煎炒烹炸样样精通；
  • 汤锅：用于煮面条或者烧水；
  • 平底不粘锅：用于煎饼、煎肉；
  • 小奶锅：做快手菜
• 菜刀
  • 切刀：刃薄，锋利，适合切菜；
  • 砍刀：刃厚，稍微钝，适合砍骨头；

家中必备调理

• 生抽
• 陈醋
• 油
• 大蒜
• 生姜
• 淀粉
• 鸡精
• 味精
• 盐

以上9个调料可以应付80%的家常菜。可以适当添加以下几种扩充：

• 料酒
• 豆瓣酱
• 干辣椒
• 白糖
• 胡椒粉

认识盐

  盐是百味的基础，做菜时别的调料可以不放，但绝对不能少了盐。放盐的原则：宁少勿多！！

煎鸡蛋

1. 碗中打入两个鸡蛋，加入适量食盐，一个鸡蛋就是一个小指甲盖那么多的盐；
2. 用筷子把鸡蛋打散。左手拿碗可以稍微向右手倾斜，不容易撒出去。打10多秒即可，目的是让蛋清和蛋黄混在一起；
3. 开火，把锅中水分烧干；
4. 倒油，用油把锅底润一下；
5. 油冒烟后，倒入鸡蛋；
6. 鸡蛋蛋清凝固后记得用锅铲捅破，让里面蛋黄流出来，否则里面煎不到；
7. 蛋液定型后翻面，一面不要煎太久，多操作几次，两面金黄即可捞出；

注意，油少或者油温过高，容易煎糊；油温太低，煎出的蛋不够松软。

荷包蛋

1. 小火，倒入少许的油；
2. 油在微微冒烟时，打一个鸡蛋下去，让鸡蛋在油里慢慢的煎，等定型（边缘变的焦黄）后翻面；
3. 撒上少许盐，倒在手掌上分开撒，再翻面；
4. 多翻面，让每一面都接触到盐，然后盛出；

  喜欢溏心蛋的可以少煎一会或者只煎一面，不过从营养学的角度来说不建议吃溏心蛋，溏心蛋没有熟，不利于人体吸收。全熟蛋杀菌效果更彻底，更利于健康。

味精与鸡精

  鸡精和味精主要用于调味，放很少一点就可以成倍的提升菜品的口味。不过很多人认为鸡精和味精有害，尤其是味精在加热到120度后会生成焦谷氨酸钠，可能致癌。但有论文指出适量吃鸡精和味精都是安全的。只需要注意味精温度过高会失去鲜味，所以只在出锅前加味精。

炒空心菜——味精和鸡精的运用

1. 择菜——把食材处理的长短大小统一，方便食用，方便烹饪；把叶子都摘下来，如果空心菜不是很老，那么根部也可以留着，只要用指甲掐一下根部，能掐动就代表还不老；
2. 洗菜，把泥沙充分洗掉，淘洗就行，不要用手搓；洗完用滤网捞出来；
3. 开火，直接开最大的火，把锅里水烧干；
4. 倒油，对于铁锅来说宁多勿少防止炒糊；
5. 油开始冒烟后倒入蔬菜，动作一定要快，用菜把油盖住防止砰溅；绿叶菜很容易熟，所以需要经常的翻炒，每隔几秒钟就翻炒一下；这个就看火大小，火大勤翻炒，火小慢翻炒；
6. 叶子快蔫掉时代表快熟了，此时放调料，放入盐、鸡精、味精，撒开一点。盐要多放一点（因为蔬菜的水多），鸡精和味精用量是盐的1/4~1/5即可，鸡精可以更少；放入调料后疯狂翻炒，让调料均匀；

鸡精和味精一起使用有1+1>2的效果。

用旺火炒菜的原因：用旺火炒菜更好吃，且蔬菜中有很多的维生素被加热后容易流失，所以用旺火炒菜可以尽快的出锅。

炒菜的第一个公式

油+菜+盐+鸡精\味精 -> 出锅。先把油烧热，放入菜，菜快熟的时候放入盐、鸡精、味精，把调理和匀就可以出锅了。至少80%带叶子的蔬菜都可以这么做。

翻炒时注意，如果菜的茎叶比较厚实，类似白菜，就可以适当减少翻炒的频率。

放调料的时候可以先放到锅铲上，这样可以控制用量，也方便和均匀。

根据经验来看，有些蔬菜含水量很大，炒菜后的汤水会很多，这时候要么选择把汤汁倒掉，要么就多放盐。

干辣椒、大蒜、花椒

干辣椒、大蒜、花椒也属于调料的范畴，不过他们是土里长出来的天然调料，一样可以增加食品的风味。这三个是川菜中的三剑客，经常形影不离。

新手炒菜容易把这些配料炒糊，因为油温太高了。在熟能生巧之前，可以在放入油后立马下锅配料。

炒菜苔

  菜苔择菜的时候需要一点小技巧，用一把刀从根部切十字，第一刀切到第二片叶子的位置，第二刀切到第三片叶子的位置。然后从第三片叶子稍微往上一点的地方切掉，这样就是一个十字花刀的形状，方便炒熟也方便入味。剩下的部分很细，切一刀就可以了。菜苔上有花的话把花去掉，口感不好。如果买来的菜苔根部很老的话，还需要先去根部的皮。

  一盘菜用三颗大蒜，三个干辣椒，几粒干花椒：

• 用到把干辣椒切成一厘米长的段；
• 大蒜剥皮，剥皮最快的方法就是用菜刀拍。然后把大蒜切成片。

炒菜步骤：

1. 烧半锅水，水开后把菜苔焯水（菜苔的茎太厚了，不好炒，需要提前焯水），煮1分钟到1分半即可，不要太久，否则就不脆了；
2. 把菜苔倒入滤网中，用冷水冲，可以保持爽脆口感；
3. 锅烧干后倒油，然后马上放入准备好的干花椒、干辣椒；看到干辣椒微微发黑的时候放大蒜，然后立即放入准备好的菜；
4. 提前焯水后菜基本已经熟了，所以翻炒片刻就可以放盐、味精、鸡精，和匀后出锅；

手撕莲白

洋葱、大白菜、卷心菜等都需要去掉外边1到2层，之地很老，卖相差，口感也不好。

然后把莲白一层一层的拨下来，每一片叶子在随意撕成片。手撕的比刀切的好吃，因为手撕的断面不整齐，更容易入味。只要叶子部分，菜帮子可以丢掉。撕完之后清洗滤水。

依旧准备大蒜、干辣椒、干花椒。莲白菜不需要焯水。

素炒四季豆

四季豆的挑选：粗壮的四季豆口感稍微老，但是四季豆味道足，缺点是筋多；细长的四季豆口感更细嫩。挑选时看表面有没有黑点或者坑坑洼洼的，这可能被虫子咬过。

四季豆比较耐放，在冰箱中放7~10天没问题。

四季豆择菜时要把两侧的筋去掉，从头部的尖开始，逆着尖使劲往后一拉就行，然后把尾巴掐下一点，逆着把另一侧筋去掉。两侧筋都去掉后，把四季豆恰成5厘米左右的段，这时中间一些没有去掉的筋就露出来了，可以去掉。

四季豆没有泥沙，清洗时使劲拿手和一下就行。

素炒四季豆的配料，可以准备2_{3瓣大蒜切片。还有一个秘密武器：留兰香（食用薄荷），取顶端的部分，掐5}6根左右，用刀稍微切碎即可。

生的四季豆吃了会引起食物中毒，所以四季豆的做法要分两步：先制熟，然后回锅调味。

在饭店里制熟四季豆，用的是大量热油，又快又好吃，但是家里这样做太浪费了。家里比较经济实惠的方法就是用水煮，把四季豆放入锅中，加水，水要稍微没过四季豆。盖上盖子大火烧开，然后转中火再煮5~10分钟。出锅后用凉水冲一下口感更佳。

剩下的步骤很简单：大火烧干锅，放油、放入大蒜，放入四季豆翻炒。不过四季豆很难入味，所以需要更早的时候放入盐，然后再翻炒两三分钟。最后调为中火再煎两三分钟。出锅前放入鸡精、味精、食用薄荷，翻炒几秒把薄荷炒到打蔫即可出锅。

豇豆、扁豆都可以用这个方法来做。

六大基酒

伏特加

  鸡尾酒中的万金油，突出纯净，就像一张空白画纸，可以填充任意的风味和材料，包括果汁、咖啡和奶茶。不知道喝什么，但就是想喝酒的时候，选择伏特加就不会出错。推荐：斯米诺、SKYY、绝对伏特加；如果想要品质好的伏特加，可以选绝对亦乐、灰雁。

金酒

  金酒又被称作风味伏特加，是在蒸馏烈酒的基础上加以杜松子为首的各种香料和草本来增加风味。所以金酒最大的特点就是有草本气息。不同品牌做出的风味不一样。推荐必富达、添加利、孟买蓝宝石。

朗姆酒

  带有浓浓热带气息的海盗酒，本身的原料是甘蔗糖蜜，所以喝起来有香甜感，做出的鸡尾酒也有热带风情。最常见的就是百加得。进阶的话朗姆酒有细分：金朗姆、黑朗姆、陈年朗姆等，刚刚入门只需要一瓶白朗姆即可。

龙舌兰

  具有异域风情的酒。必须使用墨西哥当地的蓝色龙舌兰草作为原料。派对和夜店常见的喝法是把盐放在虎口上，先舔一口盐，再喝一shooter龙舌兰，最后再咬一瓣超酸青柠。国内性价比高的龙舌兰就是奥美加、培恩。

威士忌

  威士忌种类非常多，调酒的话不推荐用高价的单一麦芽威士忌，这种威士忌是纯喝风味的，调酒不需要太强的风味。推荐百龄坛、波本。

白兰地

  白兰地的分级是按照年份分级，可以在标签上看到VS、VSOP和XO。XO是陈年时间最久的，VS是最轻的。调酒时推荐用VS，口味风格不会特别突出。

家庭吧台中的辅料推荐

利口酒

利口酒可以给烈酒加上特殊的风味。

• 君度橙酒 COINTREAU
• 金巴利 CAMPARI
• 味美思 VERMOUTH,味美思是加烈葡萄酒，分为干性、甜性、半干性。
• 苦精 Bitters。就是浓缩的草药酒。用于鸡尾酒的提香。

非酒类材料

• 柠檬和青柠檬，可以直接用青柠汁。
• 各种苏打水。
• 果汁

一些常见的鸡尾酒配方

金酒篇

GIN & TONIC 金汤力

直调酒，不需要搅拌不需要摇晃。

• 加冰
• 45-60ml金酒
• 90-150ml汤力水
• 少许青柠汁（可选，经典金汤力不加）
• 一瓣青柠做装饰

勺子只做提拉，不要搅拌，否则气泡会散失

GIMLET 螺丝钻

• 60ml金酒
• 15ml青柠汁
• 15ml糖浆
• 摇晃，一瓣青柠做装饰

NEGRONI 尼格罗尼

口感苦涩，但是很好看

• 30ml金酒
• 30ml金巴利
• 30ml甜味美思
• 搅拌，一片橙子皮做装饰

TOM COLLINS 汤姆柯林斯

• 60ml金酒
• 30ml柠檬汁
• 15ml糖浆
• 加满新鲜的苏打水
• 摇晃，一片柠檬皮做装饰

FRENCH 75 法兰西75

• 45ml金酒
• 22.5ml柠檬汁
• 22.5糖浆
• 加满香槟
• 摇晃，长条柠檬皮做装饰

AI编程

  传统的编程模型中，开发程序是一项高度专业化的任务。程序员需要具备深厚的技术背景，掌握至少一门编程语言。并且要对复杂的逻辑和算法有着清晰的理解。然而随着AI人工智能技术飞速发展，编程的方式正在迎来革命性的变化。现在迎来了一个全新的阶段：我们不再需要精通晦涩难懂的编程语法，甚至不需要直接面对复杂的代码编辑器。取而代之的是，我们可以像和朋友聊天一样，用自然、日常的语言，向一个强大的AI大模型描述我们的需求。

  AI编程的核心在于利用强大的AI大模型来辅助甚至主导编程过程。这些AI大模型经过海量数据的训练，具备了理解和生成代码的能力。通过简单的对话聊天，即使是非专业的用户，也能够与AI大模型交互，快速生成所需的程序代码。

主流AI编程IDE对比

Cursor安装与基础配置

  Curosr是一款基于人工智能的现代化代码编辑器，由Anysphere公司开发。

  Cursor是基于VS Code开发的一款编辑器，它在保留VS Code强大功能和熟悉操作体验的同时，专注于集成AI技术，帮助开发者更高效的编写代码。

  国内阿里与字节页有基于VS Code开发的IDE：

• 阿里Lingma IDE: https://lingma.aliyun.com/
• 字节Trae：https://www.trae.com.cn/

核心特征：

• AI 原生设计：从底层架构就融入了AI能力，而非后期添加的插件；
• 智能代码生成：通过自然语言描述快速生成代码片段；
• 上下文感知：深度理解项目结构和代码关系；
• 实时协助：在编程过程中提供即时的建议和优化；
• 多模型支持：集成了多种先进的大语言模型；

设置

如果之前使用VS Code的话，可以

VSCode的下载和安装

• 下载VSCode：vscode官网

  安装时有选项，推荐选择“添加到PATH”、“通过Code打开”、“添加到右键菜单”；

  安装完成后是英文版本，可以安装汉化插件。点击左侧扩展按钮，搜索安装[Chinese(Simplified)]，安装完成后右下角弹窗，点击重启后即可生效。

C++环境配置

  VSCode本质上就是一个轻量级文本编辑器，是不能够直接运行代码的，还需要额外进行配置。

方案一：安装MinGW

1. 下载MinGW-w64:MinGW;
2. 点击Toolchains targetting Win64--Personal Builds--mingw-builds--8.1.0--threads-posix--seh，单击下载里面的压缩包文件。
3. 解压到一个目录后，我们需要配置环境变量，在系统的环境变量中编辑Path，把“X:\mingw64\bin”的路径添加进去。

  上述操作完成后，我们的环境就配置完成了，VSCode会自动识别g++编译器。

方案二：复用Visual Studio的MSVC编译器

如果熟悉Visual Studio的话，可以直接复用MSVC编译器。

1、找到MSVC编译器路径，通常在

C:FilesVisual Studio\2022\14.x.x

2、配置VSCode使用MSVC：在VSCode中按Ctrl+Shift+P，输入“Edit Configurations”。在生成的c_cpp_properties.json中配置：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

{
    "configurations": [
        {
            "name": "Win32",
            "includePath": [
                "${workspaceFolder}/**",
                "C:/Program Files/Microsoft Visual Studio/2022/Community/VC/Tools/MSVC/14.x.x/include/**"
            ],
            "defines": ["_DEBUG", "UNICODE", "_UNICODE"],
            "windowsSdkVersion": "10.0.22000.0",
            "compilerPath": "C:/Program Files/Microsoft Visual Studio/2022/Community/VC/Tools/MSVC/14.x.x/bin/Hostx64/x64/cl.exe",
            "cStandard": "c17",
            "cppStandard": "c++17",
            "intelliSenseMode": "windows-msvc-x64"
        }
    ],
    "version": 4
}

配置编译环境

需要安装如下的扩展：

• C/C++：提供语法高亮、智能感知、调试支持；
• C++ Themes：优化C++语法高亮；
• CMake Tools：如果使用CMake的话，需要安装这个；
• Code Runner：一键运行代码片段；

推荐安装以下扩展：

• GitLens：增强Git功能；
• Bracket Pair Colorizer：彩虹括号；
• Todo Tree：管理TODO注释；

创建和编译C++程序

• 在本地资源管理器中新建一个文件夹用来存放代码，然后用VSCode打开这个文件夹；
• 左边工作区中点击新建文件，新建一个C语言文件，例如“test.c”；
• 编写我们的程序，如hello world。
• 点击Ctrl+Shift+P，搜索“C/C++”，选择编辑配置(UI)。可以看到其中【编译器配置】中默认的是"cl.exe"，我们需要修改为之前安装的mingw64里的gcc.exe；同时【IntelliSense】模式需要修改为"Windows-gcc-x64"；
• 在代码页点击菜单栏的终端、配置任务，选择“C/c++:gcc.exe生成活动文件”，会生成一个"task.json"文件，此时就可以生成我们的代码了；
• 在代码页点击菜单栏终端、运行生成任务，使用gcc.exe生成活动文件。
• 我们可以在终端中运行，在菜单栏点击终端、新建终端，在窗口中输出".\test.exe"，回车后就可以运行了。

github使用

注册

Github官网上注册账号(Sign up)。注册时需要使用邮箱，本地配置时也需要邮箱账户，后续的git信息就会通过邮箱发送给用户。

配置公私钥

  git常常使用ssh协议进行传输，需要配置公钥和私钥。

文件的逻辑结构

文件类型

文件的逻辑结构根据文件类型可以分为两类：

1. 有结构文件：常见的有文本文件、文档、媒体文件等
2. 无结构文件：常见的有二进制文件、链接库等

  有结构文件的文件内容由定长记录和可变长记录两部分组成。定长记录存储文件的格式、编码、文件描述等结构化数据项；可变长记录存储文件的具体内容。

  无结构文件也称为流式文件，文件内容长度以字节为单位。exe、dll、so文件都是无结构文件。

顺序文件

  顺序文件是指按顺序存放在存储介质中的文件。磁带就是典型的顺序文件存储介质，只能按顺序读取和写入文件。顺序文件是所有逻辑文件当中存储效率最高的。

  但由于顺序文件只能顺序读写，所以假如我们想要对文件内容进行增、删等操作，效率极其低下。

索引文件

  可变长文件不适合适使用顺序文件格式存储，所以为了解决这个问题发明了索引文件。索引文件需要配合索引表完成存储的操作。

辅存(磁盘)的存储空间分配

分配方式

连续分配

  如果一个文件存取的时候需要连续的扇区，就会把内存中连续的扇区分配给文件。

  连续分配只要求我们顺序的读取文件即可，所以读取操作非常容易，速度很快。但是对存储要求很高，要求满足容量的连续存储空间。

链接分配

  链接分配可以将文件存储在离散的盘块中，不再需要大块连续的存储空间，但需要额外的存储空间存储文件的盘块链接顺序。根据这个额外存储空间的不同，分为隐式链接和显式链接。

  隐式链接的方法中，隐式分配的下一个链接存储在当前盘块内，就像链表结点中的next指针。隐式链接很适合顺序访问，我们只要知道起始的盘块就可以依次遍历所有的盘块，但是隐式链接的随机访问效率很低，必须从头开始寻找。并且隐式链接的可靠性差，任何一个链接出问题都将影响整个文件。

  显式链接就不在当前盘块中指定下一个盘块的位置了，而是单独有一张表，存储物理盘块以及下一个盘块的地址数据。这张表叫FAT(File Allocation Table)，也就是我们平时说的FAT文件系统，显式链接就是FAT系统的工作原理。FAT也存在一些缺点：它不支持高效的直接存储，因为FAT的记录项非常多，磁盘越大FAT记录越大，存储时需要检索FAT表找到空闲位置。而且检索FAT表时需要将整个FAT加载到内存中，占用较大的存储空间。

索引分配

  把文件的所有盘块集中存储，存储盘块的位置称为索引。每个文件都拥有一个索引块，记录当前文件所有盘块信息，当我们读取某个文件时，只需要读取索引即可，不需要把整张表都加载到内存中。通过索引分配我们可以直接找到文件对应的盘块。文件较大时，索引分配具有明显的优势。

存储空间管理

空闲表

  空闲表可以表示某个空闲的盘块号内有多少个空闲盘块数。空闲盘曲的分配与内存的分配类似，也具有首次适应算法、循环适应算法等；回收过程也和内存回收类似。

空闲链表

  空闲链表把所有空闲盘曲组成一个空闲链表，每个链表节点存储空闲盘块和空闲的数目。存储的信息和空闲表一样，操作方式也和内存的空闲链表方式类似。

位示图

  位示图横向的是盘块，纵向的是磁道，每一个具体的盘块都有0或1的标记，0表示未使用，1表示已经被使用了。位示图优点很多，首先维护成本很低，只需要维护一张表即可；其次位示图可以非常容易的找到空闲盘块；位示图内部使用0/1比特位，占用的空间很小。

目录管理

  目录系统是树形结构存储，使得任何文件或目录都只有唯一路径

内存的分配与回收

  早期的计算机编程并不需要过多的存储管理，但随着计算机和程序越来越复杂，存储管理成为必要。存储管理需要确保计算机有足够的内存处理数据、确保程序可以从内存中获取一部分内存使用，并可以归还使用后的内存以供其他程序使用。

内存分配

• 单一连续分配：

  单一连续分配是最简单的内存分配方式，只能在单用户、单进程的操作系统使用。它把系统内存分为系统区和用户区，系统区内的内存只能够被操作系统使用，用户区内的内存只能被用户程序使用。这个分配方式已经过时不再使用了。

• 固定分区分配：

  固定分区分配是支持多道程序的最简单存储分配方式。内存被划分为若干固定大小的区域，每个分区只提供给一个程序使用，互不干扰。

• 动态分区分配：

  这是操作系统中比较常用的方法。根据进程实际需要，动态地分配内存空间。要支持这种分配方法，就需要相关的数据结构和分配算法:

  数据结构：

  假设主存中有若干分区，有些分区已经被使用，有些分区空闲。动态分区空闲表这个数据结构就可以记录分区的使用情况。

  还有动态分区空闲链数据结构，用一个双向链表的结构存储来存储当前系统中的空闲区域。

  算法：

  首次适应算法(FF)：主要使用空闲链的数据结构，每次进行内存分配的时候从链表头开始顺序查找适合的内存区域。遍历结束后发现没有合适的空闲区，则该次分配失败；如果找到了合适的空闲区，则把这块内存分配给进程使用。首次使用算法有个很大的问题：由于每次都是从头部开始遍历，使得头部的地址空间不断的被划分，导致头部地址可能出现大量碎片。对于这个问题，可以优化为循环适应算法，每次遍历结束后记录位置，下次遍历从这个位置开始，而不需要每次从头开始遍历。

  最佳适应算法：空闲链表按照容量大小进行排序，每次遍历空闲区链表时可以找到最佳的合适空闲区。这种算法可以有效避免大材小用的情况。

  快速适应算法：快速适应算法要求有多个空闲区链表，每个空闲区链表存储一种容量大小的空闲区。这样当我们需要某个大小的空闲区域时，就可以快速找到对应的链表取内存。

内存回收

  内存回收的场景可能会遇到下面四种场景：

  第一种场景是需要回收的区域和空闲区连在一起且正好在空闲区后面，这个场景非常简单，不需要新建空闲链表节点，只需要把空闲区的容量增大即可，把回收区的容量包括进去。

  第二种情况是需要回收的区域和空闲区连在一起，但在空闲区前面。这个场景也是将回收区和空闲区合并，合并而成的新的空闲区使用回收区的地址。

  第三种情况回收区恰好在两个空闲区之间，回收需要将空闲区1、空闲区2和回收区一起合并，然后新的空闲区地址使用空闲区1的地址。

  最后的场景就是单一的回收区，没有连接任何的空闲区，这种情况要为回收区创建新的空闲节点，然后把回收区插入到相应的空闲区链表中去。

段页式存储管理

  每个进程都有独立的进程空间，操作系统管理进程空间有三种管理方式：

页式存储管理

  计算机组成原理中有字和字块的概念，字和字块是相对内存条等物理设备的定义，而操作系统内存管理中的页面则是相对逻辑空间的定义。字块和页面都是指大小一样的一块内存。

  页式管理是将进程的逻辑空间划分成若干大小相同的页面，把相应的物理内存空间分成与页面大小相同的物理块。以进程为单位把进程空间装进物理内存中分散的物理块中。

  页式管理系统中需要了解内存碎片的概念。如下图所示，空闲链表中存有大小不同的空闲节点，如果需要申请一个页面大小的内存，节点1不够，只能使用节点2-3的一部分，这样就造成了内存碎片。所以页式存储管理的页面大小应该适中，过大的话难以分配，过小的话又会造成内存碎片多。一般情况下，页面大小为512B~8K。

  为了知道某个页面被分配到哪个字块，还需要了解页表的概念。页表记录进程逻辑空间和物理空间的映射关系。

  在现在计算机系统中，可以支持非常大的逻辑地址空间(~)，这样页表就会变得非常大，要占用非常大的内存空间。假设具有32位逻辑地址空间(寻址空间为即4G)的分页系统，规定页面大小为4KB，则每个进程页表中的页表项可达1M(4G/4KB=)个，如果每个页表项占用1Byte，每个进程仅仅页表就要占用1MB的内存空间。为应对这种情况，有了多级页表的设计.

  单纯的页式存储管理可能遇到的问题是，假如有一段连续的逻辑分布在多个页面中，将大大降低执行的效率。

段式存储管理

  段式存储管理将进程的逻辑空间划分成若干段，这种划分是非等分的。每一段的长度由进程内连续的逻辑长度决定，比如针对MAIN函数、子程序段X、子函数Y等，根据不同的长度分配不同的内存空间。

  我们也需要一个数据结构来保存逻辑空间到物理空间的映射，段式存储结构中的数据结构叫段表，由于段长度不同，所以相比页式存储管理，段表内多了一个段长。

  页式存储管理和段式存储管理相同点在于，都离散的管理了进程的逻辑空间，它们之间的不同点在于：

1. 页是物理单位，段是逻辑单位；
2. 分页是为了合理利用空间、分段是为了满足用户需求；
3. 页的大小由硬件固定，段的长度可动态变化
4. 页表信息是一维的，段表信息是二维的(需要记录段长度)

段页式存储管理

  结合了页式存储管理和段式存储管理，产生了段页式的存储管理。分页的优点在于虽然存在页内碎片，但相比分段来说提高了内存的利用率；分段的优点在于可以更好的满足用户需求。

  段页式存储管理首先将逻辑空间按照段式管理分成若干段，再把段内空间按页式管理分成若干页。页式管理的页地址由页号和业内偏移组成，段式管理的段地址由段号和段内偏移组成，段页式结合两者，段页地址由段号、段内页号、页内地址三者组成。

虚拟内存

  有些进程实际需要的内存很大，超过了物理内存的容量，而伴随着多道程序设计的出现，使得每个进程可用的物理内存更加稀缺。但由于现实的原因，不可能无限增加物理内存，物理内存总有不够用的时候，所以诞生了虚拟内存技术。虚拟内存是操作系统内存管理的关键技术，使得多道程序运行和大程序运行成为现实。虚拟内存技术把程序使用的内存进行划分，将暂时不使用的内存放置在辅存中。

程序的局部性原理

  局部性原理是指CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。

  局部性原理是虚拟内存可以实现的原因之一。程序加载的时候，不需要把进程所有的逻辑空间都加载到内存中，只装载部分即可。如果需要访问页时发现页面不在内存中，则发出缺页中断，发起页面置换，置换后程序就可以继续运行下去。从用户层面看，程序仿佛拥有很大的空间，即是虚拟内存。虚拟内存实际上是对物理内存的补充，速度接近于内存，成本接近于辅存。

虚拟内存置换算法

• 先进先出算法(FIFO)
• 最不经常使用算法(LFU)
• 最近最少使用算法(LRU)