莱蒙黎梦

全栈开发日志

0%

中国矿业大学数据结构实践3

发表于 分类于 ，
本文字数： 2k 阅读时长 ≈ 7 分钟

2023 CUMT 中国矿业大学 数据结构课程 实践课 代码题解

本博文由我的GitHub仓库LymoneLM/LymoneTest代码自动整理生成，进入仓库可以查看最新的代码

如果代码对您有帮助，希望可以给我的仓库点个Star，或者在GitHub关注我，感谢

在我的个人博客莱蒙黎梦可以查看本博文原文和更多其他我的博文

本博文提供的代码仅供参考学习，原题已遗失，先尝试后使用，不同年度课程题目可能略有差异

部分文件后缀有数字的是同一道题的不同写法，一般序号大的更优

A.cpp

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
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define endl "\n"
#define ll long long
#define mm(a) memset(a,0,sizeof(a))
using namespace std;
char str[110];
int len,cnt=-1;
struct Node{
    char data;
    Node *left,*right;
}*Tree;
Node* CreatTree(){
    if(len==cnt||str[++cnt]==' ')
        return NULL;
    Node *p = new Node;
    p->data=str[cnt];
    p->left=CreatTree();
    p->right=CreatTree();
    return p;
}
void PreOrderTraversel(Node* p){
    cout<<p->data<<" ";
    if(p->left!=NULL) PreOrderTraversel(p->left);
    if(p->right!=NULL) PreOrderTraversel(p->right);
}
void InOrderTraversel(Node* p){
    if(p->left!=NULL) InOrderTraversel(p->left);
    cout<<p->data<<" ";
    if(p->right!=NULL) InOrderTraversel(p->right);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin.getline(str,110);
    len=strlen(str);

    Tree = CreatTree();
    PreOrderTraversel(Tree);
    cout<<endl;
    InOrderTraversel(Tree);
    cout<<endl;
    InOrderTraversel(Tree);
    cout<<endl;
    return 0;
}

B.cpp

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
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define endl "\n"
#define ll long long
#define INF 0x3f3f3f3f
#define mm(a) memset(a, 0, sizeof(a))
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    int matrix[60][60];
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> matrix[i][j];
    bool A[60];
    mm(A);
    A[0] = true;
    int allCost = 0, minCost, minB, thisMinCost;
    for (int x = 1; x < N; x++) {
        minCost=INF;
        for (int i = 0; i < N; i++) {
            if (A[i]) {
                thisMinCost = INF;
                for (int j = 0; j < N; j++)
                    if (!A[j] && matrix[i][j] != 0)
                        thisMinCost = min(thisMinCost, matrix[i][j])
            }
            if(thisMinCost<minCost){
                minB=
            }
        }
    }

    return 0;
}

B2.cpp

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
#include <iostream>
#include <vector>
#include <climits>

int findMinVertex(const std::vector<int>& cost, const std::vector<bool>& visited, int n) {
    int minVertex = -1;
    for (int i = 0; i < n; ++i) {
        if (!visited[i] && (minVertex == -1 || cost[i] < cost[minVertex])) {
            minVertex = i;
        }
    }
    return minVertex;
}

int primMST(const std::vector<std::vector<int>>& graph, int n) {
    std::vector<int> parent(n);  // 用于存储最小生成树中每个顶点的父节点
    std::vector<int> cost(n, INT_MAX);  // 用于存储每个顶点与最小生成树的代价
    std::vector<bool> visited(n, false);  // 记录顶点是否被访问

    parent[0] = -1;  // 根节点的父节点设为-1
    cost[0] = 0;  // 根节点的代价为0

    for (int i = 0; i < n - 1; ++i) {
        int minVertex = findMinVertex(cost, visited, n);
        visited[minVertex] = true;

        for (int j = 0; j < n; ++j) {
            if (graph[minVertex][j] && !visited[j] && graph[minVertex][j] < cost[j]) {
                parent[j] = minVertex;
                cost[j] = graph[minVertex][j];
            }
        }
    }

    int minCost = 0;
    for (int i = 1; i < n; ++i) {
        minCost += cost[i];
    }

    return minCost;
}

