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

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

1、计算机工程系计算机12级卓越计Y121班数据结构实训报告1题目与要求1.1问题提出本人计划编写一个哈夫曼编码译码器，主要是进行信息通信，实现在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码(复原)的信息收发站。1.2本系统涉及的知识点最优二叉树、数组、循环、函数、分支、类型结构定义、文件、递归1.3功能要求所要实现的题目功能：1)I：初始化(Initialization)。从终端读入字符集大小n及n个字符和m个权值，建立哈夫曼树，并将它存于文件hfmtree中。(2)C：编码(Coding)。利用已建好的哈夫曼树(如不在内存，则

2、从文件hfmtree中读入)，对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中。(3)D：解码(Decoding)。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件textfile中。(4)P：打印代码文件(Print)。将文件codefile以紧凑格式显示在终端上，每行50个代码。同时，将此字符形式的编码文件写入文件codeprint中。(5)T：打印哈夫曼树(Treeprinting)。将已在内存中的哈夫曼树以直观的方式(树或凹人表形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件treep

3、rint中。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）选择

4、2后，调用解码码子菜单函数，进入函数后利用switch语句实现一个如图3所示的菜单，该菜单中1、2选项调用一个函数.图3解码（Decoding）子菜单39计算机工程系计算机12级卓越计Y121班数据结构实训报告3、根据所选菜单编写相应代码：1）初始化（Init）：利用循环将字符存入结构体数组，再利用循环从文本文件中取出字符统计字符的频率存入结构体数组中，再利用循环将其作为权值存入哈夫曼树的结构体数组中再循环寻找最小结点值建立哈夫曼树，然后再将其创建哈夫曼树存入文件中，最后对树进行逆向求叶子结点的编码并将其编码表存入文件和输出在终端上。具体程序为：voi

5、dInitialization(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;char

6、ch;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班数据结构实训报告fc

7、lose(fp);}/////////////////////////////////////////////////求解最小权值的操作/////////////////intmin(HuffmanTreeHT,inti){intj,flag=0;unsignedintk=99999;//定义k足够大for(j=1;j<=i;j++)//循环在1-i个结点中寻找权值最小的结点if(HT[j].weight

8、rent置为1，标志这个结点已找过returnflag;}/////////////构造哈夫曼