最近在学习数据结构，有必要对自己这两天的学习做一个总结，今天就来总结下，数据结构的逻辑结构

按照分类标准的不同，我们把数据结构分为逻辑机构和存储结构，今天主要讲解逻辑结构

逻辑结构：是指数据对象中的数据元素之间的相互关系，主要分为以下四种结构

1.集合结构

集合结构中的数据元素处理同属于一个集合里，它们之间没有其他关系。各个数据元素是“平等”的，它们的共同属性是“同属于一个集合”。数据结构中的集合关系就类似于数学中的集合，满足集合的三个基本性质，确定性，互异性，无序性，而满足这个性质的应该只有C语言里的结构体满足这个条件，因为结构体里的数据无序，互异，确定。

 2.线性结构

线性结构中的数据元素之间存在一对一的关系，满足这个关系的有  线性表（数组，vector，链表），队列，栈，串

下面具体解释下原因：先看定义

线性表：零个或者是多个数据元素的有限序列。

下面对其定义进行下充分的解读，首先它是一个序列，也就是说元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且之后一个前驱和后继。然后线性表强调是有限的，当元素个数为零个时称为空表。

所以线性表的元素之间是满足一对一的关系的

栈：栈(stack)是限定仅在表尾进行插入和删除操作的线性表，是一种特殊的线性表，所以属于线性结构

队列：队列(queue)是只允许在一端进行插入操作，而在另外一端进行删除操作的线性表，是一种特殊的线性表，所以属于线性结构

串：串(string)是由零个或者多个字符组成的有限序列。

看定义我们就能清楚的看到，串是特殊的线性表，只是把定义中的数据元素换成了特定的字符元素，所以串也是属于线性结构

一般情况下，把栈，队列，串，分为一组叫受限线性表。

3.树形结构

树形结构中的数据元素之间存在一种一对多的层次关系，一般分为一般树和二叉树，满足这个关系的有 set,map

4.图形结构

图形结构的数据元素是多对多的关系，一般分为有向图和无向图，

最后可以画一个思维导图进行下总结

由于暂时没有找到之前画的图，这里有一处错误更正，集合的常见结构不是结构体，结构体本身不算是数据结构，因为结构体里存放的不是相同的数据元素，这里的集合应该是哈希表，又叫散列表。

数据结构

数据结构有两个概念、逻辑结构，物理结构（存储）
逻辑结构：描述数据节点之间的关系。
物理结构：描述数据在内存中是如何存储的（分配内存空间）。

逻辑结构

集合结构，线性结构，树状结构，网络结构（图形）

集合结构

数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；

线性结构

元素存在一对一的相互关系

树状结构

元素存在一对多的相互关系

网络结构（图形）

元素存在多对多的相互关系

物理结构（存储）

物理结构又叫存储结构，分为以下四种：
顺序存储结构：顺序存储结构。
非顺序存储结构：链式存储结构、索引结构、散列结构。

顺序存储结构

数据存储内存空间是连续的

链式存储结构

数据存储内存空间是不连续的

索引存储结构

分别存放数据元素和元素间关系的存储方式，存在索引（index）用以检索数据

散列存储结构（哈希）

分别存放数据元素和元素间关系的存储方式，将关键码（key）经函数映射后（通常为 hash）得到数组索引（index），根据数组特性，通过 index 即可得到数据存储地址（addr）

// Java hashMap 映射函数 i：index , n:table.length , hash:hashcode
i = (n - 1) & hash

数据结构对性能的影响

(1)检索。检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。 [3]
(2)插入。往数据结构中增加新的节点。
(3)删除。把指定的结点从数据结构中去掉。
(4)更新。改变指定节点的一个或多个字段的值。
(5)排序。把节点按某种指定的顺序重新排列。例如递增或递减。

通常，评估一种数据结构会有如下指标：

1. 常用数据操作（随机情况下）的速度（查询、插入、删除、修改、排序）；
2. 内存利用率，内存扩展性；
3. 存储密度；
4. 存储数据类型是否灵活；
5. 随机访问性如何（影响数据操作速度即时间复杂度）；

最终，一种数据结构的性质表现，会由逻辑结构，存储结构，加其额外定义的规则决定（如栈，限制了只允许栈顶对数据进行操作）。同一存储结构也会因为不同的定义导致差异（如无序数组插入速度比有序数组快，因为无序数组直接在队尾插入数据，不需要挪动数据的位置），也就是说得具体问题还得具体分析。

数组，随机插入数据则时间复杂度为O(n)，只在队尾插入则为O(1) ,所有答案如何全看前提条件是什么。