八大数据结构分类

八大数据结构分类

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成

常见的数据结构 (C 语言)

常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等。


数组

数组是可以再内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问,数组下标从0开始。

优点
  1. 按照索引查询元素速度快

  2. 按照索引遍历数组方便

缺点
  1. 数组的大小固定后就无法扩容了

  2. 数组只能存储一种数据类型


栈是一种单向操作的线性表,只能从栈顶操作,特点是先进后出,添加元素叫入栈,取出元素叫出栈。

栈的结构就像一个集装箱,越先放进去的东西越晚才能拿出来,所以,栈常应用于实现递归功能方面的场景,例如斐波那契数列。


队列

队列与栈一样,也是一种线性表,不同的是,队列可以在一端添加元素,在另一端取出元素,也就是先进先出,从一端放入元素的操作叫入队,取出元素叫出队。

使用场景:因为队列先进先出的特点,在多线程阻塞队列管理中非常适用。


链表

链表是物理存储单元上就是非连续的,非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,每个元素包含两个节点,一个是存储数据的数据域,另一个是指向下一个节点地址的指针域。根据指针的指向,链表能形成不同的结构,例如单链表,双向链表,循环链表等。

优点
  1. 链表是很常用的一种数据结构,不需要初始化容量,可以任意加减元素;

  2. 添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可,所以添加,删除很快;

缺点
  1. 因为含有大量的指针域,占用空间较大;

  2. 查找元素需要遍历链表来查找,非常耗时。

适用场景
  1. 数据量较小,需要频繁增加,删除操作的场景

 

散列表

散列表,也叫哈希表,是根据关键码和值 (key和value) 直接进行访问的数据结构,通过key和value来映射到集合中的一个位置,这样就可以很快找到集合中的对应元素。

哈希表产生的原因

假设我们存在一个简单的键值对结构,键-员工号,值-是否在岗。现在需要这样一个功能,输入员工号,返回该员工是否在岗,理想的方法是创建一个长度为Max(员工号)的数组,数组下标就是员工号,数组中的值用0和1对是否在岗进行区分,这样只需要O(1)的时间复杂度就可以完成操作,但是扩展性不强,存在以下问题。

  1. 假设新进员工的员工号比Max(员工号)还要大,这就需要重新申请数组进行迁移操作。

  2. 假设一种极端的情况,存在两个员工,员工号分别是1和100000000001,这样子的话按照先前的设计思路,是会浪费很大的存储空间的。

上面两点,第一点是因为数组的固定申请大小的属性所决定,而第二点就是引入哈希表的原因,会不会存在一个方法,让一个大员工号变小而而且没有标记,哈希函数便产生,假设此处的哈希规则是除3取模,则员工1得到的哈希值是1,员工100000000001得到的哈希值是2,这样的话按照设计思路,只需要一个大小为2的数组便可以覆盖了,这就是哈希思想。 算法中时间和空间是不能兼得的,哈希表就是一种用合理的时间消耗去减少大量空间消耗的操作,这取决于具体的功能要求。

哈希函数

上面的例子中哈希函数的设计很随意,但是从这个例子中我们也可以得到信息

哈希函数就是一个映射,因此哈希函数的设定很灵活,只要使得任何关键字由此所得的哈希函数值都落在表长允许的范围之内即可

扩展:Python 字典的实现原理

 

未完待续

最新评论
2019-08-04 11:45:53 lihao
666

登录后评论