数据结构清华大学版课件

《数据结构清华大学版课件》由会员分享，可在线阅读，更多相关《数据结构清华大学版课件（72页珍藏版）》请在装配图网上搜索。

1、第一章 数据结构概念数据结构电子教案数据结构电子教案殷人昆殷人昆 王王 宏宏1n n什么是数据结构什么是数据结构n n抽象数据类型及面向对象概念抽象数据类型及面向对象概念n n算法定义算法定义n n模板模板n n算法简单性能分析与度量算法简单性能分析与度量第一章第一章 数据结构概念数据结构概念2 2“学生”表格3 3“课程”表格4 4学生学生(学号学号,姓名姓名,性别性别,籍贯籍贯)课程课程(课程号课程号,课程名课程名,学分学分)选课选课(学号学号,课程号课程号,成绩成绩)“选课单选课单”包含如下信息包含如下信息 学号学号 课程编号课程编号 成绩成绩 时间时间 学生选课系统中实体构成的网状关系

2、学生选课系统中实体构成的网状关系5 5UNIX文件系统的系统结构图文件系统的系统结构图/(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp6 6数据（数据（datadata）n数据是数据是信息信息的载体，是描述客观事物的数、的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。机程序识别和处理的符号的集合。n数据的分类：数据的分类：u 数值性数据数值性数据u 非数值性数据非数值性数据7 7姓名姓名 所在院系所在院系 性别性别 出生日期出生日期

3、 年年 月月职务职务 业绩业绩数据元素数据元素(data element)(data element)n数据的基本单位。在计算机程序中常作为数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。一个整体进行考虑和处理。n有时一个数据元素可以由若干有时一个数据元素可以由若干数据项数据项(Data Item)组成。数据项是具有独立含义组成。数据项是具有独立含义的最小的最小标识单位。标识单位。n数据元素又称为元素、结点、记录。数据元素又称为元素、结点、记录。8 8什么是数据结构什么是数据结构定义定义:由某一数据元素的集合以及该集合中所有由某一数据元素的集合以及该集合中所有数据元素之间的关系组成

4、。记为：数据元素之间的关系组成。记为：Data_Structure=D,R 其中，其中，D 是某一数据元素的集合，是某一数据元素的集合，R 是该集是该集合中所有数据元素之间的关系的有限集合合中所有数据元素之间的关系的有限集合。9 9例：例：N N 个网点之间的连通关系个网点之间的连通关系树形关系树形关系网状关系网状关系1561524362431010数据结构是数据的组织形式数据结构是数据的组织形式n包括三个方面：包括三个方面：u数据元素间的逻辑关系，即数据的数据元素间的逻辑关系，即数据的逻辑逻辑结构结构；u数据元素及其关系在计算机存储内的表数据元素及其关系在计算机存储内的表示，即数据的示，即数

5、据的存储表示存储表示；u数据的运算，即对数据元素施加的数据的运算，即对数据元素施加的操作操作。11 11数据的逻辑结构数据的逻辑结构n数据的逻辑结构从逻辑关系上描述数据，与数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关；数据的存储无关；n数据的逻辑结构可以看作是从具体问题抽象数据的逻辑结构可以看作是从具体问题抽象出来的数据模型；出来的数据模型；n数据的逻辑结构与数据元素本身的形式、内数据的逻辑结构与数据元素本身的形式、内容无关；容无关；n数据的逻辑结构与数据元素的相对存储位置数据的逻辑结构与数据元素的相对存储位置无关。无关。1212数据的逻辑结构分类数据的逻辑结构分类n线性结构线性结构u

6、 线性表线性表n非线性结构非线性结构u 树树u 图（或网络）图（或网络）1313线性结构线性结构树形结构树形结构树树 二叉树二叉树 二叉搜索树二叉搜索树bindevetclibuser141312112345678910315871011998745662313111414堆结构堆结构 “最大最大”堆堆 “最小最小”堆堆1235487111029164101211512369871515图结构图结构 网络结构网络结构125436113318146651619211256341616数据的存储结构数据的存储结构n数据的存储结构是逻辑结构用计算机语言的数据的存储结构是逻辑结构用计算机语言的实现；实

7、现；n数据的存储结构依赖于计算机语言。数据的存储结构依赖于计算机语言。u 顺序存储表示顺序存储表示u 链接存储表示链接存储表示u 索引存储表示索引存储表示u 散列存储表示散列存储表示主要用于内存的主要用于内存的存储表示存储表示主要用于外存主要用于外存(文文件件)的存储表示的存储表示1717抽象数据类型及面向对象概念抽象数据类型及面向对象概念n数据类型数据类型 定义：定义：一组性质相同的值的集合一组性质相同的值的集合,以及定以及定义于这个值集合上的一组操作的总称义于这个值集合上的一组操作的总称.nC语言中的数据类型语言中的数据类型 char int float double void 字符型字符

8、型 整型整型 浮点型浮点型 双精度型双精度型 无值无值 1818n构造数据类型由构造数据类型由基本数据类型基本数据类型或或构造数据构造数据类型类型组成。组成。n构造数据类型由构造数据类型由不同成分类型不同成分类型构成。构成。n基本数据类型可以看作是计算机中已实现基本数据类型可以看作是计算机中已实现的数据结构。的数据结构。n数据类型就是数据结构，不过它是从编程数据类型就是数据结构，不过它是从编程者的角度来使用的。者的角度来使用的。n数据类型是模板，必须定义属于某种数据数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。类型的变量，才能参加运算。1919抽象数据类型抽象数据类型 (ADT

9、s:Abstract Data Types)(ADTs:Abstract Data Types)n抽象数据类型是由用户定义，用以表示应抽象数据类型是由用户定义，用以表示应用问题的数据模型。用问题的数据模型。n特点是：特点是：信息隐蔽信息隐蔽和和数据封装数据封装，使用与实使用与实现相分离现相分离。n抽象数据类型可用抽象数据类型可用（D,S,P）三元组表示，三元组表示，其中，其中，D 是数据元素的集合（简称数据对是数据元素的集合（简称数据对象），象），S 是是 D上的关系集合，上的关系集合，P 是对是对 D 的的基本操作集合。基本操作集合。2020抽抽象象数数据据类类型型查找查找 登录登录 删除删

10、除 修改修改 符符 号号 表表2121抽象数据类型的描述抽象数据类型的描述n其其中中数数据据对对象象、数数据据之之间间的的关关系系用用伪伪码码描描述；基本操作定义格式为述；基本操作定义格式为ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象的定义数据对象：数据对象的定义 数据关系：数据关系的定义数据关系：数据关系的定义 基本操作：基本操作的定义基本操作：基本操作的定义 ADT 抽象数据类型名抽象数据类型名基本操作名（参数表）基本操作名（参数表）前置条件：先决条件描述前置条件：先决条件描述后置条件：操作结果描述后置条件：操作结果描述2222n基基本本操操作作有有两两种种参参数数：赋赋值值参

11、参数数只只为为操操作作提提供供输输入入值值；引引用用参参数数以以&打打头头，除除可可提提供供输输入值外，还将返回操作结果。入值外，还将返回操作结果。n “前前置置条条件件”描描述述了了操操作作执执行行之之前前数数据据结结构构和和参参数数应应满满足足的的先先决决条条件件，若若不不满满足足，则则操操作失败，并返回相应出错信息。作失败，并返回相应出错信息。n “后后置置条条件件”说说明明了了操操作作正正常常完完成成之之后后，数数据据结结构构的的变变化化状状况况和和应应返返回回的的结结果果。若若前前置置条件为空，则省略之。条件为空，则省略之。2323自然数的抽象数据类型定义自然数的抽象数据类型定义AD

12、T NaturalNumber isobjects:一个整数的有序子集合一个整数的有序子集合,它开始于它开始于0,结束于机器能表示的最大整数结束于机器能表示的最大整数(MaxInt)。Function:对于所有的对于所有的 x,y NaturalNumber;False,True Boolean,+、-、=、=等都是等都是可用的服务。可用的服务。Zero():NaturalNumber /前置条件前置条件：无：无 /后置条件后置条件：返回自然数返回自然数0 2424 IsZero(x):Boolean /前置条件前置条件：x为为NaturalNumber /后置条件后置条件：if(x=0)th

13、en 返回返回True else 返回返回False Add(x,y):NaturalNumber /前置条件前置条件：x,y为为NaturalNumber且且x+yMaxInt /后置条件后置条件：返回返回 x+y Subtract(x,y):NaturalNumber /前置条件前置条件：x,y为为NaturalNumber且且xy /后置条件后置条件：返回返回 x-y 2525 Equal(x,y):Boolean /前置条件前置条件：x,y为为NaturalNumber /后置条件后置条件：if(x=y)返回返回True else 返回返回 False Successor(x):Nat

14、uralNumber /前置条件前置条件：x为为NaturalNumber /后置条件后置条件：if(x=MaxInt)返回返回 x else 返回返回 x+1end NaturalNumber2626面向对象的概念面向对象的概念n面向对象面向对象=对象类继承通信对象类继承通信n对象对象u在应用问题中出现的各种在应用问题中出现的各种实体实体、事件事件、规格说明规格说明等。等。u由一组由一组属性值属性值和在这组值上的一组和在这组值上的一组服务服务（或称操作）构成。（或称操作）构成。u与与C中构造数据类型不同在于：中构造数据类型不同在于：C中的中的构造数据类型的变量仅涉及属性值，与构造数据类型的变

15、量仅涉及属性值，与操作分离，而操作分离，而C+中的对象则不然。中的对象则不然。2727n类类(class)，实例，实例(instance)u具有相同属性和服务的对象归于同一类，具有相同属性和服务的对象归于同一类，形成类。形成类。u类中的对象为该类的实例。类中的对象为该类的实例。u同一类的实例同一类的实例共享类的属性和类的操作；共享类的属性和类的操作；通过继承共享其父类的公共的和保护通过继承共享其父类的公共的和保护性的属性和操作；性的属性和操作；同一类的不同实例有不同的属性值。同一类的不同实例有不同的属性值。2828四边形类及其对象四边形类及其对象属性aPoint1 aPoint2aPoint3

16、 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)服务服务服务服务quadrilateral2929n继承继承u派生类（子类）：派生类（子类）：四边形，三角形，四边形，三角形，u基类（父类）：基类（父类）：多边形多边形派生类派生类继承的特性继承的特性+特有的特

