线性表及其顺序存储结构

01-数据结构与算法 飞快学 481浏览

线性表有两种存储结构:顺序存储结构和链式存储结构。

线性表的定义

线性表由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。线性表是由n(n≥0)个数据元素组成的一个有限序列,表中的每一个数据元素,除了第一个外,有且只有一个前件,除了最后一个外,有且只有一个后件。线性表中数据元素的个数称为线性表的长度。线性表可以为空表。

线性表有两种存储结构:顺序存储结构和链式存储结构。

线性表的顺序存储结构的特点

线性表的顺序存储结构具有两个基本特点:(1)线性表中所有元素所占的存储空间是连续的;(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

最大的优势是随机存取:其前后件两个元素在存储空间中是紧邻的,且前件元素一定存储在后件元素的前面,可以通过计算机直接确定第i个结点的存储地址。

线性表顺序存储的缺点 (1)插入或删除的运算效率很低,插入或删除数据元素时需要移动大量的数据元素;(2)线性表的存储空间不便于扩充,不便于对存储空间的动态分配。

顺序表的插入、删除运算

顺序表的插入运算:在一般情况下,要在第i(1≤i≤n)个元素之前插入一个新元素时,首先要从最后一个(即第n个)元素开始,直到第i个元素之间共n-i+1个元素依次向后移动一个位置,移动结束后,第i个位置就被空出,然后将新元素插入到第i项。插入结束后,线性表的长度就增加了1。顺性表的插入运算时需要移动元素,在等概率情况下,平均需要移动n/2个元素。

顺序表的删除运算:在一般情况下,要删除第i(1≤i≤n)个元素时,则要从第i+1个元素开始,直到第n个元素之间共n-i个元素依次向前移动一个位置。删除结束后,线性表的长度就减小了1。顺性表的删除运算时也需要移动元素,在等概率情况下,平均需要移动(n-1)/2个元素。

小结:顺序表的插入、删除运算不方便。