C++数据结构2

博主： Xherlock
发布时间：2023 年 06 月 23 日
338 次浏览
暂无评论
4555字数
分类： C/C++&机试

# C++数据结构2

## 二叉树

### 相关知识

二叉树递归定义：二叉树要么为空，要么由根节点、左子树、右子树构成

遍历方法：前序遍历、中序遍历、后序遍历

### 题目

#### 二叉树遍历1

[二叉树遍历_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&tqId=29483&tPage=1&ru=/kaoyan/retest/1001&qru=/ta/tsing-kaoyan/question-ranking)

**描述**

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

**输入描述**：

输入包括1行字符串，长度不超过100。

**输出描述**：

可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。

~~~
输入：
abc##de#g##f###
输出：
c b e g d f a 
~~~

思路：记死二叉树遍历模板就行了

~~~c++
#include <iostream>
using namespace std;

struct TreeNode {
    char data;
    TreeNode *leftChild;
    TreeNode *rightChild;
    TreeNode(char c): data(c), leftChild(NULL), rightChild(NULL) {}
};

TreeNode* build_tree(int& position, string s) {
    char node = s[position++];
    if (node == '#')
        return NULL;
    TreeNode* root = new TreeNode(node);
    root->leftChild = build_tree(position, s);
    root->rightChild = build_tree(position, s);
    return root;
}

void InOrder(TreeNode* t) {
    if (t) {
        InOrder(t->leftChild);
        cout << t->data << " "; 
        InOrder(t->rightChild);
    }
}

int main() {
    string tree_s;
    while (cin >> tree_s) {
        int position = 0;
        TreeNode* t = build_tree(position, tree_s);
        InOrder(t);
        cout << endl;
    }
}
~~~

#### 二叉树遍历2

[二叉树遍历_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/6e732a9632bc4d12b442469aed7fe9ce?tpId=40&tqId=21544&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking)

**描述**

二叉树的前序、中序、后序遍历的定义： 前序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树； 中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树； 后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。 给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。

**输入描述**：

两个字符串，其长度n均小于等于26。 第一行为前序遍历，第二行为中序遍历。 二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。

**输出描述**：

输入样例可能有多组，对于每组测试样例， 输出一行，为后序遍历的字符串。

~~~
输入：
ABC
BAC
FDXEAG
XDEFAG
输出：
BCA
XEDGAF
~~~

思路：本题同上一题，都是根据二叉树某种遍历结果求出二叉树，进而求另一种遍历结果

本题给出前序遍历和中序遍历，因此能够得到唯一的二叉树；前序的第一个字符肯定是root，而此root必然在中序中，因此可以不断拆分得到二叉树

~~~c++
#include <iostream>
using namespace std;

struct TreeNode {
    char data;
    TreeNode *leftChild;
    TreeNode *rightChild;
    TreeNode(char c): data(c), leftChild(NULL), rightChild(NULL) {}
};

TreeNode* Build(string str1, string str2) {
    if (str1.size() == 0)
        return NULL;
    char c = str1[0];
    TreeNode* root = new TreeNode(c);
    int position = str2.find(c);
    root->leftChild = Build(str1.substr(1, position), str2.substr(0, position));
    root->rightChild = Build(str1.substr(position+1), str2.substr(position+1));
    return root;
}

void PostOrder(TreeNode* t) {
    if (t) {
        PostOrder(t->leftChild);
        PostOrder(t->rightChild);
        cout << t->data;
    }
}

int main() {
    string str1, str2;
    while (cin >> str1 >> str2) {
        TreeNode* root = Build(str1, str2);
        PostOrder(root);
        cout << endl;
    }
}
~~~

## 二叉排序树

### 相关知识

二叉排序树特征：

1. 若左子树非空，则左子树上所有结点关键字的值均小于根结点关键字的值
2. 若右子树非空，则右子树上所有结点关键字的值均大于根结点关键字的值
3. 左右子树本身也是一棵二叉排序树

### 题目

#### 二叉排序树1

[二叉排序树_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/30a0153649304645935c949df7599602?tpId=69&tqId=29654&tPage=1&ru=/kaoyan/retest/11002&qru=/ta/hust-kaoyan/question-ranking)

**描述**

二叉排序树，也称为二叉查找树。可以是一颗空树，也可以是一颗具有如下特性的非空二叉树： 1. 若左子树非空，则左子树上所有节点关键字值均不大于根节点的关键字值； 2. 若右子树非空，则右子树上所有节点关键字值均不小于根节点的关键字值； 3. 左、右子树本身也是一颗二叉排序树。 现在给你N个关键字值各不相同的节点，要求你按顺序插入一个初始为空树的二叉排序树中，每次插入后成功后，求相应的父亲节点的关键字值，如果没有父亲节点，则输出-1。

**输入描述**：

输入包含多组测试数据，每组测试数据两行。 第一行，一个数字N（N<=100），表示待插入的节点数。 第二行，N个互不相同的正整数，表示要顺序插入节点的关键字值，这些值不超过10^8。

**输出描述**：

输出共N行，每次插入节点后，该节点对应的父亲节点的关键字值。

