哈夫曼編碼譯碼系統(tǒng)課程設(shè)計實驗報告(含源代碼C-C語言)

東北電力大學(xué)計算機科學(xué)與技術(shù)業(yè)綜合設(shè)計報告目錄摘要………………………..……………IIAbstract…………………II第一章課題描述…………11.1問題描述………………...1.2需求分析…………………..……………1.3程序設(shè)計目標(biāo)……………第二章設(shè)計簡介及設(shè)計方案論述…………2.1設(shè)計簡介.………………..………….2.2設(shè)計方案論述……………..……………22.3概要設(shè)計…………………..……………2第三章詳細(xì)設(shè)計…………..………………..3.1哈夫曼樹…………………..……………43.2哈夫曼算法………………..……………43.2.1基本思想……………..……….43.2.2存儲結(jié)構(gòu)……………..…………43.3哈夫曼編碼………………..……………53.4文件I/O流………………..……………63.4.1文件流………………63.4.2文件的打開與關(guān)閉………….…….73.4.3文件的讀寫………….……....73..5C語言文件處理方式……………………第四章設(shè)計結(jié)果及分析…………………..………………..4.1設(shè)計系統(tǒng)功能…………………….4.2進行系統(tǒng)測試……………..……………8總結(jié)…….…………………..…………致謝…….…………………..………….參考文獻…….……………..………….附錄主要程序代碼………..………….16-I-

東北電力大學(xué)計算機科學(xué)與技術(shù)業(yè)綜合設(shè)計報告摘

要在這個信息高速發(fā)展的時代，每時每刻都在進行著大量信息的傳遞，到處都離不開信息，它貫穿在人們?nèi)粘５纳钌a(chǎn)之中，對人們的影響日趨擴大,而利用哈夫曼編進行通信則可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。在生產(chǎn)中則可以更大可能的降低成本從而獲得更大的利潤，這也是信息時代發(fā)展的趨勢所在。本課程設(shè)計的目的是使學(xué)生學(xué)會分析待加工處理數(shù)據(jù)的特性，以便選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)以及進行相應(yīng)的算法設(shè)計。學(xué)生在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計的同時，培養(yǎng)學(xué)生的抽象思維能力、邏輯推理能力和創(chuàng)造性的思維方法，增強分析問題和解決問題的能力。此次設(shè)計的哈夫曼編碼譯碼系統(tǒng)，實現(xiàn)對給定報文的編碼和譯碼，并且任意輸入報文可以實現(xiàn)頻數(shù)的統(tǒng),建立哈夫曼樹以及編碼譯碼的功能。這是一個擁有完備功能的系統(tǒng)程序，對將所學(xué)到的知識運用到實踐中,具有很好的學(xué)習(xí)和研究價值關(guān)鍵詞：信息；通訊；編碼；譯碼；程序-II-

東北電力大學(xué)計算機科學(xué)與技術(shù)業(yè)綜合設(shè)計報告Abstractisadatethatinformationhighlydevelopmentinformationeveryleaveinformation,itthroughduringthelifeproduction,theinfluenceexpandsdaybydaythepeople,usingHuffmancarriesoncorrespondencebepossibletochannelfactortheintelligencereducescost.Maygreatlycostinproduction,obtainsabiggerprofit,isalsotheinformationagedevelopmentThiscurriculumissocietyanalyzetreatstheprocessingdatawiththeaimofthesuitablelogicalthememorystructurewellontheduringconstructionofdataandalgorithmdesign’sraisesstudent'sabstractthinkingability,logicreasoningabilityandthemethod,enhancementthequestiondesign'sHuffmancodescodesystem,realizestothetextthethedecoding,thearbitraryinputtextmayrealizethethetreeaswellthecodedecodingfunction.iscompletefunctionsystemprogram,toknowledgewilllearnutilizesinthegoodthevalue.Keywords：Information;Coding;Procedure-III-

東北電力大學(xué)計算機科學(xué)與技術(shù)業(yè)綜合設(shè)計報告第一章

