计算机导论课件

第2章计算机基础知识

2.1计算机的运算基础2.2命题逻辑与逻辑代数基础2.3计算机的基本结构与工作原理2.4程序设计基础2.5算法基础2.6数据结构基础2.7本章小结第2章计算机基础知识2.1计算机的运算基础基本要求：掌握数制间的转换方法以及数据在计算机内部的表示形式理解逻辑代数、计算机的工作原理、程序设计以及算法与数据结构的基本知识，为学习本书的以下各章和后续课程打好基础基本要求：计算机中的数制数值型数据的表示字符型数据的编码表示汉字的编码表示2.1计算机的运算基础计算机中的数制2.1计算机的运算基础2.1.1计算机中的数制不同数制的表示在计算机内部用二进制形式表示和存储数据。

人们习惯于用十进制记数。为了书写简单方便也使用八进制和十六进制。用加后缀或角标的形式区别不同进制数据。B—表示二进制数。O或Q—表示八进制数。D—表示十进制数（D可省略）。H—表示十六进制数。2.1.1计算机中的数制不同数制的表示2.1.1计算机中的数制二进制转换成其他进制二进制数转换成十进制数，按权展开相加即可。二进制数转换成八进制数时，以小数点为界，分别向左向右分成3位一组，不够3位补0，分完组后对应成八进制数即可。二进制数转换成十六进制数时，以小数点为界，分别向左向右分成4位一组，不够4位补0，分完组后对应成十六进制数即可。2.1.1计算机中的数制二进制转换成其他进制2.1.1计算机中的数制二进制转换成其他进制示例

(1011001.10111)2

=1×26+1×24+1×23+1×20+1×2-1+1×2-3+1×2-4+1×2-5=64+16+8+1+0.5+0.125+0.0625+0.03125+0.015625=(99.734375)10

(1011001.10111)2

=(001011001.101110)2=(131.56)8

(1011001.10111)2

=(01011001.10111000)2=(59.B8)162.1.1计算机中的数制二进制转换成其他进制示例2.1.1计算机中的数制其他进制转换成二进制十进制数转换成二进制数，先把十进制数分解成若干个数相加,每个数都是2的若干次幂，然后对应成二进制数。八进制数转换成二进制数时，每一个八进制位展开成3个二进制位即可。十六进制数转换成二进制数时，每一个十六进制位展开成4个二进制位即可。2.1.1计算机中的数制其他进制转换成二进制2.1.1数据表示其他进制转换成二进制示例

(98.75)10

=64+32+2+0.5+0.25=(1100010.11)2

(276.15)8=(010111110.001101)2=(10111110.001101)2

(3AC.1E)16

=(001110101100.00011110)2=(1110101100.0001111)22.1.1数据表示其他进制转换成二进制示例2.1.2数值型数据的表示无符号数据的表示按一定规则把无符号整数转换成二进制形式在计算机内部表示和存储。带符号数据的表示带符号数中的正负号及小数中的小数点都以二进制形式表示。需要考虑的因素机器数的范围。机器数的符号。机器数中小数点的位置。2.1.2数值型数据的表示无符号数据的表示2.1.2数值型数据的表示机器数的范围机器数的表示范围由CPU中的寄存器决定。对于无符号数，8位寄存器的表示范围是0～255，16位寄存器的表示范围是0～65535。对于带符号数，8位寄存器的表示范围是-128～+127，16位寄存器的表示范围是-32768～+32767。2.1.2数值型数据的表示机器数的范围2.1.2数值型数据的表示机器数的符号在计算机内部，任何数据（符号）都只能用二进制的两个数码0和1来表示。带符号数的表示，除了用0和1的组合来表示数值的绝对值大小外，其正负号也必须用0和1来表示。最高位为符号位，并用0表示正，用1表示负。有原码/反码/补码等表示形式。2.1.2数值型数据的表示机器数的符号2.1.2数值型数据的表示机器数示例无符号十进制数57的机器数表示。57的二进制形式为111001。[+57]原=00111001（正数的原码最高位为0，数值位补足7位）[-57]原=

10111001（负数的原码最高位为1，数值位补足7位）

[+57]反=

00111001（正数的反码与其原码相同）

[-57]反=

11000110（负数的反码，符号位不变，数值位为原码数值位取反）[+57]补=00111001（正数的补码与其原码相同）[-57]补=11000111（负数的补码在其反码的末尾加1）2.1.2数值型数据的表示机器数示例2.1.2数值型数据的表示机器数中小数点的位置定点数（定点整数/定点小数）浮点数0000000110000011h数值部分符号位小数点位置11010000000000

00

h数值部分符号位小数点位置2.1.2数值型数据的表示机器数中小数点的位置0000002.1.3字符型数据的编码表示基本含义对于字符型数据，没有相应的转换规则可以使用。需要人们规定出每个字符对应的二进制编码形式。常用的字符型数据编码ASCII码（美国标准信息交换码的简称）使用一个字节表示一个ASCII码字符。主要用于小型机和微型机。EBCDIC码（扩展BCD码）BCD码又称二—十进制编码，用二进制编码形式表示十进制数。在BCD码的基础上，又增加了一些符号和英文字母的表示。主要用于超级计算机和大型计算机。2.1.3字符型数据的编码表示基本含义BCD码与ASCII码BCD码：是一种二－十进制的编码，使用四位二进制数表示一位十进制数。十进制数与BCD码之间的转换：可按位（或四位二进制数组）直接进行。ASCII(AmericanStandardsCommitteeofIformation)码:是由美国信息交换标准委员会制定的、国际上使用最广泛的字符编码方案。ASCII码的编码方案：采用7位二进制数表示一个字符，把7位二进制数分为高三位（b7b6b5）和低四位（b4b3b2b1）7位ASCII编码表：如表2-5所示，利用该表可以查找数字、运算符、标点符号以及控制符等字符与ASCII码之间的对应关系。BCD码与ASCII码数据校验码奇偶校验码：在表示数据的N位代码中增加一位奇偶校验位，使N＋1位中“1”的个数为奇数（奇校验）或偶数（偶校验）。海明校验码：在有效信息代码中增加校验位，用来校验代码中“1”的个数是奇数（奇校验）还是偶数（偶校验），通过奇偶校验可以发现代码传输过程中的错误并自动校正。应用：用于计算机各部件之间信息传输以及计算机网络的信息传输。数据校验码2.1.4汉字的编码表示与汉字处理有关的几种编码汉字输入码数字码：国标区位码。拼音码：全拼输入法/紫光输入法/智能ABC输入法。字形码：五笔字型编码。汉字机内码（一个汉字占用2个字节，最高位置1）。计算机内部使用的汉字代码。汉字交换码：在不同信息处理系统之间进行信息交换。国标码。BIG5码。汉字字形码（用于显示和打印）2.1.4汉字的编码表示与汉字处理有关的几种编码2.2逻辑代数基础命题命题公式命题公式的等价律逻辑函数的化简

