算法笔记贪心算法哈夫曼编码问题Word下载.docx
- 文档编号:6366212
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:17
- 大小:34.67KB
算法笔记贪心算法哈夫曼编码问题Word下载.docx
《算法笔记贪心算法哈夫曼编码问题Word下载.docx》由会员分享,可在线阅读,更多相关《算法笔记贪心算法哈夫曼编码问题Word下载.docx(17页珍藏版)》请在冰点文库上搜索。
哈夫曼算法
2.#include
"
stdafx.h"
3.#include
BinaryTree.h"
4.#include
MinHeap.h"
5.#include
<
iostream>
6.using
namespace
std;
7.const
int
N
=
6;
8.template<
class
Type>
Huffman;
9.template<
10.BinaryTree<
int>
HuffmanTree(Type
f[],int
n);
11.template<
12.class
Huffman
13.{
14.
friend
BinaryTree<
HuffmanTree(Type[],int);
15.
public:
16.
operator
Type()
const
17.
{
18.
return
weight;
19.
}
20.
//private:
21.
tree;
22.
Type
23.};
24.int
main()
25.{
26.
char
c[]
{'
0'
'
a'
b'
c'
d'
e'
f'
};
27.
f[]
{0,45,13,12,16,9,5};
//下标从1开始
28.
t
HuffmanTree(f,N);
29.
cout<
各字符出现的对应频率分别为:
endl;
30.
for(int
i=1;
i<
=N;
i++)
31.
32.
c[i]<
:
f[i]<
;
33.
34.
35.
生成二叉树的前序遍历结果为:
36.
t.Pre_Order();
37.
38.
生成二叉树的中序遍历结果为:
39.
t.In_Order();
40.
41.
t.DestroyTree();
42.
0;
43.}
44.template<
45.BinaryTree<
n)
46.{
47.
//生成单节点树
48.
Huffman<
*w
new
[n+1];
49.
z,zero;
50.
=n;
51.
52.
z.MakeTree(i,zero,zero);
53.
w[i].weight
f[i];
54.
w[i].tree
z;
55.
56.
//建优先队列
57.
MinHeap<
>
Q(n);
58.
Q.Insert(w[i]);
59.
//反复合并最小频率树
60.
x,y;
61.
n;
62.
63.
x
Q.RemoveMin();
64.
y
65.
z.MakeTree(0,x.tree,y.tree);
66.
x.weight
+=
y.weight;
67.
x.tree
68.
Q.Insert(x);
69.
70.
71.
delete[]
w;
72.
x.tree;
73.}
(2)BinaryTree.h二叉树实现
1.#include<
2.using
3.template<
T>
4.struct
BTNode
5.{
6.
T
data;
7.
BTNode<
*lChild,*rChild;
8.
BTNode()
9.
10.
lChild=rChild=NULL;
11.
12.
BTNode(const
&
val,BTNode<
*Childl=NULL,BTNode<
*Childr=NULL)
13.
data=val;
lChild=Childl;
rChild=Childr;
*
CopyTree()
*nl,*nr,*nn;
if(&
data==NULL)
NULL;
23.
nl=lChild->
CopyTree();
24.
nr=rChild->
25.
nn=new
(data,nl,nr);
nn;
28.};
29.template<
30.class
BinaryTree
31.{
*root;
BinaryTree();
~BinaryTree();
void
Pre_Order();
In_Order();
Post_Order();
TreeHeight()const;
TreeNodeCount()const;
DestroyTree();
MakeTree(T
pData,BinaryTree<
leftTree,BinaryTree<
rightTree);
43.
Change(BTNode<
*r);
44.
private:
45.
Destroy(BTNode<
*&
r);
46.
PreOrder(BTNode<
InOrder(BTNode<
PostOrder(BTNode<
Height(const
*r)const;
NodeCount(const
51.};
52.template<
53.BinaryTree<
BinaryTree()
54.{
root=NULL;
56.}
57.template<
58.BinaryTree<
~BinaryTree()
59.{
60.}
61.template<
62.void
Pre_Order()
63.{
PreOrder(root);
65.}
66.template<
67.void
In_Order()
68.{
InOrder(root);
70.}
71.template<
72.void
Post_Order()
73.{
74.
PostOrder(root);
75.}
76.template<
77.int
TreeHeight()const
78.{
79.
Height(root);
80.}
81.template<
82.int
TreeNodeCount()const
83.{
84.
NodeCount(root);
85.}
86.template<
87.void
DestroyTree()
88.{
89.
Destroy(root);
90.}
91.template<
92.void
*r)
93.{
94.
if(r!
=NULL)
95.
96.
r->
data<
'
97.
PreOrder(r->
lChild);
98.
rChild);
99.
100.}
101.template<
102.void
103.{
104.
105.
106.
InOrder(r->
107.
108.
109.
110.}
111.template<
112.void
113.{
114.
115.
116.
PostOrder(r->
117.
118.
119.
120.}
121.template<
122.int
*r)const
123.{
124.
if(r==NULL)
125.
126.
else
127.
1+NodeCount(r->
lChild)+NodeCount(r->
128.}
129.template<
130.int
131.{
132.
133.
134.
135.
136.
lh,rh;
137.
lh=Height(r->
138.
rh=Height(r->
139.
1+(lh>
rh?
lh:
rh);
140.
141.}
142.template<
143.void
r)
144.{
145.
146.
147.
Destroy(r->
148.
149.
delete
r;
150.
r=NULL;
151.
152.}
153.template<
154.void
*r)//将二叉树bt所有结点的左右子树交换
155.{
156.
*p;
157.
if(r){
158.
p=r->
lChild;
159.
lChild=r->
rChild;
160.
rChild=p;
//左右子女交换
161.
Change(r->
//交换左子树上所有结点的左右子树
162.
//交换右子树上所有结点的左右子树
163.
164.}
165.template<
166.void
rightTree)
167.{
168.
root
();
169.
root->
data
pData;
170.
lChild
leftTree.root;
171.
rChild
rightTree.root;
172.}
(3)MinHeap.h最小堆实现
1.#include
4.class
MinHeap
*heap;
//元素数组,0号位置也储存元素
CurrentSize;
//目前元素个数
MaxSize;
//可容纳的最多元素个数
FilterDown(const
start,const
end);
//自上往下调整,使关键字小的节点在上
FilterUp(int
start);
//自下往上调整
MinHeap(int
n=1000);
~MinHeap();
bool
Insert(const
x);
//插入元素
RemoveMin();
//删除最小元素
GetMin();
//取最小元素
IsEmpty()
const;
IsFull()
Clear();
21.};
22.template<
23.MinHeap<
24.{
MaxSize=n;
heap=new
T[MaxSize];
CurrentSize=0;
28.}
30.MinHeap<
~MinHeap()
[]heap;
33.}
34.template<
35.void
start)
36.{
j=start,i=(j-1)/2;
//i指向j的双亲节点
temp=heap[j];
while(j>
0)
if(heap[i]<
=temp)
break;
heap[j]=heap[i];
j=i;
i=(i-1)/2;
heap[j]=temp;
51.}
53.void
end)
i=start,j=2*i+1;
temp=heap[i];
while(j<
=end)
if(
(j<
(heap[j]>
heap[j+1])
)
j++;
if(temp<
=heap[j])
heap[i]=heap[j];
i=j;
j=2*j+1;
heap[i]=temp;
71.}
72.template<
73.bool
x)
74.{
75.
if(CurrentSize==MaxSize)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 笔记 贪心 哈夫曼 编码 问题