第2章-计算机基础

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

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

3、A An n A An n1 1 A A1 1 A A0 0.A.A1 1 A A2 2 A Am m -m A Ai iN Ni i i=n 二进制二进制v二进制：使用数字二进制：使用数字0 0和和1 1等符号来表示数值且采用等符号来表示数值且采用“逢二逢二进一进一”的进位计数制。的进位计数制。v二进制数制的特点：二进制数制的特点：仅使用仅使用0 0和和1 1两个数字。两个数字。最大的数字为最大的数字为1 1，最小的数字为，最小的数字为0 0。每个数字都要乘以基数每个数字都要乘以基数2 2的幂次，该幂次由每个数字的幂次，该幂次由每个数字所在的位置决定。所在的位置决定。v二进制加法和乘法运算规

4、则：二进制加法和乘法运算规则：0 00 00 00 0 0 00 0 0 01 11 10 0 1 10 01 10 01 11 1 0 00 01 11 11 11 1 1 11 1 八进制与十六进制八进制与十六进制v八进制：使用数字八进制：使用数字0 0、1 1、2 2、3 3、4 4、5 5、6 6、7 7等符号来等符号来表示数值的，且采用表示数值的，且采用“逢八进一逢八进一”的进位计数制。的进位计数制。v十六进制：使用数字十六进制：使用数字0 0、1 1、2 2、3 3、4 4、5 5、6 6、7 7、8 8、9 9和和A A、B B、C C、D D、E E、F F等符号来表示数值，其

5、中等符号来表示数值，其中A A、B B、C C、D D、E E、F F分别表示数字分别表示数字1010、1111、1212、1313、1414、1515。十六进制的计数方法为十六进制的计数方法为“逢十六进一逢十六进一”。一一、基本概念、基本概念二进制编码：任何形式的数据在计算二进制编码：任何形式的数据在计算机内部均以机内部均以0和和1表示。表示。采用二进制的优点：容易实现，可靠采用二进制的优点：容易实现，可靠性强，运算简单，通用性强。性强，运算简单，通用性强。二二、数制及其相互转换、数制及其相互转换2、计算机中数的表示法、计算机中数的表示法二进制二进制十进制（十进制（D） 二进制（二进制（B）

6、 八进制（八进制（O） 十六进制（十六进制（H） 0 1 2 3 4 5 6 7 8 9101112131415 0 1 10 11 100 101 110 11110001001101010111100110111101111 0 1 2 3 4 5 6 71011121314151617 0 1 2 3 4 5 6 7 8 9 A B C D E F（1） r 进制转化成十进制进制转化成十进制10101(B) = 124 + 023 + 122 + 021 + 120 = 21101.11(B) = 122 + 021 + 120 + 12-1 + 12-2 = 5.75101(O) =

7、182 + 081 + 180 = 6571(O) = 781 + 180 = 57101A(H) =116 3 + 016 2 + 116 1 + 10 16 0 4106原则：按权展开，相加之和。原则：按权展开，相加之和。（2） 十进制转化成十进制转化成 r 进制进制 整数部分整数部分：除以：除以 r取余数，直到商为取余数，直到商为0，余数从右到左排列。，余数从右到左排列。 小数部分小数部分：乘以：乘以 r取整数，整数从左到右排列。取整数，整数从左到右排列。例 100.345(D)=1100100.01011(B)100(D)=144(O)=64(H)100(D)=144(O)=64(H)

8、=1100100(B)1002502 2521226232100010010.34520.69021.3802 0.760 2 1.520 2 1008128180441100166046161 1.04 十进制小数转换为非十进制小数十进制小数转换为非十进制小数十进制小数并不是都能够用有限位的其他十进制小数并不是都能够用有限位的其他进制数精确地表示进制数精确地表示, ,这时应根据精度要求转换这时应根据精度要求转换到一定的位数为止，作为其近似值。到一定的位数为止，作为其近似值。如果一个十进制数既有整数部分，又有小如果一个十进制数既有整数部分，又有小数部分，则应将整数部分和小数部分分别进数部分，则

9、应将整数部分和小数部分分别进行转换。行转换。（4）二进制转化成十六进制二进制转化成十六进制 原则：原则：四位一组四位一组 整数部分：从右向左进行分组。整数部分：从右向左进行分组。 小数部分：从左向右进行分组。小数部分：从左向右进行分组。 不足不足4位补零。位补零。 11 0110 1110 . 1101 01 (B)=36E.D4(H) 3 6 E D 464(H)： 6 4 0110 0100(B)（3） 十六进制转化成二进制十六进制转化成二进制 原则：原则： 一分为四一分为四每每一一个十六进制数对应二进制的个十六进制数对应二进制的四四位位。2C1D(H) ： 2 C 1 D 0010 11