思路：还是得多练下，二叉树数据结构学的只会概念，代码啥的基本没掌握住，方法是

~~~c++
#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *leftChild;
    TreeNode *rightChild;
    TreeNode(int v): val(v), leftChild(NULL), rightChild(NULL) {}
};

TreeNode* Insert(TreeNode* root, int x, int father) {
    if (root == NULL) {
        root = new TreeNode(x);
        cout << father << endl;
    } else if (x < root->val) 
        root->leftChild = Insert(root->leftChild, x, root->val);
    else
        root->rightChild = Insert(root->rightChild, x, root->val);
    return root;
}

int main() {
    int N;
    while (cin >> N) {
        TreeNode* root = NULL;
        int x;
        for (int i = 0; i < N; i++) {
            cin >> x;
            root = Insert(root, x, -1);
        }
    }
}
~~~

#### 二叉排序树2

[二叉排序树_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/b42cfd38923c4b72bde19b795e78bcb3?tpId=69&tqId=29670&tPage=1&ru=/kaoyan/retest/11002&qru=/ta/hust-kaoyan/question-ranking)

**描述**

输入一系列整数，建立二叉排序树，并进行前序，中序，后序遍历。

**输入描述**：

输入第一行包括一个整数n(1<=n<=100)。 接下来的一行包括n个整数。

**输出描述**：

可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。 每种遍历结果输出一行。每行最后一个数据之后有一个换行。 输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。

思路：先实现Insert，在前序、中序、后序遍历，背住就好

~~~c++
#include <iostream>
using namespace std;

struct TreeNode {
    int data;
    TreeNode *leftChild;
    TreeNode *rightChild;
    TreeNode(int data): data(data), leftChild(NULL), rightChild(NULL) {}
};

TreeNode* Insert(TreeNode* root, int x) {
    if (root == NULL)
        root = new TreeNode(x);
    else if (x < root->data)
        root->leftChild = Insert(root->leftChild, x);
    else if (x > root->data)
        root->rightChild = Insert(root->rightChild, x);
    return root;
}

void PreOrder(TreeNode* root) {
    if (root) {
        cout << root->data << " ";
        PreOrder(root->leftChild);
        PreOrder(root->rightChild);
    }
}

void InOrder(TreeNode* root) {
    if (root) {
        InOrder(root->leftChild);
        cout << root->data << " ";
        InOrder(root->rightChild);
    }
}

void PostOrder(TreeNode* root) {
    if (root) {
        PostOrder(root->leftChild);
        PostOrder(root->rightChild);
        cout << root->data << " ";
    }
}

int main() {
    int n;
    while (cin >> n) {
        TreeNode* root = NULL;
        int x;
        for (int i = 0; i < n; i++) {
            cin >> x;
            root = Insert(root, x);
        }
        PreOrder(root);
        cout << endl;
        InOrder(root);
        cout << endl;
        PostOrder(root);
        cout << endl;
    }
}
~~~

#### 二叉搜索树

[二叉搜索树_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/3d6dd9a58d5246f29f71683346bb8f1b?tpId=63&tqId=29571&tPage=1&ru=/kaoyan/retest/9001&qru=/ta/zju-kaoyan/question-ranking)

**描述**

判断两序列是否为同一二叉搜索树序列

**输入描述**：

开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。 接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。 接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。

**输出描述**：

如果序列相同则输出YES，否则输出NO

~~~
输入：
2
567432
543267
576342
0
输出：
YES
NO
~~~

思路：insert函数和之前一样，主要是写compare函数来比较两棵树，从根节点开始

* 若根节点都为空，返回true
* 若只有一个为空，肯定不同，返回false
* 若都不为空，先比较当前节点值，不同返回false，相同再去比较左子树和右子树，从头开始比较

~~~c++
#include <iostream>
using namespace std;

struct TreeNode {
    char data;
    TreeNode *leftChild;
    TreeNode *rightChild;
    TreeNode(int data): data(data), leftChild(NULL), rightChild(NULL) {}
};

TreeNode* Insert(TreeNode* root, char x) {
    if (root == NULL)
        root = new TreeNode(x);
    else if (x < root->data)
        root->leftChild = Insert(root->leftChild, x);
    else if (x > root->data)
        root->rightChild = Insert(root->rightChild, x);
    return root;
}

bool compare(TreeNode* base_root, TreeNode* root) {
    if (base_root == NULL && root == NULL)
        return true;
    if (base_root == NULL || root == NULL)
        return false;
    if (base_root->data != root->data)
        return false;
    bool left_same = compare(base_root->leftChild, root->leftChild);
    bool right_same = compare(base_root->rightChild, root->rightChild);
    return left_same && right_same;
}

int main() {
    int n;
    while (cin >> n) {
        if (n == 0)
            break;
        TreeNode* root[n+1];
        string s[n+1];
        for (int i = 0; i < n + 1; i++) {
            root[i] = NULL;
            cin >> s[i];
            for (int j = 0; j < s[i].size(); j++) {
                root[i] = Insert(root[i], s[i][j]);
            }
        }
        for (int i = 0; i < n; i++) {
            if (compare(root[0], root[i+1]))
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        }
    }
}
~~~

