哈夫曼编码译码系统实验报告数据结构课程设计样本.doc

安徽大学哈夫曼编码译码系统实验报告数据结构课程设计哈夫曼编码译码系统实验报告数据结构课程设计姓名：鉏飞祥学号：E21414018专业：软件工程完成日期2016/7/4计算机科学与技术学院1 .需求分析1.1问题描述 问题描述：运用哈夫曼编码进行通信可以大大提高信道运用率，缩短信息传播时间，减少传播成本。但是，这规定在发送端通过一种编码系统对待传数据预先编码，在接受端将传来数据进行译码（解码）。对于双工信道（即可以双向传播信息信道），每端都需要一种完整编/译码系统。试为这样信息收发站设计一种哈夫曼编译码系统。1.2基本规定 (1)输入形式和输入值范畴； (2)输出形式； (3)程序所能达到功能。1.基本规定（1）初始化（Initialzation）。从数据文献DataFile.data中读入字符及每个字符权值，建立哈夫曼树HuffTree；（2）编码（EnCoding）。用已建好哈夫曼树，对文献ToBeTran.data中文本进行编码形成报文，将报文写在文献Code.txt中；（3）译码（Decoding）。运用已建好哈夫曼树，对文献CodeFile.data中代码进行解码形成原文，成果存入文献Textfile.txt中；（4）输出（Output）。输出DataFile.data中浮现字符以及各字符浮现频度（或概率）；输出ToBeTran.data及其报文Code.txt；输出CodeFile.data及其原文Textfile.txt；2. 概要设计阐明本程序中用到所有抽象数据类型定义。主程序流程以及各程序模块之间层次(调用)关系。(1) 数据构造哈夫曼树节点struct huff int weight; int parent; int l; int r;哈夫曼编码存储struct huff *hufftree;(2) 程序模块选取1到i-1中parent为0且权值最小两个下标void Select(struct huff *HT，int n，int &s1，int &s2)构建哈夫曼树：void huffmancoding(struct huff *ht,int *w,int n)对原文进行编码：void code(char *c)依照报文找到原文：void decoding(char *zifu)3. 详细设计 核心技术分析：1：构建哈夫曼树及生成哈夫曼编码：依照每个字符权值不同，依照最优二叉树构建办法，递归生成哈夫曼树，并且用数组存储哈夫曼树。再从每一叶子节点向树根遍历，求得编码例如：如图所示四个节点v1，v2，v3，v4，她们权值分别为7，11,4,5V2V1 7 11 4 5V3V4 第一步：选取两个权值最小节点作为左右子孩子，建立一种二叉树，双亲权值为两个自孩子之和，如图 7 11 9VV2V1V3V4重复第一步： 11 16V2V1V3V427重复第一步： 16V2V1V3V4则此时建立是优有二叉树，商定定左子树边编码为1，右子树编码为0，则可以对次二叉树进行编码，如图： 10V210V110V3V4则各顶点编码为：V1 01V2 1V3 001V4 0002：将原文编码：逐个从文献读入字符，依照已经建立好哈夫曼树，找到每一字符相应编码3：将报文译码：环节一：先读入一种字符，存入匹配字符串环节二：依照匹配串找所有哈夫曼编码，如果找到相应编码，则输入该编码所相应字符，如果找不到，则读入两个字符存入匹配串，重复环节二，找到为止。环节三：把剩余字符重复环节一二4. 测试与分析 调试过程，不也许错分派空间语句却莫名让整个程序崩溃，关于编译原理和内存分派各种问题太欠缺。学了计算机构成原理与体系构造也不懂得例如在自定义函数中：Char *c;C=(char *)malloc(4*sizoef(char *);C2=(char *)malloc(4*sizeof(char);这样居然会让程序这执行到这一句时崩溃，本来不也许有错误。而这句如果写在主函数中，就不会有问题。分派空间不大，不也许是内存不够用。解决办法是分开，把C=(char *)malloc(4*sizoef(char *);放在主函数中，此外一句不变依然在自定义函数中。malloc和free尽量配对使用，注意：malloc后普通要对返回值进行判断，避免发生不必要错误。注意，最佳再p 被free掉后，加上p=NULL这句“野指针”不是NULL指针，是指向“垃圾”内存（不可用内存）指针。人们普通不会错用NULL指针，由于用if语句很容易判断。但是“野指针”是很危险，if无法判断一种指针是正常指针还是“野指针”。有个良好编程习惯是避免“野指针”唯一办法。指针p被free或者delete之后，没有置为NULL，让人误觉得p是个合法指针。别看free和delete名字（特别是delete），它们只是把指针所指内存给释放掉，但并没有把指针自身干掉。此时指针指向就是“垃圾”内存。释放后指针应及时将指针置为NULL，防止产生“野指针”malloc函数动态申请内存空间是在堆里(而普通局部变量存于栈里)，并且该段内存不会被初始化，与全局变量不同样，如果不采用手动free()加以释放，则该段内存始终存在，直到程序退出才被系统，所觉得了合理使用内存，在不合用该段内存时，应当调用free()。此外，如果在一种函数里面使用过malloc，最佳要配对使用free，否则容易导致内存泄露（没有将内存还给自由存储区）。但是，往往会在free时候发生段错误.对的做法是这样：/在分派之前加一句判断指针与否为空，防止产生内存泄露程序运营成果：完美解决所提出问题。5. 附录 #include#include#includestruct huff int weight; int parent; int l; int r;int mm;/*记录哈夫曼字码个数*/struct huff *hufftree;char *huffmancode;void Select(struct huff *HT，int n，int &s1，int &s2)/选取函数，选出parent为零，且权值最小两个节点int min1=100;int min2=100;int i;for(i=1;iHTi.weight)&(HTi.parent=0) min1=HTi.weight; for(i=1;i=n;i+) if(min1=HTi.weight)&(HTi.parent=0) s1=i; break; for(i=1;iHTi.weight)&(HTi.parent=0)&(i!=s1) min2=HTi.weight; for(i=1;i=n;i+) if(min2=HTi.weight)&(HTi.parent=0)&(i!=s1) s2=i; break; int pipei(char *c)/*在huffmancode寻找匹配编码*/ int i; for(i=1;imm;i+) if(strcmp(c,huffmancodei)=0) return i; break; return 0;void decoding(char *zifu)/*对哈夫曼编码进行译码*/ FILE *fp,*fp1; int i,j,p,ii; int n; char c11; for(i=0;i10;i+) ci=0; printf(codefile.txt报文为：n); if(fp=fopen(codefile.txt,r)=NULL) printf(errorn); char a100; for(i=1;i+) fscanf(fp,%c,&ai); if(ai=#) break; printf(%c,ai); printf(n); fclose(fp); if(fp1=fopen(testfile.txt,w)=NULL) printf(errorn); i=1; j=1; int m=1; printf(相应原文为n); while(true) if(am=#) break; for(j=0;ji;j+) cj=am+j; n=pipei(c); if(n!=0) fprintf(fp1,%c,zifun); printf(%c,zifun); m=m+i; i=1; else i+; for(ii=0;ii10;ii+) cii=0; printf(n); fclose(fp1);int main() system(color e0)；/可以写成 red 调出颜色组 system(title huffman系统)；/设立cmd窗口标题 system(date /T); system(TIME /T); void huffmancoding(struct huff *ht,int *w,int n); void code(char *c); int i; FILE *fp,*fp1,*fp2; if(fp=fopen(DataFile.txt,r)=NULL) printf(errorn); int w28; char c28; printf(从文献DataFile.txt读入字符和权值分别为：n); for(i=1;i+) fscanf(fp,%c,&ci); if(ci=#) break; fscanf(fp,%d,&wi); printf(%c：,ci); printf(%dn,wi); fclose(fp); int m=i-1; mm=i; huffmancode=(char *)malloc(i*sizeof(char *); huffmancoding(hufftree,w,m); printf(各字符编码为n); for(i=1;i=m;i+) printf(%c：,ci); printf(%sn,huffmancodei); code(c); decoding(c); return 0;void code(char *c)/*依照原文进行编码*/ FILE *fp,*fp1; int i,j; char a100; printf(tobetran.txt原文为：n); if(fp=fopen(tobetran.txt,r)=NULL) printf(errorn); for(i=1;i+) fscanf(fp,%c,&ai); if(ai=#) printf(n); break; printf(%c ,ai); fclose(fp); if(fp1=fopen(code.txt,w)=NULL) printf(errorn); printf(相应报文为：n); for(i=1;i+) if(ai=#) break; for(j=1;j=26;j+) if(ai=cj) fprintf(fp1,%s,huffmancodej); printf(%s,huffmancodej); break; printf(n); fclose(fp1);void huffmancoding(struct huff *ht,int *w,int n)/*构建哈夫曼树和哈夫曼编码*/ if(n=1) return; int m,i; m=2*n-1; ht=(struct huff *)malloc(m+1)*sizeof(struct huff); struct huff *p; for(p=ht,i=0;iweight=*w; p-parent=0; p-l=0; p-r=0; for(;il=0; p-weight=0; p-parent=0; p-r=0; for(i=1;i=4;i+) for(i=n+1;i=m;i+) int s1,s2; Select(ht,i-1,s1,s2); hts1.parent=i; hts2.parent=i; hti.l=s1; hti.r=s2; hti.weight=hts1.weight+hts2.weight; char *cd; cd=(char *)malloc(n*sizeof(char); cdn-1=0; int start,c,f; for(i=1;i=n;+i) start=n-1; for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent) if(htf.l=c) cd-start=0; else cd-start=1; huffmancodei=(char *)malloc(n-start)*sizeof(char); strcpy(huffmancodei,&cdstart); free(cd);6. 顾客使用手册 运营程序即可。如果变化，可以变化文献datafile.txt，codefile.txt中值