《计算机科学导论电子教案PPT精品文档》由会员分享,可在线阅读,更多相关《计算机科学导论电子教案PPT精品文档(179页珍藏版)》请在金锄头文库上搜索。
1、计算机科学导论FoundationsofComputerScience田际平 计算机专业副教授答疑:工程实验北楼310室(办公室)1教学计划与进度课程名称 计算机科学导论/课程类别 专业必修课/教学时数 28学时第五周绪论(计算机软件、硬件、历史等)第六周数据的类型、表示第七周数的各种表示第八周位运算、算数运算、逻辑运算第九周计算机组成第十周计算机网络第十一周操作系统定义、组成部分第十二周算法第十三周程序设计语言第十四周软件工程第十五周数据结构第十六周抽象数据类型第十七周文件结构第十八周数据库、总复习2第一部分计算机和数据3第一章 绪论数据处理冯诺伊曼理论计算机硬件计算机软件计算机发展简史4数
2、据处理任何数据处理系统都可以表示为三个步骤:数据输入数据输出计算机系统在用户看来,给出数据(出入)得到结果(输出),目的即达到,不关心也不知道数据的处理过程,所以数据处理中的处理过程对用户是看不到的,就象个“黑盒子”。对计算机科学者来说,除去数据的输入与输出,更关心数据处理系统中的数据处理过程。因为包括数据的输入与输出在内的整个数据处理都是计算机科学研究的对象。美籍匈牙利数学家冯诺伊曼(Von Neumann)于1945年奠定了现代计算机科学的基本理论。现代计算机的特点是具有速度快精度高、逻辑判断与记忆功能的、高度的自动化与灵活性。处理5冯诺伊曼理论冯诺伊曼提出的重要的计算机设计思想可概括为:
3、(1)计算机应由五个基本部件组成:运算器、控制器、存储器、输入部件与输出部件。(2)程序存储思想:将程序与数据同时存储在存储器中,让机器自动执行程序。(3)程序控制思想:计算机以运算器为中心,输入 / 输出设备与存储器之间的数据传输都通过运算器。数据流 控制流 输出设备存储器输入设备运算器控制器6冯诺依曼计算机的基本特点 计算机的基本工作原理是存储程序和程序控制称为冯诺依曼原理。按照冯诺依曼原理构造的计算机又称冯诺依曼计算机,其体系结构称为冯诺依曼结构。其基本特点为:(1)采用存储程序方式,程序和数据放在同一个存储器中,两者没有区别,指令同数据一样可以送到运算器进行运算,即由指令组成的程序是可
4、以修改的。(2)存储器是按地址访问的线性编址的唯一结构,每个单元的位数是固定的。(3)指令由操作码和地址码组成。(4)通过执行指令直接发出控制信号控制计算机的操作。(5)机器以运算器为中心,输入输出设备与存储器间的数据传送都经过运算器。(6)数据以二进制表示。7计算机硬件计算机硬件通常由五部分组成:运算器和控制器、存储器、输入与输出设备。这五部分之间的联结结构,称为冯诺依曼结构图(如前图),其以运算器为中心。运算器是对信息进行加工处理的部件。它在控制器的控制下与内存交换信息,负责进行各类基本的算术运算和与、或、非、比较、移位等各种逻辑判断和操作。此外,在运算器中还含有能暂时存放数据或结果的寄存
5、器。控制器是整个计算机的指挥中心。它负责对指令进行分析、判断,发出控制信号,使计算机的有关设备协调工作,确保系统自动运行。控制器和运算器一起组成了计算机的核心,称为中央处理器,即CPU(CentralProcessingUnit)。通常把控制器、运算器和主存储器一起称为主机,而其余的输入、输出设备和辅助存储器称为外部设备。8存储器是计算机的记忆装置,为了对存储的信息进行管理,把存储器划分成单元,每个单元的编号称为该单元的地址。存储器内的信息是按地址存取的。向存储器内存入信息也称为“写入”。写入新的内容则覆盖了原来的旧内容。从存储器里取出信息,也称为“读出”。信息读出后并不破坏原来存储的内容,因
6、此信息可以重复取出,多次利用。 计算机的存储器可分为主存储器和辅助存储器两种,通常分别简称为主存和辅存。 输入设备如:键盘、鼠标、光笔、扫描仪等。 输出设备如:屏幕显示器、打印机、绘图仪、音箱等。9计算机软件在计算机中,数据是以电信号的方式存在的,并以二进制的形式来组织数据。程序是指令的有序序列(冯诺伊曼也定义了指令集),并与其所处理的同时数据必须存放在存储器中。程序设计是以算法为基础的,算法是一套自顶向下、逐步求精地去解决问题的方法。计算机语言是由符号与单词按特定语法构成的语句集合。每个语句都对应这特定的指令集而被计算机所接收、解释与执行。软件工程是为为解决62年的软件危机而产生的一套结构化
7、(或面向对象)的程序设计思想与方法。操作系统是对计算机系统软硬件资源进行管理,并对用户使用计算机提供良好界面的程序包。10计算机发展简史1 1第一代计算机(第一代计算机(1946194619581958年)年) 其主要特征是采用电子管作为主要元器件。其主要特征是采用电子管作为主要元器件。2 2第二代计算机(第二代计算机(1958195819641964年)年) 其主要特征是由电子管改为晶体管。其主要特征是由电子管改为晶体管。 3 3第三代计算计算机导论机(第三代计算计算机导论机(1964196419741974年)年) 其主要特征是用半导体中小规模集成电路代替分立元其主要特征是用半导体中小规模
8、集成电路代替分立元 件的晶体管。件的晶体管。 4 4第四代计算机(第四代计算机(19741974年至今)年至今) 其主要特征是以大规模和超大规模集成电路为计算机其主要特征是以大规模和超大规模集成电路为计算机的主要功能部件。的主要功能部件。 - - 注:与教材所讲有不同注:与教材所讲有不同11第二章 数据的表示数据的类型计算机内部的数据表示数据十六进制表示法八进制表示法12数据的类型计算机能处理的数据分类为:数值:计算文字:编辑图象:缩放与调整音频和视频:声效与特效13计算机内部的数据统一的数据表示法:对各种类型的数据都采用同一种数据表示。位(bit):二进制数字,是存储在计算机中的最小数据单位
9、。位模式:是一个位(bit)序列,即一个二进制数字串。字节(byte):长度为8的位模式,也是度量存储空间大小的单位。14表示数据以位模式来表示各种类型的数据(1)文本由文本语言的符号个数决定位模式的长度:log2符号个数=模式长度如ASC码,128个符号,128=27,所以位模式长度为7,即用7位二进制数字表示一个ASC符号。ASC码表要了解数字与字母排列。扩展的ASC码用一个字节表示一个符号,每字节的第一位为0。15(2)数的表示,见下章(3)图象位图图象:图象由象素点阵构成,每个象素由一个位模式表示,模式长度取决于对应象素亮度与色彩(或灰度)。矢量图象:整个图由基本直线与曲线的数学公式构
10、成。(4)音频和视频:对连续的模拟信号采样,并进行数字离散化后转换为位模式存储。16八进制和十六进制表示法十进制:基本数字为09每位不会出现10,逢10进1二进制:基本数字为01每位不会出现2,逢2进1八进制:基本数字为07每位不会出现8,逢8进1十六进制:基本数字为09、A、B、C、D、E、F(相当十进制1015)每位不会出现F,逢F进117个进制对照表18八和十六进制与位模式的转化每一个八进制数对应二进制的三位(3位模式)如:144(O)=001100100(B)7123(O)=111001010011(B)7123每一个十六进制数对应二进制的四位(4位模式)如:64(H)=0110010
11、0(B)2C1D(H)=0010110000011101(B)2C1D19第三章 数的表示数制的转换整数的表示EXCESS系统浮点表示法十六进制表示法20r进制转化成十进制转换公式: an .a1a0.a-1.a-m (r) = a*rn + + a*r1 + a*r0 +a*r-1+.a*r-m 10101(B)=24+22+1=21101.11(B)=22+1+2-1+2-2=5.75101(O)=82+1=6571(O)=78+1=57101A(H)=163+16+10410621十进制转化成r进制整数部分:除以r取余数,直到商为0,余数从右到左排列。小数部分:乘以r取整数,整数从左到右
12、排列。例100.345(D)=1100100.01011(B)100(D)=144(O)=64(H)100(D)=144(O)=64(H)=1100100(B)10025022521226232100010010.34520.69021.3802 0.7602 1.52021008128180441100166046161 1.0422整数的表示正数与负数正数与负数在计算机中数的符号也是用数码来表示的,一般用“0”表示正数的符号,“1”表示负数的符号,并放在数的最高位。例如:(01011)2(11)10(11011)2(11)1023原码、补码、反码在计算机中一个数可以采用原码、补码或反码表示
13、,上面讲到的正数与负数表示法即为原码表示法。 一个正数的原码、补码、反码是相同的,而负数就不同了。 无符号整数格式(最简单的数据表示):数的范围:0(12n)。 其中为N用于存储该数据的二进制数位. 24原码(符号加绝对值格式) 假设x为n位小数,用小数点左面一位表示数的符号,则:数的范围:(12n)(12n)。 零有两种表示: 正零为0.00;负零为1.00。25补码数的范围:(12n)1。零的表示是唯一的,即: 0.00。26反码数的范围:(12n)(12n)。零的表示有两种: 正零为0.00,负零为1.11。27Excess系统特点:能同时存储正负数,易于二与十进制数转换。正数(幻数)用
14、于转换过程,在8位模式下幻数为(2 n-1)=128 或(2 n-1)-1=127,并分别称Excess-128与Excess-127。Excess系统数据表示法(数据转换法):将十进制整数与幻数之和转换为二进制数,并补足N位。如:整数-25的Excess-127数据表示为01100110 D-25+D127=D102=B1100110=B0110011028浮点数表示法浮点数可以扩大数的表示范围。浮点数由两部分组成,一部分用以表示数据的有效位,称为尾数;一部分用于表示该数的小数点位置,称为阶码。一般阶码用整数表示,尾数大多用小数表示。一个数N用浮点数表示可以写成:NMReM表示尾数,e表示指
15、数,R表示基数。基数一般取2,8,16。一旦机器定义好了基数值,就不能再改变了。因此,在浮点数表示中基数不出现,是隐含的。注:浮点数表示法类似于数据的“科学表示法”29浮点数(注:与教材讲解略有不同)IEEE标准(32位单精度浮点数表示):32位=符号1位+指数Excess-127数8位+尾数23位 十六进制表示法(略) 阶码数符110.011(B)=1.100112+10=11001.12-10=0.1100112+11阶符尾数1100110011N=数符尾数2阶符阶码尾数的位数决定数的精度。阶码的位数决定数的范围。30第四章 数位运算算数运算逻辑运算移位运算31算数运算位运算包括算数运算与
16、逻辑运算。而算数运算包括整数与浮点数的四则运算。 整数的四则运算 以二进制补码形式的存储整数,可以进行加、减、乘、除四则运算。因计算机是以反复的加来实现整数的乘(*),而以反复的减实现除(/),如下示意,所以只介绍具有典型意义的加减运算。 如: 5 * 4 5 + 5 + 5 + 5 7 / 2 7 2 2 2 + 1 减3次2即商为3 余132整数加如:24加17得724对应补码形式:0001100017+(17为00010001)11101111+7100000111再如:127加3得130进位舍127对应补码形式:011111113+00000011+130错误结果12610000010
17、注:8位模式补码表示范围为128+127,超出该范围即产生错误。所以127加1得128,再加两次1,即得126。011111111000000033整数减、浮点数的加减整数减运算也是借助加法运算实现的,即减一个整数等于加一个相同值的负数。如:10162相当于101+(62)得39101即101补码:011001016262+11000010+393900100111浮点数的加减(见教材示例)以Excess-127保存指数的IEEE规范浮点数的加减,主要是两个数的指数取等值后,再按多项式使同项(同幂次)系数(尾数)相加。34逻辑运算一个二进制位(bit)的两个可能的值0、1,如果被决定为逻辑值,
18、即定义0为“假”而1为“真”,那么就可以实现逻辑运算。许多逻辑是应用于逻辑电路方面,或由“门电路”触发而实现的。逻辑运算真值表值非运算与运算或运算异或运算xyNOTxxANDyxORyxXORy001000010111000111111035对“与”,“或”理解的示例令P为教授,Q为党员,则某大学的相关会议参加者的命题检验如下: 某人的情况 党内专家 党员扩大(专家)会 PQPANDQPORQ000(不可参加会议)001011001111(可以参加会议)136移位运算左(右)移位:对于无符号二进制数串各位左(右)移1位,最高(低)位舍弃而最低(高)位补0。左(右)移位对应着二进制乘(除)2。如
19、:D59乘2为D118,而除2为29(实际为29.5)。0011101100111011移出舍弃001110110补入000111011移出舍弃再如:确定8位模式的第四位的值是0或1。设计“掩码”(修改另一位模式的位模式)为00001000:原位模式:abcdefgh掩码:00001000AND(“与”逻辑运算)0000e0000000000e右移3次(除8)原码能被8整除则结果e为1,否则e为非1(即为0)37第二部分计算机硬件38第五章计算机组成中央处理器主存储器输入/输出子系统的内部连接程序执行两种不同的体系结构39中央处理器 CPU的全称是“Central Processing Uni
20、t”,即中央处理器。 CPU的主要性能指标有:1 1主频主频 主频即CPU工作的时钟频率。CPU的工作是周期性的,它不断地执行取指令、执行指令等操作。这些操作需要精确定时,按照精确的节拍工作,因此CPU需要一个时钟电路产生标准节拍,一旦机器加电,时钟电路便连续不断地发出节拍,就像乐队的指挥一样指挥CPU有节奏的工作,这个节拍的频率就是主频。一般说来,主频越高,CPU的工作速度越快。 40 2 2外频外频 实际上,计算机的任何部件都按一定的节拍工作。通常是主板上提供一个基准节拍供各部件使用,主板提供的节拍称为外频。 3 3倍频倍频 随着科技的发展,CPU的主频越来越快,而外部设备的工作频率跟不上
21、CPU的工作频率,解决的方法是让CPU作频率以外频的若干倍工作。 CPU主频是外频的倍数称为CPU的倍频。 CPU工作频率倍频外频41 4 4地址总线宽度地址总线宽度 我们知道,PC(Personal Computer,个人计算机)采用的是总线结构。地址总线宽度(地址总线的位数)决定了CPU可以访问的存储器的容量,不同型号的CPU总线宽度不同,因而使用的内存的最大容量也不一样。如32位 地址总线能使用的最大内存容量为4GB。 5 5数据总线宽度数据总线宽度 数据总线宽度决定了CPU与内存、输入输出设备之间一次数据传输的信息量。Pentium以上的计算机,数据总线的宽度为64位,即CPU一次可以
22、同时处理8个字节的数据。42 6 6L1L1高速缓存高速缓存 缓存是位于CPU和内存之间的容量较小但速度很快的存储器,使用静态RAM做成,存取速度比一般内存快38倍。 L1缓存也称片内缓存,Pentium时代的处理器把L1缓存集成在CPU内部。L1高速缓存容量一般在32KB64KB之间,少数可达到128KB。 7 7L2L2高速缓存高速缓存 此即二级高速缓存,通常做在主板上,目前有些CPU将二级缓存也做到了CPU芯片内。 L2高速缓存的容量一般在128KB512KB之间,有的甚至在1M以上。43 8 8工作电压工作电压 工作电压是指CPU正常工作时所需要的电压。早期CPU工作电压一般为5V,而
23、随着CPU主频的提高,CPU工作电压有逐步下降的趋势,以解决发热过高的问题。 目前CPU的工作电压一般在1.6V2.8V之间。CPU制造工艺越先进,则工作电压越低,CPU运行时的耗电功率就越小。 9协处理器协处理器 含有内置协处理器的CPU可以加快特定类型的数值计算。某些需要进行复杂运算的软件系统,如AUTO CAD就需要协处理器支持。 Pentium以上的CPU都内置了协处理器。44CPU的封装方式采用Socket结构封装的CPU与Socket插座。采用Slot结构封装的CPU与Slot插座。45存储器 1 1基本概念基本概念 存储器是由一些能表示二进制数0和1的物理器件组成的,这种器件称为
24、记忆元件或存储介质。 常用的存储介质有半导体器件和磁性材料。例如,一个双稳态半导体电路、磁性材料中的存储元等都可以存储一位二进制代码信息。 位是存储器中存储信息的最小单位,称为存储位。由若干个存储位组成一个存储单元。一个存储单元可以存放一个字,此时称为字存储单元;也可以存放一个字节,称为字节存储单元。许多存储单元的集合形成一个存储体,它是存储器的核心部件,信息就存放在存储体内。46 如何区分存放在存储体中的信息,也就是说怎样将存储体中若干个存储单元加以识别呢? 解决这个问题的方法是给每个存储单元编上号,这个编号就称为该单元的地址。若一个单元存放一个字节,则相应的地址称字节地址;若一个单元存放一
25、个机器字,那么,相应的地址称为字地址。 一个存储器中存储单元的总数称为该存储器的存储容量。计算机中存储器的容量越大,能存储的信息就越多,计算机的处理能力也就越强。 表示存储容量的单位一般用字或字节。例如,32KB表示32K字节,128KW表示128K字,其中 IK 1024。 47 存储器的两个基本操作是写入信息和读出信息(或称存数和取教)。 存储器从接到读出命令,到指定地址的信息被读出,并稳定在存储器数据寄存器或数据总线上为止的时间,称为读出时间(亦称取数时间)。 反之,将数据寄存器或数据总线上的信息写入存储器的时间称为写入时间。 在连续两次访问存储器时,从第一次开始访问到下一次开始访问所需
26、的最短时间称为存储周期,它表示存储器的工作速度。482 2存储器分类存储器分类(1)按存取方式分类:随机存储器(RAM )和顺序存储器(SAM),读写存储器和只读存储器(ROM)。(2)按存储介质分类:磁性材料存储器,半导体存储器和激光存储器。 (3)按功能和存取速度分类:寄存器型存储器、 主存储器和外存储器。 3 3存储器的性能指标存储器的性能指标(1)存储容量(capacity)(2)存取速度(access time)(3)数据传输率(data transfer rate)(4)位存储价格(cost per bit)49半导体存储器(1 1)RAMRAM RAM的全名是读写随机存取存储器(
27、Read Write Random Access Memory),本应缩写为RWRAM,但它不易发音,故流行称为RAM。 三个特点:可以读出、也可以写入; 所谓随机存取,意味着存取任一单元所需的时间相同;当断电后,存储内容立即消失,称为易失性(volatile)。 -(3)NVRAM NVRAM是一种非易失性的随机读写存储器。既能快速存取,而系统断电时又不丢失数据。实际上,它是把SRAM的实时读写功能与E2PROM的可靠非易失能力综合在一起。50(2 2)DRAMDRAM与与 SRAM SRAM RAM可分为动态(Dynamic RAM)和静态(Static RAM)两大类。 动态随机存储器D
28、RAM是用MOS电路和电容来作存储元件的,由于电容会放电,所以需要定时充电以维持存储内容的正确,这称为“刷新”,例如每隔2ms刷新一次,因此称之为动态存储器。 静态随机存储器SRAM是用双极型电路或MOS电路的触发器来作存储元件的,没有电容造成的刷新问题。只要有电源正常供电,触发器就能稳定地存储数据,因此称之为静态存储器。 DRAM的特点是高密度,SRAM的特点是高速度。512只读在储器(1 1)ROMROM ROM为只读存储器(Read Only Memory或译唯读存储器)的缩写。 ROM的用途很广,如与微程序设计相结合。 与操作系统及高级语言相结合,与应用软件相结合、与无磁盘网络工作站等
29、。 (2 2)PROMPROM与与EPROMEPROM PROM是可编程只读存储器(Programmable Read Only memory)的缩写。它与ROM的性能一样,存储的程序在处理过程中不会丢失、也不会被替换。 52 EPROM是可擦除可编程只读存储器( Erasable Programmable Read Only Memory)的缩 写。它的内容通过紫外光照射可以擦除,这种灵活性使EPROM得到广泛的应用。(3 3)E2PROME2PROM E2PROM是 电 擦 除 可 编 程 只 读 存 储 器(Electrically Erasable Programmable ROM)的
30、缩写;它包含了 EPROM的全部功能,而在擦除与编程方面更加方便这就使E2PROM比EPROM有更大的灵活性和更广泛的适应性。53输入/输出(外存储器)1磁记录的基本概念磁记录的基本概念(1 1)磁记录密度()磁记录密度(densitydensity) 面密度(areal density)。面密度等于道密度与位密度的乘积。 道密度(track density)。道密度等于磁道间距的倒数,而磁道间距(track pitch)则是相邻两条磁道中线间的距离 位密度(bit density)。磁道上单位长度存储的二进制信息量称为位密度也称为线密度。54(2 2)磁记录方式)磁记录方式 磁记录方式主要有
31、两种:水平记录方式和垂直记录方式。 水平记录方式(horizontal recording)是利用磁头磁场的水平分量在介质上写入信息,使介质沿其表面进行磁化。通常也称为横向记录方式。 缺点:是存在自退磁效应,每个小磁畴的距离不能太近,这就限制了记录密度的进一步提高。 55 垂直记录方式(vertical recording)是利用磁头磁场的垂直分量在介质上写入信息,使介质的磁化方向垂直于介质表面。 优点:是相邻位的退磁磁场几乎为零,每个磁束之间不会抵消,反而会加强,这就适合于进行高密度的磁记录。 区位记录方式(zone bit recording,简称ZBR)也称等密度记录方式。 等密度记录就
32、是保持所有磁道上记录的位密度相等。为此,可以采用两种方法: 匀线速度控制法。区域位密度法。56(3)磁记录编码技术 磁盘机曾广泛使用的编码方法有: FM调频制(Frequency Modulation)编码,M0.5; MFM改进调频制(Modified Frequency Modulation)编码, M 1;M2FM改进的改进调频制(Modified MFM)编码, M1,且可靠性、信噪比均得到改善。 还有一类成组编码方法,它是把记录的数据序列按若干位编成一组,对应于每种组态有一种编码序列与之匹配。例如 GCR(45)成组编码。57GCR(45) GCR(45)成组编码(Group Cod
33、ed Recording)就是把数据按4位编成一组,与之对应产生出5位编码序列。 编码规则是:禁止使用连续 3位以上的“0”代码组合。我们知道,4位有16种组态,5位则有32种组态,除掉含有3位以上连续“0”的组态, 5位编码序列尚有17种组态可用。选用其中16种与4位数据序列对应即可。 GCR编码效率M0.75,具有一定的自同步能力。已应用于磁带机与软磁盘机中。58GCR(45)编码数据序列d1d2d3d4GCR编码序列e1e2e3e4e500000001001000110100010101100111100010011010101111001101111011111100111011100
34、101001111101101011011010111110100100101010010111111001101011100111159 注意:数据序列通过编码电路转换为编码序列后,它还不等于就是记录序列。当通过磁头往磁表面上写数据时,还要把编码序列按一定规则变成记录脉冲。例如在GCR编码中,最后是用逢“ 1”翻转不归零制(Non Return to Zero, NRZ1)规律加以记录的。 目前,比较先进并在硬磁盘机中广泛使用的编码是 RLL(2,7)编码。这是限制两次翻转之间距离的编码,或称游程长度受限码(RunLength Limited Code,RLL)。 编码规则是:在编码序列中,
35、两个“1”之间至少有2个“0”,最多有7个“0”。60ARLL(2,7) 美国最近设计出的编码,即高级RLL码( Advanced RLL)。它把编码效率提到M2,将在未来更高密度的磁盘机中得到普遍的应用。数据序列RLL(2,7)编码序列111000000101001100111100001001001000010000001000010010000001000612软磁盘及其设备(1)软磁盘 软磁盘(原名flexible disk,后来人们戏称为floppy disk)或译为软磁盘,是人们广泛使用的一种廉价介质。 它是在聚酯塑料(mylar plastic)盘片上涂布容易磁化并有一定矫顽力的
36、磁薄膜而制成的。所用磁介质有一氧化铁、渗钴氧化铁,对于高密度介质(超过 30000bpi)则采用钡铁氧体、金属介质等。 软盘的主要规格是磁片直径。1972年出现的是8英寸软盘。1976年与微型机同时面世的是5.25英寸软盘,简称 5英寸盘。1985年日本索尼(sony)公司推出3.5英寸盘。1987年索尼公司又推出2.5英寸软盘,简称2英寸盘。目前已出现1.5英寸软盘,只是未批量生产。62 在磁片直径不断缩小的同时,软盘容量却连续扩大,以5英寸盘为例,当初的单面单密度容量为125KB,单面双密度或双面单密度为250KB,双面双密度则为500KB。 所谓单面是只用一面,双面是两面都用。所谓单密度
37、是用FM编码的,双密度(又称倍密度)是用MFM、M2FM或GCR编码记录的。 5寸软盘外观63 3英寸盘的容量有1MB、2MB、4MB等数种。 自 1987年IBM选择2MB的3.5英寸盘作为PS2系列的配置后,2MB盘正成为事实上的工业标准。随着膝上型计算机的流行,3英寸盘成为软盘的主流产品(2)驱动器与适配卡 一个完整的软盘存储系统是由软盘、软盘驱动器、软盘控制适配卡组成。 软盘驱动器(floppy disk drive)由机械运动和磁头读写两部分组成。机械运动部分又由主轴驱动系统和磁头定位系统两部分组成。 通常,主轴驱动系统使用直流伺服电机,带动磁盘以每分钟300转以上的速度旋转,并使磁
38、头定位进行磁盘信息的读写。64 软盘驱动器简称软驱。它的全部机械运动与数据读写操作,必须在软盘控制适配卡( FDC adapter)的控制下进行。 而适配卡正好把驱动器与CPU系统板联系起来,使磁盘存储系统成为整个计算机系统的一个有机组成部分。(3)软盘的使用与维护 不要弄脏,不要用手摸盘面,不要把它放在高温、潮湿、强磁、震动的地方。也不要用硬笔在封套上写划,标签要写好再贴。写保护缺口的贴上或取下,一定不要怕麻烦,携带时不要图省事,随便放在书包里,应该装在盒内。65软盘的格式软盘的格式软盘低密度高密度扇区磁道容量扇区磁道容量5.25英寸940360K15801.2M3.5英寸980720K18
39、801.44M663硬磁盘及其设备 硬盘是计算机系统中最主要的辅助存储器。硬盘盘片与其驱动器合二为一体,称为硬盘机,后来人们叫熟了,统称为硬盘。硬盘通常安装在主机箱内,所以无法从计算机的外部看到。(1 1)硬盘的种类)硬盘的种类 按硬盘的几何尺寸划分,硬盘分为3.5英寸和5.25英寸两种。近年来,市场上主要以3.5英寸为主。 按硬盘接口划分,主要有IDE、EIDE、Ultra DMA和SCSI接口硬盘。67硬盘的工作模式 20世纪90年代初期,PC机多采用IDE接口硬盘。IDE接口标准的硬盘工作方式只能是标准模式。在标准模式下,硬盘最大容量只能是528MB,硬盘与主机之间采用PIO方式(程序控
40、制输入输出方式)传输数据。突破528MB容量限制的问题,因此推出了EIDE标准。EIDE接口标准的工作模式有三种:标准模式(NormalMode),该模式与IDE的工作模式完全相同。逻辑块地址模式(LBAMode),也称大数据块模式。它突破了硬盘空间528MB的管理限制,支持的硬盘容量最大达到8.4GB。68大模式(Large Mode),也称大磁道模式,该模式是为了方便那些不支持 LBA模式设置而准备的一种工作模式,它支持的硬盘最大容量为1GB。 主板上提供两个EIDE接口,分别为EIDE1、EIDE2。一个EIDE接口可以连接符合EIDE标准的包括硬盘机、光盘驱动器等在内的2个设备。若一台
41、计算机只有一个硬盘机和一个光盘驱动器,建议优先考虑将硬盘接入EIDE 1、光盘驱动器接入EIDE 2,这样可以提高运行速度,尤其是对提高播放VCD速度很有好处。当一个 EIDE接口接2个EIDE设备(如接2个硬盘)时,硬盘上的跳线就是用来确定该硬盘是第几个设备的。69硬盘接口 由于硬盘容量的增大和读写速度的提高,必然要求硬盘接口有更高的传输率,Intel和Quantum联合推出了最新的硬盘接口标准Ultra DMA,它所采用的数据传输方式与以往不同。 在PIO方式中,CPU直接进行读写控制,而Ultra DMA采用的数据传输方式称为直接存储器存取数据传送方式,传输效率比 PIO模式高得多。Ul
42、tra DMA方式工作的硬盘仍然采用EIDE接口和主机相连。70 目前采用 Ultra DMA方式工作的硬盘有Ultra DMA33和Ultra DMA66两种。Ultra DMA33硬盘是采用和 EIDE标准相同的数据线与主板EIDE接口连接(一根40针的数据线)。 Ultra DMA66使用的是 80针接口,这样就出现了与 EIDE接口不兼容的问题,这个问题的解决办法是在传统的40针标准的EIDE信号线和地线之间穿插了40条线,以此方法来实现与现行接线插口上的兼容。 SCSI是一种智能化的接口,特别适合于并发数据的处理请求。与IDE接口相比,SCSI接口提供了更强的扩充能力。 SCSI接口
43、可以以菊花链方式挂接7个不同的外部设备。现在PC机服务器经常采用SCSI接口。71(2 2)硬盘主要的性能指标及选购)硬盘主要的性能指标及选购 容量:硬盘的容量指的是硬盘中可以容纳的数据量。 转速:转速是指硬盘内部马达旋转的速度,单位是RPM(每分钟转数)。 平均寻道时间:平均寻道时间指的是磁头到达目标数据所在磁道的平均时间,它直接影响到硬盘的随机数据传输速度。 缓存:缓存的大小会直接影响到硬盘的整体性能72磁带及其设备(1)磁带的种类 可按磁带宽度可分 按磁带外形可分为两种:卡式盒带,磁带盒 按记录方式分为两种:纵向记录方式、螺旋扫描记录方式(2)磁带文件的顺序性 由于磁带介质很窄且极长,必
44、须在两个轮盘之间有条不紊地传送、盘绕才能完成读写操作,这就决定了磁带记录的顺序性。 然而,对于面积有限的磁盘,人们可以面对整个盘面,直接读写某个磁道上、某个扇区内的某个字段,完全不必从0磁道顺序查到399磁道,这就决定了磁盘记录的随机性。73光盘存储器1光盘存储器的主要类型 固定型光盘,又叫只读光盘 追记型光盘,又叫只写一次式光盘 可改写型光盘,也叫可擦写型光盘2光盘驱动器 工作方式有两种,恒定线速度和恒定角速度。(1)恒定线速度(CLV) 无论光驱读取头是在内轨还是在外轨读取数据,数据传输率都保持不变,而光驱的转速随读取头在光盘轨迹的位置而变化,读取头远离光盘中心,光驱转速逐渐下降,使读取头
45、在单位时间内扫过光盘相同的轨迹长度,读取相同数据量,从而可以以相同的速率读出所有的数据。74(2 2)恒定角速度()恒定角速度(CAVCAV) 与CLV正好相反,它是让数据传输率发生变化,保持光盘固定的转速。光驱读取头从光盘中央向外圈移动时,数据传输率是递增的,并且数据传输率完全取决于数据所存放的位置。 购买光驱主要应考虑两方面的问题: 其一是光驱的倍速; 其二是纠错能力,“纠错”能力实际上是对“烂盘”(盘片质量不太好、有缺陷)的“读盘”能力。75子系统的内部连接(系统总线) 总线结构1单总线结构 在单总线结构中,计算机系统的部件如CPU、主存储器及输入输出设备等,都挂在一条总线上,它们之间以
46、相同的形式进行通信,故称单总线 。 CPU工作期间,单总线上的信息流动可以描述如下:首先,CPU将PC的内容(指令地址信息)和读命令(控制信息)送到总线,并将总线上的所有设备与总线送来的地址进行比较,只有与此地址相同的设备(主存)才接受命令,执行相应的操作(启动主存操作,将指令取出,经总线数据线送到CPU);76 然后,CPU检查操作码,决定下一步要执行的操作是在CPU内部进行,还是要经总线访问主存或1O设备。772双总线结构 在这种结构中有两条总线:主存总线及输入输出总线。前者负责CPU与主存、通道之间的信息传送;后者负责多台外部设备与通道及外部设备之间的信息传送)。 在CPU工作期间,取指
47、令通过主存总线完成。指令取出后,CPU检查操作码决定下一步操作是在CPU内部进行还是访问主存或IO操作。 若访问主存,则仍由主存总线完成;若IO操作,则交给通道去处理,通过输入输出总线完成。78793三总线结构 三总线结构是指在计算机系统中各部件用3条各自独立的总线构成信息通路。这3条总线是:主存总线,它负责CPU与主存的信息传送;IO总线,它负责IO设备之间以及IO设备与CPU之间的信息传送;DMA总线,即直接主存访问总线,它负责高速外部设备与主存的信息传送。 在计算机工作期间,CPU通过主存总线取到指令。然后,CPU检查操作码,决定下一步要执行的操作是在CPU内部进行,还是要访问主存或IO
48、设备。 由于IO设备与主存不在一条总线上,因此IO设备的寻址与主存单元寻址是不统一的,即采用单独编址方法。80 CPU通过访存指令访问主存,指令中给出存储单元地址;CPU通过IO指令访问IO设备时,由指令中给出IO设备接口寄存器的地址。因此,指令操作码指示CPU将使用哪条总线。81 在三总线系统中,访问主存和访问IO设备各有单独的指令。当IO指令的地址码涉及到高速外设时(如磁盘),将使用DMA总线,直接在主存与高速外设之间传送信息。 三总线结构不允许外设之间直接传送信息,只能经过主存间接传送。 总线的控制与通信1总线的控制方式 系统总线多采用集中控制方式,解决总线使用权的控制问题。按各部件使用
49、总线优先次序的确定方法的不同,集中控制与分布控制方式均对应有3种实现方法:串行链接、定时查询及独立请求。下面讨论集中控制方式的3种实现方法。82(1)串行链接方式 串行链接方式,又称链式查询方式,需要在系统总线中增加3根控制线:总线忙(BS)线,它有效时,指示总线正在被某部件使用;总钱请求(BR)线,它有效时,指示总线上至少有一个部件请求使用总线;总线响应(BG)线,它有效时,指示总线控制部件正在响应某个部 件的总线请求。 在串行链接方式中,总线上所有的部件共用一根总线请求线。若有部件请求使用总线时,均需经此线发总线请求到总线控制器。由总线控制器检查总线忙否,若总线不忙,则立即响应,即发总线响
50、应信号,经总线响应线BG串行地从一个部件送到下一个部件,依次查询。83 若响应信号到达的部件无总线请求,则该信号立即传送到下一个部件;若响应信号到达的部件有总线请求,则信号便截住,不再传下去。84串行链接方式的特点是采用硬接线逻辑,将各部件扣链在总线响应线上。因此,优先级则固定,有较高的实时响应性。此外,只需很少几根控制线就能按一定优先次序,实现总线控制,结构简单,扩充容易。(2)定时查询方式 定时查询方式采用一个计数器控制总线使用权。它仍公用一根请求线,当总线控制器收到总线请求信号,判断忙线不忙时,计数器开始计数,计数值通过一组地址线发向各部件,每个部件与总线接口均有一个地址判别线路。当地址
51、线上的计数值与请求使用总线设备的地址一致时,该设备获得总线控制权,置忙线为“1”。同时,中止计数器的计数及查询工作 。85(3)独立请求方式在独立请求方式中,每个部件均有一对总线请求线(BR)和总线批准线(BG),而不采用共享请求线的方式。86 当总线上的部件需要使用总线时,经各自的总线请求线发送总线请求信号,在总线控制器中排队。 当总线控制器按一定的优先次序决定批准某个部件的请求时,则给该部件发送总线响应信号,该部件接到此信号,就获得了总线使用权,开始传送数据。878889第六章 计算机网络网络OSI模型网络分类连接设备互连网与TCP/IP90网络计算机网络是利用现代通讯设备和线路,将分布在
52、各个不同地理位置的、功能不同且各自独立的多个计算机系统连接起来,在网络软件的支持下,实现互相通讯和资源共享的系统。计算机网络的主要功能:(1)信息交换(2)资源共享(3)分布式处理91OSI模型模型是由国际标准化组织制定的用于网络设计的指南。OSI称开放式互连系统,它允许任两个不同的计算机系统互相通讯而无需考虑其底层体系结构。OSI的七层结构:数据A数据B1 应用层 应用层 2 表示层 表示层 3 会话层 会话层 4 传输层 传输层 5 网络层 网络层 6 数据链路层 数据链路层 7 物理层 物理层 传输媒介 92OSI个层的功能数据(消息)从A发向B,实际就是A的各层(7至1层)工作后,经媒
53、介(线路)传向B,再由B的各层(1至7层)工作后得到数据(消息)。消息的数据称为“报文”,它在各层中被逐渐分解组合(如报头,报尾等)并加以检验。(1)物理层:任务是透明地传输位(比特bit)流,即传输的单位是“比特”。该层考虑何电压表示和识别“0”或“1”,及电缆插头的脚数和定义脚的连接。注意:传输介质(双绞线、同轴电缆、光纤等线路)本身并不在物理层。“透明”是一个实际存在的事物看起来好象不存在一样,透明地传输即说明比特流不受实际电路影响而传输后不变化。93(2)数据链路层:任务是在两个相邻结点间的线路上无差错地传输“帧”(读zheng,幅frame)。加报头把别特流组构成“帧”,而报尾加控制
54、信息(同步、地址、差错控制、流量控制等),可检验传输差错或重发帧,使“点对点传输”的接收端能正确无误地接受到报文。该层将有可能出差错的实际线路,变为在“网络层”向下看似乎是一条不出差错的线路。(3)网络层:任务是“站到站传输”信息,传输的单位是“分组”或“包”,该层选择合适的路由,使发送运站输层下来的包能准确无误地按地址找到并交付接受站运输层,此为该层的寻址功能。注意:这里的“网络是专用词”。对于通讯子网,由于路由问题很好解决,所以该层可省略。94(4)运输层:任务是依通讯子网的特性,合理利用网络资源并可靠地进行“端到端传输“报文。“报文”是由一个或多个信息包组成,报文较长时可以分组并交由网络
55、一下各层处理。该层在源站与目的站两个主机的进程之间,建立运输连接以透明地传送报文。即它向上层提供一个可靠的端到端服务,使上面看不到运输层以下的数据通讯细节。通讯子网内各个各结点和连接各通讯子网的路由器都没有运输层,运输层仅存在于子网之外的主机中。运输层以上各层不再关心信息传输问题,所以运输层在计算机网络体系结构中十分重要。95以下三层可统归“应用层”(5)会话层:从此不再参与数据传输,其任务是对数据传输进行管理,它在两个互相通讯的进程之间建立、组织与协调交互(会话)。如会话中的同步,整条信息是否重发,确定是双工(同时收发)还是单工(交替收发)通讯等。(6)表示层:任务是解决用户信息的语法表示。
56、表示层将欲交换的数据从适合于某一用户的“抽象语法”变换为适合于OSI系统内的传送语法。抽象语法包括数据的语法(格式)和语义(数据的意义),因为不同系统可能具有不同的编码格式。96(7)应用层:任务是定义通用的网络应用程序,它直接为用户提供服务。注意:会话层与表示层的功能经常被包含在应用层中,从而省略会话层与表示层。网络分类按考虑问题的不同角度,可使网络有不同的分类,如按网络总线的“拓扑结构”,网络可以分为集中式、分散式和分布式等;按网络的作用范围,网络可分为局域网(LAN)、城域网(MAN)或广域网(WAN)等。97网络连接设备(1)中继器:增强信号的设备。它网络的物理延伸,可以提供信号再生,
57、免除长距离信息传输所造成的通讯信号衰减所造成的错误。(2)网桥:可以连接同一网络内的两个段或连接两个同类网络的通讯控制器。(3)网关:可以连接两个不同类网络(咎由自取不同的网络协议)的通讯控制器。(4)路由器:同网关,或可用以连接两个以上的同类网络的通讯控制器。(观点不同)98互连网与TCP/IP互连网:即国际互连网(Internet),它是连接世界各地的各种局域网、城域网和广域网所构成的交互式网络。TCP/IP:传输控制协议/网际协议(网络通讯的一组规则),它是Internet的核心,要求连入Internet的每台计算机都有一个32字节的IP地址。FTP:文件传输协议,在Internet中用
58、以解决具有不同编码系统的机器之间进行文件传输。SMTP:简单邮件传输协议,Internet山支持电子邮件(email)的协议,实际要结合邮局协议POP的使用。特点是SMTP邮件地址系统。99TELNET:是Internet上允许远程登录的通用客户/服务器程序。(将本地终端模拟为远程终端)WWW/Web:称“万维网”,多媒体稳当的集合。HTTP:超文本传输协议,超文本是在“万维网”上构成网页的、包含特殊符号的多媒体文本。浏览器:接收、解释并显示超文本的程序。URL:同意资源定位器,在Internet上用方法、主机、端口和路径的地址格式指定信息(的位置)。100第三部分计算机软件101第七章操作系
59、统定义演化组成部分主流操作系统102操作系统定义计算机系统由计算机的硬件系统与软件系统构成,而计算机的软件系统又是分为系统软件与应用软件,其中的操作系统就是主要的系统软件之一。操作系统是控制和管理计算机系统内各种硬件和软件资源, 有效地组织多道程序运行的系统软件(或程序集合),是用户与计算机之间的接口。 主要功能:进程管理、存储器管理、处理机管理、设备管理、文件管理、用户界面与接口等。103计算机系统的层次结构用户用户应用软件支撑软件管理信息系统、测试工具、飞机订票系统、剪辑工具、地理信息系统、项目管理工具、数字计算软件包等语言转换工具等系统软件语言编译程序、连接装配程序、数据库管理程序、网络
60、软件等操作系统操作系统计算机硬件104演化(操作系统的发展)(1)批处理系统:早期计算机系统,程序员对机器没有控制与交互,程序(作业)都以穿孔卡片的形式交操作员执行后打印结果。操作员搜集所有程序员的作业成批运行。(2)分时系统:在引入多道程序概念后产生了分时(对CPU时间的共享),程序员直接而不是通过操作员来操作系统,使多程序共享系统资源,而用户的每个作业都可透明地得到CPU的一个“时间片”。进程是存储器中等待资源的程序,而作业是要运行的程序。(3)个人系统:当个人计算机(PC机)产生后,独占资源的单用户操作系统(个人系统)应运而生。如DOS。105(4)并行系统:一般的计算机是用一个CPU逐
61、个处理程序,即串行系统,而当一个机器中安装了多个CPU并使没个CPU都可以处理一个程序或程序的一部分,则产生了多任务的并行系统。(5)分布式操作系统:在计算机网络发展到了交互式网络阶段,则可利用分布在不同地理位置上的资源共同完成一个作业,而且程序的不同部分可以在网络内不同的计算机上运行。106操作系统的组成部分一般讲,操作系统有四大基本管理功能:存储管理、进程管理、设备管理与文件管理。(1)存储管理可以分为单道程序与多道程序的内存管理单道程序的内存管理,是除少量用于必要的操作系统存储外,基本使一个程序独占内存。即一个程序载入内存并运行,之后再用另一程序取代,操作系统不断地反复此过程。这里的问题
62、是:程序大过内存容量则无法执行;除单一程序的独占性外,数据还要不断地输入/输出,由于CPU与I/O设备速度的差异就造成CPU的不断等待(空闲)而使效率低下。107多道程序的存储管理多道程序的存储管理允许在同一时刻载入多个程序(除必要的操作系统外多程序共存)并可以同时运行这些程序。多道程序的存储管理涉及两种存储技术:非交换技术即程序在运行期间始终驻留内存,如分区调度与分页调度;交换技术即在运行过程中程序可以在内存与磁盘之间多次交换,如请求分页调度与请求分段调度。各内存管理技术的发展都是后者对前者的逐步改进。108分区调度:该技术仍是将一个程序完整地装入内存并占用连续的地址。它将内存划分为不等长的
63、若干区,每区保存一个程序,CPU在各个程序之间交替服务。CPU从一个程序开始执行指令,当有I/O操作产生或该为程序服务的时限到达时,就保存最近执行的指令地址(为返回继续执行该程序保留入口)并转入下一个程序去执行。CPU对内存中每个区均如此处理,直到最后一个区也按如此的步骤处理后再返回第一个程序。分区大小是预定义的,所以随着新程序的不断载入,终会出现区中未被占用的“空闲区”(碎片),当空闲区过多时内存可以压缩分区移动空闲区创建新的分区,但增加系统负担。109分页调度:它将内存分为大小相等的若干部分并成为“帧”,而程序则被分为大小相等的若干“页”,一般来说帧、页与与系统从存储器提取信息块的大小一致
64、。它虽然仍要求把程序整个装入内存,但不要求装入内存的连续地址。页被载入内存的帧中,但一个程序的不同页可以被载入内存中的不同帧,连续的页也不一定被载入连续的帧中。这样新程序的载入就不必在所有连续的帧出现后再载入内存。分页调度改进了分区调度的效率,但由于只有整个程序被载入后才能运行,所以当内存为此提供的可替换的帧不够时程序仍无法载入。110请求分页调度:它不仅不要求程序占用连续地址的内存,还不需要整体装入内存。该技术允许程序的页被依次载入内存并运行后再为其它页所取代,即不要求程序的所有页被同时载入,而可以被分批载入内存运行。请求分段调度:类似分页雕塑技术,因程序由主程序与若干子程序组成,所以程序可
65、以按程序的观点划分为若干段后被载入内存并执行,之后再由同一程序的其它段或别的程序段来取代。虚拟内存:以上内存管理技术使得一个部分被载入内寸执行而另一部分仍在磁盘中,但是用户感觉一个程序已经被整体载入内存,故占用磁盘的部分相当于“虚拟内存”。111进程管理(略)(1)程序、作业、进程(2)程序、作业与进程三者鲜花转换的状态图程序三态:保持状态、就绪状态、运行状态(3)调度器:作业调度器、进程调度器(4)队列:作业队列、就绪队列、I/O队列(5)进程同步:死锁、饿死112设备管理的职责文件管理的职能主流操作系统:Windows2000UNIXLinux113第八章算法概念三种结构算法的表示算法的定
66、义子算法与基本算法递归114算法的概念算法的定义:(1)通俗讲,算法就是一种解题的方法。 它可以是一组独立于计算机系统的解题步骤(2)严格说,算法是由若干条指令组成的有穷序列。算法必须满足五大特性:输入输入:具有0个或多个输入的外界量(算法开始前的初始量) 输出输出:至少产生一个输出,它们是算法执行完后的结果。 有穷性有穷性:每条指令的执行次数必须是有限的。 确定性确定性:每条指令的含义都必须明确,无二义性。 可行性可行性:每条指令的执行时间都是有限的。有序集合、明确步骤、产生结果、有限时间内终止。115算法和程序的关系算法的含义与程序相似,但二者有区别。程序不一定满足有穷性(可能有死循环);
67、程序中的指令必须是机器可执行的,与计算机系统相关,而算法中的指令(或步骤)则可以与计算机系统无关,即独立于计算机系统。一个算法若用计算机语言(程序设计语言)来书写,则它就可能是一个程序。算法的描述可以用人能看懂而机器不认的工具,如流程图表、伪代码(也可以是算法语言)程序设计语言也称算法语言,但它是把算法进一步书写为程序(计算机能识别执行的语言)116算法示例题目:从一组正整数中找出最大的正整数。算法思想:假设某一固定的地方总是放着最大值。(1)将大规模的问题限制在小规模的范围内解决;(2)集中精力解决问题中的关键步骤;(3)尽量将性质相同的步骤合并为一步进行重复;(4)边界问题:加上进入与结束
68、关键重复步的处理;(5)将正确解小规模问题的方法推广到大规模问题;(6)进一步精确与优化解决问题的过程。注意:在解题的多方法中选择具有通用性强的方法;选择通俗易懂的工具来正确描述算法。117算法模式: :输入列表算法一种逐步解决问题或完成任务的方法输出列表输入、过程、输出: :12813911输入列表算法最大值1212列表(步骤1)最大值128列表(步骤2)最大值1313列表(步骤3)最大值139列表(步骤4)最大值1311列表(步骤5)13输出列表118定义动作:12813911输入列表寻找最大值(步骤1)将最大值置为第一个数(步骤2)如果第二个数大于最大值,将第二个数置为最大值(步骤3)如
69、果第三个数大于最大值,将第三个数置为最大值(步骤4)如果第四个数大于最大值,将第四个数置为最大值(步骤5)如果第五个数大于最大值,将第五个数置为最大值13输入列表精化:12813911输入列表寻找最大值(步骤0)将最大值置为0(步骤1)如果当前数比最大值大,将最大值置为当前数(步骤5)如果当前数比最大值大,将最大值置为当前数13输入列表119泛化:输入列表寻找最大值将最大值置为0重复下一步骤N次如果当前数比最大值大,将最大值置为当前数输出列表优化:对算法进一步精简等。注意:算法要求通用性,即机器无关性,在那里都可以实现。算法描述工具:算法要求用通用性强表示方法来书写,即谁都能看得懂。一般可以采
70、用自然语言,通用符号、流程图、伪代码等书写算法。目的是研究算法的人与进一步编程序的人来阅读。120三种基本结构依据结构化算法与程序设计思想,任何一个算法或程序都可以由顺序、选择和重复(循环)这三种基本结构复合而成。顺序结构是算法或程序的最基本的结构,因任何指令都是被顺序地执行的。选择结构是根据逻辑判断进行指令段跳转的结构,即在两个或两个以上的指令段中,依据条件选中一段并跳转到该段指令继续执行。重复结构是对相对简单而独立的指令段循环执行的结构。三种基本结构都有对应的算法描述手段和程序设计语句支持。121算法描述工具之一:流程图顺序结构:选择结构:重复结构:动作1假测试真while条件假动作2真动
71、作系列B动作系列A动作系列动作n122算法描述工具之一:伪代码以“从一组正整数中找出最大的正整数”为示例。 FandLargest Input:Alistofpositiveinteger1.SetLargestto02.While(moreintegers)3.2.1if(theintegerisgreaterthenLargest)4.then5.2.1.1SetLargesttothevalueoftheinteger endif/2.1可以被定义为一个子算法endwhile3.RetuneLargest4.end123基本算法在算法中被频繁使用的、最简单的、最基本的算法:(1)求和(累
72、加器):初始化:S=0;重复:S=S+数;(2)乘积(累乘器):初始化:N=1;重复:N=N*数;(3)求最大或最小值:类似前面的示例(4)排序:将任意的一组数按“不小于”关系重新排列。选择排序冒泡排序插入排序(5)查找:给定某一特定值,在一组数中查找是否有该值。顺序查找折半查找(6)递归:把自身作为子算法重复调用以获得结果的算法。124第九章程序设计语言演化构建程序程序执行语言的分类过程化语言C(略)125演化/发展计算机语言,是依据预定义的语法规则而给出的预定义的语句集合,这些语句可组成程序。(1)机器语言(计算机产生之初)由二进制位串组成的语言,语句可以由机器直接接收、识别与执行,其所书
73、写的程序不必再经过针对于机器指令的翻译过程。(2)符号语言/汇编语言(二十世纪五十年代)语法成份都是助记符号的语言,解决了机器语言的难于读写的问题,但仍与机器相关。汇编语言程序,需针对于不同机器的指令系统,由“汇编程序”翻译为能在该机执行的程序。126(3)高级语言(二十世纪六使年代)一种尽量接近自然语言的计算机语言(如:计算的书写尽量贴近数学公式,语句功能的描述尽量贴近自然语言),它具有机器无关性(所以才有了各具特点的语言),摆脱了程序的书写与机器硬件的密切性。与符号/汇编语言程序类似,高级语言需要经过“编译程序”或“解释程序”对机器指令的翻译后才能在具体的机器上执行。高级程序语言具有机器无
74、关性,但是翻译程序必须是针对具体机器(过CPU系列)的。一种语言的程序是否能被翻译在各种机器上执行的性质,叫做该程序的“可移植性”。高级语言程序的翻译一般通称“编译”,但是“编译程序”翻译的形式主要是对程序的“整篇翻译”,而“解释程序”主要是对程序的“逐句翻译”。127构建程序构建程序的过程,实际就是从编写源程序直到程序执行得到结果的过程。它主要分为一下步骤:(1)编辑源程序为文本文件原则上可任选一种“字处理程序”,将手写源程序编辑为文本文件后作为编译程序的输入。(2)编译为目标文件接收源程序的文本,经过“预处理”扫描与翻译等两三步将其编译为目标程序(文件)。(3)链接为可执行文件将组成程序的
75、各子程序目标文件、预定义的各过程与函数的目标模块链接为可执行程序。(4)运行可执行程序得到结果机器语言构成的可执行程序被由操作系统的“载入程序”调进内存后由CPU执行并得到输出结果。128语言的分类在高级语言长期的发展中,形成了许多各具特点,其分类可概括如下:(1)过程化语言过程化语言适用于过程化程序设计,它是将解决问题所涉及到的数据,与处理数据的操作分别进行设计,并通过控制操作去处理数据。它后期发展为结构化语言及结构化程序设计。FORTRAN语言第一个高级程序设计语言,主要应用于科学与工程计算,至今其思想仍在发挥作用。COBOL语言目标明确地被定向为面向商业的通用语言,主要强调了与数据库的连
76、接与生成各种报表。129PASCAL语言第一个支持结构化程序设计思想的高级语言,主要用于科学与教育界以建立结构化程序设计思想与方法的概念。C语言最初用于系统软件(如UNIX)的开发。由于它简洁而高效、且可类似汇编语言般操作硬件而流行至今。ADA语言为美国国防部软件业务承包同意语言,由于其允许实时控制与很高的并行处理能力而主要用于工业与大型计算机。过程化语言终为结构化语言所取代。130(2)面向对象语言是一种目前流行的,更接近于人类思维的程序设计方法。它与过程化语言的不同,是它把数据及其操作定义为一个整体。C+语言它是一种支持面向对象程序设计的语言,也是C语言的扩展,或说它把C语言作为自己的一个
77、子集。它有面向对象程序设计的如下特性:1)封装性:C+通过定义“类”与“对象”将把数据的属性与操作隐蔽在其中,只用对象者只知道对象实现的功能而难以知道其是如何实现的,对于对象的内部更是难以访问或变动。1312)继承性:可以从已有的对象继承一些属性,再加上本对象特有的属性来定义新的对象,从而使一个通用类能派生出许多特殊类。3)多态性:它使得同一个名字的操作,针对不同的情况具有不同的内涵,从而使一系列相同名称的操作却各具不同的功能。JAVA语言它是在C与C+的基础上发展起来的,由于其小程序(applet)可嵌在HTML中在浏览器上运行,故一般人多是在浏览网页时见其影子。它是完全面向类的,所有数据都
78、必须属于一个类。其特性之一是它提供了丰富的预定义类库,另一特性是允许多线程地执行程序代码。132(3)函数型语言在函数程序设计中,程序可以作为数学函数来考虑。它通过定义一系列可供调用的基本子函数,让设计者组建新的函数。函数程序设计强调模块化编程,鼓励利用已有的函数开发新函数,从而不断地构建出更为庞大的程序。LISP语言是列表程序设计语言,它把要处理的一切都看成是列表(实际是“广义表”)。多用于计算机领域“人工智能”方面的程序设计。SCHEME语言它是通过对LISP语言进行标准化后得到的语言,同样是基于广义表的程序设计语言。133(4)说明性语言这是基于逻辑推理中“一阶谓词演算”而形成的一种查询
79、语言。逻辑推理是依据一些准则,从已知事实推导出新的论断(事实)一种演算。Prolog语言它是逻辑程序设计语言,其程序全部由事实与规则组成。多用于人工智能的“专家系统”。(5)专用语言近年出现的一些不同于上述四类的语言。该类语言可能是一种或多种模型的混合,也可能是具有特殊用途的语言。134HTML语言超文本标记语言,由格式标记与超级链接组成的伪语言格式标记不能单独使用,而需嵌入文本一起使用。网页是HTML文件(或htm),文件被存储于网站服务器端,可由浏览器(如IE)下载到客户端并由浏览器“翻译”为一般文本来显示。PERL语言实用摘要与报表语言,其语法类似于C语言,由于基于“正则表达式”而功能强
80、大高效。因能从字符串到组件中提取信息,故也多用于网页(网站)设计。SQL语言结构查询语言或数据库查询语言,用于与关系型数据库的链接与数据查询。135第十章软件工程软件生命周期开发过程模型模块化质量文档136软件工程软件工程产生的背景是二十世纪六十年代初的“软件危机”,因当时软件生产的复杂性越来越高,而生产率却越来越低。软件危机的主要特征:(1)软件开发周期大大超过规定日期;(2)软件开发成本严重超标;(3)软件质量难于保证。例:Win95有1000万行代码,而Win2000有5000万行代码。开发Win2000的人员中:项目管理约250人,开发人员约1700人,测试人员约3200人等。而也有许
81、多软件开发是失败的。可见软件开发必须是使用工具、技术、过程和范例产生高品质软件的高效生产途径。137软件工程定义:FritzBauer在NATO会议给出的定义:“软件工程是为了经济地获得可靠的和能在实际机器上高效运行的软件而确立和使用的健全的工程原理(方法)。” IEEE【IEE83】给出的软件工程定义:“软件工程是开发、运行、维护和修复软件的系统方法。” IEEE【IEE93】给出了更加综合的定义:“将系统化的、规范的、可度量的方法应用于软件的开发、运行和维护的过程,即将工程化应用于软件中。” 定义:定义:软件工程是应用计算机科学、数学及管理科学等原理开发软件的工程。它借鉴传统工程的原则、方
82、法,以提高质量,降低成本为目的。138软件生命(生存)周期软件生命周期是软件产品或软件系统从设计、投入使用到被淘汰的全过程。根据国标计算机软件开发规范软件生命期可划分为如下阶段:(1)可行性研究与计划(2)需求分析(3)总体设计上游(4)详细设计(5)实现(6)集成测试(7)确认测试下游(8)使用和维护(注注:教材分为四个阶段)139系统分析它是开发软件的开始阶段,其任务是明确软件应该“做什么”。该阶段可分为四个步骤:(1)定义用户:划分软件的使用者,软件可以为一般用户或特殊用户而设计。(2)定义要求:明确用户的要求,从来自用户的描述中提炼出软件的专业要求。(3)定义需求:依据用户的要求,准确
83、定义软件的系统需求(包括安全与精度的需求等)。(4)定义方法:按照语义清晰的需求说明,选择适当而可行的方法去满足系统需求。以上由高级软件开发人员(系统分析员)完全。140系统设计该阶段的任务是定义系统要“怎样做”才得以完成系统分析阶段所定义的系统需求。它将确定系统边界,完成系统文件和数据库等设计:(1)系统设计的描述工具常用“结构图”,用它表示系统的任务分解,按逻辑构造互相独立的系统模块,以及模块之间的互相作用。(2)系统的模块化:是系统设计的原则,它将整个系统划分为若干互相独立的模块,并通过对模块的设计与测试,直到主子模块的链接。141软件实现该阶段的任务是创建实际的程序,其过程一般是先书写
84、算法,再依据算法去编写程序:(1)算法描述工具:在实际编码之前使用某些工具去描述程序逻辑,常用工具一般有“流程图”或“伪代码”。一般由系统分析员或高级程序员完成。(2)编码:实际的编写程序,由程序员选择适当的语言(或项目指定的语言)并依据算法实施程序编码。142软件测试该阶段是生命周期中最漫长的,其任务是通过测试以确保各程序最终能协同工作。测试分为单独的模块测试与整个系统的联合测试。大型项目会把测试工程师设成专门的测试组。(1)白盒测试法:一般由程序员用此法按测试计划去测试自己编码的程序,它注重模块内部的程序逻辑。(2)黑盒测试法:一般由测试工程师按需求说明去测试模块之间的联系或整个系统,它忽
85、视模块内部的程序,注重模块间的接口情况。以上要靠测试人员的经验去设计测试计划。143开发过程模型(1)瀑布模型(线性顺序模型)按照传统,瀑布模型开发软件的特点是:阶段间具有顺序性和依赖性;推迟实现的观点;每个阶段必须完成规定的文档;每个阶段结束前完成文档审查,及早改正错误。(2)增量模型(递增模型)先完成一个系统子集的开发,再按同样的开发步骤增加功能(系统子集),如此递增下去直至满足全部系统需求。系统的总体设计在初始子集设计阶段就应作出设想。两种模型分别见后图所示1441. 瀑布模型 ( (线形顺序模型线形顺序模型) )可行性研究与计划可行性研究与计划需求分析需求分析设计设计编码编码运行维护运
86、行维护测试测试定义定义阶段阶段开开发发阶阶段段维护阶段维护阶段145分析分析 增量模型设计设计 编码编码测试测试 分析分析 设计设计 编码编码测试测试 分析分析 设计设计 编码编码测试测试 分析分析 设计设计 编码编码测试测试 增量增量增量增量1 11 1增量增量增量增量2 22 2增量增量增量增量3 33 3增量增量增量增量n nn n 增量增量增量增量1 11 1交付客户交付客户交付客户交付客户 增量增量增量增量2 22 2交付客户交付客户交付客户交付客户 增量增量增量增量3 33 3交付客户交付客户交付客户交付客户 增量增量增量增量n nn n交付客户交付客户交付客户交付客户日历时间日历
87、时间日历时间日历时间.146模块化模块化是一个好的软件设计的一个基本准则。模块化把大型问题分解为若干相对简单的小问题,从而减低原问题的复杂度,进而减少软件开发成本。模块化将大项目自顶向下逐步分解为能互相交换信息的小模块。设计阶段进行模块化工作的主要工具,对于过程化设计是结构图,它用以表示过程与函数之间的关系;对于面向对象是类图,用以表示类之间的关系。模块化要求模块信息隐蔽,即模块所包含的信息,不允许其它不需要该信息的模块访问,独立的模块之间仅仅交换为完成系统功能而必须交换的信息。因此模块独立性就很重要。147模块独立性的度量 在模块独立性的概念中,模块独立的含义: 模块完成独立的功能 符合信息
88、隐蔽和信息局部化原则 模块间关连和依赖程度尽量小模块独立性的度量:模块独立性取决于模块的内部和外部特征。那么定性的度量标准,是模块之间的耦合性,与模块自身的内聚性。 耦合:模块间相对独立性(相互依赖程度)的度量,耦合性越高,模块独立性越弱。 内聚:一个模块内部元素(过程)在功能上相互关联的强度。设计追求的是高内聚,既模块内尽量完成单一的任务(或功能)。148耦合模块之间耦合的类型: 低 强 无直接耦合(无信息交换)耦 独 (低耦合) 数据耦合(参数交换信息)合 立 特征耦合(参数是数组等) (中耦合) 控制耦合(交换标记信息)性 性 (较强耦合)全局耦合(全局量通讯) (强耦合) 内容耦合(访
89、问另一模块) 高 弱149内聚模块的内聚性类型: 低 弱(功能分散) 巧合内聚 0分(模块内部各个部分无联系) 逻辑内聚 1分(模块内组合各相关的内容)内 独 瞬时内聚 3分(模块功能在同一时间完成)聚 立 过程内聚 5分(模块内使各处理成份相关)性 性 通信内聚 7分(模块各部分同输入/输出) 顺序内聚 9分(模块内多功能按流程执行) 功能内聚10分(模块内集中完成一个功能) 高 强(功能单一)注意:注意:耦合与内聚密切相关又互相矛盾,但耦合是直接的主导因素,而内聚辅助耦合共同衡量独立性。150质量 优良软件的质量: 能够满足用户显示或隐式的需求,文档齐全,符合组织的操作标准,在其开发使用的
90、硬件上高效运行。 软件的质量因素可以由一下三个方面来度量: (1)可操作性:包括准确性、效率、可靠性、安全 性、及时与适用性。 (2)可维护性:包括可修改性、灵活性与可测试性。 (3)可迁移性:包括代码可重用性、互操作性与可 移植性。 质量周期:保障质量的自始至终贯穿于整个软件生命周期,它包括软件开发中的优质工具、技术评审、正规测试、改变控制、标准、度量与报告。151文档软件的正确使用与有效维护离不开文档,在软件开发过程中逐步形成了用户文档与系统文档。(1)用户文档:该文档一般称为用户手册,通常都包括指导用户熟悉软件功能的教程。(2)系统文档:为软件开发人员之外的人员,维护与修改软件而写。软件
91、生命周期各阶段,都应注意撰写相应的系统文档,使之文档化:分析阶段记录所搜集的信息;设计阶段详细注释设计工具;实现阶段书写各程序功能注释与代码段注释测试阶段记录测试计划及其测试结果。文档化工作要始于软件开发之初而终于软件报废。152第四部分数据组织153第十一章数据结构数组记录链表154数据结构定义数据结构的描述性定义:数据结构是具有一种或多种特定关系的数据集合。这里的“结构”二字可以先简单等同于“关系”二字,即数据的“结构”是指数据之间的某种特定“关系”,而数据结构是指具有该关系的数据的集合。程序设计语言中常使用强调个体的简单变量,而数据结构强调使用相关变量的集合。集合中的变量(或数据)可以被
92、单独使用也可以被整体使用。155数组数组是具有固定大小的存储空间,并由相同数据类型的元素(或叫数据或叫变量)所组成的顺序集合。数组作为一种数据结构具有以下特性:(1)预定义的固定大小空间。数组在程序中被说明后,编译阶段即为数组分配了该空间,程序执行中该数组的空间大小将不能被改变。(2)数组要求其元素必须是相同类型的。因此数组中每个元素都占有相同的存储空间,从而可预知并固定整个数组的存储空间。(3)任何时候系统都为数组分配一片地址连续的存储空间,数组元素也相应地被逐个顺序地存储于该空间之中。(4)该空间的每个元素都可作为个体被单独地去访问,而整个数组也可以被整体地去访问。156数组的操作数组除被
93、整体命名外,其各个元素也有规律性的名称。该数组元素名称与数组所在的连续空间之间有一一对应的关系。数组元素可按名 访问,数组元素被单独引用时与简单变量没有区别。一般对一组相关的数据可考虑使用数组存储,并利用数组元素名称的规律性,使用循环控制数组的各个元素。二维数组与一维数组没有本质上的区别,其数组元素同样具有规律性的名称,但其规律除与与其存储空间的连续性一致外,还与数组所存数据的二维性(由行列所构成的表)相对应。许多时候,需要利用多重嵌套的循环结构去控制对二维数组中各个元素的操作。二维数组的数组元素按行或按列存储于连续存储空间。157记录记录是具有固定大小的存储空间,并可由不同数据类型的相关元素
94、(或叫数据或叫变量)所组成的集合。记录作为数据结构具有以下特性:(1)记录必须由被称为域(或字段、数据项)的相关元素所组成。记录作为整体有名字,可以按名访问记录,记录各个域也有域名,并可按名对域进行存取,域是存取与构成记录的最小单位。(2)记录要求其元素可以是不同类型的。因此数组中每个域所占有的存储空间可能不同,而当组成记录的各域类型确定后该记录的存储空间也随之确定(可分为定长记录与不定长记录),因此记录的存储空间一般是可被预定义的。(3)记录被分配的存储空间不一定是连续的。158记录的访问记录与数组一样,其整体的数据是由构成其整体的各个元素的数据来体现的;同样,对记录或数组的访问也多是通过访
95、问其各个元素来实现的;特别是只有当至少一个元素的数据有所变化,原来的记录或数组才被改变。所以访问记录的关键是对各个记录元素的访问。一般的方法是,用分隔符(如符号“.”)标注某个元素是属于哪个记录的,并象简单变量一样地去访问一个记录的某个记录元素。这与对数组的第几个数组元素进行访问是一样的。如:数组元素A2,5与记录元素StuRrc.Name159链表链表不同于数组与记录的主要一点,是链表可以被动态生成,即链表在运行阶段可根据所需存储空间的大小而逐渐申请存储空间,以满足表中数据的存放。这就不必象数组或记录的预定义存储空间那样,在运行期间必须始终保持着存储空间的大小不变。链表是有序数据的集合。注意
96、:该有序是指数据的前后顺序,而不是数据大小的有序。链表是由被称为节点(结点)的链表元素所构成,链表的数据被分别存储于各个节点之中的。由于链表数据的有序性,所以存储表中数据的各个节点在链表中也必须保持其有序性。160链表的结构链表的存储结构是由节点所构成的。链表的各节点不一定占有连续的存储空间,但各节点的存储空间之间必须有一定的联系,以反应这些节点都是某一个链表的。因此节点的结构为:节点存储的数据下一节点的地址节点本身相当于一个记录,该记录至少有两个域,一个“数据域”用于存储链表在该节点的数据,另一个“链域”用于存储“指针”(即“地址”数据),以指明处于链表中的该节点之下一节点的位置,并保持链表
97、数据的有序性。因此一个链表的结构如下:头指针数据1数据2数据n空其中,头指针用于链表在空间中的定位,空是结束。161链表的操作指针是种存储“地址”的量,链表中除必须有头指针外,一般还会定义辅助指针以便于对链表中数据的操作(运算)。其操作一般有:(1)插入节点,申请一个与链表节点结构一致的节点,将其插入在链表中适当的位置上。(2)删除节点,在链表适当的位置处删除一个节点,并将其所占空间释放回系统空间。(3)链表定位,根据给定的某个说明位置的值,在链表中定位(找到)该位置上的节点。(4)检索节点,根据某个给定的值,在链表中查找是否存在与该值相等的数据,并返回查找成功或失败的信息。(5)遍历链表,访
98、问链表中的每个节点一次。162第十二章抽象数据类型背景线性列表栈队列树二叉数图163抽象数据类型的概念简单地讲,一般的“数据类型”是个数据集合,它说明了集合中数据的表示方式与范围,并只考虑数据本身,而“抽象数据类型”(ADT)则是数据与相关操作的封装体。ADT是OOP的重要概念,类与对象可实现数据与操作的封装,ADT也与数据结构密切相关,本章内容在数据结构课程中都有讨论。ADT的内部是数据的说明与施加在数据上的操作(函数)描述,对外是一个供ADT使用者的接口。ADT以信息隐蔽为目标,把数据与操作封装在其内部,并完成了数据结构的实现,而把其功能通过接口提供给使用者。使用者只了解ADT实现了什么功
99、能,而不知道ADT内部是怎么实现该功能的。164线性列表线性表是一种基本的数据结构,它是有序数据的集合(如链表定义)。集合中数据之间的关系是线性的,其线性关系表现在表中的每个数据(除第一个与最后一个外)都有唯一的直接前驱和唯一的直接后继,它反应了线性表中数据之间的前后顺序。线性表的存储结构往往采用数组或线性链表。一般的线性表(广义列表)对于施加在表中数据的插入、删除、排序等操作均无任何限制,而运算受到限定的线性表(限制列表),要求对表中数据的插入与删除操作,仅限制在表的头尾位置。将施加于一般线性表的插入、删除、检索与遍历等操作实现后,与表数据一起封装就实现了ADT。165栈与队列栈是插入与删除
100、操作仅被限制在表的一端(经常是被成为栈顶的表尾端)进行的线性表。因此,栈具有数据元素在表中“后进先出”的特性,所以栈也称为后进先出(LIFO)列表。枪用子弹夹与火车调度栈等都是栈的例子。栈的操作只有入栈、出栈与判断栈为空否等。队列是插入操作被限定在表的一端(表尾)而删除操作被限定在表的另一端(表头)的线性表。因为,队列具有数据元素在表中“先进先出”的特性,所以队列也称为先进先出(FIFO)列表。人的排队与计算机I/O队列等都是队列的例子。队列的操作只有入栈、出栈与判断队为空否等。栈与队列往往是通过数组与线性链表来实现的。166树树是一组有限元素(又称节点)的集合,及连接各节点的一组线段(又称分
101、支)。与节点相连接的线段0层称为该节点的度,指向节1层子树点的分支为入度分支,离开节点的为出度分支。入2层度与出度之和称节点的度。树的层数为树的深度若树非空则树至少有一个入度为0的节点,称为根;出度为0的节点为叶子;非根非叶的节点为内部节点。树中节点最大的度为该数的度。路径是连接相邻节点的序列。根到每个节点都存在唯一的路径,在该路径上,相邻节点的前驱为双亲节点,后继为孩子节点,同双亲的为兄弟节点。167二叉树二叉树是度不大于2的树。其任意节点都不多于2个子树,这两个子树分别称为左子树与右子树。二叉树有序树,其左右子树顺序不可颠倒。若二叉树的节点个数为n,则其深为log2n+1。若二叉树的深为h
102、,则其最多有2h-1个节点。平衡二叉树(1)二叉树中节点的左右子树深度之差为该及点的平衡因子(2)若二叉树中各节点的平衡因子的绝对值不大于1则其为平衡二叉树。二叉树的遍历(1)深度优先遍历:含前序遍历(NLR)、中序遍历(LNR)与后序遍历(LRN)(2)广度优先遍历:按层且各层按从左到右遍历。二叉树一般以二叉链表为存储,如表达式树。168图图是顶点与线段两个有限集合。线段用于连接两个顶点,在有向图中的线段称为“弧”,而在无向图中的线段称为“边”。有向图无向图邻接点是被线段所ABEF直接相连的一对顶点。路径是一个邻接点CDG的序列,当序列中首尾两顶点重和时称为环路。若两顶点之间存在路径则称其为
103、连通的,若图中各顶点之间都存在路径则称该图为连通的。若有向图是连通图的则称其为强连通的。存储图的顶点与边一般用邻接数组与邻接表。图的操作:顶点的添加、删除与查找;边的添加与删除;图的遍历(深度优先搜索与广度优先搜索)。图的应用:如网络与构造最小生成树。169第十三章文件结构存取方式顺序文件索引文件哈希文件文本与二进制170第十四章数据库数据库管理系统体系结构数据库模型关系模型关系的操作结构化查询语言其它数据库模型171数据库管理系统(DBMS) DBMS(DataBase Manage System)是定义、创建、维护(或管理)数据库的一种环境或工具。它允许用户控制数据库中数据的存取。 DBM
104、S由五个部分组成: (1)硬件:允许存取数据的物理部件。如计算机系统或部件,特别是计算机系统的理存储设备。 (2)软件:允许用户存取、维护与更新物理数据的程序,包括用户存取数据库中数据的权限。 (3)数据:在数据库中,数据存储于物理存储设备,并独立于软件而存在。数据与软件分离的好处,是无论管理数据的软件如何改变,都不会影响处于同一个DBMS中的物理数据及其存储方式。 172 (4)用户:最终用户与应用程序。 它们都使用数据库而各自使用的目的不同。最终用户直接从数据库中获取数据,它分为数据库管理员(DBA)与普通用户。而应用程序使用数据库是为了存取与处理数据,如数据库应用系统。 (5)规程:明确
105、定义并为数据库用户所遵循的规则。数据库的体系结构 由美国国家标准协会制定的三层体系结构: (1)内层:决定数据库中数据在存储设备上的物理位置、存取方式与存储设备之间的数据传输。 (2)概念层:定义数据库模型、数据的逻辑图表与数据库功能。它是实现数据与软件分离的中介层。 (3)外层:数据库与用户的交互层。 173数据库模型数据库模型定义数据库的逻辑设计,描述数据之间的关系。在数据库设计中曾有过三种模型:(1)层次模型:数据库中的数据被组织为树形结构,对其数据访问的路径按树的节点分枝进行。(2)网状模型:数据库中的数据按图来组织,对其数据访问的路径可有多条,一般多于层次模型。(3)关系模型:数据库
106、中的数据被组织为一系列的二维关系表(一般每个表SHI一个数据库.DBF文件),对其数据的访问是源自表与关系的关联。关系数据库模型目前数据库设计最流行的模型。现常见的各种DBMS几乎都是关系型数据库。174关系模型 关系数据库管理系统(RDBMS)的模型,是基于离散数学中有关“关系”的概念的。 关系表现为一个二维表,所以关系数据库中数据的外在表示就是关系或表的集合,而且 RDBMS中的关系或表具有如下特征: (1)名称:数据库中每个关系具有唯一的名称。 (2)属性:关系(表)的每一列称为属性,列头是属性名(并不实际存储)而列值是该属性的值。关系中属性的总数成为关系的度。 (3)元组:关系中的行称
107、为元组,它定义一组属性值,关系的元组总数称为关系的基数。 以上是关系数据库中数据的逻辑组织。 175关系操作在关系数据库中可定义操作并通过已知关系来创建新的关系: (1)插入:一元操作 (2)删除:一元操作 (3)更新:一元操作 (4)选择:产生一个新关系,是原关系元组的子集。 (5)投影:产生一个新关系,是原关系属性的子集 (6)连接:基于共有属性而把两关系组合为新关系 (7)并:由两关系的相同属性组合为一个新关系。 (8)交:由两关系的相同属性组合为一个新关系。 (9)差:由两关系的相同属性组合为一个新关系。176结构化查询语言SQL SQL是ANSI与ISO用于关系数据库的标准化语言。它是无需编程只需说明的描述性语言。对应于操作: (1)插入 (2)删除 (3)更新 (4)选择 (5)投影 (6)连接 (7)并 (8)交 (9)差177其它数据库模型分布式数据库与面向对象数据库178复习要求掌握教材的第一、二、三部分的共十五章,其中第九章9.5节的结构化语言C不要求。各章节的内容,由于教学计划的时间有限而并没有都讲授到,但都要求,所以需认真自学。各章节需要掌握基本概念、基本思想与基本方法。考试的形式分数分布:闭卷考试。四选一的选择题30分;填空题30分;简答题30分(约五六小题需简单而准确地答),10分的综合题(考虑以写算法为主)。总评中平时分占百分之三十。179