1.1.3 知识点精讲

1.1.3.1 数制及其转换

数制是用一组固定的符号和统一的规则来表示数值的方法。在采用进位计数的数字系统中，如果只用r个基本符号表示数值，则称其为r进制，r称为该数制的基数。常用进位计数制如表1-2所示。

以十进制2021.25为例，其表示形式为：

●十进制表示为(2021.25)₁₀或2021.25D。

●二进制表示为(11111100101.01)₂或11111100101.01B。

●八进制表示为(3745.2)₈或3745.2O。

●十六进制表示为(7E5.4)₁₆或7E5.4H。

对于任何一种进位的数制，所表示的数都可写作按权展开的多项式，不同数据的相互转换也是依据此实现的。如：

(2021.25)₁₀=2×103+0×102+2×101+1×100+2×10-1+5×10-2

(7E5.4)₁₆=7×162+14×161+5×160+4×16-1

1.十进制→二进制

方法：整数部分和小数部分分别转换后合并。整数的转换方法是“除2取余”，小数的转换方法是“乘2取整”，如表1-3所示。

十进制转八进制或转十六进制，与二进制的转换方法类似，不同的只是基数的改变。

2.十进制→八进制

方法：整数部分和小数部分分别转换后合并。整数的转换方法是“除8取余”，小数的转换方法是“乘8取整”。

3.十进制→十六进制

方法：整数部分和小数部分分别转换后合并。整数的转换方法是“除16取余”，小数的转换方法是“乘16取整”。

4.二进制→十进制

方法：将二进制数的每一位数乘以它的权后相加。

也就是说，二进制数的整数部分从低位到高位（即以小数点为分界从右往左）计算，第0位的权值是2的0次方，第1位的权值是2的1次方，第2位的权值是2的2次方，依次递增下去；小数部分从高位到低位（即以小数点为分界从左往右）计算，第1位的权值是2的-1次方，第2位的权值是2的-2次方，第3位的权值是2的-3次方，依次递减下去；把最后的结果相加，得到的值就是十进制的值。如：

(11111100101.01)₂=1×210+1×29+1×28+1×27+1×26+1×25+0×24+0×23+1×22+0×21+1×20+0×2-1+1×2-2=(2021.25)₁₀

5.二进制→八进制

方法：取三合一法，即以二进制的小数点为分界点，向左（或向右）每三位取成一位。二进制与八进制的对应关系如表1-4所示。

如：(11111100101.01)₂=(3745.2)₈。

转换过程如下：

1.1.3.2 数据的表示

以下重点讲解数据的表示，即计算机内最常用的信息编码。这些内容是程序员必须了解的基本知识之一，要求能熟练掌握并运用自如（下面的讲解只以小数为例，整数类似）。

1.原码、反码和补码

二进制数值数据包括二进制表示的定点小数、整数和浮点数。这里讲的编码方法，主要是如何方便统一地表示正数、零和负数，并且尽可能有利于简化对它们实现算术运算用到的规则。很容易想到，数据符号的正与负，可分别用一位二进制的“0”和“1”来表示；数据的数值用多位二进制表示。最常用的编码方法有原码、反码和补码3种。为了讨论方便，通常把表示一个数值数据的机内编码称为机器数，而把它所代表的实际值称为机器数的真值。

（1）原码

原码是一种比较直观的机器数表示方法，最高位是符号位，0代表正号，1代表负号，数值部分用该数的绝对值表示。原码的定义为

原码易于真值转换，方便乘除运算，但不利于计算机中应用最多的加减运算，故计算机中一般不用原码。

原码有以下性质：

1）在原码表示中，机器数的最高位是符号位，0代表正号，1代表负号。

2）在原码表示中，零有两种表示形式，即

[+0.0]_原=00000，[-0.0]_原=10000

3）原码表示方法的优点是数的真值和它的原码表示之间的对应关系简单，相互转换容易，用原码实现乘除运算的规则简单。缺点是用原码实现加减运算很不方便，不仅要比较参与加减运算的两个数的符号，还要比较两个数值的绝对值的大小，最后还要确定运算结果的正确符号。因此，在计算机中经常用后面介绍的补码来实现加减运算。

（2）反码

当真值为正数时，反码与原码相同；当真值为负数时，反码的符号位用1表示，数值位是原码的各位取反（1变0，0变1）的结果。反码的定义为

反码有以下性质：

1）在反码表示中，机器数最高位为符号位，0代表正号，1代表负号，负数的机器数和它的真值之间的关系为

