PTA-学校-数据结构（带头结点的链队列的基本操作、循环队列入队出队、另类循环队列、舞伴问题）
1-5 带头结点的链队列的基本操作 分数 4 作者 黄复贤 单位 菏泽学院 实现链队列的入队列及出队列操作。 函数接口定义： Status QueueInsert(LinkQueue *Q,ElemType e)；Status QueueDelete(LinkQueue *Q,ElemType *e)； 其中 Q 和 e 都是用户传入的参数。 LinkQueue 的类型定义如下： typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode * next;}LNode,*LinkList;typedef struct { LinkList front,rear; /* 队头、队尾指针 */ }LinkQueue; 裁判测试程序样例： #include <stdio.h>#include<malloc.h>#define OK 1#define ERROR 0typedef int Status;typedef int E...
PTA-学校-数据结构（括号匹配、进制转换、用链栈实现将非负的十进制数转换为指定的进制数、在一个数组中实现两个堆栈）
1-1 括号匹配 分数 4 作者 黄龙军 单位 绍兴文理学院 要求实现函数，借助如下自定义栈SqStack判断一个中、小括符[、]、(、)组成的字符串中的括弧是否匹配，是则返回true，否则返回false。例如，[[()]]、([[()]])、(()[[]])是匹配的，而(((、()]、 ([(]))是不匹配的。 typedef char ElemType; // 为char取别名ElemTypestruct SqStack{ ElemType *base; // 顺序栈的首地址，动态数组的首地址 int top; // 栈顶指针，栈非空时，为栈顶元素的下标(从0开始) void Init( ); // 初始化栈 ElemType GetTop(); // 取栈顶元素 void Push(ElemType e)...
约瑟夫环的数学解法
#include <stdio.h>int main(){ int N, p; scanf("%d %d", &N, &p); int people[3001] = { 0 }; int i; for (i = 0; i < 3001; i++) { people[i] = i; } int k = N; int start = 1; int flag = 1; while (k > 0) { int pos = (start + p - 2) % k + 1; if (flag == 1) { printf("%d", people[pos]); flag = 0; } else { printf(" %d", people[pos]); } for (i = pos; i < k; i++) { people[i] = people...
数据结构遍历二叉树中序遍历的技巧
二叉树中序遍历总结（含栈的深度理解 一、什么是二叉树中序遍历 中序遍历的核心规则是 “左 - 根 - 右”：先中序遍历左子树，再访问根节点，最后中序遍历右子树。 以简单二叉树（根A，左孩子B，右孩子C）为例，中序遍历结果为 B → A → C（即BAC）。 二、普通递归方法（基于修正后的二叉树结构） 修正后的二叉树结构： A / \ B C / / \ D E F / \ \G H I 递归逻辑：通过 “函数调用栈” 隐式实现 “左 - 根 - 右” 的顺序。每调用一次遍历函数，就将当前节点压入系统栈，先处理左子树，再访问根，最后处理右子树。 步骤拆解： 遍历A的左子树B → 遍历B的左子树D → 遍历D的左子树G（无左子树，访问G）→ 访问D → 遍历D的右子树H（访问H）→ 访问B → 访问A → 遍历A的右子树C → 遍历C的左子树E（无左子树，访问E）→ 遍历E的右子树I（访问I）→ 访问C → 遍历C的右子树F（访问F）。 最终结果：GDHBAEICF。 三、非递归方法（显式栈模拟） 递归的本质是系统栈...
PTA-学校-数据结构（反转链表、单链表逆置、约瑟夫环、 2-10 在单链表 list 的第 i 个位置上插入元素 x）
2-7 反转链表 分数 3 作者 黄正鹏 单位 贵州工程应用技术学院 给定一个常数 K 和一个单链表 L，请你在单链表上每 K 个元素做一次反转，并输出反转完成后的链表。 如果链表最后一部分不足 K 个元素，则最后一部分不翻转。 例如，假设 L 为 1→2→3→4→5→6，如果 K=3，则你应该输出 3→2→1→6→5→4；如果 K=4，则你应该输出 4→3→2→1→5→6 。 补充： 本题中可能包含不在链表中的节点，这些节点无需考虑。 输入格式: 第一行包含头节点地址，总节点数量 N 以及常数 K。1≤N≤10^5 ,1≤K≤N 节点地址用一个 5 位非负整数表示（可能有前导 0），NULL 用 −1 表示。 接下来 N 行，每行描述一个节点的信息，格式如下： Address Data Next 其中 Address 是节点地址，Data 是一个整数，Next 是下一个节点的地址。 输出格式: 将重新排好序的链表，从头节点点开始，依次输出每个节点的信息，格式与输入相同。 输入样例: 00100 6 400000 4 9999900100 1 1230968237 6 -133...
PTA-学校-数据结构（链表去重、两个有序链表合并）
2-5 链表去重 分数 5 作者 陈越 单位 浙江大学 给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。 输入格式： 输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤105，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 -1 来表示。 随后 N 行，每行按以下格式描述一个结点： 地址 键值 下一个结点 其中地址是该结点的地址，键值是绝对值不超过104的整数，下一个结点是下个结点的地址。 输出格式： 首先输出去重后的链表，然后输出被删除的链表。每个结点占一行，按输入的格式输出。 输入样例： 00100 599999 -7 8765423854 -15 0000087654 15 -100000 -15 9999900100 21 23854 输出样例： 00100 21 2385423854 -1...
PTA-学校-数据结构（求链式线性表的倒数第K项、两个有序链表序列的合并、两个有序链表序列的交集）
2-2 求链式线性表的倒数第K项 分数 5 作者 DS课程组 单位 浙江大学 给定一系列正整数，请设计一个尽可能高效的算法，查找倒数第K个位置上的数字。 输入格式: 输入首先给出一个正整数K，随后是若干非负整数，最后以一个负整数表示结尾（该负数不算在序列内，不要处理）。 输出格式: 输出倒数第K个位置上的数据。如果这个位置不存在，输出错误信息NULL。 输入样例: 4 1 2 3 4 5 6 7 8 9 0 -1 输出样例: 7 解析 #include <stdio.h>#include <stdlib.h>typedef int ElemType;typedef struct LNode { ElemType data; struct LNode* next;}LNode,* LinkList;int main() { int n; scanf ("%d", &n); if (n <= 0) { printf ("NULL&qu...