Data Types & Structures
A-Level Computer Science Topic 10 17:40 English narration · English + 中文 subtitles burned in
Chapters
Transcript
Every value your program stores needs a data type — and picking the right one matters.
你的程序存储的每一个值都需要一个数据类型——而选对类型是很重要的。
Say you store whether an item is in stock.
比如你要存一件商品是否有货。
You could write the word yes, as text.
你可以把"是"这个词当作文本写下来。
But text wastes space, and the computer cannot do logic with it.
但文本浪费空间， 计算机也没法用它做逻辑运算。
A boolean — just true or false — is smaller, faster, and exact.
而布尔值——只有真或假——更小、更快，也更精确。
Choosing the right type, and the right structure, is the quiet skill behind every good program.
选对类型，也选对结构，是每一个好程序背后那项不动声色的功夫。
Data comes in types, and types combine into structures.
数据有各种类型，而类型又组合成结构。
Today: the basic data types, records and arrays, and three abstract structures — the stack, the queue, and the linked list.
今天我们讲：基本数据类型、记录和数组， 以及三种抽象结构——栈、队列和链表。
Let's begin.
让我们开始吧。
Start with the basic types.
先从基本类型开始。
Integer, for whole numbers — counts and IDs.
整型，用于整数——计数和编号。
Real, for numbers with a fractional part — money and measurements.
实型，用于带小数部分的数——金额和测量值。
String, for text in quotes.
字符串，用于引号里的文本。
Char, for a single character.
字符型，用于单个字符。
Boolean, for true or false.
布尔型，用于真或假。
And date, for a calendar date.
日期型，用于日历日期。
The rule is simple: pick the smallest precise type that fits.
规则很简单：选能装下的、最小又精确的类型。
Use a boolean for a flag, never the words yes or no.
标志位就用布尔型，绝不用"是"或"否"这样的词。
Now put that rule to work.
现在来用这条规则。
A shop program stores six things.
一个商店程序要存六样东西。
The number of items in stock is a whole count, so integer.
库存件数是整数，所以用整型。
The price has a fractional part, so real.
价格带小数部分，所以用实型。
The product name is text, so string.
商品名称是文本，所以用字符串。
A size code is a single letter, so char.
尺码是单个字母，所以用字符型。
Whether the item is on offer is a flag, so boolean.
是否在促销是一个标志，所以用布尔型。
And the delivery day is a calendar date, so date.
送货日期是日历日期，所以用日期型。
Each one is the smallest precise type that fits — never text standing in for a number.
每一个都是能装下它又最小最精确的类型，绝不用文本去装数字。
Sometimes several values describe one thing — a stock item has an ID, a category, a cost, and whether it is in stock.
有时候，好几个值描述的是同一样东西——一件库存商品有编号、类别、成本，以及是否有货。
A record holds them all under one name, even though their types differ.
记录把它们全都放在一个名字下面，哪怕它们的类型各不相同。
You define the record type once, then reach each field with a dot — item, dot, category.
你把记录类型定义一次， 然后用一个点来访问每个字段——商品、点、类别。
Use a record when the values always belong together, like one customer or one item.
当这些值总是属于一体时就用记录， 比如一个客户，或一件商品。
Here is how a record is written.
记录是这样写的。
Start with TYPE and the type name, T stock item.
先写 TYPE，再写类型名 TStockItem。
Inside, declare each field with its own type: item I D integer, category string, item cost real, in stock boolean.
里面为每个字段声明它自己的类型： 编号是整型，类别是字符串，成本是实型，是否有货是布尔型。
Close with ENDTYPE.
最后用 ENDTYPE 收尾。
To store data you then declare a variable of that type, item one.
要存数据，再声明一个这种类型的变量，比如 Item1。
And because a record is a type like any other, you can declare a whole array of them, a hundred stock items under one name.
而且因为记录和别的类型一样， 你可以声明一整个数组，一百件库存商品放在同一个名字下。
The type block itself stores nothing — it is only the blueprint, and the variables you declare from it are what hold the data.
类型块本身不存任何数据， 它只是图纸；真正存数据的是你用它声明出来的变量。
When you have many values of the same type, use an array — an ordered collection under one name, reached by an index.
当你有许多个相同类型的值时，就用数组——一个放在同一名字下、用索引来访问的有序集合。
A one-dimensional array is a simple list.
一维数组就是一个简单的列表。
A two-dimensional array is a grid, with rows and columns.
二维数组是一个网格，有行和列。
Each item is an element; the lowest and highest valid positions are the bounds.
每一项是一个元素； 最低和最高的有效位置就是边界。
A single loop walks a list; nested loops walk a grid.
一重循环遍历一个列表；嵌套循环遍历一个网格。
Three words the exam expects.
三个考试要用的词。
An element is one item in the array.
元素是数组里的一项。
The bounds are the lowest and highest valid indices.
边界是最低和最高的有效索引。
The dimension is how many indices you need — one, here.
维度是需要几个索引，这里是一个。
Now the code.
现在看代码。
Declare names as array one to five of string, then assign through an index: names bracket three gets Cara.
声明 Names 为 ARRAY OF STRING， 然后通过索引赋值：Names 放进 Cara。
And to touch every element, loop the index from the lower bound to the upper bound — for i from one to five, output names bracket i, next i.
要访问每一个元素，就让索引从下界循环到上界： i 从一到五，输出 Names ，然后 NEXT i。
Three array routines come up again and again.
有三个数组例程反复出现。
Count or output the non-blank elements: walk the array and test each element against the empty string before you count it.
统计或者输出非空元素：遍历数组，在计数之前先判断每个元素是不是空字符串。
Insert into a sorted array: find the first index whose element is larger, move that element and every later one one place towards the end, then store the new value in the gap.
向有序数组中插入：找到第一个比它大的元素的下标， 把那个元素以及它后面的每一个都往后挪一位，再把新值放进空出来的位置。
A two-dimensional array needs two sets of bounds.
二维数组需要两组边界。
Declare grid as array one to three, one to four, of integer — three rows, four columns.
声明 Grid 为 ARRAY OF INTEGER，也就是三行四列。
Now the rule that costs marks: the first index is the row, the second is the column.
接着是最容易丢分的规则：第一个索引是行，第二个是列。
So grid bracket two comma three gets ninety-nine writes into row two, column three.
所以 Grid 赋值为 99， 写进的是第二行第三列。
To visit every cell you need nested loops, the outer over rows and the inner over columns.
要访问每一个格子就需要嵌套循环，外层走行，内层走列。
Use one-D for a single sequence, two-D when the data has two natural dimensions — a seating plan, a spreadsheet, a board of rows and columns.
单一序列用一维；数据有两个天然的维度时用二维，比如座位表、电子表格，或者一张有行有列的棋盘。
Three operations come up again and again.
有三个操作会反复出现。
The first is a linear search: check each element in turn until you find the target.
第一个是线性查找：逐个检查每个元素，直到找到目标。
In code — for i from one to n, if a bracket i equals target then output found at i.
代码是：i 从一到 n，如果 A 等于目标，就输出「找到于 i」。
Here the target is seven, so it tests four, then nine, then two, then seven, and stops at index four.
这里目标是七， 于是它先看四，再看九，再看二，然后看到七，在索引四处停下。
On average it looks at half the array.
平均要看半个数组。
And notice what it reports: the index, not the value — the position is what the rest of the program needs.
注意它返回的是索引，不是值：程序后面要用的正是这个位置。
The second is a running total — and the same shape finds a sum, a count, a maximum or a minimum.
第二个是累计变量，同样的写法可以求和、计数、求最大或求最小。
For a maximum, start the variable at the first element: max gets a bracket one, so max is three.
求最大时， 先把变量设为第一个元素：Max 取 A ，所以 Max 是三。
Then loop from the second element to n, and if a bracket i is greater than max, max takes it over.
然后从第二个元素循环到 n， 如果 A 大于 Max，就让 Max 接过它。
Nine beats three, twelve beats nine, seven does not.
九胜过三，十二胜过九，七不行。
Two marks hide here: seed it with element one, and start the loop at two.
这里藏着两个分点：用第一个元素做起点，循环从第二个开始。
The third is a bubble sort: pass through comparing each adjacent pair and swapping any that are out of order.
第三个是冒泡排序：逐对比较相邻元素，并把顺序不对的交换过来。
Take five, two, eight, one.
看 5、2、8、1。
Compare the first pair: five and two are out of order, so swap them.
比较第一对：五和二顺序不对，交换。
Compare the next pair: five and eight are already in order, so leave them.
比较下一对：五和八已经有序，不动。
Then eight and one, out of order, swap.
再比八和一，顺序不对，交换。
Eight has now bubbled all the way to the end, and one full pass always parks the largest value in its final place.
八就这样一路冒到了末尾，一整趟总能把最大的值送到它最终的位置。
Repeat passes until one whole pass makes no swaps.
反复进行，直到一整趟都没有发生交换。
The efficient bubble sort is the version the exam wants when it says "improve this algorithm".
当题目说「改进这个算法」时，它要的就是高效版冒泡排序。
Add a Swapped flag so the passes stop as soon as a pass makes no swap, and lower the upper limit by one each pass, because after each pass the largest remaining value is already in its final place.
加一个 Swapped 标志，这样只要某一趟没有发生交换就立刻停止； 并且每一趟把上界减一，因为每趟结束后，剩下的最大值已经落到它最终的位置上了。
Everything so far lived in RAM, and RAM forgets.
到目前为止，一切都住在内存里，而内存会遗忘。
The moment the program ends, every variable in it is gone.
程序一结束，里面的每个变量就都不见了。
A file is data on secondary storage — a disk — and it is kept between runs.
文件是存在辅助存储器上的数据，也就是磁盘，它在两次运行之间被保留下来。
That is how a game remembers high scores, and how a program keeps its records and settings.
游戏就是这样记住高分的，程序就是这样保存记录和设置的。
Files also let programs share data, and let a program restart from a saved state instead of starting over.
文件还让程序之间可以共享数据，让程序能从保存的状态继续，而不用一切从头再来。
A text file holds lines of readable characters, and a program reads them one line at a time.
文本文件里是一行行可读的字符，程序一次读一行。
First open the file, for read.
先以读取模式打开文件。
Then loop while not E O F, while it is not the end of the file.
然后只要还没到文件结束就一直循环。
Inside the loop, readfile pulls the next line into a string variable and you use it.
循环里用 READFILE 把下一行读进一个字符串变量，再使用它。
When the loop ends, closefile.
循环结束后关闭文件。
One exam point: E O F is tested before the read, so an empty file reads nothing at all.
一个考点：文件结束是在读取之前判断的，所以空文件什么也读不到。
Writing works the same way with a different mode.
写入的方式一样，只是模式不同。
Open for write to start a fresh file — it overwrites whatever was there.
用 FOR WRITE 打开会开一个新文件，把原来的内容覆盖掉。
Open for append to add to the end and keep the old lines.
用 FOR APPEND 打开则是加到末尾，保留原来的行。
Then writefile sends one line at a time: here a loop writes a hundred event lines, joining the word event to the number with an ampersand.
然后用 WRITEFILE 一次写一行： 这里的循环写了一百行事件，用 & 把 Event 这个词和数字接起来。
Then close it.
写完要关闭。
Always close every file — if you do not, buffered writes can be lost, and the file may stay locked.
每个文件都一定要关闭，否则缓冲区里的内容可能丢失，文件也可能一直被锁住。
Two details that carry marks.
有两个细节是有分的。
A text file holds strings, so a record is written as one line with its fields joined by a separator character, and every number or Boolean converted to a string first — then split on that separator when reading it back.
文本文件里存的是字符串，所以一条记录写成一行， 各个字段之间用一个分隔符连接，每个数字或者布尔值先转成字符串—— 读回来的时候再按那个分隔符拆开。
And opening a file for WRITE deletes any existing contents, so use APPEND when you mean to add; give the file a meaningful filename with the extension the question asked for.
另外，以写入方式打开文件会删除原有的全部内容， 所以想追加就要用追加方式； 文件名要起得有意义，并且带上题目要求的扩展名。
Now step up a level.
现在提升一个层次。
An abstract data type is a collection of data plus the operations allowed on it, and it is defined by what it does, not by how it is stored.
抽象数据类型是一批数据加上允许对它做的操作， 它由它做什么来定义，而不是由它怎么存储来定义。
Whoever uses it works only through the operations — push, pop, enqueue, dequeue.
使用者只通过这些操作来打交道： 入栈、出栈、入队、出队。
The implementation sits hidden underneath, so it can be replaced with a faster one and no code that uses it has to change.
实现藏在下面，所以可以换成更快的实现， 而用到它的代码一行都不用改。
Three to know for the exam: stack, queue and linked list.
考试要掌握三个：栈、队列和链表。
Now three abstract data types — defined by what they do, not how they are stored.
现在讲三种抽象数据类型——由它们做什么来定义，而不是由它们如何存储来定义。
A stack is LIFO, last-in, first-out: you push onto the top and pop from the top, like a pile of plates.
栈是 LIFO，后进先出：你从顶部压入，也从顶部弹出，就像一摞盘子。
Perfect for an undo history, and for function calls.
非常适合做撤销记录，以及函数调用。
A queue is FIFO, first-in, first-out: you join at the rear and leave from the front, like a line of people.
队列是 FIFO，先进先出：你从队尾加入，从队首离开，就像一排排队的人。
Perfect for scheduling and buffering.
非常适合做调度和缓冲。
Look closely at the stack.
仔细看栈。
One pointer, called Top, does all the work.
只有一个指针，叫 Top，它承担了全部工作。
Push adds an item at the top and moves Top up by one.
入栈在顶端加一项，Top 上移一格。
Pop removes the item at the top and moves Top back down.
出栈把顶端那一项取走，Top 退回一格。
Peek reads the top item without removing it, and two tests ask whether the stack is empty or full.
peek 只读顶端那一项而不取走它， 另外两个测试问栈是空的还是满的。
Notice the base never moves; only the top end changes.
注意底部从不移动，变的只是顶端。
That is why a stack fits undo history, function-call return addresses, expression parsing and backtracking.
所以栈适合做撤销记录、函数调用的返回地址、表达式解析和回溯。
Here is a stack you can see: a pile of books.
这是一个看得见的栈：一摞书。
You can only put a book on the top, and you can only take one off the top.
你只能把书放到最上面，也只能从最上面拿走一本。
The book at the bottom is trapped until everything above it is gone.
最底下那本被压住，要等上面的都拿掉才轮到它。
So the last book on is the first book off — last in, first out, the whole idea of a stack in one picture.
所以最后放上去的那本最先被拿走， 后进先出，一张图就是栈的全部道理。
A queue needs two pointers, because items arrive at one end and leave at the other.
队列需要两个指针，因为东西从一端进来，从另一端出去。
Enqueue adds at the rear and moves the Rear pointer along.
入队在队尾加入，Rear 指针往前走。
Dequeue removes from the front and moves the Front pointer along, and there are the same empty and full tests.
出队从队首移除，Front 指针也往前走，同样有空和满的测试。
But watch: both pointers only ever move forward, so a plain array queue marches off the end and wastes the cells at the start.
但要注意：两个指针只会往前走， 所以普通数组队列会一路走到末尾，把开头的格子浪费掉。
Queues run print spooling, scheduling, breadth-first search and buffering.
队列用在打印排队、任务调度、广度优先搜索和缓冲上。
And here is a queue you can see.
这是一个看得见的队列。
You join at the back and you are served from the front.
你从后面加入，从前面被服务。
Nobody in the middle jumps out, and whoever has waited longest is served next — first in, first out.
中间的人不会跳出来， 等得最久的那个人下一个被服务，先进先出。
Hold both pictures together: a stack adds and removes at the same end, a queue adds at one end and removes at the other.
把两张图放在一起记： 栈在同一端加入和取出，队列在一端加入、在另一端取出。
The third is the linked list.
第三种是链表。
Instead of one solid block, the data lives in separate nodes, and each node points to the next.
数据不是放在一整块里，而是住在一个个独立的节点中，每个节点都指向下一个。
A head pointer marks the start; the last node points to nothing.
一个头指针标出起点；最后一个节点指向空。
Because the links are just pointers, inserting or deleting is cheap — you only rewire a pointer or two.
因为这些连接只是指针，插入或删除都很便宜—— 你只需要重新接上一两个指针。
The trade-off: to reach the tenth item, you must follow the chain from the head.
代价是：要够到第十个元素，你必须从头开始，沿着这条链一路跟下去。
Name the linked-list operations properly, because that is how the question is worded.
把链表的操作名字说准，因为题目就是这样问的。
Insert adds a node and rewires the pointers around it.
插入是加一个节点，并把它周围的指针重新接好。
Delete unlinks a node and passes its pointer on.
删除是把一个节点摘下来，把它的指针交给前一个。
Search follows the chain from the head, comparing as it goes.
查找是从头指针开始沿着链一路比较。
Traverse visits every node in order, from the head until the pointer reaches the sentinel — usually null.
遍历是按顺序访问每一个节点，从头一直到指针变成哨兵值，通常是 NULL。
Set that against an array: the list wins on inserting and deleting, the array wins on jumping straight to element five hundred.
再和数组比一比：链表在插入和删除上占优，数组在直接跳到第五百个元素上占优。
So how do you implement these using an array?
那么怎么用数组来实现它们？
A stack needs the array, stack one to max size, plus one integer, Top, holding zero when the stack is empty.
栈需要一个数组 Stack ，再加一个整数 Top， 栈空时 Top 为零。
To push, first check whether Top equals max size: if it does the stack is full, and that is overflow.
入栈先检查 Top 是不是等于 MaxSize：如果是，栈满了，这就是溢出。
Otherwise add one to Top and store the value at stack Top.
否则把 Top 加一，把值存到 Stack 。
To pop, check whether Top is zero: if it is, that is underflow.
出栈先检查 Top 是不是零：如果是，这就是下溢。
Otherwise take stack Top, then subtract one from Top — nothing is erased, the old value is simply left to be overwritten by the next push.
否则取出 Stack ，再把 Top 减一：什么都不用擦掉，旧值留在原处，下一次入栈会把它覆盖。
A queue in a plain array wastes space, so we bend the array into a circle: when a pointer reaches the last cell it wraps back to the first.
普通数组里的队列会浪费空间，所以我们把数组弯成一个圈：指针走到最后一格时就绕回第一格。
One formula does it — rear becomes rear mod max size, plus one.
一个公式就够了：Rear 变成 (Rear MOD MaxSize) + 1。
Take max size six.
以 MaxSize 等于六为例。
A rear of five gives five mod six plus one, which is six, the next cell along.
Rear 是五时，(5 MOD 6) + 1 等于六，也就是下一格。
A rear of six gives six mod six plus one, which is one, back to the start.
Rear 是六时，(6 MOD 6) + 1 等于一， 回到开头。
One catch: empty and full leave the pointers in the same place, so keep a separate count of the items to tell those two states apart.
有一个坑：空和满时指针位置一样，所以要另外记一个元素计数，才能把这两种状态分开。
Exam question.
考题。
A circular queue sits in an array of size five, indices zero to four.
一个循环队列放在大小为五的数组里，索引从零到四。
Front is three, Rear is three, and one item is stored.
Front 是三，Rear 是三，里面存了一项。
Two items are added — where do the pointers end up?
现在加入两项，指针会到哪里？
Every move is pointer plus one, mod size.
每一步都是「指针加一，再对大小取模」。
The first add takes Rear from three to four.
第一次加入把 Rear 从三移到四。
The second computes four plus one mod five, which is zero, so Rear wraps round to zero.
第二次算 (4 + 1) MOD 5，等于零，所以 Rear 绕回到零。
Front has not moved, and three items are stored — in cells three, four and zero, wrapping past the end of the array.
Front 没有动，现在存了三项：在第三格、第四格和第零格，绕过了数组的末尾。
Now two items are removed.
现在移出两项。
Removing never touches Rear; it moves Front, by exactly the same rule.
移出从不动 Rear，动的是 Front，规则完全一样。
Front goes from three to four, then four plus one mod five is zero, so Front is zero as well.
Front 从三到四， 再算 (4 + 1) MOD 5 等于零，所以 Front 也到了零。
One item is left.
还剩一项。
And here is why we bother wrapping: in a linear array queue those freed cells at the start can never be reused, so the queue reports itself full while most of it is empty.
这就是我们要绕回的原因：在线性的数组队列里，开头那些空出来的格子永远用不上， 队列会在大半是空的时候就报告自己满了。
Remember: remove at the Front, add at the Rear.
记住：从队首移出，从队尾加入。
Last build: a linked list inside an array.
最后一种实现：把链表放进数组。
Define a record, T node, with a value and a next field — and next holds an index, not a memory address, with minus one meaning end of list.
定义一个记录 TNode，里面有一个值和一个 Next 字段， 而 Next 存的是索引，不是内存地址，用 -1 表示链的末尾。
Declare an array of those nodes, then two integers: head, the index of the first node, and free list head, the index of the first unused slot.
声明一个这种节点的数组， 再加两个整数：Head 是第一个节点的索引，FreeListHead 是第一个空闲槽位的索引。
Two chains now live in the same array, the data list and the free list.
现在同一个数组里住着两条链：数据链和空闲链。
Because the free list already owns the spare slots, insertion never has to ask for memory.
因为空闲链已经握着那些备用槽位，插入时根本不用去申请内存。
To insert: take the first slot off the free list, write the value into it, point its next at the node that should follow, and update the previous node's next — or head, if it goes first.
插入的做法是：从空闲链头取下第一个槽位，把值写进去，让它的 Next 指向应当跟在后面的那个节点， 再更新前一个节点的 Next，如果它排在最前面就更新 Head。
To delete: point the previous next past the node, then hand the slot back to the free list.
删除的做法是：让前一个 Next 越过这个节点，再把槽位还给空闲链。
That is a linked structure with the static allocation of an array.
这样既有链式结构的灵活，又是数组的静态分配。
Three marks to lock in.
三个要拿稳的分。
First, choose the right structure and justify it — a record for mixed fields, a two-D array for a grid.
第一，选对结构并给出理由——混合字段用记录，网格用二维数组。
Second, know how to build a stack, a queue, and a linked list from an array and pointers.
第二，要会用数组和指针实现栈、队列和链表。
Third, keep the abstract data type — what it does — separate from its implementation.
第三，把抽象数据类型——它做什么—— 与它的实现分开来看。
Get these, and this topic is yours.
掌握这些，这个专题就是你的了。
The definitions are marked against fixed wording.
这些定义是按固定措辞给分的。
A record is a data structure holding a set of data items — fields — of different data types under one identifier.
记录，是把一组不同数据类型的数据项——字段——放在一个标识符之下的数据结构。
An array holds a fixed number of elements of the same data type under one identifier, each reached by an index, and the largest and smallest valid indices are its upper and lower bounds.
数组，是把固定数量、相同数据类型的元素放在一个标识符之下，每个元素用下标访问， 最大和最小的有效下标就是它的上界和下界。
An abstract data type is a collection of data together with a set of operations on that data.
抽象数据类型，是一组数据连同作用在这组数据上的一组操作。
A stack adds and removes at the same end, the top, so the last in is the first out.
栈在同一端——栈顶——添加和移除，所以后进先出。
A queue adds at the rear and removes at the front, so the first in is the first out.
队列在队尾添加、在队头移除，所以先进先出。
A linked list holds in each node a data item and a pointer to the next node, with a start pointer to the first.
链表的每个节点存一个数据项和一个指向下一个节点的指针，另有一个指向首节点的头指针。
And the traps.
再说陷阱。
A record declaration needs its ENDTYPE and every field needs a type.
记录声明要有 ENDTYPE，每个字段都要有类型。
Test EOF before each read, and use APPEND when the file must keep what it already has.
每次读之前先判断 EOF；文件里已有的内容要保留时用追加方式。
Convert a number before writing it to a text file — NUM_TO_STR out and STR_TO_NUM back.
往文本文件里写数字之前要先转换——出去用 NUM_TO_STR，回来用 STR_TO_NUM。
Push and enqueue test for full first; pop and dequeue test for empty first, and your answer has to say so.
入栈和入队要先判满；出栈和出队要先判空，而且答案里必须写出来。
When inserting a node, set the new node's pointer to the old next node before you change the previous node's pointer, or the rest of the list is lost.
插入节点时，要先把新节点的指针指向原来的下一个节点，再改前一个节点的指针， 否则后面的链表就丢了。
And a linear search must say "not found": initialise the position to minus one and test it after the loop.
另外线性查找必须能说出「没找到」：把位置初始化为负一，循环之后再判断它。