10、00 0001 1101（B） 后边补两个零变为 0100（5）八进制转化成二进制）八进制转化成二进制每一个八进制数对应二进制的三位。每一个八进制数对应二进制的三位。(7123)O=(111 001 010 011)B (144)O=(001 100 100)B（6）二进制转化成八进制）二进制转化成八进制整数部分：从右向左进行分组。整数部分：从右向左进行分组。小数部分：从左向右进行分组。小数部分：从左向右进行分组。转化成八进制时三位一组，不足补零。转化成八进制时三位一组，不足补零。(1 101 101 110.110 101)B=(1556.65)O机器数机器数 正数和负数：通常把数的最高位定

11、义为符正数和负数：通常把数的最高位定义为符号位，号位，0表示正，表示正，1表示负。表示负。 机器数表示的范围受到字长和数据类型的机器数表示的范围受到字长和数据类型的限制。若表示一个整数，字长为限制。若表示一个整数，字长为8位，最大位，最大值为值为01111111，即，即127。整数和实数整数和实数 整数：带符号数和不带符号数。不同位数整数：带符号数和不带符号数。不同位数和数的表示范围和数的表示范围 实数：采用实数：采用“浮点数浮点数”正数：原码、反码和补码均相同，其最高位为符号位正数：原码、反码和补码均相同，其最高位为符号位，数值位是数的绝对值。，数值位是数的绝对值。负数负数 原码：符号位为原

12、码：符号位为1，数值位是数的绝对值。，数值位是数的绝对值。 反码：符号位不变，其余各位将原码按位取反。反码：符号位不变，其余各位将原码按位取反。 补码：符号位不变，其余各位将原码按位取反，补码：符号位不变，其余各位将原码按位取反，再在最低位加再在最低位加1形成。形成。 给定一个数的真值，求原码、反码和补码。给定一个数的真值，求原码、反码和补码。 给定一个数的原码、反码和补码，求数的真值。给定一个数的原码、反码和补码，求数的真值。（1）原码（假设字长）原码（假设字长8位）位）X原原= 0X ， 0 X +7：00000111 + 0：00000000 1 | X |， X 0 -7：100001

13、11 - 0：10000000(2)反码反码X反反= 0X， 0 X +7：00000111 + 0：00000000 1 | X |，X 0 -7：11111000 - 0：11111111（3）补码）补码X补补= 0X， 0 X + 7：00000111 + 0：00000000 1 | X |+1，X 0 - 7：11111001 - 0： 00000000（1）-5+4 -5补补： 11111011 +4补补： +) 00000100 11111111 -1补补（2）-9+(-5) -9补补： 11110111 -5补补： +) 11111011 11110010 -14补补1（3）1

14、27+5 +127补补： 01111111 +5补补： +) 00000101 10000100运算结果是一个负数，溢出。运算结果是一个负数，溢出。 当运算结果超出了数的表达范围，称为溢出。当运算结果超出了数的表达范围，称为溢出。 什么情况下发生溢出？同号数相加，异号数相减，什么情况下发生溢出？同号数相加，异号数相减，有可能产生溢出。有可能产生溢出。 8位补码所能表达的数的范围是位补码所能表达的数的范围是-128+127； 16位补位补码所能表达的数的范围是码所能表达的数的范围是-32768+327671.对于二进制数对于二进制数10010101和和01000010，对于，对于下列情况分别相当

15、于十进制数的多少？下列情况分别相当于十进制数的多少？将其看做无符号数将其看做无符号数将其看做原码将其看做原码将其看做反码将其看做反码将其看做补码将其看做补码2.给定一个十进制数给定一个十进制数57，将其分别转换为八，将其分别转换为八进制和十六进制数。进制和十六进制数。 定点小数格式定点小数格式v定点小数格式：把小数点固定在数值部分最高位的左边定点小数格式：把小数点固定在数值部分最高位的左边。 N N0 0 . N . N-1-1 N N-2-2 . N . N-m-m 符号位符号位 小数点小数点 数值部分数值部分 v数的范围：二进制的（数的范围：二进制的（m+1m+1）位定点小数格式的数）位定

16、点小数格式的数N N，所，所能表示的数的范围为能表示的数的范围为N N 1 1 2 2-m-m。v比例因子：对于绝对值大于比例因子：对于绝对值大于1 1的数，如果直接使用定点小的数，如果直接使用定点小数格式将会产生数格式将会产生“溢出溢出”，需根据实际需要使用一个比，需根据实际需要使用一个比例因子，将原始数据按该比例缩小，以定点小数格式表例因子，将原始数据按该比例缩小，以定点小数格式表示，得出结果后再按该比例扩大得到实际的结果。示，得出结果后再按该比例扩大得到实际的结果。 定点整数格式定点整数格式v定点整数格式：把小数点固定在数值部分最低位的右边。定点整数格式：把小数点固定在数值部分最低位的右

