第2章 计算机的基础知识 计算机的运算基础 命题逻辑与逻辑代数基础 计算机的基本结构与工作原理 程序设计基础

第2章 计算机的基础知识 算法基础 数据结构基础 小结 习题

基本要求 掌握数制间的转换方法以及数据在计算机内部的表示形式 理解逻辑代数、计算机的工作原理、程序设计以及算法与数据结构的基本知识，为学习本书的以下各章和后续课程打好基础

十进制 数制 十进制 位权表示法数制的特点： 数字的总个数等于基数。 最大的数字比基数小1。 按进位的原则进行计数称为进位计数制，简称数制 十进制 使用数字1、2、… 、9、0等符号来表示数值且采用“逢十进一”的进位计数制。 位权表示法数制的特点： 数字的总个数等于基数。 最大的数字比基数小1。 每个数字都要乘以基数的幂次，该幂次由每个数字所在的位置决定。

十进制 任何一个N进制数A可表示为： A＝An An－1 … A1 A0.A－1 A－2 … A－m -m ＝ ∑ Ai×Ni i=n

二进制：使用数字0和1等符号来表示数值且采用“逢二进一”的进位计数制。 二进制数制的特点： 仅使用0和1两个数字。 最大的数字为1，最小的数字为0。 每个数字都要乘以基数2的幂次，该幂次由每个数字所在的位置决定。

二进制 例如：

二进制加法和乘法运算规则： 〖 例2-1〗计算二进制数1011×101的值。 0＋0＝0 0＋1＝1 1＋0＝1 1＋1＝1 0×0＝0 0×1＝0 1×0＝0 1×1＝1 〖 例2-1〗计算二进制数1011×101的值。

八进制：使用数字0、1、2、3、4、5、6、7等符号来表示数值的，且采用“逢八进一”的进位计数制 八进制与十六进制 八进制：使用数字0、1、2、3、4、5、6、7等符号来表示数值的，且采用“逢八进一”的进位计数制 十六进制：使用数字0、1、2、3、4、5、6、7、8、9和A、B、C、D、E、F等符号来表示数值，其中A、B、C、D、E、F分别表示数字10、11、12、13、14、15，十六进制的计数方法为“逢十六进一”

十进制整数转换 为非十进制整数 除基取余法： “除基取余，先余为低（位），后余为高（位）”。 〖 例2-2 〗将十进制整数55转换为二进制整数。

十进制整数转换为非十进制整数 〖 例2-3 〗（55）10＝（67）8 〖 例2-4 〗（55）10＝（37）16

乘基取整法: 〖例2-5 〗（ 0.625）10＝（0.101）2 〖例2-6 〗（0.32）10 ＝（0.0101…）2 十进制小数转换为非十进制小数 乘基取整法: “乘基取整，先整为高(位),后整为低(位)” 〖例2-5 〗（ 0.625）10＝（0.101）2 〖例2-6 〗（0.32）10 ＝（0.0101…）2 十进制小数并不是都能够用有限位的其他进制数精确地表示,这时应根据精度要求转换到一定的位数为止，作为其近似值。

如果一个十进制数既有整数部分，又有小数部分，则应将整数部分和小数部分分别进行转换。 十进制小数转换为非十进制小数 如果一个十进制数既有整数部分，又有小数部分，则应将整数部分和小数部分分别进行转换。 〖 例2-7 〗将十进制数55.625转换为二进制数。 由于（55）10 = （110111）2 （0.625）10 = （0.101）2 所以（55.625）10 = （110111.101）2

位权法：把各非十进制数按权展开，然后求和 非十进制数转换为十进制数 位权法：把各非十进制数按权展开，然后求和 〖例2-8〗 （10110）2 ＝1×24＋0×23＋1×22＋1×21＋0×20 ＝16＋0＋4＋2＋0 ＝（22）10

〖例2-9〗 （10101.101）2 ＝1×24＋0×23＋1×22＋0×21＋1×20 ＋1×2-1+0×2 －2＋1×2－3 非十进制数转换为十进制数 〖例2-9〗 （10101.101）2 ＝1×24＋0×23＋1×22＋0×21＋1×20 ＋1×2-1+0×2 －2＋1×2－3 ＝16＋0＋4＋0＋1＋0.5＋0＋0.125 ＝（21.625）10

