数据结构
什么是数据结构
### 一、数据结构的起源 1968年，美国高德纳教授，《计算机程序设计艺术》第一卷《基本算法》提出，开创了数据结构与算法的先河 数据结构是一门研究数据之间关系、操作的学科，而非计算数据方法 数据结构 + 算法 = 程序 揭露了程序的本质，沃思凭借这个观点获得了图灵奖 ### 二、数据结构中的基本概 ......
【数据结构】选择排序 简单选择+堆排序
选择排序的基本思想是每次从待排序的序列中选出最小值(或者最大值)依次放在已排序序列中，直到待排序序列为空，此时序列已完全有序。选择排序的选择只需要进行n-1趟，因为当剩余元素数量为1时无需再选择，直接放在排序序列的末尾即可。 在这里学简单选择排序和堆排序两种算法，简单选择考的不多，堆排序是考察重点。 ......
「Note」数据结构方向 - 可持久化数据结构
# 1. 可持久化线段树 ## 1.1. 介绍 可持久化线段树一般用于解决区间第 $k$ 小值的询问。 首先考虑简化过的问题，区间 $\left[1,r\right]$ 的第 $k$ 小值。 考虑用权值线段树（离散化或动态开点）来求 $k$ 小值，接下来只需要解决区间的问题。 可持久化线段树核心思想 ......
「Note」您想来点数据结构吗？
### [$\color{black}{P4119\ [Ynoi2018]\ 未来日记}$](https://www.luogu.com.cn/problem/P4119) #### 思路：分块+值域分块 #### 复杂度：$O(n\sqrt n+m\sqrt n)$ #### 主题思路 数列分块需 ......
数据结构--选择排序
## 数据结构--选择排序 #### 简单选择排序 **在待排序的数据中选出最大的(小)的元素放在其最终位置.** ，时间复杂度: O(n) 示例1 输入： "1+2" 返回值： 3 示例2 输入： "(2*(3-4))*5" 返回值： -10 ......
Golang之数据库转换结构体工具table2struct
另外一个根据json生成对应结构体在线工具: https://mholt.github.io/json-to-go/ 安装: go get github.com/gohouse/converter 或者下载对应平台的二进制文件 https://github.com/gohouse/converter ......
01数据结构和算法绪论
01数据结构和算法绪论 soooob 关注 2017.10.23 18:42* 字数 625 阅读 2评论 0喜欢 0 1. 什么是数据结构？ 数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及他们之间的关系和操作等相关问题的学科。 通俗来说数据结构是： 程序设计 = 数据结构 + 算法 ......
数据结构口胡记录
数据结构口胡记录 114514天没写博客了（悲） ### [Bear and Bad Powers of 42](https://www.luogu.com.cn/problem/CF679E) $tag$：线段树，势能分析 原问题不好直接做，考虑转化维护信息 首先可以发现42的幂次并不多,所以每次 ......
[数据结构]树上倍增
# 树上倍增 ## 一、一点理解 最近遇到几个关于树上倍增问题。本人太菜，有时候想不到用倍增，这里做个总结。 树上倍增核心就是：$f[u][j]$，含义是$u$向上跳$2^j$步到的位置，然后用$f[u][j] = f[f[u][j-1]][j-1]$进行转移。 **树上倍增常见应用就是：快速幂、线 ......
redis数据结构跳表
# redis数据结构跳表 ## 数据结构 ### 跳表节点 ```c typedef struct zskiplistNode { // 层 struct zskiplistLevel { // 前进指针 struct zskiplistNode *forward; // 跨度 unsigned ......
【数据结构】排序2 交换排序
交换排序就是基于比较交换的排序。 主要讲两种交换排序算法：**冒泡排序和快速排序**。 冒泡排序比较简单一般不会单独考察，重点考察的是快速排序的内容。 #### 1.冒泡排序 **基本算法思想：** 对于每趟排序，从后往前两两比较，如果为逆序则进行交换，这样很显然不能一趟就得到正确的序列，但是每次都 ......
数据结构4
算法： 数据结构中的算法，指的是数据结构所具备的功能 解决特定问题的方法。学习的前辈们的一些优秀的经验总结 算法的五大特征： （1）有穷性。一个算法必须总是在执行有穷步后结束，且每一步都必须在有穷时间内完成。 (2) 确定性。对千每种情况下所应执行的操作，在算法中都有确切的规定，不会产生二义性， 使 ......
线性表【数据结构学习-青岛大学王卓老师】
[https://www.bilibili.com/video/BV1qz4y1p767/]() # 线性表 ## 线性表的初始化(顺序表) ```c++ Status InitList(SqList &L) { L.elem = (ElemType *) malloc(sizeof(ElemTyp ......
redis数据结构字典
# redis数据结构字典 ## 数据结构 Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。 ### 哈希表 ```c typedef struct dictht { // 哈希表数组 dictEntry **table; // ......
数据结构（哈夫曼树）：判定编码方案是否为前缀编码
前缀编码定义：（字符集中）任一编码都不是其它字符的编码的前缀（字符集中）任一编码都不是其它字符的编码的前缀（字符集中）任一编码都不是其它字符的编码的前缀重要的话说三遍！例：(1)找出下面不是前缀编码的选项A{1，01，000，001}B{1，01，011，010}C{0，10，110，11}D{0， ......
redis数据结构链表
# redis数据结构链表 ## 数据结构 ### 链表节点 ```c typedef struct listNode { // 前置节点 struct listNode * prev; // 后置节点 struct listNode * next; // 节点的值 void * value; }l ......
redis数据结构sds
# 简单字符串sds ## 数据结构 ``` c struct sdshdr { // 记录buf 数组中已使用字节的数量 // 等于SDS 所保存字符串的长度 int len; // 记录buf 数组中未使用字节的数量 int free; // 字节数组，用于保存字符串 char buf[]; } ......
Redis设计与实现——数据结构(二刷)
# SDS 动态字符串 Redis 是 c 语言实现的，传统 c 字符串存在不可变导致的频繁内存分配，一些 API 函数可能引起缓冲区溢出等问题。 Redis 在 c 字符串的基础上，封装实现了 SDS动态字符串，能够根据每次存储关键字的大小自动申请额外缓冲区内存，避免频繁申请和缓冲区溢出问题。 # ......
数据结构与算法 --- 如何分析排序算法
## 引言 排序算法是最基础的算法，对于排序算法，除学习算法原理，代码实现之外，更重要的是学习每个算法的特点，知道在什么场景下选择那种算法。 那一定是选择时间复杂度最低的排序算法就是最优的吗？ 可以从以下几个方面分析一下。 ## 排序算法的执行效率 对于排序算法的执行效率，一般从以下几个方面来分析： ......
数据结构与算法 --- “哨兵”思想
## 引言 哨兵思想是指在算法中使用一个特殊值来检测或标记某些条件的发生，它的目的是为了简化代码，并使其更容易理解，常常用于在循环中优化边界条件的判断。 ## 介绍 在算法中，"哨兵"思想是指在循环中设置一个特殊的元素（称为哨兵），以便在循环过程中能够更高效地处理某些边界情况或结束条件。 这种思想可 ......
数据结构与算法 --- 递归（一）
## 什么是递归？ **递归（Recursion)** 是一种解决问题的方法，它将问题分解为更小的子问题，并逐层解决这些子问题。递归算法的核心思想是：**一个函数可以直接或间接地调用自身**。通过这种自我调用，我们可以用简洁的代码来解决复杂问题。 ## 满足递归的条件 一般来说，满足下面三个条件就可 ......
数据结构与算法 --- 递归（二）
## 引言 上文[数据结构与算法 递归（一）](https://niuery.com/post/51) 讲述了什么是递归算法，如何编写递归算法及如何写好递归算法，本文着重讲述一下如何避免递归过深导致的堆栈溢出问题。 ## 探究产生堆栈溢出的原因 函数调用采用**函数调用栈**来保存当前“快照”（局部 ......
数据结构与算法 --- 排序算法（一）
## 引言 按照时间复杂度，将一些常见排序算法进行分类，分为以下三类： - $O(n^2)$：冒泡排序，插入排序，选择排序。 - $O(nlogn)$：快速排序，归并排序。 - $O(n)$：桶排序，计数排序，基数排序。 本篇文章讨论以下第一类：冒泡排序，插入排序，选择排序。 上一篇[数据结构与算法 ......
数据结构与算法 --- 排序算法（二）
title: 数据结构与算法 排序算法（二） category: 数据结构与算法 tags: 算法 updatedAt: 2023-05-18T15:29:17.847Z createdAt: 2023-05-13T14:43:31.656Z ## 引言 上一篇[数据结构与算法 排序算法（一）](h ......
数据结构与算法 --- 组数、链表、栈和队列（一）
数组、链表、栈和队列是四种基础数据结构，他们是高级、复杂的数据结构和算法的基础。本篇先来讲述**数组，链表，及算法的优化策略**。 ### 数组 #### 定义 **数组：数组是一种线性表数据结构，它用一组连续的内存空间存储一组具有相同类型的数据。** 定义中有三个关键词： - **线性表** - ......
数据结构与算法 --- 组数、链表、栈和队列（二）
继[数据结构与算法 组数、链表、栈和队列（一）](https://niuery.com/post/41)讲解完数组，链表及算法的优化策略之后，接下来继续讲解**两种特殊的线性表结构，栈和队列**。 ## 栈 对“栈”有一个很形象的比喻，栈就像一摞叠在一起的盘子，放盘子时，只能放在上面，不能将盘子插入 ......