内蒙古大学《算法与数据结构》讲义

《内蒙古大学《算法与数据结构》讲义》由会员分享，可在线阅读，更多相关《内蒙古大学《算法与数据结构》讲义（534页珍藏版）》请在金锄头文库上搜索。

1、下载第1章C + +程序设计大家好！现在我们将要开始一个穿越“数据结构、算法和程序”这个抽象世界的特殊旅程，以解决现实生活中的许多难题。在程序开发过程中通常需要做到如下两点：一是高效地描述数据；二是设计一个好的算法，该算法最终可用程序来实现。要想高效地描述数据，必须具备数据结构领域的专门知识；而要想设计一个好的算法，则需要算法设计领域的专门知识。在着手研究数据结构和算法设计方法之前，需要你能够熟练地运用 C + +编程并分析程序，这些基本的技能通常是从C + +课程以及其他分散的课程中学到的。本书的前两章旨在帮助你回顾一下这些技能，其中的许多内容你可能已经很熟悉了。本章我们将回顾C+ 的一些特

2、性。因为不是针对C+ 新手，因此没有介绍诸如赋值语句、if 语句和循环语句（如for 和w h i l e）等基本结构，而是主要介绍一些可能已经被你忽略的 C + +特性： 参数传递方式（如传值、引用和常量引用） 。 函数返回方式（如返值、引用和常量引用） 。 模板函数。 递归函数。 常量函数。 内存分配和释放函数：n e w与d e l e t e。 异常处理结构：t r y, c a t c h和t h r o w。 类与模板类。 类的共享成员、保护成员和私有成员。 友元。 操作符重载。本章中没有涉及的其他C + +特性将在后续章节中在需要的时候加以介绍。本章还给出了如下应用程序的代码：

3、一维和二维数组的动态分配与释放。 求解二次方程。 生成n 个元素的所有排列方式。 寻找n个元素中的最大值。此外，本章还给出了如何测试和调试程序的一些技巧。1.1 引言在检查程序的时候我们应该问一问： 它正确吗？第一部分预 备 知 识 它容易读懂吗？ 它有完善的文档吗？ 它容易修改吗？ 它在运行时需要多大内存？ 它的运行时间有多长？ 它的通用性如何？能不能不加修改就可以用它来解决更大范围的问题？ 它可以在多种机器上编译和运行吗？或者说需要经过修改才能在不同的机器上运行吗？上述问题的相对重要性取决于具体的应用环境。比如，如果我们正在编写一个只需运行一次即可丢弃的程序，那么主要关心的应是程序的正确性

4、、内存需求、运行时间以及能否在一台机器上编译和运行。不管具体的应用环境是什么，正确性总是程序的一个最重要的特性。一个不正确的程序，不管它有多快、有多么好的通用性、有多么完善的文档，都是毫无意义的（除非它变正确了） 。尽管我们无法详细地介绍提高程序正确性的技术，但可以为大家提供一些程序正确性的验证方法以及公认的一些良好的程序设计习惯，它们可以帮助你编写正确的代码。我们的目标是教会你如何开发正确的、精致的、高效的程序。1.2 函数与参数1.2.1 传值参数考察函数A b c（见程序1 - 1） 。该函数用来计算表达式 a+b+b*c+ (a+b-c) / (a+b) + 4，其中a，b和c 是整数

5、，结果也是一个整数。程序1-1 计算一个整数表达式int Abc(int a, int b, int c)return a+b+b*c+(a+b-c)/(a+b)+4;在程序1 - 1中，a，b和c 是函数Abc 的形式参数（formal parameter） ，类型均为整型。如果在如下语句中调用函数A b c：z = Abc(2,x,y)那么，2，x 和y 分别是对应于a，b 和c 的实际参数（actual parameter） 。当A bc( 2 ,x,y) 被执行时，a 被赋值为2；b 被赋值为x；c 被赋值为y。如果x 和 / 或y 不是int 类型，那么在把它们的值赋给b 和c 之前

6、，将首先对它们进行类型转换。例如，如果x 是float 类型，其值为3 . 8，那么b 将被赋值为3。在程序1 - 1中，形式参数a，b 和c 都是传值参数（value parameter） 。运行时，与传值形式参数相对应的实际参数的值将在函数执行之前被复制给形式参数，复制过程是由该形式参数所属数据类型的复制构造函数（ copy constructor）完成的。如果实际参数与形式参数的数据类型不同，必须进行类型转换，从实际参数的类型转换为形式参数的类型，当然，假定这样的类型转换是允许的。当函数运行结束时，形式参数所属数据类型的析构函数（d e s t r u c t o r）负责释放该形式参数

7、。当一个函数返回时，形式参数的值不会被复制到对应的实际参数中。因此，函数调用不会修改实际参数的值。2第一部分预 备 知 识下载1.2.2 模板函数假定我们希望编写另外一个函数来计算与程序 1 - 1相同的表达式，不过这次a，b和c是f l o a t类型，结果也是f l o a t类型。程序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;实际上不必对每一种可能的形式参数的类型都

8、重新编写一个相应的函数。可以编写一段通用的代码，将参数的数据类型作为一个变量，它的值由编译器来确定。程序 1 - 3中给出了这样一段使用t e m p l a t e语句编写的通用代码。程序1-3 利用模板函数计算一个表达式templateT Abc(T a, T b, T c)return a+b+b*c+(a+b-c)/(a+b)+4;利用这段通用代码，通过把T替换为i n t，编译器可以立即构造出程序1 - 1，把T 替换为f l o a t又可以立即构造出程序1 - 2。事实上，通过把T替换为d o u b l e或l o n g，编译器又可以构造出函数A b c的双精度型版本和长整型

