文档文本内容
本节内容
顺序表
插入
删除
王道考研/CSKAOYAN.COM知识总览
王道考研/CSKAOYAN.COM顺序表的基本操作 插入
—— 内存
用存储位置的相邻来体现
数据元素之间的逻辑关系
位序
ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。 adata[0]
bdata[1]
用静态分配方式
实现的顺序表
c ddata[2]
edata[3]
fdata[4]
data[5]
data[6]
注:本节代码建立在顺序表的“静态分配”实现方式之上,“动态分配” 也雷同。
data[7]
data[8]
逻辑结构: a b d e f data[9]
length
= 6
= 5
c
王道考研/CSKAOYAN.COM顺序表的基本操作 插入
—— 内存
1data[0]
2data[1]
3 4data[2]
基本操作:在L的
位序 i 处插入元素e 5data[3]
6data[4]
data[5]
data[6]
注意位序、数组下
data[7]
标的关系,并从后
3 data[8]
面的元素依次移动
data[9]
基操——让自己实现
length
= 6
= 5
的数据结构可以让别
人很方便地使用
王道考研/CSKAOYAN.COM顺序表的基本操作 插入
—— 内存
data[0]
data[1]
data[2]
data[3]
data[4]
data[5]
data[6]
data[7]
data[8]
data[9]
length
= 10
好的算法,应该具有“健壮性”。
能处理异常情况,并给使用者反馈
王道考研/CSKAOYAN.COM插入操作的时间复杂度
关注最深层循环语句的执行
次数与问题规模 n 的关系 问题规模 n = L.length (表长)
最好情况:新元素插入到表尾,不需要移动元素
i = n+1,循环0次;最好时间复杂度 = O(1)
最坏情况:新元素插入到表头,需要将原有的 n 个元素全都向后移动
i = 1,循环 n 次;最坏时间复杂度 = O(n);
!
平均情况:假设新元素插入到任何一个位置的概率相同,即 i = 1,2,3, … , length+1 的概率都是 p =
"#!
i = 1,循环 n 次;i=2 时,循环 n-1 次;i=3,循环 n-2 次 …… i =n+1时,循环0次
$($#!) ! $
平均循环次数 = np + (n-1)p + (n-2)p + …… + 1⋅p = = 平均时间复杂度 = O(n)
' "#! '
王道考研/CSKAOYAN.COM顺序表的基本操作 删除
——
内存
adata[0]
ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素,
bdata[1]
并用e返回删除元素的值。
cdata[2]
ddata[3]
edata[4]
fdata[5]
data[6]
逻辑结构: a b c d e f
data[7]
data[8]
data[9]
length
= 6
= 5
王道考研/CSKAOYAN.COM内存
顺序表的基本操作 删除
——
1data[0]
2data[1]
3data[2]
4data[3]
5data[4]
6data[5]
注意位序、数组下
data[6]
标的关系,并从前 复制
data[7]
面的元素依次移动
如果参数没 data[8]
有加引用符
data[9]
号,会怎样?
length
== 56
3 e
王道考研/CSKAOYAN.COM删除操作的时间复杂度
关注最深层循环语句的执行
次数与问题规模 n 的关系 问题规模 n = L.length (表长)
最好情况:删除表尾元素,不需要移动其他元素
i = n,循环 0 次;最好时间复杂度 = O(1)
最坏情况:删除表头元素,需要将后续的 n-1 个元素全都向前移动
i = 1,循环 n-1 次;最坏时间复杂度 = O(n);
!
平均情况:假设删除任何一个元素的概率相同,即 i = 1,2,3, … , length 的概率都是 p =
"
i = 1,循环 n-1 次;i=2 时,循环 n-2 次;i=3,循环 n-3 次 …… i =n 时,循环0次
$($(!) ! $(!
平均循环次数 = (n-1)p + (n-2)p + …… + 1⋅p = = 平均时间复杂度 = O(n)
' " '
王道考研/CSKAOYAN.COM知识回顾与重要考点
如果不加“&”,则被调用函数
中处理的是参数数据的复制品
王道考研/CSKAOYAN.COM