《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)格式要求

1、數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)（ 2010/2011 學(xué)年第二學(xué)期第20 周）指導(dǎo)教師：孫麒 郭奕億班級(jí)： 09 計(jì)算機(jī)科學(xué)與技術(shù)1 班學(xué)號(hào)： E09620118姓名：倪建鶴數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)任務(wù)書(shū)數(shù)據(jù)結(jié)構(gòu)與算法是計(jì)算機(jī)專(zhuān)業(yè)重要的核心課程之一，在計(jì)算機(jī)專(zhuān)業(yè)的學(xué)習(xí)過(guò)程中占有非常重要的地位。 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)就是要運(yùn)用本課程以及到目前為止的有關(guān)課程中的知識(shí)和技術(shù)來(lái)解決實(shí)際問(wèn)題。特別是面臨非數(shù)值計(jì)算類(lèi)型的應(yīng)用問(wèn)題時(shí)，需要選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)出滿(mǎn)足一定 時(shí)間和空間限制的有效算法。本課程設(shè)計(jì)要求同學(xué)獨(dú)立完成一個(gè)較為完整的應(yīng)用需求分析。并在設(shè)計(jì)和編寫(xiě)具有一定規(guī)模程序的過(guò)程中，深化對(duì)數(shù)據(jù)結(jié)構(gòu)與算法課程

2、中基本概念、理論和方法的理解；訓(xùn)練綜合運(yùn)用所學(xué)知識(shí)處理 實(shí)際問(wèn)題的能力，強(qiáng)化面向?qū)ο蟮某绦蛟O(shè)計(jì)理念；使自己的程序設(shè)計(jì)與調(diào)試水平有一個(gè)明顯的提高。赫夫曼編碼/譯碼器1 .問(wèn)題描述利用赫夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳輸數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼(復(fù)原)。對(duì)于雙工信道(即可以雙向傳輸信息的信道)，每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站編寫(xiě)一個(gè)赫夫曼碼的編/譯碼系統(tǒng)。2 . 基本要求一個(gè)完整的系統(tǒng)應(yīng)具有以下功能：(1) I:初始化(Initialization )。從終端讀入字符集大小n,以及

3、n個(gè)字符和n個(gè)權(quán)值，建立赫夫曼樹(shù)，并將它存于文件 hfmTree中。(2) E:編碼(Encoding)。利用已建好的赫夫曼樹(shù)(如不在內(nèi)存，則從文件hfmTree中讀入)，對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。D：譯碼(Decoding)。利用已建好的赫夫曼樹(shù)將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件Textfile 中。以下為選做：(4) P:印代碼文件(Print)。將文件CodeFile以緊湊格式顯示在終端上，每行 50個(gè)代碼。同時(shí)將此字 符形式的編碼文件寫(xiě)入文件CodePrin中。T :印赫夫曼樹(shù)(Treeprinting)。將已在內(nèi)存

4、中的赫夫曼樹(shù)以直觀的方式(比如樹(shù))顯示在終端上， 同時(shí)將此字符形式的赫夫曼樹(shù)寫(xiě)入文件TreePrint中。3 .測(cè)試要求(1)已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其頻率分別為0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,試設(shè)計(jì)赫夫曼編碼。(2)用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立赫夫曼樹(shù)，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THISPROGRAME IS MY FA VORITE ”。字符ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度57631514851802381811614

5、.實(shí)現(xiàn)提示(1)編碼結(jié)果以文本方式存儲(chǔ)在文件Codefile中。(2)用戶(hù)界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號(hào)，再加上“Q”，表示退出運(yùn)行 Quito請(qǐng)用戶(hù)鍵入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶(hù)選擇了 “Q”為止。（3）在程序的一次執(zhí)行過(guò)程中，第一次執(zhí)行I, D或C命令之后，赫夫曼樹(shù)已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行 I命令，因?yàn)槲募fmTree可能早已建好。具體要求：課程設(shè)計(jì)成果的內(nèi)容必須由以下四個(gè)部分組成，缺一不可。（1）上交源程序：學(xué)生按照實(shí)驗(yàn)題目的具體要求所開(kāi)發(fā)的所有源程序（應(yīng)該放到一個(gè)文件夾中）；（2）上交程序的說(shuō)明文件：（保存在.txt