9、版本。把函数 Abc 编写成模板函数可以让我们不必了解形式参数的数据类型。1.2.3 引用参数程序1 - 3中形式参数的用法会增加程序的运行开销。例如，我们来考察一下函数被调用以及返回时所涉及的操作。假定a，b 和c 是传值参数，在函数被调用时，类型T 的复制构造函数把相应的实际参数分别复制到形式参数a，b 和c 之中，以供函数使用；而在函数返回时，类型T的析构函数会被唤醒，以便释放形式参数a，b 和c。假定数据类型为用户自定义的 M a t r i x，那么它的复制构造函数将负责复制其所有元素，而析构函数则负责逐个释放每个元素（假定 Matrix 已经定义了操作符+，*和 /） 。如果我们用

10、具有1 0 0 0个元素的Matrix 作为实际参数来调用函数 A b c，那么复制三个实际参数给 a，b 和c将需要3 0 0 0次操作。当函数 A b c返回时，其析构函数又需要花费额外的 3 0 0 0次操作来释放a，b和c。在程序1 - 4所示的代码中， a，b 和c 是引用参数（ reference parameter） 。如果用语句A bc (x,y,z) 来调用函数A b c，其中x、y 和z 是相同的数据类型，那么这些实际参数将被分别赋予名称a，b 和c，因此，在函数Abc 执行期间，x、y 和z 被用来替换对应的a，b 和c。与传值参数的情况不同，在函数被调用时，本程序并没有

11、复制实际参数的值，在函数返回时也没有调用析构函数。第1章C +程序设计3下载程序1-4 利用引用参数计算一个表达式templateT Abc(T& a, T& b, T& c)return a+b+b*c+(a+b-c)/(a+b)+4;我们可以考察一下当a，b 和c 所对应的实际参数x，y 和z 分别是具有1 0 0 0个元素的矩阵时的情形。由于不需要把x，y 和z 的值复制给对应的形式参数，因此我们可以节省采用传值参数进行参数复制时所需要的3 0 0 0次操作。1.2.4 常量引用参数C + +还提供了另外一种参数传递方式常量引用（ const reference） ，这种模式指出函数不得

12、修改引用参数。例如，在程序 1 - 4中，a，b 和c 的值不能被修改，因此我们可以重写这段代码，见程序1 - 5。程序1-5 利用常量引用参数计算一个表达式templateT Abc(const T& a, const T& b, const T& c)return a+b+b*c+(a+b-c)/(a+b)+4;使用关键字const 来指明函数不可以修改引用参数的值，这在软件工程方面具有重要的意义。这将立即告诉用户该函数并不会修改实际参数。对于诸如i n t、float 和char 的简单数据类型，当函数不会修改实际参数值的时候我们可以采用传值参数；对于所有其他的数据类型（包括模板类型）

13、，当函数不会修改实际参数值的时候可以采用常量引用参数。采用程序1 - 6的语法，我们可以得到程序1 - 5的一个更通用的版本。在新的版本中，每个形式参数可能属于不同的数据类型，函数返回值的类型与第一个参数的类型相同。程序1-6 程序1 - 5的一个更通用的版本templateTa Abc (const Ta& a, const Tb& b, const Tc& c)return a+b+b*c+(a+b-c)/(a+b)+4;1.2.5 返回值函数可以返回值，引用或常量引用。在前面的例子中，函数 Abc 返回的都是一个具体值，在这种情况下，被返回的对象均被复制到调用（或返回）环境中。对于函数

14、Abc 的所有版本来说，这种复制过程都是必要的，因为函数所计算出的表达式的结果被存储在一个局部临时变量中，当函数返回时，这个临时变量（以及所有其他的临时变量和传值形式参数）所占用的空间4第一部分预 备 知 识下载将被释放，其值当然也不再有效。为了避免丢失这个值，在释放临时变量以及传值形式参数的空间之前，必须把这个值从临时变量复制到调用该函数的环境中去。如果需要返回一个引用，可以为返回类型添加一个前缀&。如：T& X(int i, T& z)定义了一个函数X，它返回一个引用参数Z。可以使用下面的语句返回z：return z；这种返回形式不会把z 的值复制到返回环境中。当函数X返回时，传值形式参数

15、i 以及所有局部变量所占用的空间都将被释放。由于z 是对一个实际参数的引用，因此，它不会受影响。如果在函数名之前添加关键字c o n s t，那么函数将返回一个常量引用，例如：const T& X (int i, T& z)除了返回的结果是一个不变化的对象之外，返回一个常量引用与返回一个引用是相同的。1.2.6 递归函数递归函数（recursive function）是一个自己调用自己的函数。递归函数包括两种：直接递归（direct recursion）和间接递归（indirect recursion） 。直接递归是指函数F的代码中直接包含了调用F的语句，而间接递归是指函数F调用了函数G，G又

16、调用了H，如此进行下去，直到F又被调用。在深入探讨C + +递归函数之前，我们来考察一下来自数学的两个相关概念数学函数的递归定义以及归纳证明。在数学中经常用一个函数本身来定义该函数。例如阶乘函数f (n) =n！的定义如下：其中n 为整数。从该定义中可以看到，当n 小于或等于1时，f (n)的值为1，如 f (-3) = f (0) = f (1) =1。当n大于1时，f (n)由递归形式来定义，在定义的右侧也出现了 f 。在右侧使用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 (n) 的一个递归定义（假定是直接递归） ，要想使它成为一个完整的定义，必须满足如下条件： 定义中必须包含一个基本部分（b a s e） ，其中对于n 的一个或多个值，f (n)必须是直接定义的（即非递归） 。为简单起见，我们假定基本部分包含了nk 的情况