除了连续储存的储存方式之外，本章将探讨电脑主记忆体其他存放资料的方式，所以主题会是资料结构，而其目的是让使用者能以抽象化工具的形式来存取资料而非强迫使用者了解资料在记忆体中的排列方式。

基本资料结构

首先先介绍一些在後续个章节中会作为范例的基本资料结构，集合资料并抽象化为串列结构或其他结构，这些方法都是解题方案中常用的工具。

阵列与聚合资料

阵列 (array) 是矩形资料块且每个资料都具有相同的型别，最简单的形式是一维阵列，亦即所有资料排列成一排且每项都以索引值来标示其位置，二维阵列包含数列与数行其位置是两个索引值标示，第一个索引标示位置相对应的列数而二个索引标示相对应的行数。

聚合类型 (aggregate type) 是可能具有不同类型和大小的资料块，在资料块中的资料通常称为栏位 (field)，例如表示某员工的资料块，栏位可能包含员工姓名(字串)、年龄(整数)和技术等级(浮点数)，聚合资料的栏位通常以栏位名称存取而非数值形式。

串列、堆叠和伫列

串列 (list)

另一种基本资料结构称为串列 (list)，是一群有序的资料串，串列的起点位置称为串列的头部 (head) 而另一端称为尾部 (tail)。

堆叠 (stack)

堆叠 (stack) 是一种只能在头部进行新增与删除的串列，比如一叠书中要新增或移除新的书都只能从这叠书的最上面进行操作，一般将堆叠的头部称为顶部 (top) 而尾部称为底部 (bottom) 或 基底 (base)，在顶部新增一个资料的动作称为推入 (pushing) 而在顶部移除一个资料的动作称为弹出 (popping)，要注意的是无论是加入或移除都只能对第一项数据进行操作，因此堆叠被认为是後进先出 (last-in first-out, LIFO)

这种 LIFO 的特性很适合处理储存或取出顺序颠倒的资料，因此堆叠通常用来作为回朔操作的资料结构，回朔 (backtracking) 是指以进入的相反次序退出的程序。

伫列 (queue)

伫列 (queue) 是一种只能在头部移除资料并只能在尾部新增资料的串列，比如排队的队伍，最先处理的是队伍中的第一位而新来排队的需要排在队伍的最後方，这种结构称为先进先出 (first-in first-out, FIFO)，伫列通常被用来当缓冲区背後的资料结构，缓冲区是当资料要从一个位置传送到另一个位置时所放置的暂时区域，当资料顶部放置於缓冲区後他们会被放置在伫列的尾端，然後当资料要转移到最後目的地时会以伫列储存的顺序转移到最後目的地，因此资料会以相同顺序转移到目的地。

树

数 (tree) 是一群有阶层组织的资料项像一般公司的阶层图一样，树中的每个位置称为节点 (node)，在顶部的节点称为根节点 (root node)，而最底层的节点称为终端节点 (terminal node) 或叶节点 (leaf node)，通常会将从根节点到叶节点的最长路径称为深度 (depth)。

有时会把树的某个节点看做可生出下一层的节点，所以会将紧邻的下层节点当作子辈 (children) 并且将紧邻的上层结点当作父辈 (parent)，此外还会将具有相同父辈的其他节点称为兄弟 (sibling)，树中每个父节点最多只能有两个子节点的树称为二元树 (binary tree)。

如果某个节点旗下的所有节点也具有数的结构的话，我们称这个小的树叫做子树 (subtree)，因此每个子节点都是该子树的根，每个这样的子树都是父节点底下的一个分支 (branch)。

资料相关概念

本章会探讨与资料结构相关的三个课题: 抽象化, 静态与动态结构的差异与指标的概念。

抽象化

电脑中的主记忆体并非如阵列, 串列, 堆叠, 伫列和树的结构，他的组织方式是连续的记忆体储存单元，因此必须要靠模拟的方式来产生所有其他的结构，所以刚刚提到的资料结构都是抽象化的工具，以便使用者可以以更便利的形式存取资讯而不用在意资料实际储存的方式。

所以的使用者并不一定是人，若当状况是某个人使用电脑记录一些数据的话，使用者就会是人，在这个状况下使用者应用的软件就必须以抽象化形式来表达其资料以便使用者使用，若当这个情况是网际网路的服务器时，使用者就会是用户端，这种情况下服务器就必须以抽象化形式来表达其资料以便使用者使用，所以使用者并不一定是人，而是看使用的状况与场景。

静态与动态结构

建构抽象化资料结构有一个重要的差异就是要模拟的结构是静态的还是动态的，也就是说这个资料结构的大小会不会随时间有所变动，一般来说静态结构会比动态结构还要好处理，若结构是静态的就只需要提供一种方式来存取各项资料，或提供另一种方式来更改指定资料的储存值，但如果是动态的话就必须要处理新增与删除资料的问题，以寻找所需要的记忆体空间以跨大资料结构。