〖例2-10〗（1207）8 ＝1×83＋2×82＋0×81＋7×80 ＝512＋128＋0＋7 ＝（647）10 非十进制数转换为十进制数 〖例2-10〗（1207）8 ＝1×83＋2×82＋0×81＋7×80 ＝512＋128＋0＋7 ＝（647）10 〖例2-11〗（1B2E）16 ＝1×163＋B×162＋2×161＋E×160 ＝1×4096＋11×256＋2×16＋14×1 ＝（6958）10

八进制数转换为二进制数：把每一位八进制数转换为对应的三位二进制数。 二进制与八进制之间的转换 二进制数转换为八进制数：以小数点为界，将整数部分自右向左和小数部分自左向右分别按每三位为一组（不足三位用0补足），然后将各个三位二进制数转换为对应的一位八进制数。 八进制数转换为二进制数：把每一位八进制数转换为对应的三位二进制数。

二进制与八进制之间的转换 〖例2-12〗 （10111001010.1011011） 2 ＝（010 111 001 010 .101 101 100）2 ＝（2712.554）8 〖例2-13〗 （456.174）8 ＝（100 101110.001 111 100）2 ＝（100101110.0011111）2

十六进制数转换为二进制数：把每一位十六进制数转换为对应的四位二进制数。 二进制与十六进制之间的转换 二进制数转换为十六进制数：以小数点为界，将整数部分自右向左和小数部分自左向右分别按每四位为一组，不足四位用0补足，然后将各个四位二进制数转换为对应的一位十六进制数。 十六进制数转换为二进制数：把每一位十六进制数转换为对应的四位二进制数。

〖例2-14〗 （10111001010.1011011）2 〖例2-15〗（1A9F.1BD ）16 二进制与十六进制之间的转换 ＝（0101 1100 1010.1011 0110）2 ＝（5CA.B6）16 〖例2-15〗（1A9F.1BD ）16 ＝（0001 1010 1001 1111.0001 1011 1101）2 ＝（1101010011111.000110111101）2

原码表示法：用符号位和数值表示带符号数，正数的符号位用“0”表示，负数的符号位用“1”表示，数值部分用二进制形式表示。 码 制 原码表示法：用符号位和数值表示带符号数，正数的符号位用“0”表示，负数的符号位用“1”表示，数值部分用二进制形式表示。 〖例2-16〗设X=+62,Y=-62,则 [X]原=0 111110 [Y]原=1 111110

反码表示法：正数的反码与原码相同，负数的反码为对该数的原码除符号位外各位取反。 码 制 反码表示法：正数的反码与原码相同，负数的反码为对该数的原码除符号位外各位取反。 〖例2-17〗设X=+62,Y=-62,则 [X]原=0 111110 [X]反=0 111110 [Y]原=1 111110 [Y]反=1 000001

说明:数的原码表示适合于进行乘除运算；补码用于进行加减运算。 码 制 补码表示法：正数的补码与原码相同，负数的补码为对该数的原码除符号位外各位取反，然后在最后一位加1。 〖例2-18〗设X=+62,Y=-62,则 [X]原=0 111110 [X]补=0 111110 [Y]原=1 111110 [Y]补=1 000010 说明:数的原码表示适合于进行乘除运算；补码用于进行加减运算。

定点小数格式：把小数点固定在数值部分最高位的左边。   定点数表示十进制纯小数-0.6876

数的范围：二进制的（m+1）位定点小数格式的数N，所能表示的数的范围为｜N｜≤ 1 － 2-m。 比例因子：对于绝对值大于1的数，如果直接使用定点小数格式将会产生“溢出”，需根据实际需要使用一个比例因子，将原始数据按该比例缩小，以定点小数格式表示，得出结果后再按该比例扩大得到实际的结果。

定点整数格式：把小数点固定在数值部分最低位的右边。 定点数表示十进制整数193

数的范围：二进制的（m+1）位定点整数格式的数N，所能表示的数的范围为｜N｜≤ 2m － 1。 比例因子：对于绝对值大于该范围的数，如果直接使用定点整数格式也将会产生“溢出”，需根据实际需要选择一个比例因子进行调整，使所表示的数据在规定的范围之内。 定点数的优点:简单直观,表示数的范围受到限制,缺乏灵活性,为防止”溢出”需要选择”比例因子”。

浮点数表示方法来源于数学中的指数表示形式： N=M×RC 例如： 浮点表示法 浮点数表示方法来源于数学中的指数表示形式：         N=M×RC 例如：

