User-Defined Data Types
A-Level Computer Science Topic 13 15:14 English narration · English + 中文 subtitles burned in
Chapters
Transcript
A plain string field will happily store nonsense.
一个普通的字符串字段会乐呵呵地存下任何胡言乱语。
Ask for a vehicle type, and someone types Bananas — the program accepts it without a murmur.
要一个车辆类型，有人却输入了"香蕉"—— 程序一声不吭地就接受了。
But if you define your own type, listing only the legal values, that mistake becomes impossible.
但如果你定义自己的类型，只列出合法的取值，这种错误就变得不可能发生。
User-defined types make your code clearer, and let the compiler catch errors for you.
用户定义类型让你的代码更清晰，还让编译器替你抓错。
The right type is the first line of defence.
选对类型，就是第一道防线。
Beyond the built-in types, you can build your own.
在内置类型之外，你还可以构建自己的类型。
Today: enumerated types and pointers, the composite types — records, sets, and classes — how files are organised, hashing, and how computers store real numbers.
今天我们讲：枚举类型和指针、复合类型——记录、集合和类—— 文件是如何组织的、散列，以及计算机如何存储实数。
Let's begin.
让我们开始吧。
Two simple custom types.
两种简单的自定义类型。
An enumerated type is a fixed list of named values — like the days of the week.
枚举类型是一份固定的、带名字的取值清单——比如一周的七天。
A variable of that type can only ever hold one of them; anything else is rejected.
这种类型的变量只能持有清单中的一个；其他任何东西都会被拒绝。
A pointer is different: it holds the memory address of another variable.
指针则不同： 它保存的是另一个变量的内存地址。
Follow it — dereference it — and you reach that variable's data.
顺着它走——对它解引用——你就能到达那个变量的数据。
Pointers are how we build dynamic structures, like linked lists and trees.
指针正是我们构建链表、树这类动态结构的方式。
Three reasons the syllabus gives, and each is worth a mark.
考纲给了三条理由，每一条都值分。
First, a built-in STRING lets you store nonsense in a field that should only ever hold one of a few legal values — nothing stops you writing "banana" into a field meant for a vehicle model.
第一，内置的 STRING 允许你把毫无意义的东西 存进一个本该只放几个合法值之一的字段——没有任何东西阻止你往车型字段里写"香蕉"。
A user-defined type restricts it, and the compiler catches the mistake before the program runs.
用户定义类型会限制它，而且编译器在程序运行之前就抓出这个错误。
Second, real entities are usually a collection of values of different types — a student is a name and an age and a grade, not one thing.
第二， 现实中的实体通常是一组不同类型的值的集合——一个学生是姓名、年龄和成绩， 而不是单独一样东西。
Third, DECLARE Taxi colon Vehicle is self-documenting: a reader knows immediately what it holds, where DECLARE Taxi colon STRING tells them nothing.
第三，DECLARE Taxi 冒号 Vehicle 是自解释的： 读的人立刻就知道它装的是什么，而 DECLARE Taxi 冒号 STRING 什么也没告诉他。
An enumerated type is a fixed list of named constants.
枚举类型是一份固定的具名常量清单。
You write TYPE Vehicle equals, then the names in brackets — M100, M230, T101 and so on.
你写 TYPE Vehicle 等于，然后在括号里列出这些名字—— M100、M230、T101 等等。
Those names now ARE the values of the new type.
这些名字现在就是这个新类型的值。
Declare a variable of that type and you can assign it T102, but you cannot assign it anything outside the list; that is the whole point.
声明一个该类型的变量， 你可以把 T102 赋给它，但不能赋任何清单之外的东西；这正是它存在的意义。
Internally they are stored as small integers, which is why comparing them is cheap.
在内部它们被存成小整数，所以比较起来很省。
Typical uses: days of the week, colours, and status codes.
典型用途：星期几、颜色，以及状态码。
A pointer does not hold data — it holds the memory address of another variable, or NULL, meaning it points at nothing.
指针不保存数据——它保存的是另一个变量的内存地址，或者 NULL，表示它什么也不指。
Here p holds an address, and at that address sits a TNode with a Value of forty-two and a Next field.
这里 p 保存一个地址，而那个地址上放着一个 TNode，里面的 Value 是四十二，还有一个 Next 字段。
To dereference, written p caret, means to follow the address and reach the variable itself, so p caret dot Value is forty-two.
解引用，写作 p 尖号，意思是顺着地址找到那个变量本身，所以 p 尖号点 Value 就是四十二。
Two reasons pointers matter: they build dynamic structures such as linked lists and trees, where each node points to the next; and they let you pass a large structure to a procedure by reference, without copying it.
指针重要有两个原因：它们能构建链表和树这类动态结构，每个结点指向下一个； 而且它们让你能按引用把一个大结构传给过程，不必复制。
Bigger custom types group several values together — the composite types.
更大的自定义类型把好几个值组合在一起——这就是复合类型。
A record holds fields of different types under one name, like a student's name, age, and grade.
记录把不同类型的字段放在一个名字下， 比如一个学生的姓名、年龄和成绩。
A set is an unordered collection of unique values, with operations like union and membership.
集合是一堆无序且唯一的值，带有并集、成员判断这样的运算。
And a class bundles data together with the methods that act on it — the heart of object-oriented programming.
而类把数据和作用于它的方法捆绑在一起——这是面向对象编程的核心。
Pick the one that fits your data.
挑一个适合你数据的。
A set is an unordered collection of unique values.
集合是一个无序的、元素互不重复的汇集。
Two words carry the meaning: unordered, so there is no first or last element and no index; and unique, so adding a value that is already there changes nothing.
两个词承载了它的含义：无序， 所以没有第一个或最后一个元素，也没有下标；不重复，所以把一个已经在里面的值再加一次， 什么也不会改变。
You write DECLARE Available colon SET OF Colour, and assign it with values in curly brackets.
你写 DECLARE Available 冒号 SET OF Colour，用花括号里的值给它赋值。
The operations you need are add, remove and a membership test — IF Green IN Available THEN.
你需要掌握的操作是添加、删除和成员测试——IF Green IN Available THEN。
And because it is a set in the mathematical sense, you also get union and intersection: union gives everything in either set, intersection only what is in both.
而且因为它就是数学意义上的集合，你还有并集和交集：并集给出在任一集合中的全部元素， 交集只给出同时在两个集合中的元素。
The class is the composite type that carries data AND the operations on it — that is what makes it different from a record.
类是那种既带数据、又带操作的复合类型——这正是它与记录的区别所在。
The data fields are called attributes, and here Capacity is one, marked PRIVATE so nothing outside the class can touch it directly.
数据字段称为属性，这里 Capacity 就是一个，标为 PRIVATE， 所以类外面的任何东西都不能直接碰它。
The operations are called methods, and GetCapacity is one, marked PUBLIC so the outside world can call it.
操作称为方法，GetCapacity 就是一个， 标为 PUBLIC，所以外界可以调用它。
And the distinction examiners test: the class is the template, while an object is an instance of that class — one actual taxi with its own capacity, made from the blueprint.
还有一个考官必考的区分： 类是模板，而对象是这个类的一个实例——一辆真实存在、有自己容量的出租车，按图纸造出来。
A question often just asks which type to use, so here is the decision in one line each.
题目常常只问该用哪种类型，所以每种用一句话给出判断。
Use an enumerated type when the variable holds a value from a fixed list.
当变量取值来自一份固定清单时，用枚举类型。
Use a pointer when you need indirection — one thing referring to another rather than containing it.
当你需要间接引用时用指针—— 一个东西引用另一个，而不是把它装在自己里面。
Use a record for a group of fields of different types describing one entity.
当要描述一个实体的一组不同类型的字段时， 用记录。
Use a set when the collection is unordered and unique and you mostly test membership.
当这个汇集是无序的、不重复的，而且你主要是做成员测试时，用集合。
And use a class when you need state AND behaviour together, because that is the only one of the five that carries operations.
而当你需要状态和行为同时存在时，用类，因为五者之中只有它带着操作。
How records sit in a file shapes how fast you can find one.
记录在文件里怎么排列，决定了你能多快找到一条。
A serial file keeps records in the order they were added — fast to append, but slow to search.
串行文件按加入的顺序保存记录——追加很快， 但搜索很慢。
A sequential file keeps them sorted by a key — slower to insert, but quick to search.
顺序文件按某个键排好序——插入较慢，但搜索很快。
And a random file places each record at a position computed from its key, so you can jump straight to it.
而随机文件把每条记录放在 由它的键算出来的位置上，于是你可以直接跳到它。
Match the layout to the job.
让排列方式匹配任务。
File organisation is how the data is laid out on disk; file access is how the program reaches one record.
文件组织是数据在磁盘上如何摆放；文件存取是程序如何找到某一条记录。
Start with the simplest.
从最简单的开始。
A serial file keeps records in the order they were added, with no sorting at all.
串行文件按记录被添加的顺序保存，完全不排序。
Appending is fast — you just write at the end.
追加很快——直接写在末尾就行。
Searching is slow, because you have no idea where anything is and must read from the start.
查找很慢，因为你根本不知道任何东西在哪里，只能从头读起。
That is exactly right for a log or an audit trail, where you write constantly and read rarely.
这恰好适合日志或审计追踪，那里你不断地写，却很少读。
A sequential file is the same idea but sorted by a key field.
顺序文件是同样的想法，但按一个键字段排了序。
Now searching is faster, because you can stop early once you pass the key you wanted, or binary-search.
现在查找快了， 因为一旦越过你要的键就可以提前停下，或者用二分查找。
The cost is insertion: a new record in the middle means shifting everything after it.
代价在插入： 往中间插一条新记录，意味着后面的全都要往后挪。
A random file, also called direct-access, computes each record's position from its key, most often by a hash function.
随机文件，也叫直接存取文件，根据每条记录的键计算出它的位置，最常用的办法是散列函数。
Look up one customer by account number and you go straight there in a single read — very fast.
按账号查一位客户，你一次读取就直接到达——非常快。
The trade-off is that reading in key order is now hard, because the records sit wherever the hash put them.
代价是现在按键的顺序读变得困难了， 因为记录躺在散列把它们放到的任何地方。
That gives us the two access methods to name: sequential access reads from start to end, and direct access jumps straight to a known position.
由此得到需要说出名字的两种存取方式： 顺序存取从头读到尾，直接存取则直接跳到已知位置。
The rule for choosing is to match the structure to the dominant operation — single-key lookups favour random, in-order reports favour sequential.
选择的原则是让结构匹配最主要的操作—— 按单个键查找就选随机，要按顺序出报表就选顺序。
A hash function turns a key into an address — the slot where that record is stored.
散列函数把一个键变成一个地址——也就是那条记录存放的槽位。
Three properties make one good: it must be fast, since you run it on every read and write; it must be deterministic, giving the same address for the same key every single time; and it must spread keys evenly, so no part of the file fills up while the rest sits empty.
三个性质决定它好不好：它必须快，因为每次读写都要跑一遍；它必须是确定的， 同一个键每一次都给出同一个地址；它还必须把键均匀散开， 不至于文件的一部分挤满而其余部分空着。
Three algorithms to know.
要掌握三种算法。
The modulo hash: address equals key MOD N, where N is the number of slots.
取模散列： 地址等于键 MOD N，其中 N 是槽位数。
Folding: split the key into pieces, add the pieces, then MOD N.
折叠法：把键切成几段，把各段相加，再 MOD N。
And a string hash: sum the character codes of the string, then MOD N.
还有字符串散列：把字符串里各字符的编码相加，再 MOD N。
A collision is when two different keys hash to the same address, and with a finite number of slots it is not a possibility but a certainty.
冲突就是两个不同的键散列到同一个地址，而在槽位数目有限的情况下， 这不是可能性问题，而是必然会发生。
Three ways to resolve it.
有三种解决办法。
Linear probing: use the next free slot, wrapping round at the end — simple, but keys bunch up into clusters, and a cluster makes every later search longer.
线性探测：用下一个空闲槽位， 到末尾就绕回开头——简单，但键会挤成一团团，而一团挤在一起会让后面每一次查找都更长。
Chaining: each slot points to a linked list of the records that landed there — no clustering, but it uses more memory for the pointers.
链接法：每个槽位指向一条链表，装着落到这里的所有记录——不会成团， 但要为指针多花内存。
Rehashing: apply a second, different hash function — it spreads keys well, at the cost of more computation.
再散列：换用第二个不同的散列函数——散得很开，代价是计算更多。
Here is the search algorithm in full, because exams ask you to describe it.
下面是完整的查找算法，因为考试会要求你描述它。
Hash the key, read that slot.
对键做散列，读那个槽位。
If the key there matches, you are done.
如果那里的键匹配，就完成了。
If it does not, follow whichever resolution strategy the file uses — the next slot for linear probing, or along the chain for chaining — until you either match or reach an empty slot.
如果不匹配，就按这个文件所用的解决策略继续走—— 线性探测就看下一个槽位，链接法就沿着链走——直到匹配上，或者遇到一个空槽位。
An empty slot means it is not there, and that is what lets the search terminate.
空槽位意味着它不在里面，正是这一点让查找能够终止。
To insert, hash the key and write into that slot, or the next free one if it is taken.
要插入，就对键做散列， 写进那个槽位，如果被占了就写进下一个空闲的。
And one number governs the whole thing: the load factor, records divided by slots.
而有一个数字支配着这一切： 装填因子，即记录数除以槽位数。
Keep it under about seventy per cent and lookups stay close to constant time; let it climb and collisions multiply.
把它保持在百分之七十以下，查找就接近常数时间； 让它继续往上爬，冲突就会成倍增加。
That last trick — computing a position from a key — is hashing.
刚才那个把位置从键算出来的把戏，就是散列。
A hash function turns a key into a slot number, so a lookup is nearly instant.
散列函数把一个键变成一个槽号， 于是查找几乎是瞬间完成的。
But sometimes two keys land on the same slot: a collision.
但有时候两个键落到了同一个槽：这叫冲突。
We resolve it — for example, by chaining, keeping a small linked list at that slot, or by probing to the next free one.
我们来解决它—— 比如用链接法，在那个槽上挂一个小小的链表，或者用探测法，找到下一个空槽。
Keep the table under about seventy percent full, and lookups stay fast.
把表的填充度保持在大约百分之七十以下，查找就一直很快。
Finally, how do computers store real numbers of wildly different sizes?
最后，计算机怎么存储大小相差悬殊的实数呢？
With floating-point — binary scientific notation.
用浮点数——二进制的科学计数法。
A number is a mantissa, the significant digits, times two to an exponent.
一个数是一个尾数，也就是有效数字，乘以二的指数次方。
To normalise, we slide the point until the first significant bit sits right after it — that squeezes out wasted zeros and maximises precision.
为了规格化， 我们把小数点滑动到第一个有效位正好在它后面为止——这挤掉了浪费的零，让精度最大化。
One catch: many decimals, like nought point one, cannot be stored exactly, so tiny rounding errors creep in.
有一个坑：许多小数，比如零点一，无法被精确存储，于是微小的舍入误差就悄悄溜了进来。
Floating-point is binary scientific notation, and it has exactly two fields.
浮点数就是二进制的科学记数法，它恰好有两个字段。
The mantissa holds the significant digits; the exponent holds the power of two to multiply by.
尾数保存有效数字； 指数保存要乘上的二的幂。
The value is mantissa times two to the exponent.
数值等于尾数乘以二的指数次方。
Both fields are stored as two's-complement integers, which is how negatives are handled.
两个字段都以补码整数的形式存放，负数就是这样处理的。
The key skill is reading the mantissa as a binary FRACTION: the first bit after the point is worth a half, the next a quarter, then an eighth, and so on.
关键的本领是把尾数读作二进制小数：小数点后第一位代表二分之一， 下一位是四分之一，再下一位是八分之一，依此类推。
So the mantissa zero point one zero one zero is a half plus an eighth, which is nought point six two five.
所以尾数零点一零一零 就是二分之一加八分之一，等于零点六二五。
With an exponent of two, the value is nought point six two five times four, which is two point five.
当指数为二时， 数值就是零点六二五乘以四，也就是二点五。
Convert one.
来换算一个。
The mantissa is one zero one one zero zero zero zero and the exponent is zero zero zero zero zero zero one one.
尾数是一零一一零零零零，指数是零零零零零零一一。
Take the exponent first: read as a plain signed integer, the exponent is plus three.
先看指数： 作为普通的有符号整数来读，指数是正三。
Now the mantissa.
现在看尾数。
It begins with a one, so it is negative, and you must read it with two's-complement rules — this is the step that costs marks.
它以一开头，所以是负数， 而且必须按补码规则来读——这一步正是丢分的地方。
Written as one point zero one one zero, the sign bit is worth minus one, and the fraction bits after it add a quarter plus an eighth, which is nought point three seven five.
写成一点零一一零， 符号位代表负一，它后面的小数位加起来是四分之一加八分之一，也就是零点三七五。
So the mantissa is minus one plus nought point three seven five, or minus nought point six two five.
所以尾数是负一加零点三七五，即负零点六二五。
Multiply by two cubed, which is eight, and the value is minus five point zero.
再乘以二的三次方，也就是八， 数值就是负五点零。
Now the other direction: store plus two point five in this format.
再看另一个方向：把正二点五存成这种格式。
First convert the number itself — in binary, two point five is one zero point one, since that is two plus a half.
先换算这个数本身—— 二进制里，二点五是一零点一，因为那是二加二分之一。
Now rewrite it as a normalised fraction times a power of two: move the point two places left and compensate, giving nought point one zero one times two squared.
现在把它改写成 规格化小数乘以二的幂：把小数点左移两位并做相应补偿，得到零点一零一乘以二的平方。
From that you can read off both fields directly.
从这里就能直接读出两个字段。
The mantissa is zero one zero one zero zero zero zero — a zero sign bit, then the digits one zero one.
尾数是零一零一零零零零——一个为零的符号位， 后面跟着数字一零一。
And the exponent is zero zero zero zero zero zero one zero, which is two.
而指数是零零零零零零一零，也就是二。
A number is normalised when the first significant bit sits immediately after the binary point, with no wasted leading zeros.
当第一个有效位紧挨在二进制小数点之后、没有浪费的前导零时，这个数就是规格化的。
Why bother?
为什么要这么做？
Because it maximises precision: every leading zero is a mantissa bit carrying no information, and you only have eight of them.
因为它让精度最大化：每一个前导零都是一个不携带信息的尾数位， 而你总共只有八位。
To normalise, shift the mantissa left and decrease the exponent by the same number of places — as shown here, shifting two places left and dropping the exponent from four to two.
要规格化，就把尾数左移，同时把指数减去相同的位数—— 就像这里，左移两位，指数从四降到二。
The value is completely unchanged; only the representation improves.
数值完全没变，改善的只是表示方式。
And the rule for negatives: with a two's-complement mantissa, normalised means the sign bit, a one, is followed immediately by a zero.
负数的规则是：对补码尾数来说，规格化意味着符号位一后面紧跟着一个零。
So the test is that the first two bits differ.
所以判据就是头两位不相同。
Finally, the errors, and these come up every year.
最后是误差，而这些每年都考。
Many denary reals simply cannot be stored exactly in binary.
许多十进制实数根本无法在二进制中精确存储。
Nought point one is the classic: in binary it is a repeating binary fraction, zero zero zero one one zero zero one one repeating forever, so it must be truncated.
零点一是最经典的例子：在二进制里它是一个循环小数， 零零零一一零零一一无限循环下去，所以必须被截断。
Four consequences.
由此有四个后果。
Rounding errors build up over many operations, which is why nought point one plus nought point two is not exactly nought point three.
舍入误差会在多次运算中累积，这就是为什么零点一加零点二并不正好等于零点三。
Comparisons fail, so never test two reals for equality — test that the absolute difference is below a small tolerance instead.
比较会失败，所以绝不要检验两个实数是否相等——而要检验它们的差的绝对值 是否小于一个很小的容差。
Subtracting two nearly equal values loses precision.
两个几乎相等的数相减会损失精度。
And overflow and underflow happen when the exponent runs out of range — too large to represent, or so small it rounds to zero.
而当指数超出范围时就发生上溢和下溢——大到无法表示，或者小到舍入为零。
Where you need exactness, such as currency, use fixed-point or BCD instead.
凡是需要精确的地方，比如货币，就改用定点数或二进码十进数。
Three marks to lock in.
三个要拿稳的分。
First, match each user-defined type to its use — enumerated for a fixed list, a record for mixed fields, a class for data plus behaviour.
第一，把每一种用户定义类型和它的用途对上——固定清单用枚举， 混合字段用记录，数据加行为用类。
Second, know the three file organisations, and how hashing finds a record fast.
第二，记住三种文件组织，以及散列如何快速找到一条记录。
Third, for floating-point, read the mantissa as a fraction and the exponent as a signed integer, then normalise to maximise precision.
第三，对于浮点数，把尾数读成小数、把指数读成有符号整数，再相乘，然后规格化以让精度最大化。
Nail these, and this topic is yours.
掌握这些，这个专题就是你的了。