上海交通大学C++课程课件_1-9章

C+程序设计,沈红斌Email:hbshen,课程目标,进一步掌握程序设计，包括过程化程序设计和面向对象的程序设计掌握C+语言了解常用的算法及算法设计过程,期末成绩的组成,期末考试：50%期中考试：20%大作业：30%,教材及参考教材,C+程序设计思想与方法（第2版）人民邮电出版社翁惠玉C+Primer人民邮电出版社C程序设计（第3版）谭浩强C+大学教程（第5版）电子工业出版社程序设计基础（第2版）吴文虎清华大学出版社,作业的相关规定及注意事项,本学期将布置若干个作业，在课后独立完成作业环境：VC6.0、VC2008、VC2010助教每周有两个晚上在机房答疑作业要求：必须独立、按时地完成每次上机作业每次上机作业的具体要求参见每次作业的文档说明上传的作业必须符合下述的“上传作业命名规则”作业上传地址：67用户码/密码：sjtu/sjtu,作业命名规则,使用WinRAR软件将上机作业（包括工程文件、资源文件、源文件和头文件等）的多个文件直接压缩为一个压缩文件，该压缩文件必须命名为：”学号_作业号.rar”。若一次作业中包含多个小题，则每个小题应分别放入一个单独文件夹，多个文件夹直接压缩为一个压缩文件。其中，每个小题的文件夹应命名为：”学号_作业号_题号”；上传的作业中应该不包括Debug文件夹以及某些声音、图像文件命名规则示例：以学号为5030309999，上传第四次作业（第四次作业中含有两个独立的小作业）为例：两个小作业的文件夹名字应为：5030309999_4_1和5030309999_4_2压缩文件名应为：5030309999_4.rar,评分标准,“完成截止日期”后、“上传截止日期”前仍可上传作业，但视为“迟交”，迟交的作业将被扣除一定的分数。在“上传截止日期”后，将停止该次作业批改。一经发现作业抄袭情况，无论任何原因，抄袭者与被抄袭者的当次作业一律记为0分,第二章通过例子学习,第一个程序第二个程序变量定义数据类型符号常量算术表达式,赋值表达式自增自减运算符强制类型转换数据的输入输出,C+程序的基本组成,基本的C+程序结构,/File:hello.cpp/thisprogramprintsthemessage/“helloeveryone”onthescreen#includeintmain()std:cout“helloeveryone”std:endl;return0;,程序注释,预处理命令,主程序,注释,C+的注释是从/开始到本行结束，也可以采用C风格的注释，即从/*与*/之间所有的文字都是注释，可以是连续的几行。注释是写给人看的，而不是写给计算机的。程序注释：从整体描述程序操作过程注释也可以出现在主程序中，解释主程序中一些比较难理解的部分。给程序添加注释是良好的程序设计风格,C程序的基本组成,基本的C程序结构,/File:hello.cpp/thisprogramprintsthemessage/“helloeveryone”onthescreen#includeintmain()std:cout“helloeveryone”std:endl;return0;,程序注释,预处理命令,主程序,编译预处理,C+的编译分成两个阶段：预编译和编译预编译处理程序中的预编译命令，即那些以#开头的指令编译预处理主要有：库包含：用#include实现，表示程序使用了某个库宏定义：用#define实现。宏包括不带参数的宏和带参数的宏。不带参数的宏通常用来定义符号常量。带参数的宏用来定义一些较为复杂的操作。,库包含的格式,库是预先做好的一些工具程序。每个库要提供一个接口，告诉库的用户如何使用库提供的功能。库包含就是把库的接口文件放入源文件，以便编译器检查程序中对库的调用是否正确。库包含格式：#include：包含了一个系统库#include“filename”：包含了一个用户自定义的库,宏定义,不带参数的宏定义通常用于为程序中的常量取一个名字，称为符号常量。格式：#define标识符替换文本如：#defineRADIUS5#definePI3.14159#defineAREAPI*RADIUS*RADIUS用define定义宏是C语言的习惯，在C+中有更好的解决方案,使用符号常量的好处,含义清楚，提高了程序的可读性。在需要改变一个常量时能做到“一改全改”,C程序的基本组成,基本的C程序结构,/File:hello.cpp/thisprogramprintsthemessage/“helloeveryone”onthescreen#includeintmain()std:cout“helloeveryone”std:endl;return0;,程序注释,预处理命令,主程序,主程序,主程序由一个或多个函数组成每个程序都必须有一个名为main的函数，它是程序的入口。,函数的构成,intmain()函数头std:cout“helloeveryone”std:endl;return0;,函数体,与PYTHON不同，C+的函数体必须用一对花括号括起来。事实上，PYTHON中所有必须缩进的语句，在C+中都必须用花括号括起来。,输出流对象std:cout,“流”指的是设备之间传递的数据流输出流是传给输出设备的数据流cout代表显示器格式将hello显示在屏幕上：std:cout“hello”std:cout“hello,everyone”std:endlstd:endl表示换行,名字空间,在大型的程序时，每个源文件可能由不同的开发者开发。不同的源文件中可能有同样的名字。当这些源文件连接起来形成一个可执行文件时，就会造成重名。名字空间是把一组程序实体组合在一起，构成的一个作用域。一个名字空间中不能有重名，不同的名字空间中可以定义相同的实体名。当引用某个实体时，需要加上名字空间的限定程序中的std是C+中所有标准库的名字空间名。,使用名字空间的指令,格式：usingnamespace名字空间名；一旦用了使用名字空间的指令，该名字空间中的所有的实体在引用时就不需要再加名字空间的限定了。第一个程序可以改写为：,/file:hello.cpp/Thisprogramprintsthemessage“Helloworld.”/Onthescreen#includeusingnamespacestd;intmain()cout“Helloworld.”radius;area=PI*radius*radius;circum=2*PI*radius;coutendl;cout园的面积为：areaendl;cout园的周长为：circumendl;return0;,变量定义,输入阶段,计算阶段,输出阶段,程序的组成,变量定义：C+中的变量在使用前都必须被定义。变量定义严格指出变量中可以存放的数据类型。输入阶段：获取执行时才能确定的用户数据。输入过程一般包括两步：显示提示信息读取数据计算阶段：由输入推导出输出的过程。通常通过各种计算得到。输出阶段：显示程序执行的结果,第二章通过例子学习,第一个程序第二个程序变量定义数据类型符号常量算术表达式,赋值表达式自增自减运算符强制类型转换数据的输入输出,变量定义,变量，也称为对象，是数据的存放之处变量有三个重要属性：名称、值、类型。变量定义就是告诉编译器变量的名字及该变量中可以存放哪一类数据类型的值C+中变量定义的格式:类型名变量名1，变量名2，变量名n；如：intnum1,num2;doublearea;在C+中，每个变量在使用前必须被定义，以便编译器检查变量使用的合法性。,变量命名,名字必须以字母或下划线开头。C+语言中，名字中出现的大写和小写字母被看作是不同的字符，因此ABC，Abc，abc是三个独立的变量名。名字中的其它字符必须是字母、数字或下划线，不得使用空格或其它特殊符号名字不可以是系统的保留词，如：int,double,for,return等，它们在C+语言中有特殊用途C+没有规定过名字的长度，但各个编译系统都有自己规定。名字应使读者易于明白其存储的值是什么，做到“见名知意”。,第二章通过例子学习,第一个程序第二个程序变量定义数据类型符号常量算术表达式,赋值表达式自增自减运算符强制类型转换数据的输入输出,数据类型,整型实型字符型布尔型,枚举类型变量赋初值了解占用的内存量,数据类型整型,整型数的表示范围：由各个编译器指定。整型数有三种存储方式，在VC中占用的空间如下所示基本型int：4byte(PC)231（2311）长整型long：long/longint4byte(PC)231（2311）短整型short：2byte(PC)-215（2151)允许的操作：算术运算、比较大小等,整型数的表示码制,讨论如何将符号位数字化。0表示正数，1表示负数。数字的三种编码方式为：原码反码补码,原码,用符号位和数值表示带符号数。正数的符号位为0，负数的符号位为1。数值部分用二进制表示。如用一个字节表示数值：62原=00111110-62原=10111110,反码,正数的反码与原码相同，负数的反码为该数的绝对值的原码取反。如：62反=00111110-62反=11000001,补码,正数的补码与原码相同，负数的补码为该数的反码加1。如：62补=00111110-62补=11000010大多数计算机系统都用补码表示整数,整数的内部表示,整数在计算机内部通常用补码表示，在VC中也是如此。整数运算时要注意数据的表示范围。如整数用两个字节表示时，正整数32767加1的结果为-32768。这称为整数运算的溢出，系统不检查这样的错误，程序员必须自己保证程序中不出现这样的错误。,无符号整数,在某些应用中，不可能出现负数，则整型数中有一半的数值范围是被浪费的。因此在C/C+中可以将所有的数都看成正整数，称为无符号数无符号数的定义：在各种整数类型前加上关键词unsigned，变成unsignedint,unsignedshort,unsignedlong,整型常量,整型常量可用十进制、八进制和十六进制表示十进制：123，-234八进制：0123十六进制：0 x123,0 x3a2f一旦定义了一个整型变量，可以将一个整型常量赋给该整型变量。如inta;a=123;或a=0 x123;都是正确的,数据类型,整型实型字符型布尔型,枚举类型变量赋初值了解占用的内存量,数据类型浮点数,VC中，实型数以浮点形式表示一个浮点数分成尾数和阶码两部分。阶码表示小数点在该数中的位数，尾数表示数的有效数值。浮点类型的分类单精度float：占用4字节，3字节尾数，1字节指数,精确度7位,范围10381038双精度double：占用8字节,5字节尾数,3字节指数,精确度1516位,范围1030710308浮点数无法精确表示,浮点数常量,浮点数常量有两种表示法：十进制表示：1.233.14-5.988科学计数法：尾数*10指数尾数e指数123e2=123002.25e-3=0.00225注意：尾数不能为空e31e3指数必须为整数2.5e2.3是非法的,数据类型,整型实型字符型布尔型,枚举类型变量赋初值了解占用的内存量,数据类型字符类型,字符类型：存放一个字母或符号，占一个字节，存放的是字符的内码。字符类型名：char,字符的机内表示,字符的机内表示用字符编码表示。常用的有ASCII,BCD,EBCDIC等。PC机中都用ASCII.ASCII码的重要特性数字0到9是顺序存放的字母被分成二段：大写的和小写的。大写字母是连续的，小写字母也是连续的,可打印字符和非打印字符,可打印字符：小写字母、大写字母、数字、标点符号、空格等非打印字符：换行和报警字符或响铃等控制字符,可打印字符的使用,字符常量a,S,2等用一对单引号括起来的数据称为字符常量与PYTHON不同，C+中的单引号和双引号有不同的用处。单引号括起来的是一个字符，双引号括起来的是字符串,可打印字符的使用,赋值charc1,c2;c1=a;c2=b;c1=97;c2=98;比较c=9和c=9？运算如：c1=a;c1=c1+2;c1的值应为？如c中存放的是小写字母，则c-a+1表示什么？如c中存放的是数字（09），则c-0表示什么？如c1,c2存放的是小写字母，则c2-c1表示什么?,转义字符,一些非打印和难以打印的字符需要用转义序列表示换行符写为n，虽然它由两个字符和n来描述，但它表示一个ASCII字符。反斜杠符号称为转义字符。双引号和单引号的转义如果在一个串中把双引号”用作一个字符，必须要对它转义，否则它会终结该字符串。cout实型数：数值不变，但以浮点的形式保存在相应的变量中Double-float：截取前面七位有效数字存放到float变量中Float-double：将有效位扩展到16位字符型-整型变量：将字符型数据放入整型变量的最后一个字节。如果所用系统将字符处理成无符号量，则前面补0。如果所用系统将字符处理成有符号量，则扩展符号。整型-字符类型：直接将整型数据的最低八位赋给字符变量。,赋值的嵌套,将赋值表达式作为更大的表达式的一部分。如：a=(x=6)+(y=7)等价于分别将x和y的值设为6和7，并将6和7相加，结果存于变量a赋值运算符=的优先级比算术运算符低,多重赋值,a=b=c=5,给a,b,c均赋值5,当用到多重赋值时，要保证所有的变量都是同类型的，以避免在自动类型转换时出现与预期不相符的结果的可能性。如变量d定义为double,变量i定义为int，语句d=i=1.5;的结果是：i等于1，d等于1.0,复合赋值运算,其他运算符与赋值运算符结合的运算符称为复合赋值运算符常用的复合赋值运算符有：+=，-=，*=，/=，%=变量op=表达式;等价于：变量=变量op表达式;如：balance+=deposit;balance-=surcharge;x/=10;salary*=2;,第二章通过例子学习,第一个程序第二个程序变量定义数据类型符号常量算术表达式,赋值表达式自增自减运算符强制类型转换数据的输入输出,自增、自减运算符,自增、自减运算符：+，-相当于+=1和-=1,它有前缀和后缀两种用法+k,k+,-k,k-，但含义有所不同。如：i=3,j=i+,i=4j=3,j=+i,i=4j=4,j=i-,i=2j=3,j=-i,i=2j=2,第二章通过例子学习,第一个程序第二个程序变量定义数据类型符号常量算术表达式,赋值表达式自增自减运算符强制类型转换数据的输入输出,强制类型转换,赋值和算术运算时会执行自动类型转换如要想使4/5的结果是0.8，而不是0，该怎么办？可以将其中一个写成浮点数。例如：4.0/5或4/5.0intx=4,y=5;要想使x/y的结果为0.8而不是0，该怎么办？答案是：用强制类型转换,强制类型转换,强制类型转换格式：（类型名）（表达式）类型名（表达式）例如，要想使两个整型变量x和y出的结果为double型，可以用下列语句,doublez;z=(double)x/y;,转换类型,强制类型转换在C+类型系统中引入了一个漏洞为了方便查找这些错误，C+提供了在强制类型转换时指明转换的性质。转换的性质有四种：静态转换(static_cast)：用于编译器隐式执行的任何类型转换重解释转换(reinterpret_cast)常量转换(const_cast)动态转换(dynamic_cast)格式转换类型(表达式)z=static_cast(x)/y;,第二章通过例子学习,第一个程序第二个程序变量定义数据类型符号常量算术表达式,赋值表达式自增自减运算符强制类型转换数据的输入输出,输入流对象cin,键盘流入的数据流，将键盘输入的数据存入变量格式：cin变量cin变量1变量2变量n,用户的响应,当程序执行到这个语句时会停下来等待用户的输入用户可以输入数据，用回车（）结束。当有多个输入数据时，一般用空白字符（空格、制表符和回车）分隔。如：a为整型，d为double，则对应于cinad，用户的输入可以为1213.212（tab键）13.21213.233,cin.get,作用：从键盘接受一个字符用法：cin.get（ch）；或ch=cin.get()，都是从键盘输入一个字符并存放到变量ch中对应的用户输入：cin.get()可以接收任意的字符，包括空白字符。,如a,b,c为字符型变量，对应语句a=cin.get();b=cin.get();c=cin.get();如果输入abc，则a的值是a，b的值是空格，c的值是b。如果将这个输入用于语句：cinabc，那么变量a、b、c的内容分别为a、b、c，因为空格被作为输入值之间的分隔符。,输出流对象cout,将变量或表达式的内容显示在显示器上格式输出一个变量的值：couta；输出多个变量的值：coutabc；输出表达式的结果：cout“Helloworld”上述情况的组合：couta+b=a+b=,=,=,!=优先级：高于赋值运算符，低于算术运算符。关系运算符内部：=和！=较低结合性：左结合关系表达式用关系运算符将二个表达式连接起来称为关系表达式关系表达式的结果是：true或false,eg.xy,ab=cd都是合法的关系表达式,注意：-2(62),第3章逻辑思维及分支程序设计,关系表达式逻辑表达式If语句Switch语句,逻辑表达式,逻辑表达是用于实现更复杂的判断逻辑运算符elsecoutyear;result=(year%4=0,if语句的嵌套,if语句的then子句或else子句是if语句，称为if语句的嵌套歧义性：if语句可以没有else子句，如if(x100)if(x90)语句1elseif(x80)语句2else语句3else语句4；配对原则：每个else子句是和在它之前最近的一个没有else子句的if语句配对。,缩进对齐,可以清晰地表示出层次，便于程序员阅读,if(x100)if(x90)语句1elseif(xy)?x:y;？：运算符用于输出。例如，想输出一个布尔变量flag的值，如果直接用coutflag;那么当flag为“真”时，输出为1；当flag为“假”时，输出为0。如果我们想让flag为“真”时输出true，为“假”时输出false，可以用if语句if(flag)cout“true”;elsecout“false”;看上去太罗嗦。但如果用？：运算符只需要一行cout(flag?true:false)=90:cout=80:cout=70:cout=60:coutD;break;default:coutE;,表达式=成绩/10,switch(score/10)case10:case9:coutA;break;case8:coutB;break;case7:coutC;break;case6:coutD;break;default:coutresult1;if(num1-num2=result1)coutresult1;if(num1*num2=result1)coutyouarerightn;elsecoutresult2;if(num1/num2=result1),该程序的缺陷,每次执行只能出一道题减法可能出现负值除法可能出现除0结果太单调,小结,本章主要介绍了计算机实现逻辑思维的机制。主要包括两个方面：如何表示一个逻辑判断如何根据逻辑判断的结果执行不同的处理逻辑判断关系表达式实现逻辑表达式根据逻辑判断执行不同的处理if语句switch语句,第4章循环控制,重复N次循环While循环Dowhile循环循环的中途退出枚举法贪婪法,for循环语句,格式：for（表达式1；表达式2；表达式3）语句执行过程：1.执行表达式12.执行表达式23.如果表达式2的结果为“true”，则执行循环体和表达式3，然后回到2，否则for语句执行结束,循环体,循环控制行,for循环语句续,作为计数循环，可以理解为for(循环变量赋初值；循环条件；循环变量增值)符合循环条件时的执行语句循环体所有语句的一次完全执行称为一个循环周期循环体可以是复合语句或空语句,逗号表达式,格式：表达式1，表达式2，,表达式n执行过程：先执行表达式1，再执行表达式2，再执行表达式n，整个表达式的计算结果为最后一个表达式的值逗号运算符的优先级是所有运算符中最低的如a的初值为0，则表达式a+=1,a+=2,a+=3,a+=4,a+=5的结果为15,有了逗号表达式，从1加到100的问题就可以只用一个语句：for(i=1,s=0;i=100;+i)s+=i;或将所有的初始化都放在循环外，即i=1；s=0；for(；i=100;+i)s+=i;建议还是用s=0;for(i=1;i=100;+i)s+=i;,for循环的进一步讨论续,表达式2也不一定是关系表达式。它可以是逻辑表达式，甚至可以是算术表达式。当表达式2是算术表达式时，只要表达式的值为非0，就执行循环体，表达式的值为0时退出循环。如果表达式2省略，即不判断循环条件，循环将无终止地进行下去。无终止的循环称为“死循环”最简单的死循环是for(;);要结束一个无限循环，必须从键盘上输入特殊的命令以中断程序执行并强制退出,For循环的进一步讨论续,表达式3也可以是任何表达式，一般为赋值表达式或逗号表达式。表达式3是在每个循环周期结束后对循环变量的修正。表达式3也可以省略，此时做完循环体后直接执行表达式2。如从1加到100，可以写为s=0;for(i=1;ib;coutdlt;for(doublex=a+dlt/2;xb;x+=dlt)integral+=(x*x+5*x+1)*dlt;cout积分值为：integralx;ex=0;p=1;i=0;while(p1e-6)ex+=p;+i;p=p*x/i;coute的x次方等于：ex0)x1=x;elsex2=x;while(fabs(fx)1e-7);cout方程的根为：xendl;return0;,第4章循环控制,重复N次循环While循环Dowhile循环循环的中途退出枚举法贪婪法,循环的中途退出,考虑一个读入数据直到读到标志值的问题。如用自然语言描述，基于标志的循环的结构由以下步骤组成：读入一个值如果读入值与标志值相等，则退出循环执行在读入那个特定值情况下需要执行的语句当一个循环中有一些操作必须在条件测试之前执行时，称为循环的中途退出问题。,问题,由于循环语句是先判断条件再决定是否执行循环体，循环的中途退出将使得循环体中的某些语句必须重复出现。基于标志的循环结构被改为：读入一个值While（读入值与标志值不相等）执行在读入那个特定值情况下需要执行的语句读入一个值,解决方案,break语句：跳出循环上述问题可以用下列方案解决：while(true)提示用户并读入数据if(value=标志)break;根据数据作出处理continue语句：跳出当前循环周期,第4章循环控制,重复N次循环While循环Dowhile循环循环的中途退出枚举法贪婪法,枚举法,对所有可能的情况一种一种去尝试，直到找到正确的答案。枚举法的实现基础是循环。,枚举法实例一,用50元钱买了三种水果。各种水果加起来一共100个。西瓜5元一个，苹果1元一个，桔子1元3个，设计一程序输出每种水果各买了几个它有两个约束条件：第一是三种水果一共100个；第二是三种水果一共花了50元可以按一个约束条件列出所有可行的情况，然后对每个可能解检查它是否满足第二个约束条件。也可以用第二个约束条件列出所有情况，然后对每个可能解检查它是否满足第一个约束条件。,#includeusingnamespacestd;intmain()intmellon,apple,orange;/分别表示西瓜数、苹果数和桔子数for(mellon=1;mellon10;+mellon)/对每种可能的西瓜数for(apple=1;apple50-5*mellon;+apple)/当西瓜数给定后可能的苹果数orange=3*(50-5*mellon-apple);/剩下的钱全买了桔子if(mellon+apple+orange=100)/三种水果数之和是否为100coutmellon:mellon;coutapple:apple;coutorange:orangeendl;return0;,执行结果,Mellon：1apple：18orange：81Mellon：2apple：11orange：87Mellon：3apple：4orange：93,实例二四大湖问题,上地理课时，四个学生回答我国四大湖的大小时分别说：甲：洞庭最大，洪泽最小，鄱阳第三乙：洪泽最大，洞庭最小，鄱阳第二，太湖第三丙：洪泽最小，洞庭第三丁：鄱阳最大，太湖最小，洪泽第二，洞庭第三对于每个湖的大小，每个人仅答对一个，设计一程序让计算机通过这些信息去判别四个湖的大小。,解题思路,如果用a,b,c,d分别表示四个湖的排序。a表示洞庭湖，b表示洪泽湖，c表示鄱阳湖，d表示太湖。我们可以假设：洞庭最大，洪泽第二，鄱阳第三，太湖第四，然后检查每位同学是否都讲对了一个。如果不是，再尝试下一种情况：洞庭最大，洪泽第二，鄱阳第四，太湖第三，再检查每位同学是否都讲对了一个。尝试所有可能的情况，直到满足每位同学都讲对一个为止。,枚举法续,为了尝试所有情况，我们需要假设洞庭湖可能是最大，也可能是第二、第三或第四。因此，a的值可能从1变到4。同样，b,c,d的值也都可能从1变到4。为此，我们需要一个控制结构，使a,b,c,d的值能自动从1变到4。这种结构就是循环结构。,四大湖排列问题的解,main()inta,b,c,d;for(a=1;a=4;+a)for(b=1;b=4;+b)if(a=b)continue;elsefor(c=1;c=4;+c)if(c=a|c=b)continue;elsed=10ab-c;if(a=1)+(b=4)+(c=3)=1,问题：效率差解决方法：一旦找到答案就应该结束,main()inta,b,c,d;boolflag=false;for(a=1;a=4;+a)for(b=1;b=4;+b)if(a=b)continue;elsefor(c=1;c=4;+c)if(c=a|c=b)continue;elsed=10ab-c;if(a=1)+(b=4)+(c=3)=1,改进版1：,程序不够简练,main()inta,b,c,d;boolflag=false;for(a=1;a=4,改进版2,列出ABC三个字母的全排列,解题思路：让第一个位置的值从A依次变到C让第一个位置的值从A依次变到C让第一个位置的值从A依次变到C注意三个位置的值不能相同可以用一个三层的嵌套循环实现，循环变量是字符类型,intmain()charc1,c2,c3;for(c1=A;c1=C;+c1)for(c2=A;c2=C;+c2)if(c1=c2)continue;elsefor(c3=A;c3=C;+c3)if(c3=a1|c3=c2)continue;elsecoutc1c2c3=ONEJIAO)onejiao+;money-=ONEJIAO;while(money=FIVEFEN)fivefen+;money-=FIVEFEN;while(money=TWOFEN)twofen+;money-=TWOFEN;while(money=ONEFEN)onefen+;money-=ONEFEN;/输出结果cout1角硬币数：onejiaoendl;cout5分硬币数：fivefenendl;cout2分硬币数：twofenendl;cout1分硬币数：onefenintarrayidx;coutendl;for(idx=0;idx=9;+idx)coutsheepi;for(i=0;imax)max=sheepi;maxNum=i;cout“最重的羊是第”maxNum“只”endl;cout“它的重量是”maxsheepi;for(i=0;imax)max=sheepi;maxNum=i;cout“最重的羊是第”maxNum“只”endl;cout“它的重量是”maxx;for(k=0;k10;+k)if(x=arrayk)coutk;break;if(k=10)coutx;lh=0;rh=9;while(lhrh)cout没有找到endl;return0;,搜索算法的效率,顺序搜索的平均时间性能（1+2+3+n)/n=(n+1)/2二分查找的最坏情况的时间性能n/2/2/2/2=1k=log2n,N和log2N的值,排序与查找,顺序查找二分查找选择排序法气泡排序法,选择排序,使数组元素按某种次序排列选择排序法：在所有元素中找到最小的元素放在数组的第0个位置在剩余元素中找出最小的放在第一个位置。以此类推，直到所有元素都放在适当的位置用伪代码表示,intlh,rh,array;输入要排序的元素，存入array;for(lh=0;lhn;lh+)在array的从lh到n1的元素之间找出最小的放入rh;交换下标lh和rh中的值;输出排好序的元素;,选择排序实例,选择排序的完善,intmain()intlh,rh,k,tmp;intarray=2,5,1,9,10,0,4,8,7,6;for(lh=0;lh10;lh+)rh=lh;for(k=lh;k10;+k)if(arraykarrayrh)rh=k;tmp=arraylh;arraylh=arrayrh;arrayrh=tmp;for(lh=0;lh10;+lh)coutarraylh;return0;,选择排序的效率,对n个元素的排序来说，找出第一个元素要比较n次，找出第二个元素比较n-1次，找出第n个元素比较一次。因此，总的比较次数为：1+2+3+n=n(n+1)/2则称时间复杂性为O(n2),排序与查找,顺序查找二分查找选择排序法气泡排序法,气泡排序法,对数组元素进行扫描。第一遍扫描冒出一个最大的气泡，放入最后一个位置。然后对剩余元素再进行第二次冒泡，冒出最大的泡放入倒数第二个位置，依次执行到最后一个元素。伪代码表示,For(i=1;in;+i)从元素0到元素n-i进行冒泡，最大的泡放入元素n-i；,冒泡过程,将待冒泡的数据从头到尾依次处理：比较相邻的两个元素，如果大的在前小的在后，就交换这两个元素。这样经过从头到尾的检查，最大的一个就被交换到最后了如果在一次起泡中没有发生交换，则表示数据都已排好序，不需要再进行起泡,进一步细化,for(i=1;in;+i)从元素0到元素n-i进行起泡，最大的泡放入元素n-i；if（没有发生过数据交换）break;,待冒泡的元素,待冒泡的元素,待冒泡的元素,待冒泡的元素,待冒泡的元素,待冒泡的元素,intmain()inta=0,3,5,1,8,7,9,4,2,10,6;inti,j,tmp,n=11;boolflag;for(i=1;in;+i)flag=false;for(j=0;jn-i;+j)if(aj+1aj)tmp=aj;aj=aj+1;aj+1=tmp;flag=true;if(!flag)break;/*一趟冒泡中没有发生交换，排序结束*/coutendl;for(i=0;in;+i)coutaiNumOfColANumOfColB;,/输入数组Acoutaij;/输入数组Bcoutbij;,/执行A*Bfor(i=0;iNumOfRowA;+i)for(j=0;jNumOfColB;+j)cij=0;for(k=0;kNumOfColA;+k)cij+=aik*bkj;,/输出数组Ccoutn输出数组C:;for(i=0;iNumOfRowA;+i)coutendl;for(j=0;jNumOfColB;+j)coutcijt;return0;,程序举例-打印N阶魔阵,第一个元素：第一行中间一列,下一单元：行-1，列+1,如行-1，列+1有内容，则下一单元为“行+1，列不变”,填写魔阵的思想,row=0;col=N/2;magicrowcol=1;for(i=2;iscale;,/生成魔阵row=0;col=(scale-1)/2;magicrowcol=1;for(count=2;count=scale*scale;count+)if(magic(row-1+scale)%scale(col+1)%scale=0)row=(row-1+scale)%scale;col=(col+1)%scale;elserow=(row+1)%scale;magicrowcol=count;/输出for(row=0;rowscale;row+)for(col=0;colscale;col+)coutmagicrowcolt;coutch;要输出ch的内容。可直接用coutb)return(a)elsereturn(b);,函数体,函数的命名,函数名是一个标识符，符合标识符命名规范函数名要有意义函数名一般是一个动词短语，表示函数的行为,函数举例无参数、无返回值的函数,打印一个由五行组成的三角形,*,voidprintstar()cout“*n”;cout“*n”;cout“*n”;cout“*n”;cout“*n”;,函数举例有参数、无返回值的函数,打印一个由n行组成的三角形,voidprintstar(intnumOfLine)inti,j;for(i=1;i=numOfLine;+i)coutendl;for(j=1;j=numOfLine-i;+j)cout;for(j=1;j=2*i-1;+j)coutnum;if(num=1,函数举例有参数、有返回值的函数,计算n!,intp(intn)ints=1,i;if(nxy;coutb)return(a);elsereturn(b);,函数原型说明,函数调用,函数实现,函数调用,#includeintmax(inta,intb)if(ab)return(a);elsereturn(b);main()intx,y;cinxy;coutxy;coutn2?n1:n2);,第6章过程封装函数,函数自己编写函数函数的使用数组作为参数带默认值的函数内联函数,重载函数函数模板变量的作用域变量的存储类别递归函数基于递归的算法,数组作为函数的参数,设计一函数，统计10位同学的平均成绩设计考虑：如何传递参数参数是10位同学的考试成绩，可以用10个整型数来表示。所以有10个整型的形式参数一组同类数据可以用一个数组来描述，所以参数也可以是一个10个元素的整型数组第二种方法更加简练返回值是平均成绩,统计函数的实现,intaverage(intarray10)inti,sum=0;for(i=0;iscorei;cout平均成绩是：average(score)side;coutcube(side)b?a:b；,函数模板的使用,maxNum=max(3,7);maxChar=max(z,a);maxDouble=max(3.5,4.6);函数模板的实例化：根据实际参数确定模板参数的值将模板参数的值代入函数模板，形成一个真正的函数,第6章过程封装函数,函数自己编写函数函数的使用数组作为参数带默认值的函数内联函数,重载函数函数模版变量的作用域变量的存储类别递归函数基于递归的算法,标识符的作用域,一个标识符能被存取的程序部分，称为标识符的作用域标识符的作用域与程序块有关。所谓的程序块是带有声明的复合语句如右框中有两块,Intmain(void)inta=2,b=3;coutab;inta=4;coutab;coutab;,标识符的作用域续,在块中说明的标识符是局部的，仅能在本块中和内部的块中存取。当内部块与外部块有同名标识符时，在内部块中屏蔽外部块的同名标识符。在一个函数中，我们不能存取主调程序的变量，即使知道该变量的名字。函数参数对该函数也是局部的，可以将它看成在块内，即函数体内说明的说明的变量。,局部变量和全局变量,局部变量：在块内定义的变量称为局部变量，即使是main函数中定义的变量也是局部的。全局变量：在所有的函数外面定义的变量称为全局变量作用范围：从定义位置到文件结束。如在作用范围外的函数要使用此变量，用关键词extern在函数内说明此全局变量。作用：方便函数间的数据传递请写出下列程序的执行结果：,intp=1,q=5，r=3;intf1()intp=3,r=2;q=p+q+r;cout“f1:p,q,r=“pqr;intf2()p=p+q+r;cout“f2:p,q,r=“pqr;intf3()intq;r=2*r;q=r+p;cout“f3:p,q,r=“pqr;main()f3();cout“afterf3:p,q,r=”pqr;f1();cout“