题目集总目录 学习笔记指路博客 线性表、堆栈
02-线性结构1 两个有序链表序列的合并 (15分)
本题链接
这是一道C语言函数填空题，训练最基本的链表操作。如果会用C编程的话，一定要做；
代码
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode List;
List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表；空链表将输出NULL */
List Merge( List L1, List L2 );
int main()
{
List L1, L2, L;
L1 = Read();
L2 = Read();
L = Merge(L1, L2);
Print(L);
Print(L1);
Print(L2);
return 0;
}
/* 你的代码将被嵌在这里 */
List Merge( List L1, List L2 ) {
List p1,p2,p3,T;
T = (List) malloc(sizeof(struct Node));
p3 = T;
p1 = L1->Next;
p2 = L2->Next;
while (p1 && p2) { //p1和p2都存在时
if (p1->Data <= p2->Data) {
p3->Next = p1;
p3 = p3->Next;
p1 = p1->Next;
} else {
p3->Next = p2;
p3 = p3->Next;
p2 = p2->Next;
}
}
if (p1) {//哪个还存在哪个后边的就全接到p3上
p3->Next = p1;
} else p3->Next = p2;
L1->Next = NULL;
L2->Next = NULL;
return T;
}
测试点
测试点如下
02-线性结构2 一元多项式的乘法与加法运算 (20分)
本题链接
这是一道C语言函数填空题，训练最基本的链表操作。如果会用C编程的话，一定要做；
思路
思路: 用带头结点的链表存储, 加法运算时: 若p1和p2(加法的两链表指针)指数比较后有一方较大，则将那一方直接放到p3中(尾插)，然后较大方的指针后移，若指数相同则合并同类项后再插入，注意若系数为0则不将其插入直接两指针后移，最后若还有一方后边有则直接接到L3后，最后要检查L3为不为空，若为空则插入零多项式。 乘法运算时： 先用L1中的每一项乘L2的第一项得一个多项式，再用L2中从第二项开始的每一项乘以L1一整个多项式(边乘边比较并插入),或利用加函数(但我用的时候超时了…所以没用)，最后也要检查L3为不为空，若为空则插入零多项式 ps：合并同类项的时候若系数合成0了，要删掉！
代码
#include <iostream>
using namespace std;
typedef int ElementType;
typedef struct LNode* List;
struct LNode {
ElementType factor; //系数
ElementType exmt; //指数
List next;
};
void Make_EmptyList(List Head) {
Head = new LNode;
Head->exmt = 0;
Head->factor = 0;
Head->next = NULL;
}
void E_Insert(List Head, ElementType f, ElementType e) {//尾插法插入
if(!Head) {
Make_EmptyList(Head);
}
List s = Head;
while (s->next) {//保证s是最后一个
s = s->next;
}
List p = new LNode;
p->factor = f;
p->exmt = e;
p->next = NULL;
s->next = p;
}
void H_Insert(List Head, ElementType f, ElementType e) {//头插法插入
if(!Head) {
Make_EmptyList(Head);
}
List p = new LNode;
p->factor = f;
p->exmt = e;
p->next = Head->next;
Head->next = p;
}
void PrintList(List Head) {
List p = Head->next;
cout << p->factor << " " << p->exmt;
p = p->next;
while (p) {
cout << " " << p->factor << " " << p->exmt;
p = p->next;
}
cout << endl;
}
void Clear_List(List Head) {
List p1 = Head->next;
while(p1){
List p2 = p1->next;
delete p1;
p1 = p2;
}
}
List AddList(List L1, List L2) {
if (!L1->next) return L2;
if (!L2->next) return L1;
List A = new LNode;
A->next = NULL;
List p1 = L1->next;
List p2 = L2->next;
if(p1->exmt == 0 && p1->factor == 0) return L2;
if(p2->exmt == 0 && p2->factor == 0) return L1;
List p3 = A;
while (p1 && p2) {
if (p1->exmt > p2->exmt) {
if(p1->factor != 0)
E_Insert(A, p1->factor, p1->exmt);
p1 = p1->next;
}
else if (p1->exmt < p2->exmt) {
if(p2->factor != 0)
E_Insert(A, p2->factor, p2->exmt);
p2 = p2->next;
} else { //p1->exmt == p2->exmt
int f = p1->factor + p2->factor;
int e = p1->exmt;
if(f != 0)
E_Insert(A, f, e);
p1 = p1->next;
p2 = p2->next;
}
}
while (p3->next) {
p3 = p3->next;
}
if (p1) {//哪个还存在哪个后边的就全接到p3上
p3->next = p1;
} else p3->next = p2;
if(!A->next) {
E_Insert(A, 0, 0);
}
return A;
}
List MultiplyList(List L1, List L2) {
List L3 = new LNode;
L3->next = NULL;
List p1 = L1->next;
List p2 = L2->next;
List p3 = L3->next;
if (!p1 || !p2) {
E_Insert(L3, 0, 0);
return L3;
}
while (p1) { //L1中的每一项乘L2的第一项
int f, e;
f = p1->factor * p2->factor;
e = p1->exmt + p2->exmt;
if(f != 0)
E_Insert(L3, f, e);
p1 = p1->next;
}
// L2中的每一项乘以L1中一整个多项式
while (p2->next) { //L2中的每项p2
p1 = L1->next;
p2 = p2->next;
while (p1) { //L1中的每一项 * p2
int f, e;
f = p1->factor * p2->factor;
e = p1->exmt + p2->exmt;
if(f == 0) {
p1 = p1->next;
continue;
}
p3 = L3;
while (p3->next && p3->next->exmt > e) {
p3 = p3->next;
}
List np = p3->next;//np->exmt <= e
if (!np) {
np = new LNode;
np->exmt = e;
np->factor = f;
np->next = NULL;
p3->next = np;
}
else if (np->exmt < e) {
List p = new LNode;
p->exmt = e;
p->factor = f;
p->next = np;
p3->next = p;
}
else {
np->factor += f;
if(np->factor == 0) {//合并同类项后为0 删除这个
p3->next = np->next;
delete np;
}
} //np->exmt == e
p1 = p1->next;
}
}
if(!L3->next) {
E_Insert(L3, 0, 0);
}
return L3;
}
int main() {
List L1, L2, L3, L4;
int n1, n2, f, e;
cin >> n1;
L1 = new LNode;
L1->next = NULL;
L2 = new LNode;
L2->next = NULL;
L3 = new LNode;
L3->next = NULL;
L4 = new LNode;
L4->next = NULL;
for (int i = 0; i < n1; ++i) {
cin >> f >> e;
E_Insert(L1, f, e);
}
cin >> n2;
for (int i = 0; i < n2; ++i) {
cin >> f >> e;
E_Insert(L2, f, e);
}
L3 = MultiplyList(L1, L2);
L4 = AddList(L1, L2);
PrintList(L3);
PrintList(L4);
return 0;
}
测试点
测试点如下，虽然少但却卡了我半天2333
02-线性结构3 Reversing Linked List (25分)
本题链接
根据某大公司笔试题改编的2014年春季PAT真题，不难，可以尝试；
题目大意
给定一个常量K和链表L,你应该反转L上每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 (≤10^5),一个正K (≤N)它是要反转的子列表的长度。 节点的地址是5位非负整数，NULL由-1表示。 然后是N行，每行描述如下格式：Address Data Next 其中Address是节点的位置，Data是整数，Next是下一个节点的位置。 输出规格： 对于每种情况，输出生成的有序链接列表。每个节点占据一条线，并且以与输入相同的格式打印。
示例输入：
00100 6 4 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218
示例输出：
00000 4 33218 33218 3 12309 12309 2 00100 00100 1 99999 99999 5 68237 68237 6 -1
思路
用结构体存数据，用数组存储下标索引，翻转时只需翻转数组元素，可利用algorithm库中的reverse函数
代码
#include <iostream>
#include <algorithm>
using namespace std;
#define maxsize 100002
struct LNode {
int Data;
int Next;
}a[maxsize];
int list[maxsize];//每个结点的地址
int Head,N,K,p;//第一个节点地址,所有结点数,翻转子序列长度
int main() {
cin >> Head >> N >> K;
list[0] = Head;
for(int i = 0; i < N; ++i) {
int index, data, next;
cin >> index >> data >> next;
a[index].Data = data;
a[index].Next = next;
}
p = a[Head].Next;
int sum = 1;
while(p != -1) {
list[sum++] = p;
p = a[p].Next;
}
int j = 0;
while(j + K <= sum) {
reverse(&list[j], &list[j+K]);
j = j + K;
}
for(int i = 0; i < sum-1; ++i) {
int id = list[i];//第i个结点的索引
printf("%05d %d %05d\n", id, a[id].Data, list[i+1]);
}
printf("%05d %d -1\n", list[sum-1], a[list[sum-1]].Data);
return 0;
}
测试点
测试点如下
02-线性结构4 Pop Sequence (25分)
本题链接
是2013年PAT春季考试真题，考察队堆栈的基本概念的掌握，应可以一试。
题目大意
给定一个可以保留最多M个数的堆栈M。放入N个数字1、2、3、...，N并随机弹出。你应该告诉给定的数字序列是否可能是堆栈的弹出序列。例如，如果M是5,N是7,我们可以从堆栈中获取1、2、3、4 、5、6、7,但不是3、2、1、7、5、6、4 输入规格： 每个输入文件包含一个测试用例。对于每个情况，第一行包含 3 个数字（所有数字不超过 1000） M（堆栈的最大容量），N（放入序列的长度），以及K（要检查的弹出序列数）。 接下来K行，每行包含一个含N个数字的弹出序列。行中的所有数字都用空格分隔。 输出规格：对于每个弹出序列，如果确实是堆栈的可能弹出序列，则用一行"YES"打印，如果不是，则打印为"否"。
示例输入：
5 7 5 1 2 3 4 5 6 7 3 2 1 7 5 6 4 7 6 5 4 3 2 1 5 6 4 3 7 2 1 1 7 6 5 4 3 2
示例输出：
YES NO NO YES NO
思路
处理每个序列时，先将1压入堆栈，每读入一个数x,将其与栈顶元素比较，若大于栈顶元素则压入直到x-1,若等于栈顶元素，直接弹出，若小于栈顶元素则直接false。若栈为空了，则需要压入一个数，若溢出了，则也是false
代码
#include <iostream>
#include <cstring>
using namespace std;
#define maxsize 100002
int s[maxsize];//堆栈
int top;//栈顶元素下标 0的时候为空堆栈
int M, N, K;//栈容量，序列长度，几个序列
void s_clear() {
top = 0;
memset(s, 0, maxsize);
}
int s_pop() {
int x = s[top];
s[top] = 0;
top--;
return x;
}
void s_push(int x) {
top++;
s[top] = x;
}
bool judge() {
bool ans = true;
int k = 1;
for (int i = 0; i < N; ++i) {
int x;
cin >> x;
if (top == 0) {//堆栈为空
s_push(k++);
}
if (x < s[top]) {
ans = false;
} else if (x == s[top]) {
s_pop();
} else { //若大于栈顶元素
while (k <= x - 1) {
s_push(k++);
}
s_push(k++);
if (top > M) ans = false;
s_pop();
}
if (k > N + 1) ans = false;
}
return ans;
}
int main() {
cin >> M >> N >> K;
for (int i = 0; i < K; ++i) {
s_clear();
if (judge()) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
测试点
测试点如下，一次过了
