数据结构-线性表

June 25, 2020

线性表

线性表是一种数据结构，其逻辑结构为线性结构；存储结构（实现）有两种：顺序、链式；对应的运算（操作）也略有不同：顺序表示可以随机访问，链式表示可以随机插入删除

线性表的定义和基本操作

线性表是具有相同类型的n（n>=0）个元素的有限序列，其中n为表长，当n=0时，该表为空表

若L命名为线性表，则一般表示为\(L=\left(a_{1}, a_{2}, \dots, a_{i}, a_{i+1}, \dots, a_{n}\right)\)

线性表的特点

表中元素个数有限

表中元素具有逻辑上的顺序性，在序列中各个元素排序有其先后次序

表中元素都是数据元素，每个元素都是单个元素

表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间

表中元素具有抽象性，即讨论元素间一对一的逻辑关系，而不考虑元素究竟表示的内容

线性表是一种逻辑结构，表示元素之间一对一相邻的关系

线性表的基本操作

9种基本操作：初始化、销毁、增删改查、遍历、是否为空、获取长度

InitList(8L)：初始化表。构造一个空的线性表 DestroyList（&L）：销毁操作。销毁线性表，并释放线性表所占用的内存空间。 LocateElem（L,e)按值查找操作。在表中查找具有给定关键值得元素。 GetELem(L,i) 按位查找操作。获取表中第个位置的元素的值。 Listlnsert(&L,i,e）插入操作。在表中的第个位置上插入指定元素e插 LIstDelete（&L, &e）：删除操作。删除表L中第个位置的元素，并用e返回删除元素的值。 Printlist（L)：输出操作。按前后顺序输出线性表的所有元素值。 Empty（L）：判空操作。若为空表，则返回TRUE否则返回ALSE。 Length（L）：求表长。返回线性表的长度，即L中数据元素的个数。

线性表的顺序表示

顺序表的定义

线性表的顺序存储又称顺序表

一组地址连续存放的存储单元依次存放线性表的元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。

数组静态分配，数组动态分配（使用指针）

顺序表的基本操作

插入、删除、按值查找

线性表的链式表示

线性表的链式存储，简称链表

通过一组任意的存储单元来存储线性表中的数据元素，通过指针实现线性逻辑关系。

单链表

单链表的定义

带头节点的单链表和不带头节点的单链表

带头节点单链表优点：链表的第一个位置和其他位置的操作统一空表和非空表的操作统一

单链表的基本操作

建立：头插、尾插

查找：按序号查找&按值查找

插入：按序号查找+插入（前插/后插）

前插与后插的转换：插入前交换节点内容

删除：按序号查找+删除

删除给定节点*p:交换节点内容+删除

表长

双链表

双链表可以看作是：一个带头节点的单链表+另一个不带头节点的单链表；所以其头节点并不能统一操作。

插入

删除

循环链表

循环单链表

统一插入删除操作

判空

循环双链表

统一插入删除操作；找尾节点更快

判空

静态链表

使用数组实现链表

顺序表和链表的对比

相同点

	顺序表	单链表
逻辑结构	属于线性表	属于线性表

不同点

	顺序表	单链表
存取方式	顺序存取、随机存取（计算位置直接存取）	顺序存取
物理结构（数据的存储）	数据元素	数据元素
物理结构（数据之间的关系）	数据元素之间的相邻性	下一个元素的指针
操作（插入，删除）	O(n)	插入删除位置指针已知O(1)，插入删除位置指针未知O(n)
操作（查找）	按值查找O(n),按序号查找O(1)	按值、按序号查找都是O(n)
内存空间	预分配（静态分配浪费空间，动态分配效率低）	按需分配，但指针使用额外空间

怎样选择线性表

		顺序表	单链表
存储	规模难以估计		*
存储	存储密度大	*
效率	按序号访问	*
效率	插入和删除操作多		*
环境	基于数组	*
环境	基于指针		*

一些操作的实现

求最大最小值

置逆

顺序表置逆

单链表置逆

将头部的节点依次插入到原尾节点后面

两路归并

合并两个有序线性表