笔记-使用C语言过程中遇到的指针现象

在学对树进行层序遍历的时候写了一个链队列, 出了个毛病(具体参见后面分析). 修的时候发现是由于悬浮指针导致的, 而且还造成了内存泄漏(后面所提到的不停地把头结点扔掉现象).

所谓悬浮指针就是说一个指针指向了法外之地(并未分配给它使用的内存). 一般会发生在当内存区域被 free 掉了, 但指针未被设置为 NULL 或其他错误赋值的情况(比如本例).

还有一个相关概念叫野指针. 野指针的意思主要是说指针在被第一次赋值之前是指向一个未知区域的(当局部变量未赋值之前, 编译器不会将其初始化为0. 这时候里面那个乱七八糟的数就可能会错误地当成地址来用). 关于悬浮指针的概念可以参考这里https://en.wikipedia.org/wiki/Dangling_pointer.

问题代码#

数据结构#


#define bool int

typedef struct TreeNode
{
    int id;                 // 树的元素. 可以是一个指向实际元素的指针. 这里用一个id简化代替
    struct TreeNode *l, *r; // 左右孩子结点. Node实质为一个二叉链表
    int tagl, tagr;         // 线索二叉树的标志位
} TreeNode, *Tree;
// 线索二叉链表

typedef struct QNode
{
    TreeNode *e;
    struct QNode *next;
} QNode;
// 这个为了实现链队列存取Treenode结点
// *Qnode: 带头单链表

typedef struct Quece
{
    QNode *f, *r;
    int Qsize;
} Quece;
// 定义队列本身的结构体. 修改队列只能通过f, r指针进行.
// Quece 使用f和r管理带头单链表

链表方法(问题出在出队的实现上)#


// Q的遍历print函数
void pQ(Quece *q)
{
    QNode *current = q->f->next; // 跳过队列头节点,因为头节点不包含数据

    if (!current)
    {
        printf("Queue is empty.\n");
        getchar();
        return;
    }
    printf("目前的队列: ");
    // printf("second is %d\n", current->next?current->next->e->id:0);
    while (current)
    {
        printf("%d ", current->e->id); // 打印当前节点的TreeNode的ID
        current = current->next;       // 移动到下一个队列节点
    }
    printf("\n");
}

// Q构造函数
bool InitQ(Quece **q, int size)
{
    *q = (Quece *)malloc(sizeof(Quece));
    // 初始化第一步: 建立队列.
    (*q)->f = (*q)->r = (QNode *)malloc(sizeof(QNode));
    (*q)->f->next = NULL;
    // 初始化第二步: 建立带头单链表.
    return 1;
}

// 判空
bool isE(Quece *q)
{
    return q->f == q->r;
}

// 入队
bool EnQ(Quece *q, TreeNode *x)
{
    QNode *new_qnode = (QNode *)malloc(sizeof(QNode));
    new_qnode->e = x;
    new_qnode->next = NULL;
    // 1. 创建--初始化一个新队列结点, 准备入队列.
    q->r->next = new_qnode;
    // 2. 将新结点上传到链上
    q->r = new_qnode;
    // 3. 将队列的尾指针指向新的链尾
    printf("[+]EnQ: %d\n", x->id);
    // 打印每个入队节点的ID
    return 1;
}

// 出队
TreeNode *DeQ(Quece *q)
{
    TreeNode *rec;
    if (q->f == q->r)
    {
        return NULL;
    }
    // 特殊情况1: 队元素为0个
    // 判空(当原本的队列事实上只有0个元素, r指向f)
    QNode *p = q->f->next;
    rec = p->e;
    // 拿出队头数据(f指向带头单链表的头结点)
    q->f->next = p->next;
    // 头指针移动到新的队首
    if (q->r == p)
        // q->r = q->f;
        q->f = q->r;
    // 错误: 手残赋值反了. 这样的后果是, 当输入情况为队中只有2结点(头--e)时, q->f = q->r;
    // 特殊情况2: 队元素为1个
    // 当队列即将清空(原本的队列事实上只有1个元素, r指向f->next)时, 将f和r对齐.
    free(p);
    // 在链上删除旧的队头结点(出队)

    printf("[-]DnQ: %d\n", rec->id); // 打印每个入队节点的ID
    return rec;
}

