Zhuming'博客
0%
//post-footer

发表于 更新于

堆和栈的区别

1、堆栈空间分配不同。栈由操作系统自动分配释放，存放函数的参数值，局部变量的值等；堆一般由程序员分配释放
2、堆栈缓存方式不同。堆使用的是一级缓存，
3、堆栈数据结构不同。堆类似数组结构，栈类似栈结构，先进后出
4、大小限制：栈的大小受系统可用内存的限制，但在实践中，堆的大小受限于操作系统和硬件的限制
5、栈不容易产生碎片，堆容易产生碎片
总的来说，栈适合于管理具有较短生命周期和固定大小的数据，而堆适合于管理具有动态生命周期和大小不确定的数据

C++的内存管理

1、C++内存分成了五个区，分别是堆、栈、自由存储区、全局/静态存储区和常量存储区。

2、内存泄漏是什么？
简单说就是申请了一个内存空间，使用完毕没有释放
解决方案：
1、良好的编码习惯；
2、使用智能指针
3、用一些常见的工具插件

malloc和局部变量分配在堆还是栈

malloc是在堆上分配内存，跟new是一样的，需要程序员自己回收内存；局部变量是在栈中分配内存的，超过作用域就自动收回

//post-footer

发表于

说说 static关键字的作用

1、定义全局静态变量和局部静态变量
(在变量前加static关键字。初始化的静态变量会在数据段分配内存，未初始化的静态变量会在BSS段分配内存。直到程序结束)
2、定义静态函数
(在函数返回类型加上static关键字，函数就被定义为静态函数，只能在本源文件中使用)
3、在变量前加上static，变量被定义为静态变量。
4、static也可以用来定义类中的静态成语变量:使用静态数据成员，它既可以被当成全局变量那样去存储，但又被隐藏在类的内部。类中的static静态数据成员拥有一块单独的存储区，而不管创建了多少个该类的对象。所有这些对象的静态数据成员都共享这一块静态存储空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class student{
private:
    static int count; //静态成员变量，必须由静态成员函数return出来
public:
    student(){
        count++;
    }
    static int getCount(){ //静态成员函数
        return count;
    }
};
int student::count =0;
int main()
{
    student s1,s2,s3;
    cout << student::getCount() << endl;
    return 0;
}

当调用一个对象的非静态成员函数时，系统会把该对象的起始地址赋给成员函数的this指针。而静态成员函数不属于任何一个对象，因此C++规定静态成员函数没有this指针（划重点，面试题常考）。既然它没有指向某一对象，也就无法对一个对象中的非静态成员进行访问。

总结:从变量和函数的角度来看static会产生静态变量和静态函数，从class上来看，static会产生静态成员变量和静态成员函数。

//post-footer

发表于

C++与C语言类似，一个C++程序从源码到执行文件，有四个过程，预编译、编译、汇编、链接

首先，预编译：

(1) 将所有的#define删除，并且展开所有宏定义

1
2
3
4
5
6
7
8
#define NUM 17
#define DNUM NUM+NUM
//则表达式 DNUM/2+NUM/2的值为?


//预编译是将DNUM转化成NUM+NUM，所以表达式变成了NUM+NUM/2+NUM/2
//等等！答案不是34,原式=NUM+NUM/2+NUM/2=17+17/2+17/2=17+8+8=33!
//C++里面采用的是floor整型计算,取整,去小数！

(2) 处理所有的条件预编译指令，如#if、#ifdef

1
2
3
4
5
6
7
#ifndef HEADER_FILE_NAME_H
#define HEADER_FILE_NAME_H
#include "HEADER_FILE"
#endif

//作用1、防止头文件被多次包含
2、使用#ifndef主要原因是为了避免重复定义，使代码模块化和可维护

(3) 处理#include预编译指令，将被包含的文件插入该预编译指令中，这也是为什么第二点中会发生重复定义

(4) 过滤所有的注释//
(5) 添加行号和文件名标识

其次，编译

(1) 词法分析：将源代码的字符序列分割成一系列的记号
(2) 将预处理后的中间文件转换成汇编语言
(3) 这个步骤将源代码翻译成机器语言。生成对应的目标文件

然后，汇编

这个过程主要将汇编代码转换成机器可以执行的指令

最后，链接

将不同的源文件产生的目标文件进行链接，从而形成一个可以执行的程序。
(1) 静态链接： 链接的时候就把调用的函数或者过程链接到了生成的可执行文件的执行；生成的静态链接库
(2) 动态链接，是在链接的时候没有把调用的函数代码链接进去，而是在执行的过程中，找要链接的代码

通俗点讲就是：静态链接直接把头文件复制进去，而动态链接是可执行文件包含对库函数的引用，但实际的库文件不被复制，由操作系统动态地加载和链接这些库文件。各有优缺点。

