毕设什么类型网站容易做,湖南网站开发 岚鸿,生活中优秀的产品设计,南阳网站备案摘要#xff1a; 1#xff0c;块状链表的介绍 2#xff0c;块状链表的代码实现#xff08;Java和C#xff09; 1#xff0c;块状链表的介绍 前面我们讲过数组和链表#xff0c;数组具有 O(1)的查询时间#xff0c;O(N)的删除#xff0c;O(N)的插入#xff0c;而链表具… 摘要 1块状链表的介绍 2块状链表的代码实现Java和C 1块状链表的介绍 前面我们讲过数组和链表数组具有 O(1)的查询时间O(N)的删除O(N)的插入而链表具有 O(N)的查询时间O(1)的删除O(1)的插入。应该说这两种数据结构都有优缺点那么这两种数据结构能不能结合起来使用呢当然是可以的结合起来就是我们今天要讲的块状数组。 前面讲到链表时候我们知道链表的每个节点只存储一个数据如果数据量比较多的话查找起来比较麻烦比如我们要查找第10000个节点需要从头开始遍历链表。 如果我们使用块状链表链表的每个节点相当于一个块假如每个块存放1000个数据我们只需要查找10次就可以定位到所在的块然后在块中可以直接获取元素的值。 如果要插入元素找到对应的块即可插入插入的时候只需要移动待插入块中后面的元素其他所有块中的元素不需要移动虽然插入元素的效率比链表低但比起数组还是有很大的提升。 对于块状链表有两点要注意一个是插入的时候如果当前块已经满了没法在插入了可以把该块分裂成两个每个存储原块一半的元素然后在执行插入。 还有就是删除的时候如果删除之后该块的元素个数已经很少了并且他的前一个块或者后一个块中元素个数也非常少这个时候可以考虑两个块进行合并。如果不合并就会退化成链表查找效率大大降低。
