数据结构设计型实验实验报告电子版.docVIP

福州大学数计学院 《数据结构》上机实验报告 专业：应用数学 学号 姓名 班级 实验名称 应用实验 实验内容 哈弗曼编码 实 验 目 的 和 要 求 【实验目的】 了解赫夫曼树的结构特点及有关概念，掌握赫夫曼树的建立和赫夫曼编码的设计 【实验功能】 赫夫曼树的建立 从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmtree中 赫夫曼编码的生成 利用以建好的赫夫曼树，对报文文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中 编码文件的译码 利用已建好的赫夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中 问 题 描 述 和 主 要 步 骤 【测试数据】 权值为1,3,5,2,4,6,8,7,。 【设计思想】 设计步骤 1、从没有父结点的结点集合中，找出2个权值最小的结点，求和后存放到新的链表单元中，并将找到的最小2个权值的结点的父结点地址指向新生成的结点。 2、重复步骤（1），直至循环完成。 3、从叶子结点遍历父结点，并记录遍历路径（当前结点为父结点的左儿子记为0，否则记为1），然后对遍历路径进行倒置处理，便得到该结点的赫夫曼编码。 4、重复步骤（3），直至完成全部叶子结点的赫夫曼编码。 实验代码： #if !defined(__DCOMM_H) #define __DCOMM_H #define NULL 0x0 #define ERR -1 #define NOERR 1 #define NOUSE 0 #define WORD unsigned int #define ESC 27 #define MENU_TIERS 2 #define MAX_MENU_WIDTH 4 #endif #include stdio.h #include iostream #include string.h #include stdio.h #include stdlib.h #include direct.h #define MAXPATH 255 #define FILE_NAME data.txt #define BUFF_LEN 10 #define MAX_NUMS 100 #define LEN_HFMCODE 100 typedef struct { WORD Weight; char HfmCode[LEN_HFMCODE]; }DATA; typedef struct { DATA data; int pParent; int pLChild; int pRChild; }HfmNode,*HfmTree; int iLeafNums; int CreateBaseTree(HfmTree *_HfmTree,int _iLeafNums,WORD *_wWeight); void CreateHfmTree(HfmTree *_HfmTree,int _iLeafNums,WORD *_wWeight); void GetMinNodeSN(HfmTree _HfmTree,int n,int *_S1,int *_S2); void GetHfmCode(HfmTree _HfmTree,int _iLeafNums); void PrintHfmCode(HfmTree _HfmTree,int _iLeafNums); int ReadFile(char *FileName,WORD *_wWeight) { FILE *_pFile; char _ch,_sBuff[BUFF_LEN]; int i; int _iPointer; int _iSN; if(!(_pFile=fopen(FileName,rb))) { printf(The file does not exist!press any key to quit\n); return ERR; } for (i=0;iBUFF_LEN;i++) { _sBuff[i]=0x0; } _iPointer=0; _iSN=0; while (!feof(_pFile)) { _ch=fgetc(_pFile); if (_ch==,) { _wWeight[_iSN]=atoi(_sBuff); for(i=0;iBUFF_LEN;i++) { _sBuff[i]=0x0; } _iPointer=0; _iSN++;