## 优先队列

### 相关知识

~~~c++
#include <queue>
priority_queue<typename> name;
~~~

优先队列：将数据按照事先规定的优先级次序进行动态组织的数据结构，访问元素时，只能访问当前队列中优先级最高的元素，**最高级先出**

### 题目

#### 复数集合

[复数集合_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/abdd24fa839c414a9b83aa9c4ecd05cc?tpId=67&tqId=29643&tPage=1&ru=/kaoyan/retest/1005&qru=/ta/bupt-kaoyan/question-ranking)

**描述**

一个复数（x+iy）集合，两种操作作用在该集合上：   1、Pop 表示读出集合中复数模值最大的那个复数，如集合为空 输出 empty ，不为空就输出最大的那个复数并且从集合中删除那个复数，再输出集合的大小SIZE；   2 Insert a+ib 指令（a，b表示实部和虚部），将a+ib加入到集合中 ，输出集合的大小SIZE；   最开始要读入一个int n，表示接下来的n行每一行都是一条命令。

**输入描述**：

输入有多组数据。 每组输入一个n(1<=n<=1000)，然后再输入n条指令。

**输出描述**：

根据指令输出结果。 模相等的输出b较小的复数。 a和b都是非负数。

思路：要设置个结构体，并重载小于号（因为类无法直接比较）

~~~c++
#include <iostream>
#include <queue>
using namespace std;

struct Complex {
    int real, imag;
    Complex(int a, int b): real(a), imag(b) {}
    bool operator< (Complex c) const {
        return real * real + imag * imag < c.real * c.real + c.imag * c.imag;
    }
};

int main() {
    int n;
    while (cin >> n) {
        string str;
        priority_queue<Complex> myPriorityQueue;
        for (int i = 0; i < n; i++) {
            cin >> str;
            if (str == "Pop") {
                if (myPriorityQueue.empty())
                    cout << "empty" << endl;
                else {
                    Complex current = myPriorityQueue.top();
                    cout << current.real << "+i" << current.imag << endl;
                    myPriorityQueue.pop();
                    cout << "SIZE = " << myPriorityQueue.size() << endl;
                }
            } else if (str == "Insert") {
                int a, b;
                scanf("%d+i%d", &a, &b);
                myPriorityQueue.push(Complex(a, b));
                cout << "SIZE = " << myPriorityQueue.size() << endl;
            }
        }
    }
}
~~~

#### 哈夫曼树

在一棵树中，从任意一个节点到达另一个节点的通路称为路径，该路径上所需经过的边的个数被称为该路径的长度。如果过树中结点带有表示某种意义的权值，那么从根节点到该节点的路径长度再乘以该节点的权值被称为该节点的带权路径长度。树中所有叶子节点的带权路径长度之和为该树的带权路径长度和。给定n个带有权值的节点，以他们为叶子节点构造一颗带权路径长度和最小的二叉树，该二叉树为哈夫曼树，也称最优树

哈夫曼树求法：

1. 所有节点放入集合K
2. 若集合K剩余节点数大于1，取出其中权值最小的两个节点，将他们构造成某个新节点的左右子节点，设这个新节点权值为两个子节点的权值和，并放入集合K
3. 若集合K仅剩一个节点，则该节点为哈夫曼树的根节点。构造过程中，所有中间节点的权值和，几位该哈夫曼树的带权路径和

[哈夫曼树_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/162753046d5f47c7aac01a5b2fcda155?tpId=67&tqId=29635&tPage=1&ru=/kaoyan/retest/1005&qru=/ta/bupt-kaoyan/question-ranking)

**描述**

哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和的最小值。

**输入描述**：

输入有多组数据。 每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。

**输出描述**：

输出权值。

思路：优先队列处理，需要重新定义优先队列**priority_queue\<int, vector\<int\>, greater\<int\>\> myPriorityQueue;**

~~~c++
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        priority_queue<int, vector<int>, greater<int>> myPriorityQueue;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            myPriorityQueue.push(x);
        }
        int sum = 0;
        while (myPriorityQueue.size() != 1) {
            int a = myPriorityQueue.top();
            myPriorityQueue.pop();
            int b = myPriorityQueue.top();
            myPriorityQueue.pop();
            sum = sum + a + b;
            myPriorityQueue.push(a+b);
        }
        cout << sum << endl;
    }
}
~~~

#### 查找第K小数

[查找第K小数_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/204dfa6fcbc8478f993d23f693189ffd?tpId=67&tqId=29637&tPage=1&ru=%2Fkaoyan%2Fretest%2F1005&qru=%2Fta%2Fbupt-kaoyan%2Fquestion-ranking)

**描述**

查找一个数组的第K小的数，注意同样大小算一样大。 如 2 1 3 4 5 2 第三小数为3。

**输入描述**：

输入有多组数据。 每组输入n，然后输入n个整数(1<=n<=1000)，再输入k。

**输出描述**：

输出第k小的整数。

~~~
输入：
6
2 1 3 5 2 2
3
输出：
3
~~~

