哈夫曼編碼譯碼系統(tǒng)課程設(shè)計(jì)實(shí)驗(yàn)報(bào)告(含源代碼C_C語(yǔ)言)

1、東北電力大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)綜合設(shè)計(jì)報(bào)告目錄摘要 iiabstract ii第一章課題描述11.1問(wèn)題描述1需求分析11.3程序設(shè)計(jì)目標(biāo)第二章設(shè)計(jì)簡(jiǎn)介及設(shè)計(jì)方案論述22. 1設(shè)計(jì)簡(jiǎn)介22.2 設(shè)計(jì)方案論述2> 3概要設(shè)計(jì)2第三章詳細(xì)設(shè)計(jì)43.1哈夫曼樹(shù)43.2哈夫曼算法4> 2. 1 基本思想43.2.2存儲(chǔ)結(jié)構(gòu)43.3哈夫曼編碼53.4文件i/o流63.4.1文件流63.4.2文件的打開(kāi)與關(guān)閉73.4.3文件的讀寫(xiě)73. . 5 c語(yǔ)言文件處理方式第四章設(shè)計(jì)結(jié)果及分析84.1設(shè)計(jì)系統(tǒng)功能84.2進(jìn)行系統(tǒng)測(cè)試8*吉13sc i射14參考文獻(xiàn)15附錄主要程序代碼16摘要在這個(gè)信息

2、高速發(fā)展的時(shí)代，每時(shí)每刻都在進(jìn)行著大量信息的傳遞，到處都離不開(kāi) 信息，它貫穿在人們?nèi)粘５纳钌a(chǎn)之中，對(duì)人們的影響日趨擴(kuò)大，而利用哈夫曼編碼 進(jìn)行通信則可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。在生產(chǎn)中則 可以更大可能的降低成本從而獲得更大的利潤(rùn)，這也是信息時(shí)代發(fā)展的趨勢(shì)所在。本課 程設(shè)計(jì)的0的是使學(xué)生學(xué)會(huì)分析待加工處理數(shù)據(jù)的特性，以便選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存 儲(chǔ)結(jié)構(gòu)以及進(jìn)行相應(yīng)的算法設(shè)計(jì)。學(xué)生在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)的同時(shí)，培養(yǎng)學(xué)生的 抽象思維能力、邏輯推理能力和創(chuàng)造性的思維方法，增強(qiáng)分析問(wèn)題和解決問(wèn)題的能力。 此次設(shè)計(jì)的哈夫曼編碼譯碼系統(tǒng)，實(shí)現(xiàn)對(duì)給定報(bào)文的編碼和譯碼，并且任意輸

3、入報(bào)文可 以實(shí)現(xiàn)頻數(shù)的統(tǒng)計(jì)，建立哈夫曼樹(shù)以及編碼譯碼的功能。這是一個(gè)擁有完備功能的系統(tǒng) 程序，對(duì)將所學(xué)到的知識(shí)運(yùn)用到實(shí)踐中，具有很好的學(xué)習(xí)和研究?jī)r(jià)值.關(guān)鍵詞：信息；通訊；編碼；譯碼；程序abstractthis is a date that information speeding highly development and transmit information every time，everywhere cannot leave the information, it passes through during the people daily life production，the

4、influence expands day by day to the people，but codes using huffman carries on the correspondence to be possible to raise the channel use factor greatly， reduces the intelligence transmission time, reduces the transmission cost. may greatly possible reduce the cost in the production，thus obtains a bi

5、gger profit，this is also the information age development tendency is. this curriculum projects goal is makes the student academic society to analyze treats the processing data the characteristic，with the aim of choosing the suitable logical organization，the memory structure as well as carries on the

6、 corresponding algorithm design. the student during the study construction of data and algorithm designs raises student's abstract thinking ability，logic reasoning ability and the creative thought method，the enhancement analysis question and solves the question ability. this design's huffman

7、 codes the code recognition system，realizes to assigns the text the code and the decoding，and the arbitrary input text may realize the frequency statistics，establishes the huffman tree as well as the code decoding function. this is one has the complete function system program, to the knowledge which

8、 will learn utilizes in the practice, has the very good study and the research value.keywords: information; communication; coding; decoding; procedure東北電力大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)綜合設(shè)計(jì)報(bào)告第一章課題描述1.1問(wèn)題描述利用哈夫曼編碼進(jìn)行通信，可以壓縮通信的數(shù)據(jù)量，提高傳輸效率，縮短信息的傳 輸時(shí)間，還有一定的保密性?，F(xiàn)在要求編寫(xiě)一程序模擬傳輸過(guò)程，實(shí)現(xiàn)在發(fā)送前將要發(fā) 送的字符信息進(jìn)行編碼，然后進(jìn)行發(fā)送，接收后將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼，即將信息還原

