新生 C 语言大赛

介绍

C 语言是一门用途广泛的计算机程序设计语言. 学习 C 语言, 既有助于同学们学习后续必修课计算机程序设计基础, 也可以消除学习其他编程语言的障碍.

新生 C 语言大赛由工物科协举办, 面向全校零基础新生, 以 C 语言学习与物理仿真为主题, 至今已经举办 9 届.

Online Judge

科协部署了 uoj 作为本次大赛的初赛平台.

选手在初赛中一共需要至少完成 7 道题目, 通过后才能进入决赛.

默认的测评环境是 Ubuntu Linux 20.04 LTS x64.

C 的编译器是 gcc 9.3.0, 编译命令: gcc code.c -o code -lm -O2 -DONLINE_JUDGE.

C++ 的编译器是 g++ 9.3.0, 编译命令: g++ code.cpp -o code -lm -O2 -DONLINE_JUDGE. 如果选择 C++11 会在编译命令后面添加 -std=c++11.

赛程安排

第十届新生 C 语言大赛的赛程安排如下:

时间阶段
01-11报名开始
01-18初赛宣讲会
01-18第一次线上培训
01-22第一次 OJ 作业
01-25报名结束
01-25第二次线上培训
01-25第二次 OJ 作业
02-08第三次线上培训
02-12决赛宣讲会
02-22决赛截止提交

安装 C 环境

工物科协为大家推荐以下搭建 C 开发环境的方法, 并且会帮助解决配置 DevC++, msys2 以及远程服务器 C 环境过程中出现的问题.

限于人力不足, 其他搭建 C 环境的方法不一定得到 debug 支持.

安装 DevC++ 集成开发环境

注意: DevC++ 安装方便, 然而开发体验一般.

安装与设置

文件名为 Dev-Cpp 5.11 TDM-GCC 4.9.2 Setup.exe, 访问 sourceforge 上点击 Download 即可下载, 或者可以通过科协文件服务器提供的镜像下载.

下载后双击下载文件, 依次点击 OK, I agree, Next, Install 即可安装.

安装后点击 Finish (一般会自动打开 Dev-c++, 没有的话自己打开桌面的快捷方式), 随后选择 简体中文, 点击 Next, Next, OK 即可完成设置.

使用

在打开的程序左上角点击 文件, 新建, 源代码.

将以下代码复制到占较大面积的白色输入框中:

#include <stdio.h>

int main() {
    printf("Hello, World!\n");
    return 0;
}

按键盘上的 , 选择一个文件夹保存源代码, 修改文件名后按下 保存, 再按下键盘上的 即可运行.

安装 msys2 配置本地 C 环境并使用 VSCode 编辑器

配置远程服务器 C 环境并使用 VSCode 编辑器

科协将会为有需要的选手提供服务器账号, 服务器上已经预装了 clang 与 gcc.

选手可以在 VSCode 编辑器中通过 ssh 获得服务器开发环境.

注意: 远程服务器 C 环境只在网络访问稳定的情况下可用.

安装 WSL Debian 发行版并使用 VSCode 编辑器

注意: 使用 WSL 要求熟悉 Linux 操作.

安装 CLion 集成开发环境

编程语言介绍

录制文件: record/talk-1.mp4

编程语言(programming language), 是用来定义计算机程序的形式语言. 它是一种被标准化的交流技巧, 用来向计算机发出指令, 能够让程序员准确地定义计算机所需要使用数据, 并精确地定义在不同情况下所应当采取的行动. 1

到今天为止, 已经出现了上千种编程语言, 根据 Stack Overflow 在 2024 年的开发者调查, 前十项最受欢迎的编程语言2为: JS, HTML/CSS, Python, SQL, TS, Bash/Shell, Java, C++, C, PHP.

语言的分类

编程语言可以按照不同的标准进行分类, 以下列出了一些常见的分类或标签.

我们可以说, C 语言是一种编译型, 过程式, 无垃圾回收的语言.

解释型, 编译型

典型的解释型语言为 Python, Python 代码的执行依赖于解释器 (interpreter, 更广泛地说, 需要运行时环境), 而编译型语言如 C 语言, 需要先将源代码针对不同的平台编译成机器码, 然后再在对应的平台上执行.

如何判断一个语言是解释型语言, 还是编译型语言呢? 一个简单的方法是看它是否需要运行时环境. 如果需要, 那么它就是解释型语言, 否则是编译型语言. 例如, Python 语言需要 Python 解释器, Java 语言需要 Java 虚拟机, 它们都是解释型语言.

什么是机器码呢? 机器码 (也称为汇编) 是依赖于平台的低级指令, 直接操作寄存器, 内存等硬件资源. 例如, 下面是一个 C 语言的 add 函数, 它把两个传入参数加起来, 并把结果返回给调用者.

int add(int a, int b) {
    return a + b;
}

在 x86-64 架构上, 上面这个函数编译得到的机器码是

add(int, int):
        lea     eax, [rdi + rsi]
        ret

而在 riscv64 架构上编译得到的机器码是

add(int, int):
        addw    a0, a0, a1
        ret

这直观地说明了不同平台上的机器码是不同的.

不过, 解释型语言也可以通过 AOT (Ahead of Time) 或 JIT (Just In Time) 技术将热点代码编译成机器码, 以提高性能. 而编译型语言也可能通过 JIT 技术以解释型的样子出现 (例如, CERN 开发的 ROOT 数据分析框架包括 Cling C++ 解释器, 它能够交互地运行 C/C++ 代码!).

因此, 也一直有人呼吁废除这种分类.因为编程语言只规定语法语义. 如何让代码可运行, 属于实现的范畴. 因此, 应该说 Python 语言往往被实现为解释型的, 而 C 语言往往被实现为编译型的. 在通常的实现外, 还有很多其他实现方式.

面向对象, 函数式, 过程式

面向对象编程 (OOP, Object-Oriented Programming) 是一种编程范式, 它将数据和操作数据的方法组合在一起, 使得对象可以通过调用方法来操作数据. 例如, Python, C++, Java 是面向对象的语言. 最典型的场景是, 你可以定义一个类, 然后创建这个类的实例, 调用实例的方法.

函数式编程 (FP, Functional Programming) 是另一种编程范式, 它将计算过程看作是数学函数的求值, 避免使用可变状态和副作用, 例如 Haskell, Lisp 是函数式语言.

过程式编程 (Procedural Programming) 是最朴素的编程范式, 它认为程序应该是一系列指令 (这很底层). 如果没有用到上面两种范式的话, 那这种编程语言可能就是过程式语言了.

当我们说某某语言是面向对象语言或者如何如何时, 指的该语言支持使用这种范式, 人们常用这种范式编程. 不代表这种语言只能用这种范式编程.

所以, 面向对象和函数式编程并不是互斥的. 你可以在面向对象语言中使用函数式编程的技巧, 也可以在函数式语言中使用面向对象的技巧. 例如 Rust 语言是一门多范式的语言, 但也有批评者认为 Rust 由于不存在继承, 不是一门真正的面向对象语言.

垃圾回收

垃圾回收 (GC, Garbage Collection) 是一种自动的内存管理技术, 一般实现为定期扫描, 自动标记并释放不再使用的内存, 使得程序员不需要手动管理内存 (显式请求内存分配, 使用完毕后显式释放内存).

垃圾回收会带来相当的性能开销, 但也为程序员减轻了负担.

除了垃圾回收和手动内存管理, 也存在所有权系统 (Ownership System) 这种内存管理方式, 例如 Rust 语言就是使用所有权系统来管理内存的.

