Airbox开发

1.资料记录

Airbox账号密码：linaro

风扇太吵的话：

sudo busybox devmem 0x50029000 32 0x500
sudo busybox devmem 0x50029004 32 0xfa0

1.TPU-MLIR 快速入门手册： https://doc.sophgo.com/sdk-docs/v23.09.01-lts/docs_latest_release/docs/tpu-mlir/quick_start/html/01_introduction.html

2.示例模型仓库地址： https://github.com/sophon-ai-algo/examples

3.TPU-MLIR 官方仓库地址 https://github.com/sophgo/tpu-mlir

4.SOPHON-SAIL 开发手册： https://doc.sophgo.com/sdk-docs/v23.05.01/docs_latest_release/docs/sophon-sail/docs/zh/html/

5.TPU-MLIR 环境搭建与使用指南： https://www.sophgo.com/curriculum/description.html?category_id=43

6.LLM 的概念与实战（其次学习，让然后看看算能学院）： https://www.sophgo.com/curriculum/description.html?category_id=47

7.Airbox Demo 参考（首先参考复现）： https://zhengorange.github.io/airbox_wiki/

7.1刷机部署等： https://gitee.com/zilla0717/AirboxWiki/blob/master/README.md

8.算能开发者论坛： https://forum.sophgo.com

9.少林派开发板实战课程： https://www.sophgo.com/curriculum/description.html?category_id=6

10.sophoneSDK3开发指南 https://sophgo-doc.gitbook.io/sophonsdk3

请根据我对图像的文字描述，回答问题。 问题：桌子上有什么？ 文字描述：'a screwdriver and tape measure on a table' 'a blue rectangular device with a red button' 'a screwdriver with a black handle' 'a close up of a machine' 'a yellow and black tape measure',

2.LLM概念与部署

1.SOPHON BM1684X介绍

SOPHON BM1684X是SOPHON专门针对深度学习领域推出的第四代张量处理器，具有32TOPS计算能力，支持32路高清硬件解码，12路高清硬件编码，适用于深度学习、计算机视觉、高性能计算等环境。

2.大模型训练过程、常见LLM与发展历程

1. Pre-train:从巨大的数据集中进行无监督训练，学习一般的语言模式和表征。
2. Fine-ture：根据特定的任务和更小的数据集训练和微调。

transformer模型分为encoder和decoder，都由注意力机制和FNN前馈神经网络(残差链接和归一化等等)组成。

常见LLM：

1. GPT-3:1750亿个参数decoder-only模型；
2. T5:文本对文本转化模型；
3. GLM130B:1300亿个参数的双语言的模型；

LLM的训练过程可以理解为对有效信息的无损压缩过程，压缩率约高，模型的智能水平越高，泛化能力约强，对任务的理解越好。

LLM模型的发展历程：

1. 统计语言模型：对语句的概率分布进行建模，计算一个句子出现的概率或一句话是否合理的概率；
2. 神经网络语言模型：循环神经网络RNN，LSTM, transformer模型；
3. 预训练语言模型：指在大规模数据集上无监督学习得到通用的语言表示，通过微调可以用于下游任务，如ELMo模型，后来产生GPT系列；
4. 大语言模型：数十亿参数，预训练+微调

3.大模型分类与压缩推理加速

根据大模型结构分类：只有encoder的模型，如BERT；有encoder和decoder的模型，如T5；只有decoder的模型，如GPT系列；实践证明只有decoder的模型效果更好。

模型压缩：

1. 剪枝(非结构化剪枝和结构化剪枝)：减少不必要的参数或者权重链接；过程：训练->剪枝->微调；
2. 量化(后训练量化和量化感知训练)：降低模型参数的准确率；进行一次FP32类型的数据可以执行四次FP8类型的数据；
3. 知识蒸馏：训练一个更小的模型来模仿大模型的行为；过程：teacher-student setup建立大小模型->教师模型生成训练数据集也就是获得知识->学生模型训练；

LLM的训练和推理加速：

1. 训练加速：data并行(分成batch放在不同的GPU上)、pipeline并行(模型分层分在不同GPU上)、tensor并行(矩阵分解，子矩阵在不同GPU上)；
2. 推理加速：
   1. KV Cache，不影响任何计算精度的前提下，通过空间换时间的思想，提高推理性能。
   2. GPT类模型一次推理只输出一个token，输出token会与输入tokens拼接在一起作为下一次推理的输入，这样不断反复直到遇到终止符。
   3. Flash-attention:重新排序注意力计算的算法，无需近似即可加速注意力并减少内存的占用。

3.TPU-MLIR环境构架你及使用指南

1.TPU-MLIR概念

TPU-MLIR是一种专用于处理器的TPU编译器。该编译器项目提供了一个完整的工具链，可以将来自不同深度学习框架(PyTorch, ONNX, TFLite和Caffe)的各种预训练神经网络模型转换为高效的模型文件(bmodel/cvimodel)，以便在SOPHON TPU上运行。通过量化到不同精度的bmodel/cvimodel，优化了模型在sophon计算TPU上的加速和性能。这使得可以将与对象检测、语义分割和对象跟踪相关的各种模型部署到底层硬件上以实现加速。

2.编译的概念(传统编译器与AI编译器)

传统的编译器是将高级编程语言编译为低级编程语言，比如机器码，组成与平台兼容的库或可执行文件；

Windows中有Microsoft Visual C++ (MSVC) 和 MinGW编译器；

Linux和MacOS中Clang,GNU Compiler Collection (GCC) 编译器；

传统编译器编译流程：

1. 词法分析:将源代码分为词法单元(Tokens)；
2. 语法分析:根据编程语言的语法，将Tokens组织成抽象语法树(Abstract Syntax Tree)；
3. 语义分析:检查语法树，确保程序的合法性；
4. 中间代码生成:将源代码转为与平台无关的中间代码；
5. 优化:基于生成的中间代码进行各种优化提升程序性能或减少资源消耗；
6. 目标代码生成:将中间代码转换为目标平台兼容的代码，生成可执行文件或库；
7. 链接:链接多个目标文件和库文件，确保符号引用正常；

AI编译器是将深度神经网络编译为二进制模型，编译流程与传统编译器相似，区别在于将源代码转化为AI模型，词法单元转换为组成AI模型的算子，主要对AI模型进行优化(模型压缩、量化、算子融合等，减少计算量与存储需求，提高推理性能)；

3.SophonSDK

SophonSDK是算能科技基于其自主研发的AI芯片所定制的深度学习SDK，涵盖了神经网络推理阶段所需的模型优化、高效运行支持等能力，为深度学习应用开发和部署提供易用、高效的全栈式解决方案。

包含以下工具包：

1. tpu-nntc负责对第三方深度学习框架下训练得到的神经网络模型进行离线编译和优化，生成最终运行时需要的BModel。目前支持Caffe、Darknet、MXNet、ONNX、PyTorch、PaddlePaddle、TensorFlow等。
2. libsophon提供BMCV、BMRuntime、BMLib等库，用来驱动VPP、TPU等硬件，完成图像处理、张量运算、模型推理等操作，供用户进行深度学习应用开发。
3. sophon-mw封装了BM-OpenCV、BM-FFmpeg等库，用来驱动VPU、JPU等硬件，支持RTSP流、GB28181流的解析，视频图像编解码加速等，供用户进行深度学习应用开发。
4. sophon-sail 提供了支持Python/C++的高级接口，是对BMRuntime、BMCV、BMDecoder、BMLib等底层库接口的封装，供用户进行深度学习应用开发。
5. tpu-mlir为TPU编译器工程提供一套完整的工具链，可以将不同框架下预训练的神经网络，转化为可以在算能TPU上高效运行的二进制文件BModel。目前直接支持的框架包括tflite、onnx和Caffe。
6. tpu-perf为模型性能和精度验证提供了一套完整工具包。
7. tpu-kernel是芯片底层开发接口，既可以调用专用指令实现深度学习业务逻辑的加速，又可以调用通用指令实现客制的各种算法加速。

TPU-MLIR：Multi-Level Intermediate Representation,基于LLVM(Low-Level Virtual Machine)开发的编译器基础框架；统一IR(Intermediate Representation)格式，并通过多层IR提高通用与可复用性；扩展性与可组合性强，便于实现优化与代码生成；自带Tensor类型，目前主要用于深度学习领域；

模型转换需要在指定的docker执行,主要分两步,一是通过 model transform.py 将原始模型 转换成mlir文件,二是通过 model_deploy.py 将mlir文件转换成bmodel.如果要转INT8模型,则需要调用 run_calibration.py生成校准表,然后传给 model_deploy.py。如果INT8模型不满足精度需要,可以调用run_qtable.py 生成量化表,用来决定哪些层采用浮点计算，然后传给 model_deploy.py 生成混精度模型。

4.AI编译器开发TPU-MLIR

1.AI编译器概念

作为框架和硬件之间的桥梁，深度学习编译器可以实现一次性代码开发和重用各种计算能力处理器的目标。算能也开源了自己开发的TPU编译工具——TPU-MLIR (Multi-Level Intermediate Representation)。TPU-MLIR是一个面向深度学习处理器的开源TPU编译器。该项目提供了完整的工具链，将各种框架下预训练的神经网络转换为可在TPU中高效运行的二进制文件bmodel，以实现更高效的推理。本课程以实际实践为驱动，引导您直观地理解、实践、掌握智能深度学习处理器的TPU编译框架。

2.MLIR代码由来

AI模型代码编译到特定硬件可以使用的二进制的模型bmodel，需要先编译为中间代码IR(在该步骤中完成优化)，其复杂度介于高级编程语言与低级机器码之间。

需要多层IR进行转换(Dialect的概念),(实现TPU-MLIR的核心概念)

Dialect组成：

1. Prefix：Dialect名称，如top层、Tpu层；
2. Operations：一系列操作，每个操作对应深度学习模型中的单个算子，如ConvOp;
3. Passes：Dialect内的转换，如Top层的图优化；Dialect内的转换，如Top层lower到Tpu层；

MLIR文本代码组成：

1. ModuleOP:当前代码本身；
2. FuncOp:其中的main Func表示代码的整体运行逻辑；其他Func可能是在代码中多次出现的具有固定顺序的操作集，封装起来反复调用；
3. Block:一个Func的所有内容，一些操作的集合；

MLIR文本代码解释：

1. 以百分号%开头的语句代表一个operation，进行tensor的操作；MLIR中两个类来完成operation的实现：operation class(通用的定义操作，提供通用的属性和操作接口，如operation的创建删除移动等)和op class(用于派生某个Dialect下的具体算子);
2. Value表示操作数，表示operation的输入和输出；主要有两个派生类：BlockArgument类(某个Block的输入参数)和OpResult类(静态单赋值的结果)；
3. type表示操作数的类型；通常是Tpye类和ShapeType类的继承类TensorType类
4. attribute：零个或多个元素的字典，这些属性是始终恒定的操作数；

MLIR中Op的定义方式：

1. 直接在C++中定义：需要继承Op基类并重写部分构造函数，代码冗余可读性差；
2. 在MLIR中的ODS(Operation Definition Specification)中定义：在td文件中编写Op定义，利用LLVM提供的TableGen语言进行定义，容易直观；

3.MLIR编译流程：

1. 将其他模型Pytorch/Tensorflow/PaddlePaddle转换为ONNX模型(提供了丰富的算子和一些基础的暑假类型，通过多个node来定义计算图。)；
2. Top层：ONNX->Top MLIR(称为前端转换),主要将onnx模型转化为origin.mlir和canonicalize操作，即算子融合、计算简化等，和硬件无关；代码在./tpu-mlir/python/transform中;
3. Lowering操作：将Top Dialect转化为TPU Dialect(表示TPU芯片的Kernel库)，代码在./tpu-mlir/lib/Conversion/TopToTpu;包含量化操作，F32/BF16/16是直接截取的量化方式，int8量化是基于校准信息的一种量化方式，用8位整型映射32位浮点型，使用数据集校准调优，也有混合精度的方式；
4. LayerGroup+AddressAssign操作(硬件层的优化，如算子融合和内存分配优化)，代码在./tpu-mlir/lib/Dialect/Tpu/Transforms;
5. Code Generation:目录./tpu-mlir/lib/Dialect/Tpu/Interfaces下包含不同芯片算子生成的机制，目录./tpu-mlir/lib/Backend下记录了根据不同芯片规格相应的实现，目录./tpu-mlir/third_party/nntoolchain/lib/引入了外部的动态库(后端算子具体实现)调用芯片底层的配置，最后生成了在TPU上运行的指令；
6. 模型编译过程中也涉及到Correctness check保证编译得到的bmodel模型性能不会下降太多。

4.两种量化方式：

1. 训练后量化：训练完成后量化，无需或仅需要少量的数据，易于实现；

   1. 训练后量化方式：
   2. 均匀量化用的比较多，分为对称量化(分为有符号和无符号两种)和非对称量化：
   3. 
   4. 在weight tensor容易得到max，min, threshold，但对于激活tensor根据输入的数值改变，此时确定这三个值就要用到校准环节；
   5. 
   6. KL散度衡量两个数据分布的相似性，TensorRT在量化过程中也用到了。

2. 量化感知训练：在训练过程中模拟量化重新训练模型，需要带标签的数据，量化后更接近F32模型的精度；在训练过程中插入伪量化算子，将weight与activation量化成低位精度再反量化回FP32引入量化误差。

MLIR实战

Pattern Rewriting Framework: 有向无环图DAG to 有向无环图DAG转换，

分为： Pattern Definition Pattern Rewriter Pattern Application

Dialect1转换为Dialect2通过Dialect Conversion组件进行转换

TPU原理： 一个完整的TPU包含多个Lane； 每个Lane包含Local memory(存储要运算的数据) 和 Execution Units(TPU上最小的计算单元)；

