顺序表和链表

https://www.bilibili.com/video/BV1hg411V7Bm?p=53

1）数据结构

结构：结构是指元素之间的关系。

逻辑结构：元素之间的相互关系称为数据的逻辑结构，可划分为线性结构和非线性结构。

附：线性结构是指其中的任意一个元素最多只有一个前驱元素和最多只有一个后继元素，满足这样的关系就是线性结构；

如果它有多个前驱元素或者是多个后继元素，这种情况下就是非线性结构。

常用的线性结构有：线性表，栈，队列、数组和串。

常见的非线性结构有：二维数组，多维数组，广义表，树（二叉树等），图。

存储结构：数据元素及元素之间的存储形式称为存储结构，可分为顺序存储和链接存储两种基本方式。

顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。

链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。

2）顺序表

存储结构：顺序存储结构（顺序表）、链式存储结构（链表）。

顺序存储方式：内存是连续分配的，并且是静态分配的，在使用前需要分配固定大小的空间。

a0	a1	a2	a3	a4	a5	a6	a7

操作：

• 访问第 i 个元素
• 查找是否含有某值（顺序查找）
• 删除第 i 个元素（后面的元素都要往前移动1个位置）
• 第 i 个元素前插入某值（后面的元素都要往后移动1个位置）

含有 n 个元素的线性表采用顺序存储，等概率删除其中任一元素，平均需要移动（）个元素。

解：设有 n 个元素，

a0	a1	a2	......	an-1

删掉的是 a₀，那么就要移动 n-1 个元素；

删掉的是 a₁，那么就要移动 n-2 个元素；

删掉的是 a₂，那么就要移动 n-3 个元素；

......

删掉的是 a_n-1，那么就要移动 0 个元素；

等差数列，平均就是 (首项+末项)/2=(n-1)/2

3）链表

存储结构：顺序存储结构（顺序表）、链式存储结构（链表）

链表（linked-list）存储方式：链表的内存是不连续的，前一个元素存储地址的下一个地址中存储的不一定是下一个元素。访问某结点应找上一结点提供的地址，每一结点有一指针变量存放下一结点的地址。

数据元素的逻辑顺序是通过链表中的指针链接次序实现的。