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...
Hello World
Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub. Quick Start Create a new post $ hexo new "My New Post" More info: Writing Run server $ hexo server More info: Server Generate static files $ hexo generate More info: Generating Deploy to remote sites $ hexo deploy More info: Deployment
PTA-学校-数据结构（头插法创建单链表、两个有序链表序列的合并、删除排序链表中的重复元素、求链表的倒数第m个元素、共享后缀的链表、单链表分段逆转、一元多项式求导）
1-5 头插法创建单链表（C） 分数 7 作者 李廷元 单位 中国民用航空飞行学院 本题要求实现两个函数，输入n个数据，采用头插法创建单链表并打印。例如：如果输入4 ，再输入3 7 9 5，则应打印输出5 9 7 3。 链表结点结构定义： struct Node { //链表结点 int data; //数据 struct Node* link; //指向下一个结点的指针}; 函数接口定义： /* 头插法建立单链表：返回单链表的头指针 */struct Node* buildLinkedList(int* arr, int n); /* 头插法建立单链表 */void printLinkedList(struct Node* head); /* 打印链表 */ 其中arr和n是用户传入的参数，n的值不超过100000。head为单链表的头指针。 裁判测试程序样例： #include <stdio.h>#include <stdlib.h>//malloc函数struct Node &...
PTA-学校-数据结构（删除链表中的元素）
1-4 删除链表中的元素 分数 7 作者 李廷元 单位 中国民用航空飞行学院 本题要求删除链表中等于给定值val的所有节点。链表ListNode的定义已经给出。要求给出函数removeElements的实现。 函数接口定义： /** head为链表头指针；val为需要删除的值。* 函数返回值为删除val后的链表的头指针。*/struct ListNode* removeElements(struct ListNode* head, int val);/* 创建链表，细节不表 */struct ListNode* buildList();/* 打印链表，细节不表 */void printList(struct ListNode* head); 裁判测试程序样例： #include<stdio.h>#include<stdlib.h>#include<string.h>/** * Definition of ListNode */struct ListNode{ int val; struct ListNode *next;&...
PTA-学校-数据结构（递增的整数序列链表的插入）
1-3 递增的整数序列链表的插入 分数 4 作者 DS课程组 单位 浙江大学 本题要求实现一个函数，在递增的整数序列链表（带头结点）中插入一个新整数，并保持该序列的有序性。 函数接口定义： List Insert( List L, ElementType X ); 其中List结构定义如下： typedef struct Node *PtrToNode;struct Node { ElementType Data; /* 存储结点数据 */ PtrToNode Next; /* 指向下一个结点的指针 */};typedef PtrToNode List; /* 定义单链表类型 */ L是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Insert要将X插入L，并保持该序列的有序性，返回插入后的链表头指针。 裁判测试程序样例： #include <stdio.h>#include <stdlib.h>typedef int ElementType;typedef struct Node *PtrToNode;st...