[X]_反=(2-2-n)+X

2）在反码表示中，0有两个编码，即

[+0.0]_反=00000，[-0.0]_反=11111

用反码实现算术运算十分不便，而且0值又有两个编码，因此反码用得很少。

（3）补码

在初等代数中，有理数的加减法统一为代数和，减去一个数变为加上这个数的相反数，如果能恰当地表示负数，使得加上一个正数和加上一个负数的算法一样，就简化了运算，节省了机器设备。补码就是实现上述要求的一种很好的机器数表示方法。

当真值为正数时，补码与原码相同；当真值为负数时，补码的符号位用1表示，数值位为原码数值位各位取反后在最低位加1，即负数的补码是其反码末位加1的结果。补码的定义为

补码有以下性质：

1）在补码表示中，机器数的最高一位是符号位，0代表正号，1代表负号。机器数和它的真值的关系为

[X]_补=2×符号位+X

2）在补码表示中，0有唯一的编码，即

[+0.0]_补=[-0.0]_补=00000

3）在计算机中实际进行加法运算时，补码的符号位和数值位一样参与运算，最高位（符号位）向上的进位舍去，结果正好是和的补码。例如：

X=51，Y=-61，X+Y=51+(-61)=-10

补码表示为：00110011+11000011=11110110。结果11110110正是-10的补码。

将补码的符号位和数值位同样看待，对数值按位取反后末位加1，这种操作称为求补。可以证明，对一个数值的补码求补所得到的正是这个数的相反数的补码，二次求补就恢复为原数。由于补码的这些优点，计算机中大多采用补码表示数值。

2.数值数据的表示

数值型数据是表示数量多少、数值大小的数据。在计算机中常用的方法是用二进制码表示数据，包括整数、纯小数、实数（统称为浮点数），以便于实现算术运算。为了更有效地、方便地统一表示正数、负数和零，对二进制数又可以先用原码、反码、补码等多种编码方案表示。

数值数据用于表示数值的大小，包含数值范围和数据精度。数值范围是指一种类型的数据所能表示的最大值和最小值；数据精度通常用实数所能给出的有效数字的位数表示。在计算机中，这两个概念是不同的，它们的值与用多少个二进制位表示某类数据，以及如何对这些位进行编码有关。

二进制数主要分成定点小数、整数与浮点数3类。

（1）定点小数

定点小数是指小数点准确固定在数据某个位置上的小数。从实用角度看，都把小数点固定在最高数据位的左边，小数点前面再设一位符号位。按此规则，任何一个小数都可以写成：

N=N_SN_-1N_-2…N_-m

如果在计算机中用m+1个二进制位表示上述小数，则可以用最高（最左）一个二进制位表示符号（如用0表示正号，则1表示负号），而用后面的m个二进制位表示该小数的数值。小数点不用明确表示出来，因为它总是固定在符号位与最高数值位之间，即所谓定点小数。定点小数的取值范围很小，对用m+1个二进制位的小数来说，它可表示的数值范围为：

|N|≤1-2-m

即小于1的纯小数。这对用户算题十分不方便，因为在算题之前，必须把要用的数通过合适的“比例因子”换算成绝对值小于1的小数，并保证运算的中间结果和最终结果的绝对值也都小于1。在输出真正结果时，还要把计算的结果按相应比例加以扩大。

定点小数表示法主要用在早期的计算机中，它最节省硬件。随着计算机硬件成本的大幅度降低，现代的通用计算机都设计成能处理与计算多种类型数值（不仅仅限于定点小数）的计算机。

（2）整数

整数表示的数据的最小单位为1，可认为它是小数点固定在数值最低位右边的一种数据。整数又被分为带符号和不带符号两类。对于带符号的整数，符号位被安排在最高位，任何一个带符号的整数都可以写成：

N=N_SN_nN_n-1…N₂N₁N₀

对于用n+1位二进制位表示的带符号的二进制整数，它可表示的数值范围为：

|N|≤2n-1

对不带符号的整数来说，所有的n+1个二进制位均被视为数值，此时它可表示的数值范围为：

0≤N≤2n+1-1

即原来的符号位被解释为2n的数值。

有时也用不带符号的整数表示另一些内容，此时它不再被理解为数值的大小，而被看成一串二进制位的某种组合。

在很多计算机中往往同时使用不同位数的几种整数，如用8位、16位、32位或64位二进制来表示一个整数，它们占用的存储空间和所表示的数值范围是不同的。

（3）浮点数

