链表结构入门

今天把前不久学到的一个很有用的算法——链表结构(linked list)——写下来,以飨后来者。

在处理数组时,如果想在某个数组中插入一个或多个数字,或者你想更换某几个数字的顺序时,如果用普通的方法你会发现非常麻烦,几乎是牵一发而动全身。数组规模小时,计算量还能够在掌控中,但是如果数组非常庞大,你就会发现情况变得非常麻烦了。

然而,一个链表结构轻松解决以上种种问题,让你不再有困扰生活变得so easy哦也~

比如我们有一个数组 A=[a1,a2,a3,a4,……,a1000]

正常读取顺序应该是从a1一直顺读到a1000,但因为剧情需要,某些角色要先行一步,比方说a1000要跑到第一个去,a88要跟a2换个位子,a50和a51之间要插入一个a1001,最后得到数组B,我们该怎么办?

“上链表~!” 决定一个(一维)数组的结构需要两个要素:数据,顺序。

链表存储的就是数据读取的顺序。 我们先为A建立一个链表。首先给A认个首领,HEAD=1,由它牵着剩下的999个数。剩下的999个数我们把它丢进一个维度为1000(跟A一样)的数 组里,取名LIST,用来存储数组的位置。LIST还剩下一个空元素我们赋值为0,这是链表的尾巴,表示链表的终止。

我们只需做个简单的循环赋值,把ID的数整体往前挪一位,并把最后一个赋值为0就做好了LIST:

HEAD = 1

DO i=1,999

LIST(i)=i+1

END DO

LIST(1000)=0

建立的链表结构就是:

HEAD=1
LIST(HEAD)=2
LIST(2) = 3

LIST(998)=999
LIST(999)=1000
LIST(1000)=0

即LIST(a)=b,这里的a是LIST里的前一位数,b是a后头的一位数。换言之,a是数组对应元素A(a)的位置,b指代A(a)后面一位数A(b)的位置。 所以只要知道一个HEAD值,我们就知道整个顺序结构是怎样了。

如果我们要将1000挪到第一个,那么这时的头头就换成了1000,HEAD=1000,此时我们只需要变换两个数,也就是LIST(1000)=1和LIST(999)=0 就大功告成了,因为1后头的所有链接都没有变化,999后面没有数了。

新链表如下(蓝色部分未变化):

HEAD = 1000
LIST(1000) = 1
LIST(1)=2
LIST(2)=3

LIST(998)=999
LIST(999)=0

如果a88要跟a2换位置,那么只需要分别改变a88与a2前一位和后一位的链接顺序就大功告成。

新链表如下:

HEAD = 1000
LIST(1000) = 1
LIST(1)=88
LIST(88)=3
LIST(3) = 4

LIST(86)=87
LIST(87)=2
LIST(2)=89
LIST(89)=90

LIST(998)=999
LIST(999)=0

如果a50和a51之间要插入一个a1001,那么需要将LIST扩充一位,并改变a50和a51之间的链接就好。

新链表如下:

HEAD = 1000
LIST(1000) = 1
LIST(1)=88
LIST(88)=3
LIST(3) = 4

LIST(49)=50
LIST(50)=1001
LIST(1001)=51
LIST(51)=52

LIST(86)=87
LIST(87)=2
LIST(2)=89
LIST(89)=90

LIST(998)=999
LIST(999)=0

总而言之,对于每一次数组的顺序变换、元素增减,只需要改变链表的局部赋值,就可轻松改变数组样貌。这对于大数组计算非常节省计算资源。链表结构的一个很好的运用就是模拟三维空间中粒子的运动,我们可以根据实际情况增减粒子数而不需要整体改变所有粒子的ID。

没有系统地学过编程语言,读写代码实在是太费脑了,琢磨了这么久才弄明白累觉不爱 继续努力!

 

注:因为这是我从原博客搬过来的,字体颜色都已经丢失了,大家可以移步http://www.blogbus.com/jncss-logs/270170035.html围观

Advertisements

【译文】离家千万里

版权声明:转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://www.blogbus.com/jncss-logs/262505618.html

(本文译自Phil Plait的博文 链接地址:http://www.slate.com/blogs/bad_astronomy/2014/02/10/curiosity_looks_to_earth_our_home_world_as_an_evening_star.html 版权所有归原博主所有,欢迎各位交流探讨,并纠正译文错误)


那一缕微弱的光,如太息般难以察觉,但这便是我们生活的世界。 照片来源:Photo by NASA/JPL-Caltech/MSSS/TAMU

有一种东西叫做家,我们总能强烈地感受它的呼唤,随时随地,不论我们走得多远,那股无法抗拒的力量会让我们转过头去凝望来时的方向……

当我们攀登高山,当我们远离海岸线去大洋漂泊,我们都有这种感受,更甚至于当我们将探测器送到太空,让它进入无边的黑暗,永无归期。

这就是好奇号,在我们核动力移动化学实验室(nuclear powered mobile chem lab)的帮助下,它经过漫漫征程到达火星地表。毫无疑问,科学家们一直在如饥似渴地研究着这只萌物轮子下近在咫尺的土地、以及即将要奔赴的地域、还有在数公里外隐约可见的莎普山(Mt. Sharp)山帽。

但即便如此,也无法阻挡那回头望一眼家乡的憧憬。在2014年1月31日,机遇号将支在桅杆顶上的相机转向了天空,在日落方向,出现了两颗明亮的恒星……但他们并不是恒星。

                                      照片来源:NASA/JPL-Caltech/MSSS/TAMU

这张图中,火星连绵的山峦被夜幕渐近的天空勾勒出美丽的轮廓。在天空中有两个光点:地球和月球。他们在图上很难看见,但可以在高分辨率图像中找到。

在距离近1亿6千万公里(1亿英里)处,这两个世界被微缩到了几个像素点里。从火星上看,地球就是夜空中跟随太阳降落的一颗星星。而且借助火星的距离优势,我们能够将地月很明显地分开,所以月球被非常清晰地从它母行星的光点中分离出来。

                                         图片来源:Photo by NASA/JPL-Caltech/MSSS/TAMU

把自己生活的整个世界坍缩成一个渺小的点大概是件难以想象的事情。每当我们走出门,双脚踩在坚实的土地上,而这土地填充了一半的天空。也许你从未这么去思考,但这是客观实在的:如果地球不在那,你的四周包括你的脚下将被天空包围。我们的星球,由于大而不透明,遮挡了苍穹的另一半。

但如果我们距离足够远,甚至仅在1万3千公里开外,世界也可以缩减成天空中的一点光芒。请记住,火星还仅是太阳系中距离我们最近的天体,更不要说茫茫宇宙。从星系尺度上看,在我们还未到达银河系遥远深处前,我们硕大的太阳就已消逝成不可见星点了。

宇宙以它广袤、深远、冰冷的形象存在着,并且从未对我们有过偏袒。

但请记住这点:以上这幅照片是由一只人类打造的机器拍摄的,而这只机器正坐在遥远的另一个星球上。数百名工作人员,耗时数千个工作年,只为一个图景,努力去游说,辛勤地去创造,直到看到它升空、成功登陆火星。你在图中看不见它,因为相机朝着另一个方向。但是假若你能在心里稍稍想象着让自己走出相片,并回头,你就会看到一只探测器“双轮”(实际它有六只轮子)踏在火星的尘土上,见证着人类的好奇之心,探索之心,和离家寻访未知世界的需求。

至于宇宙知不知道我或者关不关心我,我一点也在乎。而我了解它并且我在意它,这才是最重要的。