显然：每个浮点数包括两个组成成分，即尾数和阶码。 浮点表示法 类似地：    二进制数 显然：每个浮点数包括两个组成成分，即尾数和阶码。

尾数为小于1的小数，表示方法与定点小数相似，其长度将影响数的精度，其符号将决定数的符号。 浮点表示法 尾数为小于1的小数，表示方法与定点小数相似，其长度将影响数的精度，其符号将决定数的符号。 浮点数的阶码相当于数学中的指数，其大小将决定数的表示范围。 例：假定一个浮点数用4个字节来表示，其中尾数占3个字节，阶码占1个字节，且每一部分的第一位用于表示该部分的符号，即

浮点表示法

浮点表示法 则：浮点数的精度可达到小数点后的第7位（ 数的表示范围可达到 远远大于4字节定点整数的表示范围

浮点数的溢出：浮点数的表示范围比定点数大得多，但非无限，可能“溢出”：上溢（阶大于最大阶码）和下溢（阶小于最小阶码） 浮点表示法 规格化的浮点数： 为了提高浮点数表示的精度，通常规定其尾数的最高位必须是非零的有效位，称为浮点数的规格化形式。 浮点数的溢出：浮点数的表示范围比定点数大得多，但非无限，可能“溢出”：上溢（阶大于最大阶码）和下溢（阶小于最小阶码） 浮点计算的先驱：卡亨

BCD码：是一种二－十进制的编码，使用四位二进制数表示一位十进制数。 8421码（有权码） BCD码与ASCII码 BCD码：是一种二－十进制的编码，使用四位二进制数表示一位十进制数。 8421码（有权码） 十进制数与BCD码之间的转换：可按位（或四位二进制数组）直接进行。 〖例2-20〗将十进制数5678转换为BCD码。

BCD码与ASCII码 ASCII(American Standards Code for Information Interchange)码:是由美国信息交换标准委员会制定的、国际上使用最广泛的字符编码方案。

ASCII码的编码方案：采用7位二进制数表示一个字符，把7位二进制数分为高三位 BCD码与ASCII码 ASCII码的编码方案：采用7位二进制数表示一个字符，把7位二进制数分为高三位 b7b6b5 和低四位 b4b3b2b1 7位ASCII编码表：如表2-5所示，利用该表可以查找数字、运算符、标点符号以及控制符等字符与ASCII码之间的对应关系。

汉字输入码：由输入设备产生的汉字编码，如区位码、国标码、拼音码、新全拼、新双拼、五笔字型码、简码、表形码、自然码、智能ABC汉字输入码等。 汉字编码体系 汉字输入码：由输入设备产生的汉字编码，如区位码、国标码、拼音码、新全拼、新双拼、五笔字型码、简码、表形码、自然码、智能ABC汉字输入码等。 汉字内码：用于计算机内部存储和处理的汉字编码，通常由该汉字的国标码的两个字节（最高位置“1”）形成。

汉字字形码：确定一个汉字字形点阵的编码，用于汉字显示和打印输出。保留在存储介质中的全部汉字字形码称为字库。 汉字编码体系 汉字字形码：确定一个汉字字形点阵的编码，用于汉字显示和打印输出。保留在存储介质中的全部汉字字形码称为字库。 汉字交换码：用于在不同的汉字信息处理系统之间或与其他计算机系统之间进行信息交换。 汉字地址码：表示汉字字形信息在汉字库中的地址，用于在汉字库中查找汉字字形信息的汉字地址码等。

奇偶校验码：在表示数据的N位代码中增加一位奇偶校验位，使N＋1位中“1”的个数为奇数（奇校验）或偶数（偶校验）。 数据校验码 奇偶校验码：在表示数据的N位代码中增加一位奇偶校验位，使N＋1位中“1”的个数为奇数（奇校验）或偶数（偶校验）。 海明校验码：在有效信息代码中增加校验位，用来校验代码中“1”的个数是奇数（奇校验）还是偶数（偶校验），通过奇偶校验可以发现代码传输过程中的错误并自动校正。 应用：用于计算机各部件之间信息传输以及计算机网络的信息传输。

命题的真值:命题所具有的值“真”(true，简记为T)或“假”（false,简记为F）称为其真值。 命 题 命题：有具体意义且能判断真假的陈述句。 命题的真值:命题所具有的值“真”(true，简记为T)或“假”（false,简记为F）称为其真值。 命题标识符：表示命题的符号，该标识符称为命题常量。 原子命题：不能分解为更为简单的陈述句的命题； 复合命题：将原子命题用连接词和标点符号复合而成的命题。