主函数#

主函数就是一个标准的层序遍历. 用循环的方式来对树的每个结点进行 被入队—出队—该结点的左右孩子入队 过程.


// 1. 层序遍历(广度优先遍历)
bool visit_1(TreeNode *any_node)
{
    printf("%d ved\n", any_node->id);
}
// 1.1. 王道-层序遍历
void levelOrderTR(TreeNode *root)
{
    Quece *q;
    TreeNode *p;
    InitQ(&q, 20);
    EnQ(q, root);
    // 1. 根节点放进队列
    while (!isE(q))
    {
        pQ(q);
        p = DeQ(q);
        visit_1(p);
        if (p->l)
        {
            printf("%d 左孩子为%d\n", p->id, p->l->id);
            EnQ(q, p->l);
        }
        if (p->r)
        {
            printf("%d 右孩子为%d\n", p->id, p->r->id);
            EnQ(q, p->r);
        }
    }
}

// 1.1. 测试函数
void class1()
{
    levelOrderTR(makeTree(10));
}

其他函数#

把其他用到的函数也放在这里 mark 一下.


TreeNode *makeNode(int id)
{
    TreeNode *node;
    node = (TreeNode *)malloc(sizeof(TreeNode));
    node->id = id;
    node->l = node->r = NULL;
    return node;
}
// 构造函数(创建一个大小为size的完全二叉树)
TreeNode *makeTree(int size)
{
    void **arr = malloc(sizeof(void *) * (size + 1));
    // 用于存储结点指针的指针数组, 以便于批量创建结点
    // 为了对齐下标和id, 在这里多申请一块空间
    for (int i = 1; i <= size; i++)
    {
        arr[i] = makeNode(i);
    }
    for (int i = 1; i <= size; i++)
    {
        if (2 * i <= size)
            ((TreeNode *)arr[i])->l = ((TreeNode *)arr[2 * i]);
        // 当左子id<n, 作为一颗完全二叉树来说左子一定存在. 当左子存在, 将l指向左子.
        if (2 * i + 1 <= size)
            ((TreeNode *)arr[i])->r = ((TreeNode *)arr[2 * i + 1]);
        // 当右子id<n, 作为一颗完全二叉树来说右子一定存在. 当右子存在, 将r指向右子
    }
    printTree((TreeNode *)arr[1], 0);
    TreeNode *root = arr[1];
    free(arr);
    return root;
}

分析(第一回合)#

第一回合是根结点(e=1)的入队和出队. 我们都知道层序遍历的算法是用循环的方式来对树的每个结点进行 被入队—出队—该结点的左右孩子入队 过程. 在这里我口头上将一个while (!isE(q))循环称为一个回合. (进入while前的根结点入队-出队动作视为第一个回合)

另外需要先澄清几个名词的不同含义:

头结点: 链表的头结点(Qnode).
第一结点: 链表除了头结点以外的第一个元素结点(Qnode). 以后第n结点以此类推(树的第n结点直接注明树第n结点).
根结点: 被层序遍历的那棵树的树根结点(Treenode).

总结为: (头结点->第一结点->第二结点->…->NULL)

产生错误的样子#

一颗完全二叉树, 结点编号从 1~~10. 本来的想法是层序遍历, 打印 1~~10 出来. 但事实上上面的代码只打印如图的 1, 3, 7. 并且可以遍历到大部分孩子结点. 如图所示, 可以说是相当诡异.

断点分布#

上 F5 直接开始调试. 从输出可以明确的是问题一定出在队列数据结构实现上而不是层序遍历算法, 主要就是不清楚到底是歪在在入队, 出队, 还是初始化上. 我们在入队(EnQ)和出队(DeQ), 初始化(InitQ)实现算法中分别打断点.

EnQ实现:


