顺序表的插入.

Presentation on theme: "顺序表的插入."— Presentation transcript:

1 顺序表的插入

2 线性表的插入操作是指在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素，就是要使长度为n的线性表 (a1,…,ai-1 ,ai,…,an) 变成长度为n+1的线性表 (a1,…,ai-1 ,b,ai,…,an) 顺序表的插入

3 线性表的插入操作是指在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素，就是要使长度为n的线性表 (a1,…,ai-1 ,ai,…,an) 变成长度为n+1的线性表 (a1,…,ai-1 ,b,ai,…,an) 顺序表的插入 数据元素ai-1 和ai之间的逻辑关系发生了变化。在线性表的顺序存储结构中，由于逻辑上相邻的数据元素在物理位置上也是相邻的，因此，除非i=n+1，否则必须移动元素才能反映这个逻辑关系的变化。

4 数据元素 数据元素 序号 序号 1 12 2 13 3 21 4 24 5 28 6 30 7 42 8 77 1 12 2 13 3 21 4 24 5 顺序表的插入 插入25 25 6 28 7 30 8 42 9 77

5 一般情况下，在第i(1<=i<=n)个元素之前插入一个元素时，需将第n至第i个元素向后移动一个位置，共需要移动n-i+1个元素。 当在第一个元素之前插入一个新的元素时，需要移动n个元素，当在第n个元素之后插入一个新的元素时，需要移动0个元素。 所以，在插入任何位置都是等概率的前提下，顺序表中插入一个新的元素平均需要移动n/2个元素。 顺序表的插入

6 算法思想如下所示： (1)判断插入位置i是否合法，若不合法则返回ERROR； (2)判断顺序表的存储空间是否已满，若满则返回ERROR； (3)将第n至第i个位置的元素一次向后移动一个位置，空出第i个位置； (4)将要插入的新元素e放入第i个位置； (5)表长加1。 插入一个新的元素

7 Status ListInsert_Sq(SqList &L,int i ,ElemType e){ if(i<1 || i>L
Status ListInsert_Sq(SqList &L,int i ,ElemType e){ if(i<1 || i>L.length+1) return ERROR; //i值不合法 if(L.length==MAXSIZE) return ERROR; //当前存储空间已满 for(j=L.length-1;j>=i-1;j--) L.elem[j+1]=L.elem[j]; //插入位置及之后的元素后移 L.elem[i-1]=e; //将新元素e放入第i个位置 ++L.length; //表长增1 return OK; } 参考算法代码

8 该算法的时间复杂度应该是O(n)。另外，上述算法没有考虑顺序表空间的动态扩充问题，如果空间不够，应该怎么办呢？ 如果使用C++的new和delete来申请和释放内存空间的话，应该首先申请一段更大的内容空间，再将顺序表的元素复制到新的空间中去，再释放原来顺序表的空间。