数据结构与算法（Java 语言描述）【五】

发布于 更新于
本文目录
  1. 常用数据结构
  2. 哈希表
  3. 树
  4. 堆
  5. 图

技术文章测试开发

特点：

常用数据结构

哈希表

  • 特点：

    • 一般没有容量限制，是通过对Key的哈希计算快速存储和访问指定的内容

    • 因为一般的哈希算法是把任意长度的值，生成指定长度的Key，可能会存在哈希碰撞问题

    • 碰到哈希碰撞时，会通过一个链表来存储具有相同哈希值Key的数据

    • 为了提高哈希表的访问效率，当某个哈希值的相同Key过多，比如超过8个，会使用红黑树进行存储，性能更好

    • 具体如下图 1639311822890.png

  • 逻辑结构：根据关键码(Key)和值(Value)进行访问的数据结构

  • 物理结构：通过对Key进行一个哈希算法映射到一个指定位置，这样就能很快在哈希表中找到对应元素；物理结构上结合了数组和链表进行存储

  • 优点：插入、删除、查询都一个字，快

  • 缺点：结构略复杂，对初学者不友好

  • Java语言中的定义如下 Map<Integer,String> data = new HashMap<>();

  • 详细示例见附件中的HashMapDemo.java

树

  • 特点：

    • 由1~n个有限节点组成的一种层次化的数据结构，有唯一一个根节点

    • 称之为树，是因为其结构像一颗倒挂的树，也就是根朝上，叶子朝下

    • 每个节点有0~n个子节点

    • 没有父结点的叫根节点

    • 没有子节点的叫叶子节点

    • 具体如下图，分别为树、二叉树、满二叉树 16393161632002.png

  • 逻辑结构：由1~n个有限节点组成的一种层次化的数据结构

  • 物理结构：常用的存储方式有双亲表示法(顺序存储)、孩子表示法(链表存储)、孩子兄弟表示法(链表存储)

  • 优点：是一种相对有用的折中数据结构，其插入、删除元素很快，在查找方面也有很多的算法优化；其中二叉树既有链表的优点，也有数组的特性，是两者的优化方案，在处理大批量的动态数据方面非常有用

  • 缺点：学习稍复杂

  • 扩展：基于二叉树，还有很多扩展的应用，如平衡二叉树、红黑树、B+树等

  • Java语言中一般没有直接操作树，但有一些集合类是基于树实现的；像TreeMap和TreeSet都是基于红黑树实现的，本身也是一个二叉树

堆

  • 特点：

    • 是用数组实现的二叉树，没有像树一样的指针域

    • 根据"堆属性"来进行排序

    • 主要的应用有：构建优先队列、支持堆排序、快速找出一个集合中的最大值或最小值

  • Java语言中没有对堆的直接操作，在应用中使用也比较少

图

  • 特点：

    • 是离散数学的概念，是一些顶点的集合，并且顶点使用边连接起来，边还可以有权重

    • 广泛应用于如工作任务分解、列车运行图等方面

    • 在一个图确定后，可以使用广度优先搜索和深度优先搜索来查找两个顶点间的路径

    • 常见的场景如下图的城市关系图

    1639464739861.png

  • Java语言中没有对图的直接操作，在应用中使用需要自己构建相应数据结构

【备注：部分图片来自网络】

来源：testingpai

继续阅读