起航学习网

链表是什么，如何使用链表，在scratch课程中，如何解决链表的使用问题呢？

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

Scratch第十四讲:链表的使用

链表大家编程的时候用的不多，所以也不太熟悉，今天CC哥着重讲一下，看看小伙伴们是否能够通过链表的使用能够让程序做得更有效率。

链表：在scratch里也翻译成列表。也是变量的一种，但是是一组变量。相当于一个队列。通常用在同一类的变量组。举个例子吧，比如今天天气如何？晴天？阴天？多云？雷阵雨？等等，这些就可以看成一组变量，因为都是描述天气的。再比如今天是星期几？周一到周日，7个变量，也可以看成有关周几的一组变量。这样的例子很多，比如都有哪几门功课？公园里都有哪些花？家里有哪些家具？这些都可以看成一组组的变量。

这么一解释，是不是小伙伴顿时豁然开朗，原来链表就是变量组呀，那用途是不是很广泛呢？当然我们也可以把变量组中的一个个变量拿出来定义成单独的变量，但是这样你就会发现有大量的重复编程的内容。

我们今天用一个例子来讲讲变量的用法，首先我们先解释一下链表的指令集。

CC哥创建了一个比赛的列表。第一条指令就是在列表的后面增加一个新的变量。第二条指令就是删除变量组的某一条变量。（选项里包含了末尾和全部的选项，也就是可以直接把整个列表链表清空）第三条指令是插入指令。就是在某一项前面插入一个变量（此处也有两个选项，可以插在末尾，可以随机插入某个位置）。第四条是替换掉某个变量，也就是先删除再插入了。（选项里也包括了末尾和随机两个选项）

这三条指令相当于参数的指令了。第一个是直接返回了链表中的某一项，第二个反馈整个链表有多少项。第三个是判断整个链表中是否包含某一项目。

整个看起来是不是很像最基本的数据库列表呀。

我们通过个小游戏来简单熟悉一下：我们在屏幕上画出三个轨道，让小猫们在这个三个跑道上随机的跑。

这个简单的小动画可以用很多方法实现，我们今天试试链表怎么用：

我们首先在屏幕上画三条赛道（就画三根线吧），然后我们创建一个赛道的列表，用来表示三条赛道的Y坐标。

如果变量内容简单，可以直接在创建链表的时候，直接把变量初始内容填上。点赛道变量表的左下角的小+号就可以添加变量。

当然如果变量有规律的话，也可以通过在程序里初始化阶段通过循环指令添加。这个大家可以自己研究。

程序分解：

1：不断的克隆小猫。

2：把每个克隆小猫出现的位置放在随机的赛道上。然后向右方跑。

第一部分的程序，很简单。

第二段程序：

左边的部分很简单，关键是选择赛道这条指令。这个是CC哥新建了个积木指令。指令里只有一条语句，就是设置Y坐标为赛道变量里面任意一项的值。（之所以采用新建一个选择赛道这样的指令是想大家养成一个好习惯，让编程更具可读性，和可管理性。习惯去把一组复杂的指令打包成一个指令，以后更加方便的编程和维护。）

通过这个小例子，大家是不是对链表有些熟悉啦。

CC哥仔细在网上研究了一下关于链表的经典例子，其中有一个能非常好的学习链表的例子，就是如何取不重复的随机数。比如在1到10中任意选取五个不重复的随机数。

重复的随机数大家都会选，一条指令就做到了，那不重复的随机数呢？其实不重复的随机数应用很多，比如排雷的小游戏，你就不能把两颗雷放在同一位置，还有打比赛，随机抽取比赛队伍时，就不能一个队伍选两次。很多游戏里的随机选取都是不能重复的。

当然随机选取不重复的方法也有很多，比如把随机选取出来的数字与已经选取出来的数字做一一比对，如果重复再重新选取。

如果用链表的方法，效率就比较高：

1：从链表中任意选取一项。

2：将该项从链表中删除。

3：重复第一步。

是不是很简单，这样就不会有重复的选项了。这个小程序就留给小伙伴们自己去做了。

文章出自：http://qh.itpxw.cn/peixun/software/201949096.html

文章标题：链表是什么 Scratch中链表的使用方法是什么

免责声明：本站文章均由入驻起航学习网的会员所发或者网络转载，所述观点仅代表作者本人，不代表起航学习网立场。如有侵权或者其他问题，请联系举报，必删。侵权投诉