急求求C++编写的字符串编辑 和 哈夫曼编码 的数据结构程序

发布网友 发布时间：2022-05-18 22:19

我来回答

共1个回答

热心网友 时间：2023-11-12 03:59

吧Huffman的给你吧，字符串的就算了，麻烦
#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<string>
using
namespace
std;
const
int
MaxV
=
100;
//最大权值
const
int
MaxBit
=
15;
//最大编码位数
const
int
MaxN
=
20;
//最大结点个数
typedef
struct
{
int
weight;
//权值
int
parent;
//双亲节点下标
int
left
,
right;
//孩子节点下标
int
flag;
//
标记
}HuffNode;
typedef
struct
{
int
bit[MaxN];
int
start;
int
weight;
}Code;
class
HuffmanTree
{
public:
HuffmanTree(HuffNode
*&,
Code
*&,
int
);
//创建huffman树
void
MakeHuffm(int
weight[]
,
int
n);
void
HuffCode(int
n);
private:
HuffNode
*HuffTree;
Code
*HuffCode1;
};
HuffmanTree::HuffmanTree(HuffNode
*&huffnode
,
Code
*&huffcode,
int
n)
{
huffnode
=
new
HuffNode[2
*
n
+
1];
huffcode
=
new
Code[n
+
1];
HuffTree
=
huffnode;
HuffCode1
=
huffcode;
}
void
HuffmanTree::MakeHuffm(int
weight[]
,
int
n)
{
int
x1
,
x2
,
m1
,m2,i
,
j;
for(i
=
0;
i
<
2
*
n
-
1;
i++)
{
if(i
<
n)
{
HuffTree[i].weight
=
weight[i];
}
else
{
HuffTree[i].weight
=
0;
HuffTree[i].flag
=
0;
HuffTree[i].parent
=
0;
HuffTree[i].left
=
-1;
HuffTree[i].right
=
-1;
}
}//for
//构造非叶子节点，共
n-1个
for(i
=
0
;
i
<
n
-
1;
i++)
{
m1
=
m2
=
MaxV;
x1
=
x2
=
0;
for(j
=
0;
j
<
n
+
i;
j++)
{
if(HuffTree[j].weight
<
m1
&&HuffTree[j].flag
==
0)
{
m2
=
m1;
x2
=
x1;
m1
=
HuffTree[j].weight;
x1
=
j;
}
else
if(HuffTree[j].weight
<
m2
&&HuffTree[j].flag
==
0)
{
m2
=
HuffTree[j].weight;
x2
=
j;
}
}//for
cout<<"x1
=
"<<x1<<"
"<<"x2
=
"<<x2<<endl;
HuffTree[x1].parent
=
n
+
i;
HuffTree[x2].parent
=
n
+
i;
HuffTree[x1].flag
=
1;
HuffTree[x2].flag
=
1;
HuffTree[n
+
i].weight
=
HuffTree[x1].weight
+
HuffTree[x2].weight;
HuffTree[n
+
i].left
=
x1;
HuffTree[n
+
i].right
=
x2;
}//for
}
void
HuffmanTree::HuffCode(int
n)
{
Code
*cd
=
new
Code;
int
child
,
parent;
for(int
i
=
0
;
i
<
n;
i
++)
{
cd->start
=
n
-
1;
//从后往前
cd->weight
=
HuffTree[i].weight;
child
=
i;
parent
=
HuffTree[child].parent;
while(parent
!=
0)
{
if(HuffTree[parent].left
==
child)
{
cd->bit[cd->start]
=
0;
}
else
{
cd->bit[cd->start]
=
1;
}
cd->start--;
child
=
parent;
parent
=
HuffTree[child].parent;
}
for(int
j
=
cd->start
+
1;
j
<
n;
j++)
{
HuffCode1[i].bit[j]
=
cd->bit[j];
}
HuffCode1[i].start
=
cd->start;
HuffCode1[i].weight
=
cd->weight;
}//for
}
int
main()
{
cout<<"运行结果为："<<endl;
int
i
,
j
,
n
=
4;
int
weight[]
=
{1
,3
,5
,7};
HuffNode
*myHuffTree;
Code*
myHuffCode;
HuffmanTree
t(myHuffTree
,
myHuffCode
,
n);
if(n
>
MaxN)
{
cout<<"n越界"<<endl;
exit(1);
}
t.MakeHuffm(weight
,
n);
t.HuffCode(n);
for(i
=
0;
i
<
n;
i++)
{
cout<<"weight
=
"<<myHuffCode[i].weight<<"
Code
=
";
for(j
=
myHuffCode[i].start
+
1;
j
<
n;
j++)
{
cout<<myHuffCode[i].bit[j];
}
cout<<endl;
}
cin.get();
return
0;
}