可以依靠是否有垃圾回收机制来对语言进行分类. 例如, C/C++ 是没有垃圾回收机制的语言, 需要程序员手动管理内存, 而 Java, Python 是具有垃圾回收机制的语言, 至于 Rust, 在编译器无法推导生命周期时, 需要程序员显式标注生命周期, 以此满足所有权系统的要求.

高级语言, 低级语言

对于什么是高级语言, 什么是低级语言, 人们没有明确的定义. 一般来说, 直接操作硬件资源的语言被称为低级语言, 而更接近人类语言的语言被称为高级语言.

哪种语言适合我?

这个问题的回答取决于你的需求, 以及你熟悉哪些语言.

场景一, 你获得了 CSV 格式记录的数据, 你希望把它转换为 HDF5 格式保存. 在这种情况下, 数据才是最重要的, 处理数据转换的程序只要跑通一次, 你就可以把它扔掉, 那么 Python 生态丰富, 调试方便的特点就很适合.

场景二, 你需要批量为选手推送题目的更新补丁, 因为这个操作需要与 git, ssh 等工具交互, 你需要一个能够方便地调用系统命令的语言. 在这种情况下, Bash 脚本最为适合.

场景三, 你需要快速开发一个高性能的网络服务. Rust 或 Go 可能是多快好省的选择.

场景四, 你需要为单片机编写程序, 或为内核编写驱动. C 语言可能是唯一的选择.

场景五, 你需要做一些数据分析, 需要用到假设检验, 回归分析等统计学库. R, Python 都是不错的选择.

当然, 总是使用你最喜欢的语言也不一定错误, 因为你了解如何 debug. 但一般来说, 选择一种适合当前场景的语言是最佳实践.

C/C++

贝尔实验室的 Dennis Ritchie 于 1969-1973 年间开发了 C 语言, 很长时间以来, C 语言是系统编程和嵌入式开发的首选语言, 并且在其他领域有着广泛的应用. 它足够接近硬件, 又足够高级, 使得程序员可以在不同的层次上编程.

C 语言还是效率最高的编程语言之一. 衡量一个编程语言的效率, 最主要的指标是它的执行速度. C 语言的执行速度快, 内存占用小.

Ranking Programming Languages by Energy Efficiency 以 C 语言作为归一化基准, 比较了数十种编程语言的能耗和执行时间, 我们摘录部分数据如下. 可以看到, C 的速度是 Python 的 70 多倍, Python 需要的资源是 C 的 70 多倍!

语言能耗时间
C1.001.00
Rust1.031.04
C++1.341.56
Java1.981.89
Fortran2.524.20
Go3.232.83
JavaScript4.456.52
TypeScript21.5046.20
Lua45.9882.91
Python75.8871.90

作为一个编译型的语言, C 语言需要先编译成机器码. 编译会经过以下几个步骤 (以 gcc 为例):

               pre processor                   compiler                   assembler                 linker

    hello.c   --------------->      hello.i   --------->    hello.s      ---------->    hello.o    --------->    hello

source program              modified source program     assembly program           relocatable object       executable object
     text                            text                    text                        binary                  binary

在 Linux 系统上, 可以使用 clang 或 gcc 编译器来编译 C 语言程序. 例如, 下面是一个简单的 hello world 程序:

#include <stdio.h>
int main() {
    printf("Hello, World!\n"); // 这个程序会输出 Hello, World! 到终端
    return 0;
}

编译这个程序的命令是

clang hello.c -o hello

gcc hello.c -o hello

这个程序会输出 Hello, World! 到终端.

如果你想快速学习 C 语言, 可以阅读 Learn C in Y Minutes, 配合 C 语言教程 | 菜鸟教程一同学习.

想要深入地了解有关 C 的知识, 推荐阅读 C Primer Plus 第6版 中文版 - C Primer Plus(第六版)中文版.pdf.

总结

读完这里, 你只需要知道并记住以下这些概念, 其他作为拓展的知识与后续学习关系不大.

  1. 机器码是依赖于平台的低级指令, 直接操作硬件资源.
  2. 解释型语言需要运行时环境, 编译型语言需要先编译成机器码.
  3. C 语言是一种高效的编译型语言, 应用广泛, 贴近底层, 需要程序员手动管理内存.

  1. 编程语言 - 维基百科 ↩

  2. Technology | 2024 Stack Overflow Developer Survey ↩

整数的表示与处理

录制文件: record/talk-2.mp4

这一节简单地讨论整数的表示与处理. Programmers 64-bit Calc 是一个很好的在线工具, 可以用来查看有符号整数与无符号整数的二进制表示, 以及它们的位运算.

无符号整数

无符号整数只能表示非负整数. 计算机中无符号整数的表示方法建立了二进制数据与非负整数的双射关系.

我们记一个 ww 位的二进制数为一个长度为 ww 的向量, 最高位在前:

x⃗=(xw−1,xw−2,…,x0),xi=0,1\vec{x}=(x_{w-1},x_{w-2},\ldots,x_0), x_i=0,1

记函数 B2UwB2U_w 将一个二进制数解读为无符号整数:

B2Uw(x⃗)≔∑i=0w−1xi2iB2U_w (\vec{x})\coloneqq \sum_{i=0}^{w-1}x_i 2^i

例如, B2U4(1101)=8+4+0+1=13B2U_4(1101)=8+4+0+1=13.

有符号整数

有符号整数可以表示正整数, 负整数和零. 计算机中有符号整数的表示方法建立了二进制数据与整数的双射关系.

最通用的有符号整数表示方法是补码. 一个 ww 位的补码数的最高位是符号位, 0 表示正数, 1 表示负数. 负数的补码是对应正数的补码取反加一.

记函数 B2TwB2T_w 将一个二进制数解读为有符号整数:

B2Tw(x⃗)≔−xw−12w−1+∑i=0w−2xi2iB2T_w (\vec{x})\coloneqq -x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i 2^i

例如, B2T4(1101)=−8+4+1=−3B2T_4(1101)=-8+4+1=-3.

大小端

在计算机中, 一个多字节的对象在内存中的存储顺序有两种: 大端序 (big-endian, 也称网络序) 和小端序 (little-endian).

例如, 一个 4 字节的整数 0x01234567 在内存中的存储顺序如下:

  • 大端序: 01 23 45 67
  • 小端序: 67 45 23 01

上面用到了 16 进制表示法, 用 0-9 和 A-F 表示 0-15.

正常情况下, 不用关心大小端序, 例如对于整数的位移, 位运算等操作, 编译器会自动处理大小端序的问题.

如果手动查看内存中的数据, 需要注意大小端序的问题. 例如:

#include <stdio.h>
int main() {
    int x = 0x01234567;
    char *p = (char *)&x;
    for (int i = 0; i < sizeof(x); i++) {
        printf("%02x ", p[i]);
    }
    return 0;
}

关于 printf 函数的格式化控制符 %02x, %x 表示输出 16 进制数, %02x 限定不足两位用 0 补齐.

可以参考 Format Specification Syntax | Microsoft Learn 来查看更多的格式化控制符.

逻辑运算

在 C 中, 任何非零的整数都被视为 true, 零被视为 false.

产生 true 或 false 的运算符有 == (等于), != (不等于), > (大于), < (小于), >= (大于等于), <= (小于等于).

逻辑运算常用于条件判断, 对 true 或 falase 进行逻辑运算符的运算符有 ! (非), && (与), || (或).

下面用真值表表示逻辑运算符的运算规则:

xy!xx && yx || y
00100
01101
10001
11011

例子

三目运算符 ?: 可以用来简化条件判断. 例如, 下面的代码用来计算两个数的最小值, 并在最小值为负数时返回 0.

