C- -程序设计教程PPT课件

02:19:18,1,C+程序设计教程(第二版),第二章基本编程语句Chapter2BasicProgrammingStatements,清华大学出版社钱能,-,02:19:18,2,第二章内容,说明语句(DeclarativeStatements)条件语句(ConditionStatements)循环语句(LoopStatements)循环设计(LoopDesigns)输入输出语句(Input/OutputStatements)转移语句(MoveStatements)再做循环设计(MoreLoopDesigns),-,02:19:18,3,1.说明语句(DeclarativeStatements),数据说明：求解问题所使用的数据是什么性质，进行什么运算，表达范围如何，必须预先说明说明方式:既要指明其名字，也要指明其是什么类型，还可以顺便初始化如：inta;doubled=3.5;说明数据的另一个目的是创建一个所需大小的实体空间给该名字，以便存储所用的数据值若数据名字没有说明，使用其便是非法的,-,02:19:18,4,过程(函数)说明：求解中需要通过函数调用来实施求解时，便要对函数的性质进行说明，说明其返回类型，参数类型，参数个数函数说明分函数声明和函数定义两种：函数声明是说明函数的名字，函数的返回类型，以及函数的参数和个数如：doublearea(doublera);函数定义是在函数声明的基础上，对整个实现过程进行详细定义如：doublearea(doublera)returnra*ra*3.14;,-,02:19:18,5,调用函数就是使用函数名字，使用名字前必须清楚名字的性质，所以必须先对函数进行声明运行程序中，会涉及到被调用函数的执行，所以凡是被调用的函数都必须有函数定义，不管该定义在程序的什么位置如：doublesphere();/声明intmain()doubleresult=sphere();/调用coutr;returnr*r*3.14;,-,02:19:18,6,.条件语句(ConditionStatements),if语句的两种形态：,语句1,条件,语句1,条件,语句2,是,是,否,否,-,02:19:18,7,对应语句：if(ab)coutaendl;if(a=b)coutaendl;elsecoutb0)if(x50)cout”xisok.n”;elsecout0)if(x50)cout”OKn”;elsecout0)if(x50)cout”OKn”;elsecout”NOTOKn”;,-,02:19:18,9,条件表达式：对于if(x)a=327981;elseb=327981;可表示为：x?a=327981:b=327981;如果a和b为同类型，则还可以：(x?a:b)=327981;,-,02:19:18,10,switch多分支语句：switch(整数表达式)casevalue1:语句1;break;casevalue2:语句2;break;default:语句n;等价于：if(整数表达式=value1)语句1;elseif(整数表达式=value2)语句2;else语句n;,-,02:19:18,11,虽然switch有等价的复合if表示,而且,分支判断值只能是整数,显得应用范围狭窄,但是switch在使用上的直观和灵活形式,使得其仍具有编程价值.如：break可选，甚至case可以重叠：casevalue1:语句1;casevalue2:语句2;casev1:casev2:casev3:语句;,-,02:19:18,12,3.循环语句(LoopStatements),for循环结构：,-,02:19:18,13,对应语句为：for(inti=1;i=10;i+)cout”hello.n”;,循环初始状态,条件判断,状态修正,循环体,-,02:19:18,14,每次循环体执行，都改变循环状态，直到条件不满足而终止.如，设置求和的初始值，交给循环计算，完成循环后，输出求和结果：intsum=0;for(inti=1;i=100;i+)sum=sum+i;coutsumendl;,循环开始,循环结束,-,02:19:18,15,因为并不是所有循环都有明显的循环初始状态和状态修正的，所以，while循环是一种for循环的简洁形式.如，同样的求和：intsum=0,i=1;while(i=100)sum+=i+;coutsumendl;,循环开始,循环结束,-,02:19:18,16,4.循环设计(LoopDesigns),(1)简单字符图形的双重循环MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM,-,02:19:18,17,分析方法：该图形一共10行，每一行增加一个字符，所以，应循环10次，每次输出一行，其循环模式为：for(inti=1;i=10;+i)输出第i行(循环)换行行iM个数111222333444.101010,-,02:19:18,18,for(inti=1;i=10;+i)for(intj=1;j=i;+j)cout”M”;coutendl;,-,02:19:18,19,(2)判断素数：(利用数学定律)mij假定ij，则i2ijmj2即i2mj2即imjboolisPrime(intm)doublesqm=sqrt(m*1.0);for(inti=2;i=sqm;+i)if(m%i=0)returnfalse;returntrue;,-,02:19:18,20,5.输入输出语句(Input/OutputStatements),标准输出流:可以控制输出格式cout3)3);/0falsecoutfixed12345.678;/12345.678000coutscientific123456.678;/1.234568e+05,-,02:19:18,21,控制宽度和填充字符的操作是带参数的，注意width(n)为一次性操作，即第二次显示时将不再有效。默认为width(0)，表示仅显示数值。例如：cout.width(5);cout.fill(S);coutcoutsetw(6)setfill($)27endl;/输出：$27,-,02:19:18,22,文件流的输入出操作与标准输入出基本相同，只是需要以一定方式打开和关闭如，将文件a.in打开，逐行读入字符，输出到文件a.out：ifstreamin(“a.in”);ofstreamout(“a.out”);for(strings;getline(in,s);)outsendl;其中文件流读入操作总是伴随着状态返回，判断状态就可以确定文件是否正常读入，如getline(in,s)当读到文件尾时，便返回false，以使循环结束,-,02:19:18,23,.转移语句(MoveStatements),break除了用在switch之外，主要的是用在终结本次循环for(inti;)for(;)/.if(i=1)break;/.a=1;/.,break跳到此处,-,02:19:18,24,continue一般是用条件判断执行的，通过反条件，可以免去continue的使用，所以，它用来构筑良好的程序风格for(intn=100;n=200;+n)if(n%3=0)continue;coutnendl;免去continue的情形：for(intn=100;n=200;+n)if(n%3!=0)coutnendl;,-,02:19:18,25,goto的程序段除了系统跟踪和架构困难外，阅读也相对复杂：inta;gotoInit;Forward:a=a+1;Print:coutaendl;gotoDown;Init:a=1;gotoPrint;Down:if(a100)gotoForward;等价于：for(inti=1;i=100;+i)couti“n”;,-,02:19:18,26,break语句的可取之处：/用break语句的代码段boolflag=false;/用于做退出记号for(inti=1;i100;+i)for(intj=1;j100;+j)if(i*j=651)flag=true;break;else/.if(flag)break;/goto语句的代码段for(inti=1;i100;+i)for(intj=1;j100;+j)if(i*j=651)gotoEnd;/.End:,-,02:19:18,27,7.再做循环设计(MoreLoopDesigns),逻辑判断类的语句控制结构：for(所有可能情况)/可为多重循环if(条件1不满足)continue;if(条件2不满足)continue;/if(条件n不满足)continue;输出所要的结果,-,02:19:18,28,百鸡问题的例子：for(intc=1;c=13;+c)for(inth=1;h=18;+h)for(ints=1;s=96;+s)if(7*c+5*h+s/3-100)continue;if(c+h+s-100)continue;if(s%3)continue;coutCock:c,Hens:h,Chicks:100-c-h1e-6;+n)item*=(-1.0)*(2*n-3)/(2*n-1);sum+=item;coutPi=“setiosflags(ios:fixed)sum*4=，!，=，=，=，/错,-,02:19:18,36,.整型子类(Sub-intTypes),字符型：表示范围：有符号：-128127无符号：0255输出形式与整型数不同:inta=65;charb=65;couta“n”;coutb“n”;结果为：65A,-,02:19:18,37,枚举型：自定义整数区间，甚至列举单个整数值enumWeekMon,Tue,Wed,Thu,Fri,Sat,Sun;最大特点是可以给每个值指定一个在程序中直接使用的标记(枚举符)编程中将其当作整数常量用如：inta=7;if(a=Sun)cout“Sundayn”;,-,02:19:18,38,布尔型：表示范围仅含整数和1，也可以表示成true和false，相当于：enumboolfalse,true;因为条件表达式、逻辑运算的结果都是或，所以，相当大数量的表达式的值与布尔型对应,-,02:19:18,39,3.浮点型(Floating-PointTypes),浮点数的内部表示：国际标准IEEE754浮点表示法，它与编程所用的浮点数字面量以及输出的十进制浮点数之间有一个转换关系浮点数的表示范围：32位浮点数3.4103864位浮点数1.810308浮点数的操作：常规的加、减、乘、除等操作,-,02:19:18,40,4.C-串与string(C-stringcout*strendl;/显示Hcoutstrendl;/显示Hello,-,02:19:18,42,C-串不能直接比较,因为字符指针的比较只是地址值的比较而不是C-串的字典序比较:cout(“join”=”join”?”:”not“)”equaln”;/字面值比较char*str1=”good”;char*str2=”good”;cout(str1=str2?”:”not“)”equaln”;/字符指针比较charbuffer16=”Hello”;charbuffer26=”Hello”;cout(buffer1=buffer2?”:”not“)”equaln”;/字符数组比较结果：notequalnotequalnotequal,-,02:19:18,43,不得不配备专门操作C-串的库函数:strcpy(s1,s2);/从s2拷贝到s1strcmp(s1,s2);/比较s1与s2strcat(s1,s2);/连接s2到s1strrev(s);/将s倒排strset(s,c);/将s全置为cstrstr(s,“ell”);/查找s中的子串strchr(s,c);/查找s中的字符等等,-,02:19:18,44,但字符指针操作C-串的安全性受到质疑:char*str1;char*str2=newchar5;strcpy(str2,”ugly”);strcpy(str1,str2);/错:str1没有空间可储strcpy(str2,”Hello”);/错:str2空间不够大str2=”Hello”;/错：原来的”ugly”空间脱钩，导致内存泄漏根源：复制操作须以足够的目的地空间为前提，而所有C-串操作的空间调配都是人为安排的，C-串库函数一概不管,-,02:19:18,45,类串string串类自定义串对应字符指针的C-串操作:stringa,s1=Hello;strings2=123;a=s1;/copycout(a=s1?:not)equaln;/comparecouta+s2endl;/concatenatereverse(a.begin(),a.end();coutaendl;/reversecouta.replace(0,9,9,c)endl;/setcout(s1.find(ell)!=-1?:not)foundn;/findstringcout(s1.find(c)!=-1?:not)的读入方式总是将前导的空格（所谓空格，即包括空格、回车、水平或垂直制表符等）滤掉，将单词读入，在遇到空格时结束本次输入getline总是将行末的回车符滤掉，将其整行输入对字串”Hello,Howareyou?”的两种输入方式for(strings;cins;)couts”“;coutendl;strings;getline(cin,s);coutsa;sum+=a);coutsum“n”;,-,02:19:18,48,5.数组(Arrays),数组是同类元素的集合，它的元素排列在连续的空间中，按下标来标记描述数组必须给出元素类型，元素个数元素个数必须在编程时确定，任何变量都不允许intaa;/表示inta97;intn=100;intan;/错:元素个数必须预知constintn=100;intan;/okinta;/错:无元素个数inta=1,2,3,4,5;/ok:通过初始化确定元素个数,-,02:19:18,49,数组初始化可选，但须遵循语法无初始化的数组按规定取默认值intarray15=1,2,3,4,5,6;/错:初始值个数超元素个数intarray25=1,2,3,4;/错:不能以逗号方式省略intarray35=1,2,3,;/错:同上intarray45=;/错:初始值不能为空intarray55=1,2,3;/ok:后面元素取0intarray65=0;/ok:元素全为0intarray75;/ok:元素值不确定inta35=1,2,3,4,5,2,3,4,5,6,3,4,5,6,7;,-,02:19:18,50,数组有诸多缺陷，造成编程艰难和不安全inta5=1,2,3,4,5,c5;intb5=a;/错:无法拷贝创建c=a;/错:无法整体拷贝和局部拷贝a8=10;/错:无法动态扩容和随意增减元素for(inti=0;i=5;+i)/错:无法防范下标溢出ai=i+1;if(a=c)a0=2;/错:不可比较inta5=1;/初始化呆板,无法获得全初值,-,02:19:18,51,二维数组的初始化,下标访问及输出intarray123=1,2,3,4,5;intarray223=1,2,4;coutarray1:;for(inti=0;i2;+i)for(intj=0;j3;+j)coutarray1ij,;coutnarray2:;for(inti=0;i2;+i)for(intj=0;j3;+j)coutarray2ij,;coutn;结果为：array1:1,2,3,4,5,0,array2:1,2,0,4,0,0,-,02:19:18,52,.向量(vector),向量与数组的共同特征是元素的排列在逻辑上是线性序列结构，可以用下标进行访问向量可以按需创建，拷贝创建，局部拷贝创建，异类拷贝和创建灵活的初始化随意扩容和元素增减可通过异常来进行下标溢出追踪和处理可比较等等,-,02:19:18,53,intn=10;intt5=1,2,3,4,5;vectora(n);/按需创建vectorb(10,1);/元素赋全，灵活的初始化vectorc(b);/整体拷贝创建vectorf(t,t+5);/异类拷贝创建vectord(b.begin(),b.begin()+3);/局部拷贝创建d为b的前个元素a.assign(100);/动态扩容至100个元素,-,02:19:18,54,向量常用操作a.assign(b.begin(),b.begin()+3);/b的前3个元素赋给aa.assign(4,2);/a向量含4个元素，全初始化为2intx=a.back();/a的最后一个元素赋给变量xa.clear();/a向量清空（不再有元素）if(a.empty()cout”empty”;/a判空操作inty=a.front();/a的第一个元素赋给变量ya.pop_back();/删除a的最后一个元素a.push_back(5);/a最后插入一个元素，其值为5a.resize(10);/a元素个数调至10。多删少补，其值随机a.resize(10,2);/a元素个数调至10。多删少补，新添元素初值为2if(a=b)cout34.5iAddr:1245064=1107951616int:100float:1.4013e-43,-,02:19:18,58,指针加减整数的操作表示空间位置上的挪动但是挪动的字节数与其数据类型相关：对float指针加6实际增加了24个字节对longint指针加5实际增加了20个字节对char指针减7实际减少了7个字节对double指针减2实际减少了16个字节,-,02:19:18,59,数组名本身就是表示元素集合的首地址可以将数组名赋给指针inta3;for(inti=0;i3;+i)ai=i*2;for(int*iP=a;iPa+3;iP+=1)coutiP“:”*iP“n”;结果为：1245036:01245040:21245044:4,-,02:19:18,60,指针限定constinta=78;intb=10;intc=18;constint*ip=/ok,-,02:19:18,61,引用必须初始化，因为引用总是附属于某个实体intsomeInt=5;int结果为：8引用多用在函数参数的传递上,-,02:19:18,62,C+程序设计教程(第二版),第四章计算表达Chapter4ComputationalExpressing,清华大学出版社钱能,-,02:19:18,63,计算表达：表达计算使用一系列操作，它依赖于特定语言的操作符功能,关乎数据类型的内在特性,故计算表达目的在于深入剖析数据类型对于编程的影响，从而准确使用操作符学习方法：1.掌握操作符的功能和相互关系（优先级和结合性）2.针对内部数据类型，对一些典型的操作中的典型问题留下深刻印象,-,02:19:18,64,第四章内容,名词解释(NameExplainations)算术运算问题(ArithmeticProblems)相容类型的转换(CastCampatibleType)关系与逻辑操作(Relation/先做x+结合性：同级操作符的执行顺序的规定性，如：a=b=6;/先做b=6,-,02:19:18,67,.算术运算问题(ArithmeticProblems),整型数表示范围有限，如：不能用整型变量累计的一般循环方法来解:intsum=0;for(inti=1;i=10000;+i)sum+=i;coutsum“n”;,-,02:19:18,68,整型数的周而复始性，如：unsignedinta=2000000000;unsignedintb=3000000000;couta+b“n”;结果为:705032704超过表示范围的整型数不是报错，而是表示成一个去掉进位后的余数,-,02:19:18,69,中间结果溢出导致计算错误，如：inta=100000;intb=100000;intc=1000;couta*b/cn;couta*(b/c)n;结果为：141006510000000,-,02:19:18,70,浮点数的精度和有效位影响比较的正确性，如：floatf1=7.123456789;floatf2=7.123456785;if(f1=f2)cout“f1equaltof2n”;floatf=1.0/3.0;doubled=1.0/3.0;if(g=d)cout“gnotequaltodn”;结果为：f1equalstof2gnotequalstod,-,02:19:18,71,浮点数计算的近似性使精确性比较失败，如：doubled1=123456789.9*9;doubled2=1111111109.1;if(d1!=d2)cout“Notsamen”;elsecout“Samen”;if(abs(d1-d2)1e-05)cout“Samen”;elsecout“Notsamen”;结果为：NotsameSame,-,02:19:18,72,3.相容类型转换(CastCompatibleType),隐式转换：整型和浮点型都是数值型，所以它们是相容类型指针与整型不相容，如：7.0/3=7.0/3.0/将隐式转换成浮点=2.33333333inta=9;int*ap=3+ap/错,-,02:19:18,73,从表达能力弱的类型到强的类型的转换是安全的，反之，会引起精度丢失如：floatf=7.0/3;/doublefloatinta=7.0/3;/doubleintcout.precision(9);coutfixed7.0/3“n”;coutf“n”a“n”;结果为：2.3333333332.3333332542,-,02:19:18,74,可以用显式转换的方法，人为控制运算在一定的数据类型下工作，如：doubled=sqrt(123456.0);inta=static_cast(d)*8+5;intb=d*8+5;/隐式转换为浮点couta“n”b“n”;结果为：28132815,-,02:19:18,75,4.关系与逻辑操作(Relationsif(x=0)cout“test1okn”;if(x=5)cout“test2okn”;if(x=0)cout“test3okn”;结果为：test2ok,-,02:19:18,76,!=是操作符，=!不是操作符intx=3;if(x!=9)cout“not9n”;if(x=!9)cout“impossiblen”;条件表达式(x!=0)与(x)等同intx=3;if(x!=0)coutx;if(x)coutx;,-,02:19:18,77,不等式连写的错误:inta=-1,b=0,c=1;if(abc)cout“ok1n”;if(ab结果为：ok2,-,02:19:18,78,短路求值的妙用:避免除0的恶果if(b,-,02:19:18,79,5.位操作(BitOperations),左移操作将整数最高位挤掉，在右端补0。如：inta=12;/a为：00000000000000000000000000001100a=a在整数的高位挤一个0或1进去（有符号数挤符号位，无符号数挤），而整数最低位被挤掉。如：shortinta=-2;/1111111111111110a=a1;/a=-1即1111111111111111unsignedshortintb=65535;/1111111111111111b=b1;/b=32767即0111111111111111,-,02:19:18,81,位与操作结果为：(比较/a为：00000000000000000000000000001100intb=6;/b为：00000000000000000000000000000110/a|b为：00000000000000000000000000001110intcbit=a|b;intclogic=a|b;coutcbit“n”clogicm?m:n)*10;/保证运输次数最少,-,02:19:18,96,参数传递：形参是对实参的克隆，克隆必须遵守类型匹配规则,voidf(Typea);/a为形参voidg()Typex;f(x);/x为实参,a实体,x实体,复制,Type类型,Type类型,-,02:19:18,97,.指针参数(PointerParameters),传递指针：指针参数也是值传递的，指针值的真正用途是进行数据间访，以达到操作数据块（大小由之）的目的传递引用：引用参数本质上也是值传递的，它表现为名字传递，即以形参的名字来代替实参名字如果实参不是实体名而是表达式，那么其表达式所对应的临时实体取名为形参，并要求其为常量引用意义：指针和引用参数的存在，使函数实际上可以访问非局部的数据区，函数的黑盒性便名存实亡但这并非一定坏事，指针是一把双刃剑，或灵巧或邪恶引用是为了防范指针非安全的无意操作,-,02:19:18,98,voidmySort(int*b,intsize);voidf()inta=3,5,7,1,8,4,9;mySort(a,sizeof(a)/sizeof(a0);,传递指针须附带传递单位数据的个数,元素个数,传指针,-,02:19:18,99,限制无意操作带来的意外副作用,vectoradd(/向量加法constvector,-,02:19:18,100,3.栈机制(StackMechanism),运行时内存布局,-,02:19:18,101,未初始化局部数据的不确定性,#includevoidf()intb;/未初始化std:cout”a“n”;f();/-/8804248/2788048,-,02:19:18,102,#includeinta=5;intb=6;intmain()int*ap=(int*)4202660;*ap=8;std:couta“n”;std:coutint(/8/4202664,指针的无约束性,5,6,4202660,4202664,a,b,4202660,ap,-,02:19:18,103,4.函数指针(FunctionPointers),函数类型：函数类型因参数类型、个数和排列顺序的不同而不同，也因返回类型的不同而不同函数指针：指向代码区中函数体代码的指针.不同的函数类型,其函数指针也不同用法：函数指针经常用作函数参数，以传递连函数本身都不知道的处理过程（函数）,-,02:19:18,104,不同的函数指针，不能相互赋值,intg(int);int(*gp)(int)=g;voidf();void(*fp)();fp=f;gp=fp;/error,不同的函数,-,02:19:18,105,函数指针作为参数传递(函数名看作是函数指针),boollessThanBitSum(inta,intb)intsuma=0,sumb=0;for(intx=a;x;x/=10)suma+=x%10;for(intx=b;x;x/=10)sumb+=x%10;returnsumasumb;intmain()inta=33,61,12,19,14,71,78,59;sort(aa,aa+8,lessThanBitSum);for(inti=0;i8;+i)coutaai;coutn;/1214336171195978,-,02:19:18,106,指定函数指针类型，定义函数指针数组,typedefvoid(*MenuFun)();voidf1()coutgood!n;voidf2()coutbetter!n;voidf3()coutab;)couta+bf0509abc.txt1721357,-,02:19:18,109,main函数参数,/f0510.cpp#includeusinganmespacestd;intmain(intargc,char*argv)for(inti=0;iargc;+i)coutargvif0510a1a2a3f0510a1a2a3,-,02:19:18,110,6.递归函数(RecursiveFunctions),形式上：一个正在执行的函数调用了自身(直接递归).或者,一个函数调用了另一个函数,而另一个函数却调用了本函数(间接递归)本质上：程序在运行中调用了相同代码实体的函数,却在函数栈中重新复制了该函数的整套数据,由于每套数据中的参数也许不同,导致了计算条件发生变化，使得函数得以逐步逼近终极目标而运行,-,02:19:18,111,递归函数可以转换为非递归函数例如，求最大公约数,longgcd1(inta,intb)/递归版if(a%b=0)returnb;returngcd(b,a%b);/-longgcd2(inta,intb)/非递归版for(inttemp;b;a=b,b=temp)temp=a%b;returna;/-,-,02:19:18,112,7.函数重载(FunctionOverload),函数重载：一组概念相同，处理对象（参数）不同的过程，出于方便编程的目的，用同一个函数名字来命名的技术称为函数重载参数默认：一个函数，既可以严谨和地道的调用，也可以省略参数，轻灵地调用，达到此种方便编程目的的技术称为参数默认重载与参数默认：它们都是通过参数的变化来分辨处理任务的不同如果参数决定了不同的处理过程，则应重载，否则参数默认更简捷一些,-,02:19:18,113,重载是不同的函数，以参数的类型，个数和顺序来分辨,voidprint(double);voidprint(int);voidfunc()print(1);/voidprint(int);print(1.0);/voidprint(double);print(a);/voidprint(int);print(3.1415f);/voidpirnt(double);,-,02:19:18,114,参数默认是通过不同参数来分辨一个函数调用中的行为差异,voiddelay(inta=2);/函数声明时intmain()delay();/默认延迟秒delay(2);/延迟秒delay(5);/延迟秒voiddelay(inta)/函数定义时intsum=0;for(inti=1;i=a;+i)for(intj=1;jc/=,频繁调用的函数：用昂贵的开销换取可读性,-,02:19:18,120,/=#includeintmain()for(charc;cinc/=,内嵌代码：开销虽少，但可读性差,-,02:19:18,121,内联方式：开销少，可读性也佳,/=#includeinlineboolisDigit(char);/小函数intmain()for(charc;cinc/=,内联标记放在函数声明的前面,-,02:19:18,122,内联函数的使用经验：,函数体适当小,且无循环或开关语句，这样就使嵌入工作容易进行，不会破坏原调用主体如：排序函数不能内联程序中特别是在循环中反复执行该函数，这样就使嵌入的代码利用率较高如：上例中的isDigit函数程序并不多处出现该函数调用，这样就使嵌入工作量相对较少，代码量也不会剧增,-,02:19:18,123,/=#include#includeusingnamespacestd;/-intcalc1(inta,intb)returna+b;inlineintcalc2(inta,intb)returna+b;/-intmain()intx1000,y1000,z1000;clock_tt=clock();for(inti=0;i1000*1000*1000;+i)zi=calc1(xi%1000,yi%1000);cout(clock()-t)/CLK_TCK“withoutinlinen;t=clock();for(inti=0;i1000*1000*1000;+i)zi=calc2(xi%1000,yi%1000);cout(clock()-t)/CLK_TCKn/=,栈中若不存在读入的元素，则应入栈,创建栈,读入元素不在栈顶即为失败,退栈即逐个逐个过,-,02:19:18,129,向量方式,/=intmain()ifstreamin(rail.txt);for(intn,line=0;inn/=,模仿栈操作,-,02:19:18,130,结论,不同的数据结构有不同的操作和性能应学习使用不同数据结构的经验,-,02:19:18,131,3.算法(Algorithms),揭示：确定了数据结构之后，所采用的算法将直接决定程序的性能；任何语言都有个性，算法的选择使用是灵巧运用语言的艺术，充分发挥语言的优势是活用算法的根本做法：培养经验，用测试的办法对算法进行选择,-,02:19:18,132,问题：,已知不太大的正整数n（n46），求Fibonacci数列0112358132134的第n项的值对于后面的四种算法：unsignedfibo1(unsignedn);unsignedfibo2(unsignedn);unsignedfibo3(unsignedn);unsignedfibo4(unsignedn);如何选择其中之一,第0项,第1项,第2项,-,02:19:18,133,算法：递归法优点：算法简单，容易编程缺点：栈空间负担过重，调用开销过大,unsignedfibo1(unsignedn)if(n=1)returnn;returnfibo1(n-1)+fibo1(n-2);,n=0或1,-,02:19:18,134,算法：迭代法优点：节省空间，节省时间缺点：编程相对复杂,unsignedfibo2(unsignedn)intc=n;for(inta=0,b=1,i=2;ist;)比较输出yes或no,-,02:19:18,146,分别排序，直接加以字串比较是直截了当的思路：,for(strings,t;inst;)sort(s.begin(),s.end();sort(t.begin(),t.end();coutst;)ints1=count(s.begin(),s.end(),1);ints0=count(s.begin(),s.end(),0);intt1=count(t.begin(),t.end(),1);intt0=count(t.begin(),t.end(),0);coutst;)ints1=count(s.begin(),s.end(),1);intt1=count(t.begin(),t.end(),1);cout(s1=t1,C+标准算法,-,02:19:18,149,6.动态内存(DynamicMemory),揭示：许多问题不知道数据量的大小，需要所运用的数据结构具有扩容能力；许多问题要求时间性能甚于空间占用充分利用堆空间(动态内存)是解决这些问题的关键做法：理解堆空间的使用场合，学习堆空间的使用方法,-,02:19:18,150,使用容器，便是自动使用堆内存,例如，从abc.txt中读取诸段落：ifstreamin(abc.txt);vectorps;/ps.reserve(1100);可以预留for(strings;getline(in,s);)ps.push_back(s);预留是减小频繁扩容造成的数据移动开销,-,02:19:18,151,若每个数据的处理，都要用到已经处理的数据时，保存历史数据，则可以改善时间性能,例如，统计一亿之内的素数个数(原始版)：boolisPrime(intn)intsqrtn=sqrt(n*1.0);for(inti=2;i=sqrtn;+i)if(n%i=0)returnfalse;returntrue;/-intmain()intnum=0;for(inti=2;i=100000000;+i)if(isPrime(i)num+;coutnumreset(j);intnum=0;for(inti=2;itest(i)num+;coutnumMat;Matinput();Mattranspose(constMat,-,02:19:18,175,在多个程序文件组成的程序中共享数据，要遵守一次定义规则,/item1.cpp#includeusingnamespacestd;intn=8;/definevoidf();intmain()coutn”n”;f();,/item2.cpp#includeusingnamespacestd;