17、性特有的特性基类基类多边形多边形四边形四边形三角形三角形六边形六边形3030n通信通信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);3131Draw()move(x,y)contains(aPoint)PolygonreferencePointVerticesPolygon 类类refer

18、encePointVerticesDraw()move(x,y)contains(aPoint)Polygon的子类的子类Quadrilateral类类Quadrilateral3232算法定义算法定义n定义：定义：一个有穷的指令集一个有穷的指令集，这些指令为解，这些指令为解决某一特定任务规定了一个运算序列决某一特定任务规定了一个运算序列n特性：特性：u输入输入 有有0个或多个输入个或多个输入u输出输出 有一个或多个输出有一个或多个输出(处理结果处理结果)u确定性确定性 每步定义都是确切无歧义的每步定义都是确切无歧义的u有穷性有穷性 算法应在执行有穷步后结束算法应在执行有穷步后结束u有效性有效

19、性 每一条运算应足够基本每一条运算应足够基本3333n事例学习：事例学习：选择排序问题选择排序问题n明确问题：明确问题：递增排序递增排序n解决方案：解决方案：逐个选择最小数据逐个选择最小数据n算法框架：算法框架：for(int i=0;i n-1;i+)/n-1趟趟 从从ai检查到检查到an-1;若最小整数在若最小整数在ak,交换交换ai与与ak;n细化程序：细化程序：程序程序 SelectSort 算法设计算法设计 自顶向下，逐步求精自顶向下，逐步求精 3434 void selectSort(int a,const int n)/对n个整数a0,a1,an-1按递增顺序排序 for(int

20、 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;3535模板模板(template)(template)定义定义 适合适合多种数据类型多种数据类型的的类定义类定义或或算法算法，在特，在特定环境下通过简单地代换，变成定环境下通过简单地代换，变成针对具体某针对具体某种数据类型种数据类型的的类定义类定义或或算法。算法。3636用模板定义用于排序的数据表类用模板定义用于排序的数据表类#ifndef DATALIST_H#define DATALI

21、ST_H#include /K是表项关键码类型template /E是表项类型class dataList private:E*element;int listSize;void swap(int m1,int m2);int minKey(int low,int high);3737 public:dataList(int size=10):listSize(size),element(new Esize)dataList()delete element;void sort();friend ostream&operator (ostream&outStream,dataList&outLi

22、st);friend istream&operator (istream&inStream,dataList&inList);#endif 3838类中所有操作作为模板函数的实现类中所有操作作为模板函数的实现template void dataList :swap(int m1,int m2)/交换由m1,m2为下标的数组元素的值 E temp=element m1;element m1=element m2;element m2=temp;3939template int dataList:minKey(int low,int high)/查找数组Elementlow到Elementhigh

