青少年编程知识记录

2025年10月18日

图的访问与存储—临接矩阵

1. 什么是邻接矩阵？邻接矩阵是图的一种最基础的存储表示方法。它使用一个二维数组（即矩阵）来表示图中各个顶点之间的邻接关系。对于一个有 n 个顶点的图，其邻接矩阵是一个 n x n 的方阵，我们通常称之为 A。2. 矩阵元素的定义矩阵中每个元素 A[i][j] 的值，表示顶点 i 与顶点 j 之间的关系。这个关系的具体含义根据图的类型有所不同：对于无向图A[i][j] = 1：表示顶点 i 和顶点 j 之间有一条边相连。A[i][j] = 0：表示顶点&n

2025年10月18日

树的存储与遍历—链式存储

一、定义

链式存储是表示树结构最直观、最常用的一种方法。它的核心思想是：

用链表中的节点来表示树中的每个元素。每个节点不仅包含数据本身，还包含指向其子节点的指针。

二、基本结构

对于一个普通的树（不一定是二叉树），一个典型的链式存储节点结构如下：

// C语言示例  typedef struct TreeNode {      int data;                   // 节点中存储的数据      struct TreeNode *firstChild; // 指向第一个孩子节点的指针      struct TreeNode *nextSibling; // 指向下一个兄弟节点的指针  } Node;

这种结构通常被称为 “孩子-兄弟表示法” 或 “左孩子右兄弟表示法”。

三、基本原理

假设我们有这样一棵树：

        A        / | \       B  C  D      / \    |     E   F   G

用“孩子-兄弟表示法”的链式存储后，它在内存中的逻辑结构会变成一棵二叉树的样子：

      A       /      B ——— C ——— D     /                 /    E ——— F        G

解释：

firstChild 指针（纵向）：指向该节点的第一个子节点。

节点 A 的 firstChild 指向 B。
节点 B 的 firstChild 指向 E。
节点 D 的 firstChild 指向 G。

nextSibling 指针（横向）：指向该节点的下一个兄弟节点。

节点 B 的 nextSibling 指向 C。
节点 C 的 nextSibling 指向 D。
节点 E 的 nextSibling 指向 F

四、对于二叉树的链式存储

二叉树是一种特殊的树，每个节点最多有两个子节点（左孩子和右孩子）。它的链式存储结构更为简单：

// 二叉树的链式存储节点  typedef struct BiTNode {      int data;                // 数据域      struct BiTNode *lchild;  // 指向左子节点的指针      struct BiTNode *rchild;  // 指向右子节点的指针  } BiTNode;

对于二叉树：

      A       / \      B   C     / \   \    D   E   F

其链式存储的逻辑关系非常直观：

A 的 lchild 指向 B，rchild 指向 C。
B 的 lchild 指向 D，rchild 指向 E。
C 的 lchild 为空，rchild 指向 F

2025年10月07日

【题解】舞蹈机器人

题目描述

在一个拥有无限大小的二维平面的原点处，有一个舞蹈机器人，这个机器人将在这个平面上跳舞。

这个机器人每次可以向自己的前方移动一个单位的长度，由于它需要在移动的过程中跳舞，因此，舞蹈机器人每移动一次，就必须向左或右方向旋转，即如果此次机器人往上或下方向进行了一次移动，那么，下一次就只能往左或右方向进行一次移动。最开始时，它可以选择上下左右四个方向中的任意一个作为初始方向。

现在，机器人根据上述规则一共移动了步，请问，机器人最终可以到达多少个不同的终点？机器人到达终点时的方向可以忽略。

输入格式

输入共一行，包含一个整数，表示机器人总共移动的步数。

输出格式

输出共一行，包含一个整数，表示机器人最终能够到达的不同终点的个数。

样例 1 输入

样例 1 输出

样例 1 解释

因为总共只移动了一次，则有上下左右四个方向的四个答案。

样例 2 输入

样例 2 输出

样例 2 解释

因为总共会移动两次，且第二次的方向必须向左或向右旋转，因此，最终能到的终点只有原点左上、右上、左下、右下四个与原点距离为的点。