求索数据结构的第一性原理
数据结构
指计算机存储、组织数据的方式。
逻辑结构
指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关。
-
线性结构：数据结构中的元素存在一对一的相互关系
-
非线性结构
- 集合：数据结构中的元素除了”同属于一个集合“的相互关系外，没有其它关系
- 树形结构：数据结构中的元素存在一对多的相互关系
- 图形结构：数据结构中的元素存在多对多的相互关系
简单地说，线性结构就是表中各个结点具有线性关系。如果从数据结构的语言来描述，线性结构应该包括如下几点：
1、线性结构是非空集。
2、线性结构有且仅有一个开始结点和一个终端结点。
3、线性结构所有结点都最多只有一个直接前驱结点和一个直接后继结点。
线性表就是典型的线性结构，还有栈、队列和串等都属于线性结构。
简单地说，非线性结构就是表中各个结点之间具有多个对应关系。如果从数据结构的语言来描述，非线性结构应该包括如下几点：
1、非线性结构是非空集。
2、非线性结构的一个结点可能有多个直接前驱结点和多个直接后继结点。
在实际应用中，树结构和图结构等数据结构都属于非线性结构。
物理结构
指数据结构在计算机中的表示（又称映像），它包括数据元素的机内表示和关系的机内表示。由于具体实现的方法有顺序、链接、索引、散列等多种，所以，一种数据结构可表示成一种或多种存储结构。
数据的顺序存储结构的特点是：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系；非顺序存储的特点是：借助指示元素存储地址的指针表示数据元素之间的逻辑关系。
常用的有：
-
顺序存储
-
链式存储
-
索引存储：分别存放数据元素和元素间关系的存储方式。
所有的存储结点存放在一个区域。另设置一个索引区域存储结点之间的关系。
索引是为了加速检索而创建的一种存储结构。它是针对一个表而建立的，是由存放表的数据页面以外的索引页面组成的。每个索引页面中的行都包含逻辑指针，通过该指针可以直接检索到数据，这样就会加速物理数据的检索。例如，假设在student表的ID列上建立了一个索引，则在索引部分就有指向每个学号所对应的学生的存储位置的信息。
-
哈希存储：亦称“散列存储”，专用于集合结构的一种存储方式。
数据元素存放在一块连续的存储区域中。数据元素的存放位置是通过一个哈希函数计算而得的。哈希函数将数据元素作为自变量，计算得到的函数值是数据元素的存储地址。
数据类型
和数据结构密切相关的，它是值的集合和定义在这个值集上的一组操作的总称。
高级语言中数据类型分为两类：
- 原子类型：值不可分解，是什么就是什么。如整型、字符型等。
- 结构类型：其值是由若干成分按某种结构组成的，因此可分解，并且它的成分可以是原子类型也可以是结构类型。（套娃，有无限的可能）。比如数组，其值是由若干分量组成的，每个分量可以是整数，或者也可以是数组。
🏛 把数据结构想象成骨架，单单有骨架的话数据还是死的，必须再用数据类型这种肉来填充骨架，有骨有肉这样数据才是鲜活的！
关于数据结构的奇思妙想
- 一个因理解错”数组“概念而提出的很蠢的问题！
An array is an ordered collection of data elements of the same type, each constrained by n(n>=1) linear relationships. Arrays can be thought of as an extension of linear tables, a common data structure.
Because arrays generally do not do insert or delete operations, we usually use sequential storage to implement the array, that is, in memory to draw a contiguous space to store the array, the contiguous memory address also happens to be the array element number, this implementation is undoubtedly very practical and very reasonable.
However, from the point of view of the feasibility of data structures, I wanted to try to explore more possibilities.
We know that in the computer architecture of the Von Neumann system, data structures are generally stored in the machine in four ways: Sequential storage, chain storage, index storage, and hash storage. Now, can arrays be implemented using chained storage? And is there any possible practical value to this implementation?
@ Welbog
Array is, strictly speaking, a contiguous block of memory, addressed by a base index and offset indexes. The term “array” almost always refers to that specific implementation rather than an abstract data type with multiple implementations. A list is a more general ordered set and might be a more appropriate term for your situation.
数组是线性表的顺序存储实现，不是一种跟”线性表“那样的抽象数据结构。