思路：可以使用优先队列来做

~~~c++
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n, k;
    while (cin >> n) {
        priority_queue<int, vector<int>, greater<int>> myPriorityQueue;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            myPriorityQueue.push(x);
        }
        cin >> k;
        int a = 0;
        while (--k) {
            a = myPriorityQueue.top();
            while (myPriorityQueue.top() == a)
                myPriorityQueue.pop();
        }
        cout << myPriorityQueue.top() << endl;
    }
}
~~~

#### 搬水果

[搬水果_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/e4c775b0f3ee42a4bb72c26d2e1eef8a?tpId=65&tqId=29626&tPage=1&ru=/kaoyan/retest/4001&qru=/ta/jlu-kaoyan/question-ranking)

**描述**

在一个果园里，小明已经将所有的水果打了下来，并按水果的不同种类分成了若干堆，小明决定把所有的水果合成一堆。每一次合并，小明可以把两堆水果合并到一起，消耗的体力等于两堆水果的重量之和。当然经过 n‐1 次合并之后，就变成一堆了。小明在合并水果时总共消耗的体力等于每次合并所耗体力之和。   假定每个水果重量都为 1，并且已知水果的种类数和每种水果的数目，你的任务是设计出合并的次序方案，使小明耗费的体力最少，并输出这个最小的体力耗费值。例如有 3 种水果，数目依次为 1，2，9。可以先将 1，2 堆合并，新堆数目为3，耗费体力为 3。然后将新堆与原先的第三堆合并得到新的堆，耗费体力为 12。所以小明总共耗费体力=3+12=15，可以证明 15 为最小的体力耗费值。

**输入描述**：

每组数据输入包括两行,第一行是一个整数 n(1<=n<=10000),表示水果的种类数。第二行包含 n 个整数，用空格分隔，第 i 个整数(1<=ai<=1000)是第 i 种水果的数目。

**输出描述**：

对于每组输入，输出一个整数并换行，这个值也就是最小的体力耗费值。输入数据保证这个值小于 2^31。

思路：和哈夫曼树那题一模一样

## 散列表

### 相关知识

散列表是一种根据关键字（key）直接进行访问的数据结构，通过简历关键字和存储位置的直接映射关系（map），便可利用关键码直接访问元素，加快查找

标准库中提供映射模板map，map是一个将关键字和映射值形成一对映射后进行绑定存储的容器。map底层使用红黑树实现，内部仍然是有序的，其查找效率为$O(logn)$

标准库中还有一个无序映射unordered_map，其底层使用散列表实现，期望的查找效率为$O(1)$

~~~c++
#include <map>
map<typename T1, typename T2> name;
~~~

**map元素的添加或删除**：insert()和erase()

**map元素的访问**：

1. [key]
2. at()
3. 迭代器

**map元素操作**：find()查找特定元素、clear()清空映射

### 题目

#### 查找学生信息

[查找学生信息_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/fe8bff0750c8448081759f3ee0d86bb4?tpId=60&tqId=29499&tPage=2&ru=/kaoyan/retest/1001&qru=/ta/tsing-kaoyan/question-ranking)

**描述**

输入N个学生的信息，然后进行查询。

**输入描述**：

输入的第一行为N，即学生的个数(N<=1000) 接下来的N行包括N个学生的信息，信息格式如下： 01 李江 男 21 02 刘唐 男 23 03 张军 男 19 04 王娜 女 19 然后输入一个M(M<=10000),接下来会有M行，代表M次查询，每行输入一个学号，格式如下： 02 03 01 04

**输出描述**：

输出M行，每行包括一个对应于查询的学生的信息。 如果没有对应的学生信息，则输出“No Answer!”

思路：使用线性表会很耗时，因此使用映射查找

###### 法1：使用结构体接受，比较清晰

~~~c++
#include <iostream>
#include <map>
#include <string>
using namespace std;

struct Student {
    string name, gender;
    int age;
};

int main() {
    int N, M;
    while (cin >> N) {
        map<string, Student> myMap;
        string student_num;
        Student x;
        while (N--) {
            cin >> student_num >> x.name >> x.gender >> x.age;
            myMap.insert(pair<string, Student>(student_num, x));
        }
        cin >> M;
        while (M--) {
            cin >> student_num;
            if (myMap.find(student_num) != myMap.end()) {
                x = myMap.at(student_num);
                cout << student_num << " " <<  x.name << " " << x.gender << " " << x.age << endl;
            } else
                cout << "No Answer!" << endl;
        }
    }
}
~~~

###### 法2：每行看作一个字符串（getline()），输入输出较为简单

需要注意第一次输入N后需要用getchar()吃掉回车

~~~c++
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    int N, M;
    while (cin >> N) {
        getchar();
        map<string, string> myMap;
        string key;
        while (N--) {
            string str;
            getline(cin , str);
            int pos = str.find(" ");
            string key = str.substr(0, pos);
            myMap[key] = str;
        }
        cin >> M;
        while (M--) {
            cin >> key;
            string answer = myMap[key];
            if (answer == "")
                answer = "No Answer!";
            cout << answer << endl;
        }
    }
}
~~~

