数据结构 基本概念精.ppt

《数据结构 基本概念精.ppt》由会员分享，可在线阅读，更多相关《数据结构 基本概念精.ppt（40页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构 基本概念第1页，本讲稿共40页第一章第一章 基本概念基本概念什么是数据结构什么是数据结构数据结构的抽象层次数据结构的抽象层次算法定义算法定义性能分析与度量性能分析与度量第2页，本讲稿共40页“学生”表格 初等项：如学生性别、籍贯等，不能再分割的最小数据单位。初等项：如学生性别、籍贯等，不能再分割的最小数据单位。初等项：如学生性别、籍贯等，不能再分割的最小数据单位。初等项：如学生性别、籍贯等，不能再分割的最小数据单位。组合项：如一组成绩，可以再划分为物理成绩、化学成绩等更小的项。组合项：如一组成绩，可以再划分为物理成绩、化学成绩等更小的项。组合项：如一组成绩，可以再划分为物理成绩、化学

2、成绩等更小的项。组合项：如一组成绩，可以再划分为物理成绩、化学成绩等更小的项。第3页，本讲稿共40页 选课关系包含如下信息 学号 课程编号 成绩 学生选课系统中实体构成的网状关系第4页，本讲稿共40页UNIX文件系统的系统结构图在应用程序中涉及到各种各样的数据，为了存储它们，在应用程序中涉及到各种各样的数据，为了存储它们，组织它们，需要讨论它们的归类及它们之间的关系，从组织它们，需要讨论它们的归类及它们之间的关系，从而建立相应的数据结构，并依此实现要求的软件功能。而建立相应的数据结构，并依此实现要求的软件功能。第5页，本讲稿共40页数据：数据：信息的载体，是描述客观事物的数、字符、信息的载体，

3、是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。别和处理的符号的集合。数值性数据数值性数据 如整数、实数、双精度数等如整数、实数、双精度数等如整数、实数、双精度数等如整数、实数、双精度数等主要用于工程和科学计算，及商业事务处理中使用。主要用于工程和科学计算，及商业事务处理中使用。主要用于工程和科学计算，及商业事务处理中使用。主要用于工程和科学计算，及商业事务处理中使用。非数值性数据非数值性数据 如字符串、多媒体信息（文字、图形、如字符串、多媒体信息（文字、图形、如字符串、多媒体信息（文字、图形、如字符串、多媒体信息

4、（文字、图形、语音）等。语音）等。语音）等。语音）等。数据对象：数据对象：数据的子集。具有相同性质的数据成员数据的子集。具有相同性质的数据成员（数据元素）的集合。（数据元素）的集合。整数数据对象整数数据对象整数数据对象整数数据对象 N N=0,=0,1,1,2,2,英文字母数据对象英文字母数据对象英文字母数据对象英文字母数据对象LETTER=A,B,ZLETTER=A,B,Z 学生数据对象学生数据对象学生数据对象学生数据对象第6页，本讲稿共40页什么是数据结构？定义定义:一组数据对象一组数据对象及数据对象之间的及数据对象之间的关系关系组组成。记为：成。记为：Data_Structure=D,R

5、 其中，其中，D是数据对象的有限集合，是数据对象的有限集合，R是该集是该集合中所有数据对象之间的关系的有限集合。合中所有数据对象之间的关系的有限集合。n n个网站之间的连通关系个网站之间的连通关系以最小代以最小代以最小代以最小代价将价将价将价将n n n n个网个网个网个网站连通站连通站连通站连通树形关系树形关系树形关系树形关系任一网站任一网站任一网站任一网站出现故障出现故障出现故障出现故障而整个网而整个网而整个网而整个网络畅通络畅通络畅通络畅通网状关系网状关系网状关系网状关系第7页，本讲稿共40页数据结构的分类 根据数据对象之间的关系不同，分为两大类：根据数据对象之间的关系不同，分为两大类：

