数据结构

521 阅读4分钟

基于最近面试发现基础掌握不牢靠,重新梳理一下各个知识。

数据结构:数据元素相互之间的关系称为结构。

逻辑结构:

  • 集合结构:除了同属于一种类型外,没有其他关系
  • 线性结构:元素之间存在一对一关系常见类型有:数组,链表,队列,栈,它们之间在操作上有所区别。
  • 树形结构:元素之间存在一对多关系,常见类型有:树(有许多特例:二叉树、平衡二叉树、查找树等)。
  • 图形结构:元素之间存在多对多关系,图形结构中每个结点的前驱结点数和后续结点多个数可以任意。

物理结构:

  • 顺序存储结构:用物理位置的相邻关系表示数据元素之间的逻辑关系。
  • 链式存储结构:对每一个数据元素用一块较小的连续区域存放,称为节点,然后用指针表示逻辑关系,在节点中设置一个或多个指针,指向它的前驱或后继元素的地址。
  • 索引存储结构:这是一种顺序加链式的存储方式,数据元素按顺序结构存放,然后将每个数据元素的关键字和存储地址构造一个索引表单独储存,这种存储结构不表示元素之间的关系。
  • 哈希存储结构:数据元素按顺序或链式存储,并在数据元素的关键字与存储地址之间建立一种映射,这种存储结构不表示元素之间的关系。

常用的数据结构有:

  • 数组: 存储多个相同类型的数据的集合。
    特点:

    • 数组中的数据元素可以是基本数据类型,也可以是引用数据类型;
    • 数组具有下标,下标从0开始计数,用于快速获取数组中的数据,比如a[0],表示数组中的第一个数据;
    • 数组在创建的时候,需要在内存中申请一段固定长度的内存,如果申请的长度超过内存剩余的长度,则容易产生碎片,导致存储失败;
    • 数组分为数值数组,字符数组,指针数组,结构数组等;

    数组的优点是:get和set操作时间上都是O(1)的;缺点是:add和remove操作时间上都是O(N)的。

  • 栈:一种只能在一端进行数据插入和删除操作的线性表,又名堆栈。允许插入、删除操作的一端是栈顶、另一端是栈底。

    特点:

    • 按照先进后出的原则存储数据;
    • 栈分为顺序栈和链式栈;
  • 队列:一种特殊的线性表,只能在队头进行删除数据操作,在队尾进行增加数据操作。
    特点:

    • 遵循先进先出的原则存储数据;
    • 队列分为顺序队列和循环队列;
  • 链表:一种非连续,非顺序的存储方式,通过指针将数据进行连接的方式实现。 特点:

    • 在创建的时候,不需要指定长度,可以动态调整长度,不易产生碎片;
    • 链表的每个元素分为数据和指针,指针指向下一个数据的地址,从而形成串联;
    • 便于数据增删,不便于数据查询;
    • 链表分为单向链表,双向链表,循环列表;

    链表的优点是:add和remove操作时间上都是O(1)的;缺点是:get和set操作时间上都是O(N)的,而且需要额外的空间存储指向其他数据地址的项。查找操作对于未排序的数组和链表时间上都是O(N)。

  • 树:由一个根节点和若干个子树构成的集合。 特点:

    • 有且仅有一个根节点;
    • 子树之间不可以有交集;
    • 树的深度指的是树的有多少层;
    • 一个节点的度指的是该节点下有多少个子节点;
    • 二叉树指的是每个结点的度≤2的树。
    • 树的遍历方式分为三种,分别是前序遍历(根左右),中序遍历(左根右),后序遍历(左右根);
    • 树分为无序树,有序树,二叉树等;
  • 堆:用于动态分配和释放程序所使用的对象。 特点:

    • 堆是一棵完全二叉树;
    • 分为最小堆和最大堆,区别在于所有父节点是否大于等于其子节点,是则是最大堆,否则反之;

  • 散列表: 散列表也叫哈希表,是根据关键键值(Keyvalue)进行访问的数据结构,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度,这个映射函数叫做散列函数。 特点:
    • 便于插入,查找等操作;
    • key以数组的方式存储在栈内存中,value以链表的方式存储在堆空间中;
    • 不同的key通过哈希函数可能得到相同的结果,这时候就发生了哈希碰撞;