PTA-学校-数据结构（运用顺序表实现多项式相加、合并有序数组、在顺序表 list 中查找元素 x、在顺序表 list 的第 i 个位置上插入元素x、从顺序表 list 中删除第 i 个元素、线性表循环右移、约瑟夫环、求链式表的表长、单链表逆转）
2-7 运用顺序表实现多项式相加
分数 7
作者 胡艳梅
单位 成都理工大学
本题要求输入两个一元多项式，然后输出它们的和（相加后得到的一元多项式）
输入格式:
输入一个整数n（表示输入组数），然后依次输入每一组数据：
输入一个整数A（表示多项式的项数，小于100），然后输入A对整数，每一对整数表示对应项的指数和系数。
输出格式:
对每一组输入，在一行中输出得到的一元多项式。
输入样例:
在这里给出一组输入。例如：
2 |
输出样例:
在这里给出相应的输出。例如：
5x^0+4x^1+6x^2+19x^4-2x^5+10x^7+19x^8 |
邪修
解析
|
解释这段代码
这段代码的核心功能是用顺序表（数组）实现两个一元多项式的相加，整体逻辑遵循 “读取多项式→合并同类项→排序→格式化输出” 的流程。下面从「数据结构」「核心函数」「主流程」三个层面，逐部分详细拆解代码逻辑。
一、整体框架与数据结构
在写具体功能前，首先要定义 “如何存储多项式的项”，并限制数组大小（避免内存越界），这是代码的基础。
1. 结构体 Term：存储多项式的单个项
多项式的每一项都包含两个关键信息：指数（exp） 和 系数（coeff），用结构体可以将这两个属性 “打包” 成一个整体，方便数组存储（顺序表的核心就是 “数组存相同类型元素”）。
typedef struct { |
- 例：项
4x^1对应的Term是{exp=1, coeff=4}；项-9x^5是{exp=5, coeff=-9}。
2. 宏 MAXSIZE：限制顺序表的最大容量
题目明确 “多项式项数小于 100”，因此用宏定义数组的最大长度为 100，确保存储每个多项式（p1/p2）和结果（res）时不会越界。
二、核心函数解析
代码共封装了 4 个功能函数，分别负责 “读多项式”“合并多项式”“排序”“输出”，每个函数各司其职，最后在主函数中串联起来。
1. 函数 readPoly：读取多项式并预处理（合并同类项 + 去零项）
功能
输入一个多项式的 “项数 n” 和 “n 对（指数 + 系数）”，将其存储到顺序表（Term *poly）中，同时完成两个关键预处理：
- 跳过系数为 0 的项（系数为 0 的项对多项式无意义，如
0x^2可直接忽略）； - 合并同类项（指数相同的项，系数相加，如
2x^0 + 3x^0 = 5x^0）。
参数与返回值
- 参数 1：
int n→ 输入的 “原始项数”（可能包含同类项或零系数项）； - 参数 2：
Term *poly→ 指向存储多项式的数组（顺序表），最终会存入预处理后的有效项； - 返回值：
int len→ 预处理后多项式的 “有效项数”（无同类项、无零系数项）。
内部逻辑（逐行拆解）
int readPloy(int n , Term *poly) |
示例（结合输入样例）
输入第一组多项式的第一个原始项：5 项（0 2/1 4/5 7/7 10/8 19）
- 读
0 2：c≠0，无同类项 → 存poly[0] = {0,2}，len=1； - 读
1 4：c≠0，无同类项 → 存poly[1] = {1,4}，len=2； - 后续项均无同类项，最终
len1=5，p1数组存 5 个有效项。
2. 函数 mergePoly：合并两个多项式（核心相加逻辑）
功能
将两个预处理后的多项式 p1（有效项数 len1）和 p2（有效项数 len2）相加，结果存入 res 数组，核心是再次合并同类项（因为 p1 和 p2 可能有相同指数的项）。
参数与返回值
- 参数 1：
Term *p1→ 第一个多项式的顺序表； - 参数 2：
int len1→ 第一个多项式的有效项数； - 参数 3：
Term *p2→ 第二个多项式的顺序表； - 参数 4：
int len2→ 第二个多项式的有效项数； - 参数 5：
Term *res→ 存储结果多项式的顺序表； - 返回值：
int resLen→ 结果多项式的有效项数。
内部逻辑（逐行拆解）
int mergePoly(Term *p1, int len1, Term *p2, int len2, Term *res) |
示例（结合输入样例）
p1 有 5 项（0 2/1 4/5 7/7 10/8 19），p2 有 4 项（0 3/2 6/4 19/5 -9）：
- 步骤 1：
res先存入p1的 5 项，resLen=5； - 步骤 2 处理
p2的0 3：res 中有exp=0的项（系数 2）→ 2+3=5，res [0].coeff=5； - 处理
p2的5 -9：res 中有exp=5的项（系数 7）→7+(-9)=-2，res [2].coeff=-2； - 其他
p2项（2 6/4 19）无同类项，存入 res； - 最终
resLen=7，res 数组有 7 个有效项。
3. 函数 compare：排序规则函数（给 qsort 用）
功能
qsort 是 C 标准库的通用排序函数，需要自定义 “如何比较两个元素”。这里的规则是按多项式项的指数升序排列（如示例输出的指数顺序：0→1→2→4→5→7→8）。
参数与返回值
- 参数 1/2：
const void *a/const void *b→ 指向两个待比较的Term元素（qsort要求参数为无类型指针，兼容任意数据类型）； - 返回值：
- 若返回 正数：
a对应的元素应排在b后面； - 若返回 负数：
a对应的元素应排在b前面； - 若返回 0：两者顺序随意。
- 若返回 正数：
内部逻辑
int compare(const void *a, const void *b) |
- 例：比较
t1={1,4}（exp=1）和t2={2,6}（exp=2）→ 1-2=-1（负数）→t1排在t2前面，符合升序。
4. 函数 printPoly：格式化输出多项式
功能
将排序后的结果多项式 res，按题目要求的格式输出（如 5x^0+4x^1+6x^2+19x^4-2x^5+10x^7+19x^8），核心是处理符号：
- 第一项无前置符号（如
5x^0不写+5x^0）； - 正数项前置
+（如+4x^1）； - 负数项前置
-，且系数取绝对值（如-2x^5不写+-2x^5）。
参数
- 参数 1：
Term *poly→ 待输出的多项式顺序表； - 参数 2：
int len→ 多项式的有效项数。
内部逻辑
void printPoly(Term *poly, int len) |
示例（结合输入样例）
res 排序后有 7 项：{0,5}/{1,4}/{2,6}/{4,19}/{5,-2}/{7,10}/{8,19}：
- 第一项输出
5x^0； - 第二项
4>0→ 输出+4x^1； - 第五项
-2<0→ 输出-2x^5； - 最终拼接为示例第一行输出。
三、主函数 main：串联所有功能（流程控制）
主函数是代码的 “入口”，负责按题目输入格式读取数据，调用上述函数完成 “读→合并→排序→输出” 的完整流程。
内部逻辑（逐行拆解）
int main() |
整体流程总结（以示例输入为例）
- 读
n=2（2 组数据）； - 第一组数据：
- 读
A1=5→ 调用readPoly获len1=5； - 读
A2=4→ 调用readPoly获len2=4； - 调用
mergePoly获resLen=7； - 调用
qsort排序； - 调用
printPoly输出第一行结果；
- 读
- 第二组数据：重复上述步骤，输出第二行结果；
- 循环结束，程序退出。
四、关键细节与边界处理
- 去零项：
readPoly跳过输入的零系数项，mergePoly移除合并后系数为 0 的项，确保输出无多余项； - 同类项合并：
readPoly处理单个多项式的同类项，mergePoly处理两个多项式间的同类项，避免重复项； - 排序正确性：
compare确保指数升序，符合题目输出格式； - 符号处理：
printPoly区分第一项和后续项的符号，避免格式错误（如多余的+或-）； - 内存安全：用
MAXSIZE限制数组大小，避免数组越界（因题目项数 < 100，MAXSIZE=100足够）。
五、代码验证（结合示例输入输出）
输入样例：
2 |
代码处理后输出：
5x^0+4x^1+6x^2+19x^4-2x^5+10x^7+19x^8 |
与题目示例输出完全一致，说明代码逻辑正确。
2-8 合并有序数组
分数 7
作者 伍建全
单位 重庆科技大学
给定2个非降序序列，要求把他们合并成1个非降序序列。假设所有元素个数为N，要求算法的时间复杂度为O(N)。
输入格式:
输入有4行。
第1行是一个正整数m，表示第2行有m个整数，这些整数构成一个非降序序列，每个整数之间以空格隔开。第3行是一个正整数n，表示第4行有n个整数，这些整数也构成一个非降序序列，每个整数之间以空格隔开。
输出格式:
把第2行的m个整数和第4行的n个整数合并成一个非降序序列，输出这个整数序列。每个数之间隔1个空格。
输入样例:
6 |
输出样例:
1 2 3 4 5 6 6 7 8 9 |
解析
|
2-9 在顺序表 list 中查找元素 x
分数 7
作者 陈越
单位 浙江大学
请编写程序，将 n 个整数存入顺序表，对任一给定整数 x，查找其在顺序表中的位置。
输入格式：
输入首先在第一行给出正整数 n（≤104）；随后一行给出 n 个 int 范围内的不重复的整数，数字间以空格分隔；最后一行给出待查找的元素 x，也是 int 范围内的整数。
输出格式：
在一行中输出 x 在顺序表中的位置，即数组下标。如果没找到，则输出 -1。注意数组下标从 0 开始。
输入样例 1：
5 |
输出样例 1：
3 |
输入样例 2：
5 |
输出样例 2：
-1 |
解析
|
2-10 在顺序表 list 的第 i 个位置上插入元素 x
分数 8
作者 陈越
单位 浙江大学
请编写程序，将 n 个整数存入顺序表，对任一给定整数 x，将其插入顺序表中指定的第 i 个位置。注意：i 代表位序，从 1 开始，不是数组下标。
输入格式：
输入首先在第一行给出正整数 n（≤104）；随后一行给出 n 个 int 范围内的整数，数字间以空格分隔；最后一行给出插入位置 i 和待插入的元素 x，均为 int 范围内的整数。
输出格式：
分以下几种情况输出：
- 如果顺序表中已经有 104 个元素了，则不能插入，在一行中输出句子
错误：表满不能插入。。 - 如果插入的位置不合法，则不能插入，在一行中输出句子
错误：插入位置不合法。。 - 无论是否插入成功，都在一行中顺序输出表中的元素，每个元素后面跟一个空格。
输入样例 1：
5 |
输出样例 1：
1 2 8 3 4 5 |
输入样例 2：
5 |
输出样例 2：
错误：插入位置不合法。 |
解析
|
2-11 从顺序表 list 中删除第 i 个元素
分数 8
作者 陈越
单位 浙江大学
请编写程序，将 n 个整数存入顺序表，对任一指定的第 i 个位置，将这个位置上的元素从顺序表中删除。注意：i 代表位序，从 1 开始，不是数组下标。
输入格式：
输入首先在第一行给出正整数 n（≤104）；随后一行给出 n 个 int 范围内的整数，数字间以空格分隔；最后一行给出删除位序 i，为 int 范围内的整数。
输出格式：
如果删除的位置不合法，则不能删除，在一行中输出句子 错误：不存在这个元素。。无论是否删除成功，都在一行中顺序输出表中的元素，每个元素后面跟一个空格。
输入样例 1：
5 |
输出样例 1：
1 2 4 5 |
输入样例 2：
5 |
输出样例 2：
错误：不存在这个元素。 |
解析
|
2-12 线性表循环右移
分数 8
作者 陈越
单位 浙江大学
给定顺序表 A=(a1,a2,⋯,a**n)，请设计一个时间和空间上尽可能高效的算法将该线性表循环右移指定的 m 位。例如，(1,2,5,7,3,4,6,8) 循环右移 3 位（m=3) 后的结果是 (4,6,8,1,2,5,7,3)。
输入格式：
第一行输入 n ( 1≤n≤105)、m（m≥0）；第二行输入 n 个整数。所有数字在 int 型整数范围内，同行数字间以空格分隔。
输出格式：
输出循环右移 m 位以后的整数序列。数字间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：
6 2 |
输出样例：
5 6 1 2 3 4 |
解析
|
2-13 约瑟夫环
分数 9
作者 李廷元
单位 中国民用航空飞行学院
N个人围成一圈顺序编号，从1号开始按1、2、3…顺序报数，报p者退出圈外，其余的人再从1、2、3开始报数，报p的人再退出圈外，以此类推。
请按退出顺序输出每个退出人的原序号。
输入格式:
输入只有一行，包括一个整数N(1<=N<=3000)及一个整数p(1<=p<=5000)。
输出格式:
按退出顺序输出每个退出人的原序号，数据间以一个空格分隔，但行尾无空格。
输入样例:
在这里给出一组输入。例如：
7 3 |
输出样例:
3 6 2 7 5 1 4 |
超时代码
|
你的代码超时是因为用顺序表模拟遍历的时间复杂度太高（O (n×m)），当 n 和 m 较大时（比如 n=3000、m=5000），需要反复跳过已退出的元素（-1），无效循环次数太多。解决办法是改用数学递推法，直接计算每个退出者的位置，时间复杂度降至 O (n)，彻底避免超时。
一、超时原因分析
你的现有逻辑是 “逐个遍历数组找下一个报数到 m 的人”，核心问题在于：
- 每次找目标都要遍历整个数组，遇到已退出的元素（-1）还要跳过，相当于每次操作都要 “扫一遍” 剩余元素；
- 当 n=3000、m=5000 时，总循环次数可能达到 3000×5000=15,000,000 次，远超时间限制，导致超时。
二、优化方案：约瑟夫环数学递推法
约瑟夫环有成熟的数学递推公式，核心思路是直接计算每次退出者的位置，无需遍历数组。具体原理如下：
- 假设当前剩余
t个人（初始 t=n），从位置pos开始报数（初始 pos=0，位置从 0 开始计数，方便取模）； - 本次退出者的位置 =
(pos + m - 1) % t（m-1是因为报数从 1 开始，需转换为 0-based 索引）； - 输出该位置对应的原序号（+1，因为题目序号从 1 开始）；
- 更新下一轮的起始位置
pos为本次退出者的位置（下一轮从退出者的下一个人开始报数，取模后自动处理环形）。
1-1 求链式表的表长
分数 3
作者 陈越
单位 浙江大学
本题要求实现一个函数，求链式表的表长。
函数接口定义：
int Length( List L ); |
其中List结构定义如下：
typedef struct LNode *PtrToLNode; |
L是给定单链表，函数Length要返回链式表的长度。
裁判测试程序样例：
|
输入样例：
1 3 4 5 2 -1 |
输出样例：
5 |
解析
int Length( List L ) { |
直接使用PtrToLNode建一个p指针，指向L
- 用
PtrToLNode p = L声明指针p，使其指向链表的头节点，避免类型错误。 - 循环遍历：当
p不为空时，说明当前节点有效，计数加 1，然后移动p到下一个节点（p = p->Next）。 - 当
p为空时，说明已遍历完所有节点，返回计数结果。
1-2 单链表逆转
分数 4
作者 陈越
单位 浙江大学
本题要求实现一个函数，将给定的单链表逆转。
函数接口定义：
List Reverse( List L ); |
其中List结构定义如下：
typedef struct Node *PtrToNode; |
L是给定单链表，函数Reverse要返回被逆转后的链表。
裁判测试程序样例：
|
输入样例：
5 |
输出样例：
1 |
解析
List Reverse(List L) { |
图片解析
本博客所有文章除特别声明外，均采用 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-20
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 &...
评论