总结 : 预编译先处理#以及注释，编译将文件再转换成汇编语言，第三步汇编是把汇编语言转换成机器可以执行的指令，最后的链接就是选择静态链接还是动态链接

//post-footer

发表于

函数指针

你可以声明一个指向函数的指针，并将其用作二元函数对象，例如:

1
2
3
4
5
int add(int a, int b) {
    return a + b;
}
int (*binaryFunction)(int,int) = &add; //函数指针
int result = binaryFunction(3,5); //结果为8

函数对象

你可以定义一个类重载operator()来实现函数对象。例如：

1
2
3
4
5
6
7
8
9
struct Add {
    int operator()(int a,int b)
const {
    return a + b;
    };
};

Add add;
int result = add(3,5);
//post-footer

发表于

1.C语言是C++的子集，C++可以很好的兼容C语言，但是C++又有很多新特性，如引用、智能指针、auto变量等

2.C++是面向对象的编程语言；C语言是面向过程的编辑语言。

面对对象 ： 把世界万物当成一个对象class，包含本身的属性特性和行为(函数)
面对过程 ： 把一件事情分成很多步骤去做，比如一个事情分成了很多个函数，然后一个一个去调用

3.C语言有一些不安全的语言特性，如指针使用的潜在危险、强制转换的不确定性、内存泄漏等。而C++增加了不少新特性来改善安全性，如const常量、引用、cast转换、智能指针、try-catch等等

4.C++可复用性高，C++引入了模板(template)的概念,后面在此基础上，实现了方便开发的标准模板库STL。 C++的STL库相对于C语言的函数库更灵活、更通用

//post-footer

发表于

内存分区模型

