第九章 软件开发与信息处理技术
? 软件工程基础
? 数据库设计基础
? 数据结构与算法
? 程序设计基础
? 多媒体技术简介
9.1 软件工程基础
软件的规模大小、复杂程度决定了软
件开发的难度，因此，必须采用科学的
软件开发方法，采用抽象、分解等科学
方法降低复杂度，以工程的方法管理和
控制软件开发的各个阶段，以保证大型
软件系统的开发具有 正确性、易维护
性、可读性和可重用性
9.1.1 软件工程基本概念
软件的发展大致分为四个阶段,（ 如下图）
阶段
第一阶段 第二阶段 第三阶段 第四阶段
程序设计阶
段
程序系统阶
段
软件工程阶段
（结构化方法
发）
软件工程阶段
（面向对象方法）
典型技
术
面向批处理
有限的分布
自定义软件
多用户
实时
数据库
软件产品
分布式系统
嵌入“智能”
低成本硬件
消费者的影响
强大的桌面系统
面向对象技术
专家系统
人工神经网络
网络计算机
软件危机和软件工程
? 软件危机主要表现在,对软件开发成本和进
度的估计常常很不准确，经费预算经常突破，
完成时间一再拖延；开发的软件不能满足用
户要求，用户软件不满意的现象经常发生；
开发的软件可维护性差、可靠性差
? 软件工程,运用系统的、规范的和可定量的
方法开发、运行和维护软件。它包含三个要
素：
方法（ Methodologies）
工具（ Tools） 过程（ Procedures）
软件工程过程和软件生命周期
? 软件工程过程
? 软件生命周期
? 软件生命周期模型
? 软件工程的目标和原则
? 软件开发工具与软件开发环境
下图为软件生命周期各阶段的任务：
时期 阶段 任务 文档
软件计划
问题定义 理解用户要求，划清工作范围 计划说明书
可行性研
究
可行性方案及代价
需求分析 软件系统的目标及应完成的工作 需求规格说明书
软件开发
概要设计 系统的逻辑设计 软件概要设计说明
书
详细设计 系统模块设计 软件详细设计说明
书
软件编码 编写程序代码 程序、数据、详细
注释
软件测试 单元测试、综合测试 测试后的软件、测
试大纲、测试方案
与结果
软件维护 软件维护 运行和维护 维护后的软件
图为软件生命周期的 瀑布模型 和 快速原形法模型
软件计划
需求分析
软件设计
软件编码
软件测试
软件维护
需求分析
快速设计
建立模型
用户评价模型
修改原型
生产产品
软件工程目标和原则
目标,在给定成本、进度的前提下，开发出具
有有效性、可靠性、可理解性、可维护性、
可重用性、可适应性、可移植性、可追踪性
并满足用户需求的产品
软件工程理论和技术性研究的内容：
软件开发技术和软件管理技术
原则,抽象、信息隐蔽、模块化、局部化、确
定性、一致性、完备性和可验证性
软件开发工具与开发环境
软件开发工具,是为支持软件人员开发
和维护活动而使用的软件。
作用,可以帮助开发人员完成一些繁琐的程
序编制和调试问题，是软件开发人员将更多
的精力和时间投放到最重要的软件需求和设
计上，提高软件开发的速度和质量。
9.1.2 结构化分析方法
? 结构化方法（ Sructured
Methodology）,是计算学科的一种典型
的系统开发方法，它采用了系统科学的思想
方法，从层次的角度，自顶向下的分析和设
计系统。
? 内容,结构化分析（ Sructured Analysis）
结构化设计（ Sructured Design）
结构化程序设计（ Sructured
Program Design）
软件开发过程
? 问题定义
? 可行性研究
? 需求分析与需求分析方法
? 结构化分析方法概述
? 软件需求规格说明书
结构化分析方法使用的工具
A,数据流图（ Data Flow Diagram） 从
数据传递和加工的角度，以图形方式刻画
数据流从输入到输出的移动变换过程
B,数据字典（ Data Dictionary） 需对
数据流图中的各个元素作完整的定义和说
明，是数据流图的补充工具
C,加工逻辑描述工具 （常用：结构化自
然语言、判定树和判定表）
9.1.3 结构化设计方法
? 软件设计的基本概念,是一个把软件
需求转化为软件表示的过程，即把分析结果
加工为在程序细节上接近于源程序的软件表
示（软件描述）
? 软件设计阶段分为：
? 系统的总体设计或概要设计（确定软件系
统结构）
? 系统的详细设计（进行各模块的具体设计）
概要设计
? 概要设计 又称为总体设计，它的任务
是确定软件结构
? 结构化设计方法的基本思想,采用自顶
向下的模块化设计方法，按照模块化原
则和软件设计策略，将需求分析得到的
数据流图，映射成由相对独立、单一功
能的模块组成的软件结构
概要设计
? 概要设计的图形工具 （层次图,HIPO
图、软件结构图）
? 软件设计原理
? 软件结构设计原则
? 面向数据流的设计方法 （变换流分析
设计和事务流分析设计）
? 设计规格说明
软件结构设计原则
① 提高模块独立性
② 模块规模应该适中
③ 模块的深度、宽度、扇出和扇入适
当
④ 模块的作用域应该在控制域之内
⑤ 降低模块接口的复杂程度
⑥ 设计单入口和单出口模块
详细设计
? 任务,为软件结构图中的每一个模块
确定实现算法和局部数据结构，并用某
种工具描述出来
? 结构化程序设计
? 详细设计工具 （程序流程图、盒图 [N-S
图 ],PAD图）
? 详细设计规格说明
9.1.4 软件测试
一、软件测试的目的与任务
目的,确保软件的质量，尽量找出软件错误
并加以纠正，而不是证明软件没有错。
任务,测试任务 （通过采用一定的测试策略，
找出软件中的错误）
调试任务或纠错任务 （如果测试到错
误，则定位软件中的错误，加以纠正）
二、软件测试的准则
三、软件测试技术与方法综述
方法,静态测试法
动态测试法
技术,白盒测试用例设计
黑盒测试用例设计
9.1.4 软件测试
白盒测试用例设计
A,逻辑覆盖
以程序的内部逻辑结构为基础的测试用例
设计技术，它要求测试人员十分清楚程序
的逻辑结构，考虑的是测试用例对程序内
部逻辑覆盖的程度
根据覆盖的目标，可分为,语句覆盖、判
定覆盖、条件覆盖、判定 /条件覆盖、路
径覆盖
B, 基本路径测试
黑盒测试用例设计
分类：
等价类划分法
边界值分析法
错误推测法
因果图
四、软件测试的实施
? 单元测试
? 集成测试
? 确认测试
? 系统测试
五、软件测试计划与测试分析报告
测试 是软件生存周期中的一个独立的
关键的阶段
9.1.4 软件测试
9.1.5 程序的调试
程序调试可以分为：
静态调试 （主要通过人的思维来分析源程
序代码和排错，是主要的调试手段）
动态调试 （是静态调试的辅助）
主要的调试方法有,强行排错法
回溯法
原因排除法
9.2 数据库设计基础
? 数据库概念
? 数据模型
? 数据库设计与管理
9.2.1 数据库概念
? 数据（ Data）
? 数据处理（ Data Processing）
? 数据库（ Database,DB）
? 数据库管理系统（ Database Management
System,DBMS）
? 数据库管理员（ Database Administrator,DBA）
? 数据库系统（ Database System, DBS）
? 数据库应用系统（ Database Application
System,DBAS）
数据库系统的发展
? 人工管理阶段
? 文件系统阶段
? 数据库系统阶段
（在关于数据库的诸多新技术中，比较重要
的三种是：
面向对象数据库系统、知识库系统，以及
关系数据库系统的扩充 ）
数据库系统的基本功能
? 数据定义功能
? 数据操纵功能
? 数据库运行控制功能
? 数据库的建立和维护功能
数据库系统的基本特点
? 数据的结构化
? 数据的高共享性和低冗余性
? 数据的独立性
? 数据的统一管理与控制
数据库系统的内部结构体系
模式,是数据库中全体数据的逻辑结构和特征的描
述，它仅仅涉及到型的描述，不涉及到具体的值。
模式的一个具体值称为模式的一个实例，同一个
模式可以有多个实例。数据库管理系统采用 三级
模式结构,
概念模式
外模式（是概念模式的逻辑子集，也称子模式或
用户模式）
内模式（也称存储模式）
并提供 二级映像功能
9.2.2 数据模型
?数据模型（ data model）,是表示实
体类型及实体之间联系的模型
?数据模式的三个要素：
? 数据结构
? 数据操作
? 数据的完整性约束条件
数据模型的三个级别：
? 概念数据模型
? 逻辑数据模型
? 物理数据模型
7.2.2 数据模型
数据模型的分类
? E-R 模型（实体联系模型）
是直接从现实世界中抽象出实体类型
及实体间联系，然后用实体联系图（ E-R图）
表示数据模型
? 层次模型 （若用图表示，它是一棵倒
立的树）
? 网状模型 （ 若用图表示 是一个网络）
? 关系模型 （数据的逻辑结构是一张二
维表）
9.2.3 数据库设计与管理
数据库及其应用系统的 设计步骤：
? 用户需求分析
? 概念设计
? 逻辑设计
? 物理设计
? 数据库实施
? 数据库的维护
数据库设计的需求分析
? 用户的信息要求
? 用户的处理要求
? 对数据的安全性、完整性的要求
数据库的概念设计
概念结构设计,只讲需求分析得到的用户需
求抽象为信息结构即概念模型的过程
概念结构 独立于数据库逻辑结构，也独立
于支持数据库的 DBMS。
它是现实世界与机器世界的中介，它一方
面能够充分反映现实世界，包括实体与实体之
间的联系，同时又易于向关系、网状、层次等
各种数据模式转换。
数据库的逻辑设计
逻辑结构设计的步骤：
? 将概念结构向一般关系模型转化
? 将第一步得到的结构向特定的 DBMS
支持下的数据模型转换
? 依据应用的需求和具体的 DBMS特征
进行调整与完善
数据库的物理设计
确定数据的存储安排
存取路径的选择和调整
确定系统配置
数据库管理
数据库的管理主要指：
数据库的实施和维护
分三个步骤：
数据的载入和应用程序的调试
数据库的试运行
数据库的运行和维护
数据库的维护
在数据库运行阶段，对数据库经常性的维
护工作主要是由 DBA完成的。包括：
数据库的存储和恢复
数据库的安全性、完整性控制
数据库性能的监督、分析和改进
数据库的重组织与重构造
9.3 数据结构与算法
? 算法
? 数据结构的基本概念及术语
? 线性表
? 栈
? 队列
? 树与二叉树
? 查找与排序
9.3.1 算法
? 定义,是对特定问题求解步骤的一种描
述。或者说，是为求解某问题而设计的
步骤序列
? 特征,有穷性
确定性
有效性
输入
输出
算法复杂度
评价一个算法优劣的主要标准是：
算法的执行效率与存储需求
算法的效率,指的是时间复杂度（ Time
Complexity）
存储需求,指的是空间复杂度（ Space
Complexity ）
一般情况下，算法中的基本操作重复操作执行的
次数是问题规模 n的某个函数 f(n),算法的时间
复杂度记做 T(n)=O(f(n))
9.3.2 数据结构的基本概念及术语
?数据与数据结构
数据 是描述客观事物的数、字符以及所有能输入
到计算机中并被计算机程序加工处理的符号的集
合
数据元素 是数据的基本元素，即数据集合中的个
体
数据项 具有独立意义的最小数据单位
数据对象 具有相同特性的数据元素的集合，是数
据的子集
结构 被计算机加工的数据元素之间存在的关系
数据结构 带有结构特性的数据元素的集合
?数据的逻辑结构
? 集合
? 线性结构
? 树形结构
? 图状或网状结构
9.3.2 数据结构的基本概念及
术语
?数据的存储结构
一、顺序存储结构
主要特点：
? 结点中只有自身信息域，没有连接信息域，因
此存储密度大，存储空间利用率高
? 可以通过计算直接确定数据结构中第 i个结点
的存储地址 Li，计算公式,L0+（ i-1） m。（其
中 L0为第一个结点的存储地址,m为每个结点
所占用的存储单元个数
? 插入、删除运算不便，会引起大量结点的移动
9.3.2 数据结构的基本概念
及术语
二、链式存储结构
主要特点：
? 结点中除自身信息之外，还有表示连接
信息的指针域，因此比顺序存储密度小，
存储空间利用率低
? 逻辑上相邻的结点物理上不必邻接，可
用于线性表、树、图等多种逻辑结构的
存储表示
? 插入、删除操作灵活方便，不必移动结
点，只要改变结点中的指针值即可
? 数据的运算
? 检索,在数据结构里查找满足一定条件
的结点
? 插入,往数据结构里增加新的结点
? 删除,把指定的结点从数据结构里去掉
? 更新,改变指定结点的一个或多个域的
值
? 排序,保持线性结构的结点序列里结点
数不变，把结点按某种指定的顺序重新排
列
9.3.2 数据结构的基本概念
及术语
9.3.3 线性表
线性表 是最常用的一种数据结构。线性表的
逻辑结构是 n个数据元素的有限序列
（ a1,a2,…,an）
? 顺序表,指用顺序存储结构存储的线性表
? 链表,用链式存储结构存储的线性表
? 栈和队列 —— 是对线性表的插入、删除运算
可以发生的位置加以限制的两种特殊的线性
表
顺序表和一维数组
各种高级语言里的一维数组就是用顺序
方式存储的线性表，因此常用 一维数组
称呼顺序表
若顺序表中结点个数为 n，则：
插入 一个结点平均需要移动之结点个数
为 n/2，算法的时间复杂度是 O(n)；
删除 一个结点平均需移动结点个数为
（ n-1） /2，算法的时间复杂度是 O(n)
链 表
线性链表（单链表）,删除算法的时间复
杂度为 O(n)，其主要执行时间是搜索删除位置
循环链表,指链表的最后一个结点的指针值
指向第一个结点，整个链表形成一个环（如下
图）
…
结点 1 结点 2 结点 n
9.3.4 栈
栈,是一种特殊的线性表，是限定仅在表尾进
行插入和删除运算的线性表，表尾称为栈顶
（ top），表头称为栈底（ bottom）。
空栈,指表中无元素
? 栈中有元素 a1,a2,…,an，如 下页图 所示，称 a1为
栈底元素。新元素进栈要置于 an之上，删除或退栈
先对 an进行，即, 后进先出, （ LIFO） 的操作原则
? 栈的物理存储可以用
顺序存储结构或链式存储结构
? 栈的运算还有取栈顶元素，检查栈是否为空，
清除等。
栈的插入和删除
A
B
A
C
B
A
B
A
F
E
B
A ATOP
TOP
TOP
TOP
TOP
TOP
an
…
a2
a1
进栈 出栈
栈底
栈结构
(3)(1) (2) (5)(4) (6)
9.3.5 队列
队列,是限定所有的插入都在表的一端进
行，所有的删除都在表的另一端进行的线
性表。进行删除的一端叫 队列的头,进行
插入的一端叫 队列的尾,如 下页图 所示。
在队列中，新元素总是加入到队尾，
每次删除的总是对头元素，即当前“最老
的”元素，这就是, 先进先出, （ FIFO）
的操作原则
队列的物理存储可以用：
顺序存储结构，也可用链式存储结构
队列的示意（如下图）
出队列 a1 a2 a3 … an 入队列
头 尾
队列的插入和删除示例
初
态
插
入
A
插
入
B
删
除
A
插
入
C
插
入
D
删
除
B
插
入
E
F
R AF
R
R R
R
R R
F
F F F
F F
B
A
B B B
C C C C
D D D
溢出
7.3.6 树与二叉树
? 树形结构 是一类重要的非线性结构，
树和二叉树是最常见的树形结构
? 树（ Tree）,是一个或多个结点组成
的有限集合 T，有一个特定的结点称为
根（ Root），其余的结点分为 m（ m≥0 ）
个不相交的集合 T1,T2,…, Tm，每个
集合又是一棵树，称作这个根的子树
（ Subtree)
树形结构的常用术语
? 结点的度（ Degree）,一个结点的子树的个数
? 树的度,树中各结点的度的最大值
? 树叶（ Leaf）, 度为 0的结点
? 分支结点,度不为 0的结点
? 双亲（ Parent）、子女（ Child）,结点的各子
树的根称作该结点的子女；相应的该结点称作其
子女的双亲
? 兄弟（ Sibling）,具有相同双亲的结点互为兄
弟
? 结点的层数（ Level）树的深度（ Depth）
? 森林（ Forest）
二 叉 树
? 二叉树（ Binary Tree）,是 n（ n≥ 0)个结点
的有限集合，这个集合或者为空集（ n=0），或
者由一个根结点及两棵不相交的、分别称作这个
根的坐姿树和右子树的二叉树组成
二叉树不是树的特殊情形，二者的 区别：
二叉树为有序树
? 性质,1、在二叉树的 i层上，最多有 2i-1个结点
（ i≥ 1）
2,深度为 k的二叉树最多有 2k-1个结点
(k≥1)
完全二叉树
? 一棵深度为 k且具有 2k-1个结点的二叉
树称为 满二叉树（ Full Binary
Tree ）
? 深度为 k，有 n个结点的二叉树，当且仅
当其妹一个结点都与深度为 k的满二叉
树中编号从 1到 n的结点一一对应时，称
为 完全二叉树
树的二叉树表示
在树（森林）与二叉树间有一个自然的
一一对应的关系，每一棵树都能唯一的
转换到它所对应的二叉树
把树和森林转化成对应的二叉树：
凡是兄弟就用线连起来，然后去掉双亲
到子女的连线，只留下道第一个子女的
连线不去掉
二叉树的存储
二叉树的存储通常采用,链接方式 。每
个结点除存储结点自身的信息外再设置
两个指针域 IIink和 rlink，分别指向结
点的左子女和右子女，当结点的某个指
针为空时，则相应的指针值为空（ NIL）。
结点的形式为：
IIink info rlink
二叉树的遍历
? 遍历一个树形结构是指,按一定次序系统
的访问该结构中的所有结点，使每个结点恰好被
访问一次
? 前序遍历法（ NLR次序）
访问根，按前序遍历左子树，按前序遍历右子树
? 后序遍历法（ LRN次序）
按后序遍历左子树，按后序遍历右子树，访问根
? 中序遍历法（ LNR次序）
按中序遍历左子树，访问根，按中序遍历右子树
9.3.7 查找
? 查找,是数据结构中的基本运算
? 衡量一个查找运算法的主要标志是：
查找过程中对关节码进行的平均比
较次数，或称平均检索长度，以 n的函数
的形式表示,n是数据结构中的结点个数
顺序查找
顺序查找,是线性表的最简单的查找方法
方法,用待查关键码与线性表中各结点的关键
码值逐个比较，若找出相等的关键码值则查找
成功，若找遍所有结点都不相等，则查找失败
优点,对线性表的结点逻辑次序和存储结构无
要求
缺点,平均检索长度大
假设表中各结点被查找的概率相同，即 P=1/n,
则顺序查找成功的 平均查找长度为 (n+1)/2
二分法查找
? 二分法查找,是一种效率较高的线性表查找方法。
要进行二分法查找，线性表结点必须是按关键码值
排号顺序的，且线性表以顺序方式存储
? 方法,首先用要查找的关键码值与线性表中间位
置结点的关键码值相比较，这个中间结点把线性表
分成两个子表，比较相等则查找完成，不等则根据
比较结果确定下一步的查找应在哪个子表中进行，
如此下去，直到找到满足条件的结点
? 优点,平均检索长度小，为 ㏒ 2n。每经过一次关
键码比较，则将查找范围缩小一半，因此经过㏒ 2n
次比较就可完成查找过程
? 缺点,排序线性表花费时间，顺序方式存储插入、
删除不便
9.3.8 排序
排序,是数据处理中经常使用的一种运算
分类：
? 直接插入排序
? 选择排序
? 冒泡排序
? 快速排序
A,直接插入排序 的 基本方法,每步将一个
待排序记录按其关键码值的大小插入到
前面已排序的文件中适当位置上，直到
全部插入为止
B,选择排序 的 基本思想,每一趟在 n-
i+1(i=1,2,…,n-1）个记录中选取关键
码最小的记录作为有序序列中的第 i个记
录。它为最简单且为我们最熟悉的排序
C,冒泡排序 的 基本方法,将待排序的记录
顺次两两比较，若为逆序，则进行交换
D,快速排序,又称分区交换排序，是对冒
泡排序的一种改进。
? 快速排序 的基本方法, 在待排序序列中任取一个
记录，以它为基准用交换的发方法将所有记录分成两
部分，关键码比它小的在一个部分，关键码值比它大
的在另一个部分。再分别对两个部分实施上述过程，
一直重复到排序完成
? 下图为四种排序方法的比较：
排序方法 平均时间 最坏情况 辅助存储
直接插入排序
选择排序
冒泡排序
快速排序
O(n2)
O(n2)
O(n2)
O(n ㏒ 2n)
O(n2)
O(n2)
O(n2)
O(n2)
O(1)
O(1)
O(1)
O(㏒ 2n)
9.4 程序设计基础
? 程序设计语言发展
? 程序设计方法与风格
? 结构化程序设计
? 面向对象的程序设计
程序设计
指令,能被计算机直接识别与执行的指
示计算机进行某种操作的命令,CPU每执
行一条指令，就完成一个基本运算。
程序,指令的序列即让计算机解决某一
问题而写出的一系列指令
程序设计,编写程序的过程
程序设计语言,用于描述计算机所执
行的操作语言
9.4.1 程序设计语言发展
? 机器语言,采用计算机指令格式并以
二进制编码表达各种操作的语言
? 汇编语言,一种符号语言，采用助记
符来表达指令功能
? 高级语言,是一种面向问题的语言
? 第四代语言,是非过程化语言
9.4.2 程序设计方法与风格
良好程序设计风格的侧重：
? 源程序文档如使用的符号名应具有一定的含义，
以便对程序功能的理解；对源程序适当的进行注解，
以便读者理解程序；在程序中利用空格、空行、缩
进等技巧使程序层次清楚
? 对程序中的数据进行适当说明
? 程序中的语句结构应该简单直接，语句不复杂化
? 要对程序的所有输入数据检查其合法性，检查输
入项的各种重要组合的合理性，输入格式要简单，
输入允许默认值，输入一批数据后最好使用结束标
志，在交互式输入 /输出中使用屏幕提示信息格式
9.4.3 结构化程序设计
结构化程序设计的原则
? 自顶向下
? 逐步求精
? 模块化
? 限制使用 GOTO语句
结构化程序设计的基本结构与特点
顺序结构,按照程序语句行的自然顺序，
一条语句一条语句的往后执行程序
选择结构,又称分支结构，它根据设定
的条件，判断应该选择哪一条分支执行相
应的语句序列
循环结构,又称重复结构，它根据给定
的条件，判断是否需要重复执行某一相同
的或相似的程序段
7.4.3 结构化程序设计
结构化程序设计的优点
① 自顶向下逐步求精的方法符合人类解决复杂问题的普遍规律，
可以显著提高软件开发的成功率和生产率
② 先全局后局部、先整体后细节、先抽向后具体的逐步求精过
程开发出的程序有清晰的层次结构，使程序容易阅读和理解
③ 使用单入口单出口控制结构而不使用 GOTO语句，使得程序的
静态结构和它的动态执行情况一致
④ 控制结构有确定逻辑模式，编写程序代码只限于使用很少几
种直截了当的方式，使源程序清晰流畅，易读易懂而且容易
测试
⑤ 程序清晰和模块化使得在修改和重新设计一个软件时可以重
用的代码量最大
⑥ 程序的逻辑结构清晰，有利于程序正确性证明
9.4.4 面向对象的程序设计
面向对象方法的主要特点：
① 从问题域中客观存在的事物出发来构造软件系
统，用对象作为对这些事物的抽象表示，并以
此作为系统的基本构成单位
② 事物的静态特征用对象的属性表示，动态特征
用对象的服务表示
③ 对象的属性与服务结合为一个独立的实体，对
外屏蔽其内部细节，称作封装
④ 把具有相同属性和相同服务的对象归为一类，
类是这些对象的抽象描述，每个对象是它的类
的一个实例
面向对象方法的主要特点：
⑤ 通过在不同程度上运用抽象的原则，可以得到
较一般的类和较特殊的类
⑥ 复杂的对象可以用简单的对象作为其构成部分，
称为聚合
⑦ 对象之间通过消息进行通信，以实现对象之间
的动态联系
⑧ 通过关联表达对象之间的静态关系
9.4.4 面向对象的程序设计
面向对象方法的概念
面向对象：
面向对象 =对象 +类 +继承 +通信
如果一个软件系统是使用这样四个
概念设计和实现的，则认为这个软件系
统是面向对象的。面向对象的程序的每
一组成部分都是对象，计算是通过建立
新的对象和对象之间的通信来执行的
对 象
对象是构成世界的一个独立单位，它具有自己的
静态特征和动态特征。
静态特征,指可以用某种数据来描述的特征
动态特征,指对象所表现的行为或对象所具有的功
能
定义,对象是系统中用来描述客观事物的一个实体，
它是构成系统的一个基本单位。一个对象由一
组属性和对这组属性进行操作的一组方法构成。
属性,用来描述对象静态特征的一个数据项
方法,用来描述对象动态特征的一个操作序列
消息和方法
? 一个系统由若干个对象组成，各个对象之
间相互联系、相互作用。
? 计算机系统中，消息就是对象之间的纽带，
是用来通知、命令或请求对象执行某个处
理或回答某些信息。
? 消息可以是 数据流,也可以是 控制流 。
? 一条消息可以发送给不同的对象，而消息
的解释则完全由接收对象完成。不同的对
象对相同形式的消息可以有不同的解释
类和实例
类和对象之间的关系 如同一个模具与
用这个模具铸造出来的铸件之间的关系。
类给出了属于该类的全部对象的抽象定义，
而对象则是符合这种定义的一个实体。
一个对象又称为类的一个实例（ Instance）
类也可称作对象的模板（ Template）
继 承 性
? 定义,特殊类的对象拥有其一般类的全
部属性与方法，称作特殊类对一般类的
继承
? 继承关系是传递的
? 继承性对于软件重用有很大益处
封 装 性
封装具有两个涵义：
一、是把对象的全部属性和全部方法结合
在一起，形成一个不可分割的独立单位
（即对象）
二、也称作“信息隐蔽”，即尽可能隐蔽
对象的内部细节，对外形成一个边界，
只保留有限的对外接口使之与外部发生
联系
多 态 性
对象的多态性：
指在一般类中定义的属性或方法被特殊
类继承之后，可以具有不同的数据类型
表现出不同的行为。这使得同一个属性
或方法名在一般类及其各个特殊类中具
有不同的语义
9.5 多媒体技术简介
? 多媒体技术的基本概念
? 多媒体计算机系统
? 多媒体计算机软件系统
? 多媒体信息的数字化和压缩技术
9.5.1 多媒体技术的基本概念
定义：指信息表示媒体的多样化。
多媒体的类型 感觉媒体
表示媒体
显示媒体
传输媒体
存储媒体
多媒体技术就是利用计算机把文本、声音、
视频、动画、图形和图像等多种媒体进行
综合处理，使多种信息建立逻辑连接，集
成为一个具有交互性的系统
多媒体技术的特征
? 信息载体的多样性
? 交互性
? 集成性
? 实时性
多媒体信息中的媒体元素的类型
? 文本（ Text）
? 图形（ Graphic）
? 图像（ Image）
? 音频
? 动画
? 视频
多媒体信息处理的关键技术
? 视频和音频数据压缩和解压缩技术
关于压缩编码的国际标准有：
JPEG标准
电视电话 /会议电视 P*64Kbit/s (CCITT
H.261)标准
MPEG-1标准
? 多媒体硬件系统的专用芯片
? 大容量的外部存储器
? 多媒体同步技术
多媒体技术的应用领域
? 教育与培训
? 桌面出版
? 多媒体电子出版物
? 多媒体通信
? 多媒体声光艺术品的创作
9.5.2 多媒体计算机系统
多媒体计算机系统的组成（如下图）
多
媒
体
计
算
机
系
统
软件系统
硬件系统
多媒体应用软件
媒体处理系统工具软件
多媒体数据处理软件
多媒体操作系统
多媒体驱动软件
多媒体输入 /输出控制卡及接口
多媒体计算机硬件
多媒体外围设备
多媒体计算机硬件系统
? 主机,常规的主板,CPU及 VGA适配卡、多功能
卡等
? 多媒体适配卡,音频卡、视频卡、图形卡和压
缩卡等
? 外部存储设备,软盘驱动器、硬盘驱动器和
CD-ROM驱动器
? 输入设备
? 输出设备
9.5.3多媒体计算机软件系统
多媒体应用程序
多媒体处理系统工具
多媒体操作系统
（媒体控制接口）
音频 /视频核心处理
音频 /视频设备驱动程序
音频 /视频设备
多
媒
体
计
算
机
软
件
的
层
次
结
构
（
如
右
图
）
第五层
第四层
第三层
第二层
第一层
9.5.4 多媒体信息的数字化和压
缩技术
音频信息
?声音的特征
?模拟音频和数字音频
衡量一个数字声音波形的质量有：采样频率、采
样精度、声道数三个要素
?数字音频文件的存储格式
?数字音频文件的存储量
存储量 =采样频率 × 量化位数 /8× 声道数 × 时间
图像信息
图像信息的性能指标
? 分辨率
? 图像深度和显示深度
? 图像文件的大小
图像文件的存储格式
① BMP格式 PCX格式
② GIF格式 TIF格式
③ JPG和 PIC格式 PCD格式
④ CDR格式 PSD格式
⑤ IFF格式 DIF格式
视频信息
? 视频的彩色空间表示
RGB彩色空间
YUV和 YIQ彩色空间
? 模拟视频标准 （ NTSC制式 PAL制式
SECAM制式）
? 数字视频
? 视频序列的时间码
? 数字视频标准与文件格式
数字视频标准与文件格式
? MPEG标准
MPEG-1（ 1992年正式发布）
MPEG-2（ 1994年制定）
MPEG-4（ 1999年正式发布）
? AVI格式
? PM格式
? Quick Time格式
数据压缩技术
? 无损压缩
行程编码（ RLE）
Huffman编码
算术编码
LZW编码
? 有损压缩
三种数据压缩国际标准,JPEG-静止图像压缩标
准,MPEG-运动图像压缩编码标准,H.261-视频
通信编码标准
? 软件工程基础
? 数据库设计基础
? 数据结构与算法
? 程序设计基础
? 多媒体技术简介
9.1 软件工程基础
软件的规模大小、复杂程度决定了软
件开发的难度，因此，必须采用科学的
软件开发方法，采用抽象、分解等科学
方法降低复杂度，以工程的方法管理和
控制软件开发的各个阶段，以保证大型
软件系统的开发具有 正确性、易维护
性、可读性和可重用性
9.1.1 软件工程基本概念
软件的发展大致分为四个阶段,（ 如下图）
阶段
第一阶段 第二阶段 第三阶段 第四阶段
程序设计阶
段
程序系统阶
段
软件工程阶段
（结构化方法
发）
软件工程阶段
（面向对象方法）
典型技
术
面向批处理
有限的分布
自定义软件
多用户
实时
数据库
软件产品
分布式系统
嵌入“智能”
低成本硬件
消费者的影响
强大的桌面系统
面向对象技术
专家系统
人工神经网络
网络计算机
软件危机和软件工程
? 软件危机主要表现在,对软件开发成本和进
度的估计常常很不准确，经费预算经常突破，
完成时间一再拖延；开发的软件不能满足用
户要求，用户软件不满意的现象经常发生；
开发的软件可维护性差、可靠性差
? 软件工程,运用系统的、规范的和可定量的
方法开发、运行和维护软件。它包含三个要
素：
方法（ Methodologies）
工具（ Tools） 过程（ Procedures）
软件工程过程和软件生命周期
? 软件工程过程
? 软件生命周期
? 软件生命周期模型
? 软件工程的目标和原则
? 软件开发工具与软件开发环境
下图为软件生命周期各阶段的任务：
时期 阶段 任务 文档
软件计划
问题定义 理解用户要求，划清工作范围 计划说明书
可行性研
究
可行性方案及代价
需求分析 软件系统的目标及应完成的工作 需求规格说明书
软件开发
概要设计 系统的逻辑设计 软件概要设计说明
书
详细设计 系统模块设计 软件详细设计说明
书
软件编码 编写程序代码 程序、数据、详细
注释
软件测试 单元测试、综合测试 测试后的软件、测
试大纲、测试方案
与结果
软件维护 软件维护 运行和维护 维护后的软件
图为软件生命周期的 瀑布模型 和 快速原形法模型
软件计划
需求分析
软件设计
软件编码
软件测试
软件维护
需求分析
快速设计
建立模型
用户评价模型
修改原型
生产产品
软件工程目标和原则
目标,在给定成本、进度的前提下，开发出具
有有效性、可靠性、可理解性、可维护性、
可重用性、可适应性、可移植性、可追踪性
并满足用户需求的产品
软件工程理论和技术性研究的内容：
软件开发技术和软件管理技术
原则,抽象、信息隐蔽、模块化、局部化、确
定性、一致性、完备性和可验证性
软件开发工具与开发环境
软件开发工具,是为支持软件人员开发
和维护活动而使用的软件。
作用,可以帮助开发人员完成一些繁琐的程
序编制和调试问题，是软件开发人员将更多
的精力和时间投放到最重要的软件需求和设
计上，提高软件开发的速度和质量。
9.1.2 结构化分析方法
? 结构化方法（ Sructured
Methodology）,是计算学科的一种典型
的系统开发方法，它采用了系统科学的思想
方法，从层次的角度，自顶向下的分析和设
计系统。
? 内容,结构化分析（ Sructured Analysis）
结构化设计（ Sructured Design）
结构化程序设计（ Sructured
Program Design）
软件开发过程
? 问题定义
? 可行性研究
? 需求分析与需求分析方法
? 结构化分析方法概述
? 软件需求规格说明书
结构化分析方法使用的工具
A,数据流图（ Data Flow Diagram） 从
数据传递和加工的角度，以图形方式刻画
数据流从输入到输出的移动变换过程
B,数据字典（ Data Dictionary） 需对
数据流图中的各个元素作完整的定义和说
明，是数据流图的补充工具
C,加工逻辑描述工具 （常用：结构化自
然语言、判定树和判定表）
9.1.3 结构化设计方法
? 软件设计的基本概念,是一个把软件
需求转化为软件表示的过程，即把分析结果
加工为在程序细节上接近于源程序的软件表
示（软件描述）
? 软件设计阶段分为：
? 系统的总体设计或概要设计（确定软件系
统结构）
? 系统的详细设计（进行各模块的具体设计）
概要设计
? 概要设计 又称为总体设计，它的任务
是确定软件结构
? 结构化设计方法的基本思想,采用自顶
向下的模块化设计方法，按照模块化原
则和软件设计策略，将需求分析得到的
数据流图，映射成由相对独立、单一功
能的模块组成的软件结构
概要设计
? 概要设计的图形工具 （层次图,HIPO
图、软件结构图）
? 软件设计原理
? 软件结构设计原则
? 面向数据流的设计方法 （变换流分析
设计和事务流分析设计）
? 设计规格说明
软件结构设计原则
① 提高模块独立性
② 模块规模应该适中
③ 模块的深度、宽度、扇出和扇入适
当
④ 模块的作用域应该在控制域之内
⑤ 降低模块接口的复杂程度
⑥ 设计单入口和单出口模块
详细设计
? 任务,为软件结构图中的每一个模块
确定实现算法和局部数据结构，并用某
种工具描述出来
? 结构化程序设计
? 详细设计工具 （程序流程图、盒图 [N-S
图 ],PAD图）
? 详细设计规格说明
9.1.4 软件测试
一、软件测试的目的与任务
目的,确保软件的质量，尽量找出软件错误
并加以纠正，而不是证明软件没有错。
任务,测试任务 （通过采用一定的测试策略，
找出软件中的错误）
调试任务或纠错任务 （如果测试到错
误，则定位软件中的错误，加以纠正）
二、软件测试的准则
三、软件测试技术与方法综述
方法,静态测试法
动态测试法
技术,白盒测试用例设计
黑盒测试用例设计
9.1.4 软件测试
白盒测试用例设计
A,逻辑覆盖
以程序的内部逻辑结构为基础的测试用例
设计技术，它要求测试人员十分清楚程序
的逻辑结构，考虑的是测试用例对程序内
部逻辑覆盖的程度
根据覆盖的目标，可分为,语句覆盖、判
定覆盖、条件覆盖、判定 /条件覆盖、路
径覆盖
B, 基本路径测试
黑盒测试用例设计
分类：
等价类划分法
边界值分析法
错误推测法
因果图
四、软件测试的实施
? 单元测试
? 集成测试
? 确认测试
? 系统测试
五、软件测试计划与测试分析报告
测试 是软件生存周期中的一个独立的
关键的阶段
9.1.4 软件测试
9.1.5 程序的调试
程序调试可以分为：
静态调试 （主要通过人的思维来分析源程
序代码和排错，是主要的调试手段）
动态调试 （是静态调试的辅助）
主要的调试方法有,强行排错法
回溯法
原因排除法
9.2 数据库设计基础
? 数据库概念
? 数据模型
? 数据库设计与管理
9.2.1 数据库概念
? 数据（ Data）
? 数据处理（ Data Processing）
? 数据库（ Database,DB）
? 数据库管理系统（ Database Management
System,DBMS）
? 数据库管理员（ Database Administrator,DBA）
? 数据库系统（ Database System, DBS）
? 数据库应用系统（ Database Application
System,DBAS）
数据库系统的发展
? 人工管理阶段
? 文件系统阶段
? 数据库系统阶段
（在关于数据库的诸多新技术中，比较重要
的三种是：
面向对象数据库系统、知识库系统，以及
关系数据库系统的扩充 ）
数据库系统的基本功能
? 数据定义功能
? 数据操纵功能
? 数据库运行控制功能
? 数据库的建立和维护功能
数据库系统的基本特点
? 数据的结构化
? 数据的高共享性和低冗余性
? 数据的独立性
? 数据的统一管理与控制
数据库系统的内部结构体系
模式,是数据库中全体数据的逻辑结构和特征的描
述，它仅仅涉及到型的描述，不涉及到具体的值。
模式的一个具体值称为模式的一个实例，同一个
模式可以有多个实例。数据库管理系统采用 三级
模式结构,
概念模式
外模式（是概念模式的逻辑子集，也称子模式或
用户模式）
内模式（也称存储模式）
并提供 二级映像功能
9.2.2 数据模型
?数据模型（ data model）,是表示实
体类型及实体之间联系的模型
?数据模式的三个要素：
? 数据结构
? 数据操作
? 数据的完整性约束条件
数据模型的三个级别：
? 概念数据模型
? 逻辑数据模型
? 物理数据模型
7.2.2 数据模型
数据模型的分类
? E-R 模型（实体联系模型）
是直接从现实世界中抽象出实体类型
及实体间联系，然后用实体联系图（ E-R图）
表示数据模型
? 层次模型 （若用图表示，它是一棵倒
立的树）
? 网状模型 （ 若用图表示 是一个网络）
? 关系模型 （数据的逻辑结构是一张二
维表）
9.2.3 数据库设计与管理
数据库及其应用系统的 设计步骤：
? 用户需求分析
? 概念设计
? 逻辑设计
? 物理设计
? 数据库实施
? 数据库的维护
数据库设计的需求分析
? 用户的信息要求
? 用户的处理要求
? 对数据的安全性、完整性的要求
数据库的概念设计
概念结构设计,只讲需求分析得到的用户需
求抽象为信息结构即概念模型的过程
概念结构 独立于数据库逻辑结构，也独立
于支持数据库的 DBMS。
它是现实世界与机器世界的中介，它一方
面能够充分反映现实世界，包括实体与实体之
间的联系，同时又易于向关系、网状、层次等
各种数据模式转换。
数据库的逻辑设计
逻辑结构设计的步骤：
? 将概念结构向一般关系模型转化
? 将第一步得到的结构向特定的 DBMS
支持下的数据模型转换
? 依据应用的需求和具体的 DBMS特征
进行调整与完善
数据库的物理设计
确定数据的存储安排
存取路径的选择和调整
确定系统配置
数据库管理
数据库的管理主要指：
数据库的实施和维护
分三个步骤：
数据的载入和应用程序的调试
数据库的试运行
数据库的运行和维护
数据库的维护
在数据库运行阶段，对数据库经常性的维
护工作主要是由 DBA完成的。包括：
数据库的存储和恢复
数据库的安全性、完整性控制
数据库性能的监督、分析和改进
数据库的重组织与重构造
9.3 数据结构与算法
? 算法
? 数据结构的基本概念及术语
? 线性表
? 栈
? 队列
? 树与二叉树
? 查找与排序
9.3.1 算法
? 定义,是对特定问题求解步骤的一种描
述。或者说，是为求解某问题而设计的
步骤序列
? 特征,有穷性
确定性
有效性
输入
输出
算法复杂度
评价一个算法优劣的主要标准是：
算法的执行效率与存储需求
算法的效率,指的是时间复杂度（ Time
Complexity）
存储需求,指的是空间复杂度（ Space
Complexity ）
一般情况下，算法中的基本操作重复操作执行的
次数是问题规模 n的某个函数 f(n),算法的时间
复杂度记做 T(n)=O(f(n))
9.3.2 数据结构的基本概念及术语
?数据与数据结构
数据 是描述客观事物的数、字符以及所有能输入
到计算机中并被计算机程序加工处理的符号的集
合
数据元素 是数据的基本元素，即数据集合中的个
体
数据项 具有独立意义的最小数据单位
数据对象 具有相同特性的数据元素的集合，是数
据的子集
结构 被计算机加工的数据元素之间存在的关系
数据结构 带有结构特性的数据元素的集合
?数据的逻辑结构
? 集合
? 线性结构
? 树形结构
? 图状或网状结构
9.3.2 数据结构的基本概念及
术语
?数据的存储结构
一、顺序存储结构
主要特点：
? 结点中只有自身信息域，没有连接信息域，因
此存储密度大，存储空间利用率高
? 可以通过计算直接确定数据结构中第 i个结点
的存储地址 Li，计算公式,L0+（ i-1） m。（其
中 L0为第一个结点的存储地址,m为每个结点
所占用的存储单元个数
? 插入、删除运算不便，会引起大量结点的移动
9.3.2 数据结构的基本概念
及术语
二、链式存储结构
主要特点：
? 结点中除自身信息之外，还有表示连接
信息的指针域，因此比顺序存储密度小，
存储空间利用率低
? 逻辑上相邻的结点物理上不必邻接，可
用于线性表、树、图等多种逻辑结构的
存储表示
? 插入、删除操作灵活方便，不必移动结
点，只要改变结点中的指针值即可
? 数据的运算
? 检索,在数据结构里查找满足一定条件
的结点
? 插入,往数据结构里增加新的结点
? 删除,把指定的结点从数据结构里去掉
? 更新,改变指定结点的一个或多个域的
值
? 排序,保持线性结构的结点序列里结点
数不变，把结点按某种指定的顺序重新排
列
9.3.2 数据结构的基本概念
及术语
9.3.3 线性表
线性表 是最常用的一种数据结构。线性表的
逻辑结构是 n个数据元素的有限序列
（ a1,a2,…,an）
? 顺序表,指用顺序存储结构存储的线性表
? 链表,用链式存储结构存储的线性表
? 栈和队列 —— 是对线性表的插入、删除运算
可以发生的位置加以限制的两种特殊的线性
表
顺序表和一维数组
各种高级语言里的一维数组就是用顺序
方式存储的线性表，因此常用 一维数组
称呼顺序表
若顺序表中结点个数为 n，则：
插入 一个结点平均需要移动之结点个数
为 n/2，算法的时间复杂度是 O(n)；
删除 一个结点平均需移动结点个数为
（ n-1） /2，算法的时间复杂度是 O(n)
链 表
线性链表（单链表）,删除算法的时间复
杂度为 O(n)，其主要执行时间是搜索删除位置
循环链表,指链表的最后一个结点的指针值
指向第一个结点，整个链表形成一个环（如下
图）
…
结点 1 结点 2 结点 n
9.3.4 栈
栈,是一种特殊的线性表，是限定仅在表尾进
行插入和删除运算的线性表，表尾称为栈顶
（ top），表头称为栈底（ bottom）。
空栈,指表中无元素
? 栈中有元素 a1,a2,…,an，如 下页图 所示，称 a1为
栈底元素。新元素进栈要置于 an之上，删除或退栈
先对 an进行，即, 后进先出, （ LIFO） 的操作原则
? 栈的物理存储可以用
顺序存储结构或链式存储结构
? 栈的运算还有取栈顶元素，检查栈是否为空，
清除等。
栈的插入和删除
A
B
A
C
B
A
B
A
F
E
B
A ATOP
TOP
TOP
TOP
TOP
TOP
an
…
a2
a1
进栈 出栈
栈底
栈结构
(3)(1) (2) (5)(4) (6)
9.3.5 队列
队列,是限定所有的插入都在表的一端进
行，所有的删除都在表的另一端进行的线
性表。进行删除的一端叫 队列的头,进行
插入的一端叫 队列的尾,如 下页图 所示。
在队列中，新元素总是加入到队尾，
每次删除的总是对头元素，即当前“最老
的”元素，这就是, 先进先出, （ FIFO）
的操作原则
队列的物理存储可以用：
顺序存储结构，也可用链式存储结构
队列的示意（如下图）
出队列 a1 a2 a3 … an 入队列
头 尾
队列的插入和删除示例
初
态
插
入
A
插
入
B
删
除
A
插
入
C
插
入
D
删
除
B
插
入
E
F
R AF
R
R R
R
R R
F
F F F
F F
B
A
B B B
C C C C
D D D
溢出
7.3.6 树与二叉树
? 树形结构 是一类重要的非线性结构，
树和二叉树是最常见的树形结构
? 树（ Tree）,是一个或多个结点组成
的有限集合 T，有一个特定的结点称为
根（ Root），其余的结点分为 m（ m≥0 ）
个不相交的集合 T1,T2,…, Tm，每个
集合又是一棵树，称作这个根的子树
（ Subtree)
树形结构的常用术语
? 结点的度（ Degree）,一个结点的子树的个数
? 树的度,树中各结点的度的最大值
? 树叶（ Leaf）, 度为 0的结点
? 分支结点,度不为 0的结点
? 双亲（ Parent）、子女（ Child）,结点的各子
树的根称作该结点的子女；相应的该结点称作其
子女的双亲
? 兄弟（ Sibling）,具有相同双亲的结点互为兄
弟
? 结点的层数（ Level）树的深度（ Depth）
? 森林（ Forest）
二 叉 树
? 二叉树（ Binary Tree）,是 n（ n≥ 0)个结点
的有限集合，这个集合或者为空集（ n=0），或
者由一个根结点及两棵不相交的、分别称作这个
根的坐姿树和右子树的二叉树组成
二叉树不是树的特殊情形，二者的 区别：
二叉树为有序树
? 性质,1、在二叉树的 i层上，最多有 2i-1个结点
（ i≥ 1）
2,深度为 k的二叉树最多有 2k-1个结点
(k≥1)
完全二叉树
? 一棵深度为 k且具有 2k-1个结点的二叉
树称为 满二叉树（ Full Binary
Tree ）
? 深度为 k，有 n个结点的二叉树，当且仅
当其妹一个结点都与深度为 k的满二叉
树中编号从 1到 n的结点一一对应时，称
为 完全二叉树
树的二叉树表示
在树（森林）与二叉树间有一个自然的
一一对应的关系，每一棵树都能唯一的
转换到它所对应的二叉树
把树和森林转化成对应的二叉树：
凡是兄弟就用线连起来，然后去掉双亲
到子女的连线，只留下道第一个子女的
连线不去掉
二叉树的存储
二叉树的存储通常采用,链接方式 。每
个结点除存储结点自身的信息外再设置
两个指针域 IIink和 rlink，分别指向结
点的左子女和右子女，当结点的某个指
针为空时，则相应的指针值为空（ NIL）。
结点的形式为：
IIink info rlink
二叉树的遍历
? 遍历一个树形结构是指,按一定次序系统
的访问该结构中的所有结点，使每个结点恰好被
访问一次
? 前序遍历法（ NLR次序）
访问根，按前序遍历左子树，按前序遍历右子树
? 后序遍历法（ LRN次序）
按后序遍历左子树，按后序遍历右子树，访问根
? 中序遍历法（ LNR次序）
按中序遍历左子树，访问根，按中序遍历右子树
9.3.7 查找
? 查找,是数据结构中的基本运算
? 衡量一个查找运算法的主要标志是：
查找过程中对关节码进行的平均比
较次数，或称平均检索长度，以 n的函数
的形式表示,n是数据结构中的结点个数
顺序查找
顺序查找,是线性表的最简单的查找方法
方法,用待查关键码与线性表中各结点的关键
码值逐个比较，若找出相等的关键码值则查找
成功，若找遍所有结点都不相等，则查找失败
优点,对线性表的结点逻辑次序和存储结构无
要求
缺点,平均检索长度大
假设表中各结点被查找的概率相同，即 P=1/n,
则顺序查找成功的 平均查找长度为 (n+1)/2
二分法查找
? 二分法查找,是一种效率较高的线性表查找方法。
要进行二分法查找，线性表结点必须是按关键码值
排号顺序的，且线性表以顺序方式存储
? 方法,首先用要查找的关键码值与线性表中间位
置结点的关键码值相比较，这个中间结点把线性表
分成两个子表，比较相等则查找完成，不等则根据
比较结果确定下一步的查找应在哪个子表中进行，
如此下去，直到找到满足条件的结点
? 优点,平均检索长度小，为 ㏒ 2n。每经过一次关
键码比较，则将查找范围缩小一半，因此经过㏒ 2n
次比较就可完成查找过程
? 缺点,排序线性表花费时间，顺序方式存储插入、
删除不便
9.3.8 排序
排序,是数据处理中经常使用的一种运算
分类：
? 直接插入排序
? 选择排序
? 冒泡排序
? 快速排序
A,直接插入排序 的 基本方法,每步将一个
待排序记录按其关键码值的大小插入到
前面已排序的文件中适当位置上，直到
全部插入为止
B,选择排序 的 基本思想,每一趟在 n-
i+1(i=1,2,…,n-1）个记录中选取关键
码最小的记录作为有序序列中的第 i个记
录。它为最简单且为我们最熟悉的排序
C,冒泡排序 的 基本方法,将待排序的记录
顺次两两比较，若为逆序，则进行交换
D,快速排序,又称分区交换排序，是对冒
泡排序的一种改进。
? 快速排序 的基本方法, 在待排序序列中任取一个
记录，以它为基准用交换的发方法将所有记录分成两
部分，关键码比它小的在一个部分，关键码值比它大
的在另一个部分。再分别对两个部分实施上述过程，
一直重复到排序完成
? 下图为四种排序方法的比较：
排序方法 平均时间 最坏情况 辅助存储
直接插入排序
选择排序
冒泡排序
快速排序
O(n2)
O(n2)
O(n2)
O(n ㏒ 2n)
O(n2)
O(n2)
O(n2)
O(n2)
O(1)
O(1)
O(1)
O(㏒ 2n)
9.4 程序设计基础
? 程序设计语言发展
? 程序设计方法与风格
? 结构化程序设计
? 面向对象的程序设计
程序设计
指令,能被计算机直接识别与执行的指
示计算机进行某种操作的命令,CPU每执
行一条指令，就完成一个基本运算。
程序,指令的序列即让计算机解决某一
问题而写出的一系列指令
程序设计,编写程序的过程
程序设计语言,用于描述计算机所执
行的操作语言
9.4.1 程序设计语言发展
? 机器语言,采用计算机指令格式并以
二进制编码表达各种操作的语言
? 汇编语言,一种符号语言，采用助记
符来表达指令功能
? 高级语言,是一种面向问题的语言
? 第四代语言,是非过程化语言
9.4.2 程序设计方法与风格
良好程序设计风格的侧重：
? 源程序文档如使用的符号名应具有一定的含义，
以便对程序功能的理解；对源程序适当的进行注解，
以便读者理解程序；在程序中利用空格、空行、缩
进等技巧使程序层次清楚
? 对程序中的数据进行适当说明
? 程序中的语句结构应该简单直接，语句不复杂化
? 要对程序的所有输入数据检查其合法性，检查输
入项的各种重要组合的合理性，输入格式要简单，
输入允许默认值，输入一批数据后最好使用结束标
志，在交互式输入 /输出中使用屏幕提示信息格式
9.4.3 结构化程序设计
结构化程序设计的原则
? 自顶向下
? 逐步求精
? 模块化
? 限制使用 GOTO语句
结构化程序设计的基本结构与特点
顺序结构,按照程序语句行的自然顺序，
一条语句一条语句的往后执行程序
选择结构,又称分支结构，它根据设定
的条件，判断应该选择哪一条分支执行相
应的语句序列
循环结构,又称重复结构，它根据给定
的条件，判断是否需要重复执行某一相同
的或相似的程序段
7.4.3 结构化程序设计
结构化程序设计的优点
① 自顶向下逐步求精的方法符合人类解决复杂问题的普遍规律，
可以显著提高软件开发的成功率和生产率
② 先全局后局部、先整体后细节、先抽向后具体的逐步求精过
程开发出的程序有清晰的层次结构，使程序容易阅读和理解
③ 使用单入口单出口控制结构而不使用 GOTO语句，使得程序的
静态结构和它的动态执行情况一致
④ 控制结构有确定逻辑模式，编写程序代码只限于使用很少几
种直截了当的方式，使源程序清晰流畅，易读易懂而且容易
测试
⑤ 程序清晰和模块化使得在修改和重新设计一个软件时可以重
用的代码量最大
⑥ 程序的逻辑结构清晰，有利于程序正确性证明
9.4.4 面向对象的程序设计
面向对象方法的主要特点：
① 从问题域中客观存在的事物出发来构造软件系
统，用对象作为对这些事物的抽象表示，并以
此作为系统的基本构成单位
② 事物的静态特征用对象的属性表示，动态特征
用对象的服务表示
③ 对象的属性与服务结合为一个独立的实体，对
外屏蔽其内部细节，称作封装
④ 把具有相同属性和相同服务的对象归为一类，
类是这些对象的抽象描述，每个对象是它的类
的一个实例
面向对象方法的主要特点：
⑤ 通过在不同程度上运用抽象的原则，可以得到
较一般的类和较特殊的类
⑥ 复杂的对象可以用简单的对象作为其构成部分，
称为聚合
⑦ 对象之间通过消息进行通信，以实现对象之间
的动态联系
⑧ 通过关联表达对象之间的静态关系
9.4.4 面向对象的程序设计
面向对象方法的概念
面向对象：
面向对象 =对象 +类 +继承 +通信
如果一个软件系统是使用这样四个
概念设计和实现的，则认为这个软件系
统是面向对象的。面向对象的程序的每
一组成部分都是对象，计算是通过建立
新的对象和对象之间的通信来执行的
对 象
对象是构成世界的一个独立单位，它具有自己的
静态特征和动态特征。
静态特征,指可以用某种数据来描述的特征
动态特征,指对象所表现的行为或对象所具有的功
能
定义,对象是系统中用来描述客观事物的一个实体，
它是构成系统的一个基本单位。一个对象由一
组属性和对这组属性进行操作的一组方法构成。
属性,用来描述对象静态特征的一个数据项
方法,用来描述对象动态特征的一个操作序列
消息和方法
? 一个系统由若干个对象组成，各个对象之
间相互联系、相互作用。
? 计算机系统中，消息就是对象之间的纽带，
是用来通知、命令或请求对象执行某个处
理或回答某些信息。
? 消息可以是 数据流,也可以是 控制流 。
? 一条消息可以发送给不同的对象，而消息
的解释则完全由接收对象完成。不同的对
象对相同形式的消息可以有不同的解释
类和实例
类和对象之间的关系 如同一个模具与
用这个模具铸造出来的铸件之间的关系。
类给出了属于该类的全部对象的抽象定义，
而对象则是符合这种定义的一个实体。
一个对象又称为类的一个实例（ Instance）
类也可称作对象的模板（ Template）
继 承 性
? 定义,特殊类的对象拥有其一般类的全
部属性与方法，称作特殊类对一般类的
继承
? 继承关系是传递的
? 继承性对于软件重用有很大益处
封 装 性
封装具有两个涵义：
一、是把对象的全部属性和全部方法结合
在一起，形成一个不可分割的独立单位
（即对象）
二、也称作“信息隐蔽”，即尽可能隐蔽
对象的内部细节，对外形成一个边界，
只保留有限的对外接口使之与外部发生
联系
多 态 性
对象的多态性：
指在一般类中定义的属性或方法被特殊
类继承之后，可以具有不同的数据类型
表现出不同的行为。这使得同一个属性
或方法名在一般类及其各个特殊类中具
有不同的语义
9.5 多媒体技术简介
? 多媒体技术的基本概念
? 多媒体计算机系统
? 多媒体计算机软件系统
? 多媒体信息的数字化和压缩技术
9.5.1 多媒体技术的基本概念
定义：指信息表示媒体的多样化。
多媒体的类型 感觉媒体
表示媒体
显示媒体
传输媒体
存储媒体
多媒体技术就是利用计算机把文本、声音、
视频、动画、图形和图像等多种媒体进行
综合处理，使多种信息建立逻辑连接，集
成为一个具有交互性的系统
多媒体技术的特征
? 信息载体的多样性
? 交互性
? 集成性
? 实时性
多媒体信息中的媒体元素的类型
? 文本（ Text）
? 图形（ Graphic）
? 图像（ Image）
? 音频
? 动画
? 视频
多媒体信息处理的关键技术
? 视频和音频数据压缩和解压缩技术
关于压缩编码的国际标准有：
JPEG标准
电视电话 /会议电视 P*64Kbit/s (CCITT
H.261)标准
MPEG-1标准
? 多媒体硬件系统的专用芯片
? 大容量的外部存储器
? 多媒体同步技术
多媒体技术的应用领域
? 教育与培训
? 桌面出版
? 多媒体电子出版物
? 多媒体通信
? 多媒体声光艺术品的创作
9.5.2 多媒体计算机系统
多媒体计算机系统的组成（如下图）
多
媒
体
计
算
机
系
统
软件系统
硬件系统
多媒体应用软件
媒体处理系统工具软件
多媒体数据处理软件
多媒体操作系统
多媒体驱动软件
多媒体输入 /输出控制卡及接口
多媒体计算机硬件
多媒体外围设备
多媒体计算机硬件系统
? 主机,常规的主板,CPU及 VGA适配卡、多功能
卡等
? 多媒体适配卡,音频卡、视频卡、图形卡和压
缩卡等
? 外部存储设备,软盘驱动器、硬盘驱动器和
CD-ROM驱动器
? 输入设备
? 输出设备
9.5.3多媒体计算机软件系统
多媒体应用程序
多媒体处理系统工具
多媒体操作系统
（媒体控制接口）
音频 /视频核心处理
音频 /视频设备驱动程序
音频 /视频设备
多
媒
体
计
算
机
软
件
的
层
次
结
构
（
如
右
图
）
第五层
第四层
第三层
第二层
第一层
9.5.4 多媒体信息的数字化和压
缩技术
音频信息
?声音的特征
?模拟音频和数字音频
衡量一个数字声音波形的质量有：采样频率、采
样精度、声道数三个要素
?数字音频文件的存储格式
?数字音频文件的存储量
存储量 =采样频率 × 量化位数 /8× 声道数 × 时间
图像信息
图像信息的性能指标
? 分辨率
? 图像深度和显示深度
? 图像文件的大小
图像文件的存储格式
① BMP格式 PCX格式
② GIF格式 TIF格式
③ JPG和 PIC格式 PCD格式
④ CDR格式 PSD格式
⑤ IFF格式 DIF格式
视频信息
? 视频的彩色空间表示
RGB彩色空间
YUV和 YIQ彩色空间
? 模拟视频标准 （ NTSC制式 PAL制式
SECAM制式）
? 数字视频
? 视频序列的时间码
? 数字视频标准与文件格式
数字视频标准与文件格式
? MPEG标准
MPEG-1（ 1992年正式发布）
MPEG-2（ 1994年制定）
MPEG-4（ 1999年正式发布）
? AVI格式
? PM格式
? Quick Time格式
数据压缩技术
? 无损压缩
行程编码（ RLE）
Huffman编码
算术编码
LZW编码
? 有损压缩
三种数据压缩国际标准,JPEG-静止图像压缩标
准,MPEG-运动图像压缩编码标准,H.261-视频
通信编码标准
