软件技术基础复习重点.ppt

一 何谓信息 information 信息是对现实世界中存在的客观实体 现象 关系进行描述的数据 信息是消息 信息是知识 信息是经过加工后并对实体的行为产生影响的数据 数据 Data 是现实世界客观存在的实体或事物的属性值 表现为人们感官听到的事实和看到的景象 数据和信息的关系信息是有一定含义的数据 信息是经过加工 处理 后的数据 信息是对决策有价值的数据 信息的基本属性 事实性 等级性 可压缩性 可扩散性 可传输性 共享性 增值性与再生性 转换性 信息产品的三个层次 数据 数据采集 用于事物处理系统 信息 数据处理 用于管理信息系统 知识 信息融合 用于决策支持系统 信息技术 informationtechnology IT 主要由计算机硬件技术 计算机软件技术和通信技术三大部分组成 包含信息的产生 检测 变换 存储 传递 处理 显示 识别 提取 控制和利用等具体内容 第三节软件 Software 随着信息化 网络化和数字化时代的到来 社会对 软件 的需求激增 如今 世界发达国家都把软件列为国家发展的关键技术领域 美国国家关键技术委员会将软件列为六大关键技术之一 欧洲共同体将 软件和信息处理 列为关键技术 我国把信息产业放在优先发展的地位 看作是中国发展高新技术 赶超世界先进水平的一次千载难逢的机遇 硬件 hardware 泛指计算机的物理设备与外设 硬件系统 由运算器 控制器 存储器 输入设备 输出设备组成 其中 运算器和控制器合为中央处理器 简称CPU 只有硬件系统的计算机 为 裸机 可以狭义地将计算机系统定义为有硬件系统和软件系统两部分组成 一 软件与程序 软件 software 是指计算机程序 方法 规则的文档以及在计算机上运行它时必须数据的集合 程序与软件有联系也有区别 程序 program 为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合 是人们求解问题的逻辑思维活动的代码化描述 程序的要便于阅读 交流 1 按功能划分软件分类 软件 系统软件 应用软件 操作系统网络系统语言编译器工具软件 管理软件实时软件科学计算 数据处理嵌入式软件人工智能软件专用领域软件 四 计算机软件的发展 软件伴随计算机技术的发展经历了三个阶段 程序设计阶段软件设计阶段软件工程阶段 第四节计算机开发系统的发展 1 机器语言2 汇编语言3 高级语言4 面向对象的程序设计 算法和数据结构是程序的两个重要方面 这二者的有机结合就构成了程序 通常用执行算法时所占用的空间大小和消耗时间的多少作为衡量算法优劣的标准 即算法的分析主要包含时间和空间两个方面 称为时间复杂度和空间复杂度 用数学符号 O 表示复杂度的数量级例如 O 1 常量级O n O n2 O nk 多项式级O log2n O nlog2n 对数级O 2n O en 指数级 第一节算法分析 用数学符号 O 表示复杂度的数量级例如 O 1 常量级O n O n2 O nk 多项式级O log2n O nlog2n 对数级O 2n O en 指数级 1 时间复杂度 算法中某一具体语句在算法的运行过程中执行的次数即为该语句的频度 记做F n 时间复杂度是以算法中频度最大的语句来度量的 可记做T n O F n for k 0 k n k for j 0 j n j for i 0 i n i a i 1 时间复杂度为O n3 2 空间复杂度 实现算法可能需占用的存储空间一般有 1 指令 常数和系统变量所占用的存储空间 2 数据所占用的存储空间 3 算法执行过程中所需的辅助空间 算法的空间复杂度分析 是指对该算法在执行过程中所需辅助空间大小的分析 空间复杂度也用O n 表示 常见的空间复杂度有 O 1 O n O n2 O n3 上例为i j k与n无关 空间复杂度为O 1 3 算法的特性与描述 1 算法特性算法是对特定问题的求解步骤的一种描述 是指令的有限序列 作为算法 有以下几个基本特性 1 有穷性 每条指令执行的次数与时间都是有限的 必须在若干步之后终止 2 确定性 每条指令的含义明确 不能存在二义 即在相同条件下的结果唯一 3 可行性 算法所描述的操作可以通过有限的基本操作实现 4 输入 算法应当有0个或多个输入 5 输出 算法也应当有1个或多个输出 算法还应具有如下性能指标 1 正确性2 可读性3 健壮性4 高效性 第二节程序设计基础 迭代法递推法递归法穷举法分治法贪心法回溯法 迭代法一般用于求方程的近似根的算法设计 例如 对于方程f x 0 通过相应的数学推导可以得到x g x 则其求根过程为 1 将方程的任意一个近似根赋给变量x0 2 将x0的值保存于变量x1 然后计算g x1 并将结果存于变量x0 3 当x0与x1的差的绝对值还小于指定的精度 E 要求时 重复第2步 如若方程有根且用上述方法计算出来的近似根序列收敛 则按上述方法求得的x0就是方程的根 1 迭代法 若一个对象部分地由自己组成或按自己定义 则可称之为递归的 在递归的定义中至少要有一条是非递归的 做为递归的终止条件 即边界条件 采用递归方法来解决问题的三个条件 1 可把一个问题转化为一个新的问题 而这个新问题的解决方法仍与原问题的解法相同 2 可通过转化过程使问题得到解决 3 必定要有一个明确的结束递归的条件 否则递归将回无止境地进行下去 3 递归法 递归算法的执行过程分递推和回归两阶段 在递推阶段 把较复杂的问题 规模为n 的求解推到比原问题简单一些的问题 规模小于n 的求解 在回归阶段 当获得最简单情况的解后 逐级返回 依次得到稍复杂问题的解 编写递归函数时要注意 函数中的局部变量和参数知识局限于当前调用层 当递推进入 简单问题 层时 原来层次上的参数和局部变量便被隐蔽起来 在各个层中 各有自己的参数和局部变量 堆栈 穷举法也称枚举法 顺序列举 排列列举 组合列举 程序 数据结构 算法 通过上述例子可以看出 描述这类非数值计算问题的数学模型不再是数学方程 而是诸如表 树和图之类的数据结构 数据结构定义 数据结构是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间关系和操作的学科 通过计算机解决问题 可以通过分析数学方程式来建立数学模型 并以之为加工对象的程序设计 这种程序设计的方式为数值分析型程序设计 总 数据 data 是信息的载体 是可以用计算机表示并加工的各种 符号 的集合 数据元素 dataelement 是数据的基本单位 是数据集合中的一个个体 亦称节点 node 或记录 record 数据项 dataitem 有独立含义的数据最小单位 也称域 field 数据对象 dataobject 有相同性质的数据元素的集合 2 数据结构的基本概念和术语 数据结构 datastructure 数据元素和数据元素关系的集合 是指同一数据对象中个数据元素间存在的关系 数据结构的定义常采用集合论的方式 表示为 S D R 其中 数据结构S是一个二元组D是一个数据元素的非空有限集合R是定义在D上的关系的非空有限集合 1 数据的逻辑结构 是指数据元素及其关系的数学特性 反映数据之间的逻辑关系 三种基本结构 线性结构 数据元素存在着线性 一对一 的关系 树形结构 数据元素存在着层次 一对多 的关系 图形结构 数据元素存在着任意 多对多 的关系 2 数据的存储结构 数据在计算机内部的存储方式 3 数据的操作 数据的操作即是对数据进行的处理 3 数据结构研究的主要问题 1 数据的逻辑结构2 数据的存储结构3 数据的运算 检索 排序 插入 删除 修改等 A 线性结构B 非线性结构 A 顺序存储B 链式存储 线性表栈队列 树形结构图形结构 数据元素在计算机内部的组织方式 4 数据结构的三个方面 反映数据元素之间的逻辑关系 数据结构是一门研究数据组织 存储和运算的一般方法的学科 在数据处理的过程中 大量的数据都是以表格的形式出现的 这种表格称为线性表 它是数据元素的有限序列 线性表是一种最简单 最常见的数据结构 线性表的主要运算有插入 删除 查找和排序 线性表的常用存储结构有 向量 链表 第二节线性表 LinearList 线性结构特点 对于数据元素的线性非空有限集合存在唯一的一个被称作 第一个 的数据元素 存在唯一的一个被称作 最后一个 的数据元素 除第一个外 集合中每个数据元素均只有一个前驱 除最后一个外 集合中每个数据元素均只有一个后继 线性表上常用的运算有 初始化 求长度 取元素 定位 插入及删除等 线性表中的数据元素是各种各样的 同一线性表中的元素必定具有相同的特性 即属于同一数据对象 相邻数据元素之间存在着序列关系 二 线性表的特点与基本运算 线性表中的数据元素是各种各样的 同一线性表中的元素必定具有相同的特性 即属于同一数据对象 相邻数据元素之间存在着序列关系 线性表的存储结构采用顺序存储结构 称之为顺序表 亦为向量 采用链式存储结构 称之为链表 四 线性表的存储结构及其运算 在线性表的第i个元素之后插入一个新的元素x 先移动 后插入 x x 4 顺序表插入运算过程 线性表链式存储结构的描述在高级语言中 链式存储结构用 结构指针 来描述 对于有些没有结构指针的高级语言 也就没有相应的链式结构了 structLNode intdata structLNode link struct h p 结点中只含一个指针域的链表叫单链表 p 表示指针变量p所指向的结点 p data p data表示p指向结点的数据域 p link p link表示p指向结点的指针域 生成一个structLNode型新结点 p structLNode malloc sizeof structLNode 系统回收p结点 free p 1 线性表链式存储结构的描述 2 线性链表的基本运算 设p q s均为structLNode变量 常用的几种基本运算是 A 指针赋值s p q p link B 指针移动p p link C 在某点后插入s link p link p link s head E 删除某结点if p link NULL q p link p link q link free q 删除p的后继结点 D 在某点前插入q head while q link p q q link q link s s link p 3 顺序表和链表的比较 二者各有优 缺点 可从以下三方面比较 1 线性表的长度 顺序表的存储空间是静态分配的 故其上 下界是固定的 若执行过程中表长需要发生变化 插入 删除 就要留足空间 从而产生浪费 又可能因为不足而使表产生溢出 在表长经常发生变化时 采用链表很方便 2 线性表的主要操作 顺序表连续存放 可随机存取表中任何记录 适于频繁的查找操作的表 但是进行插入 删除 移动时 就很不方便 链表进行查找时 只能顺序从首指针起 比较浪费时间 但是插入 删除运算时 只需要较小的时间就可完成 但是其每一数据元素 多一指针域 浪费存储空间 3 高级语言实现 有些高级语言不支持指针 自然只能采用顺序表 1 定义 限定只能在表的一端进行插入和删除运算的特殊的线性表 其集合论的定义方法与线性表相同 特点 后进先出 LIFO 先进后出 FILO 设有栈表示为 s a1 a2 ai an 其中a1是栈底元素 an是栈顶元素 其原理示意图为 栈顶 top 允许插入和删除的一端 栈底 bottom 不允许插入和删除的一端 n 0时 为空栈 栈的存储结构可采用顺序结构 链式结构 一 堆栈 Stack 2 链栈用指针来实现的栈叫链栈 栈的容量事先不能估计时采用的存储结构 链栈的类型说明如下 structlnode intdata structlnode link 2 链栈 intlpush structlnode s inte structlnode pp structlnode malloc sizeof structlnode p data e p link s s p return 1 例1 链栈的进栈操作 e intlpop structlnode s int pe if s NULL return 0 pe s data s s link return 1 例2 链栈的出栈操作 运算符 优先级43322110 3 表达式的求值 思想 从左到右扫描表达式 若当前读入的是操作数 则进操作数 NS 栈 若读入的符号是运算符 应进行判断 若是 进运算符栈 若是 当运算符栈顶是 则弹出栈顶元素 继续扫描下一符号 2 若读入的运算符的优先级大于运算符栈顶的优先级 则进运算符栈 继续扫描下一符号 否则从操作数栈顶弹出两个操作数 从运算符栈弹出一个运算符 生成运算指令 把结果送入操作数栈 继续处理刚才读入的符号 3 若读入的是 且运算符栈顶的符号也是 时 则表达式处理结束 从操作数栈弹出表达式结果 以表达式 A B C D 为例说明利用栈的求值过程如下 二 队列 queue 1 定义 一种特殊的线性结构 限定只能在表的一端进行插入 在表的另一端进行删除的线性表 特点 此种结构称为先进先出 FIFO 表 常用运算 1 设置一个空队列 2 插入一个新的队尾元素 称为进队 3 删除队头元素 称为出队 4 读取队头元素 将头尾连接成一个环 形成的队列就是循环队列 让sq 0 接在sq M 1 之后 若rear 1 M 则令rear 0 实现方法 利用 模 运算 入队 rear rear 1 M sq rear x 出队 front front 1 M x sq front B循环队列 intEnQueue intQ intx int pf int pr intfront rear front pf rear pr if rear 1 MAX front return 0 else rear rear 1 MAX Q rear x pr rear return 1 计算出新的队尾 a 循环队列的入队算法 intDeQueue intQ int py int pf int pr intfront rear front pf rear pr if rear front return 0 else front front 1 MAX py Q front pf front return 1 b 循环队列的出队算法 ai ai1 ai2 ain 1 i n 数组中每一行是一个线性表 数组中每一列也是一个线性表 由于数组是线性表的推广 可用线性表的一般形式定义二维数组为 B K R 其中 K Kij 1 i m 1 j n R由以下两种关系组成 ROW Kij Kij 1 1 i m 1 j n 1 COL Kij K1 ij 1 i m 1 1 j n 数组特点 结构固定 元素同构 数组运算 给定一组下标 存取相应的数据元素 给定一组下标 修改数据元素的值 一 数组的定义 3 特殊矩阵的压缩存储 特殊矩阵 值相同元素或非零元素的分布具有一定规律 1 下三角阵 按行优先存放 a11 a21 a22 a31 a32 an1 an2 ann Loc aij Loc a11 i i 1 2 j 1 S Loc aij Loc a11 i 1 n j 1 S 1 按行优先顺序存放 先排右下标 后排左下标 即以左下标为主序存放 Loc aij Loc a11 j 1 m i 1 S 2 按列优先顺序存放 先排左下标 后排右下标 即以右下标为主序存放 3 特殊矩阵的压缩存储 特殊矩阵 值相同元素或非零元素的分布具有一定规律 1 下三角阵 按行优先存放 a11 a21 a22 a31 a32 an1 an2 ann Loc aij Loc a11 i i 1 2 j 1 S 按行优先存放 a11 a12 a21 a22 a23 a32 a34 an n 1 ann Loc aij Loc a11 2 i 1 j 1 4 三对角阵 三 稀疏矩阵 矩阵的压缩存储 矩阵在科学运算中十分广泛 且随计算机应用的发展 出现了大量的高介矩阵 这些矩阵中的绝大部分元素往往为零值 定义 非零元较零元少 且分布没有一定规律的矩阵 压缩存储原则 只存矩阵的行列维数和每个非零元的行列下标及其值 顺序存储结构三元组稀疏矩阵的转置运算 2 带辅助向量的三元组表示 为了便于通过三元组法访问稀疏矩阵中的元素 通常附设两个向量POS和NUM 称为行辅助向量 它们满足 POS 1 1POS i POS i 1 NUM i 1 2 i m其中 POS i 表示稀疏矩阵中第i行的第一个非零元素在三元组中的行号 NUM i 表示稀疏矩阵中第i行的非零元素的个数 3 伪地址表示法 伪地址表示法是通过本元素在矩阵中 含0元素 按行优先顺序的相对位置 在上例中 M中非0元素的伪地址为 1 5 8 11 12 24 伪地址表中每个节点含两个字段 一个是伪地址 另一个是元素值 该方法节省空间 但是在运算过程中要计算伪地址 浪费时间 1 带行指针向量的单链表 设置一个行指针向量 向量中每个元素为一个指针 指向本行矩阵的第一个非0元素节点 若本行无非0元素 则指针为空 矩阵中每一个非0元素由三个数据域 列 元素值以及指向本行下一个非0结点的指针 同一行的非0元素构成一个单链表 定义 树是由n个 n 0 结点组成的有限集合T 其中有且仅有一个结点为根结点 root A 其余结点可分为m m 0 个互不相交的有限集合T1 T2 Tm 其中的每一个集合Ti本身又是一棵树 称为根结点root的子树 n 0时 树为空树 特点 树中至少有一个结点 根 树中各子树是互不相交的集合 一 树的定义 一 树的定义 结点 Node 树中的元素 含数据项及若干指向其子树的指针 结点的度 Degree 结点拥有的子树数 树中最大结点的度数称为树的度数 结点的层次 Level 从根结点开始算起 根为第一层 叶子 Leaf 度为零的结点 也称端结点 孩子 Child 结点子树的根称为该结点的孩子结点 兄弟 Sibling 同一双亲的孩子 双亲 Parent 孩子结点的上层结点 深度 Depth 树中结点的最大层次数 森林 Forest M棵互不相交的树的集合 有序树 树中结点在同层中按从左到右有序排列 不能互换的称为有序树 反之 称为无序树 1 树的常用术语 一棵n个结点的k叉树 有nk个指针域 有用的指针域为n 1个 空链域为nk n 1 个 2 树的存储 1 结点异构型 根据每个结点的子树数设置相应的指针域 由于树中每个结点的度不尽相同 同一棵树中各结点的结构形式也不同 节约空间 运算不便 2 结点同构型 每个结点的指针域数目均为树的度数 运算方便 浪费空间 比较不同的k值 二 二叉树 BinaryTree 二叉树的五种基本形态 定义 二叉树是n n 0 个结点的有限集 它或为空树 n 0 或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成 特点 1 每个结点至多有二棵子树 即不存在度大于2的结点 2 二叉树的子树有左 右之分 且其次序不能任意颠倒 1 二叉树的第i层上至多有2i 1 i 1 个结点 2 深度为h的二叉树中至多含有2h 1个结点 3 若在任意一棵二叉树中 有n0个叶子结点 有n2个度为2的结点 则 n0 n2 1 1 二叉树的基本性质 2 完全二叉树特点 指深度为k的 有n个结点的 且每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应 完全一致 则为完全二叉树 1 满二叉树特点 深度为h且含有2h 1个结点的二叉树 为满二叉树 图示满二叉树 结点编号为自上而下 自左而右 2 特殊形式的二叉树 3 平衡二叉树特点 又称AVL树 它或为一棵空树 或具如下性质 其左子树和右子树都是平衡二叉树 且左 右子树的深度之差的绝对值不超过1 左 右子树的深度之差为平衡因子 平衡二叉树的平衡因子只能为0 1 1 由于二叉树常常用二叉链表表示 为了使一般树也能用二叉链表表示 必须找出树与二叉树之间的关系 为此 给定一棵树 可以找到唯一的一棵二叉树与之对应 1 普通树转换为二叉树的方法 对每个孩子进行自左至右的排序 在兄弟之间加一条连线 对每个结点 除了左孩子外 去除其与其余孩子之间的联系 以根结点为轴心 将整个树顺时针转45度 4 一般树转换为二叉树 1 树转换为二叉树 T 16 若父结点在数组中i下标处 其左孩子在2 i处 右孩子在2 i 1处 2h 1 24 1 15 1 顺序存储结构用一组连续的存储单元存放二叉树的数据元素 结点在数组中的相对位置蕴含着结点之间的关系 5 二叉树的存储结构 顺序和链式存储结构 1 遍历定义遍历是指按某条搜索路线依次寻访树中每个结点 每个结点被访问且只被访问一次 对二叉树的遍历 总共有六种方式 按先左后右的原则 一般使用三种遍历 先序遍历 DLR 访问根结点 按先序遍历左子树 按先序遍历右子树 中序遍历 LDR 按中序遍历左子树 访问根结点 按中序遍历右子树 后序遍历 LRD 按后序遍历左子树 按后序遍历右子树 访问根结点 二叉树为空时 执行空操作 即空二叉树已遍历完 三 二叉树的遍历 traversing 先序遍历 DLR中序遍历 LDR后序遍历 LRD DLR ABDC BDAC DBCA 2遍历算法 voidPre structTreeNode T if T NULL printf T data Pre T lchild Pre T rchild 先序遍历 3 由遍历序列恢复二叉树 DLR是先访问根结点 再按DLR方式遍历根结点的左子树 后按DLR方式遍历根结点的右子树 即 在DLR序列中 第一个结点一定是二叉树的根结点 LDR是先用LDR方式遍历左子树 再访问根结点 后用LDR方式遍历右子树 因此 根结点在LDR序列中必将之分割成两个子序列 前一个子序列是根结点的左子树的中序序列 而后一个子序列是根结点的右子树的LDR序列 据这两个子序列 可在DLR序列中找到对应的左子序列和右子序列 在DLR序列中 左子序列的第一个结点是左子树的根结点 右子序列的第一个结点是右子树的根结点 上述过程 就可以确定二叉树的三个结点 同时 左子树和右子树的根结点又可以分别把左子序列和右子序列划分成两个子序列 如此递归 便可得到一棵二叉树 同理 若已知结点的后序 中序序列 就可以唯一地确定一棵二叉树 已知 DLRABCDEFGHILDRBCAEDGHFI 3 由遍历序列恢复二叉树 同理 若已知结点的后序 中序序列 就可以唯一地确定一棵二叉树 已知 DLRABCDEFGHILDRBCAEDGHFI 四 哈夫曼树及其应用 WPL 例1 有4个结点 权值分别为7 5 2 4 构造有4个叶子结点的二叉树 例 给定权值 7 5 2 4 构造哈夫曼树 1 根据给的n个权值 w1 w2 wn 构造n棵二叉树的集合F T1 T2 Tn 每棵二叉树仅有一个带权为wi的根结点 2 在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新的二叉树 其根结点的权值为左右子树根结点权值之和 且规定左子树根结点的权值小于右子树根结点的权值 3 将新的二叉树加入到森林F中 去除原两棵权值最小的树 4 重复2 3步骤 直至F中只剩一棵树为止 2 哈夫曼树的构造过程 方法 1 用 2 4 2 3 3 作为叶子结点的权值生成一棵哈夫曼树 并将对应权值wi的叶子结点注明对应的字符 2 约定左分支表示字符 0 右分支表示字符 1 3 从叶子结点开始 顺着双亲反推上去 直到根结点 路径上的 0 或 1 连接的序列就是结点对应的字符的二进制编码的逆序 各字符编码是T ACS000110110111上述电文编码 11010111011101000011111000011000 哈夫曼编码 利用哈夫曼树构造通讯中的电文编码 前缀码 例 要传输的电文是 CAS CAT SAT AT 要传输的字符集是 D C A S T 字符出现的频率分别是W 2 4 2 3 3 4 哈夫曼编码 各字符编码是T ACS000110110111上述电文编码 11010111011101000011111000011000 4 哈夫曼编码 图 Graph 图G是由两个集合V G 和E G 组成的 记为G V E 其中 V G 是顶点的非空有限集 E G 是边的有限集合 边是顶点的无序对或有序对 有向图 有向图G是由两个集合V G 和E G 组成的 其中 V G 是顶点的非空有限集 E G 是有向边 也称弧 的有限集合 弧是顶点的有序对 记为 v w是顶点 v为弧尾 w为弧头 v w w v 无向图 无向图G是由两个集合V G 和E G 组成的 其中 V G 是顶点的非空有限集 E G 是边的有限集合 边是顶点的无序对 记为 v w 或 w v 并且 v w w v 一 图的基本概念 有向图 Digraph G1 G V E 顶点集合V V1 V2 V3 V4 弧的集合E 无向图 Undigraph G2 顶点集合V V1 V2 V3 V4 边的集合E V1 V3 V1 V2 V1 V4 V2 V4 顶点 V1 V3 与 V1 V3 表示同一条边 权 与图的边或弧相关的数叫权 Weight 可以表示从一个顶点到另一个顶点的距离或耗费 带权的图叫网 子图 图G V E 和图G V E 若V V E E 则称G 为G的子图 顶点的度 无向图中 顶点的度为与每个顶点相连的边的数目 有向图中 顶点的度分成入度与出度 入度 以该顶点为头的弧的数目 出度 以该顶点为尾的弧的数目 二 图的相关术语 路径 路径是顶点的序列V Vi0 Vi1 Vin 满足 Vij 1 Vij E或 E 1 j n 路径上的边或弧的数目 称为该路径的长度 网络的路径长度定义为路径上权值之和 简单路径 除第一个和最后一个顶点外 序列中其余顶点各不相同的的路径为简单路径 第一个与最后一个顶点相同的简单路径为回路 连通图 在无向图中 若从Vi到Vj存在路径 则称Vi到Vj是连通的 若在顶点集合V中每一对不同的顶点Vi到Vj都连同 则称G为连通图 强连通图 对于有向图 若从顶点Vi到Vj和从Vj到Vi之间都有路径 则称这两个顶点是强连通的 对于有向图中任何一对顶点都是强连通 则此图为强连通图 V1V2V3V4V10111V21001V31000V41100 特点 由上述可知 无向图或网络的邻接矩阵是对称的 并且 该法比较简单 用一个二维数组就可存储 缺点 浪费空间 可用处理 稀疏 矩阵的方式去处理 邻接表是图的一种链式存储结构 在邻接表中 对图中的每个结点建立一个单链表 第i个单链表中的结点表示依附于顶点Vi的边 有向图中指以Vi为尾的弧 在边少的情况下 用邻接表比邻接矩阵节省存储空间 2 邻接表 V1 V2 V4 V8 V5 V3 V6 V7 V1 V2 V4 V8 V3 V6 V7 V5 三 图的遍历 从图中某一顶点出发 访遍图中其余顶点 且使每个顶点仅被访问且仅被访问一次 1 深度优先遍历 DFS 从图的某一顶点V0出发 访问此顶点 然后依次从V0的未被访问的邻接点出发 深度优先遍历图 直至图中所有和V0相通的顶点都被访问到 若此时图中尚有顶点未被访问 则另选图中一个未被访问的顶点作起点 重复上述过程 直至图中所有顶点都被访问为止 2 广度优先遍历 BFS 从图的某一顶点V0出发 访问此顶点后 依次访问V0的各个未曾访问过的邻接点 然后分别从这些邻接点出发 广度优先遍历图 直至图中所有已被访问的顶点的邻接点都被访问到 若此时图中尚有顶点未被访问 则另选图中一个未被访问的顶点作起点 重复上述过程 直至图中所有顶点都被访问为止 V1 V2 V3 V4 V5 V6 V7 V8 V1 V2 V3 V4 V6 V7 V8 V5 迪克思特拉算法 Dijkstra 1 设A 1 n 1 n 为有向图的带权邻接矩阵 A i j 表示弧 Vi Vj 上的权值 若 Vi Vj 不存在 则A i j 为无穷大 S为已找到从源点V0出发的最短路径的终点集合 初始状态为 V0 DIST 1 n 为个终点当前找到的最短路径长度 初始值为DIST i A V0 i 算法描述 2 选择u 使DIST u min DIST w w S w V S S u 其中 V为有向图的顶点集合 3 对于所有不在S中终点w 若DIST u A u w DIST w 则修改DIST w 为DIST w DIST u A u w 4 重复操作2 3 共n 1次 由此可求得从V0到各终点的最短路径 弗洛伊德算法思想 逐步试着在原直接路径中考虑其它顶点作为中间点 如增加中间点后得到的路径较原路径长度减小 则以此新路径长度代替原值而修改矩阵元素 若增加中间点后的路径比原路径更长 就维持原相应的矩阵元素值不变 1 初始状态 第一节查找 查找 也叫检索 是根据给定的某个值 在表中确定一个关键字等于给定值的记录或数据元素 不同的数据结构采用不同的查找方法 查找的效率直接影响数据处理的效率 关键字 是数据元素中某个数据项的值 它可以标识一个数据元素 查找方法评价 查找速度 占用存储空间多少 算法本身复杂程度 平均查找长度ASL AverageSearchLength 为确定记录在表中的位置 需和给定值进行比较的关键字的个数的数学期望值叫查找算法的平均查找长度 查找的结果 查找成功 则返回找到满足条件的结点 查找失败 则返回找不到满足条件的结点的信息 intSearch Seq structSTableST intn intKey inti n ST 0 key Key while ST i key Key i 从表尾往前查 return i 监视哨 使用了监视哨 在查找过程中 不用每一步都去判断是否查找结束 找到 返回元素在线性表中的存储位置 未找到 返回0 顺序查找的算法 基本思想 对有序文件 进行查找 先找 中间记录 进行比较 根据不同情况 逐步缩小范围 直到找到或确认找不到该记录为止 适用条件 必须在具有顺序存储结构的有序表中进行 算法实现 设表长为n low high和mid分别指向待查元素所在区间的上界 下界和中点 k为给定值 初始时 令low 1 high n mid low high 2 让k与mid指向的记录比较 若k r mid key 找成功 若kr mid key 则low mid 1 重复上述操作 直至low high时 查找失败 二 对分查找 折半查找 二分法查找 查找23和79的过程如下图 mid low high 2 08 14 23 37 46 55 68 79 91 08 14 23 37 46 55 68 79 91 08 14 23 37 46 55 68 79 91 08 14 23 37 46 55 68 79 91 08 14 23 37 46 55 68 79 91 08 14 23 37 46 55 68 79 91 查找方法比较 四 二叉排序树查找 1 若它的左子树不空 则左子树上所有结点的值均小于根结点的值 1 定义 二叉排序树或者是一棵空树 或者是具有如下特性的二叉树 3 它的左 右子树也都分别是二叉排序树 2 若它的右子树不空 则右子树上所有结点的值均大于根结点的值 3 二叉排序树的生成 对于任意的一组数据元素序列 R1 R2 Rn 生成二叉排序树的过程如下 1 令R1为二叉排序树的根结点 2 若R2 R1 令R2为R1的左子树的根结点 否则 R2为R1的右子树的根结点 3 R2 Rn结点插入方法同上 序列 10 18 3 8 12 2 7 1 构成一棵二叉排序树的过程 4 删除二叉排序树上的结点 上述查找过程可见 在查找过程中 生成了一条查找路径 从根结点出发 沿 动态查找 就是在查找失败时进行 插入 操作 将要查找的关键字插入到结构中 若二叉排序树为空树 则新插入的结点为新的根结点 否则 新插入的结点必为一个新的叶子结点 其插入位置由查找过程得到 二叉排序树在生成 插入 过程中 若其形态始终保持 匀称 亦接近平衡二叉树 则平均查找长度就小 反之 平均查找长度就长 二叉排序树的平均查找长度介于对分查找与线性查找之间 ASL 1 2 2 3 4 4 8 2 6 ASL 1 2 2 3 4 5 2 6 8 3 5 哈希函数 在记录的关键字与记录的存储地址之间建立的一种对应关系 是可以根据关键字的值而直接计算出元素所在位置的函数 可表示H KEY 哈希表 哈希表是一种存储结构 是能用散列技术进行查找的表 也叫散列存储 通过哈希函数和解决冲突的办法把键值存放在哈希表中 采用哈希技术主要目标是提高查找效率 要求缩短查表和填表的时间 哈希查找 又叫散列查找 利用哈希函数进行查找的过程 冲突 两个不同的关键字K1和K2计算出相同的存储位置的现象称为冲突 K1和K2互为同义词 1 哈希函数 哈希表的基本概念 1 直接定址法 H K K或H K A K B 其中A B为常数 取关键字或关键字的某个线性函数值为散列地址 例 某公司一险种投保费交纳表 20年 将年份作关键字 哈希函数取关键字本身 若查找第3年应交纳的保费 只要查找表的第3项即可 2 哈希函数的构造方法 2 数字分析法 该法适用于较大的静态数据 在已知所有关键字键值的情况下 分析每一位的数字分布是否均匀 删除不均匀分配的数字位 根据存储空间的大小来确定所取地址的位数 542422241542813678542228171542389671542541577542886376542193552 422836281396515853135 存储空间从0 1000 3 平方取中法 若一组关键字的值在每一位上对某些数字的重复频度都很高 就不宜采用数字分析法 取关键字平方后的中间几位为哈希函数 H Key Key2 anan 1 a2a1 0100 1100 1200 1160 2060 2061 2163 2261 2262 设存储空间0 1000 平方后 取2 3 4位构成哈希地址如下 010 210 440 345 243 247 678 112 116 4 除留余数法 取关键字被不大于散列表表长m的数p除后所得的余数为哈希函数 即H K KMODp p m p一般选取小于等于表长的质数 H K KMODp C p m C的作用可以调节最终的地址范围 为小于表长的某一整型常数 5 折叠法 将关键字的值分为几段 尔后叠加求和 A 移位折叠 将各段左对齐后相加 B 边界折叠 将奇数段 偶数段倒排后相加 排序中的关键字可是主关键字也可是次关键字 若是主关键字则排序结果唯一 若是次关键字则结果不唯一 因为在带排序列中可能存在次关键字相同的记录 若Ki Kj 在排序前Ri领先于Rj 排序后顺序不变 则称该方法是稳定的 反之 是不稳定的 若待排序记录在排序过程中全部是存放在内存里的 则称该排序为内排序 若待排序记录非常多 许借助外存来辅助存储待排序记录 则称该排序为外排序 排序功能 将一个数据元素的任意序列 重新排成一个按关键字有序的序列 其过程分两步 首先比较两个关键字的大小 然后将记录从一个位置移动到另一个位置 典型的排序方法有 插入排序选择排序交换排序快速排序归并排序 堆排序是一种选择排序 堆是具有特定条件的顺序存储的完全二叉树 其特定条件是 任何一个非叶子结点的关键字大于等于 或小于等于 子女的关键字的值 2 堆排序 把自堆顶至叶子的调整过程称为 筛选 从一个无序序列建堆的过程就是一个反复 筛选 的过程 方法与构造堆类似 2 输出堆顶元素并调整建新堆的过程 筛选 3 由无序建初始堆的过程 25 56 49 78 11 65 41 36 基本思想 对待排序记录的关键字进行两两比较 若出现不满足顺序的一对记录 则交换之 直到全部记录均满足排序要求为止 有冒泡和快速排序两种 三 交换排序 五 内部排序方法的分析与选择 操作系统操作系统就是能有效地管理计算机系统中的各种软 硬件资源 合理地组织计算机的工作流程 为用户创造良好工作环境的系统软件 操作系统是与裸机最接近的软件层 操作系统的功能 1 处理机管理2 存储管理3 设备管理4 文件管理 操作系统的主要设计目标方便用户使用扩大机器功能提高系统效率构筑开放环境 第二节处理器管理 处理器管理就是要解决用户提交的作业何时调入内存 在调入内存的各个作业程序间如何分配处理器 以达到各到程序能协调一致地运行 而系统资源又能得到最大程度的利用 1 进程概念的引入多道程序系统中程序并发性执行 为了竞争有限的资源 相互间存在依赖与制约的关系 因此他们在系统中的状态是不断变化的 即时而运行 时而停顿 程序执行时所产生的问题使得传统的程序概念已经不足以对其进行描述 为之引入进程 Process 一 基本概念和术语 2 进程的定义进程是一种活动 它由一个动作系列组成 每个动作是在某个数据集上执行一段程序 整个活动的结果是提供一种系统或用户功能 一旦操作系统接受了某用户的作业 并把他调入内存执行 系统就为此作业创建一个或多个进程 因此进程可看作是程序的一次执行 即在指定内存区域中的一组指令序列的执行过程 多个进程可并发运行 并可能由各种原因随时中断 4 进程的主要特征1 动态性 执行初期被创建 执行结束被撤消 2 并发性 并发执行提高了计算机的系统资源的利用率 3 独立性 进程是一个能够独立运行的基本单位 4 异步性 进程相互制约 其执行具有间断性 5 作业 作业步作业是用户在一次算题过程中或一个事物处理中要求计算机系统所做的工作的集合 一个作业由一系列有序的作业步组成 一个作业步运行的结果产生下一个作业步所需的文件 作业的四种状态 提交 后备 执行 完成 这是作业从进入系统到运行结束要经历的四种状态 2 作业状态及转换示意图 状态转换图 1 进程的状态及其变化就绪 这类进程已经具备各种必须的资源 只等待获得CPU 运行 系统根据某种调度算法 将CPU分配给某一个就绪进程使之运行 该进程就处于运行态 阻塞 进程在运行中由要等待I O设备或发生其他错误时 就转入阻塞状态 当阻塞原因消除后 重新回到就绪态 三 进程状态及进程控制块 1 进程控制 管理 任务1 进程的建立 2 进程的撤消 3 进程的阻塞 4 进程的唤醒 实现进程的管理使用原语 primitive 原语是机器指令的延伸 由若干条机器指令构成 用以完成某一特定功能的程序段 又称为广义指令 原语在执行期间是不可分割的 四 进程控制 1 同步与互斥的概念同步 一组合作进程在运行中 由于是异步的 进程之间要协调其推进的速度 以正确完成作业运行 互斥 对于某一临界资源 一组进程不能同时进入临界区去使用它 一个进入 其他必须等待 临界资源 一次仅允许一个进程使用的资源 如打印机 读卡机 缓冲区 变量等 临界区 进程中使用临界资源的那段程序 各进程之间存在着相互制约 相互依赖的关系 六 并发程序设计中的问题 进程的同步与互斥 解决同步与互斥的方法有很多 可以用硬件实现 也可以用软件实现 用P V原语对进程中信号量进行操作以实现同步与互斥的方法 简称P V操作 2 进程的同步与互斥的解决 信号量的概念和P V原语是荷兰科学家Dijkstra提出的 把交通管理的信号灯方法搬到了操作系统中 P原语操作过程 P操作记为P S 其中S为一信号量 其执行顺序完成以下动作 1 S S 1 表示申请使用一个资源 2 若S 0 表示系统中有资源可用 现进程可继续执行 3 若S 0 表示系统中没有可用资源 则置该进程阻塞状态 到S信号量的队列中去等待 直到其他进程在S上执行V操作释放它为止 V原语操作过程 V操作记为V S 其中S为一信号量 其执行顺序完成以下动作 1 S S 1 表示释放一个资源 2 若S 0 表示系统中没有等待该资源的进程 现进程可继续执行 3 若S 0 表示系统中有等待该资源的进程 则唤醒S信号量队列中的第一个进程 使其插入到就绪队列 继续执行现进程 死锁 每个进程所要求的资源都已被另一个进程占用 出现没有一个进程能继续运行 这种情况称 死锁 2 死锁产生的原因A 资源不能共享 资源独占性 B 资源的不可剥夺性 C 资源采用动态分配原则 允许一个进程不释放已占有的资源 就又去申请别的资源 D 允许进程间非法交叉推进顺序的存在 导致循环等待资源 无法前进 七 死锁 3 死锁产生必须同时具有的四个必要条件 A 资源独占性 B 资源的不可剥夺性 C 资源采用动态的部分分配原则D 出现相关进程由于资源分配不当而出现循环等待 第三节存储管理 一 存储管理的相关概念当前存储器一般被分成三级 高速缓存 缓存 CACHE主存储器 内存RAM 处理机能直接访问的存储器 用来存放系统和用户的程序和数据 其特点是存取速度快 存储方式是以新换旧 断电信息丢失 外部存储器 外存 处理机不能直接访问的存储器 用来存放用户的各种信息 存取速度相对内存而言要慢得多 但它可用来长期保存用户信息 在文件系统中介绍 存储分配 按照一定的算法把某一空闲的主存储空间分配给作业或进程 地址映射 将程序地址空间中使用的逻辑地址变换成主存中的地址的过程 转换 定位 存储保护 保证用户程序 或进程映象 在各自的存储区域内操作 互不干扰 存储扩充 为大作业的运行提供空间 覆盖 交换 虚拟存储 虚拟存储 使用户程序的大小和结构不受主存容量和结构的限制 即使在用户程序比实际主存容量还要大的情况下 程序也能正确运行 二 存储管理的主要功能 1 分页式存储管理 分区存储管理的主要问题是碎片问题 在采用分区存储管理的系统中 会形成一些非常小的分区 最终这些非常小的分区不能被系统中的任何用户 程序 利用而浪费 造成这样问题的主要原因是用户程序装入内存时是整体装入的 为解决这个问题 提出了分页存储管理技术 分页的概念程序地址空间分成大小相等的页面 同时把内存也分成与页面大小相等的块 当一个用户程序装入内存时 以页面为单位进行分配 页面的大小是为2n 通常为1KB 2KB nKB等 待解决问题 分页式存储管理系统的地址映射 调入策略 淘汰策略 放置策略 页式地址变换图 4 淘汰策略 1 置换算法当要索取一页面并送入到全满的内存中时 必须把已在内存中的某一页淘汰掉 用来选择淘汰哪一页的规则叫做置换算法 2 颠簸在请求分页存储管理系统中 可能会出现这样的现象 即对于刚被替换出去的页 可能马上又要被访问 需要将它调入 因无空闲内存又要替换另一页 而后者可能是即将被访问的页 于是造成了系统需花费大量的时间忙于进行这种频繁的页面交换 致使系统的实际效率很低 严重时导致系统瘫痪 颠簸或抖动现象 2 虚拟设备技术 通过共享设备来模拟独占型设备的动作 使独占型设备成为共享设备 从而提高了设备利用率和系统的效率的技术 SPOOL系统 实现虚拟设备技术的硬件和软件系统称为SPOOL系统 Spooling系统 假脱机系统 构成 输入SPOOL和输出SPOOL 输出SPOOL 系统中全部行式打印机采用虚拟设备技术 例如 进程要求打印机 在某共享设备上的输出SPOOL存储区中为其分配一块存储空间 并为该进程的输出数据建立一个文件 相当于虚拟的行式打印机 各进程的输出都以文件形式暂时存放在输出SPOOL存储区中并形成了一个输出队列 输出SPOOL控制打印机进程 依次将输出队列中的各进程的输出文件最后实