数据结构

数据结构含义

数据结构可以拆分成 数据+结构两部分来理解。
数据就是我们能够输入到计算机中的描述客观事物的符号，例如文本、图像、声音、二维码等等
结构就是数据元素之间是通过什么关系来关联或存储的。

数据的组成

其中数据是由数据元素这个基本单位组成，每一个数据元素也可以称作节点或记录。而数据元素是由若干个具有独立意义的数据项组成，数据项是不可再分的。

另外具有相同特性的数据元素的集合就叫做数据对象。所以数据对象是数据的一个子集。

我们可以通过这个表格来直观的看一下这几者之间的关系

这个整体就可以看做是一组数据，每一行就是一个数据元素，而这些数据元素都是由四个数据项组成，多条记录组合起来就是一个数据对象。

结构

结构包含了逻辑结构、存储结构、运算这三个要素。
逻辑结构就是表明数据元素与数据元素之间的关系，例如小明和小亮是表兄弟，而这个表兄弟就相当于逻辑结构

存储结构就是这些数据元素在计算机中是怎么存放的。例如小明和小亮在同一个班级，但是他们是同桌、邻桌、前后桌还是其他的座位，这样不同的座位安排就相当于在计算机中不同的存储方式。

但是不管他们两个怎么坐，都不影响他们是表兄弟的关系，所以逻辑结构是一个抽象的意义，独立于计算机。

运算通常是指的数据元素的操作方式，例如插入、查找、更新、删除等等。

逻辑结构的分类

逻辑结构又可以分为以下4种：
①集合：就是数据除了属于同一个集合外，没有其他任何关系。就例如鸡圈中的小鸡，同属于一个鸡圈，但是它们可以随意的走动。

②线性结构：有唯一的开始，唯一的结束，而且元素之间是一个对一个的关联。就像是羊肉串。
除了第一个元素外，每一个元素都有一个直接前驱(前面的元素)，除了最后一个元素外，每一个元素都有一个直接后继(后面的元素)。

③树形结构：一个对多个，就像树一样，每一个树枝上都可以分出来很多叉，每一个叉上还可以再分。
但是我们通常描述出来的树形结构类似是把树倒过来看。

④图形结构：多个对多个，每一个元素都可能和其他元素相关联。例如我们的地图，一个省可能和多个省相邻。

存储结构的分类

存储结构也可以分为以下四种
①顺序存储：就是逻辑上是相邻的数据元素，在计算机中存储位置也是相邻的。
就比如 小明和小亮是兄弟，并且他们两家是紧挨着的。

而在计算机中，顺序存储就是采用了一段连续的存储空间，逻辑上相邻的元素，在存储上也是相邻的，中间不能有间隔。
下面是一个大概的存储示意，0x001表示的意思是存储地址 ②链式存储：就是逻辑上相邻的元素，在计算机中存储位置不一定相邻。
就像 小明和小亮是兄弟，但是小明在北京安家了，而小亮则在上海定居了，他们两个没有住在一起，但是小明知道小亮的家庭住址，可以很容易的找到小亮。
所以在数据元素上，会多增加一个指向下一个元素存储地址的指针域。通过这个指针域可以很方便的找到下一个元素。

③散列结构：就是通过一系列的散列算法将数据元素的key进行计算然后确定对应的数据存储位置。

例如有这样的数据，{1:"a", 22: "b", 33: "c", 40: "d", 45: "e"}
散列函数使用key%10来计算，可能得到这样的存储结果 假如上面的数据中多了一个51:"f"，那么按照上面的散列函数，就会出现51和1的冲突，像这种冲突会有其他的解决办法，常见的就是 1和51存在一起，但是中间是使用其他结构存储这两个key ④索引存储：就是除了建立存储节点的信息外，还会额外建立一个索引表来记录节点的存储地址。索引表由若干个索引项组成，假如每个节点都有一个对应的索引项，那么这个索引表就是稠密索引，如果多个节点对应一个索引项，那么这个索引表就是稀疏索引。
举例说明：
每个人都对应一个身份证号，根据身份证号又能找到对应的人，那么存储身份证号的那张表就可以理解为稠密索引。
每个学生都会有自己的班级，但是一个班级里是有多个学生的，知道了班级，就能知道班里都有哪些学生，那么维护班级的那个表就可以理解成稀疏索引。

另外我们在上网查询一些内容时，只需要输入关键字，就能查询出来相关的信息，这样根据属性值来查找记录的索引就被称为倒排索引。