#### 魔咒词典

[魔咒词典_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/c6ca566fa3984fae916e6d7beae8ea7f?tpId=63&tqId=29593&tPage=2&ru=/kaoyan/retest/9001&qru=/ta/zju-kaoyan/question-ranking)

**描述**

哈利波特在魔法学校的必修课之一就是学习魔咒。据说魔法世界有100000种不同的魔咒，哈利很难全部记住，但是为了对抗强敌，他必须在危急时刻能够调用任何一个需要的魔咒，所以他需要你的帮助。   给你一部魔咒词典。当哈利听到一个魔咒时，你的程序必须告诉他那个魔咒的功能；当哈利需要某个功能但不知道该用什么魔咒时，你的程序要替他找到相应的魔咒。如果他要的魔咒不在词典中，就输出“what?”

**输入描述**：

首先列出词典中不超过100000条不同的魔咒词条，每条格式为：   [魔咒] 对应功能   其中“魔咒”和“对应功能”分别为长度不超过20和80的字符串，字符串中保证不包含字符“[”和“]”，且“]”和后面的字符串之间有且仅有一个空格。词典最后一行以“@END@”结束，这一行不属于词典中的词条。   词典之后的一行包含正整数N（<=1000），随后是N个测试用例。每个测试用例占一行，或者给出“[魔咒]”，或者给出“对应功能”。

**输出描述**：

每个测试用例的输出占一行，输出魔咒对应的功能，或者功能对应的魔咒。如果魔咒不在词典中，就输出“what?”

~~~
输入
[expelliarmus] the disarming charm
[rictusempra] send a jet of silver light to hit the enemy
[tarantallegra] control the movement of one's legs
[serpensortia] shoot a snake out of the end of one's wand
[lumos] light the wand
[obliviate] the memory charm
[expecto patronum] send a Patronus to the dementors
[accio] the summoning charm
@END@
4
[lumos]
the summoning charm
[arha]
take me to the sky
输出：
light the wand
accio
what?
what?
~~~

思路：我是使用了两个map来分开存储，需要注意的是不能使用cin直接获取输入，因为中间有空格，要使用getline来获取整行，然后对字符串进行分割

~~~c++
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    string str, magic, function;
    map<string, string> m2f;
    map<string, string> f2m;
    while (getline(cin, str)) {
        if (str == "@END@")
            break;
        int pos = str.find("]");
        magic = str.substr(1, pos-1);
        function = str.substr(pos + 2);
        m2f[magic] = function;
        f2m[function] = magic;
    }
    int N;
    cin >> N;
    string query;
    getchar();
    while (N--) {
        getline(cin, query);
        string answer;
        if (query.find("[") == 0) {
            query = query.substr(1, query.size()-2);
            answer = m2f[query];
            if (answer == "")
                answer = "what?";
        } else {
            answer = f2m[query];
            if (answer == "")
                answer = "what?"; 
        }
        cout << answer << endl;
    }
}
~~~

**可以改进的**：题目中说了没有重复的魔咒、功能，因此放在一个映射里也可以

#### 子串计算

[子串计算_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/bcad754c91a54994be31a239996e7c11?tpId=61&tqId=29540&tPage=2&ru=%2Fkaoyan%2Fretest%2F1002&qru=%2Fta%2Fpku-kaoyan%2Fquestion-ranking)

**描述**

给出一个01字符串（长度不超过100），求其每一个子串出现的次数。

**输入描述**：

输入包含多行，每行一个字符串。

**输出描述**：

对每个字符串，输出它所有出现次数在1次以上的子串和这个子串出现的次数，输出按字典序排序。

思路：由于map底层采用的红黑树，因此内部会将元素按照关键字字典序排序

~~~c++
#include <iostream>
#include <map>
using namespace std;

int main() {
    string str;
    while (cin >> str) {
        map<string, int> myMap;
        for (int i = 0; i < str.size(); i++) {
            for (int j = 1; j <= str.size() - i; j++) {
                string key = str.substr(i, j);
                if (myMap.find(key) != myMap.end())
                    myMap[key]++;
                else
                    myMap[key] = 1;
            }
        }
        map<string, int>::iterator it;
        for (it = myMap.begin(); it != myMap.end(); it++) {
            if (it->second > 1)
                cout << it->first << " " << it->second << endl;
        }
    }
}
~~~

#### 统计同成绩学生人数

[统计同成绩学生人数_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/987123efea5f43709f31ad79a318ca69?tpId=63&tqId=29583&tPage=2&ru=%2Fkaoyan%2Fretest%2F9001&qru=%2Fta%2Fzju-kaoyan%2Fquestion-ranking)

**描述**

读入N名学生的成绩，将获得某一给定分数的学生人数输出。

**输入描述**：

测试输入包含若干测试用例，每个测试用例的格式为 第1行：N 第2行：N名学生的成绩，相邻两数字用一个空格间隔。 第3行：给定分数 当读到N=0时输入结束。其中N不超过1000，成绩分数为（包含）0到100之间的一个整数。