2.2逻辑代数基础命题命题逻辑基础命题：有具体意义且能够判断真假的陈述句。命题的真值:命题所具有的值“真”(true，简记为T)或“假”（false,简记为F）称为其真值。命题标识符：表示命题的符号，该标识符称为命题常量。原子命题：不能分解为更为简单的陈述句的命题；复合命题：将原子命题用连接词和标点符号复合而成的命题。2.2逻辑代数基础命题逻辑基础2.2逻辑代数基础连接词“与”（∧）“与”(∧):两个命题A和B的“与”(又称为A和B的“合取”)是一个复合命题，记为A∧B。当且仅当A和B同时为真时A∧B为真，在其他的情况下A∧B的真值均为假。

A∧B的真值表:

A

B

A∧B

T

T

T

T

F

F

F

T

F

F

F

F2.2逻辑代数基础连接词“与”（∧）

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

A

B

A∨B

T

T

T

T

F

T

F

T

T

F

F

F2.2逻辑代数基础连接词“或”（∨）A B连接词“非”（┑）“非”（┑）：命题A的“非”（又称为A的“否定”）是一个复合命题，记为┑A。若A为真，则┑A为假；若A为假，则┑A为真。┑A的真值表：

A┑ATFFT2.2逻辑代数基础连接词“非”（┑）A┑ATFFT2.2逻辑代数基础连接词“异或”（⊕）“异或”（⊕）：两个命题的A和B的“异或”（又称为A和B的“不可兼或”）是一个复合命题，记为A⊕B。当且仅当A和B同时为真或者同时为假时A⊕B为假，在其他的情况下A⊕B的真值为真。A⊕B的真值表：

A

B

A⊕B

T

T

F

T

F

T

F

T

T

F

F

F2.2逻辑代数基础连接词“异或”（⊕）A B连接词“条件”（→）“条件”（→）：两个命题的A和B的“条件”是一个复合命题，记为

A→B,读作“如果A，则B”。当且仅当A的真值为真，B的真值为假时，A→B为假，在其他的情况下A→B的真值均为真。A→B的真值表：

A

B

A→B

T

T

T

T

F

F

F

T

T

F

F

T2.2逻辑代数基础连接词“条件”（→）A B连接词“双条件”()

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

A

B

AB

T

T

T

T

F

F

F

T

T

F

F

T2.2逻辑代数基础连接词“双条件”()

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

F

FT

FTT

FT

F

F

F

F

F

F2.2逻辑代数基础命题公式AB┑（A→B）A∧┑BTTFFTFTT命题公式的等价律其中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＝TA∧┓A＝F交换律：A∨B＝B∨AA∧B＝B∧A2.2逻辑代数基础命题公式的等价律2.2逻辑代数基础命题公式的等价律（续）结合律：A∨（B∨C）＝（A∨B）∨C A∧（B∧C）＝（A∧B）∧C分配律：A∧（B∨C）＝A∧B∨A∧CA∨B∧C＝（A∨B）∧（A∨C）吸收律：A∧B∨A∧┓B＝A

（A∨B）∧（A∨┓B）＝A 狄－摩根定律：┓（A∨B）＝┓A∧┓B ┓（A∧B）＝┓A∨┓B双重否定律：┓┓A＝A2.2逻辑代数基础命题公式的等价律（续）2.2逻辑代数基础证明狄－摩根定律〖例2-26〗证明狄－摩根定律之一：┓（A∧B）＝┓A∨┓B。AB

A∧B┓（A∧B）┓A┓B┓A∨┓BTTTFFFFTFFTFTTFTFTTFTFFFTTTT2.2逻辑代数基础证明狄－摩根定律ABA∧B┓（A∧B）┓A┓B┓A∨┓BT逻辑代数的等价律零律：A＋0＝A A0＝0幺律：A＋1＝1 A1＝A幂等律：A＋A＝A AA＝A求补律：A＋Ā＝1 AĀ＝02.2逻辑代数基础逻辑代数的等价律2.2逻辑代数基础逻辑代数的等价律（续）BBBB(A+B)

A

(AB)交换律：A＋B＝B＋A AB＝BA结合律：A＋（B＋C）＝（A＋B）＋CA（BC）＝（AB）C分配律：A（B＋C）＝AB＋ACA＋BC＝（A＋B）（A＋C）吸收律：AB＋A＝A

（A＋B）（A＋）＝A 狄－摩根定律：＝Ā

＝Ā＋双重否定律：

＝A

A2.2逻辑代数基础逻辑代数的等价律（续）BBBB(A+B)A(AB)交换逻辑函数的化简〖例2-27〗试将逻辑函数F＝A＋ĀB化简。解：F＝A＋ĀB

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

（求补律）＝1 （求补律）BBBB