指令：GDMA(数据搬运)、BDC(运算)、其他HAU.

6.智能多媒体与TPU编程实战

1.基本概念

智能多媒体关键技术：编解码技术、图像处理技术、多媒体通信技术； 智能多媒体关键指标：解码路数、帧率、分辨率、图像处理接口丰富度、延迟、协议支持；

2.图像处理技术

空间分辨率：

1. 1080P，其中P是“逐行扫描”，表示视频在宽高比为16:9的情况下，视频总共有1080行像素数；
2. 2K，表示视频中每一帧图像的列像素数在2K的级别；
3. 通常所说的几百万像素，指的是图像的总像素，即M×N的总数到几百万；

量化：亮度的分辨率，衡量图像亮度的量化精度；

位深：表示图像中每个像素用多少个二进制位表示，灰度图通常是8位，彩色图像通常是24位；

帧率：表示视频中每秒包含的图像数；

码率：是数据传输时单位时间传送的数据比特数，单位是千比特每秒，码率kbps = 文件大小(KB) * 8/时间(s)，越高每秒显示的帧数越多；

PSNR：峰值信噪比，常用于两幅图像相似度的测量，基于统计误差衡量，越大含有信息越多，统计意义上两图之间的差异越小，相似度越高；

色彩空间模型(可以相互转换)：

1. RGB模型：R G B三基色混合，每个颜色值用8bit表示(真彩色)，RGB555是16位的RGB格式，每个分量用5位表示，还有RGB565模型；
2. HSI模型：色度H、饱和度S、亮度I组成；

3. YUV模型：亮度Y、色度UV(CbCr)组成，表示对蓝色和对红色的便宜程度；

图像存储格式：

1. BMP格式：采用位映射存储方式，与硬件设备无关除了色彩分辨率可选之外，不采用其他任何压缩-扫描格式是按从左到右、从上到下的顺序；
2. GIF格式：种连续色调的无损压缩格式，压缩率在50%左右存储量相对小，成像清晰，适合于初期的互联网；
3. PNG格式：便携式网络图像格式--存储量相对小，压缩比高；
4. JPEG格式：采用有损压缩方式去除图像数据中的冗余信息可以在获取极高的压缩率的同时保持图像质量；

图像增强：

1. 空间域增强：灰度变换、代数运算、空间域滤波，直接对图像中像素的灰度级进行操作；
2. 频域增强：频域滤波，对图像进行傅里叶变换等；

直方图：横坐标表示灰度级，纵坐标表示该灰度级 出现的频数(越均匀图像最清晰)；

边缘检测，边缘就是像素变化比较明显的区域(一阶导数极致的取区域，通常用一阶差分表示，对于二维图像，通常用梯度来检测)，具有丰富的语义信息；

根据不同的卷积核对原图像做卷积可以实现很多图像的基本处理；

对于原信号有噪声的话，可以先滤波，如高斯降噪(可以用高斯滤波卷积核)；

在精度要求不高时，Sobel是最常用的边缘检测算子(对高斯核求导再与原图像卷积)，缺点是边缘出现了好几个像素，不是只有一个像素值；

Canny边缘检测流程：

1. 高斯平滑滤波
2. 计算梯度
3. 非极大值抑制(NMS)
4. 双阈值

3.图像视频编码技术

为什么需要编码：一个高清视频存在空间冗余(帧内)、时间冗余(帧间)、心理视觉冗余(人眼对色度不敏感对亮度敏感)、编码冗余(可以用熵编码)；

涉及的三个技术：预测编码、变换编码、熵编码；

JPEG编码主要步骤：

1. 图像预处理，进行颜色空间转换和分块；
2. 零偏置电平下移，0-255转为-128到127；
3. 8x8分块 DCT变换；
4. 量化；
5. 编码；

H.264编码标准：

1. 帧内预测：分块，对于亮度，预测块可以有4×4和16×16两种尺寸吗，每种尺寸都有好几种预测方式(9和4种)，可以从各个方向来预测，计算代价，选择最优的分块尺寸和预测方式；
2. 帧间预测：运动估计(块搜索)，也可以在亚像素下进行估计，多参考帧方法；
3. 变换编码：引入4×4整数DCT(仅次于KL变换的最优正交变换)变换降低了算法的复杂度，将带有小数的系数放到量化哪里去操作(硬件不好实现带有小数的运算)；
4. 去块滤波器(对块做平滑操作(真假边界判定))，在解码的时候使用；
5. 熵编码，H.264标准规定的熵编码有两种:一种是可变长编码方案，包括统一的变长编码(UVLC)和基于上下文的自适应变长编码(CAVLC);另一种是基于上下文的自适应二进制算术编码(CABAC)。这两种方案都利用上下文信息，使编码最大限度地利用了视频流的统计信息，有效降低了编码冗余；

H.265编码标准：

1. 帧内预测：分块有64×64、32×32、16×16、8×8，最多有35种预测模式，编码结构CTU；
2. 帧间预测：
3. 变换与量化：
4. 环路滤波：去块滤波和自适应样点补偿；
5. 熵编码：只有一种熵编码：CABAC算数编码(用一段表示一个序列)，是上下文自适应编码；

4.智能多媒体通信技术

与多媒体相关的通信技术，包括TCP/IP、UDP、RTP/RTCP、RTSP、RTMP以及多媒体通信协议的应用开发技术。

数字视频接口类型：

1. SDI(Serial Digital Interface)接口，是一种广播级的高清数字输入和输出端口，常用于广播电视的摄像机接口，采用BNC接口的同轴电缆，传输非压缩的SDI信号，单线缆最多支持4Kp60标准，传输8K需要4根12G-SDI线缆，线长最多150m；
2. USB接口：USB3.0速度可达350MB/s，但线长一般控制3m以内，不超过5m；
3. HDMI接口：数字高清多媒体接口，最大传输贷款48.0Gbps，可以同时发送音频和视频信号，支持4K，即插即用，无需安装驱动，而DP接口传输速度更快，线长不超过5m；
4. GigE接口：千兆网口1000Mbps，用作高速、大数据量的图像传输，一般用来对千兆工业相机进行采集，图像数据一般是未压缩过的，上位机需要相应的千兆网卡进行接收，线长最多100m；
5. 普通IP口，100Mbps，线长最长100m，不需要采集卡，传输的是压缩的数据；

无线传输：

1. WIFI：覆盖范围小于100m，速度54Mbit/s；
2. 微波：无线电波，传输距离可达几十公里，频段一般是902-928MHz，一般选用跳频数字电台实现无线遥控；
3. LTE(如大疆无人机)
4. 5G：经过编码压缩后传输到互联网；
5. 卫星：一般是负责将演播室或现场转播系统制作完成的基带节卫星传输，常用于播出链路，目信号，通过地面卫星车内编码器压缩编码后，再通过卫星链路实现上行转发。

TCP与UDP： TCP三次握手、四次挥手还有拥塞控制(慢启动快恢复)；

RTP(Real-time Transport Protocol)与RTCP(Real-time Transport Control Protocol)：通常基于UDP协议又做了一层控制，工作于应用层和传输层之间，适用于封装要实时传输数据的应用，如视频音频模拟数据等，RTCP提供拥塞控制流量控制等(在接收端会反馈报文的损失给发送端进而调整发送速度)；

RTSP(Real Time Streaming Protocol)协议：控制分组基于TCP传输，数据分组基于UDP传输，是双向的，可以发可以拉；

RTMP(Real Time Messaging Protocol)：设计用来实时数据通信，基于TCP，多用于直播领域，默认使用端口1935，一般传输的是flv、f4v格式流，延迟在1-3s；

GB28181：国家推进的标准协议，由公安部科技信息化局提出，联网系统在进行视音频传输及控制时应建立两个传输通道:会话通道和媒体流通道。会话通道用于在设备之间建立会话并传输系统控制命令，会话协议采用SIP协议(RFC3261);媒体流通道用于传输视音频数据，经过压缩编码的视音频流采用流媒体协议RTP/RTCP传输。会话协议实现的功能主要包括:注册、心跳保活、目录查询、实时视频点播、录像查询、录像回放/下载、报警事件上报、网络校时、事件订阅等；

嵌入式AI多媒体开发架构

嵌入式AI通过底层多媒体处理接口向算法侧提供API接口，如OpenCV、FFMpeg、BMCV接口，这些接口用于对视频图像编解码、图像的基本处理如色彩空间变换、尺度变换、仿射变换等。

BMCV：自有图像处理加速接口，提供硬件加速的图像处理功能；

1. FFMPEG：开源音视频及图像处理接口(音视频编解码人员最熟悉的开源框架，提供硬件加速的H264/HEVC视频编解码，JPEG编解码，图像加速功能，所有软件支持的视频/图像编解码接口(即所有 FFMPEG 开源支持的格式)；
2. OPENCV：开源计算机视觉库(计算机视觉工程师最常用的开源框架)，封装 FFMPEG 提供硬件加速的视频编解码接口，提供硬件加速的 JPEG 编解码接口，保留原有的软件支持的图像处理功能，注意:在视频编解码上，OPENCV只是对 FFMPEG 接口的一层封装；

两种工作模式：

1. SOC模式：AI芯片中的处理器作为主控CPU，可独立运行应用程序，通过cache同步系统内存和设备内存(物理上指向同一块内存)；

2. PCIE模式：以PCIE板卡形态插到服务器主机应用程序在服务器CPU上运行，系统内存是服务器操作系统的虚拟内存空间，设备内存是PCIE板卡上的物理内存空间，在物理上是两块内存，通过PCIE同步；

C语言

1.常见使用

int i; // 整数类型变量，通常为32位（4字节）
short s; // 短整数类型变量，通常为16位（2字节）
long l; // 长整数类型变量，通常为32位或64位（4或8字节）
short int i1; // 等同于 short s; ，为16位（2字节）
long int i2; // 等同于 long l; ，为32位或64位（4或8字节）
unsigned int i3; // 无符号整数类型变量，通常为32位（4字节）
signed int i4; // 有符号整数类型变量，通常为32位（4字节）
unsigned u; // 无符号整数类型变量，大小取决于系统（一般为4字节）
signed s1; // 有符号整数类型变量，大小取决于系统（一般为4字节）
unsigned short us; // 无符号短整数类型变量，通常为16位（2字节）
总结：
int、unsigned int、signed int 通常为4字节；
short、unsigned short 通常为2字节；
long、long int 一般为4或8字节，取决于编译环境；
字节大小可能因编译环境、操作系统和编译器的不同而有所变化。

c++
#include<stdio.h>

// 定义链表
struct ListNode{
    int name;
    char b;
    char c[10];
    struct ListNode* next;
};

int main(){
    int a;
    char b;
    char str[10] = "zzwxxy";
    char str2[10];

    printf("please input string\n");
    gets(str2);
    printf("input string is:\n%s", str2);
}

/*
 * 定义字符串方式
char string[] = "zhang";
char string[] = {'z','h','a','n','g'};
char str[] = {“zhang”};
*/

/*
scanf和gets的区别：
使用方法：scanf("%s", str2);  gets(str2);
scanf ：当遇到回车，空格和tab键会自动在字符串后面添加’\0’，但是回车，空格和tab键仍会留在输入的缓冲区中。
gets：可接受回车键之前输入的所有字符，并用’\0’替代 ‘\n’.回车键不会留在输入缓冲区中

printf()和puts()的区别: 
printf("input string is:\n%s", str2);  和  puts(str2);
*/

2.链表定义及操作

c++
#include <stdio.h>
#include <stdlib.h>
struct  Node
{
   int data;
   struct Node* next;
};
struct Node* head;

// 在链表头节点插入一个值为x的节点
void Insert(int x){
   struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
   temp->data = x;
   temp->next = head;
   // if(head != NULL)temp->next = head;
   head = temp;
}

// 迭代法实现反转列表
struct Node* Reverse1(struct Node* head){
   struct Node *Current,*Prev,*next;
   Current = head;
   Prev = NULL;
   while(Current != NULL){
      next = Current->next;
      Current->next = Prev;
      Prev = Current;
      Current = next;
   }
   head = Prev;
   return head;
}

// 递归法实现反转列表
void Reverse2(struct Node* p){
   if(p->next ==NULL){
      head = p;
      return;
   }
   Reverse2(p->next);
   struct Node* q = p->next;
   q->next = p;
   p->next = NULL;
}

// 链表内指定区间反转  调试好了
struct Node* reverseBetween(struct Node* head, int m, int n ) {
    // write code here
    if(head == NULL)return head;
    if(head->next == NULL)return head;
    if(m == n)return head;
    struct Node *Current,*Prev,*next,*start,*start_last;
    int i;
    Current = head;
    Prev = NULL;
    next = NULL;
    // 先找到开始位置
    for (i=1; i<m; i++) {
        next = Current->next;
        // Current->next = Prev;
        Prev = Current;
        Current = next;
    }
    // 标记
    start_last = Prev;
    start = Current;
    // 反转
    for (i=0; i<(n-m+1); i++) {
        next = Current->next;
        Current->next = Prev;
        Prev = Current;
        Current = next;
    }
    // 头尾节点重指向
    if(start != head){
        start->next = next;
        start_last->next = Prev;//start!=head的情况下，需要保留start上一个指针
    }
    else {
        start->next = next;
        head = Prev;//start==head的情况下，直接将head指向待反转的最后一个
    }
    return head;
}

//打印链表的所有值
void Print(){
   struct Node* temp = head;
   printf("List is:");
   while(temp){
      printf("%d",temp->data);
      temp = temp->next;
   }
   printf("\n");
}

void Print2(struct Node*p){
   if(p ==NULL){
      printf("\n");
      return;
   }
   // 正序打印
   // printf("%d",p->data);
   // Print2(p->next);

   // 反转打印
   printf("%d",p->data);
   Print2(p->next);
}

int main(){
   head = NULL;
   int n,x,i;
   printf("Please input the number of node:\n");
   scanf("%d",&n);
   for(i = 0;i<n;i++){
      printf("Please input the value of Node:\n");
      scanf("%d",&x);
      Insert(x);
      Print();
   }
   head = Reverse1(head);
   printf("Reverse linked list is:\n");
   Print();

   Reverse2(head);
   printf("Reverse linked list is:\n");
   Print();
   
   // head = reverseBetween(head,2,4);
   // Print();

   // printf("Print2 linked list is:\n");
   // Print2(head);

   // char name[100];
   // printf("What is your name?\n");
   // scanf("%s",name);
   // printf("Hello,%s,nice to meet you!\n",name);
}

3.各种排序算法C语言

c++
#include <stdio.h>

// 1.插入排序，时间复杂度O(n2)，空间复杂度O(1)
void InsertSort(int a[], int n)
{
    for (int i = 1; i < n; i++)
    {
        // 若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
        if (a[i] < a[i - 1])
        {
            int j = i - 1;
            // 复制为哨兵，即存储待排序元素
            int x = a[i];
            // 先后移一个元素
            a[i] = a[i - 1];
            // 查找在有序表的插入位置
            while (x < a[j])
            {
                a[j + 1] = a[j];
                // 元素后移
                j--;
            }
            // 插入到正确位置
            a[j + 1] = x;
        }
    }
}

// 2.希尔排序,时间复杂度O(N^1.5),空间复杂度O(1)
void ShellInsertSort(int a[], int n, int dk)
{
    for (int i = dk; i < n; ++i)
    {
        if (a[i] < a[i - dk])
        { // 若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
            int j = i - dk;
            int x = a[i];     // 复制为哨兵，即存储待排序元素
            a[i] = a[i - dk]; // 首先后移一个元素
            while (j >= 0 && x < a[j])
            { // 查找在有序表的插入位置
                a[j + dk] = a[j];
                j -= dk; // 元素后移
            }
            a[j + dk] = x; // 插入到正确位置
        }
    }
}
void ShellSort(int a[], int n)
{

    int dk = n / 2;
    while (dk >= 1)
    {
        ShellInsertSort(a, n, dk);
        dk = dk / 2;
    }
}

// 选择排序,时间复杂度：O(N^2), 空间复杂度：O(1)
int SelectMinKey(int a[], int n, int i)
{
    int k = i;
    for (int j = i + 1; j < n; ++j)
    {
        if (a[k] > a[j])
            k = j;
    }
    return k;
}
void SelectSort(int a[], int n)
{
    int key, tmp;
    for (int i = 0; i < n - 1; ++i)
    {
        key = SelectMinKey(a, n, i); // 选择最小的元素
        if (key != i)
        {
            tmp = a[i];
            a[i] = a[key];
            a[key] = tmp; // 最小元素与第i位置元素互换
        }
    }
}

// 堆排序,时间复杂度：O(N*logN),空间复杂度：O(1)
void HeapAdjust(int H[], int s, int length)
{
    int tmp = H[s];
    int child = 2 * s + 1; // 左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)
    while (child < length)
    {
        if (child + 1 < length && H[child] < H[child + 1])
        { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)
            ++child;
        }
        if (H[s] < H[child])
        {                    // 如果较大的子结点大于父结点
            H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点
            s = child;       // 重新设置s ,即待调整的下一个结点的位置
            child = 2 * s + 1;
        }
        else
        { // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出
            break;
        }
        H[s] = tmp; // 当前待调整的结点放到比其大的孩子结点位置上
    }
}