6、线性结构线性结构非线性结构非线性结构线性结构中各个数据对象依次排列在一个线性序列中；线性结构中各个数据对象依次排列在一个线性序列中；线性结构中各个数据对象依次排列在一个线性序列中；线性结构中各个数据对象依次排列在一个线性序列中；非线性结构中各个数据对象不再保持在一个线性序列中，非线性结构中各个数据对象不再保持在一个线性序列中，非线性结构中各个数据对象不再保持在一个线性序列中，非线性结构中各个数据对象不再保持在一个线性序列中，每个数据对象可能与零个或多个其它数据对象有某种特每个数据对象可能与零个或多个其它数据对象有某种特每个数据对象可能与零个或多个其它数据对象有某种特每个数据对象可能与零个或多个

7、其它数据对象有某种特定的联系。定的联系。定的联系。定的联系。第8页，本讲稿共40页根据考虑问题的角度不同，分为两大类：根据考虑问题的角度不同，分为两大类：逻辑逻辑结构结构物理结构物理结构逻辑结构逻辑结构逻辑结构逻辑结构是指从解决问题出发，为实现必要的功能所建是指从解决问题出发，为实现必要的功能所建是指从解决问题出发，为实现必要的功能所建是指从解决问题出发，为实现必要的功能所建立的数据结构，属于用户视图，面向问题，根据问题所立的数据结构，属于用户视图，面向问题，根据问题所立的数据结构，属于用户视图，面向问题，根据问题所立的数据结构，属于用户视图，面向问题，根据问题所要实现的功能建立；要实现的功能

8、建立；要实现的功能建立；要实现的功能建立；物理结构物理结构物理结构物理结构是指数据应该如何在计算机中存放，是数据逻是指数据应该如何在计算机中存放，是数据逻是指数据应该如何在计算机中存放，是数据逻是指数据应该如何在计算机中存放，是数据逻辑结构的存储方式，是属于具体实现的视图，面向计辑结构的存储方式，是属于具体实现的视图，面向计辑结构的存储方式，是属于具体实现的视图，面向计辑结构的存储方式，是属于具体实现的视图，面向计算机，根据问题所要求的响应速度、处理时间、修改算机，根据问题所要求的响应速度、处理时间、修改算机，根据问题所要求的响应速度、处理时间、修改算机，根据问题所要求的响应速度、处理时间、修

9、改时间、存储空间和单位时间的处理量等建立。时间、存储空间和单位时间的处理量等建立。时间、存储空间和单位时间的处理量等建立。时间、存储空间和单位时间的处理量等建立。第9页，本讲稿共40页抽象数据类型数据类型数据类型 定义：定义：定义：定义：一组性质相同的值的集合一组性质相同的值的集合一组性质相同的值的集合一组性质相同的值的集合,以及定义于这个值集合以及定义于这个值集合以及定义于这个值集合以及定义于这个值集合上的一组操作的总称上的一组操作的总称上的一组操作的总称上的一组操作的总称.由用户定义，用以表示应用问题的由用户定义，用以表示应用问题的数据模型，数据模型，由由基本基本的数据类型的数据类型组成组

10、成,并包括并包括一组相关的服务一组相关的服务（或称操（或称操作）作）特征是使用与实现相分离，实行特征是使用与实现相分离，实行信息隐蔽信息隐蔽和和数据封装数据封装。在抽象数据类型设计时，把类型的声明与其实现分离开来。在抽象数据类型设计时，把类型的声明与其实现分离开来。在抽象数据类型设计时，把类型的声明与其实现分离开来。在抽象数据类型设计时，把类型的声明与其实现分离开来。第10页，本讲稿共40页抽抽象象数数据据类类型型第11页，本讲稿共40页严格区分抽象数据类型的两个不同视图严格区分抽象数据类型的两个不同视图从使用者角度从使用者角度 只要了解该抽象数据类型的规格说明，就可以利用其公共界只要了解该抽