bool EnQ(Quece *q, TreeNode *x)
{
    QNode *new_qnode = (QNode *)malloc(sizeof(QNode));
    new_qnode->e = x;
    new_qnode->next = NULL;
    // 1. 创建--初始化一个新队列结点, 准备入队列.
B>  q->r->next = new_qnode;
    // 2. 将新结点上传到链上
    q->r = new_qnode;
    // 3. 将队列的尾指针指向新的链尾
B>  printf("[+]EnQ: %d\n", x->id);
    // 打印每个入队节点的ID
    return 1;
}

DeQ实现:


TreeNode *DeQ(Quece *q)
{
    TreeNode *rec;
    if (q->f == q->r)
    {
        return NULL;
    }
    // 特殊情况1: 队元素为0个
    // 判空(当原本的队列事实上只有0个元素, r指向f)
    QNode *p = q->f->next;
    rec = p->e;
    // 拿出队头数据(f指向带头单链表的头结点)
    q->f->next = p->next;
    // 头指针移动到新的队首
B>  if (q->r == p)
        // q->r = q->f;
        q->f = q->r;
    // 错误: 手残赋值反了. 这样的后果是, 当输入情况为队中只有2结点(头--e)时, q->f = q->r;
    // 特殊情况2: 队元素为1个
    // 当队列即将清空(原本的队列事实上只有1个元素, r指向f->next)时, 将f和r对齐.
    free(p);
    // 在链上删除旧的队头结点(出队)

    printf("[-]DnQ: %d\n", rec->id); // 打印每个入队节点的ID
    return rec;
}

InitQ实现:


bool InitQ(Quece **q, int size)
{
    *q = (Quece *)malloc(sizeof(Quece));
    // 初始化第一步: 建立队列.
    (*q)->f = (*q)->r = (QNode *)malloc(sizeof(QNode));
B>  (*q)->f->next = NULL;
    // 初始化第二步: 建立带头单链表.
    return 1;
}

上述的点布置主要是为了在 hit break 的时候能从窗口监视到指针变量值, 然后判断链表的当前状态(因为队列打印函数(pQ)也需要遍历链表, 如果实现有问题, 此时已经不可信. 因此也只能调试).

排除正常函数#

首先介绍一个 gdb 调试方法. 在 gdb 命令行控制台直接输入x/32xb <变量名>或在 vscode 调试控制台输入-exec x/32xb <变量名>可以查看目标指针指向点位往后 32B 区域的二进制.

x/<n>xb格式解释:
- /<n> 表示要显示的内存单元数量为n个单位,在这里是 32 个字节.
- x 是显示格式,b 表示按字节(byte)查看数据.

InitQ#

InitQ 主要是用来创建头结点的. 也就是下面2个事:

给队列结构体q分配内存.(创建链表管理指针. 逻辑上的队列)
给q->f和q->r分配一个头结点.(创建链表)

捋到这里, 先来总结一下当前的内存情况.为了方便只看内存的后四位. 拿 InitQ 的断点首次被撞击时刻的情况来看:

*q: 队列结构体 *Quece 类型指针的地址(指针的指针), 已被分配正常的内存为0xD5D0. 在这之后就用不到了(初始化需要给指针赋值).
**q: 队列结构体 Quece 类型指针, 指向0x98F0~0x990F这一块范围的内存(下面有输出可以看).
- 0x98F0~0x9908: 就是q->f. 即q指针所指向的内存0x98F0~0x9908中的0x98f0~0x98f7字段值(555555559910H, 也就是0x555555559910, 这里仍然记为0x9910).
- 0x98F0~0x9908: 就是q->r. 即q指针所指向的内存0x98F0~0x9908中的0x98f8~0x98ff字段值. 同上, 为0x9910. 对比下面 gdb 二进制输出和图中gdb监视器可以证明.
- 0x9900~0x990f: 包含了我没有用到的size和malloc生成的 padding 填充(内存对齐-内存填充). 最终结果是q, q->f, q->r, q->next等后面会经常提到的变量事实上各占 32B.

