Posts

基本概念 1.结点的权 每个结点带有的具有某种现实意义的数值(比如代表重要性等) 2.结点的带权路径长度 从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积 3.树的带权路径长度 树中所有叶结点的带权路径长度之和（WPL, Weighted Path Length） $WPL=\sum_{i=1}^{n}w_il_i$ ✨4.哈夫曼树 在含有n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树 构造哈夫曼树 给定n个权值分别为 $w_1,w_2,…,w_n$ 的结点，其构造过程描述如下： ① 将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F ② 构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。 ③ 从F中删除刚才选出的两棵树，同时将新得到的树加入F中。 ④ 重复步骤②和③，直至F中只剩下一棵树为止。 假设给定结点在经过步骤①之后如下 则其②③④步骤为： $WPL_{min}=1*7+2*3+3*2+4*1+4*2=31$ 或者 $WPL_{min}=1*7+3*(1+2+2+3)=31$ 👇👇👇👇👇👇 哈夫曼树特点： ① 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。 ② 哈夫曼树的结点总数为2n-1。 ③ 哈夫曼树中不存在度为1的结点。 ④ 哈夫曼树并不唯一，但WPL必然相同且为最优。 哈夫曼编码 固定长度编码 如ASCII码 可变长度编码 前缀编码 没有一个编码是另一个编码的前缀 哈夫曼编码 由哈夫曼树得到哈夫曼编码——字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，根据之前介绍的方法构造哈夫曼树。 ✨ 应用 可用于数据压缩 如图，为英文字母使用频率表，若不进行压缩，第 i 个字母频率用$l_i表示$，路径长至少为5($2^4<26<2^5$)，则 $WPL=5×\sum_{i=1}^{n}l_i$=500 若通过构造哈夫曼树进行哈夫曼编码 则$WPL_{min}=$ $v=\frac{WPL_{min}}{WPL}$

普通树 对于一棵普通类型的树形结构，可将其转化为二叉树之后再参考二叉树的方法进行相关操作。 孩子兄弟表示法（链式结构） 通过此方法可将普通树转化为二叉树 1 2 3 4 5 //孩子兄弟即Child, Sibling typedef struct CSNode{ Elemtype data; struct CSNode *firstchild,*nextsibling;//第一个孩子和右兄弟指针,等价于*lchild,*rchild }CSNode,*CSTree 图示如下 树的遍历 1.深度优先遍历（先根遍历&后根遍历） 先根遍历 若树非空，先访问根结点，再依次对每棵子树进行先根遍历(递归)。 对如上图所示的树进行先根遍历： A B C D A (BE ) (CF) (DG) A (BEH) (CF) (DG) 即先根遍历序列为A B E H C F D G 发现与通过“孩子兄弟法”将树转为二叉树后的先序遍历序列相同 后根遍历 若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点。 对如上图所示的树进行后根遍历： B C D A (E B) (F C) (G D) A...