23、中具/有最小关键码值的表项，函数返回其位置 int min=low;for(int i=low+1,i=high,i+)if(elementi elementmin)min=i;return min;定义的重载操作定义的重载操作4040template ostream&operator (ostream&outStream,dataList outList)outStream “输出数组内容:n”;for(int i=0;i outList.listSize;i+)outStream outList.elementi;outStream endl;ouStream “输出数组当前大小:”out

24、List.listSize endl;return outStream;4141 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;4242template void dataList:sort()/按非递减顺序对按非递减顺序对listSize个

25、关键码个关键码element0到到/elementArraySize-1排序排序 for(int i=0;i=listSize-2;i+)int j=minKey(i,listSize-1);if(j!=i)swap(j,i);#endif 4343使用模板的选择排序算法的主函数使用模板的选择排序算法的主函数#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

26、 x.key;4444 dataList TestList(SZ);cin TestList;cout TestList endl;TestList.Sort();cout TestList endl;return 0;定义对象时，代定义对象时，代入实际数据类型入实际数据类型重载友元操作重载友元操作标准标准IO操作操作消息通信消息通信4545算法简单性能分析与度量算法简单性能分析与度量n n算法的性能标准算法的性能标准n n算法的后期测试算法的后期测试n n算法的事前估计算法的事前估计4646算法的性能标准算法的性能标准n n正确性正确性(Correctness)算法应满足具体问算法应满足具体