9、 成發(fā)送前的字符信息。1.2需求分析在本例中設(shè)置發(fā)送者和接受者兩個(gè)功能，1.2.1發(fā)送者的功能：輸入待傳送的字符信息；統(tǒng)計(jì)字符信息屮出現(xiàn)的字符種類(lèi)數(shù)和各字符出現(xiàn)的次數(shù)(頻率)；根據(jù)字符的種類(lèi)數(shù)和各自出現(xiàn)的次數(shù)建立哈夫曼樹(shù)；利用以上哈夫曼樹(shù)求出各字符的哈夫曼編碼；將字符信息轉(zhuǎn)換成對(duì)應(yīng)的編碼信息進(jìn)行傳送。1.2. 2接受者的功能：接收發(fā)送者傳送來(lái)的編碼信息；利用上述哈夫曼樹(shù)對(duì)編碼信息進(jìn)行翻譯，即將編碼信息還原成發(fā)送前的字符信息。 從以上分析可發(fā)現(xiàn)，在木例中的主要算法有三個(gè)： 哈夫曼樹(shù)的建立； 哈夫曼編碼的生成； 對(duì)編碼信息的翻譯。1.3程序設(shè)計(jì)目標(biāo)層次一：編程從文件中讀取一段報(bào)文，首先統(tǒng)計(jì)字符的頻

10、度，然后建立哈夫曼樹(shù)， 并給出報(bào)文的編碼，然后根據(jù)使用者的需要對(duì)指定文件里的任意二進(jìn)制編碼進(jìn)行譯碼并 顯小。層次二：使用者從系統(tǒng)界面輸入字符串，統(tǒng)計(jì)從鍵盤(pán)輸入的字符串信息，然后建 立哈夫曼樹(shù)，并給出報(bào)文的編碼，然后根據(jù)使用者的需要對(duì)指定文件里的或者使用者從 系統(tǒng)界面輸入任意二進(jìn)制編碼的進(jìn)行譯碼并顯示。第二章設(shè)計(jì)簡(jiǎn)介及設(shè)計(jì)方案論述2. 1設(shè)計(jì)簡(jiǎn)介文字處理是現(xiàn)代計(jì)算機(jī)應(yīng)用的重要領(lǐng)域。文本由字符組成，字符以某種編碼形式存 儲(chǔ)在計(jì)算機(jī)中。每個(gè)字符的編碼可以是相等長(zhǎng)度的，也可以是不等長(zhǎng)度的。ascii編碼 是等長(zhǎng)編碼。為了提高存儲(chǔ)和處理文本的效率，在一些計(jì)算機(jī)應(yīng)用場(chǎng)合，如數(shù)據(jù)通信， 常采用不等長(zhǎng)的編碼，

11、對(duì)常用的字符用較少的碼位，不常出現(xiàn)的字符用較多的碼位編碼, 從而減少文本的存儲(chǔ)長(zhǎng)度。哈夫曼編碼就是用于此fi的的不等長(zhǎng)編碼方法。所以本次設(shè) 計(jì)就是通過(guò)構(gòu)造哈夫曼樹(shù)來(lái)生成哈夫曼編碼，最終完成設(shè)計(jì)要求。2.2設(shè)計(jì)方案論述哈夫曼編碼/譯碼程序主要由主函數(shù)、哈夫曼樹(shù)類(lèi)和各種功能函數(shù)組成，程序運(yùn)行吋 首先進(jìn)入主函數(shù)，對(duì)各種功能函數(shù)進(jìn)行調(diào)用，從而實(shí)現(xiàn)了整個(gè)程序的運(yùn)行。將各種不同 的函數(shù)分別包含在各自的結(jié)構(gòu)體中，使整個(gè)程序結(jié)構(gòu)更加的清晰明了，各功能和互獨(dú)立 且緊密聯(lián)系，有利于編程的實(shí)現(xiàn)，同時(shí)也體現(xiàn)了面向?qū)ο笤O(shè)計(jì)語(yǔ)言的封裝性。在主菜單 屮運(yùn)用了 switcho函數(shù)和“case”語(yǔ)句，便于對(duì)整個(gè)程序操作和控制；

12、對(duì)數(shù)據(jù)保存在文檔 中，則運(yùn)用了文件i/o流和c語(yǔ)言的文件處理方式，進(jìn)行文件與內(nèi)存之間輸入，輸出數(shù) 據(jù)。2. 3概要設(shè)計(jì)2.3.1第一部分功能的實(shí)現(xiàn)在主函數(shù)聲明huffmantreel類(lèi)的對(duì)象huffmannode,然后用huffmannode調(diào)用它的 成員函數(shù)translatedcodeo，此函數(shù)能讀取adata. txt里的字符串并統(tǒng)計(jì)，然后建立哈 夫曼樹(shù)并對(duì)各個(gè)字符編碼和保存相關(guān)信息。然后對(duì)象huffmannode再調(diào)用成員函數(shù) translateartcle ()對(duì)指定文件得到的二進(jìn)制編碼進(jìn)行譯碼，并保存翻譯得到的信息。2.3. 1第二部分功能的實(shí)現(xiàn)獲取并保存從鍵盤(pán)輸入的字符串，并統(tǒng)計(jì)其

