logo资料库

数据结构哈夫曼编码实验报告.doc

发布时间：2022-06-15 发布人：admin 分类：说明书 资料大小：0.06M 资料格式：doc 举报 版权申诉
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
资料共9页，剩余部分请下载后查看
    数据结构实验报告 ―― 实验五 简单哈夫曼编/译码的设计与实现 本实验的目的是通过对简单哈夫曼编/译码系统的设计与实现来熟练掌握树型结 构在实际问题中的应用。此实验可以作为综合实验，阶段性实验时可以选择其中的几 个功能来设计和实现。 一、【问题描述】 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。 但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行 译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能： 1、接收原始数据。 从终端读入字符集大小 n，以及 n 个字符和 n 个权值，建立哈夫曼树，并将它存于文件 nodedata.dat 中。 2、编码。 利用已建好的哈夫曼树（如不在内存，则从文件 nodedata.dat 中读入），对文件中的正 文进行编码，然后将结果存入文件 code.dat 中。 3、译码。利用已建好的哈夫曼树将文件 code.dat 中的代码进行译码，结果存入文件 textfile.dat 中。 4、打印编码规则。 即字符与编码的一一对应关系。 二、【数据结构设计】 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时，设计一个结构体数组 HuffNode 保存哈夫曼树中各结点的信息，根 据二叉树的性质可知，具有 n 个叶子结点的哈夫曼树共有 2n-1 个结点，所以数组 HuffNode 的大小设置为 2n-1，描述结点的数据类型为： typedef struct { int weight;//结点权值 int parent; int lchild; int rchild; char inf; }HNodeType; 2、求哈夫曼编码时使用一维结构数组 HuffCode 作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链 域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值， 由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的 0、 1 序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位 码，所以设计如下数据类型： #define MAXBIT 10 typedef struct { int bit[MAXBIT]； int start；
    }HcodeType； 3、文件 nodedata.dat、code.dat 和 textfile.dat。 三、【功能（函数）设计】 1、初始化功能模块。 此功能模块的功能为从键盘接收字符集大小 n，以及 n 个字符和 n 个权值。 2、建立哈夫曼树的功能模块。 此模块功能为使用 1 中得到的数据按照教材中的构造哈夫曼树的算法构造哈夫曼树，即 将 HuffNode 数组中的各个位置的各个域都添上相关的值，并将这个结构体数组存于文件 hfmtree.dat 中。 3、建立哈夫曼编码的功能模块。 此模块功能为从文件 nodedata.dat 中读入相关的字符信息进行哈夫曼编码，然后将结果 存入 code.dat 中，同时将字符与 0、1 代码串的一一对应关系打印到屏幕上。 4、译码的功能模块。 此模块功能为接收需要译码的 0、1 代码串，按照 3 中建立的编码规则将其翻译成字符 集中字符所组成的字符串形式，存入文件 textfile.dat，同时将翻译的结果在屏幕上打印输出。 四、【编码实现】 #include #include #include #include #define MaxBit 10 #define Maxvalue 100//应该大于权重之和 #define Maxleaf 100 #define Maxnode Maxleaf*2-1 typedef struct { int weight; int parent; int lchild; int rchild; char inf; }HNodeType; struct HcodeType { int bit[MaxBit]; int start; }; void Creat_Haffmantree(int &n) { HNodeType *HaffNode=new HNodeType[2*n-1];
    int i,j; int m1,m2,x1,x2; for(i=0;i<2*n-1;i++) { HaffNode[i].weight=0; HaffNode[i].parent=-1; HaffNode[i].lchild=-1; HaffNode[i].rchild=-1; HaffNode[i].inf='0'; } for(i=0;i>HaffNode[i].inf; cout<<"请输入该字符的权值"<>HaffNode[i].weight; } for(i=0;i
    HaffNode[n+i].rchild=x2; HaffNode[n+i].inf=NULL; } cout<<"显示存储的哈弗曼树信息:"<
    c=i; p=HaffNode[c].parent; while(p!=-1) { if(HaffNode[p].lchild==c) cd.bit[cd.start]=0; else cd.bit[cd.start]=1; cd.start--; c=p; p=HaffNode[c].parent; } for(j=cd.start+1;j>inf; int f=strlen(inf); fstream outfile1; outfile1.open("E:\\code.dat",ios::out|ios::binary);//建立进行写入的文件 if(!outfile1) { cout<<"code.dat 文件不能打开!"<
    abort(); } else { cout<
    infile2.read((char*)&tempcode[num],sizeof(tempcode[num])); num++; int num=0; for(i=0;i<100;i++) tempcode[i]=-1; HcodeType *Code=new HcodeType[n]; fstream infile2;//读编码 infile2.open("E:\\code.dat",ios::in|ios::binary); while(!infile2.eof()) { } infile2.close(); num--; cout<<"从文件中读出的编码为"<
    cout<>ch1; while(!(ch1<=3&&ch1>=0)) //输入不在 0 到 4 之间无效 { cout<<"数据输入错误，请重新选择(0~4):"; cin>>ch1; } switch(ch1) { case { 1: cout<<"\t\t\t 请输入编码个数"<>n; Creat_Haffmantree(n); break; } case case 2: HaffCode(n); 3: decode(n); break; break;
    分享到：
    赞 收藏

    相关推荐

    资料库

    后端

    共收录2142份资料，累计10个分类，关注成员有19位，主要包括：Perl,Docker,Delphi,VB,PHP,Java,C,C#,Python,C++

    热门标签

    Perl Docker Delphi VB PHP Java C C# Python C++

    最新资料