17、边。 N N0 0 N Nn n N Nn-1n-1 . N . N2 2 N N1 1 . . 符号位符号位 数值部分数值部分 小数点小数点 v数的范围：二进制的（数的范围：二进制的（m+1m+1）位定点整数格式的数）位定点整数格式的数N N，所能，所能表示的数的范围为表示的数的范围为N N 2 2m m 1 1。v比例因子：对于绝对值大于该范围的数，如果直接使用定比例因子：对于绝对值大于该范围的数，如果直接使用定点小数格式也将会产生点小数格式也将会产生“溢出溢出”，需根据实际需要选择一，需根据实际需要选择一个比例因子进行调整，使所表示的数据在规定的范围之内个比例因子进行调整，使所表示的数据

18、在规定的范围之内。 浮点表示法浮点表示法v浮点表示法：小数点的位置不固定，一个浮点数分为阶码浮点表示法：小数点的位置不固定，一个浮点数分为阶码和尾数两部分。和尾数两部分。v阶码：用于表示小数点在该数中的位置，是一个整数。阶码：用于表示小数点在该数中的位置，是一个整数。v尾数：用于表示数的有效数值，可以采用整数或纯小数两尾数：用于表示数的有效数值，可以采用整数或纯小数两种形式种形式v可供选择的一种位数分配形式：设字长为可供选择的一种位数分配形式：设字长为3232位位 符号位符号位 阶码部分阶码部分 尾尾 数数 部部 分分 1 1位位 8 8位位2323位位v规格化的浮点数：为了提高浮点数表示的精

19、度通常规定其规格化的浮点数：为了提高浮点数表示的精度通常规定其尾数的最高位必须是非零的有效位，称为浮点数的规格化尾数的最高位必须是非零的有效位，称为浮点数的规格化形式。形式。 BCD BCD码与码与ASCIIASCII码码vBCDBCD码：是一种二十进制的编码，使用四位二进制数码：是一种二十进制的编码，使用四位二进制数表示一位十进制数。表示一位十进制数。v十进制数与十进制数与BCDBCD码之间的转换：可按位（或四位二进制码之间的转换：可按位（或四位二进制数组）直接进行。数组）直接进行。vASCII(American Standards Committee of ASCII(American S

20、tandards Committee of Information)Information)码码: :是由美国信息交换标准委员会制定的是由美国信息交换标准委员会制定的、国际上使用最广泛的字符编码方案。、国际上使用最广泛的字符编码方案。vASCIIASCII码的编码方案：采用码的编码方案：采用7 7位二进制数表示一个字符，位二进制数表示一个字符，把把7 7位二进制数分为高三位（位二进制数分为高三位（b b7 7b b6 6b b5 5）和低四位）和低四位 （b b4 4b b3 3b b2 2b b1 1）v7 7位位ASCIIASCII编码表：如表编码表：如表2-52-5所示，利用该表可以查找

21、数所示，利用该表可以查找数字、运算符、标点符号以及控制符等字符与字、运算符、标点符号以及控制符等字符与ASCIIASCII码之码之间的对应关系。间的对应关系。l西文字符西文字符ASCII：用七位二进制表示，存储时占：用七位二进制表示，存储时占8位，最高位，最高位是奇偶校验位。位是奇偶校验位。l常用字符有常用字符有128个，编码从个，编码从0到到127。l数字数字09，英文字母，英文字母AZ，az都是顺序排列都是顺序排列l每个字符占一个字节，即每个字符占一个字节，即8 位二进制位，最高位二进制位，最高位恒为位恒为0。 汉字编码体系汉字编码体系v汉字输入码：由输入设备产生的汉字编码，如区位码、国汉

22、字输入码：由输入设备产生的汉字编码，如区位码、国标码、拼音码、新全拼、新双拼、五笔字型码、简码、表标码、拼音码、新全拼、新双拼、五笔字型码、简码、表形码、自然码、智能形码、自然码、智能ABCABC汉字输入码等。汉字输入码等。v汉字内码：用于计算机内部存储和处理的汉字编码，通常汉字内码：用于计算机内部存储和处理的汉字编码，通常由该汉字的国标码的两个字节（最高位置由该汉字的国标码的两个字节（最高位置“1”1”）形成。）形成。v汉字字形码：确定一个汉字字形点阵的编码，用于汉字显汉字字形码：确定一个汉字字形点阵的编码，用于汉字显示和打印输出。保留在存储介质中的全部汉字字形码称为示和打印输出。保留在存储