/**
 * 初始堆进行调整
 * 将H[0..length-1]建成堆
 * 调整完之后第一个元素是序列的最小的元素
 */
void BuildingHeap(int H[], int length)
{
    // 最后一个有孩子的节点的位置 i=  (length -1) / 2
    for (int i = (length - 1) / 2; i >= 0; --i)
        HeapAdjust(H, i, length);
}
/**
 * 堆排序算法
 */
void HeapSort(int H[], int length)
{
    // 初始堆
    BuildingHeap(H, length);
    // 从最后一个元素开始对序列进行调整
    for (int i = length - 1; i > 0; --i)
    {
        // 交换堆顶元素H[0]和堆中最后一个元素
        int temp = H[i];
        H[i] = H[0];
        H[0] = temp;
        // 每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整
        HeapAdjust(H, 0, i);
    }
}

// 冒泡排序,时间复杂度：O(N^2),空间复杂度：O(1)
void BubbleSort(int r[], int n)
{
    int low = 0;
    int high = n - 1; // 设置变量的初始值
    int tmp, j;
    while (low < high)
    {
        for (j = low; j < high; ++j) // 正向冒泡,找到最大者
            if (r[j] > r[j + 1])
            {
                tmp = r[j];
                r[j] = r[j + 1];
                r[j + 1] = tmp;
            }
        --high;                      // 修改high值, 前移一位
        for (j = high; j > low; --j) // 反向冒泡,找到最小者
            if (r[j] < r[j - 1])
            {
                tmp = r[j];
                r[j] = r[j - 1];
                r[j - 1] = tmp;
            }
        ++low; // 修改low值,后移一位
    }
}

// 快速排序递归实现,时间复杂度：O(N*logN), 空间复杂度：O(logN)
int QuickSort(int *a, int low, int high)
{
    int i = low;    // 第一位
    int j = high;   // 最后一位
    int key = a[i]; // 将第一个数作为基准值-- 先找到一个基准值

    while (i < j)
    {
        while (i < j && a[j] >= key)
        {
            j--;
        }
        a[i] = a[j];

        while (i < j && a[i] <= key)
        {
            i++;
        }
        a[j] = a[i];
    }
    a[i] = key;
    if (i - 1 > low)
    {
        QuickSort(a, low, i - 1);
    }

    if (i + 1 < high)
    {
        QuickSort(a, i + 1, high);
    }

    return 0;
}

// 归并排序迭代实现,时间复杂度：O(N*logN), 空间复杂度：O(N)
void merge(int arr[], int start, int mid, int end, int len)
{
    int result[len];
    int k = 0;
    int i = start;
    int j = mid + 1;
    while (i <= mid && j <= end)
    {
        if (arr[i] < arr[j])
        {
            result[k++] = arr[i++];
        }
        else
        {
            result[k++] = arr[j++];
        }
    }
    if (i == mid + 1)
    {
        while (j <= end)
            result[k++] = arr[j++];
    }
    if (j == end + 1)
    {
        while (i <= mid)
            result[k++] = arr[i++];
    }
    for (j = 0, i = start; j < k; i++, j++)
    {
        arr[i] = result[j];
    }
}

void MergeSort(int arr[], int start, int end, int len)
{
    if (start >= end)
        return;
    int mid = (start + end) / 2;
    MergeSort(arr, start, mid, len);
    MergeSort(arr, mid + 1, end, len);
    merge(arr, start, mid, end, len);
}

int main()
{
    int i;
    int array[] = {9, 5, 6, 1, 4, 7, 3, 8, 2};
    int array2[9];
    // InsertSort(array, sizeof(array)/sizeof(array[0]));
    // ShellSort(array, sizeof(array)/sizeof(array[0]));
    // SelectSort(array, sizeof(array)/sizeof(array[0]));
    // HeapSort(array, sizeof(array)/sizeof(array[0]));
    // BubbleSort(array, sizeof(array)/sizeof(array[0]));
    // QuickSort(array, 0, 9-1);
    int len = sizeof(array) / sizeof(array[0]);
    MergeSort(array, 0, 9 - 1, len);

    printf("sort result is:");
    for (i = 0; i < 9; i++)
    {
        printf("%d", array[i]);
    }
    return 0;
}

4.二叉搜索树

c++
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct BstNode
{
   int data;
   struct BstNode *left;
   struct BstNode *right;
};

struct BstNode *GetNewNode(int data)
{
   struct BstNode *temp = (struct BstNode *)malloc(sizeof(struct BstNode));
   temp->data = data;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}

// 在二叉搜索树中插入一个节点
struct BstNode *Insert(struct BstNode *root, int data)
{
   if (root == NULL)
   {
      root = GetNewNode(data);
   }
   else if (data <= root->data)
   {
      root->left = Insert(root->left, data);
   }
   else
   {
      root->right = Insert(root->right, data);
   }
   return root;
}

// 在二叉搜索树中搜索一个节点
bool Search(struct BstNode *root, int data)
{
   if (root == NULL)
      return false;
   else if (root->data == data)
      return true;
   else if (data <= root->data)
      return Search(root->left, data);
   else
      return Search(root->right, data);
}

// 二叉搜索树的最小值
int FindMin(struct BstNode *root)
{
   struct BstNode *temp = root;
   if (temp == NULL)
   {
      printf("root is empty\n");
      return -1;
   }
   else
   {
      while (temp->left != NULL)
      {
         temp = temp->left;
      }
      return temp->data;
   }
}

// 二叉搜索树的最大值
int FindMax(struct BstNode *root)
{
   struct BstNode *temp = root;
   if (temp == NULL)
   {
      printf("root is empty\n");
      return -1;
   }
   else
   {
      while (temp->right != NULL)
      {
         temp = temp->right;
      }
      return temp->data;
   }
}
// 二叉搜索树的前序遍历
void Preorder(struct BstNode *root)
{
   if (root == NULL)
      return;
   printf("%d,", root->data);
   Preorder(root->left);
   Preorder(root->right);
}
// 二叉搜索树的中序遍历
void Inorder(struct BstNode *root)
{
   if (root == NULL)
      return;
   Inorder(root->left);
   printf("%d,", root->data);
   Inorder(root->right);
}
// 二叉搜索树的后序遍历
void Poseorder(struct BstNode *root)
{
   if (root == NULL)
      return;
   Poseorder(root->left);
   Poseorder(root->right);
   printf("%d,", root->data);
}

// 判断是否是二叉搜索树
bool IsSubtreeLesser(struct BstNode *root, int data)
{
   if (root == NULL)
      return true;
   if (root->data <= data && IsSubtreeLesser(root->left, data) && IsSubtreeLesser(root->right, data))
      return true;
   else
      return false;
}
bool IsSubtreeGreater(struct BstNode *root, int data)
{
   if (root == NULL)
      return true;
   if (root->data >= data && IsSubtreeGreater(root->left, data) && IsSubtreeGreater(root->right, data))
      return true;
   else
      return false;
}
bool IsBinarySearchTree(struct BstNode *root)
{
   if (root == NULL)
      return true;
   if (IsSubtreeLesser(root->left, root->data) && IsSubtreeGreater(root->right, root->data) && IsBinarySearchTree(root->left) && IsBinarySearchTree(root->right))
      return true;
   else
      return false;
}
// 二叉搜索树的高度
int FindHeight(struct BstNode *root)
{
   int LeftHeight = 0;
   int RightHeight = 0;
   if (root == NULL)
   {
      return -1;
   }
   LeftHeight = FindHeight(root->left);
   RightHeight = FindHeight(root->right);
   if (LeftHeight >= RightHeight)
      return LeftHeight + 1;
   else
      return RightHeight + 1;
}

int main()
{
   struct BstNode *root = NULL;
   printf("input start!\n");
   root = Insert(root, 10);
   root = Insert(root, 8);
   root = Insert(root, 7);
   root = Insert(root, 10);
   root = Insert(root, 35);
   root = Insert(root, 50);
   printf("input yes!\n");
   printf("%d", FindHeight(root));
   // Inorder(root);

   // if(IsBinarySearchTree(root) == true)printf("This is IsBinarySearchTree");
   // else printf("This is not IsBinarySearchTree");
   // if(Search(root,30) == true)printf("Found!\n");
   // else printf("Not Found!\n");

   // printf("%d\n",FindMax(root));
   // printf("%d",FindMin(root));
}

C++语言

1.常见操作

c++
#include<iostream>
#include <cstring> 
#include <string> 
using namespace std;  // 为了使用cin和cout

// 定义链表
struct ListNode
{
    int a;
    string name;
    char c;
    ListNode* next;
};

ListNode *head;

int main(){
    int a;
    char b;
    char c[8];
    string d;
    cout<<"please input string"<<endl;
    getline(cin, d);
    cout<<d<<endl;
    return 0;
}

/*
#include <cstring> 的作用：
可以使用string定义字符串
可以使用strlen获得字符串(字符串需要使用char s[10])定义的长度
int strcmp(const char *s1, const char *s2);当s1<s2时，返回为负数；当s1=s2时，返回值= 0；当s1>s2时，返回正数。
*/

/*
cin和getline的区别：
cin>>str不会读取空格； getline(cin, str); 可以读取空格，但是需要#include <string> 并且str需要通过 string定义；
*/

2.各种排序算法C++

