ASCS笔记
CS课堂笔记
写在前面
鉴于本人初入CS,加上这篇笔记是课上笔记,本文以下所有内容不保证完全正确,不保证覆盖所有课本内容。
本文顺序以课上老师的授课顺序为主。
我写下本文,为的是帮助自己更好地学习CS这门科目,因此,希望路过的大佬轻喷。
同时欢迎有需求的读者交流学习。
本笔记内容基于《Computer Science for Cambridge International AS & A Level》,剑桥大学出版社出版,教材为第二版,A-Level课程编号为9618。
PART ONE:理论基础
第一章:数据的表示
数字的内部编码
编码
本章中的讨论仅涉及整数值的编码。在之后的第16章会涉及到非整数值的编码。
计算机出于多种目的会存储各种整数值。有时候会存储一个简单的整数,但要突出这是一个正数。
在这种情况下,Signed integer会被应用。
一个Signed integer由一段包含值的二进制编码和额外的一位用于定义符号,而这种表示方式被我们叫做Sign and Magnitude representation。
从硬件上设计计算机,存在Sign&Magnitude信号,用于记录和计算浮点信息。
Sign&Magnitude中存在One's Complement和Two's Complement。Two's Complement比One's Complement的优点在于更容易计算,因此我们使用Two's Complement在计算机内计算。
有关减法
计算机为避免过度的运算,所以处理数据只做加法。但是计算机还是需要去做减法,我们这里就用到了Two's Complement二次补码。
Two’s Complement
Two's Complement叫做二次补码,计算机可以用它来计算减法。
更多相关内容可参考本文。
接下来举个做减法的例子:
比如说 23-35
0 1 0 1 1 1 - 0 1 0 0 0 1 1
最高位是代表一个正数,所以加几个 leading zero数字大小都不变。(前提是在前面加的是0不是1)
现在变成 23+(-35),就要将正 35 变成-35,使用 Two's Complement作变换,转换为二次补码。
- 首先,将
0 1 0 0 0 1 1的每一位取反,变成1 0 1 1 1 0 0 - 然后,在
1 0 1 1 1 0 0的后面追加一位 1,变成1 0 1 1 1 0 1,即为35的二次补码
现在,直接令 23 加上 35 的 Two's Complement“1 0 1 1 1 0 1 “即可算出 23-35。
位数不够可以在一开始多添几个 leading zero,使得每一位对齐。
这一举动不会影响到数据的大小。
0 0 1 0 1 1 1
+ 1 0 1 1 1 0 1
----------------------
1 1 1 0 1 0 0
现在,我们需要对于计算的结果再进行一次Two's Complement即可转换得到最后的计算答案。
1 1 1 0 1 0 0-> 0 0 0 1 0 1 1-> (+1) 0 0 0 1 1 0 0
至此,0 0 0 1 1 0 0(12)就是取模后的大小了。注意,这里是大小。
我们还知道,第一次计算后得出的1 1 1 0 1 0 0,首位是 1,代表这是一个负数。 因此,原来的符号信息加上转换后的模便是最后答案(-12)。
有关数据溢出
当然,数据溢出的可能性还是存在的:
假如说你的计算机声明的变量只有到八位。第一位是符号位,所以最大可以代表 255。
比如说 200+100,结果是 300,但是因为进位超出了计算机变量能存储的范围,部分进位信息因此丢失导致数据溢出。
单位转换
数据的单位换算总体来讲比较简单。
有一道例题是这样的:
假如在一次数据传输中,获得了2000000bit,需要存储为一个file。
请问该file的大小有多大?
首先让2000000/8,得到有多少个Byte。
如果转换成KiB,需要2000000/8/1024,得到KiB。
这里算出来是244.140625KiB。
在KiB,MiB等单位内选择一个合适的单位。要求数字不要太大,也不需要太多的小数位。
如果要转换为KB,需要2000000/8/1000,得到KB。
这里算出来是250KB。
在KB,MB等单位内选择一个合适的单位。同样要求数字不要太大,也不需要太多的小数位。
字符集
BCD
BCD按照二进制格式来对十进制数字进行编码。
每个BCD的值都是一个无符号的8位整数,值的范围从0到9。
BCD码可以很大程度上简化那些使用十进制设备的数据处理。
比如必须向人显示数字的设备,如时钟和计时器。
一个字节里面只有一个BCD:00001000,00000101,00000000,00000011
BCD封装后,一个字节里面可以有两个BCD:10000101,00000011
ASCII Code
小写字母的ASCII号比大写字母的要大。
我们可以按住alt键,然后同时在小键盘上打出ASCII码。这样可以以ASCII的方式输出。记得把Numlock打开
在考试的时候,会提供ASCII码表。
ASCII码有两种:ASCII和Extended ASCII。
普通的ASCII使用字节中的前七位来表示字符,因此这样的ASCII能表示的字符数就有27个(128个字符)。
但是Extended ASCII使用所有的八位来表示字符,因此这样的ASCII能表示的字符数就有28 (256个字符)。
Unicode
万国码有一百七十多万个文字空间,同时用两个字节代表一个文字符号。世界上所有的Symbol等都可以放在Unicode里。
Unicode使用两个字节储存一个字符。
UTF-8
不过大多欧美国家使用Unicode有点吃亏,因为他们只用其中一个Nibble就可以胜任日常使用了。
因此就诞生了一种新的字符集叫做UTF-8。
一个Byte之中第一个Nibble一般是占满的,
比如0???????或者10??????,前面的几位数字用来告诉接收端如何分组字节。
虽说把UTF-8放在了字符集这里面,但是需要注意的是:UTF-8不是字符集。
有关于UTF-8我的评价是:不太需要理解。
因为现在的语言(Java,Python)什么的都可以自动选取合适的字符集。
而且所有的字符集都是兼容ASCII码的。
中文好多字符是需要3个nibble存储的,所以对于中国来说也是不适用的。因此我国研制了自己的一套字符集叫做GBK。
图像
有位图和非位图,也可以说是矢量图。
我们常见的.jpg,.jpeg格式之类的都是位图,计算机存储每一个像素位上的信息。因此文件一般较大,而且也容易失真。
而.svg等文件类型是矢量图。矢量图记录的是像素的一系列关系,并由计算机直接绘制上色。因此无论如何蹂躏图像都不失真。
简直像极了描点发作图和数学法作图的区别。
位图大小可以用像素数量×颜色深度计算得出。像素数量使用长像素数×宽像素数计算得出。
需要注意以下几点:
- 在这里的计算方法得出的结果单位是bit。如要计算Byte那就将结果除以8。
- 因为File header的存在,这种计算方法只会得出一个文件的大致大小。
File Header
所有的文件都存在一个File Header,用于描述此文件类型,因此系统可以识别File Header来使用正确的解码方式。
一般文件开头的两个字节是File header。
操作系统会先读取File Header。 如果计算机无法识别file header,计算机就不会继续向下读取该文件了,并且让你自己制定一种合适的打开方式。
声音
Analogue的数据是连续的,而Digital的数据是离散的。
用多少空间来记录一个采样的比率叫做一个采样率。采样率越高,音频质量越高。
当然不是采样率越高越好的。因为人类对于特定声音不敏感,所以采样率到一定水准就已经足够使用了。
音频文件的计算公式为: 数据量 (B/s) = 采样频率(Hz) × 采样位数(bit) × 声道数 /8
在这里,单声道代入“1”,立体声即为双声道,代入“2”计算。
注意这里计算的是每秒的数据量
压缩
无损压缩是压缩完还原之后可以还原成原本的样子,比如说文字压缩。
有损压缩就是还原不出原来的样子,但是结果还存在于能接受的范围内。
有损压缩通过丢失一些不容易察觉到,不太影响文件质量的数据进行删除处理,这种压缩方式叫做过滤。比如说.mp3,.jpeg等等。
相比于直接存储数据的绝对大小,也可以存储下一个数据与上一个数据的变化量(相对数值)。这种存储方法可以有效地减少存储开销。
在无损压缩算法中,有这么一个典型例子,叫做Run-length coding.
算法的具体内容是将连续的一些字符转化成个数加字符的形式。
比如:
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW
可以压缩成:
12W1B12W3B24W1B14W
第二章:通信与网络技术
网络的目标与演变
广域网 (WAN)
广域网 (Wide Area Network, WAN) 是一个是一个不受单一地点限制的大型信息网络。
广域网可以通过广域网供应商来促进世界各地的设备之间的通信或者信息共享。
一般来说,广域网是一个局域网 (LAN) 或者其他网络的集合,这里面的每一个元素相互进行通信。你可以将广域网理解成子网络的网络。
互联网 (Internet) 是世界上最大的广域网。
链接广域网的电脑可以享受下面的优点:
- 可以远程控制另一台计算机。
- 可以访问存储在远程计算机上的数据档案。
- 信息可以通过数据的方式传送给远程计算机上的用户。
一个典型的广域网有下面这些特点:
- 广域网会被一个组织或一个公司用来连接站点或分支机构。
- 广域网不属于该组织或公司。
- 广域网需要从公共交换电话网络公司(PSTN)租借。
- 如果租借广域网,PSTN将提供一个专门的通信链路。
- 广域网的传输媒介将是光纤电缆。
- 广域网内数据的传输在交换机 (Switch) 之间运行。
- 交换机用来连接广域网和每个节点。
- 不会有任何终端系统直接连接到广域网上。
局域网 (LAN)
局域网 (Local area network, LAN),是在一个有限的区域内(住宅,学校,实验室,大学校园或者办公大楼等区域)链接不同终端的一个网络。
局域网可大可小,小到一个只有一个用户的家庭网络,或者是一个拥有千万设备的办公网络,都可以叫做一个局域网。
连接到局域网的设备可以享受下面的这些优点:
- 在每台个人电脑上安装应用软件的费用可以通过在连接到局域网的应用服务器上安装软件来节省。(可以在局域网的服务器上安装一个软件,这样就可以不用接着在每个终端上安装一样的软件了。说白了就是节省成本。)
- 使用一个搭建在局域网上的文件服务器,允许用户之间共享文件。
- 可以多个设备共用一个设备,比如说连接到局域网的电脑都可以使用一个打印机来打印文件。
现在的局域网都有下面这些特点:
- 用于组织或者公司的内部组网。
- 局域网可以被组织或者公司拥有。
- 传输介质一般是双绞线电缆或者Wifi。
客户机-服务器模型
客户机-服务器模型 (Client-server model)是一种分布式应用结构,它将任务或工作负载在资源或服务的提供者(称为服务器)和服务请求者(称为客户)之间进行划分。
在这种结构中,当客户计算机通过互联网向服务器发送数据请求时,服务器接受请求并以所请求的数据进行回应。
在当今的网络世界中十分的常见。
还有一个东西叫做瘦客户端 (Thin-client)。瘦客户端的功能就是为用户提供一个输入的窗口,然后再将用户输入的信息打包发送给服务器。最后再将服务器发送回来的数据解析展现给用户。
与其相反的还有胖客户端 (Thick-client)。与首客户端相反,胖客户端会在传送信息到服务器之前,在本地完成一些或者很多运算。
文件的分享
你可以将文件上传到网络上,然后其他用户就可以在服务器上将你共享的文件下载下来。这就像百度网盘一样。
当然我们还有其他的方法,比如说点对点网络模型 (Peer-to-peer model)。
点对点网络不存在一个中心的服务器来让其他主机访问,相反,P2P网络中的每一个节点都相当于是一台主机。
当一台计算机向另一台计算机发送文件请求的时候,那么收到请求的电脑就会变成一个相当于服务器的东西。
与客户机-服务器模型相比,P2P网络模型有如下优点:
- 当许多客户端同时请求一个资源的时候,P2P网络就可以很有效地规避网络堵塞。
- 一个文件地每一个小部分都可以分开进行下载。
- 一个文件的不同部分可以在不同的主机上下载。
而客户机-服务器模型的优点有:
- 允许组织来控制文件的下载和使用。
- 可以提供给文件更好的保护措施。因为所有文件都可以放在一个主机上集中管理。
网络拓扑结构
数据通信系统需要由这些部分组成:发送方,接收方,传输介质,传输的信息和传输协议。
其中,传输的介质可以是空气(WiFi), 也可以是电缆(比如以太网线)。
信息可以通过下面这几种不同的方式来通过介质传输:
- 单工模式 (Simplex mode),数据仅可以单向传输。
- 半双工模式 (Half duplex),数据可以双向传输,但是不能同时双向传输。
- 全双工模式 (Full duplex), 数据不仅可以双向传输,而且还可以同时进行双向传输。
一个数据通信系统可以由一个单独的隔离网络组成。
隔离网络的拓扑结构有好几种可能性。其中最简单的是两个系统通过一个网络链接连接,如下图所示:
这是一个典型的点对点网络 (point-to-point network)。 可以理解成两个机器之间的专用线路。传输可以是单工或者是双工。
早期的局域网拓扑结构一般都是用环形或总线拓扑结构。我们没啥必要解释环形拓扑结构,因为现在环形拓扑结构基本上已经灭绝了。
上图是总线网络 (Bus network)。总线网络包含一条总线,这条总线上连接着不同的终端设备,而且每一个终端之间没有直接连接。
所以说如果两个终端需要通信,就必须要通过总线来进行传播。
这种网络结构是相对比较有弹性的,因为其中一个终端的故障并不会影响到整个网络的瘫痪。
上图是一个完全连接的网状拓扑结构网络 (mesh topology)。
在这个配置中,每个主机之间都会被连接。这些传输是双工的。
但是这样的网络结构一般来说不是特别容易实现,因为链接主机需要的线缆开销就会很大。
所以说我们可以使用另一种网络结构来解决这个问题,那就是使用一台交换机构成的星状网络 (star topology)。
在星状网络中,每个主机都与中心设备具有点对点的链接,而且传输是双工的。
和总线结构一样:一个主机的故障不会影响到整个网络,但是中心设备一定不可以发生故障,否则整个网络就会瘫痪。
星型网络拓扑结构中,所有的设备都直接链接到中心设备上,同时所有设备互相独立,且仅仅连接到中心设备上。
在星状结构中,中心设备也可以用于将网络连接到其他的网络,特别是连接到互联网。
当多个局域网联合在一起,他们就可以形成具有不同拓扑结构和技术的一个大网络。这个局域网的集合就变成了一个混合网络 (hybrid network)。
传输载体
线缆
传输网络的线缆可以有这三种:双绞线 (Twisted pair),同轴线缆 (Coaxial)和光纤 (Fibre optic)。其中,双绞线和同轴线缆都选用了铜作为传输载体。
不同的线缆拥有不同的特性。下表展示了不同线缆的特性:
| ~ | 双绞线 (Twisted pair) | 同轴线缆 (Coaxial) | 光纤 (Fibre optic) |
|---|---|---|---|
| 费用 | 最低 | 高 | 最高 |
| 带宽 / 信息传递速率 | 小 | 大 | 很大 |
| 高频衰减 | 受影响 | 最受影响 | 最不受影响 |
| 抗干扰程度 | 很受影响 | 受点影响 | 最不受影响 |
| 是否需要中继器 | 需要 | 需要 | 一般不需要 |
双绞线电缆被广泛运用在我们的生活之中。一般在家里组局域网就会用双绞线电缆。
同轴线缆一般被有线电视公司和城域网广泛使用,同轴电缆一般不会用于长途电话布线。
光纤电缆是长距离布线的首选技术。光纤电缆是由许多单独的纤维捆扎在一起构成的,而同轴电缆就没有。
无线
除了选用线缆传输,我们还可以使用无线传输 (Wireless transmission)。
有三种选择:无线电 (Radio),微波 (Microwave)和红外线 (Infrared)。
这三种传输类型的本质区别其实是波的频率。
上表格:
| ~ | 无线电 (Radio) | 微波 (Microwave) | 红外线 (Infrared) |
|---|---|---|---|
| 频率分布 | 3kHz - 3GHz | 3-300GHz | 300 GHz - 400 THz |
| 带宽 / 信息传递速率 | —— | —— | → |
| 高频衰减 (主要由天气影响,如雨) |
—— | —— | → |
| 是否需要中继器 | —— | —— | → |
| 定向传播性 | —— | —— | → |
| 墙壁穿透能力 | ← | —— | —— |
| 抗干扰程度 | 无明显趋势 | 无明显趋势 | 无明显趋势 |
“—— —— →”或者”← —— ——“代表向这个方向递增。
有线 VS 无线
一般来说,有线传输通常被称作为“引导媒体”,无线则被称为“非引导媒体”。
当我们比较有线传输和无线传输的相对优势时,还有其他几点需要考虑。
有一些无线传输的频段是被国家禁止使用的。这意味着使用这些频段进行通信必须要经过国家的审批。
在这些频段之外,无线传输就不需要任何许可了。与此同时,在地下布下传输线缆必须先经过土地所有者的授权。
全球通信既可以通过埋在海底的光纤电缆实现,也可以使用卫星传输。
干扰对于无线传输似乎是一个比较大的问题。干扰的程度取决于具体使用的频段。
一般来说,无线传输需要的中继器相比有线传输要少得多。
只有无线网络才可以支撑起现今社会庞大的智能手机网络需求。
在小企业或者家庭内,有线网络和无线网络几乎处于同等地位,因为他们对用户的区别并不是特别的明显:即便有线网络需要提前布线的情况下。
(课本上给出的这些例子怎么想也不是很成系统的一些东西)
我们刚才在全球通信中提到了卫星通信。
卫星通信是现代通信系统的一个重要部分。下图显示了不同类型卫星距离地面的高度:
其中范艾伦辐射带 (Van Allen belt)是含有高浓度带电粒子的区域,会干扰卫星的正常通信。
离地球最远的,处于地球静止轨道 (Geostationary Earth Orbit, GEO)上的卫星是用来提供长途电话和计算机网络通信的。“地球同步”的意思是卫星轨道运行的速度与地球自转的速度相同,所以从地球上看,那颗卫星就会一直在天空上的同一个位置。只需要3颗GEO卫星就可以覆盖全球。
离地球比较近,但不是最近的那一组卫星是中地球轨道 (Medium-Earth-orbit, MEO)卫星。这个位置的卫星主要提供全球定位系统(GPS)服务,覆盖全球至少需要10颗MEO卫星。
最后在近地球轨道 (Low-Earth-orbit, LEO)上的卫星用来填充移动电话网络,覆盖全球至少需要50颗近地轨道卫星。 (虽说现在轨道上已经有上百颗近地轨道卫星了)
卫星最大的问题就是离地面的距离太远,所以延迟就理所应当的成为了一个大问题。所以说现在使用卫星网络一般是有一些专门的应用点,比如在偏远地区使用互联网,或者是使用GPS。
因为现在光纤的发展成本越来越低,高速的数据传输有着更好的媒介,于是乎对于卫星网络的需求就越来越少了。
局域网硬件
有线局域网
在早些时候,同轴线缆是用来组局域网的。不过到现在,双绞线线缆是在局域网中最常见的解决方案。你看见的经典水晶头和以太网口一般都是双绞线。同时,光纤也变得越来越普及。
在总线网络配置中,网络由一个总线和一系列由电缆连接的插口组成。总线的两端有端子 (Terminator),可以有效防止信号反射回总线。随后,每一个终端都会有一根相对较短的电缆,每一端都会有一个RJ-45连接器 (就是我们常见的水晶头), 一端插入总线插座,另一端插入端系统的LAN口。
总线可以使用中继器 (Repeater) 来链接两条总线进行扩展,让信号传达到更远的地方。如果想要扩展信号,那么我们就必须需要中继器。因为远距离传输信号的时候,由于信号的衰减,通信会变得越来越不可靠。
中继器在这里会接受所有输入的信号,并且输出一个满血的输出信号,让信号去到更远的地方。
也有些时候,一个总线网络会用一些分段方式构建。
两个网段会使用一个网桥 (Bridge)链接,网桥会为他所连接的两个网段中的终端系统存储网络地址,这样两个网段就可以互相通信了。
在星型网络结构中,每一个终端系统都具有相同类型的线缆,同时拥有相同的连接器。因为电缆必须要插入中央设备的插口中,所以电缆往往会更长一些。
在星型网络结构中,中心设备可能是一个集线器 (Hub),一个交换机 (Switch)或者是一个路由器 (Router)。现在而言,交换机是最有可能的中心设备:交换机是一种可以将特定的通信引导到特定终端的一个设备。
终端系统上的LAN端口和网络接口卡 (Network Interface Card, NIC)连接。网络接口卡用来为计算机和其他设备提供专用的网络连接,他同时被称作为网络接口控制器、网络适配器或者是LAN适配器:简称网卡。
网卡在制造的过程中都会有一个独特的网络地址,这个地址用来识别安装该网卡的终端系统。这个唯一的网络地址被称作媒体访问控制(Media Access Control, MAC)地址,我们一般叫它MAC地址。MAC地址是一个分配给网卡的唯一标识符。
无线局域网
Wi-Fi (在某些国家叫做WLAN)是一个用于描述无线以太网的术语。
它的正式描述是:IEEE 802.11,它是一个使用无线电频率传输的无线局域网标准。
Wi-Fi局域网的中心设备是一个无线接入点 (Wireless Access Point, WAP),它可以是有线网络中的其中一个终端系统。如果你有一个具有无线功能的路由器,那么他就可以作为一个无线接入点。
只要在无线局域网中的一个设备安装了无线网络接口卡 (Wireless Network Interface Card, WNIC),WAP就可以与Wi-Fi局域网中的终端系统进行通信。
无线网络接口卡是一种将你的设备连接到无线网络的设备,他也被称作无线适配器或者无线网卡。无线网络接口卡使用天线,并使用射频波提供无线数据的传输。
以太网
以太网 (Ethernet)是现代网络世界的两大主导技术之一,以太网主要是用于组建局域网。
尽管以太网在20世纪80年代被发明出来,但是不属于任何机构。后来以太网被电气和电子工程师协会 (IEEE)标准化。
他们的802委员会负责协定了议定书的制定,最后将有线网络的标准定义为IEEE 802.3标准。这个名称有时可以用于替代以太网。
到目前为止,以太网的标准已经迭代了5个版本:标准,快速,千兆,10千兆和100千兆。
名称中的千兆比特部分代表了其数据传输能力。
标准类型的以太网是在局域网上实现的,一般都会配置为总线或者以集线器为中心设备的星型网络类型。
在这两种拓扑中,传输类型都是广播。任何消息对所有的终端都是可用的,而不需要再任何一对端系统之间进行任何受控的通信交换。
最后终端系统会检查消息中定义的目的地地址,以确定信息是否发送到了它应该去到的目的地。
当使用共享介质传输数据的时候,如果两个终端系统同时传送消息,信息就会发生“碰撞”。这是指与传输相关的电压相互干扰,就会导致信息损坏。
我们采用的处理方法是:CSMA/CD (Carrier sense multiple access with collision detection)。
当传输数据的时候,这个系统会通过检测介质中的电压来判断是否存在其他的信息传递。
有这个系统之后,传输的流程就会变成这样:
- 检查传输介质中的电压。
- 如果检测到传输介质中有数据传输,那么就在一段随机时间之后再来检查是否有数据传输。
- 如果传输介质中没有数据传输,那么我们就可以开始传输数据了。
- 在传输数据的过程中,CSMA/CD会继续检测时候有数据碰撞发生。
- 如果没有检测到数据碰撞,就继续传输数据。
- 如果检测到数据碰撞,那么就先暂停传输,随后发出一个干扰信号警告所有的终端站点。然后在一段随机时间后再来一次。
现代的以太网一般由交换机驱动:星型结构中心会有一个交换机,交换机控制数据端到端的传输。
每一个终端系统都是用全双工链路连接到交换机,因此在现在的以太网网络上不会发生数据碰撞。因此在现代的以太网结构中,我们已经不需要CSMA/CD了。
当出现高强度的数据传输的时候,交换机需要能够将传入的消息存储在缓冲区 (Buffer) 中,只到线缆空闲的时候继续传输。
互联网基础设施
互联网服务提供商 (ISP)
互联网设计出来的时候,美中不足的一点就是没有对他的结构有一个明确的定义。但是互联网服务是存在一个层次的。例如:互联网服务提供商 (Internet service provider, ISP)最初的功能是为了给个人或者公司提供互联网接入。现在这个功能被一个叫做“Access ISP”的东西来执行。
这些“Access ISP”随后会接入到一个“中间层”,叫做“区域ISP (Regional ISP)“。区域ISP随后会连接到主干ISP,或者叫做一级ISP。
网络和互联网服务提供商之间通过互联网交流点 (Internet Exchange Points, IXP)联系,一级ISP和主要的互联网内容提供商一起位于层次结构的顶端。
路由器
路由器可不是只存在于我们的局域网中,互联网中同样有一些路由器。
我们可以把互联网想象成承载最多流量的一个网络,它由一组铺设在海底或者陆地上的光纤电缆组成,可以被描述成一个网状网络结构。
这种网状的电缆包含许多链接在一起的点,我们把他称之为节点(Node),在每一个节点上,都有一个叫做路由器 (Router) 的设备。
路由器不仅仅是存在于一般互联网中的网状结构中,他也存在于ISP网络中。每一个路由器都连接到其他多个路由器,他的功能是为了传输选择最佳的路线。
公共交换电话网 (PSTN)
当考虑城市建设的时候,一般来说都没有考虑用于因特网传输的专用链路。所以人类历史就这个问题最悠久的解决方案是普通老式电话服务 (Plain old telephone service, POTS),更正式的描述是公共交换电话网 (Public switched telephone network)。
在早期,电话网络传送模拟语音数据 (Analogue voice data)。 如果我们真的想要将数字数据通过电话网传播,就可以先在发送端使用调制解调器将数字信号转换为模拟信号,经过电话网络传播,然后在接收端使用调制解调器将模拟信号转化为数字信号。
这样的“拨号连接”上网方式能为用户提供中等速率的网络访问。
不过组织或者机构也可以花点小钱购买一种租赁的网络服务,这种网络服务提供了一种永久的,专用的,有传输速度保证的互联网专用链接。
现在来看,大多数的组织和机构都是用租用线路来简历广域网或城域网的。
都2023年了,祖国的网络建设都早早地把主要的通信线路换成光纤电缆了。这就允许ISP提供更好的网络服务,也允许某些人提供自己的ISP服务了。
现在的服务有这样两种:第一种是传统网络接入的宽带网络连接,另一种是WiFi热点技术。
移动电话网络
对于移动电话来说,有另一种方式来提供互联网连接。
在这种情况下,移动电话运营商会充当ISP,为手机提供网络服务。
运营商会建立通信塔等基础设施,只要手机上搭载了合适的硬件和软件,就可以使用这样的基站来传输数据。
网络应用
万维网 (WWW)
“Using the web”和”using the Internet”看起来像是同一种表述,但实际上不是这样的。
互联网是一个互联网络,而万维网是一种运行在Internet上的一个分布式应用程序。
你可以把万维网认为成Internet上的所有网页。
具体来说,web由大量的网站组成,每一个网站都有一个或者多个网页。
网页的特别之处就是他们可以包含超链接。当点击这些链接的时候,就可以直接并且基本上立即访问其他网页。
云计算
云计算通常通过互联网提供计算服务。
一个组织可以选择建立自己的私有云 (Private cloud)。在这种情况下,有一下三中方法:
- 该组织对于创建和管理安装云系统并链接到互联网负责。
- 该组织将会将创建和链接到私有网络的任务外包出去。
- 该组织将可上网的系统的创建和1管理工作外包给第三方。
太抽象了,根本看不懂
另一种选择是使用公共云 (Public cloud)。公共云由第三方云服务商创建,管理和拥有。
云提供的服务与文件服务器和应用服务器提供的服务十分相似。
它们可以通过浏览器访问,因此你可以在任何位置,任何合适的设备商访问公共云 ——— 只要拥有互联网链接。
公共云可以被个人用户或者组织访问。
公共云和私有云之间的最大区别就是系统规模。这种系统由很多大型主机计算机或者服务器群提供服务。
公共云所提供的服务可以有以下几种:
- 提供基础设施。
- 提供平台。
- 提供软件服务。
云服务的很多优势都以为以下这一点:云服务不是很依赖终端设备的配置。对于基础设施的提供,云服务的优势包括在运行软件时能调用服务器端的算力,存储,从而提供更好的性能或者更大的存储容量。
这样的话,我们甚至可以用有限的成本来运行对配置要求更高的应用程序。或者是公司的经费不足以支撑购买这些软件。
还有一点好处是:把计算机托管到云端后,会减少用户对于技术水平的需求。
云服务的劣势大多与公共云有关:云服务提供者可以访问存储在云上的所有数据,所以说云服务用户没有办法确定他们的数据是否被第三方共享。
这是一个有关数据隐私的问题,所以说云服务提供商应该有责任确保用户的数据不会丢失。
云计算的好处有:
- 只要在有互联网的情况下,就可以在任何地方访问云。
- 对本地计算机的配置需求相对较低
- 共享数据变得更容易。
- 安全措施和保障可能更好。
- 扩容更容易。
坏处可能有:
- 必须使用网络连接才可以访问云。
- 在上传数据和下载数据可能需要花费很多时间。
- 安全措施可能比较弱。
比特流
流媒体使用互联网来提供在线音乐,视频等相关服务。
一般来说,在数据被传输之前,它会被存储在一个字节中,可以用“字节流”的形式,一个一个字节的传输数据。
由于涉及到文件的大小,流媒体总是被压缩成一个比特序列,aka“比特流”。
在第一章提到的压缩技术中,将字节流转化为比特流,也是一种压缩方法。
为了使接收端的解码过程正常工作,数据必须作为比特流传输。
对于流媒体来说,“源 (Source)”是一个已经存储了待传输媒体的网站。在这种情况下,使用该资源的其中一个方法是把这个文件下载下来,然后在未来某个时刻方便听或看。
但是如果用户不想要等待漫长的下载时间,他们有另一种选择:流媒体。流媒体可以被描述为按需观看或者收听。
在这种情况下,媒体的传送和媒体的播放是两个独立的过程。传入的媒体数据被接受到终端机上的缓冲区内,然后终端上安装的媒体播放软件会从缓冲区中获取媒体数据并播放。
还有另一种流媒体是实时或者直播传输。在这种情况下,内容是在发送时生成的,例如在观看体育赛事的时候同时直播。
在接收端,我们还是使用刚才提到的缓冲区加载原理,但是在发送端,可能会产生问题,因为可能会有大量的用户同时观看一个直播,造成网络阻塞。
所以现在的解决方式是将媒体传送至很多独立的直播节点,最后再由他们传递给用户。
流媒体技术的一个关键问题是该技术是否能一直为用户提供一个还不错的用户体验。
当媒体被创建出来时,它的意图是要以创造时完全相同的速度将媒体传递给用户。如果一首歌曲在录制时持续4分钟,但如果这四分钟再传输的时候拉长成了六分钟,就听起来很奇怪。
传送内容的过程是由比特率 (Bit rate)决定的。例如,一个质量相对较差的视频可以用300kbps的比特率发送,但是一个质量相当好的音频文件只需要使用128kbps就可以了。
下图展示了一个流媒体原理示意图:
缓冲区 (Buffer)必须按照所使用媒体的正确比特率将数据传递给用户。
发送到缓冲区的数据应该以更高的速率传输给用户。当媒体播放器发现缓冲池中的内容超过了上限和下限,这代表着我们需要向服务器发送获取指令了。
IP
互联网需要技术协议才能运作。标准使用了一套称为TCP/IP的协议(参见第17章)。其中一个方面是IP寻址,用于定义从何处和到何处传输数据。
IP寻址
目前互联网使用IPv4 (Internet Protocol version 4)来进行寻址。
IPv4寻址方案基于32位(4个字节)定义一个IPv4地址。32位的IP地址一共有232个不同的IPv4地址,差不多一共有40亿个IPv4地址。
IPv4是在20世纪70年代发明的,当时PC和手机还没有被发明,当时虽然估计40亿IP地址会允许世界上一半的人使用互联网,但是到现在来说IPv4能提供的IP数量就有些捉襟见肘了。
最初的寻址方案是:IP地址中的一组位(bits)定义一个netID,另一些位定义该网络上面的一个hostID。这样做的目的是为了给互联网上的每一台设备分配一个唯一的,普遍认可的地址。
以netID和hostID分开的IP地址允许数据先定位到netID进行传输,然后再根据hostID分别传发给不同的主机。主机地址只需要在到达指定网络下检查一下就可以了。
在继续往下执行传输之前,我们需要注意host可以是子网下的任何一个设备,比如说路由器。
不同的netID和hostID的划分形式,与他们的IP级别有关系:
| Class | Class identifier | Number of bits for netID | Number of bits for hostID |
|---|---|---|---|
| Class A | 0 |
7 | 24 |
| Class B | 10 |
14 | 16 |
| Class C | 110 |
21 | 8 |
上表中可以知道,最高有效位(从左往右数)表示了网络IP的级别。接着其他的有效位会被分配为netID,其余的有效位定义了hostID。
最大的组织会被分配到A类IP。这些A类IP只能有27个,也就是128个,但是每一个组织都可以有224个不同的host。相比之下,C类IP就一共有221个IP地址,差不多一共有200万个。C类IP中每个组织都只能分配到28个host,说白了就是256个host。
但是问题在于,一旦局域网下支持PC变得普遍,可用的B类netID就太少了。但是如果把C类ID分配下去的话,hostID又太少了。所以说我们现在有更多更好的方法能解决这些问题。
在继续深入探讨之前,我们需要先介绍IP地址的表示。
在传输过程中,该技术是以32位二进制码为地址传输的。为了让用户更轻松的记忆,我们可以使用小数点分割编码地址。这就叫做Dotted-decimal notation。
比如说:
10000000 00001100 00000010 00011110
可以被写成:
128.12.2.30
无类域间路由(CIDR)
第一种改进方法被叫做 无类域间路由 (Classless inter-domain routing, CIDR)。 他保留了netID和hostID的感念,但是取消了固定的结构,允许netID和hostID根据用户的需求划分边界。
实现该目标的简单方法是在地址后面添加一个8位后缀,指定netID的位数。
例如我们把后缀定义为21,这代表着21位会被用于netID使用,剩下的11位还允许指定211不同的hostID。
假如说这样的一串IP地址:
11000011000011000000011000001110/00010101
/后面的00010101代表着最高前21位被定义为netID。
改写成Dotted decimal notation就是:195.12.6.14/21。
由你所见,CIDR不会使用最高位的前几位来定义IP地址是哪一类的。但是他确实会把存在的A,B,C类地址分别转化为后缀为8,16,24的IP地址一起使用。
子网
子网是另一种解决这个问题的方法。通过对hostID搭建一个结构,我们可以更有效地使用hostID。
为了学习这一块儿知识,我们考虑一个中型组织的例子,其中大约有150名员工,每个人都有自己的一台PC。
假设一共有六个部门的局域网,和一个总体的局域网,那么下图就给定了一个通过原始方案来通过局域网链接Internet的原理图。
该组织这下需要7个C级netID:每个局域网一个。每一个netID都指向一个局域网网关。
每个局域网的netID由IPv4地址的前24个bits表示,剩下的8个比特位是hostID。
这意味着在一个局域网中存在256个不同的host。
如果是在所有7个局域网中,可以确定一共由这些数目的host:
256 × 7 = 1792
我们提到过这个公司里面一共有150个个人工作站,因此有1642个IP地址未被使用。这些IP地址就被浪费掉了:因为其他组织也不会使用这些IP。
然而这个组织的子网解决方案只需要分配到一个C类netID即可。
例如分配的IP地址可能是194.10.9.0到194.10.9.225之间,其中netID由前三个字节组成,分别用十进制数194,10,9表示。
子网现在通过定义构成hostID的256个代码的结构来工作。
对于这个组织来说,一个明智的解决方案是使用前三位作为每个局域网的代码,其余五位作为每个工作站的代码。
下图展示了这种布局的示意图:
在因特网上,所有分配的IP地址都有一个指向路由器的netID,然后路由器就需要解释hostID,将数据通过网关传输到某个局域网上的适当工作站。
工作站可以被这样识别:
hostID 为
00001110可能是LAN0 (前三位是000) 上面的第十四个工作站 (第三位到第八位是01110)hostID为
01110000可能是LAN3 (前三位是011) 上面的第16个工作站 (第三位到第八位是10000)
这样的话一共有256个IP地址,显然这个公司的150个工作站还剩下了106个未使用的IP的地址。这剩下的这些IP地址可以保留:为了公司后期的业务扩张而保留。
也就是说,原定需要6个netID的计划,如果使用子网结构,就只需要1个netID。空余出来的netID可以给其他的组织使用。
网络桥接 (NAT)
网络地址转换 (Network address translation, NAT)
网络地址转换是将一个或者多个本地IP地址转换为一个或者多个全局IP地址,同时将全局IP地址转换为一个或者多个全局IP地址的过程,目的是为了为本地主机提供Internet访问。NAT通常是在WAN边缘路由器上实现的,用于实现核心站点,校园网,分支机构和托管站点的Internet接入。
在网络地址转换中,网络设备(通常是路由器或NAT防火墙)为私有网络中的一台或多台计算机分配一个公共地址。
网络地址转换(NAT)是一种将一个IP地址空间映射到另一个IP地址空间的方法,它通过修改数据包的IP首部中的网络地址信息,使它们在流量路由设备中传输。
NAT盒子在互联网上有一个可见的IP地址,所以说从互联网发送或者接收数据完全可以使用这个地址。在内部,IP地址就必须从一些范围内选择一个合适的IP地址作为每一个host的IP。
NAT解决了上述方案中内部网络无法连接到因特网的问题。
需要注意的是,每个地址可以被任意数量的不同的私有网络同时使用。NAT盒子中的接口安装了软件来检查每一个输入和输出的传输。在传入的传输被定向到了正确的内部地址之前,我们可以对他进行安全检查。查看下图的这些箭头,这代表着在内部的网络结构可以使用不同的网络形式来解决问题。
动态和静态IP地址
之前提到:当用户希望与Internet建立连接时,该链接由ISP处理。这样的话,ISP就需要处理很多可用的hostID。然而,ISP就需要同时支持很多hostID。
幸运的是,对于ISP和个人用户来说,这些潜在用户中的许多人将不会参与互联网互动。
所以说ISP会给用户创建一个动态地址 (Dynamic IP-address)。当用户与互联网断开连接的时候,这个IP地址就会被释放掉,然后转让给另一个用户使用。
同样我们也可以向用户分配静态地址 (Static IP-address)。静态IP地址永远不会改变。如果用户准备支付额外费用的话,那么运营商就可以向用户提供静态IP地址。
IPv6
IPv6不同与IPv4,它使用128位来表示IP地址,这样就一共允许2128个不同的IP地址存在。
所有的IPv6地址都是使用冒号隔开的十六进制来记录。代码被分解为16位一个部分,每一个部分都会使用4个十六进制数表示。
如下表所示:
| IPv6 address | Comment |
|---|---|
68E6:7C48:FFFE:FFFF:3D20:1180:695A:FF01 |
一个完整的IPv6的IP |
72E6::CFFE:3D20:1180:295A:FF01 |
在IPv6中,:0000:0000:会被替换为:: |
6C48:23:FFFE:FFFF:3D20:1180:95A:FF01 |
省略最开始的几个0 |
::192.31.20.46 |
一个IPv4地址使用IPv6的形式表示 |
域名
在互联网的日常使用中,用户需要识别特定的网页或者电子邮箱的网址。作为用户,没人喜欢记录一串复杂且不好记录的IP地址,所以我们发明了DNS (Domain name system)
域名服务(DNS)在1983年被发明,DNS服务向互联网主机分配一个可读的域名,并提供一个为单个域名查找IP地址的系统。
DNS系统被设置在一个分层的分布式数据库,并安装在覆盖整个互联网的大量域名服务器上。这些域名服务器以层次结构链接,强大的根服务器位于层次结构的顶端,支撑起整个互联网。
根服务器是可复制的,这意味着其所有数据的多个副本在任何时候都可以被保存。
然后DNS name space会被划分成一些不重叠的区域。每一个区域都有一个主要的名称服务器,上面的数据允许二级服务器从里面读取数据。
DNS名称空间 (DNS name space)是在DNS中注册的所有域名的集合。
因此域名分层导致超过有250个通用顶级域名。如.com .edu 或者.gov。
域名包含在通用资源定位器 (Universal resource locator)中。它可以识别网页或者电子邮件地址。
一个域名是由它向上的路径命名的。比如说eng.cicso.com指的是.com顶级域名中.cisco中域的.eng子域。
通过域名来查找IP地址被称为“名称解析 (name resolution)”。
对于这样的查询,一共有三种可能的结果:
- 如果该域名在被查询的服务器的控制之下,那么将返回一个权威的、正确的IP地址。
- 如果域名不在服务器的控制之下,如果IP地址存储在最近请求的地址的缓存中,仍然可以返回,但它可能已经过时了。
- 如果查询中的域是远程的,那么查询将被发送到根服务器,它可以提供适当的顶级域的名称服务器的地址。这反过来又可以为下一个低级域的名称服务器提供地址。这种情况一直持续到查询到达可以提供权威性IP地址的名称服务器。
第三章:硬件
终于讲到硬件了
关于计算机
计算机系统必须支持三个主要领域的作战能力:
- 处理数据
- 存储数据
- 输入 / 输出数据
一台计算机的核心是CPU (Central Processing Unit)。
数据的存储,输入与输出
存储
先来说存储把。
直接上表:
这些组件由上至下,属性的变化如下:
读写越来越慢
存储空间越来越大
尺寸越来越大
造价越来越便宜
输入
诶这个就很简单了,课本上给了如下几个例子
- 键盘键入
- 用一个指向性的设备 (人话就是鼠标,数位板这样的指向性输入设备)
- 手柄
- 扫描仪
- 麦克风阵列
- (从以上提到的任何数据输入设备读取数据)
- 网络链路
输出
和上面一样的清晰明了:
- 显示屏
- 打印机与绘图机
- VR头显 (好像也属于屏幕没错吧)
- 扬声器
- (写入以上提到的任何数据存储设备)
- 网络链路
嵌入式系统
嵌入式系统 (Embedded system)是在较大的机械或电子系统中具有专用功能的计算机系统。
它作为完整设备的一部分嵌入,通常包括电气或电子硬件和机械部件。
嵌入式系统也可以在更大的系统中运行。系统可以是可编程的或具有固定的功能。
嵌入式系统存在与生活中的方方面面,例如:
- 消费类电子产品:数码相机、MP3播放器、DVD播放器和打印机。
- 家用电器:微波炉、洗衣机、冰箱。
- 医疗设备:心脏监测器、血糖仪和x光机。
- 汽车系统:发动机控制单元(ECUs),安全气囊控制器和防抱死制动系统(ABS)。
- 工业自动化系统:可编程逻辑控制器(plc),监控和数据采集(SCADA)系统,分布式控制系统(DCS)。
嵌入式系统被设计为在一个更大的机械或电子系统中执行一个特定的功能。它们通常是一个完整设备的一部分,包括电气或电子硬件和机械部件。
嵌入式系统被编程以执行它所设计的特定功能。例如,洗衣机中的一个嵌入式系统可能被编程为控制水温和旋转周期。同样,数码相机中的嵌入式系统可能被编程为控制快门速度和光圈。
内存组件
随机存取存储器 (Random-access memory, RAM)和只读存储器 (Read-only memory, ROM)是计算机存储器的两种类型。
RAM是一种易失性存储器,在计算机运行时暂时储存数据。它被称为随机存取存储器,因为任何存储位置都可以被直接访问。RAM用于存储计算机需要快速访问的数据。
ROM是一种非易失性存储器,可以永久地存储数据。它被称为只读存储器,因为它只能被读取而不能被写入。它被用来存储那些即使在计算机关闭时也需要保留的数据。
RAM是易失性存储器,它暂时储存你正在处理的文件。它的速度比ROM快,可以被写入和读出。RAM用于存储计算机需要快速访问的数据。另一方面,ROM是非易失性存储器,永久地存储计算机的指令。它的速度比RAM慢。ROM用于存储需要保留的数据,即使在计算机关闭时也是如此。
有两种一般类型的RAM技术。动态RAM (Dynamic random-access memory, DRAM)由易失电的电容 (capacitors that leak electricity)构成,因此需要定期充电(每隔几毫秒)以保持所存储数据的特性。
静态RAM (Static RAM, SRAM)由触发器 (Flip-flops)构成,当计算机系统打开时,触发器可以无限地存储数据。
ROM有专门的用途,用于存储数据或程序,这些数据或程序将不加改变地反复使用。在通用系统中,最重要的用途是存储bootstrap程序。这是一个在系统打开后立即运行的程序。
在这样的系统中,ROM还有许多其他的用途,其中一些我们将在本书后面看到。此外,ROM被用于许多嵌入式系统。
ROM一共有四种类型:
一般来说,ROM中的程序或数据是作为制造过程的一部分安装的。如果需要不同的内容,必须更换芯片。
另一种选择是可编程ROM (Programmable ROM, PROM)。芯片的制造商向系统建造者提供芯片。系统构建者将程序或数据安装到芯片中。这允许系统构建者在提交整个批次被编程之前测试一些编程芯片的样本。与最简单的ROM一样,程序或数据一旦安装就不能更改。
一种更灵活的ROM类型是可擦除PROM (Erasable programmable ROM, EPROM)。已安装的数据或程序可以被擦除(使用紫外线),并可以安装新的数据或新的程序。 然而,这种重新编程通常需要将芯片从电路中移除。
最灵活的ROM类型是电可擦除式PROM(Electricity Erasable Programmable ROM, EPROM)。顾名思义,它的工作方式与EPROM类似,只是可以用电信号来删除现有数据。这有一个主要的优点,即当内容被改变时,芯片可以留在电路中。然而,该芯片仍作为只读使用。
缓存
当数据必须从计算机系统的一个部分传输到另一个部分时,如果发送数据的速度比接收数据的速度快,就会出现问题。该问题的解决方案是使用缓冲区 (Buffer)。数据在传输到目的地之前先进入缓冲区。
缓冲区的功能类似于一个队列,因此数据按照进入缓冲区的顺序出现。
通常,缓冲区是在计算机内存中创建的。
二级存储
在讨论存储设备之前,我们应该介绍一些术语。
对于任何硬件设备,无论是计算机系统的组成部分还是与之相连的外设,其运行都需要安装适当的软件。这个软件被称为“设备驱动程序”。
这不应该与术语“驱动器”相混淆,特别是与存储设备相关联。
这一术语最初指的是硬件,即介质在物理上向其传输数据或从其读取数据。然而,就像经常发生的那样,这种区别经常被忽略。因此,例如,“hard disk”,“hard disk drive”或“hard drive”具有相同的含义。
磁性介质
磁介质长期以来一直是文件存储技术的支柱。
录音磁带的发明比计算机的发明早了许多年。因此,磁带是第一个存储设备。
相比之下,硬盘是专门为计算机存储而发明的。硬盘也利用磁化来写入数据,它是在磁带首次用于存储几年之后出现的。
对于任何一种类型的磁性介质,与它的相互作用是由一个读头和一个写头控制的。磁头使用的基本物理定律是:磁化状态会影响电学特性,写头使用相反的规律。
虽然它们是独立的设备,但两个磁头会合并为一个读写磁头。磁化的两种不同状态被解释为输入或输出。
磁盘的结构一般遵循这些特性:
- 磁盘里面有很多层盘。
- 每一层盘的两面都可以存储数据,读取或者写入。
- 盘的转动速度是一致的。
- 读写头被连接到驱动器臂上,驱动器臂允许读写头在盘片表面上移动。
- 每个读写头的运动与其他层读写头的运动同步。
- 在读写头与盘面之间有一层空气,防止磁头接触磁盘表面。
光学介质
与磁带介质一样,光存储是由与计算系统无关的现有技术发展而来的。
光盘(CD)演变成CD数字音频(CD-DA),这成为CD-ROM中使用的技术。它被广泛用于分发软件,但还是无法所谓软盘的替代品。
后来出现的读写版本(CD-RW)最终意味着CD完全可以替代软盘。
然而,CD现在已经让位于DVD(最初是“数字视频光盘”,但后来改名为“数字多功能光盘”)。
最新和最强大的技术是蓝光光碟(BD)。
光盘驱动器的设计原理图如下图所示。它可以读取波长为780纳米的红外激光CD或波长为680纳米的红色激光DVD。
我们可以忽略驱动器构造的细节,而专注于它如何运作的原理。
从磁盘读取数据的过程的重要特性如下:
- 光盘有一条从表面的内端到外缘的螺旋轨道。
- 在读取数据的过程中,光盘会转动。
- 同时,激光会持续聚焦在螺旋轨道上。
- 光盘的表面凹凸不平,有坑(pits)和地(lands)。
- 发射的光线会从盘面反射。
- 坑反射与地反射之间的差异是可被检测。
- 探测器接收到的光的强度差可以解释为1或0,以便从光盘中读取二进制代码。
对于CD-RW和DVD-RW技术,光盘的反射面是由一种特殊的合金材料制成。当数据被写入光盘(“烧录”过程)时,这种材料会吸收激光所产生的热量使材料变为液体形式。
根据激光强度的不同,材料冷却后会恢复成晶体或非晶态固体形式。
当光盘读取时,激光从晶体固体反射而不是从非晶固体反射,从而允许编码为1或0。
固体介质
尽管光学存储技术不断地改进,固态存储器一直是一个巨大的竞争对手。
固态存储器的基础是 “闪存”存储器 (“Flash” memory),这是一种没有运动部件(如硬盘的读写头)的半导体技术。
这样的电路由作为记忆单元的晶体管阵列组成,在这里常用的技术称之为”NAND”,因为其基本电路类似于NAND逻辑门。
所有的存储单元串联在一起,对存储器的写入和读取的操作是由 NAND闪存控制器 (NAND flash controller)。它的特别之处在于,存储单元块的内容可以“在瞬间”被全部删除。
此外,在将数据写入内存中的一个单元区块之前,必须将该区块内的所有内容先删除。一个内存块有很多好几页内存组成,在读取数据时,一次操作只可以读取一页数据。
最常使用的是在记忆卡 (Memory card)或USB闪存驱动器 (USB Flash drive, or Memory stick)。
在后一种情况下,闪存被集成到一个设备中,该设备的内存芯片连接到一个标准的USB连接器。这是目前可移动数据存储的技术选择。
由于诸如相变随机存取存储器(PRAM)等替代技术已经在开发中,这种USB闪存技术一统江山的现状会持续多久尚不确定。
固态硬盘 (Solid state drive, SSD)是现在市面上很常见的存储产品。由于固态硬盘没有移动部件,像机械硬盘那样的读写头,很多人认为固态硬盘的存储完全可以伴随我们一辈子。
但实际上不是这样的。
随着我们对固态硬盘的使用,里面的内存颗粒会慢慢退化,进而丢失数据。不过好消息是我们有方法可以检测出有问题的部分并加以修正。
SSD与传统硬盘相比最大的优点就是读取速度超快。
通用输出设备
显示
在第1章我们讲述了如何将图像存储为由像素构成的位图(bitmap)。
屏幕显示也是基于像素的概念,但有一个主要的区别。
一个屏幕像素由三个子像素组成,通常分别代表红、绿、蓝。
通过改变各个子像素发出的光的水平,可以显示出全范围的颜色。
显示技术这几年迭代的速度十分的快。
在最初的阴极射线管(Cathode ray tube ,CRT)技术中,每一个像素没有单独的组件支撑起发光的任务。
屏幕的内表面覆盖着荧光粉,当电子落在这种荧光粉上时候屏幕就会发光。通过控制电子束的方向,来点亮特定的像素。
彩色CRT显示器有独立的红色、绿色和蓝色荧光粉,以像素阵列排列。
现在,平板显示技术占据市场的一大半。
以液晶显示技术 (Liquid-crystal display, LCD)为例:它使用包含液晶的单个单元来创建每个像素。
像素矩阵由一个统一的背光 (Backlight)来照明,每个像素都可以控制光的传输,从而创建屏幕上的图像,如下图所示:
背光照明通常由发光二极管(LED)提供。
偏振光会指向像素矩阵,并且在像素矩阵和屏幕之间放置更多的偏振器。
如果电压施加到单个像素单元,就会影响液晶分子的排列,然后改变光的偏振光,从而改变屏幕上显示的内容。
文本输出
有两种技术已经开始主导从计算机系统中存储的数据打印文档。这些是喷墨打印机 (Inkjet printer)和激光打印机 (Laserjet printer)。这两种技术都可以用于打印文本或图像。
喷墨打印机的工作原理如下:
- 填入一张纸
- 打印头在纸上移动,将墨水打在纸上
- 纸张向前移动一点位置,打印头再次在纸上移动。
- 这个过程一直持续到纸张完全打印出来。
- 打印头由喷嘴组成,将液滴喷在纸上。墨水从一个或多个墨盒供应到打印头。
激光打印机的步骤就相对复杂些了:
- 给硒鼓施加一个电荷。
- 硒鼓开始旋转。
- 在每一个步骤中,激光束被镜子和其他光学组件引导到硒鼓上的不同位置。
- 被激光照射到的硒鼓表面会使得电荷存在或者剥离。
- 这个过程重复执行,直到整个硒鼓上面产生了完整的静电图像。
- 硒鼓被涂上一层带电的碳粉,这些碳粉只粘在硒鼓表面被释放电荷的位置。
- 硒鼓在一张赋予电荷的纸上面移动。
- 最后将纸张排出的同时,使用加热过的轮子来融化碳粉,是的碳粉融合,形成图像。
- 在打印下一张文件之前,硒鼓上面的电荷会全部被排掉。
通用输入设备
键盘允许用户输入文本数据。
在文本输入过程中,似乎只要按下一个键,就会立即将相应的字符传输到计算机屏幕上,但这是错误的。按键必须先转换为字符编码(Character code),然后传输给处理器。随后,处理器会在操作系统的控制下,确保文本字符在屏幕上显示。
如果使用键盘发起某些操作,也会发生相同的过程,例如使用快捷键组合。不同之处在于,处理器必须采取所请求的操作进行响应。
为了实现这个功能,键盘有电路和它自己的微处理器和ROM芯片。键盘如何工作的重要细节如下:
- 按键位于按键矩阵 (Key matrix)的正上方。按键矩阵由一组行列导线组成。
- 按下一个按键后,按键会与导线产生接触,这就会使得行列导线连通,从而允许电流通过。
- 随后,微处理器会不断地检测是否存在电路闭合。如果电路闭合,那么微处理器就可以识别出哪里出现了电路闭合。
- 然后,处理器使用存储在ROM中的数据来识别与该交叉点相关联的字符代码,然后将这个字符发送给计算机。
GUI
通过与屏幕的交互,用户可以通过多种方式输入数据。
很久之前,计算机系统用户只能使用键盘和鼠标向电脑交互,然后使用屏幕作为显示器。而且当时的UI十分的简陋,用户的屏幕上只能生成一个菜单,用户可以通过从菜单中输入一个数组来选择一个选项。
随着图形化用户界面 (Graphical user interface, GUI)的普及,用户使用计算机的体验又更上一层楼。具体就是今天的所有图形化操作系统一样,直观,易操作。
触摸屏
触摸屏有两种:电阻式触摸屏 (Resistive touch screen)和电容式触摸屏 (Capacitive touch screen)。
电阻式触摸屏的上层屏幕不是刚性的,所以当手指按压屏幕的时候,屏幕会发生弯曲。这种弯曲就可以被下层检测出阻值的变化,从而推算出手指触摸的位置。
但是电阻式触摸屏有一个显著的缺点:他只能支持单点触控,也就是说,只允许同时出现一个物体触控屏幕。
另一个是电容式触摸屏。它运用了“人体本身是一种带电体”的原理实现了触摸屏。
电容式触摸屏不再需要一个软皮屏幕作为表面了,因为当你的手指触碰屏幕的时候,下层的电路元件会检测到电容的变化。
现在最有效的触控技术是基于互电容的投射性电容触控(Projective capacitive touch, PCT)技术。这种技术允许我们在屏幕上多点触控。
影像输入
在计算机中存储和使用图像(图形)数据有几种方法。
网络摄像头 (Webcam)是一种用于将视频图像流式传输到计算机系统的设备。
数码相机 (Digital camera)可以连接到电脑。当链接到电脑时,储存的图像或视频就可以下载到电脑上。
另一种选择是使用扫描仪 (Scanner)。
实际上,扫描仪颠倒了打印过程,它获取图像并从图像中创建数字表示。
首先一张包含图像(可能是文本)的纸被固定在一个固定的位置,光源从纸的一端移动到另一端。它覆盖了纸张的宽度。
反射光被一个由镜子和透镜组成的系统引导到一个电荷耦合器件(Charge-coupled device, CCD)上。随后CCD就会向计算机发送数据。
你需要了解下面这些有关于CCD的有趣事实:
- CCD由光敏单元阵列组成
- CCD产生的电响应与每个电池的光强成正比
- CCD需要一个模数转换器 (Analogue-to-digital converter)来产生数字值并传输到计算机。
声音的输入与输出
语音输入输出
IP电话 (IP Telephony)和视频会议 (Video conferencing)是两种同时需要语音输入和语音输出的应用。此外,语音识别可以作为输入数据到计算机的替代技术,而语音合成正被用于越来越多的应用。
我们需要一个麦克风 (Microphone)来完成声音的输入,这是一种带有隔膜的设备。
麦克风中有一种柔性材料,它会因传入的声音而振动。如果膜片连接到合适的电路,振动会引起电信号的变化。
电容传声器采用电容变化作为机构;另一种选择是使用压电晶体。模拟电信号通过模数转换器 (ADC)转换成数字信号,以便在计算机内部进行处理。
同样我们需要一个扬声器 (Speaker)完成音频输出工作。它的工作原理实际上是输入的反向过程。
来自计算机系统的数字数据通过数字模拟转换器转换为模拟。模拟信号以变化的电流的形式供给扬声器。
在大多数扬声器中,电流流过一个线圈,线圈悬浮在扬声器中永磁体提供的磁场中。随着电流的大小和方向不断变化,线圈向前和向后移动。
这种运动控制着隔膜 (Diaphragm)的运动,然后隔膜会产生声音。
第四章:逻辑门与逻辑电路
布尔逻辑与问题陈述
这里有一条陈述:
俄罗斯比新加坡更靠北吗?
无论这是不是一个低智商问题,他只有两个答案:是或者不是。
放在布尔值里面就是TRUE和FALSE。
我们现在分别假设了以下两个陈述:
如果天气预报说一会下雨或者现在正在下雨,你就应该出门带伞。
只有在工作时间中并且屋内气温高于25°C,才可以开启空调。
像这样的陈述,我们管他叫做问题陈述:
问题陈述:依赖于一个逻辑命题或者两个以上逻辑命题组合的句子。
布尔运算器
三个基本的布尔运算器分别是AND, OR和NOT。
简单说下每一个的表述,A与B都存在两个情况:TRUE或FALSE
AND:若A为TRUE,B也为TRUE,则A AND B输出为TRUE。OR:A或者B两者有一个TRUE,则A OR B输出为TRUE。NOT:如果A为FALSE,则NOT A为TRUE
像这样,我们在上一个小节中列举的例子就可以使用布尔运算器符进行表示了:
Take_umbrella = TRUE IF (raining = TRUE) OR (rain_forecast = TRUE)AC_on = TRUE IF (office hours = TRUE) AND (temperature > 25)
现在我们陈述的问题已经变成了像这样的条件语句。我们管这种语句叫做逻辑表达式:
逻辑表达式:使用布尔运算符组合的逻辑命题,可以推出一个确切的结果。
任何逻辑表达式都可只使用布尔运算AND, OR和NOT表示,但是只用他们三个就有些麻烦,不如使用一些其他的布尔运算:NAND,NOR和XOR
NAND:如果A是FALSE或者B是FALSE,则A NAND B输出为TRUE。NOR:若A为FALSE,B也为FALSE,则A NOR B输出为TRUE。XOR:如果A是TRUE或者B是TRUE,而且两者都不能同时是TRUE,A XOR B会输出为TRUE。
等到了学逻辑门的那一节,我再画一个汇总表格。
真值表
真值表简单又强大,可以用来表示任何逻辑表达式或者描述逻辑电路的可能输出结果。
在真值表内,我们将TRUE定义为1,FALSE定义为0。这样可以很简单地表示出有关布尔运算的任何逻辑。
真值表中的表头分A,B和X。
A列和B列代表最初开始的值,而X列则代表经过逻辑运算之后得出的值。
也可以通过一个等式表示:X = A AND B。
这里我们以AND作为一个例子:
| A | B | X |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
逻辑电路与逻辑门
构成计算机系统的内部电路都由逻辑电路运行。这些电路的每个状态要么就是开,要么就是关。(1和0)
逻辑电路由一个叫做逻辑门的部件组成,每一个不同的逻辑门都对应着一个布尔运算。
逻辑门都有他们自己的符号,下图展示了每种逻辑门所对应的布尔运算,图标,和真值表。
特别提及以下几点:
NOT门是一个特例,由于他的输出是他的输入的相反值,NOT只有一个输出。NAND门实际上是AND门紧接着跟了一个”NOT”。NOR门实际上是OR门后面跟了一个”NOT”。NAND和NOR门产生了与AND和OR一样的互补输出。XOR是比较输入的两个数据是否不同。相同输出0,不同输出1。
如果想要从真值表构建逻辑电路,我们首先要创建逻辑表达式。
要做到这一点,我们只需要看看真值表里面输出为1的行。
| A | B | C | X |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 |
我们发现表格中有三行的输出为1,这三行分别是:
A = 0, B = 0 and C = 1A = 0, B = 1 and C = 1A = 1, B = 0 and C = 0
以上三行中出现的and不代表逻辑运算
每一行都可以转换成这样的逻辑表达式:
NOT A AND NOT B AND CNOT A AND B AND CA AND NOT B AND NOT C
然后再将这三行结合起来:
1 | NOT A AND NOT B AND C |
现在这个结果就可以用于创建逻辑电路了,但是这个电路是非常复杂的。
在后面的第19章,我们会去讲解如何在指定逻辑问题下写出最简便的电路。
第五章:处理器基本原理
冯·诺依曼结构
初中小宝宝都知道的基本知识:
冯·诺依曼是第一位解释计算机基本结构原则的人。
符合冯·诺依曼结构 (von Neumann model) 的计算机符合以下几个条件:
- 处理器 (CPU) - 负责处理数据
- 处理器可以直接访问内存
- 处理器按顺序执行指令
- 内存包含一个“s存储程序 (Stored program)”和该程序所需的数据
- ‘存储程序’可以在任何时候被另一个程序替换
- 存储程序由独立的指令组成
中央处理器(CPU)的结构
中央处理器 (Central Processing Unit),简称CPU。
结构图示如下:
然后我们拆开讲解:
CPU的活动部分
CPU的主要活动部分有两部分:
Arithmetic Logic Unit (ALU) :算术逻辑单元
算术逻辑单元是中央处理器的执行单元,进行整数运算的结构。
这是个能实现多组算术运算和逻辑运算的组合逻辑电路,是所有中央处理器的核心组成部分。
用逻辑门构成的算数逻辑单元,主要进行二位元的算术运算,比如说加减乘。(没有整数除法)
Control unit : 控制单元
控制单元负责程序的流程管理,是整个CPU的指挥和控制中心。
由三个部件组成:
Instruction Register (IR) : 指令寄存器
Instruction Decoder (ID) : 指令译码器
Operation Controller (OC) : 操作控制器
基本功能是从内存取指令、分析指令和执行指令。
在控制单元内有一个重要部分,那就是时钟。
控制单元通过时钟来同步处理过程。
时钟分两种: Internal clock 和 System clock
Internal clock控制处理器内活动周期。
System clock控制处理器外部活动。
寄存器
Register,叫做寄存器
寄存器是CPU内部用来存放数据的一些小型存储区域,用来暂时存放参与运算的数据和运算结果。
之前提到过,寄存器在所有的存储单位里面,与CPU的交互是最快的,造价也是最高的。
因为寄存器的位置挨着ALU (算术逻辑单元),所以的读写速度会比较快。
寄存器的存储空间都很小,差不多就16、32或者64bits。
寄存器有通用的(General purpose),也有专用的(Special purpose)。
如果只存在一个通用寄存器,我们会称其为累加器 (Accumulator)。
上面说:累加器一种通用寄存器,会在ALU(算术逻辑单元)执行指令之前和之后存储一个值。
或者说:累加器是一种寄存器,用来储存计算产生的中间结果。
如果没有累加器的存在,在每次进行一次计算(加法,乘法,移位等)之后都会把结果写进内存,即便这个结果会马上在接下来的一个运算中直接使用。
这样就太慢了。
专用寄存器也各不相同。下面这张表列出了一些专用寄存器。
| Register name (寄存器名称) |
Abbreviation (缩写) |
Register’s function (功能) |
|---|---|---|
| Current instruction register (当前指令寄存器) |
CIR | Stores the current instruction while it is being decoded and executed. (在对当前指令进行解码和执行时存储该指令) |
| Index register (变址寄存器) |
IX | Stores a value; only used for indexed addressing. (可以存储一个值,而且只用于索引寻址) |
| Memory address register (储存器地址寄存器) |
MAR | Stores the address of a memory location or an I/O component which is about to have a value read from or written to. (存储即将对其进行读取或写入的内存位置或I/O组件的地址) |
| Memory data register (内存资料寄存器) |
MDR | Stores data that has just been read from memory or is just about to be written to memory. (存储刚从内存中读取或者即将写入内存的数据) |
| Program counter (程序计数器) |
PC | Stores the address of where the next instruction is to be read from. (存储从哪里读取下一条指令的地址) |
| Status register (状态寄存器) |
SR | Contains bits that are either set or cleared which can be referenced individually. (用来存放指令招待后的有关CPU的状态) |
系统总线
System bus,又名曰系统总线。
不过我们需要先理解什么是总线(Bus)。
总线是连接多个部件的信息传输线,是各部件共享的传输介质。
而系统总线,是CPU、主存、I/O设备各大部件之间的信息传输线。
系统总线分为三部分:地址总线 (Address bus), 数据总线 (Data bus) 和 控制总线 (Control bus):
CPU,内存和I/O与这三部分的总线的关系如下图所示:
接下来一个一个说这些总线都是写啥。
地址总线
定义:
地址总线 (Address bus):用来指出数据总线上的源数据或目的数据在主存单元的地址或I/O设备的地址。
地址总线的唯一功能是携带地址。
当控制单元给到了一个命令后,地址会从MAR(储存器地址寄存器)中加载到总线上。
一个地址制定了内存中的一个位置,或者一个待接受的数据,亦或者是从中读取数据的一个I/O组件。
地址总线是单向的,所以说它只能向内存控制器 (Memory controller)或者I/O控制器 (I/O Controller)发送地址,不能用于将地址传回到CPU。
地址总线的带宽定义了地址的二进制代码中的位数。
以一个很基础的计算机系统为例子:总线带宽是16位,因此它允许65536个 (216)内存位置被直接寻址。
不过对于现代计算机系统来说,这点儿内存是完全不够用的:即便将地址总线的宽度增加到32位,也仅仅允许40多亿个地址进行直接寻址。
因此当内存容量比直接寻址大得多的时候,我们会使用到一些特殊技巧。
数据总线
数据总线 (Data bus):用来传输各功能部件之间的数据信息。
数据总线的功能是传送数据,传输的数据可以是指令,地址,也可以是一个确切的值。
数据总线是双向的(Bidirectional),这意味着它可以将数据从CPU传输到内存,也可以从内存传输到CPU。
同样的,数据总线也可以选择将数据传入I/O设备,或者从I/O设备传出数据。
在上面的那张图里面,没有明确表示出从输入设备发来的数据是先传输到CPU还是存储器里面,这么做是有依据的。
比如:部分计算机系统只允许数据存储在内存之前输入CPU,也有的系统允许数据直接传输到内存。
控制总线
控制总线 (Control bus): 用来发出各种控制信号的传输线。
书上没有定义
控制总线的主要用途是传送定时信号。
控制总线以时钟周期规定的时间间隔,传输定时信号,这就确保了一个组件传输数据的时间和另一个组件读取数据的时间同步。
数据总线也是双向的(Bidirectional),数据总线将信号从控制单元传输到任何其他的系统部件,或者将信号传回到控制单元。
数据总线没啥必要拓宽带宽,所以数据总线一般有八条导线。
左右系统性能的因素
首先是处理器时钟速度。
处理器时钟速度可能是决定系统处理速度的一个重要因素。因为一个时钟周期定义了任何操作可以采取的最短时间。但是“可能是”也是有原因的,因为并不是所有的部件都可以像CPU那样飞速计算。
因为这个问题,一个现代的CPU的结构远比我们讨论的CPU结构复杂。
比如说,现在的CPU基本都是多核的,每一个核都是一个单独的处理器,CPU性能也会随着核心数量的增加而增加。而且现代CPU的高速缓存一般都全部封装在CPU的内部,因此达到最快的访问速度。
在继续下面的内容之前,我们需要了解什么是字。
字
没错,这东西就叫字。
*一个小的字节数,可以由计算机系统作为一个单元处理
计算机进行数据处理时,一次存取、加工和传送的数据长度称为字 (Word)。
计算机的每个字所包含的位数称为字长。
一个字通常由一个或多个(一般是字节的整数位)字节构成,计算机的字长决定了其CPU一次操作处理实际位数的多少,由此可见计算机的字长越大,其性能越优越。
多多少少与你操作系统的位数有关,典中典的字长,有16、32或者64位,分别是2、4、8字节。
字长将会影响组件存储容量和架构方面的设计。比如说,寄存器的大小一般都会与字长匹配,字长也会影响总线带宽。
I/O
I/O,全称(Input/Output),代表输入/输出。
我们一般指数据在内部存储器和外部存储器或其他周边设备之间的输入和输出。
每一个I/O设备都会被连接到一个叫做“端口”的接口,每个端口都连接到I/O或者设备控制器 (Device controller)。
顺带一提设备控制器 (Device controller)负责处理CPU和I/O设备之间的交互。
如果连接的I/O设备是计算机系统的一个组成部分,我们就将连接它的端口叫做内部端口。
反之,连接其他外围I/O设备的端口,叫做外部端口。
USB
简单说下USB。
USB,全程 Universal Serial Bus,译为通用串行总线。
现在你可以在几乎任何设备上见到它。
USB的出现至关重要。在USB诞生之前,普通用户一般不会去尝试添加外设,因为当时添加外设需要一定的技术知识。
USB的出现推动了即插即用技术的发展,即插即用技术诞生的目标就是消除人们对于技术水平的需求,所以任何计算机用户都可以连接他们需要的外设。即插即用只有通过创建USB标准才能实现。
*USB是一条总线,USB驱动器存储数据并连接到USB端口,USB端口允许数据沿着总线传输。
专用多媒体端口
这也不代表着所有的外部设备都使用这USB作为数据传输的媒介:一些特定的设备需要特定的接口。
在几年之前(HDMI还不算流行的日子),投影仪或者显示器之类的设备选择使用VGA (Video Graphics Array : 视频图形阵列)接口进行连接,传输视频流。
而现在,这类设备都基本采用的DP(Displayport)接口或者HDMI(High Definition Multimedia Interface : 高清多媒体接口)接口,其中一个原因是VGA并不支持传输音频数据。
指令周期
指令周期,又名读取-执行周期 (fetch-and-execute cycle),指的是CPU要执行指令需要经过的步骤。
计算机之所以能自动地工作,是因为CPU能从存放程序的内存里取出一条指令并执行这条指令;紧接着又是取指令,执行指令,如此周而复始,构成了一个封闭的循环。除非遇到停机指令,否则这个循环将一直继续下去。
下图展示了一个指令周期的结构:
图中,我们假设程序已经在运行。所以程序计数器就会找到下一条指令的地址。
在提取阶段,会执行以下步骤:
- 首先,下一个指令的地址会存在程序计数器(Program counter,可写作PC)中。这个地址会先被传送到MAR(Memory address register)中。
随后处理器开始工作。
在下一个时钟周期内,这两件事会同时发生:
- 在MAR所指向的地址中保存的指令被提取到MDR(Memory data register)中
- 程序计数器(Program counter)中存储的地址+1。
然后在MDR中存储的指令会在CPU中传输到CIR(Current instruction register)
这里需要注意两点:- 时钟周期是由系统时钟控制的周期。系统时钟将有设置,允许在为一个周期定义的时间内从内存发生一次数据传输。
- 在最后一步中,程序计数器会加一。但是如果刚才加载的指令是一个跳转指令,程序计数器就必须根据跳转条件更新程序计数器的内容。这一步只会在指令被解码之后发生。
在解码阶段,存储在CIR中的指令就会作为输入内容,被控制单元内的电路读取。根据指令的类型,控制单元会向适当的组件发送信号,准备开始执行阶段。
在执行阶段内,如果指令需要算数或者逻辑处理,就会把ALU拉下水。
寄存器传输语言
寄存器传输语言 (Register transfer notation),表示了寄存器数据传输操作和各模块内部和模块之间连接关系的记法。
涉及到寄存器的操作可以通过这种语言描述。
举个例子,一个完整的指令周期的fetch阶段可以被这样表示:
MAR ⬅ [PC]
PC ⬅ [PC] + 1; MDR ⬅ [[MAR]]
CIR ⬅ [MDR]
在寄存器传输记法中,单个数据传输的基本格式与变量赋值的格式相似。
箭头左边的那一项是数据的目的地,这里使用适当的缩写来标识特定的寄存器。
箭头右边是那个数据的定义。在这个定义中,寄存器缩写周围的方括号表示正在移动寄存器的内容,这个动作也可能包括一个算术运算。
当两个数据操作放在由分号分隔的同一行上时,这意味着两个传输同时进行。
第二行的两对方括号需要注意下:MAR的内容是一个地址;它是该地址的内容,正在被转移到MDR
两队方括号代表CPU必须进行一个逻辑处理,然后才能复制该值。
中断处理
计算机有很多情况会产生中断。比如说:
- 程序中的一个严重错误
- 硬件问题
- 等待I/O开始处理数据
- 用户交互
- 一个计时器信号
在产生了中断后,我们需要处理这些发生的中断。每一个不同的中断需要进行合适的处理,不同的中断还会有不一样的优先级,因此,处理器就必须具备判断中断类型的能力。
在处理器中加入一个中断寄存器可以是一个方法。它的工作方式与状态寄存器很相似:每一个单独的bit都作为特定类型中断的标志。
第六章:汇编语言程序设计
机器码
操作码与操作数
在深入了解什么是机器码之前,我们需要先了解什么是操作码和操作数。
操作码:定义与指令相关联的操作
操作码指计算机程序中所规定的要执行操作的那一部分指令或字段。其实就是指令序列号,用来告诉CPU需要执行哪一条指令。
指令系统的每一条指令都有一个操作码,它表示该指令应进行什么性质的操作。
不同的指令用操作码这个字段的不同编码来表示,每一种编码代表一种指令。组成操作码字段的位数一般取决于计算机指令系统的规模。
操作数:定义指令需要的任何数据
操作数指出指令执行的操作所需要数据的来源。操作数是汇编语言指令的一个字段。
机器码
所以说什么是机器码?
机器指令码(Machine code instruction):由一个操作码和一个操作数(通常是一个操作数)组成的二进制代码
机器码是机器指令码的缩写。
一开始,我们用机器码来编写程序,称之为机器语言。
机器语言虽然能够被计算机理解和接受,但毕竟根人话完全不擦边,不易被人们理解和记忆,并且用它编程容易出差错。
所以,我们用助记符 (mnemonic) 代替机器码,从而形成了汇编语言。这让指令容易理解和记忆,而且便于交流。
在继续下面的内容之前,我需要列举几个事实中的事实:
- 在所有语言里面,CPU只认机器码 (Machine code)
- 机器代码由一系列指令组成
- 一条指令中包含一个操作码 (opcode)
- 一条指令可以没有操作数 (operand),但最多可以有三个操作数
- 不同的处理器有不同的指令集
- 对于相同的操作,不同的处理器会有类似的指令,但是指令的编码是不同的。
对一个特定的处理器来说,每个单独的机器码指令都必须定义了以下内容:
- 整个指令的总比特数或字节数
- 定义操作码的位数 (number of bits that define the opcode)
- 在剩余位 (remaining bits) 中定义的操作数的个数
- 操作码占用最高有效位 (most significant bits) 还是最低有效位 (least significant bits)
操作码所需要的位数取决于处理器指令集中不同操作码的数量。操作码可以由定义操作的前几位和与寻址相关的剩余位构成。下图展示了简单处理器的合理指令格式:
一条指令由两部分组成:操作码和操作数
操作码长度为8位,其中有4位用来记录操作,2位用于记录地址类型,剩余的位数交给寻址寄存器处理。
此操作码将占用指令中的最高有效位。因为在某些情况下操作数会是一个内存地址,给它分16位可以与地址总线的位数一致。
当一条指令到达CPU的时候,控制单元会先检查操作码,来解析这一条指令定义了什么操作。这一步在指令周期内属于解码步骤。
它可以使用上一张学过的寄存器传输语言进行描述,但是需要进行一些小小的修改。
CU ⬅ [CIR(23:16)]
这一行表示了16到23位之间的数据(表示的是操作码)从当前指令寄存器中传输到控制单元。
p.s.
上面图片中一串命令一共有24位。我们从左边数第一个位,记为第0位,同理可得最后一位是第23位。
如果命令中大位在前小位在后,代表位数是从后往前数
同样的,小位在前大位在后,代表位数是从前往后数
汇编语言
程序员们希望能够编写一种程序,这种程序可以直接控制处理器的一举一动。
有些人认为这是最有效的程序类型,但是作为一个正常人用机器码程序会把你累个半死,因为这样的程序确实难写,很抽象的。
因此将一个实质性的程序以机器码的形式来进行编写就会花费很长很长的时间,并且人在编写这种语言的时候会经常犯错,因为机器码和人类语言相差的太远了。
针对这种编程需求,汇编语言是最好的解决方案。除了具有唯一定义的机器代码语言之外,每个处理器都有自己的汇编语言。
汇编语言 (Assembly language) :是一种与机器码有关的低级语言,其中操作码被写成助记符 (mnemonic) 形式,并且操作数用字符表示
低级语言的低级不是说它有多拉跨,而是指汇编语言比较接近硬件底层。
在汇编语言中,我们用助记符代替机器指令的操作码,用地址符号或标号代替指令或操作数的地址。
特定的汇编语言和特定的机器语言指令集是一一对应的,不同平台之间不可直接移植。
汇编器 (Assembler) :用来把汇编语言程序翻译成机器代码的程序
如果用汇编语言写出一个程序,他必须要被翻译成机器码才能够被CPU执行。翻译的活就是汇编器干的。
一般而言,汇编生成的是目标代码,需要经链接器(Linker)生成可执行代码才可以执行。
作为一门语言,对应于高级语言的编译器,需要一个“汇编器”来把汇编语言原文件汇编成机器可执行的代码。
把半人话翻译成电脑话
汇编语言的本质是,对于每条机器代码指令,都有一条等价的汇编语言指令,其中包括:
- 操作码的助记符(符号缩写)
- 操作数的字符表示形式
汇编语言的优点比较明显,比如说对程序员来说,汇编语言相比机器码写起来要更加容易。
此外,汇编语言还允许程序员们做一些机器码无法做到的事情,比如说:
- 做注释
- 用符号做变量名
- 地址标签
- 宏命令
- 指令 (Directives)
这里的指令告诉汇编器如何构造最终可执行机器代码的指令。
而宏命令是代表程序中要多次使用的一系列指令。有点像鼠标宏:记录鼠标移动信息之后,按某个键触发后回放此路径。
寻址类型
有如下几种寻址类型:
Symbolic addressing: 符号寻址
Relative addressing: 相对寻址
Absolute addressing: 绝对寻址
当考虑汇编程序是如何将汇编语言程序转换为机器码是,我们很有必要去了解下他们之间的区别。
我们假设有这样一个汇编程序,它的目的就是把键盘上输入的单个数字相加。
我们会在接下来的文章内反复使用这个例子!所以说好好看看这个程序是很有必要的(
下表左侧分步骤描述了一个使用符号寻址编写的汇编程序,以及对每条指令的解释:
| 使用符号寻址的汇编程序 命令 (助记符+参数) | 命令解释 |
|---|---|
IN |
这一步通过键盘输入一个数字,并将它的ASCII码存入进累加器中 |
SUB #48 |
这一步是减法运算,将ASCII码转换成二进制 |
STO MAX |
声明一个地址,名称为MAX,将累加器中的数字存储进去 |
LDM #0 |
向累加器中添加0 |
STO TOTAL |
将累加器中的这个0存入一个地址,名称为TOTAL |
STO COUNT |
将累加器中的这个0存入一个地址,名称为COUNT |
STRTLP :IN |
再次通过键盘输入一个数字,并将它的ASCII码存入进累加器中 |
SUB #48 |
这一步是减法运算,将ASCII码转换成二进制 |
ADD TOTAL |
将地址为TOTAL的值与累加器中的值相加,并将总和存储在累加器中 |
STO TOTAL |
然后再把累加器中的数据存入名叫TOTAL的地址中 |
LDD COUNT |
将存储在地址COUNT的值加载到累加器中 |
INC ACC |
向累加器中加1 |
CMP MAX |
比较累加器中的值与存储在地址MAX中的值 |
JPN STRTLP |
如果比较值不相等,程序会跳转回标记为STRTLP的指令 |
END |
程序结束执行 |
MAX: |
一个可以存储值的标记地址 |
TOTAL: |
一个可以存储值的标记地址 |
COUNT: |
一个可以存储值的标记地址 |
其中有几行需要格外解释下:
LDM (Load much): 多数据加载,将地址上的值加载到寄存器上
按照惯例:标签的后面会写有冒号,但是引用标签的时候需要去除冒号。
使用符号寻址可以让程序员使用汇编语言代码,而不需要担心程序运行的时候代码在内存中的位置。
编写汇编代码也可以将符号寻址替换为相对寻址或绝对寻址。
下表显示了上面那个表格中使用这些替代方法转换后的简单代码:
你可能发现在相对寻址改写的程序中,有[BR]这个东西。
这里我们假设有一个基址寄存器 (base register),包含程序基址。
程序基址是程序中第一条指令的地址。 查看上图的例子:使用绝对寻址的程序的第一行代码的地址是200,所以BR中存储的基址为200。
调用基址寄存器中的内容,可以使用[BR]。
两步汇编程序的汇编过程
对于任何汇编程序,在进行任何转换之前,都必须对汇编语言代码进行许多处理。比如说:
- 移除注释
- 用构成宏定义的指令列表替换指令中使用的宏名称
- 删除和存储稍后要执行的指令
我们在寻址类型章节里面设计了一个汇编程序,这个程序内包括了向前引用。
有些指令有操作数的符号地址,但在程序的那个阶段,我们不知道这个地址的位置。需要一个两遍汇编程序,以便在第一遍中确定前向引用的地址的位置。
为了在第一次传递期间实现这一点,汇编程序使用了一个符号表。
代码是逐行读取的。当一个符号地址第一次遇到时,这个名字就会被输入到一张符号表中。
在名称旁边,必须尽快添加一个相应的地址,以便识别。
下表给出了针对寻址类型章节中那个程序创建的符号表。
| Symbol | Offset |
|---|---|
MAX |
+15 |
TOTAL |
+16 |
COUNT |
+17 |
STRTLP |
+7 |
请注意,汇编程序在读取代码时必须对指令进行计数。当它遇到一个标签时,汇编程序可以将偏移值(offset)输入到符号表中。
用人话来讲就是数顺序来让处理器确定自己读的是哪一行代码。
把程序的开始设为偏移值为零,则IN这个操作有+1的偏移量,有STRTLP的那一行机器码的偏移量是+7
在第二步中,汇编程序会使用符号表(symbol table)和一个查找表(lookup table),表格中包含每个操作码的二进制代码。
每一个处理器定义过的操作码,在这个表里都可以找到对应的信息。
下表列出了我们举的例子中使用的指令对应的条目。需要注意的是:这里的二进制代码是对于待使用代码的一个建议。
如果不出意外的话(比如说汇编发生错误),那么第二遍的输出就是机器码程序了。
下面这个表格将原始汇编代码和编译好的机器码程序列在了一起,我们可以简单比较一下:
有以下几点需要简单注意下:
- 大多数的指令都有一个16位二进制数的操作数。
- 通常来说这表示一个地址,但对于
SUB和LDM指令,操作数会被用作一个值。 IN和END指令没有操作数。INC指令是一个特例。汇编语言代码中存在操作数,但它只用来定义寄存器。在机器码中,寄存器是在操作码中标识的,因此就不需要操作数了。- 在编译机器码的时候,第一个步骤会占用第零个地址。
- 像这种形式的代码是不可执行的,但它却是汇编程序的一个有效输出。
- 当程序加载到内存中准备执行时,就需要把地址稍微改改了。
- 程序代码之后的三个内存位置将会分配为零,以确保程序执行后可以正常使用它们。
寻址模式
当一条指令需要将一个值加载到寄存器中时,我们有不同的方法来识别该值。其中的每一种都被称为寻址模式 (Addressing mode)。
顺带附上寻址模式的定义:
*当指令需要使用一个值时,寻址模式定义了如何使用操作数来查找这个值。
在本单元的开始就说过:对于一个简单处理器,机器码指令中的操作码位将用于定义寻址模式。加起来一共允许有4种不同的寻址模式,如下表所示。
| 寻址模式 | 操作数的使用 |
|---|---|
| Immediate 立即寻址 |
在这种情况中,操作数是要在指令中使用的值;SUB #48就是一个很好的例子。 人话:操作数是一个确切的数学值,不需要存入任何累加器就可以直接引用的值。比如说全体正整数。 |
| Direct 直接寻址 |
在这种情况中,操作数是保存要在指令中使用的值的地址;ADD TOTAL是其中的一种情况。 人话:操作数是一个地址,执行指令的时候会使用操作数指定内存中的数据 |
| Indirect 间接寻址 |
在这种情况中,操作数是一个地址,这个地址记录了要在指令中使用的值。 人话:操作数是一个地址,但是与直接寻址不同的是:此操作数中的值会被作为一个新的地址再次重定向,直到读取该重定向后地址中的值。 |
| Indexed 变址寻址 |
在这种情况中,操作数是一个地址,但是必须将当前变址寄存器(IX)中的值加到该地址上,才可以获得要在指令中使用的值的地址。 人话:操作数是一个地址,但是最后调用数据的地址是当前操作数所定义的地址数加上变址寄存器的值,并找到最后的值。 |
对于立即寻址,有三种定义值的选项:
#48指定了十进制值48#B00110000指定等价的二进制内容#&30指定了等价的十六进制内容
汇编语言指令
继续回到具有有限指令集的简单处理器上。
我们在这里举出的所有例子,都不会与特定处理器的汇编所匹配。
每一个指令都需要基于平台,针对性的设计汇编程序。
数据的移动
这些指令种类各不一样。有些可以将数据加载到寄存器中,有一些可以将数据存储在内存里。
下面这个表格举出了一些例子:
| 指令操作码 | 指令操作数 | 简单的解释( |
|---|---|---|
LDM |
#n |
立即寻址,将数字“n”加载到累加器(ACC)中。 |
LDR |
#n |
立即寻址,将数字“n”加载到变址寄存器(IX)中。 |
LDD |
<address> |
直接寻址,将给定地址的内容加载到累加器中。 |
LDI |
<address> |
间接寻址,给定的地址将会被使用,而第二个地址的内容会加载到累加器中。 |
LDX |
<address> |
变址寻址,地址由<address>+变址寄存器中的内容组成,然后将计算出来的地址中的内容加载到累加器中。 |
MOV |
<register> |
将累加器中的内容移动至一个指定的寄存器中(IX)。 |
STO |
<address> |
将寄存器中的内容储存到一个指定的地址。 |
在这里,左侧这一列的助记符定义了指令的类型,包括了在运算中涉及到的所有寄存器,以及可能会使用到的恰当的寻址模式。
仔细阅读助记符是很重要的!
在以下所有的表格中:
<address>代表操作数是一个地址<register>代表操作数是一个寄存器缩写#n代表这是一个十进制值。比如说#23代表十进制数字23。
来一个背景解释一下上面表格的内容:
根据上图所示的内存内容,下面我会给出一些例子:
LDD 103代表值110被存入了累加器中LDI 106代表来自地址101的值208被存入了累加器中STO 106代表值208被存进了地址106中LDD INDEXVALUE代表值”3”被存入了累加器MOV IX代表累加器里面的那个”3”被存入了变址寄存器中LDX 102代表来自地址105的值206被存入了累加器中
输入和输出
下面这两个指令用于输入或输出。
在每种情况下,这些指令都只有一个操作码,没有操作数。
- 以助记符为
IN代表的操作会将键盘上输入的字符的ASCII码存储在累加器中。 - 相反,以助记符为
OUT代表的操作会将累加器中存储的ASCII码显示出来。
比较和跳步
程序是不会傻到一直一条条执行命令的——至少当他们要求被这样做的时候会这样。
程序有些时候会在每行命令之间跳转。有一些情况是无条件的,也有一些情况是有条件的:比如说执行了比较命令。
下图给出了一些比较命令的例子:
| 操作码 | 操作数 | 解释 |
|---|---|---|
JMP |
<address> |
跳转到指定的地址。 |
CMP |
<address> |
将累加器中的内容与指定地址中的内容比较。 |
CMP |
#n |
将累加器中的内容与指定十进制值比较 |
CMI |
<address> |
是个间接寻址。命令会将累加器中的内容与操作数给到的地址中的内容比较。 |
JPE |
<address> |
它会跟在一个比较命令后面。如果比较的结果为True,则会跳转到操作数给定的地址。 |
JPN |
<address> |
它会跟在一个比较命令后面。如果比较的结果为True,则会跳转到操作数给定的地址。 |
这里所有介绍的比较命令,都是比较两个数据是否相等。
相等输出为True,不相等输出为False。
比较的结果会被记录在状态寄存器中的一个标志中。
当我们执行跳转指令的时候,我们首先需要检查状态寄存器中是否有这个标志。
然后执行跳转命令的时候,我们不会立即执行,而是需要先向程序计数器提供一个新的偏移量,让程序可以继续在正确的地址上获取下一条指令。
因此在向程序计数器提供新的偏移量的时候,程序计数器就不会执行简单的+1操作了。
数学运算
简单的数学运算,但是在这里我们暂时不考虑乘除的运算,因为他们相比加减法运算没有通用性或一致性。
下表列出了一些例子:
| 操作码 | 操作数 | 解释 |
|---|---|---|
ADD |
<address> |
将操作数给定地址内的内容加到累加器中。 |
ADD |
#n |
将操作数给定的十进制数字加载到累加器中。 |
SUB |
<address> |
从累加器中减去操作数给定地址中的内容。 |
SUB |
#n |
从累加器中减去操作数给定的十进制数字。 |
INC |
<register> |
向给定的寄存器内+1。 (累加器或者是变址寄存器) |
DEC |
<register> |
向给定的寄存器内-1。 (累加器或者是变址寄存器) |
下面展示了一个以5累加到75的程序:
简单解释一下程序的运行过程:
- 前三行命令初始化了计数器和求和功能
- 在地址103的命令是每次迭代的第一行命令。
- 接下来的三行命令会向地址中的值+1,然后存储回原来的地址。
- 地址106到地址108中的指令会向总和中+5。
- 地址109和地址110的命令用来检查总和有没有到达75目标值。如果没有就重复下一次迭代。
- 到达目标值75后,地址111到地址113的命令用来输出计数结果(一共加了15次75,所以输出计数结果15。)
移位运算
逻辑移位:左移时最低位补0,右移时最高位补0的移位
比如说:0101
向左移1位就是:1010,最高位补了一个0。
向右移1位就是:0010,最低位补了一个0。
逻辑移位可以做一些很有意思的东西,比如让一个数字扩大一倍。但是这是有先决条件:这一串二进制的最高位和最低位必须是零,因此没有任何的信息丢失。
举个例子
00001010代表十进制的10。
但是将其向左逻辑移位(一位):00010100代表了十进制的20。
同样的,向右逻辑移位代表减小一倍。
左移一位是扩大一倍最简单的做法。
知道了什么叫做逻辑移位,现在介绍两个移位运算命令:
| 操作码 | 操作数 | 解释 |
|---|---|---|
LSL |
#n |
将累加器中的值向左以操作数给定的位做逻辑移位 |
LSR |
#n |
将累加器中的值向右以操作数给定的位做逻辑移位 |
移位并不是仅存在逻辑移位,我们还有其他的两种移位方式:循环移位(Cyclic shift)和算术移位(Arithmetic shift)。
循环移位:在移位时不丢失移位前原范围的位,而是将它们作为另一端的补入位。
算术移位:使用移位对累加器中存储的有符号整数进行操作或除法。
这俩了解就好。
按位逻辑操作
命令:
| 操作码 | 操作数 | 解释 |
|---|---|---|
AND |
#Bn |
将累加器中的每一位都与操作数指定值进行AND运算 |
AND |
<address> |
将累加器中的每一位都与操作数指定地址中的值进行AND运算 |
XOR |
#Bn |
将累加器中的每一位都与操作数指定值进行XOR运算 |
XOR |
<address> |
将累加器中的每一位都与操作数指定地址中的值进行XOR运算 |
OR |
#Bn |
将累加器中的每一位都与操作数指定值进行OR运算 |
OR |
<address> |
将累加器中的每一位都与操作数指定地址中的值进行OR运算 |
第七章:控制与监控系统
监控系统
监控系统可以用于创建一段时间内系统状态的记录。
监控系统被广泛用于监控系统的特定物理特性(照度,温度,湿度…)何时超出阈值。
比如说温控系统检测CPU过热,会自动降低频率。
我们在这里以温度作为一个例子:
如果计算机想要知道当前机箱内实时温度,那么计算机就必须需要一种设备来获取相关数据,并精确的传送到计算机。
这一种测量设备叫做传感器。
传感器:测量属性并可以将值传递到计算机的一种硬件。
在这个情景中,可以监控计算机机箱内温度的硬件就是热电偶。热电偶会根据温度的变化更改它的输出电压。在一些老式的电脑上,如果传感器检测到了机箱内的温度过高,会奏响它的小蜂鸣器提醒用户。
有一点需要注意,在一个监控系统内,传感器是没有任何的集成智能在里面的,所以说但凡这传感器遇上了问题,它都没有办法自我修复,那基本上就得报废了。
传感器还可以检测运动,红外,声音,ph值等各种属性。
控制系统
控制系统包含了监视系统的权限和功能,但是不止如此,控制系统还可以去对系统做出一些调整与改变。
监视系统需要一个必不可少的元件:致动器 (Actuator)。制动器是连接到其他控制设备的电机,可以应用一些改动。
下图是一个计算机控制环境的示意图。
上图中包含了一个模数转换器(ADC)和一个数字模拟转换器(DAC),它们俩都是独立的组件。在实际的系统中,它们有可能是传感器或者执行器设备的组成部分。
上图所示的系统中,计算机会定期向传感器请求数据,接着计算机就会处理这一部分数据。如果接受的数据不在期望的范围内,计算机就会采取一些操作。下一次数据请求只会发生在此操作完成后。
下图是一个闭环反馈控制系统:
其中的控制器由微处理器组成,他们可以将传感器读取的实际输出值与期望的值作比较,随后会将一个值继续传输给执行器。
控制设备的位操作
担任控制工作的计算机或者微处理器里面都必须有一个时刻运行的实时程序。该程序可以根据传感器检测到的内容为布尔变量设置值。
比如说:如果一个受控环境中有两个需要监视和控制的属性,我们就可以定义并使用四个布尔变量。
赋值就牵扯到了赋值语句,就像这样:
IF SensorDifference1 > 0 THEN Sensor1HighFlag ← TRUEIF SensorDifference1 < 0 THEN Sensor1LowFlag ← TRUEIF SensorDifference2 > 0 THEN Sensor2HighFlag ← TRUEIF SensorDifference2 < 0 THEN Sensor2LowFlag ← TRUE
与此同时,监控和控制程序的另一个部分会检查是否已经定义了任意一个标识。运行这样的一个程序的机器代码可以使用单独的位来表示每一个标识。
下面的表格说明了设置和读取表示的方法。
在这些代码片段中,每个字节的三个最低有效位 (第0, 1和第2位)会被用作标识。
下面演示了在系统打开时可能使用的所有位为零的设置:
LDD 0034 |
将一个来自某地址的字节转入累加器中。 |
|---|---|
AND #B00000000 |
使用位与(AND)运算将累加器的内容和操作数转换为0。 |
STO 0034 |
将改变后的字节存储在原始地址中。 |
下面的例子说明了某一个确切位值的切换。这将改变标志的值。
可能是因为遇到了问题,也可能是因为解决了问题。
LDD 0034 |
将一个来自某地址的字节转入累加器中。 |
|---|---|
AND #B00000000 |
使用按位异或(XOR)运算将累加器中的第2位切换。 |
STO 0034 |
将改变后的字节存储在原始地址中。 |
下面演示了如何将一个位的值设置为1,不管它现在的值是多少。
LDD 0034 |
将一个来自某地址的字节转入累加器中。 |
|---|---|
AND #B00000000 |
将累加器的内容与操作数进行按位或(OR)运算来设置第二位所表示的值。所有其他比特位保持不变。 |
STO 0034 |
将改变后的字节存储在原始地址中。 |
下面演示了将所有位都设置为0,除了一个特定的位的方法。
LDD 0034 |
将一个来自某地址的字节转入累加器中。 |
|---|---|
AND #B00000000 |
对累加器的内容和操作数进行位与(AND)运算,保持第1位的值不变,但将其他所有位转换为0。 |
STO 0034 |
将改变后的字节存储在原始地址中。 |
第八章:系统软件
操作系统
在1960年代,人们使用计算机的操作大概是这样的:
- 进入一个有很多穿孔纸条和穿孔卡片的房间
- 打开计算机
- 将穿孔卡片插入读卡器,然后按下按钮
- 将穿孔纸条插入读取器,然后按下按钮
- 按下另一个按钮来启动在穿孔卡片上存储的程序。这时候穿孔纸条会当做内存使用。
- 按下按钮将输出打印在纸上
- 关掉计算机
- 离开房间
当时的计算机用户只能通过按钮来与计算机交互。要是放到今天得需要数不清的按钮了。
所以在1960年代,确实的计算机的一个重要成分便是操作系统了。
操作系统活动
操作系统的构造实际上是非常复杂的,我们在这里寥寥数句肯定是说不清楚的。
但是我们可以大致介绍一下操作系统的大致活动与功能:
用户界面
操作系统里面的用户界面可以允许用户通过它去与系统硬件更高效地交互,从而完成一些有意思的事情。
一个操作系统至少需要满足以下两点中的其中一个对用户的输出方式:
- 一个命令行样式的用户界面
- 一个图形化的用户界面
我们用的绝大多数操作系统都是带有图形化用户界面的。
程序硬件接口
程序员的可以编写软件,用户运行这个软件。
软件需硬件的运行,所以操作系统必须保证硬件可以执行软件所希望执行的操作。
现在的程序员编写软件不再需要去了解如何针对某个别的硬件进行编程了,尤其是处理器。
随后操作系统就会担任这个工作:把人话翻译成机器听的话。
资源管理
如果一个程序正在运行,我们会管他叫做一个进程。
在现代的计算机系统内,任何进程都不可能一直不间断地运行下去,而且在计算机系统上会运行很多的进程,每一个进程都需要访问计算机系统提供的资源。
操作系统中的资源管理旨在发挥计算机使用过程中的最佳性能。管理资源最重要的两个方面是:
- 进程的调度
- 冲突进程的管理 (当两个进程同时需要计算机系统提供的同一份资源,就会产生冲突。)
内存管理
以下三点在内存管理中比较重要:
- 内存保护:确保两个程序不会共用同一个内存地址。
- 组织内存:通过组织内存的使用方案来实现有限资源的最大化利用(或者发挥最大性能),比如说虚拟内存。
- 内存优化:决定有哪些进程会保持运行在主内存中。
设备管理
每一个计算机系统都会连接各式各样的设备,比如说鼠标键盘,打印机复印机,摄像头等等。
设备管理有一下两点:
- 为设备安装正确的驱动程序。
- 控制设备有关进程的使用。
文件管理
- 文件命名
- 目录结构
- 访问控制机制
安全控制
- 当文件丢失时提供恢复
- 防止计算机被入侵
- 确保文件的安全性
错误检测与恢复
程序在执行的过程中很有可能出现错误。这有可能是因为程序编写错误,也有可能是提供了不正确的数据。
但是无论错误的原因是什么,操作系统都应该有中断进程和错误诊断的能力。
在极端的情况下,操作系统也需要有组织性地关闭系统,同时不丢失数据。
应用程序软件
应用程序可以由操作系统提供,用户也可以单独安装。
应用程序不是操作系统能够正常运行的必要条件,而是用户或者操作系统可以在需要时决定运行的程序。
举一些例子,每一个例子具体是什么样我就不展开成一个个小章节解释了,已经属于是基础知识了。
- 硬盘格式化软件和硬盘检测软件。
DiskGenius就是这样的一款优秀软件。这样的软件可以格式化你的磁盘,或者检查硬盘是否有任何坏道错误。
- 硬盘碎片化整理程序
机械硬盘因为其物理限制(转盘和磁头导致机械硬盘大多以顺序读取为主),随机读取的性能远远低于SSD(固态硬盘)的性能,所以适当的整理磁盘上的文件排布对于系统读取文件来说是很有帮助的。
我们在日常使用电脑的时候很容易产生很多碎片。这些碎片可以是不连续的,在机械硬盘中会极其拖慢系统的运行速度。
所以碎片化整理程序就可以将碎片化的文件以机械硬盘喜欢的方式重新排列,让随机读取文件更靠近顺序读取。
所以这样的碎片化整理程序对于SSD是没什么用的,除了心理作用。
- 备份文件
- 杀毒软件
这两个不用说了吧。
Program libraries 程序库
这些在Program libraries中是为了执行特定任务而创建的程序。任何程序员都可以在自己的项目里使用它们。
所有新开发的程序里面都会包含错误。这些错误在程序员debug中可能很难发现,但是在用户的日常使用中可以变的越来越明显。而这些已经验证过没有问题的Program libraries中的子程序就可以被程序员拿来直接用,省去了大量的精力去调试或者编写程序。
另一种方法是使用动态链接库(DLL)。当程序员决定使用DLL的时候,在自己的可执行代码内就可以只包含一点点代码。这允许它在程序运行的时候连接到单独存储在内存中的例程。使用DLL的优点是所有程序的可执行文件都可以做到较小的存储空间,对内存的需求也最小化。另一个有点事如果有新的例程版本可用,我们就可以直接讲新的例程加载到内存中,以便使用它的任意程序都可以升级到新的例程,而不需要去大刀阔斧地改代码。
但是问题是如果DLL损坏或者新版本的DLL存在兼容性问题或者内容错误,直接一影响就影响一片程序。同样DLL确实也是用户在使用计算机的时候经常发生的问题。这时候就需要用户去手动添加缺失的DLL。
计算机语言转换
还记得第六章的汇编器吗?这一个小结介绍类似汇编器的其他程序,不过这些程序是用来翻译高级过程语言编写程序的翻译器。
编译器和解释器
使用编译器 (Compilers)或者解释器 (Interpreter)的先决条件是:必须应用于源代码,而源代码必须是用高级语言编写的程序。
一个解释器工作的基本过程如下:
- 解释程序,源代码文件和源代码程序使用的数据都可以使用。
- 解释程序现在开始运行。
- 读取源代码的第一行。
- 每一行会被按下面5-7步的顺序分析:
- 如果有发现错误,解释程序会暂停运行,并将错误信息上报。
- 如果没有错误发现,源代码中的这一行就会被解释程序转换成中间代码。(中间代码是一种面向语法,易于翻译成目标程序的源程序的等效内部表示代码)
- 解释程序会根据生成的中间代码来执行所需要的操作。
- 然后解释程序就会重复运行4-8步的步骤分析下一行代码。
一个编译器工作的基本过程如下:
- 需要编译程序和源代码,但是不需要源代码使用的数据参与其中。
- 编译程序开始运行。
- 读取源代码的第一行。
- 每一行会被按下面5-7步的顺序分析:
- 如果有错误发生,编译程序会报告这个错误。
- 如果没有发生错误,那么源代码中的这一行就会被转换成中间代码。
- 编译程序会重复运行4-7步的步骤分析下一行代码。
- 当整个源代码处理完毕后,会发生下面两种情况的其中之一:
- 如果在整个源代码中没有发现错误,就将完整的代码转换为目标代码。
- 如果发现了任何错误,就会输出错误列表,并且不生成目标代码。
对于程序员和开发者来说,编译器和解释器各有所长:
在开发程序的时候,解释器具有优势,因为它可以在错误发生的时候识别错误并尝试修正,而无需等待整个源代码被读取和分析。
解释器的缺点在于:在程序的特定执行过程中,解释器可能无法访问包含语法错误的部分代码。因此错误就只会在结束的时候被发现。
编译器的优点是可以将可执行文件(exe)发行给用户,这样用户就没办法访问源代码了。
而在用户这边,编译器和解释器也都有自己的优缺点:
对于解释程序来说,当每一次运行一个没有错误的程序的时候,解释程序和源代码都必须可用。
对于编译后的程序,当每次运行一个没有错误的程序时候,只有目标代码可用。
编译后的目标代码可以提供相比于解释程序更快的执行速度。
编译后的程序可以有风险,因为它可能含有潜在的病毒或垃圾文件。
无论使用的是编译器还是解释器,如果他们的程序是为了特定处理器而写,则程序只能在具有特定处理器的计算机上运行。
如果有特定的条件,那么在开发程序的时候选择解释器是比较合理的。因为:
- 程序中的一个错误可能会造成多米诺效应:一错错一片。
- 解释器可以检测并修正在代码中发生的早期错误,从而限制后续发生更多问题。
- 在开发过程中,解释器附带的debug程序可以梗方便的减少工作时间。
同样在某些时候,我们也可以选择使用编译器。因为:
- 编译器可以生成一个可执行文件(.exe)。
- 编译器生成的可执行文件可以更方便的用来传播。
- 编译器生成的程序相比于解释器的程序来说,运行速度更快。
Java
当Java正在创建的时候,Java团队设想了一些十分新颖的想法。
每一个计算机都可以安装一个Java虚拟机(Java Virtual Machine)。当程序员构造一个Java程序的时候,会首先编译成Java字节码指令(Java Byte Code)。
当这个程序运行的时候,会被JVM解释,随后就可以将程序转移到任何安装有Java虚拟机的计算机上运行。
集成开发环境(IDE)
集成开发环境(Integrated development environment)是用于提供程序开发环境的应用程序。一般包括代码编辑器,编译器,调试器和图形用户界面等工具。继承了代码编写功能,分析功能,调试功能等一体化的开发软件服务套。
所有具备这一特性的软件或者软件组都可以叫做集成开发环境。
常见的IDE有微软的Visual studio系列,Jetbrains的IDEA,Pycharm。
代码高亮 (Prettyprinting)
计算机语言一般每行由不同的成分构成,有命令或者各种参数。
代码高亮功能可以将代码的每一部分通过不同的颜色或者图样展示出来,方便我们区分并阅读代码。
就像这样:
1 | package com.**.lib.lib; |
上下文敏感提示 (Context-sensitive prompts)
在一段代码的上文你可能定义了一堆变量,在代码的下文IDE就有机会自动补全你写过的变量名称。
语法检查 (Syntax check)
IDE会分析你的代码,并且通过画波浪线的方式提示你你的这部分代码可能有误。
有些IDE只负责检查错误,不过现在的IDE大多都可以为你提供更正提示。
代码折叠 (Expanding and collapsing code blocks)
当你在代码中的一个循环(或者其他组容器内)写了很多的代码,那么IDE提供了可以将容器内的代码折叠的选项。
这让你更方便的在长文件里梳理代码结构。
Debug
IDE一般都会附有调试工具来帮助你进行Debug操作。
Debug大约是程序检查去除漏洞的意思。
在调试过程中你可以为程序中的某几行打上一个断点(Breakpoint)。
当程序开始运行后到达了断点处,程序会暂时停止运行。
然后你可以选择继续运行,或者逐行运行。
这对于梳理程序逻辑很有帮助。
第九章:安全、隐私和数据完整性
定义
数据完整性
定义什么是数据完整性挺容易,但是确保数据完整就不那么容易了。
只有准确并最新的数据才会存在数据完整性,任何存储数据的个人和机构都必须尽可能地确保数据的完整性。
我们会在本章和第十一章讨论确保数据完整性的方法。
数据隐私
数据隐私指的是保持数据的私密性,而不是任凭数据公开访问权,以至于每人都可以随便使用。此现象都可以发生在个人和组织上。
每个人都有他们自己的隐私数据,而且大家都会选择保密这一部分数据不被公开。
对于个人而言,如果没有适当的法律来约束侵犯隐私的违法者,那么保证数据隐私就相对困难了。
保护数据隐私的法律必须要涉及以下几点:
- 这些数据是私人数据,因为他们主要是面向提供给个人和组织的。
- 提供数据是为了允许组织使用它,但只能用于个人理解和同意的目的。
- 数据保护法要求组织机构确保这些数据的隐私性和完整性。
- 不幸的是,拥有法律并不能保证遵守它们,但它们确实起到了威慑作用,可以使不法行为者受到法律诉讼。
数据安全
数据在我们想要使用它们的时候永远可用。如果数据已经丢失或者损坏,那么我们可以说数据的安全性已经被破坏了。
在实现数据完整性或数据隐私之前必须先实现数据安全,但数据安全本身并不能保证数据完整性或数据隐私。
保护数据的要求之一是用来存储数据的系统的安全性。
系统安全不仅仅保护数据。 系统安全措施有两个主要目标:
- 确保系统持续执行用户需要的任务。
- 以确保只有授权用户才能访问系统。
对计算机系统及其存储数据安全的威胁
对计算机系统的数据安全侵犯可能因为以下原因形成:
- 个人用户不关注数据安全
- 内部的管理混乱
- 自然灾害
- 未经授权的个体侵入系统
- 有害程序进入计算机系统
网络和互联网对计算机和数据安全的威胁
现在我们的计算机都会连接到互联网。互联网上充斥着各种各样的信息,同样的可能会存在各式各样的有害文件。部分黑客可以在系统未经授权之时入侵系统。黑客可以通过这样的手段非法获取系统内的数据。
所以说检查是否有恶意软件进入系统确实挺有必要。
恶意软件
恶意软件是恶意软件的统称。
它是为了有害的目的而被引入系统的软件。
含有恶意软件的各种类型的程序代码有:
- 病毒:试图在其他可执行代码中复制自己。
- 蠕虫:独立运行,并尝试将自身传播到网络上的其他主机。
- 逻辑炸弹:在满足某些条件之前保持潜伏。
- 特洛伊木马:替换全部或者部分的程序,知道达到木马的目的。
- 间谍软件:收集信息,然后将其传输到另一个系统。
- bot:控制一台计算机并且利用它来发动攻击。
不同类型之间的恶意软件差异并不大,有些例子属于这些类别中的一个或者不属于任何一个。
病毒类别通常根据病毒所附着的软件进行细分,例如引导扇区病毒和宏病毒。
恶意软件也可以通过他们的行为来归类:
- 钓鱼:以发送看似合法的电子邮件等手段来套取有用的信息。
- 冒充:冒充一个以假乱真的官方网站。
- 键盘记录程序:记录用户的键盘使用情况。
由用户活动引起的系统漏洞
许多系统漏洞与系统合法用户的活动直接相关,而不是恶意软件。
下面是两个不涉及恶意软件的例子:
- 使用弱密码,特别是与他们自身相关的密码。一个弱密码很容易被别人猜到或者被暴力穷举。
- 用户不太容易识别网络钓鱼和攻击,所以很容易泄露有用的信息。
用户的以下操作很有可能出现安全事故:
- 插入一个移动存储设备
- 在邮件内打开未知的超链接
- 打开一个未知的网站
- 从网络上下载未知的文件
系统本身产生的漏洞
系统在某些情况下比较容易产生漏洞。下面给出了几个例子。
有一些操作系统的安全性可能较差。随着时间的推移,操作系统越来越复杂,这就容易导致安全性下降的可能。操作系统的定期更新,打补丁或者更新服务包等都可以增强系统的安全性。
在之前,应用程序会有较大的概率携带电脑病毒等有害程序。不过现在这种情况几乎不会存在了。
还有一个比较特殊的漏洞,就是缓冲区溢出。用C语言编写的程序有很大的一部分是不会自动执行数组绑定检查的。如果有一个程序故意将代码写入内存中超出为数组定义的地址的那一部分,那么这个部分会被定义为缓冲区。
保持计算机数据良好的措施
灾难恢复
对某些大厂来说,大型计算机的运营连续性十分的重要。
我们需要保证无论发生了什么时间,计算机系统都可以正常的工作。如果必须需要关闭系统,那么我们也必须要确保系统在很短的时间内再次启动恢复正常。
一般来说,互联网大厂会同步很多副服务器,以便于主服务器在提供服务的时候发生不可抗力因素而失去服务。
他们像是一种后备服务器,允许主服务器瘫痪之后能够继续提供服务。
我们将这种后备的服务器叫做“热点”。
安全更新系统
当系统应用了一些新的更新以后,难免会遇见一些硬件上或者软件上的小错误。
一般来说,提供服务的大厂会选择在计算机不提供服务的时候进行系统更新,这样技术团队就可以用这段时间来调试新系统。
但是在现代的互联网公司内,他们的服务是24小时全年无休的。所以更新系统就可以使用到我们上一个话题内提到的“热点”系统:通过另一些主机来提供服务。
用户身份验证
即使你自己的电脑只有你自己一个用户,我们也很有必要去设置一个用户账户。
账户系统十分重要,尤其是有很多人需要使用同一台电脑的情况下。
用户账户的主要安全特征是用户身份验证,我们通常的方法是设置密码,然后将每一个用户和他们的密码做出关联。
当然我们也有其他方法,比如说使用生物识别验证和安全令牌。
生物识别验证是使用我们的指纹,人脸甚至虹膜来验证身份。安全令牌可以是一种硬件,比如说加密狗。
当然也不是说我们只能生物识别安全令牌和密码二选一。我们一般会将这些额外的验证方法与密码相结合。
良好的使用习惯
在使用计算机的时候保持一些良好的使用习惯,可以减少计算机被入侵的可能性。
比如在不用计算机的时候关机,不要在公共的计算机上记录你的个人信息等等。
防火墙
设置防火墙可以让你的电脑免于网络上有害信息的传递和黑客对你的计算机的入侵。
数据的安全性与完整性
其中一种方法是检查并核验输入。
输入数据验证
虽说是验证输入数据,但是实际上验证完了输入数据之后的数据也会发生错误。
我们这里的验证数据实际上是验证数据的各项指标,比如说大小,格式或者更多其他的内容。
我们在这里举几个例子:
- Presence check: 样式检查,用来检查输入的内容是否是空的。
- Format check: 格式检查,来检查输入的数据是否符合要求的格式(比如日期的格式就必须是 dd/mm/yyyy )。
- Length check: 长度检查,用来检查数据是否符合应有的长度。比如说用来检查输入的电话号码是否是11位。
- Range check: 范围检查,用来检查输入的数据是否在合法范围内。
- Limit check: 限制检查,检查输入的数据是否突破了一个阈值。
- Type check: 数据形式检查,用来检查输入的数据形式是否合法。(比如说构成日期的每一位数据都必须是正整数,不能是小数。)
- Existence check: 存在性检查,检查输入的内容是否已经出现过,或者检查输入的内容是否在一个列表内。例如在同一个文件夹下将一个文件重命名成另一个文件的样子会报错,是因为存在Existence check。
验证输入的数据
跟上一个话题看起来很像,但实际上不是一个操作。
在这一步,我们需要尽可能让用户输入的数据是正确的。
要达成这一点,我们可以要求用户再次确认数据,或者让他们自己检查输入的数据。
比如在注册账号密码的时候,要求用户重复输入密码。
或者在填写完表单之后,将用户填写的数据重新陈列在屏幕上,以便用户检查。
按位检查
有些时候某些数据载体上面会包含一个叫做纠错码的部分。这部分允许计算机可以根据这些纠错码来判断或还原之前丢失或损坏的数据。
这里有加和验证和其他数学方法验证。加和生成的数据会被记录到最后一位上。
这两者之间的区别就是一个是确认数据的输入,一个是验证输入数据是否合法的。
数据传输过程中的验证
数据在传输的过程中是很有可能被损坏的,比如说其中的一个位反转了过来,从0变成了1。
所以说,验证技术就会介入,来检查数据是否发生损坏。
其中最简单的方法就是使用一位奇偶校验 (One-bit parity check)。如果传输的数据是七位一字节传输的话,系统就可以在这一个字节中的第八位存储奇偶校验的信息。
下面就是一位奇偶校验的检查步骤:
- 在数据传输之后,我们会检查这一个7位字节中有多少个1。
- 如果1的数量是奇数的话,校验位会被设为1。
- 如果1的数量是偶数的话,校验位会被设为0。
- 这样的过程会在传输每一个字节的过程中重复。
- 在传输的最后,八位字节中的所有1的数量会被数出来。
- 如果这个个数是偶数,那么这个字节就是完好无误的。
- 这样的步骤也会被重复到每一个8位字节。
奇偶校验也不是万金油,数据在损坏后也有可能通过奇偶校验。比如说当一个7位字节里面反转了两个位,最后数出来的奇偶个数还是与原数据一致。
所以说比起改正传输数据的错误,奇偶校验更像是一个验证传输数据是否有错的算法。所以说如果奇偶校验发现了错误,那么我们就只能要求服务器重新发送数据了。
另一种验证方法叫做校验和。这是一个端到端的校验和,由发送端计算,然后由接收端验证。
- 将传输的数据当成若干位(如8位、16位或32位)的整数序列,将这些整数加起来,舍弃进位,得到一个结果。
- 将这个结果取反码,即将0变为1,将1变为0,得到一个校验和。
- 将校验和附加到数据后面,一起发送给接收方。
- 接收方收到数据后,将数据和校验和一起按照同样的方法进行累加,并舍弃进位,得到一个新的结果。
- 如果新的结果是全1,则说明数据没有发生改动或错误;如果新的结果不是全1,则说明数据有损坏或篡改。
一位奇偶校验和校验和是有区别的。一位奇偶校验用于存储数据,而校验和只用于传输的数据。
想要验证数据在哪一位出错了,就比上面的这些验证方法要更加复杂了。
第十章:道德与所有权
(标题翻译过来有点奇怪不过问题不大。这章的原标题叫做”Ethics and ownership”)
道德(Ethics)
不是很理解所谓标题是什么意思。
你可以找到道德的很多定义。
- 伦理学是道德科学的一个分支。
- 道德指的是任何人的行为准则。
- 道德是在特定职业或人类生活中公认的行为准则。
在这个单元中,我们不会牵扯到第一个定义,而第三个定义才是我们这一个章节研究的东西,虽然说计算机科学家和开发人员的行为准则必须反映第二个定义的道德原则。
道德原则牵扯到对与错。美得的概念通常被认为是正确的东西在一系列的发生。至于什么是对与错,可以从以下几个观点之一考虑:哲学、宗教、法律或者实用主义。
有关于哲学的辩论已经开始了2000多年,其中不乏一些伟大的人物提出的观点,比如说亚里士多德和孔子。宗教就是大家所熟悉的宗教,法律是来判断事物对与错的一种工具,而实用主义可以定义为运用常识。
虽然我们学的是CS,但是宗教信仰这类的东西确实需要在工作环境中加以考虑。法律问题显然会影响工作时间,但是他们很少会是行为准则的主要焦点。行为规则的基础仍然是有关于对与错的哲学观念和常识性的实用主义观点。这些东西会构成本章后续内容的一个框架。
计算机专业人员
无论这些人的专业是个啥,他们最起码得遵守道德规范。专业人士可以通过假如适当的专业组织来获得道德行为指导。这样的组织内会有一个行为准则,其中就会包括有关于道德实践的参考。
举个例子:英国计算机协会(British Computer Society)有四个行为准则:
- 公共利益
- 专业能力与诚信
- 对相关机构的责任
- 对此专业的责任
另一些机构和组织,比如IEEE-CS/ACM联合工作组软件工程道德规范定义了八项基础原则:
- 公共 - 软件工程师的行为应该符合公共利益
- 客户与雇主 - 软件工程师的行为应该符合客户和雇主的最大利益,同时也需要符合公共利益。
- 产品 - 软件工程师应当确保他们的产品和相关的变体符合最高的专业标准。
- 批判与判断 - 软件工程师应该保持他们专业判断的完整性和独立性。
- 管理 - 软件工程经理和领导应当支持并促进软件的开发和维护。
- 专业 - 软件工程师应当促进相对专业的诚信和声誉,同时符合公众利益。
- 同事 - 软件工程师应当公平对待他们的同事,同时也要去支持他们。
- 自身 - 软件工程师应当参与与其专业实践相关的终身学习,并促进职业实践。
虽然说上面的规则多少有些不一样,但是其中的一些内容是大致一致的:
- 都重视公众利益
- 都提出了专业人员的基本原则
- 专业人员应当自行判断情况
- 如果不确定,专业人员应该寻求建议。
(我确实觉得是上面这些内容过度抽象了,我有一说一不清楚他们想让我学啥。)
所有权与版权
上面ethic的部分实在是过于抽象所以我选择直接跳转到Ownership这一部分,至少这一部分有些实质性的内容。
如果一个人创作并且出版了一些具有独创性的作品,那么这个人就是这个作品的所有者。他就有资格去要求版权。
在这里有一个例外:个体在组织中工作。如果一个或者多个人为该组织工作并发表了他们的作品,那么这个组织就可以要求申请这些作品的版权。
版权可以被下面这些形式的作品申请:
- 文学作品
- 音乐作品
- 电影和影视作品
- 电视广播,电台和博客
- 艺术作品
- 一个计算机程序
版权因以下的两个观点而存在:
第一是:创作需要时间和精力,需要独创性思维。因此版权所有者应当有机会为此挣钱。
第二是:其他的一些个人或者组织可能会在不向创作者支付任何费用的情况下复制作品并从中赚钱。这对于版权所有者来说是十分不公平的。
版权需要通过法律程序来保护。不同的国家对于版权的法律有细微差别,但是有这么一个国际协议:版权法,是每个国家必须遵守的。例如:未经原版权持有人许可,某人不允许在另一个国家出版作品。
一般来说,版权法会包含:
- 要求记录作品的创作时间。
- 在规定的期限内,版权法会保护作品。
- 如果版权持有人去世,应当适用的法律。
- 采用版权的内容会被”©”符号注释。
如果有人买下了版权内容,那么他们就允许无限制地复制这些内容,前提是这些内容仅供个人使用。
软件许可
商业软件
商业软件本质上与一些商业产品没什么大的差别。他们一般都是由一家旨在盈利的公司创建并销售。但是他们有一个显著的差别:
设想你在科技市场买下了一台电脑,那么你就拥有这台电脑的所有权。但是如果你买下了一款计算机软件,你实际上是不会拥有他的使用权的,软件的所有权还是归属于供应商。
也就是说,买下计算机软件就是相当于买下了一个许可证,你可以在期限内使用这款软件。软件许可证可以是有期限的,也可以是买断制永久性的。
一般来说,买软件的时候都会出现一下这一些情况:
- 购买软件的每一个个体都需要去支付一定的费用。
- 一个组织可以订购一批许可证。组织内的每一个个体可以在规定的时间期限内使用这个软件。
- 对于教育工作者或者学生来说,需要支付的费用可能要相对便宜一些。
开源软件或自由软件
这两种类别都十分相似,他们都是非盈利性质的。
一些软件提供给你免费的使用权,但是软件本身是不开源的,这意味着你无法去编辑这些代码,查找代码中的BUG,或者制造属于你自己的版本。
开源软件允许你去修改代码,并基于此软件创造或者开发一个全新的软件(前提是你不要去违反开源软件的协议。)开源软件允许用户和个体查看代码的好处有很多:个体可以遍历代码并找出代码中的错误,他们也可以在一些代码托管平台上(例如Github,Gitlab)去提交自己修改的分支,以改进原来的开源部分。他们也可以发表PR(Pull request)提交合并申请或者报告开源软件的问题。也就是说:开源软件由一个强大的社区支持,而社区的力量允许开源软件作者享受好处。
人工智能(AI)
人工智能是多个学科的共同产物,包括哲学,心理学,神经科学,数学,语言学和控制工程。
人工智能涉及使用计算机或者计算机控制的设备来执行通常与人类智能行为相关的任务。我们将考虑智能人类行为的五个方面,讨论模拟这种人类行为的人工智能的一些应用。
解决问题
人工智能可以做到与你在国际象棋中对局。这可以被认为是显示了人工智能,但这只是因为国际象棋的规则是有限的。只要一台计算机拥有足够的存储容量和算力,那么这一个人工智能程序会在大量的训练之后研究更多的选项来解决现实生活中的问题,以至于人类的智力能力都无法与其竞争。
语言学
语音识别和语音合成技术已经开发并投入使用了。比如说你打一个客服电话,但是对面应答的不是一个人,而是一个机器。如果你可以清楚地描述你遇到的问题,计算机系统可能会识别你的需求,并将你移交给合适的人来帮助你。
现在的GPT语言模型也是十分的强势。没有试过的可以去注册一个New Bing试试看。
自动化
现在,机器人已经进入了工厂,开始协助大规模的生产了。这些机器人会被程序要求执行特定的循环操作。机器人的每次动作都是由某一些机制触发的。然而如果这些机器人碰到了意料之外的情况,他们就会停止运行,无论他们是否造成了任何损坏。
现在已经有很多研究旨在加速自主意识机器人的研发,为了工厂中的机器能够更灵活的处理各种任务。我们必须要在这些机器人上面增加传感器,传感器将外界信号传递给处理器,然后再由程序进行判断。
无人驾驶汽车就是一个很好的例子。不过现在在驾驶领域应用比较广的还得是自动泊车。
推理
有一些AI允许程序能够从证据和线索出发,来推理出最终的结论。最好的例子就是将数学定理交给计算机程序去进行证明和验证。
机器学习
机器学习是目前AI领域里面能给人们带来最大惊喜的分支。AI会在实际的例子中积累经验,通过正向和逆向反馈来进行学习。AI会使用一套适当的数学统计算法来学习。
这方面大家懂得都懂所以我就少写点了……
AI的影响
AI确实可以提升社会的工作效率,因为AI很适合节省一些需要重复的简单工作。在这些任务中AI可以做到比人类更高的稳定性和速度。
现在ChatGPT的爆火证明了社会确实对于AI新技术的认可和兴趣,因为AI的诞生和发展增加了人们工作的效率,减轻了人们工作的脑力支配。
然而有很多人担忧AI在未来会取代很多人类的工作,比如工厂的装配工之类的工作。这很有可能引发一批批的失业。有些人也认为AI是不具备处理部分复杂信息的能力的,比如说自动驾驶的稳定性。
只能说仁者见仁智者见智吧。
第十一章:数据库
第二章到第十章中间的内容之后目前还没讲,之后再说
关于数据库
我们所说的数据库,一般指的是数据库管理系统,又叫数据库管理软件。英文为:Database Management System (DBMS)。
常用的数据库管理软件有MySQL,SQLite等。
在很多大型公司里,一个数据库往往是一个项目的核心。
那么数据库存在的意义是什么?既然只是为了记录数据,我为啥要使用数据库?
主要是因为,我们存在大批量的数据并且还需要高速有效地写入或检索出来。
下面用一个例子来简单解释一下数据库的优势:
设想一下,你在一家电影院里工作,影院需要录入每一部电影的片名,上映时间,电影类型等等数据,并且使用文字处理软件进行记录。
在这个例子中,我们就假定使用Windows自带的“记事本”进行txt文件的编辑吧。
这样有专门的工作人员手动往这个txt文件里塞入一行一行有关的信息。一行写满了一部电影的数据,就像这样:
| 序号 | 片名 | 导演 | 电影类型 | 时长 | 票价 |
|---|---|---|---|---|---|
| 1 | 《数据库》 | 张三 | 科幻 | 110分钟 | 56元 |
| 2 | 《开学》 | 李四 | 惊悚 | 124分钟 | 79元 |
| … | … | … | … | … | … |
那么这种处理数据的方法都会出现哪些问题捏?
· 冗余
一次换班过后,原来负责记录信息的工作人员润了。取而代之的是一个新的员工。
有一天,一部叫做《数据库》电影返场了。所以这一位新员工理所当然地更新了数据:
| 序号 | 片名 | 导演 | 电影类型 | 时长 | 票价 |
|---|---|---|---|---|---|
| 1 | 《数据库》 | 张三 | 科幻 | 110分钟 | 56元 |
| 2 | 《开学》 | 李四 | 惊悚 | 124分钟 | 79元 |
| … | … | … | … | … | … |
| 541 | 《数据库》 | 张三 | 科幻 | 110分钟 | 56元 |
这显然是不合理的,因为新录入的信息与之前的老信息发生了重复。
作为一款文字处理软件,想要排查这样的错误无异于大海捞针。
但是使用数据库就不会出现这种问题。
· 无法检索并汇总
假设电影院至今已经播出了114514部不同的电影,每一部电影都存在于这份文档中。
然后有一天你的老板让你整理出来所有票价高于80元的电影的片名,导演,电影类型等数据,汇总给老板看。
然后你打开了txt文件——
寄。
你会发现你无法通过限定数据来进行检索和整理输出。因此最好的方法就是滑动鼠标滚轮靠肉眼一行一行人工检索了。
同理,使用数据库就不会出现这种问题。
· 可移带性、规范性差
然后假如电影院记录的数据十分的完整,以至于有其他的电影院想有偿使用你的这一份txt文件。
然后对方付了钱,你发过去了这一份txt文件。
但是与此同时,收到这一份文件的另一家电影院已经开始痛苦面具了——因为标准或者语言的不同,使用的这一份数据无法直接部署给对方使用,导致对方需要花费大量的经历去做数据的重新整理。
而数据库有一套比较统一的语言系统和语法,允许数据库方便地在不同计算机上转移数据。
当然还会有更多的问题,这里就不列举了
数据库的标准
像TCP,UDP之类的传输协议,都是一些白纸黑字的成文标准。SQL也是如此。
SQL,全称 Structured Query Language。
关系型数据库内容
现在很多应用都需要处理对象与对象之间的关系。
有关数据,抽离对象,数据,以及他们的关系,就可以用面向对象的语言来进行编写。
但是如果要根据此类数据创建一个数据库,就可以用关系型数据库将我们现在最主流的应用的数据平滑地记录下来。
下面来介绍一下数据库的成分:
table
关系型数据库表达主体和关系,是通过Relation来完成的。(俗话说就是表格)Attribute代表在表格里面的一个列。
而Tuple就代表其中的一个行。
就是和Excel很像,但也仅仅是看着像了。
key
key(键)代表一个专用的特征码,甄别唯一性的一串字符。
Primary key 为”主键“,代表现役判断重复性的根据。
在作为Primary key的那一项,数据不能为空,也不能重复(只能唯一)。
在CIE考试里,在创建数据库的时候,都必须需要一个主键存在。
Candidate key 是Primary key 的候选,都可以满足Primary key的特征以及功能。
而Primary key可以不是由Candidate key里面选出,因为Candidate key的定义为: “a key that could be chosen as the primary key.”
Foreign key(外键)是在某一些表内的主键必须是主键,作为在不同表之间确定信息以及联动查询的基础。
一个表格内的一个主键拿出去给别的表做一个外键,这样就可以确定在两个表内不同的数据的联系,还可以保护数据的完整性。如果不用外键来引入与别的表格的联系,就需要将数据从另一个表格中再次输入一遍。这就出现了冗余现象。
Example
有关于这点,这里举个例子解释一下:
这里有一个考试表。下面开始在考试表内记录数据:
9月1日,1号学生在4号考场里考了语文。
9月3日,一号学生在4号考场里考了计算机。
…
你会发现,其中没有一个类型的Attribute可以作为一个key来确定。所以这样就找不出一个Candidate key了:
- 学生不可以做为key,因为学生可以考多个科目。
- 科目不可以作为key,因为一个科目可以重复被考。
- 日期就更不用说了。
但是我们需要联合两个或多个数据(不会和别的搭配重合的数据)来创建一个key,其中的每一个元素可以没有作为key的潜质。
比如我规定查询”一号学生的语文考试记录“,就一定包含唯一性。
但是只去查询日期,就没法精准定位了。
三范式
三范式存在的意义是让数据库的设计更加合理化,并落实成关系型数据库。当然,你也可以选择不去遵守三范式。
第一范式(1NF)
第一范式的内容:
简单来说就是一个单元格内只能去输入一个最小不可拆分的单元,不可再分。
比如说像这样填表:
| ID | Student |
|---|---|
| 1 | 19班20号 |
这样是不满足1NF的。满足第一范式写法需要改成:
| ID | Student_Class | Student_ID |
|---|---|---|
| 1 | 19 | 20 |
第二范式(2NF)
也就是说,一个表格需要描述一类信息,一张表仅描述一件事。
其实就是为了去冗余。
Example
表格:Exam
| Student_ID | Course_ID | Date | Student_Name | Course_Name |
|---|---|---|---|---|
| 1000 | 101 | 2002.3.10 | 张三 | Linear Algebra |
在这个表格里,Student_ID,Course_ID和Date作联合主键。因为三者制约完全可以保证确定一个数据。
Student_Name依赖于Student_ID, Course_Name依赖于Course_ID。这种情况叫做部分依赖。
而部分依赖,是不符合第二范式的。
因此,我们可以将Student_Name和Course_Name抽离至两个新表格Student和Course。
在Student表格内,Student_ID为Student表主键。需要将Student_ID列抽离到学生考试表格做外键。
在Student表格内,Course_ID为Course表主键。需要将Course_ID列抽离到学生考试表格做外键。
如下所示:
Student ( Student_ID, Student_Name )
Course ( Course_ID, Course_Name )
Exam ( Student_ID, Course_ID, Date, Student_ID(fk), Student_ID(fk) )
下划线代表主键,(fk)代表外键。
第三范式(3NF)
好比说我在列一张表:
| main | commits | branch | system |
|---|---|---|---|
规定main是主键,则commits,branch,system都必须与main有联系。
假如说system仅与branch有关系,则证明不符合第三范式。
使用三范式规范化数据库
下面是一张信息表。将其转换成数据库的形式,并符合三范式要求。
Order no: 07845
Date: 25-06-2016
Customer no: 056
Customer name: CUP
Address: Cambridge square Cambridge
Sales rep no: 2
Sales Rep name: Dylan Stoddart
Product no Description Quantity Price / unit Total 327 Inkjet cartridges 24 $30 $720 563 Laser toner 5 $25 $125 Total Price: $835
在表格上方的数据,都具有原子性。
解释一下上半部分的数据:
customer_name:
customer_name显然是依赖于customer_id的,而且与order_id没有任何关系。
因此在order_table内不应该包含customer_id。
sales_rep_name:
同理,
sales_rep_name是依赖于sales_rep_id的,而且与order_id没有任何关系。因此在
order_table内不应该包含sales_rep_name。
address:
address是可以发生变化的。如果address依赖于customer_id,则代表address是固定的。 但是在实际情况下,一个订单只能有一个地址,但是收货人可以选择相对于他的多个地址。
比如说第一次寄到学校,第二次寄到公司,第三次寄到家里…因此,
address是依赖于order_id的。
接下来再分析一下下面表格的数据:
price/unit:
- 这是一个比较纠结的问题。
price/unit实际上是不依赖于product_id的。
因为如果实际操作中一旦改价格,主键不允许重复的特性会导致之前的老价格丢失掉。 - 但是书上是学的理论知识,将
price放到product_table里面也是可以的。因为没有违反任何范式。
因为第二范式的存在,我们不得不生成一个叫做product_table的表格,记录产品信息:
表格: product_table
| product_id | description | price/unit |
|---|---|---|
| 327 | Inkjet cartridges | $30 |
| 563 | Laser toner | $25 |
还需要生成customer_table和rep_table两个表格记录ID和名字的对应信息及关系:
表格: customer_table
| customer_id | customer_name |
|---|---|
| 056 | CUP |
表格: rep_table
| sales_rep_id | sales_rep_name |
|---|---|
| 2 | Dylan Stoddart |
还需要一张记录所有order信息的表格,记录order的信息。product_table和rep_table中的主键,在此表格中为外键。
表格: order_table
| order_id | date | customer_id (fk) | address | sales_rep_id (fk) |
|---|---|---|---|---|
| 07845 | 25-06-2016 | 056 | Cambridge square, Cambridge | 2 |
在此表格中,order_id构成主键。
我们在上面创建的所有表格之间都确立了某种联系。
所有的表格创建完之后,就可以使用内外键来从Product_order表中确定商品和订单的关系了。
表格: Product_order
| product_id | order_id | description | quantity | total |
|---|---|---|---|---|
本表格是product和order的关系表。
在此表格中,product_id和order_id构成联合主键。
数据库管理系统 (DBMS)
有关DBMS
数据库不仅仅是数据的集合,理解这一点至关重要。
数据库是按照理论模型的规则实现的。
大约40年前,ANSI(美国国家标准协会)在其三级模型中提出了这一基本概念。这三个层次是:
- 外部层面 (External level)
- 概念层面 (Conceptual level)
- 内部层面 (Internal level)
结构如下图所示:
这个图面内容展示了数据存储在硬盘上的结构。
数据库存储的细节只有内部层面 (Internal level)才被指示出来,内部层面是ANSI架构中最低级的一个层级。
所有的访问数据的请求和处理,全部由数据库管理系统 (Database management system, DBMS)控制。
在更高一层的概念层面,数据库有一个单一的通用视图 (View),这个视图可以由一个有特定权限访问DBMS的管理员控制,叫做数据库管理员 (Database Administrator)。
向用户提供视图的好处是:他们可以被数据库管理员用作一种确保安全性的机制。
单个用户或者用户组可以被DBA管理赋予适当的访问权限,以控制该试图允许的操作。
例如,用户可以读取数据,但是不能修改数据。或者用户只能访问数据库中有限数量的表。
在ANSI体系结构中,概念层面有一个描述用户或者程序员感知的数据组织的概念模式,这也可以被描述成逻辑模式 (Logical schema)。
逻辑模式是由数据库设计者综合所有的数据需求,并从全局的角度对数据库中全部数据的逻辑结构和特征的总体描述。是所有用户的公共数据视图,也叫做全局视图。
DBMS提供的功能
无论数据库的大小如何,一种通用的人机沟通方法是使用专用语言SQL。SQL语言会在下一节讨论。
对于大多数的DBMS类型,都有SQL命令的替代方案。比如说DBMS通过开发者接口提供软件管理工具,这种工具允许他们去在数据库内创建表格,并定义属性以及数据类型。
此外,DBMS还为程序员提供了开发用户界面的工具。DBMS还提供了一个查询处理器 (Query processor),查询处理器允许我们创建和处理数据库中的查询操作。查询就是从数据库中提取和操作数据的机制。
DBMS还可以生成一个和格式化的报告,或者一个表格。程序员可以在UI中合并对于查询和报表的访问。
被DBA使用的DBMS功能
DBA的职务是负责设置用户和程序员视图,并定义适当的、特定的访问权限。
DBMS的一个重要特性是数据词典 (Data dictionary),他是数据库的一部分。除了DBA之外,没有人能够看见数据词典。
数据词典包含了有关数据的元数据。
数据词典内可以包含以下内容:
- Field / Attribute names
- Table name
- Validation rules
- Data types
- Primary keys / Foreign keys
- Relationships
综上所述,数据词典包含所有表的属性和定义的细节,同时也包括物理存储是如何组织的。
DBA也可以为表格创建索引 (Index)来提高数据库查找数据的性能和能力。
索引是一个用于快速搜索的小型辅助表,它包含被搜索表中的一个attribute和指向该表中tuple的指针。
如果表中包含大量的attribute或者tuple,我们就很有必要为表格创建索引。
索引是具有为一只的属性相关联的辅助表。索引表包含属性值和指向原表中对应tuple的指针。索引可以在主键上,也可以在辅助键上。
搜索索引表通常来说比全表查询要快得多。
MySQL及命令及语法
数据定义语言 (DDL)
数据定义语言 (Data definition language, DDL)是SQL中用于创建或者修改表的语言。这些命令只会创建数据库的结构,但是他们不负责将任何数据存入数据库。
下面这是一段DDL的实例:
1 | CREATE DATABASE BandBooking; |
DDL有一些特性:
- SQL命令由一系列命令组成。
- 每一个命令由
;终止。 - 一个命令可以包含多行。
- 不区分大小写。
- 但是对于命令中的关键字,比如说
CREATE或者ALTER使用全大写。对表格名称,attribute名称或者数据类型使用小写。 - 当命令包含一系列项目的时候,每一个项目使用逗号隔开。
这些例子表明,一旦创建了数据库,就可以创建表和定义属性。
可以在CREATE TABLE命令中定义一个主键和一个外键,但是也可以使用如下所示的ALTER TABLE命令(它也可以用来添加额外的attribute)。
数据操作语言 (DML)
数据操作语言 (Data manipulation language, DML)可以用于下面这三种情况:
- 在创建数据库的时候将数据插入到表格中。
- 修改或删除数据库中的数据。
- 读取存储在数据库中的数据。
下面我会给出一系列例子来展示使用DML来向表格中填充数据:
1 | INSERT INTO Band ('ComputerKidz', 5) |
第一行的插入数据的方式是,根据INSERT INTO后面括号里的数据,依次填充每一个attribute。
第二第三行就使用了一种相对保守的方法。
首先第二行指定了我需要填充Band-Booking表格中的BandName和BookingID两个attribute,然后在第三行使用VALUES命令按照第二行定义的数据顺序为他们赋值。
你会发现:
- 两个命令都使用了括号。
- 如果需要向表格中每一个attribute添加一个值,那么使用
INSERT命令比较合理。 - 这些属性都有顺序。
DML的另一个用途是从数据库中查询数据,无论是原始数据还是合并数据。
这些命令总是先从SELECT命令开始。
最简单的查询形式是将attribute作为输出列出来:
1 | SELECT BandName FROM Band; |
代表从Band表格中选出了BandName这个attribute。
注意每一个元素中间都有一个空格。
我们假设Band表格只有两个属性。如果要列出两者的值,我们同样由两个方法。
1 | SELECT BandName, NumberOfMembers |
或者:
1 | SELECT * FROM Band |
在第一种方式中,被选中的attribute之间使用逗号隔开,我们也不需要使用括号把attribute括起来。
在第二种方式里面,我们使用*(星号)来表示表格中的所有attribute。
我们可以在SQL中使用控制输出指令,来规范我们输出的样式。
我们可以使用ORDER BY 命令来将输出的内容排序。比如说我们使用字母顺序来显示乐队名的数据:
1 | SELECT BandName, NumberOfMembers |
在上面的实例中,我们将BandName和NumberOfMembers两个attribute根据BandName进行了排序。请记住,ORDER BY命令的排序是默认升序排序,如果想使用倒序排序,我们可以将最后一行命令改成这样:
1 | ORDER BY BandName DESC |
升序是小在上大在下,降序是大在上小在下。
在这次查询中,没有重复条目的问题,因为BandName是BandName表的主键。
然而,在Band-Booking表中,一个单独的BandName值会出现很多次。因为一个乐队可以有很多不同的Booking。返回Booking值会蹦出很多相同的BandName值。
所以我们可以使用GROUP BY可以防止这种情况,如下所示:
1 | SELECT BandName |
这样输出的值就会按照不同的BandName归类了。
我们也可以将输出的数据加一些限制条件。这时候就可以使用WHERE命令了:
1 | SELECT BandName |
上面的命令只会返回当Headlining的值为Y的结果。
也可以同时查询多个attribute:
1 | SELECT BandName, NumberOfMembers |
返回所有人数大于二的乐队。返回内容包含符合条件的两个attribute的内容。
聚合函数 (Aggregate functions)可以对一组值进行计算,并返回一个单一的值。聚合函数有很多种,比如SUM,COUNT或者AVG等等。
下面开始举例:
1 | SELECT Count(*) |
表示Band中所有tuple的数量。
1 | SELECT AVG(NumberOfMembers) |
返回在Band表格中所有NumberOfMembers的平均值。
同样:
1 | SELECT SUM(NumberOfMembers) |
返回在Band表格中所有NumberOfMembers的总和。
有时候我们需要的数据存在在两张不同的表格中,这时候我们就需要用到连表查询。
查询可以基于两个表中数据之间的连接条件,最常用的链接方式是内连接 (inner join)。如下所示:
1 | SELECT VenueName, Date |
Band-Booking.BandName代表在Band-Booking表格中的attributeBandName。
上表将Band-Booking中的BookingID和Booking中的BookingID连接在了一起。其中Band-Booking表中的BookingID等于Booking表中的BookingID,并且Band-Booking表中的BandName列等于ComputerKidz。
这就是内连接,内连接的条件是Band-Booking.BookingID = Booking.BookingID。
Query Processor会这样处理这一段代码:
- 搜索乐队名称为ComputerKidz的实例。
- 查看BookingID。
- 然后,在Booking表中搜索具有此值的tuple。
- 对于符合条件的每一个数据,VenueName和Date都在输出中显示。
你也可以使用INNER JOIN命令来执行内连接操作。
1 | SELECT table1.column1, table2.column2 |
选定了需要输出attribute之后,使用INNER JOIN命令来确定谁与这些内容发生内连接。
随后使用ON 命令写出内连接条件。
DML的另一个用途是修改存储在数据库中的数据。UPDATE命令用于修改数据。如果ComputerKidz乐队招募了一个额外的成员,下面的SQL语句会做出必要的改变:
1 | UPDATE Band |
首先定位需要更改值的表格,然后声明我要将NumberOfMembers改成6。
最后使用WHERE告诉Query processor说,我要更改BandName是ComputerKidz的值。
如果不使用这个WHERE指令,数据库就会把表格中所有的NumberOfMembers改成6。
DELETE命令用于从数据库中删除数据,我们必须谨慎处理删除数据的操作。
假如说乐队ITWizz决定解散,我们就可以从数据库中删除他们的名字:
1 | DELETE FROM Band-Booking |
这样的就在Band-Booking表格和Band表格中都删除了这个乐队。
命令基本操作
下面来实操一下:
首先我们需要创建一个数据库。
使用create database命令创建一个database。
比如说,下列命令:
1 |
|
可以创建一个叫做school_system的一个数据库。
输出为:
1 |
|
然后,可以使用show databases;命令展示现有的所有数据库。
运行show databases的输出为:
1 |
|
在这里,school_system数据库即为我们刚才创建的数据库,其余的都是自带的。
如果想向数据库内添加数据,需要进入到特定的数据库内。(类似于cd命令)
这里可以使用use *数据库名*来进入到特定的数据库。
运行use school_system命令的输出结果为:
1 |
|
代表我们已经成功地进入了此数据库。
接下来,使用create *参数*命令是要定义数据结构。
此命令后面需要跟着要填入的数据以及信息。
比如说此命令:
1 |
|
命令代表创建一个叫做student的表格。
里面的参数为:
student_id int,代表创建一个名称为student_id的Field。它的数据类型为整型。
student_name varchar(50),代表数据类型是student_name,数据类型是varchar,长度上限为50。
P.S. varchar代表“可变的数据长度“。
student_gender char(1),代表在student_gender中,数据类型是char,上限为1。char代表”定长数据“。
输出结果为:
1 |
|
代表表格创建成功了。
这里有几个注意事项:
;代表一行命令结束。当写下一行命令后,程序不会直接完成操作,直到出现了一个;。- 如果在
student_gender char(1)的末尾加一个逗号,会判定为错误。因为这已经是此次create命令里面最后一行参数,不需要再次使用逗号隔开参数。 - 多有
()是成对出现的。括号的范围代表命令参数的范围。
使用show tables;命令展示数据库内所有的table。
在这里运行show tables;的结果为:
1 |
|
说明已经存在一个student table了
之后,我们需要写入数据。
使用insert into命令写入数据。
以下命令:
1 |
|
代表向student表格内插入(1000, '张三','M')三个数据。其中:1000对应student_id张三对应student_nameM对应student_gender 。
运行后输出为:
1 |
|
同样代表写入成功。
输入select命令,可以查看table中的数据:
运行select * from student;命令的输出为:
1 |
|
在此命令中,*代表范围内的全部。
PART TWO:基本问题的解决与编程技能
第十二章:算法设计与解决问题
计算思维
计算思维是一种解决问题的思路,通常以清晰的步骤来呈现。
计算思维是一种逻辑思维,在计算机这门学科中,使用计算思维来解决问题是十分常见的。
计算思维包括五大部分:“抽象问题”,“分解问题”,“数据建模”,“样式识别”和“算法思维”。
抽象问题
抽象问题的目标是将问题最本质最中心的部分提取出来,过滤掉我们不需要的信息,以便我们分析并解决问题。
这在我们的生活中是很常见的,比如开车在市中心规划最近的路线,我们就可以抽象我们想要的信息单独处理。
就像数学中的化简思维一样,把复杂的问题简单化,就可以让我们解决更困难的问题。
分解问题
下一步就是要把一个大块的问题分解成若干小问题,并一个一个解决。
数据建模
数据建模管的是数据的管理,分析和处理。
样式识别
有点像是套公式的意思:总结问题并发现是不是已经有相关的;成系统的解决方法,可以解决这个问题。
比如说移用已经存在的算法,比如冒泡排序。
算法设计
最后我们就需要设计一个可以解决问题的算法。
算法
我们每天都会使用算法。
假如说你想要烤个蛋糕,你可以遵循下面的步骤:
- 称量下列的原料:200g白糖,200g黄油,4个鸡蛋,200g面粉,2茶匙的酵母和2茶匙的牛奶。
- 将这些食材放入一个大碗中混合,只到混合物变得质地均匀。
- 将混合物倒入一个蛋糕模具。
- 放入烤箱,将烤箱设置为190℃,烘烤20分钟。
- 检查蛋糕到底有没有烤好。
- 将蛋糕从烤箱中的模具中拿出来,并放置在铁架上冷却。
上面的这一些步骤就是一个算法。这些食材是输入部分,而蛋糕就是这个算法的输出。算法具体的过程是讲原料混合,然后放入烤箱烘烤。
有些时候问题是会发生一些灵活的变化的,其中一些条件变化就会影响到我们解决问题的步骤。
比如说我们现在要去考虑如何在伦敦地铁中到达想要去的目的地。
从 King’s Cross St. Pancras 到 Westminster,一共有两条备选路线:
A:乘坐Victoria Line 到Green Park(4站),然后再换乘Jubilee Line到Westminster(1站)。
B:乘坐Piccadilly Line 到Green Park(6站),然后再换乘Jubilee Line到Westminster(1站)。
A看起来像是最好的路线,但是如果在Victoria Line上面有施工的话,那么B就是最好的路线。这种情况下我们就需要重新设计我们的算法。
如果以上的逻辑写成有点类似于代码的形式,那么它看起来就是这样的:
1 | IF there are engineering works on the Victoria Line |
算法的表示
在计算机中,我们会先将代码的结构或者思路以结构化英语 (Structured English)或者伪代码 (Pseudocode)表示。
有时我们也会使用流程图 (Flowchart),侧重于表示代码的逻辑过程。
算法包含很多细分的步骤,但是有些时候我们不想让计算机执行某几行代码,或者我们想重复某几行代码。
在计算机科学这门课程中,当我们在编写算法的时候,我们需要遵守下面这几个基本的结构:
- 赋值: 赋予数值一个名称,或者叫做标识符,或者更改指定标识符所代表的值。
- 顺序: 一个接一个地执行步骤。
- 选择: 在某些条件下执行某些步骤,否则就执行另一些步骤。
- 重复: 一系列的步骤被重复执行多次,这也可以被叫做迭代或者循环。
我们在使用计算机解决问题时会涉及各种各样的数据,数据流在计算机中的处理方式一般是输入 -> 处理 -> 输出。
处理好输入和输出后,我们就需要深入处理部分。首先我们需要了解处理的详细方法是什么,处理的步骤是什么样子的,我们的程序会怎么样设计。
下面给出了部分处理的不同表示方法。包括结构化英语,伪代码和流程图。
分配与顺序:
结构化英语:
SET A TO 34
INCREMENT B伪代码:
A ← 34
B ← B + 1
选择:
结构化英语:
IF A IN GREATER THAN B
THEN …
ELSE …伪代码:
IF A > B
THEN ….
ELSE ….
ENDIF
重复:
结构化英语:
REPEAT UNTIL A IS EQUAL TO B…
伪代码:
REPEAT
…
UNTIL A = B
输入:
结构化英语:
INPUT A
伪代码:
INPUT “Prompt: “ A
输出:
结构化英语:
OUTPUT “Message”
OUTPUT B伪代码:
OUTPUT “Message”, B
变量
定义
当我们在程序中处理数据的时候,他们都需要被存进内存中。
我们需要把这些数据放在一个特殊的位置,好允许他们去自由读写。
我们一般将这些内存中的位置叫做变量 (Variables)。
这些变量就好比是一个贴上标签的盒子。当一个值被输入了之后,值就会被存在一个有标识的容器内。
标识符表
标识符表是用来解释每一个变量是干嘛用的,一般来说还要列出他们的数据类型。
比如说我这里有一个被写成结构化英语形式的问题:1
2
3INPUT number of miles
CALCULATE number of km
OUTPUT calculated result as km
在我开始写伪代码之前,我需要先分析问题如何解决。
在这个问题中,我们需要设计一个变量,来存储输入的里程值,叫做Miles好了。
同时还需要另一个变量,用来存储转化为公里数后的结果。这里我选择定义这个变量为Km。
这样就可以开始列表了:
| Identifier | Explanation |
|---|---|
| Miles | Distance as a whole number of miles. |
| Km | The result from using the given formula: Km = Miles * 1.61. |
请记住:所有的标识符表中都必须包含标识符,数据类型和解释。
(我只不过是没在这里加数据类型而已,因为数据类型在下一章才会接触到)
赋值
下面我们会写到很多伪代码。
课本里出现的伪代码并不是一个确切的语言,也就是说,可能每一家出版社的计算机课本的伪代码语法都不一样。
下面的赋值内容中出现的所有伪代码,同样确定了本书伪代码的语言规范。本书之后所有的伪代码全部遵守下面的语法规范。
向变量中赋值
我们来简单举一个例子。这个例子在下面的小节中也会用到。
假如说我有一个变量NumberOfGuesses,用来记录在一个猜数字的游戏中,玩家一共猜了多少次;
玩家的名字会存储在一个叫做ThisPlayer的变量中。
玩家猜的数字会存在一个叫做Number的变量中。
那么下面的伪代码就讲述了我将用户的输入存入Number的过程:1
INPUT Number
随后我们要将NumberOfGuesses中的数值变为1,因为玩家做出了他的第一次猜测:1
NumberOfGuesses ← 1
更新值
假设玩家再次做出了一次猜测,那么变量NumberOfGuesses就应该加一:
1 | NumberOfGuesses ← NumberOfGuesses + 1 |
复制值
值可以被从一个变量中复制到另一个变量中。
假如说我们有一个变量Value1,里面有一个值15。
现在我们想要将这个值复制到变量Value2中,伪代码就可以这么写:
1 | Value2 ← Value1 |
放在左边的变量是复制操作的目标变量。
复制完成后,Value1和Value2的值都是15。
交换值
如果我们想要交换两个值,我们就需要第三个变量帮忙了。
假设Value1为15,Value2为34。
我想要让Value1和Value2的位置交换,这时候我可以定义一个新的变量,叫做Temp,用于存放临时数据。
接下来就可以写伪代码了。这看起来应该不算难理解:
1 | Temp ← Value1 |
逻辑表达式
还记得一开始的地铁问题吗?
1 | IF there are engineering works on the Victoria Line |
在这个问题的实际解决过程中,我们需要使用逻辑表达式来解决问题。具体是用于判断那个IF条件。
下面我会列出一些本书中会用到的逻辑运算符:
| Operator | Comparison |
|---|---|
= |
等于 |
< |
小于 |
> |
大于 |
<= |
小于等于 |
>= |
大于等于 |
<> |
不等于 |
经过逻辑运算后,会输出一个布尔值(TRUE 或者 FALSE)。
特别注意的是:在一些语言里面,’=’符号通常作为赋值使用,但是再本书的伪代码部分中,‘=’是逻辑运算符,’←’是赋值符号。
Example
举个例子:
13岁以下的人被归类为儿童,19岁以上的人被归类为成年人。如果他们在13到19岁之间,他们被归类为青少年。我们可以把这些语句写成逻辑语句:
If Age < 13 then person is a child.If Age > 19 then person is an adult.If Age >= 13 AND Age <= 19 then person is a teenager.
Example
我们再举一个例子:这里有一个猜数字的游戏。猜数游戏会根据特定条件采取不同的步骤。下面是算法描述。
- 玩家需要输入一个数字,来猜测存储的秘密数字。
- 如果猜对了,那么程序就会显示祝贺语。
- 如果这个数字比秘密数字要大,就会显示“秘密数字比他要小。”
- 如果这个数字比秘密数字要小,就会显示“秘密数字比他要大。”
我们就可以将这个算法用伪代码写出来:
1 | SET value for secret number |
使用逻辑操作符AND、OR和NOT可以形成更复杂的条件。
例如,猜数字游戏可能允许玩家多次猜测,如果玩家猜了10次仍然没有猜出秘密数字,则输出不同的消息:
1 | IF Guess = SecretNumber |
像上面这样:当一个IF语句包含另一个IF语句时,我们称它们为嵌套IF语句。
循环
有些时候我们的代码需要重复执行某些命令。大家都知道代码是由上到下顺序执行的。也就是说,如果按照传统的方法重复指令,就需要一遍又一遍的写下这些代码。这就会给代码带来冗余。
但是如果我们使用重复结构,或者叫做循环,就可以避免一遍又一遍地写相同的伪代码。
Example
给个例子:
我需要写一个程序,目标是将输入的10个数字里面找出最大的数字。
我们还需要一个变量来存储一个计数器,以便我们知道什么时候比较了10个数字。
先写标识符表:
| Identifier | Explanation |
|---|---|
BiggestSoFar |
Stores the biggest number input so far. |
NextNumber |
The next number to be input. |
Counter |
Stores how many numbers have been input so far. |
代码写出来是这样的:
1 | INPUT BiggestSoFar |
在这个程序中出现了循环指令:REPEAT...UNTIL
在REPEAT和UNTIL包裹的区域内,是将要循环的步骤。
UNTIL后面会跟一个逻辑表达式。当逻辑表达式成立的时候,跳出循环。
这个题目还可以换一种方法来写:
| Identifier | Explanation |
|---|---|
BiggestSoFar |
Stores the biggest number input so far. |
NextNumber |
The next number to be input. |
Counter |
Counts the number of times round the loop. |
请注意,Counter变量的用途已经改变了。这里的Counter是要记录循环的次数。
1 | INPUT BiggestSoFar |
在第一次循环的时候,Counter的值被设为了2,下一次循环就变成了3,以此类推。最后一次循环的时候,Counter的值会被设为10。这时候达到了第二行定义过的Counter最大值,所以就会跳出循环。
Rogue value是在算法上下文中的一个特殊值,通常出现在递归或者循环算法中,作为终止条件出现。
Example
下面我来用一个例子具体解释一下rogue value是干嘛用的:
有一个非零数列以0结尾。这个数列是输入部分,请你找出这个数列中的最大值。
在这个例子中,我们可以将rogue value设为0。因为0与数据类型相同,但是超出了我们正常期望值的范围。好比说如果我的输入会包含0,那么我也可以选择-1作为rogue value。
| Identifier | Explanation |
|---|---|
BiggestSoFar |
Stores the biggest number input so far. |
NextNumber |
The next number to be input. |
其中一个可行的方案可以是这样的:
1 | INPUT BiggestSoFar |
这种算法在绝大多数的情况下可以正常工作,但是如果唯一的输入是零,整个程序就炸了。
所以说我们可以使用WHILE…ENDWHILE循环来实现同样的目的:
1 | INPUT NextNumber |
在我们进入循环之前,我们需要检查是否存在一个非零的数字输入进来。为了处理第一个数字,我们需要将其存储在NextNumber和BiggestSoFar变量中。如果我们的第一个数字是零,就不执行循环中的指令。
逐步求精法
就像我们一开始在计算机思维那里提到过的:许多我们想要解决的问题比我们目前遇到的问题更大。为了让更大的问题更容易解决,我们将问题分解为更小的步骤。这些可能需要进一步分解,直到步骤足够小,可以轻松解决。
为了使问题的解决方案可编程,我们需要将解决方案的步骤分解为序列、分配、选择、重复、输入和输出。
我们可以使用一种称为逐步求精的方法,将轮廓解决方案的步骤分解为更小的步骤,直到它足够详细。
在本章节的一开始,我们就举了一个烤蛋糕的例子。当时的第二步就被我们简单的细化了一下。
Example
老规矩,上例子:
写一个程序:将选定的符号和一个奇数作为输入。输出一个完全由选定的符号组成的金字塔形状,最后一行中的符号数量与输入的数字匹配。
好比说我输入一个数字9,就会给我输出这个:
1 | A |
上面的排版可能会歪掉,所以我简单描述下:上面代码块里面就是一个由A组成的,最下面一行有九个A的三角形。
首先分解问题:具体的步骤可以写成下面的这几行结构化英语:
1 | 1. Set up initial values |
这里的1. 2. 3.等代表解决问题需要的步骤,下面会有提到。
首先初始化,然后重复以下步骤,直到完成第一行的输出:
- 输出空格数
- 输出符号
- 调整下一行要输出的空格数和符号数
其次我们还需要考虑需要使用哪些变量,以及这些变量的作用。
比如说,我们还需要:
- 组成金字塔的符号(组成金字塔具体的字符)
- 在最后一行中字符的个数(为了让金字塔看起来对称,我们必须输入一个奇数)
然后我们还需要计算形成第一行需要多少空格。如果这个金字塔是对称的,那么第一行的最后一个字符一定出现在最后一行字符的中间位置。
我们需要将第一行输出的符号数量设置为1,这样我们就需要下面的标识符:
| Identifier | Explanation |
|---|---|
Symbol |
The character symbol to form the pyramid. |
MaxNumberOfSymbols |
The number of symbols in the final row. |
NumberOfSpaces |
The number of spaces to be output in the current row. |
NumberOfSymbols |
The number of symbols to be output in the current row. |
分解问题之后,解决他就相对简单了。
解决完前摇之后,就可以将精力专注于写解决方案上了:
第一部分初始化的代码如下:
1 | INPUT Symbol |
因为变量MaxNumberOfSymbols需要一个合法的输入(一个奇数),所以我们就需要将第二行替换成下面这样,才可以保证合法输入。
1 | REPEAT |
这里的MOD是取余的意思。如果MaxNumberOfSymbols除以二之后是1,那么这就代表输入是合法的。
如果不合法,那么程序就会一直重复输入这一步,直到输入合法。
替换进去,第一步的完整代码就是:
1 | INPUT Symbol |
第二步就是个重复开始字段,所以接下来细说第三步和第四步。
这是第三步的解法:
1 | FOR i ← 1 TO NumberOfSpaces |
一个原味i循环。
然后是第四步:
1 | FOR i ← 1 TO NumberOfSymbols |
在第五步中,我们需要将接下来每一行的空格的数量减少1,将符号的数量增加2:
1 | NumberOfSpaces ← NumberOfSpaces - 1 |
第六步会检查下一行的符号数量现在是否大于开始时输入的值:
1 | UNTIL NumberOfSymbols > MaxNumberOfSymbols |
最后就可以把整块代码合起来了。这就是最后的产物:
1 | INPUT Symbol |
Stepwise refinement本质上来讲就是分解步骤。把他用到写程序中是一个很好的习惯(
模块
另一种开发解决方案的方法是将问题分解为子任务。每个子任务可以被认为是一个单独细化的模块。模块里面包含的东西是过程 (Procedure)和函数 (Function)。
过程 (Procedure)将许多小的步骤组合在一起,并给它们一个名称(标识符)。
当我们想引用这组步骤时,可以使用这个标识符。
当我们想要执行过程中的步骤时,我们通过过程的名称调用该过程。
过程是一组给定标识符的步骤,可以调用它们执行一个子任务
函数 (Function)同样将许多步骤组合在一起,并给它们一个名称(标识符)。
但是这些步骤会生成并返回一个用于表达式的值。
函数和过程的区别在于,函数可以返回值,而过程则不能。
因为函数和过程是两种不同的代码块,它们的设计目的和用途不同。
函数的设计目的是为了返回一个值,而过程的设计目的是为了执行一些操作。虽然说你可以将函数看作是一种特殊的过程,因为它们都是由一些语句组成的代码块。
因为函数返回一个值,所以函数定义同样声明了这个值的数据类型。
我们会在下一章详细介绍数据类型。
Example
上一个小结说过的画金字塔的例子,可以完全改成模块化的。
首先根据之前的解决方法,先写一个主程序:
1 | CALL SetValues |
你会发现主程序里面充满了CALL。CALL说白了就是调用。举个例子,CALL SetValues就是要调用SetValues模块。
然后我们填充每一个模块中的内容,就可以完美运行了:
1 | PROCEDURE SetValues |
同样也可以将某些模块从过程换为函数。过程基本是一样的所以不多赘述了。
变量分全局变量 (Global variable)和局部变量 (Local variable)。
局部变量是在函数内部定义的变量,只在本函数范围内有效。
全局变量是在函数外部定义的变量,从定义变量的位置到本源文件结束都有效。
在函数中,局部变量和全局变量的区别在于它们的作用域和生命周期。
局部变量只在函数内部有效,而全局变量则在整个程序中都有效。
比如说:以下代码段中,x是一个局部变量,只在 myFunction() 函数内部有效。而 y 是一个全局变量,在整个程序中都有效。
1 | int y = 10; // 全局变量 |
第十三章:数据类型与结构
数据类型
基本数据类型
基本数据类型是那些可以通过编程语言内建的命令简单定义的变量。基本数据类型也称为原子数据类型。
在计算机科学中,整数称为整数,带有小数点的数称为实数。
如果条件要么为真,要么为假,那么这些就是逻辑值,称为布尔值 (Boolean)。
有时,我们可能想存储一个字符,这就是所谓的CHAR。
如果值总是整数,则应该定义为INTEGER类型,例如在计算循环的迭代次数时。
其他数据类型
如下表:
| Data type | Explanation |
|---|---|
INTEGER |
一个正负数字 |
REAL |
一个正负数字,但是这个数字有小数位 |
CHAR |
一个字符 |
STRING |
字符串(一堆字符) |
BOOLEAN |
逻辑表述:真或假 (TRUEorFALSE) |
DATE |
由日、月和年组成的日期,有时包括小时、分钟和秒的时间 |
记录类型
有时不同数据类型的变量是一个逻辑组。
例如关于一个人的数据可以包含姓名、出生日期、身高、兄弟姐妹数量、是否是全日制学生,等等。
其中:姓名的数据类型是STRING,出生日期的数据类型是DATE,身高的数据类型是REAL,兄弟姐妹数量的数据类型是INTEGER,是否是全日制学生BOOLEAN。
我们可以声明一个包含复杂属性的一个变量。record type是一种用户定义的类型(user-defined type),因为程序员可以决定将哪些变量(字段)记录下来。
记录类型(Record type)也称为复合类型(Composite type)。
可以在伪代码中以这样的形式创建一个记录类型:
1 | TYPE <TypeIdentifier> |
其中:<TypeIdentifier>是这个记录类型的名称,<field identifier>是其中的一个参数,而<data type>就是声明这个参数的数据类型。
我们现在狠狠的声明了一个数据类型。如果我们想要为一个变量赋予这样的数据类型的话,我们需要先声明:
1 | DECLARE <variable identifier> : <TypeIdentifier> |
想要去调用某个参数,我们就可以使用这样的语法:
1 | <TypeIdentifier>.<field identifier> |
十分的容易,十分的简单。
按照上面的“关于一个人的数据”,我们可以将定义这个记录类型的过程写成伪代码:
1 | TYPE PersonType |
假如说我们要赋予Person这个变量这样的数据类型,我们就先来一步声明:
1 | DECLARE Person : PersonType |
然后我们就可以对其中的一些参数执行一些操作了。比如说:
赋值:
1 | Person.Name ← "Fred" |
想要输出其中的一个参数,直接运行下面的命令:
1 | OUTPUT Person.Name |
数组
接下来唠唠数组。
有时我们需要将数据值组织成一个列表或表格,亦或者是矩阵。
在大多数编程语言中,这些结构称为数组。
数组是一组有序的数据项,通常里面所有元素的数据类型相同,并使用一个标识符组合在一起。
使用数组维度的数组索引 (Array index)来对各个数组元素进行寻址操作。
你可以这么理解:一个列表是一个一维数组,而一个表格或者是矩阵是一个二维数组。
在编写伪代码时,数组需要在使用之前声明。
这意味着要选择一个标识符、要存储在数组中的值的数据类型以及每个维度的上界 (Upper bound)和下界 (Lower bound)。
一维数组
当我们在纸上写下一个列表的时候,我们一般会不自觉地给每一个元素编号。第一个元素的编号通常是1。所以我们可以像看待标号列表一样看待数组。
很多的编程语言,像Java,Python,或者是VB.NET,都将第一个元素编号设为0.这同样是这个数组的下界。上界就是这个数列里面最大编号。
在伪代码中,可以使用下面的方式来声明一个一维数组:
1 | DECLARE <arrayIdentifier> : ARRAY[<lowerBound>:<upperBound>] OF <dataType> |
<arrayIdentifier>是这个数组的标识符,<lowerBound>和<upperBound>是这个数组的上下界,然后<dataType>是这个数组内元素的数据类型。
举例子:
1 | DECLARE List1 : ARRAY[1:3] OF STRING |
这几个数组的特性依次如下:
- 数组
List1的上下界是1和3,内容的数据类型为STRING,这个数组内一共有3个元素。 - 数组
List2的上下界是0和5,内容的数据类型为INTEGER,这个数组内一共有6个元素。 - 数组
List3的上下界是1和100,内容的数据类型为INTEGER,这个数组内一共有100个元素。 - 数组
List4的上下界是0和25,内容的数据类型为CHAR,这个数组内一共有26个元素。
访问一维数组
可以通过索引值访问数组中的特定元素。在伪代码中,我们可以这样写:
1 | <arrayIdentifier>[x] |
<arrayIdentifier>是数组的标识符,而[x]是索引值,用于索引对应的元素。
比如说有一个数组MyList,那么它的第n个元素就是MyList[n]。
你可以用它来执行各种操作。比如说赋值:
1 | NList[25] ← 0 |
一个是将NList中的第25个元素赋值为0,一个是将AList中第3个元素赋值为字符D。
Example
上例题:你会输入一个值,然后你需要在包含7个数字的ID数组中查找这个数字。
从数组的第一个元素开始,依次检查每个元素,直到找到搜索值或到达数组的末尾。这种方法称为线性搜索 (Linear search)。
先上标识符表:
| Identifier | Data type | Explanation |
|---|---|---|
MyList |
ARRAY[0:6] OF INTEGER |
Data structure (1D array) to store seven numbers. |
MaxIndex |
INTEGER |
The number of elements in the array. |
SearchValue |
INTEGER |
The value to be searched for. |
Found |
BOOLEAN |
TRUEif the value has been found. FALSE if the value has not been found. |
Index |
INTEGER |
Index of the array element currently being processed. |
然后就是伪代码:
1 | MaxIndex ← 6 |
挺好理解的一个程序。通过每轮循环Index + 1来实现数组的遍历。
二维数组
当我们在纸上写下一个矩阵,并希望使用索引来指出我需要引用的元素的时候,按惯例来讲是先提供行号,再提供列号。
所以说在我们声明二位数组的时候,我们需要先给出行数,再给出列数。同样,我们还需要提供每一个维度的上下界。
在伪代码中,定义一个二维数组都是这样写的:
1 | DECLARE <identifier> : ARRAY[<1Bound1>:<uBound1>,<1Bound2>:<uBound2>] OF <datatype> |
其中<identifier>是二维数组的标识符,<1Bound1>和<uBound1>是第一维的上下界,<1Bound2>和<uBound2>是第二维的上下界。<datatype>是我们需要向元素定义的数据类型。
在一个二维数列中,一个元素可以从0开始标记。但是有些时候还是使用从标签1开始的行列标记更直观一点。
比如说我们想要声明一个二维数列,用来表示一个棋盘。这个棋盘有6行7列。
这样写伪代码是没有问题的:
1 | Board : ARRAY[1:6,1:7] OF INTEGER |
访问二维数列
想要访问二维数列中的元素,我们需要使用一对儿索引来访问二维数列中的一个元素。
1 | <arrayIdentifier>[x,y] |
其中<arrayIdentifier>是需要读取的数列的标识符,[x,y]是这一对索引。这一对索引就可以像坐标一样定位其中的一个确切元素。
比如说下面的伪代码:
1 | Board[3,4] ← 0 |
这一步可以将第三行第四列的元素设为0。
当我们想要读取一个一维数列中的全部元素,就需要使用循环来遍历出每一个元素的内容。
而在二维数列,我们需要使用一个循环语句来遍历每一行,然后在遍历每一行的同时遍历每一列,以读取出所有的数据。
这里是用了一个循环嵌套,aka (nested loops),我们在之前有提到。
这样的话用结构化英语写出来就是:
1 | For each row |
文本文档
当我们需要需要永久存储数据时,使用文本文件是其中的一种方法。
例如,程序执行时保存在数组中的任何数据都将在程序停止时丢失。你可以将数据保存到文件中,并在后续执行时需要读取。
向文本文档中写入
1 | OPENFILE <filename> FOR WRITE // open the file for writing |
从文本文档中读取
现有的文件可以由程序读取。
下面伪代码语句提供了从文件读取数据的功能:
1 | OPENFILE <filename> FOR READ // open the file for writing |
向文本文档中追加内容
有时,我们可能希望向现有文件添加数据,而不是创建新文件,这可以在追加模式下完成:它将新数据添加到现有文件的末尾。
1 | OPENFILE <filename> FOR APPEND # open file for append |
文件终止符 (EOF)
The End-of-file marker (EOF).
如果想从头到尾读取文件,可以使用条件循环。
每一个文本文件的末尾有一个特殊的标记,我们可以对它进行测试。
测试这个特殊的文件结束标记是许多编程语言的标准函数。每次调用这个函数时,它都会测试这个标记,如果还没有到达文件末尾,则返回FALSE,如果到达文件末尾标记,则返回TRUE。
在伪代码中,我们将这个函数称为EOF()。我们可以使用结构REPEAT.. until EOF()。
如果文件可能不包含任何数据,最好使用WHILE NOT EOF()。
抽象数据类型 (ADT)
抽象数据类型 (Abstract data type, ADT)是一组数据和一组相关操作的集合。
说的简单点,抽象数据类型就是与对该数据类型有意义的操作封装在一起的数据类型。
抽象数据类型与下方的几个条件息息相关:
- 创建该数据结构的一个新实例
- 在数据结构中查找一个元素
- 向数据结构中插入一个新成员
- 从数据结构中删除一个元素
- 以系统的方式访问存储在数据结构中的所有元素。
本章的其余部分介绍下列抽象数据类型,分别是栈、队列和链表。
栈
想下现实世界中的栈有哪些特征?要堆东西,我们把东西堆在一起。可访问的元素是栈顶的元素。如果我们试图在堆栈中找到一个元素并将其取出,很可能会导致这一堆元素坍塌。
上图显示了我们如何以如下顺序添加四个元素时表示堆栈:A、B、C、D。
注意,这些槽是从下往上编号的,因为这感觉更自然。
BaseOfStackPointer始终指向栈中的第一个位置。TopOfStackPointer指向最后一个压入栈的元素。
当一个元素从栈中弹出(POP)时,TopOfStackPointer将递减,指向当前栈顶的元素。
当栈为空时,TopOfStackPointer的值为-1。
要使用一维数组来实现这个栈,可以这样写:
DECLARE Stack:ARRAY[0:7] OF CHAR
队列
现实世界中的队列 (Queue)有哪些特征?
当人们排队时,他们在最后加入队伍。人们从队伍的前面离开队伍。如果是一个有序的队列,就不会有人插队,人们也不会从其他位置离开。
上图展示了如何表示有5个元素以如下顺序加入队列:a、B、C、D、E。
要使用数组实现队列,我们可以假设队列的前端位于位置0。
当队列为空时,EndOfQueuePointer的值为-1。当有一个值加入队列时,End0fQueuePointer会先加1,然后再将该值添加到指针所指向的数组元素中。
当队列最前面的项离开时,我们需要将其他所有项向前移动一个位置,并调整EndOfQueuePointer。
这种方法涉及大量的数据移动。一个更有效的利用槽的方法是循环队列的概念。
指针表示队列的前端和尾部,最终,队列将“绕回”起始位置。
下图展示了一个11个元素加入队列、5个元素离开队列的循环队列:
链表
在之前的章节中,我们使用数组作为线性列表。
在线性列表中,列表项存储在连续的位置上,但是这并不总是合适的。
另一种方法是将单个列表项存储在任何可用的位置,并使用指针将单个列表项链接到一个有序序列中。
列表中的元素称为节点 (Node)。节点可以由多个数据项和一个指针 (Pointer)组成,指针是一个变量,存储了它所指向的节点的地址。
存储第一个元素地址的变量称为起始指针(Start pointer)。
在下面的图中,节点框中的数据值表示该节点的key字段。每个节点可能关联许多数据项。箭头表示指针。
它没有显示节点存储在哪个地址,因此图没有给出指针的值,只给出它在概念上链接到的位置。
下图展示了如何将一个新节点a插入到链表的开头,StartPointer的内容被复制到新节点的指针字段中,并且StartPointer被设置为指向新节点 A。
在下面的图中,一个新节点P被插入到列表的末尾。
节点L的指针字段指向新节点R,新节点P的指针字段包含null指针。
为了删除列表中的第一个节点,我们将待删除节点的指针字段复制到StartPointer中:
为了删除列表中的最后一个节点,我们需要将前一个节点的指针字段设置为null指针:
有时,节点按关键字段值的顺序链接在一起,以生成一个有序链表。这意味着可能需要在两个现有节点之间插入或删除一个新节点。
如下图所示:为了在现有节点B和D之间插入一个新节点C,我们将节点B的指针字段复制到新节点C的指针字段中。我们将节点B的指针字段改为指向新节点C:
要删除列表中的节点D,我们将待删除节点D的指针字段复制到节点B的指针字段中:
请记住,在实际应用程序中,数据可能不止包含一个关键字段和一个数据项。这就是链表优于线性表的原因。
当链表元素需要重新排序时,只需要改变链表中的指针。在线性列表中,需要移动所有的数据项。
使用链表可以节省时间,但是指针字段需要更多的存储空间。
要使用数组来实现链表,可以使用一维数组来存储数据,使用一维数组来存储指针。
读取相同索引处的数组值时,一行代表一个节点:
下图展示了如何将一个新节点添加到使用数组实现的链表的开头。
请注意,值”A”被添加到索引3处,但起始指针被调整为列表的新第一个元素。
下图展示了如何将一个新节点添加到使用数组实现的链表的末尾。
注意,“P”值是在索引3处添加的。原来包含null指针(索引为0)的结点现在调整为指向新的一个node。
删除节点时,只需要调整指针。
因为旧数据可以保留在数组中,但由于没有指针指向它,因此不再可以访问它。
下图展示了如何调整起始指针,以有效地删除链表的第一个元素。
请注意,开始指针现在包含了被删除结点的指针值。
下图给出了链表倒数第二个结点的指针值如何变为null指针的过程:
在向列表中添加需要插入的节点时,该数据会被添加到data数组的任何空闲元素中。
新节点的指针被设置为指向插入点之后的节点的索引。
注意,这是插入点之前节点的指针的值,插入点之前的节点的指针设置为指向新节点。
同样,在删除节点时,只需要调整指针即可。
下图说明了如何将待删除结点的指针复制到前一个结点的指针。
未使用的节点需要被轻易定位到。一种合适的技术是将未使用的结点连接起来,形成另一个链表:未使用链表。
下图展示了我们的链表及其空闲列表:
当节点数组第一次初始化为链表时,链表是空的,所以开始的指针是空指针。
所有节点都需要连接起来,形成未使用内存块的链表。
下图展示了向链表插入数据之前链表实现的一个例子:
假设“L”、“B”和“D”被添加到链表中,并按字母顺序保存。
下图展示了这些值是如何存储在Data数组中的,以及链表和未使用链表的指针是如何发生调整的:
如果要删除包含”B”的结点,则需要将该结点的数组元素重新链接到未使用链表中。
下图展示了如何将该节点添加到未使用内存链表的前端:
在之前的小节中,我们介绍了用户定义的记录类型。
我们将相关的数据项分组为记录数据结构。
要使用记录变量,我们首先定义一个记录类型。然后我们声明该记录类型的变量。
我们可以将这个链表存储在一个记录数组中。
一条记录代表一个节点,由数据和指针组成:
第十四章:编程与数据的表示
编程语言
在前两章节中我们学习了如何使用流程图或者伪代码来描述一个程序。我们现在介绍几个比较出名且普遍运用的编程语言:
Python
Python是一种多范式编程语言,这意味着Python完全支持面向对象的编程和结构化编程。
Python有如下特性:
- 每个语句必须在单独的一行上。
- 缩进十分的重要。这就是所谓的 “缩进规则” (Off-side rule)。
- 关键字用小写字母书写。
- Python区分大小写,比如说标识符Number1与Number1或Number1不同。
- Python中的一切都是对象,所以Python是面向对象的编程语言。
- 代码大量使用了名为“切片”的概念。
- Python程序是解释型程序。
你可以在Python Shell中输入一条语句,Python解释器会立即运行它。
你还可以在Python编辑器(如IDLE)中输入程序代码,用扩展名.py保存它,然后在编辑器窗口的运行菜单中运行程序代码。
Visual Basic Console Mode (VB.NET)
VB.NET是在.NET框架上实现的一种多范式的高级程序设计语言。
微软推出了VB.NET作为其最初的Visual Basic语言的继承者。
微软的集成开发环境(IDE),用于用VB进行开发,其中的NET就是Visual Studio。
隶属微软的Visual Studio Express和Visual Studio Community都是免费软件。
课本里面的所有Visual Basic程序都是使用Microsoft Visual Basic 2010 Express Console应用程序编写的。
有关于VB.NET,这里有一些事实:
- 每个语句都应该在单独的一行中。可以在同一行中键入语句,以冒号
:作为分隔符。但是,我们不推荐这样做。 - 缩进是好文明(
- VB.NET中不区分大小写。现代的VB.NET编辑器将自动从标识符的第一个定义中复制案例。
- 我们一般对标识符和关键字使用CamelCaps表示方法(也称为PascalCaps)。
- 程序需要编译才能运行。
CamelCaps代表首字母大写的命名法则。
当我们在IDE中输入程序代码,保存代码之后单击Run按钮。这将启动编译器。
如果没有语法错误,编译后的程序就会运行。输出将显示在一个单独的控制台窗口中。
注意,当程序完成执行时,控制台窗口会自动关闭。
所以为了让控制台窗口一直打开以便能看到输出,程序的最后一条语句应该加上这一行:
Console.ReadLine()
Java
Java最初由James Gosling在Sun Microsystems(现为Oracle所有)开发,于1995年发布。
Java运行环境(Java Runtime Environment, JRE)的目标是面向用户,而Java开发包(Java Development Kit, JDK)面向软件开发人员,其中包含Java编译器 (Java Compiler)和调试器等开发工具。
Java的设计与运行平台无关。也就是说Java编译后的代码可以在所有的操作系统上运行。
有关Java的一些事实:
- 每个语句都以分号
;结尾。一行可以包含多条语句,但我们不推荐这样做。 - 缩进是一种很好的做法。
- Java区分大小写。
- 按照惯例,标识符使用CamelCaps格式大写,关键字使用小写,类 (class)的标识符使用大写。
- 复合语句由括在花括号
{中的语句序列组成。 - 只要Java语法需要使用语句,就可以使用复合语句。
- 程序需要编译成字节码,然后使用Java虚拟机 (Java Virtual Machine)运行。
Java几乎被设计为一种完全面向对象的语言。
Java中所有代码都是在类 (Class)中编写的。
只有简单数据类型(如integer、real)不是对象。字符串也是对象。
源文件必须以其包含的public类命名,并添加java后缀,例如Exl.java。
它首先必须使用Java编译器编译成字节码,生成一个名为Exl.class的文件。只有这样它才能被执行。
方法名main在Java语言中不是关键字。它只是Java启动器为将控制权传递给程序而调用的方法的名称。
和VB.NET一样:如果没有语法错误,编译后的程序就会运行。输出将显示在输出窗口中。
编程基础
(你可能发现这一小结的目录充满了冗余。不过我也没啥办法因为这个Hexo主题没法支持四级标题lol)
变量的声明
大多数编程语言都要求你声明要存储在变量中的数据的类型,以便编译器能够分配正确数量的内存空间。
声明变量的时候,数据类型决定了它能存储的内容。
声明为存储整数(integer)的变量就不能用于存储字母数字字符(字符串),反之亦然。
VB.NET和Java要求在使用变量之前声明变量。
在伪代码中,声明变量可以以下面的方法完成:
1 | DECLARE <identifier> : <datatype> |
下面的代码:
1 | DECLARE Number1 : INTEGER |
分别为:
定义Number1用于存储数字。
定义YourName用于存储字符串。
定义3个整数变量。
定义两个字符串变量。
语法定义和例子
下表展示了语法定义:
| 语言 | ~ |
|---|---|
| Python | Python没有变量声明。 |
| VB.NET | Dim <identifier>[,<identifier>]As <datatype> 每一行声明必须以 Dim开头。 |
| Java | <datatype> <identifier>[, <identifier>] |
举出一些例子:
Python
1 | # Number1 of type Integer |
这里面都是注释。虽然Python没有变量声明,但我们还是应该在模块开头添加注释。
VB.NET
1 | Dim Number As Integer |
可以将多个相同类型的变量放在同一行中。
Java
1 | int number1; |
同样,你可以将多个相同类型的变量放在同一行中。
常量的声明和赋值
有时,我们在程序中使用一个永远不变的值,例如数学常数pi的值。
为常量指定一个名称,并在程序开始时声明它,这是一种好习惯,有助于提高可读性,而不是在程序语句中直接使用一个实际的值。
在为代码中,我们将这样的常量赋值写为:
CONSTANT <identifier> = <value>
比如:
CONSTANT Pi = 3.14
。
语法定义和例子
下表展示了语法定义:
| 语言 | ~ |
|---|---|
| Python | <identifier> = <value> |
| VB.NET | Const <identifier> = <value> 每一行声明都必须以关键字 Const开头。 |
| Java | static final <datatype> <identifier> = <value> 每一行常量定义都必须以 static final开头。 |
举出一些例子:
Python
1 | PI = 3.14 |
在Python中,我们约定俗成的规定是只使用大写来写常量标识符。常量的值是可以改变的,但我们最好是要把它们当作不能改变的值。
VB.NET
1 | Const Pi = 3.14 |
在VB.NET中,常量的值不能够再被修改了。
Java
1 | static final double PI = 3.14 |
同样,在Java中,常量的值不能够再被修改了。
变量的赋值
一旦声明了变量,就可以给它赋值。
伪代码可以这样写:
<identifier> ← <expression>
比如:
1 | A ← 34 |
语法定义和例子
下表展示了语法定义:
| 语言 | ~ |
|---|---|
| Python | <identifier> = <expression> |
| VB.NET | <identifier> = <expression> |
| Java | <identifier> = <expression>; |
不难看出:三家的赋值语法都基本一致,不过Java的赋值语句最后还要多一个分号;。
举出一些例子:
Python
1 | A = 34 |
赋值符是=。
VB.NET
1 | A = 34 |
同样,赋值符是=。
但是VB.NET允许你在声明数据的同时初始化变量。比如:
1 | Dim Number1 As Integer = 0 |
Java
1 | A = 34; |
同样,赋值符是=。
Java也允许在声明语句中初始化变量,例如:
1 | int number1 = 0; |
VB.NET和Python都允许你将递增语句例如B = B + 1写成 B += 1
Java则需要将递增语句例如b = b + 1写成b++;
算数运算符
赋值不只是给变量赋初始值。需要存储计算结果时,也可以使用赋值操作。
用于计算的算术运算符如下表所示:
| 运算 | 伪代码 | Python | VB.NET | Java |
|---|---|---|---|---|
| 加法 | + |
+ |
+ |
+ |
| 减法 | - |
- |
- |
- |
| 乘法 | * |
* |
* |
* |
| 除法 | / |
/ |
/ |
/ 仅除以float或double类型时使用此运算符。 |
| 指数 | ^ |
** |
^ |
在Java里面没有专门用于指数运算的运算符。 唯一的方法是使用这行代码: Math.pow(n,e) |
| 整数除法 | DIV |
// |
\ |
/ 仅对integer数据类型作整数除法时使用。 |
| 取余 | MOD |
% |
mod |
% |
当表达式中出现多个操作符时,求值的顺序取决于数学的优先级规则 (Rules of precedence):括号、幂、乘、除、加、减。
输出信息
在伪代码中这么写:
1 | OUTPUT <string> |
当输出文本和数据到控制台屏幕时,我们可以在print列表中列出输出字符串和变量值的混合。
语法定义和例子
下面展示了语法定义:
Python
1 | print(<printlist>) |
打印列表中不同的项使用逗号,分隔。
为避免移到输出后的下一行,使用end = ‘’
双引号中的内容填充打印列表中两个元素之间的内容。
VB.NET
1 | Console.WriteLine(<printlist>) |
打印列表中所有的项用&隔开。Console.Writeline会在输出后移动到下一行,而Console.Write会在输出完毕后继续留在同一行。
Java
1 | System.out.print(<printlist>); |
打印列表中所有的项用+隔开。System.out.print会在输出后移动到下一行,而Console.Write会在输出完毕后继续留在同一行。
在伪代码中想使用差不多的换行操作,就要在打印列表后面使用注释声明了。
// newline和// no new line就可以实现这样的操作。
举出一些例子:
Python
1 | print("Hello", YourName, ". Your number is ", Number1) |
VB.NET
1 | Console.WriteLine("Hello " & YourName & ". Your number is " & Number1) |
Java
1 | System.out.printIn("Hello " + YourName + ". Your number is " + number1); |
在上面的代码示例中,您可以看到当输出语句非常长时,它们可以分散在多行中。因此必须将两个打印列表项之间的行分隔开。
你不能在一个字符串的中间折断,除非你把它变成两个单独的字符串。
在Python和VB.NET中,你也可以使用占位符来将输出排序。
在打印列表中,要打印的变量的顺序用{}中的序号表示,变量按正确的顺序从后面的变量列在字符串后面,中间用逗号分隔:
Python
1 | print("Hello {0}. Your number is {1} " .format(YourName,Number1)) |
VB.NET
1 | Console.WriteLine("Hello {0}. Your number is {1}", YourName, Number1) |
从用户获取输入
在编写输入语句时,最好提示用户他们要输入什么。
例如下面的伪代码:
INPUT "Enter a number: " A
就是可以起到这样的作用。
语法定义和例子
举出一些例子:
Python
1 | A = input("Enter a number: ") |
用户输入的内容会传输到变量A内。
输入的数据格式默认为字符串。因此如果想要转化成别的数据形式就需要特意多敲两个字转一下格式了。
双引号和单引号都可以用于输出提示信息。
VB.NET
1 | Console.Write("Enter a number: ") |
提示符必须单独作为输出语句提供。
Java
1 | import java.util.Scanner; |
必须先从Java库中导入Scanner类,并创建一个Scanner对象,然后才能使用它读取输入字符串。
提示符必须单独作为输出语句提供。
注释
写注释是个很好的文明(
语法定义和例子
举出一些例子:
Python
1 | # this is a comment |
注释使用#开头。
VB.NET
1 | ' this is a comment |
注释使用'开头。
Java
1 | // this is a comment |
注释使用//开头。
使用/*和*/来插入一个多行注释。
数据类型
每种编程语言都有内置的数据类型,下表给出了其中的一个子集。
对于VB.NET和Java,分配给给定类型变量的内存字节数在括号中给出。
| 数据描述 | 伪代码 | Python | VB.NET | Java |
|---|---|---|---|---|
| 带符号的整数 | INTEGER |
int |
Integer (4个字节) |
int (4个字节) |
| 带符号的有小数点的数字 | REAL |
float |
Single (4个字节) Double (8个字节) |
float (4个字节) double (8个字节) |
| 一个字符 | CHAR (使用单引号来分隔字符) |
不支持 | Char (2字节的Unicode) |
char (2字节的Unicode) |
| 字符串 | STRING (使用双引号来分隔字符串) |
str (虽然以ASCII码存储,但是Unicode也同样支持。) (使用单引号,双引号或者三个引号来分割字符串) |
String (每个字符使用2个字节存储,使用双引号来分割字符串) |
String (每个字符使用2个字节存储,使用双引号来分割字符串) |
| 逻辑表示符 | BOOLEAN |
boo1,可以有:True,False |
Boolean (2个字节),可以有:True,False |
Boolean,可以有:true,false |
在Python中,单个字符表示为长度为1的字符串。
在VB.NET中,字符串中的每个字符都需要两个字节的内存,并且每个字符在内存中表示为Unicode(在Unicode中,从1到127对应于ASCII)。
Date具有各种内部表示形式,但均以传统格式输出:
| 数据描述 | 伪代码 | Python | VB.NET | Java |
|---|---|---|---|---|
| Date value | DATE |
使用datetime类表示 | Date (8个字节) |
Date在Java中是一个类。需要使用Date请先敲入:import java.util.Date; |
布尔表达式
在之前的笔记中,我们介绍了逻辑语句。
这些语句包含一个条件。条件也称为布尔表达式,计算结果为True或False。其中,True和False都是布尔值。
简单的布尔表达式涉及比较操作符,而复杂的布尔表达式涉及布尔操作符。
| 运算 | 伪代码 | Python | VB.NET | Java |
|---|---|---|---|---|
| 等于 | = |
== |
= |
== |
| 不等于 | <> |
!= |
<> |
!= |
| 大于 | > |
> |
> |
> |
| 小于 | < |
< |
< |
< |
| 大于等于 | >= |
>= |
>= |
>= |
| 小于等于 | <= |
<= |
<= |
<= |
到这里三家语言都出奇的一致啊。
还有逻辑运算符:
| 运算 | 伪代码 | Python | VB.NET | Java | ||
|---|---|---|---|---|---|---|
| AND (逻辑连接) |
AND |
and |
And |
&& |
||
| OR (逻辑包含) |
OR |
or |
Or |
` | ` | |
| NOT (逻辑否定) |
NOT |
not |
Not |
! |
!
选择语句
If…Then语句
在伪代码这么写:
1 | IF <Boolean expression> |
语法定义和例子
下面展示了语法定义:
Python
1 | if <Boolean expression>: |
注意,在显示哪些语句是条件语句的一部分时,用冒号:替换了关键字THEN。
换言之,IF的条件后面必须跟:。
VB.NET
1 | If <Boolean expression>Then |
Then与逻辑表达式同行,而且End If要与If有同样的缩进。
Java
1 | if (<Boolean expression>) |
需要注意的是,布尔表达式被括在括号中。
如果条件语句中需要包含多个语句,则这些语句必须括在花括号{}中。
全部的语言都需要注意缩进!
举出一些例子:
Python
1 | if x < 0: |
VB.NET
1 | If x < 0 Then |
Java
1 | if (x < 0) |
If…Then…Else语句
伪代码:
1 | IF <Boolean expression> |
语法定义和例子
下面展示了语法定义:
Python
1 | if <Boolean expression>: |
缩进用于显示哪些语句是条件语句的一部分,else关键字必须与相应的if关键字对齐。
VB.NET
1 | If <Boolean expression> Then |
照格式看就好,不多赘述了。
Java
1 | if (<Boolean expression>) |
如果else部分需要多个语句,则这些语句必须被括在花括号{}中。
全部的语言都需要注意缩进!
举出一些例子:
Python
1 | if x < 0: |
VB.NET
1 | If x < 0 Then |
Java
1 | if (x < 0) |
嵌套IF语句
在伪代码这么写:
1 | IF <Boolean expression> |
语法定义和例子
下面展示了语法定义:
Python
1 | if <Boolean expression>: |
注意关键字elif必须与对应的if对齐。
这个结构中可以有任意多的elif部分。
VB.NET
1 | If <Boolean expression>Then |
如果ElseIf用作一个单词,那么在这个结构的末尾只需要一个End If。 ElseIf的数量可以根据需要而定。
Java
1 | if (<Boolean expression>) |
举出一些例子:
Python
1 | if x < 0: |
VB.NET
1 | If x < 0 Then |
Java
1 | if (x < 0) |
CASE语句
另一种选择结构是CASE语句。
CASE语句就像是条件判断:满足了哪一个条件就执行哪一个。
每个CASE的条件的类型可以是:
- 单个值
- 用逗号分隔的单个值
- 一个范围
在伪代码:
1 | CASE OF <expression> |
<statement(s)>的值决定执行哪些语句。根据需要可以有很多不同的情况。OTHERWISE是可选的,用于处理错误,我们一般叫错误捕获。
语法定义和例子
下表展示了语法定义:
Python
Python里面没有CASE语句。你需要使用连环I语句才能达到同样的效果。
VB.NET
1 | Select Case <expression> |
Java
1 | switch (<expression>) |
举出一些例子:
伪代码
1 | CASE OF Grade |
Python
1 | if Grade == "A": |
所以说想要达到CASE语句的效果,python就只能嵌套if了。
VB.NET
1 | Select Case Grade |
Java
1 | switch (grade) |
迭代
在伪代码中,计数控制循环的写法如下:
1 | FOR <control variable> ← s TO e STEP i |
里面的STEP值是可选的。<statement(s)>为两次缩进。
控制变量的值从s开始,每次循环递增i,直到到达值e时结束。
语法定义和例子
下表展示了语法定义:
Python
1 | for <control variable> in range(s, e, i): |
值s、e和i必须是整数类型。
当控制变量略低于e时,循环结束。s和i是可选的,如果没有输入,则它们的默认值分别为0和l。
VB.NET
1 | For <control variable> = s To e Step i |
s、e和i的类型可以是整型或浮点型。
Java
1 | for (int i = s; i < e; i ++) |
i是其中的控制变量。
举出一些例子:
伪代码
1 | FOR x ← 1 TO 5 |
Python
1 | for x in range(5): |
x的起始值是0,每次迭代都会加一。
输出为: 0 1 2 3 4
1 | for x in range(2, 14, 3): |
x的起始值为2,终止值为14,步长为3。
注意,在执行迭代循环的时候,第一次输出一定是起始值的值。
输出为:2 5 8 11
1 | for x in range(5, 1, -1): |
x的起始值为5,步长为-1,因此每次迭代都会使x的值减少1。
输出为:5 4 3 2
1 | for x in ["a", "b", "c"]: |
控制变量每次迭代时按顺序取方括号[]的一个值。
输出为:abc
VB.NET
1 | For x = 1 To 5 |
输出:1 2 3 4 5
1 | For x = 2 To 14 Step 3 |
输出:2 5 8 11 14
1 | For x = 5 To 1 Step -1 |
输出:5 4 3 2 1
1 | For x = 1 To 2.5 Step 0.5 |
因为命令是Console.WriteLine(),所以输出需要换行。
输出:
1 | 1 |
1 | For Each x In {"a", "b", "c"} |
控制变量每次迭代时按顺序取花括号{}的一个值。
输出:abc
Java
1 | for (int x = 1; x < 6; x++) |
输出: 12345
1 | for (int x = 2; x < 15; x = x + 3) |
输出: 2 5 8 11 14
1 | for (int x = 5; x < 0; x--) |
输出: 5 4 3 2 1
1 | for (double x = 1; x < 3; x = x + 0.5) |
输出: 1.0 1.5 2.0 2.5
1 | char[] letter = {'a', 'b', 'c'}; |
控制变量每次迭代时按顺序取letter中的一个值。
输出: abc
后置条件循环
后条件循环顾名思义,即循环内的语句至少执行一次,因为循环内的语句必须等到满足条件时才可以跳出循环。
当运行到后置条件时,我们需要对其进行评估。
只要条件求值为False,循环内的语句就会再次执行。当条件求值为True时,执行将转到循环后面的下一个语句。
编写后置条件循环时,必须确保循环内部有一条语句,在某个时刻将结束条件改为True。否则,循环将永远执行下去。
伪代码:
1 | REPEAT |
语法定义和例子
下面展示了语法定义:
Python
Python中没有后置条件循环。如果需要完成同样的目标就需要使用前置条件循环。
VB.NET
1 | Do |
Java
1 | do |
举出一些例子:
伪代码
1 | REPEAT |
Python
Python的执行方法放到下一个部分:前置条件语句中。
VB.NET
1 | Do |
Java
1 | do |
前置条件语句
前置条件循环,顾名思义,就是在循环内的语句执行之前计算条件。
只要条件求值为True,前置条件循环就会执行循环中的语句。当条件求值为False时,执行将转到循环后面的下一个语句。
注意,第一次遇到循环结构时,条件语句中使用的任何变量都不能是未定义(undefined)。
编写前置条件循环时,必须确保循环内部有一条语句在某个时候改变控制条件的值。否则循环将永远执行下去。
伪代码:
1 | WHILE <condition> DO |
语法定义和例子
下表展示了语法定义:
Python
1 | while <condition>: |
注意,循环中的语句必须按一定数量的空格缩进。
循环后的第一个语句必须减少缩进。
VB.NET
1 | Do While <condition> |
需要注意的是:Loop关键字表示循环结束。
VB.NET也有一个前置条件,直到遇见Loop。只要条件求值为False,就执行循环中的语句。如果第一次遇到循环时,条件的计算结果为True,则不执行循环中的语句。
Java
1 | while (<condition>) |
举出一些例子:
伪代码
1 | Answer ← "" |
Python
1 | Answer = '' |
VB.NET
1 | Dim Answer As String = "" |
可以将多个相同类型的变量放在同一行中。
Java
1 | String answer = ""; |
如何决定使用哪个循环?
如果你知道程序执行到循环语句时需要执行多少次循环,就使用计数控制的循环。
如果循环的终止取决于循环内部发生的某些条件,那么就使用条件循环。
前置条件循环还有一个好处,那就是如果条件不需要循环,就可以根本不进入循环。
内置函数
编程环境提供了许多内置函数。
其中一些在任何情况下都可以使用,而有些需要从特定的模块库中导入。
字符串操作函数
下表给出了一堆处理字符串的函数:
| 描述 | 伪代码 | Python | VB.NET | Java |
|---|---|---|---|---|
访问ThisString中的第P个字符 |
ThisString[P] (从1开始计数) |
ThisString[P] (从0开始计数) |
ThisString(P) (从0开始计数) |
ThisString.charAt(P) (从0开始计数) |
| 返回ASCII值为i的字符 | CHR(i : INTEGER) RETURNS CHAR |
chr(i) |
Chr(i) |
(char) i; |
返回字符ch的ASCII值 |
ASC(ch) RETURNS INTEGER |
ord(ch) |
Asc(ch) |
(int) ch; |
返回字符串S的长度的整数值 |
LENGTH(S : STRING) RETURNS INTEGER |
len(S) |
len(S) |
S.length(); |
返回S的最左边的L个字符 |
LEFT(S : STRING, L : INTEGER) RETURNS STRING |
S[0:L] |
Left(S, L) |
S.subString(0, L) |
返回S的最右边的L个字符 |
RIGHT(S : STRING, L : INTEGER) RETURNS STRING |
S[-L:] |
Right(S, L) |
S.subString(S.length() - L) |
在字符串S中,返回从P开始L个长度的字符串 |
MID(S : STRING, P : INTEGER, L : INTEGER) RETURNS STRING |
S[P : P + L] |
mid(S, P, L) |
S.subString(P, P + L) |
返回Ch的小写等价字符值 |
LCASE(Ch : CHAR) RETURNS CHAR |
Ch.lower() |
LCase(Ch) |
Character.toLowerCase(ch) |
返回Ch的大写等价字符值 |
UCASE(Ch : CHAR) RETURNS CHAR |
Ch.upper() |
UCase(Ch) |
Character.toUpperCase(ch) |
将字符串S全转换为大写 |
TO_UPPER(S : STRING) RETURNS STRING |
S.upper |
S.ToUpper() |
S.toUpperCase() |
将字符串S全转换为小写 |
TO_LOWER(S : STRING) RETURNS STRING |
S.lower() |
S.ToLower() |
S.toLowerCase() |
| 粘合两个字符串 | S1 & S2 |
s = S1 + S2 |
s = S1 + S2 或者: s = S1 & S2 |
s = S1 + S2 |
Python中的切片操作
在Python中,切片操作(slicing)是对序列型对象(如list, string, tuple)的一种高级索引方法。
普通索引只取出序列中一个下标对应的元素,而切片取出序列中一个范围对应的元素,这里的范围不是狭义上的连续片段。
下图显示了ThisString的表示形式。
如果我们想返回从位置3开始的长度为3的切片,我们使用ThisString[3 : 6]来给出返回DEF。
位置从0开始计数,切片上界的位置不包含在子字符串中。
如果您想象每个元素的编号从左端开始,那么更容易看到左元素(下界)是如何包括在内的,而右元素(上界)是如何被排除在外的。
下表显示了Python中其他一些有用的切片:
| 表示 | 输出 | 解释 |
|---|---|---|
ThisString[2:] |
CDEFG |
如果不给定上界,则切片包含到字符串末尾的所有字符。 |
ThisString[:2] |
AB |
如果不给定下界,则切片包括字符串开头的所有字符。 |
ThisString[-2:] |
FG |
负下界意味着它从字符串的末尾开始取切片。 |
ThisString[:-2] |
ABCDE |
负上界意味着它在该位置终止字符串。 |
数据截断
有时我们只需要实数没有经过四舍五入后的整数部分。
这就是所谓的截断 (Truncation)。
| 语言 | 代码 | 注释 |
|---|---|---|
| 伪代码 | INT(x : REAL) RETURNS INTEGER |
直接返回x的整数部分。 |
| Python | int(x) |
如果x是一个浮点类型的数据,则输出将会截断为0. |
| VB.NET | Math.Truncate(x) |
返回实数x的整数部分。 |
| Java | (int) x; |
将数字x强制转换为整数。 |
将字符串转换为数字
有时整数可以保存为字符串的形式。
要在计算中使用这样的数字,首先需要将其转换为整数。
比如说,这些函数可以从字符串5返回整数值5:
| 语言 | 代码 |
|---|---|
| Python | int(S) |
| VB.NET | CInt(S) |
| Java | Integer.valueOf(S) |
有时带小数点的数字可以保存为字符串的形式。
要在计算中使用这样的数字,首先需要将其转换为实数 (REAL),或者浮点数 (Float)。
例如,以下函数从字符串75.43返回实数75.43:
| 语言 | 代码 | 注释 |
|---|---|---|
| 伪代码 | STRING_TO_NUM(x : STRING) RETURNS REAL |
返回字符串的数字形式。 |
| Python | float(x) |
返回为浮点类型数据。 |
| VB.NET | CDbl(x) |
返回为双精度浮点型数据 (double)。 |
| Java | Float.valueOf(x) |
返回为浮点类型数据。 |
生成随机数
当我们在做仿真中经常需要用到随机数。
大多数编程语言都有各种可用的随机数生成器。
由于这些随机数是通过程序生成的,它们被称为“伪随机数”。
下面的代码示例展示了一些最有用的随机数生成器:
Python
1 | # in the random library: |
这段代码生成了一个介于1和6之间的随机数(包括1和6)。
VB.NET
1 | Dim RandomNumber As New Random |
首先我们必须建立一个RandomNumber对象。建立对象的内容到Paper 4会涉及。
这段代码生成一个介于包含1到不包含6之间的整数。
Java
1 | import java.util.Random; |
我们同样需要建立一个RandomNumber对象。建立对象的内容到Paper 4会涉及。
这段代码生成一个介于包含1到包含6之间的整数。
过程
在第12章中,我们使用过程 (Procedure)作为给一组语句命名的一种方式。
当我们想编写一个过程时,需要在主程序之前定义它。
当我们希望执行过程体中的语句时,我们就可以在主程序中调用它。
在伪代码中,过程的定义为:
1 | PROCEDURE <procedureIdentifier> |
想要调用过程时,需要使用下面这行代码:
1 | CALL <procedureIdentifier> |
语法定义和例子
下表展示了语法定义:
Python
1 | def <identifier>(): |
VB.NET
1 | Sub <identifier>() |
可以将多个相同类型的变量放在同一行中。
Java
1 | void <identifier>() |
同样,你可以将多个相同类型的变量放在同一行中。
举出一些例子:
伪代码
1 | PROCEDURE InputOddNumber |
在主代码中使用该过程就可以:
1 | CALL InputOddNumber |
Python
1 | def InputOddNumber(): |
Python编辑器对语句的不同部分进行颜色编码,这在你输入自己的代码时很有帮助。
缩进显示了哪些语句是循环的一部分。
内置函数input返回一个字符串,必须将其转换为整数才能作为数字使用。
VB.NET
1 | Module Module1 |
Visual Basic Express编辑器对语句的不同部分进行了颜色编码,因此很容易看出是否有语法错误。
编辑器还会自动缩进关键字并将其大写。
变量需要在使用之前进行声明。
当输入一个标识符而不跟随初始的大小写时,编辑器将跟随变量声明的大小写。
编辑器可以预测你的输入:当您键入语句的第一部分时,将显示弹出列表。
当你要运行主程序时,使用Console.ReadLine()命令来使得控制台一直打开。
Java
1 | package exl; |
编辑器会自动对关键字和字符串进行颜色编码。
过程体包含在花括号{}中。
编辑器可以预测你下一步输入的内容:当输入语句的第一部分时,IDE将显示弹出列表。
变量需要在使用之前进行声明。
函数
在之前的一个小节中,我们使用了内置函数。
这些是由其他程序员编写的有用的子程序,在模块库中提供。
最常用的库通常在系统库中,因此无需导入即可使用。
除了那些内置的函数,你可以编写自己的函数。
如果你构建了自己的模块库,那么你编写的任何函数都可以在另一个程序中使用。
函数用作表达式的一部分。
当程序执行到达表达式中包含函数调用的语句时,该函数就会被执行,然后在表达式中使用这个函数调用的返回值 (Return value)。
函数与过程最大的区别就是:函数有返回值。
编写自己的函数时,确保在组成函数(函数体)的语句中始终返回一个值。
如果函数体中有不同的结果,可以存在多个RETURN语句。
伪 be like:
1 | FUNCTION <functionIdentifier> RETURNS <dataType> |
语法定义和例子
下表展示了语法定义:
Python
1 | def <functionIdentifier>(): |
VB.NET
1 | Function <functionIdentifier>() As <datatype> |
Java
1 | <data type> <functionIdentifier>() |
当编程一个函数时,函数的定义应该写在与过程相同的地方。
该函数是从主程序中的表达式或过程中调用的。
不同的编程语言对其子程序使用不同的术语,如下表所示:
| 伪代码 | PROCEDURE |
FUNCTION |
|---|---|---|
| Python | void function | fruitful function |
| VB.NET | Subroutine | Function |
| Java | void method | method |
Void的意思是“什么都没有”。Python和Java都使用这个术语来表示它们的过程类型子例程没有返回值。
Python将这两种类型的子例程都称为函数。有”Fruit function”返回一个或多个值。
这里根据刚才讲过程的那一个小结,重新以函数的形式写出来:
伪代码
1 | FUNCTION InputOddNumber RETURNS INTEGER |
Python
1 | def InputOddNumber(): |
在声明阶段中,变量Number无法在主程序中使用,因为在Python中只要一个变量没有全局声明,就不可以在整个程序之间随意使用。
VB.NET
VB这边强势的给出了两种解法:
首先是使用了全局变量的方案:
1 | Module Module1 |
其次是使用了局部变量的方案:
1 | Module Module1 |
Java
1 | package exl; |
同样,因为没有全局声明过,变量number无法在主程序中调用。
全局变量可以在程序代码的任何部分使用,但是将变量声明为仅在子程序中使用的局部变量是一种良好的编程习惯。
在Python中,每个变量都是局部变量,除非我们主动声明它们为全局变量。
在VB.NET中,我们需要为子例程内的局部变量编写声明语句。
Java不支持全局变量。但是,类 (class)中声明的静态变量在整个类中都可以访问。
向子程序传参
当子例程 (Subroutine)需要主程序的一个或多个值时,我们在调用时将这些值作为参数 (Argument / Parameter)提供给子例程。这就是我们使用内置函数的方式。
当我们调用内置函数时,我们不需要知道函数中使用的标识符。
当我们定义一个需要将值传递给子例程主体的子例程时,我们在子例程头中使用参数列表。
当子例程被调用时,我们需要在括号中提供参数。提供的实参 (Argument)被赋值给子例程的相应形参 (Parameter)(注意,形参列表中的形参顺序必须与实参列表中的顺序相同)。这就是所谓的子程序接口 (Subroutine interface)。
你可能发现参数分为实参和形参。一般来说,当定义一个方法的时候,我们传递到方法中的变量叫做形参。,当调用一个方法的时候,传给方法的值叫做实参。
向函数中传参
在为代码中,一个函数头是这样写的:
1 | FUNCTION <functionIdentifier> (<parameterList>) RETURNS <dataType> |
其中,<parameterList>是形参的标识符及其数据类型的列表,使用逗号分隔。
举出一些例子:
伪代码
1 | FUNCTION SumRange(FirstValue : INTEGER, LastValue : INTEGER) RETURNS INTEGER |
Python
1 | def SumRange(FirstValue, LastValue): |
VB.NET
1 | Module Module1 |
Java
1 | package exl; |
向过程中传参
如果形参传递值 (passed by value),那么在调用时形参可以是一个实际值。
如果传进去的参数是一个变量,那么将该变量当前值的副本传递给子例程。
也就是说,调用程序中的变量的值不受子例程中发生的事情的影响。调用该变量后不会对元变量的值发生任何改变。(除非你的过程里面写了把变量值变换的条件)
对于过程,我们可以通过引用 (By reference)传递参数。
在调用时,实参必须是变量。指向该变量的内存位置(地址)的指针被传递到过程中。对变量内容的任何更改都将在调用程序/模块的过程之外有效。
人话讲:By value就是传进去的是一个值,但是这个值不会改变原变量的值——他就只是一个值而已。
而By reference就是直接把这个变量的内存地址给传进去了。所有的更改就会直接叠加在原变量上。
请注意,这两种参数传递方法都不适用于Python。
在Python或Java中,这个方法被称为对象引用传递(pass by object reference)。
这基本上是一种面向对象的参数传递方式,超出了本章的范围。重点是要了解如何使用Python和Java编程以获得所需的效果。
伪代码中的过程头 (Procedure header):
1 | PROCEDURE <ProcedureIdentifier> (<parameterList>) |
参数列表需要过程定义的更多信息。
在伪代码中,列表中的参数以下列格式之一表示:
1 | BYREF <identifier1> : <dataType> |
按值传递参数
伪代码中:
1 | PROCEDURE OutputSymbols(BYVALUE NumberOfSymbols : INTEGER, Symbol : CHAR) |
Python
在Python中,所有参数的行为都类似于局部变量,它们的效果就与传递值一样:
1 | def OutputSymbols(NumberOfSymbols, Symbol): |
VB.NET
在VB.NET中,传参方式默认为按值传递。
关键字ByVal是由编辑器自动插入的:
1 | Module Module1 |
Java
在Python中,所有参数的行为都类似于局部变量,它们的效果就与传递值一样:
1 | package exl; |
按引用传递参数
当参数通过引用传递时,当子例程内的值发生变化时,会影响调用程序中变量的值。
下面会给出一个有关于过程AdjustValuesForNextRow的例子:
1 | PROCEDURE AdjustValuesForNextRow(BYREF Spaces : INTEGER, Symbols : INTEGER) |
如果想要调用函数,就需要打出下面这行命令:
1 | CALL AdjustValuesForNextRow(NumberOfSpaces, NumberOfSymbols) |
在调用该函数时,参数空格和符号的值会在过程中更改。
调用之后,程序代码中的变量NumberOfSpaces和NumberOfSymbols将存储从过程中传递回来的更新后的值。
Python
Python没有提供按引用传递参数的功能。相反,下面的子程序表现为一个函数并返回多个值。
注意,在程序的主体部分中,变量是用来接收这些值的顺序的:
1 | def AdjustValuesForNextRow(Spaces, Symbols): |
这种将多个值作为一个单位处理的方式称为tuple。
VB.NET
在VB.NET中,ByRef关键字放在每个按引用传递的参数前面,用来表示按引用传递参数:
1 | Module Module1 |
Java
Java没有提供通过引用传递简单变量参数的功能,只有对象可以通过引用传递。
在Java中,数组是对象,所以数组是通过引用传递的。
1 | package exl; |
数组
创建一维数组
Python,VB.NET和Java从下界值为0开始计算数组元素。
伪代码be like:
1 | DECLARE <arrayIdentifier> : ARRAY[<lowerBound>:<upperBound>] OF <dataType> |
语法定义和例子
下表展示了语法定义:
| 语言 | ~ |
|---|---|
| Python | 在Python中没有数组。等价的数据结构称为列表 (list),列表是一组有序的元素序列,它们的数据类型不必相同。 |
| VB.NET | Dim <arrayIdentifier>(<upperBound>) As <dataType> |
| Java | <datatype>[] <arrayIdentifier>; <arrayIdentifier> = new int[<upperBound>+1]; |
举出一些例子:
伪代码
1 | DECLARE List1 : ARRAY[1:3] OF STRING // 3 elements in this list |
Python
1 | List1 = [] |
List1:由于没有数据类型声明和列表声明,生成列表的唯一方法是初始化一个列表。
然后可以向现有列表中添加元素。
List2:可以将元素包含在[]中。
List3:你也可以使用一个循环来为列表添加内容。
AList:可以提供一个初始值,乘以所需元素的数量。""填入初始值。
VB.NET
1 | Dim List1 As String () = {"","",""} |
可以像List1一样,在声明时初始化数组。
注意,List3有101个元素。
你可以使用范围作为数组的维度(如AList),但下界必须为0。
Java
1 | String[] list1 = {"","",""}; |
同样,你可以在声明时初始化数组(如list1)。
访问一维数组
在伪代码中,需要使用一个索引值 (Index value)来访问数组中的一个特定内容:
1 | <arrayIdentifier>[x] |
下面开始举例:
伪代码
1 | NList[25] = 0 // set 25th element to zero(0) |
Python
1 | NList[24] = 0 |
VB.NET
1 | NList(25) = 0 |
Java
1 | nList[25] = 0; |
在Python中,可使用print(<list>)打印列表的全部内容。
在VB.NET和Java中,你需要使用循环来打印数组中的所有元素。
创建二维数组
伪代码be like:
1 | DECLARE <identifier> : ARRAY[<lBound1>:<uBound1>,<lBound2>:<uBound2>] OF <dataType> |
语法定义和例子
下表展示了语法定义:
| 语言 | ~ |
|---|---|
| Python | 在Python中没有数组。等价的数据结构称为列表 (list)。 |
| VB.NET | Dim <arrayIdentifier>(<uBound1, uBound2>) As <dataType> |
| Java | <datatype> <arrayIdentifier>; <arrayIdentifier> = new <datatype>[uBound1][uBound2]; |
举出一些例子:
伪代码
1 | DECLARE Board : ARRAY[1:6, 1:7] OF INTEGER |
Python
1 | Board = [[0, 0, 0, 0, 0, 0, 0], |
VB.NET
1 | Dim Board(6, 7) As Integer |
元素的编号从0到给定的数字。这个声明多了一行和一列。
然而,如果忽略第0行和第0列,该算法可能更容易转换为程序代码。
Java
1 | int[][] board = { |
2维数组的初始化方式与一位数组类似。记住元素都是从0开始编号的。
访问二维数组
在伪代码中,需要使用一个索引值 (Index value)来访问数组中的一个特定内容:
1 | <arrayIdentifier>[x,y] |
下面开始举例:
伪代码
1 | Board[3,4] ← 0 // sets the element in row 3 and column 4 to zero |
Python
1 | Board[2][3] = 0 |
在Python中,元素从0开始编号,因此[3]访问的是第四个元素。
VB.NET
1 | Board(3, 4) = 0 |
我们忽略第0行和第0列:这里说的就是第三行第四列。
Java
1 | board[2][3] = 0; |
同样在Java中,元素从0开始编号,因此[3]访问的是第四个元素。
文本文件
向文本文件中写入
伪代码:
1 | OPENFILE <filename> FOR WRITE // open the file for writing |
下面的代码示例演示了如何用这三种语言分别打开、写入和关闭名为SampleFile.txt的文件。
如果文件已经存在,只要open file命令分配了文件句柄,它就会被覆盖。
Python
1 | FileHandle = open("SampleFile.TXT", "w") |
调用open函数时要指定文件名和模式(‘w’表示写入)。
要写入到文件中的文本行必须包含换行符\n,以便移动到文本文件的下一行。
VB.NET
1 | Dim FileHandle As IO.StreamWriter |
可以通过一个名为StreamWriter的对象访问该文件。
Java
1 | import java.io.FileWriter; |
输入输出操作会抛出异常。
管理它们的最简单方法是将你的主标题更改为: public static void main(String[] args); throws IOException
从文本文件中读取
伪代码:
1 | OPENFILE <filename> FOR READ // open the file for writing |
继续用SampleFile.txt举例:
Python
1 | FileHandle = open("SampleFile.TXT", "r") |
调用open函数时要指定文件名和模式(‘r’表示读取)。
VB.NET
1 | Dim FileHandle As IO.StreamWriter |
同样,通过一个名为StreamWriter的对象访问该文件。
Java
1 | import java.io.IOException; |
还有其他库类可用于输入/输出,例如Scanner。
追加到文本文件
伪代码:
1 | OPENFILE <filename> FOR APPEND // open the file for append |
继续用SampleFile.txt举例:
Python
1 | FileHandle = open("SampleFile.TXT", "a") |
调用open函数时要指定文件名和模式(‘a’表示附加)。
VB.NET
1 | Dim FileHandle As IO.StreamWriter |
同样,通过一个名为StreamWriter的对象访问该文件。
额外的参数True告诉系统我们需要将元素添加到对象中。
Java
1 | import java.io.FileReader; |
输入输出操作会抛出异常。
最简单的方法是将你的主标题改为: public static void main(String[] args) throws IOException
文件结束标记 (EOF)
EOF,为End Of File的缩写,通常在文本的最后存在此字符表示资料结束。
伪代码:
1 | OPENFILE "Test.txt" FOR READ |
下面的代码示例演示了如何用这三种语言分别读取和输出文件的内容。三段语言都需要当碰到EOF后终止读取:
Python
1 | FileHandle = open("Test.txt", "r") |
在Python中没有显式的EOF函数。
但是,当读取的文本行只包含文件结束标记时,该文本行的长度为0。可以运用这点达成同样的效果。
VB.NET
1 | Dim LineOfText As String |
当检测到文件结束标记时,EndOfStream就会返回True,循环就会结束。
Java
1 | import java.io.IOException; |
在Java里面也没有专门用于EOF函数。
但是,当读取的文本行只包含文件结束标记时,该文本行实际上是空的。我们可以运用这点达成同样的效果。
第十五章:软件开发
程序开发周期
开发软件需要经历很多不同的阶段。
首先我们可以使用结构化英语,伪代码或者流程图来帮助我们理清程序的结构,然后再使用实际的语言编写。
当需要大型软件系统来解决大问题时,这些阶段就会变得更加正式,特别是当更多的人参与开发时。
在设计解决方案之前,需要首先对问题进行分析。
当程序正常工作并被使用时,可能会出现需要修改的问题,这就是所谓的维护 (Maintenance)。
下面来介绍程序开发周期中的每一步:
分析 (Analysis)
解决问题的第一步是调查问题和当前的系统(如果存在的话)。
这个问题需要明确而精确地定义,然后再起草一份“需求说明书”。
下一步就是思考解决方案。一个问题可能会有很多不同的解决方案。再分析这一步,我们有必要去思考这些解决方案中,哪一个是最合适,最有效的。
第三步就是决定如何解决问题:
- Bottom-up:从一个小问题开始,然后在它的接触上一直向上构建新的内容。
- Top-down:使用伪代码,流程图或者结构图逐步细化你的代码。
设计 (Design)
到这一步你的心中应该已经有了一个确切的解决方案了。但是我们如何细致的设计解决方案?
我们可以使用一个标识表 (Identifier table),把我们需要考虑的数据全部写进表里。这有助于我们去考虑所有的数据以及它们的结构。比如说,我们到底是需要一个一维数组或者二维数组处理数据?我们是不是需要创立一个文件夹来专门存放长期数据?
随后使用伪代码或者流程图来写出你的程序。
这些都是设计这一步的任务。
编程 (Coding)
设计解决方案后,可能需要选择合适的高级编程语言。
如果你会一种以上的编程语言,你必须权衡每一种语言的利弊。
上一章提到了各种语言 (实际上只有三种语言) 的强项与弱项。
在这一步,我们会将伪代码转化成真真切切的代码。
当你开始编写程序时,你可能会发现程序在编译之前需要尝试好几次。当它最终完成时,我们就可以执行它。
有些时候程序可能会炸,在这种情况下,我们需要调试代码。
但是当我们的程序已经成功运行没有问题的时候,我们还需要考虑程序是否做了它应该做的事情。
测试 (Testing)
只有彻底的测试程序才能确保程序在所有情况下都能正常工作。
程序开发生命周期
有几种不同的开发方法。这包括瀑布式 (Waterfall)、迭代式 (Iterative)和快速应用程序开发模型 (Rapid application development model)。
程序开发生命周期遵循分析、设计、编码(实现)、测试和维护的定义阶段。
当维护时需要对程序做出进一步调整时,开发就会重新开始,从而形成一个循环。如下图所示:
瀑布模型
下图展示了瀑布式开发周期的示意图:
图中向下的箭头表示一个阶段的结果被输入到下一个阶段。
返回到早期阶段的箭头反映了这样一个事实:在早期的开发阶段需要完成当前阶段更多的工作。
瀑布模型的好处有:
- 简单易懂,因为模型的每一个阶段都定义的十分清楚。
- 由于模型中阶段的固定性,整个周期易于管理,而且每一个阶段都有特定的结果和成果。
- 每一个阶段都需要被处理并完成。
- 瀑布模型适用于需求被充分理解的小型项目。
瀑布模型的坏处有:
- 再整个开发周期的后期才能出现一个完全可用的软件。
- 对于复杂并面向对象的项目来说,这个开发模式不是特别的适合。
- 对于需要长期进行的项目来说,这个开发模式也不是很适合。
- 没法适应不断变化的需求。
- 很难衡量阶段性的发展。
- 集成部分是在最后完成的,也就是说,如果有潜在的问题或者漏洞是很难发现的。
迭代模型
迭代生命周期模型并不试图从完整的需求规范开始。相反,开发从实现程序需求的一个小子集开始。
重复的(迭代的)评审以确定进一步的需求,最终形成完整的系统。
好处如下:
- 在开发的早期阶段有一个早期Demo这就允许团队更容易找到功能或者设计缺陷。在开发的早期阶段发现问题意味着可以更快地采取纠正措施。
- 有些功能可以在周期的早期快速开发。
- 我们在早期可以周期性的获得结果。
- 我们甚至可以规划并行发展。
- 易于衡量进步和进展。
- 变更项目范围或者需求的成本更低。
- 测试和调试较小的程序子集十分的容易。
- 在迭代过程中可以很轻易地识别并解决风险。
- 更容易管理风险,因为较高风险的风险会被优先考虑。
- 每一次增量更新都可以向客户交付产品。
- 在每个增量更新中确定的问题,挑战和风险都可以被应用到下一个增量更新中。
- 更适合大型和关键任务项目。
- 在这个生命周期中,软件会被尽早地生产出来。这有助于团队从客户那里听到有关产品的评估和反馈。
当然也有坏处:
- 只有大型软件开发项目才会从这个生命周期中收益。因为很难再将小型软件系统继续拆拆拆成更小的部分了。
- 可能会需要很多的资源,包括人力物力。
- 可能会出现设计问题,因为并非所有需求都在整个生命周期的开始时收集。
- 定义增量的时候可能需要定义整个系统。
快速应用程序开发模型
RAD是一种使用最小计划的软件开发方法。相反,它规划原型来解决问题。
原型 (Prototype)是解决方案的一部分的工作模型。
在快速应用开发模型中,模块作为原型并行开发,并集成以形成完整的产品,从而更快地交付产品。没有详细的预先规划,并且随时可以在开发过程中进行更改。
特点就是分析、设计、编码和测试阶段被合并到一系列短的迭代开发周期中。
优点:
- 可以适应不断变化的需求。
- 易于衡量进步。
- 在短时间内,人越少,生产力越高。
- 开发时间可以大幅减少。
- 组建的可复用性大大增加。
- 适用于基于组件和可扩展的程序。
- 可以进行快速的审查。
- 该模型鼓励用户去积极反馈问题。
- 在集成所有模块之间就解决了许多集成中可能出现的问题。
缺点:
- 只有模块化的程序才能够使用RAD构建。
- 需要高水平的开发人员和设计师。
- 需要客户在开发的过程中全程参与。
- 仅适合开发时间较短的项目。
使用结构图设计程序
另一种模块化设计方法是选择子任务,然后构建一个结构图 (Structure chart)来显示模块之间的相互关系。
结构图中的每个框代表一个模块,其中的每一层都是上一层的细化。
结构图还显示了模块之间的接口,变量。这些变量被称为参数 (Parameters)。
向下层模块传参显示为向下指向的箭头。
向上层模块传参显示为向上指向的箭头。
下图显示了计算两个数字平均值的模块的结构图。
顶层的方框是模块的名称,它被细化成了下一级的三个子任务。INPUT numbers(参数Number1和Number2)被传递到Calculate average子任务中,然后Average参数被传递到OUTPUT average子任务中。
箭头显示了参数如何在模块之间传递。传参的层级被称为”interface”。
结构图还可以显示控制信息,比如选择和重复。
在第十二章我们举过一个有关于猜数字的例子,这里我们把它模块化先:
其中的菱形表示一个条件,要么为真,要么为假。
下图显示了绘制金字塔程序的结构图。
最上面的半圆形箭头表示箭头下方模块的重复,标签显示重复发生时的情况。
结构图帮助程序员可视化模块如何相互关联以及它们如何相互连接。当考虑一个更大的问题时,这变得更加重要。
下面给出了名为”Connect 4”游戏的程序的结构图。
在图片中我们能看见传参过程中有不同的箭头。
- 实心圆箭头表示传递的值是一个布尔值。
- 双头箭头表示变量值在模块内更新。
从结构图中写出伪代码
让我们再来将目光聚集到上面的金字塔问题。
在原来的例子中,创建模块时没有使用结构图,所有变量都是全局变量。
现在我们将使用局部变量和参数。
使用局部变量和参数的原因是因为模块是自包含的,对变量的任何更改不会对其他地方的变量值产生意外的影响。
顶层模块Pyramid调用了4个模块。
当一个模块被调用时,我们在模块标识符后面的括号中提供参数。伪代码如下:
1 | MODULE Pyramid |
状态转换图与程序设计
我们的计算机系统可以看作是一个有限状态机(Finite State Machine, FSM)。
FSM有一个叫做start的状态。输入进FSM的指令会导致一种状态到另一种状态的转换。
FSM的状态信息可以用状态转换表 (State-transition table)来表示。
下表展示了一个展示FSM状态的状态转换表:
- 如果状态为S1,则a的输入不会导致状态改变。
- 如果状态为S1,则b的一个输入将S1转换为S2。
- 如果状态为S2,则b的输入不会改变状态。
- 如果处于S2状态,则a的输入将S2转换为Sl。
| input | input name | current state | current state |
|---|---|---|---|
| S1 | S2 | ||
| input | a | S1 |
S1 |
| input | b | S2 |
S2 |
状态转移图 (State-transition graph)可以用来描述有限状态机的行为。
下图开始状态为S1。开始状态会用一个实心圆球的箭头表示。
如果有限状态机有一个最终状态(也称为停机状态 (Halting state)),则用一个双圆圈状态来表示。
如果输入产生输出,则用竖线表示。
例如,如果当前状态为S1,b的输入产生了一个输出c,并将FSM转换为S2状态。这时候就会使用竖线隔开,表示输入输出。
FSM还有一个别称:”Mealy Machine”。
错误的类型
为什么会发生错误 & 我们如何找到它们
软件可能会因为下面的这些因素而没有按照预期的想法工作:
- 程序员在编程序的时候出现了错误。
- 没有科学的在规划阶段指定需求。
- 软件设计师犯了一个设计错误。
- UI设计的贼差,所以说用户可能会在使用时使程序出现问题。
- 计算机硬件故障。
如何发现错误?
最终用户可能会报告一个错误,这无疑是不利于软件开发人员的声誉的。所以说,我们需要尽可能在软件发布之前进行测试,并修复尽可能多的漏洞。
研究表明,错误发现得越早,修复它的成本就越低。
软件在整个开发过程中都进行测试是非常重要的。
测试的目的是发现错误。著名的荷兰计算机科学家Edsger Dijkstra说:“程序测试可以用来显示bug的存在,但永远不能显示它们的不存在”。 (每日名言)
查找语法错误 (Syntax errors)很容易。编译器/解释器会为你找到它们,并且通常会给你一个提示,告诉你哪里出了问题。
根据开发环境编辑器的不同,编辑器可能会标记出一些语法错误,因此您可以在开发过程中纠正这些错误。
语法错误是一种“语法 (grammatical)”错误,指的是程序语句没有遵循高级语言结构的规则。
有些语法错误可能只有在使用解释器或编译器翻译程序时才会变得明显。
解释器和编译器的工作方式不同。一旦程序成功编译后,你就知道不会再有语法错误了。
但是对于解释型程序,情况并非如此:只有即将执行的语句才会进行语法检查。
因此,如果你的程序没有经过彻底的测试,它甚至可能还有语法错误。
更难以发现的是逻辑错误 (Logic errors)和运行时错误 (Runtime errors)。
当程序执行意外停止或“崩溃”或进入无限循环并“冻结”时,发生的就是运行时错误。
这两种类型的错误都只能通过仔细的测试才能找到。
这种错误的危险在于,它们可能只会在某些情况下出现。
如果一个程序每次执行时都崩溃,那么很明显有错误。
如果程序被频繁地使用,并且看起来一直在工作,直到某组数据导致了故障,那么在不造成严重后果的情况下很难发现故障。
测试程序的方法
存根测试
存根测试 (Stub testing)
在开发用户界面时,您可能希望在实现所有功能之前对其进行测试。
你可以为每个过程编写一个”存根 (Stub)”。
存根(stub)和模拟(mocking)一样,意味着创建一个替身,但存根只模拟行为,而不是整个对象。
当你的实现只与对象的特定行为交互时,可以使用此方法。
比如说你想要测试你的主程序,但是你的每一个模块还没有完成,就可以使用Stub testing,通过定义每一个模块应输出的内容,来做到测试主程序的目的。
每一个分叉只包含一条output语句,以确认进行了调用。
用户在主程序中选择的每个选项都将调用相关的过程。
黑盒测试
作为程序员,你可以看到你的程序代码,你的测试将涉及代码的知识(参见白盒测试)。作为全面测试的一部分,程序还应该由其他人进行测试,他们看不到程序代码,也不知道解决方案是如何编码的。
这样的程序测试人员将查看程序规范,以了解程序要做什么,设计测试数据并计算出预期的结果。
测试数据 (Test data)通常由正常数据值、极端/边界数据值和错误/异常数据值组成。
测试人员然后用测试数据运行程序并记录结果。
这种测试方法被称为黑盒测试,因为测试人员看不到程序代码的内部,程序对他们来说就像一个黑盒。
当实际结果与预期结果不匹配时,就存在问题。
在修改程序之前,程序员需要找到这种差异的原因。
一旦黑盒测试确定存在错误,就必须使用调试软件或干式运行来找到需要更正的代码行。
白盒测试
我们如何检查代码是否正确工作?
我们选择合适的测试数据来检查代码中的每一条路径。这被称为白盒测试 (White-box testing)。
干式运行算法
检查算法是否按预期工作的一种好方法是使用跟踪表和不同的测试数据来运行算法。
这也被称为walk through。
其思想是在算法的每一步写下所有变量和条件值的当前内容。
测试阶段
这些测试方法在软件开发的早期使用,例如在编写单个模块时。
有时程序员自己也会使用这些测试方法。
在较大的软件开发组织中,一般来说会有全职的软件测试人员。
软件通常由许多模块组成,有时由不同的程序员编写。
每个单独的模块可能已经通过了所有测试,但当模块合并成一个程序时,测试整个程序至关重要。这就是所谓的集成测试 (Integration testing)。
集成测试通常是增量式的。这意味着每次添加一个模块就会完成一次测试,并在添加下一个模块之前进行进一步的测试。
软件在发布给客户之前,将由软件测试人员进行内部测试。这种类型的测试称为Alpha测试 (Alpha testing)。
定制软件(为特定客户编写的)将随后发布给客户。客户将检查它是否符合他们的要求并按预期工作。这个阶段称为验收测试 (Acceptance testing)。
这通常是交接过程的一部分。在成功的验收测试之后,客户将签署软件。
当软件不是为销售而生产时,没有特定的客户来执行验收测试和签署软件。所以,在alpha测试之后,一个版本将发布给有限的潜在用户受众,即所谓的“beta测试者”。
这些测试人员将使用软件并在他们自己的环境中进行测试。这个早期的发布版本被称为beta版本,被选中的用户执行Beta测试 (Beta testing)。
在beta测试期间,用户将向软件库反馈他们发现的任何问题,以便软件库可以纠正任何报告的错误。
测试策略,测试计划和测试数据
在软件项目的设计阶段,我们需要制定合适的测试策略,以确保从一开始就对软件进行严格的测试。
我们应考虑哪些测试方法适用于所述项目,因为必须制定一个精心设计的测试计划来确保最终程序的质量。
一些时候,大型程序不能进行详尽的测试,但重要的是系统测试可以发现尽可能多的错误,因此我们需要一个测试计划。
在第一个例子中,我们设计了一个大纲规划,如下:
- 控制流:用户是否已经得到了适当的选择?所选的选项是否导致特定模块正常工作?
- 输入验证:所有的数据是否已经正确地输入进系统?
- 循环和决策:循环和决策是否正确?
- 存储:数据是否保存在正确的文件当中?
- 输出验证:程序是否能够产生正确的输出?
列出这份大纲之后,我们还要逐步细化,直到做成一个详细的测试计划。
我们如何进行这些测试?
首先我们需要选择能够让我们看到它是否被正确处理的数据,这种类型的数据称为“测试数据 (Test data)”。
它与真实的、实时的数据不同,因为它是为了测试不同的可能性而特意选择的。
我们区分不同类型的测试数据,如下表所示:
| 测试数据类型 | 解释 |
|---|---|
| Normal (valid) | 正常的,有效的,合理的数据。 |
| Abnormal (erroneous) | 程序不应该接受的数据值。 |
| Boundary (extreme) | 处于正常数据范围的边界或者极端的数据值 测试数据应该包括恰好在边界内的值(即有效数据)和恰好在边界外的值(即无效数据)。 |
如何预防错误
编写能正确工作的程序的最好方法,就是从一开始就防止错误。
我们如何将程序中的错误最小化? 产生错误的一个主要原因是贫乏的需求分析。
在设计解决方案时,理解问题以及系统的用户想要或需要什么是非常重要的。
我们应该使用如下方案来达成这一目的:
- 使用久经沙场的,主流的语言和语言结构,如结构化变成或者面向语言的设计。
- 使用业内约定俗成的规定,如标识符表,数据结构,或者使用标准的算法。
- 使用程序库 (Program libraries)中经过验证的模块和对象。
纠正性维护
维护程序不像维护机械设备那样:它不需要润滑,零件也不会磨损。
纠正性维护 (Corrective maintenance)指的是当程序由于逻辑错误或运行时错误而不能正确工作时所需要的工作。
有时,程序错误在很长一段时间内都不会变得明显,因为只有在非常罕见的情况下才会出现意外结果或程序崩溃。
这些情况可能是因为程序的某些部分不经常使用,或者因为某些情况下的数据包含极端值。过于早期的纠正性维护也可能引入其他错误。
在报告问题时,程序员需要找出导致bug的原因。
为了找到bug,程序员要么使用程序调试软件,要么使用跟踪表。
适应性维护
有时程序经常需要修改,以使其执行原本执行不了的功能。
例如,第十三章介绍的Connect 4游戏允许O和X两个玩家对战。
修改后的版本将是一个玩家成为电脑。这意味着单个玩家与电脑下棋,尝试战胜计算机。
适应性维护 (Adaptive maintenance)是对程序进行修改以增强功能或响应规格变化的行为。
改善性维护
如果你的程序运行得令人满意,但是你发现仍有改进的空间。
例如,如果文件处理由顺序访问改为直接访问,程序可能运行得更快。
改善型维护 (Perfective maintenance)的目标是修改程序以提高性能或可维护性。
AS部分完结撒花
(花)(花)(花)
最后更新于:2023.4.28