23、介质中的全部汉字字形码称为字库。字库。v汉字交换码：用于在不同的汉字信息处理系统之间或与其汉字交换码：用于在不同的汉字信息处理系统之间或与其他计算机系统之间进行信息交换。他计算机系统之间进行信息交换。v汉字地址码：表示汉字字形信息在汉字库中的地址，用于汉字地址码：表示汉字字形信息在汉字库中的地址，用于在汉字库中查找汉字字形信息的汉字地址码等。在汉字库中查找汉字字形信息的汉字地址码等。 数据校验码数据校验码v奇偶校验码：在表示数据的奇偶校验码：在表示数据的N N位代码中增加一位代码中增加一位奇偶校验位，使位奇偶校验位，使N N1 1位中位中“1”1”的个数为奇的个数为奇数（奇校验）或偶数（偶校验

24、）。数（奇校验）或偶数（偶校验）。v海明校验码：在有效信息代码中增加校验位，海明校验码：在有效信息代码中增加校验位，用来校验代码中用来校验代码中“1”1”的个数是奇数（奇校验的个数是奇数（奇校验）还是偶数（偶校验），通过奇偶校验可以发）还是偶数（偶校验），通过奇偶校验可以发现代码传输过程中的错误并自动校正。现代码传输过程中的错误并自动校正。v应用：用于计算机各部件之间信息传输以及计应用：用于计算机各部件之间信息传输以及计算机网络的信息传输。算机网络的信息传输。汉字编码汉字编码(1) 汉字输入码汉字输入码 国标区位码、全拼、双拼、微软拼音、五笔字形等。国标区位码、全拼、双拼、微软拼音、五笔字形等

25、。(2) 汉字交换码汉字交换码 国标码国标码(GB231280) ： 我国汉字交换码的国家标准我国汉字交换码的国家标准 其中：其中： 一级汉字：一级汉字：3755个；二级汉字：个；二级汉字：3008个。个。 汉字分区，每个区汉字分区，每个区94个汉字。个汉字。 每个汉字占每个汉字占两个两个字节，国标码最高位为字节，国标码最高位为0。 每个汉字占每个汉字占两个两个字节，机内码最高位为字节，机内码最高位为1。区号区中位置例： 汉字 国标码 汉字内码 沪 2706(00011011 00000110B) 10011011 10000110B 久 3035(00011110 00100011B) 10

26、011110 10100011B(3) 汉字内码汉字内码 汉字在设备或信息处理系统内部最基本的表达形式。汉字在设备或信息处理系统内部最基本的表达形式。(4) 汉字字形码：又称汉字字模，用于汉字的显示或打印。汉字字形的字模数据，以点阵或矢量函数表示。汉字字形的字模数据，以点阵或矢量函数表示。点阵：点阵：1616、2424、3232、4848。汉字字形码占用的存储空间：汉字字形码占用的存储空间： 例：例： 一个一个16 16的汉字：的汉字： 16 8 16 = 32 字节字节 一个一个24 24的汉字：的汉字： 24 8 24 = 72 字节字节 一个一个32 32的汉字：的汉字： 32 8 32

27、 = 128 字节字节 两个两个48 48的汉字：的汉字： 48 8 48 2= 576 字节字节 命题命题v命题：有具体意义且能够判断真假的陈述句。命题：有具体意义且能够判断真假的陈述句。v命题的真值命题的真值: :命题所具有的值命题所具有的值“真真”(true(true，简，简记为记为T)T)或或“假假”（false,false,简记为简记为F F）称为其真值）称为其真值。v命题标识符：表示命题的符号，该标识符称为命命题标识符：表示命题的符号，该标识符称为命题常量。题常量。v原子命题：不能分解为更为简单的陈述句的命题原子命题：不能分解为更为简单的陈述句的命题；v复合命题：将原子命题用连接词

28、和标点符号复合复合命题：将原子命题用连接词和标点符号复合而成的命题。而成的命题。 连接词连接词“与与”（ ） A A B B AB AB T T T T T T T T F F F F F F T T F F F F F F F F 连接词连接词 “ “或或”（）v“或或”（）：两个命题）：两个命题A A和和B B的的“或或”（又称为（又称为A A和和B B的的“析取析取”）是一个复合命题，记为）是一个复合命题，记为ABAB。当且仅当。当且仅当A A和和B B同时为假时同时为假时ABAB为假，在其他的情况下为假，在其他的情况下ABAB的真的真值均为真。值均为真。vABAB的真值表：的真值表：

