顺序表和链式表存储结构研究
2013-08-22梁少刚
科技视界 2013年12期
梁少刚
(宝鸡职业技术学院,陕西 宝鸡721000)
1 线性表的概述
线性表(Linear list)是最简单且最常用的一种数据结构。这种结构具有下列特点:存在一个唯一的没有前驱的(头)数据元素;存在一个唯一的没有后继的(尾)数据元素;此外,每一个数据元素均有一个直接前驱和一个直接后继数据元素。
1.1 线性表的逻辑结构
线性表是有限元素(a1,a2,a3,…,an)有序序列的集合,a1,a2,…,an都是完全相同结构的数据类型,同时它们之间的排列严格有序,其中任何元素都对应唯一的前驱以及唯一的后继。这样一个序列可以有查询、删除、插入队列任何位置的数据操作。
1.2 线性表的物理结构
顺序线性表是用一定大小的数据来存放线性表,数组长度代表线性表的长度,元素在数组的位置代表元素在线性表的位置。但对数组中元素不能跳跃插入,因为线性表中元素是顺序且连接着的,不像数组中间可以空元素。同时删除元素时,必须大量移动剩下的元素,因为必须实现其连续性。插入元素同样需要大量移动数据。因此这样存储的运行效率并不够高。所以对于有着频繁插入和删除运算的线性表,是不适合采用顺序存储的。
链式线性表是通过动态分配,分配物理上不一定相邻的存储单元。为表示他们的连续性连接性,再在分配这个存储单元时,附加一部分存储单元———指针域来指出这个元素的后继元素的存储地址。链式存储结构又分为单链表、循环链表和双向链表等。这样的链式存储多节省了操作的时间,但需要更多的存储空间。……
登录APP查看全文
