|||
刚写的一段程序注释,贴出来鼓励一下自己:——通向开放大世界设计的入口已经找到!
//一种数组、链表、字典相结合的数据结构,
//既有数组索引顺序不变,快速索引的优点,
//又有链表快速维护的优点,删除中间元素后,其他元素顺序不改变
//想象有一个动态数组,可不断地向数组中加入元素,
//每加入一个元素,该元素就很方便获得一个代表其空间位置的序号。
//如果在数组中间位置随意删除一个元素,
//那么,以往的数组,其后每个元素的位置就要前移1位,序号要减1。
//因此,元素在数组中的序号,一般不宜作为加入数组中的元素的标识,
//因为,序号会因为对其它元素的增减而发生变化。
//如果非要用数组元素的序号作为外部引用的索引(因为数组索引访问较快)。
//那么,当有元素增减维护之后,索引更新的开销(耗时复杂易错)是非常可观的。
//
//假若数组元素加入时获得的序号和其空间位置的前后并没有关联,
//那么,随意增减数组元素之后,就可以不影响到其他元素的序号。
//但,数组元素序号与空间位置的一致,正是带来数组索引快的原因。
//用这样的序号,就损失了数组按序号索引元素快的优点,也就不是数组下标了。
//
//如何做到让元素获得不受维护操作影响的序号,并按此序号索引如同用数组下标一样快?
//鲜度链的设计,解决了这个问题,代价是:使用更多的空间。
//一个顺序列表记录所有元素。(排队机)
//一个链表记录元素在顺序列表中的位置与序号的关系。(取号机)
//当需要新增元素时,由取号机负责分配一个序号给元素,而不是自动排到排队机的末尾。
//当需要删除元素时,由取号机负责回收这个序号,而不是把后面的元素自动前移。
//如果要按序号访问元素,取号机负责将序号转换为顺序队列的位置号,内部用位置号访问元素。
//所以,在取号机中,还需要增加一个字典,来记录序号和位置的对应关系。
//这样:
//链表负责维护序号的前后关系,知道:前一序号是多少?后一序号是多少?谁在头?谁在尾?
//顺序表负责存储元素,知道:哪个位置放着哪个元素?
//字典负责维护序号和位置的关系,知道:哪个序号对应哪个位置?
//如此一来:
//链表、顺序表,字典封装成了一个新型的动态数组。关键是:位置号和序号分离的设计。
//封装的外观:
//加入元素获得一个序号;提供序号,快速获得元素;删除元素,其他元素序号不变。
//这样:
//可以动态增减元素;元素的序号可以当作外部索引用;用序号获取元素,依然相当的快。
//3D打印原理:
//轮胎已经太多、太杂了,而轮胎设计制造技术已经日新月异,
//找到合用的旧轮胎的开销,已经逐渐大于随手建一个“新轮胎”。
//软件的3D打印时代将至!
真正的创新,必须要做到能让人目瞪口呆!
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-11-22 14:01
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社