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

安徽大学数据结构课程设计报告工程名称：哈弗曼编/译码系统的设计与实现姓名：鉏飞祥学号：E21414018专业：软件工程完成日期2023/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.概要设计说明本程序中用到的所有抽象数据类型的定义。主程序的流程以及各程序模块之间的层次(调用)关系。数据结构哈夫曼树的节点structhuff{intweight;intparent;intl;intr;};哈夫曼编码的存储structhuff*hufftree;程序模块选择1到i-1中parent为0且权值最小的两个下标voidSelect(structhuff*HT,intn,int&s1,int&s2)构建哈夫曼树：voidhuffmancoding(structhuff*ht,int*w,intn)对原文进行编码：voidcode(char*c)根据报文找到原文：voiddecoding(char*zifu)3.详细设计核心技术分析：1：构建哈夫曼树及生成哈夫曼编码：根据每个字符权值不同，根据最优二叉树的构建方法，递归生成哈夫曼树，并且用数组存放哈夫曼树。再从每一叶子节点向树根遍历，求得编码例如：如下图的四个节点v1，v2，v3，v4，他们的权值分别为7，11,4,5V2VV2V1V3V3V4第一步：选择两个权值最小的节点作为左右子孩子，建立一个二叉树，双亲权值为两个自孩子之和，如图7119VV2VV2V1V3V3V4重复第一步：1116V2V2V1V1V3V3V427重复第一步：16V2V2V1V1V3V3V4那么此时建立的是优有二叉树，约定定左子树边编码为1，右子树编码为0，那么可以对次二叉树进行编码，如图：10V2V210V1V110V3V3V4那么各顶点的编码为：V101V21V3001V40002：将原文编码：逐个从文件读入字符，根据已经建立好的哈夫曼树，找到每一字符对应的编码3：将报文译码：步骤一：先读入一个字符，存入匹配字符串步骤二：根据匹配串找所有的哈夫曼编码，如果找到对应的编码，那么输入该编码所对应的字符，如果找不到，那么读入两个字符存入匹配串，重复步骤二，找到为止。步骤三：把剩下的字符重复步骤一二4.测试与分析调试过程，不可能错的分配空间的语句却莫名的让整个程序崩溃，关于编译原理和内存分配的各种问题太欠缺。学了计算机组成原理与体系结构也不知道比方在自定义函数中：Char**c;C=(char**)malloc(4*sizoef(char*));C[2]=(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<stdio.h>#include<stdlib.h>#include<string.h>structhuff{intweight;intparent;intl;intr;};intmm;/*记录哈夫曼字码的个数*/structhuff*hufftree;char**huffmancode;voidSelect(structhuff*HT,intn,int&s1,int&s2)//选择函数，选出parent为零，且权值最小的两个节点{intmin1=100;intmin2=100;inti;for(i=1;i<=n;i++)if((min1>HT[i].weight)&&(HT[i].parent==0))min1=HT[i].weight;for(i=1;i<=n;i++)if((min1==HT[i].weight)&&(HT[i].parent==0)){s1=i;break;}for(i=1;i<=n;i++)if((min2>HT[i].weight)&&(HT[i].parent==0)&&(i!=s1))min2=HT[i].weight;for(i=1;i<=n;i++)if((min2==HT[i].weight)&&(HT[i].parent==0)&&(i!=s1)){s2=i;break;}}intpipei(char*c)/*在huffmancode寻找匹配的编码*/{inti;for(i=1;i<mm;i++){if(strcmp(c,huffmancode[i])==0){returni;break;}}return0;}voiddecoding(char*zifu)/*对哈夫曼编码进行译码*/{FILE*fp,*fp1;inti,j,p,ii;intn;charc[11];for(i=0;i<10;i++)c[i]='\0';printf("codefile.txt报文为：\n");if((fp=fopen("codefile.txt","r"))==NULL){printf("error\n");}chara[100];for(i=1;;i++){fscanf(fp,"%c",&a[i]);if(a[i]=='#')break;printf("%c",a[i]);}printf("\n");fclose(fp);if((fp1=fopen("testfile.txt","w"))==NULL){printf("error\n");}i=1;j=1;intm=1;printf("对应原文为\n");while(true){if(a[m]=='#')break;for(j=0;j<i;j++){c[j]=a[m+j];}n=pipei(c);if(n!=0){fprintf(fp1,"%c",zifu[n]);printf("%c",zifu[n]);m=m+i;i=1;}elsei++;for(ii=0;ii<10;ii++)c[ii]='\0';}printf("\n");fclose(fp1);}intmain(){system("colore0");//可以写成red调出颜色组system("titlehuffman系统");//设置cmd窗口标题system("date/T");system("TIME/T");voidhuffmancoding(structhuff*ht,int*w,intn);voidcode(char*c);inti;FILE*fp,*fp1,*fp2;if((fp=fopen("DataFile.txt","r"))==NULL){printf("error\n");}intw[28];charc[28];printf("从文件DataFile.txt读入字符和权值分别为：\n");for(i=1;;i++){fscanf(fp,"%c",&c[i]);if(c[i]=='#')break;fscanf(fp,"%d",&w[i]);printf("%c:",c[i]);printf("%d\n",w[i]);}fclose(fp);intm=i-1;mm=i;huffmancode=(char**)malloc(i*sizeof(char*));huffmancoding(hufftree,w,m);printf("各字符的编码为\n");for(i=1;i<=m;i++){printf("%c:",c[i]);printf("%s\n",huffmancode[i]);}code(c);decoding(c);return0;}voidcode(char*c)/*根据原文进行编码*/{FILE*fp,*fp1;inti,j;chara[100];printf("tobetran.txt原文为：\n");if((fp=fopen("tobetran.txt","r"))==NULL){printf("error\n");}for(i=1;;i++){fscanf(fp,"%c",&a[i]);if(a[i]=='#'){printf("\n");break;}printf("%c",a[i]);}fclose(fp);if((fp1=fopen("code.txt","w"))==NULL){printf("error\n");}printf("对应报文为：\n");for(i=1;;i++){if(a[i]=='#')break;for(j=1;j<=26;j++){if(a[i]==c[j]){fprintf(fp1,"%s",huffmancode[j]);printf("%s",huffmancode[j]);break;}}}printf("\n");fclose(fp1);}voidhuffmancoding(structhuff*ht,int*w,intn)/*构建哈夫曼树和哈夫曼编码*/{if(n<=1)return;intm,i;m=2*n-1;ht=(structhuff*)malloc((m+1)*sizeof(structhuff));structhuff*p;for(p=ht,i=0;i<=n;i++,p++,w++){p->weight=*w;p->parent=0;p->l=0;p