初识数据结构

1、什么是数据结构？

想要学习数据结构，首先要什么是数据呢？数据就是描述客观事物的数和字符的集合。即所有能被输入计算机中，且能被计算机处理的符号的集合，是计算机操作对象的总称，也是计算机所处理信息的某种特定的符号表示形式。例：0、1、2、3、4、5......9,A、B、C......Z等。

数据元素即数据的基本单位。例：把一个班级看着一个整体的数据，班里面的每个人就是他的基本单位。

数据项是具有独立含义的数据最小单位，也称为字段或段。班里面的一个同学是数据元素，而每个同学有自己的学号、姓名、班级等信息，它们就是组成一个数据元素的数据项。

数据对象：指性质相同相同的数据元素的集合，是数据的一个子集。 一个班里面的十几个同学可以组成一个小组，这样一个小组即为一个数据对象。

数据结构：所有数据元素以及数据元素之间的关系，即相互之间存在着某种特定关系的数据元素的集合。

数据的逻辑结构：由数据元素间的逻辑关系构成。

上面的数据1~10数据中，每个数据在逻辑上相邻元素都相差1。

数据的存储结构：数据元素即其关系在计算机存储器中的存储表示，即数据的物理结构。

数据的运算：施加在该数据上的操作。

2、数据的逻辑结构：

数据的逻辑结构即从数据的逻辑关系上描述数据，是指数据间逻辑关系的整体。数据的逻辑结构与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作从问题中抽象出来的数据模型。

了解完数据的逻辑结构理论，接下来我们将学习如何表示一个数据的逻辑结构。

2.1、逻辑结构的表示：

数据结构的逻辑表示方法有很多种，我们常用的为图表和二元组，下面为大家展示图表法。

学生表的图形表示：

二元组表示：

$B = (D,R)$

$D = \left \{d_i | 1\leqslant i \leqslant n,n\geqslant 0 \right \}$

$d_i$ 表示集合D的第i个元素，n为D中数据元素的个数。当n为0时，D为空集。

$R = \left \{r_j | 1\leqslant j\leqslant m,m\geqslant 0 \right \}$

$r_j$ 表示集合R中的第j个关系，m为R中的关系的个数，若m = 0，则R是一个空集。表面集合D中的元素间不存在任何逻辑关系，彼此是独立的。

R中的一个关系r是序偶的集合，对于r中的任一序偶 $<x,y>(x,y\epsilon D)$ ，表示元素x和y之间是相邻的，x在y之前，y在x之后，x为该序偶的第一元素，y为该许偶的第二元素。x为y的直接前驱元素，y为x的直接后驱元素。若某个元素没有前驱元素，则该元素为开始元素，若某个元素没有后继元素，则称该元素为终端元素。

例：下面有一张城市表，假设城市区号唯一，给出其逻辑结构的二元组表示。

表中有5个元素，其逻辑结构的二元组表示如下：

$City = (D,R)$

$D = \left \{ 010,021,027,029,025 \right \}$

$R = \left \{ r \right \}$

$r = \left \{ <010,021>,<021,027>,<027,029>,<029,025> \right \}$

2.2逻辑结构的类型：

集合：数据元素之间除了“属于同一个集合”的关系以外别无其他关系。

线性结构：该结构中的数据元素之间存在着一对一的关系。

树形结构：该结构中的数据元素之间存在着一对多的关系，树形结构除了开始的元素外，每个元素有且仅有一个前驱元素，除了终端元素外，每个元素有一个或者多个后继元素。

例：有一种数据结构 $B_i = (D,R)$ ,其中：

$D = \left \{ a,b,c,d,e,f,g,h,i \right \}$

$R = \left \{ r \right \}$

$r =\left \{ <a,b>,<a,c>,<a,d>,<b,e>,<c,f>,<c,g>,<d,h>,<d,i>,<d,j> \right \}$

图形结构：该结构中的数据元素之间存在多对多的关系。树形结构和图形结构统称为非线性结构。

3、存储结构：

顺序存储结构：利用数据元素在存储器中的相对位置来表示数据元素之间的逻辑顺序，如数组。

顺序存储结构是数据存储的一种方式，它有以下特点：

        连续的存储空间：顺序存储结构使用一块连续的内存空间来存储数据元素，这些数据元素在物理上是相邻的。
        固定的大小：在顺序存储结构中，每个数据元素占用的存储空间大小是固定的，这使得可以通过索引直接访问数据元素。
        支持随机访问：由于数据元素在内存中的位置是连续的，因此可以快速地通过索引直接访问任何一个数据元素，这种访问方式称为随机访问。
        简单的数据关系：顺序存储结构通常用于存储线性表，其中数据元素之间存在“一对一”的简单线性关系。
        高效的数据处理：由于数据元素的存储位置连续，许多操作如遍历、排序等都可以高效地执行。

