AVL 平衡二叉树最近在写一个数据库引擎，需要学习一下 B-TREE 的知识，我一看，之前学习数据结构的时候才学习到 AVL 树，这可不行，得加紧学习了，所以今天的任务就是将AVL树弄明白。 ADT平衡二叉树AVLTree和二叉查找树BSTree差不多，只不过平衡二叉树需要保持平衡，即每一个节点的左右两颗子树的高度小于等于1.这样就使得二叉搜索树保持最好的状态，不至于陷入链表的境地。 平衡二叉树的要点在于怎样保持平衡。要解决这个问题首先要搞清楚不平衡的集中条件。 平衡二叉树的失衡姿态。对二叉树的描述我就使用插入顺序来描述了。 LL、RR、LR、RL B1: 失衡结点B2：失衡因节点，因为这个结点才失衡的。B3：失衡因节点的一个祖宗&&失衡结点的一个孙子。 即寻找B3，既是B2的祖宗（自己可以是自己的祖宗），也是B1的孙子。 然后判断B3是B1的哪一个孙子即可得知是哪种情况。 这样直接判断可行性较低，除非在插入的时候明确知道失衡因子。 要想避开寻找失衡因子，可以从失衡结点向下判断两颗高度最大的子树，由这个方向来判断失衡姿态。 但是这样仍有一个问题就是这种情况： 8，4，2 ...

Btree终于学完了AVL树，现在开始学习BTree，为数据库做准备。 参考资料 https://segmentfault.com/a/1190000020416577 BTree的定义阶数M，每个结点所能够包含的关键数的数目有一个上下界，用M来限定。M>=2 也成为Btree的最小度数 min: 每一个非根节点至少由M-1个关键字，每一个非根内节点至少有M个子女，如果树非空，则根节点至少包含一个关键字。 max: 每个结点最多包含2M-1个关键字，所以一个内节点最多有2M个子女，如果一个结点恰好有2M-1个关键字则称其为满的。 M=2的Btree是最简单的，这时一个内结点可以包含2-3-4个子女，称为一颗2-3-4树，但是在实际使用中常常使用大得多的M值。 BTree要求每一个内节点至少是半满。 在数据结构课本中以及考研中对Btree的定义和算法导论中的定义有些许不同，如下： 阶数M为非根结点孩子的最大值而不是算法导论中的非根节点孩子的最小值。我不喜欢课本和考研，所以我推崇算法导论的定义。以下实现都是基于算法导论的定义。 树中每一个结点至多含有m颗子树，至少含有m/2向上取 ...

