1、线性表的逻辑结构的基本特征
线性结构是一个数据元素的有序(次序)集
1).集合中必存在唯一的一个“第一元素”;
2).集合中必存在唯一的一个“最后元素”
3).除最后元素之外均有唯一的后继;
4).除第一元素之外,均有唯一的前驱
2、线性表的顺序存储实现
顺序表是线性表的顺序存儲结构。用一组地址连续的存储单元依次存储线性表的元素
逻辑顺序与物理顺序一致
属随机存取的存储结构,即存取每个元素所花时间相等
假设线性表中每个元素需占用c个存储单元计算结点存储地址公式:
顺序表上实现基本运算及时间复杂度分析。
假设在第 i 个元素之前插入的概率为 pi则在长度为n的线性表中插入一个元素所需移动元素次数的期望值为:
若假定在线性表中任何一個位置上进行插入的概率都相等,则移动元素的期望值为:
插入算法的平均时间复杂性为 平均时间复杂性量级为O(n)。
假设删除第 i 個元素的概率为qi , 则在长度为n的线性表中删除一个元素所需移动元素次数的期望值为:
若假定在线性表中任何一个位置上进行删除的概率都是相等的则移动元素的期望值为:
删除算法的平均时间复杂性为
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。