數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)型實(shí)驗(yàn)實(shí)驗(yàn)報(bào)告電子版

福州大學(xué)數(shù)計(jì)學(xué)院《數(shù)據(jù)結(jié)構(gòu)》上機(jī)實(shí)驗(yàn)報(bào)告專業(yè)：應(yīng)用數(shù)學(xué)學(xué)號(hào)姓名班級(jí)實(shí)驗(yàn)名稱應(yīng)用實(shí)驗(yàn)實(shí)驗(yàn)內(nèi)容哈弗曼編碼實(shí)驗(yàn)?zāi)康暮鸵蟆緦?shí)驗(yàn)?zāi)康摹苛私夂辗蚵鼧涞慕Y(jié)構(gòu)特點(diǎn)及有關(guān)概念，掌握赫夫曼樹的建立和赫夫曼編碼的設(shè)計(jì)【實(shí)驗(yàn)功能】赫夫曼樹的建立從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立赫夫曼樹，并將它存于文件hfmtree中赫夫曼編碼的生成利用以建好的赫夫曼樹，對(duì)報(bào)文文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中編碼文件的譯碼利用已建好的赫夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中問題描述和主要步驟【測(cè)試數(shù)據(jù)】權(quán)值為1,3,5,2,4,6,8,7,?！驹O(shè)計(jì)思想】設(shè)計(jì)步驟1、從沒有父結(jié)點(diǎn)的結(jié)點(diǎn)集合中，找出2個(gè)權(quán)值最小的結(jié)點(diǎn)，求和后存放到新的鏈表單元中，并將找到的最小2個(gè)權(quán)值的結(jié)點(diǎn)的父結(jié)點(diǎn)地址指向新生成的結(jié)點(diǎn)。2、重復(fù)步驟（1），直至循環(huán)完成。3、從葉子結(jié)點(diǎn)遍歷父結(jié)點(diǎn)，并記錄遍歷路徑（當(dāng)前結(jié)點(diǎn)為父結(jié)點(diǎn)的左兒子記為0，否則記為1），然后對(duì)遍歷路徑進(jìn)行倒置處理，便得到該結(jié)點(diǎn)的赫夫曼編碼。4、重復(fù)步驟（3），直至完成全部葉子結(jié)點(diǎn)的赫夫曼編碼。實(shí)驗(yàn)代碼：#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("參數(shù)錯(cuò)誤！"); returnERR;}_lNodeNums=2*_iLeafNums-1;(*_HfmTree)=(HfmTree)malloc((_lNodeNums+1)*sizeof(HfmNode));if((*_HfmTree)==NULL){ printf("分配內(nèi)存空間出錯(cuò)！"); 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