junyi's blog

hahahahaha

0%

数据结构与算法

Posted on Edited on In

摘要

  • 复习计算机基础四大件，打牢基础。

第一章 C++回顾

  • 第一章讨论C++语言的一些特性。因为本章不是C++入门，所以没有介绍诸如赋值语句，if语句和循环语句(例如for和while)等基本结构。本章要复习的C++特性如下：
    • 参数传递的不同方式(例如值传递，引用传递和常量引用传递)
    • 函数或方法返回的不同方式(例如值返回，引用返回和常量引用返回)
    • 模板函数
    • 递归函数
    • 常量函数
    • 内存分配和释放函数: new，delete
    • 异常处理结构: try, catch, throw
    • 类与模板类
    • 类的公有成员，保护成员和私有成员
    • 友元
    • 操作符重载
    • 标准模板库
  • 本章包含如下应用程序的代码：
    • 动态分配和释放一维和二维数组
    • 求解二次方程
    • 生成n个元素的所有排列方式
    • 寻找n个元素的最大值

1.1 引言

  • 在检查一个程序时，我们应该问如下几个问题
    • 它正确吗？
    • 它容易读懂吗？
    • 它有完善的文档吗？
    • 它容易修改吗？
    • 它在运行时需要多大的内存？
    • 它的运行时间有多长？
    • 它的通用性如何？能否不加修改就可以解决更大范围的数据？
    • 它可以直接在多种计算机上编译和运行吗？或者说它需要修改之后才能运行？
  • 上述一些问题的重要性是相对的，取决于应用环境。但不管具体的应用环境是什么，程序最重要的特性是正确。

1.2 函数与参数

1.2.1 传值参数

1
2
3
4
int abc(int a, int b, int c)
{
    return a + b * c;
}

  • a,b和c是函数abc的形参(formal parameter)，每一个形参都是整型的。

  • 如果在下面的语句中调用函数abc

    • z = abc(2, x, y);

  • 那么, 2, x和y便分别是a，c和c对应的实参(actual parameter)

  • 形参a，b，c实际上是传值参数(value parameter)。在运行时，函数abc执行前，把实参复制给形参，复制过程是由形参类型的复制构造函数(copy constructor)来完成的。如果实参和形参的类型不同，必须进行类型转换，把实参转换为形参的类型，当然，前提是这样的类型转换是允许的。

  • 当函数运行结束时，形参类型的析构函数(destructor)负责释放形式参数。当一个函数运行结束时，形参的值不会被复制到对应的实参中。因此，函数调用不会修改与形参对应的实参的值。

1.2.2 模板函数

1
2
3
4
5
template<class T>
T abc(T a, T b, T c)
{
    return a + b * c;
}

1.2.3 引用参数

  • 使用形参会增加程序的运行时间。例如，我们来考察一下函数被调用以及返回时所涉及的操作。当a，b和c是传值参数时，一进入函数调用，类型T的复制构造函数便把相应的实参分别复制给形参a，b和c，以供函数使用。当函数返回时，类型T的析构函数被启用，以释放形式参数a，b和c的空间。
    1
    2
    3
    4
    5
    template<class T>
    T abc(T& a, T& b, T& c)
    {
        return a + b * c;
    }
  • 与传值参数的情况不同，当函数被调用时，这个程序没有复制实参的值，在函数返回时，也没有调用析构函数。

1.2.4 常量引用参数

  • C++还提供了另外一种参数传递模式–常量引用(const reference)。这种模式指明的引用参数不能被函数修改。
  • 用关键字const来指明函数不可修改的引用参数，这在软件工程方面具有重要意义。函数头告诉用户该函数不会修改实参。