課題描述1.1問題描述利用哈夫曼編碼進行通信，可以壓縮通信的數(shù)據(jù)量，提高傳輸效率，縮短信息的傳輸時間，還有一定的保密性?，F(xiàn)在要求編寫一程序模擬傳輸過程，實現(xiàn)在發(fā)送前將要發(fā)送的字符信息進行編碼，然后進行發(fā)送，接收后將傳來的數(shù)據(jù)進行譯碼，即將信息還原成發(fā)送前的字符信息。1.2需求分析在本例中設(shè)置發(fā)送者和接受者兩個功能，1.2.1發(fā)送的能①輸入待傳送的字符信息；②統(tǒng)計字符信息中出現(xiàn)的字符種類數(shù)和各字符出現(xiàn)的次數(shù)（頻率②根據(jù)字符的種類數(shù)和各自出現(xiàn)的次數(shù)建立哈夫曼樹；③利用以上哈夫曼樹求出各字符的哈夫曼編碼；④將字符信息轉(zhuǎn)換成對應(yīng)的編碼信息進行傳送。1.2.2接受的能①接收發(fā)送者傳送來的編碼信息；②利用上述哈夫曼樹對編碼信息進行翻譯，即將編碼信息還原成發(fā)送前的字符信息。從以上分析可發(fā)現(xiàn)，在本例中的主要算法有三個：（1）哈夫曼樹的建立；（2）哈夫曼編碼的生成；（3）對編碼信息的翻譯。1.3程序設(shè)目層次一編程從文件中讀取一段報文首先統(tǒng)計字符的頻度然后建立哈夫曼樹，并給出報文的編碼然后根據(jù)使用者的需要對指定文件里的任意二進制編碼進行譯碼并顯示。層次二：使用者從系統(tǒng)界面輸入字符串，統(tǒng)計從鍵盤輸入的字符串信息，然后建立哈夫曼樹，并給出報文的編碼，然后根據(jù)使用者的需要對指定文件里的或者使用者從系統(tǒng)界面輸入任意二進制編碼的進行譯碼并顯示。--

東北電力大學(xué)計算機科學(xué)與技術(shù)業(yè)綜合設(shè)計報告第二章2.1設(shè)計簡介

設(shè)計簡介及設(shè)方案論述文字處理是現(xiàn)代計算機應(yīng)用的重要領(lǐng)域。文本由字符組成，字符以某種編碼形式存儲在計算機中。每個字符的編碼可以是相等長度的，也可以是不等長度的。編碼是等長編碼。為了提高存儲和處理文本的效率，在一些計算機應(yīng)用場合，如數(shù)據(jù)通信，常采用不等長的編碼常用的字符用較少的碼位常出現(xiàn)的字符用較多的碼位編碼，從而減少文本的存儲長度。哈夫曼編碼就是用于此目的的不等長編碼方法。所以本次設(shè)計就是通過構(gòu)造哈夫曼樹來生成哈夫曼編碼，最終完成設(shè)計要求。2.2設(shè)計方案論述哈夫曼編碼/譯碼程序主要由主函數(shù)哈夫曼樹類和各種功能函數(shù)組成序運行時首先進入主函數(shù)，對各種功能函數(shù)進行調(diào)用，從而實現(xiàn)了整個程序的運行。將各種不同的函數(shù)分別包含在各自的結(jié)構(gòu)體中，使整個程序結(jié)構(gòu)更加的清晰明了，各功能相互獨立且緊密聯(lián)系，有利于編程的實現(xiàn)，同時也體現(xiàn)了面向?qū)ο笤O(shè)計語言的封裝性。在主菜單中運用了switch()函數(shù)和”語句，便于對整個程序操作和控制；對數(shù)據(jù)保存在文檔中，則運用了文件流和語言的文件處理方式，進行文件與內(nèi)存之間輸入，輸出數(shù)據(jù)。2.3概要設(shè)計2.3.1

第一部分功能的實現(xiàn)在主函數(shù)聲明HuffmanTree1類的對HuffmanNode后用HuffmanNode調(diào)用它的成員函數(shù)TranslatedCode()此函數(shù)能讀取里的字符串并統(tǒng)計然后建立哈夫曼樹并對各個字符編碼和保存相關(guān)信息。然后對象HuffmanNode再調(diào)用成員函數(shù)TranslateArtcle（）對指定文件得到的二進制編碼進行譯碼，并保存翻譯得到的信息。2

