阅读 52

顺序表的插入删除算法移动元素次数分析

设:L.elem[0..maxleng-1] 中有 legth 个元素,

在 L.elem[i-1] 之前插入 新元素 e ,1<=i<=length

例:i = 3,e = 6,length = 6

 

如上图,我们需要在第三个元素,也就是 "8" 之前插入 “6”,

因此需要将 “8”,“20“,”30”,“35” 这些元素统统后移一格

如下图:

--------------------------------------------------分---------------界---------------线------------------------------------------------------------

 

 

 也就是将,从第 i-1 个元素开始,统统向后移动一位,然后将元素 “x” 插入 第 "i-1" 个位置,即下图:

 

移动元素下标范围:i - 1 ~ n - 1 或 i - 1 ~ L.length - 1

 

元素移动方向为:是从 最后一个元素 an 开始,一直到 ai 处,依次向后移动一个位置,而非从 第 ai 开始。

基于此思想,进行一个动态表插入与静态表插入的对比:

算法①:静态分配线性表空间,用指针指向被操作的线性表(下图)

算法思想:
① 判断插入的位置是否合理即:if ( i<1 || i>L.length+1 ) return ERROR; 

i 这里指的是第几个元素,而非下标。

因此,i<1这里即插入位置不合理。(我们无法在 第0个 元素前插入,因为它不存在)

L.length + 1 :我们为了插入元素顺利,因此让线性表占用存储空间为元素数量+1,

体现在这里就是 L.length + 1,i 超出这个值,则无法插入(没位置了,添加不进去)

② 判断表长是否达到分配空间的最大值,

if (L.length>=maxleng) return OVERFLOW

如果 线性表长度 大于等于 最大长度,这里是从线性表长度的角度表达规则。

③ 从线性表中的最后一个位置到插入位置的所有元素,依次往后移动一个元素的位置,这样给待插入元素留出一个空位置

 

 

即:L.elem[j+1] = L.elem[j]; //将原位置元素赋值给新位置

④ 线性表长度变量 + 1,L.length ++;

⑤ return ok,返回结果,表示插入成功。

 

关于 for 循环部分:

1. 从最后一个元素开始,依次向后移动一位

2. j = L.length - 1 // L.length 即线性表长度,L.length - 1 即线性表中 最后一位元素 的 下标

3. j >= i-1 为 for 循环的条件,当下标变成 i - 1 时停止 for 循环。在满足 j>=i-1 条件的情况下,才会进行for 循环,不满足这个条件,就停止 for 循环,同时 “;”是在 L.elem[j+1] = L.elem[j] 这个代码后,因此 for 循环在运行过程中,它的运行范围就止步于此。

4. L.elem[j+1] = L.elem[j] 将下标为 j 的元素,赋值到下标为 j+1 的位置。

--------------------------------------------------分---------------界---------------线------------------------------------------------------------

动态 分配线性表空间,用 引用参数 表示被操作的线性表

伪代码部分(如下图)

 

 

如果插入元素使得表长超过原来分配的空间大小时,这时候可以使用:

 

 

newbase = (ElemType *) realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));

寻找更大片的连续地址空间,但极端情况下可能发生扩容失败。

如果找到新的更大片的连续地址空间后,我们要将线性表的基地址改成一个新地址。

代码讲解:

L.length:当前数据元素的个数(即线性表的长度)

L.listsize:当前分配的存储容量

ElemType *newbase:定义一个Elemtype类型的指针变量

关于 realloc :

语法 指针名=(数据类型*)realloc(要改变内存大小的指针名,新的大小)
代码 newbase = (ElemType *) realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType))
代码含义 之前定义了一个结构体,名为ElemType, 现在使用realloc()函数重新分配一块内存。这个内存的大小为 (L.lestsize+LISTINCREMENT) ElemType结构体。
Elemtype * 声明下面的变量是指针,指向Elemtype类型
LISTINCREMENT 线性表或者链表存储空间增量
备注 新的大小可大可小(如果新的大小大于原内存大小,则新分配部分不会被初始化;如果新的大小小于原内存大小,可能会导致数据丢失)
功能 先判断当前的指针是否有足够的连续空间,如果有,扩大mem_address指向的地址,并且将mem_address返回,如果空间不够,先按照newsize指定的大小分配空间,将原有数据从头到尾拷贝到新分配的内存区域,而后释放原来mem_address所指内存区域(注意:原来指针是自动释放,不需要使用free),同时返回新分配的内存区域的首地址。即重新分配存储器块的地址。
返回值 如果重新分配成功则返回指向被分配内存的指针,否则返回空指针NULL。
注意 当内存不再使用时,应使用free()函数将内存块释放。

 

 

 

 

 

 

 

 

 

 

 

L.elem = newbase:新基地址,

L.listsize += LISTINCREMENT:增加存储容量

for 循环代码块:从最后一个开始,到第 i 个元素,挨个往后挪

L.elem[i - 1] = e:将元素 "e" 赋值给被空出来的 原第 i-1 个元素 的存储位置

L.length++:线性表长度加一

--------------------------------------------------分---------------界---------------线------------------------------------------------------------

插入操作  移动元素次数  的分析

 

 

总之,在一个线性表中,往里面插入一个元素的时候,它移动元素的长度的数学期望值,是等于线性表长度的一半。

--------------------------------------------------分---------------界---------------线------------------------------------------------------------

在线性表中删除元素,同样也存在移动元素的过程,只是这个移动方向和插入元素时的移动方向是相反的。

a1 a2 ... ai-1 ai ai+1 ...   an // //

 

 

比如对上边这个线性表中的元素 “ai” 进行删除时,需要把 ai+1 一直到 an ,依次向原 ai 位置移动一格。变成如下:

a1 a2 ... ai-1 ai+1 ...   an  // //  

 

 

删除代码如下:

 

 代码中算法基本思想:

① 判断删除元素的下标是否存在。关于此处用 ->

-> 是指针操作符 如果 L 是一个结构实例的指针,要用 -> 访问结构里的变量,而不能用点。
. 是结构操作符 如果L 是一个结构的实例而非指针,只能用点而不能用 -> 

 

 

 

② 用一个 for 循环来移动元素,移动元素下标范围为 i 到 length - 1

③ 修改表长为原表长减一

--------------------------------------------------分---------------界---------------线------------------------------------------------------------

删除操作及移动元素次数的分析:

删除元素的位置只有 n 中情形。

 

 --------------------------------------------------分---------------界---------------线------------------------------------------------------------

一个思考题:顺序存储结构的线性表插入一个元素算法的时间复杂度是平方数量及的吗?

原文:https://www.cnblogs.com/AronKeener/p/14639449.html

文章分类
代码人生
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 gxwowoo@163.com 举报,一经查实,本站将立刻删除。
相关推荐