线性表的顺序存储结构-软考在线

线性表的顺序存储结构



被考次数： 2次

被考频率：低频率

答错率： 66%

知识难度：

考试要求：掌握

知识路径： > 计算机科学基础 > 常用数据结构 > 线性表及链表 > 线性表

本知识点历年真题试卷分布

>> 试题列表

1）顺序表的概念

线性表的顺序存储结构采用一组连续的存储单元依次存储线性表中的各数据元素。建立一个数组V，线性表的长度为N，V[i]表示第i个分量，第i个分量是线性表中第i个元素a_i在计算机存储器中的映象，即V[i]=a_i。若线性表的第一个元素的存储地址是LOC（a₁)，每个元素用L个存储单元，则表的第i个元素的存储地址为：LOC（a_i）=LOC（a₁）+（i-1）*L。

假设线性表的数据元素的类型为ElemType（在实际应用中，此类型应根据实际问题中出现的数据元素的特性具体定义，如为int、float类型等），线性表的顺序表的C语言描述如下：

从中可以看出，顺序表是由数组data和len两部分组成的。为了反映data和len之间的关系，上述类型定义中将它们说明为结构体类型Sqlist的两个域。这样，Sqlist类型就完全描述了顺序表的组织。

2）基本运算在顺序表上的实现

由于C语言中数组的下标是从0开始的，所以，在逻辑上所指的"第k个位置"实际上对应的是顺序表的"第k-1个位置"。这里仅给出在顺序表上线性表的插入和删除函数。

（1）插入函数。

插入函数的语法如下：

（2）删除函数。

删除函数的语法如下：

3）插入和删除元素算法的时间复杂度分析

（1）插入算法的时间复杂度。

插入算法的时间复杂度的分析如下：

其中p_i是在第i个元素前插入元素的概率，c_i是在第i个元素前插入元素时元素移动次数。

（2）删除算法的时间复杂度。

删除算法的时间复杂度的分析如下：

其中p_i是在第i个元素前删除元素的概率，c_i是在第i个元素前删除元素时元素移动次数。

可见，插入和删除算法的时间复杂度均为O（n）。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5