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

福州大学数计学院《数据结构》上机实验报告专业：应用数学学号姓名班级实验名称应用实验实验内容哈弗曼编码实验目的和要求【实验目的】了解赫夫曼树的结构特点及有关概念，掌握赫夫曼树的建立和赫夫曼编码的设计【实验功能】赫夫曼树的建立从终端读入字符集大小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#defineNULL0x0#defineERR-1#defineNOERR1#defineNOUSE0#defineWORDunsignedint#defineESC27#defineMENU_TIERS2#defineMAX_MENU_WIDTH4#endif#include<stdio.h>#include<iostream>#include<string.h>#include<stdio.h>#include<stdlib.h>#include<direct.h>#defineMAXPATH255#defineFILE_NAME"data.txt"#defineBUFF_LEN10#defineMAX_NUMS100#defineLEN_HFMCODE100typedefstruct{ WORDWeight; charHfmCode[LEN_HFMCODE];}DATA;typedefstruct{ DATAdata; intpParent; intpLChild; intpRChild;}HfmNode,*HfmTree;intiLeafNums;intCreateBaseTree(HfmTree*_HfmTree,int_iLeafNums,WORD*_wWeight);voidCreateHfmTree(HfmTree*_HfmTree,int_iLeafNums,WORD*_wWeight);voidGetMinNodeSN(HfmTree_HfmTree,intn,int*_S1,int*_S2);voidGetHfmCode(HfmTree_HfmTree,int_iLeafNums);voidPrintHfmCode(HfmTree_HfmTree,int_iLeafNums);intReadFile(char*FileName,WORD*_wWeight){FILE*_pFile;char_ch,_sBuff[BUFF_LEN];inti;int_iPointer;int_iSN;if(!(_pFile=fopen(FileName,"rb"))){ printf("Thefiledoesnotexist!pressanykeytoquit\n"); returnERR;}for(i=0;i<BUFF_LEN;i++){ _sBuff[i]=0x0;}_iPointer=0;_iSN=0;while(!feof(_pFile)){ _ch=fgetc(_pFile); if(_ch==',') { _wWeight[_iSN]=atoi(_sBuff); for(i=0;i<BUFF_LEN;i++) { _sBuff[i]=0x0; } _iPointer=0; _iSN++; } else { _sBuff[_iPointer]=_ch; _iPointer++; }}iLeafNums=_iSN;fclose(_pFile);returnNOERR;}intCreateBaseTree(HfmTree*_HfmTree,int_iLeafNums,WORD*_wWeight){WORD_lNodeNums;inti;if(_iLeafNums<=1||_wWeight==NULL){ printf("参数错误！"); returnERR;}_lNodeNums=2*_iLeafNums-1;(*_HfmTree)=(HfmTree)malloc((_lNodeNums+1)*sizeof(HfmNode));if((*_HfmTree)==NULL){ printf("分配内存空间出错！"); returnERR;}memset((*_HfmTree),0,sizeof(HfmNode)*(_lNodeNums+1));for(i=0;i<_iLeafNums;i++){ (*_HfmTree)[i+1].data.Weight=_wWeight[i];}returnNOERR;}voidCreateHfmTree(HfmTree*_HfmTree,int_iLeafNums,WORD*_wWeight){ WORD_lNodeNums; int_S1,_S2; inti; _lNodeNums=2*_iLeafNums-1; CreateBaseTree(_HfmTree,_iLeafNums,_wWeight); for(i=_iLeafNums+1;i<=_lNodeNums;i++) { GetMinNodeSN(*_HfmTree,i-1,&_S1,&_S2); (*_HfmTree)[_S1].pParent=i; (*_HfmTree)[_S2].pParent=i; (*_HfmTree)[i].pLChild=_S1; (*_HfmTree)[i].pRChild=_S2; (*_HfmTree)[i].data.Weight=(*_HfmTree)[_S1].data.Weight+(*_HfmTree)[_S2].data.Weight; (*_HfmTree)[i].pParent=NULL;}}voidGetMinNodeSN(HfmTree_HfmTree,intCurrMaxUnitSN,int*_S1,int*_S2){inti; _HfmTree[0].data.Weight=-1; *_S1=*_S2=0; for(i=1;i<=CurrMaxUnitSN;++i) {if(_HfmTree[i].data.Weight!=0&&_HfmTree[i].pParent==0) { if(_HfmTree[i].data.Weight<_HfmTree[*_S1].data.Weight) { *_S2=*_S1; *_S1=i; } elseif(_HfmTree[i].data.Weight<_HfmTree[*_S2].data.Weight) { *_S2=i; } } } return;}voidGetHfmCode(HfmTree_HfmTree,int_iLeafNums){ int_iCurrLeafNodeSN; int_iCurrNodeSN,_iLastNodeSN; inti,_iTmp; char_tmpHfmCode[LEN_HFMCODE]; for(_iCurrLeafNodeSN=1;_iCurrLeafNodeSN<=_iLeafNums;_iCurrLeafNodeSN++) { _iCurrNodeSN=_iCurrLeafNodeSN; while(_HfmTree[_iCurrNodeSN].pParent!=NULL) { _iLastNodeSN=_iCurrNodeSN; _iCurrNodeSN=_HfmTree[_iCurrNodeSN].pParent; memset(_tmpHfmCode,0,LEN_HFMCODE); if(_HfmTree[_iCurrNodeSN].pLChild==_iLastNodeSN) { strcpy(_tmpHfmCode,"0"); } else { strcpy(_tmpHfmCode,"1"); } strcat(_tmpHfmCode,_HfmTree[_iCurrLeafNodeSN].data.HfmCode); strcpy(_HfmTree[_iCurrLeafNodeSN].data.HfmCode,_tmpHfmCode); } }}voidPrintHfmCode(HfmTree_HfmTree,int_iLeafNums){ inti; for(i=1;i<=_iLeafNums;i++) { printf("Weight:%d\tHuffmanCode:%s\n",_HfmTree[i].data.Weight,_HfmTree[i].data.HfmCode); }}voidmain(){ char_sPath[MAXPATH]; HfmTreepHfmTree; WORDwWeight[MAX_NUMS]; getcwd(_sPath,MAXPATH); strcat(_sPath,"\\"); strcat(_sPath,FILE_NAME); if(ReadFile(_sPa