(AB)

(AB)2.2逻辑代数基础逻辑函数的化简〖例2-27〗试将逻辑函数F＝A＋ĀB化简。2.3计算机的基本结构与工作原理

辅助存储器内存储器运算器控制器输入设备输出设备

程序原始数据运算结果控制信息数据2.3计算机的基本结构与工作原理辅助存储器内存储器运运算器运算器：对二进制数进行运算的部件。它在控制器的控制下执行程序中的指令,完成各种算术运算、逻辑运算、比较运算、移位运算以及字符运算等。运算器的组成：算术逻辑部件（ALU）完成加、减、乘、除等四则运算以及与、或、非、移位等逻辑运算；寄存器用来暂存参加运算的操作数或中间结果，常用的寄存器有累加寄存器、暂存寄存器、标志寄存器和通用寄存器等。运算器的主要技术指标：运算速度，其单位是MIPS（百万指令/秒），通常是按照一定的频度执行各类指令的统计值。2.3计算机的基本结构与工作原理

运算器2.3计算机的基本结构与工作原理存储器存储器：用来存储数据和程序的部件。存储单位：“位”（bit）、“字节”（byte）、“字”和“字长”存储容量：存储器所包含的存储单元的总数，其单位为K

（1K＝210＝1024）。存储器的分类：内存储器：又称为主存储器，简称为内存或主存，用来存放现行程序的指令和数据。包括随机存取存储器（RAM）和只读存储器（ROM）等。外存储器：又称为辅助存储器，简称为外存或辅存，用来存放需要长期保存的信息。2.3计算机的基本结构与工作原理

存储器2.3计算机的基本结构与工作原理控制器控制器：是指挥计算机的各个部件按照指令的功能要求协调工作的部件。控制器的组成：程序计数器（PC）：用来对程序中的指令进行计数，使控制器能依次读取指令；指令寄存器（IR）：在指令执行期间暂时保存正在执行的指令。指令译码器（ID）：用来识别指令的功能，分析指令的操作要求。时序控制电路：用来生成时序信号，以协调在指令执行周期内各部件的工作。微操作控制电路：用来产生各种控制操作命令。2.3计算机的基本结构与工作原理

控制器2.3计算机的基本结构与工作原理输入/输出设备输入/输出设备：简称为I/O设备，是外部与计算机交换信息的渠道。输入设备：用于输入程序、数据、操作命令、图形、图像以及声音等信息。常用的输入设备有键盘、鼠标器、扫描仪、光笔、数字化仪以及语音输入装置等。输出设备：用于显示或打印程序、运算结果、文字、图形、图像等，也可以播放声音。常用的输出设备有显示器、打印机、XY绘图仪以及声音播放装置等。2.3计算机的基本结构与工作原理

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

计算机的指令系统2.3计算机的基本结构与工作原理计算机的工作原理见教材52页图2-6指令的执行过程2.3计算机的基本结构与工作原理

计算机的工作原理2.3计算机的基本结构与工作原理指令的执行过程取指令：即按照指令计数器中的地址，从内存储器中取出指令，并送往指令寄存器中。分析指令：即对指令寄存器中存放的指令进行分析，由操作码确定执行什么操作，由地址码确定操作数的地址。执行指令：即根据分析的结果，由控制器发出完成该操作所需要的一系列控制信息，去完成该指令所要求的操作。上述步骤完成后，指令计数器加1，为执行下一条指令做好准备。如果遇到转移指令，则将转移地址送入指令计数器。2.3计算机的基本结构与工作原理

指令的执行过程2.3计算机的基本结构与工作原理计算机组织与系统结构领域的一些主要技术1精简指令集技术在指令系统中仅包含（1）使用频率高的指令；（2）支持操作系统和高级语言的程序设计的指令。精简指令计算机（reducedinstructionset

computer,RISC)复杂指令计算机（complexinstructionset

computer,CISC)2高速缓冲存储技术(cache)为使慢速的RAM与快速的CPU相匹配，采用cache技术。方法：将CPU从RAM某一地址读取数据，自动将该地址相近的整批数据读入cache中。2.3计算机的基本结构与工作原理

计算机组织与系统结构领域的一些主要技术2.3计算机的基本结3虚拟存储技术利用硬盘的支持以小的物理内存模拟大的内存，从而程序能够使用整个内存地址空间的技术。4指令流水线技术

CPU可以在完成一条指令之前将开始执行另外一条指令，以加快计算机的处理速度。5并行处理技术把一个程序划分为多个能够并行地有单独处理器执行的进程，多个处理机协同地并行工作，达到甚至超过了巨型机的高性能。

并行计算机系统有：

SISD（单指令流但数据流）、SIMD、MISD、MIMD2.3计算机的基本结构与工作原理

3虚拟存储技术2.3计算机的基本结构与工作原理机器语言汇编语言高级语言结构化程序设计语言面向对象程序设计语言可视化程序设计语言人工智能程序设计语言学习语言是设计程序的基础2.4程序设计基础机器语言学习语言是设计程序的基础2.4程序设计基础2.4.1机器语言机器语言的特点

由二进制编码指令构成的语言。是一种依附于机器硬件的语言。机器语言程序可以直接执行。机器语言程序片段0001010101101100//把地址为01101100的内存单元中的数装入0101号寄存器0001011001101101//把地址为01101101的内存单元中的数装入0110号寄存器0101000001010110//把01101100和01101101中的数相加,结果存入0000号寄存器0011000001101110//把0000号寄存器中的数存入地址为01101110的内存单元中2.4.1机器语言机器语言的特点2.4.2汇编语言汇编语言的特点由助记符指令构成的语言。也是一种依附于机器硬件的语言。汇编语言源程序需要汇编后才能执行。汇编语言程序片段

MOVR5,X//把内存单元X中的数装入R5寄存器

ADDR5,Y//把R5中的数与Y单元中的数相加，结果存入R5

