计算机科学导论电子教案

计算机科学导论Foundations

of

Computer

Science田际平

计算机专业副教授答疑:工程实验北楼310室(办公室)第一页，共一百七十九页。教学计划与进度课程名称计算机科学导论/课程类别专业必修课/教学时数28学时第五周绪论(计算机软件、硬件、历史等)第六周数据的类型、表示第七周数的各种表示第八周位运算、算数运算、逻辑运算第九周计算机组成第十周计算机网络第十一周操作系统定义、组成部分第十二周算法第十三周程序设计语言第十四周软件工程第十五周数据结构第十六周抽象数据类型第十七周文件结构第十八周数据库、总复习第二页，共一百七十九页。第一部分计算机和数据第三页，共一百七十九页。第一章

绪论数据处理冯•诺伊曼理论计算机硬件计算机软件计算机发展简史第四页，共一百七十九页。数据处理任何数据处理系统都可以表示为三个步骤：数据输入

数据输出计算机系统在用户看来，给出数据（出入）得到结果（输出），目的即达到，不关心也不知道数据的处理过程，所以数据处理中的处理过程对用户是看不到的，就象个“黑盒子”。对计算机科学者来说，除去数据的输入与输出，更关心数据处理系统中的数据处理过程。因为包括数据的输入与输出在内的整个数据处理都是计算机科学研究的对象。美籍匈牙利数学家冯•诺伊曼(VonNeumann)于1945年奠定了现代计算机科学的基本理论。现代计算机的特点是具有速度快精度高、逻辑判断与记忆功能的、高度的自动化与灵活性。处理第五页，共一百七十九页。冯•诺伊曼理论输出设备冯•诺伊曼提出的重要的计算机设计思想可概括为：计算机应由五个基本部件组成：运算器、控制器、存储器、输入部件与输出部件。程序存储思想：将程序与数据同时存储在存储器中，让机器自动执行程序。程序控制思想:计算机以运算器为中心，输入/输出设备与存储器之间的数据传输都通过运算器。存储器数据流输入设备控制流运算器控制器第六页，共一百七十九页。冯·诺依曼计算机的基本特点计算机的基本工作原理是存储程序和程序控制称为冯·诺依曼原理。按照冯·诺依曼原理构造的计算机又称冯·诺依曼计算机，其体系结构称为冯·诺依曼结构。其基本特点为：采用存储程序方式，程序和数据放在同一个存储器中，两者没有区别，指令同数据一样可以送到运算器进行运算，即由指令组成的程序是可以修改的。存储器是按地址访问的线性编址的唯一结构，每个单元的位数是固定的。指令由操作码和地址码组成。通过执行指令直接发出控制信号控制计算机的操作。机器以运算器为中心，输入输出设备与存储器间的数据传送都经过运算器。数据以二进制表示。第七页，共一百七十九页。计算机硬件计算机硬件通常由五部分组成：运算器和控制器、存储器、输入与输出设备。这五部分之间的联结结构，称为冯·诺依曼结构图（如前图），其以运算器为中心。运算器是对信息进行加工处理的部件。它在控制器的控制下与内存交换信息，负责进行各类基本的算术运算和与、或、非、比较、移位等各种逻辑判断和操作。此外，在运算器中还含有能暂时存放数据或结果的寄存器。控制器是整个计算机的指挥中心。它负责对指令进行分析、判断，发出控制信号，使计算机的有关设备协调工作，确保系统自动运行。控制器和运算器一起组成了计算机的核心，称为中央处理

器，即CPU（Central

Processing

Unit）。通常把控制器、运算器和主存储器一起称为主机，而其余的输入、输出设备和辅助存

储器称为外部设备。第八页，共一百七十九页。存储器是计算机的记忆装置，为了对存储的信息进行管理，把存储器划分成单元，每个单元的编号称为该单元的地址。存储器内的信息是按地址存取的。向存储器内存入信息也称为“写入”。写入新的内容则覆盖了原来的旧内容。从存储器里取出信息，也称为“读出”。信息读出后并不破坏原来存储的内容，因此信息可以重复取出，多次利用。计算机的存储器可分为主存储器和辅助存储器两种，通常分别简称为主存和辅存。输入设备如：键盘、鼠标、光笔、扫描仪等。输出设备如：屏幕显示器、打印机、绘图仪、音箱等。第九页，共一百七十九页。计算机软件在计算机中，数据是以电信号的方式存在的，并以二进制的形式来组织数据。程序是指令的有序序列（冯•诺伊曼也定义了指令集），并与其所处理的同时数据必须存放在存储器中。程序设计是以算法为基础的，算法是一套自顶向下、逐步求精地去解决问题的方法。计算机语言是由符号与单词按特定语法构成的语句集合。每个语句都对应这特定的指令集而被计算机所接收、解释与执行。软件工程是为为解决62年的软件危机而产生的一套结构化（或面向对象）的程序设计思想与方法。操作系统是对计算机系统软硬件资源进行管理，并对用户使用计算机提供良好界面的程序包。第十页，共一百七十九页。计算机发展简史第一代计算机（1946～1958年）其主要特征是采用电子管作为主要元器件。第二代计算机（1958～1964年）其主要特征是由电子管改为晶体管。第三代计算计算机导论机（1964～1974年）其主要特征是用半导体中小规模集成电路代替分立元件的晶体管。第四代计算机（1974年至今）其主要特征是以大规模和超大规模集成电路为计算机的主要功能部件。注：与教材所讲有不同第十一页，共一百七十九页。第二章

数据的表示数据的类型计算机内部的数据表示数据十六进制表示法八进制表示法第十二页，共一百七十九页。数据的类型计算机能处理的数据分类为：数值：计算文字：编辑图象：缩放与调整音频和视频：声效与特效第十三页，共一百七十九页。计算机内部的数据统一的数据表示法：对各种类型的数据都采用同一种数据表示。位（bit）：二进制数字，是存储在计算机中的最小数据单位。位模式：是一个位（bit）序列，即一个二进制数字串。字节（byte）：长度为8的位模式，也是度量存储空间大小的单位。第十四页，共一百七十九页。表示数据以位模式来表示各种类型的数据（1）文本由文本语言的符号个数决定位模式的长度：log2

符号个数=模式长度如ASCⅡ码，128个符号，128=27

，所以位模式长度为7，即用7位二进制数字表示一个ASCⅡ符号。ASCⅡ码表要了解数字与字母排列。扩展的ASCⅡ码用一个字节表示一个符号，每字节的第一位为0。第十五页，共一百七十九页。（2）数的表示，见下章图象位图图象：图象由象素点阵构成，每个象素由一个位模式表示，模式长度取决于对应象素亮度与色彩（或灰度）。矢量图象：整个图由基本直线与曲线的数学公式构成。音频和视频：对连续的模拟信号采样，并进行数字离散化后转换为位模式存储。第十六页，共一百七十九页。八进制和十六进制表示法十进制：基本数字为0…9每位不会出现10，逢10进1二进制：基本数字为0…1每位不会出现2，逢2进1八进制：基本数字为0…7每位不会出现8，逢8进1十六进制：基本数字为0…9、A、B、C、D、E、F（相当十进制10…15

）每位不会出现F，逢F进1第十七页，共一百七十九页。个进制对照表第十八页，共一百七十九页。八和十六进制与位模式的转化每一个八进制数对应二进制的三位（3位模式）如：144(O)=001

