首页 题目记录

题目集总目录
学习笔记指路博客 线性表、堆栈

# 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;
}
# 测试点
测试点如下，一次过了
在这里插入图片描述