数据结构——树

一、树、二叉树性质

　　一般这种题会问你结点数、高度、空指针域等问题
　　需牢记：
　　　1.二叉树：n0 + n1 + n2 = n1 + 2*n2 + 1 = n
　　　　这个方程最重要！！！可以解决度、边、结点数直接关系的问题。题中出现度、结点直接用此公式就对了
　　　2.二叉树：0 = 2 + 1，即叶节点数 = 度为2的结点数 + 1（由1的前两个组成方程推导出来）
　　　3.二叉树：2n个孩子指针，只有n-1个结点可以作为孩子被指，故有2n-(n-1)=n+1个空指针（空链域）
　　　4.完全/满二叉树：一行的起始结点号 = 该行可容纳的结点数 = 2^(n-1)；一行的末尾结点号 = 整棵树的结点数 = 2^n-1
　　　5.完全二叉树：高度公式里上外下（+1在对数里面就向上取整，外面就向下取整）
　　　6.完全二叉树的叶节点只有可能出现在倒数两行，一个完全二叉树的叶节点要么处于上面那行，要么出现在下面那行

二、二叉树的遍历

　　前序遍历，根左右，对于一个结点而言，先访问它，再访问其左子树，再访问其右子树。最后被访问到的是该结点右子树的最右下的叶节点。最先访问到的是结点本身。
　　中序遍历，左根右，对于一个结点而言，先访问其左子树，再访问它，再访问其右子树。最后被访问到的是该结点右子树的最右下转折处的结点。最先访问到的是其左子树最左下转折处的结点。
　　后序遍历，左右根，对于一个结点而言，先访问其左子树，再访问其右子树，再访问它。最后被访问到的是结点本身。最先访问到的是该结点左子树最左下的叶节点。
　　层次遍历，利用队列，从根节点进入队列开始，每次出一个，并将其孩子添加到队列中知道队列为空。
　　四个遍历一定要烂熟于心。

三、创造线索二叉树

　　介绍：线索二叉树的创造依赖于前、中、后遍历序列。结点的左孩子为空，则设置左孩子指针为其前驱的位置并置ltag = 1；结点的右孩子为空，则设置右孩子指针为其后继的位置并置rtag = 1。ltag与rtag表明了该结点的指针是否为线索。
　　将一棵二叉树改为线索二叉树：需要对二叉树遍历，而遍历分为先序中序与后序。遍历的种类决定了线索二叉树的种类。
　　先序：先设置当前结点的前驱（空左孩子）再设置pre的后继（空右孩子），再递归到左孩子，最后递归到右孩子。
　　中序：先递归到左孩子，再设置当前结点的前驱（空左孩子）再设置pre的后继（空右孩子），最后递归到右孩子。
　　后序：先递归到左孩子，再递归到右孩子，最后设置当前结点的前驱（空左孩子）再设置pre的后继（空右孩子）。
　　特别注意：先序遍历创造线索二叉树中，递归到左孩子小心此时的左孩子指针可能不指向其左孩子而指向其前驱。

四、遍历线索二叉树

　　方法：线索二叉树的遍历需由该线索二叉树的种类决定。但思想是一致的：多米诺骨牌——找到序列的首结点，从序列的首结点出发，想尽办法找到下一个结点。
　　先序：
　　　　找到序列首结点：即一个序列的根节点
　　　　找到下一个结点的办法：后继线索存在则用之。否则（右孩子存在），若左孩子不存 　　　　　　在，则下一个结点为右孩子；若左孩子存在，则下一个结点为左孩子。
　　中序：
　　　　找到序列首结点：最左下转折处的结点
　　　　找到下一个结点的办法：后继线索存在则用之。否则（右孩子存在），找到右子树序　　　
　　　　　　列首结点。
　　后序：
　　　　找到序列首结点：最左下的叶节点
　　　　找到下一个结点的办法：后继线索存在则用之。否则，若其为左孩子且其双亲右孩子
　　　　　　存在，找到其双亲右子树的最左下的叶结点；若其为左孩子且其双亲右孩子不存
　　　　　　在，则其双亲就是后继；若其为双亲的右孩子，则其双亲同样为后继。
　　　　可见后序线索二叉树找后继需要找双亲结点，需要借助三叉链表或栈。

五、树、森林转二叉树

　　每个结点的左右指针存储左孩子右兄弟。相当于整个树/森林顺时针旋转了45度。转成后的二叉树左孩子空指针域都是原来树的叶节点才有的；右孩子空指针域每个非叶节点一个（在非叶节点的最后一个孩子处），若是森林最后一棵树的根节点又有一个。