29、A A B B ABAB T T T T T T T T F F T T F F T T T T F F F F F F 连接词连接词“非非”（）v“非非”（）：命题）：命题A A的的“非非”（又称为（又称为A A的的“否定否定”）是一个复合命题，记为）是一个复合命题，记为 AA。若。若A A为真，则为真，则AA为假为假；若；若A A为假，则为假，则AA为真。为真。vAA的真值表：的真值表： A AAAT TF FF FT T 连接词连接词 “ “异或异或”（）“异或异或” ” （）：两个命题的）：两个命题的A A和和B B的的“异或异或”（又称为（又称为A A和和B B的的“不可兼或不可兼或

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

31、真的真值为真，B B的真值为假时，的真值为假时，ABAB为假，在其他的情况下为假，在其他的情况下ABAB的真的真值均为真。值均为真。vABAB的真值表：的真值表： A A B B A BA B T T T T T T T T F F F F F F T T T T F F F F T T 连接词连接词 “双条件双条件”( )( )v“双条件双条件”( ):( ):两个命题的两个命题的A A和和B B的的“双条件双条件”（又（又称为称为A A当且仅当当且仅当B B）是一个复合命题，记为）是一个复合命题，记为A BA B，读，读作作“A A当且仅当当且仅当B”B”。 当且仅当当且仅当A A的真值与

32、的真值与B B的真值相的真值相同时，同时， A BA B为真，否则为真，否则A BA B的真值均为假。的真值均为假。vA BA B的真值表：的真值表： A A B B A BA B T T T T T T T T F F F F F F T T T T F F F F T T 命题公式命题公式v命题公式：命题公式： 由命题变元、连接词和括号组成的合式的式子称为由命题变元、连接词和括号组成的合式的式子称为命题公式。命题公式。v命题公式等价：如果两个不同的命题公式命题公式等价：如果两个不同的命题公式P P和和Q Q，无论其命题变元，无论其命题变元取什么值它们的真值都相同，则称该两个命题公式等价，记

33、为取什么值它们的真值都相同，则称该两个命题公式等价，记为P PQ Q。例例2-252-25证明证明 （ABAB）与）与ABAB是等价的。是等价的。 A AB B（ABAB）ABABT TT T F F F F T T F F T TT T F F T T F F F F F F F F F F F F 命题公式的等价律命题公式的等价律其中其中A A、B B、C C等为命题变元，等为命题变元，T T表示表示“真真”，F F表示表示“假假”v零律：零律： AFAFA A AF AFF Fv幺律：幺律： ATATT T A T A TA A v幂等律：幂等律：AAAAA A A A A AA Av求

34、补律：求补律：AAAAT T AA AAF Fv交换律：交换律：ABABBABA AB ABBABA 命题公式的等价律（续）命题公式的等价律（续）v结合律：结合律： AA（BCBC）（）（ABAB）CC A A（BCBC）（）（ABAB）CCv分配律：分配律： AA（BCBC）ABACABAC ABC ABC（ABAB）（ACAC）v吸收律：吸收律： ABABABABA A （ABAB）（ABAB）A Av狄摩根定律：狄摩根定律：（ABAB）ABAB （ABAB）ABABv双重否定律：双重否定律： A AA A 证明狄摩根定律证明狄摩根定律例例2-262-26证明狄摩根定律之一：证明狄摩根定律

35、之一：（ABAB）ABAB。A AB ABAB（ABAB）AABBABABT TT TT TF FF FF FF FT TF FF FT TF FT T T TF FT TF FT T T TF FT TF FF FF FT TT TT TT T 逻辑代数的等价律逻辑代数的等价律v零律：零律： A A0 0A AA 0A 00 0v幺律：幺律： A A1 11 1A 1A 1A A v幂等律：幂等律：A AA AA A A A A AA Av求补律：求补律：A A 1 1A A 0 0 逻辑代数的等价律（续）逻辑代数的等价律（续）B BB BB BB B(A+B)(A+B) A (A B)(A

36、 B)v交换律：交换律：A AB BB BA A A B A BB AB Av结合律：结合律：A A（B BC C）（）（A AB B）C C A A（B CB C）（）（A BA B）C Cv分配律：分配律：A A（B BC C）A BA BA CA C A AB CB C（A AB B）（）（A AC C）v吸收律：吸收律：A BA BA A A A （A AB B）（）（A A ）A Av狄摩根定律：狄摩根定律： v双重否定律：双重否定律： A A A 逻辑函数的化简逻辑函数的化简例例2-272-27试将逻辑函数试将逻辑函数F FA A B B化简。化简。 解：解：F FA A B B（

37、A A ）(A(AB)B)（分配律）（分配律）1 (A1 (AB) B) （求补律）（求补律） A AB B （幺律）（幺律）例例2-282-28试将逻辑函数试将逻辑函数F FABABA A B B 化简。化简。解：解：F F ABABA A B B A A（B B ） （B B ）（分配律）（分配律） A A （求补律）（求补律） 1 1 （求补律）（求补律）BBBB (A B)(A B) (A B)(A B)计算机硬件的基本结构计算机硬件的基本结构 辅助存储器辅助存储器内存储器内存储器运运 算算 器器 控制控制 器器输入设备输入设备输出设备输出设备 程序原始数据 运算 结果控制信息数据 运