1.2.5 返回值

  • 一个函数可以返回一个值，一个引用或一个常量引用。前面的例子都是返回一个值。在这种情况下，返回的对象被复制到调用环境中。对于函数abc的所有版本来说，这种复制过程都是必要的，因为函数所计算出的表达式结果被存储在一个局部的临时变量中，当函数结束时，这个临时变量(以及所有其他的临时变量，局部变量和传值参数)所占用的空间将被释放，其值当然也不再有效。为了不丢失这个值，在释放临时变量，局部变量以及传值参数的空间之前，要把这个值从临时变量复制到调用该函数的环境中去。
  • 给函数返回类型增加一个后缀 &，我们便指定了一个引用返回(reference return)。函数头： T& mystery(int i, T& z);
  • 定义了一个函数 mystery，它返回的是类型T的一个引用。例如，可以使用下面的语句返回Z： return z；
  • 这种返回形式不会把z的值复制到返回环境中。当函数结束时，形参i以及所有局部变量的空间都被释放。因为z仅仅是对一个实参的引用，所以它不受影响。
  • 如果把关键字const加载函数头上，便得到const型引用返回(const reference return): const T& mystery(int i, T& z);
  • const引用返回与引用返回是类似的，不同之处在于，const引用返回在返回调用环境时，必须将值赋给const常量。

1.2.6 重载函数

  • 一个函数的签名(signature)是由这个函数的形参类型以及形参个数确定的。C++可以定义两个或更多的同名函数，但是任何两个同名函数不能有同样的签名。定义多个同名函数的机制称为函数重载(function overloading)。

1.3 异常

  • 异常是表示程序出现错误的信息。

1.3.2 处理异常

  • 一段代码抛出的异常由包含这段代码的try块来处理。紧跟在try块之后的是catch块。每一个catch块都有一个参数，参数的类型决定了这个catch块要捕捉的异常的类型。
    • catch(char *e){} : 捕捉的异常类型是 char *
    • catch(bad_alloc e){} : 捕捉的异常类型是 bad_alloc
    • catch(exception& e){} : 捕捉的异常类型是基类型exception以及所有从exception派生的类型(例如 bad_alloc, bad_typeid)
    • catch(…) {} : 捕捉所有异常，不管是什么类型。
  • catch块一般包含异常改正之后所恢复的代码。如果不可能恢复，那么catch块的代码输出报错信息。

1.4 动态存储空间分配

1.4.1 操作符 new

  • C++操作符new用来进行动态存储分配或运行时存储分配，它的值是一个指针，指向所分配空间。

1.4.4 操作符delete

  • 动态分配的存储空间不再需要时应该把它释放。释放的空间可重新用来动态分配。C++操作符delete用来释放由操作符new所分配的空间。

1.7 递归函数

  • 递归函数(recursive function)或方法自己调用自己。在直接递归(direct recursion)中，递归函数f的代码包含了调用f的语句，而在间接递归(indirect recursion)中，递归函数f调用了函数g，g又调用了函数h，如此进行下去，直至又调用了f。

1.7.3 C++递归函数

  • 使用C++可以编写递归函数。正确的递归函数必须包含基础部分。每一次递归调用，其参数值都比上一次的参数值要小，从而重复调用递归函数使参数值达到基础部分的值。

1.8 标准模板库

  • C++标准模板库(STL)是一个容器，适配器，迭代器，函数对象(也称仿函数)和算法的集合。有效使用STL，应用程序的设计会简单许多。

1.9 测试与调试

1.9.1 什么是测试

  • 正确性是程序最重要的属性。
  • 在程序测试(program testing)中，我们在目标计算机上，用一组输入数据来实际运行一个程序，然后将运行结果与期望结果相比较。这组输入数据称为测试数据(test data)。如果两个结果不同，就可以判定程序有问题。
  • 测试的目的不是要证明程序是否正确，而是要暴露程序的错误。因此，选择的测试集一定要能暴露程序的错误。测试集不同，暴露的程序错误也不同。

1.9.3 调试

  • 测试可以暴露程序的错误。一旦测试结果与期望结果不同，就说明程序有错误。确定并纠正程序错误的过程称为调试(debugging)。
感谢老板支持！敬礼(^^ゞ