链表小技巧 & 常见问题

Written by Baymax

使用宏定义简化malloc

1
2
3
4
5
6
7
8
9
10
11
#define new(X) (X*)malloc(sizeof(X))
typedef struct Node{
  ...
  struct Node* next;
  ...
}Node;

//原来创建节点的方式
Node *node = (Node*)malloc(sizeof(Node));
//简化后创建节点方式
Node *node = new(Node);

使用头节点

头节点是链表中的一个特殊节点，通常位于链表的最前端。它并不存储有效数据，而是一个辅助节点，用于简化链表操作，例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 没有使用头节点
typedef struct Node {
    int data;
    struct Node* next;
}Node;

Node* head = NULL; // 链表头指针，空链表
Node* newNode = new(Node);
newNode->data = 5;
newNode->next = head;
head = newNode;
--------------------------------------------------------------------
// 使用头节点
Node* head = new Node();  // 头节点
head->next = nullptr;      // 头节点的next指向nullptr

// 插入新节点到链表头部
Node* newNode = new Node();
newNode->data = 5;
newNode->next = head->next;
head->next = newNode;

使用头节点可以让链表的操作（如插入、删除、遍历）更加统一，不需要特别处理空链表的情况或操作链表头节点本身。

比如，插入一个新节点到链表的头部，没头节点的情况下，如果链表为空，插入操作就需要特判。而有了头节点，插入头节点的操作可以直接写成相同的逻辑，无论链表是否为空：

1
2
3
4
5
6
7
8
9
10
11
12
// 无头节点
if (head == NULL) {
    head = new(Node);
  	...
} else {
    newNode->next = head;
    head = newNode;
}
--------------------------------------------------------------------
// 使用头节点
newNode->next = head->next;
head->next = newNode;

同样，在没有头节点的链表中，如果要删除链表的头节点，我们需要单独处理删除操作；但有了头节点后，删除头节点就变得和删除其他节点一样，统一处理：

1
2
3
4
5
6
7
8
9
10
11
// 无头节点
if (head != NULL) {
    Node* temp = head;
    head = head->next;
    free(temp);
}
--------------------------------------------------------------------
// 使用头节点
Node* temp = head->next;
head->next = head->next->next;
free(temp);

常见问题

不能定义名字为 read 的函数

judge 上已经有定义好的 read 函数，不少同学在本地写代码时因为重复定义了名为 read 的函数而导致无法 AC。

文件相关函数综述

在一般情况下，下面中“推荐使用”部分的几个函数已经可以满足当前所有的文件输入输出需求。
如果你愿意了解更多，可以向下查看。

注：以下函数参数列表中 char* 可以大致理解为字符串
FILE* 可以大致理解为文件

为了便于理解，省略了大部分 const 修饰符，并人为修改了一些参数类型。

推荐使用：

  • fopen(char* filename, char* mode) 和 fclose(FILE* stream)

    • 打开和关闭文件的函数。前者返回一个 FILE 类型的指针，后者接受一个 FILE* 类型的指针并关闭它。
    • 是文件读入的基础函数。
    • 一般来说 fopen 的 mode 参数只需要使用 "r"（读入）与 "w"（写入）两种。
    • 在程序未尾使用 fclose 来输出/输入文件可以让你的程序更可靠。推荐使用。
    • fopen 在失败时返回 NULL（空指针），fclose 则返回 EOF。

  • fscanf(FILE* stream, char* format,...) 和 fprintf(FILE* stream, char* format,...)

    • 和基础输入输出 scanf、printf 的用法和行为都几乎一样。
    • 需要结合 fopen 函数使用。
    • 在读到文件末尾时，fscanf 返回 EOF。

  • fgets(char* str, int num, FILE* stream) 和 fputs(char* str, FILE* stream)

    • 读入一整行字符串，不会因为空格停止读入。与 gets 函数相似。
    • 读入的最大长度为 num。

  • 在读到文件未尾时，fgets 返回 空指针 NULL。

  • 请注意：如果混用 fscanf 和 fgets，fgets 可能会读入 fscanf 当作分隔符而没有读入的换行符。

  • fputs 函数与 puts 函数相似，输出一整个字符串。

可以使用，但是需要额外注意：

  • freopen(char* filename, char* mode, FILE* stream)

    • 将参数传入的流重定向到文件流。
    • 如果 stream 是 stdin，则重定向后可以用标准输入输出的方式（如 scanf, gets）来读写文件。
    • freopen 失败时返回 空指针 NULL。
    • 由于操作系统的差别，不应该 在使用 freopen 打开文件后再次使用 freopen 返回标准输入输出。
    • freopen 可以作为调试时的选择之一。

  • fgetc(FILE* stream) 和 fputc(char character, FILE* stream)

    • 与 getchar 和 putchar 相似，从文件里读入或输出单一字符。
    • 在读到末尾时，fgetc 返回 EOF。
    • getc 和 putc 函数和这两个函数行为上没有区别，但是为了防止混淆，此处不予列出。

基本不会使用到：

  • fread(void* ptr, size_t size, size_t count, FILE* stream) 和
    fwrite(void* ptr, size_t size, size_t count, FILE* stream)

    • 从文件中读入或输出一整块数据。
    • 在读到末尾时，fread 仍然会返回已读入数据的数量（依照 size 参数计算）。
    • 需要通过 ferror, feof 等判断是否读完。
    • 除非你知道自己在做什么，否则不应该使用这两个函数。
    • 这两个函数的文件读写速度高于其他函数，在对性能有高要求时可以考虑。

  • fflush(FILE* stream)

    • 如果输出流中有缓存的未输出数据，将其写入对应的文件。
    • 可以配合 fwrite 等函数工作。
    • 一般来说不会用到。
    • 错误时返回 EOF。

不推荐使用：

  • feof(FILE* stream) 和 ferror(FILE* stream)

    • 可以用来判断文件是否读取完毕，或是找出文件读取时的错误。
    • 经测试在 Windows 系统和 Linux 系统上的行为有区别。
    • 除非你知道自己在做什么，否则不应该使用这两个函数。

  • ftell, fseek, fgetpos, fsetpos 和 rewind

    • 文件读取或写入时操作写入位置的函数。
    • 可以配合 fread 和 fwrite 使用。
    • 除非你知道自己在做什么，否则不应该使用这五个函数。

参考资料：C++ reference - cstdio