浅谈线性表

线性表是最基本、最简单、也是最常用的一种数据结构，一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。

在稍复杂的线性表中，一个数据元素可由多个数据项（item）组成，此种情况下常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）。线性表中的个数n定义为线性表的长度，n=0时称为空表。在非空表中每个数据元素都有一个确定的位置，如用ai表示数据元素，则i称为数据元素ai在线性表中的位序。

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

线性表主要分为两大类：顺序表和链表

一、顺序表

顺序表是指用一组地址连续的存储单元依次存储线性表中的数据元素的线性表。

因为这种方式与高级程序设计语言中一维数组的表示和实现相一致，所以也称为数组表示法。采用顺序表表示的线性表，表中逻辑位置相邻的数据元素将存放到存储器中物理地址相邻的存储单元之中，表中元素的逻辑关系与存储顺序(物理关系)相符，换言之，顺序表中数据元素的逻辑关系是以其在存储结构中的物理(位置)关系来表示的。

因此，在顺序表中，可以根据顺序表中数据元素的位序，随机访问表中的任一元素，即顺序表是一种随机存取的存储结构。

二、链表

链表就是指采用链式存储结构表示和实现的线性表。

链表的特点是采用一组任意的存储单元来存放线性表中的数据元素，这些存储单元可以是连续的，也可以是不连续的。 在链表中，数据元素之间的逻辑关系并不依赖其对应的存储地址，而是通过设置专门用于指示数据元素之间逻辑关系的指针来描述。

 因此，在链表中的每个数据元素是由用于存放代表其本身信息的数据域和用于存放指示数据元素之间逻辑关系的指针域两部分组成的，数据元素的这种特殊存储方式，称为 结点(Node) 。

根据链表结点中包含指针域的指针个数、指针指向和连接方式，可将链表分为线性链表、循环链表、双向链表、多重链表、十字链表、二叉链表、邻接表、邻接多重表等，其中线性链表、循环链表和双向链表用于实现线性表的链式存储结构，其他形式则用于实现扩展线性结构(数组和广义表等)或非线性结构(树、图等)。

线性表作为数据结构中的重要组成成员，线性表的逻辑结构简单，便于实现和操作，因此，线性表在实际应用中得到了广泛应用。在本站的数据结构和算法教程中还有对许多的优秀的数据结构全面解析，让我们能够快速掌握各种数据结构。