数据结构、算法与应用-c++语言描述

《数据结构、算法与应用-c++语言描述》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

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

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

5、整数。程序1-1计算一个整数表达式intAbc(inta,intb,intc){returna+b+b*c+(a+b-c)/(a+b)+4;}在程序1-1中，a，b和c是函数Abc的形式参数（formalparameter），类型均为整型。如果在如下语句中调用函数Abc：z=Abc(2,x,y)那么，2，x和y分别是对应于a，b和c的实际参数（actualparameter）。当Abc(2,x,y)被执行时，a被赋值为2；b被赋值为x；c被赋值为y。如果x和/或y不是int类型，那么在把它们的值赋给b和c之前，将首先对它们进行类型转换。例如，如果x是float类型，其值为3

6、.8，那么b将被赋值为3。在程序1-1中，形式参数a，b和c都是传值参数（valueparameter）。运行时，与传值形式参数相对应的实际参数的值将在函数执行之前被复制给形式参数，复制过程是由该形式参数所属数据类型的复制构造函数（copyconstructor）完成的。如果实际参数与形式参数的数据类型不同，必须进行类型转换，从实际参数的类型转换为形式参数的类型，当然，假定这样的类型转换是允许的。当函数运行结束时，形式参数所属数据类型的析构函数（destructor）负责释放该形式参数。当一个函数返回时，形式参数的值不会被复制到对应的实际参数中。因此，函数调用不会修改实际参

7、数的值。第1章C++程序设计3下载1.2.2模板函数假定我们希望编写另外一个函数来计算与程序1-1相同的表达式，不过这次a，b和c是float类型，结果也是float类型。程序1-2中给出了具体的代码。程序1-1和1-2的区别仅在于形式参数以及函数返回值的数据类型。程序1-2计算一个浮点数表达式floatAbc(floata,floatb,floatc){returna+b+b*c+(a+b-c)/(a+b)+4;}实际上不必对每一种可能的形式参数的类型都重新编写一个相应的函数。可以编写一段通用的代码，将参数的数据