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

#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));
}

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;
}

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;
}

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;
}

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;
}

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

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;

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;

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个结点.
}

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;
}

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;