数据结构课程设计哈夫曼.docx
《数据结构课程设计哈夫曼.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计哈夫曼.docx（12页珍藏版）》请在冰点文库上搜索。
数据结构课程设计哈夫曼
#include
#include
#include
#defineMAX99
charcha[MAX];
charhc[MAX-1][MAX];
ints1,s2;//设置全局变量，以便在方法（函数）select中返回两个变量
typedefstruct//huffman树存储结构
{
unsignedintweight;//权值
intlchild,rchild,parent;
}huftree;
voidselect（huftreetree[],intk）//找寻parent为0,权最小的两个节点
{
inti;
for（i=1;i<=k&&tree[i].parent!
=0;i++）;s1=i;//初始化s1
for（i=1;i<=k;i++）
if（tree[i].parent==0&&tree[i].weightfor（i=1;i<=k;i++）
if（tree[i].parent==0&&i!
=s1）break;s2=i;//初始化s2
for（i=1;i<=k;i++）
if（tree[i].parent==0&&i!
=s1&&tree[i].weight}
voidhuffman（huftreetree[],int*w,intn）//生成huffman树
{intm,i;
if（n<=1）return;
m=2*n-1;
for（i=1;i<=n;i++）//给tree中每个结点权值赋值，且分别给左右孩子及双亲初始化
{tree[i].weight=w[i];tree[i].parent=0;
tree[i].lchild=0;tree[i].rchild=0;}
for（i=n+1;i<=m;i++）//给除了叶子结点下的其它结点初始化
{tree[i].weight=0;tree[i].parent=0;
tree[i].lchild=0;tree[i].rchild=0;}
for（i=n+1;i<=m;i++）//最终结果
{select（tree,i-1）;
tree[s1].parent=i;
tree[s2].parent=i;
tree[i].lchild=s1;
tree[i].rchild=s2;
tree[i].weight=tree[s1].weight+tree[s2].weight;
}
}
voidhuffmancode（huftreetree[],charcode[],intn）//输出huffman编码
{
intstart,c,i,f;
cout<<"哈夫曼树：
"<for（i=1;i<=2*n-1;i++）
cout<<<<<<code[n-1]='\0';//
cout<<"哈夫曼编码:
"<for（i=1;i<=n;i++）
{start=n-1;
for（c=i,f=tree[i].parent;f!
=0;c=f,f=tree[f].parent）//输出huffman编码
{if（tree[f].lchild==c）
code[--start]='0';//把编码存入code
elsecode[--start]='1';}
strcpy（hc[i],&code[start]）;//把code分别复制给hc
cout<"<}
}
voidtohuffmancode（intn）//编码部分
{
inti=0,j;
charanychar[9999];
cout<<"请输入你要编码的字符串:
"<>>";
cin>>anychar;
cout<<"编码为:
";
for（;anychar[i]!
='\0';i++）
{
j=0;
for（;anychar[i]!
=cha[j]&&j<=n;）j++;
if（j<=n）cout<}
cout<}
voiddecode（charch[],huftreetree[],intn）//译码
{
inti,j,m;charb;
m=2*n-1;
i=m;
cout<<"请输入编码:
"<>>";
cin>>b;
cout<<"译码为:
";
while（b!
='\n'）//遇到回车时，结束
{
if（b=='0'）i=tree[i].lchild;
elsei=tree[i].rchild;
if（tree[i].lchild==0）
{cout<j=i,i=m;
}
cin.get（b）;
}
if（tree[j].lchild!
=0）
cout<cout<}
voidmain（）
{
inti=0,n=0;
int*w,weight[MAX];
charcode[MAX];
huftreetree[MAX];
w=weight;
charin;
while（in!
='5'）
{
cout<<"******哈夫曼编码********"<cout<<"*1建立初始化哈夫曼树*"<cout<<"*2输出哈夫曼编码*"<cout<<"*3编码*"<cout<<"*4译码*"<cout<<"*5退出*"<cout<<"********************"<cout<<"请输入（1--5）:
";cin>>in;
cout<switch（in）
{
case'1':
cout<<"请输入待编码字符个数:
";
cin>>n;
cout<<"请输入字符及对应权值:
"<for（i=1;i<=n;i++）
{
cout<<">>>";
cin>>cha[i]>>weight[i];
}
huffman（tree,w,n）;break;//生成huffman树
case'2':
huffmancode（tree,code,n）;break;
case'3':
tohuffmancode（n）;break;
case'4':
decode（cha,tree,n）;break;
}
}
}
一、设计题目与要求
【问题描述】
设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。
【内容】
1）初始化：
键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；
2）编码：
利用建好的哈夫曼树生成哈夫曼编码；
3）输出编码；
4）译码功能
5）显示哈夫曼树；
6）
二、概要设计
这个设计主要是解决如何将字符进行哈夫曼编和译码的功能,主要分为头节点、select程序、创建哈夫曼树、输出哈夫曼树、输出哈夫曼编码和译码功能。
创建Huffman树原理：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。
n个权值分别设为w1、w2、…，然后将其认为有n棵树的森林，在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树且新树的根结点权值为其左、右子树根结点权值之和，从森林中删除选取的两棵树，并将新树加入森林，一直重复这个过程，最后合成唯一的一个树即为Huffman树；首先要对数进行定义。
然后进行初始化，将每个节点的所有指针都标记为-1，m个叶结点的哈夫曼树共有2m-1个结点，然后构造哈夫曼树的m-1个非叶结点，然后查找文件中权值最小的两个结点相结合，用for循环实现最小权值结合，最后构成哈夫曼树。
1.select程序是为了寻找最小权值的字符，不断地循环找寻最小权值。
2.创建哈夫曼树是将最小的权值依次相结合成成一个大的二叉树
3.输出哈夫曼树是将二叉树用矩阵的方式表达出来
4.输出哈夫曼编码是将输入的字符用01串的形式表达出来
5.译码功能是将01串的哈夫曼编码在二叉树中的字符输出
三、算法设计
1、生成huffman树（流程图如下1.1）
图1.1
这是生成哈夫曼树的流程图，节点一共有2n-1个，首先给n个叶子赋值，初始化其余的n-1个节点，然后寻找双亲，再给双亲赋值。
在给n个叶子赋值时要先挑选出两棵根节点最小的树最为左右子树构造。
新的树的权值是这两个树的权值之和。
在生成哈夫曼树之前还有一个寻找最小权值的select函数，这个函数是生成哈夫曼树的一个重要的函数，流程图如下图
2.哈夫曼编码的输出（如图）
哈夫曼编码的输出是将n-1的节点赋给start，然后经i赋给c，i的双亲则赋值给f，在进行循环的时候，f与c的关系则是f一直都是c的双亲，当f==0的时候则此时的c就是二叉树的根节点，如果左孩子等于c则记为0，如果有孩子是C则记为1，然后根据左零右一的定则依次读取，因为程序的读取是从树的最下端的叶子依次往上读取,所以要反转存储的顺序，将先前的01串从后往前进行读取储存
3.译码
译码是根据哈夫曼编码来读取字符，相对于哈夫曼编码的输出是一个反向的过程，首先输入01字符串，然后根据字符串的01的顺序来读取哈夫曼树中的字符。
首先输入编码，当编码不为空的时候，如果输入的编码是零则是左孩子，1则是右孩子，如此类推，最后寻找到字符的所在地位置，然后输出字符。
如果排定左孩子不等于零，则说明输入的编码错误。
。
四、运行结果和调试分析
1.建立和初始化哈夫曼树
在初始化的过程是在寻找最小权值的时候进行的，然后把最小的两个权值分别赋给s1和s2，在这段程序中的对字符与权值的输入上遇到了一些麻烦，运用了c++中输入与输出。
2.输出哈弗曼编码
在输出哈夫曼编树的时候因为存在C++的内容在看哈夫曼树的时候没有看懂矩阵所表达的意思，在老师的帮助和分析下才理解了，这个输出矩阵的每一列所表达的含义
3.输出哈夫曼编码
4．译码
在译码的环节也出现了问题，并且没有解决，就是当输入编码的时候，例如c的编码为011，但是当输入的编码是0111时的时候也会输出的字符的C,这个问题一直没有得到解决。
升级会员 