数据结构

概述

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。

划分

从关注的维度看，数据结构可以划分为数据的逻辑结构和物理结构，同一逻辑结构可以对应不同的存储结构。

逻辑结构反映的是数据元素之间的逻辑关系，逻辑关系是指数据元素之间的前后间以什么形式相互关联，这与他们
在计算机中的存储位置无关。

逻辑结构包括：

• 集合：只是扎堆凑在一起，没有互相之间的关联
• 线性结构：一对一关联，队形
• 树形结构：一对多关联，树形
• 图形结构：多对多关联，网状

物理结构指的是逻辑结构在计算机存储空间中的存放形式(也称为存储结构)。一般来说，一种数据结构的
逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序存储、链式存储、索引存储和哈希存储
等。

• 顺序存储：用一组地址连续的存储单元依次存储集合的各个数据元素，可随机存取，但增删需要大批移动
• 链式存储：不要求连续，每个节点都由数据域和指针域组成，占据额外空间，增删快，查找慢需要遍历
• 索引存储：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。检索快，空间占用大
• 哈希存储：将数据元素的存储位置与关键码之间建立确定对应关系，检索快，存在映射函数碰撞问题

程序中常见的数据结构

• 数组(Array)：连续存储，线性结构，可根据偏移量随机读取，扩容困难
• 栈( Stack)：线性存储，只允许一端操作，先进后出，类似水桶
• 队列(Queue)：类似栈，可以双端操作。先进先出，类似水管
• 链表( LinkedList)：链式存储，配备前后节点的指针，可以是双向的
• 树( Tree)：典型的非线性结构，从唯一的根节点开始，子节点单向执行前驱（父节点）
• 图(Graph)：另一种非线性结构，由节点和关系组成，没有根的概念，互相之间存在关联
• 堆(Heap)：特殊的树，特点是根结点的值是所有结点中最小的或者最大的，且子树也是堆
• 散列表(Hash)：源自于散列函数，将值做一个函数式映射，映射的输出作为存储的地址

算法

算法指的是基于存储结构下，对数据如何有效的操作，采用什么方式可以更有效的处理数据，提高数据运算效率。
数据的运算是定义在数据的逻辑结构上，但运算的具体实现要在存储结构上进行。一般涉及的操作有以下几种：

• 检索：在数据结构里查找满足一定条件的节点。

• 插入：往数据结构中增加新的节点，一般有一点位置上的要求。

• 删除：把指定的结点从数据结构中去掉，本身可能隐含有检索的需求。

• 更新：改变指定节点的一个或多个字段的值，同样隐含检索。

• 排序：把节点里的数据，按某种指定的顺序重新排列，例如递增或递减