6、中）在說(shuō)明文檔中應(yīng)該寫(xiě)明上交程序所在的目錄，上交程序 的主程序文件名，如果需要安裝，要有程序的安裝使用說(shuō)明；（3）設(shè)計(jì)報(bào)告：（保存在word文檔中，文件名要求：按照“姓名學(xué)號(hào)設(shè)計(jì)題目”起名，如文件名為“張三_XXX_赫夫曼編碼” .doc。打印稿用A4紙）。其中包括： 題目； 實(shí)驗(yàn)?zāi)康模?需求分析：在該部分中敘述實(shí)現(xiàn)的功能要求； 概要設(shè)計(jì)：在此說(shuō)明每個(gè)部分的算法設(shè)計(jì)說(shuō)明（可以是描述算法的流程圖），每個(gè)程序中使用的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)說(shuō)明（如果指定存儲(chǔ)結(jié)構(gòu)請(qǐng)寫(xiě)出該存儲(chǔ)結(jié)構(gòu)的定義）； 詳細(xì)設(shè)計(jì)各個(gè)算法實(shí)現(xiàn)的源程序，對(duì)每個(gè)題目要有相應(yīng)的源程序（可以是一組源程序， 每個(gè)功能模塊采用不同的函數(shù)實(shí)現(xiàn)）。源程序要按

7、照寫(xiě)程序的規(guī)則來(lái)編寫(xiě)。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部 分要加上清晰的程序注釋?zhuān)?調(diào)試分析測(cè)試數(shù)據(jù)，測(cè)試輸出的結(jié)果，時(shí)間復(fù)雜度分析，和每個(gè)模塊設(shè)計(jì)和調(diào)試時(shí)存在問(wèn)題的思考（問(wèn)題是哪些？問(wèn)題如何解決？），算法的改進(jìn)設(shè)想； 總結(jié)：總結(jié)可以包括：設(shè)計(jì)過(guò)程的收獲、遇到問(wèn)題及解決問(wèn)題過(guò)程的思考、程序調(diào)試能力的思考、對(duì)數(shù) 據(jù)結(jié)構(gòu)這門(mén)課程的思考、在設(shè)計(jì)過(guò)程中對(duì)數(shù)據(jù)結(jié)構(gòu)課程的認(rèn)識(shí)等內(nèi)容。三、工作內(nèi)容及工作計(jì)劃：一周（20）時(shí)間地點(diǎn)工作內(nèi)容指導(dǎo)教師7月11 日上午10-414實(shí)驗(yàn)要求，需求分析；孫麒、郭奕億下午10-414查找資料，總體結(jié)構(gòu)設(shè)計(jì)；孫麒、郭奕億7月12日上午10-414算法設(shè)計(jì)、用戶(hù)界面設(shè)

8、計(jì)孫麒、郭奕億下午10-414算法設(shè)計(jì)、用戶(hù)界面設(shè)計(jì)孫麒、郭奕億7月13日上午10-414詳細(xì)設(shè)計(jì)孫麒、郭奕億下午10-414詳細(xì)設(shè)計(jì)孫麒、郭奕億7月14日上午10-414詳細(xì)設(shè)計(jì)孫麒、郭奕億下午10-414詳細(xì)設(shè)計(jì)孫麒、郭奕億7月15日上午10-414上機(jī)檢查、答辯孫麒、郭奕億下午10-414上機(jī)檢查、答辯孫麒、郭奕億四、考核成績(jī)?cè)u(píng)定規(guī)范：本課程設(shè)計(jì)的評(píng)價(jià)由三部分組成，包括程序演示（50% ,課程設(shè)計(jì)報(bào)告（30% ,回 答教師提問(wèn)（20% 。1 程序演示：優(yōu)功能完善，全部測(cè)試正確，并且能夠?qū)植窟M(jìn)行完善。良功能完善，但測(cè)試欠缺。中功能基本完善，但程序尚有部分錯(cuò)誤。及格完成內(nèi)存中赫夫曼編碼 /

