【考研数据结构知识点详解及整理——C语言描述】第二章 线性表顺序存储结构上的基本操作——顺序表的插入操作
25计算机考研，数据结构知识点整理（内容借鉴了王道408＋数据结构教材），还会不断完善所整理的内容，后续的内容也会不断更新（可以关注），若有错误和不足欢迎各位朋友指出!
目录
一.插入操作
1.算法思想
2.算法描述
3.算法分析
一.插入操作
顺序表的插入运算是指在表的第i(1≤i≤n+1)个位置前插入一个新元素e，使长度为n的顺序表（，…，
，
，…，
）变成长度为n+1的顺序表（
，…，
，e，
，…，
）(其中n为L的表长度)。
1.算法思想
用顺序表作为线性表的存储结构时,由于结点的物理顺微视频 2-2序必须和结点的逻辑顺序保持一致，因此必须将原表中位置n，n-1，…，i上顺序表插入的结点,依次后移到位置n+1，n，…，i+1上，空出第i个位置，然后在该位置插入新结点e。当i=n+1时，是指在顺序表的末尾插人结点,所以无须移动结点，直接将e插人表的末尾即可。
2.算法描述
#define OK 1
#define ERROR O
int InsList( SeqList * L,int i,ElemType e)
/*在顺序表L中第i个数据元素之前插入一个元素e,i的合法取值范围是1≤i≤L->last+2*/
{int k;if((i<1)||(i>L->last+2)) /*首先判断插入位置是否合法*/{printf("插人位置i值不合法");return(ERROR);}if(L->last>=MAXSIZE-1){printf("表已满,无法插人");return(ERROR);}for(k=L->last;k>=i-1;k--) /*为插入元素而移动位置，i-1为最后一个元素移动的下标*/L->elem[k+1]=L->elem[k]; //插入位置及之后的元素后移动L->elem[i-1]=e; //在c语言数组中，第i个元素的下标为i-1，将新元素e放入第i个元素L->last++; //表长增1return(OK);
}3.算法分析
最好情况：当在表尾(i=L->last+2)插人元素时，因为循环的终值大于初值，此时不需要移动元素，可直接在表尾插人e，元素后移语句将不执行，时间复杂度为O(1)。
最坏情况：在表头(i=1)插入元素时，移动元素的语句L->elem[k+1]=L->elem[k]需执行n次，即将表中已存在的n个元素依次后移一个位置才能将e插入，时间复杂度为O(n)。因此，语句L->elem[k+1]=L->elem[k]的语句执行频度与插入位置i有关。
平均情况：设为在长度为n的表中插入一个元素所需移动元素的平均次数，假设
为在第i个元素之前插入元素的概率，并假设在任何位置上插人的概率相等，
=1/(n+1)，i=1，2，n+1，则有
因此，顺序表的插入算法的平均时间复杂度为O(n) 。