【数据结构】Btree家族
BtreeBtree 介绍
Btree 是一种多路搜索树,每个节点可以存储多个元素,每个元素可以有多个子节点。
对于一棵M阶的B树,每个节点最多有M个子节点,最少有⌈M/2⌉个子节点(⌈x⌉为向上取整符号);最多有M-1个元素,最少有⌈M/2⌉-1个元素。(B+树也是一样)
2-3树是一种特殊的 btree,2-3树的阶数为 3,每个节点最多有 2 个元素,最多有 3 个子节点。(其中“2-3”代表的是该树允许的子节点个数范围)
同样地,对于一棵4阶的2-3-4树,每个节点最多有4个子节点,最多有3个元素。每个节点最少有2个子节点,最少有1个元素。Btree 特性1.关键字集合分布在整颗树中;
2.任何一个关键字出现且只出现在一个结点中;
3.搜索有可能在非叶子结点结束;
4.其搜索性能等价于在关键字全集内做一次二分查找;
Btree 的插入
插入的时候,先找到插入的位置,然后插入到叶子节点中。
如果插入之后,叶子节点的元素个数大于 m,那么就需要进行分裂操作。
分裂操作:将叶子节点的元素分成两部分,左边的元素个数为 (m+1)/2,右边的元素个数为 m-(m+1)/2,然后将左边的 ...
vscode使用小tips
Q1:多开vscode进程的时候,md文件的预览会失败,报错:Error loading webview: Error: Could not register service worker: InvalidStateError: Failed to register a ServiceWorker: The document is in an invalid state..
解决方法:只留下一个进程,删掉其他的进程,然后重启vscode,再打开md文件,就可以正常预览了。不过不知道有没有更好的解决方法。
【数据结构】备考
题型选择题填空题解答题设计题25分往年例题
判断连通分量的数量In 2022, the Scheol of Sofware Engmneering las enrolled N fesmen. After a Icwmncnths, some are fiends and some are not Their tnendship is transitive.1f wknow tiat A is a flond of B and B is a fnend ot e then we can consider that A islso a triend of Csayig tha A B imd C form circle of friends. Plse use yourimowledge of dafa structure to compute the total nnmber of cireles of fends in1he fTesltnen(a) What kind of datu structire will you design for the computation? E ...
2023国赛经历总结和复盘
戏剧性的三天先吐槽一下:暴雨开局/80w个数据/Excel民工/word指挥官/盒子空间/透明厕所玻璃/无门浴室/熬大夜之后直接回校跑了个1km,跑完回去接着干活/极限提交操作/结题夜宵喝了两杯,烧烤甚至忘记还钱了!
是全力以赴、团结协作、恣意享受的三天半。
复盘选题第一天晚上六点准时开始看题,一开始大概看了三道题,觉得A、B都有比较浓厚的物理建模的成分,C题看起来很常规,我们也很有把握,觉得如果选了C题不管怎么样肯定能做做完,而且会有很多人选,很难获奖。于是我们大概拉了一遍流程之后(直到这里也没觉得C有什么问题)就去看A题了。A题不仅题目里给出了很多参考文献,在知网上也能找到很多相关的论文,特别是兰州交通大学的学位论文。在读论文的过程中我也发现了一个开源的仿真软件能够导入坐标、模拟出定日镜场的模型。看起来非常酷炫,感觉图像这一块是稳了(因为先前物理背景的题比较担心的是一些物理的专业图形规范作图)。于是我们开始八点左右到快十点,三个人开始研究A题怎么做。可惜最后我们没能研究出各种阴影遮挡的处理方法,解决不了这个问题,A题最基本的物理模型就无法建立起来。按照时间安排,第一天晚上睡觉前必须 ...
【数据结构】AVL树+splay树
AVL树前置知识
二叉排序树:左子树的所有节点都小于根节点,右子树的所有节点都大于根节点
平衡二叉树:左右子树的高度差不超过1的二叉排序树
二叉树的高度:根节点到叶子节点的最长路径
二叉树的深度:根节点到叶子节点的最短路径
二叉树的平衡因子:左子树的高度减去右子树的高度
AVL树的定义
AVL树是一棵空树或者它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树的二叉排序树。
AVL树的调整
LL型单旋:右旋
RR型单旋:左旋
LR型双旋:先左旋再右旋
RL型双旋:先右旋再左旋
tips:旋转之后,根节点的平衡因子为0,左右子树的平衡因子为1或者-1
图解:AVL树的插入按照常规的二叉排序树的插入方法插入节点,然后从插入节点开始向上回溯,找到第一个平衡因子的绝对值大于1的节点,然后根据该节点的平衡因子和插入节点的值的大小关系,进行旋转操作。
AVL树的删除如果删除的节点是叶子节点,直接删除即可。如果删除的节点不是叶子节点,那么需要找到该节点的前驱或者后继节点来替换该节点,然后删除前驱或者后继节点。删除之后,从删除节点的父节点开始向上回溯,找到第一个平衡因子的 ...
【设计模式】obbserver in MVC
MVC和Observer的联系MVC是软件架构,Observer是设计模式,是不同层面的东西,不能直接比较异同
MVC本质上是解耦,让UI和逻辑,数据分离。一旦应用,基本上整个项目都要遵从这种模式。
Observer是一种传递消息的机制,特点是被观察者不需要知道观察者是谁,降低了耦合。这是一种模式,三两个class就可以实现,对网站构架没有影响。
如果硬要说联系,Observer模式经常被应用在MVC架构中,作为一种消息处理的机制。
observer模式观察者模式也称作监听模式,即观察与被观察的关系,比如你在烧开水时看它有没有开,你就是观察者,水就是被观察者。观察者模式是指对象之间一对多的依赖关系,每当那个特定对象改变状态时,所有依赖于它的对象都会得到通知并被自动更新。
cs61b sp21 proj0 2048 中的MVC和observerMVC
The MVC pattern divides our problem into three parts:
The model represents the subject matter being represented and act ...
【影评】《Oppenheimer》(奥本海默)
इदानीं अहं क्रूरः कटनकर्ता, जगतः नाशकः भवेयम्।
“我现在成了死神,世界的毁灭者。”
——《薄伽梵歌》
壹先说结论,个人觉得值得一看,无论是对冲着诺兰导演还是奥本海默传记或者是电影体验来的(看各人口味)。但是有点门槛:时长考验膀胱,音量考验耳膜,时间线考验理解。影片的剧情稍微了解二战历史或者是学过高中历史的应该都能看懂大概,但是如果对这块历史很有了解的应该看起来会更舒服。
电影的时长长达三个小时,虽然时间较长,但节奏紧凑。
影片基于真实历史背景,对于对物理学和二战历史政治感兴趣的观众来说将是一场盛宴。
剧情从中间开始,时间线分裂且跳跃,虽然不影响整体理解,但完全理解所有细节可能有一定难度。
演员阵容堪称豪华,演技也确实无可挑剔
人物和人名很多,再加上我有一点脸盲,看完一整部除了戏份特别多或者特别好认的角色,还有很多不知道哪里冒出来的名字/有印象叫不出名字的,但是不影响整体的理解。
全片无特效(除了为了引进大陆特殊处理过的桥段,那就挺明显的),全部实景搭建和拍摄。关于具体以及一些其他方面技术相关的消息,最近网上有很多采访诺兰的视频,可以 ...
JAVA语言程序设计基础
overvew教材:《java 语言程序设计》参考书目:如下图
lab
lab1:java command line environment
lab2:bank project 1
lab3:bank project 2
lab4:GUI教学内容:1~5 章Java特性
oriented object
distributed
simple
multi-threaded
multi-thread
secure
platform-independent(软硬件平台)一次编译,到处运行关键terms解释
JVM:Java Visual Machine
hotspot?
HotSpot 是一种 Java 虚拟机(Java Virtual Machine,JVM)的实现,它是由 Oracle(以前是 Sun Microsystems)开发的,并且在 Java 开发和运行时环境中广泛使用。HotSpot JVM 被认为是一种高性能的 JVM 实现,它主要关注在执行 Java 代码时的运行时性能优化。
以下是一些 HotSpot JVM 的关键特点和功能:
即时编译(Just-In-Time C ...