此外，顺序存储结构适用于需要频繁进行随机访问的场景，如数组、栈、队列等。它们在内存中的物理布局简单且易于管理，但可能需要在插入和删除操作时移动大量元素以维护数据的连续性。

链式存储结构：通过结点中的指针来表示数据元素之间的关系，数据元素可以存放在任意的存储单元中。

链式存储结构是数据结构中的一种重要存储方式，它与顺序存储结构相对。以下是链式存储结构的特点和概念：

        ①.节点组成：
        数据域：用于存储数据元素的实际信息。
        指针域：用于存储指向直接后继元素的地址信息。
        ②. 链表类型：
         单链表：每个节点只有一个指针域，指向下一个节点。
         双链表：每个节点有两个指针域，分别指向前一个和下一个节点。
        循环链表：链表中的最后一个节点的指针域指向第一个节点，形成闭环。
        ③.头节点和头指针：
        头节点：链表中的第一个节点，可以是虚拟的也可以是实际存储数据的节点。
        头指针：指向链表中第一个节点的地址。
        ④. 优势与适用场景：
        灵活性：链式存储结构不需要连续的内存空间，因此可以动态地分配内存，适合数据规模不确定的情况。
        插入和删除操作：由于链表的节点可以分散存储在内存中，因此在进行插入和删除操作时，不需要像顺序存储结构那样移动大量元素，提高了操作的效率。
         不适合随机访问：由于链表的节点可能分散在内存的各个角落，因此随机访问某个节点的效率较低。

索引存储结构：在存储数据元素信息的同时还建立附加索引表，包含数据元素和存储地址。

索引存储结构是数据库中用于提高数据检索效率的一种数据结构。它通过为数据表中的一列或多列创建一个排序的数据结构，使得数据库管理系统能够快速定位到所需的数据。

以下是索引存储结构的关键点：

        1. B+树结构：这是数据库中常用的索引存储结构，特别是在MySQL数据库中。B+树是一种平衡多路查找树，能够保持数据的有序性，并且所有数据都存储在叶子节点上，这有助于区间访问和高效的顺序扫描。
        2. B树索引：B树是B+树的前身，也是一种自平衡的多路查找树。B树的每个节点都存储了数据，而B+树的非叶子节点只存储键值信息，不存储实际数据，这使得B+树的非叶子节点可以拥有更多的子节点，从而降低了树的高度。
        3. 哈希结构：哈希索引使用哈希表来存储数据，它可以提供非常快速的点查询能力。但是，哈希索引不支持范围查询，因为它们不保持数据的有序性。
        4. R树结构：这是一种用于空间索引的数据结构，适用于地理空间数据的索引，如地图上的地理位置。R树结构不常见于传统的关系型数据库中。
        5. 聚簇索引和非聚簇索引：聚簇索引是指数据行和索引在一起存放，数据行就是按照索引的顺序存储的。非聚簇索引则是数据行和索引分开存放，索引包含指向数据行的指针。
        6.索引的选择：选择合适的索引类型对于数据库的性能至关重要。通常，如果需要进行范围查询或者顺序访问，B+树是一个不错的选择；如果需要快速的点查询，可以考虑使用哈希索引。
        7. 性能考虑：索引虽然可以提高查询速度，但也会降低更新表的速度，因为索引本身也需要被更新。因此，在设计数据库时，需要权衡查询和更新的需求，合理地创建和使用索引。

散列存储结构：通过关键字直接计算出元素的物理地址。

散列存储结构，也称为哈希存储，是一种利用关键码与数据元素存储位置之间的对应关系来直接访问数据的结构。

散列存储结构的核心在于**哈希函数**，它的作用是将关键码转换成表中的位置，以便直接访问对应的数据元素。这种存储结构的主要优点是它能够提供接近常数时间的访问效率，即O(1)的时间复杂度，这对于大量数据的快速检索非常重要。

然而，散列存储结构也存在一些潜在的问题：

        冲突：当两个不同的关键码通过哈希函数映射到同一个存储位置时，就会发生冲突。解决冲突的方法有多种，如开放定址法、链地址法等。
        分布不均：如果哈希函数设计得不够好，可能会导致数据在表中的分布不均匀，从而降低存储空间的利用率和查找效率。
        性能依赖：散列表的性能在很大程度上依赖于哈希函数的设计。一个好的哈希函数应该能够将关键码均匀地映射到整个表中，以减少冲突和提高访问速度。