线索二叉树 WHY 方便从任一个结点出发，找到其前驱、后继；方便遍历 普通二叉树中，对任意一个结点，若想找到其前驱/后继结点，只能再进行一次相应的前/中/后序遍历才行，复杂度太高。 为此，我们引入前驱线索，后继线索的概念。其中，前驱线索由左孩子指针充当，后继线索由右孩子指针充当。 1 2 3 4 typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; 构建出如下图所示的结构： 但是， *lchild(*rchild)有可能指向存在的结点，为此我们引入线索标志。当线索标志为1时，表示孩子指针指向前驱后继，线索标志为0时，表示孩子指针指向左右孩子。此时 1 2 3 4 5 typedef struct ThreadNode{ ElemType data; struct ThreadNode *lchild,*rchild; int ltag,rtag;//左右线索标志 }ThreadNode,*ThreadTree; 这样，每一个线索链表中的结点就可以图示为: HOW 如何分别用代码实现前中后序遍历下的线索链表 1.中序线索化 其实中序线索化的过程就是再进行一遍中序遍历，为每个节点添加额外的信息(lchild, rcild, ltag, rtag). 🍔初始定义结构体 1 2 3 4 5 typedef struct ThreadNode{ ElemType data; struct ThreadNode *lchild,*rchild; int ltag,rtag; }ThreadNode,*ThreadTree; 🍔定义前驱指针...

由遍历序列构造出二叉树 仅知道一种遍历序列是无法确定唯一的二叉树的，以中序遍历为例，对于一个中序遍历序列“BDCAE”，其对应的树形结构可能有下面三种： 因此，至少需要两种遍历序列才可以推知树形结构。 1.前序+中序遍历序列 🎈基本步骤 由前序遍历的特性得知，前序遍历中第一个节点必然为根节点，因此根据中序遍历特性，根节点左边为左子树下的所有节点，右边为右子树下的所有节点，然后分别在左子树序列右子树序列中重复进行即可。 🎈示例 前序遍历序列：A D B C E 中序遍历序列：B D C A E 首先能确定根节点为A，根据中序遍历序列可以得到： 对于左子树BDC，根据前序遍历，此子树根节点为D，根据中序遍历序列： image-20210508165242806 至此，二叉树的还原工作就完成了！至于更复杂的序列，逐步推断即可😋 2.后序+中序遍历序列 🔑与1不用的是，后序遍历中根节点为后序遍历序列尾部的那个节点，其余参照1即可！ 3.层序遍历+中序遍历 🔑 根据层序遍历特性，层序遍历中根节点始终在子树前面，“根左右” 🎈示例 层序遍历序列：A D E B C 中序遍历序列：B D C A E 根节点为A，根据中序遍历序列可以得到： 对于左子树BDC，根据前序遍历，此子树根节点为D，根据中序遍历序列： 思考 如果前序，后续，层序两两组合能否确定唯一的树结构？ 假设给定序列如下： 前序：A B 后序：B A 层序：A B 其两两组合都满足两种结构： 因此前序，后续，层序两两组合不能确定唯一的树结构。

向量的空间管理，有静态和动态两种策略 静态空间管理策略 开辟内部数组_elem[]并使用一段地址连续的物理空间，_capacity表示总容量 ，_size表示当前的实际规模n，示意图如下： 若采用静态空间管理策略，容量_capacity固定，则有明显的不足… 上溢/overflow： _elem[]不足以存放所有元素，尽管此时系统往往仍有足够的空间 下溢/underflow： _elem[]中的元素寥寥无几，装填因子 λ = _size / _capacity « 50% 动态空间管理策略 在即将上溢时，适当扩大内部数组的容量 递增策略 当需要扩容时，为_capacity追加固定大小的空间，即 1 T* oldElem = _elem; _elem = new T[ _capacity += INCREMENT ]; 考虑最坏情况，在初始容量为0的空向量中连续插入n = m*I个元素 那么，在第1，I+1，2I+1，3I+1…次插入元素时都需要扩容，表示为 递增策略 倍增策略 当需要扩容时，增加_capacity 为原来的两倍，即 1 T* oldElem = _elem; _elem = new T[ _capacity <<= 1 ]; 考虑最坏情况，在初始容量为1的空向量中连续插入n = 2^m个元素 那么，在第1，2，4，8…次插入元素时都需要扩容，表示为 倍增策略 两种策略的复杂度分析 考虑最坏的情况，两种策略的复杂度分别为...

减而治之(Decrease and conquer) 什么是“减而治之”？ 为求解一个大规模的问题，可以将其划分为两个问题，其一平凡，另一规模缩减 ，分别求解子问题，由子问题的解得原问题的解 减而制之 比如说，对于一个数组A的求和问题，可以设计如下的算法 1 2 3 4 5 sum( int A[], int n ) { return n < 1? 0 : sum(A, n - 1) + A[n - 1]; } 当规模缩减到一定程度后，抵达递归基，返回0 复杂度分析 1. 递归跟踪 绘出计算过程中出现过的所有递归实例（及其调用关系） ，那么它们各自所需时间之总和，即为整体运行时间 上例中，共计n+1个递归实例(分析)，各自只需O(1)时间 故总体运行时间为： T(n) =O(1) × (n+1) =O(n) 2.递推方程 对于大规模的问题、复杂的递归算法，递归跟踪不再适用 此时可采用另一抽象的方法… 在本例中，有T(n)=T(n-1) + O(1),T(0)=O(1) 则，T(n) = T(n-2)+O(2) = T(n-3)+O(3) = T(n-n)+O(n)=O(n)...

导论 所谓算法，即特定计算模型下，旨在解决特定问题的指令序列。输入：待处理的信息（问题）输出：经处理的信息（答案） 正确性 的确可以解决指定的问题 确定性 任一算法都可以描述为一个由基本操作组成的序列 可行性 每一基本操作都可实现，且在常数时间内完成 有穷性 对于任何输入，经有穷次基本操作，都可以得到输出 ::: tip Algorithms + Data Structures = Programs (Algorithms + Data Structures) x Efficiency = Computation ::: 如何评判算法的其优劣(计算模型) 实验统计是最直接的方法，但足以准确反映算法的真正效率？不足够！ - 不同的算法，可能更适应于不同规模的输入 - 不同的算法，可能更适应于不同类型的输入 - 同一算法，可能由不同程序员、用不同程序语言、经不同编译器生成 - 同一算法，可能实现并运行于不同的体系结构、操作系统… 为给出客观的评判，需要抽象出一个理想的平台或模型 - 不再依赖于上述种种具体的因素 - 从而直接而准确地描述、测量并评价算法 1.图灵机模型(TM) 示意图 组成 说明 Tape 依次均匀地划分为单元格 各存有某一字符，初始均为'#' Head 总是对准某一单元格，并可 读取或改写其中的字符。每经过一个节拍，可 转向左侧或右侧的邻格 Alphabet 字符的种类有限 State TM总是处于有限种状态中的某一种 。每经过一个节拍 可按照规则转向另一种状态 。统一约定，‘h’ = halt(停止) 2....

基本语法 输出语句 语句 功能 echo 输出字符串类型 print_r 输出引用类型(对象,数组等) var_dunp 检测变量类型 ::: tip echo语句可用于给前端返回响应体。比如前端通过ajax请求，可以在xhr.response中直接得到echo的内容 ::: 变量&常量 👉🏼 变量 语句 功能 返回值 isset() 检测变量是否存在 boolean unset() 删除某个变量 none 👉🏼 常量 常量用const 或 define 定义，常量名一般全部大写，不受作用域的限制 ::: tip 一般是define在类外定义常量，const在类内定义常量，并且const必须通过类名::变量名来进行访问。但是php5.3以上支持类外通过const定义常量。 ::: :::danger const不能在条件语句中使用，必出错 ::: 参考文章 《PHP中define() 与 const定义常量的区别详解》...

利用php中的GD库可以完成验证码类的开发。后盾人教程 PHP创建图像步骤 发送HTTP头信息，声明内容为图像 1 2 3 header('Content-type:image/gif'); header('Content-type:image/jpeg'); header('Content-type:image/png'); 通过设置头信息让浏览器渲染出图像，而不是HTML等其他类型 创建画布 1 imageCreateTrueColor(width,height); width & height 画布宽高，即为输出图片的尺寸,返回为source 类型，后续操作都是针对这个资源展开。 创建绘图所需要的颜色 1 imageColorAllocate(img_resource,R,G,B); 颜色从属于创建画布产生的图像资源而存在，后面三个值分别为红绿蓝三个通道的值，为int类型,在0—255之间。 绘图（填充画布、画圆、画方块、画线条、画布上写字） 👉 填充画布(画布背景) 1 imageFill(img_resource,x,y,color); 👉 画圆 1 2 3 4 //绘制空心圆形 imageEllipse(img_res,x,y,w,h,color); //绘制填充好的实心圆 imageFilledEllipse(img_res,x,y,w,h,color); 绘制 圆心(x,y) 宽 x，高 h，的圆 👉 画方 1 2 3 4 //空心矩形 imageRectangle(img_res,x1,y1,x2,y2,color); //实心矩形 imageFilledRectangle (img_res,x1,y1,x2,y2,color); (x1,y1)为左上角坐标， (x2,y2)为右下角坐标...

基本命令 1 2 3 4 5 6 7 8 git config --global #全局配置 git config #当前仓库配置 mkdir #创建文件夹 ls #列出当前目录下(文件，文件夹) ls -a #所有all rm -rf * #删除当前目录下所有 touch #新建文件 cat #查看文件中的内容 不想`git add . 所有？ 配置.gitignore 定义忽略提交的文件，其中 所有空行或者以注释符号 ＃ 开头的行都会被 Git 忽略。 匹配模式最后跟反斜杠（/）说明要忽略的是目录。 可以使用标准的 glob 模式(php)匹配。 从版本库删除 1 2 git rm ... #从版本库中删除，本地也会删除 git rm --cached ... #只从版本库删除 从版本库改名 1 git mv ....