六、哈夫曼树

　　若所有叶节点表示一种信息，叶节点的权为信息使用的频度。整棵树的带权路径长度评价了用二进制对信息进行编码的代价。而哈夫曼树做到了使这种代价最小。
　　构造哈夫曼树（最重要）：若由n个带权结点需要生成哈夫曼树，则将他们所有视为一棵棵单节点树。每次取权值最小的合并，新树权值为合并前两棵树的权值之和。
　　从构造过程可以看出：每次两棵树合并，左右位置可互换，因此每次合并有两种选择。故哈夫曼树不是唯一的。
　　每次合并树的数量都少1，初始n棵，最后1棵，故合并了n-1次，产生了n-1个非叶节点，最后的树总计n-1+n=2n-1个结点。
　　补充1：还可以为三进制、四进制...创造哈夫曼树，此时哈夫曼树就不再是二叉树了。整棵树的度要么为进制数，要么为0。
　　补充2：哈夫曼树的带权路径长度的两种计算方法：①所有叶节点带权路径长度之和（原始定义）；②所有分支结点（非根节点）权值之和（记住即可，没讲为什么）

七、并查集

　　能够合并与查找结点所在集合的数据结构称为并查集。采用顺序存储的双亲表示法表示的森林（不一定是二叉树森林）来实现。森林中每一棵树就代表一个集合。
　　查找：查找一个元素所在的集合，就是查找其所在树的根节点。采用循环访问其双亲结点的索引知道-1（根节点处的索引）即可。另外可以在每次循环结束（找到后）进行一些步骤来优化。具体措施是再走一遍循环，将每一个访问到的结点的索引都改成根节点的索引，即直接称为根节点的孩子，以此减小树高。
　　合并：合并两棵树。可能需要利用查找找到根节点的索引。直接将一个根节点的数组内容（双亲索引）从-1改为另一个根节点的索引即可。更优化的方法是，让所有根节点的数组内容不再存储-1，而是树的结点个数，在合并的时候使用条件语句保证小树合并到大树，以此减小树高。

高等数学重要定义整理

一、函数、极限与连续

1.函数：两个数集之间多对一的映射关系
2.复合函数：数集A与数集B有多对一的关系，数集B与数集C亦有多对一的关系，A映射出来的B必须有一个以上的元素可以映射C，就称A到C的映射关系为复合函数
3.反函数：两个数集之间一对一的映射关系
4.数列的极限：数列一定能在未来某个时候(n > N)达到接近一个常数的要求(ɛ)，该常数称为该数列的极限
5.函数的极限：
5.1 自变量趋于无穷大时的极限：函数一定能在未来某个时候(|x| > X)达到接近一个常数的要求(ɛ)，该常数称为该函数趋于无穷大时的极限（把绝对值拿掉可区分趋于正无穷与负无穷的极限）
5.2 自变量趋于有限值时的极限：函数一定能在靠近该有限值的某个时候(0 < |x - x0| < δ)达到接近一个常数的要求(ɛ)，该常数称为该函数趋于有限值时的极限（把绝对值拿掉可区分左极限右极限）
6.无穷大：一个函数，在一点或无穷远处要多大有多大
7.无穷小：一个函数，在一点或无穷远处要多小有多小
8.在x0连续：在点x0的邻域内有定义，且x0到两侧点不突变（limΔy = lim(f(x0+Δx) - f(x0) = 0)————Δy是无穷小
9.间断点：在某点处不连续的点
9.1 第一类间断点：较为温和的间断点
9.1.1 可去间断点：左右极限存在且相等
9.1.2 跳跃间断点：左右极限存在但不等
9.2 第二类间断点：变化较为剧烈
9.2.1 无穷间断点：在一点处趋于无穷
9.2.2 振荡间断点：sin(1/x)的x=0点

二、导数与微分

1.一点导数：Δy与Δx的比值的极限。特别注意Δy一定是一动一静。
2.一点微分：增量Δy的线性主部f'(x0)Δx(即Δx->0时,Δy与dy互为等价无穷小)。特别注意Δy一定是一动一静。
3.一点可导：该点某邻域有定义，且Δy与Δx的比值的极限存在（即左极限等于右极限且极限不为无穷）————Δy是Δx的同阶或高阶无穷小
4.一点可微：该点某邻域有定义，且A为常数————Δy是Δx的同阶或高阶无穷小
5.区间上可导/可微：区间上每一点都可导/可微（分为开区间与闭区间）

