此作业为某大学数据结构作业1，答案为我当时所写，仅供学习和参考

问题 A: 查成绩

题目描述

期末考试结束后，数学老师给出了班里同学们的数学成绩，为了快速查成绩，请编程帮助查成绩。

输入

第一行为N（N<1000）表示班级人数，第一行后N行，每行两个部分，一个是学号（符号最多8个），一个是成绩（整数）。
最后一行是要查找成绩同学的学号。

输出

输出要查找同学的学号。

样例输入

1
2
3
4
2
001 90
002 95
002

样例输出

1
95

参考答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    int num[n];
    int score[n];
    for (int i = 0; i < n; ++i) {
        cin >> num[i] >> score[i];
    }
    int find_num;
    cin >> find_num;
    for (int i = 0; i < n; ++i) {
        if (num[i] == find_num) {
            cout << score[i];
            return 0;
        }
    }
    return 0;
}

问题 B: 插入数据

题目描述

已有一个整数序列，现在要在不同的位置插入一些整数，请输出插入数据后的序列。

输入

第一行是N（N<1000）表示原序列中元素的个数，紧接着第二行是N个整数，第三行是要插入的元素个数M（M<1000）,第四开始M行，每行是一对数据k（要插入到原序列的位置，从1开始计数）和x。

输出

输出插入元素后的整数序列。

样例输入

1
2
3
4
5
5
1 2 3 4 5
2
1 11
3 33

样例输出

1
11 1 2 33 3 4 5

参考答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <vector>

using namespace std;

struct node{
    int data;
    node* next;
};

node* getNewNode(int data){
    return new node({data, nullptr});
}

void insert(node* head, int index, int data){
    for (int i = 1; i < index; ++i) {
        head = head->next;
    }
    node* tmp = getNewNode(data);
    tmp->next = head->next;
    head->next = tmp;
}

void find_idx(vector<node*> &v, node* head, int index){
    for (int i = 0; i < index; ++i) {
        head = head->next;
    }
    v.push_back(head);
}

void v_insert(node* pos, node* head, int data){
    node* p = head;
    head = head->next;
    while (head!=pos) {
        head = head->next;
        p = p->next;
    }
    head = getNewNode(data);
    head->next = p->next;
    p->next = head;
}

int main() {
    int n;
    cin >> n;
    node* head = getNewNode(0), *tail = head;
    int num;
    for (int i = 1; i <= n; ++i) {
        cin >> num;
        tail->next = getNewNode(num);
        tail = tail->next;
    }
    cin >> n;
    int index;
    vector<node*> v;
    vector<int> nums;
    for (int i = 0; i < n; ++i) {
        cin >> index >> num;
        nums.push_back(num);
        find_idx(v, head, index);
    }
    for (int i = 0; i < n; ++i) {
        v_insert(v[i], head, nums[i]);
    }
    while (head->next!=nullptr) {
        head = head->next;
        cout << head->data << " ";
    }
    return 0;
}

问题 C: 二路归并

题目描述

有两个按元素值递增有序的整数顺序表A和B，设计一个算法将顺序表A和B的全部元素合并到一个递增有序顺序表C中，并依次输出C中的元素。

输入

占两行，依次是A和B的序列（元素个数都小于100）。

输出

依次输出C中的元素。

样例输入

1
2
1 2 3 4 5
1 2 3 4 6

样例输出

1
1 1 2 2 3 3 4 4 5 6

参考答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v1, v2;
    char chs[10000] = {0};
    cin.getline(chs, 10000);
    int i = 0;
    while (chs[i]!=0) {
        int j = i, num = 0;
        while (chs[j] != ' ' && chs[j] != 0) {
            num = num*10+chs[j++]-'0';
        }
        v1.push_back(num);
        i = j+1;
    }
    char chs2[10000];
    cin.getline(chs2, 10000);
    i = 0;
    while (chs2[i]!=0) {
        int j = i, num = 0;
        while (chs2[j] != ' ' && chs2[j] != 0) {
            num = num*10+chs2[j++]-'0';
        }
        v2.push_back(num);
        i = j+1;
    }

    int idx1=0, idx2=0;
    vector<int> ans;
    while (idx1 < v1.size() && idx2 < v2.size()) {
        if (v1[idx1] < v2[idx2]) {
            cout << v1[idx1++] << " ";
        } else {
            cout << v2[idx2++] << " ";
        }
    }

    if (idx1==v1.size()) {
        for (int j = idx2; j < v2.size(); ++j) {
            if (j == v2.size()-1) { cout << v2[j]; }
            else { cout << v2[j] << " "; }
        }
    } else {
        for (int j = idx1; j < v1.size(); ++j) {
            if (j == v1.size()-1) { cout << v1[j]; }
            else { cout << v1[j] << " "; }
        }
    }
    return 0;
}

