序列

你应该记得，我们在编码那一张提过如何表示多个数字的，没错，定长编码可以帮我们解决这个问题，帮我们界定数字之间的边界。但是，当我们要表示的数据不只是一组的时候，又该怎么来界定边界？

比如，我们有两组数，分别是$1,3,5,7,9,11$和$0,2,4,6,8,10$，假设以一个字节（十六进制）表示的话，就是下面这个样子的：

0x01030507 0x090B0002 0x0406080A

好的，接下来请完成以下任务：

• 找到第二个序列中的第三个数。

嗯，是不是感觉自己懵了，如果不知道第一组有几个的话你是不可能准确找到这个数字的。

于是我们得到了一个简单的界定序列边界的方法，就是要知道各序列对应的长度。

比如我们知道这两个序列是连续放在一起的，第一个序列长度是$6$，同时也知道要找的是第二个序列的第三个数，那么这个数就应该是第$6+3$个数字。

当然，这个数字要从$1$数过去才行，否则从任意其他的位置数，都不能得到我们想要的结果。

长度

我们可以看到，界定一个序列，必须要知道的是两点，第一个是他的起始元素，第二个就是这个序列的长度。

一般来说，当这个序列的长度固定不变，并且每个元素是挨在一起的时候，我们常把它叫做array。

关于array，我非常不喜欢“数组”这个翻译，因为这里面并不一定是数，也有可能是符，所以我会尽可能地使用array来表示它。

在JavaScript中，定义一个array如下：

let nums = [1, 2, 3, 4, 5]

对于array来讲，初始元素是方括号中的取值为0的时候的值。在方括号中的值我们称之为index（索引，奇葩翻译一般叫做下标）。这些索引以数字的形式出现，作为序号来表示数据在序列中的位置。

有个重点是，这里的索引是从$0$开始，最大是$\mathrm{序}\mathrm{列}\mathrm{长}\mathrm{度}-1$，这其实也就是为什么我们在第三章讲过程的时候提到循环的写法的一个原因。

不过对于遍历序列来说还支持另外一种写法。

for(let item of nums) {
    console.log(item);
}

不需要你去管什么索引了，这样子写就像是在说

对于 nums 里面的 item
    输出 item 的值

当然，在Python中看起来更自然：

for item in nums:
    print(item)

串

JavaScript中的字符串与array类似，自己维护了长度。但在早期的一些编程语言（如C语言）中，是没有做这种记录的，取而代之的是使用一个特定的标志来表示，这里是最后一个值为空。这种字符串也有另外一个名字，叫空结尾串（Null-terminated String）。

这种特殊标记就可以让我们界定一个序列的边界的另外一种方式。

我们可以来简单模拟一下这个行为：

let content = ['h', 'e', 'l', 'l', 'o', null];

// 求长度：

function length(nts) {
    let length = 0;
    for (let item of nts) {
        if (item != null) {
            length ++;
        } else {
            break;
        }
    }
    return length;
}

length(content) // 5

而实际存放这个串的空间大小：

content.length // 6

可变长序列

试想你在一个笔记本上记录内容，每一行算是一个条目，当一页记录满以后，并不能连续地往下面记了，就需要翻到下一页纸。

连续不连续并不重要，重要的是我们能从这一页翻到下一页。

对应到我们的序列表示上，只要当前元素能够记录下一个元素的位置，是不是就表示我们的序列就能从第一个元素全部找出来了呢？

就像这张图片描述的：

这种结构被称为链接列表（也叫链表，Linked List）在上世纪五十年代就已经设计用于实际的程序。链表这种结构非常的灵活，可以很轻松的在任意位置添加或者删除数据。因为并不需要内存结构上的连续，所有的位序关系都是靠前一个元素和后一个元素之间的链接关系来确定，而添加或者删除数据只要改变一下这种链接关系就可以了。

但是对于链表来说一个很大的问题就是访问数据。比如我们要访问链表的第n个元素的时候，对于array和串这种结构来说，因为内存空间上是连续的，直接做一次加法就能找到，但是对于链表来说每次都要从第一个元素开始找起。而且，这种形式的链表又称作单链表（Singly Linked List），是没有办法从尾部往头部走的。

所以，在单链表的基础上，又构造了双链表（Double Linked List），每一个元素除了纪录自己对应的下一个元素之外，还要保存自己对应的上一个元素。这种时候如果做一些相邻元素的访问，就比单链表高效了一些。

比如，当我访问列表中第7个元素，然后再去访问第6个的时候，只要从第7个元素向前查找一次就可以了。

也许以后你可能还会听说到循环链表（Circular Linked List），或者是其他的形式，这些都离不开最初链表的思想：把数据和位置做关联。

线性结构

我们简单的做一个总结。

对于array，string和list我们都称为序列，原因其实是显而易见的。

首先，他们满足这样一点：所有的都是从头到尾连续地组织在一起，从任何地方出发都能找到下一个元素或者是到序列尾部。就像是在头和尾之间有一条线把他们串起来一样，而且在逻辑表示上，我们也是把他们放成一串。

另外，对于每一个元素，他们在序列中的位置是固定的，换句话说，序列中的元素是有前后顺序的。当我任意交换两个元素的位置，得到的新序列就跟原来的序列是不同的。

第三点就是，当我们从第一个元素开始找下去的时候，总是能找到最后一个元素（对于没有最后一个元素的情况，我们会在以后进行探讨）。

总结下来就是，序列是线性的（Linear）、有序的（Ordered，类比“排序过的（Sorted）”）和有穷的（Finite）。

生成器

很多时候我们的序列是通过某种规则产生的，而这种规则

练习：最长公共子序列（Longest Common Subsequence）

通常我们会对两个序列的内容进行对比，比较这两个序列有什么地方不同。这就是典型的LCS问题。LCS的应用很多，大部分版本控制系统的核心逻辑中就有它的存在。

请参阅Wikipedia对LCS问题的分析和讨论，尝试实现求LCS的算法，并试分析该算法要求迭代器至少要属于哪个category。