2020重庆中国烟草招聘考试计算机知识点:顺序表的插入

设长度为 n 的顺序表为(a1,a2,…,ai,…,an)，要在顺序表的第i(1≤i≤n)个元素ai之前插入一个新 元素x，插入后得到长度为 n+1的线性表(a1,a2,…,ai-1,x, ai,…,an)，即 (a1,a2,…,ai-1, a’i, a’i+1,…,a’n+1)，其中a’i 为新插入的元素x，a’i+1 为原表中的ai ，其余类推，a’n+1为原表中an 。

一般情况下，要在第i(1≤i≤n)个元素之前插入一个新元素时，首先要从最后一个元素开始，直到第i个元素之间共 n-i+1 个元素依次向后移动一个位置。移动结束时，第i个位置就被空出，然后将新元素插入，插入结束线性表的长度增1。在平均情况下，插入一个新元素，需要移动表中一半的元素。