Abstract data types
International Baccalaureate · IB Diploma · Computer Science · HL Tópico 8 4:28 Narração em inglês · Legendas em inglês + 中文 gravadas
Capítulos
Transcrição
A music app holds a playlist of ten thousand songs.
音乐应用的歌单里有一万首歌。
Adding a song in the middle of an array means shifting thousands of items along.
在数组中间插入一首歌，要把成千上万个元素往后挪。
Searching an unsorted list for a title checks them one by one.
在无序列表里找一个歌名，要一个个地查。
Choosing a different structure makes both jobs fast.
换一种数据结构，这两件事都能变快。
An abstract data type is defined by the values it holds and the operations on them, not by how it is stored.
抽象数据类型由它保存的值和对这些值的操作来定义，而不是由存储方式定义。
A stack is push, pop and peek, last in first out.
栈就是 push、pop、peek，后进先出。
It can be built from an array or a linked list, and code that uses the stack never needs to know which.
它可以用数组或链表实现，使用栈的代码根本不需要知道是哪一种。
A linked list is a chain of nodes.
链表是由节点组成的链。
Each node holds data and a pointer to the next node.
每个节点保存数据和指向下一个节点的指针。
The list is reached through its head, and the last node points to None.
通过头指针访问链表，最后一个节点指向 None。
To traverse it, follow the pointers from the head until None.
遍历时从头指针出发，沿着指针走，直到 None。
To insert thirty-one after the node holding twenty-five: step one, point the new node at forty.
要在二十五后面插入三十一：第一步，让新节点指向四十。
Step two, redirect twenty-five's pointer to the new node.
第二步，把二十五的指针改为指向新节点。
The order matters.
顺序很重要。
Doing step two first would lose the only pointer to forty, and with it the rest of the list.
先做第二步就会丢掉唯一指向四十的指针，后面整段链表也就丢了。
No items are shifted.
没有任何元素需要移动。
A singly linked list points only to the next node and uses the least memory.
单向链表只指向下一个节点，占用内存最少。
A doubly linked list also points back, so it can be traversed both ways.
双向链表还指向前一个节点，可以双向遍历。
In a circular list the last node points back to the first, which suits taking turns, such as round-robin scheduling.
循环链表的最后一个节点指回第一个，适合轮流做事，比如时间片轮转调度。
An array reads any index at once, but inserting in the middle shifts items.
数组可以直接读取任意下标，但在中间插入要移动元素。
A linked list inserts at a known node without shifting, but has no index, so access means traversing.
链表在已知节点处插入不用移动，但没有下标，访问要遍历。
A linked list grows one node at a time, but stores a pointer with every item.
链表一次增加一个节点，但每个元素都要额外存一个指针。
In a binary search tree every key on a node's left is smaller and every key on its right is larger.
在二叉搜索树中，节点左边的键都更小，右边的键都更大。
This tree was built by inserting fifty, thirty, seventy, twenty, forty, sixty, eighty, then thirty-five.
这棵树依次插入五十、三十、七十、二十、四十、六十、八十，最后是三十五。
Thirty-five is less than fifty, go left; more than thirty, go right; less than forty, go left.
三十五小于五十，往左；大于三十，往右；小于四十，往左。
So it becomes forty's left child.
所以它成为四十的左孩子。
To search, start at the root and go left if the key is smaller, right if larger.
查找时从根出发，键更小往左，更大往右。
Each comparison drops a whole subtree, so a balanced tree is searched in log n steps.
每比较一次就排除一整棵子树，所以平衡树的查找是 log n 步。
But keys inserted already sorted, ten, twenty, thirty, all go right and make one long chain, and search becomes order n.
但如果按已排好的顺序插入，十、二十、三十，都往右走，形成一条长链，查找就变成 O(n)。
A traversal visits every node once.
遍历把每个节点访问一次。
Pre-order visits the node before its children, which copies a tree.
前序遍历在访问孩子之前访问节点，用来复制树。
In-order visits it between them, and for a search tree gives the keys in sorted order.
中序遍历在两个孩子之间访问节点，对搜索树来说得到的是排好序的键。
Post-order visits it after them, which deletes a tree, children before parents.
后序遍历在孩子之后访问节点，用来删除树，先删孩子再删父节点。
A set holds distinct values with no order.
集合保存互不相同、没有顺序的值。
The union of a and b holds everything in either set.
a 和 b 的并集包含两个集合里的所有元素。
The intersection holds only what is in both: computer science.
交集只包含两者共有的：计算机科学。
The difference, a minus b, keeps what is in a but not in b.
差集 a 减 b 保留在 a 中但不在 b 中的元素。
Membership tests are fast, because Python sets are hash tables.
成员判断很快，因为 Python 的集合就是哈希表。
A hash table stores pairs in an array, and a hash function turns each key into a slot.
哈希表把键值对存在数组里，哈希函数把每个键变成一个槽位。
With seven slots, fifteen mod seven is one, and twenty-two mod seven is also one: a collision.
七个槽位时，十五除以七余一，二十二除以七也余一：这就是冲突。
Chaining keeps a list in the slot.
链地址法在槽位里保存一个链表。
Linear probing tries the next slot instead, so twenty-two moves on to slot two.
线性探测则试下一个槽位，所以二十二移到槽位二。
The load factor is the number of items divided by the number of slots.
负载因子等于元素个数除以槽位数。
As it rises, more keys collide: chains grow longer, or probing visits more slots, and search slows towards order n.
它越高，冲突越多：链越来越长，或者探测要访问更多槽位，查找就慢慢接近 O(n)。
So the table is enlarged and every key is rehashed.
所以要扩大表，并把每个键重新哈希。
Try these. Insert a node in the right order. Build a search tree and give its three traversals. And place four keys into a hash table with linear probing, wrapping round from the last slot.
试试这些：按正确顺序插入一个节点；建一棵搜索树并写出三种遍历；再用线性探测把四个键放进哈希表，到最后一个槽位要绕回开头。
In the exam, describe an ADT by its operations and rule.
考试时，用操作和规则来描述抽象数据类型。
Give linked-list pointer changes in order.
按顺序写出链表指针的修改。
Check a search tree by reading its in-order traversal, which must be sorted.
读一遍中序遍历来检查搜索树，结果必须有序。
And show the mod arithmetic for every hashed key.
每个键的取模运算都要写出来。