三、微分中值定理及导数应用

1.费马引理：可导函数极值点处的导数为0
2.极值点：在点x0的邻域内有定义，且该点函数值在该邻域内最大/最小
3.驻点：导数为0的点
4.在区间I上是凹的：f(x)在I上连续，且任意两点中值小于均值(f((x1+x2)/2) < ((f(x1)+f(x2))/2))
5.在区间I上是凸的：f(x)在I上连续，且任意两点中值大于均值(f((x1+x2)/2) > ((f(x1)+f(x2))/2))
6.拐点：连续曲线弧上凹与凸的分界点
7.渐近线：
水平渐近线——limf(x) = A
铅直渐近线——limf(x) = ∞
斜渐近线 —— lim(f(x) - ax - b) = 0

四、不定积分

1.原函数：在一个区间内的每一个点原函数求导都为该函数
2.不定积分：一个函数的原函数的全体

数据结构——串

本文主要介绍串的核心算法——KMP算法。
前提：假设字符串起始索引为1。主串长度为m，索引为i；模式串长度为n，索引为j。

一、如何计算主体函数（已知next数组）的时间复杂度

KMP算法无非就两个部分：i与j共同增加1；i不动，j减少（即j = next[j]）。
时间复杂度的求解需要知道上述两个运行次数为无穷大的语句相加的结果。

1.i与j共同加1

这种情况是遇到相匹配或模式串第1位于主串第i位不匹配导致的。
i从1增长到主串结尾m，因此该语句最多执行m次。

2.i不动，j减少

这种情况是遇到模式串的第j位与主串的i位不匹配导致的。
j每次减少的量若最少会导致操作步骤的最多。因此j每次减少1，操作步骤会最多。
j的每次减一消耗的是上述的i加一操作。
因此j减1最多的执行次数与操作一一致，m次

总结

因此俩个操作之和就是2m次。时间复杂度为其基本同阶无穷大，即O(m)。

二、next与nextval数组的手算求法

1.next数组

首项与第二项填0与1。后面每一项找到当前项前面的字符串的最长相同前后缀的前缀，该前缀的后面一位的索引即该该项的next值。

2.nextval数组

写出next数组。接下来开始nextval手算。
第一项填0，后面每一项比对该项与next[该项下标]对应的字符是否相等，
若不相等，直接填next；若相等，填nextval[next[该项下标]]

UNIX 98伪终端核心系统调用及实践实现

1. UNIX 98伪终端核心系统调用

以下为伪终端的工作模式，伪终端即伪终端对，分为伪终端主设备与伪终端从设备。主设备向用户显示信息或读取输入，从设备与作业进程交互。
驱动程序介于两者之间，维护有输入队列(主设备->从设备)与输出队列(从设备->主设备)。回显指的是将输入队列的数据添加至输出队列，这里的行缓冲（不同于stdio库的行缓冲）指输入队列出现换行符才将输入队列的内容发给从设备供前台进程组读取。

1.1 posix_openpt

功能描述

打开伪终端主设备（PTY Master），返回主设备文件描述符。

函数声明

#include <stdlib.h>
#include <fcntl.h>

int posix_openpt(int flags);

参数详解

• flags：打开模式标志位（按位或组合）：

  • O_RDWR：必须指定的读写模式
  • O_NOCTTY：防止成为控制终端
  • O_CLOEXEC：设置close-on-exec标志

返回值

• 成功：返回主设备文件描述符（≥3）

• 失败：返回-1，设置errno：

  • ENOMEM：内核内存不足
  • ENOSPC：伪终端资源耗尽
  • EMFILE：进程文件描述符达上限

1.2 grantpt

功能描述

设置从设备（PTY Slave）的权限为可访问。

函数声明

#include <stdlib.h>

int grantpt(int master_fd);

参数详解

• master_fd：由posix_openpt返回的主设备描述符

返回值

• 成功：返回0

• 失败：返回-1，设置errno：

  • EINVAL：无效文件描述符
  • EACCES：权限不足

1.3 unlockpt

功能描述

解除主设备的访问锁，允许从设备被打开。

函数声明

#include <stdlib.h>

int unlockpt(int master_fd);

参数详解

• master_fd：已通过grantpt授权的主设备描述符

返回值

• 成功：返回0

• 失败：返回-1，设置errno：

  • EINVAL：无效文件描述符

1.4 ptsname

功能描述

获取伪终端从设备路径名。

函数声明

#include <stdlib.h>

char *ptsname(int master_fd);

参数详解

• master_fd：已解锁的主设备描述符