(关于内存对齐)备注: malloc会把堆对齐到某个特定的大小. 观察q->f和q->r所指向的地址之差 $9930H - 9910H = 20H = 32D$ 可以得到在这里事实上每个内存块可以视为是32B. 而 Qnode, Quece 结构体也因为其对齐策略(不同于malloc, 结构体按照最大成员的整数倍进行对齐), 在代码上下文中事实上被视为sizeof(Qnode)==16和sizeof(Quece)==24.


-exec x/32xb q
0x5555555598f0: 0x10 0x99 0x55 0x55 0x55 0x55 0x00 0x00 #98f7 # q->f的指针
0x5555555598f8: 0x10 0x99 0x55 0x55 0x55 0x55 0x00 0x00 #98ff # q->r的指针
0x555555559900: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 #9907 # size 和 padding
0x555555559908: 0x21 0x00 0x00 0x00 0x00 0x00 0x00 0x00 #990f

EnQ#

在对 InitQ 进行初步检查后, 暂时认为 InitQ 是没有问题的. 下面对 EnQ 排查. 第一次进入 EnQ 时, EnQ 所做工作如下:

创建一个新结点 new_qnode(指向0x9930)
初始化新结点的 e(值为1, 树根结点) 和 next(初始化为指向NULL).
把原链表尾结点的 next 指向新结点, 也就是让q->r->next(指向NULL)指向新结点所在的内存区域*new_qnode(0x9930), 这一步将 new_qnode 上传到链上. 属于使用尾指针的尾插法(1/2).
把队列尾指针 q->r 指向新结点(原0x9910—后0x9930), 补全链表的指针关系. 属于使用尾指针的尾插法(2/2).


-exec x/32xb q->f
0x555555559910: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 #9817 # q->f->e (空值. 这个值不重要)
0x555555559918: 0x10 0x99 0x55 0x55 0x55 0x55 0x00 0x00 #981f # q->f->next (本来初始化为0. 在本回合第一结点(树根)首次入队后指向了第一结点)
0x555555559920: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 #9927 
0x555555559928: 0x21 0x00 0x00 0x00 0x00 0x00 0x00 0x00 #992f
# 这块内存是经过第一次 EnQ 的链表头结点


-exec x/32xb q->r
0x555555559930: 0x00 0x93 0x55 0x55 0x55 0x55 0x00 0x00 #9837 # q->r->e      (这个值不重要. 主要是对应链表结点--二茬树结点用)
0x555555559938: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 #983f # q->r->next (这个指针很重要)
0x555555559940: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 #9947 
0x555555559948: 0x21 0x00 0x00 0x00 0x00 0x00 0x00 0x00 #994f
# 这块内存是经过第一次 EnQ 的链表第一结点, 二叉树根节点

这里对比看下图中代码和调试内容也没什么问题. 故排除 EnQ 的嫌疑.

DeQ#

首先来说明一点, 出队的时候需要先判断2个特殊情况: 队长为 0 和 1 的时候. 对这俩情况做俩不同的处理:

0:当队长判断为0, 实际操作如下.


if (q->f == q->r)
{
    return NULL;
}
// 特殊情况1: 队元素为0个
// 判空(当原本的队列事实上只有0个元素, r指向f)

1:当队长判断为1, 实际操作如下.


TreeNode *rec;
// res用来暂存待会用来弹出的树节点
QNode *p = q->f->next;
rec = p->e;
q->f->next = p->next;
// 头指针next跟上新的队首
if (q->r == p)    // 这里是错误连锁反应的关键
E> {q->f = q->r;} // 这里是错误的源头. 显然赋值反了
    // {q->r = q->f;} // 正解
// 如果队长>1, 尾指针不用动(一般的). 
// 但当队长判断为1(尾指针指向的结点马上要被出队), 那就得让尾指针指向头结点完成复位(回到初始化状态).
free(p);
printf("[-]DnQ: %d\n", rec->id); // 打印每个入队节点的ID
return rec;

一般的:当队长判断为非0也非1, 实际操作如下.