100

100(B)7123(O)=111

001

010

011(B)7

1

2

3每一个十六进制数对应二进制的四位（4位模式）如：64(H)=0110

0100(B)2C1D(H)=0010

1100

0001

1101(B)2

C

1

D第十九页，共一百七十九页。第三章

数的表示数制的转换整数的表示EXCESS系统浮点表示法十六进制表示法第二十页，共一百七十九页。r进制转化成十进制转换公式：an

...a1a0.a-1...a-m

(r)

=

a*rn

+

…+

a*r1

+

a*r0+a*r-1+...a*r-m10101(B)=24+22+1=21101.11(B)=22+1+2-1+2-2=5.75101(O)=82+1=6571(O)=7

8+1=57101A(H)=163+16+10＝4106第二十一页，共一百七十九页。十进制转化成r进制整数部分：除以r取余数，直到商为0，余数从右到左排列。小数部分：乘以r取整数，整数从左到右排列。例

100.345(D)=1100100.01011(B)~

100(D)=144(O)=64(H)2

1002500225021210.345281008124814011610016640626023011010.69021.38020.76021.52021.04100(D)=144(O)=64(H)=1100100(B)第二十二页，共一百七十九页。整数的表示正数与负数在计算机中数的符号也是用数码来表示的，一般用“0”表示正数的符号，“1”表示负数的符号，并放在数的最高位。例如：（01011）2

＝

（＋11）10（11011）2

＝

（－11）10第二十三页，共一百七十九页。原码、补码、反码在计算机中一个数可以采用原码、补码或反码表示，上面讲到的正数与负数表示法即为原码表示法。一个正数的原码、补码、反码是相同的，而负数就不同了。无符号整数格式(最简单的数据表示):数的范围：0

～－（1－2

n）。其中为N用于存储该数据的二进制数位.第二十四页，共一百七十九页。原码(符号加绝对值格式)假设x为n位小数，用小数点左面一位表示数的符号，则：数的范围：（1－2

n）～－（1－2n）。零有两种表示：正零为0.0…0；负零为1.0…0。第二十五页，共一百七十九页。补码数的范围：（1－2

n）～－1。零的表示是唯一的，即：

0.0…0。第二十六页，共一百七十九页。反码数的范围：（1－2

n）～－（1－2

n）。零的表示有两种：正零为0.0…0，负零为1.1…1。第二十七页，共一百七十九页。Excess系统特点:能同时存储正负数,易于二与十进制数转换。正数（幻数）用于转换过程，在8位模式下幻数为（2

n-1）=128或（2

n-1）-1=127，并分别称Excess-128与Excess-127。Excess系统数据表示法（数据转换法）：将十进制整数与幻数之和转换为二进制数，并补足N位。如：整数-25的Excess-127数据表示为01100110D-25+D127=D102=B1100110=B01100110第二十八页，共一百七十九页。浮点数表示法浮点数可以扩大数的表示范围。浮点数由两部分组成，一部分用以表示数据的有效位，称为尾数；一部分用于表示该数的小数点位置，称为阶码。一般阶码用整数表示，尾数大多用小数表示。一个数N用浮点数表示可以写成：

N

＝

M·ReM表示尾数，e表示指数，R表示基数。基数一般取2，8，16。一旦机器定义好了基数值，就不能再改变了。因此，在浮点数表示中基数不出现，是隐含的。注:浮点数表示法类似于数据的“科学表示法”第二十九页，共一百七十九页。浮点数(注:与教材讲解略有不同)110.011(B)=1.10011×2+10=11001.1×2-10=0.110011×2+11阶符阶码

数符

尾数1100110011N=

数符

尾数2阶符

阶码尾数的位数决定数的精度。阶码的位数决定数的范围。IEEE标准(32位单精度浮点数表示):32位=符号1位+指数Excess-127数8位+尾数23位十六进制表示法(略)第三十页，共一百七十九页。第四章

数位运算算数运算逻辑运算移位运算第三十一页，共一百七十九页。算数运算位运算包括算数运算与逻辑运算。而算数运算包括整数与浮点数的四则运算。整数的四则运算以二进制补码形式的存储整数，可以进行加、减、乘、除四则运算。因计算机是以反复的加来实现整数的乘（*），而以反复的减实现除（/），如下示意，所以只介绍具有典型意义的加减运算。如：5

*

47

/

25

+

5

+

5

+

57

–

2

–

2

–

2

+

1减3次2即商为3

余1第三十二页，共一百七十九页。整数加如：24加–17得724对应补码形式：00011000–17+（17为00010001）11101111

+71

00000111再如：127加3得130进位舍3+00000011

+130错误结果–12610000010127

对应补码形式：

01111111注：8位模式补码表示范围为–128

~

+127，超出该范围即产生错误。所以127加1得–128，再加两次1，即得–126。01111111

10000000第三十三页，共一百七十九页。整数减、浮点数的加减整数减运算也是借助加法运算实现的，即减一个整数等于加一个相同值的负数。如：101–62相当于101+（–62）得39+101

即

101

补码：0110010162

– –

62

+

1100001039

39

00100111浮点数的加减（见教材示例）以Excess-127保存指数的IEEE规范浮点数的加减，主要是两个数的指数取等值后，再按多项式使同项（同幂次）系数（尾数）相加。第三十四页，共一百七十九页。逻辑运算一个二进制位（bit）的两个可能的值0、1，如果被决定为逻辑值，即定义0为“假”而1为“真”，那么就可以实现逻辑运算。许多逻辑是应用于逻辑电路方面，或由“门电路”触发而实现的。逻辑运算真值表值非运算与运算或运算异或运算xyNOTxxANDyxORyxXORy0010000101110001111110第三十五页，共一百七十九页。对“与”，“或”理解的示例令P为教授，Q为党员，则某大学的相关会议参加者的命题检验如下：某人的情况

党内专家P

Q P

AND

Q党员扩大（专家）会P

OR

Q000

（不可参加会议）001011001111（可以参加会议）

1第三十六页，共一百七十九页。移位运算左（右）移位：对于无符号二进制数串各位左（右）移1位，最高（低）位舍弃而最低（高）位补0。左（右）移位对应着二进制乘（除）2。如：D59乘2为D118，而除2为29（实际为29.5）。00111011

00111011移出舍弃

001110110

补入

000111011移出舍弃再如：确定8位模式的第四位的值是0或1。设计“掩码”（修改另一位模式的位模式）为00001000：原位模式：abcdefgh掩码：00001000

AND（“与”逻辑运算）0000e000

0000000e右移3次（除8）原码能被8整除则结果e为1，否则e为非1（即为0）第三十七页，共一百七十九页。第二部分计算机硬件第三十八页，共一百七十九页。第五章计算机组成中央处理器主存储器输入/输出子系统的内部连接程序执行两种不同的体系结构第三十九页，共一百七十九页。中央处理器Unit”CPU的全称是“Central