浮点数是指小数点在数据中的位置可以左右浮动的数据。它通常被表示成：

N=M×RE

这里的M被称为浮点数的尾数，R被称为阶码的基数，E被称为阶的阶码。计算机中一般规定R为2、8或16，是一个确定的常数，不需要在浮点数中明确表示出来。因此，要表示浮点数，一是要给出尾数M的值，通常用定点小数形式表示，它决定了浮点数的表示精度，即可以给出的有效数字的位数。二是要给出阶码，通常用整数形式表示，它指出的是小数点在数据中的位置，决定了浮点数的表示范围。浮点数也要有符号位。在计算机中，浮点数通常被表示成如下格式：

●M_s是尾数的符号位，即浮点数的符号位，安排在最高一位。

●E是阶码，紧跟在符号位之后，占用m位，含阶码的一位符号。

●M是尾数，在低位部分，占用n位。

合理地选择m和n的值是十分重要的，以便在总长度为1+m+n个二进制表示的浮点数中，既保证有足够大的数值范围，又保证有所要求的数值精度。

若不对浮点数的表示格式做出明确的规定，同一个浮点数的表示就不是唯一的。例如0.5也可以表示为0.05×101、50×10-2等。为了提高数据的表示精度，也为了便于浮点数之间的运算与比较，规定计算机内浮点数的尾数部分用纯小数形式给出，而且当尾数的值不为0时，其绝对值应大于或等于0.5，这被称为浮点数的规格化表示。对不符合这一规定的浮点数，要通过修改阶码并同时左移或右移尾数的办法使其变成满足这一要求的表示形式，这种操作被称为规格化处理，浮点数的运算结果就经常需要进行规格化处理。

当一个浮点数的尾数为0时，不论其阶码为何值，该浮点数的值都为0。当浮点数的阶码小于它所表示范围的最小值时，不管它的尾数为何值，计算机都把该浮点数看成0值，通常把它称为机器零，此时该浮点数的所有各位（包括阶码和尾数位）都清为0值。

对短浮点数和长浮点数，当它的尾数不为0值时，其最高一位必定为1，在将这样的浮点数写入内存或磁盘时，不必给出该位，可左移1位去掉它，这种处理技术称为隐藏位技术，目的是让尾数多保存1位二进制位。在将浮点数取回执行运算时，再恢复该隐藏位的值。对于临时使用的浮点数，则不使用隐藏位技术。

浮点数比定点小数和整数使用起来更方便。例如，可以用浮点数直接表示电子的质量9×10-28克、太阳的质量2×1033克、圆周率3.1416等。上述值都无法直接用定点小数或整数表示，因为受数值范围和数值表示格式各方面的限制。

目前，计算机中主要使用3种形式的IEEE754浮点数，如表1-5所示。

在IEEE标准中，约定小数点左边隐含有一位。通常这位数就是1，因此单精度浮点数尾数的有效位数为24位，即尾数为1.××…×。

（4）十进制数的编码

十进制数的每一个数位的基数为10，但到了计算机内部，出于存储与计算方便的目的，必须采用基2码对每个十进制数位进行重编码，所需要的最少的基2码的位数为log₂10，取整数为4。用4位二进制代码表示1位十进制数符，称为二—十进制编码，简称BCD编码。因为4位二进制可以有16种组合，而十进制数只有0～9十个不同的数符，故有多种BCD编码。根据4位代码中每一位是否有确定的权来划分，BCD编码可分为有权码和无权码两类。

应用最多的有权码是8421码，即4个二进制位的权从高到低分别为8、4、2和1。无权码中用得较多的是余3码和格雷码。余3码是在8421码的基础上把每个数符的代码加上0011后构成的。格雷码的编码规则是相邻的两个代码之间只有一位不同。

常用的8421码、余3码、格雷码与十进制数符的对应关系如表1-6所示。

3.非数值数据的表示

在计算机中，除了数值数据外，还有非数值数据，例如文字、声音、图形、图像等信息。这些信息都必须经过数字化编码后才能被传送、存储和处理。

（1）逻辑数据的表示

逻辑数据是用来表示二值逻辑中的“是”与“否”或“真”与“假”两个状态的数据。例如用1表示“真”，则0表示“假”。注意：这里的1和0没有数值有无或大小的概念，只有逻辑上的意义。

（2）ASCII

ASCII（美国标准信息交换码）是计算机中使用最普遍的字符编码，该编码已被国际标准化组织（ISO）采纳，成为一种国际通用的信息交换用标准代码。