连接词“与”（ ∧） “与”( ∧):两个命题A和B的“与”(又称为A和B的“合取”)是一个复合命题，记为A∧B。当且仅当A和B同时为真时A∧B为真，在其他的情况下A∧B的真值均为假。 A∧B的真值表 T F

连接词 “或”（∨） “或”（∨）：两个命题A和B的“或”（又称为A和B的“析取”）是一个复合命题，记为A∨B。当且仅当A和B同时为假时A∨B为假，在其他的情况下A∨B的真值均为真。 A∨B的真值表 A B A∨B T F

连接词“非”（┑） “非”（┑）：命题A的“非”（又称为A的“否定”）是一个复合命题，记为 ┑A。若A为真，则┑A为假；若A为假，则┑A为真。 ┑A的真值表 A ┑A T F

连接词 “异或”（⊕） “异或” （⊕）：两个命题的A和B的“异或”（又称为A和B的“不可兼或”）是一个复合命题，记为A⊕B。当且仅当A和B同时为真或者同时为假时A⊕B为假，在其他的情况下A⊕B的真值为真。 A⊕B的真值表 A B A⊕B T F

连接词“条件”（ →） “条件”（ →）：两个命题的A和B的“条件”是一个复合命题，记为 A→B的真值表 A→B,读作“如果A，则B”。 当且仅当A的真值为真，B的真值为假时，A→B为假，在其他的情况下A→B的真值均为真。 A→B的真值表 A B A →B T F

连接词 “双条件”( ) “双条件”( ):两个命题的A和B的“双条件”（又称为A当且仅当B）是一个复合命题，记为A B，读作“A当且仅当B”。 当且仅当A的真值与B的真值相同时， A B 为真，否则A B的真值均为假。 A B的真值表 A B A B T F

命题公式 命题公式： 由命题变元、连接词和括号组成的合式的式子称为命题公式。 命题公式等价：如果两个不同的命题公式P和Q，无论其命题变元取什么值它们的真值都相同，则称该两个命题公式等价，记为P＝Q。 〖例2-28〗证明 ┑（A→B）与A∧┑B是等价的。 A B ┑（A→B） A∧┑B T F

其中A、B、C等为命题变元，T表示“真”，F表示“假” 零律： A∨F＝A A∧F＝F 幺律： A∨T＝T A ∧T＝A 命题公式的等价律 其中A、B、C等为命题变元，T表示“真”，F表示“假” 零律： A∨F＝A A∧F＝F 幺律： A∨T＝T A ∧T＝A 幂等律：A∨A＝A A ∧A＝A 求补律：A∨┓A＝T A∧┓A＝F 交换律：A∨B＝B∨A A∧B＝B∧A

结合律： A∨（B∨C）＝（A∨B）∨C A∧（B∧C）＝（A∧B）∧C 分配律： A∧（B∨C）＝A∧B∨A∧C 命题公式的等价律（续） 结合律： A∨（B∨C）＝（A∨B）∨C A∧（B∧C）＝（A∧B）∧C 分配律： A∧（B∨C）＝A∧B∨A∧C A∨B∧C＝（A∨B）∧（A∨C）

吸收律： A∧B∨A∧┓B＝A （A∨B）∧（A∨┓B）＝A 狄－摩根定律： ┓（A∨B）＝┓A∧┓ ┓（A∧B）＝┓A∨┓B 命题公式的等价律（续） 吸收律： A∧B∨A∧┓B＝A （A∨B）∧（A∨┓B）＝A 狄－摩根定律： ┓（A∨B）＝┓A∧┓ ┓（A∧B）＝┓A∨┓B 双重否定律： ┓┓ A＝A

证明狄－摩根定律 〖例2-29〗证明狄－摩根定律之一：┓（A∧B）＝┓A∨┓B。 A A∧B ┓（A∧B） ┓A ┓B ┓A∨┓B T F

零律： A＋0＝A A 0＝0 幺律： A＋1＝1 A 1＝A 幂等律：A＋A＝A A A＝A 求补律：A＋Ā ＝1 A Ā ＝0 逻辑代数的等价律 零律： A＋0＝A A 0＝0 幺律： A＋1＝1 A 1＝A 幂等律：A＋A＝A A A＝A 求补律：A＋Ā ＝1 A Ā ＝0