Processing，即中央处理器。CPU的主要性能指标有：1．主频主频即CPU工作的时钟频率。CPU的工作是周期性的，它不断地执行取指令、执行指令等操作。这些操作需要精确定时，按照精确的节拍工作，因此CPU需要一个时钟电路产生标准节拍，一旦机器加电，时钟电路便连续不断地发出节拍，就像乐队的指挥一样指挥CPU有节奏的工作，这个节拍的频率就是主频。一般说来，主频越高，CPU的工作速度越快。第四十页，共一百七十九页。2．外频实际上，计算机的任何部件都按一定的节拍工作。通常是主板上提供一个基准节拍供各部件使用，主板提供的节拍称为外频。3．倍频随着科技的发展，CPU的主频越来越快，而外部设备的工作频率跟不上CPU的工作频率，解决的方法是让CPU作频率以外频的若干倍工作。CPU主频是外频的倍数称为CPU的倍频。CPU工作频率＝倍频×外频第四十一页，共一百七十九页。4．地址总线宽度我们知道，PC（Personal

Computer，个人计算机）采用的是总线结构。地址总线宽度（地址总线的位数）决定了CPU可以访问的存储器的容量，不同型号的CPU总线宽度不同，因而使用的内存的最大容量也不一样。如32位

地址总线能使用的最大内存容量为4GB。5．数据总线宽度数据总线宽度决定了CPU与内存、输入／输出设备之间一次数据传输的信息量。Pentium以上的计算机，数据总线的宽度为64位，即CPU一次可以同时处理8个字节的数据。第四十二页，共一百七十九页。6．L1高速缓存缓存是位于CPU和内存之间的容量较小但速度很快的存储器，使用静态RAM做成，存取速度比一般内存快3～8倍。L1缓存也称片内缓存，Pentium时代的处理器把L1缓存集成在CPU内部。L1高速缓存容量一般在32KB～64KB之间，少数可达到128KB。7．L2高速缓存此即二级高速缓存，通常做在主板上，目前有些CPU将二级缓存也做到了CPU芯片内。L2高速缓存的容量一般在128KB～512KB之间，有的甚至在1M以上。第四十三页，共一百七十九页。工作电压工作电压是指CPU正常工作时所需要的电压。早期CPU工作电压一般为5V，而随着CPU主频的提高，CPU工作电压有逐步下降的趋势，以解决发热过高的问题。目前CPU的工作电压一般在1.6V～2.8V之间。CPU制造工艺越先进，则工作电压越低，CPU运行时的耗电功率就越小。协处理器含有内置协处理器的CPU可以加快特定类型的数值计算。某些需要进行复杂运算的软件系统，如AUTO

CAD就需要协处理器支持。Pentium以上的CPU都内置了协处理器。第四十四页，共一百七十九页。CPU的封装方式采用Socket结构封装的CPU与Socket插座。采用Slot结构封装的CPU与Slot插座。第四十五页，共一百七十九页。存储器1．基本概念存储器是由一些能表示二进制数0和1的物理器件组成的，这种器件称为记忆元件或存储介质。常用的存储介质有半导体器件和磁性材料。例如，一个双稳态半导体电路、磁性材料中的存储元等都可以存储一位二进制代码信息。位是存储器中存储信息的最小单位，称为存储位。由若干个存储位组成一个存储单元。一个存储单元可以存放一个字，此时称为字存储单元；也可以存放一个字节，称为字节存储单元。许多存储单元的集合形成一个存储体，它是存储器的核心部件，信息就存放在存储体内。第四十六页，共一百七十九页。如何区分存放在存储体中的信息，也就是说怎样将存储体中若干个存储单元加以识别呢？解决这个问题的方法是给每个存储单元编上号，这个编号就称为该单元的地址。若一个单元存放一

个字节，则相应的地址称字节地址；若一个单元存

放一个机器字，那么，相应的地址称为字地址。一个存储器中存储单元的总数称为该存储器的存储容量。计算机中存储器的容量越大，能存储的信息就越多，计算机的处理能力也就越强。表示存储容量的单位一般用字或字节。例如，

32KB表示32K字节，128KW表示128K字，其中IK＝1024。第四十七页，共一百七十九页。存储器的两个基本操作是写入信息和读出信息（或称存数和取教）。存储器从接到读出命令，到指定地址的信息被读出，并稳定在存储器数据寄存器或数据总线上为止的时间，称为读出时间（亦称取数时间）。反之，将数据寄存器或数据总线上的信息写入存储器的时间称为写入时间。在连续两次访问存储器时，从第一次开始访问到下一次开始访问所需的最短时间称为存储周期，它表示存储器的工作速度。第四十八页，共一百七十九页。2．存储器分类按存取方式分类：随机存储器（RAM

）和顺序存储器（SAM），读写存储器和只读存储器（ROM）。按存储介质分类：磁性材料存储器，半导体存储器和激光存储器。按功能和存取速度分类：寄存器型存储器、主存储器和外存储器。3．存储器的性能指标存储容量（capacity）存取速度（access

time）数据传输率（data

transfer

rate）位存储价格（cost

per

bit）第四十九页，共一百七十九页。半导体存储器（1）RAMRAM的全名是读写随机存取存储器（ReadWrite

Random

Access

Memory），本应缩写为

RWRAM，但它不易发音，故流行称为RAM。三个特点：可以读出、也可以写入；所谓随机存取，意味着存取任一单元所需的时间相同；当断电后，存储内容立即消失，称为易失性（volatile）。（3）NVRAMNVRAM是一种非易失性的随机读写存储器。既能快速存取，而系统断电时又不丢失数据。实际上，它是把SRAM的实时读写功能与E2PROM的可靠非易失能力综合在一起。第五十页，共一百七十九页。（2）DRAM与

SRAMRAM可分为动态（Dynamic

RAM）和静态（Static

RAM）两大类。动态随机存储器DRAM是用MOS电路和电容来作存储元件的，由于电容会放电，所以需要定时充电以维持存储内容的正确，这称为“刷新”，例如每隔2ms刷新一次，因此称之为动态存储器。静态随机存储器SRAM是用双极型电路或MOS电路的触发器来作存储元件的，没有电容造成的刷新问题。只要有电源正常供电，触发器就能稳定地存储数据，因此称之为静态存储器。DRAM的特点是高密度，SRAM的特点是高速度。第五十一页，共一百七十九页。2．只读在储器ROMROM为只读存储器（Read

Only

Memory或译唯读存储器）的缩写。ROM的用途很广，如与微程序设计相结合。与操作系统及高级语言相结合，与应用软件相结合、与无磁盘网络工作站等。PROM与EPROMPROM是可编程只读存储器（Programmable

ReadOnly

memory）的缩写。它与ROM的性能一样，存储的程序在处理过程中不会丢失、也不会被替换。第五十二页，共一百七十九页。EPROM是可擦除可编程只读存储器（

ErasableProgrammable

Read

Only

Memory）的缩

写。它的内容通过紫外光照射可以擦除，这种灵活性使EPROM得到广泛的应用。（3）E2PROME2PROM是电擦除可编程只读存储器（ElectricallyErasable

Programmable

ROM）的缩写；它包含了EPROM的全部功能，而在擦除与编程方面更加方便．这就使

E2PROM比EPROM有更大的灵活性和更广泛的适应性。第五十三页，共一百七十九页。输入/输出（外存储器）1．磁记录的基本概念（1）磁记录密度（density）·面密度（areal

density）。面密度等于道密度与位密度的乘积。·道密度（track

density）。道密度等于磁道间距的倒数，而磁道间距（track

pitch）则是相邻两条磁道中线间的距离·位密度（bit