38、算器运算器v运算器：对二进制数进行运算的部件。它在控制器的控运算器：对二进制数进行运算的部件。它在控制器的控制下执行程序中的指令制下执行程序中的指令, ,完成各种算术运算、逻辑运算、完成各种算术运算、逻辑运算、比较运算、移位运算以及字符运算等。比较运算、移位运算以及字符运算等。v运算器的组成：算术逻辑部件（运算器的组成：算术逻辑部件（ALUALU）完成加、减、乘、）完成加、减、乘、除等四则运算以及与、或、非、移位等逻辑运算；寄存除等四则运算以及与、或、非、移位等逻辑运算；寄存器用来暂存参加运算的操作数或中间结果，常用的寄存器用来暂存参加运算的操作数或中间结果，常用的寄存器有累加寄存器、暂存寄存

39、器、标志寄存器和通用寄存器有累加寄存器、暂存寄存器、标志寄存器和通用寄存器等。器等。v运算器的主要技术指标：运算速度，其单位是运算器的主要技术指标：运算速度，其单位是MIPSMIPS（百（百万指令万指令/ /秒），通常是按照一定的频度执行各类指令的统秒），通常是按照一定的频度执行各类指令的统计值。计值。 存储器存储器v存储器：用来存储数据和程序的部件。存储器：用来存储数据和程序的部件。v存储单位：存储单位：“位位”（bitbit）、）、“字节字节”（bytebyte）、）、“字字”和和“字长字长”v存储容量：存储器所包含的存储单元的总数，其单位为存储容量：存储器所包含的存储单元的总数，其单位为

40、KBKB （1KB1KB2 210101024B1024B）。）。(1M=1024KB, 1GB=1024MB, (1M=1024KB, 1GB=1024MB, 1T=1024G)1T=1024G)v存储器的分类：存储器的分类：内存储器：又称为主存储器，简称为内存或主存，用来内存储器：又称为主存储器，简称为内存或主存，用来存放现行程序的指令和数据。包括随机存取存储器（存放现行程序的指令和数据。包括随机存取存储器（RAMRAM）和只读存储器（）和只读存储器（ROMROM）等。）等。外存储器：又称为辅助存储器，简称为外存或辅存，用外存储器：又称为辅助存储器，简称为外存或辅存，用来存放需要长期保存的

41、信息。来存放需要长期保存的信息。内存和外存的比较内存和外存的比较内存直接同内存直接同CPU进行数据交换，存取进行数据交换，存取速度快，容量小。内存的存取速度直速度快，容量小。内存的存取速度直接影响计算机的运算速度。（在计算接影响计算机的运算速度。（在计算机的性能指标中内存通常是指机的性能指标中内存通常是指RAM的的容量）容量）外存（辅存）：计算机把外存数据调外存（辅存）：计算机把外存数据调到内存，才能和到内存，才能和CPU进行数据交换。进行数据交换。容量大，速度慢。容量大，速度慢。内存属于易失性存储器，外存是非易内存属于易失性存储器，外存是非易失性存储器失性存储器 存储单元地址存储单元地址整个

42、内存分成若干个存储单元，一般整个内存分成若干个存储单元，一般一个单元存一个字节。为了能有效地一个单元存一个字节。为了能有效地进行数据存取，每个单元必须有唯一进行数据存取，每个单元必须有唯一的编号（地址）来标识。的编号（地址）来标识。 控制器控制器v控制器：是指挥计算机的各个部件按照指令的功能要求协控制器：是指挥计算机的各个部件按照指令的功能要求协调工作的部件。调工作的部件。v控制器的组成：控制器的组成： 程序计数器（程序计数器（PCPC）：用来对程序中的指令进行计数，）：用来对程序中的指令进行计数，使控制器能依次读取指令；使控制器能依次读取指令； 指令寄存器（指令寄存器（IRIR）：在指令执行

43、期间暂时保存正在执）：在指令执行期间暂时保存正在执行的指令。行的指令。 指令译码器（指令译码器（IDID）：用来识别指令的功能，分析指令）：用来识别指令的功能，分析指令的操作要求。的操作要求。 时序控制电路：用来生成时序信号，以协调在指令执时序控制电路：用来生成时序信号，以协调在指令执行周期内各部件的工作。行周期内各部件的工作。 微操作控制电路：用来产生各种控制操作命令。微操作控制电路：用来产生各种控制操作命令。 输入输入/ /输出设备输出设备v输入输入/ /输出设备：简称为输出设备：简称为I/OI/O设备，是外部与计算机交设备，是外部与计算机交换信息的渠道。换信息的渠道。v输入设备：用于输入