**输出描述**：

对每个测试用例，将获得给定分数的学生人数输出。

思路：直接映射map，很好用的，相当于python的字典了

~~~c++
#include <iostream>
#include <map>
using namespace std;

int main() {
    int N;
    while (cin >> N) {
        map<int, int> myMap;
        if (N == 0)
            break;
        int score, query;
        while (N--) {
            cin >> score;
            myMap[score]++;
        }
        cin >> query;
        if (myMap.find(query) != myMap.end())
            cout << myMap[query] << endl;
        else
            cout << 0 << endl;
    }
}
~~~

注：**也可以用count**

* map.find返回的是迭代器，成功指向要查找的元素，失败指向end
* map.count返回整数，1表示有这个元素，0表示无

#### 开门人和关门人

[开门人和关门人_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/a4b37b53a44d454ab0834e1517983215?tpId=63&tqId=29587&tPage=2&ru=%2Fkaoyan%2Fretest%2F9001&qru=%2Fta%2Fzju-kaoyan%2Fquestion-ranking)

**描述**

每天第一个到机房的人要把门打开，最后一个离开的人要把门关好。现有一堆杂乱的机房签到、签离记录，请根据记录找出当天开门和关门的人。

**输入描述**：

每天的记录在第一行给出记录的条目数M (M > 0 )，下面是M行，每行的格式为   证件号码 签到时间 签离时间   其中时间按“小时:分钟:秒钟”（各占2位）给出，证件号码是长度不超过15的字符串。

**输出描述**：

对每一天的记录输出1行，即当天开门和关门人的证件号码，中间用1空格分隔。   注意：在裁判的标准测试输入中，所有记录保证完整，每个人的签到时间在签离时间之前，且没有多人同时签到或者签离的情况。

思路：使用map可以直接帮我们自动比较字符串的字典序并排列好，很方便

**需要注意的点**：map.begin()或end()属于迭代器，不能+1或-1，要用++或--

~~~c++
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    int M;
    while (cin >> M) {
        map<string, string> in;
        map<string, string> out;
        string num, in_t, out_t;
        while (M--) {
            cin >> num >> in_t >> out_t;
            in[in_t] = num;
            out[out_t] = num;
        }
        cout << in.begin()->second << " " << (--out.end())->second << endl;
    }
}
~~~

#### 谁是你的潜在朋友

**描述**

“臭味相投”——这是我们描述朋友时喜欢用的词汇。两个人是朋友通常意味着他们存在着许多共同的兴趣。然而作为一个宅男，你发现自己与他人相互了解的机会并不太多。幸运的是，你意外得到了一份北大图书馆的图书借阅记录，于是你挑灯熬夜地编程，想从中发现潜在的朋友。   首先你对借阅记录进行了一番整理，把N个读者依次编号为1,2,…,N，把M本书依次编号为1,2,…,M。同时，按照“臭味相投”的原则，和你喜欢读同一本书的人，就是你的潜在朋友。你现在的任务是从这份借阅记录中计算出每个人有几个潜在朋友。

**输入描述**：

每个案例第一行两个整数N,M，2 <= N ，M<= 200。接下来有N行，第i(i = 1,2,…,N)行每一行有一个数，表示读者i-1最喜欢的图书的编号P(1<=P<=M)

**输出描述**：

每个案例包括N行，每行一个数，第i行的数表示读者i有几个潜在朋友。如果i和任何人都没有共同喜欢的书，则输出“BeiJu”（即悲剧，^ ^）

思路：分别设置一个数组接收每个读者喜欢的书的编号，一个map接收每本书的喜欢人数

~~~c++
#include <iostream>
#include <map>
using namespace std;

int main() {
    int N, M;
    while (cin >> N >> M) {
        map<int, int> myMap;
        int readers[N];
        int p;
        for (int i = 0; i < N; i++) {
            cin >> p;
            myMap[p]++;
            readers[i] = p;
        }
        for (int i = 0; i < N; i++) {
            if (myMap[readers[i]] == 1)
                cout << "BeiJu" << endl;
            else
                cout << myMap[readers[i]] - 1 << endl;
        }
    }
}
~~~

最后修改：2023 年 06 月 23 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

Reverse（十一）
浏览次数: 2629
Win11新机鼓捣记录
浏览次数: 2382
栈~数制转换
浏览次数: 1604
C++学习
浏览次数: 1603
Python实现文件管理系统（重命名和删除）
浏览次数: 1575

顶点软件
你写得非常清晰明了，让我很容易理解你的观点。
mars
博主你好，请问怎么知道的alloc函数属于Buffer下的方法...
lj
该评论仅登录用户及评论双方可见
Mr.Guan
:@(赞一个)
Typecho
欢迎加入 Typecho 大家族

js逆向爬虫3
浏览次数: 502
CH1 静态分析
浏览次数: 400
古典密码技术
浏览次数: 855
机试Day1
浏览次数: 1083
可恶！
浏览次数: 917

C++数据结构2

Xherlock • 2023 年 06 月 23 日

# C++数据结构2

## 二叉树

### 相关知识

