线性表

逻辑结构

线性表是n $n \leq 0$ 个数据元素的有限序列，在表中，元素之间存在着线性的逻辑关系；表中有且仅有一个开始结点；有且仅有一个终端结点；除开始结点外，表中的每个结点均只有一个前驱结点，除终端结点外，表中的每个结点均只有一个后继结点。根据它们之间的关系可以排成一个线性序列,记作 $a_0,a_1,a_2,\cdots, a_n$

线性表中数据元素的个数定义为线性表的长度，称为表长

特点

$\textcircled 1$ 同一性。线性表由同类数据元素组成，每一个 $a_i$ 必须属于同一数
$\textcircled 2$ 有穷性。线性表由有限个数据元素组成，表长度就是表中数据元素的个数
$\textcircled 3$ 线性表中相邻数据元素之间存在着序偶关系

ADT LinearList {    数据元素： D = {$a_i \in  D_0, i = 1,2,..., n, n \geq 0, D_0$为某一个数据对象}    结构关系： S = {$<a_i, a_{i+1}>a_i, a_{i+1} \in D_0,  i = 1,2,..., n $}    基本操作：        InitListL        DestoryListL        ClearListL        EmptyListL        ListLengthL        LocalteL,e        GetDataL,i        InsertDataL,i, el        DeleteDataL,i}

顺序存储

在计算机内可以用不同的方法来存储数据信息，最常用的方法就是顺序存储。顺序存储是指在内存中用一块地址连续的存储空间按顺序存储线性表的各个数据元素。采用顺序存储结构的线性表称为顺序表表顺序表中逻辑上相邻的数据元素在物理存储位置上也是相邻的。

如图所示

设第一个元素存放地址为 $OCa_0$ , 每个元素占用的空间大小为 $d$ 个字节，则元素 $a_i$ 的存放地址为 $LOCa_i = LOCa_0 + d * i - 1$

特点：是用物理位置上的相邻来表示数据元素之间逻辑相邻的关系，存储密度高，且能随机存取数据元素。但线性表在进行插入、删除时需要移动大量数据元素，运行效率低，而且顺序表需要预先分配存储空间，若表长*变化较大，则存储规模难以事先确定，估算过大会造成存储空间的浪费

链式存储

链表是通过一组任意的存储单元来存储线性表中的数据元素。这组存储单元可以是连续的，也可以是不连续的。为建立起数据元素之间的线性关系，对于每个数据元素，除了存放数据元素自身的信息外，还必须有包含指示该元素直接后继元素存储位置的信息，这两部分信息组成一个结点。也就是说，链表中的每个结点都至少包括两个域，一个域存储数据元素信息，称为数据域；另一个域存储直接后继元素的地址，称为指针域

n个元素的线性表通过每个结点的指针域连接成了一条“链子”，故形象地称之为“链表”。因为每个结点中只有一个指向其直接后继的指针，所以称其为单链表

在单链表的基础上，将其最后一个结点的指针域指向该链表头结点，使得链表头尾结点相连，就构成了单循环链表

在单链表中的每个结点中再加一个指向直接前驱的指针域，用这种结点组成的链表称为双向链表

静态链表是用数组实现的，每个数据元素除了存储数据信息外，还要存储逻辑相邻的下一个数据元素在数组中的位置。

实现参考动态数组

顺序表和链表的比较

顺序表优点

用数组存储数据元素，操作方法简单，容易实现
无须为表示结点间的逻辑关系而增加额外的存储开销。#
存储密度高
顺序表可按元素位序随机存取结点

顺序表缺点

做插入、删除操作时，须大量地移动数据元素，效率比较低
要占用连续的存储空间，存储分配只能预先进行。如果估计过大，可能导致后部大量空间闲置；如果预先分配过小，又会造成数据溢出