/*
 *冒泡排序,时间复杂度O(N^2)；空间复杂度：O(1)；稳定排序
 *思路：第一趟：两两元素相比，前一个比后一个大就交换，直到将最大的元素交换到末尾位置；一共进行n-1趟这样的交换将可以把所有的元素排好。

 *插入排序，时间复杂度O(N^2)；空间复杂度O(1)；稳定排序
 *思路：假设数组除最后一个元素都有序了，那么将最后一个元素与前面的比较，如果前面的元素大则向右移动。实际过程从数组的第二个元素开始执行插入排序

 *希尔排序，时间复杂度O(N^1.5)；空间复杂度O(1)；不稳定排序。
 *思路：先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的元素进行排序。然后将gap逐渐减小重复上述分组和排序的工作。当到达gap=1时，所有元素在统一组内排好序。
 
 *选择排序，时间复杂度O(N^2); 空间复杂度O(1);不稳定排序。
 *思路：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始(末尾)位置，然后选出次小(或次大)的一个元素，存放在最大(最小)元素的下一个位置，重复这样的步骤直到全部待排序的数据元素排完。优化：每次最大和最小同时选.

 *堆排序，时间复杂度O(N*logN)；空间复杂度O(1)；不稳定排序。
 *思路：升序为例，构建一个堆结构，然后每个父节点均替换为子节点的最大值，然后根节点就是最大值，重复这个步骤。

 *快速排序，时间复杂度O(N*logN)；空间复杂度O(logN)；不稳定排序。
 *思路：最右边的值为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。确定两个指针left 和right 分别从左边和右边向中间遍历数组。如果选最右边为基准值，那么left指针先走，如果遇到大于基准值的数就停下来。然后右边的指针再走，遇到小于基准值的数就停下来。交换left和right指针对应位置的值。重复以上步骤，直到left = right ，最后将基准值与left(right)位置的值交换。

 *归并排序，递归实现，时间复杂度O(N*logN)；空间复杂度O(N)；稳定排序。
 *思路：采用分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

c++
#include<iostream>
using namespace std;

int len = 10;
int a[10] = {5,7,2,6,4,1,3,9,8,10};

/*
 *冒泡排序,时间复杂度O(N^2)；空间复杂度：O(1)；稳定排序
 *思路：第一趟：两两元素相比，前一个比后一个大就交换，直到将最大的元素交换到末尾位置；一共进行n-1趟这样的交换将可以把所有的元素排好。
*/
void MaoPao(int a[]){
    int temp;
    int flag = 0;
    // n-1趟排序
    for(int i = 0; i < len - 1; i++){
        for(int j = 0; j < len - 1 -i; j++){
            if(a[j] > a[j + 1]){
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
                flag = 1;
            }
        }
        // 若某一趟排序中没有元素交换则说明所有元素已经有序，不需要再排序
        if(flag == 0)break;
    }
}

/*
 *插入排序，时间复杂度O(N^2)；空间复杂度O(1)；稳定排序
 *思路：假设数组除最后一个元素都有序了，那么将最后一个元素与前面的比较，如果前面的元素大则向右移动。实际过程从数组的第二个元素开始执行插入排序
*/
void ChaRu(int a[]){
    // 从第一轮就从第二个元素开始找，所以n-1轮就可以
    for(int i = 0; i < len - 1; i++){
        // 已经有序的最后一个元素
        int end = i;
        // 需要排序的元素
        int temp = a[end + 1];
        while(end >= 0){
            if(a[end] > temp){
                // 直接替换 循环外面再将被替换的值放到适当位置
                a[end + 1] = a[end];
                end--;
            }
            else{
                break;
            }
        }
        a[end + 1] = temp;
    }
}

/*
 *希尔排序，时间复杂度O(N^1.5)；空间复杂度O(1)；不稳定排序。
 *思路：先选定一个整数gap，把待排序文件中所有记录分成gap个组，所有距离为gap的记录分在同一组内，并对每一组内的元素进行排序。然后将gap逐渐减小重复上述分组和排序的工作。当到达gap=1时，所有元素在统一组内排好序。
*/
void ShellSort(int a[], int n){
    int gap = n;
    while (gap > 1)
    {
        //gap /= 2;
        gap = gap / 3 + 1;
        for (int i = 0; i < n - gap; i++)
        {
            int end = i;
            int x = a[end + gap];
            while (end >= 0)
            {
                if (a[end] > x)
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = x;
        }
    }
}

/*
 *选择排序，时间复杂度O(N^2); 空间复杂度O(1);不稳定排序。
 *思路：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始(末尾)位置，然后选出次小(或次大)的一个元素，存放在最大(最小)元素的下一个位置，重复这样的步骤直到全部待排序的数据元素排完。优化：每次最大和最小同时选.
*/
void SelectSort(int a[], int n){
    //保存数组的起始位置
    int begin = 0;
    //保存换数组的末尾位置
    int end = n - 1;
    int temp;
    while (begin < end)
	{
            int maxi = begin;//保存最大元素下标
            int mini = begin;//保存最小元素下标
            //遍历数组寻找最小和最大元素
            for (int i = begin; i <= end; i++)
            {
                if (a[i] < a[mini])
                {
                    mini = i;
                }
                if (a[i] > a[maxi])
                {
                    maxi = i;
                }
            }
            //将最小元素交换到起始位置
            temp = a[begin];
            a[begin] = a[mini];
            a[mini] = temp;

            //判断最大值的位置是否在起始位置
            if (maxi == begin)
            {
                    maxi = mini;    
            }
            //将最大元素交换到末尾位置
            temp = a[end];
            a[end] = a[maxi];
            a[maxi] = temp;
            //移动数组起始和末尾位置
            begin++;
            end--;
        }
}

/*
 *堆排序，时间复杂度O(N*logN)；空间复杂度O(1)；不稳定排序。
 *思路：升序为例，构建一个堆结构，然后每个父节点均替换为子节点的最大值，然后根节点就是最大值，重复这个步骤。
*/
void HeapAdjust(int H[], int s, int length)
{
    int tmp = H[s];
    // 左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)
    int child = 2 * s + 1; 
    while (child < length)
    {
        if (child + 1 < length && H[child] < H[child + 1])
        { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)
            child++;
        }
        if (H[s] < H[child])
        {   // 如果较大的子结点大于父结点
            H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点
            s = child;       // 重新设置s ,即待调整的下一个结点的位置
            child = 2 * s + 1;
        }
        else
        { // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出
            break;
        }
        H[s] = tmp; // 当前待调整的结点放到比其大的孩子结点位置上
    }
}
/**
 * 初始堆进行调整
 * 将H[0..length-1]建成堆
 * 调整完之后第一个元素是序列的最小的元素
 */
void BuildingHeap(int H[], int length)
{
    // 最后一个有孩子的节点的位置 i=  (length -1) / 2
    for (int i = (length - 1) / 2; i >= 0; --i)
        HeapAdjust(H, i, length);
}
void HeapSort(int H[], int length)
{
    // 初始堆
    BuildingHeap(H, length);
    // 从最后一个元素开始对序列进行调整
    for (int i = length - 1; i > 0; --i)
    {
        // 交换堆顶元素H[0]和堆中最后一个元素
        int temp = H[i];
        H[i] = H[0];
        H[0] = temp;
        // 每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整
        HeapAdjust(H, 0, i);
    }
}

/*
 *快速排序，时间复杂度O(N*logN)；空间复杂度O(logN)；不稳定排序。
 *思路：最右边的值为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。确定两个指针left 和right 分别从左边和右边向中间遍历数组。如果选最右边为基准值，那么left指针先走，如果遇到大于基准值的数就停下来。然后右边的指针再走，遇到小于基准值的数就停下来。交换left和right指针对应位置的值。重复以上步骤，直到left = right ，最后将基准值与left(right)位置的值交换。
*/
int PartSort(int a[], int left, int right){
    // 选最右面为基准
    int key = right;
    while(left < right){
	//选右边为基准值，左指针先走
        while(left < right && a[left] <= a[key]){
            left++;
        }
        //右指针再走
        while(left < right && a[right] >= a[key]){
            right--;
        }
        // 交换
        int temp = a[right];
        a[right] = a[left];
        a[left] = temp;
    }
    int temp = a[key];
    a[key] = a[left];
    a[left] = temp;
    return left;
}
void QuickSort(int a[], int left, int right){
    if(left >= right)return;
    // 第一次快排
    int keyi = PartSort(a, left, right);
    // 左子序列快排
    QuickSort(a, left, keyi - 1);
    // 右子序列快排
    QuickSort(a, keyi + 1, right);
}

/*
 *归并排序，递归实现，时间复杂度O(N*logN)；空间复杂度O(N)；稳定排序。
  *思路：采用分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
*/
void _MergeSort(int* a, int left, int right,int* tmp)
{
    //区间中没有元素时不再合并
    if (left >= right)
    {
        return;
    }
    //划分数组，每次一分为二
    int mid = (left + right) / 2;
    _MergeSort(a, left, mid,tmp);//划分左区间
    _MergeSort(a, mid + 1, right,tmp);//划分右区间
 
    //合并有序序列
    int begin1 = left, end1 = mid;//有序序列1
    int begin2 = mid + 1, end2 = right;//有序序列2
    int i = left;
    //注意结束条件为一个序列为空时就停止
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (a[begin1] < a[begin2])
        {
            tmp[i++] = a[begin1++];
        }
        else
        {
            tmp[i++] = a[begin2++];
        }
    }

    //两序列不可能同时为空，将剩余元素合并
    while (begin1 <= end1)
    {
        tmp[i++] = a[begin1++];
    }

    while (begin2 <= end2)
    {
        tmp[i++] = a[begin2++];
    }
 
    //将合并后的序列拷贝到原数组中
    //在这里拷贝的原因是 保证返回到上一层递归后两个子序列中的元素是有序的
    int j = 0;
    for (j = left; j <= right; j++)
    {
        a[j] = tmp[j];
    }
}
void MergeSort(int* a, int n)
{
    //因为需要将两个有序序列合并，需借助额外数组
    int* tmp = (int*)malloc(sizeof(int) * n);
    if (tmp == NULL)
    {
        perror("malloc");
        exit(-1);
    }
    _MergeSort(a, 0, n - 1,tmp);
    free(tmp);
    tmp = NULL;
}

int main(){
    // MaoPao(a);
    // ChaRu(a);
    // ShellSort(a, len);
    // SelectSort(a, len);
    // HeapSort(a, len);
    // QuickSort(a, 0, len - 1);
    // MergeSort(a, len);
    cout<<"out:"<<endl;
    for(int i = 0; i < len; i++){
        cout<<a[i];
        cout<<',';
    }
}

C++容器常见使用

vector

c++
vector<int> v;//默认初始化
vector<int> v(v1);//用v1初始化v
vector<int>v(v1.begin(),v1.end());//用v1初始化v
vector<int> v(10);//定义一个大小为10的数组！
vector<int> v(10,1)//定义个全为1而且长度为10的数组

a.front() //返回第一个元素
a.back() //末尾元素
c.begin() 返回一个迭代器，它指向容器的第一个元素
c.end() 返回一个迭代器，它指向容器的最后一个元素的下一个位置
c.rbegin() //返回一个逆序迭代器，它指向容器的最后一个元素
c.rend() 返回一个逆序迭代器，它指向容器的第一个元素前面的位置
v,push_back() //增
v.insert() //插入
    1、v.insert(p, t) //将t插到p的前面
    2、v.insert(p, n, t) //将n个t插入p之前
    3、v.insert(p, i, j) //将区间[i,j)的元素插入到p之前
v.pop_back();//删除最后一个元素
v.erase(t,k)
    1、v.erase(t,k)//删除[t,k)之间的元素
    2、v.erase(p)//删除p指向的元素
v.chear()==v.erase(begin(),end());//删除所有元素

//下标法
int length = v.size();
for(int i=0;i<length;i++)
    {
        cout<<v[i];
    }
cout<<endl;
//迭代器法
vector<int>::const_iterator iterator = v.begin();
for(;iterator != v.end();iterator++)
    {
        cout<<*iterator;
    }

set容器

set底层实现通常是平衡二叉树元素自动排序，这为查找元素提供了良好性能，但同时也造成了一个重要限制：不能直接改变元素值，因为这会打乱原本正确的顺序。

unordered_set底层实现通常是hash-table元素是无序的。

c++
#include <set>

/*set 生成*/
set<int> st;

/*set 迭代器*/
set<int>::iterator iter 
st.begin() 
st.end() 

/*set 插入*/
st.insert(2); //插入一个元素

/*set 删除*/
st.erase(st.begin()); //删除迭代器指向元素 
st.erase(2); //删除所有为2的元素 

/*set 容量*/
st.size()

/*set 查找*/
st.find(2) //从前往后找，若找到，返回指向该处的迭代器；反之，返回迭代器st.end()
st.lower_bound(x) //二分查找大于等于x的元素中最小的一个，并返回指向该元素的迭代器。
st.upper_bound(x) //二分查找大于x的元素中最小的一个，并返回指向该元素的迭代器。

/*set 某元素个数*/
st.count(2); //返回容器里2的个数

/*set 判空*/
st.empty() //返回布尔值 

/*set 清空*/
st.clear();

map容器

c++
#include <map>

/*map 生成*/
map<key_type, value_type> name;
map<int, int> mp;

/*map 迭代器*/
map<int, int>::iterator iter
mp.begin() 
mp.end() 

/*map 键值*/
iter->first //key
iter->second //value

/*map 插入*/
mp[2] = 5; //直接添加
mp.insert(pair<int, int>(2, 5)); //insert一个pair

/*删除*/
mp.erase(iter); //删除迭代器所指的键值对 

/*map 容量*/
mp.size()

/*map 查找*/
mp.find(2) //从前往后找，若找到，返回指向该处的迭代器；反之，返回迭代器mp.end()

/*map 某元素个数*/
st.count(2); //返回key为2的个数（map中只可能是0或者1） 

/*map 判空*/
mp.empty() //返回布尔值 

/*map 清空*/
mp.clear();

stack 容器

c++
#include <stack>

/*stack 生成*/
stack<int> sk;

/*stack 插入*/
sk.push(2); //把一个元素放入栈 

/*stack 删除*/
sk.pop(); //删除栈顶的元素 

/*stack 栈顶*/
sk.top(); //返回栈顶元素 

/*stack 容量*/
sk.size();

/*stack 判空*/
sk.empty()

queue容器

c++
#include <queue>

/*queue 生成*/
queue<int> q;

/*queue 头尾*/
q.front();
q.back();

/*queue 插入*/
q.push(2); //在队尾插入一个元素 

/*queue 删除*/
q.pop(); //在队首删除一个元素

/*queue 容量*/
q.size();