ASCII采用7个二进制位对字符进行编码；低4位组d₃d₂d₁d₀用作行编码，高3位组d₆d₅d₄用作列编码。而一个字符在计算机内实际上用8位表示，正常情况下，最高一位b₇为0，在需要奇偶校验时，这一位可用于存放奇偶校验的值，此时称这一位为校验位。

根据ASCII的构成格式，可以很方便地从对应的代码表中查出每一个字符的编码。基本的ASCII字符代码如表1-7所示。

ASCII码表是由128个字符组成的字符集。其中编码值0～31不对应任何可印刷（或称有字形）字符，通常称它们为控制字符，用于通信中的通信控制或计算机设备中的功能控制。编码值为32的是空格（或间隔）字符SP，编码值为127的是删除控制DEL码。其余94个字符称为可印刷字符，若把空格也计入可印刷字符，则有95个可印刷字符。

（3）汉字编码

汉字处理包括汉字的编码输入、汉字的存储和汉字的输出等环节。也就是在计算机中处理汉字时，必须先对汉字进行编码。

西文是拼音文字，基本符号比较少，编码比较容易，而且在一个计算机系统中，输入、内部处理、存储和输出都可以使用同一代码。汉字种类繁多，编码比拼音文字困难，而且在一个汉字处理系统中，输入、内部处理、存储和输出对汉字代码的要求不尽相同，所以采用的编码也不尽相同。汉字信息处理系统在处理汉字和词语时，关键的问题是要进行一系列的汉字代码转换。在计算机中，通常用2个字节表示1个汉字。

1.1.3.3 算术运算和逻辑运算

1.计算机中二进制数的运算方法

简单来讲，计算机中二进制运算是满2进1，相当于我们常用的十进制的满10进1。

二进制数的算术运算包括加、减、乘、除四则运算，下面分别予以介绍。

（1）二进制数的加法

根据“逢二进一”规则，二进制数加法的法则为：

0+0=0

0+1=1+0=1

1+1=0（进位为1）

1+1+1=1（进位为1）

（2）二进制数的减法

根据“借一有二”的规则，二进制数减法的法则为：

0-0=0

1-1=0

1-0=1

0-1=1（借位为1）

（3）二进制数的乘法

二进制数乘法过程可仿照十进制数乘法进行。由于二进制数只有0和1两种可能的乘数位，因此二进制数乘法更为简单。二进制数乘法的法则为：

0×0=0

0×1=1×0=0

1×1=1

（4）二进制数的除法

二进制数除法与十进制数除法很类似。可先从被除数的最高位开始，将被除数（或中间余数）与除数相比较，若被除数（或中间余数）大于除数，则用被除数（或中间余数）减去除数，商为1，并得相减之后的中间余数，否则商为0。再将被除数的下一位补充到中间余数的末位，重复以上过程，就可得到所要求的各位商数和最终的余数。例如：

100110÷110的过程如下：

所以，100110÷110=110余10。

2.逻辑代数的基本运算

逻辑代数有与（逻辑乘，符号·）、或（逻辑加，符号+）、非（求反，符号-）三种基本逻辑运算，是按一定的逻辑关系进行运算的代数，也是分析和设计数字电路的数学工具。逻辑代数只有0和1两种逻辑值，有与、或、非三种基本逻辑运算，还有与或、与非、与或非、异或几种导出逻辑运算。

“与”逻辑运算：当且仅当X、Y均为1时，其逻辑乘X·Y才为1，否则为0。

“或”逻辑运算：只要X、Y任一（或者同时）为1，逻辑加X+Y就为1，否则为0。

“非”逻辑运算：当X为1时，X即为0；当X为0时，X即为1。

逻辑运算的基本依据是以下基本公式：

1.1.3.4 数学应用

1.常用数值计算

（1）矩阵

在数学中，矩阵是一个按照长方形阵列排列的复数或实数集合，最早来自方程组的系数及常数所构成的方阵，由英国数学家凯利首先提出。

矩阵是高等代数中的常见工具，也常见于统计分析等应用数学学科中。计算机科学中，三维动画制作常用到矩阵。

（2）近似求解

近似求解是以近似数为计算对象的数学计算方法。近似地表示某一个量的真正值（准确数）的数，称为近似数，近似数与其真正值的差别称为“误差”。近似数的截取方法有去尾法（舍弃要求的第几位后面的所有数字）、收尾法（对要求写出n位的数从第n+1位起舍去，在第n位上加上一单位）和四舍五入法。近似数的精确度通常用“绝对误差”和“相对误差”及相应的误差“界”来描述，通常用“有效数字”和“可靠数字”来表述精确度。