int main() {
    int n;
    std::cin >> n;

    std::vector<std::vector<int>> graph(n, std::vector<int>(n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cin >> graph[i][j];
        }
    }

    int minCost = primMST(graph, n);
    std::cout << minCost << std::endl;

    return 0;
}

C.cpp

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
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define endl "\n"
#define ll long long
#define INF 0x3f3f3f3f
#define mm(a) memset(a, 0, sizeof(a))
using namespace std;

class Node {
public:
    int weight;
    Node *left, *right;
    Node(int _weight) : weight(_weight) {
        left = right = NULL;
    }
    Node(const Node &n) {
        weight = n.weight;
        left = n.left;
        right = n.right;
    }
    friend bool operator<(Node l, Node r) {
        return l.weight < r.weight;
    }
    ll Travel(int deep){
        if(left=NULL)
            return deep*weight;
        return left->Travel(deep+1)+right->Travel(deep+1);
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, temp;
    set<Node> forest;
    while (cin >> n) {
        ll weight = 0;
        for (int i = 0; i < n; i++) {
            cin >> temp;
            forest.insert(Node(temp));
        }
        Node *A, *B;
        for (int i = 1; i < n; i++) {
            A = new Node(*forest.begin());
            forest.erase(forest.begin());
            B = new Node(*forest.begin());
            forest.erase(forest.begin());
            Node C(A->weight + B->weight);
            C.left=A;
            C.right=B;
            forest.insert(C);
        }
        A = new Node(*forest.begin());
        cout<<A->Travel(0)<<endl;
    }

    return 0;
}

C2.cpp

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
73
74
75
#include <iostream>
#include <queue>
#include <vector>

struct Node {
    int weight;
    Node* left;
    Node* right;

    Node(int w) : weight(w), left(nullptr), right(nullptr) {}
};

struct CompareNodes {
    bool operator()(Node* a, Node* b) {
        return a->weight > b->weight;
    }
};

Node* buildHuffmanTree(const std::vector<int>& leafWeights) {
    std::priority_queue<Node*, std::vector<Node*>, CompareNodes> pq;

    for (int weight : leafWeights) {
        Node* node = new Node(weight);
        pq.push(node);
    }

    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();

        Node* parent = new Node(left->weight + right->weight);
        parent->left = left;
        parent->right = right;

        pq.push(parent);
    }

    return pq.top();
}

int calculatePathLength(Node* root, int depth) {
    if (root == nullptr) {
        return 0;
    }

    if (root->left == nullptr && root->right == nullptr) {
        return root->weight * depth;
    }

    int leftPathLength = calculatePathLength(root->left, depth + 1);
    int rightPathLength = calculatePathLength(root->right, depth + 1);

    return leftPathLength + rightPathLength;
}

int main() {
    int n;

    while (std::cin >> n) {
        std::vector<int> leafWeights(n);

        for (int i = 0; i < n; ++i) {
            std::cin >> leafWeights[i];
        }

        Node* root = buildHuffmanTree(leafWeights);
        int pathLengthSum = calculatePathLength(root, 0);

        std::cout << pathLengthSum << std::endl;
    }

    return 0;
}

D2.cpp

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
#include <iostream>
#include <string>
#include <unordered_map>

struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(char v) : val(v), left(nullptr), right(nullptr) {}
};

int getHeight(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }

    int leftHeight = getHeight(root->left);
    int rightHeight = getHeight(root->right);

    return std::max(leftHeight, rightHeight) + 1;
}