交换律：A＋B＝B＋A A B＝B A 结合律：A＋（B＋C）＝（A＋B）＋C A（B C）＝（A B）C 逻辑代数的等价律（续） 交换律：A＋B＝B＋A A B＝B A 结合律：A＋（B＋C）＝（A＋B）＋C A（B C）＝（A B）C 分配律：A（B＋C）＝A B＋A C A＋B C＝（A＋B）（A＋C）

逻辑代数的等价律（续） 吸收律： 狄－摩根定律： 双重否定律：

〖例2-30〗试将逻辑函数F＝A＋ĀB化简。 解：F＝A＋Ā B ＝（A＋Ā ）(A＋B) （分配律） ＝1(A＋B) （求补律） 逻辑函数的化简 〖例2-30〗试将逻辑函数F＝A＋ĀB化简。 解：F＝A＋Ā B ＝（A＋Ā ）(A＋B) （分配律） ＝1(A＋B) （求补律） ＝A＋B （幺律）

计算机硬件的基本结构 辅助存储器 内存储器 运 算 器 控制 器 输入设备 输出设备 程序 原始数据 运算 结果 控制信息 数据

运算器：对二进制数进行运算的部件。它在控制器的控制下执行程序中的指令,完成各种算术运算、逻辑运算、比较运算、移位运算以及字符运算等 运 算 器 运算器：对二进制数进行运算的部件。它在控制器的控制下执行程序中的指令,完成各种算术运算、逻辑运算、比较运算、移位运算以及字符运算等

运 算 器 运算器的组成：算术逻辑部件（ALU）完成加、减、乘、除等四则运算以及与、或、非、移位等逻辑运算；寄存器用来暂存参加运算的操作数或中间结果，常用的寄存器有累加寄存器、暂存寄存器、标志寄存器和通用寄存器等。

运算器的主要技术指标：运算速度，其单位是MIPS（百万指令/秒），通常是按照一定的频度执行各类指令的统计值。 运 算 器 运算器的主要技术指标：运算速度，其单位是MIPS（百万指令/秒），通常是按照一定的频度执行各类指令的统计值。

存储单位：“位”（bit）、“字节”（byte）、“字”和“字长” 存 储 器 存储器：用来存储数据和程序的部件 存储单位：“位”（bit）、“字节”（byte）、“字”和“字长” 存储容量：存储器所包含的存储单元的总数，其单位为K （1K＝210＝1024）

内存储器：又称为主存储器，简称为内存或主存，用来存放现行程序的指令和数据。包括随机存取存储器（RAM）和只读存储器（ROM）等。 存 储 器 存储器的分类： 内存储器：又称为主存储器，简称为内存或主存，用来存放现行程序的指令和数据。包括随机存取存储器（RAM）和只读存储器（ROM）等。 外存储器：又称为辅助存储器，简称为外存或辅存，用来存放需要长期保存的信息。

控制器：是指挥计算机的各个部件按照指令的功能要求协调工作的部件。 控制器的组成： 程序计数器（PC）： 控 制 器 控制器：是指挥计算机的各个部件按照指令的功能要求协调工作的部件。 控制器的组成： 程序计数器（PC）： 用来对程序中的指令进行计数，使控制器能依次读取指令；

指令寄存器（IR）：在指令执行期间暂时保存正在执行的指令。 指令译码器（ID）：用来识别指令的功能，分析指令的操作要求 控 制 器 指令寄存器（IR）：在指令执行期间暂时保存正在执行的指令。 指令译码器（ID）：用来识别指令的功能，分析指令的操作要求 时序控制电路：用来生成时序信号，以协调在指令执行周期内各部件的工作。 微操作控制电路：用来产生各种控制操作命令。

输入/输出设备：简称为I/O设备，是外部与计算机交换信息的渠道。 输入设备：用于输入程序、数据、操作命令、图形、图像以及声音等信息。常用的输入设备有键盘、鼠标器、扫描仪、光笔、数字化仪以及语音输入装置等。

输出设备：用于显示或打印程序、运算结果、文字、图形、图像等，也可以播放声音。常用的输出设备有显示器、打印机、XY绘图仪以及声音播放装置等。 输入/输出设备 输出设备：用于显示或打印程序、运算结果、文字、图形、图像等，也可以播放声音。常用的输出设备有显示器、打印机、XY绘图仪以及声音播放装置等。