9、譯碼，但不涉及文件操作。不及格功能不完善，且程序錯(cuò)誤較多，無(wú)法運(yùn)行。2課程設(shè)計(jì)報(bào)告：優(yōu)包括設(shè)計(jì)內(nèi)容，設(shè)計(jì)思想，已經(jīng)完成的任務(wù)及達(dá)到的目標(biāo)，設(shè)計(jì)思路清晰、書(shū)寫(xiě)條理清楚，源程序結(jié)構(gòu)合理、清晰，注釋說(shuō)明完整，有對(duì)本次課程設(shè)計(jì)的心得體會(huì)。良 包括設(shè)計(jì)內(nèi)容，設(shè)計(jì)思想，已經(jīng)完成的任務(wù)及達(dá)到的目標(biāo)，設(shè)計(jì)思路基本清晰、書(shū)寫(xiě)條理基本清楚，源程序結(jié)構(gòu)合理、清晰，注釋說(shuō)明基本完整，有對(duì)本次課程設(shè)計(jì)的心得體會(huì)。中 課程設(shè)計(jì)報(bào)告內(nèi)容基本完整，思路較清晰，書(shū)寫(xiě)基本清楚，源程序結(jié)構(gòu)尚可，有注釋說(shuō)明但不完整。及格課程設(shè)計(jì)報(bào)告內(nèi)容基本完整，思路較差，書(shū)寫(xiě)尚清楚。不及格課程設(shè)計(jì)報(bào)告內(nèi)容不完整，書(shū)寫(xiě)沒(méi)有條理。3回答教師提問(wèn)：優(yōu)能回

10、答教師提出的所有問(wèn)題，并完全正確，思路清晰良基本能回答教師提出的所有問(wèn)題，有些小錯(cuò)誤中基本能回答教師提出的問(wèn)題，少數(shù)問(wèn)題回答錯(cuò)誤或不清楚及格能回答教師提出的問(wèn)題，但較多問(wèn)題回答錯(cuò)誤或不能回答不及格基本不能回答教師提出的問(wèn)題數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)目錄一、 題目二、 需求分析三、 概要設(shè)計(jì)四、 程序說(shuō)明五、 詳細(xì)設(shè)計(jì)六、 實(shí)驗(yàn)心得與體會(huì)赫夫曼編譯碼器一、題目問(wèn)題描述利用赫夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳輸數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/

11、譯碼系統(tǒng)。試為這樣的信息收發(fā)站編寫(xiě)一個(gè)赫夫曼碼的編/ 譯碼系統(tǒng)?；疽笠粋€(gè)完整的系統(tǒng)應(yīng)具有以下功能：(1) I:初始化(Initialization )。從終端讀入字符集大小n,以及n個(gè)字符和n個(gè)權(quán)值，建立赫夫曼樹(shù)，并將它存于文件 hfmTree中。(2) E:編碼(Encoding)。利用已建好的赫夫曼樹(shù)(如不在內(nèi)存，則從文件hfmTree中讀入)，對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。D：譯碼(Decoding)。利用已建好的赫夫曼樹(shù)將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件Textfile 中。(以下為選做：)(4) P:印代碼文件(P

12、rint)。將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫(xiě)入文件CodePrin中。T :印赫夫曼樹(shù)(Treeprinting)。將已在內(nèi)存中的赫夫曼樹(shù)以直觀的方式(比如樹(shù))顯示在終端上， 同時(shí)將此字符形式的赫夫曼樹(shù)寫(xiě)入文件TreePrint中。測(cè)試要求(1)已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其頻率分別為0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,試設(shè)計(jì)赫夫曼編碼。(2)用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立赫夫曼樹(shù)，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THISPROGRAME IS MY FAVORITE

13、” 。字符ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161二、需求分析(1)初始化哈夫曼數(shù)(2)輸入字符保存至 tobetran.txt中(3)對(duì)字符編碼(4)編碼結(jié)果以文本方式存儲(chǔ)在文件Codefile中。(5)在對(duì)codefile中編碼進(jìn)行譯碼(6)打印編碼和哈夫曼樹(shù)用戶(hù)界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號(hào)，再加上“Q”，表示退出運(yùn)行 Quito請(qǐng)用戶(hù)鍵入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶(hù)選擇了 “Q”為止。在程序的一次執(zhí)行過(guò)程中，第一次執(zhí)行I

