数据结构huffman编码作业报告_数据结构作业及答案
数据结构huffman编码作业报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构作业及答案”。
哈夫曼编码与解码
一、设计思想
在设计本程序时，主要用到的算法有如下三个：
一、创建哈夫曼树算法；
二、求哈夫曼编码算法；
三、求哈夫曼解码算法。 创建哈夫曼树算法如下：
1)存储结构：构造由信息元素与对应的权值组成的信息元素结构体来存储已给定的字母与其权重信息；构造由信息元素、权值、当前结点的父结点、左结点、右结点组成的哈夫曼树结点结构体来存储树结点的信息，还会很方便地帮助创建哈夫曼树；构造由信息元素与对应的哈夫曼编码结构体来存储哈夫曼编码信息；方便进行对数据的编码。2)结构体数组处理：哈夫曼树没有度为 1 的结点，若一个哈夫曼树由 n 个叶子结点，则该哈夫曼树共有2n-1个结点。应用以上的原理，根据用户输入的信息元素的个数n开辟大小为2n-1的哈夫曼树数组来满足创建哈夫曼树的需要，并对此数组进行初始化，叶子结点的信息元素与权值即给定的的信息元素与权值；非叶子结点的信息元素与权值设置为空值；所有哈夫曼树结点的父结点、左结点、右结点设置为 0。
3)选择权值最小与次小：在进行比较的过程中循环取出权值进行比较，设置两个s1，s2分别记录本次循环最小与次小的权值，进行下一次的比较选择。返回权值最小与次小的哈夫曼树结点信息。
4)生成小树：应用3)中想法，在用户输入的信息元素中选择权值中最小与次小的元素分别赋值给右叶子结点与左叶子结点，并把这两个权值之和赋值给这两个结点的父结点，记录父结点位置。
5)生成哈夫曼树：再应用3)4)把这些小树的父结点的权值进行比较选择，选择权值比较大的设置为新的右结点的权值，权值比较小的设置为左结点，把这两个权值的和赋值给新的父结点；以此重复进行，最终生成哈夫曼树。 求哈夫曼编码算法如下
1)采用无栈非递归遍历哈夫曼树：每次站在根结点遍历哈夫曼树，直至到达某一个叶子结点为止，并临时用一个数组记录遍历过程中每个结点的状态。编码完成后再复制给哈夫曼编码结构体中的编码数组。
2)遍历与编码：在逻辑上，遍历时向左子时，编码为0，向右子为1，将每次的结点状态记录连接即哈夫曼编码；站在根结点上，若到左子上记录此时的结点状态为0，并把指针指向左子，进行下一次的遍历，若到右结点上记录此时的结点状态1，并把指针指向右子，进行下一次的判断遍历；重复进行，到达某一个叶子结点为止，完毕后，将每次
哈夫曼编码与解码
下面是哈夫曼编码过程的大致过程（如图2）：
图2 为huffman树的各节点进行编码
下面是对指定文件内信息编码的大致过程（如图3）：
图3 信息的编码
哈夫曼编码与解码
{
int j,k;/*找出第一个单节点树*/
for(k=1;k
{
if(ht[k].parent!=0)
{ } continue;
s1=k;
break;
} /*找出其中权重最小的树*/
for(j=1;j
{
if(ht[j].parent!=0)
{ } { }
continue;
if(ht[j].weight
s1=j;
} /*找出第二个单节点树*/
for(k=1;k
{
if(ht[k].parent!=0||k==s1){ }
continue;
s2=k;
break;
} /*找出其中权重次小的树*/
for(j=1;j
{
if(ht[j].parent!=0)
{ } {
continue;
if(ht[j].weight
s2=j;
哈夫曼编码与解码
cd[--Istart]='0';
} { }
else/*右1*/
cd[--Istart]='1';
hc[i]=(char *)malloc((n-Istart)*sizeof(char));
strcpy(hc[i], &cd[Istart]);/*将临时储存的code拷贝至hc中*/ }
}
free(cd);/*释放cd*/ }
void main(){
char text[300];/*声明储存源码或Huffman码的临时数组*/
int i,j,count,choice;/*储存字母数组*/ /*储存字母对应权重的数组*/
char zi[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
int w[26]={64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1};
huffmantree ht;
huffmancode hc;
HuffmanTree(ht,w,zi,26);/*生成huffman树*/
huffmancoding(ht,hc,26);/*根据huffman树生成huffman码*/
FILE *fp;
printf(“[1]Encoding...n”);printf(“[2]Decoding...n”);scanf(“%d”,&choice);if(choice==1)/*1为编码*/ {
char file[20];printf(“Please choice the file:”);/*输入需要编码的文件名*/ scanf(“%s”,file);printf(“******************从%s文件读取字符串******************n”,file);if((fp=fopen(file,“r”))==NULL){ } fgets(text,300,fp);/*从文件中读取字符串*/ fclose(fp);printf(“Source code is:”);/*输出读取的字符串*/ puts(text);printf(“cannot open this filen”);
printf(“Please choice function:”);/*选择编码还是译码*/
哈夫曼编码与解码
}
}
} printf(“n”);} /*显示由部分电码译码得到的字符，并准备对后面的电码进行译码*/ printf(“%c”,ht[count].letter);count=51;
四、运行结果
下图是对SourceCode.txt文件信息进行编码，所得到的效果图（如图5所示）：
图5 对SourceCode.txt文件进行编码
下图是对CodeFile.txt文件中Huffman码进行译码，所得到的效果图（如图6所示）：
图6 对CodeFile.txt文件中Huffman码进行译码