density）。磁道上单位长度存储的二进制信息量称为位密度也称为线密度。第五十四页，共一百七十九页。（2）磁记录方式磁记录方式主要有两种：水平记录方式和垂直记录方式。水平记录方式（horizontal

recording）是利用磁头磁场的水平分量在介质上写入信息，使介质沿其表面进行磁化。通常也称为横向记录方式。缺点：是存在自退磁效应，每个小磁畴的距离不能太近，这就限制了记录密度的进一步提高。第五十五页，共一百七十九页。垂直记录方式（vertical

recording）是利用磁头磁场的垂直分量在介质上写入信息，使介质的磁化方向垂直于介质表面。优点：是相邻位的退磁磁场几乎为零，每个磁束之间不会抵消，反而会加强，这就适合于进行高密度的磁记录。区位记录方式（zone

bit

recording，简称ZBR）也称等密度记录方式。等密度记录就是保持所有磁道上记录的位密度相等。为此，可以采用两种方法：①匀线速度控制法。②区域位密度法。第五十六页，共一百七十九页。（3）磁记录编码技术磁盘机曾广泛使用的编码方法有：FM调频制（Frequency

Modulation）编码，M＝0.5；MFM改进调频制（Modified

FrequencyModulation）编码，

M＝

1；M2FM改进的改进调频制（Modified

MFM）编码，

M＝1，且可靠性、信噪比均得到改善。还有一类成组编码方法，它是把记录的数据序列按若干位编成一组，对应于每种组态有一种编码序列与之匹配。例如GCR（4／5）成组编码。第五十七页，共一百七十九页。GCR（4／5）GCR（4／5）成组编码（Group

CodedRecording）就是把数据按4位编成一组，与之对应产生出5位编码序列。编码规则是：禁止使用连续3位以上的“0”代码组合。我们知道，4位有16种组态，5位则有

32种组态，除掉含有3位以上连续“0”的组态，5位编码序列尚有17种组态可用。选用其中16种与4位数据序列对应即可。GCR编码效率M＝0.75，具有一定的自同步能力。已应用于磁带机与软磁盘机中。第五十八页，共一百七十九页。GCR（4∕5）编码数据序列GCR编码序列d1d2d3d4e1e2e3e4e5000011001000111011001010010001110011010011101010110101011010110011110111100011010100101001101001010101101011110011110110101101111001110111101111第五十九页，共一百七十九页。注意：数据序列通过编码电路转换为编码序列后，它还不等于就是记录序列。当通过磁头往磁表面上写数据时，还要把编码序列按一定规则变成记录脉冲。例如在GCR编码中，最后是用逢“1”翻转不归零制（Non

Return

to

Zero，

NRZ－1）规律加以记录的。目前，比较先进并在硬磁盘机中广泛使用的编码是

RLL（2，7）编码。这是限制两次翻转之间距离的编码，或称游程长度受限码（Run－LengthLimited

Code，RLL）。编码规则是：在编码序列中，两个“1”之间至少有2个“0”，最多有7个“0”。第六十页，共一百七十九页。ARLL（2，7）美国最近设计出的编码，即高级RLL码（

Advanced

RLL）。它把编码效率提到M＝2，将在未来更高密度的磁盘机中得到普遍的应用。数据序列RLL（2，7）编码序列111000100100000100100001001000010000100011000100100011100001000第六十一页，共一百七十九页。2．软磁盘及其设备（1）软磁盘软磁盘（原名flexible

disk，后来人们戏称为floppy

disk）或译为软磁盘，是人们广泛使用的一种廉价介质。它是在聚酯塑料（mylar

plastic）盘片上涂布容易磁化并有一定矫顽力的磁薄膜而制成的。所用磁介质有γ一氧化铁、渗钴氧化铁，对于高密度介质（超过

30000bpi）则采用钡铁氧体、金属介质等。软盘的主要规格是磁片直径。1972年出现的是8英寸软盘。1976年与微型机同时面世的是

5.25英寸软盘，简称5英寸盘。1985年日本索尼（sony）公司推出3.5英寸盘。1987年索尼公司又推出2.5英寸软盘，简称2英寸盘。目前已出现

1.5英寸软盘，只是未批量生产。第六十二页，共一百七十九页。在磁片直径不断缩小的同时，软盘容量却连续扩大，以5英寸盘为例，当初的单面单密度容量为

125KB，单面双密度或双面单密度为250KB，双面双密度则为500KB。所谓单面是只用一面，双面是两面都用。所谓单密度是用FM编码的，双密度（又称倍密度）是用MFM、M2FM或GCR编码记录的。5寸软盘外观第六十三页，共一百七十九页。3英寸盘的容量有1MB、2MB、4MB等数种。自1987年IBM选择2MB的3.5英寸盘作为PS／2系列的配置后，2MB盘正成为事实上的工业标准。随着膝上型计算机的流行，3英寸盘成为软盘的主流产品．（2）驱动器与适配卡一个完整的软盘存储系统是由软盘、软盘驱动器、软盘控制适配卡组成。软盘驱动器（floppy

disk

drive）由机械运动和磁头读写两部分组成。机械运动部分又由主轴驱动系统和磁头定位系统两部分组成。通常，主轴驱动系统使用直流伺服电机，带动磁盘以每分钟300转以上的速度旋转，并使磁头定位进行磁盘信息的读写。第六十四页，共一百七十九页。软盘驱动器简称软驱。它的全部机械运动与数据读写操作，必须在软盘控制适配卡（

FDCadapter）的控制下进行。而适配卡正好把驱动器与CPU系统板联系起来，使磁盘存储系统成为整个计算机系统的一个有机组成部分。（3）软盘的使用与维护不要弄脏，不要用手摸盘面，不要把它放在高温、潮湿、强磁、震动的地方。也不要用硬笔在封套上写划，标签要写好再贴。写保护缺口的贴上或取下，一定不要怕麻烦，携带时不要图省事，随便放在书包里，应该装在盒内。第六十五页，共一百七十九页。软盘的格式低密度高密度软盘扇磁容扇磁容区道量区道量360K15801.2M5.25英寸9403.5英寸980720K18801.44M第六十六页，共一百七十九页。3．硬磁盘及其设备硬盘是计算机系统中最主要的辅助存储器。硬盘盘片与其驱动器合二为一体，称为硬盘机，后来人们叫熟了，统称为硬盘。硬盘通常安装在主机箱内，所以无法从计算机的外部看到。（1）硬盘的种类按硬盘的几何尺寸划分，硬盘分为3.5英寸和5.25英寸两种。近年来，市场上主要以3.5英寸为主。按硬盘接口划分，主要有IDE、EIDE、UltraDMA和SCSI接口硬盘。第六十七页，共一百七十九页。硬盘的工作模式20世纪90年代初期，PC机多采用IDE接口硬盘。

IDE接口标准的硬盘工作方式只能是标准模式。在标准模式下，硬盘最大容量只能是528MB，硬盘与主机之间采用PIO方式（程序控制输入／输出方式）传输数据。突破528MB容量限制的问题，因此推出了EIDE标准。EIDE接口标准的工作模式有三种：标准模式（

Normal

Mode），该模式与IDE的工作模式完全相同。逻辑块地址模式（LBA