13、信息。然后利用這些信息建立哈夫曼樹(shù)對(duì) 各個(gè)字符進(jìn)行編碼和保存相關(guān)信息。接著可以調(diào)用函數(shù)huffmantranslatecoding2 () 對(duì)指定文件得到的二進(jìn)制編碼信息進(jìn)行譯碼和保存得到的翻譯信息，或者可以調(diào)用 huffmantranslatecodingo對(duì)從系統(tǒng)頁(yè)而輸入的二進(jìn)制編碼進(jìn)行翻譯并保存翻譯信息第三章詳細(xì)設(shè)計(jì)3.1哈夫曼樹(shù)哈夫曼樹(shù)也稱(chēng)最優(yōu)二叉樹(shù).給定一組具有確定權(quán)值的葉子結(jié)點(diǎn)，可以構(gòu)造出不同的 二叉樹(shù)，將其中帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)稱(chēng)為哈夫曼樹(shù).其中，葉子結(jié)點(diǎn)的權(quán)值 (weight)是對(duì)葉子結(jié)點(diǎn)賦予的一個(gè)有意義的數(shù)值量.設(shè)二叉樹(shù)具有n個(gè)帶權(quán)值的葉子結(jié) 點(diǎn)，從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的

14、路徑長(zhǎng)度與相應(yīng)葉子結(jié)點(diǎn)權(quán)值的乘積之和叫做二叉樹(shù)的 帶權(quán)路徑長(zhǎng)度(weighted path length),記為：wpl= y wklk, w為第k個(gè)葉子結(jié)點(diǎn)的權(quán)值，1、為從根結(jié)點(diǎn)到第k個(gè)葉子結(jié)點(diǎn)的路徑侖=1長(zhǎng)度.3.2哈夫曼算法3. 2. 1基本思想根據(jù),哈夫曼的定義,一棵二叉樹(shù)要使其帶權(quán)路徑長(zhǎng)度最小，必須使權(quán)值越大的葉子 結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn).依據(jù)這個(gè)特點(diǎn)便提出了哈夫 曼算法，其基本思想是：初始化：由給定的n個(gè)權(quán)值wb w2，wj構(gòu)造n棵只有一個(gè)根結(jié)點(diǎn)的二叉 樹(shù)，從而得到一個(gè)二叉樹(shù)集合f= t, t2，,tj ;選取與合并:在f中選取根結(jié)點(diǎn)的權(quán)值最小的兩棵二叉

15、樹(shù)分別作為左、右子 樹(shù)構(gòu)造一顆新的二叉樹(shù)，這棵新二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)的權(quán)值 之和；刪除與加入:在f中刪除作為左、右子樹(shù)的兩棵二叉樹(shù)，并將新建立的二叉樹(shù) 加入到f中；重復(fù)(2)、(3)兩步，當(dāng)集合f中只剩下一棵二叉樹(shù)吋，這棵二叉樹(shù)便是哈夫曼樹(shù).3. 2.2存儲(chǔ)結(jié)構(gòu)weightparentlchildrchildnf在由哈夫曼算法構(gòu)造的哈夫曼樹(shù)屮，非葉子結(jié)點(diǎn)的度均為2,根據(jù)二叉樹(shù)的性質(zhì)可知， 具有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)共冇2n-l個(gè)結(jié)點(diǎn),其中冇n-1個(gè)非葉子結(jié)點(diǎn)，它們是在n_l 次的合并過(guò)程中生成的.為了便于選取根結(jié)點(diǎn)權(quán)值最小的二叉樹(shù)以及合并操作，設(shè)置一 個(gè)數(shù)組huffmann

16、ode2n-l保存哈夫曼樹(shù)中各結(jié)點(diǎn)的信息,數(shù)組元素的結(jié)點(diǎn)結(jié)構(gòu)如圖3-1 所示.的結(jié)點(diǎn)結(jié)構(gòu)圖3-1哈夫曼樹(shù) 其中，weight:權(quán)值域，保存該結(jié)點(diǎn)的權(quán)值；lchild:指針域，保存該錯(cuò)點(diǎn)的左孩子錯(cuò)點(diǎn)在數(shù)組中的下標(biāo) rchild:指針域，保存該結(jié)點(diǎn)的右孩子結(jié)點(diǎn)在數(shù)組屮的不標(biāo) p a r e n t:指針域，保存該結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中的下標(biāo). inf:存儲(chǔ)相關(guān)的字符信息可以用c中的結(jié)構(gòu)類(lèi)型定義上述結(jié)點(diǎn).struct huffmannodechar inf;int weight; int parent; int lchild, rchild;3.3哈夫曼編碼哈夫曼樹(shù)可用于構(gòu)造最短的不等長(zhǎng)編碼方案，具

