数据结构概念精.ppt

1第1页，本讲稿共72页n n什么是数据结构什么是数据结构n n抽象数据类型及面向对象概念抽象数据类型及面向对象概念n n算法定义算法定义n n模板模板n n算法简单性能分析与度量算法简单性能分析与度量第一章第一章 数据结构概念数据结构概念第2页，本讲稿共72页“学生”表格第3页，本讲稿共72页“课程”表格第4页，本讲稿共72页学生学生(学号学号,姓名姓名,性别性别,籍贯籍贯)课程课程(课程号课程号,课程名课程名,学分学分)选课选课(学号学号,课程号课程号,成绩成绩)“选课单选课单”包含如下信息包含如下信息 学号学号 课程编号课程编号 成绩成绩 时间时间 学生选课系统中实体构成的网状关系学生选课系统中实体构成的网状关系学生选课系统中实体构成的网状关系学生选课系统中实体构成的网状关系第5页，本讲稿共72页UNIX文件系统的系统结构图文件系统的系统结构图/(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp第6页，本讲稿共72页数据（数据（datadata）n数据是数据是信息信息的载体，是描述客观事物的数、字的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。序识别和处理的符号的集合。n数据的分类：数据的分类：u 数值性数据数值性数据u 非数值性数据非数值性数据第7页，本讲稿共72页姓名姓名 所在院系所在院系 性别性别 出生日期出生日期 年年 月月职务职务业绩业绩数据元素数据元素(data element)(data element)n数据的基本单位。在计算机程序中常作为一个整数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。体进行考虑和处理。n有时一个数据元素可以由若干有时一个数据元素可以由若干数据项数据项(Data Item)组成。数据项是具有独立含义组成。数据项是具有独立含义的最小标的最小标识单位。识单位。n数据元素又称为元素、结点、记录。数据元素又称为元素、结点、记录。第8页，本讲稿共72页什么是数据结构什么是数据结构定义定义:由某一数据元素的集合以及该集合中所有数据元由某一数据元素的集合以及该集合中所有数据元素之间的关系组成。记为：素之间的关系组成。记为：Data_Structure=D,R 其中，其中，D 是某一数据元素的集合，是某一数据元素的集合，R 是该集合是该集合中所有数据元素之间的关系的有限集合中所有数据元素之间的关系的有限集合。第9页，本讲稿共72页例：例：N N 个网点之间的连通关系个网点之间的连通关系 树形关系树形关系网状关系网状关系156152436243第10页，本讲稿共72页数据结构是数据的组织形式数据结构是数据的组织形式n包括三个方面：包括三个方面：数据元素间的逻辑关系，即数据的数据元素间的逻辑关系，即数据的逻辑结构逻辑结构；数据元素及其关系在计算机存储内的表示，即数据元素及其关系在计算机存储内的表示，即数据的数据的存储表示存储表示；数据的运算，即对数据元素施加的数据的运算，即对数据元素施加的操作操作。第11页，本讲稿共72页数据的逻辑结构数据的逻辑结构n数据的逻辑结构从逻辑关系上描述数据，与数数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关；据的存储无关；n数据的逻辑结构可以看作是从具体问题抽象出来数据的逻辑结构可以看作是从具体问题抽象出来的数据模型；的数据模型；n数据的逻辑结构与数据元素本身的形式、内容无数据的逻辑结构与数据元素本身的形式、内容无关；关；n数据的逻辑结构与数据元素的相对存储位置无关。数据的逻辑结构与数据元素的相对存储位置无关。第12页，本讲稿共72页数据的逻辑结构分类数据的逻辑结构分类n线性结构线性结构 线性表线性表n非线性结构非线性结构 树树 图（或网络）图（或网络）第13页，本讲稿共72页线性结构线性结构树形结构树形结构树树 二叉树二叉树 二叉搜索树二叉搜索树bindevetclibuser14131211234567891031587101199874566231311第14页，本讲稿共72页堆结构堆结构 “最大最大”堆堆 “最小最小”堆堆123548711102916410121151236987第15页，本讲稿共72页图结构图结构 网络结构网络结构12543611331814665161921125634第16页，本讲稿共72页数据的存储结构数据的存储结构n数据的存储结构是逻辑结构用计算机语言的实现；数据的存储结构是逻辑结构用计算机语言的实现；n数据的存储结构依赖于计算机语言。数据的存储结构依赖于计算机语言。顺序存储表示顺序存储表示 链接存储表示链接存储表示 索引存储表示索引存储表示 散列存储表示散列存储表示主要用于内存的存主要用于内存的存储表示储表示主要用于外存主要用于外存(文文件件)的存储表示的存储表示第17页，本讲稿共72页抽象数据类型及面向对象概念抽象数据类型及面向对象概念n数据类型数据类型 定义：定义：一组性质相同的值的集合一组性质相同的值的集合,以及定以及定义于这个值集合上的一组操作的总称义于这个值集合上的一组操作的总称.nC语言中的数据类型语言中的数据类型 char int float double voidchar int float double void 字符型字符型 整型整型 浮点型浮点型 双精度型双精度型 无值无值 第18页，本讲稿共72页n构造数据类型由构造数据类型由基本数据类型基本数据类型或或构造数据类型构造数据类型组成。组成。n构造数据类型由构造数据类型由不同成分类型不同成分类型构成。构成。n基本数据类型可以看作是计算机中已实现的基本数据类型可以看作是计算机中已实现的数据结构。数据结构。n数据类型就是数据结构，不过它是从编程者数据类型就是数据结构，不过它是从编程者的角度来使用的。的角度来使用的。n数据类型是模板，必须定义属于某种数据类型的数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。变量，才能参加运算。第19页，本讲稿共72页抽象数据类型抽象数据类型 (ADTs:Abstract Data Types)(ADTs:Abstract Data Types)n抽象数据类型是由用户定义，用以表示应用问抽象数据类型是由用户定义，用以表示应用问题的数据模型。题的数据模型。n特点是：特点是：信息隐蔽信息隐蔽和和数据封装数据封装，使用与实现相使用与实现相分离分离。n抽象数据类型可用抽象数据类型可用（D,S,P）三元组表示，其三元组表示，其中，中，D 是数据元素的集合（简称数据对象），是数据元素的集合（简称数据对象），S 是是 D上的关系集合，上的关系集合，P 是对是对 D 的基本操作集的基本操作集合。合。第20页，本讲稿共72页抽抽象象数数据据类类型型查找查找 登录登录 删除删除 修改修改 符符 号号 表表第21页，本讲稿共72页抽象数据类型的描述抽象数据类型的描述n其其中中数数据据对对象象、数数据据之之间间的的关关系系用用伪伪码码描描述述；基本操作定义格式为基本操作定义格式为ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象的定义数据对象：数据对象的定义 数据关系：数据关系的定义数据关系：数据关系的定义 基本操作：基本操作的定义基本操作：基本操作的定义 ADT 抽象数据类型名抽象数据类型名基本操作名（参数表）基本操作名（参数表）前置条件：先决条件描述前置条件：先决条件描述后置条件：操作结果描述后置条件：操作结果描述第22页，本讲稿共72页n基基本本操操作作有有两两种种参参数数：赋赋值值参参数数只只为为操操作作提提供供输输入入值值；引引用用参参数数以以&打打头头，除除可可提提供供输输入入值值外外，还将返回操作结果。还将返回操作结果。n “前前置置条条件件”描描述述了了操操作作执执行行之之前前数数据据结结构构和和参参数数应应满满足足的的先先决决条条件件，若若不不满满足足，则则操操作作失失败败，并返回相应出错信息。并返回相应出错信息。n “后后置置条条件件”说说明明了了操操作作正正常常完完成成之之后后，数数据据结结构构的的变变化化状状况况和和应应返返回回的的结结果果。若若前前置置条条件件为为空空，则则省略之。省略之。第23页，本讲稿共72页自然数的抽象数据类型定义自然数的抽象数据类型定义ADT NaturalNumber isobjects:一个整数的有序子集合一个整数的有序子集合,它开始于它开始于0,结束于机器能表示的最大整数结束于机器能表示的最大整数(MaxInt)。Function:对于所有的对于所有的 x,y NaturalNumber;False,True Boolean,+、-、=、=等都是可用等都是可用的服务。的服务。Zero():NaturalNumber /前置条件前置条件：无：无 /后置条件后置条件：返回自然数返回自然数0 第24页，本讲稿共72页 IsZero(x):Boolean /前置条件前置条件：x为为NaturalNumber /后置条件后置条件：if(x=0)then 返回返回True else 返回返回False Add(x,y):NaturalNumber /前置条件前置条件：x,y为为NaturalNumber且且x+yMaxInt /后置条件后置条件：返回返回 x+y Subtract(x,y):NaturalNumber /前置条件前置条件：x,y为为NaturalNumber且且xy /后置条件后置条件：返回返回 x-y 第25页，本讲稿共72页 Equal(x,y):Boolean /前置条件前置条件：x,y为为NaturalNumber /后置条件后置条件：if(x=y)返回返回True else 返回返回 False Successor(x):NaturalNumber /前置条件前置条件：x为为NaturalNumber /后置条件后置条件：if(x=MaxInt)返回返回 x else 返回返回 x+1end NaturalNumber第26页，本讲稿共72页面向对象的概念面向对象的概念n面向对象面向对象=对象类继承通信对象类继承通信n对象对象在应用问题中出现的各种在应用问题中出现的各种实体实体、事件事件、规规格说明格说明等。等。由一组由一组属性值属性值和在这组值上的一组和在这组值上的一组服务服务（或称操作）构成。（或称操作）构成。与与C中构造数据类型不同在于：中构造数据类型不同在于：C中的构造中的构造数据类型的变量仅涉及属性值，与操作分数据类型的变量仅涉及属性值，与操作分离，而离，而C+中的对象则不然。中的对象则不然。第27页，本讲稿共72页n类类(class)，实例，实例(instance)具有相同属性和服务的对象归于同一类，具有相同属性和服务的对象归于同一类，形成类。形成类。类中的对象为该类的实例。类中的对象为该类的实例。同一类的实例同一类的实例n共享类的属性和类的操作；共享类的属性和类的操作；n通过继承共享其父类的公共的和保护通过继承共享其父类的公共的和保护性的属性和操作；性的属性和操作；n同一类的不同实例有不同的属性值。同一类的不同实例有不同的属性值。第28页，本讲稿共72页四边形类及其对象四边形类及其对象属性aPoint1 aPoint2aPoint3 aPoint4服务服务Draw()move(x,y)contains(aPoint)属性值属性值quadrilateral1quadrilateral2(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第29页，本讲稿共72页n继承继承u派生类（子类）：派生类（子类）：四边形，三角形，四边形，三角形，u基类（父类）：基类（父类）：多边形多边形派生类派生类继承的特性继承的特性+特有的特性特有的特性基类基类多边形多边形四边形四边形三角形三角形六边形六边形第30页，本讲稿共72页n通信通信u消息传递消息传递uC+中消息传递的方式：中消息传递的方式：定义：定义：Point p;void move(int x,inty);使用：使用：p.move(x,y);uC中则不同，需使用函数调用方式：中则不同，需使用函数调用方式：定义：定义：Point p;void move(Point q,int x,inty);使用：使用：move(p,x,y);第31页，本讲稿共72页Draw()move(x,y)contains(aPoint)PolygonreferencePointVerticesPolygon 类类referencePointVerticesDraw()move(x,y)contains(aPoint)Polygon的子类的子类Quadrilateral类类Quadrilateral第32页，本讲稿共72页算法定义算法定义n定义：定义：一个有穷的指令集一个有穷的指令集，这些指令为解决某，这些指令为解决某一特定任务规定了一个运算序列一特定任务规定了一个运算序列n特性：特性：u输入输入 有有0个或多个输入个或多个输入u输出输出 有一个或多个输出有一个或多个输出(处理结果处理结果)u确定性确定性 每步定义都是确切无歧义的每步定义都是确切无歧义的u有穷性有穷性 算法应在执行有穷步后结束算法应在执行有穷步后结束u有效性有效性 每一条运算应足够基本每一条运算应足够基本第33页，本讲稿共72页n事例学习：事例学习：选择排序问题选择排序问题n明确问题：明确问题：递增排序递增排序n解决方案：解决方案：逐个选择最小数据逐个选择最小数据n算法框架：算法框架：for(int i=0;i n-1;i+)/n-1趟趟 从从ai检查到检查到an-1;若最小整数在若最小整数在ak,交换交换ai与与ak;n细化程序：细化程序：程序程序 SelectSort 算法设计算法设计 自顶向下，逐步求精自顶向下，逐步求精 第34页，本讲稿共72页 void selectSort(int a,const int n)/对n个整数a0,a1,an-1按递增顺序排序 for(int i=0;i n-1;i+)int k=i;/从ai查到an-1,找最小整数,在ak for(int j=i+1;j n;j+)if(aj ak)k=j;int temp=ai;ai=ak;ak=temp;第35页，本讲稿共72页模板模板 (template)(template)定义定义 适合适合多种数据类型多种数据类型的的类定义类定义或或算法算法，在特定环，在特定环境下通过简单地代换，变成境下通过简单地代换，变成针对具体某种数据针对具体某种数据类型类型的的类定义类定义或或算法。算法。第36页，本讲稿共72页用模板定义用于排序的数据表类用模板定义用于排序的数据表类#ifndef DATALIST_H#define DATALIST_H#include /K是表项关键码类型template /E是表项类型class dataList private:E*element;int listSize;void swap(int m1,int m2);int minKey(int low,int high);第37页，本讲稿共72页 public:dataList(int size=10):listSize(size),element(new Esize)dataList()delete element;void sort();friend ostream&operator (ostream&outStream,dataList&outList);friend istream&operator (istream&inStream,dataList&inList);#endif 第38页，本讲稿共72页类中所有操作作为模板函数的实现类中所有操作作为模板函数的实现template void dataList :swap(int m1,int m2)/交换由m1,m2为下标的数组元素的值 E temp=element m1;element m1=element m2;element m2=temp;第39页，本讲稿共72页template int dataList:minKey(int low,int high)/查找数组Elementlow到Elementhigh中具/有最小关键码值的表项，函数返回其位置 int min=low;for(int i=low+1,i=high,i+)if(elementi elementmin)min=i;return min;定义的重载操作定义的重载操作第40页，本讲稿共72页template ostream&operator (ostream&outStream,dataList outList)outStream “输出数组内容:n”;for(int i=0;i outList.listSize;i+)outStream outList.elementi;outStream endl;ouStream “输出数组当前大小:”outList.listSize endl;return outStream;第41页，本讲稿共72页 template istream&operator (istream&inStream,dataList inList)/输入对象为inList，输入流对象为inStream cout inList.listSize;cout “输入数组元素值:n”;for(int i=0;i inList.listSize;i+)cout “元素”i inList.elementi;return inStream;第42页，本讲稿共72页template void dataList:sort()/按非递减顺序对按非递减顺序对listSize个关键码个关键码element0到到/elementArraySize-1排序排序 for(int i=0;i=listSize-2;i+)int j=minKey(i,listSize-1);if(j!=i)swap(j,i);#endif 第43页，本讲稿共72页使用模板的选择排序算法的主函数使用模板的选择排序算法的主函数#include#include“dataList.h”const int SZ=10;int main()struct sick /患者 int key;char*name15;int age;char*address30;bool operator (sick x)return key x.key;第44页，本讲稿共72页 dataList TestList(SZ);cin TestList;cout TestList endl;TestList.Sort();cout TestList endl;return 0;定义对象时，代入定义对象时，代入实际数据类型实际数据类型重载友元操作重载友元操作标准标准IO操作操作消息通信消息通信第45页，本讲稿共72页算法简单性能分析与度量算法简单性能分析与度量n n算法的性能标准算法的性能标准n n算法的后期测试算法的后期测试n n算法的事前估计算法的事前估计第46页，本讲稿共72页算法的性能标准算法的性能标准n n正确性正确性(Correctness)算法应满足具体问题的需算法应满足具体问题的需求。求。n n可读性可读性(Readability)算法应该容易阅读。以算法应该容易阅读。以有利于阅读者对程序的理解。有利于阅读者对程序的理解。n n效率效率 效率指的是算法执行的时间和空间利用率。效率指的是算法执行的时间和空间利用率。通常这两者与问题的规模有关。通常这两者与问题的规模有关。n n健壮性健壮性(Robustness)算法应具有容错处理的算法应具有容错处理的功能。当输入非法数据时，算法应对其作出反功能。当输入非法数据时，算法应对其作出反应，而不应产生莫名其妙的输出结果。应，而不应产生莫名其妙的输出结果。第47页，本讲稿共72页算法的后期测试算法的后期测试n对一个算法要作出全面的分析可分成两个阶段进对一个算法要作出全面的分析可分成两个阶段进行，即行，即事前分析事前分析和和事后测试事后测试n事前分析事前分析要求事前求出该算法的一个时间界限要求事前求出该算法的一个时间界限函数。函数。n事后测试事后测试则要求在算法执行后通过算法执行则要求在算法执行后通过算法执行的时间和实际占用空间的统计资料来分析。的时间和实际占用空间的统计资料来分析。n事后分析要求在算法中的某些部位插装时间事后分析要求在算法中的某些部位插装时间函数函数 time()，测定算法完成某一功能所花费测定算法完成某一功能所花费时间。时间。第48页，本讲稿共72页例如，给出顺序搜索例如，给出顺序搜索(Sequenial Search)算法算法int seqsearch(int a,int n,int x)/在a0,an-1中搜索与给定值 x 相等的元/素，函数返回其位置，失败返回-1。int i=0;while(i n&ai!=x)i+;if(i=n)return-1;return i;第49页，本讲稿共72页 插装插装 time()的计时程序的计时程序 double start,stop;time(&start);int k=seqsearch(a,n,x);time(&stop);double runTime=stop-start;cout n runTime endl;事实上，算法运行时间要受事实上，算法运行时间要受输入规模、利用编译输入规模、利用编译程序生成的目标代码的质量、计算机程序指令系程序生成的目标代码的质量、计算机程序指令系统的品质和速度等制约。统的品质和速度等制约。第50页，本讲稿共72页算法的事前估计算法的事前估计n算法的事前估计主要包括时间复杂性和空间算法的事前估计主要包括时间复杂性和空间复杂性的分析：复杂性的分析：u问题的规模：问题的规模：如：矩阵的阶数、图的结点个如：矩阵的阶数、图的结点个数、被分类序列的正整数个数等。数、被分类序列的正整数个数等。u时间复杂性时间复杂性：算法所需时间和问题规模的函：算法所需时间和问题规模的函数，记为数，记为 T(n)。当当 n 时的时间复杂性，时的时间复杂性，称为称为渐进时间复杂性渐进时间复杂性。u空间复杂性空间复杂性：算法所需空间和问题规模的：算法所需空间和问题规模的函数。记为函数。记为 S(n)。当当 n 时的时间复杂性，时的时间复杂性，称为称为渐进空间复杂性渐进空间复杂性。第51页，本讲稿共72页空间复杂度度量空间复杂度度量n n存储空间的固定部分存储空间的固定部分存储空间的固定部分存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分程序指令代码的空间，常数、简单变量、定长成分程序指令代码的空间，常数、简单变量、定长成分程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分、对象的数据成员等如数组元素、结构成分、对象的数据成员等)变变变变量所占空间量所占空间量所占空间量所占空间n n可变部分可变部分尺寸与实例特性有关的成分变量所占空间、引用变尺寸与实例特性有关的成分变量所占空间、引用变尺寸与实例特性有关的成分变量所占空间、引用变尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间、通过量所占空间、递归栈所用空间、通过量所占空间、递归栈所用空间、通过量所占空间、递归栈所用空间、通过new和和delete命令动态使用空间命令动态使用空间命令动态使用空间命令动态使用空间第52页，本讲稿共72页时间复杂度度量时间复杂度度量n n编译时间编译时间编译时间编译时间n n运行时间运行时间运行时间运行时间uu程序步程序步FF语法上或语义上有意义的一段指令序列；语法上或语义上有意义的一段指令序列；FF执行时间与问题规模无关；执行时间与问题规模无关；执行时间与问题规模无关；执行时间与问题规模无关；FF例如：例如：声明声明语句语句：程序步数为：程序步数为0;表达表达式式：程序步数为：程序步数为1第53页，本讲稿共72页n程序步确定方法程序步确定方法u插入计数全局变量插入计数全局变量countu建表，建表，列出个语句的程序步列出个语句的程序步例例 以迭代方式求累加和的函数以迭代方式求累加和的函数 float sum(float a,int n)float s=0.0;for(int i=0;i n;i+)s=s+ai;return s;第54页，本讲稿共72页在求累加和程序中加入在求累加和程序中加入 count 语句语句 float sum(float a,int n)float s=0.0;count+;/count 统计执行语句条数 for(int i=0;i n;i+)count+=2;/针对 for 语句s+=ai;count+;/针对赋值语句 count+=2;/针对 for 的最后一次 count+;/针对 return 语句 return s;执行结束得执行结束得 程序步数程序步数 count=3*n+4第55页，本讲稿共72页程序的简化形式程序的简化形式 void sum(float a,int n)for(int i=0;i n;i+)count+=3;count+=4;第56页，本讲稿共72页注意注意：一个语句本身的程序步数可能不等于该语句一一个语句本身的程序步数可能不等于该语句一次执行所具有的程序步数。次执行所具有的程序步数。例如：例如：赋值语句赋值语句x=sum(R,n)本身程序步数为本身程序步数为 1；一次执行对函数一次执行对函数 sum(R,n)的调用需要的程序步的调用需要的程序步数为数为 3*n+4；一次执行的程序步数为一次执行的程序步数为 1+3*n+4=3*n+5第57页，本讲稿共72页计算累加和程序计算累加和程序程序步数计算工作表格程序步数计算工作表格第58页，本讲稿共72页时间复杂度的渐进表示法时间复杂度的渐进表示法例例 求两个求两个n阶方阵的乘积阶方阵的乘积C=A Bvoid MatrixMultiply(int Ann,int Bnn,int Cnn)for(int i=0;i n;i+)2n+2 for(int j=0;j n;j+)n(2n+2)Cij=0;n2 for(int k=0;k n;k+)n2(2n+2)Cij=Cij+Aik*Bkj;n3 3n3+5n2+4n+2第59页，本讲稿共72页时间复杂度的渐进表示法时间复杂度的渐进表示法n算法中所有语句的频度之和是算法中所有语句的频度之和是矩阵阶数矩阵阶数n的函的函数数 T(n)=3n3+5n2+4n+2n一般地，称一般地，称 n 是问题的规模。则时间复杂度是问题的规模。则时间复杂度 T(n)是问题规模是问题规模 n 的函数。的函数。n当当n趋于无穷大时，把时间复杂度的数量级（阶）趋于无穷大时，把时间复杂度的数量级（阶）称为算法的渐进时间复杂度称为算法的渐进时间复杂度 T(n)=O(n3)大大O表示法表示法第60页，本讲稿共72页n加法规则加法规则 针对并列程序段针对并列程序段 T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)n各种函数的增长趋势各种函数的增长趋势 c log2n n nlog2n n2 n3 2n 3n n!第61页，本讲稿共72页T(n)=T1(n)+T2(n)+T3(n)=O(max(1,n,n2)=O(n2)变量计数变量计数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)x=0;y=0;for(int k=0;k n;k+)x+;第62页，本讲稿共72页n乘法规则乘法规则 针对嵌套程序段针对嵌套程序段 T(n,m)=T1(n)*T2(m)=O(f(n)*g(m)n渐进的空间复杂度渐进的空间复杂度 S(n)=O(f(n)n两个并列循环的例子两个并列循环的例子第63页，本讲稿共72页 void exam(float x ,int m,int n)float sum ;for(int i=0;i m;i+)/x中各行 sumi=0.0;/数据累加 for(int j=0;j n;j+)sumi+=xij;for(i=0;i m;i+)/打印各行数据和 cout i “:”sum i endl;渐进时间复杂度为渐进时间复杂度为 O(max(m*n,m)第64页，本讲稿共72页起泡排序起泡排序 void bubbleSort(int a,int n)/对表 a 逐趟比较,n 是表当前长度 for(int i=1;i=i;j-)/n-i次比较 if(aj-1 aj)int tmp=aj-1;aj-1=aj;aj=tmp;/一趟比较 第65页，本讲稿共72页渐进时间复杂度渐进时间复杂度 O(f(n)*g(n)=O(n2)BubblrSort 外层循环外层循环 n-1 趟趟内层循环内层循环 n-i 次比较次比较第66页，本讲稿共72页n有时有时,算法的时间复杂度不仅依赖于问题规模算法的时间复杂度不仅依赖于问题规模 n，还与输入实例的初始排列有关。，还与输入实例的初始排列有关。n在数组在数组 An 中查找给定值中查找给定值 k 的算法：的算法：int i=n-1;while(i=0&Ai!=k)i-;return i;n算法的语句算法的语句 i-的频度不仅与的频度不仅与 n 有关，还与有关，还与 A 中各元素的取值中各元素的取值以及以及 k 的取值的取值有关。有关。第67页，本讲稿共72页n例：设有两个算法在同一机器上运行，其执行时例：设有两个算法在同一机器上运行，其执行时间分别为间分别为 100n2 和和 2n，问：要使前者快于后者，问：要使前者快于后者，n 至少要取多大？至少要取多大？解答：解答：问题是找出满足问题是找出满足 100n2 2n=8192 n=14时，时，100n2=19600 2n=16384 n=15时，时，100n2=22500 arraySize 或者对于某一个或者对于某一个 k(0 k n)，使得，使得k!*2k maxInt 时，应按出错处理。时，应按出错处理。第69页，本讲稿共72页可有如下几种不同的出错处理方式：可有如下几种不同的出错处理方式：用用 cerr 及及 exit(1)语语句句来来终终止止执执行行并并报报告告错误；错误；用用返返回回整整数数函函数数值值 0,1 来来实实现现算算法法，以以区区别别是是正常返回还是错误返回；正常返回还是错误返回；在在函函数数的的参参数数表表设设置置一一个个引引用用型型的的整整型型变变量量来来区别是正常返回还是某中错误返回。区别是正常返回还是某中错误返回。抛出异常。抛出异常。第70页，本讲稿共72页#include#define n 100#define maxInt 0 x7fffffffbool calc(int T,int n)int i,value=1;if(n!=0)for(i=1;i maxInt/n/2)return false;/直接判断直接判断 i!*2i MaxInt 是危险的是危险的 value*=n*2;第71页，本讲稿共72页 Tn=value;/n!*2n Tn return true;void main()int An,i;for(i=0;i n;i+)if(!calc(A,i)cout failed at i endl;break;第72页，本讲稿共72页