数据结构课程设计报告 哈弗曼编码

数据结构课程设计院系：班级：组别：指导教师：摘要随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。

算法与数据结构的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。

算法与数据结构旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。

数据结构是在整个计算机科学与技术领域上广泛被使用的术语。

它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。

数据结构有逻辑上的数据结构和物理上的数据结构之分。

逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。

数据结构是数据存在的形式。

《数据结构》主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。

数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。

学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。

通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。

目录一.设计目的数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。

因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。

通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。

数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。

在当今信息时代，信息技术己成为当代知识经济的核心技术。

我们时刻都在和数据打交道。

比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。

实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。

数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。

数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。

学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。

通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。

通过此次课程设计主要达到以下目的：一、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；二、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；三、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；四、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

二.需求分析摘要 (2)目录 (3)一.设计目的 (3)二.需求分析 (4)2.1哈夫曼编码/译码器简介 (5)2.2需求分析 (5)2.2.1程序的基本功能 (5)2.2.2输入/输出形式 (6)2.2.3测试数据要求 (6)2.3基本要求 (6)a.编/译码系统应具有以下功能： (6)b.测试数据 (7)三.概要设计 (7)3.1问题分析哈夫曼树的定义 (7)3.2系统结构图（功能模块图） (8)四.详细设计 (9)4.1 编码与译码 (9)4.2 源代码 (12)4.3运行结果 (17)五.调试分析 (18)在我自己课程设计中，就在编写好源代码后的调试中出现了不少的错误，遇到了很多麻烦及困难，我的调试及其中的错误和我最终找出错误，修改为正确的能够执行的程序中，通过分析，我学到了： (18)六.小结 (20)2.1哈夫曼编码/译码器简介举例说明，先前快速远距离通信的主要手段是电报，即将需传送的文字转换成由二进制的字符组成的字符串。

在传送电文时，希望总长尽可能地短，如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，以减少经费。

哈夫曼树就是根据此原理设计出来的一种存储结构。

本次要做的哈夫曼编码/译码器的主要功能是：运用二叉树来设计二进制的前缀编码。

若给一个文件，先统计文件中每个字符出现的频数，即作为此字符的权值，然后将里面的字符编码成相应的哈夫曼编码；反之，根据哈夫曼译码原理把所给二进制数编译成对应的字符串。

2.2需求分析2.2.1程序的基本功能本程序可以对任何大小的字符型文件进行Huffman编码，生成一个编码文件。

并可以在程序运行结束后的任意时间对它解码还原生成字符文件。

即：先对一条电文进行输入，并实现Huffman编码，然后对Huffman编码生成的代码串进行译码，最后输出电文数字2.2.2输入/输出形式当进行编码时输入为原字符文件文件名，当程序运行编码完成之后输入编码文件名（默认名为code.dll）。

当进行译码时输入为编码文件名（默认名为code.dll），从文件中读取Huffman编码树后输入字符文件的文件名。

2.2.3测试数据要求本程序中测试数据主要为字符型文件。

2.3基本要求a.编/译码系统应具有以下功能：（1）I：初始化（Initialization）。

从终端读入字符集大小n，以及n 个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。

（2）E：编码（Encoding）。

利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

（3）D：译码（Decoding）。

利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。

（4）P：印代码文件（Print）。

将文件CodeFile以紧凑格式显示在终端上，每行50个代码。

同时将此字符形式的编码文件写入文件CodePrin 中。

（5）T：印哈夫曼树（Tree printing）。

将已在内存中的哈夫曼树以直观的方式（树或凹入表形式或广义表）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

b.测试数据（1）利用下面这道题中的数据调试程序。

某系统在通信联络中只可能出现八种字符，其概率分别为0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。

（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。

字符空格 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z频度 57 63 15 1 48 51 80 23 8 18 1 16 1三.概要设计3.1问题分析哈夫曼树的定义1、哈夫曼树节点的数据类型定义为：typedef struct{HuffmanTree HT;//引用上一个数据类型char *c;//存放将要建立哈夫曼树的字符int longth;//字符的大小，即开始第一步输入的一个整数HuffmanCode HC;//存放对应的哈夫编码即对应的01代码}Huffman;2、所实现的功能函数如下（1）int min(HuffmanTree t,int i)接收原始数据：从终端读入字符集大小n，n个字符和n个权值，建立哈夫曼树，存于文件hfmtree.dat中。

供InitHuffman（）函数调用（2）void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)初始化哈夫曼树，处理InputHuffman(Huffman Hfm)函数得到的数据，按照哈夫曼规则建立2叉树。

此函数块调用了Select（）函数。

（3）void Select(HuffmanTree HT,int end,int *s1,int *s2)把输入的字符按权值从小到大排序，挑出最小权值供HuffmanCoding()调用并且根节点的权值等于他的左右孩子的权值和（4）void Decoding()编码功能函数：利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.dat中读入）对文件中的正文进行编码，然后将结果存入文件codefile.dat中。

