? 什么是数据结构
? 抽象数据类型及面向对象概念
? 数据结构的抽象层次
? 用 C++描述面向对象程序
? 算法定义
? 模板
? 性能分析与度量
“学生”表格
学 号 姓 名 性别 籍 贯 出生年月
1 98 131 刘激扬 男 北 京 19 79.12
2 98 164 衣春生 男 青 岛 19 79.07
3 98 165 卢声凯 男 天 津 19 81.02
4 98 182 袁秋慧 女 广 州 19 80.10
5 98 224 洪 伟 男 太 原 19 81.01
6 98 236 熊南燕 女 苏 州 19 80.03
7 98 297 宫 力 男 北 京 19 81.01
8 98 310 蔡晓莉 女 昆 明 19 81.02
9 98 318 陈 健 男 杭 州 19 79.12
“课程”表格
课程编号 课 程 名 学时
024002 程序设计基础 64
024010 汇编语言 48
024016 计算机原理 64
024020 数据结构 64
024021 微机技术 64
024024 操作系统 48
024026 数据库原理 48
“选课单” 包含如下信息
学号 课程编号 成绩 时间
学生选课系统中实体构成的网状关系
学生
(学号,姓名,性别,籍贯 )
课程
(课程号,课程名,学分 )
选课
(学号,课程号,成绩 )
UNIX文件系统的系统结构图
/ (root)
bin lib user etc
math ds sw yin tao xie
Stack.cppQueue.cpp Tree.cpp
数据 （ data）
? 数据是信息的载体，是描述客观事物
的数、字符、以及所有能输入到计算
机中，被计算机程序识别和处理的符
号的集合。
? 数值性数据
? 非数值性数据
数据对象 (data object)
? 数据的子集。具有相同性质的数据成
员（数据元素）的集合。
? 整数数据对象
N = { 0,?1,?2,… }
? 学生数据对象
什么是数据结构
定义,
由某一数据对象及该对象中所有
数据成员之间的关系组成。记为：
Data_Structure = {D,R}
其中,D 是某一数据对象,R 是该
对象中所有数据成员之间的关系的有
限集合。
N 个网点之间的连通关系
树形关系 网状关系
1
5
2
4
36
1
5
2
4
36
抽象数据类型及面向对象概念
? 数据类型
定义,一组性质相同的值的集合,以
及定义于这个值集合上的一组操作
的总称,
? C语言中的数据类型
char int float double void
字符型 整型 浮点型 双精度型 无值
抽象数据类型
(ADTs,Abstract Data Types)
?由用户定义，用以表示应用问题的
数据模型
?由 基本的数据类型 组成,并包括 一组
相关的服务 （或称操作）
?信息隐蔽 和 数据封装,使用与实现
相分离
抽
象
数
据
类
型
查找 登录 删除 修改
符 号 表
自然数的抽象数据类型定义
ADT NaturalNumber is
objects,一个整数的有序子集合,它开始于 0,
结束于机器能表示的最大整数 (MaxInt)。
Function,对于所有的 x,y ? NaturalNumber;
False,True ? Boolean,+,-,<,==,=等
都是可用的服务。
Zero( ), NaturalNumber 返回自然数 0
IsZero(x), if (x==0) 返回 True
Boolean else 返回 False
Add (x,y), if (x+y<=MaxInt)返回 x+y
NaturalNumber else 返回 MaxInt
Subtract (x,y), if (x < y) 返回 0
NaturalNumber else 返回 x - y
Equal (x,y), if (x==y) 返回 True
Boolean else 返回 False
Successor (x), if (x==MaxInt) 返回 x
NaturalNumber else 返回 x+1
end NaturalNumber
面向对象的概念
? 面向对象 = 对象＋类＋继承＋通信
? 对象
? 在应用问题中出现的各种 实体,
事件, 规格说明 等
? 由一组 属性值 和在这组值上的一
组 服务 （或称操作）构成
? 类 (class)，实例 (instance)
? 具有 相同属性和服务 的对象归于
同一类，形成类
? 类中的对象为该类的实例
属性
aPoint1 aPoint2
aPoint3 aPoint4
服务
Draw( )
move(?x,?y)
contains(aPoint)
属性值 属性值
quadrilateral1 quadrilateral2
(35,10) (50,10)
(35,25) (50,25)
(45,65) (50,45)
(65,66) (60,70)
Draw( )
move(?x,?y)
contains(aPoint)
Draw( )
move(?x,?y)
contains(aPoint)
服务 服务
四边形类及其对象
quadrilateral
? 继承
? 派生类,四边形，三角形,…
子类 特化类 (特殊化类 )
? 基类,多边形
父类 泛化类 (一般化类 )
? 通信
? 消息传递
Draw( )
move(?x,?y)
contains(aPoint)
Polygon
referencePoint
Vertices
Polygon 类
referencePoint
Vertices
Draw( )
move(?x,?y)
contains(aPoint)
Polygon的子类
Quadrilateral类
Quadrilateral
? 线性结构
?直接存取类 数组,文件
?顺序存取类 表,栈,队列,优先队列
?广义索引类 线性索引,搜索树
? 非线性结构
?层次结构类 树，二叉树，堆
?群结构类 集合，图
数据结构的抽象层次
线性结构
树形结构
树 二叉树 二叉搜索树
14131211
2 3 4
5 6 7 8 9 10 3
1 5
8
7
10
11
9
987
4 5 6
62 3 13
1
bin dev etc lib user
1
堆结构
,最大”堆, 最小”堆
12
3 5 4 8
7
11
10
2
9
16
4
10
1211
5
1
2
36
98
7
群聚类
图结构 网络结构
1 2
5
6
4
3
1 2
5 4
3611
33
18
14
6
6
5
16
19
21
数据的两个视图
? 数据的逻辑结构 面向应用
? 数据的物理结构 面向存储
? 顺序结构
? 链表结构
? 散列结构
? 索引结构
? 在该数据结构上的操作
为什么选用面向对象及 C++语言
讲述数据结构？
? PASCAL与 C描述是面向过程的。
? C++描述兼有面向过程与面向对
象的特点。
? Java描述是面向对象的。
? 用面向对象及 C++描述与国际接
轨，是市场需要 。
用 C++描述面向对象程序
? C++的函数特征
? C++的数据声明
? C++的作用域
? C++的类
? C++的对象
? C++的输入 /输出
? C++的函数
? C++的参数传递
? C++的函数名重载和
操作符重载
? C++的动态存储分配
? 友元 (friend)函数
? 内联 (inline)函数
? 结构 (struct)与类
? 联合 (Union)与类
算法定义
? 定义,一个有穷的指令集,这些指令为
解决某一特定任务规定了一个运算序列
? 特性：
? 输入 有 0个或多个输入
? 输出 有一个或多个输出 (处理结果 )
? 确定性 每步定义都是确切、无歧义的
? 有穷性 算法应在执行有穷步后结束
? 有效性 每一条运算应足够基本
? 事例学习,选择排序问题
? 明确问题,递增排序
? 解决方案,逐个选择最小数据
? 算法框架：
for ( int i = 0; i < n-1; i++ ) { //n-1趟
从 a[i]检查到 a[n-1];
若最小整数在 a[k],交换 a[i]与 a[k];
}
? 细化程序,程序 SelectSort
算法设计 自顶向下，逐步求精
void selectSort ( int a[ ],const int n ) {
//对 n个整数 a[0],a[1],…,a[n -1]按递增顺序排序
for ( int i = 0; i < n-1; i++ ) {
int k = i;
//从 a[i]查到 a[n-1],找最小整数,在 a[k]
for ( int j = i+1; j < n; j++ )
if ( a[j] < a[k] ) k = j;
int temp = a[i]; a[i] = a[k]; a[k] = temp;
}
}
模板 (template)
定义
适合 多种数据类型 的类定义或算法，
在特定环境下通过简单地代换，变成
针对具体某种数据类型 的类定义或算
法
用模板定义用于排序的数据表类
#include <iostream.h>
template <class Type>
class dataList {
private:
Type *Element;
int ArraySize;
void Swap (int m1,int m2);
int MaxKey (int low,int high);
public:
dataList (int size = 10), ArraySize (size),
Element (new Type [Size]) { }
~dataList ( ) {delete [ ] Element;}
void Sort ( );
friend ostream& operator << (ostream&
outStream,datalist<Type>& outList);
friend istream& operator >> (istream&
inStream,datalist<Type>& inList);
}
类中所有操作作为模板函数的实现
#include,datalist.h”
template <class Type> void dataList
<Type>,,Swap (int m1,int m2) {
//交换由 m1,m2为下标的数组元素的值
Type temp = Element [m1];
Element [m1] = Element [m2];
Element [m2] = temp;
}
template <class Type>
int dataList<Type>::
MaxKey (int low,int high) {
//查找数组 Element[low]到 Element[high]
//中的最大值，函数返回其位置
int max = low;
for (int k = low+1,k <= high,k++)
if ( Element[max] < Element[k] )
max = k;
return max;
}
template <class Type> ostream&
operator<< (ostream& OutStream,
dataList<Type> OutList) {
OutStream <<,数组内容, \n”;
for (int i = 0; i < OutList.ArraySize; i++)
OutStream << OutList.Element[i] << ‘ ’;
OutStream << endl;
OuStream <<,数组当前大小,, <<
OutList.ArraySize << endl;
return OutStream;
}
template <class Type>
istream& operator >> (istream& InStream,
dataList<Type> InList) {
cout <<,录入数组当前大小,,;
Instream >> InList.ArraySize;
cout <<,录入数组元素值, \n”;
for (int i = 0; i < InList.ArraySize; i++) {
cout <<,元素, << i <<,:” ;
InStream >> InList.Element[i];
}
return InStream;
}
template <class Type>
void dataList<Type>::Sort ( ) {
//按非递减顺序对 ArraySize个关键码
//Element[0]到 Element[ArraySize-1]排序
for ( int i = ArraySize -1; i > 0; i-- ) {
int j = MaxKey (0,i);
if ( j != i ) swap (j,i);
}
}
使用模板的选择排序算法的主函数
#include,selecttm.h”
const int SIZE = 10;
int main ( ) {
dataList <int> TestList (SIZE);
cin >> TestList;
cout << TestList << endl;
TestList.Sort ( );
cout << TestList << endl;
return 0;
}
性能分析与度量
? 算法的性能标准
? 算法的后期测试
? 算法的事前估计
算法的性能标准
? 正确性
? 可使用性
? 可读性
? 效率
? 健壮性
算法的后期测试
在算法中的某些部位插装时间函数
time ( )
测定算法完成某一功能所花费时间
顺序搜索 (Sequenial Search)
int seqsearch ( int a[ ],int n,int x ) {
//在 a[0],…,a[n -1]中搜索 x
int i = 0;
while ( i < n && a[i] != x )
i++;
if ( i == n ) return -1;
return i;
}
插装 time( ) 的计时程序
double start,stop;
time (&start);
int k = seqsearch (a,n,x);
time (&stop);
double runTime = stop - start;
cout << " " << n << " " <<
runTime << endl;
算法的事前估计
? 空间复杂度
? 时间复杂度
空间复杂度度量
? 存储空间的固定部分
程序指令代码的空间，常数、简单变量、
定长成分 (如数组元素、结构成分、对象
的数据成员等 )变量所占空间
? 可变部分
尺寸与实例特性有关的成分变量所占空
间、引用变量所占空间、递归栈所用空
间、通过 new和 delete命令动态使用空间
时间复杂度度量
? 编译时间
? 运行时间
? 程序步
?语法上或语义上有意义的一段指令
序列
?执行时间与实例特性无关
?例如,声明语句,程序步数为 0; 表
达式,程序步数为 1
? 程序步确定方法
? 插入计数全局变量 count
? 建表,列出个语句的程序步
例 以迭代方式求累加和的函数
float sum ( float a[ ],int n ) {
float s = 0.0;
for ( int i = 0; i < n; i++ )
s += a[i];
return s;
}
在求累加和程序中加入 count语句
float sum ( float a[ ],int n ) {
float s = 0.0;
count++; //count 统计执行语句条数
for ( int i = 0; i < n; i++ ) {
count++; //针对 for 语句
s += a[i];
count++;
} //针对赋值语句
count++; //针对 for 的最后一次
count++; //针对 return 语句
return s;
} 执行结束得 程序步数 count = 2*n+3
程序的简化形式
void sum ( float a[ ],int n ) {
for ( int i = 0; i < n; i++ )
count += 2;
count += 3;
}
注意,
一个语句本身的程序步数可能不等
于该语句一次执行所具有的程序步数。
例如：赋值语句 x = sum (R,n)
本身的程序步数为 1；
一次执行对函数 sum (R,n) 的调用
需要的程序步数为 2*n+3；
一次执行的程序步数为
1+2*n+3 = 2*n+4
计算 累加和 程序
程序步数 计算工作表格
程 序 语 句
一次执行所
需程序步数
执行
频度
程序
步数
{ 0 1 0
float s = 0.0 ; 1 1 1
for ( int i=0 ; i<n ; i++ ) 1 n+1 n+1
s += a[ i] ; 1 n n
return s ; 1 1 1
} 0 1 0
总程序步数 2n+3
时间复杂度的渐进表示法
? 大 O表示法
? 加法规则 针对并列程序段
T(n,m) = T1 (n) + T2 (m)
= O(max (f (n),g (m)))
c < log2n < n < nlog2n < n2 < n3 <
2n < 3n < n!
? 乘法规则 针对嵌套程序段
T (n,m) = T1 (n) * T2 (m)
= O(f (n)*g (m))
? 渐进的空间复杂度
S (n) = O(f (n))
? 两个并列循环的例子
void exam ( float x[ ][ ],int m,int n ) {
float sum [ ];
for ( int i = 0; i < m; i++ ) { //x中各行
sum[i] = 0.0; //数据累加
for ( int j = 0; j < n; j++ )
sum[i] += x[i][j];
}
for ( i = 0; i < m; i++ ) //打印各行数据和
cout << i <<,,, <<sum [i] << endl;
}
渐进时间复杂度为 O(max (m*n,m))
template <class Type> //起泡排序
void dataList<Type>,,bubbleSort ( ) {
//对表逐趟比较,ArraySize 是表当前长度
int i = 1; int exchange = 1;
//当 exchange 为 0 则停止排序
while ( i < ArraySize && exchange ) {
BubbleExchange ( i,exchange );
i++;
} //一趟比较
}
template <class Type>
void dataList<Type>::
BubbleExchange(int i,int & exchange ){
exchange = 0; //假定元素未交换
for ( int j = ArraySize-1; j>=i; j--)
if ( Element[j-1] > Element[j] ) {
Swap ( j -1,j ); //发生逆序,交换
exchange = 1; //做“发生交换”标
志
}
}
渐进时间复杂度
O(f (n)*g (n)) = O(n2)
?
?
?
???1
1 2
1n
i
)n ( ni)(n?
BubblrSort n-1趟
BubbleExchange ( )
n-i次比较
? 抽象数据类型及面向对象概念
? 数据结构的抽象层次
? 用 C++描述面向对象程序
? 算法定义
? 模板
? 性能分析与度量
“学生”表格
学 号 姓 名 性别 籍 贯 出生年月
1 98 131 刘激扬 男 北 京 19 79.12
2 98 164 衣春生 男 青 岛 19 79.07
3 98 165 卢声凯 男 天 津 19 81.02
4 98 182 袁秋慧 女 广 州 19 80.10
5 98 224 洪 伟 男 太 原 19 81.01
6 98 236 熊南燕 女 苏 州 19 80.03
7 98 297 宫 力 男 北 京 19 81.01
8 98 310 蔡晓莉 女 昆 明 19 81.02
9 98 318 陈 健 男 杭 州 19 79.12
“课程”表格
课程编号 课 程 名 学时
024002 程序设计基础 64
024010 汇编语言 48
024016 计算机原理 64
024020 数据结构 64
024021 微机技术 64
024024 操作系统 48
024026 数据库原理 48
“选课单” 包含如下信息
学号 课程编号 成绩 时间
学生选课系统中实体构成的网状关系
学生
(学号,姓名,性别,籍贯 )
课程
(课程号,课程名,学分 )
选课
(学号,课程号,成绩 )
UNIX文件系统的系统结构图
/ (root)
bin lib user etc
math ds sw yin tao xie
Stack.cppQueue.cpp Tree.cpp
数据 （ data）
? 数据是信息的载体，是描述客观事物
的数、字符、以及所有能输入到计算
机中，被计算机程序识别和处理的符
号的集合。
? 数值性数据
? 非数值性数据
数据对象 (data object)
? 数据的子集。具有相同性质的数据成
员（数据元素）的集合。
? 整数数据对象
N = { 0,?1,?2,… }
? 学生数据对象
什么是数据结构
定义,
由某一数据对象及该对象中所有
数据成员之间的关系组成。记为：
Data_Structure = {D,R}
其中,D 是某一数据对象,R 是该
对象中所有数据成员之间的关系的有
限集合。
N 个网点之间的连通关系
树形关系 网状关系
1
5
2
4
36
1
5
2
4
36
抽象数据类型及面向对象概念
? 数据类型
定义,一组性质相同的值的集合,以
及定义于这个值集合上的一组操作
的总称,
? C语言中的数据类型
char int float double void
字符型 整型 浮点型 双精度型 无值
抽象数据类型
(ADTs,Abstract Data Types)
?由用户定义，用以表示应用问题的
数据模型
?由 基本的数据类型 组成,并包括 一组
相关的服务 （或称操作）
?信息隐蔽 和 数据封装,使用与实现
相分离
抽
象
数
据
类
型
查找 登录 删除 修改
符 号 表
自然数的抽象数据类型定义
ADT NaturalNumber is
objects,一个整数的有序子集合,它开始于 0,
结束于机器能表示的最大整数 (MaxInt)。
Function,对于所有的 x,y ? NaturalNumber;
False,True ? Boolean,+,-,<,==,=等
都是可用的服务。
Zero( ), NaturalNumber 返回自然数 0
IsZero(x), if (x==0) 返回 True
Boolean else 返回 False
Add (x,y), if (x+y<=MaxInt)返回 x+y
NaturalNumber else 返回 MaxInt
Subtract (x,y), if (x < y) 返回 0
NaturalNumber else 返回 x - y
Equal (x,y), if (x==y) 返回 True
Boolean else 返回 False
Successor (x), if (x==MaxInt) 返回 x
NaturalNumber else 返回 x+1
end NaturalNumber
面向对象的概念
? 面向对象 = 对象＋类＋继承＋通信
? 对象
? 在应用问题中出现的各种 实体,
事件, 规格说明 等
? 由一组 属性值 和在这组值上的一
组 服务 （或称操作）构成
? 类 (class)，实例 (instance)
? 具有 相同属性和服务 的对象归于
同一类，形成类
? 类中的对象为该类的实例
属性
aPoint1 aPoint2
aPoint3 aPoint4
服务
Draw( )
move(?x,?y)
contains(aPoint)
属性值 属性值
quadrilateral1 quadrilateral2
(35,10) (50,10)
(35,25) (50,25)
(45,65) (50,45)
(65,66) (60,70)
Draw( )
move(?x,?y)
contains(aPoint)
Draw( )
move(?x,?y)
contains(aPoint)
服务 服务
四边形类及其对象
quadrilateral
? 继承
? 派生类,四边形，三角形,…
子类 特化类 (特殊化类 )
? 基类,多边形
父类 泛化类 (一般化类 )
? 通信
? 消息传递
Draw( )
move(?x,?y)
contains(aPoint)
Polygon
referencePoint
Vertices
Polygon 类
referencePoint
Vertices
Draw( )
move(?x,?y)
contains(aPoint)
Polygon的子类
Quadrilateral类
Quadrilateral
? 线性结构
?直接存取类 数组,文件
?顺序存取类 表,栈,队列,优先队列
?广义索引类 线性索引,搜索树
? 非线性结构
?层次结构类 树，二叉树，堆
?群结构类 集合，图
数据结构的抽象层次
线性结构
树形结构
树 二叉树 二叉搜索树
14131211
2 3 4
5 6 7 8 9 10 3
1 5
8
7
10
11
9
987
4 5 6
62 3 13
1
bin dev etc lib user
1
堆结构
,最大”堆, 最小”堆
12
3 5 4 8
7
11
10
2
9
16
4
10
1211
5
1
2
36
98
7
群聚类
图结构 网络结构
1 2
5
6
4
3
1 2
5 4
3611
33
18
14
6
6
5
16
19
21
数据的两个视图
? 数据的逻辑结构 面向应用
? 数据的物理结构 面向存储
? 顺序结构
? 链表结构
? 散列结构
? 索引结构
? 在该数据结构上的操作
为什么选用面向对象及 C++语言
讲述数据结构？
? PASCAL与 C描述是面向过程的。
? C++描述兼有面向过程与面向对
象的特点。
? Java描述是面向对象的。
? 用面向对象及 C++描述与国际接
轨，是市场需要 。
用 C++描述面向对象程序
? C++的函数特征
? C++的数据声明
? C++的作用域
? C++的类
? C++的对象
? C++的输入 /输出
? C++的函数
? C++的参数传递
? C++的函数名重载和
操作符重载
? C++的动态存储分配
? 友元 (friend)函数
? 内联 (inline)函数
? 结构 (struct)与类
? 联合 (Union)与类
算法定义
? 定义,一个有穷的指令集,这些指令为
解决某一特定任务规定了一个运算序列
? 特性：
? 输入 有 0个或多个输入
? 输出 有一个或多个输出 (处理结果 )
? 确定性 每步定义都是确切、无歧义的
? 有穷性 算法应在执行有穷步后结束
? 有效性 每一条运算应足够基本
? 事例学习,选择排序问题
? 明确问题,递增排序
? 解决方案,逐个选择最小数据
? 算法框架：
for ( int i = 0; i < n-1; i++ ) { //n-1趟
从 a[i]检查到 a[n-1];
若最小整数在 a[k],交换 a[i]与 a[k];
}
? 细化程序,程序 SelectSort
算法设计 自顶向下，逐步求精
void selectSort ( int a[ ],const int n ) {
//对 n个整数 a[0],a[1],…,a[n -1]按递增顺序排序
for ( int i = 0; i < n-1; i++ ) {
int k = i;
//从 a[i]查到 a[n-1],找最小整数,在 a[k]
for ( int j = i+1; j < n; j++ )
if ( a[j] < a[k] ) k = j;
int temp = a[i]; a[i] = a[k]; a[k] = temp;
}
}
模板 (template)
定义
适合 多种数据类型 的类定义或算法，
在特定环境下通过简单地代换，变成
针对具体某种数据类型 的类定义或算
法
用模板定义用于排序的数据表类
#include <iostream.h>
template <class Type>
class dataList {
private:
Type *Element;
int ArraySize;
void Swap (int m1,int m2);
int MaxKey (int low,int high);
public:
dataList (int size = 10), ArraySize (size),
Element (new Type [Size]) { }
~dataList ( ) {delete [ ] Element;}
void Sort ( );
friend ostream& operator << (ostream&
outStream,datalist<Type>& outList);
friend istream& operator >> (istream&
inStream,datalist<Type>& inList);
}
类中所有操作作为模板函数的实现
#include,datalist.h”
template <class Type> void dataList
<Type>,,Swap (int m1,int m2) {
//交换由 m1,m2为下标的数组元素的值
Type temp = Element [m1];
Element [m1] = Element [m2];
Element [m2] = temp;
}
template <class Type>
int dataList<Type>::
MaxKey (int low,int high) {
//查找数组 Element[low]到 Element[high]
//中的最大值，函数返回其位置
int max = low;
for (int k = low+1,k <= high,k++)
if ( Element[max] < Element[k] )
max = k;
return max;
}
template <class Type> ostream&
operator<< (ostream& OutStream,
dataList<Type> OutList) {
OutStream <<,数组内容, \n”;
for (int i = 0; i < OutList.ArraySize; i++)
OutStream << OutList.Element[i] << ‘ ’;
OutStream << endl;
OuStream <<,数组当前大小,, <<
OutList.ArraySize << endl;
return OutStream;
}
template <class Type>
istream& operator >> (istream& InStream,
dataList<Type> InList) {
cout <<,录入数组当前大小,,;
Instream >> InList.ArraySize;
cout <<,录入数组元素值, \n”;
for (int i = 0; i < InList.ArraySize; i++) {
cout <<,元素, << i <<,:” ;
InStream >> InList.Element[i];
}
return InStream;
}
template <class Type>
void dataList<Type>::Sort ( ) {
//按非递减顺序对 ArraySize个关键码
//Element[0]到 Element[ArraySize-1]排序
for ( int i = ArraySize -1; i > 0; i-- ) {
int j = MaxKey (0,i);
if ( j != i ) swap (j,i);
}
}
使用模板的选择排序算法的主函数
#include,selecttm.h”
const int SIZE = 10;
int main ( ) {
dataList <int> TestList (SIZE);
cin >> TestList;
cout << TestList << endl;
TestList.Sort ( );
cout << TestList << endl;
return 0;
}
性能分析与度量
? 算法的性能标准
? 算法的后期测试
? 算法的事前估计
算法的性能标准
? 正确性
? 可使用性
? 可读性
? 效率
? 健壮性
算法的后期测试
在算法中的某些部位插装时间函数
time ( )
测定算法完成某一功能所花费时间
顺序搜索 (Sequenial Search)
int seqsearch ( int a[ ],int n,int x ) {
//在 a[0],…,a[n -1]中搜索 x
int i = 0;
while ( i < n && a[i] != x )
i++;
if ( i == n ) return -1;
return i;
}
插装 time( ) 的计时程序
double start,stop;
time (&start);
int k = seqsearch (a,n,x);
time (&stop);
double runTime = stop - start;
cout << " " << n << " " <<
runTime << endl;
算法的事前估计
? 空间复杂度
? 时间复杂度
空间复杂度度量
? 存储空间的固定部分
程序指令代码的空间，常数、简单变量、
定长成分 (如数组元素、结构成分、对象
的数据成员等 )变量所占空间
? 可变部分
尺寸与实例特性有关的成分变量所占空
间、引用变量所占空间、递归栈所用空
间、通过 new和 delete命令动态使用空间
时间复杂度度量
? 编译时间
? 运行时间
? 程序步
?语法上或语义上有意义的一段指令
序列
?执行时间与实例特性无关
?例如,声明语句,程序步数为 0; 表
达式,程序步数为 1
? 程序步确定方法
? 插入计数全局变量 count
? 建表,列出个语句的程序步
例 以迭代方式求累加和的函数
float sum ( float a[ ],int n ) {
float s = 0.0;
for ( int i = 0; i < n; i++ )
s += a[i];
return s;
}
在求累加和程序中加入 count语句
float sum ( float a[ ],int n ) {
float s = 0.0;
count++; //count 统计执行语句条数
for ( int i = 0; i < n; i++ ) {
count++; //针对 for 语句
s += a[i];
count++;
} //针对赋值语句
count++; //针对 for 的最后一次
count++; //针对 return 语句
return s;
} 执行结束得 程序步数 count = 2*n+3
程序的简化形式
void sum ( float a[ ],int n ) {
for ( int i = 0; i < n; i++ )
count += 2;
count += 3;
}
注意,
一个语句本身的程序步数可能不等
于该语句一次执行所具有的程序步数。
例如：赋值语句 x = sum (R,n)
本身的程序步数为 1；
一次执行对函数 sum (R,n) 的调用
需要的程序步数为 2*n+3；
一次执行的程序步数为
1+2*n+3 = 2*n+4
计算 累加和 程序
程序步数 计算工作表格
程 序 语 句
一次执行所
需程序步数
执行
频度
程序
步数
{ 0 1 0
float s = 0.0 ; 1 1 1
for ( int i=0 ; i<n ; i++ ) 1 n+1 n+1
s += a[ i] ; 1 n n
return s ; 1 1 1
} 0 1 0
总程序步数 2n+3
时间复杂度的渐进表示法
? 大 O表示法
? 加法规则 针对并列程序段
T(n,m) = T1 (n) + T2 (m)
= O(max (f (n),g (m)))
c < log2n < n < nlog2n < n2 < n3 <
2n < 3n < n!
? 乘法规则 针对嵌套程序段
T (n,m) = T1 (n) * T2 (m)
= O(f (n)*g (m))
? 渐进的空间复杂度
S (n) = O(f (n))
? 两个并列循环的例子
void exam ( float x[ ][ ],int m,int n ) {
float sum [ ];
for ( int i = 0; i < m; i++ ) { //x中各行
sum[i] = 0.0; //数据累加
for ( int j = 0; j < n; j++ )
sum[i] += x[i][j];
}
for ( i = 0; i < m; i++ ) //打印各行数据和
cout << i <<,,, <<sum [i] << endl;
}
渐进时间复杂度为 O(max (m*n,m))
template <class Type> //起泡排序
void dataList<Type>,,bubbleSort ( ) {
//对表逐趟比较,ArraySize 是表当前长度
int i = 1; int exchange = 1;
//当 exchange 为 0 则停止排序
while ( i < ArraySize && exchange ) {
BubbleExchange ( i,exchange );
i++;
} //一趟比较
}
template <class Type>
void dataList<Type>::
BubbleExchange(int i,int & exchange ){
exchange = 0; //假定元素未交换
for ( int j = ArraySize-1; j>=i; j--)
if ( Element[j-1] > Element[j] ) {
Swap ( j -1,j ); //发生逆序,交换
exchange = 1; //做“发生交换”标
志
}
}
渐进时间复杂度
O(f (n)*g (n)) = O(n2)
?
?
?
???1
1 2
1n
i
)n ( ni)(n?
BubblrSort n-1趟
BubbleExchange ( )
n-i次比较
