图解数据结构：线性表_数据结构线性表查找图解

1. 数据结构三要素

1）逻辑结构 指的是数据间的逻辑关系，与数据的存储无关，独立于计算机之外。它又分为线性结构和非线性结构

• 线性结构：线性表，栈，队列，串，数组和广义表
• 非线性结构：树，图，集合

2）存储结构 是逻辑结构的存储映像，就是数据间的关系在计算机中的表现形式。也成为物理结构。它又分为 4 类：顺序存储 ，链式存储，索引存储和散列存储

• 顺序存储：把逻辑上相邻的元素存储在物理位置也相邻的存储单元里
• 链式存储：不要求物理位置的相邻，借助指示元素存储地址的指针表示元素之间的逻辑关系
• 索引存储：在存储元素信息的同时，添加附加的索引表，通过索引对节点进行操作
• 散列存储：也称 Hash 存储，根据结点的关键字通过散列函数计算出结点的存储地址

相同的逻辑结构在计算机里可以用不同的存储结构实现。比如逻辑结构中的线性结构，可以用数组（顺序存储）或单向链表（链接存储）来实现。

3）数据运算： 施加在数据上的运算（包括定义与实现）。运算的定义是针对逻辑结构，运算的实现是针对物理结构

2. 线性表的定义

线性表定义：

• 具有相同数据类型的 n 个数据元素的有限序列
• 线性表是一种逻辑结构，表示元素之间一对一的逻辑关系

使用线性表存储数据的方式可以这样理解，把所有数据用一根线儿串起来，再存储到物理空间中

下图中，左侧是“串”起来的数据，右侧是空闲的物理空间。把这 “一串儿” 数据放置到物理空间，我们可以选择以下两种方式：

将具有“一对一”关系的数据“线性”地存储到物理空间中，这种存储结构就称为线性存储结构：

• ① 顺序表（如上图左边）：将数据依次存储在连续的整块物理空间中
• ② 链表（如上图右边）：数据分散的存储在物理空间中，通过一根线保存着它们之间的逻辑关系
  • 单链表
  • 双链表
  • 循环单链表
  • 循环双链表

下面详细讲解这两种存储结构