fuRan's Code 皆無は真実、万事が許す。
Posts with the tag 数据结构:

实现一个红绿灯

 2022-01-12  2022-12-01  667 words  2 minutes  设计规划 数据结构 

前几天遇到一道有意思的题目。
大意是用 async 和 await 实现一个红绿灯。红灯停 5s、绿灯 10s、黄灯 3s。

扩展：支持手动切换当前灯的状态

【数据结构】链表(chain)学习笔记

 2020-11-21  2022-12-01  1618 words  4 minutes  数据结构 

简述

说链表我决定还是扯上数组一起,它们都是线性存储结构,区别在于数组在内存上是连续的,有序的.而链表则是通过节点内的指针指向下个节点,最后把所有节点串起来.就好比数组是长椅、链表是板凳;你开辟一个长度为5的数组好比搬了一个5人坐的长椅过来,1个人坐是占那么多空间, 5个人坐亦然;链表则是1个人坐就搬1个板凳,十分灵活. 且如果你现在中间插了一个人. 长椅组只能去找6人坐的新长椅了, 板凳组的只用再搬一个板凳就好了. 所以链表的插入成本是O(1).但是数组也有优势, 即通过标号搜索的成本是O(1),而链表需要从头(head)开始遍历,成本是O(n)

【数据结构】图(graph)学习笔记

 2020-11-18  2022-12-01  1060 words  3 minutes  数据结构 

简述

图是一种N对N的数据结构, 有有向图,加权图等等很多花样; 相关算法也很多除了常用的DFS、BFS, 还有什么A*、弗洛伊德算法、迪杰斯特拉算法;实现方法也有诸如接邻矩阵、接邻表、十字链表. 萌新泪目T^T.
下面是用十字链表实现的双向加权图, 只实现了BFS、DFS(backtrack),我也就算是入了个门, 挖了坑,以后学到了再填=- =

基础信息
寻路算法参考资料

【数据结构】堆(heap)学习笔记

 2020-11-18  2022-12-01  1033 words  3 minutes  数据结构 

简述

这里的堆都是二叉堆, 是一种优先队列(priority queue), 但他不是队列那种链式结构, 而是树型结构.
它满足以下两个性质

  1. 完全二叉树

在一颗二叉树中，若除最后一层外的其余层都是满的，并且最后一层要么是满的，要么在右边缺少连续若干节点，则此二叉树为完全二叉树（Complete Binary Tree）。具有n个节点的完全二叉树的深度为 \(\begin{matrix} log_{2}n+1 \end{matrix}\) 深度为k的完全二叉树，至少有 \(\begin{matrix} 2^{k-1} \end{matrix}\) 个节点，至多有 \(\begin{matrix} 2^{k}-1 \end{matrix}\) 个节点。

  1. 父节点大于(小于)子节点; 大于的是最大堆, 小于的是最小堆.

它和队列一样只有两个操作

  1. 插入(insert)
  2. 从头部移出一项(pop)

但在这两个操作之后,为了维持上述属性, 还会以下自处理

  1. 上浮(swim), 一般在插入(insert)后, 如果插入元素小于(最小堆)父元素, 交换其位置, 循环至满足性质;
  2. 下沉(sink), 一般在取走头(pop)后, 用末尾元素填充头部, 如果填充元素大于(最小堆)子元素, 交换其位置,循环至满足性质;

【数据结构】栈(stack)学习笔记

 2020-11-18  2022-12-01  303 words  1 minute  数据结构 

简述

栈也是一种线性存储结构, 但它只能从栈顶压入, 栈顶弹出数据, 也就是后进先出LIFO(Last In First Out).请和队列(Queue)区分开.

【数据结构】队列(queue)学习笔记

 2020-11-18  2022-12-01  293 words  1 minute  数据结构 

简述

队列也是一种线性存储结构, 但它只能从队尾添加数据, 队头取出数据, 也就是先进先出FIFO(First In First Out). 请和栈(Stack)区分开.

【数据结构】红黑树学习笔记

 2020-11-09  2022-12-01  4619 words  10 minutes  数据结构 

参考资料

维基(中文)
维基(英文)
算法导论(第三版)第13章
删除理解1 删除理解2

简述

红黑树(RBT)是一种自平衡的二叉搜索树(BST), 首先看BST的定义

二叉查找树，也称有序二叉树（ordered binary tree），或已排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

  • 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 任意节点的左、右子树也分别为二叉查找树。
  • 没有键值相等的节点（no duplicate nodes）。

如图

graph TD ROOT((1000)) --> A((100)) ROOT((1000)) --> B((10000)) A --> A1((10)) A --> A2((500)) B --> B1((5000)) B --> B2((100000))

在这些基础上再加上以下五条性质

  1. 每个结点要么是红的要么是黑的。
  2. 根结点是黑的。
  3. 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
  4. 如果一个结点是红的，那么它的两个儿子都是黑的。
  5. 对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。
graph TD ROOT((10)) --> A((5)) ROOT((10)) --> B((15)) A --> A1((3)) A --> A2((7)) B --> B1((13)) B --> B2((20)) A1 --> A11((1)) A1 --> A12[NIL] A2 --> A21[NIL] A2 --> A22[NIL] B1 --> B11[NIL] B1 --> B12[NIL] B2 --> B21((18)) B2 --> B22((25)) style ROOT fill: black,color:white style A1 fill: black,color:white style A12 fill: black,color:white style A2 fill: black,color:white style A21 fill: black,color:white style A22 fill: black,color:white style B1 fill: black,color:white style B11 fill: black,color:white style B12 fill: black,color:white style B2 fill: black,color:white style A fill: red,color:black style A11 fill: red,color:black style B fill: red,color:black style B21 fill: red,color:black style B22 fill: red,color:black

最下面应试还有一层叶子节点(nil), mermaid毕竟是画流程图的, 画树还是有点勉强