指令：能被计算机识别并执行的二进制代码，它规定了计算机能完成的某一种操作。 计算机的指令系统 指令：能被计算机识别并执行的二进制代码，它规定了计算机能完成的某一种操作。 指令系统：一台计算机能执行的所有指令的集合。

指令的格式：一条指令由操作码和地址码组成。操作码规定了该指令进行的操作种类；地址码给出了操作数、结果以及下一条指令的地址。 计算机的指令系统 指令的格式：一条指令由操作码和地址码组成。操作码规定了该指令进行的操作种类；地址码给出了操作数、结果以及下一条指令的地址。

计算机的指令系统 指令的分类： 数据传送型指令 数据处理型指令 输入输出型指令 硬件控制指令

计算机的工作原理 见教材52页 图2-6 指令的执行过程

取指令：即按照指令计数器中的地址，从内存储器中取出指令，并送往指令寄存器中。 指令的执行过程 取指令：即按照指令计数器中的地址，从内存储器中取出指令，并送往指令寄存器中。 分析指令：即对指令寄存器中存放的指令进行分析，由操作码确定执行什么操作，由地址码确定操作数的地址。

执行指令：即根据分析的结果，由控制器发出完成该操作所需要的一系列控制信息，去完成该指令所要求的操作。 指令的执行过程 执行指令：即根据分析的结果，由控制器发出完成该操作所需要的一系列控制信息，去完成该指令所要求的操作。 上述步骤完成后，指令计数器加1，为执行下一条指令做好准备。如果遇到转移指令，则将转移地址送入指令计数器。

计算机组织与系统结构 领域的一些主要技术 精简指令集技术 高速缓冲存储技术 虚拟存储技术 指令流水线技术 并行处理技术

机器语言：由计算机的指令系统组成，使用机器语言编写的程序计算机能够直接理解并执行，但编程和理解都十分的困难。 程序设计语言 机器语言：由计算机的指令系统组成，使用机器语言编写的程序计算机能够直接理解并执行，但编程和理解都十分的困难。 汇编语言：使用“助忆符”来表示指令的操作码，并使用存储单元或寄存器的名字表示地址码，以便于记忆和书写。

面向过程程序设计语言 面向对象程序设计语言 高级程序设计语言：是一种与机器的指令系统无关、表达形式更接近于被描述的问题的程序设计语言，便于程序的编写。使用高级程序设计语言编写的程序称为源程序，它必须经过程序设计语言翻译系统的处理后才能执行。 面向过程程序设计语言 面向对象程序设计语言

程序设计：是一个使用程序设计语言产生一系列的指令以告诉计算机该做什么的过程。 广义的程序设计： 需求分析 详细设计 测试 总体设计 编码 运行与维护

结构化程序设计：采用自顶向下逐步求精的设计方法和单入口单出口的控制成分（顺序、分支和循环）。 T F T F 条件 A B （a）顺序结构 （b）选择型分支结构 （c）循环结构

标识符：按意命名、保留字用大写字母、使用统一的缩写规则。 良好的程序设计风格 标识符：按意命名、保留字用大写字母、使用统一的缩写规则。 表达式：使用括号、使用库函数、条件化简、函数与过程 模块化：模块的独立性（高内聚、低耦合）、模块的规模适中。

程序行的排列格式：排列格式美观、层次分明、使用统一的缩进格式，同一嵌套深度并列的语句对齐。 良好的程序设计风格 程序行的排列格式：排列格式美观、层次分明、使用统一的缩进格式，同一嵌套深度并列的语句对齐。 注释：添加必要的注释，以说明程序、过程和语句等的功能及注意事项。

解题的步骤

算法：是由一系列规则组成的过程，这些规则确定了一个操作的顺序，以 便能在有限步骤内得到特定问题的解。 算 法 算法：是由一系列规则组成的过程，这些规则确定了一个操作的顺序，以 便能在有限步骤内得到特定问题的解。 算法的性质： 确定性 通用性 有限性

算 法 算法的描述工具： 自然语言 流程图 决策表 算法描述语言

欧几里德算法（Euclid’s Algorithm） 〖例2-32〗若给定两个正整数m和n，试写出求它们的最大公因子的算法。 该算法的步骤用文字表述如下： 第1步：读入两个正整数m和n（设m>n） 第2步：求m和n的余数r＝mod（m,n） 第3步：用n的值取代 m，用r的值取代n