TreeNode *rec;
// res用来暂存待会用来弹出的树结点
QNode *p = q->f->next;
// p指向第一结点
rec = p->e;
// 拿出队头数据(f指向带头单链表的头结点)
q->f->next = p->next;
// 头指针next跟上新的队首
free(p);
// 在链上删除旧的队头结点(出队)
printf("[-]DnQ: %d\n", rec->id); // 打印每个入队节点的ID
return rec;

在对 EnQ 进行初步检查后, 暂时认为 EnQ 是没有问题的. 下面对 DeQ 排查. 第一次进入 DeQ 时, DeQ 所做工作如下:

对队列链表判空. 空则不需要出队.(这里队长为1, 1!=0)
对队列链表判是否长度为1. 创建一个临时的Qnode* p指向第一结点(0x9930).
拿出第一结点数据.
让头结点的 next 指针q->f->next指向”第二结点”.
- 一般地: 如果第二结点存在, 指向它.
- **本次的情况:**如果第二结点不存在, 指向它(空). 并且操作q->r指向q->f(bug在这一步赋值反了).
释放p所指向的内存, 也就是原本的第一结点. 现在原本的第二结点接班变成新的第一结点了(一般地).

第一回合的总结说明#

从代码片段显然可以看出, 在操作q->r指向q->f过程中赋值写反了. 由于这句写反的赋值, 以及对是否队长为1的判断(队尾r是否和f->next指向同一区域)导致在第一回合的结尾彻底改变了链表的结构, 抛弃了头结点. 而后续也产生了连锁错, 造成了速度为每回合 0~1 个结点的内存泄漏.

现在来详细说明一下第一回合内改变链表结构的过程: 链表的头结点由于f和r和*(0x9910)->next都跑去指向了即将被删除的第一结点, 整个链表于是断开, 分成两个结构:

头[0x9910]->NULL (没有指针指向它. 正常情况下s->f, s->r应当指向它)
- 作为再也无法被访问的内存区域, 这里也是内存泄漏的开始.
非法区域[0x9930] (s->f, s->r, p)
- 注: 在本次运行的情况下, 这个非法区域(0x9930)事实上还保留着之前第一结点的内容(free函数只会标记该区域为空闲, 不会将其全体写0). 因此下面两个表达式也成立:
- *(0x9930)->e==1
- *(0x9930)->next==NULL

这里附图当时的分析. 需要注意的是图中一些名词比如野指针的用法错误了. 这里应当是悬浮指针. 以及现在所到达的位置.


Quece *q;
TreeNode *p;
// 出队结点
InitQ(&q, 20);
EnQ(q, root);
// 1. 根节点放进队列
while (!isE(q))
{
    pQ(q);
    p = DeQ(q);
->  visit_1(p); // 这里是第一回合最后到达的位置. 
    if (p->l)
    {
        printf("%d 左孩子为%d\n", p->id, p->l->id);
        EnQ(q, p->l);
    }
    if (p->r)
    {
        printf("%d 右孩子为%d\n", p->id, p->r->id);
        EnQ(q, p->r);
    }
    // 当左/右孩子存在就入队. 因此每循环可能会入队0~2个结点.
}

分析(第二回合)#

第二回合是根的左孩子结点(e=2)的入队和出队.

EnQ#

当 hit break 到 EnQ 内部的时候, 第二回合的 EnQ 也将进行 创建-尾插 的两个工作. 这时候 EnQ 要运行两次, 入队 root 的左右孩子, 也就是树的 2 和 3 结点. 下面按照入队顺序挨个看.

入队树的第二结点(链表第一结点)#