如果正文中没有要编码的字符，则键盘读入并存储到ToBeTran文件中。

读入ToBeTran中将要编码的内容，将编码好的哈夫曼编码存储到CodeFile中。

（5）void Decoding(Huffman Hfm)译码功能函数：利用已建好的哈夫曼树将文件codefile.dat中的代码进行译码，结果存入文件textfile.dat 中。

（6）void Code_printing()打印功能函数：输出哈夫曼树，字符，权值，以及它对应的编码。

（7）主函数的简要说明，主函数主要设计的是一个分支语句，让用户挑选所实现的功能。

使用链树存储，然后分别调用统计频数函数，排序函数，建立哈夫曼函数，编码函数，译码函数来实现功能。

3.2系统结构图（功能模块图）码/译码器夫曼树树哈夫曼树四.详细设计4.1 编码与译码创建哈弗曼树开始初始化哈夫曼链表且有2n-1个节点i=1i<np->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;for(i=n+1;i<=m;++i)HT[s1].parent=HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;结束编码开始将字符存入哈夫曼编码结构体数组的字符单元中if(q==q->Parent->LChild)HC[i].code[--HC [i].start]='0' HC[i].code[--H C[i].start]='1'p=p->nextI=n 时结束译码4.2 源代码#include "stdafx.h" 开始Root指向根节点P!=rootcode[i]=='0'p=p->LChildp=p->Rchildp->LChild==NULL&&p->RChild==NULLs[k++]=str[j]p=root结束#include<iomanip.h>#include<stdio.h>#include<string.h>#define MAX 99char cha[MAX];char hc[MAX-1][MAX];int s1,s2; //设置全局变量，以便在方法(函数)select中返回两个变量typedef struct //huffman树存储结构{unsigned int weight;//权值int lchild,rchild,parent;}huftree;void select(huftree tree[],int k) //找寻parent为0,权最小的两个节点{int i;for (i=1;i<=k && tree[i].parent!=0 ;i++); s1=i;//初始化s1for (i=1;i<=k;i++)if (tree[i].parent==0 && tree[i].weight<tree[s1].weight) s1=i;//把最小值赋给s1for (i=1; i<=k ; i++)if (tree[i].parent==0 && i!=s1) break; s2=i;//初始化s2for (i=1;i<=k;i++)if ( tree[i].parent==0 && i!=s1 && tree[i].weight<tree[s2].weight) s2=i;//把最小值赋给s2}void huffman(huftree tree[],int *w,int n) //生成huffman树{ int m,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;}}void huffmancode(huftree tree[],char code[],int n)//输出huffman编码{int start,c,i,f;printf("哈夫曼树：");//输出hufftreefor(i=1;i<=2*n-1;i++)printf("5d%",i);printf("5d%",tree[i].weight);printf("5d%",tree[i].parent);printf("5d%",tree[i].lchild);printf("5d%",tree[i].rchild);printf("\n");code[n-1]='\0';//printf("哈夫曼编码:\n");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';//把编码存入codeelse code[--start]='1';}strcpy(hc[i],&code[start]);//把code分别复制给hcprintf("%s",cha[i]);printf("-->");printf("%s",hc[i]);printf("\n");//分别输出编码for是满足条件进入}}void tohuffmancode(int n)//编码部分{int i=0,j;char anychar[9999];printf("请输入你要编码的字符串:\n");printf(">>>");gets(anychar);printf("编码为:");for (;anychar[i]!='\0';i++){j=0;for(;anychar[i]!=cha[j]&&j<=n;) j++;if (j<=n)printf("%d",hc[j]);}printf("\n");}void decode(char ch[],huftree tree[],int n)//译码{int i,j,m;char b;m=2*n-1;i=m;printf("请输入编码:\n");printf(">>>");scanf("%d",b);printf("译码为:");while(b!=10) //遇到回车时，结束{if(b=='0')i=tree[i].lchild;else i=tree[i].rchild;if(tree[i].lchild==0){printf("%d",ch[i]);j=i,i=m;}cin.get(b);}if(tree[j].lchild!=0)printf("\nERROR\n");}void main(){int i=0,n=0;int *w,weight[MAX];char code[MAX];huftree tree[MAX];w=weight;char in;while (in!='5'){printf(" ---------------哈夫曼编码-------------\n");printf("1 建立初始化哈夫曼树 2 输出哈夫曼编码3 编码4 译码5 退出\n");printf("请输入(1--5):");scanf("%d",in);printf("\n");switch (in){case '1': printf("请输入待编码字符个数:");scanf("%d",&n);printf("请输入字符及对应权值:");for(i=1;i<=n;i++){printf(">>>");scanf("%s",cha[i]);scanf("%d",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;}}}4.3运行结果根据此次实验的设计需求及原理，我们编写出相应的源代码，在运行时可以得到相应的功能：如下图的界面所示：此界面中显示7种选择，可以分别执行不同的部分，由此看出，选择序号i可以进入哈夫曼树初始化界面，然后会提示输入字符个数，字符及相应的权值。