欧几里德算法（Euclid’s Algorithm） 第4步：判别r的值是否为零，如果r＝0，则m为最大公因子；否则返回 第2步 第5步：输出m的值，即为最大公因子

欧几里德算法（算法描述语言表示） PROCEDURE Euclid； BEGIN READ（m,n）; REPEAT; r:=MOD（m,n）; m:=n; n:=r; UNTIL r＝0; WRITE (m) END

欧几里德算法（流程图表示） m=n BEGIN READ m，n r=mod(m,n) n=r WRITE m r≠0 END Y N

数据：描述客观事物的数、字符以及所有能输入到计算机并被计算机程序处理的符号的集合，如数值、字符、图形、图像、声音等。 数据结构 数据：描述客观事物的数、字符以及所有能输入到计算机并被计算机程序处理的符号的集合，如数值、字符、图形、图像、声音等。

数 据 结 构 数据结构：带有结构的数据元素的集合，结构反映了数据元素相互之间存在的某种联系。从学科的角度来看，数据结构是计算机科学技术的一个分支，它主要研究数据的逻辑结构和物理结构以及它们之间的关系，并对这种结构定义相应的运算，设计出实现这些运算的算法。

在表中查找特定元素LOCATE（L，x） 插入新元素INSERT（L，i，b） 线 性 表 线性表：是n个数据元素的有限序列。 线性表的运算：设L为一个线性表 置空表SETNULL（L） 求表的长度LENGTH（L） 取表元素GET（L，i） 在表中查找特定元素LOCATE（L，x） 插入新元素INSERT（L，i，b）

线 性 表 线性表的运算：设L为一个线性表 删除表元素DELETE（L，i） 线性表的存储结构： 顺序存储结构 链式存储结构

堆栈（stack）：是一种受限的线性表，即只能在表的一端（表尾）进行插入和删除操作。 堆 栈 堆栈（stack）：是一种受限的线性表，即只能在表的一端（表尾）进行插入和删除操作。 进栈和退栈操作按“后进先出”（Last In First Out，LIFO）的原则进行。

堆栈的运算：设S为一个堆栈 置空栈SETNULL（S） 进栈PUSH（S，x） 退栈POP（S） 取栈顶元素TOP（S） 堆 栈 堆栈的运算：设S为一个堆栈 置空栈SETNULL（S） 进栈PUSH（S，x） 退栈POP（S） 取栈顶元素TOP（S） 判断堆栈是否为空EMPTY（S） 堆栈的存储结构：顺序存储结构

队列（queue）：也是一种受限的线性表,只能在表的一端（队尾）进行插入，在表的另一端（队首）进行删除操作。 队 列 队列（queue）：也是一种受限的线性表,只能在表的一端（队尾）进行插入，在表的另一端（队首）进行删除操作。 进、出队列操作按“先进先出”（First In First Out，FIFO）的原则进行。

队列的存储结构：链式存储结构，一个链队列需要设置队首指针和队尾指针。 队 列 队列的运算：设Q为一个队列 置空队列SETNULL（Q） 进入队列ADDQUEUE（Q，x） 退出队列DELQUEUE（Q） 取队首元素FRONTQUE（Q） 判断队列是否为空EMPTY（Q） 队列的存储结构：链式存储结构，一个链队列需要设置队首指针和队尾指针。

小 结 基本知识,包括:计算机的运算基础、逻辑代数基础、计算机的基本结构与工作原理、程序设计基础、算法与数据结构的基础知识。 应掌握数据在计算机内部的表示形式及数制间的转换方法，理解命题逻辑、逻辑代数、计算机的结构、程序设计语言、结构化程序设计方法以及算法与数据结构的基本知识，为进一步学习本书的以下各章和后继课程打好基础。 本章介绍了计算机的一些基本知识,包括:数制与码制、数的定点与浮点表示、信息的编码；逻辑代数与逻辑电路基础;计算机的基本结构与工作原理;程序设计语言、结构化程序设计、程序设计风格；以及算法与数据结构的基础知识。 通过本章的学习，应掌握数据在计算机内部的表示形式及数制间的转换方法，理解逻辑代数、逻辑电路、计算机的结构、程序设计语言、结构化程序设计方法以及算法与数据结构的基本知识，为进一步学习本书的以下各章和后继课程打好基础。

习 题 P.65 一、简答题 二、选择题 三、综合题