44、程序、数据、操作命令、图形、输入设备：用于输入程序、数据、操作命令、图形、图像以及声音等信息。常用的输入设备有键盘、鼠标图像以及声音等信息。常用的输入设备有键盘、鼠标器、扫描仪、光笔、数字化仪以及语音输入装置等。器、扫描仪、光笔、数字化仪以及语音输入装置等。v输出设备：用于显示或打印程序、运算结果、文字、输出设备：用于显示或打印程序、运算结果、文字、图形、图像等，也可以播放声音。常用的输出设备有图形、图像等，也可以播放声音。常用的输出设备有显示器、打印机、显示器、打印机、XYXY绘图仪以及声音播放装置等。绘图仪以及声音播放装置等。 计算机的指令系统计算机的指令系统v指令：能被计算机识别并执行的

45、二进制代码，它规定指令：能被计算机识别并执行的二进制代码，它规定了计算机能完成的某一种操作。了计算机能完成的某一种操作。v指令系统：一台计算机能执行的所有指令的集合。指令系统：一台计算机能执行的所有指令的集合。v指令的格式：一条指令由操作码和地址码组成。操作指令的格式：一条指令由操作码和地址码组成。操作码规定了该指令进行的操作种类；地址码给出了操作码规定了该指令进行的操作种类；地址码给出了操作数、结果以及下一条指令的地址。数、结果以及下一条指令的地址。v指令的分类：指令的分类： 数据传送型指令数据传送型指令 数据处理型指令数据处理型指令 输入输出型指令输入输出型指令 硬件控制指令硬件控制指令

46、指令的执行过程指令的执行过程v取指令：即按照指令计数器中的地址，从内存储器中取指令：即按照指令计数器中的地址，从内存储器中取出指令，并送往指令寄存器中。取出指令，并送往指令寄存器中。v分析指令：即对指令寄存器中存放的指令进行分析，分析指令：即对指令寄存器中存放的指令进行分析，由操作码确定执行什么操作，由地址码确定操作数的由操作码确定执行什么操作，由地址码确定操作数的地址。地址。v执行指令：即根据分析的结果，由控制器发出完成该执行指令：即根据分析的结果，由控制器发出完成该操作所需要的一系列控制信息，去完成该指令所要求操作所需要的一系列控制信息，去完成该指令所要求的操作。的操作。v上述步骤完成后，

47、指令计数器加上述步骤完成后，指令计数器加1 1，为执行下一条指，为执行下一条指令做好准备。如果遇到转移指令，则将转移地址送入令做好准备。如果遇到转移指令，则将转移地址送入指令计数器。指令计数器。 计算机组织与系统结构领域的一些主要技术计算机组织与系统结构领域的一些主要技术v精简指令集技术（精简指令集技术（RISCRISC）v高速缓冲存储技术（高速缓冲存储技术（cachecache）v虚拟存储技术虚拟存储技术v指令流水线技术指令流水线技术v并行处理技术并行处理技术 程序设计语言程序设计语言v机器语言：由计算机的指令系统组成，使用机器语言编写机器语言：由计算机的指令系统组成，使用机器语言编写的程序

48、计算机能够直接理解并执行，但编程和理解都十分的程序计算机能够直接理解并执行，但编程和理解都十分的困难。的困难。v汇编语言：使用汇编语言：使用“助忆符助忆符”来表示指令的操作码，并使用来表示指令的操作码，并使用存储单元或寄存器的名字表示地址码，以便于记忆和书写存储单元或寄存器的名字表示地址码，以便于记忆和书写。v高级程序设计语言：是一种与机器的指令系统无关、表达高级程序设计语言：是一种与机器的指令系统无关、表达形式更接近于被描述的问题的程序设计语言，便于程序的形式更接近于被描述的问题的程序设计语言，便于程序的编写。使用高级程序设计语言编写的程序称为源程序，它编写。使用高级程序设计语言编写的程序称

49、为源程序，它必须经过程序设计语言翻译系统的处理后才能执行。必须经过程序设计语言翻译系统的处理后才能执行。面向过程程序设计语言面向过程程序设计语言面向对象程序设计语言面向对象程序设计语言 程序设计程序设计v程序设计：是一个使用程序设计语言产生一系列的指程序设计：是一个使用程序设计语言产生一系列的指令以告诉计算机该做什么的过程。令以告诉计算机该做什么的过程。v广义的程序设计：广义的程序设计： 需求分析需求分析 总体设计总体设计 详细设计详细设计 编码编码 测试测试 运行与维护运行与维护 结构化程序设计结构化程序设计 结构化程序设计：采用自顶向下逐步求精的设计方法和单入口单出口结构化程序设计：采用自

