【数据结构入门精讲 | 第十三篇】考研408、公司面试树专项练习（二）
在上一篇中我们进行了树的判断题、选择题、填空题专项练习，在这一篇中我们将进行编程题的相关练习。
目录
编程题
R7-1 目录树
在ZIP归档文件中，保留着所有压缩文件和目录的相对路径和名称。当使用WinZIP等GUI软件打开ZIP归档文件时，可以从这些信息中重建目录的树状结构。请编写程序实现目录的树状结构的重建工作。
输入格式:
输入首先给出正整数N（≤104），表示ZIP归档文件中的文件和目录的数量。随后N行，每行有如下格式的文件或目录的相对路径和名称（每行不超过260个字符）：
- 路径和名称中的字符仅包括英文字母（区分大小写）；
- 符号“\”仅作为路径分隔符出现；
- 目录以符号“\”结束；
- 不存在重复的输入项目；
- 整个输入大小不超过2MB。
输出格式:
假设所有的路径都相对于root目录。从root目录开始，在输出时每个目录首先输出自己的名字，然后以字典序输出所有子目录，然后以字典序输出所有文件。注意，在输出时，应根据目录的相对关系使用空格进行缩进，每级目录或文件比上一级多缩进2个空格。
输入样例:
7
b
c\
ab\cd
a\bc
ab\d
a\d\a
a\d\z\
输出样例:
root
a
d
z
a
bc
ab
cd
d
c
b
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#define MAXN 100010
using namespace std;
struct node {
string name;
int isCata; // 目录文件标记
vector<node*> child; // 孩子指针
};
bool cmp(node* a, node* b) {
if(a->isCata != b->isCata) return a->isCata > b->isCata;
else return a->name < b->name;
}
void dfs(node* root,int level) {
if(root == NULL) return ;
// 先输出自己
for(int i = 0; i < level; ++i) printf(" ");
printf("%s\n",root->name.c_str()) ;
// 排序所有孩子 ： 目录在前，文件在后，字典升序
sort(root->child.begin(),root->child.end(),cmp);
// 向下递归
for(int i = 0; i < root->child.size(); ++i)
dfs(root->child[i],level+1);
}
int n;
int main() {
scanf("%d",&n);
getchar();
// 建立根节点
node* root = new node;
root->name = "root";
root->isCata = 1;
string tmp,str;
node* curRoot;
for(int j = 0; j < n; ++j) {
// 每一个新的路径，都将根设为 root
curRoot = root;
getline(cin,str);
for(int i = 0; i <= str.size(); ++i) {
if(str[i] == '\\') { // 情况 1. 是目录 ： 切换当前目录，
// 在当前父目录中寻找，看是否存在
int flag = 0;
for(int k = 0; k < curRoot->child.size(); ++k) {
// 1.1 有该目录
if(curRoot->child[k]->name == tmp && curRoot->child[k]->isCata == 1) {
// 则切换当前目录
curRoot = curRoot->child[k];
flag = 1;
break;
}
}
// 1.2 没有该目录则创建一个
if(!flag) {
// 创建结点
node* newnode = new node;
newnode->name = tmp;
newnode->isCata = 1;
// 加入父目录
curRoot->child.push_back(newnode) ;
// 切换当前目录
curRoot = newnode;
}
// 单词清零
tmp.clear();
// 情况 2. 是文件
}else if(i == str.size()) {
if(!tmp.empty()) { // 到达最后，而单词不空，说明是文件
// 将文件加入到父节点中
node* newnode = new node;
newnode->name = tmp;
newnode->isCata = 0;
curRoot->child.push_back(newnode) ;
}
tmp.clear();
} else { // 情况 3. 累加单词字母
tmp += str[i];
}
}
}
// 输出过程
dfs(root,0);
return 0;
}
R7-1 是否同一棵二叉搜索树
给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。
输入格式:
输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤10)和L，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列。随后L行，每行给出N个插入的元素，属于L个需要检查的序列。
简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为0时，标志输入结束，这组数据不要处理。
输出格式:
对每一组需要检查的序列，如果其生成的二叉搜索树跟对应的初始序列生成的一样，输出“Yes”，否则输出“No”。
输入样例:
4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0
输出样例:
Yes
No
No
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct TreeNode *Tree;
struct TreeNode{
ElementType Data;
Tree Left;
Tree Right;
int flag; //判别一个序列，没被访问设为0，被访问设为1
};
typedef Tree BinTree;
BinTree Create(int N);
BinTree NewNode(int V);
BinTree Insert(BinTree T,int V);
int Judge(BinTree T,int N);
int check(BinTree T,int V);
void ResetT(BinTree T);
void FreeTree(BinTree T);
int main()
{
int N,L,i;
BinTree T;
scanf("%d",&N);
while(N)
{
scanf("%d",&L);
T = Create(N);
for(i = 0; i < L;i++)
{
if(Judge(T,N)) printf("Yes\n");
else printf("No\n");
ResetT(T); /* 清除T中的标记flag*/
}
FreeTree(T); /* 比较完一组就释放*/
scanf("%d",&N);
}
}
void FreeTree(BinTree T)
{
if(T->Left) FreeTree(T->Left);
if(T->Right) FreeTree(T->Right);
free(T);
}
void ResetT(BinTree T)
{
if(T->Left) ResetT(T->Left);
if(T->Right) ResetT(T->Right);
T->flag = 0;
}
BinTree Create(int N)
{
BinTree T = NULL;
int V,i;
scanf("%d",&V);
T = NewNode(V);
for(i = 0;i < N-1;i++)
{
scanf("%d",&V);
T = Insert(T,V);
}
return T;
}
BinTree NewNode(int V)
{
BinTree BT;
BT = (BinTree)malloc(sizeof(struct TreeNode));
BT->Data = V;
BT->Left = NULL;
BT->Right = NULL;
BT->flag = 0;
return BT;
}
BinTree Insert(BinTree T,int V)
{
BinTree TNode;
if(!T) T = NewNode(V);
else{
if(T->Data < V)
{
T->Right = Insert(T->Right,V);
}
if(T->Data > V)
{
T->Left = Insert(T->Left,V);
}
}
return T;
}
/*当发现序列中的某个数和T不一样，必须把序列后面的数都读完*/
int Judge(BinTree T,int N)
{
int i;
int V;
int flag = 0;
/*flag:0 代表目前一致 flag:1 代表已经不一致 */
scanf("%d",&V);
if(V!=T->Data) flag = 1;
else T->flag = 1;
for (i = 1; i < N;i++)
{
scanf("%d",&V);
/* 若check为0，则return 0；之前出现的节点没有被访问过，出现新的节点，所以树不一致*/
if(!flag && !check(T,V)) flag = 1;
}
if(flag)
return 0;
else return 1;
}
int check(BinTree T,int V)
{
if(T->flag)
{
if(V > T->Data) return check(T->Right,V);
if(V < T->Data) return check(T->Left,V);
// 若相等，则说明之前已经出现过一个相同的数，则两个树不一致
if(V == T->Data) return 0;
}
else{
if(V == T->Data)
{
T->flag = 1;
return 1;
}
else{
return 0;
}
}
}
R7-2 二叉搜索树的结构
二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。（摘自百度百科）
给定一系列互不相等的整数，将它们顺次插入一棵初始为空的二叉搜索树，然后对结果树的结构进行描述。你需要能判断给定的描述是否正确。例如将{ 2 4 1 3 0 }插入后，得到一棵二叉搜索树，则陈述句如“2是树的根”、“1和4是兄弟结点”、“3和0在同一层上”（指自顶向下的深度相同）、“2是4的双亲结点”、“3是4的左孩子”都是正确的；而“4是2的左孩子”、“1和3是兄弟结点”都是不正确的。
输入格式：
输入在第一行给出一个正整数N（≤100），随后一行给出N个互不相同的整数，数字间以空格分隔，要求将之顺次插入一棵初始为空的二叉搜索树。之后给出一个正整数M（≤100），随后M行，每行给出一句待判断的陈述句。陈述句有以下6种：
A is the root，即"A是树的根"；A and B are siblings，即"A和B是兄弟结点"；A is the parent of B，即"A是B的双亲结点"；A is the left child of B，即"A是B的左孩子"；A is the right child of B，即"A是B的右孩子"；A and B are on the same level，即"A和B在同一层上"。
题目保证所有给定的整数都在整型范围内。
输出格式：
对每句陈述，如果正确则输出Yes，否则输出No，每句占一行。
输入样例：
5
2 4 1 3 0
8
2 is the root
1 and 4 are siblings
3 and 0 are on the same level
2 is the parent of 4
3 is the left child of 4
1 is the right child of 2
4 and 0 are on the same level
100 is the right child of 3
输出样例：
Yes
Yes
Yes
Yes
Yes
No
No
No
#include <iostream>
#include <string>
#include <string.h>
#include <map>
using namespace std;
const int MAX = 1e7 + 10;
int tree[MAX]; //二叉搜索树
int deepth[MAX]; //结点深度
int tem;
map<int, int> num; //键值对应的结点编号
void creatTree(int x, int d) //建立二叉搜索树
{
if (tree[x] == 0x3f3f3f3f)
{
tree[x] = tem;
num.insert(make_pair(tem, x));
deepth[x] = d;
}
else
{
if (tem < tree[x])
creatTree(x * 2, d + 1);
else
creatTree(x * 2 + 1, d + 1);
}
return;
}
int main()
{
int n; cin >> n;
memset(tree, 0x3f, sizeof(tree)); //将每个元素初始化为0x3f3f3f3f
for (int i = 0; i < n; i++)
{
cin >> tem;
creatTree(1, 1);
}
int k; cin >> k;
while (k--)
{
string str;
int a, b;
cin >> a >> str;
if (str == "and")
{
cin >> b >> str >> str;
if (str == "siblings")
{
if (num.find(a) == num.end() || num.find(b) == num.end())
cout << "No" << endl;
else if (num[a] / 2 == num[b] / 2)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
else
{
getline(cin, str);
if (num.find(a) == num.end() || num.find(b) == num.end())
cout << "No" << endl;
else if (deepth[num[a]] == deepth[num[b]])
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
else
{
cin >> str >> str;
if (str == "root")
{
if (num.find(a) == num.end())
cout << "No" << endl;
else if (num[a] == 1)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
else if (str == "parent")
{
cin >> str >> b;
if (num.find(a) == num.end() || num.find(b) == num.end())
cout << "No" << endl;
else if (num[a] == num[b] / 2)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
else if (str == "left")
{
cin >> str >> str >> b;
if (num.find(a) == num.end() || num.find(b) == num.end())
cout << "No" << endl;
else if (num[b] * 2 == num[a])
cout << "Yes" << endl;
else
cout << "No" << endl;
}
else
{
cin >> str >> str >> b;
if (num.find(a) == num.end() || num.find(b) == num.end())
cout << "No" << endl;
else if (num[b] * 2 + 1 == num[a])
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
}
return 0;
}
R7-3 平衡二叉树的根
将给定的一系列数字插入初始为空的AVL树，请你输出最后生成的AVL树的根结点的值。
输入格式:
输入的第一行给出一个正整数N（≤20），随后一行给出N个不同的整数，其间以空格分隔。
输出格式:
在一行中输出顺序插入上述整数到一棵初始为空的AVL树后，该树的根结点的值。
输入样例1:
5
88 70 61 96 120
输出样例1:
70
输入样例2:
7
88 70 61 96 120 90 65
输出样例2:
88
#include <iostream>
using namespace std;
struct Node {
int data;
Node* lc;
Node* rc;
};
int height(Node* T) {
return T == NULL ? 0 : max(height(T->lc), height(T->rc)) + 1;
}
Node* turn1(Node* T) { //单向右旋
Node* A = T->lc;
T->lc = A->rc;
A->rc = T;
return A;
}
Node* turn2(Node* T) { //单向左旋
Node* A = T->rc;
T->rc = A->lc;
A->lc = T;
return A;
}
Node* turn3(Node* T) { //先左旋后右旋
T->lc = turn2(T->lc);
return turn1(T);
}
Node* turn4(Node* T) { //先右旋后左旋
T->rc = turn1(T->rc);
return turn2(T);
}
Node* Insert(Node* T, int x) {
if (!T)
T = new Node({ x,NULL,NULL });
else if (x < T->data) {
T->lc = Insert(T->lc, x);
if (height(T->lc) - height(T->rc) == 2)
T = (x < T->lc->data ? turn1(T) : turn3(T));
}
else if (x > T->data) {
T->rc = Insert(T->rc, x);
if (height(T->lc) - height(T->rc) == -2)
T = (x > T->rc->data ? turn2(T) : turn4(T));
}
return T;
}
int main() {
Node* Tree = NULL;
int n, t;
cin >> n;
while (n--) {
cin >> t;
Tree = Insert(Tree, t);
}
cout << Tree->data << endl;
return 0;
}
R7-1 完全二叉搜索树
一个无重复的非负整数序列，必定对应唯一的一棵形状为完全二叉树的二叉搜索树。本题就要求你输出这棵树的层序遍历序列。
输入格式：
首先第一行给出一个正整数 N（≤1000），随后第二行给出 N 个不重复的非负整数。数字间以空格分隔，所有数字不超过 2000。
输出格式：
在一行中输出这棵树的层序遍历序列。数字间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：
10
1 2 3 4 5 6 7 8 9 0
输出样例：
6 3 8 1 5 7 9 0 2 4
#include <iostream>
#include <algorithm>
using namespace std;
int in[1001];
int res[1001];
int n,len;
void dfs(int i){
if(i>n)
return;
dfs(2*i);
res[i] = in[++len];
dfs(2*i+1);
}
int main(){
cin >> n;
for(int i = 1;i<=n;i++){
cin >> in[i];
}
sort(in+1,in+1+n);
dfs(1);
for(int i = 1;i<=n;i++){
if(i==1)
cout << res[i];
else
cout << " " << res[i];
}
return 0;
}
R7-1 修理牧场
农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数Li个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是Li的总和。
但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。
请编写程序帮助农夫计算将木头锯成N块的最少花费。
输入格式:
输入首先给出正整数N（≤104），表示要将木头锯成N块。第二行给出N个正整数（≤50），表示每段木块的长度。
输出格式:
输出一个整数，即将木头锯成N块的最少花费。
输入样例:
8
4 5 1 2 1 3 1 1
输出样例:
49
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const ll maxx=1e18;
const int N=1E6+100;
const int p=1e4;
const double eps =1e-8;
priority_queue<int,vector<int>,greater<int>>pmin;
int n,t,sum;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>t;
pmin.push(t);
}
while(pmin.size()!=1)
{
int k1,k2;
k1=pmin.top();
pmin.pop();
k2=pmin.top();
pmin.pop();
sum+=(k1+k2);
pmin.push(k1+k2);
}
cout<<sum;
}
R7-2 嘴强王者
在召唤师峡谷中，优秀的召唤师总是喜欢比较自己的战斗力强弱，而青铜召唤师也不甘示弱，他们比较嘴炮的强弱。由于他们的嘴炮水平总是不断变化，难以通过人工进行比较，因此请你帮他们开发一个算法，找出其中的嘴强王者。
输入格式:
第一行两个正整数n,m，表示有n个选手，m次操作（1≤n≤105,1≤m≤5000)。
第二行有n个整数，分别表示第i个选手的初始嘴炮值ai；选手的编号从1到n。
接下来有m行，每行三个正整数x,l,r;
当x=1时，这是一个询问操作，询问区间[l,r]里面嘴炮值最高的召唤师，即嘴强王者；
当x=0时，这是一个更新操作，表示选手l的嘴炮值更新为r。
题目保证在每个查询区间内，嘴强王者是唯一的。
输出格式:
对于每个询问操作，在一行里面输出里面的嘴强王者的编号及其嘴炮值，用用空格分隔，行末没有多余空格。
输入样例:
5 6
1 2 3 4 5
1 1 5
0 3 6
1 3 4
1 4 5
0 2 9
1 1 5
输出样例:
在这里给出相应的输出。例如：
5 5
3 6
5 5
2 9
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
int n, m;
int v[18][1 << 17];
int h = 1;
void build() {
for (int i = 1; i <= h; i++) {
int span = pow(2, i);
for (int j = 1; j <= n; j += span) {
v[i][j] = max(v[i - 1][j], v[i - 1][j + (span / 2)]);
}
}
}
int update(int index, int val, int ll, int rr) {
int idx = log2(rr - ll + 1);
int mid = (ll + rr) / 2;
if (ll > index || rr < index) return v[idx][ll];
if (ll == rr) {
if (ll == index) {
v[0][index] = val;
return val;
}
else return v[0][ll];
}
// 更新最大值
return v[idx][ll] = max(update(index, val, ll, mid), update(index, val, mid + 1, rr));
}
int find(int l, int r, int ll, int rr) {
if (rr < l || ll > r) return 0;
int idx = log2(rr - ll + 1);
if (ll >= l && rr <= r) return v[idx][ll];
int mid = (ll + rr) / 2;
return max(find(l, r, ll, mid), find(l, r, mid + 1, rr));
}
int main() {
cin >> n >> m;
while (pow(2, h) < n) h++;
map<int, set<int>> mp; // 用来记录下标的小技巧
for (int i = 1; i <= n; i++) {
cin >> v[0][i];
mp[v[0][i]].insert(i);
}
build();
for (int i = 0; i < m; i++) {
int x, l, r;
cin >> x >> l >> r;
if (x == 1) {
int ans = find(l, r, 1, pow(2, h));
int idx = *mp[ans].lower_bound(l); // 二分快速查找当前的下标
cout << idx << " " << ans << endl;
}
else {
mp[v[0][l]].erase(l); // 更新时删除原来的下标
mp[r].insert(l); // 添加新的下标
update(l, r, 1, pow(2, h));
}
}
return 0;
}
R7-3 房屋分拆
厂长买了一整间房屋作为车间，现准备将整个房屋分成若干个车间。装修公司规定分拆房屋的价格等于被分拆房屋的面积。如想将面积为200的房间分拆为面积为80、70和50的三个车间，第一次将房屋分拆为面积120和80的两个房间，花费200，第二次将面积为120的房间分拆为面积为70和50的两个房间，花费120，总花费为320。如果采用另一种方案，第一次将面积200的房屋分拆为150和50，花费200，第二次将面积为150的房间分拆为80和70的房间，花费150，则总花费为350。显然第一种方案花费更少。请编写程序为厂长设计花费最少的分拆方案。
输入格式:
输入为两行，第一行为一个整数n，表示所需的车间数量。第二行为n个正整数，以空格间隔，给出每个车间需要的面积。n不超过100000，且保证最终结果小于231。
输出格式:
输出为一个整数，表示将整个房屋分拆为n个车间所需的最少花费。
输入样例:
8
1 1 1 1 2 3 4 5
输出样例:
49
#include<stdio.h>
#include<stdlib.h>
typedef struct Node * Heap; /*堆结构*/
struct Node
{
int * Data;
int Size;
};
typedef Heap MinHeap;/*最小堆*/
Heap CreateHeap(int n)//最小堆的创建
{
MinHeap H=(MinHeap)malloc(sizeof(struct Node));
H->Data=(int *)malloc(2*(n+1)*sizeof(int));
H->Size=0;//初始化
H->Data[0]=0;/*最小堆的哨兵*/
return H;
}
void Insert(Heap H,int m)//建初堆
{
int i;
i=++H->Size;
for(; H->Data[i/2]>m; i/=2)
H->Data[i]=H->Data[i/2];
H->Data[i]=m;
}
int Del(Heap H)//重建小跟堆
{
int parent,child;
int min,x;
min=H->Data[1];
x=H->Data[H->Size--];//用最后一个元素替代已经输出的堆顶元素
for(parent=1; parent*2<=H->Size ; parent=child) //沿较小的孩子向下筛选{
{
child=parent*2;
if((child!=H->Size)&&(H->Data[child]>H->Data[child+1])) child++;
if(H->Data[child]>=x) break;
else H->Data[parent]=H->Data[child];
}
H->Data[parent]=x;
return min;
}
int main()
{
int n,m,i,sum=0,a,b;
scanf("%d",&n);
Heap H=CreateHeap(n);
for(i=1; i<=n; i++)
{
scanf("%d",&m);
Insert(H,m);/*将所有元素入堆(H)*/
}
while(H->Size!=1)
{
a=Del(H);//去掉最小值再重建堆
b=Del(H);//去掉次小值再重建堆
b=a+b;
sum+=b;//不断累加求和
Insert(H,b);
}
printf("%d\n",sum);
// system("pause");
return 0;
}
R7-4 动态区间求和
输入样例:
3 2
1 2 3
1 2 0
2 1 3
输出样例:
6
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 5;
ll n, q, c[MAXN];//树状数组， 下标为某一个元素， 值为这个元素出现的次数
int lowbit(int x) {
return x&(-x);
}
//update将第x个整数加上v
void update(int x, int v)
{
for (int i = x; i <= n; i += lowbit(i)) {
c[i] += v;
}
}
//getSum返回前x个整数之和
ll getSum(int x) {
ll sum = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
sum += c[i];
}
return sum;
}
int main()
{
cin >> n >> q;
memset(c, 0, sizeof(c));
for (int i = 1; i <= n; i++) {
int temp;
cin >> temp;
update(i, temp);
}
while (q--)
{
int a, b, c;
cin >> a >> b >> c;
if (a == 1) {
update(b, c);
}
else if (a == 2) {
cout << getSum(c) - getSum(b - 1) << endl;
}
}
}
R7-1 哈夫曼编码
给定一段文字，如果我们统计出字母出现的频率，是可以根据哈夫曼算法给出一套编码，使得用此编码压缩原文可以得到最短的编码总长。然而哈夫曼编码并不是唯一的。例如对字符串"aaaxuaxz"，容易得到字母 ‘a’、‘x’、‘u’、‘z’ 的出现频率对应为 4、2、1、1。我们可以设计编码 {‘a’=0, ‘x’=10, ‘u’=110, ‘z’=111}，也可以用另一套 {‘a’=1, ‘x’=01, ‘u’=001, ‘z’=000}，还可以用 {‘a’=0, ‘x’=11, ‘u’=100, ‘z’=101}，三套编码都可以把原文压缩到 14 个字节。但是 {‘a’=0, ‘x’=01, ‘u’=011, ‘z’=001} 就不是哈夫曼编码，因为用这套编码压缩得到 00001011001001 后，解码的结果不唯一，“aaaxuaxz” 和 “aazuaxax” 都可以对应解码的结果。本题就请你判断任一套编码是否哈夫曼编码。
输入格式：
首先第一行给出一个正整数 N（2≤N≤63），随后第二行给出 N 个不重复的字符及其出现频率，格式如下：
c[1] f[1] c[2] f[2] ... c[N] f[N]
其中c[i]是集合{‘0’ - ‘9’, ‘a’ - ‘z’, ‘A’ - ‘Z’, ‘_’}中的字符；f[i]是c[i]的出现频率，为不超过 1000 的整数。再下一行给出一个正整数 M（≤1000），随后是 M 套待检的编码。每套编码占 N 行，格式为：
c[i] code[i]
其中c[i]是第i个字符；code[i]是不超过63个’0’和’1’的非空字符串。
输出格式：
对每套待检编码，如果是正确的哈夫曼编码，就在一行中输出"Yes"，否则输出"No"。
注意：最优编码并不一定通过哈夫曼算法得到。任何能压缩到最优长度的前缀编码都应被判为正确。
输入样例：
7
A 1 B 1 C 1 D 3 E 3 F 6 G 6
4
A 00000
B 00001
C 0001
D 001
E 01
F 10
G 11
A 01010
B 01011
C 0100
D 011
E 10
F 11
G 00
A 000
B 001
C 010
D 011
E 100
F 101
G 110
A 00000
B 00001
C 0001
D 001
E 00
F 10
G 11
输出样例：
Yes
Yes
No
No
#include<iostream>
#include<queue>
#include<vector>
#include<string>
#include<map>
using namespace std;
int c[100],f[100],n,m;
string code[100];//存储序列
char ch[100];
map<char,int> mp;
bool check(int WPL){
int a,b,wpl = 0;
for(int i = 0;i<n;++i){
for(int j = i+1;j<n;++j){
a = code[i].find(code[j]);
//前缀判断，存在则返回第一个位置，否则返回最后一个位置
b = code[j].find(code[i]);
if((a==0) || (b==0)){
return false;
}
}
wpl+=mp[ch[i]]*code[i].length();//计算当前wpl
}
if(wpl==WPL) return true;
else return false;
}
int main(){
cin>>n;
priority_queue<int,vector<int>,greater<int> > pqu;//优先队列，排序
for(int i = 0;i<n;++i){
scanf(" %c %d",&c[i],&f[i]);
pqu.push(f[i]);
mp[c[i]] = f[i];//存储字母的权值
}
int WPL= 0,tmp = 0;
while(pqu.size()>1){//compute WPL
tmp = pqu.top();
pqu.pop();
tmp+=pqu.top();
pqu.pop();
WPL+=tmp;
pqu.push(tmp);
}
cin >> m;
for(int i = 0;i<m;++i){
for(int j = 0;j<n;++j){
scanf(" %c",&ch[j]);
cin >>code[j];
}
if(check(WPL))
cout <<"Yes"<<endl;
else
cout <<"No"<<endl;
}
return 0;
}
至此，树的编程题就结束了，在下一篇中我们将介绍散列表的相关知识点。
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！