《数据结构,算法与应用 C++语言描述》- 第1章 练习题答案

Chapter1 练习题

Q1

解释:因为形参没有使用引用。形参是通过对实参的值进行的复制得到的,所以函数体中任何对形参的修改都不会作用于实参。

改进:

void swap(int& x, int& y)
{
  int temp = x;
  x = y;
  y = temp;
}

Q2

  • 注意模板函数如何传递数组的常量引用。语法const T (&arr)[N],解读

    • const常量,不允许修改实参

    • T为数组中元素的类型

    • (&arr)表示对数组的引用

    • [N]表示数组的元素个数

  • 注意声明数组的方式,未指定数组元素个数,由编译器根据{}中的元素个数确定。通过本例学会如何传递数据(按引用传递)

  • 注意count()调用时,只传递了数组名,未传递数组大小

#include <iostream>

template <typename T, std::size_t N>
std::size_t count(const T (&arr)[N]) {
    return N;
}

int main() {
    int intArray[] = {1, 2, 3, 4, 5};
    double doubleArray[] = {1.1, 2.2, 3.3, 4.4};

    std::size_t intCount = count(intArray);
    std::size_t doubleCount = count(doubleArray);

    std::cout << "Number of elements in intArray: " << intCount << std::endl;
    std::cout << "Number of elements in doubleArray: " << doubleCount << std::endl;

    return 0;
}

Q3

#include <iostream>

template <typename T, std::size_t N> // support the size of array
void fill(T (&arr)[N], T eleValue) // don't use const so as to modify real parameter
{
    for (int i = 0; i < N; i++)
    {
        arr[i] = eleValue;
    }
}

template <typename T, std::size_t N>
void showArr(const T (&arr)[N])
{
    for (int i = 0; i < N; i++)
    {
        std::cout << arr[i];
        if (i != N - 1) std::cout << ",";
    }
    std::cout << std::endl;
}

int main()
{
    int intArr[] = {1, 2, 3};
    std::cout << "original array elements: " << std::endl;
    showArr(intArr);

    fill(intArr, 6);
    std::cout << "after filled with value, current array elements: " << std::endl;
    showArr(intArr);
}

Q4

  • T()的用法,它的作用是对类型T进行初始化
    • 对于大多数内置类型,都会默认初始化为0值
    • 只有T类型有构造函数,就可以正确地初始化,通常应该设置为默认为0值
    • 对于用户自定义类型,可能会出错,这需要在使用时注意
  • 特别要注意,函数中临时创建的值(作用域为函数内),不能返回它的引用。因为函数运行结束后,所有临时变量都将被析构
#include <iostream>

template <typename T, std::size_t N>
T inner_product(const T (&array1)[N], const T (&array2)[N])
{
    T result = T();  // 使用 T() 来初始化。不要使用T result =0,因为T的类型是不确定的,赋值为0可能导致问题
    for (std::size_t i = 0; i < N; i++)
    {
        result += (array1[i] * array2[i]);
    }

    return result;
}

int main()
{
    int arr_a[] = {1, 2, 3, 4, 5};
    int arr_b[] = {6, 7, 8, 9, 10};

    int result = inner_product(arr_a, arr_b);
    std::cout << "Inner product: " << result << std::endl;

    return 0;
}

Q5

区别两种情况,即是否要修改实参数组中的元素。既然题干中提到了a[i]=value+i,就表示在实参中修改了。

#include <iostream>

template <typename T, std::size_t N>
void iota(T (&arr)[N], T value) // do not use 'const' so as to apply modification to real parapter
{
    for (int i = 0; i < N; i++)
    {
        arr[i] = value + i;
    }
}

template <typename T, std::size_t N>
void showArr(const T (&arr)[N])
{
    for (int i = 0; i < N; i++)
    {
        std::cout << arr[i];
        if (i != N - 1) std::cout << ",";
    }
    std::cout << std::endl;
}

int main()
{
    int intArray[] = {1, 2, 3, 4, 5};
    int value = 3;

    showArr(intArray);

    iota(intArray, value);

    showArr(intArray);
}

Q6

本题所谓的有序,可以指定是升序还是降序。当前回答

仅考虑升序:

#include <iostream>

template <typename T, std::size_t N>
bool is_stored(const T (&arr)[N])
{
    for (int i = 0; i < N; i++)
    {
        // don't need compare last element
        if (i == N - 1) return true;

        if (arr[i] <= arr[i + 1]) continue;
        else return false;
    }
}

int main()
{
    int intArray[] = {1, 2, 3, 7, 5};

    if (is_stored(intArray)) std::cout << "sorted" << std::endl;
    else std::cout << "not sorted" << std::endl;
}

同时考虑升序或降序

#include <iostream>

template <typename T, std::size_t N>
bool is_stored(const T (&arr)[N])
{
    bool ascending_order = true;

    // if ascending order
    for (int i = 0; i < N; i++)
    {
        // don't need compare last element
        if (i == N - 1) return true;

        if (arr[i] <= arr[i + 1]) continue;
        else
        {
            ascending_order = false;
            break;
        }
    }

    // if descending order
    for (int i = 0; i < N; i++)
    {
        // don't need compare last element
        if (i == N - 1) return true;

        if (arr[i] >= arr[i + 1]) continue;
        else return false;
    }
}

int main()
{
    int intArray[] = {7, 5, 2};

    if (is_stored(intArray)) std::cout << "sorted" << std::endl;
    else std::cout << "not sorted" << std::endl;
}

Q7

#include <iostream>

// good habit to grant meaning to special number
#define NOMATCH -1

template <typename T, std::size_t N>
int mismatch(const T (&arr1)[N], const T (&arr2)[N])
{
    for (int i = 0; i < N; i++)
    {
        if (arr1[i] != arr2[i])
            return i;
    }
    return NOMATCH;
}

int main()
{
    int intArray1[] = {6, 5, 2};
    int intArray2[] = {6, 5, 1};

    int result = mismatch(intArray1, intArray2);
    if (result != NOMATCH)
        std::cout << "matched index: " << result << std::endl;
    else
        std::cout << "no match" << std::endl;

    return 0;
}

Q8

两个函数签名相同。原因:判断函数签名,看两点,只要这两条相同,则视为具有相同签名

  1. 函数名,本题中均为abc
  2. 参数。包括参数类型和个数

仅仅通过返回值类型的不同,不能视为重载(overloading),既然不是重载,如果二者同时存在,则会报错error: ambiguating new declaration of xxx

Q9

本题要理解编译器为什么要报错?就是编译器不会自作主张。

当编译器既可以这样也可以那样时,就会报错,因为它不知道你的真实目的(你想要的结果)是什么。

  • 1).3个参数均为int,编译器有两个选择,abc(int,int,int)abc(float,float,float),这时是没有歧义的,只能选择abc(int,int,int)
  • 2).3个参数均为float,同理,也无歧义
  • 3).参数为(int,int,float),编译器发现没有现成的函数签名可用,但可以通过类型转换使用已经有的签名,但问题来了,既然可以将int转为float调用abc(float,float,float),也可以将float转为int调用abc(int,int,int),这时编译器就会报错
  • 4).3个参数均为double类型,通过类型转换,既可以都转为int,也可以都转换为float,于是编译器又不知道该选哪个了,从而报错