TreeNode* buildTree(const std::string& preorder, const std::string& inorder, int preStart, int preEnd, int inStart, int inEnd, std::unordered_map<char, int>& inorderIndex) {
    if (preStart > preEnd || inStart > inEnd) {
        return nullptr;
    }

    char rootValue = preorder[preStart];
    TreeNode* root = new TreeNode(rootValue);

    int rootIndex = inorderIndex[rootValue];

    int leftSize = rootIndex - inStart;

    root->left = buildTree(preorder, inorder, preStart + 1, preStart + leftSize, inStart, rootIndex - 1, inorderIndex);
    root->right = buildTree(preorder, inorder, preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd, inorderIndex);

    return root;
}

int main() {
    int n;

    while (std::cin >> n) {
        std::string preorder, inorder;
        std::cin >> preorder >> inorder;

        std::unordered_map<char, int> inorderIndex;
        for (int i = 0; i < n; ++i) {
            inorderIndex[inorder[i]] = i;
        }

        TreeNode* root = buildTree(preorder, inorder, 0, n - 1, 0, n - 1, inorderIndex);
        int height = getHeight(root);

        std::cout << height << std::endl;
    }

    return 0;
}

E2.cpp

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <string>
#include <queue>
#include <sstream>

struct TreeNode {
    int index;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int i) : index(i), left(nullptr), right(nullptr) {}
};

bool isCompleteBinaryTree(TreeNode* root, int nodeCount) {
    if (root == nullptr) {
        return true;
    }

    std::queue<TreeNode*> q;
    q.push(root);

    int currentIndex = 0;

    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();

        if (node->index != currentIndex) {
            return false;
        }

        currentIndex++;

        if (node->left != nullptr) {
            q.push(node->left);
        } else if (currentIndex < nodeCount) {
            return false;
        }

        currentIndex++;

        if (node->right != nullptr) {
            q.push(node->right);
        } else if (currentIndex < nodeCount) {
            return false;
        }

        currentIndex++;
    }

    return true;
}

TreeNode* buildTree(const std::vector<std::string>& treeData) {
    std::vector<TreeNode*> nodes(treeData.size());

    for (int i = 0; i < treeData.size(); ++i) {
        if (treeData[i] != "-") {
            nodes[i] = new TreeNode(i);
        }
    }

    for (int i = 0; i < treeData.size(); ++i) {
        if (treeData[i] != "-") {
            TreeNode* node = nodes[i];
            int leftIndex, rightIndex;
            std::istringstream iss(treeData[i]);
            iss >> leftIndex >> rightIndex;

            if (leftIndex != -1) {
                node->left = nodes[leftIndex];
            }

            if (rightIndex != -1) {
                node->right = nodes[rightIndex];
            }
        }
    }

    return nodes[0];
}

int main() {
    int n;

    while (std::cin >> n) {
        std::vector<std::string> treeData(n);

        for (int i = 0; i < n; ++i) {
            std::cin >> treeData[i];
        }

        TreeNode* root = buildTree(treeData);
        bool isComplete = isCompleteBinaryTree(root, n);

        if (isComplete) {
            std::cout << "YES " << n - 1 << std::endl;
        } else {
            std::cout << "NO 0" << std::endl;
        }
    }

    return 0;
}

E3.cpp

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
#include <bits/stdc++.h>

using namespace std;

const int N = 30;
int n;
int l[N], r[N];
bool hf[N];
int maxCur = -1, nodeId;

void dfs(int u, int cur)
{
    if(cur > maxCur)
    {
        maxCur = cur;
        nodeId = u;
    }
    if(l[u] != -1) dfs(l[u], 2 * cur);
    if(r[u] != -1) dfs(r[u], 2 * cur + 1);
}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        string a, b;
        cin >> a >> b;
        if(a != "-")
        {
            l[i] = stoi(a);
            hf[stoi(a)] = true;
        }
        else l[i] = -1;
        if(b != "-")
        {
            r[i] = stoi(b);
            hf[stoi(b)] = true;
        }
        else r[i] = -1;
    }
    int root = 0;
    while(hf[root]) root ++;

    dfs(root, 1);
    
    if(maxCur == n)
        cout << "YES" << ' ' << nodeId << endl;
    else
        cout << "NO" << ' ' << root << endl;
}