Mode），也称大数据块模式。它突破了硬盘空间528MB的管理限制，支持的硬盘容量最大达到8.4GB。第六十八页，共一百七十九页。大模式（Large

Mode），也称大磁道模式，该模式是为了方便那些不支持LBA模式设置而准备的一种工作模式，它支持的硬盘最大容量为1GB。主板上提供两个EIDE接口，分别为EIDE1、EIDE2。一个EIDE接口可以连接符合EIDE标准的包括硬盘机、光盘驱动器等在内的2个设备。若一台计算机只有一个硬盘机和一个光盘驱动器，建议优先考虑将硬盘接入EIDE

1、光盘驱动器接入

EIDE

2，这样可以提高运行速度，尤其是对提高播放VCD速度很有好处。当一个EIDE接口接2个EIDE设备（如接2个硬盘）时，硬盘上的跳线就是用来确定该硬盘是第几个设备的。第六十九页，共一百七十九页。硬盘接口由于硬盘容量的增大和读写速度的提高，必然要求硬盘接口有更高的传输率，Intel和Quantum联合推出了最新的硬盘接口标准——UltraDMA，它所采用的数据传输方式与以往不同。在PIO方式中，CPU直接进行读写控制，而UltraDMA采用的数据传输方式称为直接存储器存取数据传送方式，传输效率比PIO模式高得多。Ultra

DMA方式工作的硬盘仍然采用EIDE接口和主机相连。第七十页，共一百七十九页。目前采用

Ultra

DMA方式工作的硬盘有Ultra

DMA／33和Ultra

DMA／66两种。UltraDMA／33硬盘是采用和

EIDE标准相同的数据线与主板EIDE接口连接（一根40针的数据线）。Ultra

DMA／66使用的是

80针接口，这样就出现了与

EIDE接口不兼容的问题，这个问题的解决办法是在传统的40针标准的EIDE信号线和地线之间穿插了40条线，以此方法来实现与现行接线插口上的兼容。SCSI是一种智能化的接口，特别适合于并发数据的处理请求。与IDE接口相比，SCSI接口提供了更强的扩充能力。SCSI接口可以以菊花链方式挂接7个不同的外部设备。现在PC机服务器经常采用SCSI接口。第七十一页，共一百七十九页。（2）硬盘主要的性能指标及选购容量：硬盘的容量指的是硬盘中可以容纳的数据量。转速：转速是指硬盘内部马达旋转的速度，单位是

RPM（每分钟转数）。平均寻道时间：平均寻道时间指的是磁头到达目标数据所在磁道的平均时间，它直接影响到硬盘的随机数据传输速度。缓存：缓存的大小会直接影响到硬盘的整体性能第七十二页，共一百七十九页。磁带及其设备磁带的种类可按磁带宽度可分按磁带外形可分为两种：卡式盒带，磁带盒按记录方式分为两种：纵向记录方式、螺旋扫描记录方式磁带文件的顺序性由于磁带介质很窄且极长，必须在两个轮盘之间有条不紊地传送、盘绕才能完成读写操作，这就决定了磁带记录的顺序性。然而，对于面积有限的磁盘，人们可以面对整个盘面，直接读写某个磁道上、某个扇区内的某个字段，完全不必从0磁道顺序查到399磁道，这就决定了磁盘记录的随机性。第七十三页，共一百七十九页。光盘存储器光盘存储器的主要类型固定型光盘，又叫只读光盘追记型光盘，又叫只写一次式光盘可改写型光盘，也叫可擦写型光盘光盘驱动器工作方式有两种，恒定线速度和恒定角速度。（1）恒定线速度（CLV）无论光驱读取头是在内轨还是在外轨读取数据，数据传输率都保持不变，而光驱的转速随读取头在光盘轨迹的位置而变化，读取头远离光盘中心，光驱转速逐渐下降，使读取头在单位时间内扫过光盘相同的轨迹长度，读取相同数据量，从而可以以相同的速率读出所有的数据。第七十四页，共一百七十九页。（2）恒定角速度（CAV）与CLV正好相反，它是让数据传输率发生变化，保持光盘固定的转速。光驱读取头从光盘中央向外圈移动时，数据传输率是递增的，并且数据传输率完全取决于数据所存放的位置。购买光驱主要应考虑两方面的问题:其一是光驱的倍速；其二是纠错能力，“纠错”能力实际上是对“烂盘”（盘片质量不太好、有缺陷）的“读盘”能力。第七十五页，共一百七十九页。子系统的内部连接（系统总线）总线结构1．单总线结构在单总线结构中，计算机系统的部件如CPU、主存储器及输入输出设备等，都挂在一条总线上，它们之间以相同的形式进行通信，故称单总线。CPU工作期间，单总线上的信息流动可以描述如下：首先，CPU将PC的内容（指令地址信息）和读命令（控制信息）送到总线，并将总线上的所有设备与总线送来的地址进行比较，只有与此地址相同的设备（主存）才接受命令，执行相应的操作（启动主存操作，将指令取出，经总线数据线送到CPU）；第七十六页，共一百七十九页。然后，CPU检查操作码，决定下一步要执行的操作是在CPU内部进行，还是要经总线访问主存或1／O设备。第七十七页，共一百七十九页。2．双总线结构在这种结构中有两条总线：主存总线及输入输出总线。前者负责CPU与主存、通道之间的信息传送；后者负责多台外部设备与通道及外部设备之间的信息传送）。在CPU工作期间，取指令通过主存总线完成。指令取出后，CPU检查操作码决定下一步操作是在CPU内部进行还是访问主存或I／O操作。若访问主存，则仍由主存总线完成；若I／O操作，则交给通道去处理，通过输入输出总线完成。第七十八页，共一百七十九页。第七十九页，共一百七十九页。3．三总线结构三总线结构是指在计算机系统中各部件用3条各自独立的总线构成信息通路。这3条总线是：主存总线，它负责CPU与主存的信息传送；I／O总线，它负责I／O设备之间以及I／O设备与CPU之间的信息传送；DMA总线，即直接主存访问总线，它负责高速外部设备与主存的信息传送。在计算机工作期间，CPU通过主存总线取到指令。然后，CPU检查操作码，决定下一步要执行的操作是在CPU内部进行，还是要访问主存或I／O设备。由于I／O设备与主存不在一条总线上，因此I／O设备的寻址与主存单元寻址是不统一的，即采用单独编址方法。第八十页，共一百七十九页。CPU通过访存指令访问主存，指令中给出存储单元地址；CPU通过I／O指令访问I／O设备时，由指令中给出I／O设备接口寄存器的地址。因此，指令操作码指示CPU将使用哪条总线。第八十一页，共一百七十九页。在三总线系统中，访问主存和访问I／O设备各有单独的指令。当I／O指令的地址码涉及到高速外设时（如磁盘），将使用DMA总线，直接在主存与高速外设之间传送信息。三总线结构不允许外设之间直接传送信息，只能经过主存间接传送。总线的控制与通信1．总线的控制方式系统总线多采用集中控制方式，解决总线使用权的控制问题。按各部件使用总线优先次序的确定方法的不同，集中控制与分布控制方式均对应有3种实现方法：串行链接、定时查询及独立请求。下面讨论集中控制方式的3种实现方法。第八十二页，共一百七十九页。（1）串行链接方式串行链接方式，又称链式查询方式，需要在系统总线中增加3根控制线：总线忙（BS）线，它有效时，指示总线正在被某部件使用；总钱请求（BR）线，它有效时，指示总线上至少有一个部

