C++算法必备这是一本涵盖数据结构和算法的书籍，本书所用书籍使用的语言为c++；内容详细，覆盖全面。

文件名称: C++算法必备

所属分类: C/C++

开发工具:

文件大小: 16mb

下载次数: 0

上传时间: 2019-02-23

提供者: abc1592*******

下载 (16mb)

不能下载？报告错误

详细说明：这是一本涵盖数据结构和算法的书籍，本书所用书籍使用的语言为c++；内容详细，覆盖全面。Chinasbub.com 第l章C++程序设计 3 下载 1.2.2模板函数假定我们希望编写另外一个函数来计算与程序1-1相同的表达式,不过这次a,b和c是foat 类型,结果也是foat类型。程序1-2中给出了具体的代码。程序1-1和1-2的区别仅在于形式参数以及函数返回值的数据类型。程序1-2计算一个浮点数表达式 float abc( float a, float b float c return a+b+b*c+(a+b-c)/(a+b)+4 实际上不必对每一种可能的形式参数的类型都重新编写一个相应的函数。可以编写一段通用的代码,将参数的数据类型作为一个变量,它的值由编译器来确定。程序1-3中给岀了这样一段使用 d template语句编写的通用代码程序1-3利用模板函数计算一个表达式 template T Abc(T a, T b, T c return a+b+b c+(a+b-c/(a+b)+4 利用这段通用代码,通过把T替换为int,编译器可以立即构造岀程序1-1,把T替换为foat 又可以立即构造岀程序1-2。事实上,通过把7替换为 double或long,编译器又可以构造出函数 Abc的双精度型版本和长整型版本。把函数Abe编写成模板函数可以让我们不必了解形式参数的数据类型。 1.23引用参数程序1-3中形式参数的用法会增加程序的运行开销。例如,我们来考察一下函数被调用以及返回时所涉及的操作。假定a,b和c是传值参数,在函数被调用时,类型T的复制构造函数把相应的实际参数分别复制到形式参数a,b和c之中,以供函数使用;而在函数返回时,类型 T的析构函数会被唤醒,以便释放形式参数a,b和c。假定数据类型为用户自定义的 Matriⅸx,那么它的复制构造函数将负责复制其所有元素而析构函数则负责逐个释放每个元素(假定 Matrix已经定义了操作符+,*和/b如果我们用具有1000个元素的 Matrix作为实际参数来调用函数Abc,那么复制三个实际参数给a,b和c 将需要3000次操作。当函数Abc返回时,其析构函数又需要花费额外的3000次操作来释放a, b和c 在程序1-4所示的代码中,a,b和c是引用参数( reference parameter)。如果用语句 Abc(x,y,z)来调用函数Abc,其中x、y和z是相同的数据类型,那么这些实际参数将被分别赋予名称a,b和,因此,在函数Abc执行期间,x、y和z被用来替换对应的a,b和c。与传值参数的情况不同,在函数被调用时,本程序并没有复制实际参数的值,在函数返回时也没有调用析构函数第—部分预备知识 Chinaspub.com 下载程序1-4利用引用参数计算一个表达式 template T Abc(T& a, T& b, T& c) return a+b+b*C+(a+b-c/(a+b)+4 我们可以考察一下当a,b和c所对应的实际参数x,y和分别是具有1000个元素的矩阵时的情形。由于不需要把x,y和z的值复制给对应的形式参数,因此我们可以节省采用传值参数进行参数复制时所需要的3000次操作。 1.2.4常量引用参数 C艹+还提供了另外一种参数传递方式—常量引用( const reference),这种模式指出函数不得修改引用参数。例如,在程序1-4中,a,b和c的值不能被修改,因此我们可以重写这段代码,见程序1-5 程序1-5利用常量引用参数计算一个表达式 template T Abc(const T& a, const T& b, const T& c) return a+b+b*c+(a+b-c)/(a+b)+4 使用关键字 const来指明函数不可以修改引用参数的值,这在软件工程方面具有重要的意义。这将立即告诉用户该函数并不会修改实际参数。对于诸如int、 float和char的简单数据类型,当函数不会修改实际参数值的时候我们可以采用传值参数;对于所有其他的数据类型(包括模板类型),当函数不会修改实际参数值的时候可以采用常量引用参数。采用程序1-6的语法,我们可以得到程序1-5的一个更通用的版本。在新的版本中,每个形式参数可能属于不同的数据类型,函数返回值的类型与第一个参数的类型相同。程序1-6程序1-5的一个更通用的版本 template Ta Abc(const Ta& a, const Tb& b, const Tc& c) return a+b+b*c+(a+b-c)(a+b)+4; 2.5返回值函数可以返回值,引用或常量引用。在前面的例子中,函数AbC返回的都是一个具体值, 在这种情况下,被返回的对象均被复制到调用(或返回)环境中。对于函数Abc的所有版本来说,这种复制过程都是必要的,因为函数所计算出的表达式的结果被存储在一个局部临时变量中,当函数返回时,这个临时变量(以及所有其他的临时变量和传值形式参数)所占用的空间 Chia-pub co的第l章C++程序设计 5 下载将被释放,其值当然也不再有效。为了避免丟失这个值,在释放临时变量以及传值形式参数的空间之前,必须把这个值从临时变量复制到调用该函数的环境中去。如果需要返回一个引用,可以为返回类型添加一个前缀&。如: T& x(int i, T& z 定义了一个函数X,它返回一个引用参数Z。可以使用下面的语句返回z: return z 这种返回形式不会把z的值复制到返回环境中。当函数X返回时,传值形式参数i以及所有局部变量所占用的空间都将被释放。由于z是对一个实际参数的引用,因此,它不会受影响。如果在函数名之前添加关键字 const,那么函数将返回一个常量引用,例如 const T&X (int i, T& z) 除了返回的结果是一个不变化的对象之外,返回一个常量引用与返回一个引用是相同的。 1.26递归函数递归函数( recursive function)是一个自己调用自己的函数。递归函数包括两种:直接递归( direct recursion)和间接递归( indirect recursion〉直接递归是指函数F的代码中直接包含了调用F的语句,而间接递归是指函数F调用了函数G,G又调用了H,如此进行下去,直到F又被调用。在深入探讨C++递归函数之前,我们来考察一下来自数学的两个相关概念—数学函数的递归定义以及归纳证明。在数学中经常用一个函数本身来定义该函数。例如阶乘函数f(n)=n!的定义如下 f(r n≤1 nf(n-1)n>1 其中n为整数从该定义中可以看到,当n小于或等于时,f(n)的值为1,如f(-3)=f(0)=f(1)=1。当n 大于1时,f(m)由递归形式来定义,在定义的右侧也出现了∫。在右侧使用f并不会导致循环定义,因为右侧f的参数小于左侧f的参数。例如,从公式(1-1)中可以得到f(2)=2f(1),由于我们已经知道f(1)=1,因此f(2)=2*1=2。以此类推,f(3)=3f(2)=3*2=6 对于函数f(m)的一个递归定义(假定是直接递归),要想使它成为一个完整的定义,必须满足如下条件定义中必须包含一个基本部分(base),其中对于n的一个或多个值,f(m)必须是直接定义的(即非递归)。为简单起见,我们假定基本部分包含了n≤k的情况,其中k为常数。(在基本部分中指定n≥k的情形也是可能的,但较少见在递归部分( recursive component)中,右侧所出现的所有f的参数都必须有一个比n小, 以便重复运用递归部分来改变右侧出现的f,直至出现f的基本部分。在公式(1-1)中,基本部分是:当n≤1时f(n)=1;递归部分是f(m)=nf(n-1),其中右侧的参数为n-1,比n要小。重复应用递归部分可把f(n-1)变换成对f(n-2),f(n-3),…,直到f(1) 的调用。例如: f(5)=5f(4)=20f(3)=60f(2)=120f(1) 注意每次应用递归部分的结果是更趋近于基本部分,最后,根据基本部分的定义可以得到 f(5)=120。从这个例子中可以看出,对于n≥1有f(m)=n(n-1)(n-2)1 作为递归定义的另外—个例子,我们来考察一下斐波那契数列的定义第—部分预备知识 Chnapul.com 下载 F=0,F1=1,F=F+F,(n>1) (1-2 在这个定义中,F=0和F=1构成了定义的基本部分,F=F+F,是定义的递归部分。右侧函数的参数都小于n。为使公式(1-2)成为F的一个完整的递归定义,对于任何n1的斐波那契数,对递归部分的重复应用应能把右侧出现的所有F变换成基本部分的形式。因为对一个 n1的整数重复减去1或2会得到0或1,因此右侧F的出现总可以被变换成基本定义。比如, F=F +F=F +F +F +F=3F +2F =3 现在我们把注意力转向与计算机递归函数相关的第二个概念—刂归纳证明。在归纳证明中可以按照如下步骤来证明一个命题的正确性,比如证明如下公式 ∑i=n(n+1)/2(n≥0) (1-3) 首先我们可以验证,对于n的一个或多个基本的值(如n=0或n=0,1)该公式是成立的;然后假定当n∈(0m)时公式是成立的,其中m是一个任意整数(大于等于验证时所取的最大值), 如果能够证明对于n的下一个值(如m+1)公式也是成立的,那么就可以确定该公式是成立的。这种证明方法可以归纳为三个部分—归纳初值( induction base),归纳假设( induction hypothesis)和归纳步证明( induction step 下面通过对n进行归纳来证明公式(1-3)。在归纳初值部分,取n=0来进行验证,由于公式的左边●i=0,公式的右边也为0,所以当n=0时公式(1-3)是成立的。在归纳假设部分假定当n≤m时公式是成立的,其中m是任意大于等于0的整数(对于接下来的归纳证明,只需假定n=m时公式是成立的即可)在归纳证明中需要证明当n=m+1时公式(1-3)是成立的。对 1+1 于n=mt+1,公式左边为·i=m+1+·i,从归纳假设中可以知道。i=m(m+1)2,所以当n=m+1 时左边变成m+1+m(m+1)2=(m+1)(m+2)/2,正好与公式右边相等乍看起来,归纳证明好象是一个循环证明—因为我们建立了一个假设为正确的结论。不过,归纳证明并不是循环证明,就像递归定义并不是循环定义一样。每个正确的归纳证明都会有一个基本值验证部分,它与递归定义的基本部分相类似,在归纳证明时我们利用了比n值小时结论的正确性来证明取值为n时结论的正确性。重复应用归纳证明,可以减少对基本值验证的应用。 C++允许我们编写递归函数。一个正确的递归函数必须包含一个基本部分。函数中递归调用部分所使用的参数值应比函数的参数值要小,以便函数的重复调用能最终获得基本部分所提供的值。例1-1阶乘]程序1-7给出了一个利用公式(1-1)计算n!的C++函数。函数的基本部分包含了 n≤1的情形。考虑调用 Factoria(2)。为了计算else语句中的2* Factorial(1),需要挂起 Factorial(2) 然后进入调用 Factorial(1)。当 Factorial(2)被挂起时,程序的状态(如局部变量、传值形式参数的值、引用形式参数的值以及代码的执行位置等)被保留在递归栈中,在执行完 Factorial(1)时这些程序状态又立即恢复。调用 Factorial(1)所得到的返回值为1,之后, Factorial(2)恢复运行, 计算表达式2*1,并将结果返回。程序1-7计算n!的递归函数 nt Factorial (int n) 计算n! Chinasbub.com 第l章C++程序设计 7 下载 if (n<=1)return 1; else return n * Factorial(n-1) 在计算 Factorial(3)时,当到达else语句时,计算过程被挂起以便先计算出 Factorial(2)。我们已经看到 Factorial(2)是怎样获得最终结果2的。当 Factorial(2)返回时, Factorial(3)继续运行, 计算出最后的结果3*2 鉴于程序1-7的代码与公式(1-1)的相似性,该程序的正确性与公式(1-1)的正确性是等价的。例1-2模板函数Sum(见程序1-8)统计元素a[0至a[n-l的和(简记为a[0:n-1])从代码中我们可以得到这样的递归公式:当n=0时,和为0;当n>0时,n个元素的和是前面n-个元素的和加上最后一个元素。见程序1-9。程序1-8累加a[0:n-1 template T Sum(T al, int n 计算a0:n-1的和 T tsum=0 for (int i=0; i < n; i++) tsum +=a[] return tsum 程序1-9递归计算a[0:n-1] emplate T Rsum(T al, int n) 计算a[0:n-1]的和 if (n >0) return Rsum(a, n-1)+ a[n-1] return o 例1-3[排列]通常我们希望检查n个不同元素的所有排列方式以确定一个最佳的排列。比如, a,b和c的排列方式有:abc,acb,buc,bca,cab和cba。n个元素的排列方式共有n肿。由于采用非递归的C++函数来输出n个元素的所有排列方式很困难,所以可以开发一个递归函数来实现。令E={e1,…,e}表示n个元素的集合,我们的目标是生成该集合的所有排列方式。令E为E中移去元素i以后所获得的集合,pem(Y表示集合X中元素的排列方式,e,perm (η表示在perm(Y中的每个排列方式的前面均加上e以后所得到的排列方式。例如,如果 E=a, b,c), #BAE=b, c), perm(E, )=(bc, cb),e, perm(e, )=(abc, acb). 对于递归的基本部分,采用n=1。当只有一个元素时,只可能产生一种排列方式,所以 perm(E)=(e),其中e是E中的唯一元素。当n>1时,perm(E)=e,perm(E,)+e,perm (E2)+e,perm(E)+…+tn,perm(E,)。这种递归定义形式是采用n个perm(x来定义perm(E,其中每个X包含n-1个元素。至此,一个完整的递归定义所需要的基本部分和递归部分都已完成。第一部分预备知识 China-bub.com 下载当n=3并且E=(a,b,c)时,按照前面的递归定义可得pem(E)=apem({b,c})+bpem({a, c})+c,perm({a,b})。同样,按照递归定义有perm({b,c})=b.perm({c})+c,pem({b}),所以 a perm({b,c})=ab.perm({c})+ac:pem({b})=ab,c+ac.b=(abc,acb)。同理可得 b perm (a, c)=ba perm (c)+ bc perm (a)=ba.c+ bc. a=(bac, bca), cperm (a,b)= caperm (b))+cb perm (a)=ca.b+cb.a=(cab, cba), FTltperm(e)=(abc, acb, bac, bca, cab, cba)o 注意a,perm({b,c})实际上包含两个排列方式:abc和acb,a是它们的前缀,perm({b,c}) 是它们的后缀。同样地, ac pern({b})表示前缀为ac、后缀为perm({b})的排列方式。程序1-10把上述perm(E)的递归定义转变成一个C++函数,这段代码输出所有前缀为istO k-1,后缀为 llist[k:m]的排列方式。调用Perm(list,0,n-1)将得到ist0:n-1]的所有n!个排列方式,在该调用中,k=0,m=n-1,因此排列方式的前缀为空,后缀为istD:n-1]产生的所有排列方式。当k=m时,仅有一个后缀lstm],因此list[0:m]即是所要产生的输出。当k void Perm(T list[ int k, int m) /生成lst[k:m的所有排列方式 int i if(k==m){/输出一个排列方式 for(i=0; i<= m; i++) cout < list cout < end: else∥ lists:m有多个排列方式 ∥递归地产生这些排列方式 Swap(list[k], list[) Perm(list, k+1, m) Swap(list [k], list [] 程序1-11交换两个值 template inline void Swap(T& a, T& b) /交换a和b T temp = a; a=b; b= temp 练习 1.试编写一个模板函数 [Input,它要求用户输入一个非负数,并负责验证用户所输入的数是第l章C++程序设计 9 下载否真的大于或等于0,如果不是,它将告诉用户该输入非法,需要重新输入一个数。在函数非成功退出之前,应给用户三次机会。如果输入成功,函数应当把所输入的数作为引用参数返回。输入成功时,函数应返回true,否则返回alse。上机测试该函数。 2.试编写一个模板函数,用来测试数组a中的元素是否按升序排列(即a[i≤a[i+1],其中0≤ i2的整数,调用1)中的函数计算F时,同一个F会被处理至少一次。 3)试编写一个非递归的函数来计算斐波那契数列F,该函数应能直接计算出每个斐波那契数。上机测试代码的正确性。 5.试编写一个递归函数,用来输出n个元素的所有子集。例如,三个元素{a,b,c}的所有子集是:{}(空集),{a},{b},{c},{a,b},{a,c},{b,c}和{a,b,c}。 6.试编写一个递归函数来确定元素x是否属于数组a[0:n-1]。 1.3动态存储分配 1.3.1操作符new C++操作符new可用来进行动态存储分配,该操作符返回一个指向所分配空间的指针。例如,为了给一个整数动态分配存储空间,可以使用下面的语句来说明一个整型指针变量当程序需要使用该整数时,可以使用如下语法来为它分配存储空间 y new int 操作符new分配了一块能存储一个整数的空间,并将指向该空间的指针返回给y,y是对整数指针的引用,而*y则是对整数本身的引用。为了在刚分配的空间中存储一个整数值,比如10,可以使用如下语法 10 我们可以把上述三步(说明y,分配存储空间,为*y赋值)进行适当的合并,如下例所示 nt*y= new int; y=10 或 int *y new int (10) 或 int y y= new int (10); 1.32—维数组在本书的许多示例程序中都使用了一维或二维数组,这些数组的大小在编译时可能是未知的,事实上,它们可能随着函数调用的变化而变化。因此,对于这些数组必须进行动态存储分配。为了在运行时创建一个一维浮点数组ⅹ,首先必须把x说明成一个指向oat的指针,然后为数组分配足够的空间。例如,一个大小为n的一维浮点数组可以按如下方式来创建 float*x= new float [n] 10第部分预备知识 Chinapub.com 下载操作符new分配n个浮点数所需要的空间,并返回指向第一个浮点数的指针。可以使用如下语法来访问每个数组元素:x[0],x[1,…,x[n1 1.3.3异常处理在执行语句 float*x= new float [n]; 时,如果计算机不能分配足够的空间怎么办?在这种情况下,nw不能够分配所需数量的存储空间,将会引发一个异常( exception)在 Borland c++中,当new不能分配足够的空间时,它会引发( throw)一个异常 calloc(在 except h中定义)可以采用try- catch结构来捕获( catch) new所引发的异常 float x try x= new float [n] catch( calloc){∥仅当new失败时才会进入 cerr <<"Out of Memory" < endl exit(1): 1 当一个异常出现时,程序进入与该异常相对应的 catch语句块中执行。在上面的例子中,只有在执行try语句时产生了 calloc异常,才会进入 catch( calloc)语句块,由语句exit(1)终止程序的运行。(exit0在 stdlib. h中定义。) 在C艹程序中处理错误条件的常用方法就是每当检测到这样的条件时就引发一个异常。当个异常被引发时,必须指明它的类型(如前面的 calloc)我们把可能会产生异常的程序代码放入try块中,在ry块之后放上一个或多个 catch块,每个 catch块用来处理一个特定类型的异常。例如 catch(xalo块仅处理 calloc异常。语法 catch(.…)定义了一个能捕获所有异常的 catch 块。当—个异常被引发时,检査在程序执行过程中所遇到的最接近的try- catch代码,如果其中的— catch块能够处理所产生的异常,程序将从这个 catch块中继续执行,否则,继续检査直到找到与异常相匹配的块。如果找不到能处理该异常的 catch块,程序将显示信息“ Abnorma program termination(异常程序终结y并终止运行。如果一个try块没有引发异常,程序的执将越过与该try块相对应的 catch块 1.3.4操作符 delete 动态分配的存储空间不再需要时应该被释放,所释放的空间可重新用来动态创建新的结构。可以使用C艹+操作符 delete来释放由操作符new所分配的空间。下面的语句可以释放分配给*y的空间以及一维数组x delete y delete []X 1.3.5二维数组虽然℃艹提供了多种机制用来说明二维数组,但其中的多数机制都要求在编译时明确地知道每一维的大小。而且,在使用这些机制时,很难编写出一个允许形式参数是一个第二维大小未知的二维数组的函数。之所以如此,是因为当形式参数是一个二维数组时,必须指定其第二维的大小。例如,a[10是一个合法的形式参数,而a[I[]不是。克服这种限制的一条有效途径就是对于所有的二维数组使用动态存储分配。本书从头至尾

(系统自动生成,下载前可以参看下载内容)