(21)--第二章第三节顺序表的插入和删除.pdf

01顺序表的插入操作

目录02顺序表的删除操作

CONTENTS03算法性能分析

01顺序表的插入操作

顺序表的插入操作

1.问题分析

L=(a,a,a,……,a,a,a,……,a)

123i-1ii+1n

aaa……aaa……a

123i-1ii+1n

e

•在一个线性表L的第i个位置插入新元素(e)，表中

元素的逻辑结构变化如下：

由a,a改变为a,e和e,a

i-1ii-1i

•存储结构如何反映逻辑结构的变化？

哪里需要变化？需要怎样的变化？

插入过程中顺序表的存储结构变化

L

……

位序：12345……i-1ii+1n-1n

……

aaaaa……aaaaa

12345i-1ii+1n-1n

……

下标：01234……i-2i-1in-2n-1

L

ee

……

位序：12345……i-1ii+1n-1nn+1

……

……

a1a2a3a4a5……ai-1aiai+1an-1an

……

下标：01234……i-2i-1in-2n-1n

顺序表的插入操作

2.算法思路

1.检查顺序表L的合法性，i：1~L.length+1；

2.将第i个元素到最后一个元素依次后移一个位

置，注意移动的方向性；

3.在空出的第i个位置上插入新元素e。

算法结束

顺序表的插入操作

3.算法描述