PTA數據結構題目集 第五週——堆&哈夫曼樹&並查集
2020-08-08 19:59:36
題目集總目錄
學習指路部落格 堆與哈夫曼樹與並查集
05-樹7 堆中的路徑 (25分)
將在「小白專場」中介紹C語言的實現方法，是建立最小堆的基本操作訓練，一定要做
題目大意
給出最小堆的插入序列，和下標序列，每個下標i輸出Data[i]到根結點路徑上的值。
程式碼
#include <iostream>
using namespace std;
const int mindata = -10005;
const int maxsize = 10000;
typedef struct HeapStruct *MinHeap;
struct HeapStruct {
int *Data;
int Size;
};
MinHeap Create(int maxsize) {
MinHeap H = new HeapStruct;
H->Data = new int[maxsize];
H->Size = 0;
H->Data[0] = mindata;
return H;
}
void Insert(int data, MinHeap H) {
int i;
i = ++H->Size;
for(; H->Data[i>>1] > data; i >>= 1) {
H->Data[i] = H->Data[i>>1];
}
H->Data[i] = data;
}
void PrintPath(int index, MinHeap H) {
bool flag = false;
while(index != 0) {
if(flag) cout << " " << H->Data[index];
else cout << H->Data[index];
flag = true;
index >>= 1;
}
cout << endl;
}
int main() {
MinHeap H = Create(maxsize);
int N, M, x;
cin >> N >> M;
for(int i = 0; i < N; ++i) {
cin >> x;
Insert(x, H);
}
for(int i = 0; i < M; ++i) {
cin >> x;
PrintPath(x, H);
}
return 0;
}
測試點
測試點如下
05-樹8 File Transfer (25分)
關於並查集，2005、2007年浙江大學計算機學院免試研究生上機考試題即由此題改編而來。「小白專場」中介紹了原始並查集演算法的優化，聽完課以後自己嘗試一下
題目大意
每個樣例中，C爲查詢任意兩個計算機是否聯通，I爲連通這兩個計算機，最後S結束後檢查是否全部連通，如沒有全部不連通則輸出有多少個連通的。
思路
並查集+路徑壓縮
程式碼
#include <iostream>
using namespace std;
const int maxn = 10005;
int fa[maxn];
int N, x, y;
char ch;
inline void init() {
for(int i = 1; i <= N; ++i)
fa[i] = i;
}
int find(int x) {//查詢+路徑壓縮 把沿途的每個節點的父節點都設爲根節點
return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
void Merge(int x, int y) {
fa[find(x)] = find(y);
}
int main() {
scanf("%d", &N);
init();
getchar();
scanf("%c", &ch);
while(ch != 'S') {
scanf("%d %d", &x, &y);
getchar();
if(ch == 'C') {
if(find(x) == find(y)) cout << "yes" << endl;
else cout << "no" << endl;
} else if(ch == 'I') Merge(x, y);
scanf("%c", &ch);
}
int ans = 0;
for(int i = 1; i <= N; ++i) {
if(fa[i] == i) ans++;
}
if(ans == 1) cout << "The network is connected." << endl;
else cout << "There are " << ans << " components." << endl;
return 0;
}
測試點
測試點如下
05-樹9 Huffman Codes (30分)
考察對Huffman編碼的理解，程式可能略繁，量力而爲。
題目大意： 給出若幹字元及其頻率，判斷學生給的編碼方式是否爲最優編碼
思路
看了陳越姥姥的講解才知道，先根據給定的字元及其頻率構建哈夫曼樹，得到最優解的WPL(編碼長度)，再判斷學生給的編碼，在長度一致的情況下，判斷是否爲字首碼。這裏我用優先佇列代替小頂堆的一大串程式碼，求wpl時用的是另一種方法。
程式碼
#include <iostream>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
#define div 1000000007
const int maxn = 70;
const int inf = 0x3f3f3f;
int N,M,codelen;
struct Code {
char ch;
string s;
int f;//頻率
}a[maxn];
typedef struct TreeNode* CodeTree;
struct TreeNode {
int Weight;
CodeTree Left, Right;
};
CodeTree head;
priority_queue<int,vector<int>, greater<int> > q; //優先佇列代替小頂堆
int WPL() {
int wpl = 0;
while(q.size() > 1) {
int t1 = q.top();
q.pop();
int t2 = q.top();
q.pop();
wpl += (t1+t2);
q.push(t1+t2);
}
return wpl;
}
bool check() {//檢查是否是字首碼
head = new TreeNode;
head->Left = head->Right = NULL;
head->Weight = -1;
CodeTree p = head;
for (int i = 0; i < N; ++i) {
string code = a[i].s;
int len = code.length();
for (int i = 0; i < len; ++i) {
if (code[i] == '1') {
if (!p->Right) {
p->Right = new TreeNode;
p->Right->Left = p->Right->Right = NULL;
p->Right->Weight = -1;
}
p = p->Right;
//中途有別的結點 有字首碼
}
else {
if (!p->Left){
p->Left = new TreeNode;
p->Left->Right = p->Left->Left = NULL;
p->Left->Weight = -1;
}
p = p->Left;
}
if (p->Weight != -1) return false;
}
p->Weight = 1;
if (p->Left || p->Right) return false;
p = head;
}
return true;
}
int main(){
ios::sync_with_stdio(false);
cin >> N;
for(int i = 0; i < N; ++i) {
cin >> a[i].ch >> a[i].f;
q.push(a[i].f);
}
int codelen = WPL();
cin >> M;
while(M--) {
int len = 0;
for(int i = 0; i < N; ++i){
cin >> a[i].ch >> a[i].s;
len += a[i].f * a[i].s.length();
}
if(len == codelen && check()) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
測試點
測試點如下