C++程序在执行时，将内存大致分为四个区域

  • 代码区: 存放函数体的二进制代码，由操控系统进行管理
  • 全局区: 存放全局变量和静态变量(static以及常量(const)
  • 栈区: 由编译器自动分配释放，存放函数的参数值，局部变量等
  • 堆区: 由程序员分配和释放，new和delete

内存四区的意义

不同区域存放的数据，赋予不同的生命周期

//post-footer

发表于 更新于

什么是哈夫曼树？

哈夫曼树（Huffman Tree）是一种用于编码的树形数据结构，通常用于数据压缩算法中。哈夫曼树的特点是，频率较高的字符在树的顶部，频率较低的字符在树的底部，从而实现了不同字符的编码长度不同，且尽量短的目标。

哈夫曼树的构建过程通常是根据字符出现的频率来构建的，频率越高的字符在树中的位置越靠近树的根节点。构建哈夫曼树的基本思路是，首先将所有字符作为单独的节点，并按照频率从小到大排序。然后，将频率最低的两个节点合并为一个新节点，新节点的频率为两个节点的频率之和，并将新节点放入原来的节点列表中。重复这个过程，直到只剩下一个节点，即树的根节点。

哈夫曼树的一个重要应用是哈夫曼编码（Huffman Coding），它是一种变长编码方式，将字符映射为不定长的二进制编码。哈夫曼编码的特点是，频率较高的字符对应的编码较短，频率较低的字符对应的编码较长，从而实现了对数据的高效压缩。

总之，哈夫曼树是一种用于数据压缩的树形数据结构，通过根据字符频率构建树，实现了高效的数据压缩编码。

哈夫曼树的应用

哈夫曼树是一种用于数据压缩的重要数据结构。它通常用于构建哈夫曼编码，是一种变长编码（即不同字符的编码长度可能不同）。

下面是哈夫曼树的一些常见应用：

数据压缩：哈夫曼树最经典的应用就是数据压缩。在数据传输和存储过程中，对于一些出现频率较高的字符，用较短的编码表示，而对于出现频率较低的字符，用较长的编码表示，这样可以减少数据的存储空间和传输带宽。

文件压缩：在文件压缩中，通常会使用哈夫曼编码对文件中的字符进行编码，从而实现文件的压缩。常见的压缩文件格式，如ZIP、GZIP等，都使用了哈夫曼树。

通信传输：在通信传输中，为了节省传输带宽，可以使用哈夫曼编码对通信中的数据进行编码。特别是在无线通信、移动通信等场景中，传输带宽有限，采用哈夫曼编码能够提高传输效率。

图像压缩：在图像压缩中，哈夫曼树可以用于对图像数据进行压缩编码，从而减少图像文件的存储空间。

音频压缩：在音频压缩中，哈夫曼编码也可以用于对音频数据进行压缩编码，减少音频文件的存储空间和传输带宽。

总之，哈夫曼树在数据压缩领域有着广泛的应用，能够帮助我们高效地压缩和传输数据，节省存储空间和传输成本。

//post-footer

发表于

单调栈是一种常用的数据结构，主要用于解决一些与连续元素相关的问题。以下是单调栈的一些常见应用：

  • 寻找下一个更大元素（Next Greater Element）：给定一个数组，对于数组中的每个元素，找到右边第一个比它大的元素。这个问题可以使用单调递减栈来解决。遍历数组，将元素的索引入栈，如果当前元素比栈顶元素大，那么弹出栈顶元素，并将当前元素作为栈顶元素的下一个更大元素。
    eg.奶牛问题(洛谷 P2947)利用单调栈，将O(n²)优化成了O(n)

  • 寻找下一个更小元素（Next Smaller Element）：类似于上述问题，给定一个数组，对于数组中的每个元素，找到右边第一个比它小的元素。这个问题可以使用单调递增栈来解决。

  • 寻找最近更大元素（Closest Greater Element）：给定一个数组，对于数组中的每个元素，找到距离它最近且大于它的元素。这个问题可以使用单调递减栈来解决。遍历数组，如果当前元素比栈顶元素大，那么弹出栈顶元素，直到找到距离当前元素最近的更大元素。

  • 寻找最近更小元素（Closest Smaller Element）：类似于上述问题，给定一个数组，对于数组中的每个元素，找到距离它最近且小于它的元素。这个问题可以使用单调递增栈来解决。

柱状图中最大矩形面积（Largest Rectangle in Histogram）：给定一个柱状图，找到面积最大的矩形。这个问题可以使用单调递增栈来解决。遍历柱状图，如果当前柱的高度小于栈顶柱的高度，则计算栈顶柱的面积，并更新最大面积。反之，将当前柱入栈。

接雨水（Trapping Rain Water）：给定一个数组，表示不同高度的墙，求解能够容纳多少雨水。这个问题可以使用单调递减栈来解决。遍历数组，如果当前元素比栈顶元素大，则计算两者之间能够容纳的雨水量，并累加到总雨水量中。

以上是单调栈的一些常见应用，它可以帮助我们解决许多与连续元素相关的问题，提高算法的效率并简化代码实现。

//post-footer

发表于

C++ 基础

1.1.1 简述下C++语言的特点

  1. C++在C语言的基础上引入了面对对象的机制，同时也兼容C语言
    (面对对象：把一切事物抽象，然后对每个事物的性质和行为进行分析,而面向过程指将一件事情按照步骤进行)
  2. C++有三大特性: (1). 封装 (2). 继承 (3). 多态
    (封装：就是将一个类的信息隐藏在类的内部，不允许外界直接访问，而是提供某些方法实现对隐藏信息的访问和操作。封装的好处就是增强了数据安全性，也方便了类的实现和修改)
    1
    2
    3
    4
    5
    6
    7
    8
    class student{
    public:  //公共权限  类内可以访问 类外可以访问
        string School;
    protected: //保护权限 类内可以访问 类外不可以访问
        string PhoneNumber;
    private: //私有权限 类内可以访问 类外不可以访问
        int Birthday;
    }
     (继承：类与类之间的一种关系。让子类继承父类的特征和行为。好处在于实现了代码的复用)
    1
    2
    3
    4
    5
    6
    class BasePage{
    public:...
    protected:...
    private:...
    }
    class Java : public BasePage{...}
     继承方式：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class A{
    public: int a;
    protected: int b;
    private: int c;
    }

    class B:public A //第一种方法
    {
    public: int a;
    protected: int b;
    不可访问: int c;
    }
    class B:protected A //第二种方法
    {
    protected:
    int a;int b;
    不可访问：int c;
    }
    class B:private A //第三种方法
    {
    private:int a int b;
    不可访问: int c;
    }

struct和class唯一区别在于默认的访问权限不同

struct默认公共；class默认私有

(多态：指的是一个类对象的相同方法在不同情形下有不同的表现形式。使得不同内部结构的对象可以共享相同的外部接口)

1

  1. C++语言编写出的程序结构清晰、易于扩充，程序可读性好。
  2. C++生成的代码质量高，运行效率高、仅比汇编语言慢10%~20%
  3. C++更加安全，增加了const常量，引用，四类cast转化、智能指针等
  4. C++可复用性高、引入了模板的概念、比如标准模板库STL
  5. 最后，C++是不断在发展的语言。C++后续版本更是更新发展了不少新特性比如nullptr、auto变量等
//post-footer

发表于 更新于

什么是链表？

 如图

链表的特点:用一组位于任意位置的存储单元存储线性表的数据元素

代码实现链表的方法:
动态链表：工程上为了节省空间经常使用
静态链表：算法竞赛里面经常使用,而且会直接使用STL list