数据结构实验四哈弗曼编码.doc

数据结构实验四实验报告实验名称:哈弗曼编码姓名:黄州龙班级:08级软件工程A班学号:082512102需求分析本实验涉及的算法思想是最优二叉树的构建,而该算法思想的实际应用广泛,哈弗曼编码就是这一算法的应用,通过本实验的练****可以加深学生对二叉树的理解,学****如何将算法学以致用,并为以后应用中有所突破奠定基础;实验程序是通过用户输入的哈弗曼编码频度表文件(.txt)路径,从硬盘中读取数据,并进一步使用哈弗曼编码算法进行哈弗曼树的构建,最后输出编码结果给用户,也可以选择将哈弗曼树存入文件保存起来;实验程序可以实现对已知频度的码值进行编码的功能,具有一定的使用价值,编写的函数算法是完全可以被用在其他的软件程序中的,具有很好的代码复用性;存储编码频度表的文件的结构:首行是一个正整数N,表示有N个码第二行是N个以空格隔开的字符,即N个码的码值,第三行是N个用空格隔开的非负整数,对应N个码值的频度;测试数据;:::26ABCDEFGHIJKLMNOPQRSTUVWXYZ12345678910111213141516171819202**********:9IAMZEPHYR987654321概要设计1、二叉链结点的定义structTreeNode{ chardata;//数据域,具体应用时可能是别的类型intvisit;//当前的访问状态 TreeNode*l;//左树域 TreeNode*r;//右树域};//endofdefinitiontoTreeNode2、创建森林和创建哈弗曼树模块StatuscreateForest(vector<TreeNode*>&forest,stringfilename)初始条件:filename所指示的文件路径有效且文件内容符合格式要求参数:第一个参数传入用来存放每个码结点的地址的向量,第二个参数传入编码频度表文件的路径字符串操作结果:从文件中读取数据并构建出码值二叉森林,为哈弗曼编码算法做准备StatuscreateHuffman(vector<TreeNode*>&forest)初始条件:传入的码值森林已经初始化参数:第一个参数传入码值森林所初始化的向量操作结果:码值森林只剩一个结点,该结点是哈弗曼树的根结点3、输出哈弗曼编码和输出哈弗曼树模块voidprintHuffmanCode(TreeNode*root)初始条件:传入的树根结点是有效的树根结点参数:第一个参数传入哈弗曼树的根结点操作结果:输出每个码值对应的哈弗曼编码printTree(TreeNode*tn,intdepth)初始条件:传入的二叉树的根是有效的,传入的二叉树深度与二叉树相对应参数:第一个参数传入要进行树形输出的二叉树的根结点第二个根结点传入二叉树的深度操作结果;将二叉树以树状进行输出,比较直观详细设计1、创建森林和创建哈弗曼树模块StatuscreateForest(vector<TreeNode*>&forest,stringfilename){ ifstreamis(());//从路径字符串初始化文//件流cout<<"从文件中读取编码频度表......\n";//提示以开始//读取intcodenum=0;TreeNode*code=NULL;is>>codenum;//读取码数cout<<"有"<<codenum<<"个编码.\n";for(inti=0;i<codenum;i++)//根据结点数一次读入码值数//据并以此创建结点森林{ code=newTreeNode; if(!code)//创建结点,若失败则返回错误returnERROR; is>>code->data; while(code->data<'A'||code->data>'Z') is>>code->data; code->l=NULL; code->r=NULL; (code);//将单结点树加入森林 code=NULL;}for(intj=0;j<codenum;j++)//依次读入频度到对应的结点{ is>>forest[j]->visit;}cout<<"读取完毕......\n现在输出内容:\n";//提示读取完//();//关闭文件流for(intk=0;k<codenum;k++){ cout<<"编码:"<<forest[k]->data<<"频度:"<<forest[k]->visit<<endl;}//输出数据以便进行确认returnO