件请求使用总线；总线响应（BG）线，它有效时，指示总线控制部件正在响应某个部件的总线请求。在串行链接方式中，总线上所有的部件共用一根总线请求线。若有部件请求使用总线时，均需经此线发总线请求到总线控制器。由总线控制器检查总线忙否，若总线不忙，则立即响应，即发总线响应信号，经总线响应线BG串行地从一个部件送到下一个部件，依次查询。第八十三页，共一百七十九页。若响应信号到达的部件无总线请求，则该信号立即传送到下一个部件；若响应信号到达的部件有总线请求，则信号便截住，不再传下去。第八十四页，共一百七十九页。串行链接方式的特点是采用硬接线逻辑，将各部件扣链在总线响应线上。因此，优先级则固定，有较高的实时响应性。此外，只需很少几根控制线就能按一定优先次序，实现总线控制，结构简单，扩充容易。（2）定时查询方式定时查询方式采用一个计数器控制总线使用权。它仍公用一根请求线，当总线控制器收到总线请求信号，判断忙线不忙时，计数器开始计数，计数值通过一组地址线发向各部件，每个部件与总线接口均有一个地址判别线路。当地址线上的计数值与请求使用总线设备的地址一致时，该设备获得总线控制权，置忙线为“1”。同时，中止计数器的计数及查询工作。第八十五页，共一百七十九页。（3）独立请求方式在独立请求方式中，每个部件均有一对总线请求线（BR）和总线批准线（BG），而不采用共享请求线的方式。第八十六页，共一百七十九页。当总线上的部件需要使用总线时，经各自的总线请求线发送总线请求信号，在总线控制器中排队。当总线控制器按一定的优先次序决定批准某个部件的请求时，则给该部件发送总线响应信号，该部件接到此信号，就获得了总线使用权，开始传送数据。第八十七页，共一百七十九页。第八十八页，共一百七十九页。第八十九页，共一百七十九页。第六章

计算机网络网络OSI模型网络分类连接设备互连网与TCP/IP第九十页，共一百七十九页。网络计算机网络是利用现代通讯设备和线路,将分布在各个不同地理位置的、功能不同且各自独立的多个计算机系统连接起来，在网络软件的支持下，实现互相通讯和资源共享的系统。计算机网络的主要功能：信息交换资源共享分布式处理第九十一页，共一百七十九页。OSI模型模型是由国际标准化组织制定的用于网络设计的指南。OSI称开放式互连系统，它允许任两个不同的计算机系统互相通讯而无需考虑其底层体系结构。OSI的七层结构：数据A1应用层表示层会话层传输层网络层数据链路层物理层数据B应用层表示层会话层传输层网络层数据链路层物理层传输媒介第九十二页，共一百七十九页。OSI个层的功能数据（消息）从A发向B，实际就是A的各层（7至1层）工作后，经媒介（线路）传向B，再由B的各层（1至7层）工作后得到数据（消息）。消息的数据称为“报文”，它在各层中被逐渐分解组合（如报头，报尾等）并加以检验。（1）物理层：任务是透明地传输位（比特bit）流，即传输的单位是“比特”。该层考虑何电压表示和识

别“0”或“1”，及电缆插头的脚数和定义脚的连接。注意：传输介质（双绞线、同轴电缆、光纤等线路）本身并不在物理层。“透明”是一个实际存在的事物看起来好象不存在一样，透明地传输即说明比特流不受实际电路影响而传输后不变化。第九十三页，共一百七十九页。（2）数据链路层：任务是在两个相邻结点间的线路上无差错地传输“帧”（读zheng，幅frame）。加报头把别特流组构成“帧”，而报尾加控制信息（同步、地址、差错控制、流量控制等），可检验传输差错或重发帧，使“点对点传输”的接收端能正确无误地接受到报文。该层将有可能出差错的实际线路，变为在“网络层”向下看似乎是一条不出差错的线路。（3）网络层：任务是“站到站传输”信息，传输的单位是“分组”或“包”，该层选择合适的路由，使发送运站输层下来的包能准确无误地按地址找到并交付接受站运输层，此为该层的寻址功能。注意：这里的“网络是专用词”。对于通讯子网，由于路由问题很好解决，所以该层可省略。第九十四页，共一百七十九页。（4）运输层：任务是依通讯子网的特性，合理利用网络资源并可靠地进行“端到端传输“报文。“报文”是由一个或多个信息包组成，报文较长时可以分组并交由网络一下各层处理。该层在源站与目的站两个主机的进程之间，建立运输连接以透明地传送报文。即它向上层提供一个可靠的端到端服务，使上面看不到运输层以下的数据通讯细节。通讯子网内各个各结点和连接各通讯子网的路由器都没有运输层，运输层仅存在于子网之外的主机中。运输层以上各层不再关心信息传输问题，所以运输层在计算机网络体系结构中十分重要。第九十五页，共一百七十九页。以下三层可统归“应用层”会话层：从此不再参与数据传输，其任务是对数据传输进行管理，它在两个互相通讯的进程之间建立、组织与协调交互（会话）。如会话中的同步，整条信息是否重发，确定是双工（同时收发）还是单工（交替收发）通讯等。表示层：任务是解决用户信息的语法表示。表示层将欲交换的数据从适合于某一用户的“抽象语法”变换为适合于OSI系统内的传送语法。抽象语法包括数据的语法（格式）和语义（数据的意义），因为不同系统可能具有不同的编码格式。第九十六页，共一百七十九页。（7）应用层：任务是定义通用的网络应用程序，它直接为用户提供服务。注意：会话层与表示层的功能经常被包含在应用层中，从而省略会话层与表示层。网络分类按考虑问题的不同角度，可使网络有不同的分类，如按网络总线的“拓扑结构”，网络可以分为集中式、分散式和分布式等；按网络的作用范围，网络可分为局域网（LAN）、城域网（

MAN

）或广域网（WAN）等。第九十七页，共一百七十九页。网络连接设备中继器：增强信号的设备。它网络的物理延伸，可以提供信号再生，免除长距离信息传输所造成的通讯信号衰减所造成的错误。网桥：可以连接同一网络内的两个段或连接两个同类网络的通讯控制器。网关：可以连接两个不同类网络（咎由自取不同的网络协议）的通讯控制器。路由器：同网关，或可用以连接两个以上的同类网络的通讯控制器。（观点不同）第九十八页，共一百七十九页。互连网与TCP/IP互连网：即国际互连网（Internet），它是连接世界各地的各种局域网、城域网和广域网所构成的交互式

网络。TCP/IP：传输控制协议/网际协议（网络通讯的一组规则），它是Internet的核心，要求连入Internet的每台计算机都有一个32字节的IP地址。FTP：文件传输协议，在Internet中用以解决具有不同编码系统的机器之间进行文件传输。SMTP：简单邮件传输协议，Internet山支持电子邮件（email）的协议，实际要结合邮局协议POP的使用。特点是SMTP邮件地址系统。第九十九页，共一百七十九页。TELNET：是Internet上允许远程登录的通用客户/服务器程序。（将本地终端模拟为远程终端）WWW/Web：称“万维网”，多媒体稳当的集合。