/*queue 判空*/
q.empty()

priority_queue 容器

c++
/*
头文件queue主要包括循环队列queue和优先队列priority_queue两个容器。其中priority_queue容器相当于大根堆（或者小根堆），大根堆每次堆顶是最大元素，小根堆每次堆顶是最小元素。（以下typename均用int举例）
*/
#include <queue>

/*priority_queue 生成*/
priority_queue<int> q; //大根堆
priority_queue<int, vector<int>, greater<int>> q; //小根堆

/*priority_queue 插入*/
q.push(2); //把一个元素插入堆 

/*priority_queue 删除*/
q.pop(); //删除堆顶的元素 

/*priority_queue 堆顶*/
q.top(); //返回堆顶元素 

/*priority_queue 容量*/
q.size();

/*priority_queue 判空*/
q.empty()

list双向链表

deque

deque是double ended queue的缩写，是一个动态数组，可以向两端发展(双向开口的连续线性空间)，因此无论在头部或者尾部安插元素都十分迅速，在中间按插元素则比较费时，因为必须移动其他元素。 双端队列的元素被表示为一个分段数组，容器中的元素分段存放在一个个大小固定的数组中，此外，容器还需要维护一个存放这些数组首地址的索引数组。

初始化与定义已经在序列要求里面，而且方法与vector类似，只是多了push_front()(),pop_front(),这里不做过多的阐述。

c++
#include <deque>

/*dequeue 生成*/
dequeue<int> dq;

/*dequeue 头尾*/
dq.front();
dq.back();

/*dequeue 迭代器*/
dq.begin() 
dq.end()

/*dequeue 插入*/
dq.push_front(2); //头插入 
dq.push_back(2); //尾插入 

/*dequeue 删除*/
dq.pop_front(); //头删除 
dq.pop_back(); //尾删除 

/*dequeue 容量*/
dq.size();

/*dequeue 判空*/
dq.empty()

/*dequeue 清空*/
dq.clear();

pair容器

c++
#include <utility>

/*pair 生成*/
pair<int, int> pr = make_pair(0,1);
pair<int, int> pr(0, 1);

/*pair 两个值*/
pr.first 
pr.second 

/*pair 多与其他容器结合使用*/
set<pair<int, int>> st;
vector<pair<int, int>> vct(mp.begin(), mp.end());

1.使用MQTT实现智能家居-基于所有Linux开发板

1.相关概念

MQTT协议全称是Message Queuing Telemetry Transport，翻译过来就是消息队列遥测传输协议，它是物联网常用的应用层协议，运行在TCP/IP中的应用层中，依赖TCP协议，因此它具有非常高的可靠性，同时它是基于TCP协议的 <客户端-服务器> 模型发布/订阅主题消息的轻量级协议，也是我们常说的发送与接收数据。

MQTT适合物联网,类似：订阅电视台某个频道。

MQTT报文格式：

1. 固定报头：占两个字节，第一个字节的高4位表示控制报文的类型(两个保留使用14个)，低4位表示报文类型的标志位，PUBLISH报文的第一字节bit3是控制报文的重复分发标志（DUP），bit1-bit2是服务质量等级，bit0是PUBLISH报文的保留标志，用于标识PUBLISH是否保留，当客户端发送一个PUBLISH消息到服务器，如果保留标识位置1，那么服务器应该保留这条消息，当一个新的订阅者订阅这个主题的时候，最后保留的主题消息应被发送到新订阅的用户。固定报头的第二个字节开始是剩余长度字段，是用于记录剩余报文长度的，表示当前的消息剩余的字节数。
2. 可变报头：只有某些报文才拥有可变报头，可变报头的内容会根据报文类型的不同而有所不同。CONNECT报文的可变报头包含四个字段：协议名（Protocol Name）、协议级别（Protocol Level）、连接标志（Connect Flags）(一些标志位，如遗嘱的状态和是否有用户名密码等)以及保持连接（Keep Alive）字段。
3. 有效荷载：有效载荷也是存在与某些报文中，不同的报文有效载荷也是不一样的，比如：CONNECT报文的有效载荷（payload）包含一个或多个以长度为前缀的字段，可变报头中的标志决定是否包含这些字段。如果包含的话，必须按这个顺序出现：客户端标识符，遗嘱主题，遗嘱消息，用户名，密码 。SUBSCRIBE报文的有效载荷包含了一个主题过滤器列表，它们标识着客户端想要订阅的主题，每一个过滤器后面跟着一个字节，这个字节被叫做服务质量要求（Requested QoS），它给出了服务端向客户端发送应用消息所允许的最大QoS等级。

2.开源mqttclient框架分析

程序设计(分层)：

1. app：根据数据控制设备，while(1){等待消息；处理消息；}
2. 协议层：负责数据的解析、打包，MQTT/FTP/SSH；
3. 平台/驱动：负责设备初始化、数据收发，提供定时器/多线程/网卡收发；

客户端程序框架：

1. 订阅端要做的事情：连接、订阅(主题)、等待；
2. 发布端要做的事情：连接、发布(主题+消息本身)；

1.连接服务器函数调用过程

2.创建线程调用过程 其中创建的线程中的函数mqtt_yield_thread会读网络数据，处理数据包，保持心跳

3.发布消息调用过程

4.订阅消息过程

消息何时到来？不知道！

所以，必定是某个内核线程不断查询网卡：

• 读网卡数据

  • 得到数据的话就判断、处理

在第2步创建的线程，while(1){读网络数据；if(是否是一个发布者消息){判断那个topic,并执行对应的函数；}}

3.在Ubuntu上使用MQTT

1. git clone官方代码(用韦东山的，现在更新的有点问题)；
2. 安装cmake：sudo apt-get install cmake g++
3. 编译 & 运行：./build.sh
4. 运行build.sh脚本后会在 ./build/bin/目录下生成可执行文件emqx、baidu、onenet等多个平台的可执行程序，直接运行即可：./build/bin/emqx

4.在Linux开发板上使用MQTT

源码直接复现：