垃圾回收 (garbage collection): 将未使用的储存空间回收以作为未来使用的过程称为垃圾回收 (garbage collection)，垃圾回收有些细微的问题，比如说在使用链结结构的情况下，每次指标内容更改时就必须要决定是否要回收原先指标指向的储存空间，这样的问题非常复杂，而不精确的垃圾回收会导致资料的流失或储存空间减少，所以如果垃圾回收没有将未使用的空间回收的话就会让可用空间减少，这种情况称为记忆体泄漏 (memory leak)。

指标

电脑主记忆体的储存单元是以数值型态的位置来标示，因为是数值型态所以这些位置本身可以进行编码并储存於记忆体储存单元中，而指标(pointer) 就是用来储存这种编码位置的储存区，在资料结构中指标是用来记录资料储存的位置，所以指标总是指向某一笔资料或是空的记忆体，简单来说指标是指向门牌号码，而这个门牌里面可能有住人(有资料)或没有住人(空的)，在前面介绍 CPU 的时候有提到程序计数器是用来储存下一个要执行的指令的位置，这个就是指标，实际上程序计数器也叫做指令指标 (instruction pointer)，很多近代的程序语言的基本型态都包含了指标，也就是说这些程序语言允许宣告、配置和操作指标。

资料结构实作

在前面几章中介绍了资料结构应如何储存在电脑的主记忆体中，这些资料结构在高阶程序语言中是基本的结构，接着要来了解如果使用了这些结构是如何将他们转换为机械语言以及处理储存於主记忆体的资料。

阵列储存

在一个静态结构的阵列中，阵列的大小不会因为任何原因发生变化，所以在主记忆体中会保留一个固定大小的连续储存空间，接着资料会从记忆体空间的第一个位置开始储存资料，将第一列的所有资料储存在记忆体中，按照相同的方式在储存下一列，这种储存方式称为以列为优先法 (row major order)，另一种是以行为优先法 (column major oeder) 这就是一行接着一行的储存资料。

如果每列为 5 个元素的话，我们希望要找到第三列的四行的资料，我们需要先经过第一列与第二列，这样才能到达目标第三列，接着要跳过第一道第三行才能到目标第四行，所以我们需要跳过 5(一列五个) * 2(跳过两列) + 3(跳过三行) = 13 个元素，根据上面的算法可以有一个公式用於计算，如果我们以 c 代表阵列行数，则第 i 列与 j 行资料的位置将是

x + (c * (i - 1)) + (j + 1)

上面的 x 第一列第一行资料所在的储存单元位置，也就是说需要听过 i - 1 列以到达目标列数，而每个列包含 c 个资料，所以要再跳过 j + 1 个资料向才能达到目标行数，上面的例子中 c = 5, i = 3, j = 4，若起始位置设为 x 则要到第三列第四行的话需要听过 x + (5 * 2) + 3 = x + 13，这就跟我们刚算的结果一样，而 (c * (i - 1)) + (j - 1) 有时候被称为地址多项式 (address polynomial)。

串列储存

如果要在记忆体中储存名字，方法之一是将整个名字的串列储存在一个连续的记忆体中就跟阵列一样，将整个串列储存在一个很大的记忆体区块中，每个资料项都相继的储存於连续的记忆体储存单元中，这样的排列方式称为连续串列 (contiguous list)，连续串列在静态串列中非常好用，不过如果要储存动态串列的话就会有问题，当对串列进行新增会删除的话会导致资料花费很多时间在重新排列，最坏的情况下可能会导致整个串列都要移动到新加入内容的後面，这样就会在背地做很多额外的工作导致效能降低。

如果允许串列的每个资料都储存在记忆体的不同位置而不是一定要连续的储存在一起的话就可以解决这个问题，以前面要储存名字的例子来说，我们可以将名称设定不能超过 8 个字元，接着将这 8 个字元放进 9 个连续的记忆体储存单位中，而空出来的那个位元则作为指标，他会指向下一个名称的记忆体位置，这样串列就可以散布在整个记忆体中而不用一定要连续存放，这种串联方式称为链结串列 (linked list)。

为了要保有链结串列的起始位置，这时就需要另一个指标用来储存第一笔资料向的位置，将这个指标称为头部指标 (head pointer)，而为了要标记串列的尾端则需要使用一个空指标 (null point)，他是放在串列的最後一项只是一个特殊位元的字串。

刚刚提到的需要新增或删除项目，在链结串列中只需要改变一个指标值就可以删除或新增一个项目，已删除为例，如果要删除某项的话只需要将指标移动到要被删除项目的下一项即可，这样当走遍整个串列时，因为没有指标指向被删除的资料项所以就会跳过他。