HTTP：超文本传输协议，超文本是在“万维网”上构成网页的、包含特殊符号的多媒体文本。浏览器：接收、解释并显示超文本的程序。URL：同意资源定位器，在Internet上用方法、主机、端口和路径的地址格式指定信息（的位置）。第一百页，共一百七十九页。第三部分计算机软件第一百零一页，共一百七十九页。第七章操作系统定义演化组成部分主流操作系统第一百零二页，共一百七十九页。操作系统定义计算机系统由计算机的硬件系统与软件系统构成，而计算机的软件系统又是分为系统软件与应用软件，其中的操作系统就是主要的系统软件之一。操作系统是控制和管理计算机系统内各种硬件和软件资源,有效地组织多道程序运行的系统软

件（或程序集合），是用户与计算机之间的接口。主要功能:进程管理、存储器管理、处理机管理、设备管理、文件管理、用户界面与接口等。第一百零三页，共一百七十九页。计算机系统的层次结构用户用户支撑软件测试工具、剪辑工具、项目管理工具、语言转换工具等应用软件管理信息系统、飞机订票系统、地理信息系统、数字计算软件包等系统软件语言编译程序、连接装配程序、数据库管理程序、网络软件等操作系统计算机硬件第一百零四页，共一百七十九页。演化（操作系统的发展）批处理系统：早期计算机系统，程序员对机器没有控制与交互，程序（作业）都以穿孔卡片的形式交操作员执行后打印结果。操作员搜集所有程序员的作业成批运行。分时系统：在引入多道程序概念后产生了分时（对CPU时间的共享），程序员直接而不是通过操作员来操作系统，使多程序共享系统资源，而用户的每个作业都可透明地得到CPU的一个“时间片”。进程是存储器中等待资源的程序，而作业是要运行的程序。个人系统：当个人计算机（PC机）产生后，独占资源的单用户操作系统（个人系统）应运而生。如DOS。第一百零五页，共一百七十九页。（4）并行系统：一般的计算机是用一个CPU逐个处理程序，即串行系统，而当一个机器中安装了多个CPU并使没个CPU都可以处理一个程序或程序的一部分，则产生了多任务的并行系统。（5）分布式操作系统：在计算机网络发展到了交互式网络阶段，则可利用分布在不同地理位置上的资源共同完成一个作业，而且程序的不同部分可以在网络内不同的计算机上运行。第一百零六页，共一百七十九页。操作系统的组成部分一般讲，操作系统有四大基本管理功能：存储管理、进程管理、设备管理与文件管理。（1）存储管理可以分为单道程序与多道程序的内存管理单道程序的内存管理，是除少量用于必要的操作系统存储外，基本使一个程序独占内存。即一个程序载入内存并运行，之后再用另一程序取代，操作系统不断地反复此过程。这里的问题是：程序大过内存容量则无法执行；除单一程序的独占性外，数据还要不断地输入/输出，由于CPU与I/O设备速度的差异就造成CPU的不断等待（空闲）而使效率低下。第一百零七页，共一百七十九页。多道程序的存储管理多道程序的存储管理允许在同一时刻载入多个程序（除必要的操作系统外多程序共存）并可以同时运行这些程序。多道程序的存储管理涉及两种存储技术：非交换技术即程序在运行期间始终驻留内存，如分区调度与分页调度；交换技术即在运行过程中程序可以在内存与磁盘之间多次交换，如请求分页调度与请求分段调度。各内存管理技术的发展都是后者对前者的逐步改进。第一百零八页，共一百七十九页。分区调度：该技术仍是将一个程序完整地装入内存并占用连续的地址。它将内存划分为不等长的若干区，每区保存一个程序，CPU在各个程序之间交替服务。CPU从一个程序开始执行指令，当有I/O操作产生或该为程序服务的时限到达时，就保存最近执行的指令地址（为返回继续执行该程序保留入口）并转入下一个程序去执行。CPU对内存中每个区均如此处理，直到最后一个区也按如此的步骤处理后再返回第一个程序。分区大小是预定义的，所以随着新程序的不断载入，终会出现区中未被占用的“空闲区”（碎片），当空闲区过多时内存可以压缩分区移动空闲区创建新的分区，但增加系统负担。第一百零九页，共一百七十九页。分页调度：它将内存分为大小相等的若干部分并成为“帧”，而程序则被分为大小相等的若干“页”，一般来说帧、页与与系统从存储器提取信息块的

大小一致。它虽然仍要求把程序整个装入内存，但不要求装入内存的连续地址。页被载入内存的帧中，但一个程序的不同页可以被载入内存中的不同帧，连续的页也不一定被载入连续的帧中。这样新程序的载入就不必在所有连续的帧出现后再载入内存。分页调度改进了分区调度的效率，但由于只有整个程序被载入后才能运行，所以当内存为此提供的可替换的帧不够时程序仍无法载入。第一百一十页，共一百七十九页。请求分页调度：它不仅不要求程序占用连续地址的内存，还不需要整体装入内存。该技术允许程序的页被依次载入内存并运行后再为其它页所取代，即不要求程序的所有页被同时载入，而可以被分批载入内存运行。请求分段调度：类似分页雕塑技术，因程序由主程序与若干子程序组成，所以程序可以按程序的观点划分为若干段后被载入内存并执行，之后再由同一程序的其它段或别的程序段来取代。虚拟内存：以上内存管理技术使得一个部分被载入内寸执行而另一部分仍在磁盘中，但是用户感觉一个程序已经被整体载入内存，故占用磁盘的部分相当于“虚拟内存”。第一百一十一页，共一百七十九页。进程管理（略）程序、作业、进程程序、作业与进程三者鲜花转换的状态图程序三态：保持状态、就绪状态、运行状态调度器：作业调度器、进程调度器队列：作业队列、就绪队列、I/O队列进程同步：死锁、饿死第一百一十二页，共一百七十九页。设备管理的职责文件管理的职能主流操作系统：Windows

2000UNIXLinux第一百一十三页，共一百七十九页。第八章算法概念三种结构算法的表示算法的定义子算法与基本算法递归第一百一十四页，共一百七十九页。算法的概念算法的定义:通俗讲，算法就是一种解题的方法。它可以是一组独立于计算机系统的解题步骤严格说，算法是由若干条指令组成的有穷序列。算法必须满足五大特性：输入：具有0个或多个输入的外界量（算法开始前的初始量）输出：至少产生一个输出，它们是算法执行完后的结果。有穷性：每条指令的执行次数必须是有限的。确定性：每条指令的含义都必须明确，无二义性。可行性：每条指令的执行时间都是有限的。有序集合、明确步骤、产生结果、有限时间内终止。第一百一十五页，共一百七十九页。算法和程序的关系算法的含义与程序相似，但二者有区别。程序不一定满足有穷性（可能有死循环）；程序中的指令必须是机器可执行的，与计算机系统相关，而算法中的指令（或步骤）则可以与计算机系统无关，即独立于计算机系统。一个算法若用计算机语言（程序设计语言）来书写，则它就可能是一个程序。算法的描述可以用人能看懂而机器不认的工具，如流程图表、伪代码（也可以是算法语言）程序设计语言也称算法语言，但它是把算法进一步书写为程序（计算机能识别执行的语言）第一百一十六页，共一百七十九页。算法示例题目：从一组正整数中找出最大的正整数。算法思想：假设某一固定的地方总是放着最大值。将大规模的问题限制在小规模的范围内解决；集中精力解决问题中的关键步骤；尽量将性质相同的步骤合并为一步进行重复；边界问题：加上进入与结束关键重复步的处理；将正确解小规模问题的方法推广到大规模问题；进一步精确与优化解决问题的过程。注意：在解题的多方法中选择具有通用性强的方法；选择通俗易懂的工具来正确描述算法。第一百一十七页，共一百七十九页。输入列表算法模式:算法一种逐步解决问题或完成任务的方法输出列表12

