Question

Data

英文的“Data”是複数形，是指大量资料，而非一笔资料。

中文的“资料”，大家国文造诣都很棒，应该都知道是什麽意思。不过为求慎重，还是查一下国语字典吧：

一、可供参考或研究的材料。如：“第一手资料”、“原始资料”。
二、生产、生活中必需的东西。如：“生产资料”、“生活资料”。
三、在社会科学中，指研究者对社会现象中某些事实所作的纪录。
四、计算机中一切数值、记号和事实的概称。通常指未加以处理者。

听起来有点複杂，就当我没查吧。

简单来说，计算机拿来储存、拿来计算的东西，就叫做资料。

程式语言的变数

“资料”听起来不明不白，有点抽象。对于初学者来说，从程式语言的变数入手，会比较有感觉。

上面这些都是一笔资料的 C++程式码范例。可是如果有非常多笔资料怎麽办呢？

可是如果有一万笔、一亿笔资料怎麽办呢？

是的，这时候你就必须学习“资料结构 Data Structure”。要不然你会抓狂的。

资料结构是资料的储存方式。资料结构的用途，是让我们计算资料的时候，可以简便地、快速地存取资料。

由于坊间已有许多图文并茂的资料结构书籍，以下不再重複整理，仅做重点介绍。

大量 Data 资料结构: Array / List

Array

繁中“阵列”，简中“数组”。连续的记忆体。

一个格子放入一笔资料，资料可以是一个数字、一个字元（所有字元合起来变成字串）、一个物件等等。

搜寻、插入、删除的时间複杂度都是 O(N)。资料已排序，则支援二分搜寻。

UVa 10370 11991 11716

特殊的 Array

根据资料数量，调整阵列大小，称作 Dynamic Array。每当阵列装满资料，就另外建立两倍大的新阵列，将资料搬到新阵列，捨弃原阵列。搬移的总时间複杂度是 O(1 + 2 + 4 + 8 + ... + N) = O(2N - 1) = O(N)。

可以直接使用 STL 的 vector。

List（Linked List）

繁中“串列”，简中“链表”。藉由指标得到下一块记忆体。

搜寻的时间複杂度是 O(N)。知道正确位置，插入与删除的时间複杂度是 O(1)，否则必须先搜寻。无索引值，故不支援二分搜寻。

可以直接使用 STL 的 list。

深究串列，其实串列是用阵列实作。一步一步釐清：

上图：藉由指标得到下一块记忆体。

中图：指标是一个变数，储存记忆体位址。

下图：电脑记忆体是一条很长的阵列，串列其实是散落在阵列裡面。另外还需要一个变数记录串列的开头，不过这边没画上去。

特殊的 List

尾串到头，头尾循环，称作 Circular List。特色是开头可以随便选、随便动。

只串单向，称作 Singly Linked List。双向都串，称作 Doubly Linked List，特色是双向都能搜寻。

Doubly Linked List 若用 XOR 实作，称作 XOR Linked List。

Doubly Linked List 若可以还原删除动作，称作 Dancing Links，经常配合 Backtracking 一起使用。

UVa 11988 ICPC 2659

List 裡面放入 Array

英文网路称做 Unrolled Linked List，中文网路称作“鬆散链表”、“块状链表”。查无正式学术名称。

N 笔资料，分成 A 块，每块约 B = N/A 个元素。每块各自记录元素数量。

索引：先数块、再数元素，时间複杂度为 O(A)。

搜寻：全找，时间複杂度为 O(N)。资料已排序，则为 O(A + logB)。

插入、删除：一块大于等于 2B 就拆开成两块，相邻两块小于等于 B 就合併成一块，避免一拆开就要合併、一合併就要拆开，时间複杂度为 O(A + 2B) 到 O(2A + B)。

N 笔资料，分成 A = sqrtN 块，每块约 B = sqrtN 个元素，是最均衡的，可令时间複杂度最低。索引、插入、删除的时间複杂度为 O(sqrtN)。竞赛选手称此技巧为 sqrt decomposition。

上古时代的文字编辑器曾使用此资料结构。

Array 裡面放入 List

大致上就是图论的 Adjacency Lists。

大致上就是之后提到的 Hash Table。

大量 Data 资料结构: Queue / Stack

Queue

繁中“伫列”，简中“队列”。像排队，维持资料前后顺序。

Array 和 List 皆可实作。

插入、删除需时 O(1)。搜寻需时 O(N)。

伫列有暂留的性质。

可以直接使用 STL 的 queue。

UVa 10935 11995 12100 1598

特殊的 Queue

记忆体循环使用，称作 Circular Queue。

资料保持排序，可以随时得到最小（大）值，称作 Priority Queue。资料保持排序，可以随时得到最小值、最大值，称作 Double Ended Priority Queue。

Stack

繁中“堆叠”，简中“栈”。像叠盘子，颠倒资料前后顺序。

Array 和 List 皆可实作。

插入、删除需时 O(1)。搜寻需时 O(N)。

堆叠有反转的性质、有括号对应的性质、有递迴与叠代的性质。

可以直接使用 STL 的 stack。

UVa 101 514 673 271 10152

Deque（Double Ended Queue）

两头皆能插入与删除，称作 Deque，同时有著 Stack 和 Queue 的功效。

Array 和 Doubly Linked List 皆可实作。

可以直接使用 STL 的 deque。

UVa 12207