.3.1第二部分功能的實現(xiàn)獲取并保存從鍵盤輸入的字符串，并統(tǒng)計其信息。然后利用這些信息建立哈夫曼樹對各個字符進行編碼和保存相關(guān)信息。接著可以調(diào)用函數(shù)HuffmanTranslateCoding2（）對指定文件得到的二進制編碼信息進行譯碼和保存得到的翻譯信息，或者可以調(diào)用HuffmanTranslateCoding()對從系統(tǒng)頁面輸入的二進制編碼進行翻譯并保存翻譯信息--

東北電力大學(xué)計算機科學(xué)與技術(shù)業(yè)綜合設(shè)計報告第三章

詳細(xì)設(shè)計3.1夫曼樹哈夫曼樹也稱最優(yōu)二叉樹.給定一組具有確定權(quán)值的葉子結(jié)點,可以構(gòu)造出不同的二叉樹將其中帶權(quán)路徑長度最小的二叉樹稱為哈夫曼樹.其中,葉子結(jié)點的權(quán)值(weight)是對葉子結(jié)點賦予的一個有意義的數(shù)值量設(shè)二叉樹具有n個帶權(quán)值的葉子結(jié)點,從根結(jié)點到各個葉子結(jié)點的路徑長度與相應(yīng)葉子結(jié)點權(quán)值的乘積之和叫做二叉樹的帶權(quán)路徑長度(weightedpathlength),記為:Wklk,w第k葉子結(jié)點的權(quán)值l從根結(jié)點到第k個葉子結(jié)點的路徑kk長度.3.2夫曼算法基本思想根據(jù),哈夫曼的定,一棵二叉樹要使其帶權(quán)路徑長度最,必須使權(quán)值越大的葉子結(jié)點越靠近根結(jié),而權(quán)值越小的葉子結(jié)點越遠離根結(jié)點.依據(jù)這個特點便提出了哈夫曼算法,其基本思想是:(1)初始化:由給定的n個權(quán)值w,w,…,w}構(gòu)造n只有一個根結(jié)點的二叉12n樹,從而得到一個二叉樹集合F={T,T,…,T};12n(2)選取與合并:在F中選取根結(jié)點的權(quán)值最小的兩棵二叉樹分別作為左、右子樹構(gòu)造一顆新的二叉樹,這棵新二叉樹的根結(jié)點的權(quán)值為其左右子樹根結(jié)點的權(quán)值之和;(3)刪除與加入:在F中刪除作為左子樹的兩棵二叉樹,并將新建立的二叉樹加入到F中;(4)重復(fù)(2)兩步,當(dāng)集合F中只剩下一棵二叉樹時,這棵二叉樹便是哈夫曼--

東北電力大學(xué)計算機科學(xué)與技術(shù)業(yè)綜合設(shè)計報告樹.存儲結(jié)構(gòu)在由哈夫曼算法構(gòu)造的哈夫曼樹中,非葉子結(jié)點的度均為據(jù)二叉樹的性質(zhì)可知,具有n葉子結(jié)點的哈夫曼樹共有2n-1個結(jié)點,其中個非葉子結(jié)點它們是在n-1次的合并過程中生成的.了便于選取根結(jié)點權(quán)值最小的二叉樹以及合并操作,設(shè)置一個數(shù)HuffmanNode[2n-1]保存哈夫曼樹中各結(jié)點的信息數(shù)組元素的結(jié)點結(jié)構(gòu)如圖3-1所示.

weightparentlchildrchildinf3-1哈夫曼樹其中,weight:權(quán)值域,保存該結(jié)點的權(quán)值;lchild:指針域,保存該結(jié)點的左孩子結(jié)點在數(shù)組中的下標(biāo)rchild:指針域,保存該結(jié)點的右孩子結(jié)點在數(shù)組中的下標(biāo)parent:指針域,保存該結(jié)點的雙親結(jié)點在數(shù)組中的下標(biāo)Inf:存儲相關(guān)的字符信息可以用C中的結(jié)構(gòu)類型定義上述結(jié)點.structHuffmanNode{charinf;intweight;intparent;intlchild,rchild;};3.3夫曼編碼