（3）插值

插值是离散函数逼近的重要方法，利用它可以通过函数在有限个点处的取值状况，估算出函数在其他点处的近似值。如插值可用来填充图像变换时像素之间的空隙等。插值法是数据处理和编制函数表的常用工具，也是数值积分、数值微分、非线性方程求根和微分方程数值解法的重要基础，许多求解计算公式都是以插值为基础导出的。

2.排列组合、应用统计

（1）排列

一个对象被称为一个元素，从许多对象中抽取一部分，将抽出的元素排成一排，就是排列问题，具体又分为以下两类：

1）有重复的排列。在有放回选取中，同一元素可被重复选中，从n个不同元素中取出m个元素组成的排列，称为有重复的排列。由于m个元素中每个元素的选取都有n种可能，因此它的排列总数为nm。

2）选排列和全排列。从包含n个不同元素的总体中，每次取出m(m≤n)个不同元素按一定的顺序排成一列，这样的一列元素称为选排列，其排列总数为。当m=n时，排列称为全排列，其排列总数为n!。

排列数公式：=n(n-1)…(n-m+1)

阶乘：=n(n-1)…1=n!，特别地，0!=1

排列数公式和阶乘的关系：

（2）组合

从n个不同元素中每次取出m(m≤n)个不同元素并成一组，不考虑其次序，称每个组为一个组合，其组合数为。

组合数与排列数关系：

组合数计算公式：

组合数的性质：

1），特别地，=1。

2）。

3）二项式定理：

特别地，。

3.编码基础

数据校验码就是一种常用的能够发现某些错误甚至具有一定自动纠错能力的数据编码方法。它的实现原理是在合法的数据编码之间加进一些不允许出现的（非法的）编码，使合法数据编码出现某些错误，成为非法编码，这样就可以通过检查编码的合法性达到发现错误的目的。合理地设计编码规则，安排合法、不合法的编码数量，可以获得发现错误的能力，甚至达到自动纠正错误的目的。这里用到一个码距（最小码距）的概念。码距是指任意两个合法码之间至少有多少个二进制位不同。仅有一位不同，称其（最小）码距为1，例如用4位二进制表示16种状态，因为16种编码都用到了，所以此时码距为1，也就是说，任何一个编码状态的4位码中的一位或几位出错，都会成为另一个合法码，此时的编码方法无检错能力。若用4位二进制表示8种合法状态，就可以只用其中的8种编码来表示这8种合法状态，而把另8种编码作为非法编码，此时合法编码的码距为2。一般说来，合理地增大编码的码距，就可以提高发现错误的能力，但代价是表示一定数量的合法码所使用的二进制位数变多了，增加了电子线路的复杂性、数据存储和数据传送的数量。在确定与使用数据校验码的时候，通常要考虑在不过多增加硬件开销的情况下，尽可能地发现较多的错误，甚至能自动纠正某些最常出现的错误。常用的数据校验码有奇偶校验码、海明校验码、循环冗余校验码等。纠错编码是对检错编码的更进一步的发展和应用。

（1）奇偶校验码

奇偶校验是一种简单有效的校验方法。这种方法通过在编码中增加一位校验位来使编码中1的个数为奇数（奇校验）或者偶数（偶校验），从而使码距变为2。当合法编码中发生了错误，即编码中有1变成0或0变成1，则该编码中1的个数的奇偶性就发生了变化，从而可以发现错误。

目前应用的奇偶校验码有3种：水平奇偶校验码、垂直奇偶校验码和水平垂直校验码。

●水平奇偶校验码

对每一个数据的编码添加校验位，使信息位与校验位处于同一行。

●垂直奇偶校验码

把数据分成若干组，一组数据占一行，排列整齐，再加一行校验码，针对每一列采用奇校验或者偶校验。

●水平垂直校验码

在垂直校验码的基础上，给每个数据再增加一位水平校验位，便构成水平垂直校验码。例如，32位数据10100101 00110110 11001100 10101011的水平垂直奇校验码和水平垂直偶校验码如表1-8所示。

水平垂直校验码可以发现2位错误，但不能找出错误所在；而当1位出现错误时，还能找到这个错误的位置，于是可以进行纠正。

（2）海明校验码