int non_negative_min(int x, int y) {
    int is_negative = x < 0 || y < 0;
    return is_negative ? 0 : x < y ? x : y;
}

位运算

位运算符有 & (与), | (或), ^ (异或), ~ (取反), << (左移), >> (右移).

下面用真值表表示位运算符的运算规则:

xyx & yx | yx ^ y~x
000001
010111
100110
111100

左移和右移是移位运算符, 用来将一个数的二进制表示向左或向右移动若干位.

  • 左移始终将空出的位补 0.
  • 右移有两种方式: 逻辑右移和算术右移.
    • 逻辑右移将空出的位补 0.
    • 算术右移将空出的位填充为原先的最高位.
xx << 2x >> 2 (逻辑右移)x >> 2 (算术右移)
001100000000
110000001111

无符号数的右移必须被实现为逻辑右移, 有符号数的右移在绝大多数平台上被实现为算术右移.

思考题

下面这个 C 函数的功能是什么?

 int f(int x) {
     int a = x | (~x + 1);
     return (a >> 31) + 1;
 }

数组与指针

录制文件: record/talk-2.mp4

数组

数组是多数编程语言中的基本数据类型之一, 用来连续存储相同类型的数据. 数组的元素可以通过下标来访问, 下标从 0 开始.

int a[5] = {1, 2, 3, 4, 5};
struct Point {
    int x;
    int y;
};
struct Point points[3] = {{1, 2}, {3, 4}, {5, 6}};

访问任何一个元素的时间复杂度是 O(1)O(1). 数组的长度是固定的, 不能动态改变.

访问越界的数组元素是未定义行为(undefined behavior, UB), 可能会导致程序崩溃.

int a[5] = {1, 2, 3, 4, 5};
printf("%d\n", a[5]); // 未定义行为

指针

指针是值为内存地址的变量

每一个变量都有一个内存位置, 每一个内存位置都定义了可使用 & 运算符访问的地址, 它表示在虚拟内存中的一个地址.

例如, 变量 a 的地址是 0x7fffbf7f1b4c, 可以通过 &a 来获取 0x7fffbf7f1b4c 这个值.

在 64 位机器中, 指针的大小是 8 字节, 在 32 位机器中, 指针的大小是 4 字节. 指针的大小就是机器的字长.

int 指针的类型声明是 int *, 表示指向 int 类型的指针. 类似地, char 指针的类型声明是 char *, 表示指向 char 类型的指针.

例如, 通过指针加偏移量来访问数组元素:

int a[5] = {1, 2, 3, 4, 5};
int *p = a;               // 定义指针 p, p 指向 a 的第一个元素
printf("%d\n", *p);       // 输出 1
printf("%d\n", *(p + 1)); // 输出 2

通过下标访问数组元素和通过指针访问数组元素是等价的. 可以查看 godbolt 来查看编译器生成的汇编代码.

指针还可以指向指针, 例如, int ** 表示指向 int * 类型的指针.

可以用这样的方式动态创建二维数组:

int m = 3, n = 4;
int **a = (int **)malloc(n * sizeof(int *));
for (int i = 0; i < n; i++) {
    a[i] = (int *)malloc(m * sizeof(int));
}
int *p = a[0];            // p 指向 a 的第一个元素
printf("%d\n", *p);       // 输出 1
printf("%d\n", *(p + 1)); // 输出 2
for (int i = 0; i < n; i++) {
    free(a[i]);
}
free(a);

通过指针修改变量的值

对指针使用 * 解引用操作符, 可以获取和修改修改变量的值, 例如:

#include <stdio.h>
void swap(int *a, int *b) {
    printf("%d %d\n", *a, *b); // 输出 1 2
    int t = *a;
    *a = *b;
    *b = t;
}
int main() {
    int x = 1, y = 2;
    swap(&x, &y);
    printf("%d %d\n", x, y); // 输出 2 1
    return 0;
}

动态内存分配

在 C 语言中, 可以使用 malloc 函数来动态分配内存, 使用 free 函数来释放内存.

它们的原型在 stdlib.h 头文件中, 在典型的 Linux 操作系统中, 具体的实现由 glibc 提供.

#include <stdlib.h>
#include <stdio.h>
int main() {
    int *p = (int *)malloc(5 * sizeof(int));
    for (int i = 0; i < 5; i++) {
        printf("%d\n", p[i]);
    }
    free(p); // 释放内存

    int *q = (int *)calloc(5, sizeof(int)); // 并初始化为 0
    for (int i = 0; i < 5; i++) {
        printf("%d\n", q[i]);
    }
    free(q);
}

malloc 与 calloc 的区别是, malloc 不会初始化内存, calloc 会初始化内存为 0.

此外, malloc 接受的参数是分配的字节数, calloc 接受的参数是分配的元素个数和每个元素的大小.

C++面向对象编程与数据结构简介

C++ 相对于 C , 增加了类 class , 类是定义对象的模板, 与 C 中的结构体只能包含成员变量不同, 类包含有成员变量与成员函数.

以下为一个类的例子(仅做说明使用):

class ClassName{
private:
    // 成员变量
    int capacity;
protected:
    int size;
    int *array;
public:
    // 构造函数
    ClassName(int c = 4)
        :capacity(c), size(0){
        array = new int[c];
    }
    // 析构函数
    ~ClassName(){
        delete [] array;
    }
};

class DerivedClass : public ClassName{
public:
    // 成员函数
    int sum(int n){
        if(n > size) n = size;
        int sum = 0;
        for(int i=0;i<n;i++) sum += array[i];
        return sum;
    }
};

其中:

  • public, private, protected 是访问修饰符: public 表示公共成员, 在类的内部与外部均可访问; private 表示私有成员, 只能在类的内部访问; protected 表示受保护的成员, 在类及其派生类中可以被访问. 如果不作声明, 成员默认为私有.

  • ClassName() 是构造函数, 在创建对象时自动调用, 用于初始化对象. ~ClassName() 是析构函数, 在删除对象时自动调用, 用于清理资源. 这两个函数不需要设置返回类型, 命名需要与类的名称完全匹配, 构造函数可以重载, 析构函数不能传参.

  • DerivedClass 是 ClassName 的派生类, 子类可以继承父类的属性与方法. public 表示子类从父类继承来的成员在子类中的访问级别保持不变; private 表示继承来的成员在子类中变为私有, 不能被子类的对象直接访问; protected 表示继承来的成员在子类中变为受保护的, 不能被子类的对象直接访问, 但可以在子类的派生类中被访问.

C++ 还支持模版类, 可以创建与类型无关的类, 如:

template <typename T> class TemplateClass{
    T data;
};

在声明变量时, 如令类型为 int , 可以按如下格式声明:

TemplateClass<int> tc;

在 C++ 中, 结构体也有所改动, 除访问修饰符外, 其余功能与类基本相同, 以下对一些基本数据结构的介绍均不做封装, 以结构体形式呈现. 以下介绍均使用 C++ 代码(仅供参考, 如有问题请及时指出), 参考邓俊辉老师的讲义, 可以自行修改为 C 的形式使用; 如果要直接使用 C++ 的标准模版库(STL), 请自行查找资料.

向量(vector)

向量是数组的抽象与泛化, 由一组元素按线性次序封装而成, 各元素与 [0,n) 内的秩(rank)一一对应.

以下为一个包含基本的构造、操作与一些算法的 Vector 实现例子:

#include <cstdlib>
#include <ctime>
using namespace std;
using Rank = unsigned int;
#define DEFAULT_CAPACITY 64 //默认容量