8

13

9

11输入列表输入、过程、输出:算法8列表（步骤1）列表（步骤2）13列表（步骤3）9最大值

12

12最大值12最大值13最大值13最大值13列表（步骤4）11

列表（步骤5）13

输出列表第一百一十八页，共一百七十九页。12

8

13

9

11输入列表定义动作：寻找最大值（步骤1）将最大值置为第一个数（步骤2）如果第二个数大于最大值，将第二个数置为最大值（步骤3）如果第三个数大于最大值，将第三个数置为最大值（步骤4）如果第四个数大于最大值，将第四个数置为最大值（步骤5）如果第五个数大于最大值，将第五个数置为最大值13输入列表精化： 12

8

13

9

11

输入列表寻找最大值（步骤0）将最大值置为0（步骤1）如果当前数比最大值大，将最大值置为当前数……（步骤5）如果当前数比最大值大，将最大值置为当前数13输入列表第一百一十九页，共一百七十九页。输入列表泛化：寻找最大值将最大值置为0重复下一步骤N次如果当前数比最大值大，将最大值置为当前数输出列表优化：对算法进一步精简等。注意：算法要求通用性，即机器无关性，在那里都可以实现。算法描述工具：算法要求用通用性强表示方法来书写，即谁都能看得懂。一般可以采用自然语言，通用符号、流程图、伪代码等书写算法。目的是研究算法的人与进一步编程序的人来阅读。第一百二十页，共一百七十九页。三种基本结构依据结构化算法与程序设计思想，任何一个算法或程序都可以由顺序、选择和重复（循环）这三种基本结构复合而成。顺序结构是算法或程序的最基本的结构，因任何指令都是被顺序地执行的。选择结构是根据逻辑判断进行指令段跳转的结构，即在两个或两个以上的指令段中，依据条件选中一段并跳转到该段指令继续执行。重复结构是对相对简单而独立的指令段循环执行的结构。三种基本结构都有对应的算法描述手段和程序设计语句支持。第一百二十一页，共一百七十九页。算法描述工具之一：流程图顺序结构：

选择结构：

重复结构：动作1假

测试

真while条件

假动作2真……动作系列B动作系列A动作系列动作n第一百二十二页，共一百七十九页。算法描述工具之一：伪代码以“从一组正整数中找出最大的正整数”为示例。FandLargestInput

:

A

list

of

positive

integerSet

Largest

to

0While

(

more

integers)3.4.5.if

(

the

integer

is

greater

then

Largest)thenSet

Largest

to

the

value

of

the//2.1可以被定义为一个子算法integerend

ifend

while3.

Retune

Largest3.

end第一百二十三页，共一百七十九页。基本算法在算法中被频繁使用的、最简单的、最基本的算法：求和（累加器）：初始化：S=0；重复：S=S+数；乘积（累乘器）：初始化：N=1；重复：N=N*数；求最大或最小值：类似前面的示例排序：将任意的一组数按“不小于”关系重新排列。选择排序冒泡排序插入排序查找：给定某一特定值，在一组数中查找是否有该值 。顺序查找折半查找递归：把自身作为子算法重复调用以获得结果的算法。第一百二十四页，共一百七十九页。第九章程序设计语言演化构建程序程序执行语言的分类过程化语言C(略)第一百二十五页，共一百七十九页。演化/发展计算机语言，是依据预定义的语法规则而给出的预定义的语句集合,这些语句可组成程序。机器语言（计算机产生之初）由二进制位串组成的语言，语句可以由机器直接接收、识别与执行，其所书写的程序不必再经过针对于机器指令的翻译过程。符号语言/汇编语言（二十世纪五十年代）语法成份都是助记符号的语言，解决了机器语言的难于读写的问题，但仍与机器相关。汇编语言程序，需针对于不同机器的指令系统，由

“汇编程序”翻译为能在该机执行的程序。第一百二十六页，共一百七十九页。（3）高级语言（二十世纪六使年代）一种尽量接近自然语言的计算机语言（如：计算的书写尽量贴近数学公式，语句功能的描述尽量贴近自然语言），它具有机器无关性（所以才有了各具特点的语言），摆脱了程序的书写与机器硬件的密切性。与符号/汇编语言程序类似，高级语言需要经过“编译程序”或“解释程序”对机器指令的翻译后才能在具体的机器上执行。高级程序语言具有机器无关性，但是翻译程序必须是针对具体机器（过CPU系列）的。一种语言的程序是否能被翻译在各种机器上执行的性质，叫做该程序的“可移植性”。高级语言程序的翻译一般通称“编译”，但是“编译程序”翻译的形式主要是对程序的“整篇翻译”，而“解释程序”主要是对程序的“逐句翻译”。第一百二十七页，共一百七十九页。构建程序构建程序的过程，实际就是从编写源程序直到程序执行得到结果的过程。它主要分为一下步骤：编辑源程序为文本文件原则上可任选一种“字处理程序”，将手写源程序编辑为文本文件后作为编译程序的输入。编译为目标文件接收源程序的文本，经过“预处理”扫描与翻译等两三步将其编译为目标程序（文件）。链接为可执行文件将组成程序的各子程序目标文件、预定义的各过程与函数的目标模块链接为可执行程序。运行可执行程序得到结果机器语言构成的可执行程序被由操作系统的“载入程序”调进内存后由CPU执行并得到输出结果。第一百二十八页，共一百七十九页。语言的分类在高级语言长期的发展中，形成了许多各具特点，其分类可概括如下：（1）过程化语言过程化语言适用于过程化程序设计，它是将解决问题所涉及到的数据，与处理数据的操作分别进行设计，并通过控制操作去处理数据。它后期发展为结构化语言及结构化程序设计。FORTRAN语言第一个高级程序设计语言，主要应用于科学与工程计算，至今其思想仍在发挥作用。COBOL语言目标明确地被定向为面向商业的通用语言，主要强调了与数据库的连接与生成各种报表。第一百二十九页，共一百七十九页。PASCAL语言第一个支持结构化程序设计思想的高级语言，主要用于科学与教育界以建立结构化程序设计思想与方法的概念。C语言最初用于系统软件（如UNIX）的开发。由于它简洁而高效、且可类似汇编语言般操作硬件而流行至今。ADA语言为美国国防部软件业务承包同意语言，由于其允许实时控制与很高的并行处理能力而主要用于工业与大型计算机。过程化语言终为结构化语言所取代。第一百三十页，共一百七十九页。（2）面向对象语言是一种目前流行的，更接近于人类思维的程序设计方法。它与过程化语言的不同，是它把数据及其操作定义为一个整体。C++语言它是一种支持面向对象程序设计的语言，也是

C语言的扩展，或说它把C语言作为自己的一个子集。它