(完整word版)Huffman編碼報(bào)告

(完整word版)Huffman編碼報(bào)告(完整word版)Huffman編碼報(bào)告(完整word版)Huffman編碼報(bào)告《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)上機(jī)實(shí)習(xí)報(bào)告課設(shè)題目Huffman編碼和解碼班級(jí)學(xué)生姓名學(xué)號(hào)指導(dǎo)教師時(shí)間2015.12—2015。1第23頁(yè)（共27頁(yè)）一、設(shè)計(jì)目的1.進(jìn)一步熟悉C語(yǔ)言開發(fā)環(huán)境，熟悉用C語(yǔ)言完成一個(gè)應(yīng)用程序的設(shè)計(jì)過(guò)程，掌握有關(guān)編輯、調(diào)試和整合程序的方法和技巧.2.通過(guò)此設(shè)計(jì),了解《數(shù)據(jù)結(jié)構(gòu)》課程中霍夫曼編碼的的有關(guān)內(nèi)容,明確其操作，熟悉其設(shè)計(jì)，同時(shí)學(xué)習(xí)到有關(guān)位向量的內(nèi)容，對(duì)文件掌握加深二、設(shè)計(jì)內(nèi)容Huffman編碼與解碼（必做)(Huffman編碼、二叉樹)[問(wèn)題描述］對(duì)一篇英文文章(大于2000個(gè)英文字符），統(tǒng)計(jì)各字符出現(xiàn)的次數(shù)，實(shí)現(xiàn)Huffman編碼，以及對(duì)編碼結(jié)果的解碼.［基本要求]（1)輸出每個(gè)字符出現(xiàn)的次數(shù)和編碼，其中求最小權(quán)值要求用堆實(shí)現(xiàn)。（2)在Huffman編碼后，要將編碼表和英文文章編碼結(jié)果保存到文件中,編碼結(jié)果必須是二進(jìn)制形式，即01的信息用比特位表示，不能用字符’0’和'1（3)提供讀編碼文件生成原文件的功能。三、數(shù)據(jù)結(jié)構(gòu)說(shuō)明在該程序中我僅僅使用了兩個(gè)結(jié)構(gòu)體來(lái)完成編碼,用位域來(lái)實(shí)現(xiàn)bite流存儲(chǔ)：constintMAXSIZE=300;//定義一次分配的Huffman儲(chǔ)存單詞最大量為500constintOVERFLOW=0;constintERROR=0;constintLineCountNum=500;typedefstructWordCount｛ charWord;//存放字符 intfreq；intparent,lchild，rchild；//存放親子節(jié)點(diǎn)位置intplace；//用來(lái)保存第一次堆排序后，建立霍夫曼表前的相對(duì)位置 char*HuffmanCode;//存放霍夫曼編碼}WordCount,*WC;//存放單詞結(jié)點(diǎn)的結(jié)構(gòu)體typedefstructHuffmanTree{ WCw; intNumber；//存儲(chǔ)有多少數(shù)據(jù)存入}HuffmanTree，*HTree;typedefstruct｛ unsignedinta：1；}bite;//設(shè)置位段，存儲(chǔ)一個(gè)bite//****＊＊*****＊＊＊操作函數(shù)聲明*＊**＊＊＊**＊*voidInitHuffmanTree(HTree&H）;//初始化霍夫曼樹voidHeapSort（WC&W，intNumber,intchoice）；//堆排序核心函數(shù)voidHeapAdjust(WC&W,intdown,intup,intchoice);//堆排序調(diào)整函數(shù)，實(shí)現(xiàn)兩種排序voidHuffmanCoding（HTree＆H，WC＆HT）；//求霍夫曼樹和霍夫曼編碼表voidShowHuffmanTree(HTreeH);//輸出霍夫曼樹voidSelect(WC＆W,inti，int＆s1,int＆s2);//選擇1-i—1之間最小的兩個(gè)數(shù)，且parent為0,用s1,s2返回voidGetTheDeCode(HTreeH);//將編碼結(jié)果寫入函數(shù)voidPutTheDeCode（FILE＊fp1，F(xiàn)ILE＊fp2）；//將編碼結(jié)果解碼得到文章voidCountTheWord（HTree&H,FILE＊fp);//記錄單詞權(quán)值voidShowTheEassy(FILE＊wp);//展示文章四、詳細(xì)設(shè)計(jì)首先我給出了編碼和解碼的菜單供其選擇在編碼功能中,我先通過(guò)CountTheWord（）函數(shù)進(jìn)行單詞權(quán)值記錄，然后進(jìn)入編碼功能，值得一提的是,編碼時(shí)我給堆排序設(shè)計(jì)了兩種排序形式—-對(duì)權(quán)值的排序和對(duì)位置的排序，以達(dá)到選擇兩個(gè)最小的權(quán)值結(jié)點(diǎn)的最優(yōu)時(shí)間復(fù)雜度的目的，此功能通過(guò)switch實(shí)現(xiàn),但要給編碼結(jié)構(gòu)體中放置一個(gè)place空間，這也從側(cè)面反映了時(shí)間和空間矛盾的地方（值得一提的是，有些編碼并不可見且有特殊含義，如換行符，所以將字符放入文件中時(shí)，并不對(duì)其進(jìn)行處理，讀出是進(jìn)行順序讀出)編碼結(jié)束后將編碼結(jié)果，對(duì)應(yīng)字符分別存放在文件中，然后對(duì)整篇文章進(jìn)行編碼解碼時(shí)依據(jù)霍夫曼編碼的唯一性進(jìn)行比較求解，遇到同樣的字符即返回對(duì)應(yīng)的字母并寫入解碼文件中五、調(diào)試與測(cè)試(測(cè)試數(shù)據(jù)：獻(xiàn)給艾米莉的玫瑰)首先打開文件進(jìn)行字符權(quán)值統(tǒng)計(jì)并輸出結(jié)果（有些符號(hào)不可見,所以無(wú)法顯示）然后對(duì)其進(jìn)行堆排序輸出編碼表，及其對(duì)應(yīng)親子關(guān)系(#號(hào)代表為父結(jié)點(diǎn)）輸出編碼結(jié)果（可以輕易看出編碼具備唯一性）將編碼寫入文件，一下顯示文件部分內(nèi)容位域存儲(chǔ)的bite編碼文檔編碼對(duì)應(yīng)的字符順序存儲(chǔ)（可以看到因?yàn)閾Q行符的存在,自動(dòng)換行了)解碼（將文章在命令行顯示，也寫入了翻譯文檔(以doc格式保存））六、課程設(shè)計(jì)總結(jié)本次程序設(shè)計(jì)過(guò)程中遇到過(guò)許多大大小小的問(wèn)題,也在設(shè)計(jì)思路上遇到過(guò)難題，但都在各方面的努力下得到了解決。一些問(wèn)題如下：Bite形式保存由于以前沒(méi)學(xué)到過(guò)位向量的內(nèi)容，有一段時(shí)間無(wú)法實(shí)現(xiàn)這個(gè)功能，后來(lái)在網(wǎng)絡(luò)上偶然接觸到位域的內(nèi)容，認(rèn)識(shí)到其可行性，于是解決了此問(wèn)題選擇最小的兩個(gè)權(quán)值一開始我認(rèn)識(shí)的這個(gè)可能很復(fù)雜，又聯(lián)想到堆排序可以對(duì)其有序輸出，但我又不想改變其位置,所以增設(shè)一個(gè)place記錄一開始的編碼表位置，進(jìn)行編碼時(shí)改變后可以輕易還原總結(jié)：霍夫曼編碼在通信領(lǐng)域內(nèi)是十分重要的內(nèi)容,對(duì)其的掌握既能幫助我們理解二叉樹的重要性，也能為我們未來(lái)工作提供一個(gè)更廣闊的舞臺(tái)七、附錄/＊*題目：Huffman編碼的編碼和解碼*作者：楊歡*學(xué)號(hào):161420325*完成時(shí)間:2015-12-30算法思想：以書上的霍夫曼算法為核心進(jìn)行文章（所有內(nèi)容，包括標(biāo)點(diǎn),換行符,所以命令行可能無(wú)法顯示部分字符）編碼和解碼.對(duì)于比特位的存儲(chǔ)，我選擇用位域進(jìn)行簡(jiǎn)單方便的操作。文件的讀寫都以最基本的方式進(jìn)行.測(cè)試文章上，我選擇艾米莉的玫瑰這一小說(shuō)測(cè)試,數(shù)據(jù)量大，可以驗(yàn)證程序的正確性*/＃include〈stdio。h>#include〈stdlib.h〉#include〈string。h〉constintMAXSIZE=300；//定義一次分配的Huffman儲(chǔ)存單詞最大量為500constintOVERFLOW=0;constintERROR=0;constintLineCountNum=500；typedefstructWordCount{ charWord；//存放字符 intfreq;intparent,lchild,rchild；//存放親子節(jié)點(diǎn)位置intplace;//用來(lái)保存第一次堆排序后，建立霍夫曼表前的相對(duì)位置 char*HuffmanCode；//存放霍夫曼編碼}WordCount,*WC；//存放單詞結(jié)點(diǎn)的結(jié)構(gòu)體typedefstructHuffmanTree｛ WCw； intNumber;//存儲(chǔ)有多少數(shù)據(jù)存入｝HuffmanTree，*HTree;typedefstruct{ unsignedinta:1；｝bite；//設(shè)置位段，存儲(chǔ)一個(gè)bite//**＊＊**＊*＊＊＊**＊操作函數(shù)聲明＊*＊＊＊＊*＊*＊＊voidInitHuffmanTree(HTree＆H);//初始化霍夫曼樹voidHeapSort（WC&W,intNumber，intchoice）;//堆排序核心函數(shù)voidHeapAdjust（WC&W,intdown,intup,intchoice);//堆排序調(diào)整函數(shù)，實(shí)現(xiàn)兩種排序voidHuffmanCoding（HTree＆H，WC＆HT);//求霍夫曼樹和霍夫曼編碼表voidShowHuffmanTree(HTreeH)；//輸出霍夫曼樹voidSelect(WC&W，inti,int＆s1,int＆s2)；//選擇1—i—1之間最小的兩個(gè)數(shù),且parent為0，用s1,s2返回voidGetTheDeCode（HTreeH)；//將編碼結(jié)果寫入函數(shù)voidPutTheDeCode(FILE*fp1,FILE＊fp2);//將編碼結(jié)果解碼得到文章voidCountTheWord（HTree&H，F(xiàn)ILE*fp）；//記錄單詞權(quán)值voidShowTheEassy(FILE＊wp);//展示文章//***＊***＊**＊*主函數(shù)*＊＊＊＊＊**＊*****＊intmain（)｛ FILE＊fp，*wp； HTreeH； WCHT;//存放編碼表 printf("**＊＊*＊*＊＊＊＊*＊菜單＊＊**＊***＊*＊*＊***＊＊*＊＊*＊*＊＊\n"）; printf("＊＊＊＊＊**＊＊1.編碼文檔***＊**＊*\n"）; printf（”＊＊＊＊＊***＊2.解碼文檔**＊＊＊＊＊*\n"）; printf(”*＊＊＊＊＊*＊＊0.退出*＊*＊*＊*＊＊*＊＊＊＊＊**＊＊＊＊＊＊＊*＊**\n”）； printf(”請(qǐng)輸入您的選擇:"); intchoice； scanf("%d"，＆choice); getchar（）; while（choice!=0) { switch（choice） ｛ case1: InitHuffmanTree(H）; if（!（fp=fopen("獻(xiàn)給艾米莉的玫瑰。txt”，"r”）)) {//以文本文件形式打開文件 printf("此文件不存在\n”)； exit（ERROR); } printf("文件打開成功\n”）; CountTheWord（H,fp);printf(”按任意鍵統(tǒng)計(jì)該文章各字符出現(xiàn)的頻率為\n"); getchar(）；ShowHuffmanTree（H）;printf("按任意鍵開始堆排序\n”); getchar(）;HeapSort(H-〉w,H—>Number,1）；//對(duì)頻率排序printf(”按任意鍵輸出堆排序后的情況\n”）;getchar（）;ShowHuffmanTree（H）； printf（”現(xiàn)在開始進(jìn)行霍夫曼樹的構(gòu)建和霍夫曼編碼的構(gòu)建\n");HuffmanCoding（H,HT）;printf（”輸入任意鍵輸出霍夫曼編碼表："）;getchar（); printf(”字符 位置 權(quán)值 左孩子 右孩子 父親\n"）；for（inti=1；i〈=2＊H—>Number；++i） ｛ printf("％c %d ％d %d %d %d\n"，HT［i］。Word,i，HT[i].freq,HT[i］。lchild,HT［i].rchild，HT[i］。parent)； ｝ printf（"按任意鍵輸出構(gòu)建的霍夫曼編碼結(jié)果:”); getchar()； for（inti=1;i<=H—>Number;++i） { printf("％c 對(duì)應(yīng)的編碼為 %s\n”,H—>w[i］.Word，H—>w［i］.HuffmanCode）； ｝ printf("按任意鍵將結(jié)果寫入文件\n"）; getchar（)； GetTheDeCode（H）; free（H）；//釋放空間，避免影響 break; case2: PutTheDeCode(fp，wp）； printf（"該英文文章為\n"）; ShowTheEassy(wp）; printf("\n"）; fclose（fp）; break； case0： break; ｝ printf(”請(qǐng)輸入您的選擇："）; scanf（"%d”,＆choice）; getchar（）;｝return0;}//＊*＊＊＊＊＊＊＊操作函數(shù)實(shí)現(xiàn)＊＊*＊******voidInitHuffmanTree（HTree＆H)｛if(！(H=（HuffmanTree*）malloc(sizeof（HuffmanTree)）))exit（OVERFLOW）;if（!(H-〉w=（WC）malloc（sizeof(WordCount)*MAXSIZE）)） exit（OVERFLOW）；//創(chuàng)建結(jié)點(diǎn) H—>Number=0；}//**＊***＊*＊＊*＊＊*＊*將結(jié)果寫入文件**＊*＊*＊***＊＊**＊＊*＊**voidGetTheDeCode（HTreeH）｛ FILE*fp,*wp; //****＊**＊將編碼表寫出＊＊＊***** if（！(fp=fopen（”編碼表文檔.txt"，"w”））） {//以二進(jìn)制方式寫出文章編碼printf(”此文件不存在\n”)； clearerr（fp); exit（ERROR); ｝ for（inti=1;i〈=H—〉Number;++i) fprintf(fp，"％s\n”，H—>w[i]。HuffmanCode）; fclose（fp）； if（!(fp=fopen（”編碼表對(duì)應(yīng)單詞文檔.txt"，”w"）)) {//以二進(jìn)制方式寫出文章編碼printf(”此文件不存在\n”）; clearerr（fp); exit（ERROR); } for（inti=1；i〈=H-〉Number；++i) fprintf(fp,"％c",H->w［i].Word）；//因?yàn)榇嬖趽Q行符,需要進(jìn)行讀取換行符，所以不進(jìn)行分行存儲(chǔ) fclose（fp）; //＊＊*＊＊＊＊＊將編碼文檔寫出＊**＊**＊＊*＊* if（!（fp=fopen("獻(xiàn)給艾米莉的玫瑰.txt",”r"））) ｛//打開文章進(jìn)行對(duì)比寫出編碼結(jié)果printf("此文件不存在\n”); clearerr(fp）; exit（ERROR)； ｝ if（?。╳p=fopen(”編碼文檔.txt",”wb"））） ｛//以二進(jìn)制形式寫出編碼文檔 printf（”此文檔不存在\n”); clearerr(wp)； exit（ERROR）； ｝ biteSave; while(!feof(fp)） ｛ charCount; fscanf（fp,”%c",&Count）； for(inti=1;i<=H—〉Number;++i) ｛ if（Count==H->w[i］。Word) ｛//尋找到匹配的，得到其字符編碼，現(xiàn)在將其以Bite位寫出到文件 for(intj=0;j<strlen（H—〉w［i］.HuffmanCode）；++j） { if(H—〉w[i]。HuffmanCode［j］==’1'） Save.a=1； else Save.a=0; fwrite(&Save，sizeof(bite),1,wp）；//用位段寫進(jìn)文件 } break； ｝ } } fclose(fp); fclose（wp）； printf（”寫出成功\n”）; }//*＊＊*＊＊＊＊**＊將編碼文件翻譯成英文＊＊**＊＊＊*＊***voidPutTheDeCode(FILE*fp,FILE*wp)｛ HTreeH; InitHuffmanTree（H);//＊****＊**＊＊*＊*讀取編碼文件*＊＊＊＊＊＊* if(!（fp=fopen(”編碼表文檔.txt”，”r"））） {printf（"此文件不存在\n”）； clearerr（fp）； exit(ERROR）； } intNum=1; charCount［MAXSIZE]；//存放出來(lái)的01字符串 memset（Count，0，MAXSIZE*sizeof(char）)； while(！feof（fp)） { fscanf（fp,"%s",Count）; if(strlen（Count）！=0） ｛ if（?。℉-〉w［Num］.HuffmanCode=(char*)malloc(（strlen（Count）+1）*sizeof（char））)） exit（OVERFLOW）； strcpy（H—〉w［Num］.HuffmanCode，Count)； memset（Count，0，strlen（Count)＊sizeof（char)）;//清零 ++Num; ｝ }//將編碼導(dǎo)出 fclose（fp); if(！(fp=fopen(”編碼表對(duì)應(yīng)單詞文檔。txt”，"r”)）） {printf("此文件不存在\n”）； clearerr（fp）; exit（ERROR）； } Num=1； while(!feof(fp)） ｛ H—>w［Num]。Word=fgetc（fp）; ++Num； } fclose(fp)；//＊*＊*＊＊＊＊＊**＊＊＊翻譯**＊＊＊*＊＊*＊ if（!(fp=fopen("編碼文檔。txt”，"rb”)）) ｛//以二進(jìn)制讀取編碼文檔printf（”此文件不存在\n”)； clearerr（fp）； exit(ERROR); } if(!（wp=fopen("翻譯文檔。doc”，"w”）)) ｛//寫出文章編碼printf（”此文件不存在\n”）； clearerr(wp); exit（ERROR）; ｝ bitePut;//位段，用來(lái)將字符讀出 Num=Num—2；//存儲(chǔ)了多余的換行符并且多加了一次，還原真實(shí)數(shù)目 intNumberCount=strlen(H->w［Num］。HuffmanCode);//存放最小的霍夫曼編碼數(shù)，減小后面的比較次數(shù) intCT,i=0,j=1; while（！feof(fp）） ｛ if(i<NumberCount) {//從最小字符串開始可以減少循環(huán) fread（＆Put,sizeof(bite），1，fp）； if（Put.a==1) Count[i]=’1’; else Count［i]=’0'; ++i； ｝ else ｛ while(j<=Num） ｛ if（strcmp(Count，H—〉w［j］。HuffmanCode)==0) ｛//依據(jù)霍夫曼編碼的唯一性，遇到編碼相同即可進(jìn)行單詞寫入 fprintf（wp,"％c”，H—〉w[j］。Word）； //編碼匹配，清空計(jì)數(shù)和數(shù)組，狀態(tài)重置 memset（Count，0,sizeof(char）＊（i+1)); i=0； j=1; break； ｝ ++j; if（j>Num） {//代表當(dāng)前編碼不是霍夫曼編碼,繼續(xù)讀入編碼 fread(&Put，sizeof(bite），1，fp); if（Put。a==1) Count［i］=’1'； else Count［i］=’0’; j=1; ++i； ｝ ｝ ｝ } fclose(fp)； fclose（wp); ｝//＊＊*＊＊＊＊＊＊**＊＊*解碼文章輸出*＊＊*＊**＊**voidShowTheEassy（FILE*wp)｛ if(!（wp=fopen（"翻譯文檔。doc","r"）)） ｛//寫出文章編碼printf("此文件不存在\n"）； clearerr（wp); exit(ERROR）； ｝ charLine[LineCountNum]; while(！feof(wp)） { fgets（Line，LineCountNum,wp）; printf("％s"，Line); memset（Line,0，sizeof（char)*strlen（Line））；//清零 ｝}//＊****＊*＊＊**存儲(chǔ)單詞＊＊＊＊＊＊*＊**＊＊＊＊＊voidCountTheWord(HTree＆H,FILE＊fp）｛ intWordNumCount=1；//單詞結(jié)點(diǎn)記載 intjcount;//單詞重復(fù)比較操作時(shí)的臨時(shí)變量 charLineCount［LineCountNum］;//讀入文章時(shí)規(guī)定一行最大單詞量 charAcount； H-〉Number=0; while（！feof(fp)) ｛//當(dāng)文件未讀到文件尾時(shí)進(jìn)行循環(huán) memset(LineCount，0,LineCountNum)；//清零 fgets(LineCount,LineCountNum,fp）;//行輸出 for(inti=0;i〈strlen（LineCount)；++i） ｛ Acount=LineCount［i]; if（WordNumCount==1） { H-〉w[WordNumCount］.Word=Acount; H-〉w［WordNumCount].freq=1； ++H->Number； ++WordNumCount； ｝ else { jcount=WordNumCount-1; while(jcount>=1)//進(jìn)行重復(fù)單詞的比較 ｛ if(H—〉w［jcount］.Word==Acount） ｛ ++H-〉w［jcount］.freq； break; } ——jcount; if（jcount<1） ｛//代表無(wú)重復(fù)單詞,進(jìn)行加操作 H->w[WordNumCount]。Word=Acount； H-〉w[WordNumCount]。freq=1； ++H->Number; ++WordNumCount； ｝ } ｝ } } fclose(fp）;//關(guān)閉文件｝//****＊＊*＊＊＊*＊＊＊堆排序函數(shù)＊*＊***＊＊*＊***＊*＊8voidHeapAdjust（WC&W，intdown,intup,intchoice)｛//已知除W[down]。freq外均滿足堆定義,case1對(duì)頻率排序，case2對(duì)原本位置排序 WordCountrc=W［down]; switch(choice) { case1: for（intj=2*down；j<=up；j＊=2) { if(j<up&＆（W［j］.freq<W［j+1］。freq）) ++j;//j為頻率較大的記錄下標(biāo) if（?。╮c。freq<W［j].freq)) break;//rc應(yīng)插入在位置down上 W［down］=W[j]； down=j; } case2： for(intj=2＊down；j<=up；j＊=2） ｛ if（j<up＆＆(W[j]。place<W［j+1]。place)) ++j;//為位置較大的記錄下標(biāo) if(?。╮c.place〈W[j］。place）） break；//rc應(yīng)插入在位置down上 W[down]=W［j］； down=j; ｝ } W[down]=rc；｝voidHeapSort（WC&W,intNumber,intchoice){ WordCountt； for(inti=Number/2；i>0;—-i) HeapAdjust(W,i,Number，choice);//建成大頂堆 for（inti=Number;i>1;—-i) { //將堆頂記錄和當(dāng)前未經(jīng)排序的子序列1。。i中最后一個(gè)記錄交換 t=W［1]; W[1］=W[i］； W［i]=t; //1。。。。i-1重新調(diào)整為大頂堆 HeapAdjust(W，1,i—1，choice）; ｝｝//＊****＊＊＊＊*＊＊**霍夫曼編碼核心函數(shù)*＊*＊＊*＊＊**＊voidHuffmanCoding(HTree＆H，WC＆HT){//＊*＊**＊*＊*＊＊***＊＊霍夫曼編碼表構(gòu)建**＊**＊*＊＊＊＊＊** if（H—>Number<=1） return; intm=2＊H->Number，i，s1，s2；//0號(hào)單元未用WCp；//存放霍夫曼列表 if(！(HT=(WordCount＊)malloc(sizeof(WordCount）＊(m+1）))）//0號(hào)未用 exit（OVERFLOW）； for（p=HT，i=1；i〈=H-〉Number；++i) { p[i］。Word=H->w［i]。Word； p[i].freq=H—>w［i］。freq； p[i].parent=p[i］。lchild=p［i］。rchild=0； p[i]。place=i;//位置保存 } i=H->Number+1; while(i〈=m） { p［i］。Word='＃';//代表為空 p［i]。freq=0； p[i]。parent=p［i］。lchild=p［i］.rchild=0; p［i］。place=i;//位置保存 ++i; } for（i=H—〉Number+1;i〈=m;++i） { Select（HT，i-1,s1，s2）；//選擇最小的兩個(gè)數(shù) HT［s1]。parent=i； HT[s2］.parent=i; HT［i]。lchild=HT[s1］。place； HT［i].rchild