11、象数据类型的规格说明，就可以利用其公共界只要了解该抽象数据类型的规格说明，就可以利用其公共界只要了解该抽象数据类型的规格说明，就可以利用其公共界面中的服务来使用这个类型，而不必关心其物理实现，这样使面中的服务来使用这个类型，而不必关心其物理实现，这样使面中的服务来使用这个类型，而不必关心其物理实现，这样使面中的服务来使用这个类型，而不必关心其物理实现，这样使用者可以在开发过程中抓住重点，集中精力考虑如何解决应用用者可以在开发过程中抓住重点，集中精力考虑如何解决应用用者可以在开发过程中抓住重点，集中精力考虑如何解决应用用者可以在开发过程中抓住重点，集中精力考虑如何解决应用问题，使问题得到简化。问

12、题，使问题得到简化。问题，使问题得到简化。问题，使问题得到简化。从实现者角度从实现者角度 把抽象数据类型的物理实现封装起来，有利于编码、测试以及将来把抽象数据类型的物理实现封装起来，有利于编码、测试以及将来把抽象数据类型的物理实现封装起来，有利于编码、测试以及将来把抽象数据类型的物理实现封装起来，有利于编码、测试以及将来修改。因为这样做可以使错误局部化，一旦出现错误，其传播范围不修改。因为这样做可以使错误局部化，一旦出现错误，其传播范围不修改。因为这样做可以使错误局部化，一旦出现错误，其传播范围不修改。因为这样做可以使错误局部化，一旦出现错误，其传播范围不至于影响其它模块。至于影响其它模块。至

13、于影响其它模块。至于影响其它模块。如果为了提高效率希望改进数据结构，可能需要改变抽象数如果为了提高效率希望改进数据结构，可能需要改变抽象数如果为了提高效率希望改进数据结构，可能需要改变抽象数如果为了提高效率希望改进数据结构，可能需要改变抽象数据类型的物理实现，但只要界面中的服务的使用方式不变，其据类型的物理实现，但只要界面中的服务的使用方式不变，其据类型的物理实现，但只要界面中的服务的使用方式不变，其据类型的物理实现，但只要界面中的服务的使用方式不变，其它所有使用该数据类型的程序都可以不变，从而大大提高系统它所有使用该数据类型的程序都可以不变，从而大大提高系统它所有使用该数据类型的程序都可以不

14、变，从而大大提高系统它所有使用该数据类型的程序都可以不变，从而大大提高系统稳定性。稳定性。稳定性。稳定性。第12页，本讲稿共40页 数据结构的抽象层次最高的数据抽象是一个聚集类，其作用是把所有的数据抽象关最高的数据抽象是一个聚集类，其作用是把所有的数据抽象关最高的数据抽象是一个聚集类，其作用是把所有的数据抽象关最高的数据抽象是一个聚集类，其作用是把所有的数据抽象关联在一起，代表数据结构，并给出数据结构都具有的操作联在一起，代表数据结构，并给出数据结构都具有的操作联在一起，代表数据结构，并给出数据结构都具有的操作联在一起，代表数据结构，并给出数据结构都具有的操作初始化初始化初始化初始化(init

15、ialinitial)、插入插入插入插入(insertinsert)、删除、删除、删除、删除(deletedelete)和查找和查找和查找和查找(searchsearch)。第13页，本讲稿共40页线性聚类线性聚类线性表线性表 类中所有数据成员都按某种次序排列在一个序列中。类中所有数据成员都按某种次序排列在一个序列中。类中所有数据成员都按某种次序排列在一个序列中。类中所有数据成员都按某种次序排列在一个序列中。根据对聚集中元素存取方法的不同：根据对聚集中元素存取方法的不同：根据对聚集中元素存取方法的不同：根据对聚集中元素存取方法的不同：直接存取类直接存取类直接存取类直接存取类 数组、记录、文件数

16、组、记录、文件数组、记录、文件数组、记录、文件 直接存取某一指定项而不须先访问其前驱。直接存取某一指定项而不须先访问其前驱。直接存取某一指定项而不须先访问其前驱。直接存取某一指定项而不须先访问其前驱。顺序存取类顺序存取类顺序存取类顺序存取类 栈、队列、表栈、队列、表栈、队列、表栈、队列、表 只能从序列中第一个元素起，按序逐个访问到指定的元素。只能从序列中第一个元素起，按序逐个访问到指定的元素。只能从序列中第一个元素起，按序逐个访问到指定的元素。只能从序列中第一个元素起，按序逐个访问到指定的元素。广义索引类广义索引类广义索引类广义索引类 散列表、词典散列表、词典散列表、词典散列表、词典“关键码关