17、體做法如下：設(shè)需要編碼的字符集 合為山，d2，d丄它們?cè)谧址谐霈F(xiàn)的頻率為wl，w丄以db d2，dn作為葉 子結(jié)點(diǎn)，wb %，作為葉子結(jié)點(diǎn)的權(quán)值，構(gòu)造一顆哈夫曼編碼樹(shù)，規(guī)定哈夫曼編碼樹(shù) 的左分支代表0,右分支代表1，則從根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)所經(jīng)過(guò)的路徑組成的0和1 的序列便為該葉子結(jié)點(diǎn)對(duì)應(yīng)字符的編碼，稱(chēng)為哈夫曼編碼(huffman code).在哈夫曼編碼樹(shù)中，數(shù)的帶權(quán)路徑長(zhǎng)度的含義是各個(gè)字符的碼長(zhǎng)與其出現(xiàn)次數(shù)的乘 積之和，所以釆用哈夫曼樹(shù)構(gòu)造的編碼是一種能使字符串的編碼總長(zhǎng)度最短的不等長(zhǎng)編 碼.由于哈夫曼編碼樹(shù)的每個(gè)字符結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，它們不可能在根結(jié)點(diǎn)到其他字符 結(jié)點(diǎn)的路徑上，所以一

18、個(gè)字符的哈夫曼編碼不可能是另一個(gè)字符的哈夫曼編碼的前綴, 從而保證了解碼的唯一性.i c+文件i/o流3.4.1文件的打開(kāi)與關(guān)閉本程序中，建立流對(duì)象調(diào)用成員函數(shù)open和close進(jìn)行文件的打開(kāi)和關(guān)閉。成員函數(shù)open返回非零值或者true,表示流對(duì)象己經(jīng)成功關(guān)聯(lián)到磁盤(pán)文件，否則 返回0或者false表示該流對(duì)象沒(méi)有關(guān)聯(lián)到文件。成員函數(shù)close首先刷新緩沖區(qū)，把所冇等待輸出的內(nèi)容寫(xiě)到磁盤(pán)文件中，然后關(guān) 閉磁盤(pán)文件，并斷開(kāi)磁盤(pán)文件與文件緩沖區(qū)的聯(lián)系。3.4.2文件的讀寫(xiě)由于 ifstream、ofstream、fstream 分別派生自 istream、ostream、iostream,因 此

19、定義于類(lèi)istream、ostream、iostream中的大部分共有成員函數(shù)。流插入運(yùn)算符函數(shù)operator和流提取運(yùn)算符函數(shù)operator、put/get/getline 函數(shù)主要用于格式化i/o。write/ read函數(shù)則常用于無(wú)格式化i/o。ii c語(yǔ)言文件處理方式3.5. 1結(jié)構(gòu)體file結(jié)構(gòu)體file類(lèi)型可以用來(lái)定義文件型指針變量，可以使指針指向某一個(gè)文件的結(jié)構(gòu)體 變量，從而通過(guò)該結(jié)構(gòu)體變量中的文件信息能夠訪(fǎng)問(wèn)該文件。例如：file *fp;3.5.2文件的打開(kāi)（fopen函數(shù)）和文件的打開(kāi)（fclose函數(shù)）file *fp;fp= fopen （文件名，使用文件方式）；

20、fclose （文件指針）；例如：file *fp;fp=fopcn( “al”，” w”)； fclose(fp);3.5.3文件的讀寫(xiě)fputc函數(shù)把一個(gè)字符寫(xiě)到磁盤(pán)文件上去，其一般調(diào)用形式為 putc (ch, fp);其中ch是要輸出的字符。fp是文件指針變量。fgct函數(shù)從指定的文件讀入一個(gè)字符，該文件必須是以讀或讀寫(xiě)方式打開(kāi)的。 fgetc函數(shù)的調(diào)用形式 ch=fgetc(fp);其中ch是要輸出的字符。fp是文件指針變量。3.6程序功能的詳細(xì)設(shè)計(jì)請(qǐng)看附錄的源程序的詳細(xì)清單第四章設(shè)計(jì)結(jié)果及分析4.1設(shè)計(jì)系統(tǒng)功能層次一：編程從文件中讀取一段報(bào)文，首先統(tǒng)計(jì)字符的頻度，然后建立哈夫曼樹(shù)，

21、 并給出報(bào)文的編碼，然后根據(jù)使用者的需要對(duì)指定文件里的任意二進(jìn)制編碼進(jìn)行譯碼并 顯示。層次二：使用者從系統(tǒng)界面輸入字符申，統(tǒng)計(jì)從鍵盤(pán)輸入的字符申信息，然后建 立哈夫曼樹(shù)，并給出報(bào)文的編碼，然后根據(jù)使用者的需要對(duì)指定文件里的或者使用者從 系統(tǒng)界面輸入任意二進(jìn)制編碼的進(jìn)行譯碼并顯示。4.2進(jìn)行系統(tǒng)測(cè)試c *c: docu>ents and set t ingsad>inist r at or 桌面29號(hào)29號(hào)早上m)ebug29號(hào),huffmancode and huffnantranslate systemkkkkkkkxmmmrtf老暈編碼/譯碼系統(tǒng)* 欠仰 f申甲 系、東北電力大

