数据结构顺序表应用实验报告 数据结构之顺序表上基本运算的实现[8]

数据结构之顺序表上基本运算的实现[8]  

　　算法

　　顺序表的插入运算 时间主要消耗在了数据的移动上 在第i个位置上插入 x 从 ei 到 en 都要向下移动一个位置 共需要移动 n i+ 个元素 设在第i个位置上作插入的概率为Pi 则平均移动数据元素的次数

　　由于 ≤ i≤ n+ 共有 n+ 个位置可以插入 即在等概率情况下pi= / (n+ ) 则

　　因此在顺序表上作插入运算 该算法的时间复杂度为O(n)

　　 顺序表的删除运算

　　顺序表的删除运算是指将表中第 i 个元素从线性表中去掉 删除后使原表长为 n 的线性表 (e e ei ei ei+ en)变为表长为 n 的线性表

　　(e e ei ei+ en) 其中i ≤ i≤ n