当前位置:鱼C工作室 >数据结构和算法 > 查看文章

线性表4 – 数据结构和算法09

线性表4

 

让编程改变世界

Change the world by program


 

删除操作

 

所以删除算法的思路:

如果删除位置不合理,抛出异常;

取出删除元素;

从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置;

表长-1。

 

实现代码:ListDelete.c

 

现在我们分析一下,插入和删除的时间复杂度。

最好的情况:插入和删除操作刚好要求在最后一个位置操作,因为不需要移动任何元素,所以此时的时间复杂度为O(1)。

最坏的情况:如果要插入和删除的位置是第一个元素,那就意味着要移动所有的元素向后或者向前,所以这个时间复杂度为O(n)。

 

至于平均情况,就取中间值O((n-1)/2)。

按照前边游戏秘籍指导,平均情况复杂度简化后还是O(n)。

 

线性表顺序存储结构的优缺点

 

线性表的顺序存储结构,在存、读数据时,不管是哪个位置,时间复杂度都是O(1)。而在插入或删除时,时间复杂度都是O(n)。

这就说明,它比较适合元素个数比较稳定,不经常插入和删除元素,而更多的操作是存取数据的应用。

那我们接下来给大家简单总结下线性表的顺序存储结构的优缺点:

 

优点:

无须为表示表中元素之间的逻辑关系而增加额外的存储空间。

可以快速地存取表中任意位置的元素。

 

缺点:

插入和删除操作需要移动大量元素。

当线性表长度变化较大时,难以确定存储空间的容量。

容易造成存储空间的“碎片”。

 

线性表的链式存储结构

 

前面我们讲的线性表的顺序存储结构,它最大的缺点就是插入和删除时需要移动大量元素,这显然就需要耗费时间。

那我们能不能针对这个缺陷或者说遗憾提出解决的方法呢?要解决这个问题,我们就得考虑一下导致这个问题的原因!

为什么当插入和删除时,就要移动大量的元素?

 

原因就在于相邻两元素的存储位置也具有邻居关系,它们在内存中的位置是紧挨着的,中间没有间隙,当然就无法快速插入和删除。

经过叽叽呱呱的讨论之后,我们派出几个童鞋跟大家分享一下思路。

 

A童鞋:

让当中每个元素之间都留有一个空位置,这样要插入一个元素时,就不至于要移动了。可一个空位置如何解决多个相同位置插入数据的问题呢?所以这个想法显然不行。

 

B童鞋:

那就让当中每个元素之间都留足够多的位置,根据实际情况制定空隙大小,比如每个元素间留10个空位。

那么问题就显而易见了,造成资源的极大浪费,并且在同一个位置插入11次也不是不可能。

 

C童鞋:

反正要在相邻元素间留多少空间都是有可能不够的,那不如干脆不要考虑相邻位置这个问题了。

哪里有空位就放在哪里,记得在小甲鱼老湿的《零基础入门学习C语言》中讲到的指针刚好可以派上用场。

每个元素多用一个位置来存放指向下一个元素的位置的指针。

这样子从第一个元素可以找到第二个元素,第二个元素可以找到第三个元素,依此类推,所有的元素我们就都可以通过遍历而找到了。

好,太棒了,这个想法灰常好!掌声鼓励!

 

分页阅读: 1 2 下一页
为您推荐

报歉!评论已关闭.