? 什么是数据结构
抽象数据类型及面向对象概念
数据结构的抽象层次
用 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次比较