F2.cpp

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
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <vector>
#include <unordered_map>
#include <sstream>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

TreeNode* buildTree(const std::vector<int>& inorder, const std::vector<int>& postorder,
                    int inStart, int inEnd, int postStart, int postEnd,
                    std::unordered_map<int, int>& indexMap) {
    if (inStart > inEnd || postStart > postEnd) {
        return nullptr;
    }

    int rootVal = postorder[postEnd];
    TreeNode* root = new TreeNode(rootVal);

    int rootIndex = indexMap[rootVal];

    int leftTreeSize = rootIndex - inStart;
    int rightTreeSize = inEnd - rootIndex;

    root->left = buildTree(inorder, postorder, inStart, rootIndex - 1, postStart, postStart + leftTreeSize - 1, indexMap);
    root->right = buildTree(inorder, postorder, rootIndex + 1, inEnd, postEnd - rightTreeSize, postEnd - 1, indexMap);

    return root;
}

void inorderTraversal(TreeNode* root, std::vector<int>& inorderSequence) {
    if (root == nullptr) {
        return;
    }

    inorderTraversal(root->left, inorderSequence);
    inorderSequence.push_back(root->val);
    inorderTraversal(root->right, inorderSequence);
}

int main() {
    int N;
    std::cin >> N;

    std::vector<int> preorder(N);
    std::vector<int> postorder(N);

    for (int i = 0; i < N; ++i) {
        std::cin >> preorder[i];
    }

    for (int i = 0; i < N; ++i) {
        std::cin >> postorder[i];
    }

    std::unordered_map<int, int> indexMap;

    for (int i = 0; i < N; ++i) {
        indexMap[preorder[i]] = i;
    }

    TreeNode* root = buildTree(preorder, postorder, 0, N - 1, 0, N - 1, indexMap);

    std::vector<int> inorderSequence;
    inorderTraversal(root, inorderSequence);

    std::cout << "Yes" << std::endl;
    for (int i = 0; i < inorderSequence.size(); ++i) {
        std::cout << inorderSequence[i];
        if (i != inorderSequence.size() - 1) {
            std::cout << " ";
        }
    }
    std::cout << std::endl;

    return 0;
}

F3.cpp

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
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
 
const int maxn = 40;
int pos1[maxn], pos2[maxn];
int a1[maxn], a2[maxn];
int L[maxn], size[maxn], R[maxn];
bool book = false;
 
void dfs(int l, int r) {
    if (l >= r)
        return;
    int root = a1[l];
    int lroot = a1[l + 1];
    int rroot = a2[pos2[root] - 1];
    if (lroot == rroot) {
        R[root] = rroot;
        book = true;
        dfs(l + 1, r);
        return;
    }
    int lsize = pos1[rroot] - pos1[lroot];
    L[root] = lroot;
    R[root] = rroot;
    dfs(l + 1, l + lsize);
    dfs(l + lsize + 1, r);
}
 
void dfs3(int now) {
    if (L[now])
        dfs3(L[now]);
    cout << now << " ";
    if (R[now])
        dfs3(R[now]);
    if (now == a1[1])
        cout << endl;
}
 
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        size[i] = 1;
        cin >> a1[i];
        pos1[a1[i]] = i;
    }
    for (int i = 1; i <= n; i++) {
        cin >> a2[i];
        pos2[a2[i]] = i;
    }
 
    dfs(1, n);
    if (book)
        cout << "No" << endl;
    else
        cout << "Yes" << endl;
    dfs3(a1[1]);
 
    return 0;
}

编程作业、大作业、课程设计程序代码调试、协助/指导，制作软件/脚本/网页，经验丰富质量高

支持C/C++、JAVA、Python、Matlab、JavaScript、R语言等，欢迎咨询

企鹅：3451216814

-------------本文结束感谢您的阅读-------------

欢迎关注我的其它发布渠道