C++程序设计 -1

1、山东大学计算机科学与技术学院 数据结构 第1章 C+程序设计1第1章C+程序设计程序设计山东大学计算机科学与技术学院 数据结构 第1章 C+程序设计2本章内容：C+特性：参数传递方式（如传值、引用和常量引用）。函数返回方式（如返值、引用和常量引用）。模板函数。递归函数。常量函数。内存分配和释放函数：new与delete。异常处理结构：try,catch和throw。类与模板类。类的共享成员、保护成员和私有成员。友元。操作符重载。4/30/20223Value Parameters Template Functions Reference ParametersConst Reference Pa

2、rameters Return Values 递归函数(Recursive Functions)斐波那契数列(Fibonacci numbers)阶乘(Factorial)排列(Permutations)1.2 Functions and Parameters 4/30/20224程序1-1 计算一个整数表达式int Abc(int a, int b, int c)return a+b+b*c+4;X=10;Y=20;z=Abc(2,x,y)形式参数( formal parameter)实际参数(actual parameter)复制构造函数( copy constructor)1.析构函数(

3、destructor)1.2.1传值参数(Value Parameters)4/30/20225传值传递模式- 1存储器状态int Abc(int a, int b, int c)return a+b+b*c+4;AA. 在执行方法前，局部量的不存在。在 Abc方法前A代码m=20;x = 10;y = 15;z=Abc(m,x,y);x x1010y1015m1020z10？4/30/20226传值传递模式- 2存储器状态B. 调用方法时首先给形式参数分配空间，然后把实际参数的值赋给对应的形式参数。Values are copied atBint Abc(int a, int b, int

4、c)return a+b+b*c+4;代码m=20;x = 10;y = 15;z=Abc(m,x,y);Bm1020 x1010a1020b1010c1015y1015z10？4/30/20227传值传递模式- 3C存储器状态C. 在方法体中，使用形式参数运算。执行 后Cint Abc(int a, int b, int c)return a+b+b*c+4;代码m=20;x = 10;y = 15;z=Abc(m,x,y);m1020 x1010y1015a1020b1010c1015z10？4/30/20228传值传递模式- 4代码D存储器状态D. 方法体执行完，形式参数失去了意义，在方

5、法体中没有改变实际参数的值，计算植被返回。. 执行方法后Dint Abc(int a, int b, int c)return a+b+b*c+4;m=20;x = 10;y = 15;z=Abc(m,x,y);m1020 x1010y1015z101844/30/20229程序1-2 计算一个浮点数表达式float Abc(float a, float b, float c)return a+b+b*c+4;重新编写一个相应的函数？1.2.2模板函数(Template Functions)4/30/202210实际上不必对每一种可能的形式参数的类型都重新编写一个相应的函数。可以编写一段通用的

6、代码，将参数的数据类型作为一个变量，它的值由编译器来确定。templateT Abc(T a, T b, T c)return a+b+b*c+4;1.2.3模板函数(Template Functions)模板函数使用示例main()int n=1; int k=1; int j=2; int m=abc(n,k,j);/ 4/30/2022114/30/202212传值参数形式参数的用法会增加程序的运行开销。程序1-3中，在函数被调用时，类型T 的复制构造函数把相应的实际参数分别复制到形式参数a，b 和c 之中，以供函数使用；而在函数返回时，类型T的析构函数会被唤醒，以便释放形式参数a，b

7、和c。T : Matrix(10*10)Abc 被调用时 :300次操作 (copy constructors)Abc 返回时: 300 次操作 (destructors)1.2.3引用参数(Reference Parameters)4/30/202213程序1-4 利用引用参数计算一个表达式templateT Abc(T& a, T& b, T& c)return a+b+b*c+(a+b-c)/(a+b)+4;Abc(x,y,z):Abc 被调用时 :实际参数（x、y 和z）将被分别赋予名称a，b 和cAbc(x,y,z):在函数Abc 执行期间，x、y 和z 被用来替换对应的a，b 和c

8、。与传值参数的情况不同，在函数被调用时，本程序并没有复制实际参数的值，在函数返回时也没有调用析构函数。 1.2.3引用参数(Reference Parameters)4/30/202214传引用传递模式- 2存储器状态B.调用参数的值，这里是一个地址，被复制给形式参数。Values are copied atBint Abc(int a, int b, int c)return a+b+b*c+(a+b-c)/(a+b)+4;代码m=3;x = 10;y = 20;z=Abc(m,x,y);Bm1020 x1010y1015z10？abc4/30/202215传引用传递模式- 4代码D存储器状

