NOC 2023 知识点

1.函数的定义

1.1 函数的名字只能是数字、字母或下划线，不可以用数字开头（int 2abc 是非法的），不可以使用关键字名称（int char 是非法的）。

1.2 函数可以嵌套调用，但是不可以嵌套定义。如下例。

int fun1() {
    ...
}

int fun2() {
    func1(); // 合法
    ...
}

int fun3() {
    int fun4() { //不合法
        ...
    }
    ...
}

1.3 函数不一定要有形参，也不一定要有返回值。如下例。

int fun1() { // 无形参
    ...
}

void fun2() {
    ... // 无返回值
}

1.4 函数可以返回多个不同类型的值。如下例。

struct p {
    int x, y;
};

p fun1() {
    p p1;
    ...
    return p1;
}

2.函数的重载

2.1 多次定义同名的函数，并用调用的参数类型和个数来区别调用哪一个函数。注意，不能存在两次参数类型、个数完全相同函数重载。如下例。

int fun(int x, int y) {
    ...
} // 1 号

int fun(double x, double y) {
    ...
} // 2 号

int main() {
    fun(1, 2); // 调用 1 号
    fun(1.5, 3.5); // 调用 2 号
    ...
}

2.2 注意，常数浮点数默认为 double 精度。

3.指针和引用

3.1 指针变量存储指向另一个变量的位置，用类似 int *p 的语句来定义，并使用 *p 访问原变量的值。

3.2 引用变量是另一个变量的别名，两个名称指向同一个内存地址，用类似 int &q 来定义，并直接使用 q 来访问原变量。

3.3 两个例子中的 *p 和 q 的值进行修改时，原变量的值也同样变化。如下例。

int main() {
    int a = 10;
    int *p = &a; // 存储 a 的内存地址
    int b = *a; // 访问 a 的值

    int x = 5;
    int &q = x; // 将 q 作为 x 的别名
    q++; // q 和 x 的值同时增加
         // 实际上，应该是同一个内存地址增加
    ...
}

4.数组访问的时间复杂度

4.1 数组的访问时间复杂度是 \(O(n)\)。

4.2 数组的插入、删除时间复杂度是 \(O(n)\)。

4.3 链表中，访问和插入、删除的时间复杂度恰好相反。