顺序表和链表

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

1）数据结构

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

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

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

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

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

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

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

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

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

2）顺序表

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

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

a0	a1	a2	a3	a4	a5	a6	a7

操作：

• 访问第 i 个元素（因为内存是连续分配的，所以知道了首元素的位置，就可以快速定位到第 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）存储方式：链表的内存是不连续的，前一个元素存储地址的下一个地址中存储的不一定是下一个元素。访问某结点应找上一结点提供的地址，每一结点有一指针变量存放下一结点的地址。

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

单链表：

链表中每个元素称结点，每个结点是一个结构体变量，它有若干成员组成：

• 数据部分：可有若干项（整、实、字符、结构体型等）
• 指针变量：通常具有指向自身结构体类型的指针变量，存放下一结点的地址，最后一个结点（表尾）的地址部分为NULL。

操作：

• 访问第 i 个元素（因为在内存中不是连续的，所以必须从前往后依次遍历，直到第 i 个元素）
• 查找是否含有某值（从前往后顺序依次查找，和顺序表在性能方面是一样的）
• 删除第 i 个元素（只需要修改第 i-1 个元素的指针指向第 i+1个元素的地址，操作起来非常快，比顺序表快）
• 第 i 个元素前插入某值（只需要修改第 i-1 个元素的指针指向新插入的元素的地址，然后将新插入的元素的指针指向原先的第 i 个元素地址，操作起来非常快，比顺序表快）

其他概念：

• 尾结点：最后一个有效结点。
• 首结点：第一个有效结点。
• 头结点：第一个有效结点之前的那个结点，存放链表首地址。
• 头指针：指向头结点的指针变量。
• 尾指针：指向尾结点的指针变量。

特点：

• n个结点离散分布，彼此通过指针相联系。
• 除头结点和尾结点外，每个结点只有一个前驱结点和一个后继结点。头结点没有前驱结点，尾结点没有后继结点。
• 头结点并不存放有效数据，只存放链表首地址。其数据类型同首结点类型一样。
• 加头结点的目的是方便对链表的操作，比如在链表头部进行结点的删除、插入。

4）顺序表存储和链式存储性能对比

性能类别	具体项目	顺序存储	链式存储
空间性能	存储密度	=1，更优	<1
	容量分配	事先确定	动态改变，更优
时间性能	查找运算	O(n/2)	O(n/2)
	读运算（定位）	O(1)，更优	O([n+1]/2)，最好情况为1，最坏情况为n
	插入运算	O(n/2)，最好情况为0，最坏情况为n	O(1)，更优
	删除运算	O([n-1]/2)	O(1)，更优

考点1：数据结构的划分

数据结构中的逻辑结构是指数据对象中元素之间的相互关系。

按逻辑结构可将数据结构分为（）。

A、静态结构和动态结构

B、线性结构和非线性结构 √

C、散列结构和索引结构

D、顺序结构和链表结构

题解：

选项D是物理结构、存储结构

考点2：顺序表的特征

若某线性表长度为n且采用顺序存储方式，则运算速度最快的操作时（）。

A、查找与给定值相匹配的元素的位置

B、查找并返回第 i 个元素的值（1≤i≤n） √

C、删除第 i 个元素（1≤i≤n）

D、在第 i 个元素（1≤i≤n）之前插入一个新元素

考点3：链表的特征

以下关于单链表存储结构特征的叙述中，不正确的是（）。

A、表中结点所占用存储空间的地址不必是连续的

B、在表中任意位置进行插入和删除操作都不用移动元素

C、所需空间与结点个数成正比

D、可随机访问表中的任一结点 √

题解：

选项D的描述是顺序表的特征

总结

顺序表和链表

• 数据结构
  • 逻辑结构
  • 存储结构
• 顺序表
  • 相邻元素存储相邻
• 链表
  • 相邻元素存储位置不相邻，通过指针联系
  • 类型：单链表、双向链表和循环链表
  • 其他概念：头结点、首结点、尾结点、头指针、尾指针
• 顺序存储和链式存储性能对比
  • 读/定位（顺序表占优）
  • 查找（顺序表和链表性能相同）
  • 插入（链表占优）
  • 删除（链表占优）