猪脚说第十期

`sizeof`和`strlen`

约定，假设我们有数组char buf[512];，如果我们用数组名给一个指针赋值，如char *p = buf;，则称用指针p管理数组buf。显然，*p，p[2]，*(p + 10)，p--， *p++，(*p)++等操作都是允许的。当然，特别要注意的是，buf++这一操作是不允许的，因为数组名是一个常量。

两者对比

sizeof是一个运算符，而strlen是一个 C 库函数。前者获取运算对象的字节数，后者返回字符串的长度。

**sizeof(数组名)**返回数组总字节数。

char c[10];    // sizeof(c) = 10 × 1 = 10
double d[20];  // sizeof(d) = 20 × 8 = 160

strlen的参数是字符串首地址，返回字符串的长度。

char buf[] = "hello"; // strlen(buf) = 5
char *p = buf;        // strlen(p) = 5，因为 p 存的也是字符串首地址

**sizeof(指针变量)**的值是固定的。32 位机器为 4，64 位机器为 8。

// 32 位机器上
char *pc;   // 字符指针，size 为 4
int *pi;    // 整型指针，size 为 4
double *pd; // 双精度浮点型指针，size 为 4

struct node {char c; long l; int arr[10];};
struct node *pn;   // 结构体指针，size 为 4

int (*pa)[100];    // 数组指针，size 为 4
void (*pf)(int i, struct node *p, char c);
                   // 函数指针，size 为 4

综上，特别注意

char buf[512] = "hello";
char *p = buf;
sizeof(buf);  // 512
sizeof(p);    // 4 or 8
strlen(buf);  // 5
strlen(p);    // 5

结构体的`size`

以 32 位机器为例。

结构体的成员按照声明的顺序排布。例如

struct node {
    int i;
    struct node *next;
};
/*
  ----------------------
  |         int        | 4 字节 \
  ----------------------         8 字节 sizeof(struct node) == 8
  |         ptr        | 4 字节 /
  ----------------------
*/

但是，一般情况下结构体的size并不等于其各个成员的size之和，这是因为，为了满足size的 4 字节对齐（即总size是 4 的整倍数），系统可能会空出一些不用的字节。例如

struct node {
    char c;
    int i;
    short s; // 2 字节
};
/*
  ----------------------
  |        char        |  1 字节
  ----------------------
  |        空白         |  补 3 字节
  ---------------------------------> 4 字节
  |        int         |  4 字节
  ---------------------------------> 8 字节
  |       short        |  2 字节
  ----------------------
  |        空白         |  补 2 字节
  ---------------------------------> 12 字节
*/

如果声明成员的顺序不同，可能会出现其他情况，如

struct node {
    char c;
    short s;
    int i;
};
/*
  ----------------------
  |        char        |  1 字节
  ----------------------
  |        short       |  2 字节
  ----------------------
  |        空白         |  补 1 字节
  ---------------------------------> 4 字节
  |        int         |  4 字节
  ---------------------------------> 8 字节
*/

当然，获取结构体的size只需要通过sizeof即可，以上内容属于补充性的说明。

`malloc`

malloc的参数是欲分配空间的字节数，它返回一个通用指针，具体要怎么利用这片内存，由编程者自己决定（强转成指向谁的指针）。务必理解以下代码

// 32 位机器，以下代码都在 main 中
void *p = malloc(8);  // 分配 8 个字节的内存，首地址交给 p
char *pc = (char*)p;  // 用字符指针管理这片内存(能装 8 个字符)
pc[0] = 'a'; pc[1] = 'b'; pc[2] = 'c'; pc[3] = '\0';
                      // 构造了字符串 "abc"
int *pi = (int*)p;      // 再用整型指针管理这片内存(能装 2 个整数)
pi[0] = -1; pi[1] = 10; // 进行了合法的赋值
double *pd = (double*)p; // 最后用浮点型指针管理这片内存(能装 1 个双精度浮点数)
*pd = 3.14; // 用指针形式访问
pd[0] *= 2; // 用数组形式访问
// 注意以上操作是连续的，有了一片可访问的内存，我想怎么用就怎么用

树的理论知识汇总

基本定义

树是一种特殊的图。但我们还没有给出图的定义，因此可形象理解：给若干顶点，在它们间连若干条边（可以是 0 条），即得到一张图。边上有箭头规定边的方向的图，称为有向图；否则称无向图。给定一张无向图，如果任意两个顶点间都有一条或多条边把它们连在一起，则称无向图是连通的。
注意，以下内容并不完全严谨但适用于本课程。

连通且无圈的无向图称为树。
设树 $T$ 有 $n$ 个顶点，$m$ 条边，则 $m = n - 1$。$总度数 = 2m=2(n-1)$。
设 $T$ 是无向图，则以下几种说法等价
- $T$ 是树。
- $T$ 连通且无圈。
- $T$ 的每一对顶点间有唯一的一条路径将它们连接。
- $T$ 连通且“边数 = 顶点数 - 1”。
- $T$ 无圈且“边数 = 顶点数 - 1”。
若树 $T$ 的每个顶点的度都小于或等于 $2$，且已经规定好了左右次序，则称 $T$ 为二叉树。
若二叉树 $T$ 每一层的节点数都达到最大值，则称 $T$ 为满二叉树。
若二叉树 $T$ 扣除最后一层的节点成为满二叉树，且最后一层节点严格从左到右排列，则称 $T$ 为完全二叉树。