template <typename T> struct Vector{
// 成员变量
    Rank size;
    Rank capacity;
    T* elem;

// 辅助函数
    void CopyFrom(T const* A, Rank lo, Rank hi);
    void Expand(); //向量空间不足时扩容
    void Shrink(); //装填因子过小时压缩
    void Swap(Rank a, Rank b); //交换元素

// 构造函数
    Vector(Rank c = DEFAULT_CAPACITY); //默认构造
    Vector(Rank c, Rank s, T v); //容量为c,规模为s,所有元素初始为v;(s<=c)
    Vector(T const *A, Rank n); //数组整体复制
    Vector(T const *A, Rank lo, Rank hi); //数组区间复制
    Vector(Vector<T> const &V); //向量整体复制
    Vector(Vector<T> const &V, Rank lo, Rank hi); //向量区间复制

// 析构函数
    ~Vector(); //释放内部空间

// 插入删除函数
    Rank Insert(Rank r, T const &e); //插入元素//返回插入元素的位置
    Rank Insert(T const &e); //默认作为末元素插入//返回插入元素的位置
    Rank Remove(Rank lo, Rank hi); //删除秩在区间[lo, hi)之内的元素//返回被删元素的数目
    T Remove(Rank r); //删除秩为r的元素//返回被删元素

// 查找函数
    Rank BinSearch(T const &e, Rank lo, Rank hi); //有序向量二分查找算法

// 排序函数
    void BubbleSort(Rank lo, Rank hi); //起泡排序算法
    void Merge(Rank lo, Rank mi, Rank hi, T *former); //归并算法
    void MergeSort(Rank lo, Rank hi, T *former); //归并排序算法
    void MergeSort(Rank lo, Rank hi); //归并排序调用接口
    Rank Partition(Rank lo, Rank hi); //轴点构造算法
    void QuickSort(Rank lo, Rank hi); //快速排序算法
};

template <typename T> void Vector<T>::CopyFrom(T const *A, Rank lo, Rank hi){
    capacity = (hi-lo)*2;
    if(capacity < DEFAULT_CAPACITY) capacity = DEFAULT_CAPACITY; 
    elem = new T[capacity];
    for(size=0; lo<hi; size++,lo++) elem[size] = A[lo];
}
template <typename T> void Vector<T>::Expand(){ 
    if(size < capacity) return;
    T* oldelem = elem;
    CopyFrom(oldelem, 0 ,capacity);
    delete [] oldelem;
}
template <typename T> void Vector<T>::Shrink(){
    if(capacity < DEFAULT_CAPACITY<<1) return;
    if(size<<2 > capacity) return;
    T* oldelem = elem;
    capacity >>= 1;
    elem = new T[capacity];
    for(Rank i=0;i<size;i++) elem[i] = oldelem[i];
    delete [] oldelem;
}
template <typename T> void Vector<T>::Swap(Rank a, Rank b){
    T temp=elem[a];
    elem[a]=elem[b];
    elem[b]=temp;
}

template <typename T> Vector<T>::Vector(Rank c){
    size = 0;
    capacity = c;
    elem = new T[capacity];
}
template <typename T> Vector<T>::Vector(Rank c, Rank s, T v){
    capacity = c;
    elem = new T[capacity];
    for(size=0;size<s;size++) elem[size] = v;
}
template <typename T> Vector<T>::Vector(T const* A, Rank n){
    CopyFrom(A, 0, n);
}
template <typename T> Vector<T>::Vector(T const *A, Rank lo, Rank hi){
    CopyFrom(A, lo, hi);
}
template <typename T> Vector<T>::Vector(Vector<T> const &V){
    CopyFrom(V.elem, 0, V.size);
}
template <typename T> Vector<T>::Vector(Vector<T> const &V, Rank lo, Rank hi){
    CopyFrom(V.elem, lo, hi);
}

template <typename T> Vector<T>::~Vector(){
    delete [] elem;
}

template <typename T> Rank Vector<T>::Insert(Rank r, T const &e){
    Expand();
    for(Rank i=size;r<i;i--) elem[i] = elem[i-1];
    elem[r] = e;
    size++;
    return r;
}
template <typename T> Rank Vector<T>::Insert(T const &e){
    return Insert(size, e);
}
template <typename T> Rank Vector<T>::Remove(Rank lo, Rank hi){
    if(lo == hi) return 0;
    for(; hi<size; lo++,hi++) elem[lo] = elem[hi];
    size = lo;
    Shrink(); 
    return hi-lo;
}
template <typename T> T Vector<T>::Remove(Rank r){
    T e = elem[r];
    Remove(r, r+1);
    return e;
}

template <typename T> Rank Vector<T>::BinSearch(T const &e, Rank lo, Rank hi){
    while(lo < hi){
        Rank mi = (lo+hi)>>1;
        if(e < elem[mi]) hi = mi;
        else lo = mi+1;
    }
    return lo-1;
}

template <typename T> void Vector<T>::BubbleSort(Rank lo, Rank hi){
    for(Rank last; lo<hi; hi=last){
        last = lo;
        for(Rank i=lo+1; i<hi; i++){
            if(elem[i-1] > elem[i]){
                Swap(i-1, i);
                last = i;
            }
        }
    } 
}
template <typename T> void Vector<T>::Merge(Rank lo, Rank mi, Rank hi, T *former){
    Rank lf = mi-lo, ll = hi-mi;
    T *all = elem+lo, *latter = elem+mi;
    for (Rank i=0;i<lf;i++) former[i] = all[i];
    Rank i=0,j=0,k=0;
    while(j<lf && k<ll){
        if(former[j] <= latter[k]){
            all[i] = former[j];
            i++;
            j++;
        }
        else{
            all[i] = latter[k];
            i++;
            k++;
        }
    }
    while(j<lf){
        all[i] = former[j];
        i++;
        j++;
    }
}
template <typename T> void Vector<T>::MergeSort(Rank lo, Rank hi, T *former){
    if(hi-lo < 2) return;
    Rank mi = (lo+hi)>>1;
    MergeSort(lo, mi, former);
    MergeSort(mi, hi, former);
    Merge(lo, mi, hi, former);
}
template <typename T> void Vector<T>::MergeSort(Rank lo, Rank hi){
    T* former = new T[((hi-lo)>>1) + 1];
    MergeSort(lo, hi, former);
    delete [] former;
}
template <typename T> Rank Vector<T>::Partition(Rank lo, Rank hi){
    srand(time(0));
    Swap(lo, lo+rand()%(hi-lo));
    T pivot = elem[lo];
    while(lo<hi){
        do hi--;
        while((lo<hi) && (pivot<elem[hi]));
        if(lo<hi) elem[lo] = elem[hi];
        do lo++;
        while((lo<hi) && (elem[lo]<pivot));
        if(lo<hi) elem[hi] = elem[lo];
    }
    elem[hi] = pivot;
    return hi;
}
template <typename T> void Vector<T>::QuickSort(Rank lo, Rank hi){
    if(hi-lo < 2) return;
    Rank mi = Partition(lo, hi);
    QuickSort(lo, mi);
    QuickSort(mi+1, hi);
}

列表(list)

静态与动态的操作与存储

根据是否修改数据结构, 所有操作大致分为两类方式:

  • 静态: 仅读取, 数据结构的内容与组成一般不变 (如search);

  • 动态: 需写入, 数据结构的局部或整体将改变 (如sort).

