数据结构-线性表

线性表是最基本、最简单、也是最常用的一种数据结构。

简介

定义

线性表是数据结构的一种，一个线性表是 n(n>=0) 个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。

在稍复杂的线性表中，一个数据元素可由多个数据项(item)组成，此种情况下常把数据元素称为记录(record)，含有大量记录的线性表又称文件(file)。

线性表中的个数 n 定义为线性表的长度，n=0 时称为空表。在非空表中每个数据元素都有一个确定的位置。

线性表的相邻元素之间存在着序偶关系，除第一个元素外，每个元素有且仅有一个直接前驱，除最后一个元素外，每个元素有且仅有一个直接后继。

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储)，但是把最后一个数据元素的尾指针指向了首位结点。

分类

在数据结构逻辑层次上细分，线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的线性表，可以自由的删除或添加结点。受限线性表主要包括栈和队列，受限表示对结点的操作受限制。

优点

线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。

特点

线性表具有以下特点：

• 集合中元素个数有限且数据类型相同。
• 集合中必存在唯一的一个第一元素和最后元素。
• 除最后一个元素之外，均有唯一的后继(后件)。
• 除第一个元素之外，均有唯一的前驱(前件)。

存储结构

线性表是线性结构的一种数据结构，线性表有两种，分别是顺序存储结构的线性表(叫做顺序表)和链式存储结构的线性表(叫做链表)。

顺序存储结构

顺序存储结构指的是用一段地址连续的存储单元依次存储线性表的数据元素。它以物理位置相邻来表示线性表中数据元素间的逻辑关系，可随机存取表中任一元素。

顺序表是指顺序存储结构的线性表，使用数组实现，一组地址连续的存储单元，数组大小有两种方式指定，一是静态分配，二是动态扩展。顺序表表现在物理内存中，也就是物理上的存储方式，事实上就是在内存中找个初始地址，然后通过占位的形式，把一定的内存空间给占了，然后把相同数据类型的数据元素依次放在这块空地中。注意，这块物理内存的地址空间是连续的。

线性表的顺序存储结构，在存、取数据时，时间复杂度是 O(1)；而在插入或者删除时，时间复杂度是 O(n)。也就是说线性表的顺序存储结构比较适合存取数据，不适合经常插入和删除数据的应用。

优点：

• 无需为了表示表中元素之间的逻辑关系而增加额外的存储空间(相对于链式存储而言)；
• 可以快速的存取表中任意位置的元素；
• 存储密度大(等于1)，存储空间利用率高。

缺点：

• 插入和删除操作需要移动大量的元素；
• 当线性表长度变化较大时，难以确定存储空间的容量；
• 容易造成存储空间的“碎片”(因为线性表的顺序存储结构申请的内存空间都以连续的，如果因为某些操作导致某个部分出现了一小块的不连续内存空间，因为这一小块内存空间太小不能够再次被利用/分配，那么就造成了内存浪费，也就是“碎片”)。

链式存储结构

链式存储结构指的是用一组任意的存储单元存储线性表中的数据元素。它的存储单元可以是连续的，也可以是不连续的。

在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)，这两部分信息组成数据元素的存储映像，称为结点。它包括两个域：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域(指针域中存储的信息称为指针或链)。

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以存在内存中未被占用的任意位置。与顺序存储相比，允许存储空间不连续，插入删除时不需要移动大量的元素，只需修改指针即可，但查找某个元素，只能从头遍历整个链表。

线性表的链式存储结构，在查找数据时，时间复杂度是 O(n)；而在插入或者删除时，时间复杂度是 O(1)。也就是说线性表的链式存储结构比较适合插入或者删除数据，不适合经常查找数据的应用。

优点：

• 无需分配存储空间，只要有就可以分配，元素个数不受限制；
• 可以快速插入或者删除元素。

缺点：

• 查找操作需要从表头开始查找；
• 存储密度小(小于1)，存储空间利用率低。

总结

存储方式	顺序存储结构	链式存储结构
内存分配	用一段连续的存储单元依次存储线性表的数据元素	用一组任意的存储单元存放线性表的元素
空间性能	需要预分配存储空间，分大了浪费，小了容易发生上溢	不需要分配存储空间，只要有就可以分配，元素个数不受限制
时间性能	查找 O(1)、插入和删除 O(n)	查找 O(n)、插入和删除 O(1)
存储密度	大	小
应用	顺序表	链表

结构特点

线性结构具有以下特点：

1. 均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。
2. 有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个”的数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素(直接前驱)和后面均只有一个数据元素（直接后继）。