的結(jié)點結(jié)構(gòu)哈夫曼樹可用于構(gòu)造最短的不等長編碼方案體做法如:設(shè)需要編碼的字符集合為{d,d,…,d},它們在字符串中出現(xiàn)的頻率為w,w,…,w},以d,d,…,d作為葉12n12n12n子結(jié)點,w,w,…,w作為葉子結(jié)點的權(quán)值,構(gòu)造一顆哈夫曼編碼樹,規(guī)定哈夫曼編碼樹12n的左分支代表0右分支代表1則從根結(jié)點到每個葉子結(jié)點所經(jīng)過的路徑組成的和1的序列便為該葉子結(jié)點對應(yīng)字符的編碼,稱為哈夫曼編碼HuffmanCode).--

東北電力大學(xué)計算機科學(xué)與技術(shù)業(yè)綜合設(shè)計報告在哈夫曼編碼樹,數(shù)的帶權(quán)路徑長度的含義是各個字符的碼長與其出現(xiàn)次數(shù)的乘積之和所以采用哈夫曼樹構(gòu)造的編碼是一種能使字符串的編碼總長度最短的不等長編碼.由于哈夫曼編碼樹的每個字符結(jié)點都是葉子結(jié)點,們不可能在根結(jié)點到其他字符結(jié)點的路徑,所以一個字符的哈夫曼編碼不可能是另一個字符的哈夫曼編碼的前綴,從而保證了解碼的唯一性.3.4文件I/O流文件的打開與關(guān)閉本程序中，建立流對象調(diào)用成員函數(shù)openclose進行文件的打開和關(guān)閉。成員函數(shù)回非零值或者true，表示流對象已經(jīng)成功關(guān)聯(lián)到磁盤文件，否則返回0或者false表示該流對象沒有關(guān)聯(lián)到文件。成員函數(shù)close首先刷新緩沖區(qū)，把所有等待輸出的內(nèi)容寫到磁盤文件中，然后關(guān)閉磁盤文件，并斷開磁盤文件與文件緩沖區(qū)的聯(lián)系。文件的讀寫由于ifstream、ofstream、fstream分別派生自、iostream，因此定義于類istream、ostream、iostream中的大部分共有成員函數(shù)。流插入運算符函數(shù)operator<<和流提取運算符函數(shù)put/get/getline函數(shù)主要用于格式化I/O。write/read函數(shù)則常用于無格式化I/O。3.5言文件處理式體結(jié)構(gòu)體FILE類型可以用來定義文件型指針變量，可以使指針指向某一個文件的結(jié)構(gòu)體變量，從而通過該結(jié)構(gòu)體變量中的文件信息能夠訪問該文件。例如：FILE*fp;文（（fcloseFILE*fp;fp=fopen(文件名，使用文件方式)；fclose（文件指針例如：--

東北電力大學(xué)計算機科學(xué)與技術(shù)業(yè)綜合設(shè)計報告FILE*fp;fp=fopen(“al”,”w”);fclose(fp);fputc把一個字符寫到磁盤文件上去，其一般調(diào)用形式為putc(ch,fp);其中ch是要輸出的字符。fp是文件指針變量。fget函數(shù)從指定的文件讀入一個字符，該文件必須是以讀或讀寫方式打開的。fgetc數(shù)的調(diào)用形式ch=fgetc(fp);其中ch是要輸出的字符。fp是文件指針變量。3.6程序功能的詳細(xì)計詳?shù)谒恼?.1計系統(tǒng)功能

設(shè)計結(jié)果及分層次一編程從文件中讀取一段報文首先統(tǒng)計字符的頻度然后建立哈夫曼樹，并給出報文的編碼然后根使用者的需要對指定文件里的任意二進制編碼進行譯碼并顯示。層次二：使用者從系統(tǒng)界面輸入字符串，統(tǒng)計從鍵盤輸入的字符串信息，然后建立哈夫曼樹，并給出報文的編碼，然后根據(jù)使用者的需要對指定文件里的或者使用者從系統(tǒng)界面輸入任意二進制編碼的進行譯碼并顯示。--

東北電力大學(xué)計算機科學(xué)與技術(shù)業(yè)綜合設(shè)計報告4.2行系統(tǒng)測試圖系統(tǒng)界面--

