数据结构重读 – 线性表的顺序存储

1、线性表也可以用顺序表示实现,即用一组地址连续的存储单元依次存储线性表的数据元素。特点是ai和ai+1位于相邻的存储单元上,只要确定了存储线性表的起始位置,任意元素都可以随机存取。

2、LOC(ai) = LOC(a1)+(i-1)*l

3、通常用数组来描述数据结构中的顺序存储结构。

4、线性表的顺序存储不同于数组的地方是:数组的大小是静态不动的;而线性表类似于C++中的vector,如果存储空间不够,会自动的增加内部空间,而这一切,对外部用户是透明的。

5、顺序存储的随机访问效率很高O(1),但插入是个大问题,除非i=n+1,否则必须移动i之后的所有元素。一般来说,倒着写for(从n~i)会简单一些(插入应从后往前拷贝)。

6、同理,删除第i个元素,需要将第i+1至第n个元素依次向前移动一个位置(删除可以从pos从前往后copy)。

7、对于线性表的顺序存储,插入和删除平均都要费n/2的操作。

8、线性表的顺序存储,基础操作如下(初始化、插入、删除等):

9、

 

Leave a Reply

Your email address will not be published.