哈夫曼編碼與解碼實(shí)驗(yàn)報(bào)告

《哈夫曼編碼與解碼實(shí)驗(yàn)報(bào)告》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目：哈夫曼編碼與解碼學(xué)生姓名：侯清源學(xué)號(hào)：1021111118班級(jí)：102111111指導(dǎo)教師：張軍2012年6月1日15東華理工大學(xué)軟件學(xué)院軟件工程系目錄需求分析說明總體設(shè)計(jì)詳細(xì)設(shè)計(jì)實(shí)現(xiàn)部分程序測(cè)試部分實(shí)驗(yàn)總結(jié)附圖：開發(fā)環(huán)境和工程文件介紹15東華理工大學(xué)軟件學(xué)院軟件工程系1，需求分析說明A，通信線路中實(shí)現(xiàn)信息的最大傳送，利用變長(zhǎng)編碼的方式，可以有效充分利用帶寬，實(shí)現(xiàn)信息傳送前的壓縮。B，在文件保存時(shí)，利用哈夫曼編碼的方式，壓縮文件?？梢詫?shí)現(xiàn)硬盤存儲(chǔ)最大的信息量。C，實(shí)驗(yàn)?zāi)康模?，.學(xué)會(huì)使用哈夫曼進(jìn)行對(duì)文本文件的編碼與譯碼。2，通過對(duì)哈夫曼的編碼與譯

2、碼，能夠理解通信領(lǐng)域中的數(shù)據(jù)傳輸?shù)膲嚎s原理。3，通過對(duì)哈夫曼的編碼/譯碼器的研究與分析，能夠徹底的理解軟件設(shè)計(jì)的一般步驟和方法，靈活地運(yùn)用各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作，熟練地把所學(xué)地?cái)?shù)據(jù)結(jié)構(gòu)應(yīng)用地軟件開發(fā)當(dāng)中，提高軟件設(shè)計(jì)水平，增強(qiáng)程序設(shè)計(jì)能力。D，實(shí)現(xiàn)功能壓縮：實(shí)現(xiàn)對(duì)用戶輸入的字符串壓縮，并在終端顯示相應(yīng)字符對(duì)應(yīng)的頻率，編碼，編碼長(zhǎng)度，平均編碼長(zhǎng)度，字符個(gè)數(shù)。并顯示字符串編碼后的二進(jìn)制文件。解壓：實(shí)現(xiàn)對(duì)壓縮后的二進(jìn)制文件解壓，還原為原來的字符串。并顯示在終端。和用戶輸入的字符串比較。2，總體設(shè)計(jì)2,1開發(fā)環(huán)境介紹編譯器：gcc4.6.3編輯器：vim7.0附插件：ctags、t

3、aglist、autocomplpop。打開syntaxenable、syntaxon、setnumber。操作系統(tǒng)：Ubuntu12.04LTS硬件環(huán)境：Processor：Intel(R)Core?i5-2430CPU@2.40GHzVendor:AcerTravelMate4750GBusinessLaptopMemory:4G2.2系統(tǒng)框架系統(tǒng)結(jié)構(gòu)流程15東華理工大學(xué)軟件學(xué)院軟件工程系算法思想描述（文字和圖）1，首先，根據(jù)用戶輸入的字符串得到字符頻率。根據(jù)頻率得到頻率數(shù)據(jù)，對(duì)該頻率數(shù)組由棧頂?shù)綏５陀尚〉酱笈帕?，同時(shí)將從小到大順序存入優(yōu)先隊(duì)列2，構(gòu)造哈弗曼樹，過程如

4、下：從棧中取出兩個(gè)最小頻率。按照左小右大的原則。構(gòu)造哈弗曼樹。同時(shí)生成父節(jié)點(diǎn)，即頻率和。同時(shí)父節(jié)點(diǎn)入棧，重新按照由小到大的順序排列。3，重復(fù)2過程，直到棧為空。4，編碼解碼的過程編碼時(shí)，根據(jù)哈弗曼樹，左0右1，建立map>容器，右邊存儲(chǔ)字符，右邊存儲(chǔ)編碼。編碼時(shí)，從根節(jié)點(diǎn)遞歸遍歷算法編碼，左節(jié)點(diǎn)編碼時(shí)添加0，右節(jié)點(diǎn)編碼添加1解碼時(shí)，也是根據(jù)哈弗曼編碼樹，從根節(jié)點(diǎn)開始，如果碰到編碼的首部是1，往右遍歷；如果是0，往左遍歷。直到葉子節(jié)點(diǎn)，遍歷匹配字符成功，返回匹配的字符。同時(shí)回到根節(jié)點(diǎn)，重復(fù)該步驟，翻譯下一個(gè)編碼。1，詳細(xì)設(shè)計(jì)3.1，類模板

5、設(shè)計(jì)1，類模板設(shè)計(jì)資料：高永平老師給的資料：《數(shù)據(jù)結(jié)構(gòu)（STL框架）》王曉東編著，陳道蓄主審2，主要是STL編程，并利用了vectormapqueue等容器，使用了容器的迭代器iterator15東華理工大學(xué)軟件學(xué)院軟件工程系哈夫曼樹類結(jié)構(gòu)模板Hafftree類模板原型TemplateHufftree+templateHufftree(InputIteratorbegin,InputIteratorend);構(gòu)造哈夫曼樹+~Hufftree()析構(gòu)函數(shù)+t

6、emplatevectorencode(InputIteratorbegin,InputIteratorend);編碼+vectorencode(DataTypeconst&value);返回字符編碼+doubleencodelength(DataTypeconst&value);返回字符編碼長(zhǎng)度+templatevoiddecode(vectorconst&v,OutputIteratoriter);對(duì)字符串解碼-classNode;字符串節(jié)

7、點(diǎn)類-classNodeOrder;排序時(shí)用的類-Node*tree;根節(jié)點(diǎn)-typedefmap>encodemap;encodemapencodetable;編碼表Node類成員：templateNode+Frequencyfreqeuency;權(quán)或頻率+Node*leftChild;左孩子指針+unionNode*rightChild;右孩子指針DataType*data;字符域指針Template