二叉树递归定义：二叉树要么为空，要么由根节点、左子树、右子树构成

遍历方法：前序遍历、中序遍历、后序遍历

### 题目

#### 二叉树遍历1

**描述**

**输入描述**：

输入包括1行字符串，长度不超过100。

**输出描述**：

可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。

~~~
输入：
abc##de#g##f###
输出：
c b e g d f a 
~~~

思路：记死二叉树遍历模板就行了

~~~c++
#include <iostream>
using namespace std;

struct TreeNode {
    char data;
    TreeNode *leftChild;
    TreeNode *rightChild;
    TreeNode(char c): data(c), leftChild(NULL), rightChild(NULL) {}
};

void InOrder(TreeNode* t) {
    if (t) {
        InOrder(t->leftChild);
        cout << t->data << " "; 
        InOrder(t->rightChild);
    }
}

int main() {
    string tree_s;
    while (cin >> tree_s) {
        int position = 0;
        TreeNode* t = build_tree(position, tree_s);
        InOrder(t);
        cout << endl;
    }
}
~~~

#### 二叉树遍历2

**描述**

**输入描述**：

两个字符串，其长度n均小于等于26。 第一行为前序遍历，第二行为中序遍历。 二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。

**输出描述**：

输入样例可能有多组，对于每组测试样例， 输出一行，为后序遍历的字符串。

~~~
输入：
ABC
BAC
FDXEAG
XDEFAG
输出：
BCA
XEDGAF
~~~

思路：本题同上一题，都是根据二叉树某种遍历结果求出二叉树，进而求另一种遍历结果

本题给出前序遍历和中序遍历，因此能够得到唯一的二叉树；前序的第一个字符肯定是root，而此root必然在中序中，因此可以不断拆分得到二叉树

~~~c++
#include <iostream>
using namespace std;

struct TreeNode {
    char data;
    TreeNode *leftChild;
    TreeNode *rightChild;
    TreeNode(char c): data(c), leftChild(NULL), rightChild(NULL) {}
};

void PostOrder(TreeNode* t) {
    if (t) {
        PostOrder(t->leftChild);
        PostOrder(t->rightChild);
        cout << t->data;
    }
}

int main() {
    string str1, str2;
    while (cin >> str1 >> str2) {
        TreeNode* root = Build(str1, str2);
        PostOrder(root);
        cout << endl;
    }
}
~~~

## 二叉排序树

### 相关知识

二叉排序树特征：

### 题目

#### 二叉排序树1

**描述**

**输入描述**：

**输出描述**：

输出共N行，每次插入节点后，该节点对应的父亲节点的关键字值。

思路：还是得多练下，二叉树数据结构学的只会概念，代码啥的基本没掌握住，方法是

~~~c++
#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *leftChild;
    TreeNode *rightChild;
    TreeNode(int v): val(v), leftChild(NULL), rightChild(NULL) {}
};

#### 二叉排序树2

**描述**

输入一系列整数，建立二叉排序树，并进行前序，中序，后序遍历。

**输入描述**：

输入第一行包括一个整数n(1<=n<=100)。 接下来的一行包括n个整数。

**输出描述**：

思路：先实现Insert，在前序、中序、后序遍历，背住就好

~~~c++
#include <iostream>
using namespace std;

struct TreeNode {
    int data;
    TreeNode *leftChild;
    TreeNode *rightChild;
    TreeNode(int data): data(data), leftChild(NULL), rightChild(NULL) {}
};

void PreOrder(TreeNode* root) {
    if (root) {
        cout << root->data << " ";
        PreOrder(root->leftChild);
        PreOrder(root->rightChild);
    }
}

void InOrder(TreeNode* root) {
    if (root) {
        InOrder(root->leftChild);
        cout << root->data << " ";
        InOrder(root->rightChild);
    }
}

void PostOrder(TreeNode* root) {
    if (root) {
        PostOrder(root->leftChild);
        PostOrder(root->rightChild);
        cout << root->data << " ";
    }
}

#### 二叉搜索树

**描述**

判断两序列是否为同一二叉搜索树序列

**输入描述**：

**输出描述**：

如果序列相同则输出YES，否则输出NO

~~~
输入：
2
567432
543267
576342
0
输出：
YES
NO
~~~

思路：insert函数和之前一样，主要是写compare函数来比较两棵树，从根节点开始

~~~c++
#include <iostream>
using namespace std;

struct TreeNode {
    char data;
    TreeNode *leftChild;
    TreeNode *rightChild;
    TreeNode(int data): data(data), leftChild(NULL), rightChild(NULL) {}
};

## 优先队列

### 相关知识

~~~c++
#include <queue>
priority_queue<typename> name;
~~~

优先队列：将数据按照事先规定的优先级次序进行动态组织的数据结构，访问元素时，只能访问当前队列中优先级最高的元素，**最高级先出**

### 题目

#### 复数集合

**描述**

**输入描述**：

输入有多组数据。 每组输入一个n(1<=n<=1000)，然后再输入n条指令。

**输出描述**：

根据指令输出结果。 模相等的输出b较小的复数。 a和b都是非负数。