MOVZ,R5//把R5中的数存入Z单元中

2.4.2汇编语言汇编语言的特点2.4.3高级语言高级语言的特点

由自然语言和数学公式表示的语言。是一种独立于机器硬件的语言。高级语言程序需要编译后才能执行。高级语言程序片段

Z=X+Y

//把内存单元X中的数与Y中的数相加，结果存入Z单元

2.4.3高级语言高级语言的特点2.4.3高级语言常用高级语言

FORTRAN语言FORTRAN是FORmulaTRANslator（公式翻译器）的缩写。主要用于复杂的科学计算领域。ALGOL语言ALGOL是ALGOrithmLanguage（算法语言）的缩写。主要用于数学与科学计算。2.4.3高级语言常用高级语言2.4.3高级语言常用高级语言

COBOL语言

COBOL是COmmonBusiness-OrientedLanguage（面向商业的通用语言）的缩写。主要用于企业管理和事务处理。BASIC语言

BASIC是Beginner’sAll-purposeSymbolicInstructionCode（初学者通用符号指令码）的缩写。主要用于初学者和较小规模的程序开发。2.4.3高级语言常用高级语言2.4.4结构化程序设计语言早期程序设计方法的不足注重功能的实现/注重内存的节省/注重执行效率的提高。不注重程序结构的清晰性。不注重程序的可理解性和可修改性。结构化程序设计语言的特点

注重程序结构的清晰性。注重程序的可理解性和可修改性。采用模块化程序设计方法。2.4.4结构化程序设计语言早期程序设计方法的不足结构化程序设计结构化程序设计：采用自顶向下逐步求精的设计方法和单入口单出口的控制成分（顺序、分支和循环）。TFTF条件AAB（a）顺序结构（b）选择型分支结构（c）循环结构AB条件2.4.4结构化程序设计语言结构化程序设计TFTF条件AAB（a良好的程序设计风格标识符：按意命名、保留字用大写字母、使用统一的缩写规则。表达式：使用括号、使用库函数、条件化简、函数与过程模块化：模块的独立性（高内聚、低耦合）、模块的规模适中。程序行的排列格式：排列格式美观、层次分明、使用统一的缩进格式，同一嵌套深度并列的语句对齐。注释：添加必要的注释，以说明程序、过程和语句等的功能及注意事项。2.4.4结构化程序设计语言良好的程序设计风格2.4.4结构化程序设计语言2.4.4结构化程序设计语言常用结构化程序设计语言

PASCAL语言

是在ALGOL语言的基础上发展起来的。以法国著名科学家帕斯卡的名字命名。严格的语法格式与结构化形式。C语言

是在ALGOL60语言的基础上发展起来的。兼具低级语言和高级语言的特点。是最为流行的程序设计语言之一。2.4.4结构化程序设计语言常用结构化程序设计语言2.4.5面向对象程序设计语言结构化程序设计方法的不足

面向过程的设计方法与人们习惯的思维方式仍然存在一定的距离，所以很难自然、准确地反映真实世界，因而用编写出来的程序，特别是规模比较大的程序，其质量是难以保证的。强调了要实现功能的操作方法（模块），而被操作的数据（变量）处于实现功能的从属地位，即程序模块和数据结构是松散地耦合在一起，当程序复杂度较高时，容易出错，而且错误难以查找和修改。2.4.5面向对象程序设计语言结构化程序设计方法的不足2.4.5面向对象程序设计语言面向对象程序设计语言的特点

将问题分解为对象。对象将自己的属性和方法封装成一个整体，供程序设计者使用。对象之间的相互作用则通过消息传递来实现。使人们对复杂系统的认识过程与程序设计过程尽可能一致。2.4.5面向对象程序设计语言面向对象程序设计语言的特点2.4.5面向对象程序设计语言常用面向对象程序设计语言

Simula67

发布于1967年，是面向对象语言的鼻祖。C++

发布于1983年，是在C语言的基础上发展起来的。C++是得到广泛应用的一种面向对象语言。目前常用的版本有VisualC++,C#,VisualC++.Net等。Java发布于1995年，适合于网络程序设计。也是目前得到广泛应用的一种面向对象程序设计语言。2.4.5面向对象程序设计语言常用面向对象程序设计语言2.4.6可视化程序设计语言可视化程序设计语言的特点

以图形化的编程方式将面向对象技术的特性体现出来。使开发软件这一原本枯燥、难以理解的工作变得相对轻松快捷。常用可视化程序设计语言VisualC++功能强大，比较适合专业人员使用。VisualBasic易于学习和掌握，比较适合非专业人员和初学者使用。2.4.6可视化程序设计语言可视化程序设计语言的特点2.4.7人工智能程序设计语言人工智能程序设计语言的特点

适合于知识表示和逻辑推理。

常用人工智能程序设计语言LISP

LISP是LIStProcessing（表处理）的缩写。可以解决人工智能中的符号处理问题。

PROLOG

是PROgramminginLOGic（逻辑程序设计）的缩写。自动实现模式匹配、自动回溯这两种人工智能中常用的基本操作。2.4.7人工智能程序设计语言人工智能程序设计语言的特点良好的程序设计风格标识符：按意命名、保留字用大写字母、使用统一的缩写规则。表达式：使用括号、使用库函数、条件化简、函数与过程模块化：模块的独立性（高内聚、低耦合）、模块的规模适中。程序行的排列格式：排列格式美观、层次分明、使用统一的缩进格式，同一嵌套深度并列的语句对齐。注释：添加必要的注释，以说明程序、过程和语句等的功能及注意事项。2.4程序设计基础良好的程序设计风格2.4程序设计基础算法算法：是由一系列规则组成的过程，这些规则确定了一个操作的顺序，以便能在有限步骤内得到特定问题的解。算法的性质：确定性通用性有限性算法的描述工具：自然语言流程图决策表算法描述语言2.5算法基础算法2.5算法基础欧几里德算法（Euclid’sAlgorithm）例2-32〗若给定两个正整数m和n，试写出求它们的最大公因子的算法。 该算法的步骤用文字表述如下： 第1步：读入两个正整数m和n（设m>n）。 第2步：求m和n的余数r＝mod（m,n）。 第3步：用n的值取代m，用r的值取代n。 第4步：判别r的值是否为零，如果r＝0，则m为最大公因子；否则返回第2步。 第5步：输出m的值，即为最大公因子。2.5算法基础欧几里德算法（Euclid’sAlgorithm）2.52.5算法基础欧几里德算法（算法描述语言表示）PROCEDUREEuclid；

