数据结构与算法

共 8 篇笔记

跳表(Skip List)

关键思想:跳表由多层链表组成。每个节点在第 i 层有一个 forward[i] 指针,指向该层的下一个节点;为了支持排名(rank)/区间计数,我们在每层维护一个 span[i] —— 从当前节点走 forward[i]…

哈希

哈希就是一种索引 核心思想:哈希是一种通过一个函数(哈希函数),将任意长度的输入(如字符串、对象等),映射到一个固定长度的输出(哈希值)的技术。这个输出通常是一个整数,可以作为数组的索引。 目标:理想情况下,通过这个索引…

特殊的树

在离散数学中,N个节点、N-1条边就是树,并不必须要提到根。 至于为什么节点和边是这样的关系,因为不能成环! 树是二部图 二部图是一种特殊的图,它的所有节点可以被划分到两个独立的集合(比如集合A和集合B)中,并且满足:…

树

树和图是最常见的非线性数据结构 树的性质总结,使用小猫神力展开领域! 以下是树(包括一般树和二叉树)的主要性质总结(仅结论): 节点数与边数的关系 一棵有 个节点的树有 条边。 度与节点数的关系 设树中度为 的节点数为…

栈和队列

一个编译好的、静态存储在硬盘上的程序(如 a.exe),是如何被加载到内存中,并成为一个动态运行的进程的? 这个过程依赖于操作系统的核心机制:创建虚拟地址空间 和 按需加载。它就像为程序搭建一个专属的、私有的“理想厨房”…

线性表

ADT: a set of objects together with a set of operations. Abstract data types are mathematical abstractions;now…

算法分析

指令空间:存储程序指令。 数据空间:存储常量、简单变量、复合变量。 环境栈空间:保存部分完成函数恢复执行所需的信息。 当一个函数(或方法、过程)被调用时,系统会为其在环境栈顶压入(Push)一个“栈帧(Stack Fra…

OVERVIEW

下棋AI:在树上找必胜路径 数据:信息的载体,数字、字符或者其他符号组成的集合 可以分为数值型数据和非数值型数据 数据结构:数据对象+数据对象之间的关系的统称 Data_Structure={D,R} 分为线性数据结构和…

查看全部文章 ↗