22、學(xué):信:g工崔學(xué)齡計(jì)機(jī)附3班興趣小組 制作人：范輝強(qiáng)（組長(zhǎng)）李哲周興宇職字符串，然后對(duì)提罨昀.的一支在本系養(yǎng)中婪可以進(jìn)行如下操作: 第一部分勒能：bxt lkacode.txta :第二部分功能：c :對(duì)您輸入的d:對(duì)bcode-txte :對(duì)您輸入的二進(jìn)制編碼迸行譯碼 第三部分功能：f :退出本系統(tǒng)溫馨提示：4灘歡矚藉心”文本繼的 b在a后運(yùn)行2：llf3.b與a是5.譯碼d/copyright by fanfan*請(qǐng)輸入您要進(jìn)行的操作（a/b/c/d/e/f（不e分大小寫(xiě):圖4-1系統(tǒng)界面y> *'*w> *w> *w> *w> *w> *w&g

23、t; *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w&

24、gt; *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> *w> 障輸入您要迸行的操作（a/b/c/d/e/fx不e分大小寫(xiě):a >"w* "w* "w* "w* "w* "w* "w* "w*

25、 "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* &q

26、uot;w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "w* "

27、;w* "w* "w* *文件中提職的文章字符串是:ueleone to china!字符串中字符種類(lèi)有14種圖4-2從文件中提取字符串并進(jìn)行字符的統(tǒng)計(jì)累風(fēng)風(fēng)風(fēng)只mmm*.b個(gè)字符對(duì)應(yīng)的哈夫曼編碼是1110110111111111000110010001000101110100101010001110110文的編碼為：1110110111111111000110011100001000001000101110100101010001110110 報(bào)文的編碼已經(jīng)保存在a code .txt中*晴輸入您要進(jìn)行的操作（a/b/c/d/e/fx不e分大小寫(xiě):圖4-3a操作的字符串的

