大话数据结构-7 线性表概念

定义

零个或多个数据元素的有限序列。
线性表元素的个数n (n≥0)定义为线性表的长度，当n=0时，称为空表。

线性表的抽象数据类型

线性表的顺序存储结构

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
可以用一维数组来实现顺序存储结构。

数据长度与线性表长度区别

数组的长度是存放线性表的存储空间的长度,存储分配后这个量是一般是不变的。
线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。
在任意时刻，线性表的长度应该小于等于数组的长度。
地址计算方法：数组下标是从0开始的。

随机存取结构

线性表中可以算出任意位置的地址，都是相同，也就是一个常数，用时间复杂度表示为O(1)。通常把这一特点的存储结构称为随机存取结构。
线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O(1);而插入或删除时，时间复杂度都是O(n)。

线性表顺序存储结构的优缺点

线性表的链式存储结构

顺序表的缺点：插入删除需要移动大量的元素，很耗费时间。

线性表链式存储结构定义

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。

现在链式结构中，除了要存数据元素信息外，还要存储它的后继元素的存储地址。

我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像，称为结点(Node)。

n个结点(a;的存储映像)链结成一个链表，即为线性表(a1, az, .，. an)的链式存储结构，因为此链表的每个结点中只包含-一个指针域, 所以叫做单链表。

链表中第一 个结点的存储位置叫做头指针。

为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息

单链表结构与顺序存储结构优缺点

静态链表

用数组描述的链表叫做静态链表。见本站静态链表文章。

静态链表优缺点

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

双向链表

双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

总结