14、, D或C命令之后，赫夫曼樹(shù)已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因?yàn)槲募fmTree可能早已建好。三、概要設(shè)計(jì)函數(shù)間的關(guān)系如圖3.1所示：圖3.1函數(shù)間的關(guān)系數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)赫夫曼編譯碼器的主要功能是先建立赫夫曼樹(shù)，然后利用建好的赫夫曼樹(shù)生成赫夫 曼編碼后進(jìn)行譯碼。在數(shù)據(jù)通信中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符0、1組成的二進(jìn)制用，稱(chēng)之為編碼。構(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)之為赫夫曼編碼。最簡(jiǎn)單的二進(jìn)制編碼方式是等長(zhǎng)編碼。若采用不等長(zhǎng)編碼，讓出現(xiàn)頻率

15、高的字符具有 較短的編碼，讓出現(xiàn)頻率低的字符具有較長(zhǎng)的編碼，這樣可能縮短傳送電文的總長(zhǎng)度。赫 夫曼樹(shù)課用于構(gòu)造使電文的編碼總長(zhǎng)最短的編碼方案。其主要流程圖如圖3.2所示。是否為根結(jié)點(diǎn)?否為空I<2*N?輸出兩子結(jié)點(diǎn)和已構(gòu)造的結(jié)點(diǎn)I+編碼為1/輸出根結(jié)點(diǎn)和權(quán)值此時(shí)編碼為0調(diào)用SELECT函數(shù)將data和權(quán)值賦給ht父結(jié)點(diǎn)為兩子結(jié)點(diǎn)之和計(jì)算根結(jié)點(diǎn)函數(shù)是21 / 30四、程序說(shuō)明1 赫夫曼樹(shù)抽象數(shù)據(jù)類(lèi)型定義ADT HuffmanCoding數(shù)據(jù)對(duì)象具有相同特性的數(shù)據(jù)元素的集合數(shù)據(jù)關(guān)系R:滿(mǎn)足最優(yōu)二叉樹(shù)的關(guān)系基本操作P：Init （ &t）操作結(jié)果：構(gòu)造一個(gè)空赫夫曼樹(shù)t 。encode（

16、）操作結(jié)果：利用赫夫曼樹(shù)進(jìn)行編碼Decode（）操作結(jié)果：利用赫夫曼樹(shù)進(jìn)行譯碼2 . 主函數(shù)Void mian （） 打印表頭；While（ 選擇項(xiàng)不為q）輸入選擇項(xiàng)；Switch（ 選擇項(xiàng) ）Case i ： 初始化；break。Case w：輸入要編碼的字符；break ；Case e：編碼字符；break ；Case d； 譯碼操作；break；Case p；打印代碼；break；Case t ； 打印赫夫曼樹(shù)；break ；Default ：輸入錯(cuò)誤，重新選擇；五、詳細(xì)設(shè)計(jì)源程序：#include <iomanip.h>#include <malloc.h>#i

17、nclude <stdio.h>const int UINT_MAX=1000 。typedef struct/權(quán)值/父節(jié)點(diǎn)，左孩子結(jié)點(diǎn)，右孩子結(jié)點(diǎn)/代表赫夫曼樹(shù)/代表赫夫曼編碼int weight 。int parent,lchild,rchild 。HTNode,* HuffmanTree 。typedef char *HuffmanCode 。/定義全局變量HuffmanTree HT 。HuffmanCode HC 。int *w,i,j,n 。char *z 。int flag=0 。int numb=0 。int min(HuffmanTree t,int i)/ 選出

18、葉子結(jié)點(diǎn)int j,flag 。int k=UINT_MAX 。/取k 為足夠大的值for(j=1 。 j<=i 。 j+)if(tj.weight<k&&tj.parent=0)k=tj.weight,flag=j 。tflag.parent=1 。return flag 。/返回標(biāo)識(shí)符void select(HuffmanTree t,int i,int &s1,int &s2)/ 排序兩個(gè)葉子結(jié)點(diǎn)int j 。s1=min(t,i) 。s2=min(t,i) 。if(s1>s2)/ s1 為最小的兩個(gè)值中序號(hào)小的那個(gè)j=s1 。s1=s2