与操作方式相对应地, 数据元素的存储与组织方式也分为两种:

  • 静态: 数据空间整体创建或销毁. 数据元素的物理次序与其逻辑次序严格一致; 可支持高效的静态操作. (比如向量, 元素的物理地址与其逻辑次序线性对应)

  • 动态: 为各数据元素动态地分配和回收的物理空间. 相邻元素记录彼此的物理地址, 在逻辑上形成一个整体; 可支持高效的动态操作.

列表介绍

列表是采用动态储存策略的典型结构, 其中的元素称作节点(node), 通过指针或引用彼此联接, 在逻辑上构成一个线性序列.

列表的相邻节点彼此互称前驱(predecessor)或后继(successor), 没有前驱/后继的节点称作首(first)/末(last)节点. 由此形成下列双向列表结构:(一个[]代表一个节点)

[|first|s] <---> [p|B|s] <---> [p|C|s] <---> ... <---> [p|Y|s] <---> [p|last|]

如此, 列表中各元素的物理地址将不再决定于逻辑次序, 不同于向量的循秩访问 (call by rank), 而是采用循位置访问 (call by position): 利用节点之间的相互引用, 找到特定的节点.

列表代码

首先给出列表节点的代码 ListNode.h, 每个节点包含有 3 个成员变量: 数值、前驱、后继.

#include <iostream>
using Rank = unsigned int;

template <typename T> struct ListNode;
template <typename T> using ListNodePosi = ListNode<T>*; //列表节点位置

template <typename T> struct ListNode{ //列表节点模板类(以双向链表形式实现)
// 成员
    T data; //数值
    ListNodePosi<T> pred, succ; //前驱、后继

// 构造函数
    ListNode(){} //针对head和tail的构造
    ListNode(T const &e, ListNodePosi<T> p = NULL, ListNodePosi<T> s = NULL)
        :data(e), pred(p), succ(s){} //默认构造器(类T须定义复制方法)

// 操作接口
    ListNodePosi<T> InsertPred(T const &e){
        ListNodePosi<T> x = new ListNode(e, pred, this);
        pred->succ = x;
        pred = x;
        return x;
    } //紧靠当前节点之前插入新节点
    ListNodePosi<T> InsertSucc(T const &e){
        ListNodePosi<T> x = new ListNode(e, this, succ);
        succ->pred = x;
        succ = x;
        return x;
    } //紧随当前节点之后插入新节点
};

为了便于列表的构造与操作, 在首节点之前引入哨兵头节点(head), 在末节点之后引入哨兵尾结点(tail), 这样所有列表内部的节点都拥有了前驱与后继. 此时, 对于有n个内部节点的列表, 可以将头、首、末、尾节点的秩视为 -1、0、n-1、n .

以下为一个包含基本的构造与操作的 List 实现例子:

#include "ListNode.h"

template <typename T> struct List{ //列表模板类
// 成员变量
    Rank size; //规模
    ListNodePosi<T> head, tail; //头哨兵、尾哨兵

// 辅助函数
    void Init(); //列表创建时的初始化
    void CopyNodes(ListNodePosi<T> p, Rank n); //复制列表中自位置p起的n项
    Rank Clear(); //清除所有节点

// 构造函数
    List(); //默认
    List(List<T> const &L); //整体复制列表L
    List(List<T> const &L, Rank r, Rank n); //复制列表L中自第r项起的n项
    List(ListNodePosi<T> p, Rank n); //复制列表中自位置p起的n项

// 析构函数
    ~List(); //释放(包含头、尾哨兵在内的)所有节点

// 运算符重载
    ListNodePosi<T> operator[](Rank r) const; //重载,支持循秩访问（效率低）

// 插入删除函数
    ListNodePosi<T> InsertFirst(T const &e); //将e当作首节点插入
    ListNodePosi<T> InsertLast(T const &e); //将e当作末节点插入
    ListNodePosi<T> Insert(ListNodePosi<T> p, T const &e); //将e当作p的后继插入
    ListNodePosi<T> Insert(T const &e, ListNodePosi<T> p); //将e当作p的前驱插入
    T Remove(ListNodePosi<T> p); //删除合法位置p处的节点,返回被删除节点

// 遍历
    void Traverse(void (*visit)(T&)); //依次实施visit操作（函数指针）
    template <typename VST> void Traverse(VST &visit); //依次实施visit操作（函数对象）
};

template <typename T> void List<T>::Init(){
    head = new ListNode<T>;
    tail = new ListNode<T>;
    head->succ = tail;
    head->pred = NULL;
    tail->pred = head;
    tail->succ = NULL;
    size = 0;
}
template <typename T> void List<T>::CopyNodes(ListNodePosi<T> p, Rank n){ 
    //请确保p合法，且至少有n-1个真后继
    Init();
    for(; n>0; n--){
        InsertLast(p->data);
        p = p->succ;
    }
}
template <typename T> Rank List<T>::Clear(){
   Rank oldsize = size;
   while(size > 0) Remove(head->succ);
   return oldsize;
}

template <typename T> List<T>::List(){
    Init();
}
template <typename T> List<T>::List(List<T> const &L){
    CopyNodes(L.head->succ, L.size);
}
template <typename T> List<T>::List(List<T> const &L, Rank r, Rank n){
    //请确保 r+n <= L.size
    ListNodePosi<T> p = L.head->succ;
    for(; r>0; r--) p = p->succ;
    CopyNodes(p, n);
}
template <typename T> List<T>::List(ListNodePosi<T> p, Rank n){
    CopyNodes(p, n);
}

template <typename T> List<T>::~List(){
    Clear();
    delete head;
    delete tail;
}

template <typename T> ListNodePosi<T> List<T>::operator[](Rank r) const{
    //请确保 0 <= r < size
    ListNodePosi<T> p = head->succ;
    for(; r>0; r--) p = p->succ;
    return p;
}

template <typename T> ListNodePosi<T> List<T>::InsertFirst(T const &e){
    size++;
    return head->InsertSucc(e);
}
template <typename T> ListNodePosi<T> List<T>::InsertLast(T const &e){
    size++;
    return tail->InsertPred(e);
}
template <typename T> ListNodePosi<T> List<T>::Insert(ListNodePosi<T> p, T const &e){
    size++;
    return p->InsertSucc(e);
}
template <typename T> ListNodePosi<T> List<T>::Insert(T const &e, ListNodePosi<T> p){
    size++;
    return p->InsertPred(e);
}
template <typename T> T List<T>::Remove(ListNodePosi<T> p){
    //请确保p合法
    T e = p->data;
    p->pred->succ = p->succ;
    p->succ->pred = p->pred;
    delete p;
    size--;
    return e;
}

template <typename T> void List<T>::Traverse(void (*visit)(T&)){
    for(ListNodePosi<T> p=head->succ; p!=tail; p=p->succ) visit(p->data);
}
template <typename T> template <typename VST> void List<T>::Traverse(VST &visit){
    for(ListNodePosi<T> p=head->succ; p!=tail; p=p->succ) visit(p->data);
}

栈与队列

栈(stack)

栈是受限的线性序列:

  • 只能在栈顶(top)插入和删除;

  • 栈底(bottom)为盲端.

其包含 3 个基本接口:

  • 入栈 Push(): 将元素插入栈顶;

  • 出栈 Pop(): 将栈顶元素取出;

  • 查顶 Top(): 查询栈顶元素.

栈的实现不难, 以下分别给出根据向量与列表派生得到的栈的例子:

#include "Vector.h"

template <typename T> struct Stack : Vector<T>{
    //入栈: 等效于将新元素作为向量的末元素插入
    void Push(T const& e){
        Vector<T>::Insert(e);
    }
    //出栈: 等效于删除向量的末元素
    T Pop(){
        return Vector<T>::Remove(Vector<T>::size - 1);
    }
    //查顶: 直接返回向量的末元素
    T& Top(){
        return Vector<T>::elem[Vector<T>::size - 1];
    }
};

