信息化的本质分享 http://blog.sciencenet.cn/u/Babituo

博文

一种数组、链表、字典相结合的数据结构

已有 329 次阅读 2020-3-2 10:10 |个人分类:虚构开放世界|系统分类:科研笔记|关键词:学者| 鲜度表, 动态数组

刚写的一段程序注释,贴出来鼓励一下自己:——通向开放大世界设计的入口已经找到!


//一种数组、链表、字典相结合的数据结构,

//既有数组索引顺序不变,快速索引的优点,

//又有链表快速维护的点,删除中间元素后,其他元素顺序不改变


//想象有一个动态数组,可不断地向数组中加入元素,

//每加入一个元素,该元素就很方便获得一个代表其空间位置的序号。

//如果在数组中间位置随意删除一个元素,

//那么,以往的数组,其后每个元素的位置就要前移1位,序号要减1。

//因此,元素在数组中的序号,一般不宜作为加入数组中的元素的标识,

//因为,序号会因为对其它元素的增减而发生变化。

//如果非要用数组元素的序号作为外部引用的索引(因为数组索引访问较快)。

//那么,当有元素增减维护之后,索引更新的开销(耗时复杂易错)是非常可观的。

//

//假若数组元素加入时获得的序号和其空间位置的前后并没有关联,

//那么,随意增减数组元素之后,就可以不影响到其他元素的序号。

//但,数组元素序号与空间位置的一致,正是带来数组索引快的原因。

//用这样的序号,就损失了数组按序号索引元素快的优点,也就不是数组下标了。

//

//如何做到让元素获得不受维护操作影响的序号,并按此序号索引如同用数组下标一样快?

//鲜度链的设计,解决了这个问题,代价是:使用更多的空间。


//一个顺序列表记录所有元素。(排队机)

//一个链表记录元素在顺序列表中的位置与序号的关系。(取号机)

//当需要新增元素时,由取号机负责分配一个序号给元素,而不是自动排到排队机的末尾。

//当需要删除元素时,由取号机负责回收这个序号,而不是把后面的元素自动前移。

//如果要按序号访问元素,取号机负责将序号转换为顺序队列的位置号,内部用位置号访问元素。

//所以,在取号机中,还需要增加一个字典,来记录序号和位置的对应关系。

//这样:

//链表负责维护序号的前后关系,知道:前一序号是多少?后一序号是多少?谁在头?谁在尾?

//顺序表负责存储元素,知道:哪个位置放着哪个元素?

//字典负责维护序号和位置的关系,知道:哪个序号对应哪个位置?

//如此一来:

//链表、顺序表,字典封装成了一个新型的动态数组。关键是:位置号和序号分离的设计。

//封装的外观:

//加入元素获得一个序号;提供序号,快速获得元素;删除元素,其他元素序号不变。

//这样:

//可以动态增减元素;元素的序号可以当作外部索引用;用序号获取元素,依然相当的快。


//3D打印原理:

//轮胎已经太多、太杂了,而轮胎设计制造技术已经日新月异,

//找到合用的旧轮胎的开销,已经逐渐大于随手建一个“新轮胎”。

//软件的3D打印时代将至!


真正的创新,必须要做到能让人目瞪口呆!




http://blog.sciencenet.cn/blog-33982-1221327.html

上一篇:虚构开放大世界的第一人称视角
下一篇:智慧城市信息模型——我的探索之路1/5

1 张学文

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-5-29 18:53

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部