创建过程:由图可以看到new_qnode被malloc分配到了0x9930所开辟的一块Qnode内存空间(32B). 而巧合的是在上一回合中, q->f和q->r也都被错误地指向了0x9930. 这样就导致队列链表的结构在新结点初始化完毕, 并且尚未投入使用之前立刻就发生了如下的变化. 此时, 链表主体不存在头结点, 有且仅有一个结点就是这个新生产的第一结点. 同时也需要注意的是, s->f, s->r, new_qnode现在全都指向0x9930.
1. 头[0x9910]->NULL (再也没有指针可以指向它)
2. 2[0x9930] (s->f, s->r, *(0x9930)->next, new_qnode)
**“尾插”过程:**在创建新结点完毕后, 正常流程下要进行带头单链表的尾插操作了. 也就是下面代码块的q->r->next = new_qnode;和q->r = new_qnode;两步. 从前面可以看到s->f, s->r, new_qnode现在全指向0x9930. 因此这一通操作下来, 几个变量值, 0x9930内存块存储的值就变成了下面这样.
- q->f, q->f->next, q->r, q->r->next, new_qnode: 0x9930
总结为存在的指针域全都指向了0x9930. f, r全部指向第一结点, 第一结点的 next 指针也指向自己.


bool EnQ(Quece *q, TreeNode *x)
{
    QNode *new_qnode = (QNode *)malloc(sizeof(QNode));
    new_qnode->e = x;
    new_qnode->next = NULL;
    // 1. 创建--初始化一个新队列结点, 准备入队列.
B>  q->r->next = new_qnode;
    // 2. 将新结点上传到链上
    q->r = new_qnode;
    // 3. 将队列的尾指针指向新的链尾
B>  printf("[+]EnQ: %d\n", x->id);
    // 打印每个入队节点的ID
    return 1;
}

入队树的第三结点(链表第二结点)#

**创建过程:**由图可以看到new_qnode被malloc分配到了0x9950所开辟的一块Qnode内存空间(32B). 创建过程没有太大问题.
尾插过程:q->r->next = new_qnode;和q->r = new_qnode;两步操作, 解除了自指, 并且把 r 指向了新结点. 为使得链表现在变成一个不带头的单链表. 回顾全体的结点如下所示.
1. 头[0x9910]->NULL (再也没有指针可以指向它)
2. 2[0x9930] (s->f)—>3[0x9950] (s->r)—>NULL

DeQ#

在树的 2 和 3 结点入队之后, 队列链表接受 DeQ 处理. 由于失去了头结点, q->f直接指向了第一结点, 因此再次满足了关系式q->f->next==q->r. 尽管根本不是这个关系式所期待的实际情况.


TreeNode *rec;
// res用来暂存待会用来弹出的树节点
QNode *p = q->f->next;
rec = p->e;
q->f->next = p->next;
if(p==q->r)
    q->f=q->r;
free(p);
printf("[-]DnQ: %d\n", rec->id); // 打印每个入队节点的ID
return rec;

经过q->f->next = p->next;和q->f=q->r;的处理, 链表的结构发生了和第一回合一样的变化. 经过指针误操作, 导致f, r, p, 全部指向第二结点(第一回合的第一结点). 第一结点(第一回合的头结点)被丢弃, 链表断裂再也无法被访问, 造成第二次内存泄漏. 而另一边f, r, p所指向的0x9950旋即被free掉, f和r再次变成悬浮指针. 此时链表的结构如下.

头[0x9910]->NULL (再也没有指针可以指向它)
2[0x9930]->NULL (再也没有指针可以指向它)
3[0x9950] (s->f, s->r)—>NULL

第二回合的总结说明#

从第二回合可以看到 bug 所形成的结构开始产生规律, 也就是在抛掉头结点后变成了一个不带头的单链表形式, 并且在当 $此不带头单链表长度=2$ 的时候会直接把第一结点咔嚓掉. 后面去吃饭了就没继续看了. 不过可以预测的是, 在后面的几个回合, 当树在下一次出队动作产生之前所做出的入队无法打破单链表长度=2的局面, 那么内存泄漏就会以每循环一个的速度持续发生. 并且层序遍历(访问 DeQ 的返回值)由于 DeQ 的内部问题只能访问到树的右孩子. 表现到最后就是只能访问树的最右侧(我这里写的makeTree只能造完全二叉树, 所以是 $1, 3, 7, 15, ...$ 这样一个序列).