思路：要设置个结构体，并重载小于号（因为类无法直接比较）

~~~c++
#include <iostream>
#include <queue>
using namespace std;

#### 哈夫曼树

哈夫曼树求法：

**描述**

**输入描述**：

输入有多组数据。 每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。

**输出描述**：

输出权值。

思路：优先队列处理，需要重新定义优先队列**priority_queue\<int, vector\<int\>, greater\<int\>\> myPriorityQueue;**

~~~c++
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

#### 查找第K小数

**描述**

查找一个数组的第K小的数，注意同样大小算一样大。 如 2 1 3 4 5 2 第三小数为3。

**输入描述**：

输入有多组数据。 每组输入n，然后输入n个整数(1<=n<=1000)，再输入k。

**输出描述**：

输出第k小的整数。

~~~
输入：
6
2 1 3 5 2 2
3
输出：
3
~~~

思路：可以使用优先队列来做

~~~c++
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

#### 搬水果

**描述**

**输入描述**：

**输出描述**：

对于每组输入，输出一个整数并换行，这个值也就是最小的体力耗费值。输入数据保证这个值小于 2^31。

思路：和哈夫曼树那题一模一样

## 散列表

### 相关知识

标准库中还有一个无序映射unordered_map，其底层使用散列表实现，期望的查找效率为$O(1)$

~~~c++
#include <map>
map<typename T1, typename T2> name;
~~~

**map元素的添加或删除**：insert()和erase()

**map元素的访问**：

1. [key]
2. at()
3. 迭代器

**map元素操作**：find()查找特定元素、clear()清空映射

### 题目

#### 查找学生信息

**描述**

输入N个学生的信息，然后进行查询。

**输入描述**：

**输出描述**：

输出M行，每行包括一个对应于查询的学生的信息。 如果没有对应的学生信息，则输出“No Answer!”

思路：使用线性表会很耗时，因此使用映射查找

###### 法1：使用结构体接受，比较清晰

~~~c++
#include <iostream>
#include <map>
#include <string>
using namespace std;

struct Student {
    string name, gender;
    int age;
};

###### 法2：每行看作一个字符串（getline()），输入输出较为简单

需要注意第一次输入N后需要用getchar()吃掉回车

~~~c++
#include <iostream>
#include <map>
#include <string>
using namespace std;

#### 魔咒词典

**描述**

**输入描述**：

**输出描述**：

每个测试用例的输出占一行，输出魔咒对应的功能，或者功能对应的魔咒。如果魔咒不在词典中，就输出“what?”

思路：我是使用了两个map来分开存储，需要注意的是不能使用cin直接获取输入，因为中间有空格，要使用getline来获取整行，然后对字符串进行分割

~~~c++
#include <iostream>
#include <map>
#include <string>
using namespace std;

**可以改进的**：题目中说了没有重复的魔咒、功能，因此放在一个映射里也可以

#### 子串计算

**描述**

给出一个01字符串（长度不超过100），求其每一个子串出现的次数。

**输入描述**：

输入包含多行，每行一个字符串。

**输出描述**：

对每个字符串，输出它所有出现次数在1次以上的子串和这个子串出现的次数，输出按字典序排序。

思路：由于map底层采用的红黑树，因此内部会将元素按照关键字字典序排序

~~~c++
#include <iostream>
#include <map>
using namespace std;

#### 统计同成绩学生人数

**描述**

读入N名学生的成绩，将获得某一给定分数的学生人数输出。

**输入描述**：

**输出描述**：

对每个测试用例，将获得给定分数的学生人数输出。

思路：直接映射map，很好用的，相当于python的字典了

~~~c++
#include <iostream>
#include <map>
using namespace std;

注：**也可以用count**

* map.find返回的是迭代器，成功指向要查找的元素，失败指向end
* map.count返回整数，1表示有这个元素，0表示无

#### 开门人和关门人

**描述**

每天第一个到机房的人要把门打开，最后一个离开的人要把门关好。现有一堆杂乱的机房签到、签离记录，请根据记录找出当天开门和关门的人。

**输入描述**：

**输出描述**：

思路：使用map可以直接帮我们自动比较字符串的字典序并排列好，很方便

**需要注意的点**：map.begin()或end()属于迭代器，不能+1或-1，要用++或--

~~~c++
#include <iostream>
#include <map>
#include <string>
using namespace std;

#### 谁是你的潜在朋友

**描述**

**输入描述**：

每个案例第一行两个整数N,M，2 <= N ，M<= 200。接下来有N行，第i(i = 1,2,…,N)行每一行有一个数，表示读者i-1最喜欢的图书的编号P(1<=P<=M)

**输出描述**：

每个案例包括N行，每行一个数，第i行的数表示读者i有几个潜在朋友。如果i和任何人都没有共同喜欢的书，则输出“BeiJu”（即悲剧，^ ^）

思路：分别设置一个数组接收每个读者喜欢的书的编号，一个map接收每本书的喜欢人数

~~~c++
#include <iostream>
#include <map>
using namespace std;

发表评论 取消回复

C++数据结构2

发表评论取消回复