返回值

• 成功：返回从设备路径字符串指针（如/dev/pts/5）

• 失败：返回NULL，设置errno：

  • EINVAL：无效文件描述符

2. ptyMasterOpen函数实现

功能目标

打开伪终端主设备并完成初始化配置，返回从设备路径。

函数原型

#include <fcntl.h>
#include <string.h>
#include <errno.h>

int ptyMasterOpen(char *slaveName, size_t snLen) {
    int master_fd;
    char *slave_path;
    
    master_fd = posix_openpt(O_RDWR | O_NOCTTY);
    if (master_fd == -1) return -1;

    if (grantpt(master_fd) == -1) {
        close(master_fd);
        return -1;
    }

    if (unlockpt(master_fd) == -1) {
        close(master_fd);
        return -1;
    }

    slave_path = ptsname(master_fd);
    if (slave_path == NULL) {
        close(master_fd);
        errno = EINVAL;
        return -1;
    }

    if (strlen(slave_path) >= snLen) {
        close(master_fd);
        errno = EOVERFLOW;
        return -1;
    }

    strncpy(slaveName, slave_path, snLen);
    return master_fd;
}

关键处理逻辑

• 缓冲区验证：通过strlen校验目标缓冲区容量
• 错误处理链：确保资源泄露防护
• 标志位组合：O_RDWR|O_NOCTTY保证基本功能

3. ptyFork函数实现

3.1 核心数据结构

termios结构体（终端属性）

struct termios {
    tcflag_t c_iflag;  // 输入模式标志
    tcflag_t c_oflag;  // 输出模式标志
    tcflag_t c_cflag;  // 控制模式标志
    tcflag_t c_lflag;  // 本地模式标志
    cc_t c_cc[NCCS];   // 控制字符数组
};

winsize结构体（窗口尺寸）

struct winsize {
    unsigned short ws_row;    // 行数
    unsigned short ws_col;    // 列数
    unsigned short ws_xpixel; // 水平像素
    unsigned short ws_ypixel; // 垂直像素
};

3.2 函数实现

#include <unistd.h>
#include <sys/ioctl.h>

pid_t ptyFork(int *masterFd, char *slaveName, size_t snLen,
              const struct termios *slaveTermios,
              const struct winsize *slaveWS) {
    int mfd, saved_errno;
    pid_t childPid;

    mfd = ptyMasterOpen(slaveName, snLen);
    if (mfd == -1) return -1;

    childPid = fork();
    if (childPid == -1) {
        saved_errno = errno;
        close(mfd);
        errno = saved_errno;
        return -1;
    }

    if (childPid != 0) {  // 父进程
        *masterFd = mfd;
        return childPid;
    }

    // 子进程执行流
    if (setsid() == -1) _exit(EXIT_FAILURE);

    close(mfd);

    int slave_fd = open(slaveName, O_RDWR);
    if (slave_fd == -1) _exit(EXIT_FAILURE);

#ifdef TIOCSCTTY
    if (ioctl(slave_fd, TIOCSCTTY, 0) == -1)
        _exit(EXIT_FAILURE);
#endif

    if (slaveTermios && tcsetattr(slave_fd, TCSANOW, slaveTermios) == -1)
        _exit(EXIT_FAILURE);

    if (slaveWS && ioctl(slave_fd, TIOCSWINSZ, slaveWS) == -1)
        _exit(EXIT_FAILURE);

    dup2(slave_fd, STDIN_FILENO);
    dup2(slave_fd, STDOUT_FILENO);
    dup2(slave_fd, STDERR_FILENO);

    if (slave_fd > STDERR_FILENO)
        close(slave_fd);

    return 0;
}

3.3 关键操作说明

1. 会话控制：

   • setsid()：创建新会话，脱离原终端控制
   • TIOCSCTTY：显式获取控制终端（BSD兼容）

2. 描述符重定向：

   • dup2三步操作：实现标准流全重定向

3. 属性继承：

   • tcsetattr：精确复制原终端行为特征
   • TIOCSWINSZ：保持窗口尺寸一致性

4. 系统调用关系图谱

graph TD
    A[posix_openpt] --> B[grantpt]
    B --> C[unlockpt]
    C --> D[ptsname]
    D --> E[ptyMasterOpen]
    E --> F[fork]
    F --> G[setsid]
    G --> H[ioctl-TIOCSCTTY]
    H --> I[tcsetattr]
    I --> J[dup2]

通过系统调用的组合使用，可构建完整的伪终端通信通道，为高级终端应用开发奠定基础。