算法设计与分析讲义-中科院-陈玉福appendix

《算法设计与分析讲义-中科院-陈玉福appendix》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、206附录1.关于C++程序设计在程序开发过程中通常需要做到如下两点：一是高效地描述数据；二是设计一个好的算法，该算法最终可用程序来实现。要想高效地描述数据，必须具备数据结构领域的专门知识；要想设计一个好的算法，需要算法设计领域的专门知识。这里我们采用C++语言来描述算法，并假定大家已经掌握了C++程序设计的基本方法。同时还假设大家已经具备数据结构的必备知识，剩下的主要任务是探讨算法设计领域的专门知识。为了便于今后的学习，我们还是简要地回顾一下C++程序设计方面的有关知识和数据结构方面的知识。本章主要复习C++程序设计方面的知识，内容主要有

2、：模板函数、参数传递方式、类与模板类、类的共享成员－保护成员－私有成员、友元、操作符重载、数组的动态分配与释放等。§1模板函数1.1函数与模板函数考察下列函数：程序1-1计算一个整数表达式intAbc(inta,intb,intc){returna+b+c+b*c+(a+b+c)/(a+b)+4;}程序1-2计算一个浮点数表达式floatAbc(floata,floatb,floatc){returna+b+c+b*c+(a+b+c)/(a+b)+4;207}这两个函数中除了形式参数与返回值的类型不同外，再没有别的差别。如果我们能够编写一段

3、通用代码，将参数的数据类型作为一个变量，它的值由编译器来确定，就可以简化程序的编写工作，这一特性在C++语言的模板函数中体现。程序1-3利用模板函数计算一个表达式templateTAbc(Ta,Tb,Tc){returna+b+c+b*c+(a+b+c)/(a+b)+4;}利用这段通用代码，通过把T替换成int，编译器可以立即构作出程序1-1；把T替换成float又可以立即构作初程序1-2。同样可以把T替换成double和long，等等。把函数Abc编写成模板函数可以使我们免去了解形式参数的类型。1.2传值参数和引用参数在上

4、面的函数Abc中，a，b，c是形式参数。如果调用函数Abc时采用z=Abc(x,y,2)x，y，2分别是对应a，b，c的实际参数。A，b，c都是传值参数。运行时，与传值形式参数对应的实际参数的值将在函数执行之前被复制给形式参数，复制过程是由该形式参数所属数据类型的复制构造函数（copyconstructor）完成的。如果实际参数与形式参数的数据类型不同，必须进行类型转换，从实际参数的类型转换为形式参数的类型（这里假定该种类型转换是允许的）。当函数运行结束时，形式参数所属数据类型的析构函数（destructor）负责释放该形式参数。当一个函数

5、返回时，形式参数不会被复制到对应的实际参数中。因此，函数调用不会修改实际参数的值。208值得注意的是，采用传值参数会增加程序的开销。假定a，b，c是传值参数，在函数Abc被调用时，类型T的复制构造函数把相应的实际参数分别复制到形式参数a，b，c之中，以供函数Abc使用。如果用具有1000个元素的矩阵Matrix作为实际参数来调用函数Abc，那么复制三个实际参数给a，b，c，将需要3000次操作。同理，当函数Abc返回时，其析构函数又需要花费额外的3000次操作来释放a，b，c。C++语言通过使用引用参数来减少这笔开销的。程序1-4利用引用参

6、数计算一个表达式templateTAbc(T&a,T&b,T&c){returna+b+c+b*c+(a+b+c)/(a+b)+4;}在程序1-4中，a，b，c，是引用参数（referenceparameter）。如果用语句Abc（x，y，z）来调用函数Abc，其中x，y，z是相同的数据类型，那么这些实际参数被分别赋予名称a，b，c，因此，在函数Abc执行期间，x，y，z被用来替换对应的a，b，c。与传值情况不同，在函数调用时，本程序并没有复制实际参数的值，在返回也没有调用析构函数。如果x，y，z分别是1000个元素的矩阵，

7、由于不需要把x，y，z的值复制给对应的形式参数，因此，我们至少可以节省采用传值参数进行复制时所需要的3000次操作。事实上，引用只是个别名，当建立引用时，程序用另一个变量或对象（目标）的名字初始化它。引用不是值，不占用存储空间，声明引用时，目标的存储状态不会改变。引用一旦初始化，它就维系在一定的目标上，再也不分手。函数的返回值也可以采取引用的方式。程序1-6关于函数的返回值或返回引用的程序209＃includefloattemp;floatfn1(floatr){temp=r*r*3.14;returntemp;}f

8、loat&fn2(floatr){temp=r*r*3.14;returntemp;}voidmain()floata=fn1(5.0);//形式1float&b=fn1(5.0