27、问题的需求。题的需求。n n可读性可读性(Readability)算法应该容易阅读。算法应该容易阅读。以有利于阅读者对程序的理解。以有利于阅读者对程序的理解。n n效率效率 效率指的是算法执行的时间和空间利效率指的是算法执行的时间和空间利用率。通常这两者与问题的规模有关。用率。通常这两者与问题的规模有关。n n健壮性健壮性(Robustness)算法应具有容错处算法应具有容错处理的功能。当输入非法数据时，算法应对其理的功能。当输入非法数据时，算法应对其作出反应，而不应产生莫名其妙的输出结果。作出反应，而不应产生莫名其妙的输出结果。4747算法的后期测试算法的后期测试n对一个算法要作出全面的分析

28、可分成两个阶对一个算法要作出全面的分析可分成两个阶段进行，即段进行，即事前分析事前分析和和事后测试事后测试n事前分析事前分析要求事前求出该算法的一个时间界要求事前求出该算法的一个时间界限函数。限函数。n事后测试事后测试则要求在算法执行后通过算法执行则要求在算法执行后通过算法执行的时间和实际占用空间的统计资料来分析。的时间和实际占用空间的统计资料来分析。n事后分析要求在算法中的某些部位插装时间事后分析要求在算法中的某些部位插装时间函数函数 time()，测定算法完成某一功能所花测定算法完成某一功能所花费时间。费时间。4848例如，给出顺序搜索例如，给出顺序搜索(Sequenial Search)

29、算法算法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;4949 插装插装 time()的计时程序的计时程序 double start,stop;time(&start);int k=seqsearch(a,n,x);time(&stop);double runTime=stop-start;cout n runTime endl;事实上，算法运行时间要受事实上，算法运行时间要受输入规模、利用输

30、入规模、利用编译程序生成的目标代码的质量、计算机编译程序生成的目标代码的质量、计算机程序指令系统的品质和速度等制约。程序指令系统的品质和速度等制约。5050算法的事前估计算法的事前估计n算法的事前估计主要包括时间复杂性和空算法的事前估计主要包括时间复杂性和空间复杂性的分析：间复杂性的分析：u问题的规模：问题的规模：如：矩阵的阶数、图的结如：矩阵的阶数、图的结点个数、被分类序列的正整数个数等。点个数、被分类序列的正整数个数等。u时间复杂性时间复杂性：算法所需时间和问题规模：算法所需时间和问题规模的函数，记为的函数，记为 T(n)。当当 n 时的时间时的时间复杂性，称为复杂性，称为渐进时间复杂性渐

31、进时间复杂性。u空间复杂性空间复杂性：算法所需空间和问题规模：算法所需空间和问题规模的函数。记为的函数。记为 S(n)。当当 n 时的时间时的时间复杂性，称为复杂性，称为渐进空间复杂性渐进空间复杂性。5151空间复杂度度量空间复杂度度量n n存储空间的固定部分存储空间的固定部分程序指令代码的空间，常数、简单变量、定程序指令代码的空间，常数、简单变量、定长成分长成分(如数组元素、结构成分、对象的数如数组元素、结构成分、对象的数据成员等据成员等)变量所占空间变量所占空间n n可变部分可变部分尺寸与实例特性有关的成分变量所占空间、尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间

32、、通过引用变量所占空间、递归栈所用空间、通过new和和delete命令动态使用空间命令动态使用空间5252时间复杂度度量时间复杂度度量n n编译时间编译时间n n运行时间运行时间uu程序步程序步FF语法上或语义上有意义的一段指令序语法上或语义上有意义的一段指令序列；列；FF执行时间与问题规模无关；执行时间与问题规模无关；FF例如：例如：声明声明语句语句：程序步数为：程序步数为0;表达表达式式：程序步数为：程序步数为15353n程序步确定方法程序步确定方法u插入计数全局变量插入计数全局变量countu建表，建表，列出个语句的程序步列出个语句的程序步例例 以迭代方式求累加和的函数以迭代方式求累加和

