数据结构线性表KMP算法
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 好的好的378的博客！
相关推荐
2025-10-13
PTA-学校-数据结构（两个有序序列的中位数、数组循环左移）
2-1 两个有序序列的中位数 分数 6 作者 DS课程组 单位 浙江大学 已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A0,A1,⋯,A**N−1的中位数指A(N−1)/2的值,即第⌊(N+1)/2⌋个数（A0为第1个数）。 输入格式: 输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。 输出格式: 在一行中输出两个输入序列的并集序列的中位数。 输入样例1: 51 3 5 7 92 3 4 5 6 输出样例1: 4 输入样例2: 6-100 -10 1 1 1 1-50 0 2 3 4 5 输出样例2: 1 解析 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 100000typedef int ElemType;typedef ElemType * list;typedef struct{ ElemType * data; int lengh; ...
2025-10-14
PTA-学校-数据结构（最长连续递增子序列）
2-3 最长连续递增子序列 分数 6 作者 DS课程组 单位 浙江大学 给定一个顺序存储的线性表，请设计一个算法查找该线性表中最长的连续递增子序列。例如，(1,9,2,5,7,3,4,6,8,0)中最长的递增子序列为(3,4,6,8)。 输入格式: 输入第1行给出正整数n（≤105）；第2行给出n个整数，其间以空格分隔。 输出格式: 在一行中输出第一次出现的最长连续递增子序列，数字之间用空格分隔，序列结尾不能有多余空格。 输入样例： 151 9 2 5 7 3 4 6 8 0 11 15 17 17 10 输出样例： 3 4 6 8 解析 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 100000typedef int ElemType;typedef struct { ElemType *data; int length; int size;}SqList;int main(){ SqList L; L.data = (ElemType...
2025-10-13
PTA-学校-数据结构（顺序表操作集、数组元素的区间删除）
1-1 顺序表操作集 分数 5 作者 陈越 单位 浙江大学 本题要求实现顺序表的操作集。 函数接口定义： List MakeEmpty(); Position Find( List L, ElementType X );bool Insert( List L, ElementType X, Position P );bool Delete( List L, Position P ); 其中List结构定义如下： typedef int Position;typedef struct LNode *List;struct LNode { ElementType Data[MAXSIZE]; Position Last; /* 保存线性表中最后一个元素的位置 */}; 各个操作函数的定义为： List MakeEmpty()：创建并返回一个空的线性表； Position Find( List L, ElementType X )：返回线性表中X的位置。若找不到则返回ERROR； bool Insert( List L, ElementType X, P...
2025-10-15
PTA-学校-数据结构（在指定位置插入元素、集合减法、顺序表（删除））
2-4 在指定位置插入元素 分数 6 作者 张志梅 单位 青岛大学 给出 n 个整数，在指定位置 pos（位置从1起始）前插入给定的值 val，请输出插入后的整数序列。 输入格式: 包含多组测试。第一行会有一个 T 表示组数 (1<=T<=20)，每组测试的第一行输入三个数 n , pos , val，第二行输入n个整数。其中，1<=n<=100，1<=pos<=n+1，1<=val<=100。 输出格式: 每组测试输出包含一行，行末不允许有多余的空格。 输入样例: 25 1 41 2 3 4 56 3 92 4 6 8 0 2 输出样例: 4 1 2 3 4 52 4 9 6 8 0 2 解析 #include <stdio.h>#include <stdlib.h>typedef int ElemType;#define MAXSIZE 100typedef struct{ ElemType *data; int length; int size;} SqList;i...
2025-10-17
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...
2025-10-16
PTA-学校-数据结构（运用顺序表实现多项式相加、合并有序数组、在顺序表 list 中查找元素 x、在顺序表 list 的第 i 个位置上插入元素x、从顺序表 list 中删除第 i 个元素、线性表循环右移、约瑟夫环、求链式表的表长、单链表逆转）
2-7 运用顺序表实现多项式相加 分数 7 作者 胡艳梅 单位 成都理工大学 本题要求输入两个一元多项式，然后输出它们的和（相加后得到的一元多项式） 输入格式: 输入一个整数n（表示输入组数），然后依次输入每一组数据： 输入一个整数A（表示多项式的项数，小于100），然后输入A对整数，每一对整数表示对应项的指数和系数。 输出格式: 对每一组输入，在一行中输出得到的一元多项式。 输入样例: 在这里给出一组输入。例如： 250 21 45 77 108 1940 32 64 195 -930 34 78 230 -35 97 21 输出样例: 在这里给出相应的输出。例如： 5x^0+4x^1+6x^2+19x^4-2x^5+10x^7+19x^87x^4+9x^5+21x^7+2x^8 邪修 解析 #include <stdio.h>#include <stdlib.h>typedef struct { int exp; int coeff;}Term;#define MAXSIZE 100int readPloy(int ...
评论