本章介绍机试中考查的一些非线性数据结构，包括二叉树、二叉排序树、优先队列和散列表等较为高级的数据结构。
10.1 二叉树（Binary Tree）
二叉树的递归定义：二叉树要么为空，要么由根节点（Root）、左子树（Left Subtree）和右子树（Right Subtree）构成，而左右两个子树又分别是一棵二叉树。
每个结点的定义如下：
struct TreeNode{
ElementType data;
TreeNode *leftChild;
TreeNode *rightChild;
};
常考——遍历算法：前序遍历（NLR）、中序遍历（LNR）、后序遍历（LRN）。其中的序是指根节点在何时被访问。
层序遍历：按照广搜BFS的方法进行遍历。
例题10.1 二叉树遍历
提交网址
#include <iostream>
using namespace std;
typedef struct node{
char data;
struct node *lc, *rc;
}BTree;
string str;
int pos;
BTree* CreateBTree(){
char c = str[pos++];
if(c == '#'){
return NULL;
}
BTree *t = (BTree*) malloc(sizeof(BTree));
t->data = c;
t->lc = CreateBTree();
t->rc = CreateBTree();
return t;
}
void InOrdOutput(BTree *t){
if(t == NULL){
return;
}
InOrdOutput(t->lc);
printf("%c ", t->data);
InOrdOutput(t->rc);
return;
}
int main(){
while(getline(cin, str)){
pos = 0;
BTree *T = CreateBTree();
InOrdOutput(T);
printf("\n");
}
return 0;
}
例题10.2 二叉树遍历
提交网址 和数据结构的noj题目一模一样。可以拿之前的noj题目来复习了。
#include <iostream>
#include <string>
using namespace std;
typedef struct node{
char data;
struct node *lc, *rc;
}BTree;
BTree* PreInOrd(string P, string I){
if(P.size() == 0 || I.size() == 0) return NULL;
BTree *t = (BTree*) malloc(sizeof(BTree));
t->data = P[0];
int pos = I.find(P[0]);
t->lc = PreInOrd(P.substr(1, pos), I.substr(0, pos));
t->rc = PreInOrd(P.substr(pos+1), I.substr(pos+1));
return t;
}
void PostOrdOutput(BTree *t){
if(t == NULL) return;
PostOrdOutput(t->lc);
PostOrdOutput(t->rc);
printf("%c", t->data);
}
int main(){
string pre, in;
while(cin >> pre >> in){
int len = pre.length();
BTree* T = PreInOrd(pre, in);
PostOrdOutput(T);
printf("\n");
}
return 0;
}
10.2 二叉排序树（二叉搜索树 Binary Search Tree）
一棵非空的二叉排序树具有如下的特征：
- 若左子树非空，则左子树上所有结点关键字均小于根结点关键字的值。
- 若右子树非空，则右子树上所有结点关键字均大于根结点关键字的值。
- 左、右子树本身也是一棵二叉排序树。
下面的两道例题都是需要用到插入的方法来进行二叉排序树的建树。
例题10.3 二叉排序树
提交网址
#include <iostream>
using namespace std;
struct TreeNode{
int data;
TreeNode *lc, *rc;
TreeNode(int x): data(x), lc(NULL), rc(NULL) {}
};
TreeNode* Insert(TreeNode *root, int x, int father){
if(root == NULL){
root = new TreeNode(x);
printf("%d\n", father);
}else if(x < root->data){
root->lc = Insert(root->lc, x, root->data);
}else{
root->rc = Insert(root->rc, x, root->data);
}
return root;
}
int main(){
int n;
while(scanf("%d", &n) != EOF){
TreeNode *root = NULL;
for(int i=0; i<n; i++){
int x;
scanf("%d", &x);
root = Insert(root, x, -1);
}
}
return 0;
}
例题10.4 二叉排序树
提交网址
#include <iostream>
using namespace std;
struct BTree{
int data;
BTree *lc, *rc;
BTree(int x): data(x), lc(NULL), rc(NULL) {}
};
BTree* Insert(BTree* t, int x){
if(t == NULL){
BTree* tmp = new BTree(x);
return tmp;
}
if(t->data < x){
t->rc = Insert(t->rc, x);
}else if(t->data > x){
t->lc = Insert(t->lc, x);
}
return t;
}
void PreOrder(BTree* t){
if(t == NULL) return;
printf("%d ", t->data);
PreOrder(t->lc);
PreOrder(t->rc);
}
void InOrder(BTree* t){
if(t == NULL) return;
InOrder(t->lc);
printf("%d ", t->data);
InOrder(t->rc);
}
void PostOrder(BTree* t){
if(t == NULL) return;
PostOrder(t->lc);
PostOrder(t->rc);
printf("%d ", t->data);
}
int main(){
int n;
while(scanf("%d", &n) != EOF){
BTree* T = NULL;
int x;
while(n--){
scanf("%d", &x);
T = Insert(T, x);
}
PreOrder(T);
printf("\n");
InOrder(T);
printf("\n");
PostOrder(T);
printf("\n");
}
return 0;
}
习题10.1 二叉搜索树
提交网址
#include <iostream>
using namespace std;
struct BTree{
int data;
BTree *lc, *rc;
BTree(int x): data(x), lc(NULL), rc(NULL) {}
};
BTree* Insert(BTree* t, int x){
if(t == NULL){
BTree* tmp = new BTree(x);
return tmp;
}
if(t->data < x){
t->rc = Insert(t->rc, x);
}else if(t->data > x){
t->lc = Insert(t->lc, x);
}
return t;
}
bool Equal(BTree *x, BTree *y){
if(x == NULL && y == NULL){
return true;
}else if(x == NULL || y == NULL){
return false;
}
return x->data == y->data && Equal(x->lc, y->lc) && Equal(x->rc, y->rc);
}
int main(){
int n;
while(scanf("%d", &n) != EOF){
string x, y;
BTree *ref = NULL;
cin >> x;
for(int i=0; i<x.length(); i++){
ref = Insert(ref, x[i] - '0');
}
BTree *t;
for(int i=0; i<n; i++){
cin >> y;
t = NULL;
for(int j=0; j<y.length(); j++){
t = Insert(t, y[j] - '0');
}
if(Equal(ref, t)){
printf("YES\n");
}else{
printf("NO\n");
}
}
}
return 0;
}
10.3 优先队列（Priority Queue）
在优先级队列中，每个元素都被赋予了优先级，访问元素时，只能访问当前队列中优先级最高的元素，即最高级先出（First-In Breatest-Out）。
1. STL-priority_queue
标准库中的优先队列模板：（使用二叉堆实现）
#include <queue>
1. priority_queue的定义：priority_queue<typename> name
2. priority_queue的状态：empty(), size()
3. priority_queue元素的添加或删除：push(), pop()
4. priority_queue元素的访问：top()来访问当前队列中优先级最高的元素
2. 优先队列的应用
（1）顺序问题
例题10.5 复数集合
提交网址
#include <iostream>
#include <queue>
using namespace std;
struct Complex{
int real;
int 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(scanf("%d", &n) != EOF){
priority_queue<Complex> myPriorityQueue;
while(n--){
string str;
cin >> str;
if(str == "Pop"){
if(myPriorityQueue.empty()){
printf("empty\n");
}else{
Complex current = myPriorityQueue.top();
myPriorityQueue.pop();
printf("%d+i%d\n", current.real, current.imag);
printf("SIZE = %d\n", myPriorityQueue.size());
}
}else{
int a, b;
scanf("%d+i%d", &a, &b);
myPriorityQueue.push(Complex(a, b));
printf("SIZE = %d\n", myPriorityQueue.size());
}
}
}
return 0;
}
（2）哈夫曼树（Huffman Tree）/ 最优树
由于n个带有权值的结点构成的哈夫曼树可能不唯一，所以关于哈夫曼树的机试往往考察的是求解最小带权路径长度和。
例题10.6 哈夫曼树
提交网址 这一题用优先队列确实很妙啊！
如果要采用小根堆，即 优先级低的先输出 ，那么就需要按照
priority_queue<typename, vector<typename>, greater<typename>> name
的方式重新定义优先队列。
#include <iostream>
#include <queue>
using namespace std;
int main(){
int n;
while(scanf("%d", &n) != EOF){
priority_queue<int, vector<int>, greater<int>> myPriorityQueue;
int num;
while(n--){
scanf("%d", &num);
myPriorityQueue.push(num);
}
int answer = 0;
while(myPriorityQueue.size() >= 2){
int a = myPriorityQueue.top();
myPriorityQueue.pop();
int b = myPriorityQueue.top();
myPriorityQueue.pop();
answer += a + b;
myPriorityQueue.push(a + b);
}
printf("%d\n", answer);
}
return 0;
}
习题10.2 查找第K小的数
提交网址
只用sort也可以做这一题，函数中unique可以去重。如果不记得，自己写出来也不麻烦。
不是后续存在动态插入和删除，就可以用sort代替。
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int n, k;
int a[1000];
while(scanf("%d", &n) != EOF){
for(int i=0; i<n; i++){
scanf("%d", &a[i]);
}
scanf("%d", &k);
sort(a, a + n);
unique(a, a + n);
printf("%d\n", a[k - 1]);
}
return 0;
}
习题10.3 搬水果
提交网址 思路和例题10.6 哈夫曼树一样的。
#include <iostream>
#include <queue>
using namespace std;
int main(){
int n, tmp;
while(scanf("%d", &n) != EOF){
if(n == 0) break;
priority_queue<int, vector<int>, greater<int>> q;
while(n--){
scanf("%d", &tmp);
q.push(tmp);
}
int answer = 0;
while(q.size() >= 2){
int a = q.top();
q.pop();
int b = q.top();
q.pop();
answer += a + b;
q.push(a + b);
}
printf("%d\n", answer);
}
return 0;
}
10.4 散列表
散列表是一种根据关键字（Key）直接进行访问的数据结构，通过建立关键字和存储位置的直接映射关系(map)，便可利用关键码直接访问元素，以加快查找的速度。
1. STL-map
映射模板map：map是一个将关键字(key)和映射值(value)形成一对映射后进行绑定存储的容器。
map的底层是用红黑树实现的，内部仍然是有序的，其查找效率仍然为O(logn)。
标准库中还有一个无序映射unordered_map，其底层是用散列表实现的，其期望的查找效率为O(1)。
#include <map>
1. map的定义：map<typename T1, typename T2> name;
2. map的状态：empty(), size()
3. map元素的添加和删除：insert(), erase()
4. map元素的访问：
1. 由于map内部重载了[]运算符，因此可以通过[key]的方式访问
2. 可以使用at()进行访问
3. 还可以使用迭代器进行访问
5. map元素操作：find(), clear()
6. map迭代器操作：begin(), end()
2. 映射的应用
例题10.7 查找学生信息
提交网址
#include <iostream>
#include <map>
using namespace std;
int main(){
int n;
map<string, string> mp;
scanf("%d", &n);
getchar();
string str;
while(n--){
getline(cin, str);
string key = str.substr(0, str.find(" "));
mp[key] = str;
}
scanf("%d", &n);
while(n--){
cin >> str;
string answer = mp[str];
if(answer == ""){
answer = "No Answer!";
}
cout << answer << endl;
}
return 0;
}
例题10.8 魔咒词典
提交网址
这一题需要注意一下字符串的输入和输出，什么时候使用getchar等等。
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main(){
string key, value, str;
map<string, string> dictionary;
while(getline(cin, str)){
if(str == "@END@") break;
int pos = str.find("]");
key = str.substr(0, pos + 1);
value = str.substr(pos + 2);
dictionary[key] = value;
dictionary[value] = key;
}
int n;
scanf("%d", &n);
getchar();
while(n--){
getline(cin, str);
string out = dictionary[str];
if(out == ""){
cout << "what?" << endl;
}else if(out[0] == '['){
cout << out.substr(1, out.size() - 2) << endl;
}else{
cout << out << endl;
}
}
return 0;
}
例题10.9 子串计算
提交网址
对于这一题，由于map底层采用的是红黑树，因此在其内部仍然会将元素按照关键字进行排序，故输出顺序也刚好符合题目的要求。
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main(){
string str;
while(cin >> str){
map<string, int> num;
for(int i=0; i<=str.size(); i++){
for(int j=0; j<i; j++){
string key = str.substr(j, i - j);
num[key]++;
}
}
map<string, int>::iterator it;
for(it = num.begin(); it != num.end(); it++){
if(it->second > 1){
cout << it->first << " " << it->second << endl;
}
}
}
return 0;
}
习题10.4 统计同成绩学生人数
提交网址 其实这一题用map反而浪费，因为只需要计算一个分数的人数，就算遍历也只需要一次。为了练习还是使用map做吧。
#include <iostream>
#include <map>
using namespace std;
int main(){
int n;
while(scanf("%d", &n) != EOF){
if(n == 0) break;
map<int, int> mp;
int grade;
while(n--){
scanf("%d", &grade);
mp[grade]++;
}
scanf("%d", &grade);
printf("%d\n", mp[grade]);
}
return 0;
}
习题10.5 开门人和关门人
提交网址 这题居然能用map，绝绝子。注意迭代器end()不是指向最后一个，需要向前移一位。
#include <iostream>
#include <map>
using namespace std;
int main(){
int n;
while(scanf("%d", &n) != EOF){
string name, openTime, closeTime;
map<string, string> open;
map<string, string> close;
while(n--){
cin >> name >> openTime >> closeTime;
open[openTime] = name;
close[closeTime] = name;
}
cout << open.begin()->second << " " << (--close.end())->second << endl;
}
return 0;
}
习题10.6 谁是你的潜在朋友
提交网址
#include <iostream>
#include <map>
using namespace std;
int main(){
int n, m;
while(scanf("%d%d", &n, &m) != EOF){
map<int, int> mp;
int a[200];
for(int i=0; i<n; i++){
scanf("%d", &a[i]);
mp[a[i]]++;
}
for(int i=0; i<n; i++){
int num = mp[a[i]] - 1;
if(num == 0){
printf("BeiJu\n");
}else{
printf("%d\n", num);
}
}
}
return 0;
}
|