问题 D: 最大值个数

题目描述

有一个整数单链表L，其中可能存在多个值相同的结点，设计一个算法查找L中最大值结点的个数。

输入

单链表L中的元素，个数不定。

输出

查找L中最大值结点的个数。

样例输入

1
1 2 3 4 5 5 20 20 1 2 3 4 5

样例输出

1
2

参考答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <string>

using namespace std;

struct node{
    int data;
    node* next;
};

node* getNewNode(int data){
    return new node({data, nullptr});
}

int main() {
    string str;
    getline(cin, str);
    int i = 0;
    node* head = getNewNode(0), *tail = head;
    while (i<str.size()) {
        int j = i, num = 0;
        while (str[j] != ' ' && str[j] != 0) {
            num = num*10+str[j++]-'0';
        }
        node* p = getNewNode(num);
        tail->next = p;
        tail = tail->next;
        i = j+1;
    }

    int count = 0;
    int max_num = tail->data;
    while (head->next != nullptr) {
        head = head->next;
        if (head->data > max_num) {
            max_num = head->data;
            count = 0;
        }
        if (head->data == max_num) {
            ++count;
        }
    }
    cout << count;
    return 0;
}

问题 E: 约瑟夫（Joseph）问题

题目描述

编写一个程序求解约瑟夫（Joseph）问题。有n个小孩围成一圈，给他们从1开始依次编号，从编号为1的小孩开始报数，数到第m（0<m<n）个小孩出列，然后从出列的下一个小孩重新开始报数，数到第m个小孩又出列，…，如此反复直到所有的小孩全部出列为止，求整个出列序列。

输入

占一行为n和m（n<100）。

输出

整个出列序列。

样例输入

1
6 5

样例输出

1
5 4 6 2 3 1

参考答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
using namespace std;

struct node{
    int data;
    node* next;
};

node* getNewNode(int data){
    return new node({data, nullptr});
}

int main() {
    int n, m;
    cin >> n >> m;
    node* p = getNewNode(1), *q = p;
    for (int i = 2; i <= n; ++i) {
        q->next = getNewNode(i);
        q = q->next;
    }
    q->next = p;

    while (p->next!=p) {
        m %= n;
        for (int i = 2; i <= m; ++i) {
            p = p->next;
        }
        cout << p->data << " ";
        p->data = p->next->data;
        p->next = p->next->next;

    }
    cout << p->data;
    return 0;
}

问题 F: 括号配对

题目描述

设计一个算法利用顺序栈检查用户输入的表达式中括号是否配对（假设表达式中可能含有圆括号()、中括号[]和大括号{}）。

输入

占一行为含有三种括号的表达式（最长100个符号）。

输出

匹配时输出YES，小括号不匹配输出NO1，中括号不匹配时输出NO2，大括号不匹配时输出NO3。

样例输入

1
{([a])}

样例输出

1
YES

参考答案

我认为此题目描述不是很清楚，并且某些样例也有问题，这个答案参考了别人所写

只需注意，遇到中括号以右边为准，其他括号以左边为准

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <stack>

using namespace std;

int main() {
    char chs[1000] = {0};
    cin.getline(chs, 1000);
    stack<char> stk;
    int i = 0;
    while (chs[i]!=0) {
        if (chs[i] == '(' || chs[i] == '[' || chs[i] == '{') stk.push(chs[i]);
        else if (chs[i] == ')') {
            if (stk.empty()) {
                cout << "NO1";
                return 0;
            }
            if (stk.top() == '(') {
                stk.pop();
            } else {
                if (stk.top() == '[') {
                    cout << "NO2";
                    return 0;
                }
                else if (stk.top() == '{') {
                    cout << "NO3";
                    return 0;
                }
            }
        }
        else if (chs[i] == ']') {
            if (stk.empty()) {
                cout << "NO2";
                return 0;
            }
            if (stk.top() == '[') {
                stk.pop();
            } else if (stk.top() != '[') {
                cout << "NO2";
                return 0;
            }
        }
        else if (chs[i] == '}') {
            if (stk.empty()) {
                cout << "NO3";
                return 0;
            }
            if (stk.top() == '{') {
                stk.pop();
            } else {
                if (stk.top() == '(') {
                    cout << "NO1";
                    return 0;
                }
                else if (stk.top() == '[') {
                    cout << "NO2";
                    return 0;
                }
            }
        }
        ++i;
    }
    if (stk.empty()) {
        cout << "YES";
    }
    else {
        if (stk.top() == '(') cout << "NO1";
        else if (stk.top() == '[') cout << "NO2";
        else if (stk.top() == '{') cout << "NO3";
    }
    return 0;
}