50、顶向下逐步求精的设计方法和单入口单出口的控制成分（顺序、分支和循环）。的控制成分（顺序、分支和循环）。 T FTF条件AAB（a）顺序结构 （b）选择型分支结构 （c）循环结构AB条件 良好的程序设计风格良好的程序设计风格v标识符：按意命名、保留字用大写字母、使用统标识符：按意命名、保留字用大写字母、使用统一的缩写规则。一的缩写规则。v表达式：使用括号、使用库函数、条件化简、函表达式：使用括号、使用库函数、条件化简、函数与过程数与过程v模块化：模块的独立性（高内聚、低耦合）、模模块化：模块的独立性（高内聚、低耦合）、模块的规模适中。块的规模适中。v程序行的排列格式：排列格式美观、层次分明、程序

51、行的排列格式：排列格式美观、层次分明、使用统一的缩进格式，同一嵌套深度并列的语句使用统一的缩进格式，同一嵌套深度并列的语句对齐。对齐。v注释：添加必要的注释，以说明程序、过程和语注释：添加必要的注释，以说明程序、过程和语句等的功能及注意事项。句等的功能及注意事项。 算法算法v算法：是由一系列规则组成的过程，这些规则确定了算法：是由一系列规则组成的过程，这些规则确定了一个操作的顺序，以便能在有限步骤内得到特定问题一个操作的顺序，以便能在有限步骤内得到特定问题的解。的解。v算法的性质：算法的性质：确定性确定性通用性通用性有限性有限性v算法的描述工具：算法的描述工具：自然语言自然语言流程图流程图决策

52、表决策表算法描述语言算法描述语言 时间复杂度时间复杂度 T(n)实际上是表示当问题的规模实际上是表示当问题的规模n充分大时，该程序运充分大时，该程序运行时间的一个数量级。行时间的一个数量级。 空间复杂度空间复杂度 运行时所占用的空间的大小运行时所占用的空间的大小 易理解性易理解性 结构好，易理解，易修改等。结构好，易理解，易修改等。 欧几里德算法（欧几里德算法（EuclidEuclids Algorithms Algorithm）例例2-322-32若给定两个正整数若给定两个正整数m m和和n n，试写出求它们的最大公，试写出求它们的最大公因子的算法。因子的算法。该算法的步骤用文字表述如下：该

53、算法的步骤用文字表述如下：第第1 1步：读入两个正整数步：读入两个正整数m m和和n n（设（设mnmn）。）。第第2 2步：求步：求m m和和n n的余数的余数r rmodmod（m,nm,n）。）。第第3 3步：用步：用n n的值取代的值取代 m m，用，用r r的值取代的值取代n n。第第4 4步：判别步：判别r r的值是否为零，如果的值是否为零，如果r r0 0，则，则m m为最大为最大公因子；否则返回公因子；否则返回 第第2 2步。步。第第5 5步：输出步：输出m m的值，即为最大公因子。的值，即为最大公因子。PROCEDURE EuclidPROCEDURE Euclid； BEG

54、INBEGIN READ READ（m,nm,n）; ; REPEAT;REPEAT; r:=MOD r:=MOD（m,nm,n）; ; m:=n; m:=n; n:=r; n:=r; UNTIL r UNTIL r0;0; WRITE (m) WRITE (m) ENDEND欧几里德算法（流程图表示） m=n BEGIN READ m，n r=mod(m,n)n=rWRITE mr0ENDYN 数据结构数据结构v数据：描述客观事物的数、字符以及所有能输入到计算数据：描述客观事物的数、字符以及所有能输入到计算机并被计算机程序处理的符号的集合，如数值、字符、机并被计算机程序处理的符号的集合，如数

55、值、字符、图形、图像、声音等。图形、图像、声音等。v数据结构：带有结构的数据元素的集合，结构反映了数数据结构：带有结构的数据元素的集合，结构反映了数据元素相互之间存在的某种联系。从学科的角度来看，据元素相互之间存在的某种联系。从学科的角度来看，数据结构是计算机科学技术的一个分支，它主要研究数数据结构是计算机科学技术的一个分支，它主要研究数据的逻辑结构和物理结构以及它们之间的关系，并对这据的逻辑结构和物理结构以及它们之间的关系，并对这种结构定义相应的运算，设计出实现这些运算的算法。种结构定义相应的运算，设计出实现这些运算的算法。v几种典型的数据结构几种典型的数据结构 线性表线性表 v线性表：是线性表：是n n个数据元素的有限序列。个数据元素的有限序列。v线性表的运算：设线性表的运算：设L L为一个线性表为一个线性表置空表置空表SE