? 什么是数据结构
抽象数据类型及面向对象概念
数据结构的抽象层次
用 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 element)
数据的 基本单位 。在计算机程序中常作为一个整体进行考虑和处理。
有时一个数据元素可以由若干 数据项
(Data Item)组成。 数据项 是 具有独立含义的最小标识单位 。
数据元素又称为元素、结点、记录。
数据对象 (data object)
数据的子集。具有相同性质的数据成员（数据元素）的集合。
整数数据对象
N = { 0,?1,?2,… }
学生数据对象什么是数据结构定义,
由某一数据对象及该对象中所有数据成员之间的关系组成。记为：
Data_Structure = {D,R}
其中,D 是某一数据对象,R 是该对象中所有数据成员之间的关系的有限集合。
N 个网点之间的连通关系树形关系 网状关系
1
5
2
4
36
1
5
2
4
36
数据结构 是数据的 组织形式
数据元素间的 逻辑关系,即数据的逻辑结构 ；
数据元素及其关系在计算机存储内的表示，即数据的 存储表示 ；
数据的运算，即对数据元素施加的操作 。
数据的逻辑结构
数据的逻辑结构 从逻辑关系上描述数据,与数据的存储无关 ；
数据的逻辑结构可以看作是 从具体问题抽象出来的数据模型 ；
数据的逻辑结构 与数据元素本身的形式、内容无关 ；
数据的逻辑结构与数据元素的相对位置无关。
数据的逻辑结构分类
线性结构
线性表
非线性结构
树
图（或网络）
线性结构树形结构树 二叉树 二叉搜索树
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语言中的数据类型
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
线性结构
直接存取类 数组,文件
顺序存取类 表,栈,队列,优先队列
广义索引类 线性索引,搜索树
非线性结构
层次结构类 树，二叉树，堆
群结构类 集合，图数据结构的抽象层次数据结构的抽象层次为什么选用面向对象及 C++语言讲述数据结构？
PASCAL与 C描述是面向过程的。
C++描述兼有面向过程与面向对象的特点。
Java描述是面向对象的。
用面向对象及 C++描述与国际接轨，是市场需要 。
算法定义
定义,一个有穷的指令集,这些指令为解决某一特定任务规定了一个运算序列
特性：
输入 有 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)
定义适合 多种数据类型 的 类定义 或 算法,
在特定环境下通过简单地代换，变成针对具体某种数据类型 的 类定义 或 算法用模板定义用于排序的数据表类
#ifndef DATALIST_H
#define DATALIST_H
#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);
};
#endif
类中所有操作作为模板函数的实现
#ifndef SELECTTM_H
#define SELECTTM_H
#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) {
//输入对象为 InList，输入流对象为 InStream
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);
}
}
#endif
使用模板的选择排序算法的主函数
#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!
变量计数
x = 0; y = 0;
for ( int k = 0; k < n; k ++ )
x ++;
for ( int i = 0; i < n; i++ )
for ( int j = 0; j < n; j++ )
y ++;
T1(n) = O(1)
T2(n) = O(n)
T3(n) = O(n2)
T(n) = T1(n)+T2(n)+T3(n) = O( max( 1,n,n2 ) )
= O(n2)
乘法规则 针对嵌套程序段
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次比较
有时,算法的时间复杂度不仅依赖于问题规模 n，还与输入实例的初始排列有关。
在数组 A[n] 中查找给定值 k 的算法：
int i = n-1;
while ( i >= 0 && A[i] != k )
i--;
return i;
算法的语句 i-- 的频度不仅与 n 有关，
还与 A[ ] 中各元素的取值,以及 k 的取值 有关。
出错处理问题举例
试编写一个函数计算 n!*2n 的值，结果存放于数组 A[arraySize] 的第 n 个数组元素中 (0? n? arraySize)
若设计算机中允许的整数的最大值为
maxInt，则当 n > arraySize 或者对于某一个 k ( 0? k? n )，使得 k!*2k > maxInt
时，应按出错处理。
可有如下三种不同的出错处理方式：
用 cerr << 及 exit (1) 语句来终止执行并报告错误；
用返回整数函数值 0,1 来实现算法,
以区别是正常返回还是错误返回；
在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某中错误返回 。
#include "iostream.h"
#define arraySize 100
#define MaxInt 0x7fffffff
int calc ( int T[ ],int n ) {
int i,value = 1;
if ( n != 0 ) {
for ( i = 1; i < n; i++) {
value *= i * 2;
if ( value > MaxInt / n / 2 )
return 0;
} //直接判断 i!*2i > MaxInt 是危险的
value *= n * 2;
}
T[n] = value; return 1; //n!*2n? T[n]
}
void main ( ) {
int A[arraySize],i;
for ( i = 0; i < arraySize; i++ )
if ( !calc ( A,i ) ) {
cout << "failed at " << i << endl;
break;
}
}
抽象数据类型及面向对象概念
数据结构的抽象层次
用 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 element)
数据的 基本单位 。在计算机程序中常作为一个整体进行考虑和处理。
有时一个数据元素可以由若干 数据项
(Data Item)组成。 数据项 是 具有独立含义的最小标识单位 。
数据元素又称为元素、结点、记录。
数据对象 (data object)
数据的子集。具有相同性质的数据成员（数据元素）的集合。
整数数据对象
N = { 0,?1,?2,… }
学生数据对象什么是数据结构定义,
由某一数据对象及该对象中所有数据成员之间的关系组成。记为：
Data_Structure = {D,R}
其中,D 是某一数据对象,R 是该对象中所有数据成员之间的关系的有限集合。
N 个网点之间的连通关系树形关系 网状关系
1
5
2
4
36
1
5
2
4
36
数据结构 是数据的 组织形式
数据元素间的 逻辑关系,即数据的逻辑结构 ；
数据元素及其关系在计算机存储内的表示，即数据的 存储表示 ；
数据的运算，即对数据元素施加的操作 。
数据的逻辑结构
数据的逻辑结构 从逻辑关系上描述数据,与数据的存储无关 ；
数据的逻辑结构可以看作是 从具体问题抽象出来的数据模型 ；
数据的逻辑结构 与数据元素本身的形式、内容无关 ；
数据的逻辑结构与数据元素的相对位置无关。
数据的逻辑结构分类
线性结构
线性表
非线性结构
树
图（或网络）
线性结构树形结构树 二叉树 二叉搜索树
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语言中的数据类型
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
线性结构
直接存取类 数组,文件
顺序存取类 表,栈,队列,优先队列
广义索引类 线性索引,搜索树
非线性结构
层次结构类 树，二叉树，堆
群结构类 集合，图数据结构的抽象层次数据结构的抽象层次为什么选用面向对象及 C++语言讲述数据结构？
PASCAL与 C描述是面向过程的。
C++描述兼有面向过程与面向对象的特点。
Java描述是面向对象的。
用面向对象及 C++描述与国际接轨，是市场需要 。
算法定义
定义,一个有穷的指令集,这些指令为解决某一特定任务规定了一个运算序列
特性：
输入 有 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)
定义适合 多种数据类型 的 类定义 或 算法,
在特定环境下通过简单地代换，变成针对具体某种数据类型 的 类定义 或 算法用模板定义用于排序的数据表类
#ifndef DATALIST_H
#define DATALIST_H
#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);
};
#endif
类中所有操作作为模板函数的实现
#ifndef SELECTTM_H
#define SELECTTM_H
#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) {
//输入对象为 InList，输入流对象为 InStream
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);
}
}
#endif
使用模板的选择排序算法的主函数
#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!
变量计数
x = 0; y = 0;
for ( int k = 0; k < n; k ++ )
x ++;
for ( int i = 0; i < n; i++ )
for ( int j = 0; j < n; j++ )
y ++;
T1(n) = O(1)
T2(n) = O(n)
T3(n) = O(n2)
T(n) = T1(n)+T2(n)+T3(n) = O( max( 1,n,n2 ) )
= O(n2)
乘法规则 针对嵌套程序段
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次比较
有时,算法的时间复杂度不仅依赖于问题规模 n，还与输入实例的初始排列有关。
在数组 A[n] 中查找给定值 k 的算法：
int i = n-1;
while ( i >= 0 && A[i] != k )
i--;
return i;
算法的语句 i-- 的频度不仅与 n 有关，
还与 A[ ] 中各元素的取值,以及 k 的取值 有关。
出错处理问题举例
试编写一个函数计算 n!*2n 的值，结果存放于数组 A[arraySize] 的第 n 个数组元素中 (0? n? arraySize)
若设计算机中允许的整数的最大值为
maxInt，则当 n > arraySize 或者对于某一个 k ( 0? k? n )，使得 k!*2k > maxInt
时，应按出错处理。
可有如下三种不同的出错处理方式：
用 cerr << 及 exit (1) 语句来终止执行并报告错误；
用返回整数函数值 0,1 来实现算法,
以区别是正常返回还是错误返回；
在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某中错误返回 。
#include "iostream.h"
#define arraySize 100
#define MaxInt 0x7fffffff
int calc ( int T[ ],int n ) {
int i,value = 1;
if ( n != 0 ) {
for ( i = 1; i < n; i++) {
value *= i * 2;
if ( value > MaxInt / n / 2 )
return 0;
} //直接判断 i!*2i > MaxInt 是危险的
value *= n * 2;
}
T[n] = value; return 1; //n!*2n? T[n]
}
void main ( ) {
int A[arraySize],i;
for ( i = 0; i < arraySize; i++ )
if ( !calc ( A,i ) ) {
cout << "failed at " << i << endl;
break;
}
}