#include "List.h"

template <typename T> struct Stack : List<T>{
    //入栈: 等效于将新元素作为列表的末元素插入
    void Push(T const& e){
        List<T>::InsertLast(e);
    }
    //出栈: 等效于删除列表的末元素
    T Pop(){
        return List<T>::Remove(List<T>::tail->pred);
    }
    //查顶: 直接返回列表的末元素
    T& Top(){
        return List<T>::tail->pred->data;
    } 
};

队列(queue)

队列与栈类似, 也是受限的线性序列:

  • 只能在队尾插入(查询): Enqueue() / Rear()

  • 只能在队首删除(查询): Dequeue() / Front()

队列的实现与栈类似, 以下给出根据列表派生得到的队列的例子:

#include "List.h"

template <typename T> struct Queue : List<T>{
    //入队: 尾部插入
    void Enqueue(T const& e){
        List<T>::InsertLast(e);
    }
    //出队: 首部删除
    T Dequeue(){
        return List<T>::Remove(List<T>::head->succ);
    }
    //队首
    T& Front(){
        return List<T>::head->succ->data;
    }
};

树(tree)

树介绍

树是一种半线性、具有层次的数据结构, 由一系列相联的节点组成, 每个节点除了存储本身的信息外, 还有着指向其父节点(parent)与子节点(child)的指针. 除根节点(root)外, 每个节点拥有一个父亲, 所有节点都拥有非负个孩子(没有孩子的节点叫做叶节点), 一个节点的孩子互为兄弟, 从根节点向下延伸成一个近似于三角形的树状. 将一个节点及其所有后代取出, 即为以该节点为根的一颗子树, 其中的节点数叫做该子树的规模.

注: 这里不介绍与平衡树有关的概念, 也不做时间复杂度的分析, 故略去高度与深度的概念, 可自行了解.

二叉树(binary tree)

二叉树是指所有节点的孩子数目不超过 2 , 此时可以用左右来区分两个孩子, 即左孩子(lc)、右孩子(rc). 引入外部节点(即空节点NULL)后, 可以使得原有节点的孩子数目都为 2 , 便于理解与分析.

首先给出二叉数节点模版类的代码 BinNode.h :

#include <iostream>
template <typename T> struct BinNode;
template <typename T> using BinNodePosi = BinNode<T>*; //节点位置
using Rank = unsigned int;

template <typename T> struct BinNode{ //二叉树节点模板类
// 成员变量
   T data; //数值
   BinNodePosi<T> parent, lc, rc; //父节点及左右孩子

// 构造函数
    BinNode()
        :parent(NULL), lc(NULL), rc(NULL){}
    BinNode(T e, BinNodePosi<T> p = NULL, BinNodePosi<T> l = NULL, BinNodePosi<T> r = NULL)
        :data(e), parent(p), lc(l), rc(r){
            if(lc) lc->parent = this;
            if(rc) rc->parent = this;
        }

// 操作接口
    BinNodePosi<T> InsertLc(T const& e){ //插入左孩子
        return lc = new BinNode<T>(e, this);
    }
    BinNodePosi<T> InsertRc(T const& e){ //插入右孩子
        return rc = new BinNode<T>(e, this);
    }
    void AttachLc(BinNodePosi<T> x){ //接入左子树
        lc = x;
        if(x) x->parent = this;
    }
    void AttachRc(BinNodePosi<T> x){ //接入右子树
        rc = x;
        if(x) x->parent = this;
    }
    bool IsLeftChild(){ //判断当前节点是否为左孩子
        if(parent){
            if(this == parent->lc) return true;
        }
        return false;
    }
    bool IsRightChild(){ //判断当前节点是否为右孩子
        if(parent){
            if(this == parent->rc) return true;
        }
        return false;
    }
    BinNodePosi<T> Succ(){ //取当前节点的直接后继
        BinNodePosi<T> s = this;
        if(rc){
            s = rc;
            while(s->lc) s = s->lc;
        }
        else{
            while(s->IsRightChild()) s = s->parent;
            s = s->parent;
        }
        return s;
    }
};

以下为一个包含基本的构造与操作的 BinTree 实现例子:

#include "BinNode.h" //引入二叉树节点类

template <typename T> struct BinTree { //二叉树模板类
// 成员变量
    BinNodePosi<T> root; //根节点

// 构造函数
    BinTree() :root(NULL){} //默认构造方法
    BinTree(BinTree<T> const& s); //复制方法

// 析构函数
    ~BinTree();

// 插入删除函数
    BinNodePosi<T> Insert(T const& e); //插入根节点
    BinNodePosi<T> Insert(T const& e, BinNodePosi<T> x); //插入左孩子
    BinNodePosi<T> Insert(BinNodePosi<T> x, T const& e); //插入右孩子
    BinNodePosi<T> Attach(BinTree<T> S, BinNodePosi<T> x); //接入左子树
    BinNodePosi<T> Attach(BinNodePosi<T> x, BinTree<T> S); //接入右子树
    Rank Remove(BinNodePosi<T> x); //子树删除
    BinTree<T>* Secede(BinNodePosi<T> x); //子树分离
};

// 将以s为根的子树的节点复制,得到的子树的根以p为父亲
template <typename T> BinNodePosi<T> NodeCopy(BinNodePosi<T> p, BinNodePosi<T> s){
    if(!s) return NULL;
    BinNodePosi<T> t = new BinNode<T>(s->data, p, NULL, NULL);
    t->lc = NodeCopy(t, s->lc);
    t->rc = NodeCopy(t, s->rc);
    return t;
}
template <typename T> BinTree<T>::BinTree(BinTree<T> const& s){
    root = NodeCopy<T>(NULL, s.root);
}

template <typename T> BinTree<T>::~BinTree(){
    if(!root) Remove(root);
}

template <typename T> BinNodePosi<T> BinTree<T>::Insert(T const& e){
    return root = new BinNode<T>(e);
}
template <typename T> BinNodePosi<T> BinTree<T>::Insert(T const& e, BinNodePosi<T> x){
    x->InsertLc(e);
    return x->lc;
}
template <typename T> BinNodePosi<T> BinTree<T>::Insert(BinNodePosi<T> x, T const& e){
    x->insertRc(e);
    return x->rc;
}
template <typename T> BinNodePosi<T> BinTree<T>::Attach(BinTree<T> S, BinNodePosi<T> x){
    //请确保 x->lc == NULL
    if(x->lc = S.root) x->lc->parent = x;
    S.root = NULL; //释放原树
    return x; 
}
template <typename T> BinNodePosi<T> BinTree<T>::Attach(BinNodePosi<T> x, BinTree<T> S){
    //请确保 x->rc == NULL
    if(x->rc = S.root) x->rc->parent = x;
    S.root = NULL; //释放原树
    return x;
}
//删除二叉树中位置x处的节点及其后代，返回被删除子树的规模
template <typename T> static Rank RemoveAt(BinNodePosi<T> x){
    //请确保 x为二叉树中的合法位置
    if(!x) return 0;
    Rank n = 1 + RemoveAt(x->lc) + RemoveAt(x->rc);
    delete x;
    return n;
}
template <typename T> Rank BinTree<T>::Remove(BinNodePosi<T> x){
    //请确保 x为二叉树中的合法位置
    if(x->IsLeftChild()) x->parent->lc = NULL;
    else if(x->IsRightChild()) x->parent->rc = NULL;
    else root = NULL;
    Rank n = RemoveAt( x );
    return n;
}
template <typename T> BinTree<T>* BinTree<T>::Secede(BinNodePosi<T> x){
    //请确保 x为二叉树中的合法位置
    if(x->IsLeftChild()) x->parent->lc = NULL;
    else if(x->IsRightChild()) x->parent->rc = NULL;
    else root = NULL;
    BinTree<T>* S = new BinTree<T>;
    S->root = x;
    x->parent = NULL;
    return S;
}