BEGINREAD（m,n）;REPEAT;r:=MOD（m,n）;m:=n;n:=r;UNTILr＝0; WRITE(m)

END2.5算法基础欧几里德算法（算法描述语言表示）欧几里德算法（流程图表示）

m=n

BEGIN

READm，n

r=mod(m,n)n=rWRITEmr≠0ENDYN2.5算法基础欧几里德算法（流程图表示）m=nBEGIN线性表线性表：是n个数据元素的有限序列。线性表的运算：设L为一个线性表置空表SETNULL（L）求表的长度LENGTH（L）取表元素GET（L，i）在表中查找特定元素LOCATE（L，x）插入新元素INSERT（L，i，b）删除表元素DELETE（L，i）线性表的存储结构：顺序存储结构链式存储结构2.6数据结构基础线性表2.6数据结构基础堆栈堆栈（stack）：是一种受限的线性表，即只能在表的一端（表尾）进行插入和删除操作。进栈和退栈操作按“后进先出”（LastInFirstOut，LIFO）的原则进行。堆栈的运算：设S为一个堆栈置空栈SETNULL（S）进栈PUSH（S，x）退栈POP（S）取栈顶元素TOP（S）判断堆栈是否为空EMPTY（S）堆栈的存储结构：顺序存储结构2.6数据结构基础堆栈2.6数据结构基础3.7本章小结队列队列（queue）：也是一种受限的线性表,只能在表的一端（队尾）进行插入，在表的另一端（队首）进行删除操作。进、出队列操作按“先进先出”（FirstInFirstOut，FIFO）的原则进行。队列的运算：设Q为一个队列置空队列SETNULL（Q）进入队列ADDQUEUE（Q，x）退出队列DELQUEUE（Q）取队首元素FRONTQUE（Q）判断队列是否为空EMPTY（Q）队列的存储结构：链式存储结构，一个链队列需要设置队首指针和队尾指针。3.7本章小结队列本章小结本章介绍了计算机的一些基本知识,包括:数制与码制、数的定点与浮点表示、信息的编码；逻辑代数与逻辑电路基础;计算机的基本结构与工作原理;程序设计语言、结构化程序设计、程序设计风格；以及算法与数据结构的基础知识。通过本章的学习，应掌握数据在计算机内部的表示形式及数制间的转换方法，理解逻辑代数、逻辑电路、计算机的结构、程序设计语言、结构化程序设计方法以及算法与数据结构的基本知识，为进一步学习本书的以下各章和后继课程打好基础。本章小结第2章计算机基础知识

2.1计算机的运算基础2.2命题逻辑与逻辑代数基础2.3计算机的基本结构与工作原理2.4程序设计基础2.5算法基础2.6数据结构基础2.7本章小结第2章计算机基础知识2.1计算机的运算基础基本要求：掌握数制间的转换方法以及数据在计算机内部的表示形式理解逻辑代数、计算机的工作原理、程序设计以及算法与数据结构的基本知识，为学习本书的以下各章和后续课程打好基础基本要求：计算机中的数制数值型数据的表示字符型数据的编码表示汉字的编码表示2.1计算机的运算基础计算机中的数制2.1计算机的运算基础2.1.1计算机中的数制不同数制的表示在计算机内部用二进制形式表示和存储数据。

人们习惯于用十进制记数。为了书写简单方便也使用八进制和十六进制。用加后缀或角标的形式区别不同进制数据。B—表示二进制数。O或Q—表示八进制数。D—表示十进制数（D可省略）。H—表示十六进制数。2.1.1计算机中的数制不同数制的表示2.1.1计算机中的数制二进制转换成其他进制二进制数转换成十进制数，按权展开相加即可。二进制数转换成八进制数时，以小数点为界，分别向左向右分成3位一组，不够3位补0，分完组后对应成八进制数即可。二进制数转换成十六进制数时，以小数点为界，分别向左向右分成4位一组，不够4位补0，分完组后对应成十六进制数即可。2.1.1计算机中的数制二进制转换成其他进制2.1.1计算机中的数制二进制转换成其他进制示例

(1011001.10111)2

=1×26+1×24+1×23+1×20+1×2-1+1×2-3+1×2-4+1×2-5=64+16+8+1+0.5+0.125+0.0625+0.03125+0.015625=(99.734375)10

(1011001.10111)2

=(001011001.101110)2=(131.56)8

(1011001.10111)2

=(01011001.10111000)2=(59.B8)162.1.1计算机中的数制二进制转换成其他进制示例2.1.1计算机中的数制其他进制转换成二进制十进制数转换成二进制数，先把十进制数分解成若干个数相加,每个数都是2的若干次幂，然后对应成二进制数。八进制数转换成二进制数时，每一个八进制位展开成3个二进制位即可。十六进制数转换成二进制数时，每一个十六进制位展开成4个二进制位即可。2.1.1计算机中的数制其他进制转换成二进制2.1.1数据表示其他进制转换成二进制示例

(98.75)10

=64+32+2+0.5+0.25=(1100010.11)2

(276.15)8=(010111110.001101)2=(10111110.001101)2

(3AC.1E)16