28、哈夫曼編碼|請(qǐng)輸入您要迸行的操作(a/b/c/d/e/f不區(qū)分大小寫(xiě)：* 城真ssswii?welcome to china?(碼的結(jié)果已徑保存到。<1&七8-力*1；中圖4-3 b操作對(duì)acode.txt里的二進(jìn)制編碼進(jìn)行譯碼和保存翻譯信息docu>ents and sett ingsad>inistrator桌面29號(hào)29號(hào)早上debug29障輸入您要進(jìn)行的操作（a/b/c/d/e/f不區(qū)分大小寫(xiě): c,sass;sk¥$7kkkkkkkkkkkkkkkkkkkkkkkkkkwhovi do you do?tthow do you do?k入的數(shù)據(jù)己經(jīng)保

29、存在“cdata.txt ”中字符串中共含有字符14個(gè)rxrvrvrvrvrvrvrv現(xiàn)現(xiàn)現(xiàn)現(xiàn)現(xiàn)現(xiàn)現(xiàn)現(xiàn) 出出出出出出出出字芋字字字字字字字符串中字符種類(lèi)有8種您輸入的字符串編碼為：1010010011001001101100101001110111010100110013001011001010011101000字符串的二進(jìn)制編碼己經(jīng)保存在“ccode.txt ”中苔字符對(duì)應(yīng)的編碼為:h： 101001 b： 0011kt: 001001:1011d： 00101l： 10101u： 001000 p： 101000請(qǐng)輸入您要進(jìn)行的操作（a/b/c/d/e/f不區(qū)分大小寫(xiě):圖4-4 c操作從鍵

30、盤(pán)輸入字符串并統(tǒng)計(jì)、編碼和保存圖4-5d操作對(duì)ccode.txt里的二進(jìn)制編碼進(jìn)行譯碼再保存保存docu>ents and settingsad>inistrator桌面29號(hào)29號(hào)早上debug29號(hào),xxxm(xxxxxxxxx請(qǐng)輸入您要迸行的操作（a/b/c/d/e/f不e分大小寫(xiě)： exxxxxxxxx請(qǐng)您輸入您要編譯的二迸制編碼：101001001100100110110010110101001000101000 譯碼翻譯懂到的文葶已保存在“ctransdata.txt ”中 譯碼翻譯禧奐的文輋為:h。dvu?xxxxxxxx請(qǐng)輸入您要迸行的操作（a/b/c/d/e/f不

31、e分大小寫(xiě):圖4-6e操作對(duì)在系統(tǒng)頁(yè)而輸入的二進(jìn)制編碼進(jìn)行譯碼圖4-7f操作退出系統(tǒng)co 回 22 29號(hào)29號(hào)呈上30文件(f)賴(lài)(e)韓(v)組is 包含到庫(kù)中工具co幫助(h)共享 刻錄新敕件夾 31a庫(kù)*4家庭組d，計(jì)算機(jī)本腿盤(pán)(o) tools (d:) data (e:) backup (f:)網(wǎng)絡(luò)win-nel2tiv8名稱(chēng)慘改日期題0 29號(hào)早上調(diào)，游束.exe2010/12/29 22:34口 acode.txt2010/12/30 7:31義本a檔議 adata.txt2010/12/30 7:29義本義檔、_, atransdata.txt2010/12/30 7:31義

32、本義桂bdata.txt2010/12/30 7:34義本義桂瞳 ccode.txt2010/12/30 7:34文本義檔1 ctransdata.txt2010/12/30 7:36文本義檔匕transcdata2.txt2010/12/30 7:35義本義rrr8個(gè)對(duì)象«k-war圖4-8以上操作得到的相關(guān)數(shù)據(jù)圖4-8退出系統(tǒng)巳 幺士 心 亡口通過(guò)本次課程設(shè)計(jì)使我對(duì)哈夫曼樹(shù)及哈夫曼編碼有了更深刻的理解，同時(shí)對(duì)c，c+ 的編程以及算法的實(shí)現(xiàn)產(chǎn)生了比較大的興趣。還學(xué)到了許多在處理程序時(shí)的技巧和方 法，這都對(duì)以后的學(xué)習(xí)大有裨益，以及感受到在編程設(shè)計(jì)屮團(tuán)隊(duì)合作精神的重要性。在這次程序設(shè)計(jì)

33、中，我覺(jué)得重要的一點(diǎn)，那就是不要人云亦云，要有自己的主見(jiàn)， 不管別人如何，一定要有自己的思想，并且始終不改變的去堅(jiān)持，縱然，可能會(huì)遇到很 多難以解決的困難，都要自始到終，相信自己能把這個(gè)程序做得出來(lái)。當(dāng)自己最終在自 己的努力下完成任務(wù)的時(shí)候，那就會(huì)有更多屬于自己的收獲，包括成功的喜悅以及程序 屮體現(xiàn)的思想。其次是我認(rèn)為調(diào)試功能是整個(gè)編寫(xiě)程序過(guò)程中很重要的一個(gè)環(huán)節(jié)。通過(guò)此次實(shí)驗(yàn)我 對(duì)調(diào)試有了更加深刻的理解，懂得怎么樣去調(diào)試程序，如何發(fā)現(xiàn)錯(cuò)誤，如何更高效的改 正，最終能把程序?qū)崿F(xiàn)。致謝在本次課程設(shè)計(jì)的整個(gè)過(guò)程中，要特別感謝自始至終給我提供幫助和指導(dǎo)的x老師, 是他耐心的指導(dǎo)才使得木次設(shè)計(jì)得以順得完

34、成，同時(shí)，也要感謝小組成員的不懈努力和 互和配合，在此還要特別感謝為我們提供良好上機(jī)環(huán)境的學(xué)校.如果沒(méi)有以上老師，同 學(xué)和學(xué)校的幫助和支持，本次設(shè)計(jì)實(shí)難完成.再次感謝老師的精心輔導(dǎo)和同學(xué)的相互幫 助，使我們順利完成此次設(shè)計(jì)以及為學(xué)習(xí)以后的科良好的基礎(chǔ).參考文獻(xiàn)【1】c語(yǔ)言程序設(shè)計(jì)（第三版）譚浩強(qiáng)清華大學(xué)出版社2009.10【2】c+語(yǔ)言程序設(shè)計(jì)（第四版）。鄭莉董淵何江舟清華大學(xué)出版社2010. 7【3】數(shù)據(jù)結(jié)構(gòu)（c版）。曲朝陽(yáng)郭曉利王曉慧孫鴻飛中國(guó)電力出版社2007.8附錄主要程序代碼：/huffmancodel.h#ifndef huffmamcode h#define huffmamcod

35、e h#include< i ostream#include<fstream>using namespace stcl;struct huffmannode/定義哈夫曼樹(shù)各結(jié)點(diǎn)int weight;int parent;int lchild,rchild;int flag;class huffmancodel/哈夫曼編碼類(lèi)public:char info100;int start;char leaf;；class huffmantreel/建立哈夫曼樹(shù)類(lèi)private:huffmannode *node;public:int f;huffmancodel *hf;huffma

36、ntreel();huffmantreel0; void trans1atedcode0;void codehuf(huffmannode a口，huffmancodel b, int n); void createhfmtree(char str, int m, int n);void transcode(huffmancodel b, int n); void translateartcle(huffmancodel b, int n);；#cndif /hueemamcode_hhuffmancode. cppinclude "iostreant#include<stdi

37、o. h>include "math, h"include stdlib. h#includehuffmancodel. h"#include<string>using namespace std;define maxdata 10000 /最長(zhǎng)字符串ftdefine maxsize 150/最多子葉數(shù)/第一部分功能(w)實(shí)現(xiàn)的代碼$huffmantreel:huffmantreol() node=null; /將樹(shù)結(jié)點(diǎn)初始化為空huffmantreel:"huffmantreel0 delete node; /釋放結(jié)點(diǎn)空間void h

38、uffmantreel:createhfmtree(char str, int m, int n)/建立哈夫曼樹(shù) int i, j, ml, m2, xl, x2;huffmannode hfmnodenew huffmannode;huffmancodel *hfmcode=new huffmancodeln; for (i=0;i<2*nl;i+)hfmnodei. weight=0;hfmnodei. parent=0;hfmnodei. flag=0;hfmnodei. lchid=-l;hfmnodeei. rchild=-l;for (i=0;in;i+)hfmnodei.

39、weight=mi ; llfmcode i . leaf=str i ;for(i=0;i<n-l;i+)ml=m2=32767; xl=x2=0;for(j=0;j<n+i;j+)if(hfmnodeej. weight<=ml&&hfmnodej. flag=0)m2=ml; x2=xl;ml=hfmnodej. weight; xl=j；else if(hfmnodej. weight<=m2&&hfmnodej, flag=0)m2=hfmnodej. weight; x2=j;hfmnodex1. parent=n+i;hfm

40、nodex2. parent=n+i;hfmnodexl. flag=l;hfmnodex2. flag=l;hfmnoden+i. weight=hfmnodexl. weight+hfmnodex2. weight;hfmnoden+i. lchild=xl;hfmnoden+i. rchild=x2;codelluf (hfmnode, llfmcode, n);transcode(hfmcode, n);/trans 1ateartc1e(hfmcode, n); hf=hfmcode; f=n;void huffmantreel: codelluf (huff mannode a,

41、huffmancodel b,int n) /對(duì)哈夫曼樹(shù)進(jìn)行編碼 huffmancodel hfd; int c, p;for(int i=0;in;i+)hfd. start=n-1; c=i;p=ac. parent; while (p!=0)if (ap. lchildc)hfd. infohfd. start='o ；elsehfd. info hfd. start= 1 ；hfd. start; c=p;p=ac. parent;printf(%c :，bi. leaf); for (int j=hfd. start+1;j<n;j+)bi. infoj=hfd. in

42、foj; printf("%c，hfd. tnfoj);printf czn?，); bi. start=hfd. start;void iiuffmantreel:transcode(iluffmancodel b，int n)/對(duì)文章進(jìn)行翻譯并保存ifstream ifs cwdata. txt)； ofstream ofs (wcode. txt”)； char s 1000;int t=0; char ch;,、,'i i 4i "<<endl;printf ("報(bào)文的編碼為：n"); while(ifs. get(ch)if

43、(ch!= n) st=ch;for(int i=0;in;i+)if (st=bi. leaf)for (int j=bi. start+1;j<n;j+)printf(%c，bi. infoj); ofs«bi. infoj;t+;printf crt);printf (報(bào)文的編碼已經(jīng)保存往wcode. txlan");,、,、ii4 < f i 本本本本<endl;void huffmantreel:translateartcle(huffmancodel b, int n) /將所譯的碼翻譯成文章并保存int t=0;if stream ifs (

44、vcode. txt)； ofstream ofs (transwdata. txt)；string s; getl ine (i fs, s);for (t=0 int 1=0 int j二0printf ("報(bào)文的譯碼結(jié)果為:n"); while(l<t)while (j<n)int hu二bj. start+1; int k=0; while (hu<n)if(sl=bj. infohu) 1+;hu+;k+;elsebreak;if(hu=n)printf ("%c, bj. leaf); ofsbj. leaf; j=0;break:e

45、lsel=l-k;j+; continue;printf crt）;printf （譯碼的鉆果己經(jīng)保存到transwdata. 1】1:中13）;/ /【i i i i i k u«% rt* «% rt* «% rt* rt% ，丁、7% *t% 7% *t% 7% *t% 7% *t%，丁、*t%，丁、*t% r* *t% r* *t% r* *t% r*，t、xt% r* xt% 4、t% 4、t% 4、t% 4、t% xt% xtx t% *y* t% *y* t% *y* >t% xt% xt% xt% xt% *t% *y* >t%林林&q

46、uot;endl;void huffmantreel:translatedcode()ifstream ifs c'wdata. txt)；char str1000;char str100;int i=0, j, m100, h, k=0;int n=0;y- « <x- / /sl sl sl sl slz slz slz slz slz slz sl sllz lz lz lz lzlz lz lz lz lz >1>1>1>1>1>1>1>1ixtx xx xtx <、，丁、xx，丁、xx，丁、xx，丁、xx，

47、丁、<、，丁、x|x，丁、x|，丁、x|x，丁、x|>，丁、x|>，丁、x|>，卜 *1%，卜 *|>x x|，卜 x|>，卜 *1，卜'丁、，卜'丁、，卜'丁、，卜'丁、'卜'丁、，卜 t%，矗、'丁、'«、tx，蠡、xy> ,、，丁、'龕、y% ,、xyx，矗、，丁、'«、，丁、，矗、，丫、，蠡、，丁、<«、，丫、xjx x|x xx林林"endl;printf ("文件中提取的文章字符串是：n"); c

48、har ch;while (ifs. get (ch)printf(%c"， ch); if (ch!= n)strn+=ch;printf crt);printf ("字符串中共含有字符%(1個(gè)1<，n); for(i=0;in;i+)j=o;h=o;while(stri!=strj)j+；if(j=i)strk=stri;printf (字符%(:出現(xiàn),strk);elsecontinue; for(j=i；j<n；j+)if(stri=strj) h+;printf(%cuxn,h);mk=h;k+; <4* < lvl* vl* vl* vl

49、* vl* vl* vl* vl* vl* vl* vl*%lx%lx %lx %lx %lx %lx【| 11 i ik<r%<r%本本本本<<endl;printf c字符串中字符種類(lèi)有%(1種1/，k);rw 1 1i4、4、t、2 t、t、2 t、t> t、2 t、t、t、t、t、t、t、t、t、本林本"<endl;printf ("每個(gè)字符對(duì)應(yīng)的哈夫曼編碼是：n");createlifmtree(str, m, k); cin. get ();/ printf(n");/main, cpp/#include&

50、quot;huffmancodel. h"/第二部分功能實(shí)現(xiàn)的代碼 $«$«$typedef struct/哈弗曼樹(shù)節(jié)點(diǎn)的結(jié)構(gòu)體char info; /關(guān)聯(lián)字符信息 unsigned int weight; /每個(gè)節(jié)點(diǎn)的權(quán)職 unsigned int parent, 1 chi 1d, rchild;htnode, *huffmantree;typedef char *huffniancode; /存儲(chǔ)哈弗*s編碼void select(huffmantree ht, int j,int &sl, int &s2)/選擇雙親節(jié)點(diǎn)為0,并且最小的兩個(gè)

51、子葉節(jié)點(diǎn)int i=l, in;while(hti. parent!=0)/找第一個(gè)雙親節(jié)點(diǎn)為0的子葉結(jié)點(diǎn)1+;for(s2=sl=i;i<j;i+)/保證s 1中的權(quán)值最小，s2次小if(hti. parent=0 && hti. weight<htsi, weight)s2=s1; sl=i;else if(hti. parent=0 && hti. weight>=htsi, weight &&hti. weight<=hts2. weight)s2=i;while(hti. parent=0 &&

52、sl=s2)m=i; m+;whileparent!=0)m+;s2=m;void huffmancoding(huffmantree &ht, huffmancode &hc, int *w, int n, char *info) /哈弗曼編碼int i, m;huffmantree p; if(n<l) return; m = 2氺n-1;ht = (huffmantree)malloc(m+l)*sizoof(htnode); for (p=ht+l, i=l; i<=n;+i,十+p,十+w, +info)/初始化所有已存在的子葉信息p-info =氺inf

53、o; p-weight =氺w;p->parent = 0; p->lchild = 0; p->rchild = 0;/forfor(; i=m;+i, +p)/構(gòu)造所需要的過(guò)度根節(jié)點(diǎn)p->weight = 0; p->parent =0; p->lchild = 0; p->rchild = 0;/forfor (i=n+l;i=m;+i)/建立哈弗曼樹(shù)int si, s2;select (ht, i-1, si, s2);htsl. parent =i;hts2. parent =i;iiti. lchild = s2;hti. rchild =

54、 si;hti. weight = htsl. weight+hts2. weight; /for/哈弗曼編碼hc = (huffmancode)malloc(n+1)*sizeof(char *); char* cd = (char*)malloc(nsizeof(char); cdn-l = 0 ；for(i=l;i=n;+i)int f;unsigned int c; int start=nl;for (c=i, f=hti. parent;f !=0;c=f, f=htf. parent) iflchild=c) cdstart = 0 ；else cdstart = 1 ；hci=(

55、char*)maloc(n-start)*sizeof(char); strepy&cdstart);/forfree (cd);/huffmancodi ng/y功能實(shí)現(xiàn)輸出并保存字符串的二進(jìn)制編碼void checkcoding(huffmantree iit, huffmancode hc, char 氺strcheck, int m, int k) ofstream ofs(bcode. txt)；/查詢(xún)哈弗曼編碼信息int p;for (int i=0; i<m; i+)for (int j=l;info != strchecki; j+);/輸出并保存字符串的二進(jìn)制編碼cout«hcj;ofs«hcj;cout«endl;cout<字符串的二進(jìn)制編碼己經(jīng)保存在“bcode.txt”中endl;/c0ut譯碼翻譯得到的文章已保存在“data, txt”中"endl;xtx tx tx tx xx xx（| i i i i "<endl;cout<"各字符對(duì)應(yīng)的編碼為，encil;/輸出各字符對(duì)應(yīng)的哈夫曼編碼for （ p二1;p=k;p+）cout<<htp. info： ，/<<hcp«endl;/checkcoding/對(duì)鍵盤(pán)輸入的二進(jìn)制