导图社区 计算机二级-基础知识
- 64
- 3
- 0
- 举报
计算机二级-基础知识
来源于对官方书籍内容的整理，汇总了计算机系统、数据结构与算法、程序设计基础、软件工程基础、数据库设计基础的知识，快来看看吧！
编辑于2023-04-07 16:19:12
- 相似推荐
- 大纲
计算机二级 基础知识
1、计算机系统
1.1 概述
1.1.1 计算机的发展历程
第一台电子数字计算机
ENIAC
1946年，美国宾夕法尼亚大学
18000个电子管、1500个继电器、30吨、170m2、140KW、每秒5000次加法
发展四阶段
1946-20世纪50年代后期，电子管
20世纪50年代后期-20世纪60年代中期，晶体管
20世纪60年代中期-20世纪70年代初期，集成电路
20世纪70年代初期-至今，大规模集成电路
1.1.2 计算机体系结构
第一台存储程序的计算机
EDSAC
“存储程序”思想
冯诺依曼，1946年6月
①计算机（指硬件）由运算器、控制器、存储器、输入设备、输出设备组成
②计算机内部采用二进制来表示指令和数据
③需将编好的程序和原始数据事先存入存储器中，然后再启动计算机工作
非冯诺依曼结构计算机
数据驱动的数据流计算机
需求驱动的归约计算机
模式匹配驱动的智能计算机
1.1.3 计算机系统基本组成
一个完整的计算机系统应包含硬件系统和软件系统
硬件系统
硬件系统也被称为裸机，只能识别由0和1组成的机器代码
软件系统
是为运行、管理和维护计算机而编制的各种程序、数据和文档的总称
按面向应用对象的不同分类
系统软件
指控制和协调计算机及外部设备，支持应用软件开发和运行的软件
主要功能
调度、监控和维护计算机系统，合理分配系统资源，管理计算机系统中各独立硬件，使它们协调地工作，确保计算机正常高效地运行
包括操作系统（最主要）、语言处理系统、数据库管理系统和系统辅助处理程序
应用软件
硬件
指组成一台计算机的各种物理装置，它们是由借助电、磁、光、机械等原理构成的各种物理部件组成
是计算机工作的物质基础
软件
指在硬件设备上运行的各种程序、数据以及有关的资料
程序是指令集合
文档是对程序做的必要的说明以及整理出的有关资料
组成总结框图
计算机系统
硬件
主机
中央处理器
运算器
控制器
内存储器（主存储器）
外设
外存储器
输入设备
输出设备
软件
系统软件
操作系统
服务软件
编译与解释系统
应用软件
信息管理软件
辅助设计软件
文字处理软件
图形软件
各种程序包
1.2 计算机硬件系统
原始的冯诺依曼计算机结构上以运算器为中心，如今已以存储器为中心
各硬件系统通过总线连在一起
硬件系统简介
中央处理器
运算器
对数据进行算术运算和逻辑运算（即对数据进行加工处理）
控制器
对程序所规定的指令进行分析，控制并协调输入、输出操作或对内存的访问
存储器
负责存储程序和数据，并根据控制命令提供这些程序和数据。分为内存和外存
输入设备
负责把用户的信息（包括程序和数据）输入到计算机中
输出设备
负责将计算机中的信息（包括程序和数据）传送到外部媒介供用户查看或保存
1.2.1 中央处理器（CPU）
是计算机系统的核心
执行软件（程序）指令将数据加工成信息
通常包括控制器和算术逻辑单元（运算器），它们都包含有寄存器或高速存储区域，并通过总线连接起来。通常二者被合成在一块集成电路的芯片（CPU芯片）上
控制器（CU）
是计算机的控制中心和指挥中心
控制器解释存储在CPU中的指令，然后执行指令
对于每个指令，控制单元要执行四个基本操作
1、获取指令
2、分析指令
3、执行指令
4、存储结果
运算器（ALU）
可以执行算术运算和逻辑运算，并能控制这些操作的速度
算术运算——加减乘除
逻辑运算——比较
寄存器
是高速存储区域，可以在处理过程中临时存储数据
所有数据在处理前都存在寄存器中
CPU中寄存器的数量和每个寄存器的大小（多少位）可以确定CPU的性能和速度 如32位的CPU是指CPU中的寄存器是32位的
种类
指令寄存器
地址寄存器
存储寄存器
累加寄存器
总线
是在CPU内部以及在CPU和主板的其他部件之间传输信息的电子数据线路。 总线像是多车道的高速公路，通道越多，位的传输越快
CPU品质的高低直接决定计算机系统的性能
反映CPU品质的最重要的指标是主频和字长
主频
CPU工作节拍受主时钟控制，主时钟不断产生固定频率的时钟， 主时钟的频率即（CPU）的主频
主频说明了CPU的工作速度，主频越高，CPU的运算速度就越快
字长
字长指CPU可以同时处理的二进制数据的位数
在执行指令过程中，CPU除访问内存之外，还可以通过总线访问各种输入输出设备
1.2.2 计算机的基本工作原理
1 计算机指令格式
计算机指令是能够被计算机识别并执行的二进制代码， 它规定了计算机能完成的某种操作
计算机指令通常由两部分组成
操作码
操作码指出该指令需要完成操作的类型或性质
操作码也是二进制代码
操作码的二进制位数决定了该种计算机最多能具有的指令条数（即操作种类）
若某指令操作码所占位数为k，则该种计算机最多可有2的k次条指令
为了使计算机有n条指令，则该计算机指令中的操作码 至少应有[log2(n-1)]+1个二进制位
[ ]指取整
操作数（地址码）
地址码用来描述该指令的操作对象 要么直接给出操作数，要么指出操作数的存储器地址或寄存器地址（即寄存器名）
根据指令中操作数的性质分类
源操作数
目的操作数
若指令中的操作码和操作数（地址码）共占n个字节，则称该指令为n字节指令
2 计算机指令的寻址方式
指令中操作数的真实地址称为有效地址，它由寻址方式和形式地址共同决定
寻址方式
指确定本条指令的数据地址以及下一条将要执行的指令的地址， 与硬件结构密切相关
分为指令寻址和数据寻址
指令寻址
分为顺序寻址和跳跃寻址
数据寻址
立即寻址
所需的操作数由指令的地址码部分直接给出
直接寻址
指令的地址码部分给出操作数在存储器中的地址
隐含寻址
操作数的地址隐含在操作码或者某个寄存器中
间接寻址
寄存器寻址
寄存器间接寻址
堆栈寻址
3 计算机指令系统
某种计算机的所有指令的集合称为该计算机的指令系统
指令系统一般具有的指令
数据传送指令
将数据在内存之间，或在CPU的各寄存器之间，或在CPU的寄存器与内存之间进行传送
数据处理指令
对数据进行处理，主要包括算术运算、逻辑运算与关系运算
程序控制指令
控制程序中指令的执行顺序
输入/输出指令
实现外部设备与主机之间的数据传输
其他指令
4 计算机执行指令的基本过程
计算机的工作就是自动快速地执行程序
程序是解决实际问题的计算机指令的集合
计算机中，用程序计数器（PC）来决定程序中各条指令的执行顺序
在计算机开始执行程序时，程序计数器的值为该被执行程序的第一条指令所在的 内存单元地址，此后按如下步骤依次执行程序中的各指令
取指令
分析指令
执行指令
修改程序计数器
一般把计算机完成一条指令所花费的时间称为一个指令周期。 指令周期越短，指令执行就越快
5 指令执行的时序
考虑到所有的器件（寄存器、存储器）中存储器的速度最慢，CPU访问一次内存所花的时间较长。 故通常用内存中读取一个指令字的最短时间来规定CPU周期，即也称机器周期。 一般最长的操作是访问存储器（读/写），这个时间也用于访问外设接口（寄存器） 将每条指令占用的时间称为指令周期
由于指令执行时取指令必须访问存储器，所以占用一个机器周期
分析指令所占用时间极短，无需分配一个完整的机器周期，一般在取指周期后期完成
执行指令和指令的操作数有关，故可能是一个到多个机器周期
每条指令的执行大致过程
取指周期
执行周期1
执行周期2
执行周期3
执行周期4
1.2.3 存储器
在现代以存储器为中心的计算机系统中， 存储器的特性已成为影响整个系统最大吞吐量的决定性因素
分类
按存储介质
半导体存储器
磁表面存储器
磁芯存储器
光盘存储器
按存取方式
随机存储器（RAM）
静态存储单元（SRAM）
每个存储位由4~6个晶体管组成
保存信息较稳定
优点
结构简单、可靠性高、速度较快
缺点
所用元件较多
占硅片面积大，功耗大，故集成度不高
动态存储单元（DRAM）
分三管式和单管式
共同特点是靠电容存储电荷的原理来寄存信息
为保证不丢失信息，须在2ms内对存储单元进行一次恢复操作， 这个过程称为再生或刷新
集成度更高、功耗更低，被广泛使用
只读存储器（ROM）
串行访问存储器
按计算机中的作用
主存
辅存
缓存
程序的局部性规律
时间局部性
指如果一个存储项被访问，则该项可能很快被再次访问
空间局部性
如果一个存储项被访问，则该项及其邻近的项也可能很快被访问
一般用速度高的SRAM元件组成，速度与CPU相当，但较贵
一般由块表和快速存储器组成
缓存管理要解决好两个问题，即内存内容的定位和缓存内容的替换
闪存
从EEPROM基础上发展来
兼有EPROM的价格便宜、集成密度高和EEPROM的电可擦除和可重写特性，且速度比EEPROM快
与磁盘相比，闪存具有抗震、节能、体积小、容量大和价格便宜等特点
闪存读写操作一般以块为单位
存储器的层次化结构
存储器有3个重要指标
速度
容量
每位（bit）价格
分类图
存储器
主存
随机存储器
静态RAM
动态RAM
只读存储器
MROM
PROM
EPROM
EEPROM
闪速存储器
辅存
磁盘
磁带
光盘
……
缓存（Cache）
最重要的是主存储器
主存储器一般采用半导体存储器， 与辅存相比容量小、读写速度快、价格高
1.2.4 数据的内部表示
1、进位计数制及其相互转换
基数
指进位计数制中所拥有数字的个数
权
是每位上数字的值
某一位上所表示的数等于该位上的数字乘以该位的权，整个数字的值就是各位上表示数的和
2、定点数的表示和运算
无符号数的表示
无符号数是指非负整数，机器字长的全部位数均用来表示数值的大小，相当于数的绝对值
带符号数的表示
带符号数是指在计算机中将数的符号数码化。
一般规定二进制最高位为符号位，“0”表示正，“1”表示负 这种在机器中将符号位也数码化的数称为机器数
原码
在数的原码表示中，机器数的最高位为符号位，其后的数值以绝对值形式给出
反码
正数的反码与原码相同，负数的反码是对该数的原码除符号位外各位取反
补码
正数的补码与原码相同，负数的补码是在该数的反码的最后一位加上1
计算机中带符号数的加减运算都可以用加法来实现， 且两数的补码之“和”等于两数“和”的补码
（偏移码）
补码的符号位取反即是偏移码
3、浮点数的表示和运算
浮点数的表示范围
浮点数是指小数点位置可浮动的数据，通常以右式表示
N为浮点数 M为其尾数 E为其阶码 R为“阶的基数（底）”，且R为常数，一般为2、4、8，一台计算机中R相同
浮点数的机内表示
Ms | E | M 1位 n+1位 m位
Ms是尾数的符号位，为0是表示数为正，为1时表示数为负 E是阶码，一般是整数，最高位是符号位 M为尾数，由Ms和M组成一个定点小数
为保证数据精度，浮点数通常用规格化形式表示
当R=2，且尾数值不为0时，其绝对值大于或等于0.5（十进制）
对非规格化浮点数，可通过左/右移尾数，并修改阶码值使复合规格化要求
IEEE 754 标准
常用浮点数格式
①单精度浮点数（32位）
阶码8位，尾数24位（内含1位符号位）
②双精度浮点数（64位）
阶码11位，尾数53位（内含1位符号位）
尾数M只是表示小数点之后的二进制位数，标准规定小数点左边还有一个隐含位， 规格化数和非规格化数的隐含位分别是1和0
规格化数的阶码二进制位不全部为0或全部为1（全部为1时为特殊数值，如正负无穷大等）
1.2.5 总线和外设
1、总线
（1）总线的基本概念
总线是连接计算机中各个部件的信息传输线，是各个部件共享的传输介质
总线上信息的传输方式分为串行传输和并行传输， 计算机中CPU通过总线与内存、外设等连接。
总线依据功能和实现方式的不同可分为片内总线、系统总线和通信总线等
片内总线
芯片内部的总线
系统总线
计算机各部件之间的信息传输线，包括数据总线、地址总线和控制总线
数据总线为双向总线，宽度与机器字长、存储字长有关
地址总线为单相总线，与存储地址、I/O地址有关
控制总线为部分出、部分入方式，控制器通过该总线控制所有部件
通信总线
用于计算机系统之间或计算机系统与其他系统之间的通信，依据总线的不同传输方式 又分为串行通信总线和并行通信总线
（2）总线的组成及性能指标
总线的结构通常分为单总线结构和多总线结构
单总线结构是将CPU、主存、I/O设备都挂在一组总线上
多总线结构是将速度较低的I/O设备从单总线上分离出来，形成主总线与I/O设备总线分开的结构
总线的性能指标包括
总线宽度（数据总线的根数）
总线带宽（数据传输率）
时钟同步/异步（总线上的数据与时钟同步的称为同步总线，异步同理）
（3）总线仲裁
由于总线上连接着多个部件，因此需要总线控制器统一管理
总线控制器的工作主要包括总线的判优控制（仲裁逻辑）和通信控制
总线仲裁逻辑可分为集中式和分布式 前者将控制逻辑集中在一处 后者将控制逻辑分散在总线的各个部件之上
（4）总线操作
读和写
读是将从设备中的数据读出并经总线传输到主设备
写是由主设备到从设备的数据传输过程
块传送
主设备给出要传输的数据块的起始地址后，就可以利用总线对固定长度的数据一个接一个地读出或写入
写后读或读后写
读后写往往用于校验数据的正确性
写后读往往用于多道程序的对共享存储资源的保护
广播和广集
广播
主设备同时向多个从设备传输数据的操作模式
广集
将多个从设备的数据在总线上完成AND或OR操作
通常用于检测多个中断源
（5）总线标准
总线标准就是系统与各模块、模块与模块之间的一个互连的标准界面
系统总线
ISA
EISA
VESA
PCI
PCI局部总线是高性能的32位或64位总线，它是专门为高集成度的外围部件、扩充插板和处理器/存储器系统而设计的互连机制
AGP
是一种视频接口的技术标准，专用于连接主存和图形存储器
总线宽32位，时钟频率66MHZ，能以133MHZ工作， 最高的传输速率可达533Mbps
设备总线
IDE
早期大部分PC的硬盘和相当数量的CD-ROM驱动器都是通过这种接口和主机连接的
SCSI
现已成为各种计算机的系统接口
RS-232
是一种串行通信总线标准
USB
基于通用的连接技术，可实现外设的简单快速连接
2、输入/输出系统
（1）外部设备的分类
围绕主机设置的各种硬件装置称为外部设备或外围设备， 它们主要用来完成数据的输入、输出、成批存储以及对信息加工处理的任务
输入/输出设备
向计算机输入信息的外部设备称为输入设备
接受计算机输出信息的外部设备称为输出设备
辅助存储器
指主机以外的存储装置，又称为后援存储器或外存
终端设备
由输入设备/输出设备和终端控制器组成，一般通过通信线路和主机相连
可进一步分为通用终端设备和专用终端设备
过程控制设备
脱机设备
（2）硬盘存储器
硬盘是最重要的大容量外存设备
可分为固定磁头磁盘存储器和移动磁头磁盘存储器
固定头磁盘存储器又称每道一头型磁盘存储器，无需头臂定位机构
移动磁头的磁盘存储器在存取数据时，磁头在磁盘上做径向运动
磁头和磁臂是驱动器的重要组成部分，磁头安装在磁臂上，负责读写各磁道的数据
一个具有n个盘片的磁盘组，可将n个面上的同一半径的磁道看成一个圆柱面。 这些磁道存储的信息称为柱面信息
主要性能指标
存储密度
道密度
沿磁盘半径方向单位长度上的磁道数，单位是道/英寸
位密度
磁道单位长度上能记录的二进制代码位数，单位是位/英寸
存储容量
一个磁盘存储器所能存储的字节总数
存取时间
从发出读写命令后，磁头从某一起始位置移动至新的记录位置，到完成从盘片表面读出或写入信息所需要的时间
进一步划分为3个部分
将磁头定位至所要求的磁道上所需的时间（定位时间或寻道时间）
寻道完成后至磁道上需要访问的信息到达磁头下的时间（等待时间）
读写相应块的时间
实际中使用存取时间的平均值来表示
数据传输率
磁盘存储器在单位时间内向主机传送数据的字节数
（3）I/O接口
基本功能
实现设备的选择
实现数据缓冲以达到速度匹配
实现数据串并格式转换
实现电平转换
传送控制命令
反应设备的状态
（4）I/O方式
程序查询方式
程序主动查询输入/输出设备是否准备好 会使CPU大部分时间处于等待状态，系统效率低
程序中断方式
中断
计算机在执行程序的过程中，当出现异常情况或者特殊情况时，CPU停止当前程序的运行，转而执行对这些异常情况或者特殊情况进行处理的程序（中断服务处理程序）处理结束之后再返回到现行程序的断点处继续运行
中断判优
CPU对多个中断源的请求依据优先级进行排队的过程
多重中断/中断嵌套
在处理某一个中断的过程中又发生了新的中断请求，从而中断当前服务程序的执行，又转去进行新的中断处理
中断屏蔽
产生中断请求后，用程序方式有选择的封锁部分中断， 而允许其余部分中断仍得到响应
DMA方式
直接内存存取（DMA）是I/O设备与主存储器之间由硬件组成的直接数据通路， 用于高速I/O设备与主存之间的成组数据传送
通道方式
通道是一个独立于CPU的专门管理I/O的处理器， 它控制设备与内存直接进行数据交换
与DMA相比，通道方式进一步减轻了CPU的工作负担， 增加了计算机系统的并行工作程度
1.3 操作系统
计算机系统中所有的硬件和软件统称为计算机资源
1.3.1 操作系统概述
操作系统是最基本的和最核心的系统软件，是直接与硬件层相邻的第一层软件 它对硬件进行首次扩充，是其他软件运行的基础
1、操作系统的功能与任务
主要作用
①管理系统资源
②为用户提供资源共享的条件和环境，并对资源的使用进行合理调度
③提供输入/输出的方便环境，简化用户的输入/输出工作，提供良好的用户界面
④规定用户的接口，发现、处理或报告计算机操作过程中所发生的各种错误
操作系统是用以控制和管理系统资源、方便用户使用计算机的程序的集合
功能和任务
①处理机管理
处理机（CPU）是整个计算机硬件的核心
充分发挥处理机的作用，提高它的使用效率
②存储器管理
对有限的内存储器进行合理的分配，以满足多个用户程序运行的需要
③设备管理
有效地管理各种外部设备，使这些设备充分发挥效率； 并还有给用户提供简单而易于使用的接口
④文件管理
实现唯一地标识计算机系统中的每一组信息； 有条理地组织这些信息
⑤用户接口
2、操作系统的发展过程
（1）手工操作（无操作系统）
特点：用户独占机器，CPU等待手动操作，CPU利用不充分
（2）批处理系统
（3）多道程序系统
（4）分时系统
（5）个人计算机操作系统
3、操作系统的分类
按计算机硬件规模
大型机操作系统
小型机操作系统
微型机操作系统
按使用环境和访问方式
①多道批处理操作系统
“多道”指在计算机内存中存入多个用户作业
“批处理”指在外存中存入大量的后备作业，作业的运行完全由系统控制， 用户与其作业之间没有交互作用，用户不能能直接控制其作业的运行 通常称这种方式为批处理或脱机操作
②分时操作系统
允许多个联机用户同时使用一台计算机系统进行计算的操作系统
特点
多路性（同时性）
终端用户感觉上好像独占计算机
交互性
独立性
终端用户彼此独立，互不干扰
及时性
快速得到响应
③实时操作系统
是指当外界事件或数据产生时，系统能够接受并以足够快的速度予以处理和响应，能够控制所有任务同时进行
三种实时系统
过程控制系统
工业生产自动控制等
信息查询系统
图书资料查询系统等
事务处理系统
飞机订票系统等
一般分为硬实时操作系统和软实时操作系统
硬实时操作系统必须使任务在确定的时间内完成
软实时操作系统能让绝大多数任务在确定时间内完成
一般采用基于优先级的抢占调度方式
④网络操作系统
为了使计算机能方便的传送信息和共享网络资源，将计算机加入网络中
功能
网络通信
资源管理
网络管理
网络服务
通信透明性
⑤分布式操作系统
分布式计算机系统
指由多台分散的计算机经网络互连而成的系统
一个结点出错不影响其他结点运行
主要优点：健壮性强、扩充容易、可靠性高、维护方便、效率较高
用于管理分布式计算机系统的操作系统
与集中式操作系统的主要区别在于 资源管理、进程通信和系统结构
⑥嵌入式操作系统
运行于嵌入式系统之上的操作系统
特点
微型化
专业化
实时性
1.3.2 进程管理
1、并发程序设计
操作系统的主要目标是提高计算机系统的处理效率， 增强系统中各种硬件的并行操作能力
顺序程序
程序中与各个操作相对应的程序段的执行一定是顺序的
特点
①顺序性
程序所规定的动作严格的按顺序执行
②封闭性
程序一旦开始执行，其计算结果不受外界因素的影响
③可再现性
程序的计算结果与他的运行速度无关
多个程序并发执行
指一组在逻辑上互相独立的程序或程序段在执行过程中， 其执行时间在客观上互相重叠
特点
并发程序没有封闭性
程序与其执行过程不是一一对应的关系
程序并发执行可以互相制约
2、进程的基本概念
系统的状态和各程序在其中活动的描述是动态的； 程序是静态的概念
进程
指一个具有一定独立功能的程序关于某个数据集合的一次运行活动
进程与程序的关系
①进程是程序在处理机上的一次执行过程，是动态的概念 程序只是一组指令的有序集合，是静态的概念
②进程是程序的执行过程，是一次运行活动，它的存在是暂时的； 程序可以作为一种软件资源长期保存，它的存在是永久的
③进程是程序的执行过程，进程的组成包括程序和数据，以及记录进程相关信息的“进程控制块”
④一个程序可能对应多个进程
⑤一个进程可以包含多个程序
3、进程的状态及其转化
进程活动的基本状态
（1）创建状态
（2）就绪状态
在多处理器系统中，每个CPU都有自己的就绪队列， 而每个活动进程某一时刻只会在一个就绪队列中
（3）等待状态
又称为阻塞状态或封锁状态，或称逻辑上是不可执行的
（4）运行状态
在单CPU下，处于运行状态的进程只能有一个
（5）终止状态
每个进程的创建是以建立进程控制块为标志
进程3种状态的转换
①处于就绪状态的进程，一旦分配到CPU，就转为运行状态
②处于运行状态的进程，当需要等待某个事件发生才能继续运行时，则转为等待状态； 或者由于分配给它的时间片用完，就让出CPU而转为就绪状态
③处于等待状态的进程，如果它等待的事件已经发生，就转为就绪状态
4、进程控制块及其组织
（1）进程控制块PCB
进程控制块是由系统为每个进程分别建立的，用以记录对应进程的程序和数据 的存储情况，记录进程的动态信息
PCB的基本内容
①进程名
②特征信息
③执行状态信息
④通信信息
⑤调度优先数
⑥现场信息
⑦系统栈
⑧进程映象信息
⑨资源占有信息
⑩族关系
（2）进程的组织
对进程的物理组织方式通常有线性表和链接表两种
5、进程调度
就是按一定策略动态地把CPU分配给处于就绪队列中的某一进程并使之执行的过程
进程调度亦可称为处理器调度或低级调度， 相应的进程调度程序可称为分配程序或低级调度程序
高级调度是作业调度，负责对CPU之外的系统资源进行调度
基本的进程调度方式
抢占方式
指就绪队列一旦有优先级高于当前正在运行的进程出现时，系统便立即把CPU分配给高优先级的进程，并保存被抢占了CPU的进程的有关状态信息，以便恢复
非抢占方式
一旦CPU分给了某进程，即使就绪队列中出现了优先级高的进程，也不能抢占CPU
在任一时刻，处于运行状态的进程数至多等于计算机系统CPU的个数
最基本的进程调度算法
（1）先来先服务调度算法
最常见策略
（2）时间片轮转调度算法
是系统把所有就绪进程按先后次序排队，CPU总是优先分配给就绪队列中的第一个就绪进程，并分配给它一个固定的时间片
（3）优先级调度算法
根据CPU是否可被抢占
抢占式优先级调度算法
非抢占式优先级调度算法
确定优先级的因素
进程类型
运行时间
通常成反比
作业的优先级
死锁状态
若干个进程均因互相“无知地”等待对方所占有的资源而无限地等待
1.3.3 存储管理
1、存储管理的功能和地址重定位
（1）存储管理的功能
①地址变换
②内存分配
③存储共享与保护
④存储器扩充
（2）地址重定位
地址变换（地址映射）
当用户程序进入内存执行时，必须把用户程序中的所有相对地址（逻辑地址）转换成内存中的实际地址（物理地址）
指对程序中的指令地址以及指令中有关地址的部分（有效地址）进行调整的过程
实现方式
静态地址重定位
在程序执行之前由操作系统的重定位装入程序完成，程序必须占用连续的内存空间 且一旦装入内存后，程序不便于移动
动态地址重定位
在程序执行期间进行，由专门的硬件机构完成，通常用重定位寄存器，在每次进行存储访问时，将取出的逻辑地址加上重定位寄存器的内容形成物理地址
2、连续存储管理（界地址存储管理）
基本特点
内存空间被划分成一个个分区，一个作业占一个分区， 即系统和用户作业都以分区为单位享用内存
地址重定位采取静态地址重定位方法，分区的存储保护可采用上、下界寄存器保护方式
为了实现地址的转换，需要设置一个基址寄存器（重定位寄存器）BR和 限长寄存器（界限寄存器）LR
3、分页式存储管理
作业空间被划分为页，实际的内存空间被划分为块，页的大小与块的大小相等
（1）分页式存储管理的地址重定位
分页式存储管理通常会在内存中为每个作业开辟一块特定区域，建立起作业的逻辑页与存储块之间的对应关系表，称为页面映象表或简称页表
最简单的页表只包含页号、块号
（2）分页式存储保护
可从两个方面实现
在进行地址变换时，产生的页号应小于页表长度，否则视为越界访问
可在页表中增加存取控制和存储保护的信息：对每一个存储块，可允许4种保护方式
禁止做任何操作、只能执行、只能读、能读/写
优点
能有效解决碎片问题，内存利用率高，内存分配与回收算法也比较简单
缺点
采用动态地址变换机构增加了硬件成本，也降低了处理机速度
4、分段式存储管理及段页式存储管理
（1）分段式存储管理
作业的地址空间由若干个逻辑分段组成，每一分段是一组逻辑意义完整的信息集合，并有自己的名字（段名） 每一段都是以0开始的连续的一位地址空间，整个作业则形成了二位地址空间
以段为基本单位分配内存，且每一段必须分配连续的内存空间， 但各段之间不要求连续
采用动态重定位技术
优点体现在地址空间的管理
（2）段页式存储管理
是分页和分段的结合，兼备二者优点
特点
①作业地址空间进行段式管理
②每段内再分成若干大小固定的页，每段都从零开始
③对内存空间的管理仍然和分页存储管理一样，将其分成若干个与页面大小相同的物理块，对内存空间的分配是以物理块为单位的
④作业的逻辑地址包括3个部分：段号、段内页号、页内位移
段号（s）| 段内页号（p）| 页内位移（d）
为了实现地址变换，段页式系统设立了段表和页表
为了指出运行作业的段表起始地址和段表的长度，硬件需要一个段表控制寄存器
5、虚拟存储器管理
根据程序的时间局部性和空间局部性，可在作业运行过程中只让当前用到的信息进入内存，其余的留在外存，从而给用户提供一个比实际内存空间大得多的地址空间，这种大容量的地址空间并不是真实的存储空间，而是虚拟的，故称这样的存储器为虚拟存储器，用于支持虚拟存储器的外存为后备存储器
（1）请求页式存储管理
与分页式存储管理不同，根据作业运行时的实际要求只装入了目前运行所要用到的一些页，其余的页仍保存在外存，等到需要时再请求系统调入
缺页中断
按照分页式管理的处理，程序中的逻辑地址变换时，根据页号可查页表， 若该页在内存，查找得到相应块号，转换成物理地址，执行程序指令； 若该页不在内存，则会引起缺页中断
当发生缺页中断时，若内存中已无空闲块，就要把已在内存的一些页面置换出去，常用的页面置换算法包括：
①最优算法
②先进先出算法
③最近最久未使用算法
优点
用户的地址空间不再受内存大小的限制，方便程序设计
可容纳更多作业进入系统，有利于多道程序运行
更有效利用内存
（2）请求段式存储管理
在程序运行时，首先调入一个或若干个程序段运行，在运行过程中调用到其他段时，会产生段错误，操作系统就根据该段长度在内存分配一个连续的分区给该段使用。若内存中无空闲分区，则考虑进行段的紧凑或淘汰某些段
1.3.4 文件管理
1、文件及文件系统
文件
指一组带标识（文件名）的、在逻辑上有完整意义的信息项的序列
文件系统
指负责存取和管理文件信息的软件机构
功能
方便用户，实现对文件的“按名存取”
实现对文件存储空间的组织、分配和文件信息的存储，并且要对文件提供保护和有效的检索等功能
常用文件系统
EXT2/4
Linux最为常用的文件系统
NFS
网络文件系统
HPFS
IBM OS/2的文件系统
FAT
NTFS
（1）文件类型
按用途分
系统文件
库文件
用户文件
按性质分
普通文件
目录文件
特殊文件
按保护级别分
只读文件
读写文件
可执行文件
不保护文件
按文件数据的形式分
源文件
目标文件
可执行文件
（2）文件系统模型
传统模型为层次模型，对支持单个文件系统比较合适； 现代操作系统一般可支持多个文件系统
2、文件的组织结构
（1）文件的逻辑结构
指从用户观点出发所见到的文件结构
记录式文件
在逻辑上总是被看成一组顺序记录的集合，是一种有结构的文件组织， 并且根据记录长度可分成定长记录文件和变长记录文件
流式文件
又称无结构文件，是由一组相关信息组合成的有序字符流
（2）文件的物理结构
指文件在外部存储介质上的存放形式，又称存储结构
基本的文件物理存储组织形式包括顺序结构、链接结构和索引结构
顺序结构
把一个逻辑上连续的文件信息存放在连续编号的物理块中， 只需给出首块块号和文件长度
链接结构
把一个逻辑上连续的文件分散的存放在不同的物理块中，在各物理块中设立一个指针（连接字），它指示该文件的下一个物理块，最后一个块连接字为NULL，表示该块是文件结尾
索引结构
系统为每个文件建立一个索引表
3、文件目录管理
（1）文件目录概念
为了根据文件名存取文件，必须建立文件名与文件在外存空间中的物理地址的对应，表示这种对应关系的数据结构称为文件目录。 把若干文件目录组织在一起，以文件的形式保存在外存上，就形成了目录文件
每个文件在目录文件中登记为一项 每个文件的文件目录项又称为文件控制块（FCB）
FCB一般包括
①有关文件存取控制的信息
②有关文件结构的信息
③有关文件使用的信息
④有关文件管理的信息
在文件目录实现中，为了减少检索文件访问的物理块数，会把文件目录项中的文件名和其他管理信息分开，后者称为索引结点（i结点）
（2）文件目录结构
根据文件目录的组织结构
①单级目录（简单文件目录）
是个线性表 要防止不同用户对文件取相同的名字
②二级目录
允许每个用户建立各自的名字空间，并通过建立相应的总文件目录来 管理这些名字空间
各个用户的名字空间构成了各个用户文件目录（UFD），而 管理这些目录的总文件目录称为主目录（MFD）
特点
提高了文件检索速度
部分地允许文件名重名，但对同一用户仍不允许
③多级层次目录（树结构目录）
优点
既方便用户查找文件，又可把不同类型和用途的文件分类
（不同/同一）用户可使用相同名字的文件
有利于文件的保护
缺点
不能直接支持文件或目录的共享
（3）存取权限
存取权限可以通过建立访问控制表（ACL）和存取权限表来实现
访问控制表
以文件为单位建立
存取权限表
以用户或用户组为单位建立
大型文件系统主要采用的安全性保护的措施
对文件和目录的权限设置
对文件和目录进行加密
4.、文件空闲区的组织
文件存储空间管理方案
（1）空闲文件项和空闲区表
空闲区和其他文件目录放在一张表中
（2）空闲块链
指将所有空闲块链接在一起
（3）位示图
用若干字节构成一张表，表中的每一个二进制位对应一个物理块，并依次顺序编号
（4）空闲块成组链接法
将所有的空闲块进行分组，再通过指针将组与组之间链接起来
1.3.5 I/O设备管理
1、输入/输出软件的层次结构
输入/输出软件的设计目的就是将软件组织成一种层次结构
2、中断处理过程
外部设备完成了I/O操作后，设备控制器便向CPU发出一个中断请求，CPU响应后便转向中断处理程序
①检查CPU响应中断的条件是否满足
②若满足，CPU响应中断，立即关中断
③保存被中断的CPU环境
④分析产生中断的原因，转入相应设备的中断处理程序
⑤执行中断处理程序
⑥恢复被中断进程的CPU现场，返回被中断的程序
⑦开中断，CPU继续执行
3、设备驱动程序
指驱动物理设备和DMA控制器或I/O控制等直接进行I/O操作的子程序集合
主要负责启动对应设备进行I/O操作
功能
①可将接收到的抽象要求转换为具体要求
②接受用户的I/O请求
③取出请求队列中的队首请求，完成指定的I/O操作
④处理来自设备的中断
4、与设备无关的I/O软件
功能
①向用户层软件提供同一接口
②设备命名
③设备保护
④提供一个独立与设备的块
5、用户层的I/O软件
是I/O系统软件分层中的最上层，它面向程序员， 负责与用户和设备无关的I/O软件通信
主要包含于I/O操作的库例程和SPOOLing系统
用户层I/O软件还会用到缓冲技术，它的实现主要是设置合适的缓冲区， 可通过硬件寄存器实现硬缓冲或在内存中设置软缓冲
6、设备的分配与回收
为了方便系统的管理，进程在使用资源时必须首先向设备管理程序提出资源申请
2、数据结构与算法
2.1 算法
2.1.1 算法的基本概念
算法是指解题方案的准确而完整的描述
对于一个问题，若可以通过一个计算机程序，在有限的存储空间内运行有限长的时间而得到正确的结果，则称这个问题是算法可解的
通常，程序的编制不可能优于算法的设计
算法的基本特征
（1）可行性
①算法的每一个步骤必须能够实现
②算法执行的结果要能够达到预期的目的
算法与计算公式有差别
（2）确定性
指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性
（3）有穷性
算法必须能在执行有限个步骤之后终止
（4）拥有足够的情报
2.1.2 算法设计基本方法
（1）列举法
基本思想
根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的
常用于解决“是否存在”“有多少种可能”等问题
（2）归纳法
基本思想
通过列举少量的特殊情况，经过分析，最后找出一般的关系
（3）递推
指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果
本质属于归纳法
（4）递归
基本思想
将问题逐层分解，当解决了最后的简单的问题后， 再沿着原来分解的逆过程逐步进行综合
分类
直接递归
间接递归
本质属于归纳法
（5）减半递推技术
分治法
对问题分而治之，常用的分治法就是减半递推技术
减半
将问题的规模减半，而问题的性质不变
递推
重复“减半”的过程
是归纳法的分支
（6）回溯法
就是“试”
通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探
2.1.3 算法复杂度
时间复杂度
指执行算法所需要的计算工作量
可以用算法在执行过程中所需基本运算的执行次数来度量算法的工作量
算法所执行的基本运算次数与问题的规模有关
算法的工作量=f(n)
n是问题的规模
分析算法工作量的方法
平均性态
用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量
最坏情况复杂性
指在规模为n时，算法所执行的基本运算的最大次数
空间复杂度
指执行这个算法所需要的内存空间
算法程序所占的空间
输入的初始数据所占的存储空间
算法执行过程中所需要的额外空间
通常采用压缩存储技术
2.2 数据结构的基本概念
“数据结构”这门学科主要研究和讨论的问题
①数据的逻辑结构
②数据的存储结构
③对各种数据结构进行的运算
2.2.1 什么是数据结构
数据处理
指对数据集合中的各元素以各种方式进行运算
在数据处理领域中，每一个需要处理的对象都可以抽象成数据元素（简称元素）
一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系（联系），这种关系反映了该集合中的数据元素所固有的一种结构。 在数据处理领域中，通常把这种固有的关系用前后件关系（或直接前驱与直接后继关系）来描述
数据结构
指相互有关联的数据元素的集合
1、数据的逻辑结构
数据结构应包含的信息
①表示数据元素的信息
②表示各数据元素之间的前后件关系
“前后件关系”指逻辑关系，与存储位置无关
指反映数据元素之间逻辑关系的数据结构
逻辑结构的两要素
一是数据元素的集合，通常记为D
二是D上的关系，通常记为R
为了反应D中各元素之间的前后件关系，一般用二元组来表示 如a与b是D中的两个数据，则二元组（a，b）表示a是b的前件，b是a的后件
数据结构可表示为 B=（D，R）
B表示数据结构
2、数据的存储结构
数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（物理结构）
2.2.2 数据结构的图形表示
在数据结构的图形表示中，对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，简称结点
在数据结构中，没有前件的结点称为根结点，没有后件的结点称为终端结点（叶子结点）
根据需要或在处理过程中，可以在一个数据结构中增加一个新结点（插入运算），也可删除数据结构中的某个结点（删除运算）
插入和删除是对数据结构的两种基本运算 此外，运算还有查找、分类、合并、分解、复制和修改等
2.2.3 线性结构与非线性结构
若在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构
依据数据结构中各元素之间前后件关系的复杂程度
线性结构
若一个非空的数据结构满足这两个条件，则为线性结构，又称线性表
①有且只有一个根结点
②每一个结点最多有一个前件和后件
在一个线性结构中插入或删除任何一个结点后还应是线性结构， 否则即使满足二条件，也不是线性结构
非线性结构
如果一个数据结构不是线性结构，则称之为非线性结构
线性结构与非线性结构都可以是空的数据结构
要以具体情况来确定。 若对该数据结构的运算是按线性结构的规则来处理的，则属于线性结构， 否则属于非线性结构
2.3 线性表及其顺序存储结构
2.3.1 线性表的基本概念
线性表由一组数据元素构成 在复杂的线性表中，由若干数据项组成的数据元素称为记录，而由多个记录构成的线性表称为文件
线性表是由n（非负）个数据元素a1，a2，a3，…，an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件
即线性表或是一个空表可以表示为
ai是属于数据对象的元素，通常也称为线性表的一个结点
线性表是一种线性结构
非空线性表的结构特征
①有且只有一个根结点a1，它无前件
②有且只有一个终端结点an，它无后件
③除根结点与终端结点外，其他所有结点有且只有一个前件和后件。
线性表中结点个数n称为线性表的长度，当n=0时，称为空表
2.3.2 线性表的顺序存储结构
顺序存储结构具有的基本特点
①线性表中所有元素所占的存储空间是连续的
②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的
在顺序存储结构中，线性表中每一个数据元素在计算机存储空间中的存储地址由该元素在线性表中的位置序号唯一确定
在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间
对线性表的主要运算
线性表的插入
线性表的删除
线性表的排序
线性表的分解
线性表的合并
线性表的复制
线性表的逆转
2.3.3 顺序表的插入运算
假设线性表的存储空间为V（1：m），线性表的长度为n（n<=m），插入的位置为i（表示在第i个元素之前插入），则插入过程为
①首先处理三种异常情况
当存储空间已满（即n=m）时为“上溢”错误，不能进行插入，算法结束
当i>n时，认为在最后一个元素之后插入
当i<1时，认为在第1个元素之前插入
②然后从最后一个元素开始，直到第i个元素，其中每一个元素均往后移动一个位置
③最后将新元素插入到第i个位置，并且将线性表的长度增加1
2.3.4 顺序表的删除运算
假设线性表的存储空间为V（1：m），线性表的长度为n（n<=m），删除的位置为i（表示删除第i个元素），则删除过程为
①首先处理两种异常情况
当线性表为空时为“下溢”错误，不能进行删除，算法结束
当i<1或i>n时，认为不能进行删除，算法结束
②然后从第i+1个元素开始，直到最后一个元素，其中每一个元素均依次往前移动一个位置
③最后将线性表的长度减小1
2.4 栈和队列
2.4.1 栈及其基本运算
1、什么是栈
栈是限定在一端进行插入与删除的线性表
允许插入与删除的一端称为栈顶， 而不允许插入与删除的另一端称为栈底
栈顶元素总是最后被插入的元素，也是最先能被删除的元素
栈底元素总是最先被插入的元素，也是最后才能被删除的元素
栈是按照“先进后出”或“后进先出”的原则组织数据的， 故栈也被称为“先进后出”表或“后进先出”表 栈有记忆作用
通常用指针top来指示栈顶的位置，用指针bottom指向栈底
往栈中插入一个元素称为入栈运算，删除一个元素称为退栈运算 栈顶指针top动态反应了栈中元素的变化情况
2、栈的顺序存储及其运算
在程序设计语言中，用一维数组S（1：m）作为栈的顺序存储空间， 其中m为栈的最大容量
top=0表示栈空，top=m表示栈满
栈的基本运算
入栈
在栈顶位置插入一个新元素
操作过程
①首先判断栈顶指针是否已经指向存储空间最后一个位置
若是，则说明栈空间已满，无法再进行入栈操作（栈“上溢”错误），算法结束
②然后将栈顶指针进一（top+1）
③最后将新元素x插入栈顶指针指向的位置
退栈
取出栈顶元素并赋给一个指定的变量
操作过程
①首先判断栈顶指针是否为0
若是，则说明栈空，无法进行退栈操作（栈“下溢”错误），算法结束
②然后将栈顶元素赋给一个指定的变量
③最后将栈顶指针退一（top-1）
读栈顶元素
将栈顶元素赋给一个指定的变量
操作过程
①首先判断栈顶指针是否为0
若是，则说明栈空，读不到栈顶元素，算法结束
②然后将栈顶元素赋给指定的变量y
2.4.2 队列及其基本运算
1、什么是队列
队列的原则
①初始时线性表为空
②当有用户程序来到时，将该用户程序加到线性表的末尾进行等待
③当计算机系统执行完当前的用户程序后，就从线性表的头部取出一个用户程序来执行
指允许在一端进行插入、而在另一端进行删除的线性表
允许插入的一端称为队尾，通常用尾指针（rear）指向队尾元素 允许删除的一端称为排头（队头），常用排头指针（front）指向排头元素的前一个位置
队列又称“先进先出”或“后进后出”线性表，体现了“先来先服务”的原则
在队尾插入一个元素称为入队运算，从排头删除一个元素称为退队运算
2、循环队列及其运算
循环队列
将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间
基本运算
入队运算
每进行一次入队运算，队尾指针就进一， 当队尾指针rear=m+1时，则置rear=1
退队运算
每进行一次退队运算，排头指针就进一， 当排头指针front=m+1时，则置front=1
由于无论队列空还是满，front=rear，故为了区分队列满还是空，增加一个标志s
s=0表示队列空；s=1表示队列非空
队列空与队列满的条件
队列空
s=0
队列满
s=1，且front=rear
运算
假设循环队列的初始状态为空，即s=0，且front=rear=m
入队运算
在循环队列的队尾加入一个新元素
操作过程
①首先判断队列是否满
当循环队列非空且队尾指针等于排头指针时，说明队列已满（“上溢”），算法结束
②然后将队尾指针进一（rear=rear+1），并当rear=m+1时置rear=1
③最后将新元素x插入队尾指针指向的位置，并且置循环队列非空标志
退队运算
在循环队列的排头位置推出一个元素并赋给指定的变量
操作过程
①首先判断循环队列是否为空
当队列空（s=0）时，“下溢”，算法结束
②然后将排头指针进一（front=front+1），并当front=m+1时置front=1
③再将排头指针指向的元素赋给指定的变量
④最后判断退队后循环队列是否为空
2.5 线性链表
2.5.1 线性链表的基本概念
假设数据结构中的每一个数据结点对应一个存储单元， 这种存储单元称为存储结点，简称结点
在链式存储方式中，每个结点由两个部分组成
数据域
用于存放数据元素值
指针域
用于存放指针（指针用于指向该结点的前件或后件）
数据元素之间的逻辑关系由指针域来确定
1、线性链表
指线性表的链式存储结构
存储结点
数据域
存储数据元素的值
指针域
存放下一个数据元素的存储序号（即存储结点的地址），即指向后件结点
是线性单链表， 而在双向链表中，一个左指针（Link），指前件，一个右指针（Rlink），指后件
用一专门的指针HEAD指向线性链表中第一个数据元素的结点 用NULL或0表示最后一个结点的指针域为空，表示链表终止
2、带链的栈
实际应用中，带链的栈可用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈
可利用栈经常要进行退栈和入栈操作
基本操作
①栈的初始化
②入栈
③退栈
④读栈顶元素
栈底指针位置可能发生改变
3、带链的队列
基本操作
①队列的初始化
②入队
③退队
2.5.2 线性链表的基本运算
①在线性链表中包含指定元素的结点之前插入一个新元素 ②在线性链表中删除包含指定元素的结点 ③将两个线性链表按要求合并成一个线性链表 ④将一个线性链表按要求进行分解 ⑤逆转线性链表 ⑥复制线性链表 ⑦线性链表的排序 ⑧线性链表的查找
1、在线性链表中查找指定元素
在非空线性链表中寻找包含指定元素值x的前一个结点p的基本方法
从头指针指向的结点开始往后沿指针进行扫描，直到后面已经没有结点或下一个结点的数据为x为止
2、线性链表的插入
指在链式存储结构的线性表中插入一个新元素
在线性链表中包含元素x的结点之前插入一个新元素b的过程
①从可利用栈取得一个结点，设该结点号为p，并置结点p的数据域为插入的元素值b
②在线性链表中寻找包含元素x的前一个结点，设该结点的存储序号为q
③最后将结点p插入到结点q之后
由于插入的新结点取自于可利用栈，故只要可利用栈不空，在线性链表插入时就不会出现“上溢”
3、线性链表的删除
指在链式存储结构下的线性表中删除包含指定元素的结点
在线性链表中删除包含元素x的结点过程
①在线性链表中寻找包含元素x的前一个结点，设该结点序号为q
②将结点q后的结点p从线性链表中删除
③将包含元素x的结点p送回可利用栈
2.5.3 循环链表
与线性链表相比的特点
①增加了一个表头结构，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头针指向表头结点
②最后一个结点的指针域不是空，而是指向表头结点
实际运用中，与线性链表相比的优点
①只要指出表中任意一个结点的位置，就可以从它出发访问到表中其他所有的结点
②由于在循环链表中设置了一个表头结点，故在任何情况下循环链表中至少有一个结点存在，从而使空表与非空表的运算统一
2.6 树与二叉树
2.6.1 树的基本概念
树是一种简单的非线性结构，所有数据元素之间的关系具有明显的层次特性
在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，它们都称为该结点的子结点，没有后件的结点称为叶子结点。一个结点所拥有的后件个数称为该结点的度，在树中，一个结点的度为n，则表示该结点有n个分支，而每一个分支指向一个后件，因此在树中，除根结点外，每一个结点都有一个唯一的分支指向它，故树中的结点数即为树中所有结点的度之和加1.
树的分层原则
根结点在第1层
同一层上的所有结点的子结点都在下一层
树的最大层次称为树的深度
以某结点的一个子结点为根构成的树称为该结点的一棵子树
叶子结点没有子树
表示算术表达式的原则
①表达式中的每一个运算符在树中对应一个结点，称为运算符结点
②运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）
③运算对象中的单变量均为叶子结点
树在计算机中通常用多重链表表示
2.6.2 二叉树及其基本性质
1、什么是二叉树
特点
①非空二叉树只有一个根结点
②每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树
所有子树也均为二叉树
当一个结点既没有左子树也没有右子树时，该结点为叶子结点
2、二叉树的基本性质
性质1
在二叉树的第k层上，最多有2的k-1次（k>=1）个结点
性质2
深度为m的二叉树最多有2的m次-1个结点
性质3
在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2个结点多1个
性质4
具有n个结点的二叉树，其深度至少为[log2n]+1个，其中[ ]表示取整
3、满二叉树与完全二叉树
（1）满二叉树
除最后一层外，每一层上的所有结点都有两个子结点
（2）完全二叉树
除最后一层外，每一层上的结点数均达到最大值， 在最后一层只缺少右边的若干结点
叶子结点只可能在层次最大的两层出现
满二叉树也是完全二叉树，完全二叉树一般不是满二叉树
性质5
具有n个结点的完全二叉树的深度为[log2n]+1
性质6
设完全二叉树共有n个结点。若从根结点开始，按层序（每一层从左到右）用自然数1,2，...，n给结点进行编号，则对于编号为k（k=1,2，…，n）的结点有以下结论
①若k=1，则该结点为根结点，它没有父结点； 若k>1，则该结点的父结点编号为INT（k/2）
②若2k<=n，则编号为k的结点的左子结点编号为2k； 否则该结点无左子结点（显然也无右子结点）
③若2k<=n，则编号为k的结点的右子结点编号为2k+1；否则该结点无右子结点
2.6.3 二叉树的存储结构
用于存储二叉树中各元素的存储结点的组成
数据域
指针域（两个）
左指针域
用于指向该结点的左子结点的存储地址
右指针域
用于指向该结点的右子结点的存储地址
二叉树的链式存储结构称为二叉链表
BT称为二叉链表的头指针，用于指向二叉树跟结点
顺序存储结构对于一般的二叉树不适用， 对满二叉树和完全二叉树可按层序进行顺序存储
2.6.4 二叉树的遍历
指不重复地访问二叉树的所有结点
遍历二叉树的方法实际上是要确定访问各结点的顺序，以便不重不漏的访问到二叉树中的所有结点
一般先遍历左子树，再遍历右子树
在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可分为
1、前序遍历（DLR）
首先访问根结点，然后遍历左子树，最后遍历右子树， 且在遍历左、右结点时，仍按上序
故前序遍历二叉树的过程是一个递归的过程
过程
若二叉树为空，则结束返回
否则
①访问根结点
②前序遍历左子树
③前序遍历右子树
2、中序遍历（LDR）
首先遍历左子树，然后访问根结点，最后遍历右子树 且在遍历左、右子树时，仍按上序
故中序遍历二叉树的过程是一个递归的过程
过程
若二叉树为空，则结束返回
否则
①中序遍历左子树
②访问根结点
③中序遍历右子树
3、后序遍历（LRD）
首先遍历左子树，然后遍历右子树，最后访问根结点 且在遍历左、右子树时，仍按上序
故后序遍历二叉树的过程是一个递归的过程
过程
若二叉树为空，则结束返回
否则
①后序遍历左子树
②后序遍历右子树
③访问根结点
2.7 查找技术
2.7.1 顺序查找
又称顺序搜索，一般指在线性表中查找指定的元素，基本方法为
从线性表的第一个元素开始，依此将线性表中的元素与被查元素进行比较，若相等则表示找到（查找成功） 若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（查找失败）
只能采用顺序查找的情况
线性表是无序表
采用链式存储结构的有序线性表
2.7.2 二分法查找
又称对分查找，只适用于顺序存储的有序表 （指线性表中的元素按值非递减排列，即由小到大，但允许相邻元素值相等）
设有序线性表的长度为n，被查元素为x，则对分查找的方法为
将x与线性表的中间项进行比较
若中间项的值等于x，则说明查到，查找结束
若x小于中间项的值，则在线性表的前半部分以相同的方法查找
若x大于中间项的值，则在线性表的后半部分以相同的方法查找
（一直进行到查找成功或子表长度为0时）
最坏比较log2n次
2.8 排序技术
2.8.1 交换类排序法
1、冒泡排序法
通过相邻元素的交换逐步将线性表变成有序
基本过程
首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小
若两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。最后就将线性表中的最大者换到了表的最后
然后，从后到前扫描剩下的线性表，在扫描过程中逐次比较相邻两个元素的大小
若两个元素中，后面的元素小于前面的元素，则将它们互换，称之为消去了一个逆序。最后就将线性表中的最小者换到了表的最前
重复操作至剩下的线性表变空为止
每一次都将最大者沉到表的底部，最小者冒到表的前头，故称为冒泡排序，也可称为下沉排序
最坏情况要进行n（n-1）/2次比较
2、快速排序法
也是一种互换类的排序方法，但因比冒泡快，故称为快速排序法
基本思想
线性表的分割
从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成了两部分（两个子表），T插入到其分界线的位置
一直分割直到所有子表为空
最坏情况要进行n（n-1）/2次比较，但实际效率比冒泡高得多
2.8.2 插入类排序法
1、简单插入排序法
插入排序
指将无序序列中的各元素依次插入到已经有序的线性表中
假设线性表中前j-1个元素已经有序，现在要讲线性表中第j各元素插入到前面的有序子表中，过程为
首先将第j个元素放到一个变量T中，然后从有序子表的最后一个元素开始，往前逐个与T比较，将大于T的元素依次向后移动一个位置，直到发现一个元素不大于T为止
最坏情况要进行n（n-1）/2次比较，效率与冒泡相同
2、希尔排序法
基本思想
将整个无序序列分割成若干小的子序列分别进行插入排序
子序列的分割方法
将相隔某个增量h的元素构成一个子序列。 在排序过程中，逐次减小这个增量，最后当h减小到1时，进行依次插入排序，排序完成
增量序列一般取
n为待排序序列的长度
最坏情况所需比较次数为
2.8.3 选择类排序法
1、简单选择排序法
基本思想
扫描整个线性表，从中选出最小的元素，将它交换到表的最前面，然后对剩下的子表采用同样的方法，直到子表空为止
最坏情况要进行n（n-1）/2次比较
2、堆排序法
在调整堆的过程中，总是将根结点值与左、右子树的根结点值进行比较，若不满足堆的条件，则将左、右子树根结点值中的大者与根结点值进行交换 直到所有子树均为堆为止
方法
①首先将一个无序序列建成堆
②然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应在序列的最后）。不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序列，反复至剩下的子序列为空为止
最坏情况所需比较次数为
3、程序设计基础
3.1 程序设计方法与风格
清晰第一，效率第二
1、源程序文档化
考虑因素
①符号名的命名
符号名的命名应具有一定的实际含义，以便对程序功能的理解
②程序注释
序言性注释
常位于每个程序的开头部分，它给出程序的整体说明，主要描述内容可以包括
程序标题 程序功能说明 主要算法 接口说明 程序位置 开发简历 程序设计者 复审者 复审日期 修改日系等
功能性注释
一般嵌在源程序体之中，主要描述其后的语句或程序做什么
③视觉组织
可以再程序中利用空格、空行、缩进等技巧使程序层次清晰
2、数据说明的方法
注意点
①数据说明的次序规范化
②说明语句中变量安排有序化
③使用注释来说明复杂数据的结构
3、语句的结构
注意点
在一行内只写一条语句
程序编写应优先考虑清晰性
除非对效率有特殊要求，程序编写要做到清晰第一，效率第二
首先要保证程序正确，然后才要求提高速度
避免使用临时变量而使程序的可读性下降
避免不必要的转移
尽可能使用库函数
避免采用复杂的条件语句
尽量减少使用“否定”条件的条件语句
数据结构要利于程序的简化
要模块化、使模块功能尽可能单一化
利用信息隐蔽，确保每一个模块的独立性
从数据出发去构造程序
不要修补不好的程序，要重新编写
4、输入和输出
原则
①对所有的输入数据都要检验数据的合法性
②检查输入项的各种重要组合的合理性
③输入格式要简单，以使得输入的步骤和操作尽可能简单
④输入数据时，应允许使用自由格式
⑤应允许默认值
⑥输入一批数据时，应允许使用自由格式
⑦在以交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入的请求，同时在数据输入过程中和输入结束时，应在屏幕上给出状态信息
⑧当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性；给所有的输出加注释，并设计输出报表格式
3.2 结构化程序设计
3.2.1 结构化程序设计的原则
（1）自顶向下
（2）逐步求精
（3）模块化
（4）限制使用GOTO语句
3.2.2 结构化程序的基本结构与特点
（1）顺序结构
（2）选择结构
（3）循环结构
按结构化程序设计方法设计出的程序的优点
程序易于理解、使用和维护
提高了编程工作的效率，降低了软件开发成本
3.2.3 结构化程序设计原则和方法的应用
设计中应把握的要素
①使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑
②选用的控制结构只准许有一个入口和一个出口
③程序语句组成容易识别的块，每块只有一个入口和一个出口
④复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现
⑤语言中所没有的控制结构，应该采用前后一致的方法来模拟
⑥严格控制GOTO语句的使用
3.3 面向对象的程序设计
3.3.1 关于面向对象方法
面向对象的软件开发方法的提出以20世纪60年代末SIMULA语言为标志
本质
主张从客观世界固有的事物出发来构造系统，提倡用人类在现实生活中常用的思维方法来认识、理解和描述客观事物，强调最终建立的系统能够映射问题域， 即系统中的对象以及对象之间关系能够如实的反映问题域中的固有事物及其关系
优点
1、与人类习惯的思维方法一致
面向对象方法和技术以对象为核心
基本原理
使用现实世界的概念抽象的思考问题从而自然地解决问题
2、稳定性好
3、可重（chong）用性好
软件重用是指在不同的软件开发过程中重复使用或相似软件元素的过程
重用是提高软件生产率的最主要的方法
重复使用一个对象类的方法
创建该类的实例，从而直接使用它
从它派生出一个满足当前需要的新类
4、易于开发大型软件产品
5、可维护性好
（1）用面向对象的方法开发的软件稳定性比较好
（2）用面向对象的方法开发出了软件比较容易修改
（3）用面对对象的方法开发出的软件比较容易理解
（4）易于测试和调试
3.3.2 面向对象方法的基本概念
1、对象
对象可以用来表示客观世界中的任何实体，应用领域中有意义的、与所要解决的问题有关系的任何事物都可以作为对象
面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个实体， 是构成系统的一个基本单位，它由一组表示其静态特征的属性和它可执行的一组操作组成。
属性
指对象所包含的信息，它在设计对象时确定，一般只能通过执行对象的操作来改变
不同对象的同一属性可以具有相同或不同的属性值 属性值应指的是纯粹的数据值，而不能指对象
操作
描述了对象执行的功能，若通过消息传递，还可以为其他对象使用
基本特点
①标识唯一性
对象可由其内在本质来区分
②分类性
可以将具有相同属性和操作的对象抽象成类
③多态性
同一个操作可以是不同对象的行为
④封装性
对象的内部状态只能由其自身改变
⑤模块独立性好
对象内部各种元素彼此结合得很紧密，内聚性强
2、类和实例
类是具有共同属性、共同方法的对象的集合 类是对象的抽象，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例
“对象”可以指具体也可以泛指一般 “实例”必然指一个具体的对象
3、消息
是一个实例与另一个实例之间传递的信息， 它请求对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流
消息中只包含传递者的要求，但并不指示接受者应该怎样完成这些处理
组成部分
①接受信息的对象的名称
②消息标识符（消息名）
③零个或多个参数
4、继承
是使用已有的类定义作为基础建立新类的定义技术 广义地说，继承是指能够直接获得已有的性质和特征，而不必重复定义它们
单继承
一个类只允许有一个父类
多重继承
一个类允许有多个父类
5、多态性
指同样的消息被不同的对象接收时导致完全不同的行动的现象
4、软件工程基础
4.1 软件工程基本概念
4.1.1 软件定义与软件特点
软件是与计算机系统的操作有关的计算机程序、规程及可能的相关文档的完整集合
程序
是软件开发人员根据用户需求开发的、用程序设计语言描述的、适合计算机执行的指令序列
数据
是使程序能正常操纵信息的数据结构
文档
是与程序开发、维护和使用有关的图文资料
软件的组成部分
机器可执行的程序和数据
机器不可执行的，与软件开发、运行、维护、使用等有关的文档
特点
①软件是一种逻辑实体，而不是物理实体，具有抽象性
②软件的生产与硬件不同，它没有明显的制作过程
③软件在运行、使用期间不存在磨损、老化问题
④软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，这导致了软件移植的问题
⑤软件复杂性高，成本高昂
⑥软件开发涉及诸多的社会因素
分类
按功能分
应用软件
为解决特定领域的应用而开发的软件
系统软件
是计算机管理自身资源，提高计算机使用效率并服务于其他程序的软件
如操作系统，编译程序，汇编程序，网络软件，数据库管理系统
支撑软件（工具软件）
是介于系统软件和应用软件之间，协助用户开发软件的工具型软件
4.1.2 软件危机与软件工程
软件工程概念的出现源自软件危机
软件危机
泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题
主要表现
①软件需求的增长得不到满足
②软件开发成本和进度无法控制
③软件质量难以保证
④软件不可维护或维护程度非常低
⑤软件的成本不断提高
⑥软件开发生产率的提高赶不上硬件的发展和应用需求的增长
软件工程
应用计算机科学理论和技术以及工程管理原则和方法，按预算和进度，实现满足用户要求的软件产品的定义、开发、发布和维护的工程或进行研究的学科
三要素
方法
是完成软件工程项目的技术手段
工具
支持软件的开发、管理、文档生成
过程
支持软件开发的各个环节的控制、管理
软件工程的进步与学科的发展是近几十年软件产业迅速发展的重要原动力
核心思想
把软件产品看作一个工程产品来处理
4.1.3 软件过程与软件生命周期
1、软件过程
是把输入转化为输出的一组彼此相关的资源和活动
基本活动
①P（plan）
软件规格说明
②D（do）
软件开发或软件设计与实现
③C（check）
软件确认
④A（action）
软件演进
通常把用户的要求转变成软件产品的过程叫做软件开发过程
2、软件生命周期
指软件产品从提出、实现、使用维护到停止使用退役的过程 可分为三个阶段
软件定义
任务是确定软件开发工作必须完成的目标，确定工程的可行性
软件开发
任务是具体完成设计和实现定义阶段所定义的软件 通常包括总体设计和详细设计（系统设计）、编码和测试（系统实现）
软件运行维护
任务是使软件在运行中持久的满足用户的需要
4.1.4 软件工程的目标与原则
1、软件工程的目标
基本目标
付出较低的开发成本
达到要求的软件功能
取得较好的软件性能
开发的软件易于移植
需要较低的维护费用
能按时完成开发，及时交付使用
软件工程的理论和技术性研究的主要内容
（1）软件开发技术
包括软件开发方法学（主体内容）、开发过程、开发工具和软件工程环境
（2）软件工程管理
包括软件管理学、软件工程经济学、软件心理学等
2、软件工程的原则
①抽象
②信息隐蔽
③模块化
④局部化
⑤确定性
⑥一致性
⑦完备性
⑧可验证性
4.1.5 软件开发工具与软件开发环境
1、软件开发工具
软件开发工具的发展是从单项工具的开发逐步向集成工具发展
2、软件开发环境
是全面支持软件开发全过程的软件工具集合
4.2 结构化分析方法
包括结构化分析方法、结构化设计方法和结构化编程方法，其核心和基础是结构化程序设计理论
4.2.1 需求分析与需求分析方法
1、需求分析
（1）需求的定义
①用户解决问题或达到目标所需的条件或权能
②系统或系统部件要满足合同、标准、规范或其他正式规定文档所需具有的条件或权能
③一种反映①或②所描述的条件或权能的文档说明
（2）需求分析阶段的工作
①需求获取
目的
确定对目标系统的各方面需求
主要任务
建立获取用户需求的方法框架，并支持和监控需求获取的过程
关键问题
对问题空间的理解
人与人之间的通信
不断变化的需求
②需求分析
③编写需求规格说明书
④需求评审
2、需求分析方法
①结构化分析方法
面向数据流的结构化分析方法
面向数据结构的Jackson方法
面向数据结构的结构化数据系统开发方法
②面向对象的分析方法
静态分析方法
动态分析方法
4.2.2 结构分析方法
1、关于结构化分析方法
是结构化程序设计理论在软件需求分析阶段的运用
步骤
①通过对用户的调查，以软件的需求为线索，获得当前系统的具体模型
②去掉具体模型中非本质因素，抽象出当前系统的逻辑模型
③根据计算机的特点分析当前系统与目标系统的差别，建立目标系统的逻辑模型
④完善目标系统并补充细节，写出目标系统的软件需求规格说明
⑤评审直到确认完全符合用户对软件的需求
2、结构化分析的常用工具
（1）数据流图（DFD）
建立步骤
①由外向里
先画系统的输入输出，然后画系统的内部
②自顶向下
顺序完成顶层、中间层、底层数据流图
③逐层分解
构成规则和注意事项
①对加工处理建立唯一、层次性的编号，且每个加工处理通常要求既有输入又有输出
②数据存储之间不应该有数据流
③数据流图的一致性
④父图、子图关系与平衡规则
（2）数据字典（DD）
数据字典是结构化分析方法的核心
作用
对DFD中出现的被命名的图形元素的确切解释
包含的信息
名称、别名、何处使用/如何使用、内容描述、补充信息等
（3）判定树
（4）判定表
4.2.3 软件需求规格说明书
1、软件需求规格说明书的作用
①便于用户、开发人员进行理解和交流
②反映出用户问题的结构，可以作为软件开发工作的基础和依据
③作为确认测试和验收的依据
④为成本估算和编制计划进度提供基础
⑤软件不断改进的基础
2、软件需求规格说明书的内容
应重点描述
软件的目标 软件的功能需求 性能需求 外部接口 属性 约束条件
3、软件需求规格说明的特点
衡量软件需求规格说明书质量好坏的标准、标准的优先级及标准的内涵
①正确性
②无歧义性
③完整性
④可验证性
⑤一致性
⑥可理解性
⑦可修改性
⑧可追踪性
4.3 结构化设计方法
4.3.1 软件设计的基本概念
1、软件设计的基础
软件设计是一个把软件需求转换为软件表示的过程
基本目标
确定系统的物理模型
重要性和地位
①软件开发阶段占据软件项目开发总成本绝大部分，是在软件开发中形成质量的关键环节
②软件设计是开发阶段最重要的步骤，是将需求准确地转化为完整的软件产品或系统的唯一途径
③软件设计做出的决策，最终影响软件实现的成败
④设计是软件工程和软件维护的基础
内容
从技术观点看
软件设计包括软件结构设计、数据设计、接口设计、过程设计
从工程管理角度看
软件设计分两步完成：概要设计（结构设计）和详细设计
软件设计一般过程
软件设计是一个迭代的过程，先进行高层次的结构设计，后进行低层次的过程设计，穿插进行数据设计和接口设计
2、软件设计的基本原理
（1）抽象
（2）逐步求精和模块化
（3）信息隐蔽和局部化
信息隐蔽
所设计的模块使得其所包含的信息对于不需要这些信息的模块是不能访问的
隐蔽的是模块的实现细节，而非一切信息
（4）模块独立性
指软件模块的编写和修改应使其具有独立功能，且与其他模块的关联尽可能少
3、结构化设计方法
基本思想
将软件设计成由相对独立、单一功能的模块组成的结构
4.3.2 概要设计
1、概要设计的任务
（1）设计软件系统结构
具体过程
①采用某种设计方法，讲一个复杂的系统按功能划分成模块
②确定每个模块的功能
③确定模块之间的调用关系
④确定模块之间的接口
⑤评价模块结构的质量
（2）数据结构及数据库设计
数据设计
是实现需求定义和规格说明过程中提出的数据对象的逻辑表示
具体任务
确定输入、输出文件的详细数据结构
结合算法设计，确定算法所必需的逻辑数据结构及其操作
确定对逻辑数据结构所必需的那些操作的程序模块，限制和确定各个数据设计决策的影响范围
需要与操作系统或调度程序接口所必需的控制表进行数据交换时，确定其详细的数据结构和使用规则
数据的保护性设计：防卫性、一致性、冗余性设计
原则
①用于功能和行为的系统分析原则也应用于数据
②应该标识所有的数据结构以及其上的操作
③应当建立数据字典，并用于数据设计和程序设计
④低层的设计决策应该推迟到设计过程的后期
⑤只有那些需要直接使用数据结构、内部数据的模块才能看到该数据的表示
⑥应该开发一个由有用的数据结构和应用于其上的操作组成的库
⑦软件设计和程序设计语言应该支持抽象数据类型的规格说明和实现
（3）编写概要设计文档
要编写概要设计说明书、数据库设计说明书、集成测试计划等
（4）概要设计文档评审
软件结构设计工具
（程序）结构图
是描述软件结构的图形工具
模块用一个矩形表示
箭头表示模块间的调用关系
带注释的箭头表示模块调用过程中来回传递的信息
带实心圆的箭头表示传递的是控制信息
带空心圆的箭心表示传递的是数据
常用的结构图
传入模块、传出模块、变换模块和协调模块
有关术语
深度
表示控制的层数
上级模块、从属模块
上下两层模块a和b，且有a调用b，则a是上级模块，b是从属模块
宽度
整体控制跨度（最大模块数的层）的表示
扇入
调用一个给定模块的模块个数
扇出
一个模拟块直接调用的其他模块数
叶子模块
树中位于叶子结点的模块
2、面向数据流的结构化设计方法
（1）数据流类型
变换型
事务型
（2）面向数据流设计方法的实施要点与设计过程
设计过程和步骤
第1步
分析、确认数据流图的类型，区分是事物型还是变化型
第2步
说明数据流的边界
第3步
把数据流图映射为程序结构
①变换型
1、确定数据流图是否具有变换特性
2、确定输入流和输出流的边界，划分出输入、变换和输出。独立出变换中心
3、进行第一级分解，将变换型映射成软件结构
输入数据处理模块协调对所有输入数据的接收
变换中心控制模块管理对内部形式的数据的所有操作
输出数据处理控制模块协调输出信息的产生过程
4、按上述步骤如出现事物流也可按事物流的映射方式对各个子流进行逐级分解，直到分解到基本功能
5、对每个模块写一个简要说明
内容为该模块的接口描述、模块内部的信息、过程陈述、包括的主要判定点及任务等
6、利用软件结构的设计原则对软件结构进一步转化
②事物型
步骤与变换型大致类似，主要差别在于数据流图到软件结构的映射方法不同
它是将事务中心映射成为软件结构中发送分支的调度模块，将接受通路映射成软件结构的接收分支
第4步
根据设计准则对产生的结构进行细化和求精
3、设计的准则
①提高模块独立性
②模块规模适中
③深度、宽度、扇入、扇出适当
经验表明，好的软件设计结构常是顶层高扇出，中间层扇出较少，底层高扇入
④使模块的作用域在该模块的控制域内
⑤应减少模块的接口和界面的复杂性
⑥设计成单入口、单出口的模块
⑦设计功能可预测的模块
4.3.3 详细设计
任务
为软件结构图中的每一个模块确定实现算法和局部数据结构，用某种选定的表达工具表示算法和数据结构的细节
常见过程设计工具
图形工具
程序流程图（程序框图）
程序流程图构成的5种控制结构
顺序型
选择型
先判断重复型
后判断重复型
多分支选择型
N-S图
5种控制结构
特征
①每个构件具有明确的功能域
②控制转移必须遵守结构化设计要求
③易于确定局部数据和（或）全局数据的作用域
④易于表达嵌套关系和模块的层次结构
PAD（问题分析）图
5种控制结构
特征
①结构清晰，结构化程度高
②易于阅读
③最左端的纵线是程序主干线，对应程序的第一层结构 每增加一层PAD图向右扩展一条纵线，故 程序的纵线数等于程序层次数
④程序执行： 从PAD图最左主干线上端结点开始，自上而下、自左向右依次执行 程序终止于最左主干线
表格工具
判定表
语言工具
PDL（过程设计语言）
特征
①有为结构化构成元素、数据说明和模块化特征提供的关键词语法
②处理部分的描述采用自然语言语法
③可以说明简单和复杂的数据结构
④支持各种接口描述的子程序定义和调用技术
4.4 软件测试
4.4.1 软件测试的目的和定义
软件测试是一项验证和评估活动，其目的是基于满足规定的需求来保证软件的质量
软件测试的目的是为了发现错位而执行程序的过程
4.4.2 软件测试的准则
1、所有测试都应追溯到需求
2、严格执行测试计划，排除测试的随意性
3、充分注意测试中的群集现象
4、程序员应避免检查自己的程序
5、穷举测试不可能
6、妥善保存相关资料
4.4.3 软件测试方法与技术综述
分类
按是否需要执行被测软件
静态测试
代码检查
主要检查代码和设计的一致性
包括
代码审查
代码走查
桌面检查
静态分析
静态结构分析
代码质量度量
（不实际运行软件，主要由人工进行）
动态测试
是基于计算机的测试，是为了发现错误而执行程序的过程
测试用例的格式
[（输入值集），（输出值集）]
按功能
白盒测试
也称结构测试或逻辑驱动测试
在程序内部进行，主要用于完成软件内部操作的验证
基本原则
保证所测模块中每一独立路径至少执行一次
保证所测模块所有判断的每一分支至少执行一次
保证所测模块每一循环都在边界条件和一般条件下至少各执行一次
验证所有内部数据结构的有效性
是穷举路径测试
主要方法
逻辑覆盖测试
①语句覆盖
②基本路径覆盖
③判定覆盖
④条件覆盖
⑤判断-条件覆盖
基本路径测试
思想和步骤
根据软件过程性描述中的控制流程确定程序的环路复杂性度量， 用此度量定义基本路径集合，并由此导出一组测试用例对每一条独立执行路径进行测试
黑盒测试
也称功能测试或数据驱动测试
不考虑程序内部的逻辑结构和内部特性，是在软件接口处进行
主要诊断功能不对或遗漏、界面错误、数据结构或外部数据库访问错误、性能错误、初始化和终止条件错
主要测试方法
（1）等价类划分法
将程序的所有可能的输入数据划分成若干部分（等价类），然后从每个等价类中选取数据作为测试用
等价类
①有效等价类
合理有意义的输入数据构成的集合
可检验程序中符合规定的功能、性能
②无效等价类
不合理、无意义的输入数据构成的集合
可检验程序中不符合规定的功能、性能
实施步骤
1、划分等价类
2、根据等价类选取相应的测试用例
（2）边界值分析法
经验表明，程序错误最容易出现在输入或输出范围的边界上
（3）错误推测法
基本想法
列举出程序所有可能有的错误和容易发生错误的特殊情况。根据它们选择测试用例
4.4.4 软件测试的策略
软件测试一般步骤
1、单元测试
是对软件设计的最小单位——模块（程序单元）进行正确性检验的测试
测试内容
①模块接口测试
②局部数据结构测试
③重要的执行路径测试
④出错处理测试
⑤影响以上各点及其他相关点的边界条件测试
常用模拟环境测试
为被测模块设计和搭建驱动模块和桩模块
驱动模块相当于被测模块的主程序 它接收测试数据，并传给被测模块，输出实际测试结果
桩模块常用于代替被测模块调用的其他模块，仅做少量的数据操作，是一个模拟子程序，不必将子模块的所有功能带入
2、集成测试
把模块按照设计要求组装起来的同时进行测试， 目的是发现与接口有关的错误
组装方式
非增量方式组装
也称一次性组装方式，将所有软件单元一次组装在一起再测试
增量方式组装
将已经测试好的模块逐步组装成较大系统，边连接边测试
包括
（1）自顶向下的增量方式
将模块按系统程序结构，从主控模块（主程序）开始，沿控制层次自顶向下地逐个把模块连接起来 能较早地验证主要的控制点和判断点
（2）自底向上的增量方式
从软件结构中最底层的、最基本的软件单元开始集成和测试
（3）混合增量方式
在程序结构的高层使用自顶向下的增量方式，在低层使用自底向上的方式
依据是概要设计说明书
3、确认测试
首先运用黑盒测试方法
4、系统测试
在实际环境下进行测试
4.5 程序的调试
4.5.1 基本概念
程序调试的任务是诊断和改正程序中的错误
软件测试贯穿整个软件生命期，程序调试主要在开发阶段
1、程序调试的基本步骤
（1）错误定位
（2）修改设计和代码，以排除错误
（3）进行回归测试，防止引进新的错误
2、程序调试的原则
（1）确定错误的性质和位置时的注意事项
①分析思考与错误征兆有关的信息
②避开死胡同
③只把调试工具当做辅助手段来使用
④避免使用试探法，最多当做最后手段
（2）修改错误的原则
①在出现错误的地方，很可能还有别的错误
经验表明，错误有群集现象
②常见失误是只修改了错误的征兆或表现，而没有修改错误本身
③注意修正错误的同时可能会引入新的错误
④修改错误的过程将迫使人们暂时回到程序设计阶段
⑤修改源代码操作，不要改变目标代码
4.5.2 软件调试方法
1、强行排错法
2、回溯法
3、原因排除法
主要通过演绎和归纳
上面的每种方法都可使用调试工具来辅助完成
调试的成果是排错，为了修改程序中错误，常会采用“补丁程序”来实现
5、数据库设计基础
5.1 数据库系统的基本概念
5.1.1 数据、数据库、数据库管理系统
1、数据
数据实际上就是描述事物的符号记录
一般分为两部分
临时性数据
一般存放于内存中
持久性数据
数据库系统中处理的对象
结构
型
给出数据表示的类型
包括将多种相关数据以一定结构方式组合构成特定的数据框架（数据结构）， 数据库中在特定条件下称之为数据模式
值
给出符合给定型的值
在数据库系统及数据库应用系统中，数据占主体地位，而非程序
2、数据库
数据库（DB）是数据的集合
具有“集成”“共享”的特点
3、数据库管理系统
数据库管理系统（DBMS）是数据库的机构，是一种系统软件， 是数据库系统的核心
功能
①数据模式定义
②数据存取的物理构建
③数据操纵
④数据的完整性、安全性定义与检查（基本功能）
⑤数据库的并发控制与故障恢复
⑥数据的服务
数据语言
数据定义语言（DDL）
负责数据的模式定义与数据的物理存取构建
数据操纵语言（DML）
负责数据的操纵，包括查询以及增、删、改等操作
数据控制语言（DCL）
负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等功能
结构形式
交互式命令语言
宿主型语言
关系数据库普遍使用了结构化查询语言SQL，该语言是一种非过程性操作语言
4、数据库管理员（DBA）
主要工作
①数据库设计
②数据库维护
③改善系统性能，提高系统效率
5、数据库系统
数据库系统（DBS）的组成
DB
DBMS
DBA
系统平台之一——硬件平台
计算机（基础硬件平台）
网络
系统平台之二——软件平台
操作系统（基础软件平台）
数据库系统开发工具
接口软件
6、数据库应用系统（DBAS）
包括
DB
DBMS
DBA
硬件平台
软件平台
应用软件
由数据库系统所提供的的数据库管理系统（软件）及数据库系统开发工具书写而成
应用界面
不计DBA，将应用软件与应用界面记成应用系统
5.1.2 数据库系统的发展
发展阶段：人工管理阶段、文件系统阶段、数据库管理系统
1、文件系统阶段
提供了简单的数据共享和管理能力，是数据库系统的雏形
2、层次数据库与网状数据库系统阶段
从20世纪60年代末期起，真正的数据库系统——层次数据库与网状数据库开始发展
3、关系数据库系统阶段
工程数据库系统
数据库与工程领域的结合
图形数据库系统
数据库与图形应用的结合
统计数据库系统
数据库与图像应用的结合
知识库系统
数据库与人工智能应用领域的结合
分布式数据库系统
数据库与网络应用的结合
云计算技术的基础
并行数据库系统
数据库与多机并行应用的结合
面向对象数据库系统
数据库与面向对象方法的结合
5.1.3 数据库系统的基本特点
1、数据的集成性
2、数据的高共享性与低冗余性
3、数据独立性
（1）物理独立性
数据的物理结构的改变不影响数据库的逻辑结构，从而不致引起应用程序的变化
（2）逻辑独立性
数据库总体逻辑结构的改变不需要相应改变应用程序
4、数据统一管理与控制
①数据的完整性检查
②数据的安全性保护
③并发控制
5.1.4 数据库系统的内部结构体系
三级模式
（1）概念模式
抽象的描述，不涉及具体的硬件环境与平台，也与具体软件环境无关
以概念模式为框架的数据库称为概念数据库
（2）外模式
也称子模式或用户模式
是用户的数据视图，也是用户所见到的数据模式
以外模式为框架的数据库叫用户数据库
（3）内模式
又称物理模式
给出了数据库物理存储结构与物理存储方法
以内模式为框架的数据库叫物理数据库
二级映射
（1）概念模式到内模式的映射
一般由DBMS实现
（2）外模式到概念模式的映射
一般由DBMS实现
5.2 数据模型
5.2.1 数据模型的基本概念
现实世界
客观世界中的划定边界的一个部分环境
信息世界
通过抽象对现实世界进行数据库级上的刻画所构成的逻辑模型
计算机世界
在信息世界基础上致力于其在计算机物理结构上的描述，从而形成的物理模型
数据模型的内容
（1）数据结构
主要描述数据的类型、内容、性质以及数据间的联系等
是数据模型的基础，一般数据模型的分类均以数据结构的不同而分
（2）数据操作
主要描述在相应数据结构上的操作类型与操作方式
（3）数据约束
主要描述数据结构内数据间的语法、语义联系，它们之间的制约与依存关系以及数据动态变化的规则
按不同的应用层次分类
概念数据模型
简称概念模型，面向客观世界、面向用户的模型 与具体的数据管理系统无关，与具体的计算机平台无关 是整个数据模型的基础
如（扩充的）E-R模型、面向对象模型及谓词模型等
逻辑数据模型
又称数据模型，面向数据库系统的模型
如层次模型、关系模型、面向对象模型等
物理数据模型
又称物理模型，面向计算机物理表示的模型
5.2.2 E-R模型
1、E-R模型的基本概念
（1）实体
现实世界中的事物可以抽象称为实体，实体是概念世界中的基本单位 凡是有共性的实体可以组成一个集合称为实体集
（2）属性
属性刻画了实体的特征
每个属性可以有值，一个属性的取值范围称为值域或值集
（3）联系
现实世界中事物间的关联称为联系
一对一联系（1:1）
一对多（1：m）或多对一（m：1）联系
多对多（m：n）联系
2、E-R模型三个基本概念之间的连接关系
（1）实体集（联系）与属性间的连接关系
一个实体可以由若干个属性，实体以及它的所有属性构成了实体的一个完整描述
一个实体的所有属性取值组成了一个值集叫元组
在概念世界中，可以用元组表示实体，也可用它区别不同的实体
（2）实体（集）与联系
实体集间可以通过联系建立连接关系
3、E-R模型的图示法
（1）实体集表示法
矩形
（2）属性表示法
椭圆
（3）联系表示法
菱形
5.2.3 层次模型
基本结构是树结构
树结构的特性
①每棵树有且仅有一个无双亲结点，称为根
②树中除根外所有结点有且仅有一个双亲
支持的操作
查询、插入、删除和更新
5.2.4 网状模型
是个不加任何条件限制的无向图
在现实中，网状模型将通用的网络拓扑结构分为一些基本结构
一般将一个网络分为若干个二级树（只有两个层次的树）
基本结构简单二级树叫系， 系的基本数据单位是记录（相当于E-R模型中的实体（集）） 记录又可由若干数据项（相当于E-R中的属性）组成 系中有一个首记录（相当于简单二级树的根） 有若干成员记录（相当于简单二级树的叶）
5.2.5 关系模型
1、关系的数据结构
关系模型采用二维表来表示，简称表
二维表由表框架以及表的元组组成
表框架由n个命名的属性组成，n称为属性元数 表框架对应了关系的模式，即类型的概念
表框架中按行存放数据，每行数据称为元组 一个表框架可以存放m个元组，m称为表的基数
二维表的性质
①元组个数有限
②元组的唯一性
③元组的次序无关性
④元组分量的原子性
⑤属性名唯一性
⑥属性的次序无关性
⑦分量值域的同一性
满足以上7个性质的二维表称为关系
键（码）
在二维表中能唯一标识元组的最小属性集
二维表中可能有若干个键，它们称为该表的候选码或候选键
从所有候选键中选取一个作为用户使用的键称为主键（主码）
关系框架与关系元组构成了一个关系 一个语义相关的关系集合构成一个关系数据库 关系的框架称为关系模式，而语义相关的关系模式集合构成了关系数据库模式
关系子模式对应用户数据库称视图
2、关系操纵
（1）数据查询
可分解为一个关系内的属性指定、一个关系内的元组选择、两个关系的合并以及一个查询操作
（2）数据删除
可分解为一个关系内的元组选择与关系中元组删除
（3）数据插入
仅插入操作
（4）数据修改
可分解为删除需修改的元组与插入修改后的元组
3、关系中的数据约束
（1）实体完整性约束
（2）参照完整性约束
（3）用户定义的完整性约束
5.3 关系代数
1、关系模型的基本操作
①关系的属性指定
②关系的元组选择
③两个关系合并
④一个或多个关系的查询
⑤关系中元组的插入
⑥关系中元组的删除
2、关系模型的基本运算
（1）插入
（2）删除
（3）修改
（4）查询
①投影运算
选出列
符号p
②选择运算
选出行
符号s
③笛卡尔积运算
3、关系代数中的扩充运算
（1）交运算
（2）除运算
（3）连接与自然连接运算
自然连接的条件
两关系间有公共域
通过公共域的相等值进行连接
5.4 数据库设计与管理
5.4.1 数据库设计概述
基本任务
根据用户对象的信息需求、处理需求和数据库的支持环境设计出数据模式
方法
面向数据的方法
以信息需求为主，兼顾处理需求
面向过程的方法
以处理需求为主，兼顾信息需求
数据库设计目前一般采用生命周期法
需求分析阶段
概念设计阶段
逻辑设计阶段
物理设计阶段
编码阶段
测试阶段
运行阶段
进一步修改阶段
5.4.2 数据库设计的需求分析
调查的重点是“数据”和”处理“， 通过调查获得用户的要求为
信息需求
处理需求
安全性和完整性的要求
5.4.3 数据库概念设计
1、数据库概念设计概述
设计目的
分析数据间内在语义关联，在此基础上建立一个数据的抽象模型
设计方法
（1）集中式模式设计法
（2）视图集成设计法
主要得到E-R模型
2、数据库概念设计的过程
（1）选择局部应用
（2）视图设计
三种设计次序
自顶向下
从抽象级别高且普遍性强的对象开始逐步细化
自底向上
从具体的对象开始，逐步抽象、普遍化与一般化
由内向外
先从最基本与最明显的对象着手逐步扩充至非基本、不明显的其他对象
（3）视图集成
实质
将所有的局部视图统一与合并成一个完整的数据模式
最重要的工作
解决局部设计中的冲突
常见冲突
①命名冲突
②概念冲突
③域冲突
④约束冲突
集成过程
（1）消除冲突
（2）消除冗余
5.4.4 数据库的逻辑设计
1、从E-R图向关系模式转换
会遇到的转换问题
（1）命名与属性域的处理
（2）非原子属性处理
（3）联系的转换
2、逻辑模式规范化及调整、实现
（1）规范化
关系数据库设计的关键是关系数据库模式的设计， 必须在关系数据库规范化理论的指导下进行
对于关系模式
若其中的每个属性都已不能再分为简单项，则它属于第一范式模式（1NF） 若某个关系模式R为1NF，且R中每个非主属性完全依赖于R的某个候选键，则称其为2NF 若关系模式R为2NF，且每个非主属性都不传递依赖于R的候选键，则称R为3NF 若所有属性都不传递依赖于关系的任何候选键，则称为BCNF
（2）RDBMS
对逻辑模式进行调整以满足RDBMS的性能、存储空间等要求，同时对模式做适应RDBMS限制条件的修改，包括
调整性能以减少连接运算
调整关系大小，使每个关系数量保持在合理的水平，从而提高存取效率
尽量采用快照，将某时刻值固定，并定期更换
3、关系视图设计
又称为外模式设计
关系视图的作用
提供数据逻辑独立性
能适应用户对数据的不同需求
有一定数据保密功能
5.4.5 数据库的物理设计
主要目标
对数据库内部物理结构做调整并选择合理的存取路径，以提高数据库访问速度及有效利用存储空间
5.4.6 数据库管理
1、数据库的建立
数据模式建立
由DBA建立，DBA利用RDBMS中的DDL语言定义
数据加载
DBA可编制加载数据程序将外界数据加载至数据模式内
2、数据库的调整
调整关系模式与视图使之更能适应用户的需求
调整索引与集簇使数据库性能与效率更佳
调整分区、数据库缓冲区大小以及并发度使数据库物理性能更好
3、数据库的重组
指重新调整数据库存储空间
4、数据库安全性控制与完整性控制
5、数据库的故障校复
6、数据库监控
DBA要观察数据库动态变化和性能变化