数据结构
DATA
STRUCTURE
—— C++ 描述
什么是数据结构
抽象数据类型及面向对象概念
数据结构的抽象层次
用 C++描述面向对象程序
算法定义
模板
性能分析与度量
“学生”表格学 号 姓 名 性别 籍 贯 出生年月
1 98 13 1 刘激扬 男 北 京 19 79,12
2 98 16 4 衣春生 男 青 岛 19 79,07
3 98 16 5 卢声凯 男 天 津 19 81,02
4 98 18 2 袁秋慧 女 广 州 19 80,10
5 98 20 3 林德康 男 上 海 19 80,05
6 98 22 4 洪 伟 男 太 原 19 81,01
7 98 23 6 熊南燕 女 苏 州 19 80,03
8 98 29 7 宫 力 男 北 京 19 81,01
9 98 31 0 蔡晓莉 女 昆 明 19 81,02
10 98 31 8 陈 健 男 杭 州 19 79,12
“课程”表格课程编号 课 程 名 学时
0 2 4 0 0 2 程序设计基础 6 4
0 2 4 0 1 0 汇编语言 4 8
0 2 4 0 1 6 计算机原理 6 4
0 2 4 0 2 0 数据结构 6 4
0 2 4 0 2 1 微机技术 6 4
0 2 4 0 2 4 操作系统 4 8
0 2 4 0 2 6 数据库原理 4 8
选课单包含如下信息学 号 课程编号 成 绩 时 间学生选课系统中实体构成的网状关系
UNIX文件系统的系统结构图
数据,数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。
数值性数据
非数值性数据
数据对象,数据的子集。具有相同性质的数据成员（数据元素）的集合。
整数数据对象 N = { 0,?1,?2,… }
学生数据对象什么是数据结构定义,由 某一数据对象 及 该对象中所有数据成员 之间的关系组成。记为：
Data_Structure = {D,R}
其中,D是某一数据对象,R是该对象中所有数据成员之间的关系的有限集合。
n个网站之间的连通关系树形关系 网状关系抽象数据类型及面向对象概念
数据类型定义,一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称,
C语言中的数据类型
char int float double void
字符型 整型 浮点型 双精度型 无值抽象数据类型
(ADTs,Abstract Data Types)
由用户定义，用以表示应用问题的数据模型
由 基本的数据类型 组成,并包括 一组相关的服务 （或称操作）
信息隐蔽 和 数据封装,使用与实现相分离自然数的抽象数据类型定义
ADT NaturalNumber is
objects,一个整数的有序子集合,它开始于 0,
结束于机器能表示的最大整数 (MaxInt)。
Function,对于所有的 x,y? NaturalNumber;
False,True? Boolean,+,-,<,==,=等都是可用的服务。
Zero( ),返回自然数 0
NaturalNumber
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)
具有相同属性和服务的对象归于同一类，形成类
类中的一个对象为该类的一个实例
继承
派生类,载重车，轿车，摩托车,…
子类 特化类 (特殊化类 )
基类,车辆父类 泛化类 (一般化类 )
通信
消息传递
用于描述数据结构的语言
Smalltalk Effel C++ Java
线形聚类
直接存取类
顺序存取类
广义索引类
非线形聚类
层次聚集类 树，二叉树，堆
群聚集类 集合，图数据结构的抽象层次数据结构的抽象层次线性聚集类中各数据成员之间的线性关系树形结构树 二叉树 二叉搜索树堆结构
,最大”堆,最小”堆群聚类图结构 网络结构算法定义
定义,一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列
特性：
输入 有 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;
//k指示当前找到的最小整数
int temp = a[i]; a[i] = a[k]; a[k] = temp;
//交换 a[i]与 a[k]
}
}
模板 (template)
定义 适合 多种数据类型 的 类定义 或算法,在特定环境下通过简单地代换，
变成 针对具体某种数据类型 的 类定义或 算法用模板定义用于排序的数据表 (dataList)类
#ifndef DATALIST_H
#define DATALIST_H
#include <iostream.h>
template <class Type>
class dataList {
private:
Type *Element;
int ArraySize;
void Swap (const int m1,const int m2);
int MaxKey (const int low,const int high);
public:
dataList (int size = 10),ArraySize (size),
Element (new Type [Size]) { }
~dataList ( ) {delete [ ] Element;}
void Sort ( );
friend ostream& operator << (ostream&
outStream,const datalist<Type>&
outList);
friend istream& operator >> (istream&
inStream,const datalist<Type>&
inList);
};
#endif
dataList类中所有操作作为模板函数的实现
#ifndef SELECTTM_H
#define SELECTTM_H
#include,datalist.h”
template <class Type>
void dataList <Type>::
Swap (const int m1,const int m2) {
//交换由 m1,m2为下标的两个数组元素的值
Type temp = Element [m1];
Element [m1] = Element [m2];
Element [m2] = temp;
}
template <class Type>
int dataList<Type>::
MaxKey (const int low,const 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,
const dataList<Type> OutList) {
OutStream <<,Array Contents,\n”;
for (int i=0; i<OutList.ArraySize; i++)
OutStream << OutList.Element[i] << ‘ ’;
OutStream << endl;
OuStream <<,Array Current Size,,<<
OutList.ArraySize << endl;
return OutStream;
}
template <class Type>
istream& operator >> (istream& InStream,
dataList<Type> InList) {
//输入对象为 InList,输入流对象为 InStream
cout <<,Enter array Current Size,,;
Instream >> InList.ArraySize;
cout <<,Enter array elements,\n”;
for (int i=0; i<InList.ArraySize; i++) {
cout <<,Elememt” << 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);
}
}
#endif
使用模板的选择排序算法的主函数
#include,selecttm.h”
const int SIZE = 10;
int main ( ) {
dataList <int> TestList (SIZE);
cin >> TestList;
cout <<,Testing Selection Sort,\n” <<
TestList << endl;
TestList.Sort ( );
cout <<,After sorting,\n” <<
TestList << endl;
return 0;
}
性能分析与度量
算法的性能标准
算法的后期测试
算法的事前估计算法的性能标准
正确性
可使用性
可读性
效率
健壮性算法的后期测试在算法中的某些部位插装时间函数
time ( )
测定算法完成某一功能所花费的时间顺序搜索 (Sequenial Search)
行 int seqsearch ( int a[ ],const int n,
const int x ) //a[0],…,a [n-1]
1 {
2 int i = 0;
3 while ( i < n && a[i] != x )
4 i++;
5 if ( i == n ) return -1;
6 return i;
7 }
插装 time()的计时程序
void TimeSearch ( )
{ //在 1..1000中搜索 0,10,…,90,100,200,…,1000
int a[1001],n[20];
for ( int j=1; j<=1000; j++ )
a[j] = j; //a[1]=1,a[2]=2,…
for ( j=0; j<10; j++ ) {
n[j] = 10*j; //n[0]=0,n[1]=10,n[2]=20
n[j+10] = 100*( j+1 );
} //n[10]=100,n[11]=200,n[12]=300,..
cout << " n time" << endl;
for ( j=0; j<20; j++ ) {
long start,stop;
time (start);
int k = seqsearch (a,n[j],0);
time (stop);
long runTime = stop - start;
cout << " " << n[j] << " " <<
runTime << endl;
}
cout << "Times are in hundredths of a
second." << endl;
}
程序测试结果输出
n 0 10 20 30 40 50 60 70 80 90
r u n
T i m e
0 0 0 0 0 0 0 0 0 0
n 100 200 300 400 500 600 700 800 900 1000
r u n
T i m e
0 0 0 0 0 0 0 0 0 0
改进的计时程序
void TimeSearch ( ) {
int a[1001],n[20];
const long r[20] = {300000,300000,200000,
200000,100000,100000,100000,80000,
80000,50000,50000,25000,15000,15000,
10000,7500,7000,6000,5000,5000 };
for ( int j=1; j<=1000; j++ )
a[j] = j;
for ( j=0; j<10; j++ ) {
n[j] = 10*j; n[j+10] = 100*( j+1 );
}
cout << " n totalTime runTime" << endl;
for ( j=0; j<20; j++ ) {
long start,stop;
time (start); //开始计时
for ( long b=1; b<=r[j]; b++ )
int k = seqsearch(a,n[j],0 ); //执行 r[j]次
time (stop); //停止计时
long totalTime = stop - start;
float runTime =
(float)(totalTime) / (float)(r[j]);
cout << " " << n[j] << " " << totalTime
<< " " << runTime << endl;
}
}
程序测试结果输出
n 0 10 20 30 40 50 60 70 80 90
总的运行时间
241 533 582 736 467 565 659 604 681 472
单个运行时间
0.00
08
0.00
18
0.00
29
0.00
37
0.00
47
0.00
56
0.00
66
0.00
75
0.00
85
0.009
4
n 100 200 300 400 500 600 700 800 900 1000
总的运行时间
527 505 451 593 494 439 484 467 434 484
单个运行时间
0.01
05
0.02
02
0.03
01
0.03
95
0.04
94
0.05
85
0.06
91
0.07
78
0.08
68
0.09
68
算法的事前估计
空间复杂度
时间复杂度空间复杂度度量
存储空间的固定部分程序指令代码的空间，常数、简单变量、
定长成分 (如数组元素、结构成分、对象的数据成员等 )变量所占的空间
可变部分尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用的空间、通过 new和 delete命令动态使用的空间时间复杂度度量
编译时间
运行时间
程序步
语法上或语义上有意义的一段指令序列
执行时间与实例特性无关
例如：
注释,程序步数为 0
声明语句,程序步数为 0
表达式,程序步数为 1
例 以迭代方式求累加和的函数行 float sum ( float a[ ],const int n )
1 {
2 float s = 0.0;
3 for ( int i=0; i<n; i++ )
4 s += a[i];
5 return s;
6 }
程序步确定方法
插入计数全局变量 count
建表,列出个语句的程序步在求累加和程序中加入 count语句
float sum ( float a[ ],const 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[ ],const 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
fl oat s = 0.0 ; 1 1 1
for ( i n t i = 0 ; i < n ; i + + ) 1 n +1 n +1
s + = a [ i ] ; 1 n n
r e tu r n s ; 1 1 1
} 0 1 0
总程序步数 2 n +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 example (float x[ ][ ],int m,int n,int k) {
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 <<,Line,<< i <<
,:,<<sum [i] << endl;
} 渐进时间复杂度为 O(max (m*n,m))
template <class Type> //起泡排序的算法
void dataList<Type>::bubbleSort ( ) {
//对表 Element[0]到 Element[ArraySize-1]
//逐趟进行比较,ArraySize是表当前长度
int i = 1; int exchange = 1;
//当 exchange为 0则停止排序
while ( i < ArraySize && exchange ) {
BubbleExchange ( i,exchange );
i++;
} //一趟比较
}
template <class Type>
void dataList<Type>::
BubbleExchange(const int i,int & exchange ){
exchange = 0; //假定元素未交换
for ( int j = ArraySize-1; j>=i; j--)
if ( Element[j-1] > Element[j] ) {
Swap ( j -1,j ); //发生逆序
//交换 Element[j-1]与 Element[j]
exchange = 1; //做“发生了交换”标志
}
} 渐进时间复杂度
O(f (n)*g (n)) =
1n
1i 2
1)n ( ni)(n
DATA
STRUCTURE
—— C++ 描述
什么是数据结构
抽象数据类型及面向对象概念
数据结构的抽象层次
用 C++描述面向对象程序
算法定义
模板
性能分析与度量
“学生”表格学 号 姓 名 性别 籍 贯 出生年月
1 98 13 1 刘激扬 男 北 京 19 79,12
2 98 16 4 衣春生 男 青 岛 19 79,07
3 98 16 5 卢声凯 男 天 津 19 81,02
4 98 18 2 袁秋慧 女 广 州 19 80,10
5 98 20 3 林德康 男 上 海 19 80,05
6 98 22 4 洪 伟 男 太 原 19 81,01
7 98 23 6 熊南燕 女 苏 州 19 80,03
8 98 29 7 宫 力 男 北 京 19 81,01
9 98 31 0 蔡晓莉 女 昆 明 19 81,02
10 98 31 8 陈 健 男 杭 州 19 79,12
“课程”表格课程编号 课 程 名 学时
0 2 4 0 0 2 程序设计基础 6 4
0 2 4 0 1 0 汇编语言 4 8
0 2 4 0 1 6 计算机原理 6 4
0 2 4 0 2 0 数据结构 6 4
0 2 4 0 2 1 微机技术 6 4
0 2 4 0 2 4 操作系统 4 8
0 2 4 0 2 6 数据库原理 4 8
选课单包含如下信息学 号 课程编号 成 绩 时 间学生选课系统中实体构成的网状关系
UNIX文件系统的系统结构图
数据,数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。
数值性数据
非数值性数据
数据对象,数据的子集。具有相同性质的数据成员（数据元素）的集合。
整数数据对象 N = { 0,?1,?2,… }
学生数据对象什么是数据结构定义,由 某一数据对象 及 该对象中所有数据成员 之间的关系组成。记为：
Data_Structure = {D,R}
其中,D是某一数据对象,R是该对象中所有数据成员之间的关系的有限集合。
n个网站之间的连通关系树形关系 网状关系抽象数据类型及面向对象概念
数据类型定义,一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称,
C语言中的数据类型
char int float double void
字符型 整型 浮点型 双精度型 无值抽象数据类型
(ADTs,Abstract Data Types)
由用户定义，用以表示应用问题的数据模型
由 基本的数据类型 组成,并包括 一组相关的服务 （或称操作）
信息隐蔽 和 数据封装,使用与实现相分离自然数的抽象数据类型定义
ADT NaturalNumber is
objects,一个整数的有序子集合,它开始于 0,
结束于机器能表示的最大整数 (MaxInt)。
Function,对于所有的 x,y? NaturalNumber;
False,True? Boolean,+,-,<,==,=等都是可用的服务。
Zero( ),返回自然数 0
NaturalNumber
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)
具有相同属性和服务的对象归于同一类，形成类
类中的一个对象为该类的一个实例
继承
派生类,载重车，轿车，摩托车,…
子类 特化类 (特殊化类 )
基类,车辆父类 泛化类 (一般化类 )
通信
消息传递
用于描述数据结构的语言
Smalltalk Effel C++ Java
线形聚类
直接存取类
顺序存取类
广义索引类
非线形聚类
层次聚集类 树，二叉树，堆
群聚集类 集合，图数据结构的抽象层次数据结构的抽象层次线性聚集类中各数据成员之间的线性关系树形结构树 二叉树 二叉搜索树堆结构
,最大”堆,最小”堆群聚类图结构 网络结构算法定义
定义,一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列
特性：
输入 有 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;
//k指示当前找到的最小整数
int temp = a[i]; a[i] = a[k]; a[k] = temp;
//交换 a[i]与 a[k]
}
}
模板 (template)
定义 适合 多种数据类型 的 类定义 或算法,在特定环境下通过简单地代换，
变成 针对具体某种数据类型 的 类定义或 算法用模板定义用于排序的数据表 (dataList)类
#ifndef DATALIST_H
#define DATALIST_H
#include <iostream.h>
template <class Type>
class dataList {
private:
Type *Element;
int ArraySize;
void Swap (const int m1,const int m2);
int MaxKey (const int low,const int high);
public:
dataList (int size = 10),ArraySize (size),
Element (new Type [Size]) { }
~dataList ( ) {delete [ ] Element;}
void Sort ( );
friend ostream& operator << (ostream&
outStream,const datalist<Type>&
outList);
friend istream& operator >> (istream&
inStream,const datalist<Type>&
inList);
};
#endif
dataList类中所有操作作为模板函数的实现
#ifndef SELECTTM_H
#define SELECTTM_H
#include,datalist.h”
template <class Type>
void dataList <Type>::
Swap (const int m1,const int m2) {
//交换由 m1,m2为下标的两个数组元素的值
Type temp = Element [m1];
Element [m1] = Element [m2];
Element [m2] = temp;
}
template <class Type>
int dataList<Type>::
MaxKey (const int low,const 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,
const dataList<Type> OutList) {
OutStream <<,Array Contents,\n”;
for (int i=0; i<OutList.ArraySize; i++)
OutStream << OutList.Element[i] << ‘ ’;
OutStream << endl;
OuStream <<,Array Current Size,,<<
OutList.ArraySize << endl;
return OutStream;
}
template <class Type>
istream& operator >> (istream& InStream,
dataList<Type> InList) {
//输入对象为 InList,输入流对象为 InStream
cout <<,Enter array Current Size,,;
Instream >> InList.ArraySize;
cout <<,Enter array elements,\n”;
for (int i=0; i<InList.ArraySize; i++) {
cout <<,Elememt” << 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);
}
}
#endif
使用模板的选择排序算法的主函数
#include,selecttm.h”
const int SIZE = 10;
int main ( ) {
dataList <int> TestList (SIZE);
cin >> TestList;
cout <<,Testing Selection Sort,\n” <<
TestList << endl;
TestList.Sort ( );
cout <<,After sorting,\n” <<
TestList << endl;
return 0;
}
性能分析与度量
算法的性能标准
算法的后期测试
算法的事前估计算法的性能标准
正确性
可使用性
可读性
效率
健壮性算法的后期测试在算法中的某些部位插装时间函数
time ( )
测定算法完成某一功能所花费的时间顺序搜索 (Sequenial Search)
行 int seqsearch ( int a[ ],const int n,
const int x ) //a[0],…,a [n-1]
1 {
2 int i = 0;
3 while ( i < n && a[i] != x )
4 i++;
5 if ( i == n ) return -1;
6 return i;
7 }
插装 time()的计时程序
void TimeSearch ( )
{ //在 1..1000中搜索 0,10,…,90,100,200,…,1000
int a[1001],n[20];
for ( int j=1; j<=1000; j++ )
a[j] = j; //a[1]=1,a[2]=2,…
for ( j=0; j<10; j++ ) {
n[j] = 10*j; //n[0]=0,n[1]=10,n[2]=20
n[j+10] = 100*( j+1 );
} //n[10]=100,n[11]=200,n[12]=300,..
cout << " n time" << endl;
for ( j=0; j<20; j++ ) {
long start,stop;
time (start);
int k = seqsearch (a,n[j],0);
time (stop);
long runTime = stop - start;
cout << " " << n[j] << " " <<
runTime << endl;
}
cout << "Times are in hundredths of a
second." << endl;
}
程序测试结果输出
n 0 10 20 30 40 50 60 70 80 90
r u n
T i m e
0 0 0 0 0 0 0 0 0 0
n 100 200 300 400 500 600 700 800 900 1000
r u n
T i m e
0 0 0 0 0 0 0 0 0 0
改进的计时程序
void TimeSearch ( ) {
int a[1001],n[20];
const long r[20] = {300000,300000,200000,
200000,100000,100000,100000,80000,
80000,50000,50000,25000,15000,15000,
10000,7500,7000,6000,5000,5000 };
for ( int j=1; j<=1000; j++ )
a[j] = j;
for ( j=0; j<10; j++ ) {
n[j] = 10*j; n[j+10] = 100*( j+1 );
}
cout << " n totalTime runTime" << endl;
for ( j=0; j<20; j++ ) {
long start,stop;
time (start); //开始计时
for ( long b=1; b<=r[j]; b++ )
int k = seqsearch(a,n[j],0 ); //执行 r[j]次
time (stop); //停止计时
long totalTime = stop - start;
float runTime =
(float)(totalTime) / (float)(r[j]);
cout << " " << n[j] << " " << totalTime
<< " " << runTime << endl;
}
}
程序测试结果输出
n 0 10 20 30 40 50 60 70 80 90
总的运行时间
241 533 582 736 467 565 659 604 681 472
单个运行时间
0.00
08
0.00
18
0.00
29
0.00
37
0.00
47
0.00
56
0.00
66
0.00
75
0.00
85
0.009
4
n 100 200 300 400 500 600 700 800 900 1000
总的运行时间
527 505 451 593 494 439 484 467 434 484
单个运行时间
0.01
05
0.02
02
0.03
01
0.03
95
0.04
94
0.05
85
0.06
91
0.07
78
0.08
68
0.09
68
算法的事前估计
空间复杂度
时间复杂度空间复杂度度量
存储空间的固定部分程序指令代码的空间，常数、简单变量、
定长成分 (如数组元素、结构成分、对象的数据成员等 )变量所占的空间
可变部分尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用的空间、通过 new和 delete命令动态使用的空间时间复杂度度量
编译时间
运行时间
程序步
语法上或语义上有意义的一段指令序列
执行时间与实例特性无关
例如：
注释,程序步数为 0
声明语句,程序步数为 0
表达式,程序步数为 1
例 以迭代方式求累加和的函数行 float sum ( float a[ ],const int n )
1 {
2 float s = 0.0;
3 for ( int i=0; i<n; i++ )
4 s += a[i];
5 return s;
6 }
程序步确定方法
插入计数全局变量 count
建表,列出个语句的程序步在求累加和程序中加入 count语句
float sum ( float a[ ],const 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[ ],const 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
fl oat s = 0.0 ; 1 1 1
for ( i n t i = 0 ; i < n ; i + + ) 1 n +1 n +1
s + = a [ i ] ; 1 n n
r e tu r n s ; 1 1 1
} 0 1 0
总程序步数 2 n +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 example (float x[ ][ ],int m,int n,int k) {
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 <<,Line,<< i <<
,:,<<sum [i] << endl;
} 渐进时间复杂度为 O(max (m*n,m))
template <class Type> //起泡排序的算法
void dataList<Type>::bubbleSort ( ) {
//对表 Element[0]到 Element[ArraySize-1]
//逐趟进行比较,ArraySize是表当前长度
int i = 1; int exchange = 1;
//当 exchange为 0则停止排序
while ( i < ArraySize && exchange ) {
BubbleExchange ( i,exchange );
i++;
} //一趟比较
}
template <class Type>
void dataList<Type>::
BubbleExchange(const int i,int & exchange ){
exchange = 0; //假定元素未交换
for ( int j = ArraySize-1; j>=i; j--)
if ( Element[j-1] > Element[j] ) {
Swap ( j -1,j ); //发生逆序
//交换 Element[j-1]与 Element[j]
exchange = 1; //做“发生了交换”标志
}
} 渐进时间复杂度
O(f (n)*g (n)) =
1n
1i 2
1)n ( ni)(n
