1、2.1 逻辑代数2.2 数字电路2.3 内存储器2.4 中央处理器2.5 外部设备第二章 计算机硬件组成与工作原理计算机系统包括硬件和软件两部分，如图2-1所示。计算机出现至今，其系统发展迅速，但是基本硬件组成与工作原理仍然是冯诺依曼型计算机。冯诺依曼型计算机具有如下特点：(1)包括中央处理器(运算器、控制器)、存储器(内存储器、外存储器)、输入设备、输出设备；(2)符号0和1表示数据；(3)存储程序：程序存储在内存储器中，中央处理器按照存储的程序有条不紊地执行。计算机基本硬件组成如图2-2所示。2.1 逻辑代数逻辑代数在逻辑值集合T(真)，F(假)上，定义了三个基本逻辑运算：(逻辑与)、(逻
2、辑或)、(逻辑非)，记为。其它逻辑运算都可以用这三个基本逻辑运算表达。逻辑与也称为逻辑乘、合取，使用符号、AND、&；逻辑或也称为逻辑加、析取，使用符号+、OR、|；逻辑非也称为否定，使用符号、NOT、!。如表2-1所示，逻辑变量是取值只能为逻辑值的变量，逻辑表达式是由逻辑变量或逻辑变量与逻辑运算构成的。真值表是逻辑表达式的所有可能取值情况的罗列，如表2-1所示。采用的计数规则是低位向高位逢二进一；基数为2，第i位的位权为2i(整数部分最低位为第0位)。例1-2 (1100.011)2=123+122+12-2+12-3计算机学科也采用八进制数(Octal)和十六进制数(Hexadecimal
3、)，但是在计算机中只采用二进制，引入八进制和十六进制是因为它们比二进制简洁，而且二进制与它们的转换比与十进制的转换简单。各进制数的特点如表1-1所示。2.2 数 字 电 路计算机采用数字电路，数字电路的工作信号是数字信号，数字信号只有两个数字符号：1和0。事实上，1和0只是电路的二值状态的表示，如果考虑电平的高和低，则可以用1和0表示。同理，逻辑值的真和假也可以用1和0表示，这与用T和F表示没有本质区别。总而言之，1和0可以表示任何的二值状态，1和0统一了电路状态与逻辑值，从而可以设计电路实现逻辑运算。实现逻辑与、逻辑或、逻辑非运算的电路分别称为与门、或门、非门，它们的电路符号如图2-3所示。
4、类似地，其它逻辑运算的门电路可以用这三个基本门电路组合实现，当然，也可以重新设计实现。进一步，可以用门电路组合实现计算机的其它功能部件。下面将具体介绍非门以及用门电路组合实现的触发器。2.2.1 非门MOS晶体管如图2-4所示，包括栅极(G)、漏极(D)、源极(S)。用MOS晶体管实现的非门如图2-5所示。MOS晶体管是由G的电平高低控制D、S之间处于接通还是断开状态的电子开关，当G为高电平(1)时，D与S之间导通(接通状态)；当G为低电平(0)时，D与S之间截止(断开状态)。图2-5所示的非门由两个MOS晶体管V1和V2构成，其中V2是工作管(开关作用)，而V1做V2的负载管，并总是处于导通
5、状态。A是输入端，F是输出端。当A输入1(高电平)时，V2导通，F输出0(低电平)；当A输入0(低电平)时，V2截止，F输出1(高电平)。2.2.2 触发器触发器是可以接收并保持所接收的1或0的电路，是内存储器的基本存储元件。基本触发器如图2-6所示，左边和右边是一个与门和一个非门构成的与非门，两个与非门的输出互相反馈到对方的输入，触发器的输入端是R和S，输出端是Q和 。Q2.3 内 存 储 器根据存取方式，内存储器(Memory，也称主存储器，简称内存、主存)可以分为随机存取存储器(Random Access Memory，RAM)和只读存储器(Read Only Memory，ROM)。通
6、常所说的内存是指RAM，它是内存的主体，是计算机的信息交流中心，它可以在指定位置(内存地址)存入(写入)或者取出(读出)数据。RAM由类似触发器的存储元件组成，其存取速度快，但是只能临时存储数据，一旦断电，数据将消失。内存基本组成如图2-7所示，包括存储体、地址电路、数据电路、读/写控制电路。2.4 中央处理器2.4.1 指令系统不同计算机系统，归纳的基本操作可以不同，从而编码表示的机器指令也可以不同，即指令系统就可以不同。对于同一程序，如果两台计算机的执行结果相同，则称它们在机器指令级别兼容。事实上，一旦计算机精心归纳一些基本操作，实现了其基本能力，若再增加基本操作，则只能增加其便利性等能力
7、，而不能增加其基本能力。因此，在设计指令系统时，导致了两个方向，一个是精简指令集计算机(Reduced Instruction Set Computer，RISC)，RISC中只保留了最简单、最常用的指令，这样设计的计算机效率高且速度快；另一个是复杂指令集计算机(Complex Instruction Set Computer，CISC)，CISC中一些可完成复杂任务的单个指令所能实现的任务，需要多个RISC指令才能实现，因此这样设计的计算机更容易编程。不管是RISC还是CISC，归纳和编码基本操作的基本方法都是类似的，即所有基本操作都包括功能信息和数据信息。功能信息告知计算机，要执行什么操作
8、；数据信息告知计算机，操作的数据来自何处，操作的结果去向何处。当编码表示基本操作时，功能信息和数据信息分别编码，编码表示的功能信息称为操作码，编码表示的数据信息称为操作数，即机器指令包括操作码和操作数。例2-1 设两个加数分别存储于地址为X和Y的内存单元中，两个加数相加，将和存于地址为Z的内存单元中。首先，从上述问题中归纳基本操作，给出两个方案。1方案一方案一将整个问题直接作为基本操作，其功能信息是相加，数据信息是两个加数分别来自地址为X和Y的内存单元，和存于地址为Z的内存单元。当编码表示基本操作时，功能信息(操作码)的编码长度l由功能不同的基本操作的数目m决定，即l=lbm；数据信息(操作数
9、)的编码可以直接使用内存地址。这样，可以如图2-8所示安排基本操作的各个信息。在方案一中，如果内存地址的编码长度为n，则操作数的编码长度为3n，机器指令比较长。2方案二方案二引入寄存器，将这个问题分解为更小的基本操作。寄存器是中央处理器中用于临时存储数据的部件。每个寄存器有一个编号，称为寄存器地址。方案二将这个问题分解为下列三个基本操作：取数操作：从地址为X的内存单元中取出加数1，存于地址为A的寄存器中；加法操作：地址为A的寄存器中的加数1与地址为Y的内存单元中的加数2相加，和存于地址为A的寄存器中；存数操作：从地址为A的寄存器中取出和，存于地址为Z的内存单元中。可以看到，取数操作和存数操作进
10、行数据传输，真正进行两个加数相加的是加法操作。加法操作的功能信息是相加，数据信息是两个加数分别来自地址为A的寄存器和地址为Y的内存单元，和存于地址为A的寄存器中。当编码表示加法操作时，功能信息(操作码)的编码长度l由功能不同的基本操作的数目m决定，即l=lbm；数据信息(操作数)的编码可以直接使用寄存器地址和内存地址，而且加数1与和采用同一寄存器，只需表示一次。这样，可以如图2-9所示安排基本操作的各个信息。在方案二中，如果内存地址的编码长度为n，寄存器地址的编码长度为r，则操作数的编码长度为n+r。由于寄存器数量很少，一般为几个，远远少于内存单元数量，因此，r小于n，相对于方案一，方案二的机
11、器指令比较短。现在，采用方案二，编码表示基本操作得到机器指令。假设功能不同的基本操作(机器指令)的数目为16，寄存器的数目为4，内存单元的数目为1K，则操作码的编码长度至少为4位，寄存器地址至少为2位，内存地址至少为10位，机器指令长度至少为16位。如果机器指令采用16位，则机器指令格式如图2-10所示。部分机器指令的功能及为它们指派的操作码如表2-3所示。例2-1仅仅介绍了设计指令系统的基本方法，真正指令系统的设计要比这个例子复杂。根据机器指令功能，可将其分为四类：(1)数据处理类。例如，加、减、乘、除等算术运算，与、或、非等逻辑运算，左移、右移等移位运算等。(2)数据传送类。例如，中央处理
12、器与内存之间的取数据、存数据操作，主机与外部设备之间的数据输入、数据输出操作等。(3)程序控制类。例如，无条件转移与条件转移等。(4)CPU状态管理类。例如，结束等。根据机器指令格式，可以将其分为四类(OP代表操作码，X、Y、Z代表内存地址，A代表寄存器地址)：(1)三地址：有三个内存地址，指令格式为(OP,X,Y,Z)，可以完成(X)OP(Y)Z的操作。(2)二地址：有两个内存地址，指令格式为(OP,X,Y)，可以完成(X)OP(Y)X的操作。(3)单地址：有一个内存地址，指令格式为(OP,A,X)，可以完成(A)OP(X)A的操作。(4)零地址：没有内存地址，指令格式为(OP)，可以完成诸
13、如结束等操作。此外，真正指令系统的操作数也有多种编码方法，称为机器指令寻址方法。寻址方式主要包括以下五种：(1)立即寻址方式：形式地址的数值不是地址，而是数据。(2)直接寻址方式：形式地址的数值是数据的有效地址。(3)间接寻址方式：形式地址的数值是数据的有效地址的地址，即根据形式地址找到一个内存单元，这个内存单元中存储了数据的有效地址，再根据该有效地址找到另一个内存单元，这个内存单元中存储了数据。(4)相对寻址方式：程序计数器的数值与形式地址的数值的和是数据的有效地址，即根据程序计数器的数值与形式地址的数值计算数据的有效地址，再根据有效地址找到一个内存单元，这个内存单元中存储了数据。这种方式主
14、要用于转移指令。(5)变址寻址方式：变址寄存器的数值与形式地址的数值的和是数据的有效地址，即根据变址寄存器的数值与形式地址的数值计算数据的有效地址，再根据有效地址找到一个内存单元，这个内存单元中存储了数据。这种方式可以扩大寻址范围。程序计数器和变址寄存器是中央处理器中用于存储内存地址的寄存器，程序计数器用于存储指令地址，而变址寄存器用于存储数据地址。2.4.2 中央处理器中央处理器(Central Processing Unit，CPU)可有条不紊地执行存储在内存中的机器指令形式的程序，完成信息处理，其执行过程如图2-11所示。当用户发出运行某程序的命令后，CPU开始执行程序，先从内存中取出第
15、一条指令进行分析并执行，再从内存中取出下一条指令进行分析并执行，这样重复，直至遇到结束指令，CPU结束程序运行。CPU的基本组成如图2-12所示，主要包括运算器和控制器。运算器用于完成算术运算和逻辑运算，主要包括算术逻辑单元和通用寄存器。数据从内存取出后送至通用寄存器或者算术逻辑单元进行算术运算或者逻辑运算，结果存于通用寄存器后送至内存。控制器用于控制计算机工作，主要包括程序计数器、指令寄存器、指令译码器和控制部件。程序计数器存储和计算下一条指令的内存地址。程序第一条指令的内存地址称为程序首地址。首先，运行程序命令将程序首地址赋予程序计数器，根据程序首地址就可以取出第一条指令。当指令取出后，程
16、序计数器自动加1计算得到下一条指令的内存地址。如果程序顺序执行，则根据这个地址就可以取出下一条指令；如果程序非顺序执行，则转移指令会将转移地址重新赋予程序计数器，从而可以根据新地址取出下一条指令。需要强调，程序计数器的自动加1不是加数值1，而是加一条机器指令长度，例如，如果一条指令长度为一个内存单元，则加1就是加数值(1)2；如果一条指令长度为两个内存单元，则加1就是加数值(10)2。指令从内存取出后送至指令寄存器，完成取指令；指令译码器分析指令的操作码，完成分析指令；根据分析结果，控制部件发出控制信号，完成执行指令。在执行指令中，如果从内存取数据，则指令的操作数指示了数据的内存地址。数据寄存
17、器用于暂时存放从内存读出的指令或数据以及向内存写入的数据。若是从内存读出的指令，则送至指令寄存器；若是数据，则送至通用寄存器或者算术逻辑单元。地址寄存器用于暂时存放即将访问的指令或数据在内存中的地址，根据这个内存地址，可以从相应内存单元中取出指令或数据。2.5 外 部 设 备2.5.1 输入设备计算机通过输入设备输入数据。输入设备种类很多，例如，键盘、鼠标、麦克风、摄像头、触摸屏、条形码阅读器、扫描仪等，可以根据需要选择配置。键盘和鼠标是基本输入设备。2.5.2 输出设备计算机通过输出设备输出数据。输出设备种类也很多，例如，显示器、音箱(耳机)、投影仪、打印机、绘图仪等，也可以根据需要选择配置
18、。显示器是基本输出设备。2.5.3 外存储器外存储器本质上是存储设备，用于长期存储大量数据，计算机可以在其上输出(写、存)数据，也可以从其上输入(读、取)数据，因此，外存储器也是特殊的输入/输出设备。外存储器种类也很多，例如，硬盘、光盘、移动硬盘、U盘等。硬盘是基本外存储器。3.1 处理器管理3.2 存 储 管 理3.3 设备管理3.4 文件管理第三章 操 作 系 统3.1 处理器管理3.1.1 程序的并发执行处理器管理的任务是当多道程序并发执行时，合理、自动地分配CPU给各道程序，以提高CPU的利用率。所谓程序的并发执行是指一组在逻辑上互相独立的程序，在执行过程中，其执行时间在客观上互相重叠
19、，即一个程序的执行尚未结束，另一程序的执行已经开始的执行方式。与此对应的是程序的顺序执行和并行执行。程序的顺序执行是指一个程序执行结束之后才开始执行下一个程序的执行方式。程序的并行执行是指在多CPU系统中，多道程序同时执行的执行方式。因此，程序的并发执行不同于并行执行，程序的并发执行是宏观上的，程序“同时”执行，微观上，程序“交替”执行。那么，程序如何并发执行以提高CPU的利用率？设有三道程序A、B、C，每道程序分成输入、处理、输出三个程序段。例如，程序A分成输入程序段AI、处理程序段AC、输出程序段AO。如果这三道程序顺序执行，则当执行输入程序段时，CPU和输出设备空闲；当执行处理程序段时，
20、输入设备和输出设备空闲；当执行输出程序段时，输入设备和CPU空闲，这样，CPU及其它系统资源利用率低下。这三道程序可以如图3-3所示地并发执行，这样，在虚线表示的某个时间段上，AO占用输出设备、BC占用CPU、CI占用输入设备，各个系统资源都充分利用。3.1.2 进程当多道程序并发执行时，程序可能“走走停停”，为了更好地控制并发执行的程序，引入了进程。进程是指程序对给定数据集，在处理器上的一次执行过程。进程与程序既相关又不相同，进程包括程序、数据和进程控制块；进程与程序不是一一对应的，一个程序可以创建多个进程，一个进程也可以由多个程序创建；进程具有动态性、生命期，因创建而产生、因调度而执行、因
21、得不到资源而暂停执行、因撤消而消亡，程序只是静态指令集合。传统进程是资源分配的基本单位，也是调度执行的基本单位。当进程切换时，系统开销较大，所以系统中的进程不能太多，切换也不能过于频繁，这就限制了并发程度，于是引入线程，线程是进程的一个实体。引入线程之后，进程继续作为资源分配的基本单位，而线程作为新的调度执行的基本单位。一个进程的多个线程可以并发执行，并且切换时的系统开销较小，从而提高了并发程度。在进程生命周期内，根据资源分配或者调度执行情况，进程可以在就绪态、执行态、阻塞态三个基本状态之间转换，如图3-4所示。(1)就绪态：进程已经获得除CPU之外的其它所需资源，一旦获得CPU即可运行，并等
22、待分配CPU的状态。(2)执行态：进程占有CPU并在CPU上执行的状态。(3)阻塞态：进程尚未获得除CPU之外的其它所需资源，即使获得CPU也无法运行，等待分配其它资源的状态。进程创建之后处于就绪态。就绪态进程可以有多个，它们排成一个就绪队列。当CPU空闲时，按照进程调度策略从就绪队列中选择一个进程分配CPU，该进程从就绪态转换为执行态。阻塞态进程可以有多个，它们的阻塞原因可能相同也可能不同，它们按照阻塞原因排成队列。当等待的事件发生时，例如，数据输入完毕，唤醒等待该事件的进程，进程从阻塞态转换为就绪态。3.1.3 进程控制因共享与竞争资源，进程之间将产生相互制约关系，主要表现为进程互斥和进程
23、同步。1进程互斥进程互斥是指一组并发进程在同一时刻要求同一临界资源而相互排斥。所谓临界资源是指一次只能供一个进程使用的资源。2进程同步进程同步是指一组并发进程为共同完成一个任务而相互合作。事实上，进程互斥和进程同步经常同时出现。如果不对并发进程所需资源的动态分配加以控制，则可能出现死锁。所谓死锁是指一组并发进程彼此互相等待对方所拥有的资源，且这组并发进程在得到对方所拥有的资源之前不会释放自己所拥有的资源，从而造成各并发进程想得到资源又得不到而不能继续向前推进的状态。为了解决死锁，系统可以破坏死锁产生的必要条件，尽可能地预防与避免死锁，系统也可以建立检测和解除死锁的机制，即当检测到死锁发生时，采
24、用资源剥夺或进程撤销解除死锁。3.2 存 储 管 理3.2.1 存储管理方案存储管理是指内存储器的管理，管理任务包括内存的分配、回收、保护及扩充。管理方案有分区存储管理、分页存储管理、虚拟存储管理、段式存储管理和段页式存储管理等。1分区存储管理分区存储管理是早期的存储管理方案，其基本思想是：把内存的用户区划分成若干区域，每个区域分配给一个用户程序使用，并限定它们只能在自己的区域中运行。区域的划分方法有固定分区、可变分区和可重定位分区等。分区存储管理要求程序装入连续的内存区域中，如果不能满足这个要求，就需要以移动区域使之连续为代价。为此，引入分页存储管理。2分页存储管理分页存储管理的基本思想是：
25、把内存空间(实际内存的存储空间)分成若干个大小相等的块。物理地址(内存地址)包括块号和块内地址，把虚拟空间(程序需要的存储空间)分成若干个大小与块相等的页；逻辑地址(虚拟空间的地址，也称为虚拟地址)包括页号和页内地址。内存分配和回收以块为单位，一个块存储一个页，逻辑上连续的页可以存储在物理上不连续的块中，采用页表存储块和页的映射关系即每个页的页号、块号等信息。上述存储管理方案，不论是分区存储管理还是分页存储管理，都要求程序整个装入内存，如果不能满足这个要求，程序就无法运行。为此，目前的存储管理采用虚拟存储管理技术，它可以提供比实际内存大得多的虚拟内存，保证多道程序的并发执行。3虚拟存储管理虚拟
26、存储管理技术的基本思想是：当程序运行时，不是将程序一次性全部从外存装入内存，而是先装入将要执行的部分，再逐步调入需要的部分，调出不要的部分。这样，程序大小不受内存容量的限制，都可以调入内存运行。虚拟存储管理技术主要有请求页式管理、请求段式管理、请求段页式管理等。下面重点介绍请求页式管理技术。3.2.2 请求页式管理请求页式管理是在分页存储管理的基础上，增加了请求调页和页面置换而形成的虚拟存储管理技术。请求页式管理的基本思想是：把内存空间分成若干个大小相等的块，物理地址包括块号和块内地址，把虚拟空间分成若干个大小与块相等的页，逻辑地址包括页号和页内地址。内存分配和回收以块为单位，一个块存储一个页
27、，逻辑上连续的页可以存储在物理上不连续的块中，采用页表存储块和页的映射关系即每个页的页号、块号、中断位(作为是否装入内存的标志)等信息。当程序运行时，先装入将要执行的页到块中，并设置页表；当访问某个逻辑单元时，先根据逻辑地址计算该单元的页号和页内地址，然后查页表，通过中断位判断该页是否在内存中：如果在内存，得到该单元在内存中的块号和块内地址，再计算该单元的物理地址，最后根据物理地址访问相应内存单元；否则发生缺页中断，则需要请求调页，即分配一个块，将该页调入内存，并修改页表，之后按在内存的方式处理，即根据该单元在内存中的块号和块内地址计算该单元的物理地址，根据物理地址访问相应的内存单元。当请求调
28、页时，如果内存没有空闲块，就需要根据一定的算法进行页面置换，即调出不需要的页，再调入需要的页，同时修改页表。若页面置换算法选择不当，则可能造成抖动现象，即刚被换出的页又被访问，需要重新调入，从而导致系统频繁置换页面。常用的页面置换算法有最佳置换算法、先进先出置换算法、最近最少未使用置换算法以及最近未用置换算法。3.3 设 备 管 理3.3.1 程序查询方式程序查询方式如图3-6所示。CPU在运行主程序的过程中，如果需要设备进行数据输入输出，就会启动设备。在设备准备期间，CPU处于查询等待状态，即CPU不停地主动查询设备就绪与否，直至设备就绪，从而进行数据交换，数据输入/输出结束，CPU继续运行
29、主程序。在这种设备管理方式下，CPU利用率低下，因为在设备准备期间，CPU处于查询等待状态。3.3.2 中断控制方式 中断是指计算机在运行程序过程中，当遇到需要紧急处理的事件时，暂停运行当前程序，转去运行处理紧急事件的程序(中断服务程序)，当处理紧急事件的程序运行结束后，再继续运行暂停的程序。中断控制方式包括中断请求与中断响应两类。中断控制方式如图3-7所示。CPU在运行主程序的过程中，如果需要设备进行数据输入/输出，就会启动设备。在设备准备期间，CPU继续运行主程序，设备就绪后向CPU发出中断请求，CPU收到中断请求后判断是否进行中断响应，如果响应，CPU暂停运行主程序，转去运行中断服务程序
30、，进行数据交换，数据输入/输出结束，CPU返回继续运行主程序。与程序查询方式相比，中断控制方式提高了CPU利用率，因为在设备准备期间，CPU可以继续运行主程序而无需等待。3.4 文 件 管 理3.4.1 多重索引结构文件的三级索引结构如图3-8所示。文件的索引节点不仅存储了文件名、文件大小等文件描述信息，还存储了若干找到文件数据信息的指针。图中包括直接块指针12项，一次间接块指针、二次间接块指针和三次间接块指针各1项。所谓直接块是存储文件数据信息的数据块，即通过直接块指针找到一个数据块，该数据块中存储的是文件数据信息。一次间接块是存储直接块地址的数据块，即通过一次间接块指针找到一个数据块，该数
31、据块中存储的是若干直接块地址，再通过这些直接块地址找到数据块，这些数据块中存储的才是文件数据信息；二次间接块是存储一次间接块地址的数据块；三次间接块则是存储二次间接块地址的数据块。3.4.2 多级目录结构为了实现文件的按名存取，可将文件控制块组织成目录，以便于文件的按名检索。为了更好地管理文件，例如解决文件的重名冲突等，文件通常采用如图3-9所示的多级目录结构。多级目录结构像一棵倒置的有根树，所以也称为树型目录结构。在图中，节点是文件，节点是目录，根目录是盘符，目录下面可以包括子目录或文件。同一目录下面不能有同名文件，但是不同目录下面可以有同名文件。事实上，访问这两个文件时采用的绝对路径是不同
32、的，一个是“D:程序test.c”，另一个是“D:备份test.c”，因此这两个文件是同名的不同文件。4.1 算 法4.2 数 据 结 构第四章 算法与数据结构4.1 算 法4.1.1 算法描述一个问题可以有多种求解方法，一个求解方法可以有多种描述形式。如果在人与人之间交流，可以采用自然语言、示例、图、表、公式等描述形式；如果在人与计算机之间交流，则只能采用程序设计语言，因此程序也称为程序设计语言描述的算法。下面，通过一个例子介绍不同的算法描述形式。例4-1 求解两个正整数的最大公约数。针对这个问题，给出两种求解方法：穷举法和辗转相除法，每种方法给出三种描述形式：自然语言形式、流程图形式和程序
33、设计语言(C语言)形式。1穷举法(1)穷举法的自然语言形式如下：令S为两个正整数M、N中的较小者；令R1为M除以S的余数，R2为N除以S的余数；若R1与R2同时等于0，则S就是两个正整数的最大公约数，否则令S为S减1，返回继续。穷举法的流程图形式如图4-1所示。(2)穷举法的程序设计语言形式如下：int greatest_common_divisor(int m,int n)int s,r1,r2;if(mn)s=n;else s=m;r1=m%s;r2=n%s;while(r1!=0|r2!=0)s=s-1;r1=m%s;r2=n%s;return(s);2辗转相除法(1)辗转相除法的自然语
34、言形式如下：令M为两个正整数中的较大者，N为较小者；令R为M除以N的余数；若R等于0，则N就是两个正整数的最大公约数；否则令M为N，N为R，返回继续。(2)辗转相除法的程序设计语言形式如下：int greatest_common_divisor(int m,int n)int r;if(mn)r=m;m=n;n=r;r=m%n;while(r!=0)m=n;n=r;r=m%n;return(n);辗转相除法的流程图形式如图4-2所示。4.1.2 算法分析前面提到，一个问题可以有多个求解算法，究竟哪个算法好呢？这就是算法分析的任务。算法分析，也称为算法复杂性分析，是对运行算法所消耗的资源进行分析
35、。算法消耗的资源越多，算法复杂性就越高。资源可以分为时间资源(运行时间)和空间资源(内存空间)，因此，算法复杂性分析也分为时间复杂性分析和空间复杂性分析。例4-2 直观分析例4-1给出的两个算法穷举法和辗转相除法。穷举法和辗转相除法的算法分析如表4-1所示。如果选择变量数目作为空间度量，则穷举法需要5个变量M、N、S、R1、R2，辗转相除法需要3个变量M、N、R，辗转相除法优于穷举法。如果选择循环语句执行次数作为时间度量，则当M=30，N=15时，穷举法和辗转相除法都是0次循环，而当M=30，N=16时，穷举法是14次循环，辗转相除法是2次循环。可以看到，不同的M和N，同一算法的循环次数也不同
36、，因此，时间复杂性有最好情况、最坏情况、平均情况三种。从平均情况来看，辗转相除法优于穷举法。事实上，当进行算法复杂性分析时，不可能也没必要如例4-2一样，针对特定输入分析算法的变量数目和基本语句执行次数，而是分析随着问题规模的增长，复杂性增长的量级。例如，算法的时间复杂性与算法本身、问题规模n相关，当算法确定时，算法的时间复杂性就是n的函数T(n)，并且通常采用渐进上界O(f(n)表达其时间复杂性增长的量级。如果算法的时间复杂性过高，则该算法可能是理论可计算，而实际不可计算。例如，时间复杂性为O(2n)的算法，随着问题规模n的增加，运行时间呈指数增加，算法就是理论可计算而实际不可计算。4.1.
37、3 算法设计1.分治与递归计算机求解问题所需时间一般都与问题规模相关，问题规模越小，所需时间越少，也较容易处理。分治是将一个难以直接解决的规模较大的原问题分解成一系列规模较小的子问题，分别求解各个子问题，再合并子问题的解得到原问题的解。分治是算法设计的基本策略，包括三个步骤：(1)分解：将原问题分解成一系列子问题。(2)求解：求解各个子问题。(3)合并：合并子问题的解得到原问题的解。在算法设计中，递归与分治就像孪生兄弟，密切相关。递归是指函数(或过程)直接调用自己或通过一系列调用语句间接调用自己。通常，递归用于解决结构自相似问题，即构成原问题的子问题与原问题在结构上相似，可以采用类似方法求解。
38、递归是描述问题和解决问题的基本方法，包括两个要素：(1)边界条件：确定递归何时终止，也称为递归出口。(2)递归模式：确定原问题如何分解为子问题，也称为递归体。例4-3 求解n!。方法一：n!可以展开为n!=n*(n-1)*(n-2)*3*2*1，可以采用循环求解，流程图如图4-3所示，程序如下：int factorial(int n)int p,m;p=1;m=1;while(m=2)p=fibonacci(n-1)+fibonacci(n-2);return(p);从图4-5可以看到，在f5的递归计算中，有许多子问题被重复计算，如f3被重复计算了2次，f2被重复计算了3次。随着n的增加，这个
39、现象更加突显，严重影响计算效率。方法二：采用动态规划，即颠倒计算方向，将自顶而下计算变为自底而上计算，对每个子问题仅计算一次并将解保存在表格中，当需要再次计算该子问题时，通过查表获得其解，从而避免重复求解公共子问题，程序如下：int fibonacci(int n)int p,f100,i;if(n=0)p=0;if(n=1)p=1;if(n=2)f0=0;f1=1;for(i=2;i=n;i+)fi=fi-1+fi-2;p=fn;return(p);动态规划求解过程中的表格如表4-2所示。4.2 数 据 结 构4.2.1 基本概念数据结构是相互之间存在一种或多种特定关系的数据元素的集合。所谓
40、数据元素是在程序中作为一个整体进行考虑和处理的数据的基本单位，可由若干个数据项组成。例4-5 如图4-6所示，在职工管理中，一个职工的信息就是一个数据元素，可由职工号、姓名、性别、出生年月等数据项组成。数据结构的研究内容包括：(1)数据的逻辑结构：研究数据元素之间的逻辑关系。(2)数据的存储结构：研究数据元素及其关系在计算机中的表示与存储。(3)基本操作的算法：研究当某种逻辑结构采用某种存储结构实现时，基本操作的算法及复杂性。数据结构的研究内容如图4-7所示。逻辑结构可以分为线性结构、树结构、图结构，存储结构可以分为顺序存储结构和链式存储结构。例4-6 在职工管理中，n个职工的信息是n个数据元
41、素，它们的逻辑结构可以看做线性结构中的线性表，即数据元素之间的逻辑关系是线性关系，而且可以在任一位置删除或者插入一个数据元素，如图4-8所示。线性表的顺序存储结构可以采用C语言中的数组实现，一个数组元素存储一个数据元素，数据元素之间的逻辑相邻采用数组元素之间的物理相邻表示，顺序存储结构如图4-9所示。线性表的链式存储结构可以采用C语言中的指针实现，如图4-10所示，一个结点存储一个数据元素，数据元素之间的逻辑相邻采用结点之间的指针表示。4.2.2 线性结构线性结构是指数据元素之间的逻辑关系是线性关系(一对一关系)。第一个数据元素没有前驱，只有唯一后继，最后一个数据元素没有后继，只有唯一前驱，其
42、它数据元素有唯一前驱和唯一后继。如图4-12所示，圆圈表示数据元素，线表示数据元素之间的关系。根据线性结构中数据元素的操作限制，线性结构分为以下几个：(1)线性表：允许在任一位置进行插入和删除操作。(2)堆栈：只允许在一端进行插入和删除操作。这一端称为栈顶，另一端称为栈底，如图4-13所示。堆栈的特点是先进栈的数据元素后出栈，称为先进后出(First In Last Out，FILO)。(3)队列：只允许在一端进行插入操作，在另一端进行删除操作。插入一端称为队尾，删除一端称为队头，如图4-14所示。队列的特点是先进队的数据元素先出队，称为先进先出(First In First Out，FIFO
43、)。4.2.3 树结构树结构是一种非常重要的数据结构。树的递归定义为：没有结点(数据元素)的树称为空树。在非空树中，有且仅有一个结点称为根结点，其余结点可分为若干互不相交的集合，每个集合又是一棵树，称为根结点的子树。结点的子树数目称为结点的度。除根结点外，度为0的结点称为叶子结点，度不为0的结点称为内部结点。结点的子树根结点称为该结点的子结点，相应地，该结点称为子树根结点的父结点。根结点没有父结点，可以有若干子结点；叶结点没有子结点，只有唯一父结点；内部结点只有唯一父结点，可以有若干子结点。因此，树结构是指数据元素(结点)之间的逻辑关系是一对多关系(分支)，一个父结点可以有若干子结点，一个子结
44、点只有唯一父结点，如图4-15所示。二叉树是一种应用广泛的特殊的树结构，它的递归定义是：没有结点(数据元素)的二叉树称为空树。在非空二叉树中，有且仅有一个结点称为根结点，其余结点可分为两个互不相交的集合，每个集合又是一棵二叉树，分别称为根结点的左子树和右子树。二叉树的特点是任意结点至多有二个子结点，子结点有左右之分，如图4-16所示。二叉排序树又是一种用于查找的特殊的二叉树，它的特点是：对于任意结点，若它的左子树不空，则左子树上所有结点的值均小于它的值；若它的右子树不空，则右子树上所有结点的值均大于它的值，如图4-17所示。4.2.4 图结构图结构是比树结构更复杂的一种数据结构。如图4-18所
45、示，在图结构中，数据元素(顶点)之间的逻辑关系是多对多关系(边)。根据边是否有方向，可将图分为有向图(如图4-18(a)所示)和无向图(如图4-18(b)所示)。在无向图中，从顶点vs到顶点ve的路径是顶点序列vs=v1，v2，vk=ve，其中vi与vi+1(1ik)之间有边。如果从顶点vs到顶点ve有路径，则称vs与ve是连通的。如果任意两个顶点都是连通的，则称无向图是连通图。连通图的生成树是极小连通子图，即含有全部n个顶点、仅含有n-1条边的连通子图。连通图的生成树可能不唯一。在图中，边可以附带一个称为权的值，称为带权图，如图4-18(b)所示。带权连通图的最小生成树是边的权之和最小的生成
46、树。带权连通图的最小生成树也可能不唯一。5.1 程序设计语言5.2 编译原理第五章 程序设计语言与编译原理5.1 程序设计语言5.1.1 机器语言机器语言就是机器指令。回顾第二章介绍的两个加数相加的机器指令形式的程序：0001 00 00100000000011 00 00100000010010 00 00100000100000 00 0000000000可以看到机器语言程序是0、1形式的程序，可以被计算机直接识别和处理，执行效率高，但是它与指令系统相关，通用性差，可读性差，容易出错且不易纠错，编写效率低。为了克服机器语言的缺点，引入了汇编语言。5.1.2 汇编语言以下是采用COMET模型
47、机的CASL汇编语言编写的两个加数相加的汇编语言程序。STARTLD GR0,XADD GR0,YST GR0,ZENDSTART表示程序开始，LD(LOAD)表示载入数据，ADD表示相加，ST(STORE)表示存储数据，END表示程序结束，GR0(GENERAL REGISTER)表示通用寄存器地址，X、Y、Z表示内存地址。LD GR0,X表示从X中载入数据到GR0中；ADD GR0,Y表示GR0中的数据与Y中的数据相加，和存于GR0中；ST GR0,Z表示从GR0中存储数据到Z中。机器语言相比，汇编语言的编写效率提高了，但是它仍然与指令系统相关，通用性也差。于是，出现了高级语言。5.1.3
48、 高级语言主流高级语言主要包括命令型语言和面向对象语言。1.命令型语言命令型语言，也称为面向过程语言，采用结构化程序设计，以操作为中心，进行功能分解和模块划分，强调程序“做什么”和“如何做”。命令型语言包括Fortran语言、Pascal语言和C语言等。Fortran语言是第一个广泛用于科学计算的高级语言；Pascal语言在早期的高校计算机程序设计教学中处于主导地位；C语言是20世纪70年代发展起来的高级语言。C语言兼顾了高级语言与汇编语言的特点，允许直接访问操作系统和底层硬件，因此在系统级应用和实时处理应用的开发中成为主要语言。程序设计语言的基本元素主要包括以下几点：(1)常量与变量：常量是
49、在程序运行过程中其值不能改变的量；变量是在程序运行过程中其值可以改变的量，具有数据类型、变量名、变量值三个属性。(2)数据类型：数据是程序处理的基本对象，数据类型决定了数据的存储长度、取值范围及允许的操作。(3)运算符与表达式：运算是数据加工的过程。(4)选择与循环等控制语句：程序具有顺序、选择、循环三种控制结构。(5)函数与过程等程序模块：函数与过程是一段具有独立功能的程序模块。2.面向对象语言面向对象语言采用面向对象程序设计，以数据为中心，进行对象抽取和类抽象，强调程序“包括什么对象”、“对象包括什么属性和方法”。面向对象语言包括C+语言、Java语言和C#语言等。C+语言是在C语言基础上
50、于20世纪80年代发展起来的面向对象语言，与C语言兼容，C+语言增加了类机制。Java语言是20世纪90年代发展起来的广泛用于网络开发的面向对象语言。C#语言是Microsoft为.net开发的全新的面向对象语言，它吸收了C+、Java等语言的优点。下面给出采用C+语言编写的计算圆的面积和周长的高级语言程序。#include const double pi=3.14;class circle;public:int radius;double calculate-area()return pi*radius*radius;double calculate-perimeter()return 2*
