Jared's blog Jared's blog
首页
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • Java
  • 数据库SQL
  • 设计模式
  • 集成开发环境
  • Linux系统
  • 代码管理
  • 项目管理
  • 后端

    • 中间件
    • Spring家族
    • 服务器软件
    • 数据库
    • 搜索引擎
    • 分布式&微服务
    • 容器化
  • 前端

    • 基础
    • 模板框架
    • 组件化框架
  • 运维知识
  • 部署工具
架构与模型
  • 在线教育
  • 电商
  • 疑惑日志
  • 随笔
  • 友链
  • 书籍
  • 娱乐
  • Github (opens new window)
  • Gitee (opens new window)
  • CSDN (opens new window)

Jared H

💻🤣😜
首页
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • Java
  • 数据库SQL
  • 设计模式
  • 集成开发环境
  • Linux系统
  • 代码管理
  • 项目管理
  • 后端

    • 中间件
    • Spring家族
    • 服务器软件
    • 数据库
    • 搜索引擎
    • 分布式&微服务
    • 容器化
  • 前端

    • 基础
    • 模板框架
    • 组件化框架
  • 运维知识
  • 部署工具
架构与模型
  • 在线教育
  • 电商
  • 疑惑日志
  • 随笔
  • 友链
  • 书籍
  • 娱乐
  • Github (opens new window)
  • Gitee (opens new window)
  • CSDN (opens new window)
  • 数据结构与算法

    • README
    • 数据结构

      • 线性结构
        • 逻辑结构
      • 算法

    • 计算机网络

    • 操作系统

    • Java

    • 数据库-SQL

    • 设计模式

    线性结构

    # 1. 线性结构

    # 数组

    数组是列表的实现方式之一,数组中的元素在内存中是连续存储的,且每个元素占用相同大小的内存。

    数组的优点:

    • 检索效率高

    数组的缺点:

    • 随机增删元素的效率较低
    • 事先必须知道数组的长度
    • 空间通常是有限制的
    • 需要大块连续的内存块

    # 链表

    链表中每一个节点都包含此节点的数据和指向下一节点地址的指针。由于是通过指针进行下一个数据元素的查找和访问,使得链表的自由度更高。 这表现在对节点进行增加和删除时,只需要对上一节点的指针地址进行修改,而无需变动其它的节点。不过事物皆有两极,指针带来高自由度的同时,自然会牺牲数据查找的效率和多余空间的使用。

    链表的优点:

    • 随机增删元素效率较高(因为增删元素不涉及到大量元素的位移)

    链表的缺点:

    • 查询效率低,每一次查找某个元素的时候都需要从头节点开始往下遍历

    # 队列

    队列是一种 FIFO 式的数据结构:第一个元素将被首先处理。有两个重要操作:入队和出队。我们可以使用带有两个指针的动态数组来实现队列。 我们可以使用广度优先搜索(BFS)。

    • 使用数组实现的叫静态队列
    • 使用链表实现的叫动态队列

    # 栈

    栈是一种 LIFO 式的数据结构:最后一个元素将被首先处理。有两个重要操作:push 和 pop。栈的实现非常简单,使用动态数组就足以实现栈。

    当满足 LIFO 原则时,我们使用栈。深度优先搜索(DFS)是栈的一个重要应用。

    • 使用数组实现的叫静态栈
    • 使用链表实现的叫动态栈

    # 散列表

    散列表(Hash table,也叫哈希表)是一种查找算法,与链表、树等算法不同的是,散列表算法在查找时不需要进行一系列和关键字(关键字是数据元素中某个数据项的值,用以标识一个数据元素)的比较操作。

    散列表算法希望能尽量做到不经过任何比较,通过一次存取就能得到所查找的数据元素, 因而必须要在数据元素的存储位置和它的关键字(可用 key 表示)之间建立一个确定的对应关系,使每个关键字和散列表中一个唯一的存储位置相对应。因此在查找时,只要根据这个对应关系找到给定关键字在散列表中的位置即可。这种对应关系被称为散列函数(可用 h(key)表示)。

    有两种不同类型的哈希表:哈希集合和哈希映射。

    • 哈希集合是集合数据结构的实现之一,用于存储非重复值。
    • 哈希映射是映射 数据结构的实现之一,用于存储(key, value)键值对。

    用的构造散列函数的方法有:

    (1)直接定址法: 取关键字或关键字的某个线性函数值为散列地址。

    即:h(key) = key 或 h(key) = a * key + b,其中 a 和 b 为常数。

    (2)数字分析法:找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址。

    (3)平方取值法: 取关键字平方后的中间几位为散列地址。这是因为:平方后中间几位和关键字中每一位都相关,故不同关键字会以较高的概率产生不同的哈希地址

    例:我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11,E的内部编码为05,Y的内部编码为25,A的内部编码为01, B的内部编码为02。由此组成关键字“KEYA”的内部代码为11052501,同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。之后对关键字进行平方运算后,取出第7到第9位作为该关键字哈希地址,如下所示

    关键字 内部编码 内部编码的平方值 H(k)关键字的哈希地址
    KEYA 11052501 122157778355001 778
    KYAB 11250102 126564795010404 795
    AKEY 01110525 001233265775625 265
    BKEY 02110525 004454315775625 315

    (4)折叠法:将关键字分割成位数相同的几部分,然后取这几部分的叠加和作为散列地址。

    例如:每一种西文图书都有一个国际标准图书编号,它是一个10位的十进制数字,若要以它作关键字建立一个哈希表,当馆藏书种类不到10,000时,可采用此法构造一个四位数的哈希函数。

    (5)除留余数法:取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址,

    即:h(key) = key MOD p p ≤ m

    (6)随机数法:选择一个随机函数,取关键字的随机函数值为它的散列地址,

    即:h(key) = random(key)

    上次更新: 2022/04/01, 15:14:40
    README
    逻辑结构

    ← README 逻辑结构→

    Theme by Vdoing Copyright © 2020-2022 Jared H
    粤ICP备20046800号
    • 跟随系统
    • 浅色模式
    • 深色模式
    • 阅读模式
    ×