这是由Richard Hamming于1950年提出的目前还被广泛采用的一种很有效的校验编码方法。采用这种编码方法只要增加少数几个校验位，就能检测出两位错误，亦能检验出发生错误位的位置并能自动恢复出错位的正确值，后者被称为自动纠错。它的实现原理是：在k个数据位之外加上r个校验位，从而形成一个k+r位的新码字，使新的码字的码距均匀地拉大。把数据的每一个二进制位分配在几个不同的偶校验位的组合中，当某一位出错后，就会引起相关的几个校验位的值发生变化，这不但可以发现数据位出错了，还能指出是哪一位出错了，为进一步自动纠错提供了依据。

假设为k个数据位设置r个校验位，则校验位能表示2r个状态，可用其中的一个状态指出“没有发生错误”，用其余的2r-1个状态指出有错误且错误发生在某一位（包括k个数据位和r个校验位），因此校验位的位数应满足如下关系：

2r≥k+r+1

如果想检出且自动纠正一位错误，或想同时发现两位错误（此时不能纠错），校验位的位数r和数据位的位数k应满足如下关系：

2r-1≥k+r

按上述不等式，可计算出数据位k与校验位r的对应关系，如表1-9所示。

设计海明码的关键是合理地将每个数据位分配到r个校验组中，以确保能发现码字中任何一位出错；若要实现纠错，还要求能指出是哪一位出错，对出错位求反则得到该位的正确值。例如，当数据位为3位（用D₃D₂D₁表示）时，校验位应为4位（用P₄P₃P₂P₁表示）。可通过表1-10列出的对应关系，完成把每个数据划分在形成不同校验位的偶校验值的逻辑表达式中。

在P₄，P₃，P₂，P₁列的相应行分别填1，在该4列的后3行其他位置分别填0，在第1行的每个尚空位置分别填1。若只看后3行，该列的3个位5的组合值分别为十进制的1，2，4，0，则分配D₁，D₂，D₃列的组合值分别为3，5，6，以保证后3行各竖列的编码值各不相同。

表中D₃，D₂，D₁为3位数据位，P₄，P₃，P₂，P₁为4位校验位。其中低3位中的每一个校验位P₃，P₂，P₁的值都是用3个数据位中不同的几位通过偶校验运算规则计算出来的。其对应关系是：对P_i（i的取值为1～3），总是用处于P_i取值为1的行中的用1标记出来的数据位计算其值。最高一个校验位P₄，被称为总校验位，它的值是通过对全部3个数据位和其他校验位（不含P₄本身）执行偶校验计算求得的。

形成各校验位的值的过程叫作编码，按刚说明的规则，4个校验位所用的编码公式为：

P₄=D₃⊕D₂⊕D₁⊕P₃⊕P₂⊕P₁

P₃=D₃⊕D₂

P₂=D₃⊕D₁

P₁=D₂⊕D₁

由多个数据位和多个校验位组成的码字，将作为一个数据单位处理，例如被写入内存或被传送走。之后，在执行内存读操作时或在数据接收端，可以对得到的码字通过偶校验来检查其合法性，通常称该操作过程为译码。所用的译码方程为：

S₄=P₄⊕D₃⊕D₂⊕D₁⊕P₃⊕P₂⊕P₁

S₃=P₃⊕D₃⊕D₂

S₂=P₂⊕D₃⊕D₁

S₁=P₁⊕D₂⊕D₁

译码公式和编码公式的对应关系很简单。译码方程是用一个校验码和形成这个校验码的编码公式执行异或运算，实际上是又一次执行偶校验运算。通过检查4个S的结果，可以实现检错、纠错的目的。实际情况是：译码求出来的S₄，S₃，S₂，S₁的值与表1-10中的哪一列的值相同，就说明是哪一位出错了，故又称表1-10为出错模式表。若出错的是数据位，对其求反则实现纠错；若出错的是校验位，则不必理睬。例如：

任何一位（含数据位、校验位）均不错，则4个S都应为0值。

若单独一位数据位出错，4个S中会有3个为1。如D₃错，则S₄S₃S₂S₁为1110。

若单独一位校验位出错，4个S中会有1个或2个为1。如P₁错，S₄S₃S₂S₁为1001；如P₄错，S₄S₃S₂S₁为1000。

任何两位（含数据位、校验位）同时出错，S₄一定为0，而另外3个S位一定不全为0，此时只知道是两位同时出错，但不能确定是哪两位出错，故无法纠错。如D₁，P₂出错，会使S₄S₃S₂S₁为0001。注意：S₄的作用在于区分是奇数位出错还是偶数位出错，S₄为1是奇数位错，为0是无错或偶数位错。这不仅是发现两位错所必需的，也是确保能发现并改正一位错所必需的。若不设置S₄，某种两位出错对几个S的影响与单独另一位出错可能是一样的，此时不加以区分，简单地按一位出错来自动完成纠错处理反而会帮倒忙。