17、键码关键码关键码值值值值”偶对的集合。偶对的集合。偶对的集合。偶对的集合。第14页，本讲稿共40页非线性聚类非线性聚类 所有数据元素与其它数据元素之间不存在简单的线性所有数据元素与其它数据元素之间不存在简单的线性所有数据元素与其它数据元素之间不存在简单的线性所有数据元素与其它数据元素之间不存在简单的线性关系。关系。关系。关系。根据关系的不同：根据关系的不同：根据关系的不同：根据关系的不同：层次聚集类层次聚集类层次聚集类层次聚集类 树，二叉树，堆树，二叉树，堆树，二叉树，堆树，二叉树，堆 按层次划分的数据元素的集合，指定层次上元素可以有零个或按层次划分的数据元素的集合，指定层次上元素可以有零个或

18、按层次划分的数据元素的集合，指定层次上元素可以有零个或按层次划分的数据元素的集合，指定层次上元素可以有零个或多个处于下一层次上的直接后继。多个处于下一层次上的直接后继。多个处于下一层次上的直接后继。多个处于下一层次上的直接后继。群聚集类群聚集类群聚集类群聚集类 集合，图集合，图集合，图集合，图 所有元素之间没有任何顺序关系。所有元素之间没有任何顺序关系。所有元素之间没有任何顺序关系。所有元素之间没有任何顺序关系。第15页，本讲稿共40页线性聚集类中各数据成员之间的线性关系树形结构树形结构树树 二叉树二叉树 二叉搜索树二叉搜索树第16页，本讲稿共40页堆结构“最大最大”堆堆 “最小最小”堆堆第1

19、7页，本讲稿共40页群聚类图结构图结构 网络结构网络结构第18页，本讲稿共40页算法定义 定义：定义：定义：定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个有穷的指令集，这些指令为解决某一特定任务规定了一个有穷的指令集，这些指令为解决某一特定任务规定了一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列。一个运算序列。一个运算序列。一个运算序列。特性：特性：特性：特性：输入输入输入输入 必须有必须有必须有必须有0 0 0 0个或多个输入，是算法开始运算前给于算法的量。个或多个输入，是算法开始运算前给于算法的量。个或多个输入，是算法开始运算前给于算法的量。个或多个输入，是算

20、法开始运算前给于算法的量。输出输出输出输出 应有一个或多个输出应有一个或多个输出应有一个或多个输出应有一个或多个输出(处理结果处理结果处理结果处理结果)，输出的量是算法计，输出的量是算法计，输出的量是算法计，输出的量是算法计算的结果。算的结果。算的结果。算的结果。确定性确定性确定性确定性 每步定义都是确切、无歧义的，对于每一种情况，需要每步定义都是确切、无歧义的，对于每一种情况，需要每步定义都是确切、无歧义的，对于每一种情况，需要每步定义都是确切、无歧义的，对于每一种情况，需要执行的动作都应严格地、清晰地规定。执行的动作都应严格地、清晰地规定。执行的动作都应严格地、清晰地规定。执行的动作都应严

21、格地、清晰地规定。有穷性有穷性有穷性有穷性 算法应在执行有穷步后结束。算法应在执行有穷步后结束。算法应在执行有穷步后结束。算法应在执行有穷步后结束。有效性有效性有效性有效性 每一条运算应足够基本，原则上能够精确执行，甚至人每一条运算应足够基本，原则上能够精确执行，甚至人每一条运算应足够基本，原则上能够精确执行，甚至人每一条运算应足够基本，原则上能够精确执行，甚至人们仅用笔和纸做有限次运算就能完成。们仅用笔和纸做有限次运算就能完成。们仅用笔和纸做有限次运算就能完成。们仅用笔和纸做有限次运算就能完成。第19页，本讲稿共40页 事例学习：事例学习：事例学习：事例学习：选择排序问题选择排序问题选择排序