=(001110101100.00011110)2=(1110101100.0001111)22.1.1数据表示其他进制转换成二进制示例2.1.2数值型数据的表示无符号数据的表示按一定规则把无符号整数转换成二进制形式在计算机内部表示和存储。带符号数据的表示带符号数中的正负号及小数中的小数点都以二进制形式表示。需要考虑的因素机器数的范围。机器数的符号。机器数中小数点的位置。2.1.2数值型数据的表示无符号数据的表示2.1.2数值型数据的表示机器数的范围机器数的表示范围由CPU中的寄存器决定。对于无符号数，8位寄存器的表示范围是0～255，16位寄存器的表示范围是0～65535。对于带符号数，8位寄存器的表示范围是-128～+127，16位寄存器的表示范围是-32768～+32767。2.1.2数值型数据的表示机器数的范围2.1.2数值型数据的表示机器数的符号在计算机内部，任何数据（符号）都只能用二进制的两个数码0和1来表示。带符号数的表示，除了用0和1的组合来表示数值的绝对值大小外，其正负号也必须用0和1来表示。最高位为符号位，并用0表示正，用1表示负。有原码/反码/补码等表示形式。2.1.2数值型数据的表示机器数的符号2.1.2数值型数据的表示机器数示例无符号十进制数57的机器数表示。57的二进制形式为111001。[+57]原=00111001（正数的原码最高位为0，数值位补足7位）[-57]原=

10111001（负数的原码最高位为1，数值位补足7位）

[+57]反=

00111001（正数的反码与其原码相同）

[-57]反=

11000110（负数的反码，符号位不变，数值位为原码数值位取反）[+57]补=00111001（正数的补码与其原码相同）[-57]补=11000111（负数的补码在其反码的末尾加1）2.1.2数值型数据的表示机器数示例2.1.2数值型数据的表示机器数中小数点的位置定点数（定点整数/定点小数）浮点数0000000110000011h数值部分符号位小数点位置11010000000000

00

h数值部分符号位小数点位置2.1.2数值型数据的表示机器数中小数点的位置0000002.1.3字符型数据的编码表示基本含义对于字符型数据，没有相应的转换规则可以使用。需要人们规定出每个字符对应的二进制编码形式。常用的字符型数据编码ASCII码（美国标准信息交换码的简称）使用一个字节表示一个ASCII码字符。主要用于小型机和微型机。EBCDIC码（扩展BCD码）BCD码又称二—十进制编码，用二进制编码形式表示十进制数。在BCD码的基础上，又增加了一些符号和英文字母的表示。主要用于超级计算机和大型计算机。2.1.3字符型数据的编码表示基本含义BCD码与ASCII码BCD码：是一种二－十进制的编码，使用四位二进制数表示一位十进制数。十进制数与BCD码之间的转换：可按位（或四位二进制数组）直接进行。ASCII(AmericanStandardsCommitteeofIformation)码:是由美国信息交换标准委员会制定的、国际上使用最广泛的字符编码方案。ASCII码的编码方案：采用7位二进制数表示一个字符，把7位二进制数分为高三位（b7b6b5）和低四位（b4b3b2b1）7位ASCII编码表：如表2-5所示，利用该表可以查找数字、运算符、标点符号以及控制符等字符与ASCII码之间的对应关系。BCD码与ASCII码数据校验码奇偶校验码：在表示数据的N位代码中增加一位奇偶校验位，使N＋1位中“1”的个数为奇数（奇校验）或偶数（偶校验）。海明校验码：在有效信息代码中增加校验位，用来校验代码中“1”的个数是奇数（奇校验）还是偶数（偶校验），通过奇偶校验可以发现代码传输过程中的错误并自动校正。应用：用于计算机各部件之间信息传输以及计算机网络的信息传输。数据校验码2.1.4汉字的编码表示与汉字处理有关的几种编码汉字输入码数字码：国标区位码。拼音码：全拼输入法/紫光输入法/智能ABC输入法。字形码：五笔字型编码。汉字机内码（一个汉字占用2个字节，最高位置1）。计算机内部使用的汉字代码。汉字交换码：在不同信息处理系统之间进行信息交换。国标码。BIG5码。汉字字形码（用于显示和打印）2.1.4汉字的编码表示与汉字处理有关的几种编码2.2逻辑代数基础命题命题公式命题公式的等价律逻辑函数的化简

2.2逻辑代数基础命题命题逻辑基础命题：有具体意义且能够判断真假的陈述句。命题的真值:命题所具有的值“真”(true，简记为T)或“假”（false,简记为F）称为其真值。命题标识符：表示命题的符号，该标识符称为命题常量。原子命题：不能分解为更为简单的陈述句的命题；复合命题：将原子命题用连接词和标点符号复合而成的命题。2.2逻辑代数基础命题逻辑基础2.2逻辑代数基础连接词“与”（∧）“与”(∧):两个命题A和B的“与”(又称为A和B的“合取”)是一个复合命题，记为A∧B。当且仅当A和B同时为真时A∧B为真，在其他的情况下A∧B的真值均为假。

A∧B的真值表:

A

B

A∧B

T

T

T

T

F

F

F

T

F

F

F

F2.2逻辑代数基础连接词“与”（∧）

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

A

B

A∨B

T

T

T

T

F

T

F

T

T

F

F

F2.2逻辑代数基础连接词“或”（∨）A B连接词“非”（┑）“非”（┑）：命题A的“非”（又称为A的“否定”）是一个复合命题，记为┑A。若A为真，则┑A为假；若A为假，则┑A为真。┑A的真值表：

A┑ATFFT2.2逻辑代数基础连接词“非”（┑）A┑ATFFT2.2逻辑代数基础连接词“异或”（⊕）“异或”（⊕）：两个命题的A和B的“异或”（又称为A和B的“不可兼或”）是一个复合命题，记为A⊕B。当且仅当A和B同时为真或者同时为假时A⊕B为假，在其他的情况下A⊕B的真值为真。A⊕B的真值表：

