数据结构概观

发布时间:2019-07-04 作者:大扑棱蛾子 阅读次数:
版权声明:未经允许不得转载至微信公众号,转载至个人博客请注明出处。 阅读原文

数据结构

依据在概念上如何组织或汇集数据,可大致分为线性数据结构和非线性数据结构。

线性数据结构

  • 列表: 列表是项的线性集合,对项的添加、删除和搜索没有任何限制。列表分为有序列表无序列表
  • 队列: 队列是线性集合,只能按项被添加的顺序删除项。通常把队列说成先进先出数据结构。通常没有在队列中搜索项的操作。
    队列
  • 栈: 栈与队列的区别在于只能按项被添加的逆序删除它们。通常把栈说成是后进先出的数据结构。通常没有在栈中搜索项的操作。
    栈

非线性数据结构

  • 二叉树: 作为模拟实际系统或抽象系统的数据结构,二叉树是由项组成的,这些想对整棵树的贡献依赖于它们在树中的位置。把一项从一个位置移动到另一个位置将改变这棵二叉树的意义
  • 普通树: 普通树模拟诸如公司组织结构、家庭树这样的层次。它是二叉树结构的一般化。
  • 二叉查找树: 二叉查找树与二叉树有相同的结构形式,但是二叉查找树上的每一项都是自给自足的,当一项在树中的位置发生变化时,它对整棵树的贡献不变,而且整棵树的意义与项的相对排列无关。它是有序列表的树模拟。可以随意添加、删除或搜索项。
  • AVL树: AVL树是一种特殊的高度平衡的二叉查找树。普通的二叉查找树提供搜索项的机制;而AVL树的重要意义在于其搜索速度得到的极大的提高。
  • 作为优先队列的堆: 优先队列是FIFO队列的特化,其中的项有指定的优先度。在优先队列的所有项中,有最高优先度的项最先离开。这里,我们选择根据概念结构分类:它是作为堆实现的,而堆是特殊的二叉树结构。
  • 可更新堆: 一个简单的优先队列即堆中,它的优先度不再变化。如果要改变它的优先度,就需要可更新堆,即有可更新优先度的堆。可更新堆的实现引发有安全性和效率的若干问题,这需要比标准堆更精致的解决方案。

散列表

散列表存储以高效搜索为唯一目的的项,然而,与二叉查找树不同,散列表不以有效的顺序排列项,也没有树的结构。高效三列表的实现需要关于数的数学性质的丰富知识,以及关于操作数的所谓的散列函数的丰富知识。

图模拟关系。

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×