22、问题选择排序问题 明确问题：明确问题：明确问题：明确问题：非递减排序非递减排序非递减排序非递减排序 解决方案：解决方案：解决方案：解决方案：逐个选择最小数据逐个选择最小数据逐个选择最小数据逐个选择最小数据 算法框架：算法框架：算法框架：算法框架：for(intfor(int i=i=0;0;in-in-1;1;i+i+)/)/n n-1-1趟趟趟趟 从从从从a a i i 检查到检查到检查到检查到a a n-n-1;1;若最小的整数在若最小的整数在若最小的整数在若最小的整数在a a k k,交换交换交换交换a a i i 与与与与a a k k;细化程序：细化程序：细化程序：细化程序：程序程序

23、程序程序 SelectSortSelectSort 如何选择值最小的数据；如何选择值最小的数据；如何选择值最小的数据；如何选择值最小的数据；如何交换两个数据的值。如何交换两个数据的值。如何交换两个数据的值。如何交换两个数据的值。算法设计算法设计 自顶向下，逐步求精自顶向下，逐步求精 第20页，本讲稿共40页 void selectSort(int a,const int n)/对对n个整数个整数a0,a1,an-1,按非递减顺序排序按非递减顺序排序 for(int i=0;in-1;i+)int k=i;/从从ai检查到检查到an-1,找最小的整数找最小的整数,在在ak for(int j=i

24、+1;jn;j+)if(aj 00第30页，本讲稿共40页例例 以迭代方式求累加和的函数以迭代方式求累加和的函数行行行行 float sum(float a,const int n)1 2 float s=0.0;3 for(int i=0;in;i+)4 s+=ai;5 return s;6 程序步确定方法程序步确定方法 在程序中插入计数全局变量在程序中插入计数全局变量countcount；建表，列出程序内各个语句的程序步数。建表，列出程序内各个语句的程序步数。第31页，本讲稿共40页 在求累加和程序中加入在求累加和程序中加入count语句语句 float sum(float a,const

25、 int n)float s=0.0;count+;/count是全局变量，统计执行语句条数是全局变量，统计执行语句条数 for(int i=0;in;i+)count+;/针对针对for语句语句 s+=ai;count+;/针对赋值语句针对赋值语句 count+;/针对针对for的最后一次的最后一次 count+;/针对针对return语句语句 return s;执行结束得执行结束得 程序步数程序步数count=2*n+3第32页，本讲稿共40页程序的简化形式程序的简化形式 void sum(float a,const int n)for(int i=0;in;i+)count+=2;cou

26、nt+=3;第33页，本讲稿共40页注意：注意：一个语句本身的程序步数可能不等于该语句一一个语句本身的程序步数可能不等于该语句一次执行所具有的程序步数。次执行所具有的程序步数。例如：赋值语句例如：赋值语句x=sum(R,n);本身的程序步数为本身的程序步数为1；一次执行对函数一次执行对函数 sum(R,n)的调用需要的程序步的调用需要的程序步数为数为 2*n+3；一次执行的程序步数为一次执行的程序步数为1+2*n+3=2*n+4第34页，本讲稿共40页时间复杂性的渐进表示法全面分析一个算法，需要考虑在最坏、最好、全面分析一个算法，需要考虑在最坏、最好、平均情况下的时间代价。平均情况下的时间代价

27、。大大O表示法表示法最坏情况最坏情况 当且仅当存在正整数当且仅当存在正整数当且仅当存在正整数当且仅当存在正整数c c和和和和n n0 0，使得，使得，使得，使得T T(n n)cf(n n)对所有对所有对所有对所有的的的的n n n n0成立，则称该算法的渐进时间复杂度为成立，则称该算法的渐进时间复杂度为成立，则称该算法的渐进时间复杂度为成立，则称该算法的渐进时间复杂度为T T(n n)=)=O O(f(n n)。当实例特性当实例特性n n充分大时，算法的时间复杂度随充分大时，算法的时间复杂度随n n变化，在最坏情况下若存在一个增长的上界，即变化，在最坏情况下若存在一个增长的上界，即变化，在最

28、坏情况下若存在一个增长的上界，即变化，在最坏情况下若存在一个增长的上界，即cfcf(n)，则该算法的时间复杂度增长的数量级为，则该算法的时间复杂度增长的数量级为，则该算法的时间复杂度增长的数量级为，则该算法的时间复杂度增长的数量级为f f(n n)，即称该算法的渐进时间复杂度为，即称该算法的渐进时间复杂度为，即称该算法的渐进时间复杂度为，即称该算法的渐进时间复杂度为T T(n n)=)=O O(f f(n n)。第35页，本讲稿共40页 大大大大O表示法的使用表示法的使用 需要考虑关键操作的程序步数；需要考虑关键操作的程序步数；需要考虑关键操作的程序步数；需要考虑关键操作的程序步数；关键操作大

29、多在循环和递归中；关键操作大多在循环和递归中；关键操作大多在循环和递归中；关键操作大多在循环和递归中；在大多数场合中，程序步骤与执行频度一一对应。在大多数场合中，程序步骤与执行频度一一对应。在大多数场合中，程序步骤与执行频度一一对应。在大多数场合中，程序步骤与执行频度一一对应。如果给出的是渐进值，可直接考虑关键操作的执行频度，提出其如果给出的是渐进值，可直接考虑关键操作的执行频度，提出其如果给出的是渐进值，可直接考虑关键操作的执行频度，提出其如果给出的是渐进值，可直接考虑关键操作的执行频度，提出其与实例特性与实例特性与实例特性与实例特性n n的函数关系的函数关系的函数关系的函数关系g g(n

30、n)，从而得到渐进时间复杂度，从而得到渐进时间复杂度，从而得到渐进时间复杂度，从而得到渐进时间复杂度。渐进时间复杂度的计算渐进时间复杂度的计算渐进时间复杂度的计算渐进时间复杂度的计算 单个循环单个循环单个循环单个循环 在循环内的简单语句即为关键操作，该程序段的渐进时在循环内的简单语句即为关键操作，该程序段的渐进时在循环内的简单语句即为关键操作，该程序段的渐进时在循环内的简单语句即为关键操作，该程序段的渐进时间复杂度应是此关键操作的执行频度的大间复杂度应是此关键操作的执行频度的大间复杂度应是此关键操作的执行频度的大间复杂度应是此关键操作的执行频度的大O O表示。表示。表示。表示。第36页，本讲稿

31、共40页 几个并列的循环几个并列的循环几个并列的循环几个并列的循环 先分析每个循环的渐进时间复杂度，然后利用先分析每个循环的渐进时间复杂度，然后利用先分析每个循环的渐进时间复杂度，然后利用先分析每个循环的渐进时间复杂度，然后利用大大大大O O表示表示表示表示法的加法规则来计算渐进时间复杂度。法的加法规则来计算渐进时间复杂度。法的加法规则来计算渐进时间复杂度。法的加法规则来计算渐进时间复杂度。大大大大O O表示法的加法规则表示法的加法规则表示法的加法规则表示法的加法规则 当两个并列的程序段的时间代价分别为当两个并列的程序段的时间代价分别为当两个并列的程序段的时间代价分别为当两个并列的程序段的时间

32、代价分别为T T1 1(n n)=)=O O(f f(n n)和和和和T T2 2(mm)=)=O O(g g(mm)时，时，时，时，则将两个程序段连在一起后整个程序段的时间代价为：则将两个程序段连在一起后整个程序段的时间代价为：则将两个程序段连在一起后整个程序段的时间代价为：则将两个程序段连在一起后整个程序段的时间代价为：T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)所谓所谓所谓所谓(max(f(n),g(m)，是指当，是指当，是指当，是指当n n与与与与mm充分大时充分大时充分大时充分大时f(n)与与与与g(m)中的大值，具中的大值，具中的大值，具中的大值，具有如下关

33、系：有如下关系：有如下关系：有如下关系：c log2n n nlog2n n2 n3 2n 3n n!取取取取c、log2n、n、nlog2n时间效率比较高；时间效率比较高；时间效率比较高；时间效率比较高；取取取取n2、n3时间效率差强人意；时间效率差强人意；时间效率差强人意；时间效率差强人意；取取取取2n、3n、n!当当当当n n稍微大一点，算法的时间代价变为很大，稍微大一点，算法的时间代价变为很大，稍微大一点，算法的时间代价变为很大，稍微大一点，算法的时间代价变为很大，以至于不能计算。以至于不能计算。以至于不能计算。以至于不能计算。第37页，本讲稿共40页两个并列循环的例子两个并列循环的例

34、子 void example(float x ,int m,int n,int k)float sum ;for(int i=0;im;i+)/x 中各行中各行 sumi=0.0;/数据累加数据累加 for(int j=0;jn;j+)sumi+=xij;/关键操作关键操作1，渐进时间复杂度为，渐进时间复杂度为O(m*n)。for(i=0;i m;i+)/打印各行数据和打印各行数据和 printf(Line%d:%dn“,i,sum i);/关键操作关键操作2，渐进时间复杂度为，渐进时间复杂度为O(m)。/根据大根据大o表示法的加法规则，渐进时间复杂度为表示法的加法规则，渐进时间复杂度为O(m

35、ax(m*n,m)第38页，本讲稿共40页n n多层的嵌套循环多层的嵌套循环n n关键操作应该在最内层循环中，先自外向内层层分析关键操作应该在最内层循环中，先自外向内层层分析关键操作应该在最内层循环中，先自外向内层层分析关键操作应该在最内层循环中，先自外向内层层分析每层循环的时间渐进复杂度，然后利用每层循环的时间渐进复杂度，然后利用每层循环的时间渐进复杂度，然后利用每层循环的时间渐进复杂度，然后利用大大大大O O表示法的表示法的表示法的表示法的乘法规则来计算渐进时间复杂度。乘法规则来计算渐进时间复杂度。乘法规则来计算渐进时间复杂度。乘法规则来计算渐进时间复杂度。n n大大大大O O表示法的乘法

36、规则表示法的乘法规则表示法的乘法规则表示法的乘法规则n n当两个嵌套的程序段的时间代价分别为当两个嵌套的程序段的时间代价分别为当两个嵌套的程序段的时间代价分别为当两个嵌套的程序段的时间代价分别为T T1 1(n n)=)=OO(f f(n n)和和和和T T2 2(mm)=)=OO(g g(mm)时，时，时，时，n n整个程序的时间代价为整个程序的时间代价为整个程序的时间代价为整个程序的时间代价为T(n,m)=T1(n)*T2(m)=O(f(n)*g(m)n n如果一个程序的循环中有一个包含有循环的函数调如果一个程序的循环中有一个包含有循环的函数调如果一个程序的循环中有一个包含有循环的函数调如

37、果一个程序的循环中有一个包含有循环的函数调用语句，也可以在被调用的函数内部寻找关键操作，用语句，也可以在被调用的函数内部寻找关键操作，用语句，也可以在被调用的函数内部寻找关键操作，用语句，也可以在被调用的函数内部寻找关键操作，使用乘法规则来计算渐进时间复杂度。使用乘法规则来计算渐进时间复杂度。使用乘法规则来计算渐进时间复杂度。使用乘法规则来计算渐进时间复杂度。第39页，本讲稿共40页/冒泡排序的算法冒泡排序的算法 void bubbleSort(int Element,int ArraySize)/对表对表Element0到到ElementArraySize-1逐趟进行比较逐趟进行比较,ArraySize是是表当前长度表当前长度 int i=1;int exchange=1;/当当exchange为为0则停止排序则停止排序 while(i=i;j-)if(Elementj-1 Elementj)/执行频度为执行频度为n-i Swap(j-1,j);exchange=1;/置置“发生了交换发生了交换”标志标志 /执行频度至多为执行频度至多为f(n)=n-1 i+;/一趟比较一趟比较 渐进时间复杂度渐进时间复杂度 O(f(n)*g(n)=O(n-1)*(n-i)=O()=O()第一章结束第一章结束第40页，本讲稿共40页