问题 G: 后缀表达式

题目描述

给出一个中缀表达式，输出该表达式的后缀表达式。

输入

占一行，一个中缀表达式（运算符只有+-*/，最多1000个字符），输出后缀表达式。

输出

输出后缀表达式。

样例输入

1
(56-20)/(4+2)

样例输出

1
56 20 - 4 2 + /

参考答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main() {
    char chs[1005];
    cin.getline(chs, 1005);
    int i=0;
    stack<char> stk;
    while (chs[i]!=0) {
        if (chs[i] >= '0' && chs[i] <='9') {
            int j = i;
            while (chs[j] >= '0' && chs[j] <='9') {
                cout << chs[j++];
            }
            cout << " ";
            i = j;
        }
        else if (chs[i] == '(') {
            stk.push('(');
            ++i;
        }
        else if (chs[i] == '+') {
            while (!stk.empty() && (stk.top() == '*' || stk.top() == '/' || stk.top() == '-')) {
                cout  << stk.top() << " ";
                stk.pop();
            }
            stk.push('+');
            ++i;
        }
        else if (chs[i] == '-') {
            while (!stk.empty() && (stk.top() == '*' || stk.top() == '/' || stk.top() == '+')) {
                cout  << stk.top() << " ";
                stk.pop();
            }
            stk.push('-');
            ++i;
        }
        else if (chs[i] == '*') {
            while (!stk.empty() && (stk.top() == '/')) {
                cout  << stk.top() << " ";
                stk.pop();
            }
            stk.push('*');
            ++i;
        }
        else if (chs[i] == '/') {
            while (!stk.empty() && (stk.top() == '*')) {
                cout  << stk.top() << " ";
                stk.pop();
            }
            stk.push('/');
            ++i;
        }
        else if (chs[i] == ')') {
            while (!stk.empty() && stk.top() != '(') {
                cout << stk.top() << " ";
                stk.pop();
            }
            stk.pop();
            ++i;
        }
    }
    while (!stk.empty()) {
        cout << stk.top() << " ";
        stk.pop();
    }
    return 0;
}

问题 H: 字符串反转

题目描述

小C很喜欢倒着写单词，现在给你一行小C写的文本，你能把每个单词都反转并输出它们吗？

输入

输入包含多组测试样例。第一行为一个整数T，代表测试样例的数量，后面跟着T个测试样例。
每个测试样例占一行，包含多个单词。一行最多有1000个字符。

输出

对于每一个测试样例，你应该输出转换后的文本。

样例输入

1
2
3
4
3
olleh !dlrow
I ekil .bulcmca
I evol .mca

样例输出

1
2
3
hello world!
I like acmclub.
I love acm.

参考答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n = 0;
    char tmp[1005] = {0};
    cin.getline(tmp, 1005);
    int a = 0;
    vector<string> ans;
    while (tmp[a] != ' ' && tmp[a] != 0) {
        n = n*10 + tmp[a++]-'0';
    }
    for (int k = 0; k < n; ++k) {
        ans.emplace_back("");
        char chs[1005] = {0};
        cin.getline(chs, 1005);
        int i = 0;
        while (chs[i]!=0) {
            string str;
            int j = i;
            while (chs[j] != ' ' && chs[j] != 0) {
                str.push_back(chs[j++]);
            }
            i = j+1;
            for (auto it = str.rbegin();it != str.rend(); ++it) {
                ans[k].push_back(*it);
            }
            ans[k].push_back(' ');
        }
    }
    for (int p = 0; p < n; ++p) {
        cout << ans[p] << endl;
    }
    return 0;
}