如果是新增的从择需要选择一块没被使用的记忆体储存单元，将大小定义成跟其他连结一样大，然後将要插入位置的前一笔资料的指标指向新增的资料，而新增资料的指标就指向原先指向的资料位置即可

堆叠与伫列储存

堆叠

为了储存堆叠和伫列可以使用类似连续串列的方式，在堆叠中需要保留一块足够大的记忆体空间以应付最大的堆叠情况，在记忆体的区块的某一端指定为堆叠的基底，这个是第一个资料被放入的地方，之後的每一项资料都会被存在前一下的下个位置，因此堆叠会往记忆体区块的另一个方向除件增加。

当有资料被 pushing 或 popping 堆叠时，顶部位置会跟着在记忆体区块的储存单元中来回移动，因为当有新资料被 pushing 近来顶部位置就必须要移动到最新资料的记忆体位置上，相对的如果 popping 了资料那麽顶部就需要移动到下一笔资料的记忆体位置上，为了知道顶部所在的位置，顶部位置的地址会储存在另一个记忆体中，称为堆叠指标 (stack pointer) 亦即堆叠指标是指向堆叠顶部的指标。

上图为堆叠的完整结构，他的运作会是：要推入一个新的资料需要将堆叠指标指向堆叠顶部的下一个位置然後将新资料存入堆叠顶部的位置，而如果要弹出一个资料则需要先读出堆叠指标所指向的位置资料值然後将堆叠指标指向堆叠顶部的前一个位置。

伫列

伫列的传统实作方法跟堆叠很像，一样要保留一块够大的记忆体空间以应付最大的伫列，但是在伫列操作中需要在两端进行操作因此需要预留两个记忆体单元作为头尾的指标，其中一个称为头部指标 (head pointer) 而指向尾部的指标称为尾部指标 (tail pointer)，当伫列为空时头尾两个指标会指向同个位置，每次要储存一个新资料资料会被存入尾部指标的位置，然後尾部指标会指向下一个未使用的位置，因此尾部指标总是会指向伫列尾部第一个空位，而从伫列中移除资料的话要先读出头部指标所指出的位置的资料，然後从头部指标值指向伫列的下一个资料。

伫列的储存方式会有一个问题，那就是随着资料的增加与删除会让整个伫列在记忆体中不断移动，因此需要某个方法将伫列局限在某段记忆体中，这个方法其实很简单就是当着列的尾部达到记忆体区块的末端时，把之後新增的资料存在记忆体另一端空白的区域(因为伫列尾部指标会随着资料删除而往前移动)，这样就可以让头部指标重新指回记忆体区块的初始位置，这种方式称为环形伫列 (circular queue)。

二元树储存

二元树的每个节点最多只有两个子辈，他的结构与链结串列差不多但不一样的是二元树的资料结构会有三个元素：资料, 指向该节点的第一个子辈节点, 指向该节点的第二个子辈节点，通常会将第一个指标当作左子辈指标 (left child point) 而另一个称为右子辈指标 (right child point)，不过这只是方便我们记忆，实际上电脑的记忆体是没有左右之分的。

要储存树状结构首先需要有一块足够大的记忆体区块，接着以二元树来说每个节点需要指向自己的左子辈指标和右子辈指标，如果没有子辈节点的话要把它指定为空值(表示这个节点是终端节点)，还需要预留一个记忆体位置用於储存跟节点的位置，称为根指标 (root pointer)。

另一种储存二元树的方式是将他储存在连续的记忆体储存空间中，将根节点储存於第一个位置，接着将根节点的左子辈与右子辈储存在第二与第三个记忆体中，接着每个节点的子辈的左右子辈分别存於 2n 和 2n+1 个储存位置，而记忆体中没有储存的位置会以特殊位元字串表示该位置没有资料。

以上面的图为例，A 是根节点所以会储存在记忆体的第一个位置，接着 B 和 C 是根节点的左右子辈所以分别放在第二与第三个位置，接着由於 D 是 B 节点的左子辈指标所以他存放的位置是 2 * 2 = 4，相对的 E 是右子辈指标所以会存放在 2 * 2 + 1 = 5，所以如果 E 节点也有左右子辈的话那麽他们存放的位置将会是 2 * 5 = 10 和 2 * 5 + 1 = 11。

相较於第一种储存方式，这种连续储存的方式可以提供很有效率的找到任何节点的父节点和兄弟节点，每个子辈的父节点会是该位置除 2 的值(余数不算)，比如上面提到的 E 的左子辈位置为 10 那麽他的父节点位置就在 10 / 2 = 5 的位置，不过如果二元树中不是每个节点都有子辈的话那麽这种储存方式就会变得很没效率，因为会有很多空的直储存在记忆体中从而占据很多记忆体空间。

Reference

• computer science - AN OVERVIEW