東北電力大學(xué)計算機科學(xué)與技術(shù)業(yè)綜合設(shè)計報告圖從文件中提取字符串并進行字符的統(tǒng)--

東北電力大學(xué)計算機科學(xué)與技術(shù)業(yè)綜合設(shè)計報告圖4-3A操作的字符串的哈夫曼編碼--

東北電力大學(xué)計算機科學(xué)與技術(shù)業(yè)綜合設(shè)計報告圖B作對Acode.txt里的二進制編碼進行譯碼和保存翻信息--

東北電力大學(xué)計算機科學(xué)與技術(shù)業(yè)綜合設(shè)計報告圖C作從鍵盤輸入字符串并統(tǒng)計、編碼和保存--

東北電力大學(xué)計算機科學(xué)與技術(shù)業(yè)綜合設(shè)計報告圖作對里的二進制編碼進行譯再保存保存圖4-6E作對在系統(tǒng)頁面輸入的二進制編碼進行譯碼--

東北電力大學(xué)計算機科學(xué)與技術(shù)業(yè)綜合設(shè)計報告圖作退出系統(tǒng)--

東北電力大學(xué)計算機科學(xué)與技術(shù)業(yè)綜合設(shè)計報告圖以上操作得到的相關(guān)數(shù)據(jù)圖退出系統(tǒng)總結(jié)通過本次課程設(shè)計使我對哈夫曼樹及哈夫曼編碼有了更深刻的理解同時對CC++的編程以及算法的實現(xiàn)產(chǎn)生了比較大的興趣。還學(xué)到了許多在處理程序時的技巧和方法，這都對以后的學(xué)習(xí)大有裨益，以及感受到在編程設(shè)計中團隊合作精神的重要性。在這次程序設(shè)計中，我覺得重要的一點，那就是不要人云亦云，要有自己的主見，不管別人如何，一定要有自己的思想，并且始終不改變的去堅持，縱然，可能會遇到很多難以解決的困難，都要自始到終，相信自己能把這個程序做得出來。當(dāng)自己最終在自己的努力下完成任務(wù)的時候，那就會有更多屬于自己的收獲，包括成功的喜悅以及程序中體現(xiàn)的思想。--

東北電力大學(xué)計算機科學(xué)與技術(shù)業(yè)綜合設(shè)計報告其次是我認(rèn)為調(diào)試功能是整個編寫程序過程中很重要的一個環(huán)節(jié)通過此次實驗我對調(diào)試有了更加深刻的理解，懂得怎么樣去調(diào)試程序，如何發(fā)現(xiàn)錯誤，如何更高效的改正，最終能把程序?qū)崿F(xiàn)。致

謝在本次課程設(shè)計的整個過程中別感謝自始至終給我提供幫助和指導(dǎo)X老師，是他耐心的指導(dǎo)才使得本次設(shè)計得以順得完成，同時，也要感謝小組成員的不懈努力和互相配合，在此還要特別感謝為我們提供良好上機環(huán)境的學(xué)校.如果沒有以上老師，同學(xué)和學(xué)校的幫助和支持，本次設(shè)計實難完.再次感謝老師的精心輔導(dǎo)和同學(xué)的相互幫助，使我們順利完成此次設(shè)計以及為學(xué)習(xí)以后的科目打下良好的基礎(chǔ)--

東北電力大學(xué)計算機科學(xué)與技術(shù)業(yè)綜合設(shè)計報告參考文獻【1語程序設(shè)（第三版）譚強清大學(xué)出版社2009.10【2】C++語言程序設(shè)計（第四版鄭莉董淵何江舟清華大學(xué)出版社【3】數(shù)據(jù)結(jié)（C版朝陽郭曉利王曉慧孫鴻飛中國電力出版社2007.8--

東北電力大學(xué)計算機科學(xué)與技術(shù)業(yè)綜合設(shè)計報告附錄主要程序代碼:--

東北電力大學(xué)計算機科學(xué)與技術(shù)業(yè)綜合設(shè)計報告--

東北電力大學(xué)計算機科學(xué)與技術(shù)業(yè)綜合設(shè)計報告