二叉搜索树(binary search tree)

在二叉树中, 如果规定任一节点的数值均不小于其左后代, 均不大于其右后代 (等效于均不小于其左孩子, 均不大于其右孩子; 也可以做相反的规定), 此时的二叉树便具有了顺序性, 叫做二叉搜索树. 为了简化, 假定所有节点的数值都不相等.

二叉搜索树可由二叉树派生得到, 增加了对于数值进行查找、插入、删除的 3 个函数. 二叉搜索树的查找 Search() 与向量的二分查找原理类似, 从根节点开始, 在每个节点处判断是否命中, 若未命中则根据相对大小深入左/右子树继续查找; 为了插入与删除操作在查找操作的基础上正确进行, 在每次调用查找函数 Search() 后, 用 hot 记录最终命中节点的父亲(特别的, 若命中根节点, 则 hot = NULL , 若未命中节点, 则 hot 为最后一次到达的有效节点). 二叉搜索树的插入 Insert() 和删除 Remove() 大体上与列表相同, 特别的是, 当删除的节点有 2 个真孩子时, 无法直接重建链接关系, 需要找到该节点的直接后继(即所有数值大于该节点数值的节点中最小的那一个), 其必然只有 1 个真孩子, 可将其与原待删除节点交换后删除.

以下为一个包含基本操作的 BST 实现例子:

#include "BinTree.h"

template <typename T> struct BST : BinTree<T>{ //二叉搜索树模板类
// "命中"节点的父亲
    BinNodePosi<T> hot;
// 查找
    BinNodePosi<T>& Search(const T& e){
        if(!BinTree<T>::root || e==BinTree<T>::root->data){
            hot = NULL;
            return BinTree<T>::root;
        }
        BinNodePosi<T>& v = BinTree<T>::root;
        for(hot=BinTree<T>::root; ; ){
            if(e < hot->data) v = hot->lc;
            else v = hot->rc;
            if(!v || e==v->data) return v;
            hot = v;
        }
    }
// 插入
    BinNodePosi<T> Insert(const T& e){
        BinNodePosi<T>& x = Search(e);
        if(x) return x; //节点已存在,无需重复插入
        x = new BinNode<T>(e, hot);
        return x;
    } //无论e是否存在于原树中, 返回时总有 x->data == e
// 删除
    bool Remove(const T& e){
        BinNodePosi<T>& x = Search(e);
        if(!x) return false; //节点不存在,不能删除
        BinNodePosi<T> w = x; //实际被删除节点
        BinNodePosi<T> succ = NULL; //实际被删除节点的接替者
        if( !x->lc ){
            x = x->rc;
            succ = x;
        }
        else if( !x->rc ){
            x = x->lc;
            succ = x;
        }
        else{ //若左右子树均存在,则选择x的直接后继作为实际被摘除节点
            w = w->Succ();
            x->data = w->data;
            succ = w->rc;
            if(w->IsRightChild()) w->parent->rc = succ;
            else w->parent->lc = succ;
        }
        hot = w->parent;
        if(succ) succ->parent = hot;
        delete w;
        return true;
    }
};

多叉树

若节点的孩子数目可以大于 2 , 则这棵树为多叉树. 多叉树可直接通过将节点的孩子指针存入一个列表来实现, 若已知每个节点孩子数目上限(不是很大时, 如三叉树), 也可存入数组中; 多叉树也可以使用长子-兄弟表示法转化为二叉树: 对于一个节点, 把它的长子记为其左孩子, 将最大的弟弟记为其右孩子(这样, 次子就是长子的右孩子, 以此类推).

散列表(hash table)

散列是一种循对象访问的数据结构, 一个散列由若干桶组成, 每个桶中可存放一个词条(Entry), 每个词条包含有关键码(key)与数值(value)两个成员变量(也叫键值对).

以下为词条模版类的一个实现方式:

template <typename K, typename V> struct Entry{ //词条模板类
    K key; //关键码
    V value; //数值
    Entry(K k = K(), V v = V()) :key(k), value(v){}; //默认构造方法
    Entry(Entry<K, V> const& e) :key(e.key), value(e.value){}; //基于克隆的构造方法
    // 可通过重载运算符自行补充判等器与比较器
};

通过散列表, 可以在 O(1) 的时间由关键码访问数值, 这需要将词条的关键码通过散列函数 hash() 映射到 [0,M) 这一区间的整数中, 其中 M 为桶总数. 当数据集已知且固定时, 理论上可以实现 n 个词条从任意互异关键码映射到 [0,n) 的双射散列函数, 从而构造完美散列; 但对于未知的或动态变化的数据集, 无法实现完美散列. 记 λ = N/M 为装填因子, N 为词条数, λ 越大, 空间利用率越高, 但出现冲突(不同关键码具有相同的 hash 值)的情况会越严重, 故为了实现正确查找, 同时保证较高的空间利用率, 需要完成以下 2 个基本任务:

  • 精心设计散列表及散列函数 hash() , 尽可能降低冲突的概率;

  • 制定可行的预案, 以便在发生冲突时, 能够尽快予以排解.

对于散列函数的设计, 常用的方法为除余法, 即 hash(key) = key % M, 且桶总数 M 应取为素数; 更进一步地, 可以使用MAD法(Multiply-Add-Divide), 即 hash(key) = (a * key + b) % M, 其中 M 为素数, a > 1, b > 0, a % M != 0. 特别的, 如果词条的 value 均为字符串, 设字符集中字符总数为 S, 考虑将字符串转化为 S 进制的整数作为 key, 但碍于存储限制, key 的值可能超出 int 甚至 long long int 的范围, 可以考虑用 key 计算 hash 值后(注: (S×A+B)mod  M=(S×(Amod  M)+B)mod  M(S\times A+B)\mod M=(S\times(A\mod M)+B)\mod M ) , 再通过进一步比较字符串的内容是否相同来判定词条是否相同, 而真实的 key 值无需记录.

对于冲突的排解, 有开放散列与封闭散列两种解决策略. 开放散列每个桶中可容纳词条数不限, 每个桶中可进入的词条类型有限制, 其实现原理较为简单: 每个桶拥有一个列表, 存放对应的一组 hash 值相同的词条. 封闭散列每个桶中只可容纳 1 个词条, 但每个桶中可进入的词条类型没有限制, 其实现原理相对复杂: 对于每一组 hash 值相同的词条, 都事先约定了若干备用桶, 依次串接成试探链, 存放时沿试探链查找到第一个空桶时放入, 读取时沿试探链查找词条, 至第一个未曾存放过词条的桶时查找失败. 对于试探链的选取, 可以采用最简单的线性试探: 试探的桶序号每次 +1, 即 ri(key)=(hash(key)+i)mod  M,i=0,1,2,3,…r_i(key)=(\text{hash}(key)+i)\mod M,\kern6pt i=0,1,2,3,\dots , 这种试探在桶存满时需扩容, 为了保证试探次数的期望 E<2E<2 , 建议装填因子 λ<0.5\lambda<0.5 ; 为了避免出现连续的失败试探, 可以采用平方试探: ri(key)=(hash(key)+i2)mod  M,i=0,1,2,3,…r_i(key)=(\text{hash}(key)+i^2)\mod M,\kern6pt i=0,1,2,3,\dots , 这种试探必须保证装填因子 λ<0.5\lambda<0.5, 避免出现有空桶但找不到的情况; 进一步的, 为了增大空间利用率, 可以采用双向平方试探: ri(key)=(hash(key)+(−1)i+1⋅(⌈i/2⌉)2)mod  M,i=0,1,2,3,…r_i(key)=(\text{hash}(key)+(-1)^{i+1}\cdot (\left\lceil i/2\right\rceil)^2)\mod M,\kern6pt i=0,1,2,3,\dots , 这种试探的素数 MM 需要保证 M=4⋅k+3M=4\cdot k+3 , 此时必然能保证所有桶都被试探链前 MM 项包含.