33、的函数 float sum(float a,int n)float s=0.0;for(int i=0;i n;i+)s=s+ai;return s;5454在求累加和程序中加入在求累加和程序中加入 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;执行结束得执行结束得 程序步数程序步

34、数 count=3*n+45555程序的简化形式程序的简化形式 void sum(float a,int n)for(int i=0;i n;i+)count+=3;count+=4;5656注意注意：一个语句本身的程序步数可能不等于该语一个语句本身的程序步数可能不等于该语句一次执行所具有的程序步数。句一次执行所具有的程序步数。例如：例如：赋值语句赋值语句x=sum(R,n)本身程序步数为本身程序步数为 1；一次执行对函数一次执行对函数 sum(R,n)的调用需要的程的调用需要的程序步数为序步数为 3*n+4；一次执行的程序步数为一次执行的程序步数为 1+3*n+4=3*n+55757计算累加

35、和程序计算累加和程序程序步数计算工作表格程序步数计算工作表格5858时间复杂度的渐进表示法时间复杂度的渐进表示法例例 求两个求两个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+25959时间复杂度的渐进表示法时间复杂度的渐进表示法n算法中所有语句的频度之和是算法中所有语句的频度之和是矩阵阶

36、数矩阵阶数n的的函数函数 T(n)=3n3+5n2+4n+2n一般地，称一般地，称 n 是问题的规模。则时间复杂是问题的规模。则时间复杂度度 T(n)是问题规模是问题规模 n 的函数。的函数。n当当n趋于无穷大时，把时间复杂度的数量级趋于无穷大时，把时间复杂度的数量级（阶）称为算法的渐进时间复杂度（阶）称为算法的渐进时间复杂度 T(n)=O(n3)大大O表示法表示法6060n加法规则加法规则 针对并列程序段针对并列程序段 T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)n各种函数的增长趋势各种函数的增长趋势 c log2n n nlog2n n2 n3 2n 3n n!61

37、61T(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+;6262n乘法规则乘法规则 针对嵌套程序段针对嵌套程序段 T(n,m)=T1(n)*T2(m)=O(f(n)*g(m)n渐进的空间复杂度渐进的空间复杂度 S(n)=O(f(n)n两个并列循环的例子两个并列循环的例子6363 void exam(float x ,int m,int n)flo

38、at 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)6464起泡排序起泡排序 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;/一趟比较 6565渐进时间复杂度渐进时间复

39、杂度 O(f(n)*g(n)=O(n2)BubblrSort 外层循环外层循环 n-1 趟趟内层循环内层循环 n-i 次比较次比较6666n有时有时,算法的时间复杂度不仅依赖于问题规算法的时间复杂度不仅依赖于问题规模模 n，还与输入实例的初始排列有关。，还与输入实例的初始排列有关。n在数组在数组 An 中查找给定值中查找给定值 k 的算法：的算法：int i=n-1;while(i=0&Ai!=k)i-;return i;n算法的语句算法的语句 i-的频度不仅与的频度不仅与 n 有关，还与有关，还与 A 中各元素的取值中各元素的取值以及以及 k 的取值的取值有关。有关。6767n例：设有两个算

40、法在同一机器上运行，其执例：设有两个算法在同一机器上运行，其执行时间分别为行时间分别为 100n2 和和 2n，问：要使前者快问：要使前者快于后者，于后者，n 至少要取多大？至少要取多大？解答：解答：问题是找出满足问题是找出满足 100n2 2n=8192 n=14时，时，100n2=19600 2n=16384 n=15时，时，100n2=22500 arraySize 或者对于某一个或者对于某一个 k(0 k n)，使得，使得k!*2k maxInt 时，应时，应按出错处理。按出错处理。6969可有如下几种不同的出错处理方式：可有如下几种不同的出错处理方式：用用 cerr 及及 exit(

41、1)语语句句来来终终止止执执行行并并报报告错误；告错误；用用返返回回整整数数函函数数值值 0,1 来来实实现现算算法法，以以区区别是正常返回还是错误返回；别是正常返回还是错误返回；在在函函数数的的参参数数表表设设置置一一个个引引用用型型的的整整型型变变量来区别是正常返回还是某中错误返回。量来区别是正常返回还是某中错误返回。抛出异常。抛出异常。7070#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;7171 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;7272