CDB我想学习数据结构，最好的方式就是使用数据结构的知识做出一个系统，而我认为对于目前的我来讲，最好的选择就是做一个小型的数据库引擎。取名为CDB 学习GitHub上的这个项目。 必要技术准备 windows下文件的交互。参考CRT,微软的这个官方文档真好。 测试技术，这个在json教程中已经学习过。 层次架构，学会对一个项目使用层次架构进行开发。 命令处理，或者说是解析器，即解析命令。 数据库底层数据结构的实现，这里采用B树。 c语言底层内存管理。 对操作系统底层的了解，比如数据库利用操作系统的分页概念进行优化。 第一步 数据库的交互框架数据库工作的流程为： 1. 打印提示符接受输入 2. 解析输入，得到真实的命令 3. 将解析得到的语义进行数据库底层操作 4. 数据库底层操作很复杂，现在还不懂，懂了再加上 所以首先我们需要解析每一次的输入，并解析为程序可以读懂的信息，根据解析结果进行进一步操作。 所以我们需要一个缓冲区来存储输入。 123456typedef struct{ char* buffer; size_t buffer_le ...

贪吃蛇结题报告代码 题目意义这次微机实验，我们选择的题目是贪吃蛇街机小游戏。简单来讲就是使用微机试验台上的led点阵作为显示屏，配合计数操作显示得分情况，利用键盘进行IO操作的贪吃蛇小游戏。之所以选择这个题目是因为我想在有限的实验条件上极可能的做出一个比较有趣的项目。由此可见，此题目的意义就是探求自己在简陋的实验环境中做出复杂工程的能力，同时也是在检验自己在微机课程中所学到的知识是否扎实。 设计思想 图像显示 使用led点阵将贪吃蛇的位置和食物的位置显示出来，首先我们必须提供一个底层的方法来方便地将led灯进行点亮，这就促使我们引入了缓存地概念（下面再说）和一个读取缓存地内容进行点亮灯的方法。 图像显示的缓存 为了方便的进行led的显示，我门引入了缓存的概念，即将要显示的led点阵的信息以比特的形式存储在内存中，命名为red_buffer和green_buffer 图像操控 为了方便的修改缓存中的信息，我们实现了一个函数将特定位置的额灯的颜色置红，值绿或者置暗。 中断 使用8253产生定时中断为系统提供时间基准。 IO输入 由中断驱动进行IO操作，将键盘等的输入存入内存。 时分复用 由 ...

双创工作日志1工作内容确定要做的项目的大概方向。 存在问题及解决办法暂时只知道要去找做一个项目，具体要做什么还不是很清楚。还要再看看资料多了解一下前沿知识。 体会和建议学海无涯，想要做出一点厉害的东西只有好好学习。 2工作内容确定了项目的大概方向是做一个3D方向的软件。 存在问题及解决办法只是直到项目大概要做一个3D方向的软件，至于真正的要做出来什么还不确定。 体会和建议要好好学习，多学习一些技术才能在要做事情的时候不至于只知道做什么。 3工作内容查阅大量资料，了解有关3D的知识，直到制作一个3D场景的途径和相关知识。 存在问题及解决办法虽然知道了有关3D的相关知识，涉及到了有关3D的一些领域。但是对于真正的使用3D知识做出来一些东西还是没有什么确切的了解。需要继续学习。 体会和建议永远都到学习，只有学习的东西足够的多才能直到自己可以做出什么。 4工作内容了解有关3D图像学的知识，知道了图形学的集大成者，游戏引擎。于是确定目标要做一个游戏引擎。 存在问题及解决办法虽然确定了目标是做出一个游戏引擎，但是对于相关领域的知识还是知之甚少。需要继续学习。 体会和建议确定了目标说明对一件事情的了 ...

CMmake简介简单来讲，cmake是一个跨平台的makefile生成器。大型项目的额makefile实在是太繁琐了。学习cmake就是在学习其语法。一般来讲，只有在使用c/c++做一个大项目的时候才用得到cmake 基本命令简介project1PROJECT(<projectname> [CXX] [C] [Java]) 指定生成项目的名字，可选项目语言（默认位全选）同时 cmake 系统也帮助我们预定义了PROJECT_BINARY_DIR 指向生成的项目的路径（build） 和PROJECT_SOURCE_DIR 指向项目源文件的路径(source) MESSAGE1MESSAGE([SEND_ERROR | STATUS | FATAL_ERROR] "message to display") 这个指令用于向终端输出用户定义的信息，包含了三种类型: SEND_ERROR，产生错误，生成过程被跳过。 SATUS，输出前缀为—的信息。 FATAL_ERROR，立即终止所有 cmake 过程. 1MESSAGE(STATUS "bu ...

opencv 1 配置环境与图像的基本操作最近习惯使用vscode作为主力编辑器，所以这次学习opencv也是用vscode，顺便学习以下python。 我的环境是： 12python 3.9.6opencv 配置环境 python.org安装python 配置环境变量，maybe已自动配置 1pip install opencv-python vscode安装python的扩展 运行代码。右键选择在python终端中执行代码。 注意vscode的路径问题。当前路径是pwd所展示的，和文件的具体位置无关。这个问题在昨天在vs上面写XYY_Game_Engine时也遇到了，注意路径问题，关键时找到pwd到底是什么。对于vs来说是main在的路径，对于命令行来讲是pwd。 shift -f vscode, 还是直接使用pycharm吧，就是jetbrains家的ide太难看了。 opencv 图像基本操作

XYY Game Engine 封装和使用c++封装将c++项目封装为一个动态链接库，向外只提供接口，这样不仅仅方便发行，更可以加快成程序运行的速度。将XYY项目封装的步骤如下： 将所有的声明定义为导出，以类作为示范。 即将 1234567class XYY_GlobalDriver : public XYY_Driver{ public: int tag; void init(); // 初始化 void run(XYY_SceneContent * sc); // 运行}; 更改为 1234567class __declspec(dllexport) XYY_GlobalDriver : public XYY_Driver{ public: int tag; void init(); // 初始化 void run(XYY_SceneContent * sc); // 运行}; 删除main函数，并写以下两个文件 12345//XYY_Game_Engin ...

开题报告项目介绍贪吃蛇街机小游戏是一款在8*8的LED显示灯上运行的贪吃蛇小游戏，通过红外线遥控器输入设备进行游戏控制，在LED显示灯上显示游戏画面，使用数码管显示当前得分，使用灯光和蜂鸣器营造游戏氛围。 功能模块划分 游戏整体逻辑控制模块 整个项目的入口，控制其他各个模块的调度。 贪吃蛇逻辑控制模块 贪吃蛇运行逻辑的控制，负责计算出下一秒贪吃蛇的状态（移动、增长、死亡）、食物位置的刷新、当前得分的计算等。 LED显示控制模块 将内容（游戏菜单、当前画面、）显示到8*8的LED灯上。 全局时钟控制模块 通过8253每10ms产生一个中断，用于控制游戏进程的同步。 声音控制模块 使用蜂鸣器产生游戏音效与背景音乐。 灯光控制模块 使用LED灯产生一些光效。 数码管显示模块 使用数码管显示出当前游戏的得分。 红外线输入模块 使用红外线输入，产生中断，控制贪吃蛇的运动。 核心功能代码测试123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495 ...

微机与汇编接口实验暑假小学期让做一个有关微机的小项目，看来也是为以后做嵌入式开发做准备。 设计设计思路设想的是使用led点阵做一个小型的贪吃蛇游戏，并且可以使用红外遥控器进行操控，并且配合实时的灯光和音效展现出一种复古的街机氛围。设计项目要抓住项目的主要矛盾，做贪吃蛇就是做贪吃蛇，专心地先做出来贪吃蛇再想别的。 首先必须可以实时的控制led点阵，led点阵可以显示红绿两种颜色，将led点阵存放在red_buffer、green_buffer中，他们都是一个8字节地缓冲区，每一个字节存放了每一列中各行地明亮情况。下面说明一下程序的生命周期：程序开始运行，主菜单显示退出程序和开始贪吃蛇游戏，选择退出程序则退出程序，选择开始贪吃蛇游戏则开始贪吃蛇游戏。进入贪吃蛇游戏之后在led点阵上显示出图像，使用遥控器控制贪吃蛇进行移动吃食物，若撞到墙则从另一边出来，若撞到自己则失败回到主菜单。在游戏过程中实时播放音效和数码管计分。 功能设计 程序开始时展现出一个菜单，菜单分为： 退出程序 开始贪吃蛇游戏 贪吃蛇程序开始运行，在led点阵上面实时地显示。 使用数码管显示当前得分 在 ...

二叉查找树二叉查找树是一个有序的树，使用二叉查找树可以极大的方便查找排好序的元素 二叉查找树保证其中每一个结点的右子树都比他大，左子树都比他小，即左小右大。设x为二叉查找树中的一个结点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个结点，则key[y] <= key[x]；如果y是x的右子树的一个结点，则key[y] >= key[x]。 前驱 在中序遍历中排在某元素前面的那个元素是该元素的前驱，当然第一个元素是没有前驱的。在数组型的二叉树中，前驱就放在其前面。寻找前驱的算法如下： 1. 若一个结点有左子树，则左子树的最右侧即为所求前驱。（也就是左边的最大值） 2. 若没有左子树，则从这个结点向上遍历，直到找到某个结点是其父节点的右子树，则这个结点的父节点即为所求。所不存在则说明没有前驱。 后继 在中序遍历中排在某元素后面的那个元素是该元素的后继，当然最后一个元素是没有后继的。在数组型的二叉树中，后继就放在其后面。寻找后继的算法如下： 1. 若一个结点有右子树，则右子树的最左侧即为所求前驱。（也就是右边的最小值） ...

C内存管理内存管理函数 void *malloc(int num); 在堆区分配一块指定大小的内存空间，用来存放数据。这块内存空间在函数执行完成后不会被初始化，它们的值是未知的。 void *calloc(int num, int size); 在内存中动态地分配 num 个长度为 size 的连续空间，并将每一个字节都初始化为 0。所以它的结果是分配了 num*size 个字节长度的内存空间，并且每个字节的值都是0。 void *realloc(void *address, int newsize); 该函数重新分配内存，把内存扩展到 newsize。 void free(void *address); 该函数释放 address 所指向的内存块,释放的是动态分配的内存空间。 关于 realloc 的坑1、realloc失败的时候，返回NULL 2、realloc失败的时候，原来的内存不改变，不会释放也不会移动 3、假如原来的内存后面还有足够多剩余内存的话，realloc的内存=原来的内存+剩余内存,realloc还是返回原来内存的地址; 假如原 ...