-
Notifications
You must be signed in to change notification settings - Fork 0
/
Main.cpp
163 lines (138 loc) · 3.53 KB
/
Main.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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
/**
* C 语言: 二项堆
*
* @author skywang
* @date 2014/04/02
*/
#include <iostream>
#include "BinomialHeap.h"
using namespace std;
#define DEBUG 0
// 共7个 = 1+2+4
int a[] = {12, 7, 25, 15, 28,
33, 41};
// 共13个 = 1+4+8
int b[] = {18, 35, 20, 42, 9,
31, 23, 6, 48, 11,
24, 52, 13 };
// 验证"二项堆的插入操作"
void testInsert()
{
int i;
int alen=sizeof(a)/sizeof(a[0]);
BinomialHeap<int>* ha=new BinomialHeap<int>();
cout << "== 二项堆(ha)中依次添加: ";
for(i=0; i<alen; i++)
{
cout << a[i] <<" ";
ha->insert(a[i]);
}
cout << endl;
cout << "== 二项堆(ha)的详细信息: " << endl;
ha->print();
}
// 验证"二项堆的合并操作"
void testUnion()
{
int i;
int alen=sizeof(a)/sizeof(a[0]);
int blen=sizeof(b)/sizeof(b[0]);
BinomialHeap<int>* ha=new BinomialHeap<int>();
BinomialHeap<int>* hb=new BinomialHeap<int>();
cout << "== 二项堆(ha)中依次添加: ";
for(i=0; i<alen; i++)
{
cout << a[i] <<" ";
ha->insert(a[i]);
}
cout << endl;
cout << "== 二项堆(ha)的详细信息: " << endl;
ha->print();
cout << "== 二项堆(hb)中依次添加: ";
for(i=0; i<blen; i++)
{
cout << b[i] <<" ";
hb->insert(b[i]);
}
cout << endl;
cout << "== 二项堆(hb)的详细信息: " << endl;
hb->print();
// 将"二项堆hb"合并到"二项堆ha"中。
ha->combine(hb);
cout << "== 合并ha和hb后的详细信息: " << endl;
ha->print();
}
// 验证"二项堆的删除操作"
void testDelete()
{
int i;
int blen=sizeof(b)/sizeof(b[0]);
BinomialHeap<int>* hb=new BinomialHeap<int>();
cout << "== 二项堆(hb)中依次添加: ";
for(i=0; i<blen; i++)
{
cout << b[i] <<" ";
hb->insert(b[i]);
}
cout << endl;
cout << "== 二项堆(hb)的详细信息: " << endl;
hb->print();
// 将"二项堆hb"合并到"二项堆ha"中。
hb->remove(20);
cout << "== 删除节点20后的详细信息: " << endl;
hb->print();
}
// 验证"二项堆的更新(减少)操作"
void testDecrease()
{
int i;
int blen=sizeof(b)/sizeof(b[0]);
BinomialHeap<int>* hb=new BinomialHeap<int>();
cout << "== 二项堆(hb)中依次添加: ";
for(i=0; i<blen; i++)
{
cout << b[i] <<" ";
hb->insert(b[i]);
}
cout << endl;
cout << "== 二项堆(hb)的详细信息: " << endl;
hb->print();
// 将节点20更新为2
hb->update(20, 2);
cout << "== 更新节点20->2后的详细信息: " << endl;
hb->print();
}
// 验证"二项堆的更新(增加)操作"
void testIncrease()
{
int i;
int blen=sizeof(b)/sizeof(b[0]);
BinomialHeap<int>* hb=new BinomialHeap<int>();
cout << "== 二项堆(hb)中依次添加: ";
for(i=0; i<blen; i++)
{
cout << b[i] <<" ";
hb->insert(b[i]);
}
cout << endl;
cout << "== 二项堆(hb)的详细信息: " << endl;
hb->print();
// 将节点6更新为60
hb->update(6, 60);
cout << "== 更新节点6->60后的详细信息: " << endl;
hb->print();
}
int main()
{
// 1. 验证"二项堆的插入操作"
testInsert();
// 2. 验证"二项堆的合并操作"
//testUnion();
// 3. 验证"二项堆的删除操作"
//testDelete();
// 4. 验证"二项堆的更新(减少)操作"
//testDecrease();
// 5. 验证"二项堆的更新(增加)操作"
//testIncrease();
return 0;
}