1.1.3.5 常用数据结构

数据结构是指数据对象及其相互关系和构造方法，一个数据结构S可以用一个二元组表示为：S=(D,R)。其中，D是数据结构中的数据的非空有限集合，R是定义在D上的关系的非空有限集合。在数据结构中，结点及结点间的相互关系称为数据的逻辑结构，数据在计算机中的存储形式称为数据的存储结构。

数据结构按逻辑结构的不同分为线性结构和非线性结构两大类，其中非线性结构又可分为树形结构和图结构，而树形结构又可以分为树结构和二叉树结构。

常用的数据结构有：数组（静态数组、动态数组）、线性表、链表（单向链表、双向链表、循环链表）、队列、栈、树（二叉树、查找树）、图等。

1.数组

数组是一种常用的数据结构，是线性表的推广。在程序设计语言中将数组看作存储于一个连续存储空间中的相同数据类型的数据元素的集合。通过数组元素的下标（位置序号），可以找到存放数组元素的存储地址，从而可以访问该数组元素的值。数组元素是按顺序存储的。

数组有静态和动态两种，静态数组是在定义时就给定长度，并且在编译时就分配固定的存储空间，在整个程序运行期间其长度不会改变。动态数组是在定义和编译时没有给定大小，在程序运行时根据需要增加或减少存储空间。动态数组使用起来更灵活，但会加大设计难度和增加程序的额外开销，优点是灵活使用了有限的存储空间。

2.线性表

线性表是一种简单且常用的数据结构，是由相同类型的结点组成的有限序列。一个由n个结点a₀，a₁，…，a_n-1组成的线性表可记为(a₀,a₁,…,a_n-1)。线性表的结点个数为线性表的长度，长度为0的线性表称为空表。对于非空线性表，a₀是线性表的第一个结点，a_n-1是线性表的最后一个结点。线性表的结点构成一个序列，对序列中的两个相邻结点a_i和a_i+1，称a_i是a_i+1的前驱结点，a_i+1是a_i的后继结点。其中a₀没有前驱结点，a_n-1没有后继结点。

线性表中结点之间的关系可由结点在线性表中的位置确定，通常(a_i,a_i+1)（0≤i≤n-2）表示两个结点之间的先后关系。例如，如果两个线性表有相同的数据结点，但它们的结点在线性表中出现的顺序不同，则它们是两个不同的线性表。

3.链表

链表是一种线性表，是一种可以实现动态分配的存储结构，它不需要一组地址连续的存储单元，而是用一组任意的甚至是在存储空间中零散分布的存储单元来存放线性表的数据。链表在进行频繁插入和删除操作时，不必进行大量的元素移动，可以克服线性存储的缺点，但是，由于链表的存储位置是不确定的，因此没有了线性存储可以随机存取的优点。

4.队列

队列是一种先进先出的线性表，它只允许在表的一端插入元素，而在表的另一端删除元素。在队列中，允许插入元素的一端称为队尾，允许删除元素的一端称为队首。

5.栈

也叫堆栈，它是一种运算受限的线性表，限定仅在表尾进行插入和删除操作。一端被称为栈顶，相对地把另一端称为栈底。向一个栈插入新元素称作进栈、入栈或压栈，是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素被称为出栈或退栈，是把栈顶元素删除掉，使它的下一个元素成为新的栈顶元素。

6.树

树是由一个或多个结点组成的有限集合T，它满足以下两个条件：

1）有一个特定的结点，称为根结点。

2）其余的结点分成m(m≥0)个互不相交的有限集合。其中每个集合又都是一棵树，称T₁，T₂，…，T_m-1为根结点的子树。

很明显地可以看出树定义是递归的，它表明了树本身的固有特征，也就是说，一棵树由若干棵子树构成，而子树又由更小的子树构成。

7.图

图是程序员考试中最复杂的一种数据结构，在最近几年当中很少出现。它比树更复杂，在线性结构中，除首结点没有前驱、末结点没有后继之外，一个结点只有唯一的一个直接前驱和唯一的一个直接后继。而图结构中，任意两个结点之间都可能有直接的关系，所以图中一个结点的前驱结点和后继结点的个数是没有限制的。