常用结论

非空二叉树的性质

第 $i$ 层最多有 $2^{i-1}$ 个节点。
若深度为 $h$，则最多有 $2^h-1$ 个节点。
设叶子节点有 $n_0$ 个，度为 $2$ 的节点有 $n_2$ 个，则 $n_0 = n_2 + 1$。

满二叉树的性质

第 $i$ 层有 $2^{i-1}$ 个节点。
深度为 $h$ 的满二叉树有 $2^{h}-1$ 个节点，其中叶子节点有 $2^{h-1}$ 个。
具有 $n$ 个节点的满二叉树的深度为 $\text{log}_2(n+1)$。

完全二叉树的性质

具有 $n$ 个节点的完全二叉树的深度为 $\lfloor \text{log}_2n\rfloor + 1$。
深度为 $h$ 的完全二叉树至少有 $2^{h-1}$ 个节点。
对具有 $n$ 个节点的完全二叉树按层次从上到下、每层从左到右从 $1$ 开始编号，则编号为 $i$ 的节点具有性质
- $i = 1$ 表示根节点；
- $i > 1$ 时，该点的父节点编号为 $\lfloor i\ /\ 2\rfloor$；
- 若 $2i>n$，则该节点无左孩子，否则左孩子的编号为 $2i$；
- 若 $2i+1>n$，则该节点无右孩子，否则右孩子的编号为 $2i+1$。
对具有 $n$ 个节点的完全二叉树按层次从上到下、每层从左到右从 $0$ 开始编号，则编号为 $i$ 的节点具有性质
- $i = 0$ 表示根节点；
- $i > 0$ 时，该点的父节点编号为 $\lfloor (i-1)\ /\ 2\rfloor$；
- 若 $2i+1\geq n$，则该节点无左孩子，否则左孩子的编号为 $2i+1$；
- 若 $2i+2\geq n$，则该节点无右孩子，否则右孩子的编号为 $2i+2$。

Huffman 编码的一些问题

此题在做之前一定要仔细看题面，题面已经给出了所有思路与逻辑，原有代码已经定义好的结构体等变量不能自己再重定义，只能严格按照原有代码补充所需步骤。

为什么用`char`不行

对于该题的实验步骤 4，在题面中给出的代码片段（如下）中，

char hc;
// ...
for (i = 0; s[i] != '\0'; i++) {
  // ...
}

变量hc的类型是char，如果不特殊处理，则会导致fputc(hc, obj)与printf("%x", hc)的输出结果错误。

原因是在输出时，输出函数fputc()与printf()会先将hc由char类型转换为int类型，所以当hc的最高位为1时，会转化成一个负数，从而得到错误的输出。

为什么会将hc由char转换为int类型呢？
- fputc()函数原型中，第一个参数为int类型，即在输出时会进行隐式类型转换
- printf()函数的可变长参数表中，并不会实际接收到char类型的参数（与该函数的具体实现方式有关）

解决方案：将hc定义为unsigned char类型，或者在输出时先进行强制类型转换，旨在不让其被识别为负数。

二进制模式和文本模式

文件读写一般采用二进制模式或文本模式。

二进制模式
- "wb"、"rb"
- 读写文件时不进行任何预处理，会原封不动得到原有数据
文本模式
- "w"、"r"
- 读写文件时会先经过预处理，因此得到的数据和原有数据存在差别。比如在windows系统下，会进行\r\n与\n的转换（所以读到这儿的同学不妨想一想，大作业究竟怎么读入更方便）
- 目前遇到的上机题目中，大家只需要用文本模式读写文件即可

对于编程题第 6 题（选做题）的解压功能，如果使用文本模式"r"来读入，在读到十六进制字节0x1A时，会被当作控制字符SUB（对应的ASCII码是0x1A）处理，产生与控制台ctrl + Z相同作用（结束输入），从而产生bug。解决方式为使用二进制模式"rb"读入。

对一个文件多次读入

猪脚说第二期已经提到过“文件偏移量”的概念，不清楚的同学可以自行翻阅。

读完文件后，文件偏移量已经到了该文件的末尾，那我们怎么再次对这个文件从头开始读入呢？有这样一个函数：

int fseek(FILE *stream, long offset, int origin);

该函数位于<stdio.h>库中，实现重定位流（数据流或者文件）上的文件内部位置指针。

各参数的含义为：stream将指向以origin为参考位置，偏移offset个字节的位置。若函数执行成功，则返回值为 0，否则为非 0 值，并设置error错误代码。

其中，offset为偏移量，正数表示正向偏移，负数表示负向偏移。

第三个参数origin设定文件从哪儿开始偏移，可能取值为三个宏：

SEEK_SET：文件开头
SEEK_CUR：当前位置
SEEK_END：文件结尾

简而言之，给出以下三种合法调用：

fseek(fp, 0L, SEEK_SET);
// 将文件偏移量设置到文件头

fseek(fp, 100L, SEEK_CUR);
// 将文件偏移量设置到当前位置后的 100 字节处

fseek(fp, -100L, SEEK_END);
// 将文件偏移量设置到离文件结尾 100 字节处

这个函数很重要，在该实验题的实验步骤 4 中很可能会用到。当然，如果只是想从头开始读文件，可以先关闭文件，再重新打开。

Author: diandian, Riccardo

Diandian Honey Pot