19、。s2=j。void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)HC/w 存放 n 個(gè)字符的權(quán)值(均>0) ，構(gòu)造哈夫曼樹(shù)HT 并求出 n 個(gè)字符的哈夫曼編碼int m,i,s1,s2,start。int c,f。HuffmanTree p 。char *cd 。if(n<=1)return。m=2*n-1 。/結(jié)點(diǎn)數(shù)HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode) 。/ 0 號(hào)單元未用for(p=HT+1,i=1 。 i<=n 。 +i,+p,+w

20、) p->weight=*w 。p->parent=0。p->lchild=0 。p->rchild=0 。for( 。 i<=m 。 +i,+p)p->parent=0。for(i=n+1 。 i<=m 。 +i) / 建赫夫曼樹(shù)select(HT,i-1,s1,s2)。HTs1.parent=HTs2.parent=i 。HTi.lchild=s1 。HTi.rchild=s2 。HTi.weight=HTs1.weight+HTs2.weightHC=(HuffmanCode)malloc(n+1)*sizeof(char*) 。cd=(char

21、*)malloc(n*sizeof(char) 。/編碼結(jié)束符cdn-1='0' 。for(i=1 。 i<=n 。 i+) /逐個(gè)字符求編碼start=n-1 。for(c=i,f=HTi.parent 。 f!=0 。 c=f,f=HTf.parent)/ 從葉子到根逆向求編碼if(HTf.lchild=c)cd-start='0' 。elsecd-start='1' 。HCi=(char*)malloc(n-start)*sizeof(char) 。strcpy(HCi,&cdstart) 。/復(fù)制cd 到 HCfree(cd

22、)。void InitHuffman() /初始化赫夫曼鏈表flag=1。int num 。int num2。cout<<"赫夫曼鏈表初始化"<<endl<<"結(jié)點(diǎn)的個(gè)數(shù) n="。cin>>num。n=num。w=(int*)malloc(n*sizeof(int)。 分配權(quán)值空間z=(char*)malloc(n*sizeof(char)。分配字符空間cout<<"n請(qǐng)依次輸入"<<n<<"個(gè)字符"<<endl。cha

23、r temp2。for(i=0。 i<n。 i+)/輸入字符cout<<"字符"<<i+1<<":"<<endl 。gets(temp)*(z+i)=*temp 。)cout<<"n請(qǐng)依次輸入"<<n<<"個(gè)字符的權(quán)"<<endl。for(i=0。 i<=n-1 。 i+)/輸入權(quán)cout<<endl<<i+1<<":"。cin>>num2*

24、(w+i)=num2 。)輸入部分結(jié)束 編碼HuffmanCoding(HT,HC,w,n) 。cout<<" 字符對(duì)應(yīng)的編碼為:"<<endl 。for(i=1 。 i<=n 。 i+)cout<<" 字符 "<<*(z+i-1)<<" 的編碼為："。puts(HCi) 。/輸出編碼/將赫夫曼編碼寫(xiě)入文件cout<<" 赫夫曼編碼寫(xiě)入文件htmTree.txt 中 "<<endl 。FILE *htmTree 。char r

25、=' ','0' 。if(htmTree=fopen("htmTree.txt","w")=NULL)cout<<" 文件打開(kāi)失敗"<<endl 。return 。fputs(z,htmTree) 。/文件中輸入z 字符串cout<<endl 。 /不加這個(gè)代碼文件輸入有誤fputc('n',htmTree) 。 /換行for(i=0 。 i<n 。 i+)/文件中輸入權(quán)fprintf(htmTree,"%d ",*(w+i)

26、 。fputs(r,htmTree) 。fprintf(htmTree,"n") 。 /換行for（i=1 。 i<=n 。 i+）/文件中輸入編碼fputs(HCi,htmTree) 。fputs(r,htmTree) 。fclose(htmTree) 。/init/獲取字符并寫(xiě)入文件創(chuàng)建待編碼文件void inputcode()FILE *virttran,*tobetran 。char str。if(tobetran=fopen("tobetran.txt","w")=NULL)cout<<" 不能打

27、開(kāi)文件"<<endl 。return。cout<<" 請(qǐng)輸入你想要編碼的字符并以#號(hào)結(jié)束"<<endl 。str=getchar()。 / 用來(lái)初始化str=getchar()。 /此語(yǔ)句用來(lái)接收輸入的第一個(gè)字符while(str!='#')fputc(str,tobetran) 。str=getchar()。cout<<" 寫(xiě)入成功！"<<endl 。fclose(tobetran) 。void encode()/ 完成編碼功能cout<<" 下

28、面對(duì)目錄下文件tobetran.txt 中的字符進(jìn)行編碼"<<endl。FILE *tobetran,*codefile 。if(tobetran=fopen("tobetran.txt","rb")=NULL)cout<<" 不能打開(kāi)文件"<<endl 。return 。if(codefile=fopen("codefile.txt","wb")=NULL)cout<<" 不能打開(kāi)文件"<<endl 。r

29、eturn 。char *tran。i=99。tran=(char*)malloc(100*sizeof(char) 。/為tran 分配 100 個(gè)字節(jié)while(i=99)if(fgets(tran,100,tobetran)=NULL)cout<<" 不能打開(kāi)文件"<<endl 。break。for(i=0 。 *(tran+i)!='0' 。 i+)/ 對(duì) tobetran 文件中字符通過(guò)初始化的哈夫曼編碼進(jìn)行編碼for(j=0 。 j<=n 。 j+)if(*(z+j-1)=*(tran+i)fputs(HCj,cod

30、efile) 。puts(HCj) 。if(j>n)cout<<" 字符錯(cuò)誤，無(wú)法編碼!"<<endl 。break。cout<<" 完成！ "<<endl<<" 編碼已寫(xiě)入codefile.txt 中 "<<endl<<endl 。fclose(tobetran) 。fclose(codefile) 。free(tran)。void decode()/ 完成譯碼功能cout<<" 下面對(duì)根目錄下文件codefile.txt

31、 中的字符進(jìn)行譯碼"<<endl 。FILE *codef,*txtfile 。if(txtfile=fopen("Textfile.txt","w")=NULL)cout<<" 不能打開(kāi)文件"<<endl 。return 。if (codef=fopen("codefile.txt","r")=NULL)cout<<" 不能打開(kāi)文件"<<endl 。return 。char *tbdc,*outext,i

32、2 。int io=0,i,m 。unsigned long length=10000 。tbdc=(char*)malloc(length*sizeof(char) 。/分配空間fgets(tbdc,length,codef) 。 /codefile 中提取編碼outext=(char*)malloc(length*sizeof(char) 。/分配空間m=2*n-1 。for(i=0 。 *(tbdc+i)!='0' 。 i+) /進(jìn)入循環(huán)依次譯碼i2=*(tbdc+i) 。if(HTm.lchild=0)*(outext+io)=*(z+m-1) 。io+。m=2*n-1

33、 。i-。else if(i2='0') m=HTm.lchild 。else if(i2='1') m=HTm.rchild 。*(outext+io)=*(z+m-1) 。*(outext+io+1)='0' 。fputs(outext,txtfile) 。 /譯碼完畢將譯碼放入文件cout<<" 完成！ "<<endl<<" 結(jié)果已寫(xiě)入txtfile.txt 中 "<<endl<<endl 。free(tbdc) 。free(outext)

34、。fclose(txtfile) 。fclose(codef) 。void printcode()/打印代碼cout<<" 打印赫夫曼樹(shù)"<<endl 。/ 輸出 "打印赫夫曼樹(shù)"語(yǔ)句25 / 30cout<<" 下 面 打 印 根 目 錄 下 文 件 CodePrin.txt 中 編 碼 字 符"<<endl<<"n"。FILE * CodePrin,* codefile 。if(CodePrin=fopen("CodePrin.txt&quo

35、t;,"w")=NULL)cout<<" 不能打開(kāi)文件"<<endl 。return 。if(codefile=fopen("codefile.txt","r")=NULL)cout<<" 不能打開(kāi)文件"<<endl 。return 。char *work3 。work3=(char*)malloc(51*sizeof(char) 。doif(fgets(work3,51,codefile)=NULL)cout<<" 不能讀取

36、文件"<<endl 。break。fputs(work3,CodePrin) 。 /放入puts(work3) 。while(strlen(work3)=50) 。free(work3) 。cout<<" 打印完成！"<<endl<<endl 。fclose(CodePrin) 。fclose(codefile) 。/打印赫夫曼樹(shù)的函數(shù)void coprint(HuffmanTree start,HuffmanTree HT)char t=' ' 。if(start!=HT)FILE * TreePr

37、int 。if(TreePrint=fopen("TreePrint.txt","a")=NULL)cout<<" 創(chuàng)建文件失敗"<<endl 。return。numb+。 /該變量為已被聲明為全局變量coprint(HT+start->rchild,HT) 。if(start->lchild&&start->rchild) t='<'。cout<<setw(5*numb)<<start->weight<<t<

38、;<endl 。fprintf(TreePrint,"%dn",start->weight) 。coprint(HT+start->lchild,HT) 。numb-。fclose(TreePrint) 。void printree(HuffmanTree HT,int w) / 打印赫夫曼樹(shù)HuffmanTree p 。p=HT+w 。coprint(p,HT)。cout<<"打印完成！ "<<endl。 輸出"打印工作結(jié)束"void printhead() cout<<&quo

39、t;ntt"。cout<<"歡迎使用赫夫曼編碼解碼系統(tǒng)ntt"。ntt"cout<<"i.初始化赫夫曼鏈表ntt"。cout<<"w.輸入字符保存在相應(yīng)義件中ntt"。cout<<"e編 碼ntt"。cout<<"d.譯碼ntt"。cout<<"p.打印編碼ntt"。cout<<"t.打印赫夫曼樹(shù)ntt"。cout<<"q.退出nt

40、t"。cout<<"cout<<endl 。if(flag=0)cout<<"鏈表尚未初始化，輸入'i'進(jìn)行初始化ntt"<<endl。cout<<"請(qǐng)選擇："。/*2 .主程序*/ void main()char choice owhile(choice!='q')printhead()。cin>>choice 。switch(choice)case 'i':InitHuffman() 。/按下i 則進(jìn)行初始化赫夫

41、曼鏈表31 / 30break。case 'w':/按下w 編碼字符inputcode() 。break。case 'e':/按下e 編碼encode()。break。case 'd':/按下d 譯碼decode()。break。case 'p':/按下p 打印編碼printcode() 。break。case 't':/按下 t 打印赫夫曼樹(shù)printree(HT,2*n-1) 。break。case 'q':/按下q 退出break。default:cout<<" 輸入錯(cuò)誤

42、，請(qǐng)重新選擇"<<endl 。free(z)。/釋放z 結(jié)點(diǎn)free(w) 。/釋放w 結(jié)點(diǎn)free(HT) 。/釋放HT 結(jié)點(diǎn)運(yùn)行結(jié)果:口初始化赫夫曼鏈袤M，輸入字符保存在相應(yīng)文件巾© .編 碼d.理 碼>打印編碼td 工印赫夫曼樹(shù)q-> 出隧表尚未初始化.輸；V ?進(jìn)行初始化情選擇一 特夫曼鏈表初始化 結(jié)點(diǎn)的個(gè)數(shù)n27 情依次輸入如個(gè)字符 岸符。序符土 序符3：brz±-4：輸入空格加26個(gè)字符輸入相應(yīng)的權(quán)值磷 1 D:stddynj h. cp p.exeT0 10s .1為10 111-缸為為為為為為為為為為為為為為為為為為為為為為為 既3馬3馬3馬馬3馬馬馬馬馬馬馬馬馬馬馬3馬馬馬 Tfl 5 Tfl 5 5 5 5 5 5 1 5 SN 5 -. p ? 5 5 5 -.fl & Fffl扁扁扁.扁扁 扁扁扁扁扁扁扁扁扁扁扁扁扁扁扁扁扁 rou L - u rT3 PT Rou LJ, L - - all 二 FTJ rou 匚" 二 rTJ WTJ rou L - 符符槍都張簞祚而熱布神布郴步雨御梅機(jī)棉布祚用枷擲 E±子字字字字丈子字字字字字子字字字字字字字蜃 'D:studynjh.cpp.ex?&quo