《数据结构实训》实训报告

《《数据结构实训》实训报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

计算机工程系计算机12级卓越计Y121班数据结构实训报告1题目与要求1.1问题提出本人计划编写一个哈夫曼编码译码器，主要是进行信息通信，实现在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码(复原)的信息收发站。1.2本系统涉及的知识点最优二叉树、数组、循环、函数、分支、类型结构定义、文件、递归1.3功能要求所要实现的题目功能：1)I：初始化(Initialization)。从终端读入字符集大小n及n个字符和m个权值，建立哈夫曼树，并将它存于文件hfmtree中。(2)C：编码(Coding)。利用已建好的哈夫曼树(如不在内存，则从文件hfmtree中读入)，对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中。(3)D：解码(Decoding)。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件textfile中。(4)P：打印代码文件(Print)。将文件codefile以紧凑格式显示在终端上，每行50个代码。同时，将此字符形式的编码文件写入文件codeprint中。(5)T：打印哈夫曼树(Treeprinting)。将已在内存中的哈夫曼树以直观的方式(树或凹人表形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。2功能设计2.1算法设计本系统需要实现的功能要求：1、利用switch语句设计如图1所示的主菜单（图中的文字宋体5号）：1、初始化（Init）39 计算机工程系计算机12级卓越计Y121班数据结构实训报告2、编码（Coding）3、解码（Decoding）4、打印代码（print）5、打印哈夫曼树（Treeprint）6、退出请输入你的选择（1～6）：图1哈夫曼编码译码器主菜单2、(1)选择2后，调用编码子菜单函数，进入函数后利用switch语句实现一个如图2所示的菜单，该菜单中1、2选项调用一个函数。图2编码（coding）子菜单（2）选择2后，调用解码码子菜单函数，进入函数后利用switch语句实现一个如图3所示的菜单，该菜单中1、2选项调用一个函数.图3解码（Decoding）子菜单39 计算机工程系计算机12级卓越计Y121班数据结构实训报告3、根据所选菜单编写相应代码：1）初始化（Init）：利用循环将字符存入结构体数组，再利用循环从文本文件中取出字符统计字符的频率存入结构体数组中，再利用循环将其作为权值存入哈夫曼树的结构体数组中再循环寻找最小结点值建立哈夫曼树，然后再将其创建哈夫曼树存入文件中，最后对树进行逆向求叶子结点的编码并将其编码表存入文件和输出在终端上。具体程序为：voidInitialization(HuffmanTree&HT,HuffmanCode&HC,List*L)//初始化{Statistics(L,N);CreateHT_HC(HT,HC,L,N);printf(" Initializationsucceed!!!!! ");}///////////////////////////////统计文件中的字符(字符是从Ascll32--126)频率，将其频率作为权值建立哈夫曼树/////////voidStatistics(List*L,intn){FILE*fp;inti,j;intm;charch;for(i=0,j=32;j<=126;j++){L[i].chars=j;i++;}if((fp=fopen("test.txt","r"))==NULL)//打开test.txt文件{printf("cannotopenthefile!!!");exit(0);}while((ch=fgetc(fp))!=EOF)//从文件中逐个取出字符直到文件结尾{m=ch-32;//m等于字符的Ascll码值减去空格的Ascll码，其值就为这个字符存放数组的下标L[m].weight++;}39 计算机工程系计算机12级卓越计Y121班数据结构实训报告fclose(fp);}/////////////////////////////////////////////////求解最小权值的操作/////////////////intmin(HuffmanTreeHT,inti){intj,flag=0;unsignedintk=99999;//定义k足够大for(j=1;j<=i;j++)//循环在1-i个结点中寻找权值最小的结点if(HT[j].weightweight=L[i-1].weight;p->parent=0;p->lchild=0;p->rchild=0;}for(i=n+1;i<=m;++i,++p){p->parent=0;p->lchild=0;p->rchild=0;}////////////////////////////构造哈夫曼树///////////////////////////////////for(i=n+1;i<=m;++i){s1=min(HT,i-1);//在HT[1-i]中选择parent为0且weight最小的两个结点其序号分别为s1,s2s2=min(HT,i-1);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}SaveHT(HT,m);//保存创建好的哈夫曼树于hfmTreeHT.txt文件中////////////////////////逆向求叶子结点的编码//////////////////////////////HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//申请n+1个头指针空间，0号单元未用cd=(char*)malloc(n*sizeof(char));//申请求编码的工作区间cd[n-1]='';//编码的结束符for(i=1;i<=n;i++){start=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码if(HT[f].lchild==c;cd[--start]='0';elsecd[--start]='1';39 计算机工程系计算机12级卓越计Y121班数据结构实训报告HC[i]=(char*)malloc((n-start)*sizeof(char));//申请第i个字符编码的空间，因为每个字符的编码长度不一，所以申请n-start个strcpy(HC[i],&cd[start]);}free(cd);SaveHT_HC(HC,L,N);//保存哈夫曼编码的对照表HC于HfmTree.txt中}2）求编码（Coding）：①采用只读方式打开文件将其需编码的文件打开再利用循环对文件中的字符进行编码，最后创建一文件将其编码存入文件中。具体程序代码为：//////////////////////编码文件中的字符串//////////////////////////////////voidHfmEncodingtxt(HuffmanCode&HC,intn){inti=1;FILE*fp1;FILE*fp2;charch;if((fp1=fopen("test1.txt","r"))==NULL)//打开test1.txt文件{printf("cannotopenthefile!!!");exit(0);}if((fp2=fopen("hfmTreeHC.txt","w+"))==NULL)//打开建立一个hfmTreeHC.txt文件，用于存放test1.txt文件中字符的编码串{printf("cannotopenthefile!!!");exit(0);}while((ch=fgetc(fp1))!=EOF)//从test1.txt文件中逐个字符取出{intAscll=ch-32+1;fprintf(fp2,"%s",HC[Ascll]);i++;}printf(" 文件编码成功！编码的0、1串已存入hfmTreeHC.txt文件请自行查看。 ");fclose(fp1);fclose(fp2);39 计算机工程系计算机12级卓越计Y121班数据结构实训报告}②从终端输入字符串存放于字符数组中，再利用循环求各个字符对应在编码表里的编码。具体程序代码为：/////////////////编码从键盘输入的字符串////////////voidHfmEncodinginput(HuffmanCode&HC){inti;charchars[20];printf(" 输入少于20个字符的串：");getchar();gets(chars);printf(" 字符串的编码串为： ");for(i=0;chars[i]!='';i++){intAscll=chars[i]-32+1;printf("%s",HC[Ascll]);}printf(" 字符串编码成功！！！ ");}3）求译码（Decoding）:①采用只读方式打开其需译码的文件再利用循环和判断语句对文件中的编码符根据创建的哈夫曼树进行译码，最后创建一文件将其译码存入文件中。具体程序代码为：//实现对文件hfmTreeHC中的代码串进行译码并将其译码存入hfmDecode.txt文件//voidHfmDecodingtxt(HuffmanTree&HT,List*L,intn){inti=1,j=1;intflag=1;charch;FILE*fp1;FILE*fp2;if((fp1=fopen("hfmTreeHC.txt","r"))==NULL)//打开hfmTreeHC.txt文件{printf("cannotopenthefile!!!");exit(0);}if((fp2=fopen("hfmDecode.txt","w+"))==NULL)//打开建立一个hfmDecode.txt文件，用于存放hfmTreeHC.txt文件中编码的译码39 计算机工程系计算机12级卓越计Y121班数据结构实训报告{printf("cannotopenthefile!!!");exit(0);}inta=2*n-1,w;//定义a初始化为根节点的下标，w用于记录左或右孩子的下标while((ch=fgetc(fp1))!=EOF)//从文件hfmTreeHC.txt中逐个取出字符{if(ch=='0')w=HT[a].lchild;elsew=HT[a].rchild;if(w<=N){fprintf(fp2,"%c",L[w-1].chars);//到此处，一个译码已形成，然后再逐个将相应的译码写入文件hfmDecode.txt中a=2*n-1;//a重置为根结点}elsea=w;}printf(" 译码成功！！！！！编码的0、1串译文已存入hfmDcode.txt文件请自行查看。 ");fclose(fp1);fclose(fp2);}②从终端输入0,1字符串存放于字符数组中，再根据创建的哈夫曼树利用循环进行译码。具体程序代码为：///////////////实现对从键盘输入的代码串进行译码//////////////////////voidHfmDecodinginput(HuffmanTree&HT,List*L,intn){inti;inta=2*n-1,w;charcharhc[N];printf("请输入你要译码的0、1编码串(len<95)： ");getchar();gets(charhc);39 计算机工程系计算机12级卓越计Y121班数据结构实训报告for(i=0;charhc[i]!='';i++){if(charhc[i]=='0')w=HT[a].lchild;elsew=HT[a].rchild;if(w<=N){printf("%ct",L[w-1].chars);a=2*n-1;}elsea=w;}}4）打印代码（print）：利用只读的方式打开存放编码的文件，再利用循环读取编码用判断语句将其限制每行50个代码显示在终端上并将此形式写入另一文件中。具体程序代码为：/////打印hfmTreeHC.txt文件中的代码，并将代码的译码另存入Codefile.txt文件voidPrintHC(){intnum=0;charch1,ch2;FILE*fp1;FILE*fp2;FILE*fp3;if((fp1=fopen("hfmTreeHC.txt","r"))==NULL)//打开hfmTreeHC.txt文件{printf("cannotopenthefile!!!");exit(0);}if((fp2=fopen("Codefile.txt","w+"))==NULL)//创建打开Codefile文件{printf("cannotopenthefile!!!");exit(0);}printf(" ttCodefile.txt文件中的代码串为： ");39 计算机工程系计算机12级卓越计Y121班数据结构实训报告while((ch1=fgetc(fp1))!=EOF)//从文件hfmTreeHC.txt中逐个取出字符{printf("%c",ch1);fprintf(fp2,"%c",ch1);//将取出的符写入Codefile.txt文件中num=num+1;if(num%50==0)//每行输出50个代码{printf(" ");fprintf(fp2,"%c",' ');}}printf(" 已将hfmTreeHC.txt中的代码的译码另存入Codefile.txt文件中，请自行查看！！！ ");fclose(fp1);fclose(fp2);}5）打印哈夫曼树（Treeprint）：定义树型头指针node,移动指针node1，采用先序递归遍历凹入式打印哈夫曼树，采用追加方式创建用于存放凹入式哈夫曼树，再利用循环调节结点的位置以及关系。node1初次调用指向数组中的最后一个位子即根结点。具体程序代码为：////////////////凹入式打印哈夫曼树//////////voidPrintTree(HuffmanTreenode,HuffmanTreenode1,intlevel)//采用先序遍历,node为指向HT的头指针，node1则指向HT[i]当前的存储单元{if(node1==NULL)return;FILE*fp;fp=fopen("hfmTreeHT-chars.txt","a+");if(fp==NULL){printf("cannotopenfilehfmTreeHT-chars.txt!!! ");exit(0);}for(inti=1;i<=level;i++){printf("|");39 计算机工程系计算机12级卓越计Y121班数据结构实训报告fprintf(fp,"%c%c%c",'|','','');}printf("%d",node1->weight);printf(" ");fprintf(fp,"%d",node1->weight);//将字符型的哈夫曼树写于hfmTreeHT-chars.txt文件中fprintf(fp,"%c",' ');if(node1->lchild!=0)PrintTree(node,node+node1->lchild,level+1);if(node1->rchild!=0)PrintTree(node,node+node1->rchild,level+1);fclose(fp);}图4，哈夫曼编码译码系统图2.2部分模块流程图流程图的画法请参阅相关资料。39 计算机工程系计算机12级卓越计Y121班数据结构实训报告图5统计文件Statistic函数的流程图图6创建哈夫曼树的流程图39 计算机工程系计算机12级卓越计Y121班数据结构实训报告图7编码哈夫曼树的流程图图8文件编码（codingtxt）（左），终端输入编码（codinginput）（右）的流程图39 计算机工程系计算机12级卓越计Y121班数据结构实训报告图9文件译码（Decodingtxt）的流程图图10终端译码（Decodinginput）流程图39 计算机工程系计算机12级卓越计Y121班数据结构实训报告图11打印代码（print）流程图图12打印哈夫曼树（Treeprint）的流程图3程序代码设计初始化模块39 计算机工程系计算机12级卓越计Y121班数据结构实训报告(1)1）函数原形：voidInitialization(HuffmanTree&HT,HuffmanCode&HC,List*L)2）功能：调用文件统计Statistics(L,N)函数和创建哈夫曼树和树编码的函数CreateHT_HC(HT,HC,L,N);从而初始化哈夫曼编码表3）变量及类型：HuffmanTreeHT：结构体树型形参变量，接收main()传过来树的首地址。HuffmanCodeHC：字符型形参变量，接收main()传过来编码数组的首地址。List*L：结构体形参数组，接收main()传过来初始化数组的首地址。(2)1)函数原形：voidCreateHT_HC(HuffmanTree&HT,HuffmanCode&HC,List*L,intn)2)功能：利用从文本文件中取出字符统计字符的频率，将其作为权值循环寻找最小结点值建立哈夫曼树，然后再将其创建哈夫曼树存入文件中，最后对树进行逆向求叶子结点的编码并将其编码表存入文件和输出在终端上。3）变量及类型：HuffmanTreeHT：结构体树型形参变量，接收main()传过来树的首地址。HuffmanCodeHC：字符型形参变量，接收main()传过来编码数组的首地址。List*L：结构体形参数组，接收main()传过来数组的首地址。intn:整型形参变量，接收main()传过来HT数组的长度。inti：整型变量，放结构体数组HT,HC的下标，也用于循环变量。intm；整型变量,放结构体数组HT树的全部结点。ints1,s2：都为整型变量，存放每次寻找权值最小两个结点的存储位置即下标，其中：s1为最小，s2为次小；intstart：整型变量，作为数组cd的下标，初始化为最后的存储位置。unsignedintc：无符号整型变量，做循环变量。unsignedintf：无符号整型变量，存放结构体数组HT树的双亲结点的下标。char*cd：字符型指针变量，申请空间后用于暂时存放编码。HuffmanTreep：结构体指针变量，初始化哈夫曼树时移动指向数组HT。4）说明：char*cd，字符型指针变量，申请空间后只是用于暂时存放编码，所以当编码完之后需要释放存储空间，从而避免浪费存储空间。编码模块（1）、1）函数原形：voidHfmEncodingtxt(HuffmanCode&HC)2）功能：采用只读方式打开文件从文件中读取字符，再按照初始化模块得出的哈夫曼编码表利用循环进行文件编码，最后创建一文件将其编码存入文件中。3）变量及类型：HuffmanCodeHC：字符型形参变量，接收main()初始化后传过来编码数组的首地址。39 计算机工程系计算机12级卓越计Y121班数据结构实训报告inti:整型变量，放HC数组的下标FILE*fp1:文件指针变量，指向要编码的文件。FILE*fp2:文件指针变量，指向存编码代码串的文件。charch:字符型变量，用于存放从要编码的文件取出的字符。（2）、1）函数原形：voidHfmEncodinginput(HuffmanCode&HC)2）功能：从终端输入字符串存放于字符数组中，再利用循环求各个字符对应在编码表里的编码。3）变量及类型：HuffmanCodeHC：字符型形参变量，接收main()初始化后传递过来编码数组的首地址。inti：整型变量，用于循环变量。charchars[]：字符型数组，用于存放从终端输入的字符串。译码模块（1）、1）函数原形：voidHfmDecodingtxt(HuffmanTree&HT,List*L,intn)2）功能：采用只读方式打开其需译码的文件再利用循环和判断语句对文件中的编码符根据创建的哈夫曼树进行译码，最后创建一文件将其译码存入文件中。3）变量及类型：HuffmanTreeHT：结构体树型形参变量，接收main()传过来树的首地址。List*L：结构体形参数组，接收main()传过来初始化数组的首地址。intn:整型形参变量，接收main()传过来HT数组的长度。charch：字符型变量，用于存放从要编码的文件取出的字符。inta:整型变量，放结构体数组HT的下标；intw:整型变量，放结构体数组HT的下标；FILE*fp1：文件指针变量，指向要译码的文件。FILE*fp2：文件指针变量，指向存放译码的文件。（2）、1）函数原形：voidHfmDecodinginput(HuffmanTree&HT,List*L,intn)2）功能：从终端输入0,1字符串存放于字符数组中，再根据创建的哈夫曼树利用循环进行译码。3）变量及类型：HuffmanTreeHT：结构体树型形参变量，接收main()传过来树的首地址。List*L：结构体形参数组，接收main()传过来初始化数组的首地址。intn:整型形参变量，接收main()传过来HT数组的长度。charcharhc[]：字符型数组，用于存放从终端输入的01字符串。inta:整型变量，放结构体数组HT的下标；intw:整型变量，放结构体数组HT的下标；inti：整型变量，放结构体数组HT的下标，也用于循环变量。39 计算机工程系计算机12级卓越计Y121班数据结构实训报告打印模块（1）、1）函数原形：voidPrintHC()2）功能：利用只读的方式打开存放编码的文件，再利用循环读取编码用判断语句将其限制每行50个代码显示在终端上并将此形式写入另一文件中。3）变量及类型：intnum：整型变量，用于代码串计数，使其每行实现输出50个。charch：字符型变量，用于存放从代码串文件中取出的字符。FILE*fp1：文件指针变量，指向存放代码串的文件。FILE*fp2：文件指针变量，指向存放另一种形式的代码串文件。（2）、1）函数原形：voidPrintTree(HuffmanTreenode,HuffmanTreenode1,intlevel)2)功能：定义树型头指针node,移动指针node1，采用先序递归遍历凹入式打印哈夫曼树，采用追加方式创建用于存放凹入式哈夫曼树，再利用循环调节结点的位置以及关系。3）变量及类型：HuffmanTreenode：结构体树数组类型指针形参变量，一直指向首单元，只为在递归中容易移动指针变量。HuffmanTreenode1：结构体树数组类型指针形参变量，初始化指向末单元（即根结点），递归中指针逐一遍历作递归的实参变量。intlevel：整型变量形参，用作循环变量，只为在递归中调节树的结点的位置使关系更能直观。4总结1、程序调试与测试情况：①测试目的：检测文件统计字符频率是否成功。39 计算机工程系计算机12级卓越计Y121班数据结构实训报告结果分析：从文件中进行对照，可得出字符统计无错误。②测试目的：检测建树、初始化是否成功。输入：1输出：给出提示“savehfmTreeHTsucceed!!!”，输出了“哈夫曼编码表”最后给出提示“savehfmTreeHT-HCsucceed！！Initializationsucceed!!!!!”截屏：39 计算机工程系计算机12级卓越计Y121班数据结构实训报告39 计算机工程系计算机12级卓越计Y121班数据结构实训报告结果分析：回到文件中查看，建树成功，哈夫曼编码表也无错误。③测试目的：检测终端输入的编码是否成功。输入：“liuzhou”输出：“1011101110000110110110111101110100001”截屏：结果分析：通过初始化得出的编码表进行，比较可得编码无错误。④测试目的：检测终端输入的译码是否成功。输入：“1100110110111010111101110101”输出：“thisis”截屏：结果分析：通过初始化得出的编码表进行，比较可得编码无错误。39 计算机工程系计算机12级卓越计Y121班数据结构实训报告2、感想：在本次程序设计中，我对最优二叉树有了深入的了解，而且也知道程序设计是要求分块调试的。当然因为知识的欠缺，很多函数功能的实现都是只是通过参数传递而不能实现从文件中读取；而且对于时间和空间的优化并没有体现。在编写过程中也会出现很多错误，不过最终通过百度，问老师也能解决了。5参考文献[1]严蔚敏吴伟民，数据结构（C语言版），北京：清华大学出版社，2007[2]严蔚敏吴伟民，数据结构题集，北京：人民邮电出版社，1999附录：程序清单#include#include#include#defineN95///////////////////////////////////////////////////////////////哈夫曼树的存储结构typedefstructHTNode{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//////////////////////////////////////////////////////////////动态分配数组存储哈夫曼编码表typedefchar**HuffmanCode;/////////////////////////////////////////////////////////////统计字符频率的存储结构typedefstruct{charchars;intweight;}List,*Lists;/////////////////////////////////////////////////////各子函数的声明//////////////////////39 计算机工程系计算机12级卓越计Y121班数据结构实训报告voidmenu();//主菜单voidmenu1();//编码（HuffmanEncoding）的子菜单voidmenu2();//译码（HuffmanDecoding）的子菜单voidchoose1(HuffmanTree&HT,HuffmanCode&HC,List*L);//对编码Hfmcoding子菜单的选择voidchoose2(HuffmanTree&HT,HuffmanCode&HC,List*L);//对译码HfmDecoding子菜单的选择voidInitialization(HuffmanTree&HT,HuffmanCode&HC,List*L);//初始化voidStatistics(List*L,intn);//统计文件中的字符频率intmin(HuffmanTreeHT,inti);//查找最小结点的操作voidCreateHT_HC(HuffmanTree&HT,HuffmanCode&HC,List*L,intn);//构造哈夫曼树及哈夫曼编码表voidSaveHT(HuffmanTree&HT,intm);//保存建好的哈夫曼树voidSaveHT_HC(HuffmanCode&HC,List*L,intn);//保存哈夫曼编码的对照表并将表输出voidHfmEncodingtxt(HuffmanCode&HC,intn);//编码文件中的字符串voidHfmEncodinginput(HuffmanCode&HC);//编码从键盘输入的字符串voidHfmDecodingtxt(HuffmanTree&HT,List*L,intn);//译码文件中的0、1代码串voidHfmDecodinginput(HuffmanTree&HT,List*L,intn);//译码从键盘输入的0、1代码串voidPrintHC();//输出每行50个的编码串voidPrintTree(HuffmanTreenode,HuffmanTreenode1,intlevel);//凹入式打印哈夫曼树///////////////////////////////////////实现客户的选择功能///////////////////////////////////////////voidmain()//主函数{intchoose;39 计算机工程系计算机12级卓越计Y121班数据结构实训报告HuffmanTreeHT;HuffmanCodeHC;ListL[N]={};while(1){menu();scanf("%d",&choose);switch(choose)//对主菜单的选择{case1:///////////////////////////////////////初始化操作/////////////////////////Initialization(HT,HC,L);printf(" 请按回车键回主菜单.");getchar();getchar();system("cls");break;case2://////////////////////////////////////////编码操作////////////////////////////////////////////system("cls");choose1(HT,HC,L);system("cls");break;case3://///////////////////////////////////////////译码操作///////////////////////////system("cls");choose2(HT,HC,L);system("cls");break;case4://////////////////////////打印代码文件///////////////////////////////system("cls");PrintHC();printf(" 请按回车键回主菜单.");getchar();getchar();system("cls");39 计算机工程系计算机12级卓越计Y121班数据结构实训报告break;case5://////////////////////////凹入式打印哈夫曼树///////////////////////system("cls");PrintTree(HT,HT+2*N-1,1);printf(" 已将凹入式形式的哈夫曼树存入hfmTreeHT-chars.txt文件中，请自行查看！！！ ");printf(" 请按回车键回主菜单.");getchar();getchar();system("cls");break;case6:printf(" 感谢您的使用！t请按回车键退出。");exit(0);break;default:system("cls");printf(" illegalletter!pleaseinputrightnumebr. ");getchar();}}}voidInitialization(HuffmanTree&HT,HuffmanCode&HC,List*L)//初始化{Statistics(L,N);CreateHT_HC(HT,HC,L,N);printf(" Initializationsucceed!!!!! ");}///////////////////////////////统计文件中的字符(字符是从Ascll32--126)频率，将其频率作为权值建立哈夫曼树/////////voidStatistics(List*L,intn)39 计算机工程系计算机12级卓越计Y121班数据结构实训报告{FILE*fp;inti,j;intm;charch;for(i=0,j=32;j<=126;j++){L[i].chars=j;i++;}if((fp=fopen("test.txt","r"))==NULL)//打开test.txt文件{printf("cannotopenthefile!!!");exit(0);}while((ch=fgetc(fp))!=EOF)//从文件中逐个取出字符直到文件结尾{m=ch-32;//m等于字符的Ascll码值减去空格的Ascll码，其值就为这个字符存放数组的下标L[m].weight++;}fclose(fp);}/////////////////////////////////////////////////求解最小权值的操作/////////////////intmin(HuffmanTreeHT,inti){intj,flag=0;unsignedintk=99999;//定义k足够大for(j=1;j<=i;j++)//循环在1-i个结点中寻找权值最小的结点if(HT[j].weightweight=L[i-1].weight;p->parent=0;p->lchild=0;p->rchild=0;}for(i=n+1;i<=m;++i,++p){p->parent=0;p->lchild=0;p->rchild=0;}39 计算机工程系计算机12级卓越计Y121班数据结构实训报告////////////////////////////构造哈夫曼树///////////////////////////////////for(i=n+1;i<=m;++i){s1=min(HT,i-1);//在HT[1-i]中选择parent为0且weight最小的两个结点，其序号分别为s1,s2s2=min(HT,i-1);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}SaveHT(HT,m);//保存创建好的哈夫曼树于hfmTreeHT.txt文件中////////////////////////逆向求叶子结点的编码//////////////////////////////HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//申请n+1个头指针空间，0号单元未用cd=(char*)malloc(n*sizeof(char));//申请求编码的工作区间cd[n-1]='';//编码的结束符for(i=1;i<=n;i++){start=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码if(HT[f].lchild==c)cd[--start]='0';elsecd[--start]='1';HC[i]=(char*)malloc((n-start)*sizeof(char));//申请第i个字符编码的空间，因为每个字符的编码长度不一，所以申请n-start个strcpy(HC[i],&cd[start]);39 计算机工程系计算机12级卓越计Y121班数据结构实训报告}free(cd);SaveHT_HC(HC,L,N);//保存哈夫曼编码的对照表HC于HfmTree.txt中}///////////////////////////////////////////////////编码文件中的字符串//////////////////////////////////voidHfmEncodingtxt(HuffmanCode&HC,intn){inti=1;FILE*fp1;FILE*fp2;charch;if((fp1=fopen("test1.txt","r"))==NULL)//打开test1.txt文件{printf("cannotopenthefile!!!");exit(0);}if((fp2=fopen("hfmTreeHC.txt","w+"))==NULL)//打开建立一个hfmTreeHC.txt文件，用于存放test1.txt文件中字符的编码串{printf("cannotopenthefile!!!");exit(0);}while((ch=fgetc(fp1))!=EOF)//从test1.txt文件中逐个字符取出{intAscll=ch-32+1;fprintf(fp2,"%s",HC[Ascll]);i++;}printf(" 文件编码成功！！！编码的0、1串已存入hfmTreeHC.txt文件请自行查看。 ");fclose(fp1);39 计算机工程系计算机12级卓越计Y121班数据结构实训报告fclose(fp2);}/////////////////编码从键盘输入的字符串////////////voidHfmEncodinginput(HuffmanCode&HC){inti;charchars[20];printf(" 输入少于20个字符的串：");getchar();gets(chars);printf(" 字符串的编码串为： ");for(i=0;chars[i]!='';i++){intAscll=chars[i]-32+1;printf("%s",HC[Ascll]);}printf(" 字符串编码成功！！！ ");}/////实现对文件hfmTreeHC.txt中的代码串进行译码，并将其译码存入hfmDecode.txt文件///////////////voidHfmDecodingtxt(HuffmanTree&HT,List*L,intn){inti=1,j=1;intflag=1;charch;FILE*fp1;FILE*fp2;if((fp1=fopen("hfmTreeHC.txt","r"))==NULL)//打开hfmTreeHC.txt文件{printf("cannotopenthefile!!!");39 计算机工程系计算机12级卓越计Y121班数据结构实训报告exit(0);}if((fp2=fopen("hfmDecode.txt","w+"))==NULL)//打开建立一个hfmDecode.txt文件，用于存放hfmTreeHC.txt文件中编码的译码{printf("cannotopenthefile!!!");exit(0);}inta=2*n-1,w;//定义a，初始化为根节点的下标，w用于记录左孩子或右孩子的下标while((ch=fgetc(fp1))!=EOF)//从文件hfmTreeHC.txt中逐个取出字符{if(ch=='0')w=HT[a].lchild;elsew=HT[a].rchild;if(w<=N){fprintf(fp2,"%c",L[w-1].chars);//到此处，一个译码已形成，然后再逐个将相应的译码写入文件hfmDecode.txt中a=2*n-1;//a重置为根结点}elsea=w;}printf(" 译码成功！！！！！编码的0、1串译文已存入hfmDcode.txt文件请自行查看。 ");fclose(fp1);fclose(fp2);}//////////////////////实现对从键盘输入的代码串进行译码//////////////////////voidHfmDecodinginput(HuffmanTree&HT,List*L,intn){inti;inta=2*n-1,w;39 计算机工程系计算机12级卓越计Y121班数据结构实训报告charcharhc[N];printf("请输入你要译码的0、1编码串(len<95)： ");getchar();gets(charhc);for(i=0;charhc[i]!='';i++){if(charhc[i]=='0')w=HT[a].lchild;elsew=HT[a].rchild;if(w<=N){printf("%ct",L[w-1].chars);a=2*n-1;}elsea=w;}}///////打印hfmTreeHC.txt文件中的代码，并将代码的译码另存入Codefile.txt文件中////////voidPrintHC(){intnum=0;charch1,ch2;FILE*fp1;FILE*fp2;FILE*fp3;if((fp1=fopen("hfmTreeHC.txt","r"))==NULL)//打开hfmTreeHC.txt文件{printf("cannotopenthefile!!!");exit(0);}if((fp2=fopen("Codefile.txt","w+"))==NULL)//创建打开Codefile.txt文件{39 计算机工程系计算机12级卓越计Y121班数据结构实训报告printf("cannotopenthefile!!!");exit(0);}printf(" ttCodefile.txt文件中的代码串为： ");while((ch1=fgetc(fp1))!=EOF)//从文件hfmTreeHC.txt中逐个取出字符{printf("%c",ch1);fprintf(fp2,"%c",ch1);//将取出的符写入Codefile.txt文件中num=num+1;if(num%50==0)//每行输出50个代码{printf(" ");fprintf(fp2,"%c",' ');}}printf(" 已将hfmTreeHC.txt中的代码的译码另存入Codefile.txt文件中，请自行查看！！！ ");fclose(fp1);fclose(fp2);}////////////////凹入式打印哈夫曼树//////////voidPrintTree(HuffmanTreenode,HuffmanTreenode1,intlevel)//采用先序遍历,node为指向HT的头指针，node1则指向HT[i]当前的存储单元{if(node1==NULL)return;FILE*fp;fp=fopen("hfmTreeHT-chars.txt","a+");if(fp==NULL){printf("cannotopenfilehfmTreeHT-chars.txt!!! ");exit(0);}39 计算机工程系计算机12级卓越计Y121班数据结构实训报告for(inti=1;i<=level;i++){printf("|");fprintf(fp,"%c%c%c",'|','','');}printf("%d",node1->weight);printf(" ");fprintf(fp,"%d",node1->weight);//将字符型的哈夫曼树写于hfmTreeHT-chars.txt文件中fprintf(fp,"%c",' ');if(node1->lchild!=0)PrintTree(node,node+node1->lchild,level+1);if(node1->rchild!=0)PrintTree(node,node+node1->rchild,level+1);fclose(fp);}voidSaveHT(HuffmanTree&HT,intm)//保存哈夫曼树于hfmTreeHT.txt文件中{inti;FILE*fp;fp=fopen("hfmTreeHT.txt","w+");if(fp==NULL){printf("cannotopenfilehfmTreeHT.txt!!! ");exit(0);}for(i=1;i<=m;i++)fprintf(fp,"%dt%dt%dt%dt%d ",i,HT[i].parent,HT[i].lchild,HT[i].rchild,HT[i].weight);fclose(fp);printf(" savehfmTreeHTsucceed！！！ ");}39 计算机工程系计算机12级卓越计Y121班数据结构实训报告voidSaveHT_HC(HuffmanCode&HC,List*L,intn)//保存哈夫曼编码的对照表并将表输出{inti;FILE*fp;fp=fopen("hfmTreeHT-HC.txt","w+");if(fp==NULL){printf("cannotopenfilehfmTree.dat!!! ");exit(0);}printf(" t哈夫曼编码表 ");for(i=1;i<=n;i++)//循环将哈夫曼编码表写入hfmTreeHT-HC.txt文件中{fprintf(fp,"%ct%dt",L[i-1].chars,L[i-1].weight);fprintf(fp,"%s ",HC[i]);}for(i=1;i<=n;i++)//循环将哈夫曼编码表输出在屏幕上{printf("%c-->(%d)---%s",L[i-1].chars,L[i-1].weight,HC[i]);if(i%2==0)printf(" ");}fclose(fp);printf(" savehfmTreeHT-HCsucceed！！！ ");}/////////////////////////////////////////////对编码Hfmcoding子菜单的选择////////////////voidchoose1(HuffmanTree&HT,HuffmanCode&HC,List*L){intchoose1,a=1;while(a){menu1();scanf("%d",&choose1);39 计算机工程系计算机12级卓越计Y121班数据结构实训报告switch(choose1){case1:////////////////////实现对文件中的字符进行编码///////////////////HfmEncodingtxt(HC,N);printf(" 请按回车键回子菜单.");getchar();getchar();system("cls");break;case2:////////////////////实现对从键盘输入的字符进行编码//////////////system("cls");HfmEncodinginput(HC);printf(" 请按回车键回子菜单.");getchar();//getchar();system("cls");break;case3:///////////////////退出编码的子菜单，进入主菜单///////////////printf("感谢您的使用！ 请按回车键退出并返回主菜单。");getchar();getchar();system("cls");a=0;break;default:system("cls");printf(" illegalletter!pleaseinputrightnumebr. ");getchar();}}}39 计算机工程系计算机12级卓越计Y121班数据结构实训报告///////////////////////////////////////////对译码HfmDecoding子菜单的选择//////voidchoose2(HuffmanTree&HT,HuffmanCode&HC,List*L){intchoose2,a=1;while(a){menu2();scanf("%d",&choose2);switch(choose2){case1://////////////////////实现对文件中的编码代码进行译码////////////////HfmDecodingtxt(HT,L,N);printf(" 请按回车键回子菜单.");getchar();getchar();system("cls");break;case2://///////////////////实现对从键盘输入的编码代码串进行译码/////////////system("cls");HfmDecodinginput(HT,L,N);printf(" 请按回车键回子菜单.");getchar();system("cls");break;case3:///////////////////退出译码的子菜单，进入主菜单//////////////printf(" 感谢您的使用！t请按回车键退出并返回主菜单。");getchar();getchar();a=0;system("cls");break;39 计算机工程系计算机12级卓越计Y121班数据结构实训报告default:system("cls");printf(" illegalletter!pleaseinputrightnumebr. ");getchar();}}}//////////////////////////////////////主菜单//////////////////////////////////////////////////////////voidmenu(){printf(" **********************欢迎进入哈夫曼编码译码菜单*************************** ");printf(" 1、初始化(Initialization) ");printf(" 2、编码（Huffmancoding） ");printf(" 3、解码(Huffmandecoding) ");printf(" 4、打印代码文件(Print) ");printf(" 5、打印哈夫曼树(Treeprinting) ");printf(" 6、退出运行(Quit) ");printf(" ******************************************************************************** ");printf(" 请注意：在你选择各项操作前请先进行1、初始化(Initialization)，否则将会出错!!! ");printf("输入您的选择（1~6）：");}/////////////////////////////////////////////编码（Huffmancoding）的子菜单/////////////////////////voidmenu1(){printf("****************************Huffmancoding*****************************");printf(" 1、Huffmancodetxt ");printf(" 2、Huffmancodeinput ");printf(" 3、Quit ");39 计算机工程系计算机12级卓越计Y121班数据结构实训报告printf("******************************************************************************** ");printf("输入您的选择（1~3）：");}///////////////////////////////////////////译码（HuffmanDecoding）的子菜单////////////////////////voidmenu2(){printf("****************************Decoding*****************************");printf(" 1、HuffmanDecodetxt ");printf(" 2、HuffmanDecodeinput ");printf(" 3、Quit ");printf("******************************************************************************** ");printf("输入您的选择（1~3）：");}39