9、态D. 方法体执行完，形式参数失去了意义，在方法体中没有改变实际参数的值，计算植被返回。. 执行方法后Dint Abc(int a, int b, int c)return a+b+b*c+(a+b-c)/(a+b)+4;m=3;x = 10;y = 20;z=Abc(m,x,y);m1020 x1010y1015z101844/30/202216templateT Abc(const T& a, const T& b, const T& c)return a+b+b*c+(a+b-c)/(a+b)+4;这种模式指出函数不得修改引用参数。1.2.4常量引用参数(Const Reference

10、Parameters)4/30/202217对于诸如i n t、float 和char 的简单数据类型，当函数不会修改实际参数值的时候我们可以采用传值参数；对于所有其他的数据类型（包括模板类型），当函数不会修改实际参数值的时候可以采用常量引用参数。编程建议:4/30/202218函数可以返回值，引用或常量引用。返回值，在这种情况下，被返回的对象均被复制到调用（或返回）环境中。返回引用，可以为返回类型添加一个前缀&， 返回值是对一个实际参数的引用，不会复制值到返回环境中。 T &X(int i,T& z) Return z; 常量引用返回，返回的结果是一个不变化的对象。 Const T &X(i

11、nt i,T& z)1.2.5返回值(Return Values)4/30/202219递归函数是一个自己调用自己的函数。递归函数包括两种：直接递归(direct recursion)和间接递归(indirect recursion)。l直接递归是指函数F的代码中直接包含了调用F的语句 F Fl间接递归是指函数F调用了函数G，G又调用了H，如此进行下去，直到F又被调用 FGHF1.2.6递归函数(Recursive Functions)4/30/2022201. 数学函数的递归定义阶乘函数 f(n)=n！完整的递归定义，必须包含：n基本部分 （一般包含了nk 的情况） f(n)=1 n 1 f

12、(n) 是直接定义的（即非递归） n递归部分: （右侧所出现的所有f 的参数都必须有一个比n 小 ） f(n)=nf(n-1) n1 1.2.6 递归函数4/30/2022212. C+递归函数一个正确的递归函数必须包含：l一个基本部分l递归调用部分(所使用的参数值应比函数的参数值要小)例 1-1 (程序 1-7)int Factorial(int n) /计算 n！ if (n=1) return 1; else return n*Factorial(n-1);1.2.6 递归函数4/30/202222递归过程在实现时，需要自己调用自己。层层向下递归，退出时的次序正好相反4/30/20222

13、3递归工作栈每一次递归调用，需要分配存储空间，来保留程序的状态(如局部变量、参数值、代码的执行位置等) 。每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。递归递归工作记录工作记录4/30/202224例1-2 模板函数Sum 计算元素a 0至an-1 的和程序 1-9templateT Rsum(T a, int n) if (n 0) return Rsum(a, n-1) + an-1; return 0;1.2.6 递归函数4/30/202225例1-3 斐波纳西Fib斐波那契数列的定义：F0=0，F1=1，Fn=Fn-1+Fn-2 (n1)int Fib(int n)/计

14、算n！if(n=0) return 0; if(n=1) return 1;return fibo1(n-1)+fibo1(n-2);1.2.6 递归函数4/30/202226例1-3 排列 E=e1, e2, en-1, en，Ei= e1, ei-1, ei+1, en-1, enPerm(X)=集合X 中元素的排列方式 。ei Perm(X)=在perm (X) 中的每个排列方式的前面均加上ei以后所得到的排列方式。E=a,b,cE1= b,c, E2= a,c, E3= a,bPerm(E1)=(bc,cb)a Perm(E1)=(abc,acb)Perm(E)=?1.2.6 递归函数

15、4/30/202227E=a,b,cperm(E)=a.perm(b,c)+b.perm(a,c)+c.perm(a,b)。同样，按照递归定义有perm(b,c)=b.perm(c)+c.perm(b),所以a.perm(b,c)=ab.perm(c)+ac.perm(b) =ab.c+ac.b=(abc,acb)。同理可得b.perm(a,c)=ba.perm(c)+bc.perm(a) =ba.c+bc.a=(bac,bca)，c.perm(a,b)=ca.perm(b)+cb.perm(a) =ca.b+cb.a=(cab,cba)。所以perm(E)=(abc,acb,bac,bca,

16、cab,cba)。排列递归模拟4/30/202228程序程序1-101-10使用递归函数生成排列使用递归函数生成排列前缀为前缀为list0list0：k-1,k-1,后边为后边为listklistk：mm的全排列的全排列templatetemplateVoid Perm(T list,int k,int m)Void Perm(T list,int k,int m)/生成生成listklistk：mm的所有排列方式的所有排列方式int i;int i;if(k = m)if(k = m)/输出一个排列方式输出一个排列方式for(i=0;i=m;i+)for(i=0;i=m;i+) coutli

17、sti; coutlisti;coutendl;coutendl; else/else/listklistk：mm有多个排列方式，递归地产生这些排列方式有多个排列方式，递归地产生这些排列方式for(i=k;i=m;i+)for(i=k;i=m;i+)Swap(listk,listi);Swap(listk,listi);Perm(list,k+1,m);Perm(list,k+1,m);Swap(listk,listi);Swap(listk,listi); 排列递归实现4/30/202229n递归优点：递归简洁、易编写、易懂易证明正确性n递归缺点：递归效率低重复计算多1.2.6 递归函数4/

18、30/202230n递归函数改为非递归n改为非递归的目的是提高效率n单向递归可直接用迭代实现非递归n其他情形必须借助栈实现非递归1.2.6 递归函数4/30/202231阶乘非递归实现计算n！的非递归函数int Factorial(int n)/计算n！if(n=1) return 1;int f=2;for(int i=3;i=n;i+)f*=i;return f;1.2.6 递归函数4/30/202232斐波那契数列非递归实现long Fib ( long n ) if ( n = 1 ) return n; long twoback = 0, oneback = 1, Current; for ( int i = 2; i = n; i+ ) Current = twoback + oneback