首页 / 软件开发 / 数据结构与算法 / 数据结构：线性表的定义和操作

数据结构：线性表的定义和操作2013-11-26 51cto博客 lilin9105一、线性表定义:

线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，其中的结点，有且仅有一个开始结点（第一元素）没有前驱但有一个后继结点，有且仅有一个终端结点（最后节点）没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列：k1,k2,…,kn，其中k1是开始结点，kn是终端结点。

上述定义可以用下列图像记忆

如一对有序序列（A,B,C,............Z）

图表示为

（^，A（第一节点，没有前驱但有一个后继结点）,B,C ……（其它的结点都有且仅有一个前驱和一个后继结点）……….Z（最后节点,没有后继但有一个前驱结点），^）

总结：凡是符合上图特点的均可以认为是线性表。

二、线性表的顺序表示与链式表示的区别

顺序表

存储图如下

特点:

一、逻辑上相邻的数据元素，物理存储位置也相邻。（逻物一致）

二、顺序表的存储空间需要预先分配。

优点：

（1）方法简单，各种高级语言中都有数组，容易实现。（语言通用性）

（2）不用为表示节点间的逻辑关系而增加额外的存储开销。（内存节约性）

（3）顺序表具有按元素序号随机访问的特点。（逻物一致性）

缺点：

（1）在顺序表中做插入、删除操作时，平均移动表中的一半元素，因此对n较大的顺序表效率低。（操作低效率）

（2）需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。（内存固定性）

链式表

存储图如下