A

B

A⊕B

T

T

F

T

F

T

F

T

T

F

F

F2.2逻辑代数基础连接词“异或”（⊕）A B连接词“条件”（→）“条件”（→）：两个命题的A和B的“条件”是一个复合命题，记为

A→B,读作“如果A，则B”。当且仅当A的真值为真，B的真值为假时，A→B为假，在其他的情况下A→B的真值均为真。A→B的真值表：

A

B

A→B

T

T

T

T

F

F

F

T

T

F

F

T2.2逻辑代数基础连接词“条件”（→）A B连接词“双条件”()

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

A

B

AB

T

T

T

T

F

F

F

T

T

F

F

T2.2逻辑代数基础连接词“双条件”()

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

F

FT

FTT

FT

F

F

F

F

F

F2.2逻辑代数基础命题公式AB┑（A→B）A∧┑BTTFFTFTT命题公式的等价律其中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＝TA∧┓A＝F交换律：A∨B＝B∨AA∧B＝B∧A2.2逻辑代数基础命题公式的等价律2.2逻辑代数基础命题公式的等价律（续）结合律：A∨（B∨C）＝（A∨B）∨C A∧（B∧C）＝（A∧B）∧C分配律：A∧（B∨C）＝A∧B∨A∧CA∨B∧C＝（A∨B）∧（A∨C）吸收律：A∧B∨A∧┓B＝A

（A∨B）∧（A∨┓B）＝A 狄－摩根定律：┓（A∨B）＝┓A∧┓B ┓（A∧B）＝┓A∨┓B双重否定律：┓┓A＝A2.2逻辑代数基础命题公式的等价律（续）2.2逻辑代数基础证明狄－摩根定律〖例2-26〗证明狄－摩根定律之一：┓（A∧B）＝┓A∨┓B。AB

A∧B┓（A∧B）┓A┓B┓A∨┓BTTTFFFFTFFTFTTFTFTTFTFFFTTTT2.2逻辑代数基础证明狄－摩根定律ABA∧B┓（A∧B）┓A┓B┓A∨┓BT逻辑代数的等价律零律：A＋0＝A A0＝0幺律：A＋1＝1 A1＝A幂等律：A＋A＝A AA＝A求补律：A＋Ā＝1 AĀ＝02.2逻辑代数基础逻辑代数的等价律2.2逻辑代数基础逻辑代数的等价律（续）BBBB(A+B)

A

(AB)交换律：A＋B＝B＋A AB＝BA结合律：A＋（B＋C）＝（A＋B）＋CA（BC）＝（AB）C分配律：A（B＋C）＝AB＋ACA＋BC＝（A＋B）（A＋C）吸收律：AB＋A＝A

（A＋B）（A＋）＝A 狄－摩根定律：＝Ā

＝Ā＋双重否定律：

＝A

A2.2逻辑代数基础逻辑代数的等价律（续）BBBB(A+B)A(AB)交换逻辑函数的化简〖例2-27〗试将逻辑函数F＝A＋ĀB化简。解：F＝A＋ĀB

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

（求补律）＝1 （求补律）BBBB

(AB)

(AB)2.2逻辑代数基础逻辑函数的化简〖例2-27〗试将逻辑函数F＝A＋ĀB化简。2.3计算机的基本结构与工作原理

辅助存储器内存储器运算器控制器输入设备输出设备

程序原始数据运算结果控制信息数据2.3计算机的基本结构与工作原理辅助存储器内存储器运运算器运算器：对二进制数进行运算的部件。它在控制器的控制下执行程序中的指令,完成各种算术运算、逻辑运算、比较运算、移位运算以及字符运算等。运算器的组成：算术逻辑部件（ALU）完成加、减、乘、除等四则运算以及与、或、非、移位等逻辑运算；寄存器用来暂存参加运算的操作数或中间结果，常用的寄存器有累加寄存器、暂存寄存器、标志寄存器和通用寄存器等。运算器的主要技术指标：运算速度，其单位是MIPS（百万指令/秒），通常是按照一定的频度执行各类指令的统计值。2.3计算机的基本结构与工作原理

运算器2.3计算机的基本结构与工作原理存储器存储器：用来存储数据和程序的部件。存储单位：“位”（bit）、“字节”（byte）、“字”和“字长”存储容量：存储器所包含的存储单元的总数，其单位为K

（1K＝210＝1024）。存储器的分类：内存储器：又称为主存储器，简称为内存或主存，用来存放现行程序的指令和数据。包括随机存取存储器（RAM）和只读存储器（ROM）等。外存储器：又称为辅助存储器，简称为外存或辅存，用来存放需要长期保存的信息。2.3计算机的基本结构与工作原理

存储器2.3计算机的基本结构与工作原理控制器控制器：是指挥计算机的各个部件按照指令的功能要求协调工作的部件。控制器的组成：程序计数器（PC）：用来对程序中的指令进行计数，使控制器能依次读取指令；指令寄存器（IR）：在指令执行期间暂时保存正在执行的指令。指令译码器（ID）：用来识别指令的功能，分析指令的操作要求。时序控制电路：用来生成时序信号，以协调在指令执行周期内各部件的工作。微操作控制电路：用来产生各种控制操作命令。2.3计算机的基本结构与工作原理

控制器2.3计算机的基本结构与工作原理输入/输出设备输入/输出设备：简称为I/O设备，是外部与计算机交换信息的渠道。输入设备：用于输入程序、数据、操作命令、图形、图像以及声音等信息。常用的输入设备有键盘、鼠标器、扫描仪、光笔、数字化仪以及语音输入装置等。输出设备：用于显示或打印程序、运算结果、文字、图形、图像等，也可以播放声音。常用的输出设备有显示器、打印机、XY绘图仪以及声音播放装置等。2.3计算机的基本结构与工作原理

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

