数据结构 华中科技大学计算机学院 (1)
---------------------------------------------
本课程的任务
1.基本数据结构的定义、特性、运算与算法
1.1 线性结构：线性表；栈,队列,双队列；数组,串。
1.2 非线性结构：树,二叉树；图,网络。
2.数据结构的存储结构与实现选择存储结构,设计算法
3.查找算法：顺序,折半,分块,哈希,二叉排序树等
4.排序算法：内部排序,外部排序
5.文件
6.基本应用与综合应用
**不要求了解和掌握第 8章和其它各章中带 **号的小节基本要求
1.阅读教材与参考书、听课、记笔记；
2.完成一定数量的书面作业；
3.使用 C或 C++完成 5个以上的上机作业 。
第一章 绪 论
1.1什么是 数据、结构 (关系 )、数据结构？
建立数学模型是分析具体问题的过程，包括：
分析具体问题中操作对象
找出这些对象间的关系，并用数学语言描述数学模型分两类：
1）数值计算类：
例：根据三条边，求三角形面积。
假定：三条边依次为 a,b,c三个实型数，
满足,a>0,b> 0,c>0,a+b>c,b+c>a,c+a>b,
c)-(s*b)-(s*a)-(s*s
2
cba则 s=
area=
2）非数值计算类,
例 1,5个整数组成的 集合,
D={20,-5,66,15,44}
其中,20,-5,66等称为数据元素 (元素 )，
元素与元素之间关系是它们同属于集合 D。
D={20,-5,66,15,44}是一个数据对象例 2,一列整数,(线性结构 )
L=(20,-5,66,15,44）
其中,元素与元素之间在 L中是前后关系或线性关系。
L=(20,-5,66,15,44)是一个线性表。
例 3 一张 登记表 DL
序号 姓 名 性 别 年 龄
1 李 刚 男 25 记录 1
2 王 霞 女 29 记录 2
3 刘大海 男 40 记录 3
4 李爱林 男 44 记录 4
其中：姓名、性别、年龄是 数据项 (item),数据域 (field)；
(姓名，性别，年龄 )是 记录 (record),
C语言将 "记录 "(record)定义为,结构,(struct)；
登记表也是一个线性表。
例 4 树状结构其中,A,B,C等是 结点 (node)；
A与 B,B与 E,A与 C之间是层次关系或父子关系。
华中科技大学 (A)
计算机学院 (B) 管理学院 (C) 成教学院 (D)
科学系 (E) 应用系 (F) 工程系 (G)
例 5 图状结构
A
B D
C E F
G
其中,A,B,C 等是 顶点 (vertex),
图中任意两个顶点之间都可能有关系。
1.2 基本概念和术语
1.数据（ data) ----
所有能输入到计算机中并被计算机程序加工、处理的符号的总称。
如：整数、实数、字符、声音、图象、图形等。
2.数据元素 (data element)---
数据的基本单位。（元素、记录、结点、顶点）
在计算机程序中通常作为一个整体进行考虑和处理。
3.数据项 (data item)----
是数据的不可分割的最小单位。如：姓名、年龄等一个数据元素可由一个或多个数据项组成。
如,(姓名、年龄 )
4.数据对象 (data object)——
由性质相同 (类型相同 )的数据元素组成的集合。
数据对象是数据的一个子集。
例 1 由 4个整数组成的数据对象
D1={20,-30,88,45}
例 2 由正整数组成的数据对象
D2={1,2,3,...}
例 3 由 26个字母组成的数据对象
D3={A,B,C,...,Z}
其中,D1,D3是有穷集,D2是无穷集。
5.抽象数据对象
ElemSet={某种同类型的数据元素 }
6.数据结构 (data structure)----
相互之间存在一种或多种特定关系的数据元素的集合。
数据元素之间的关系称为 结构。
四类基本结构：
集合 线性结构 树形结构 图状结构
1.线性表
2.栈线性结构 3.队列,双队列
4.数组数据结构 5.字符串非 线 性 1.树,二叉树结 构 2.图逻辑结构,带有结构的数据元素的集合数据结构 (逻辑结构 )分类
6.存储结构 ----
数据结构在计算机存储器中的 映象 (mapping)。
存储结构也称为,存储表示,物理结构,物理表示 。
(1)顺序存储结构 (向量,一维数组 )
例,char a[4]={'A','B','C','D?}；
A B C D
0 1 2 3
a是一维数组
(2)非顺序存储结构 (链接表）
例,单链表
data next
┌─┬┐ ┌─┬┐ ┌─┬┐ ┌─┬─┐
Head ─→│A │┼→│B │┼→│C │┼→│D │^ │
└─┴┘ └─┴┘ └─┴┘ └─┴─┘
4个结点的单链表
7.数据类型（ data type)---
是一个值的集合和定义在这个值上的一组操作的总称。
(1)原子类型 (如,int,char,float等 )
(2)结构类型 (如：数组,结构,联合体等）
8.抽象数据类型 (Abstract Data Type)----
与计算机的实现无关的数据类型。
形式定义：
ADT 抽象数据类型名
{ 1.数据对象；
2.数据关系,一个或多个关系；
3.一组基本操作 /运算
} ADT 抽象数据类型名注意,ElemType是抽象元素类型。
1.3 算法和算法分析
1.算法 ----求解一个特定任务的指令的有限序列。
例,求 a[0]..a[n-1]中 n个数的平均值 (假定 n>0)。
float average(float a[ ],int n)
{ int i； float s=0.0； //累加器赋初值
for (i=0； i<n； i++)
s=s+a[i]； //a[i]累加到 s中
s=s/n； //计算平均值
printf(“ave=%f”,s)； //输出
return(s)； //返回
}
其中,a,n为输入量； s为输出量。
2.算法的 5个特征
(1)有穷性,在有限步 (或有限时间 )之后算法终止。
例,{ i=0； s=0；
while (i<=10)
s+=i；
i++；
}
(2)确定性,无二义性。
例 1,{ x=5； y=10；
z=x+++y；
printf(“%d,%d,%d”,x,y,z)；
}
x+++y 解释为,x + (++y)？还是 (x++)+ y？
例,int x=0; 表达式,x++ +x++ 的值
(3)可行性,可以在计算机上实现。
for( i=1,s=0； i<1000000000000； ++i) s++；？？？
(4)输入,有 0或多个输入量。
(5)输出,至少有一个输出量。
3.算法设计要求
(1)正确性
a.无语法错误；
b.对 n组输入产生正确结果；
c.对特殊输入产生正确结果；
d.对所有输入产生正确结果。
(2)可读性,,算法主要是为了人的阅读与交流,。
(3)健壮性
scanf(“%d”,&x)； y/=x；？？？
(4)高效与低存储量下列描述不符合算法的什么特征和要求？
例 1
void suanfa1( )
{ int i,s=0；
for (i=0； i>=0； i++) //死循环
s++； //不能终止
}
例 2
float suanfa2( )
{ int x,y；
scanf(“%d”,&x)；
y=sqrt(x)； //当 x<0时,出错
return(y)；
}
算法的描述工具：
（ 1） 自然语言；
（ 2） 程序设计语言；
（ 3） 流程图（框图）；
（ 4） 伪码语言；
是一种包括高级程序设计语言的三种基本结构（顺序、
选择、循环）和自然语言成分的,面向读者,的语言。
（ 5） 类 C
介于伪码语言和程序设计语言之间的一种表示形式。保留了 C语言的精华；不拘泥与 C语言的语法细节；同时也添加了一些 C++的成分。
特点：便于理解、阅读；能方便的转换成 C语言。
目的：便于简明扼要的描述算法；突出算法的思路。
算法描述举例问题：设一维数组 a[0..n-1]中已有 n个整数,
其中 n为个常数,试设计算法,求 a[]中的最大值。
算法基本思想,
1.maxai=a[0]；
2.i=1；
3.若 i<=n-1,则：
3.1 若 a[i]>maxai,则 maxai=a[i]；
3.2 i++；
3.3 转 3
4.maxai为最大值。
Ｃ函数 (算法 )
//求数组 a中 n个元素的最大值
int a_maxint(int a[],int n)
{ int j,maxai=a[0]； //最大值的初值
for (j=1； j<=n-1； j++)
if (a[j]>maxai) //比较元素大小
maxai＝ a[j]； //新的最大值
printf("maxai＝ %d\n",maxai)； //输出
return maxai；
}
4.算法的 时间复杂度 ----
算法 (或程序 )中基本操作 (或语句 )重复执行的次数的总和。
设 n为求解的 问题的规模,基本操作 (或语句 )执行次数总和称为 语句频度,记作 f(n)； 时间复杂度记作 T(n),有：
T(n)=O(f(n))
例 1 { int s；
scanf(“%d”,&s)；
s++；
printf(“%d”,s)；
}
其中：语句频度为,f(n)=f(1)=3
时间复杂度为,T(n)=O(f(n))=O(3)=O(1）
O(1)称成为常量阶 /常量数量级例 2 分析下面的算法
void sum(int a[],int n)
{ int s=0,i； // 1次
for(i=0； i<n； i++) // n次 (严格为 2*(n+1)次）
s=s+a[i]； // n次
printf(“%d”,s)； // 1次
}
其中：语句频度为,f(n)=1+n+n+1
时间复杂度为,T(n)=O(f(n))=O(2n+2)=O(n）
O(n)称成为线性阶 /线性数量级例 3 分析下面的算法
1,void sum(int m,int n)
2,{ int i,j,s=0； // 1次
3,for(i=1； i<=m； i++) // m次
4,{ for(j=1； j<=n； j++) // m*n次
5,s++； // m*n次
6,printf(“%d”,s)； // m次
7,}
8,}
其中,f(m,n)=1+m+2*m*n+m=2mn+2m+1
当 m=n时,f(n)=2n2+2n+1
T(n)=O(f(n))=O(2n2+2n+1)=O(n2)
O(n2 ) 称成为平方阶 /平方数量级例 4 分析下面的算法；当 n=5,指出输出结果
1,void sum(int n)
2,{ int i,j,s=0； // 1次
3,for(i=1； i<=n； i++) // n次
4,{ for(j=1； j<=i； j++) //?次
5,s++； //?次
6,printf(“%d”,s)； // n次
7,}
8,}
其中：第 4行的次数为 1+2+...+n=n(1+n)/2
第 5行的次数为 1+2+...+n=n(1+n)/2
f(n)=1+n+n(n+1)+n=n2+3n+1
T(n)=O(f(n))=O(n2）
O(n2）称成为平方阶 /平方数量级例 5 冒泡排序 的 C语言算法
// 对数组 a中 n个数按递增次序作冒泡排序
1,void bubble1(int a[],int n)
2,{ int i,j,temp；
3,for(i=0； i<=n-2； i++) //？ 次
4,for(j=0； j<=n-2-i； j++) //？ 次
5,if (a[j]>a[j+1]) //？ 次
6,{ temp=a[j]； //？ 次
7,a[j]=a[j+1]； //？ 次
8,a[j+1]=temp； //？ 次
9,}
10,for(i=0； i<n； i++) // n 次
11,printf(“%d”,a[i])； // n 次
12,}
思考：在最好情况下,f(n)=? T(n)=O(f(n))=?
在最坏情况下,f(n)=? T(n)=O(f(n))=?
一般情况：
原序列,10 3 7 8 5 2 1 4 9 6
第 1遍,3 7 8 5 2 1 4 9 6 10
第 2遍,3 7 5 2 1 4 8 6 9 10
第 3遍,3 5 2 1 4 7 6 8 9 10
第 4遍,3 2 1 4 5 6 7 8 9 10
第 5遍,2 1 3 4 5 6 7 8 9 10
第 6遍,1 2 3 4 5 6 7 8 9 10
第 7遍,1 2 3 4 5 6 7 8 9 10
第 8遍,2 1 3 4 5 6 7 8 9 10
第 9遍,1 2 3 4 5 6 7 8 9 10
最坏情况：
10 9 8 7 6 5 4 3 2 1
每次比较都 发生 数据交换。
最好情况：
1 2 3 4 5 6 7 8 9 10
每次比较都 不发生 数据交换。
算法改进：
每一遍开始时,change=false，结束时，若 change未变，
表示未发生数据交换，即已递增有序。
1,void bubble1(int a[],int n)
2,{ int i,j,temp；
3,for(i=0； i<=n-2； i++) // n-1 次
4,for(j=0； j<=n-2-i； j++) // n-1+n-2+..+1 次
=n(n-1)/2
5,if (a[j]>a[j+1]) // n(n-1)/2次
6,{ temp=a[j]； // 0 或 n(n-1)/2次
7,a[j]=a[j+1]； // 0 或 n(n-1)/2次
8,a[j+1]=temp； // 0 或 n(n-1)/2次
9,}
10,for(i=0； i<n； i++) // n 次
11,printf(“%d”,a[i])； // n 次
12,}
在最好情况下,f(n)= n-1+n(n-1)+2n=n2+2n-1
在最坏情况下,f(n)=5n2/2+n/2-1
T最好 (n)= T最坏 (n) = O(n2)
例 6 冒泡排序的,类 C语言,算法
// 对数组 a中 n个数按递增次序作冒泡排序
1,void bubble2(int a[],int n)
2,{ for(i=n-1,change=TRUE； i>=1 && change； i--)
3,{ change=FALSE； // change为交换标志
4,for(j=0； j<i； ++j)
5,if (a[j]>a[j+1])
6,{ a[j] <--> a[j+1]； // 交换元素
7,change=TRUE； //修改交换标志
8,}
9,}
10,}
思考：在最好情况下,f(n)=? T(n)=O(f(n))=?
在最坏情况下,f(n)=? T(n)=O(f(n))=?
例 6 冒泡排序的,类 C语言,算法时间复杂度分析。
1,void bubble2(int a[],int n)
2,{for(i=n-1,change=TRUE； i>=1 && change； i--) //1 或 n-1
3,{ change=FALSE； //1 或 n-1
4,for(j=0； j<i； ++j) //n-1或 n*(n-1)/2
5,if (a[j]>a[j+1]) //n-1或 n*(n-1)/2
6,{ a[j] <--> a[j+1]； //0或 n*(n-1)/2
7,change=TRUE； //0或 n*(n-1)/2
8,}
9,}
10,}
在最好情况下,T最好 (n)=O(f最好 (n))= O(n)
在最坏情况下,T最坏 (n)=O(f最坏 (n))= O(n2)
算法时间复杂度,T(n)= T最坏 (n)= O(n2)
例 7,求解,S=1!+2!+…,.+n!
算法 1：
long sum_of_fac(int n)
{
long s=0,t,i,j;
for(i=1;i<=n;i++) //n次
{
t=1; //n次
for(j=1;j<=i;j++) //n*(n+1)/2次
t*=j; //n*(n+1)/2次
s+=t; //n次
}
return (s); //1次
}
f(n)=n+n+n*(n+1)/2+ n*(n+1)/2+n+1=n2+4n+1
T(n)=O(f(n))=O(n2)
求 i!
例 7(续）,求解,S=1!+2!+…,.+n!
算法 2：
long sum_of_fac(int n)
{
long s=0,t,i;
t=1; //1次
for(i=1;i<=n;i++) //n次
{
t*=i; //n次
s+=t; //n次
}
return (s); //1次
}
f(n)=1+n+n+n+n+1=3n+2
T(n)=O(f(n))=O(n)
求 i!
5.算法的 空间复杂度 ----
执行算法所需存储空间的大小。
课外作业
1.一个算法具有哪几个特点？举例说明之。
2.下列描述不符合算法的什么特征和要求？
(1) void suanfa1( )
{ int i,s=0；
for (i=0； i>=0； i++)s++；
}
(2) float suanfa2(float x)
{ float y；
y=sqrt(x)；
return(y)；
}
3.分析并写出下面各语句所代表的算法的时间 复杂度 。
(n代表问题规模 )
(1) for (i=1; i<=n;i++)
for (j=1; j<=i;j++)
for (k=1; k<=j;k++)
{ s=i+k; printf(“%d”,s); }
(2) m=91; n=100;
while (n>0)
if (m>0) {m-=10; n--;}
else m++;
4.执行和分析下面的算法,回答问题 。
int suan_fan(int n)
{ int i,j,x=0；
for(i=1； i<n； i++)
{ for(j=1； j<i； j++)
x++；
printf("x=%d\n",x)；
}
return x；
}
1) 试问语句,x++；,共计执行多少次？
2) 试分析算法的时间复杂度；
3) 假定 n=6,试指出算法的输出结果；
4) 假定 n=6,算法的返回值是多少？
5.执行和分析下面的算法,回答问题 。
int suanfa1(int m,int n)
{ int i,j,s=0；
for(i=1； i<=m； i++)
{ for(j=1； j<=n； j++)
s++；
printf(“%d”,s)；
}
return s；
}
1) 试问语句 "printf(“%d”,s)； " 共计执行多少次？
2) 试问语句 "s++； " 共计执行多少次？
3） 该算法的时间复杂度是多少？
4）当 m=n=5时,算法的 输出结果是什么？
5） 当 m=n=5时,算法的返回 值 是什么？
---------------------------------------------
本课程的任务
1.基本数据结构的定义、特性、运算与算法
1.1 线性结构：线性表；栈,队列,双队列；数组,串。
1.2 非线性结构：树,二叉树；图,网络。
2.数据结构的存储结构与实现选择存储结构,设计算法
3.查找算法：顺序,折半,分块,哈希,二叉排序树等
4.排序算法：内部排序,外部排序
5.文件
6.基本应用与综合应用
**不要求了解和掌握第 8章和其它各章中带 **号的小节基本要求
1.阅读教材与参考书、听课、记笔记；
2.完成一定数量的书面作业；
3.使用 C或 C++完成 5个以上的上机作业 。
第一章 绪 论
1.1什么是 数据、结构 (关系 )、数据结构？
建立数学模型是分析具体问题的过程，包括：
分析具体问题中操作对象
找出这些对象间的关系，并用数学语言描述数学模型分两类：
1）数值计算类：
例：根据三条边，求三角形面积。
假定：三条边依次为 a,b,c三个实型数，
满足,a>0,b> 0,c>0,a+b>c,b+c>a,c+a>b,
c)-(s*b)-(s*a)-(s*s
2
cba则 s=
area=
2）非数值计算类,
例 1,5个整数组成的 集合,
D={20,-5,66,15,44}
其中,20,-5,66等称为数据元素 (元素 )，
元素与元素之间关系是它们同属于集合 D。
D={20,-5,66,15,44}是一个数据对象例 2,一列整数,(线性结构 )
L=(20,-5,66,15,44）
其中,元素与元素之间在 L中是前后关系或线性关系。
L=(20,-5,66,15,44)是一个线性表。
例 3 一张 登记表 DL
序号 姓 名 性 别 年 龄
1 李 刚 男 25 记录 1
2 王 霞 女 29 记录 2
3 刘大海 男 40 记录 3
4 李爱林 男 44 记录 4
其中：姓名、性别、年龄是 数据项 (item),数据域 (field)；
(姓名，性别，年龄 )是 记录 (record),
C语言将 "记录 "(record)定义为,结构,(struct)；
登记表也是一个线性表。
例 4 树状结构其中,A,B,C等是 结点 (node)；
A与 B,B与 E,A与 C之间是层次关系或父子关系。
华中科技大学 (A)
计算机学院 (B) 管理学院 (C) 成教学院 (D)
科学系 (E) 应用系 (F) 工程系 (G)
例 5 图状结构
A
B D
C E F
G
其中,A,B,C 等是 顶点 (vertex),
图中任意两个顶点之间都可能有关系。
1.2 基本概念和术语
1.数据（ data) ----
所有能输入到计算机中并被计算机程序加工、处理的符号的总称。
如：整数、实数、字符、声音、图象、图形等。
2.数据元素 (data element)---
数据的基本单位。（元素、记录、结点、顶点）
在计算机程序中通常作为一个整体进行考虑和处理。
3.数据项 (data item)----
是数据的不可分割的最小单位。如：姓名、年龄等一个数据元素可由一个或多个数据项组成。
如,(姓名、年龄 )
4.数据对象 (data object)——
由性质相同 (类型相同 )的数据元素组成的集合。
数据对象是数据的一个子集。
例 1 由 4个整数组成的数据对象
D1={20,-30,88,45}
例 2 由正整数组成的数据对象
D2={1,2,3,...}
例 3 由 26个字母组成的数据对象
D3={A,B,C,...,Z}
其中,D1,D3是有穷集,D2是无穷集。
5.抽象数据对象
ElemSet={某种同类型的数据元素 }
6.数据结构 (data structure)----
相互之间存在一种或多种特定关系的数据元素的集合。
数据元素之间的关系称为 结构。
四类基本结构：
集合 线性结构 树形结构 图状结构
1.线性表
2.栈线性结构 3.队列,双队列
4.数组数据结构 5.字符串非 线 性 1.树,二叉树结 构 2.图逻辑结构,带有结构的数据元素的集合数据结构 (逻辑结构 )分类
6.存储结构 ----
数据结构在计算机存储器中的 映象 (mapping)。
存储结构也称为,存储表示,物理结构,物理表示 。
(1)顺序存储结构 (向量,一维数组 )
例,char a[4]={'A','B','C','D?}；
A B C D
0 1 2 3
a是一维数组
(2)非顺序存储结构 (链接表）
例,单链表
data next
┌─┬┐ ┌─┬┐ ┌─┬┐ ┌─┬─┐
Head ─→│A │┼→│B │┼→│C │┼→│D │^ │
└─┴┘ └─┴┘ └─┴┘ └─┴─┘
4个结点的单链表
7.数据类型（ data type)---
是一个值的集合和定义在这个值上的一组操作的总称。
(1)原子类型 (如,int,char,float等 )
(2)结构类型 (如：数组,结构,联合体等）
8.抽象数据类型 (Abstract Data Type)----
与计算机的实现无关的数据类型。
形式定义：
ADT 抽象数据类型名
{ 1.数据对象；
2.数据关系,一个或多个关系；
3.一组基本操作 /运算
} ADT 抽象数据类型名注意,ElemType是抽象元素类型。
1.3 算法和算法分析
1.算法 ----求解一个特定任务的指令的有限序列。
例,求 a[0]..a[n-1]中 n个数的平均值 (假定 n>0)。
float average(float a[ ],int n)
{ int i； float s=0.0； //累加器赋初值
for (i=0； i<n； i++)
s=s+a[i]； //a[i]累加到 s中
s=s/n； //计算平均值
printf(“ave=%f”,s)； //输出
return(s)； //返回
}
其中,a,n为输入量； s为输出量。
2.算法的 5个特征
(1)有穷性,在有限步 (或有限时间 )之后算法终止。
例,{ i=0； s=0；
while (i<=10)
s+=i；
i++；
}
(2)确定性,无二义性。
例 1,{ x=5； y=10；
z=x+++y；
printf(“%d,%d,%d”,x,y,z)；
}
x+++y 解释为,x + (++y)？还是 (x++)+ y？
例,int x=0; 表达式,x++ +x++ 的值
(3)可行性,可以在计算机上实现。
for( i=1,s=0； i<1000000000000； ++i) s++；？？？
(4)输入,有 0或多个输入量。
(5)输出,至少有一个输出量。
3.算法设计要求
(1)正确性
a.无语法错误；
b.对 n组输入产生正确结果；
c.对特殊输入产生正确结果；
d.对所有输入产生正确结果。
(2)可读性,,算法主要是为了人的阅读与交流,。
(3)健壮性
scanf(“%d”,&x)； y/=x；？？？
(4)高效与低存储量下列描述不符合算法的什么特征和要求？
例 1
void suanfa1( )
{ int i,s=0；
for (i=0； i>=0； i++) //死循环
s++； //不能终止
}
例 2
float suanfa2( )
{ int x,y；
scanf(“%d”,&x)；
y=sqrt(x)； //当 x<0时,出错
return(y)；
}
算法的描述工具：
（ 1） 自然语言；
（ 2） 程序设计语言；
（ 3） 流程图（框图）；
（ 4） 伪码语言；
是一种包括高级程序设计语言的三种基本结构（顺序、
选择、循环）和自然语言成分的,面向读者,的语言。
（ 5） 类 C
介于伪码语言和程序设计语言之间的一种表示形式。保留了 C语言的精华；不拘泥与 C语言的语法细节；同时也添加了一些 C++的成分。
特点：便于理解、阅读；能方便的转换成 C语言。
目的：便于简明扼要的描述算法；突出算法的思路。
算法描述举例问题：设一维数组 a[0..n-1]中已有 n个整数,
其中 n为个常数,试设计算法,求 a[]中的最大值。
算法基本思想,
1.maxai=a[0]；
2.i=1；
3.若 i<=n-1,则：
3.1 若 a[i]>maxai,则 maxai=a[i]；
3.2 i++；
3.3 转 3
4.maxai为最大值。
Ｃ函数 (算法 )
//求数组 a中 n个元素的最大值
int a_maxint(int a[],int n)
{ int j,maxai=a[0]； //最大值的初值
for (j=1； j<=n-1； j++)
if (a[j]>maxai) //比较元素大小
maxai＝ a[j]； //新的最大值
printf("maxai＝ %d\n",maxai)； //输出
return maxai；
}
4.算法的 时间复杂度 ----
算法 (或程序 )中基本操作 (或语句 )重复执行的次数的总和。
设 n为求解的 问题的规模,基本操作 (或语句 )执行次数总和称为 语句频度,记作 f(n)； 时间复杂度记作 T(n),有：
T(n)=O(f(n))
例 1 { int s；
scanf(“%d”,&s)；
s++；
printf(“%d”,s)；
}
其中：语句频度为,f(n)=f(1)=3
时间复杂度为,T(n)=O(f(n))=O(3)=O(1）
O(1)称成为常量阶 /常量数量级例 2 分析下面的算法
void sum(int a[],int n)
{ int s=0,i； // 1次
for(i=0； i<n； i++) // n次 (严格为 2*(n+1)次）
s=s+a[i]； // n次
printf(“%d”,s)； // 1次
}
其中：语句频度为,f(n)=1+n+n+1
时间复杂度为,T(n)=O(f(n))=O(2n+2)=O(n）
O(n)称成为线性阶 /线性数量级例 3 分析下面的算法
1,void sum(int m,int n)
2,{ int i,j,s=0； // 1次
3,for(i=1； i<=m； i++) // m次
4,{ for(j=1； j<=n； j++) // m*n次
5,s++； // m*n次
6,printf(“%d”,s)； // m次
7,}
8,}
其中,f(m,n)=1+m+2*m*n+m=2mn+2m+1
当 m=n时,f(n)=2n2+2n+1
T(n)=O(f(n))=O(2n2+2n+1)=O(n2)
O(n2 ) 称成为平方阶 /平方数量级例 4 分析下面的算法；当 n=5,指出输出结果
1,void sum(int n)
2,{ int i,j,s=0； // 1次
3,for(i=1； i<=n； i++) // n次
4,{ for(j=1； j<=i； j++) //?次
5,s++； //?次
6,printf(“%d”,s)； // n次
7,}
8,}
其中：第 4行的次数为 1+2+...+n=n(1+n)/2
第 5行的次数为 1+2+...+n=n(1+n)/2
f(n)=1+n+n(n+1)+n=n2+3n+1
T(n)=O(f(n))=O(n2）
O(n2）称成为平方阶 /平方数量级例 5 冒泡排序 的 C语言算法
// 对数组 a中 n个数按递增次序作冒泡排序
1,void bubble1(int a[],int n)
2,{ int i,j,temp；
3,for(i=0； i<=n-2； i++) //？ 次
4,for(j=0； j<=n-2-i； j++) //？ 次
5,if (a[j]>a[j+1]) //？ 次
6,{ temp=a[j]； //？ 次
7,a[j]=a[j+1]； //？ 次
8,a[j+1]=temp； //？ 次
9,}
10,for(i=0； i<n； i++) // n 次
11,printf(“%d”,a[i])； // n 次
12,}
思考：在最好情况下,f(n)=? T(n)=O(f(n))=?
在最坏情况下,f(n)=? T(n)=O(f(n))=?
一般情况：
原序列,10 3 7 8 5 2 1 4 9 6
第 1遍,3 7 8 5 2 1 4 9 6 10
第 2遍,3 7 5 2 1 4 8 6 9 10
第 3遍,3 5 2 1 4 7 6 8 9 10
第 4遍,3 2 1 4 5 6 7 8 9 10
第 5遍,2 1 3 4 5 6 7 8 9 10
第 6遍,1 2 3 4 5 6 7 8 9 10
第 7遍,1 2 3 4 5 6 7 8 9 10
第 8遍,2 1 3 4 5 6 7 8 9 10
第 9遍,1 2 3 4 5 6 7 8 9 10
最坏情况：
10 9 8 7 6 5 4 3 2 1
每次比较都 发生 数据交换。
最好情况：
1 2 3 4 5 6 7 8 9 10
每次比较都 不发生 数据交换。
算法改进：
每一遍开始时,change=false，结束时，若 change未变，
表示未发生数据交换，即已递增有序。
1,void bubble1(int a[],int n)
2,{ int i,j,temp；
3,for(i=0； i<=n-2； i++) // n-1 次
4,for(j=0； j<=n-2-i； j++) // n-1+n-2+..+1 次
=n(n-1)/2
5,if (a[j]>a[j+1]) // n(n-1)/2次
6,{ temp=a[j]； // 0 或 n(n-1)/2次
7,a[j]=a[j+1]； // 0 或 n(n-1)/2次
8,a[j+1]=temp； // 0 或 n(n-1)/2次
9,}
10,for(i=0； i<n； i++) // n 次
11,printf(“%d”,a[i])； // n 次
12,}
在最好情况下,f(n)= n-1+n(n-1)+2n=n2+2n-1
在最坏情况下,f(n)=5n2/2+n/2-1
T最好 (n)= T最坏 (n) = O(n2)
例 6 冒泡排序的,类 C语言,算法
// 对数组 a中 n个数按递增次序作冒泡排序
1,void bubble2(int a[],int n)
2,{ for(i=n-1,change=TRUE； i>=1 && change； i--)
3,{ change=FALSE； // change为交换标志
4,for(j=0； j<i； ++j)
5,if (a[j]>a[j+1])
6,{ a[j] <--> a[j+1]； // 交换元素
7,change=TRUE； //修改交换标志
8,}
9,}
10,}
思考：在最好情况下,f(n)=? T(n)=O(f(n))=?
在最坏情况下,f(n)=? T(n)=O(f(n))=?
例 6 冒泡排序的,类 C语言,算法时间复杂度分析。
1,void bubble2(int a[],int n)
2,{for(i=n-1,change=TRUE； i>=1 && change； i--) //1 或 n-1
3,{ change=FALSE； //1 或 n-1
4,for(j=0； j<i； ++j) //n-1或 n*(n-1)/2
5,if (a[j]>a[j+1]) //n-1或 n*(n-1)/2
6,{ a[j] <--> a[j+1]； //0或 n*(n-1)/2
7,change=TRUE； //0或 n*(n-1)/2
8,}
9,}
10,}
在最好情况下,T最好 (n)=O(f最好 (n))= O(n)
在最坏情况下,T最坏 (n)=O(f最坏 (n))= O(n2)
算法时间复杂度,T(n)= T最坏 (n)= O(n2)
例 7,求解,S=1!+2!+…,.+n!
算法 1：
long sum_of_fac(int n)
{
long s=0,t,i,j;
for(i=1;i<=n;i++) //n次
{
t=1; //n次
for(j=1;j<=i;j++) //n*(n+1)/2次
t*=j; //n*(n+1)/2次
s+=t; //n次
}
return (s); //1次
}
f(n)=n+n+n*(n+1)/2+ n*(n+1)/2+n+1=n2+4n+1
T(n)=O(f(n))=O(n2)
求 i!
例 7(续）,求解,S=1!+2!+…,.+n!
算法 2：
long sum_of_fac(int n)
{
long s=0,t,i;
t=1; //1次
for(i=1;i<=n;i++) //n次
{
t*=i; //n次
s+=t; //n次
}
return (s); //1次
}
f(n)=1+n+n+n+n+1=3n+2
T(n)=O(f(n))=O(n)
求 i!
5.算法的 空间复杂度 ----
执行算法所需存储空间的大小。
课外作业
1.一个算法具有哪几个特点？举例说明之。
2.下列描述不符合算法的什么特征和要求？
(1) void suanfa1( )
{ int i,s=0；
for (i=0； i>=0； i++)s++；
}
(2) float suanfa2(float x)
{ float y；
y=sqrt(x)；
return(y)；
}
3.分析并写出下面各语句所代表的算法的时间 复杂度 。
(n代表问题规模 )
(1) for (i=1; i<=n;i++)
for (j=1; j<=i;j++)
for (k=1; k<=j;k++)
{ s=i+k; printf(“%d”,s); }
(2) m=91; n=100;
while (n>0)
if (m>0) {m-=10; n--;}
else m++;
4.执行和分析下面的算法,回答问题 。
int suan_fan(int n)
{ int i,j,x=0；
for(i=1； i<n； i++)
{ for(j=1； j<i； j++)
x++；
printf("x=%d\n",x)；
}
return x；
}
1) 试问语句,x++；,共计执行多少次？
2) 试分析算法的时间复杂度；
3) 假定 n=6,试指出算法的输出结果；
4) 假定 n=6,算法的返回值是多少？
5.执行和分析下面的算法,回答问题 。
int suanfa1(int m,int n)
{ int i,j,s=0；
for(i=1； i<=m； i++)
{ for(j=1； j<=n； j++)
s++；
printf(“%d”,s)；
}
return s；
}
1) 试问语句 "printf(“%d”,s)； " 共计执行多少次？
2) 试问语句 "s++； " 共计执行多少次？
3） 该算法的时间复杂度是多少？
4）当 m=n=5时,算法的 输出结果是什么？
5） 当 m=n=5时,算法的返回 值 是什么？