图G是由两个集合V和E构成的二元组，记作G=(V,E)，其中V是图中顶点的非空有限集合，E是图中边的有限集合。图可以分为有向图和无向图。

1.1.3.6 常用算法

算法是为解决某个问题而设计的步骤和方法。有了算法，就可以据此编写程序，在计算机上调试运行，最后得到问题的答案。当然这不是一朝一夕就能实现的，需要刻苦地学习和不断地提升。这里先做个简单介绍，后续章节会进一步详细介绍。

1.算法与数据结构的关系

算法是特定问题求解步骤的描述，是在计算机中表现为指令的有限序列。它是独立于语言而存在的一种解决问题的方法和思想。

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成，分为逻辑数据结构和存储数据结构两种。

数据结构是算法实现的基础，算法总是要依赖于某种数据结构来实现。两者的区别在于，算法更加抽象，侧重于对问题的建模，而数据结构则是具体实现方面的问题，两者是相辅相成的。也可以理解为数据结构是数据间的有机关系，算法是对数据的操作步骤。

2.算法设计和算法描述

算法可以采用多种语言来描述，例如，自然语言、计算机语言或某些伪语言。许多教材中采用的是以一种计算机语言为基础，适当添加某些功能或放宽某些限制而得到一种类语言。这些类语言既具有计算机语言的严谨性，又具有灵活性，同时也容易上机实现，因而被广泛接受。目前，许多数据结构的教材采用类Pascal语言、类C++或类C语言作为算法描述语言。

3.常用的排序算法

所谓排序，就是使一串记录按照其中的某个或某些关键码（key，即键）的大小，递增或递减地排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域都得到重视，尤其是在大量数据的处理方面。

一般来说，排序有升序排列和降序排列两种。在算法中，基本排序有：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、基数排序、堆排序、计数排序、桶排序。

4.查找方法

用关键码标识一个数据元素，查找时根据给定的某个关键码（即特定值），在表中确定这个关键码等于找到的给定值的记录或数据元素。在计算机中进行查找的方法是根据表中的记录的组织结构确定的。常见的查找方法有：顺序查找（也称为线性查找）、二分查找、分块查找、哈希表查找等。

5.常用的数值计算方法

数值计算方法是微分方程、常微分方程、线性方程组的求解，是一种研究并解决数学问题的数值近似解方法，是在计算机上使用的解数学问题的方法，简称计算方法。常用的数值计算方法是迭代法。

迭代法是用来求解数值计算问题中的非线性方程或方程组的一种算法（即设计方法），它包括简单迭代法、对分法、牛顿法等。它的主要思路是：从某个点出发，通过某种方法求出下一个点，这个求出来的点应该离所要求的解的点更近一步，当两者之间的差近到可以接受的精度范围时，就认为找到了问题的解。

6.字符串处理算法

字符串是一种特殊的线性表，在处理非数值数据时有着广泛的用途，成为数据处理领域中最重要的数据类型之一。字符串的基本操作包括求字符串长度、字符串比较、字符串连接、求子串、串插入、串删除等。

7.递归算法

在调用一个函数的过程中又出现直接或间接地调用该函数本身，则该调用称为函数的递归调用。

对于初学者而言，递归是一个非常难理解的知识点，需要考生多下功夫，建议多画图理解其调用规律。采用递归方法来解决问题，必须符合以下三个条件：①可以把要解决的问题转化为一个新问题，而这个新问题的解决方法仍与原来的解决方法相同，只是所处理的对象有规律地递增或递减；②可以应用这个转化过程使问题得到解决；③必须有一个明确的结束递归的条件。

8.最小生成树、拓扑排序和单源点最短路径求解算法

（1）最小生成树

在图论的数学领域中，如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树。生成树是连通图的包含图中所有顶点的极小连通子图。从不同的顶点出发进行遍历，可以得到不同的生成树。常用的生成树算法有DFS生成树、BFS生成树、PRIM最小生成树和Kruskal最小生成树。

（2）拓扑排序

对一个有向无环图（简称DAG）G进行拓扑排序，是将G中的所有顶点排成一个线性序列，使得对于图中任意一对顶点u和v，若边＜u,v＞∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序的序列，简称拓扑序列。简单地说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称为拓扑排序。

（3）单源点最短路径

给定一个带权有向图G=(V,E)，其中每条边的权是一个实数。另外，给定V中的一个顶点，称为源。计算从源到其他所有各顶点的最短路径长度，这里的长度就是指路径上各边的权之和，这个问题通常称为单源最短路径问题。