计算机的指令系统2.3计算机的基本结构与工作原理计算机的工作原理见教材52页图2-6指令的执行过程2.3计算机的基本结构与工作原理

计算机的工作原理2.3计算机的基本结构与工作原理指令的执行过程取指令：即按照指令计数器中的地址，从内存储器中取出指令，并送往指令寄存器中。分析指令：即对指令寄存器中存放的指令进行分析，由操作码确定执行什么操作，由地址码确定操作数的地址。执行指令：即根据分析的结果，由控制器发出完成该操作所需要的一系列控制信息，去完成该指令所要求的操作。上述步骤完成后，指令计数器加1，为执行下一条指令做好准备。如果遇到转移指令，则将转移地址送入指令计数器。2.3计算机的基本结构与工作原理

指令的执行过程2.3计算机的基本结构与工作原理计算机组织与系统结构领域的一些主要技术1精简指令集技术在指令系统中仅包含（1）使用频率高的指令；（2）支持操作系统和高级语言的程序设计的指令。精简指令计算机（reducedinstructionset

computer,RISC)复杂指令计算机（complexinstructionset

computer,CISC)2高速缓冲存储技术(cache)为使慢速的RAM与快速的CPU相匹配，采用cache技术。方法：将CPU从RAM某一地址读取数据，自动将该地址相近的整批数据读入cache中。2.3计算机的基本结构与工作原理

计算机组织与系统结构领域的一些主要技术2.3计算机的基本结3虚拟存储技术利用硬盘的支持以小的物理内存模拟大的内存，从而程序能够使用整个内存地址空间的技术。4指令流水线技术

CPU可以在完成一条指令之前将开始执行另外一条指令，以加快计算机的处理速度。5并行处理技术把一个程序划分为多个能够并行地有单独处理器执行的进程，多个处理机协同地并行工作，达到甚至超过了巨型机的高性能。

并行计算机系统有：

SISD（单指令流但数据流）、SIMD、MISD、MIMD2.3计算机的基本结构与工作原理

3虚拟存储技术2.3计算机的基本结构与工作原理机器语言汇编语言高级语言结构化程序设计语言面向对象程序设计语言可视化程序设计语言人工智能程序设计语言学习语言是设计程序的基础2.4程序设计基础机器语言学习语言是设计程序的基础2.4程序设计基础2.4.1机器语言机器语言的特点

由二进制编码指令构成的语言。是一种依附于机器硬件的语言。机器语言程序可以直接执行。机器语言程序片段0001010101101100//把地址为01101100的内存单元中的数装入0101号寄存器0001011001101101//把地址为01101101的内存单元中的数装入0110号寄存器0101000001010110//把01101100和01101101中的数相加,结果存入0000号寄存器0011000001101110//把0000号寄存器中的数存入地址为01101110的内存单元中2.4.1机器语言机器语言的特点2.4.2汇编语言汇编语言的特点由助记符指令构成的语言。也是一种依附于机器硬件的语言。汇编语言源程序需要汇编后才能执行。汇编语言程序片段

MOVR5,X//把内存单元X中的数装入R5寄存器

ADDR5,Y//把R5中的数与Y单元中的数相加，结果存入R5

MOVZ,R5//把R5中的数存入Z单元中

2.4.2汇编语言汇编语言的特点2.4.3高级语言高级语言的特点

由自然语言和数学公式表示的语言。是一种独立于机器硬件的语言。高级语言程序需要编译后才能执行。高级语言程序片段

Z=X+Y

//把内存单元X中的数与Y中的数相加，结果存入Z单元

2.4.3高级语言高级语言的特点2.4.3高级语言常用高级语言

FORTRAN语言FORTRAN是FORmulaTRANslator（公式翻译器）的缩写。主要用于复杂的科学计算领域。ALGOL语言ALGOL是ALGOrithmLanguage（算法语言）的缩写。主要用于数学与科学计算。2.4.3高级语言常用高级语言2.4.3高级语言常用高级语言

COBOL语言

COBOL是COmmonBusiness-OrientedLanguage（面向商业的通用语言）的缩写。主要用于企业管理和事务处理。BASIC语言

BASIC是Beginner’sAll-purposeSymbolicInstructionCode（初学者通用符号指令码）的缩写。主要用于初学者和较小规模的程序开发。2.4.3高级语言常用高级语言2.4.4结构化程序设计语言早期程序设计方法的不足注重功能的实现/注重内存的节省/注重执行效率的提高。不注重程序结构的清晰性。不注重程序的可理解性和可修改性。结构化程序设计语言的特点

注重程序结构的清晰性。注重程序的可理解性和可修改性。采用模块化程序设计方法。2.4.4结构化程序设计语言早期程序设计方法的不足结构化程序设计结构化程序设计：采用自顶向下逐步求精的设计方法和单入口单出口的控制成分（顺序、分支和循环）。TFTF条件AAB（a）顺序结构（b）选择型分支结构（c）循环结构AB条件2.4.4结构化程序设计语言结构化程序设计TFTF条件AAB（a良好的程序设计风格标识符：按意命名、保留字用大写字母、使用统一的缩写规则。表达式：使用括号、使用库函数、条件化简、函数与过程模块化：模块的独立性（高内聚、低耦合）、模块的规模适中。程序行的排列格式：排列格式美观、层次分明、使用统一的缩进格式，同一嵌套深度并列的语句对齐。注释：添加必要的注释，以说明程序、过程和语句等的功能及注意事项。2.4.4结构化程序设计语言良好的程序设计风格2.4.4结构化程序设计语言2.4.4结构化程序设计语言常用结构化程序设计语言

PASCAL语言

是在ALGOL语言的基础上发展起来的。以法国著名科学家帕斯卡的名字命名。严格的语法格式与结构化形式。C语