以下为一个包含基本的构造、操作的 HashTable 实现例子:

#include "Entry.h"
#include <iostream>
using Rank = unsigned int;
#define DEFAULT_CAPACITY 7

// 查找不小于l的最小的4k+3素数
Rank Prime(Rank l){
    if(l > 0x7FFFFFFF) return l; //初始时l过大,直接返回l//一般不应出现
    Rank p = l;
    p += 3 - (p%4);
    bool isprime = 1;
    for(Rank h=1; ; p+=4){
        isprime = 1;
        while(h*h < p) h++;
        for(Rank i=3; i<h; i++){
            if(p%i == 0){
                isprime = 0;
                break;
            }
        }
        if(isprime) return p;
    }
}

template <typename K, typename V> struct HashTable{
// 成员变量
    Entry<K, V>** ht; //桶数组,存放词条指针
    bool* removed; //懒惰删除标记(可改为使用位图)//C++布尔数组内存管理有时会出现问题,可改为int
    Rank M, N, S; //桶的总数、词条的数目、使用过的桶数

// 散列函数(请自行选择hash函数,这里给出一个示例)
    Rank hash(K k){return ((Rank)k)%M;}

// 构造函数
    HashTable(Rank c = DEFAULT_CAPACITY); //创建一个容量不小于c的散列表

// 析构函数
    ~HashTable(); //释放桶数组及其中各(非空)元素所指向的词条

// 试探函数
    Rank Probe4Hit(const K& k); //沿关键码k对应的试探链,找到词条匹配的桶
    Rank Probe4Free(const K& k); //沿关键码k对应的试探链,找到首个可用空桶

// 扩容/减容函数
    void Rehash(); //重散列算法: 扩充桶数组,保证装填因子在警戒线以下

// 插入删除读取函数
    bool Put(K k, V v); //插入(禁止词条相等,故可能失败)
    bool Remove(K k); //删除
    V* Get(K k); //读取
};

template <typename K, typename V> HashTable<K,V>::HashTable(Rank c){
    M = Prime(c); 
    N = 0;
    S = 0;
    ht = new Entry<K, V>*[M];
    for(Rank i=0;i<M;i++) ht[i] = NULL;
    removed = new bool[M];
    for(Rank i=0;i<M;i++) removed[i] = false;
}

template <typename K, typename V> HashTable<K,V>::~HashTable(){
    for(Rank i=0;i<M;i++){
        if(ht[i]) delete ht[i];
    }
    delete [] ht;
    delete [] removed;
}

template <typename K, typename V> Rank HashTable<K, V>::Probe4Hit(const K& k){
    //采用双向平方试探
    for(int r=k,i=2; ; i++){
        if((ht[r] && k==ht[r]->key) || (!ht[r] && !removed[r])) return r;
        if(i%2==0) r = k + (i>>1)*(i>>1);
        else r = k - (i>>1)*(i>>1);
        while(r < 0) r += M;
        r %= M;
    }
}
template <typename K, typename V> Rank HashTable<K, V>::Probe4Free(const K& k){
    //采用双向平方试探
    for(int r=k,i=2; ; i++){
        if(!ht[r]) return r;
        if(i%2==0) r = k + (i>>1)*(i>>1);
        else r = k - (i>>1)*(i>>1);
        while(r < 0) r += M;
        r %= M;
    }
}

template <typename K, typename V> void HashTable<K, V>::Rehash(){
    Rank oldM = M;
    Entry<K, V>** oldht = ht;
    M = Prime(4*N);
    N = 0;
    S = 0;
    ht = new Entry<K, V>*[M];
    for(Rank i=0;i<M;i++) ht[i] = NULL;
    delete removed;
    removed = new bool[M];
    for(Rank i=0;i<M;i++) removed[i] = false;
    for(Rank i=0;i<oldM;i++){
        if(oldht[i]) Put(oldht[i]->key, oldht[i]->value);
    }
    delete [] oldht;
}

template <typename K, typename V> bool HashTable<K, V>::Put(K k, V v){
    if( ht[Probe4Hit(k)] ) return false; //忽略相等元素
    Rank r = Probe4Free(k); 
    ht[r] = new Entry<K, V>(k, v);
    N++;
    if(removed[r]) removed[r] = false;
    else S++;
    if(2*S > M) Rehash(); //若装填因子高于50%,重散列
    return true;
}
template <typename K, typename V> bool HashTable<K, V>::Remove(K k){
    Rank r = Probe4Hit(k);
    if( !ht[r] ) return false; //确认目标词条确实存在
    delete ht[r];
    ht[r] = NULL;
    N--;
    removed[r] = true;
    return true;
}
template <typename K, typename V> V* HashTable<K, V>::Get(K k){
    Rank r = Probe4Hit(k);
    if(ht[r]) return &(ht[r]->value);
    else return NULL;
}

常见问题解答

哪些提问可以得到帮助

  • 为什么我的提交答案错误/时间超限?:

    为了比赛公平, 工作人员在确定测试点数据没有问题后, 只能告诉选手, 评测正常, 请继续尝试. 并且, 工作人员不能提供比题目描述页面更详细的提示.

  • 我的提交答案错误, 是因为卡在了输出格式上吗?:

    同上, 工作人员确认后, 只能告知是或不是, 不能进行其他提示.

在本地可以运行, 但提交后有运行错误

请以评测机环境为准, 本地环境与评测机环境往往并不相同. 例如选手使用 Visual Studio, 而 OJ 所用的编译器是 gcc.

一道题目得到多少分视为通过

初赛对此的规定是, 得到 100 分(通过所有测试点)视为通过.

如何提问

在提问前, 建议大家阅读这篇文章 X-Y Problem. 这里总结其中的核心意思:

在寻求别人帮助的时候, 最好把我们想解决的问题和整个事情的来龙去脉说清楚.

推荐按照这样的模板来提问:

  • 问题描述: 简要说明你遇到的问题 (Y 问题).
  • 背景信息: 描述问题的来龙去脉 (X 问题).
  • 尝试过的解决方法: 列出你已经尝试过的解决方案及结果.
  • 期望的帮助: 明确说明你希望得到什么样的帮助.

注意事项

  • 不要拍屏, 除非这是唯一的办法, 或者问题是关于屏幕的. 同样地, 不要用截图代替文本.
    • 图片无法被搜索, 同时传输和查看的成本远高于文本.
    • 推荐使用 pastebin 来分享报错, 代码, 日志等等一切文本信息.
  • 不要称呼别人为大佬, 大神等等. 对等地, 不要称呼自己是蒟蒻, 小白等等.
    • 这会让谦逊的同学不愿回答你的问题.
    • 闻道有先后, 大家都是从小白开始的.

反馈问题

欢迎在 Issues 中提问并反馈问题.

此外, 也可以通过邮件或微信联系 adamanteye 以便非公开地反馈 bug.