1. 官方代码编译不出来，用韦东山保存的mqttclient代码，进行交叉编译(注意修改代码后要先移除原先编译的build，不然不回更新可执行文件。
2. 实际操作：

shell
// 1. 创建文件
$ cat arm-linux.cmake
set(CMAKE_SYSTEM_NAME Linux)
set(CMAKE_C_COMPILER arm-buildroot-linux-gnueabihf-gcc)
set(CMAKE_CXX_COMPILER arm-buildroot-linux-gnueabihf-g++)
// 2. 修改build.sh
cmake .. "-DCMAKE_TOOLCHAIN_FILE=../arm-linux.cmake"
// 3. 执行
./build.sh
// 4. 编译库，得到：./libmqttclient/lib/libmqttclient.so
./make-libmqttclient.sh
// 5. 修改代码后要先移除build文件夹
rm -rf build

在工程中使用MQTT方法：

1. 方法1：修改MQTT源码，然后执行rm -rf build和./build.sh
2. 方法2：使用库
   1. 编译库(./make-libmqttclient.sh)，得到：./libmqttclient/lib/libmqttclient.so
   2. 将编译得到的./libmqttclient/include和libmqttclient.so复制出来再在makefile里编译时加上头文件.h的路径、库的路径、其他库的路径。
   3. 将库文件libmqttclient.so拷贝到开发板的/lib目录，开发板就能找到这个库了。
3. 方法3：把MQTT源码放入自己的工程
   1. 使用makefile来管理，可以使用韦东山提供的makefile模板；
   2. 添加头文件，库的位置等等；

2.物联网视频监控系统

1.两种方案：

1. MJPG-streamer：可以运行在低性能的板子上，对ARM板的性能要求不高，主频200MHz的ARM芯片也能实现。
2. ffmpeg：比较热门的流媒体方案；

2.相关概念

1. 流媒体协议：RTMP、HTTP-FLV、HLS
2. 推流端：ffmpeg；
3. 流媒体服务器：Nginx；
4. 拉流端：浏览器/VLC播放器；

3.MJPG-streamer程序框架：

在imx6ull上运行mjpg推流到本地ip的8080端口：

mjpg_streamer -i "/usr/lib/mjpg-streamer/input_uvc.so -d /dev/video1 -f 30 -q 90 -n" -o "/usr/lib/mjpg-streamer/output_http.so -w /usr/share/mjpg-streamer/www"

4.FFmpeg数据传输流程：

音视频编解码流程：

5.摄像头和声卡接口

1.摄像头接口(v4l2)：

1. 设置格式：分辨率、图像的格式、帧率；
2. 启动摄像头；
3. 得到数据：app向内核请求buffer,将buffer放入队列，摄像头驱动程序将数据存入buffer,app将buffer出列，得到数据。
4. 停止；

2.声卡接口(ALSA)：

1. 指标：采样频率、采样精度(多少位编码)；
2. 比较复杂需要使用ioctl设置很多参数，所以一般基于alsa-lib来编写app;

6.流媒体服务器nginx反向代理

移植nginx方法：1.下载源码，手工编译。2.使用Buildroot,配置选择nginx，直接编译生成映像文件。

使用Buildroot：

1. 设置交叉编译工具链
2. 下载第3方模块：
   1. 在Buildroot目录下，创建目录：mkdir dl/nginx
   2. 使用git下载：cd dl/nginx && git clone https://github.com/winshining/nginx-http-flv-module.git
   3. 在2020年使用GIT下载这个模块时，实验成功。在2023年时失败，可能是这个模块引入了bug。我们执行上述命令得到的是最新的源码，还要执行以下命令取出2020年的源码： cd dl/nginx/nginx-http-flv-module ; git checkout 1ccfee122804b28c60f1f923eee7824a5111680c
3. 在Buildroot根目录
   1. make menuconfig
   2. 把原来的lighttpd去掉，否则板子也会自动启动它，就会有两个HTTP服务了：lighttpd, nginx
   3. 如图选择Nginx，建议把所有功能都选上
   4. 并且设置额外的参数，在“additional modules”中添加： $(TOPDIR)/dl/nginx/nginx-http-flv-module
   5. 最后执行(先删除之前编译的nginx，我发现有时设置的第3方模块不起作用，删除后再make就可以了)：rm -rf output/build/nginx-1.15.7 && make
   6. 这会在Buildroot的dl/nginx目录下自动下载源码，并编译
   7. 结果保存在output/images目录下，有emmc.img, sdcard.img，可以直接烧写到板能的EMMC或SD卡上

rtmp协议走的端口经常被防火墙拦截，可以使用http_flv协议(修改配置文件增加一个location节点) rtmp推流给nginx过程：rtmp推流到某个地址，nginx访问的html界面中含有这个地址，就能观看到摄像头视频；

7.内网穿透：

1. 可以使用花生壳实现内网穿透只要本地浏览器可以拉流，就可以映射到花生壳，但是免费版带宽只有1Mbps很卡；
2. 也可以将nginx部署到自己的服务器；

3.基于Linux从零写BootLoader

单板下载方式：

1. 后台式下载：在升级的时候，新固件在后台悄悄下载，即新固件下载属于应用程序功能的一部分，在新固件下载过程中，应用可以正常使用。下载完成后，系统再跳到BootLoader程序，由BootLoader完成新固件覆盖老固件的操作
2. 非后台式下载：在升级的时候，系统需要先从应用程序跳入到BootLoader程序，由BootLoader进行新固件下载工作，下载完成后BootLoader继续完成新固件覆盖老固件的操作，至此升级结束。

新旧固件覆盖模式：

1. 双区模式：双区模式中老固件和新固件在flash中各占一块bank（存储区），对应后台式下载；
2. 单区模式：单区模式的非后台式下载只有一个bank0（运行区），老固件和新固件共享这一个bank0，对应非后台式下载。

MCU OTA升级过程：

1. 制作升级包：固件Firmware通过数字签名得到升级包(包括firmware、header和signature value);
2. 下载升级包：根据上位机软件和MCU设备约定的通信协议，上位机软件将升级包通过OTA方式发送给MCU设备，MCU设备收到数据后，根据通信协议解析出升级包的数据，并将升级包的数据保存到存储器中。
3. 验签升级包：MCU设备接收完所有的升级包后，先计算升级包中固件的摘要，然后使用非对称秘钥的公钥解密升级包的签名值，如果解密出来的固件摘要与自己计算的摘要相同，则验签成功。
4. 固件更新：验签成功保证了固件的完整性和合法性后，MCU设备从应用程序进入BootLoader程序，在BootLoader程序中将flash中的新固件数据搬运到旧固件的存储区，将其覆盖。然后BootLoader程序启动固件运行，此时固件为新固件。

Linux OTA升级过程： 升级过程基本和MCU类似，有以下概念：

1. linux系统主要由三大部分组成为uboot(引导启动程序)、kernel(内核)和rootfs(根文件系统)，在flash中以此存放。
2. Linux系统的启动流程：上电->bootloader->(启动)->kernel->(挂载)->rootfs->(启动)->app;
3. 一般可在uboot中下载升级包来升级uboot\kernel\rootfs ，与MCU在BootLoader程序中完成升级类似。
4. 应用程序升级流程：制作升级包（打包签名工具）、下载升级包（下载工具）、升级包验签、程序更新。（与MCU OTA升级的区别：在制作升级包时将应用程序相关的文件，比如可执行程序、库文件、配置文件打包为压缩包再进行签名）
5. OTA升级的核心：1.如何接收固件；2.如何保证固件的完整性和合法性；3.如何替换固件；

RAM、ROM、Flash的区别：

1. RAM：掉电数据丢失，但运行快，正是因为运行快，所以程序中变化的数据都会在RAM中变化，变量也存储在里面。
2. flash：运行慢，但掉电数据不丢失，正是因为掉电不丢失，所以写好的程序会存在flash里面。
3. ROM：一种半导体内存，其特性是一旦储存资料就无法再将之改变或删除。通常用在不需经常变更资料的电子或电脑系统中，资料并且不会因为电源关闭而消失。只能读出事先所存数据的固态半导体存储器。
4. 在单片机中RAM是存变量以及变量的运算的地方，flash是存程序的地方。

BootLoader 引入的目的：更新系统； 主要作用：

1. 初始化硬件：比如设置时钟、初始化内存；
2. 启动内核/APP：从Flash读出内存、存入内存、给内核设置参数、启动内核；
3. 调试作用：在开发产品时，需要经常调试内核，使用BootLoader可以方便地更新内核；

必备知识： 段/重定位 散列文件 异常向量

4.uboot移植

uboot：universal bootloader; uboot就是一个裸机程序，功能是用来启动内核，进而启动各种应用程序；作为通用的bootloader能支持很多soc厂家、板卡厂家、开发的不同型号的板；

linux硬件组成：

在flash中有uboot、内核和文件系统的程序。单片机内存比较小一般64KB，可以直接用SRAM(不用初始化)，linux内存比较大，几百M，几G，一般用DDR/SDRAM(需要初始化)

uboot有flash的驱动程序，能读flash，上电启动过程：

1. 先运行uboot，启动内核：
   1. 初始化内存；
   2. 初始化其他硬件(时钟、flash);
   3. 读flash把内核copy进内存；
   4. 启动内核；
2. 内核程序启动应用程序：
   1. 读写flash，启动驱动程序：网络/u盘/LCD/其他输入输出设备；
   2. 以一定的格式能读写文件，文件系统；
   3. 找到并启动APP；

uboot源码提供了dtb目录用来各种厂家的设备树指定硬件资源，这些dts文件不会编译进uboot的可执行文件，只作为配置文件传给uboot使用。

烧录的uboot = 原始uboot.bin + 某个dtb；

保证uboot源码不臃肿。

XIP(execute in place)，RAM和Flash都是XIP设备，cpu可以直接发出地址信号读得到指令并执行，都是cpu读取指令就好像直接在内存上运行的程序，其实执行是在cpu上。SD卡就不是XIP设备，需要CPU通过emmc控制器读取SD上的指令然后运行(这个过程需要通过BootROM，cpu可以直接读BootROM上代码执行，BootROM上的代码可以将SD卡上的uboot上的程序读到内存中)。

因此uboot启动流程，根据uboot代码位置分为两种情况：

1. 对于XIP设备：
   1. 硬件初始化(内存、flash、时钟等)；
   2. 读flash，把内核copy进内存;
   3. 启动内核；
2. 对于非XIP设备：
   1. 由BootROM把uboot复制进内存RAM；
   2. 下面开始执行uboot；
   3. 硬件初始化(不用初始化RAM)；
   4. 读flash，把内核copy进内存;
   5. 启动内核；

uboot源码结构，在u-boot目录下执行"tree . -d > 1.txt"，可以得到目录的结构，精简如下：

shell
├── arch    
│   ├── arm              // 1. 架构相关
│   │   ├── cpu
│   │   │   ├── armv7
│   │   │   │   ├── mx6
│   │   ├── dts
│   │   │   └── include
│   │   │       └── dt-bindings -> ../../../../include/dt-bindings
│   │   ├── include
│   │   │   ├── asm
│   │   │   │   ├── arch-imx
│   │   │   │   ├── arch-imx8
│   │   │   │   ├── arch-imx8m
│   │   │   │   ├── imx-common
│   │   │   └── debug
│   │   ├── lib
│   │   ├── mach-rockchip
│   │   │   ├── rk3036
│   │   │   ├── rk3288
│   │   │   └── rk3399
│   │   ├── lib
├── board                // 单板相关
│   ├── freescale
│   │   ├── common
│   │   │   └── p_corenet
│   │   ├── corenet_ds
│   │   ├── mx6ul_14x14_ddr3_arm2
│   │   ├── mx6ul_14x14_evk
│   │   ├── mx6ul_14x14_lpddr2_arm2
│   │   ├── mx6ull_ddr3_arm2
│   │   ├── mx6ullevk
├── cmd                  // 通用的命令
│   ├── fastboot
│   └── mvebu
├── common               // 通用的
│   ├── eeprom
│   ├── init
│   └── spl
├── configs
├── disk
├── drivers               // 各类驱动
├── fs                    // 文件系统
│   ├── cbfs
│   ├── cramfs
│   ├── ext4
│   ├── fat
│   ├── jffs2
│   ├── reiserfs
│   ├── sandbox
│   ├── ubifs
│   ├── yaffs2
│   └── zfs
├── include
├── lib                  // 库
├── net                  // 网络协议

Makefile分析：比如all规则，clean规则，include语法；

vim命令删除注释:g/^#/d

uboot中有很多源码，用编译哪些源码得到最后的uboot.bin文件需要配置。比如IMX6ULL配置命令: make mx6ull_14x14_evk_defconfig生成了.config文件。

执行过程：

• 制作工具：scripts/kconfig/conf
• 把默认配置信息写入文件".config"

文件.config中含有架构、soc、厂家、单板等配置信息。

以命令mx6ull_14x14_evk_defconfig为例分析怎么得到的.config文件：

从makefile中分析过程，mx6ull_14x14_evk_defconfig依赖scripts/kconfig/conf，又依赖其他东西...，makefile中以下过程展开：

shell
mx6ull_14x14_evk_defconfig: scripts/kconfig/conf
	$(Q)$< $(silent) --defconfig=arch/$(SRCARCH)/configs/$@ $(Kconfig)

就是：

shell
UBOOTVERSION=2017.03 scripts/kconfig/conf --defconfig=arch/../configs/mx6ull_14x14_evk_defconfig Kconfig

所以要分析scripts/kconfig/conf.c，该代码整体结构：

shell
defconfig_file = "arch/../configs/mx6ull_14x14_evk_defconfig";
name = "Kconfig"

conf_parse(name);  // 解析uboot根目录下的Kconfig文件

conf_read(defconfig_file); // 读配置文件

conf_set_all_new_symbols(def_default); // 设置new_symbols为默认值

conf_write(NULL); // 写到.config

分析结果：

• Kconfig：这是一个通用文件，里面规定了一些依赖，比如：
  • 如果是ARM架构，就默认选中A、B、C配置
  • 如果是RISC-V架构，就默认选中a、b、c配置
• defconfig_file：这是厂家提供的，里面定义了
  • ARM架构
  • 自己的一些配置项
• 怎么处理呢？
  • 使用defconfig_file的内容去解析Kconfig，确定各个依赖的配置项
  • 其他未涉及的配置项，给它们指定默认值
  • 写入.config

uboot config界面语法(增加配置项、菜单(多选、单选)，选择了某个配置项后就会把这个功能编进uboot里)；

得到的.config用来选择哪些目录/文件被编译，并得到一个.h文件存放.c文件用到的宏等；

得到.config后，使用make就可以编译uboot了，内部过程：

1. 检查更新头文件，比如include/config.h、u-boot.cfg(才是完全的最终的信息)
2. 制作工具
3. 交叉编译：编译哪些目录哪些文件，.c文件可能需要使用.config的配置值，它可以引用config.h

整体理解uboot编译流程（涉及子文件目录的编译等等，Makefile文件还是很复杂的）

XIP

BootROM

相对寻址、绝对寻址

uboot完整启动流程总结：

基本概念

机器学习

1.常见的激活函数

1. Sigmoid：1/（1+e-x） 缺点：梯度消失;
2. Tanh：=2Sigmoid(2x) - 1缺点：梯度消失;
3. Relu：=x(x>0时) =0(x<0时);

2.卷积运算的输出尺寸：

Out = (in + 2p - k)/s + 1;

3.NoSql

非关系型数据库，不使用SQL作为主要查询语言，而是主要以key-value键值对的形式进行数据存储。这种数据库设计主要针对当前互联网时代的复杂数据，具备高度的可伸缩性和可用性。作用：作为缓存减少IO读操作，减轻CPU和IO压力，通过内存直接读取数据，相对于传统关系型数据库，能够处理超大规模和高并发数据。

4.分布式计算

如何应用分布式系统进行计算，即把一组计算机通过网络相互连接组成分散系统，然后将需要处理的数据分散成多个部分，交由分散在系统内的计算机组同时计算再将结果最终合并得到最终结果。

5.大数据相关的技术(工具、技术和方法)：

1. 大数据存储技术：包括分布式文件系统（如HDFS）、分布式数据库（如Cassandra、HBase）和NoSQL数据库（如MongoDB、Redis）等。
2. 大数据处理技术：包括分布式计算框架（如MapReduce、Spark）、流处理框架（如Storm、Flink）和图处理框架（如Giraph）等。
3. 大数据分析技术：包括数据挖掘、机器学习、统计分析等方法，以及可视化工具（如Tableau、PowerBI）等。
4. 大数据采集技术：包括数据抓取技术、数据清洗技术、数据集成技术等。大数据安全技术：包括数据加密、数据备份、数据恢复等，保证数据的安全性和可靠性。

6.LR（Logistic Regression）(一种解决二分类的机器学习方法)

LR是一种用于二分类和多分类问题的线性模型。它使用逻辑函数将输入特征与输出概率之间建立关联，通常用于概率建模和分类任务。

7.准确率有什么缺点和问题

准确率（Accuracy）在不平衡数据集中容易误导，因为它不考虑类别之间的不平衡。在类别分布不均匀时，准确率可能不是一个合适的评估指标，需要考虑其他指标如精确度、召回率、F1分数等。

8.常见的优化算法

常见的优化算法包括梯度下降法（包括随机梯度下降和批量梯度下降）、Adam、RMSprop、Adagrad等。这些算法用于调整模型参数以最小化损失函数。

9.常见的特征提取方法

常见的特征提取方法包括主成分分析（PCA）、线性判别分析（LDA）、单词嵌入（Word Embeddings）、卷积神经网络（CNN）特征提取等，用于从原始数据中提取有用的特征。

10.CNN和MLP区别，CNN的优势

CNN（卷积神经网络）和MLP（多层感知机）都是神经网络模型，但CNN在处理图像和空间数据时具有优势。CNN使用卷积层和池化层可以捕捉局部特征和空间结构，减少了参数数量，并且在图像处理等领域表现出色。

11.RNN和LSTM，优缺点

RNN（循环神经网络）是一种适用于序列数据的神经网络，但它存在梯度消失和梯度爆炸的问题。LSTM（长短时记忆网络）是RNN的一种变体，通过门控机制解决了梯度问题，可以更好地捕捉长期依赖性。然而，LSTM相对复杂，训练和计算成本较高。

12.常见的传统机器学习算法

线性回归、逻辑回归、决策树、支持向量机、朴素贝叶斯等

13.过拟合(overfitting)与解决办法

过拟合是训练效果很好，预测效果很差； 解决：

1. 增加数据量，数据增强；
2. 正规化：（简化机器学习的关键公式为 y=Wx . W为机器需要学习到的各种参数. 在过拟合中, W 的值往往变化得特别大或特别小. 为了不让W变化太大, 我们在计算误差上做些手脚. 原始的 cost 误差是这样计算, cost = 预测值-真实值的平方. 如果 W 变得太大, 我们就让 cost 也跟着变大, 变成一种惩罚机制）
3. Dropout:训练的时候, 我们随机忽略掉一些神经元和神经联结 , 是这个神经网络变得”不完整”. 用一个不完整的神经网络训练一次.
4. 简化模型:
5. 多种模型组合：
6. 贝叶斯方法：

14. min(x,y)的期望；X,Y服从0-1的高斯分布，问min(x,y)的期望

高斯分布

均匀分布：

相关概念

0.设计原则

六大设计原则：

1. 单一职责原则，理解：不同的类具备不同的职责，各司其职。做系统设计是，如果发现有一个类拥有了两种职责，那么就要问一个问题：可以将这个类分成两个类吗？如果真的有必要，那就分开，千万不要让一个类干的事情太多。总结：一个类只承担一个职责
2. 开放封闭原则，理解：类、模块、函数，可以去扩展，但不要去修改。如果要修改代码，尽量用继承或组合的方式来扩展类的功能，而不是直接修改类的代码。当然，如果能保证对整个架构不会产生任何影响，那就没必要搞的那么复杂，直接改这个类吧。总结：对软件实体的改动，最好用扩展而非修改的方式。
3. 里式替换原则，理解：父类可被子类替换，但反之不一定成立。也就是说，代码中可以将父类全部替换为子类，程序不会出现异常，但反过来就不一定了。总结：在继承类时，务必重写（override）父类中所有的方法，尤其需要注意父类的protected方法（它们往往是让你重写的），子类尽量不要暴露自己的public方法供外界调用。
4. 最少知识原则，理解：尽量减少对象之间的交互，从而减小类之间的耦合。在做系统设计时，不要让一个类依赖于太多其他的类，需尽量减小依赖关系，否则死都不知道怎么死的。总结：一定要做到：低耦合、高内聚。
5. 接口隔离原则，理解：不要对外暴露没有实际意义的接口。也就是说，尽量保证接口的实用性。当需要对外暴露接口时，需要再三斟酌，若没必要对外提供就删了吧，因为一旦提供了就意味着，将来要多做一件事情，何苦给自己找事做呢。总结：不要对外暴露没有实际意义的接口。
6. 依赖倒置原则，理解：高层模块不应该依赖于底层模块，而应该依赖于抽象。抽象不应依赖于细节，细节应依赖于抽象。应该面向接口编程，不该面向实现类编程。面向实现类编程相当于就事论事，那是正向依赖；面向接口编程，相当于透过现象看本质，抓住事务的共性，那就是反向依赖，即依赖倒置。总结：面向接口编程，提取出事务的本质和共性。

23种设计模式：

1. 创建型模式（5种）：工厂方法模式、抽象工厂模式、单例模式、建造者模式、原型模式。
2. 结构型模式（7种）：适配器模式、装饰器模式、代理模式、外观模式、桥接模式、组合模式、享元模式。
3. 行为型模式（11种）：策略模式、模板方法模式、观察者模式、迭代子模式、责任链模式、命令模式、备忘录模式、状态模式、访问者模式、中介者模式、解释器模式。

1.编程语言

1.列表、数组、链表的区别：

1. 列表可以存放不同的数据类型、数组和链表是存放相同数据类型的集合；
2. 列表和数组内存连续，链表内存不连续；
3. 列表不可以进行数学四则运算，数组可以进行数学四则运算；
4. 数组和列表访问速度比链表快；
5. 链表增加删除操作比数组和列表快；

2.define和const的区别

1. define是预处理指令，用于创建符号常量。const是C和C++的关键字，用于创建具有常量值的变量，本质是只读变量。
2. define在预处理阶段执行。const在编译阶段执行。
3. define没有类型检查，仅进行文本替换。const有类型检查，可以与变量类型关联。

3.指针和引用的区别

1. 指针：指针是一个变量，保存着内存地址。引用：引用是已存在变量的别名，没有自己的内存地址。
2. 指针可以具有空值(NULL)，引用不能为空，必须在初始化时指向一个有效的对象。
3. 可以修改指针的指向，可以将指针重新赋值为另一个地址。一旦引用被初始化，它始终指向同一个对象，不可更改。
4. 指针需要额外的内存空间来存储地址值。引用不需要额外的内存空间，因为它是对已存在变量的别名。

4.[C/C++] const int* 与 int const* 的区别

先确定一个规则：const默认与左边结合，左边没有东西则与右边结合。在这个规则下进行分析。
1.const int* a
const与int结合，因此变量a是一个指向常量整型的指针。
2.int const * a
const与int结合，因此变量a与1同。
3.int* const  a
const与*结合，因此变量a是一个指向整型的常量指针。
4.const int* const a
第1个const与int结合，第2个const与*结合，因此变量a是一个指向常量整型的常量指针。
5.int const * const a
第1个const与int结合，第2个const与*结合，因此变量a与上同。
6.int const * const * a
第1个const与int结合，第2个const与左边的*结合，而变量a前还有1个多出来的*，因此变量a是一个二级指针，即指向4/5中常量指针的指针。
7.int const * const * const a
第1个const与int结合，第2个const与左边的*结合，第3个const也与左边的*结合，因此变量a是一个常量二级指针，即指向4/5中常量指针的常量指针。
附注：1.常量整型不可改值。2.常量指针不能修改指针的指向。

5. volatile关键字：

1. volatile 可以保证对特殊地址的稳定访问（变量地址）；
2. 到地址去读取，告诉编译器不要优化；
3. 用处：a. 中断服务程序中修改的变量需要加 volatile；b. 全局变量；c. 多任务环境下各任务间共享的标志应该加 volatile；

6. inline关键字：

1. inline 是C++引入的关键字
2. inline 只适合涵数体内代码简单的涵数使用（switch while for）
3. inline 是一种"用于实现的关键字"
4. 内联是以代码膨胀（复制）为代价
5. 如果函数体内出现循环，那么执行函数体内代码的时间要比函数调用的开销大，(不能有switch while)
6. inline 只适合涵数体内代码简单的涵数使用

4. 有符号和无符号运算，强制转换为无符号。

5.C语言const、static、extern、volatile关键字

1. const，只读常量，不可以修改和二次赋值，可以用在变量声明时对变量进行初始化，也可以修饰指针，有常量指针，指向的内容(*p)不能改变，还有指针常量，指针本身(p)不能改变；也可以修饰引用，即变量的别名；也可以修饰函数的形参，即传入的参数在函数内数值不能改变；还可以修饰函数返回值；
2. static，加static修饰，为静态变量，存储在静态内存中，在整个程序执行过程中一直存在，不像局部变量，当所在的函数执行完后就自行销毁了，整个程序结束之后static变量才会被回收，这是修饰局部变量，当修饰全局变量和修饰函数的时候，会修改标识符的链接属性，从外部链接属性变为内部链接属性，即只能在当前源文件中访问不能在其他源文件中访问；也可在面向对象的编程中，修饰类内数据成员和成员函数，修饰类内成员后，对于类的每个对象，它是共有的，修饰成员函数也是对每个对象共有，所以不能有this指针。
3. extern,修饰变量表示改变量在别的文件中已有声明了，如果在另一个文件中将这个变量声明为外部变量，那么这个变量的作用域将被扩展到另外一个文件中。
4. volatile，易变的关键词，告诉编译系统所修饰的变量可能会被意想不到地改变。那么编译器就不会对代码进行优化，每次遇到这个变量就去内存中去读，用于中断服务程序中供其他程序检测的变量、用于多任务环境下，各任务间共享的标志、用于存储器映射的硬件寄存器的定于。

6.B树 B+树 红黑树定义区别

B树：

定义： B树是一种自平衡的多路搜索树，它可以有多个子节点，不同于二叉树的是，一个节点可以有超过两个的子节点。B树特别适合用于读写相对较大的数据块的存储系统，如磁盘。

数据结构： 一个B树的节点可能包含多个键（数据项）和子指针。节点中的键是有序的，并且每个键的左侧子树包含的键都比它小，右侧子树包含的键都比它大。B树通过重新分布键和指针，分裂和合并节点来维持平衡。

优点： 减少了磁盘I/O操作。保持了树的平衡。对于大型数据集的查找和顺序访问非常高效。

缺点： 节点分裂和合并的过程相对复杂。当数据经常插入和删除时，维护成本较高。

应用： 数据库索引。文件系统。

B+树：

定义： B+树是B树的变种，所有的值都在叶子节点上，并且叶子节点是通过指针连接的，这样就提供了对数据的顺序访问。内部节点（非叶子节点）只存储键值，并作为索引使用。

数据结构： 与B树类似，但B+树有两个不同点：一是非叶子节点不存储数据，仅用于索引；二是所有叶子节点之间都是相互链接的，这样就支持了快速的顺序遍历。

优点： 所有的查询都要查找到叶子节点，查询性能稳定。叶子节点形成了一个有序链表，便于全范围扫描。

缺点： 由于数据只存在于叶子节点，所以可能需要更多的I/O操作来达到叶子节点。

应用： 数据库索引（特别是范围查询和顺序访问）。

红黑树：

定义： 红黑树是一种自平衡的二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是红色或黑色。通过对任何一条从根到叶子的路径上各个节点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出两倍，因而是近似平衡的。

数据结构： 每个节点包含颜色、键值、左右子节点以及指向父节点的指针。红黑树的约束包括：每个节点要么是红色，要么是黑色。根节点是黑色。所有叶子（NIL节点）是黑色。如果一个节点是红色的，则它的子节点必须是黑色的（反之不一定）。从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

优点： 保证最长路径不会超过最短路径的两倍，因而是平衡的。在实际应用中，插入、删除、查找操作都有很好的性能。

缺点： 算法实现相对复杂。在最坏情况下，可能需要多次颜色变更和树旋转。

应用： 关联数组。高级语言的数据结构库，如C++的STL中的map和set。

B树与B+树与红黑树的区别

1. B树和B+树都是多路平衡查找树，而红黑树是二叉平衡查找树。
2. B树中节点存储键和数据，而B+树的数据仅存储在叶子节点，内部节点只存键。
3. B+树的叶子节点通过指针相连，便于全范围扫描，而B树不是。
4. 红黑树的操作相对于B树和B+树来说更快，因为它是二叉的，但在处理大量数据时，由于B树和B+树减少了磁盘I/O，可能会更有效率。
5. B树和B+树通常用于数据库和文件系统中，红黑树多用于内存中数据结构的实现。

2.ARM架构

1.内存映射的原理

1. 将一块内存空间映射到不同的进程空间中

2.进程和线程的区别：

1. 进程是一个具有独立功能的程序，是系统进行资源分配和调度的独立单位;
2. 线程是进程中的一个执行任务，是处理器调度和分配的基本单位;
3. 一个进程至少拥有一个线程，多个线程可以共享数据;

3.进程间的通信方式：

信号量、消息队列、共享内存、管道、套接字;

4.黑盒测试、白盒测试、灰色测试

1. 黑盒测试是测试人员不了解正在测试的软件的内部结构和源代码。与用户界面进行交互，测试其功能。单元，集成，系统和验收;
2. 白盒测试方法的目标是对软件的内部结构及其背后的逻辑进行分析。找一些边界情况进行测试;
3. 灰盒测试介于两者中间;

5.TCP和UDP的区别：

1. TCP和UDP是计算机网络中传输层的两个主要协议，主要有以下几个方面的区别：
2. 连接特性方面：
   1. TCP是面向连接的协议。在传输数据之前，需要通过三次握手来建立连接，并在数据传输完成后通过四次挥手来释放连接。这种连接机制确保了数据传输的可靠性和顺序性;
   2. UDP则是无连接的协议。发送数据前不需要建立连接，直接发送数据包，这使得UDP在传输数据时更加灵活和高效;
3. 可靠性方面：
   1. TCP使用校验和、重传控制、序号标识、滑动窗口和确认应答等机制来确保数据的无差错、不丢失、不重复且按序到达;
   2. UDP则提供尽最大努力交付的服务，不保证数据的可靠传输。在数据传输过程中，如果发生丢包或乱序，UDP不会进行重传或顺序控制;
4. 效率与实时性：
   1. UDP具有较好的实时性和较高的工作效率，因为它不需要建立连接和进行复杂的控制操作;
   2. TCP虽然提供了可靠的数据传输，但由于其复杂的控制机制，相对UDP而言效率较低;
5. 通信模式：
   1. TCP连接只能是点对点的，即一条TCP连接只能连接两个端点;
   2. UDP则支持一对一、一对多、多对一和多对多的交互通信模式，这使得UDP在广播和多播等场景中更具优势;
6. 首部开销：
   1. TCP的首部较大，通常为20字节，这增加了每个数据包的开销;
   2. UDP的首部较小，只有8字节，减少了数据包的开销，提高了传输效率;

OSI网络模型

层级	名称	作用	协议	关键词
7	应用层	各类网络服务	HTTP、FTP
6	表示层	数据编码、格式转换、加密	LPP、NBSSP
5	会话层	维护会话	SSL、TLS、DAP、LDAP
4	传输层	建立主机端到端的连接（应用间的通信）	TCP、UDP	端口号、TCP、UDP
3	网络层	路由选择，控制数据包在设备间的转发（主机间通信）	**IP、ICMP、路由器、**RIP、IGMP、OSPF	IP地址、路由器、ping通
2	数据链路层	将比特流封装成数据帧（数据帧、网卡间通信）	ARP、网卡、交换机、PPTP、L2TP、ATMP	MAC地址、网卡
1	物理层	定义电平、传输介质、物理接口	光纤、集线器、中继器等物理器件

3.三次握手、四次挥手流程

1. 第一次握手：Client将标志位SYN(建立新连接)置为1，随机产生一个值seq=x，并将该数据包发送给Server，Client进入SYN_SENT状态，等待Server确认。
2. 第二次握手：Server收到数据包后由标志位SYN=1知道Client请求建立连接，Server将标志位SYN和ACK(确认)都置为1，ack=x+1，随机产生一个值seq=y，并将该数据包发送给Client以确认连接请求，Server进入SYN_RCVD状态。
3. 第三次握手：Client收到确认后，检查ack是否为x+1，ACK是否为1，如果正确则将标志位ACK置为1，ack=y+1，并将该数据包发送给Server，Server检查ack是否为y+1，ACK是否为1，如果正确则连接建立成功，Client和Server进入ESTABLISHED状态，完成三次握手，随后Client与Server之间可以开始传输数据了。
4. 第一次挥手：客户端向服务器发起请求释放连接的TCP报文，置FIN为1。客户端进入终止等待-1阶段。
5. 第二次挥手：服务器端接收到从客户端发出的TCP报文之后，确认了客户端想要释放连接，服务器端进入CLOSE-WAIT阶段，并向客户端发送一段TCP报文。客户端收到后进入种植等待-2阶段。
6. 第三次挥手：服务器做好了释放服务器端到客户端方向上的连接准备，再次向客户端发出一段TCP报文。。此时服务器进入最后确认阶段。
7. 第四次挥手：客户端收到从服务器端发出的TCP报文，确认了服务器端已做好释放连接的准备，于是进入时间等待阶段，并向服务器端发送一段报文。注意：第四次挥手后客户端不会立即进入closed阶段，而是等待2MSL再关闭。

3.TCP通信为什么连接的时候是三次握手，关闭的时候却是四次握手？

1. 因为当Server端收到Client端的SYN连接请求报文后，可以直接发送SYN+ACK报文。其中ACK报文是用来应答的，SYN报文是用来同步的。但是关闭连接时，当Server端收到FIN报文时，很可能并不会立即关闭SOCKET，所以只能先回复一个ACK报文，告诉Client端，“你发的FIN报文我收到了”。只有等到我Server端所有的报文都发送完了，我才能发送FIN报文，因此不能一起发送。故需要四步握手。

4.进程之间的通信方式

1. 管道pipe：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
2. 命名管道FIFO：有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。
3. 消息队列MessageQueue：消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
4. 共享存储SharedMemory：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量，配合使用，来实现进程间的同步和通信。
5. 信号量Semaphore：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
6. 套接字Socket：套解口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同及其间的进程通信。
7. 信号 ( sinal ) ： 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。

5.堆和栈的区别

1. 程序内存布局场景下，堆与栈表示两种内存管理方式。

   1. 栈由操作系统自动分配释放 ，用于存放函数的参数值、局部变量等；
   2. 堆由开发人员分配和释放， 若开发人员不释放，程序结束时由 OS 回收，分配方式类似于链表。
   3. 堆的生长方向向上，内存地址由低到高；栈的生长方向向下，内存地址由高到低。

2. 数据结构场景下，堆与栈表示两种常用的数据结构。

   1. 栈是一种线性结构，所以可以使用数组或链表（单向链表、双向链表或循环链表）作为底层数据结构，拥有“先进后出”的特性；
   2. 堆是一种常用的树形结构，是一种特殊的完全二叉树，当且仅当满足所有节点的值总是不大于或不小于其父节点的值的完全二叉树被称之为堆。堆的这一特性称之为堆序性。因此，在一个堆中，根节点是最大（或最小）节点。如果根节点最小，称之为小顶堆（或小根堆），如果根节点最大，称之为大顶堆（或大根堆）。堆的左右孩子没有大小的顺序。

6. FreeRTOS和Linux的区别

FreeRTOS和Linux是两个不同的嵌入式操作系统，它们在设计理念、架构和功能上存在一些异同。

• 设计理念：FreeRTOS是一个实时操作系统（RTOS），专注于实时性和资源占用的最小化。它被设计用于低功耗、有限资源的嵌入式系统。而Linux是一个通用的操作系统，注重功能丰富性和多任务处理能力。它被广泛应用于服务器、PC和嵌入式系统。
• 架构：FreeRTOS采用了基于优先级的抢占式调度算法，具有较低的内存占用和响应时间延迟。它通常以任务为单位进行调度，任务之间共享资源需要通过信号量、互斥锁等机制进行同步和互斥操作。而Linux采用了时间片轮转调度算法，支持多线程和多进程并发执行。它提供了丰富的进程间通信（IPC）机制，如管道、信号量、消息队列等。
• 功能：FreeRTOS提供了基本的任务管理、内存管理、事件驱动等功能，并且可以根据具体需求进行定制和扩展。它适用于对实时性要求较高的应用场景，如工业控制、汽车电子等。而Linux提供了更为完善的文件系统、网络协议栈、设备驱动等功能，适用于需要复杂功能和大规模软件开发的应用领域。

总体而言，FreeRTOS和Linux在实时性能、资源占用和功能丰富度上存在差异。选择使用哪个操作系统取决于具体的应用需求和资源限制。

7.FreeRTOS处理中断

Cortex-M内核支持中断优先级配置，中断优先级数值越小，优先级越高，与FreeRTOS任务优先级相反，任务优先级数值越小，优先级越低。

FreeRTOS中，实际上是没有中断的，中断还是由硬件产生。以STM32为例，中断请求的响应过程还是由STM32的中断服务函数完成，而FreeRTOS在其中的作用可以说成是唤醒某个阻塞或就绪任务。

也就是说，在硬件STM32的中断函数中，需要使用信号量或事件等完成中断与FreeRTOS系统任务的通信，实现通过中断函数来唤醒一次或多次FreeRTOS系统任务。

假设我们正在开发一个嵌入式系统，其中一个传感器通过中断方式通知系统有新的数据可用。我们将使用 FreeRTOS 来处理这个中断事件。在这个示例中，传感器中断触发 vSensorISR 中断服务例程，该例程通过释放信号量 xSemaphore 通知等待的任务有中断事件发生。任务函数 vTaskFunction 通过等待信号量的方式实现对中断事件的处理。这种方式保证了中断处理的实时性，同时避免了在中断服务例程中直接调用 FreeRTOS API。

8.Linux处理中断

玩过 MCU 的人都知道，中断服务程序的设计最好是快速完成任务并退出，因为此刻系统处于被中断中。但是在 ISR 中又有一些必须完成的事情，比如：清中断标志，读/写数据，寄存器操作等。

在 Linux 中，同样也是这个要求，希望尽快的完成 ISR。但事与愿违，有些 ISR 中任务繁重，会消耗很多时间，导致响应速度变差。Linux 中针对这种情况，将中断分为了两部分：

1. 上半部（top half）：收到一个中断，立即执行，有严格的时间限制，只做一些必要的工作，比如：应答，复位等。这些工作都是在所有中断被禁止的情况下完成的。

2. 底半部（bottom half）：能够被推迟到后面完成的任务会在底半部进行。在适合的时机，下半部会被开中断执行。

上半部立即执行，下半部放在工作队列或者内核线程去处理。

9.freertos和linux怎么调度

freertos: 每个任务都有一个任务控制块(TCB)，当任务发生切换后，选择就绪任务列表里优先级最高的任务轮流执行。

任务在就绪状态下，每个优先级都有一个对应的列表，从就绪任务列表中高优先级列表往下找，找到第一个非空列表轮流执行里面的任务。

列表由列表头和列表项组成，列表头和列表项组成一个双向循环链表。

调度过程：在移植时，我们把系统时钟中断xPortSysTickHandler加入到了中断向量表，这个中断周期设置为1ms。这个中断是系统的核心，我们称作调度器，在这里会调用xTaskIncrementTick()把时间计数值加1，并检查有哪些延时任务到期了，将其从延时任务列表里移除并加入到就绪列表里。如果到期的任务优先级>=当前任务则开始一次任务切换。如果当前任务就绪态里有多个任务，也需要切换任务，优先级相同需要在一个系统时钟周期的时间片里轮流执行每个任务。另外在应用程序里也可以通过设置xYieldPending的值来通知调度器进行任务切换。

任务调度方式：

1. 抢占式：最高优先级的任务一旦就绪，总能得到CPU的执行权；它抢占了低优先级的运行机会。在抢占式调度系统中，总是运行最高优先级的任务。如果有好几个最高优先级的任务，则可以时间轮转调度。
2. 协作式：本质是任务运行一段时间放弃cpu运行权让其他任务运行，否则会一直占用cpu，其他任务无法执行。
3. 时间片轮转：让相同优先级的几个任务轮流运行，每个任务运行一个时间片，任务在时间片运行完之后，操作系统自动切换到下一个任务运行；在任务运行的时间片中，也可以提前让出CPU运行权，把它交给下一个任务运行。如果高优先级任务不阻塞，低优先级任务无法运行。

Linux调度

Linux把任务主要分为两类：

1. 实时任务：有很高的优先级需要尽快完成交付；
2. 普通任务：没有一定的实时性要求，尽快完成交付即可。

当系统中存在实时任务时，调度程序会优先选择实时任务执行，普通任务将得不到执行的机会。同时不同类型的任务有不同的调度策略。

在 CPU 的角度看进程行为的话，可以分为两类：

1. CPU 消耗型：此类进程就是一直占用 CPU 计算，CPU 利用率很高
2. IO 消耗型：此类进程会涉及到 IO，需要和用户交互，比如键盘输入，占用 CPU 不是很高，只需要 CPU 的一部分计算，大多数时间是在等待 IO

CFS是 Completely Fair Scheduler 简称，即完全公平调度器。CFS 调度器和以往的调度器不同之处在于没有固定时间片的概念，而是公平分配 CPU 使用的时间。比如：2个优先级相同的任务在一个 CPU 上运行，那么每个任务都将会分配一半的 CPU 运行时间，这就是要实现的公平。

但现实中，必然是有的任务优先级高，有的任务优先级低。CFS 调度器引入权重 weight 的概念，用 weight 代表任务的优先级，各个任务按照 weight 的比例分配 CPU 的时间。比如：2个任务A和B，A的权重是1024，B的权重是2048，则A占 1024/(1024+2048) = 33.3% 的 CPU 时间，B占 2048/(1024+2048)=66.7% 的 CPU 时间。

10. ARM(Advanced RISC Machines)处理器分类

目前，ARM处理器(内核)分为5类：Cortex-A、Cortex-R、Cortex-M、Machine Learning、SecurCore。前3种我们大部分人都听说过，见下图：

A系列主要用来跑Linux

M系列就是本科玩过的单片机，可以跑FreeRTOS：

1. STM32 F0xx系列（M0 48MHZ）
2. STM32 Lxxx系列(M3 32MHZ)
3. STM32 F1xx系列(M3 72MHZ)
4. STM32 F2xx系列(M3 120MHZ)
5. STM32 F3xx系列(M3 120MHZ)
6. STM32 F4xx系列(M4 168MHZ)

3单板相关

1.STM32启动方式：

1. 从Flash启动，将Flash地址0x0800 0000映射到0x00000000，这样启动以后就相当于从0x08000000开始的，这是我们最常用的模式；
2. 从SRAM启动，将SRAM地址0x20000000映射到0x00000000，这样启动以后就相当于从0x20000000开始的，用于调试，笔者基本没用过
3. 从系统存储器启动(System memory)，将系统存储器地址x1FFFF000映射到0x00000000，这样启动以后就相当于从0x1FFFF000开始执行的，值得注意的是这个系统存储器里面存储的其实是STM32自带的Bootloader代码，这其实是一个官方的IAP，它提供了可以通过UART1接口将用户的代码下载到Flash中的功能,然后将boot0置0，复位单片机，便可以Flash启动。

2.STM32上电到main函数之前做了什么事?

1. 初始化堆栈指针SP=_initial_sp，启动方式不同，指向地址不同。
2. 初始化PC（通用寄存器指针）指针=Reset_Handler，若果是Flash启动就是0x0800 0000。
3. SystemInit（配置系统时钟）
4. __main(MDK自带的函数)，初始化堆栈，.data .bss。
5. 最终调用main 函数去到C 的世界

3.IIC为什么要加上拉电阻，为什么使用开漏输出
上拉电阻原因

1. 当IIC总线在空闲状态，SDA和SCL需要处于高电平状态。
2. 开漏输出无法输出高电平，使用上拉电阻可以完成高低电平之间的转换。
   开漏输出原因
3. 假如使用推挽输出可能导致器件的烧毁
4. 实现线与功能

4. 进程的内存空间从低地址到高地址内存布局依次是：

保留区 –> 文本段（包含程序和字符串常量）–>初始化的变量(.data，包含全局变量和静态变量)—>未初始化的变量（.bss，包含全局变量和静态变量）—>堆—>共享库或mmap—>栈–>命令函参数(main函数的参数)–>环境变量—>内核空间

5. 推挽输出和开漏输出的区别：

推挽输出的最大特点是可以真正能真正的输出高电平和低电平，在两种电平下都具有驱动能力。常说的与推挽输出相对的就是开漏输出，对于开漏输出和推挽输出的区别最普遍的说法就是开漏输出无法真正输出高电平，即高电平时没有驱动能力，需要借助外部上拉电阻完成对外驱动。所谓的驱动能力，就是指输出电流的能力。

4.FreeRTOS

1. 创建任务函数：xTaskCreate();
2. 删除任务：vTaskDelete( NULL );传入NULL参数表示删除的是当前任务。
3. 启动调度器任务开始执行：vTaskStartScheduler();
4. 调度器启动之后修改任务优先级：vTaskPrioritySet();
5. 查询任务的优先级：uxTaskPriorityGet()
6. 任务挂起：vTaskSuspend()
7. 处于挂起状态的任务唤醒：vTaskResume()或vTaskResumeFromISR()
8. 任务的状态：运行态、阻塞态(正在等待某个事件)、挂起状态、就绪状态
9. 延迟使用函数：vTaskDelay(250 / portTICK_RATE_MS)进入阻塞态250ms
10. 空闲任务钩子函数：void vApplicationIdleHook( void )
11. 打印字符串和整型值：vPrintStringAndNumber()
12. 打印字符串：vPrintString( "hello world\r\n" );
13. FreeRTOS 中所有的通信与同步机制都是基于队列实现的。
14. 创建队列：xQueueCreate()返回一个 xQueueHandle 句柄以便于对其创建的队列进行引用。
15. 队列数据赋值：xQueueSendToBack()或xQueueSend()将数据发送到队列尾，xQueueSendToFront()将数据发送到队列首部。在中断中使用xQueueSendToFrontFromISR()与xQueueSendToBackFromISR()。
16. 读取队列中的值：xQueueReceive()用于从队列中接收(读取）数据单元。接收到的单元同时会从队列中删除。xQueuePeek()也是从从队列中接收数据单元，不同的是并不从队列中删出接收到的单元。在中断中使用xQueueReceiveFromISR()。
17. 查询队列中当前有效数据单元的个数：uxQueueMessagesWaiting()在中断服务中使用其中断安全版本 uxQueueMessagesWaitingFromISR()。
18. 马上切换至其他任务：taskYIELD();
19. 如果队列存储的数据单元尺寸较大，那最好是利用队列来传递数据的指针而不是对数据本身在队列上一字节一字节地拷贝进或拷贝出。
20. 只有以”FromISR”或”FROM_ISR”结束的 API 函数或宏才可以在中断服务例程中
21. 创建二值信号量：vSemaphoreCreateBinary()
22. 带阻塞时间的读取队列(信号量)：xSemaphoreTake()。不能在中断服务例程中调用。
23. 中断中放置令牌：xSemaphoreGiveFromISR()
24. __asm{ int 0x82 } 这条语句产生中断
25. 创建一个计数信号量：xSemaphoreCreateCounting()
26. taskENTER_CRITICAL()与taskEXIT_CRITICAL()之间称为临界区，临界区执行的内容不会切换到其他任务。
27. 挂起调度器：vTaskSuspendAll()可以停止上下文切换而不用关中断。
28. 唤醒调度器：xTaskResumeAll()
29. 创建互斥量：xSemaphoreCreateMutex()
30. 创建内存：pvPortMalloc()
31. 释放内存：vPortFree()
32. 查询指定任务的运行历史中，其栈空间还差多少就要溢出：uxTaskGetStackHighWaterMark()
33. 空闲任务钩子函数作用：执行低优先级，后台或需要不停处理的功能代码。测试处系统处理裕量。将处理器配置到低功耗模式。