哈夫曼編碼與譯碼的實(shí)現(xiàn)

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)說(shuō)明書(shū)哈夫曼編碼與譯碼的實(shí)現(xiàn)學(xué)生姓名萬(wàn)永馨學(xué)號(hào)1021024016班級(jí)信管101成績(jī)指導(dǎo)教師余冬梅數(shù)學(xué)與計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2023年3月2日數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)評(píng)閱書(shū)題目哈夫曼編碼與譯碼的實(shí)現(xiàn)學(xué)生姓名萬(wàn)永馨學(xué)號(hào)1021024016指導(dǎo)教師評(píng)語(yǔ)及成績(jī)指導(dǎo)教師簽名：年月日辯論評(píng)語(yǔ)及成績(jī)辯論教師簽名：年月日教研室意見(jiàn)總成績(jī)：室主任簽名：年月日2023—2023學(xué)年第一學(xué)期專業(yè)：信息管理與信息系統(tǒng)學(xué)號(hào)：1021024016姓名：萬(wàn)永馨課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)設(shè)計(jì)題目：哈夫曼編碼與譯碼的實(shí)現(xiàn)完成期限：自2023年2月20日至2023年3月2日共2周設(shè)計(jì)依據(jù)、要求及主要內(nèi)容〔可另加附頁(yè)〕：該設(shè)計(jì)題目將按以下要求完成：哈夫曼編碼與譯碼是信息傳輸中應(yīng)用的經(jīng)典算法，運(yùn)用C或VC++結(jié)合數(shù)據(jù)結(jié)構(gòu)等根底知識(shí)，按以下要求編程實(shí)現(xiàn)各種進(jìn)制的轉(zhuǎn)換。任務(wù)要求：1〕闡述設(shè)計(jì)思想,畫(huà)出流程圖;2〕需要對(duì)哈夫曼編碼/譯碼的相關(guān)原理有所了解，設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)，建立必要的信息數(shù)據(jù)文件〔最好存儲(chǔ)成外部文件〕，并分析完成用戶所需的根本操作功能；3〕實(shí)現(xiàn)給定信息的編碼和譯碼功能；4〕應(yīng)有較好的界面設(shè)計(jì)，說(shuō)明程序測(cè)試方法；5〕按照格式要求完成課程設(shè)計(jì)說(shuō)明書(shū)。設(shè)計(jì)要求:1〕問(wèn)題分析和任務(wù)定義：根據(jù)設(shè)計(jì)題目的要求，充分地分析和理解問(wèn)題，明確問(wèn)題要求做什么？〔而不是怎么做？〕限制條件是什么？確定問(wèn)題的輸入數(shù)據(jù)集合。2〕邏輯設(shè)計(jì)：對(duì)問(wèn)題描述中涉及的操作對(duì)象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原那么劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設(shè)計(jì)的結(jié)果應(yīng)寫(xiě)出每個(gè)抽象數(shù)據(jù)類型的定義〔包括數(shù)據(jù)結(jié)構(gòu)的描述和每個(gè)根本操作的功能說(shuō)明〕，各個(gè)主要模塊的算法，并畫(huà)出模塊之間的調(diào)用關(guān)系圖；3〕詳細(xì)設(shè)計(jì)：定義相應(yīng)的存儲(chǔ)結(jié)構(gòu)并寫(xiě)出各函數(shù)的偽碼算法。在這個(gè)過(guò)程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡(jiǎn)單和易于調(diào)試，抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝，根本操作的規(guī)格說(shuō)明盡可能明確具體。詳細(xì)設(shè)計(jì)的結(jié)果是對(duì)數(shù)據(jù)結(jié)構(gòu)和根本操作做出進(jìn)一步的求精，寫(xiě)出數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的類型定義，寫(xiě)出函數(shù)形式的算法框架；4〕程序編碼：把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語(yǔ)言程序。同時(shí)參加一些注解和斷言，使程序中邏輯概念清楚；5〕程序調(diào)試與測(cè)試：能夠熟練掌握調(diào)試工具的各種功能，設(shè)計(jì)測(cè)試數(shù)據(jù)確保程序正確。調(diào)試正確后，認(rèn)真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果；6〕結(jié)果分析：程序運(yùn)行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。算法的時(shí)間、空間復(fù)雜性分析；7〕編寫(xiě)課程設(shè)計(jì)報(bào)告；以上要求前三個(gè)階段的任務(wù)完成后，將設(shè)計(jì)說(shuō)明書(shū)的草稿交指導(dǎo)老師面審，審查合格方可進(jìn)入后續(xù)階段的工作。設(shè)計(jì)工作結(jié)束，經(jīng)指導(dǎo)老師驗(yàn)收合格后將設(shè)計(jì)說(shuō)明書(shū)裝訂，并辯論。指導(dǎo)教師〔簽字〕：教研室主任〔簽字〕：批準(zhǔn)日期：年月日摘要在當(dāng)今信息爆炸時(shí)代，如何采取有效的數(shù)據(jù)壓縮技術(shù)來(lái)節(jié)省數(shù)據(jù)文件的儲(chǔ)存空間越來(lái)越引起人們的重視。本次課程設(shè)計(jì)的實(shí)驗(yàn)題目為哈夫曼編碼與譯碼的實(shí)現(xiàn)。利用哈夫曼樹(shù)求得的用于通訊的二進(jìn)制編碼稱為哈弗曼編碼。通常我們將文字轉(zhuǎn)化為二進(jìn)制稱為編碼，而將二進(jìn)制轉(zhuǎn)化為文字稱為譯碼。此次程序就是將一個(gè)簡(jiǎn)單的文件進(jìn)行編碼轉(zhuǎn)化為二進(jìn)制數(shù)存入文件并進(jìn)行譯碼進(jìn)而輸出。而將文件轉(zhuǎn)化為二進(jìn)制編碼運(yùn)用哈夫曼樹(shù)的相關(guān)知識(shí)可以有效的節(jié)省存儲(chǔ)空間與時(shí)間。關(guān)鍵詞：哈夫曼樹(shù);哈夫曼樹(shù)的編碼;哈夫曼樹(shù)的譯碼;哈夫曼樹(shù)初始化;哈夫曼樹(shù)的建立開(kāi)發(fā)工具：visualC++目錄1.引言62.課題描述73.程序設(shè)計(jì)83.1實(shí)驗(yàn)?zāi)康呐c根本要求83.2局部函數(shù)介紹83.3主要模塊程序流程圖94系統(tǒng)實(shí)現(xiàn)134.1主函數(shù)〔菜單函數(shù)〕134.2建立HuffmanTree134.3生成Huffman編碼并寫(xiě)入文件154.4對(duì)文件哈夫曼譯碼.txt進(jìn)行譯碼譯碼165系統(tǒng)調(diào)試17附錄源程序231.引言在課程設(shè)計(jì)過(guò)程中，我們四個(gè)人一組選擇一個(gè)課題，認(rèn)真研究，根據(jù)課堂講授內(nèi)容，借助書(shū)本，自己動(dòng)手實(shí)踐。這樣不但有助于我們消化課堂所講解的內(nèi)容，還可以增強(qiáng)我們的獨(dú)立思考能力和動(dòng)手能力；通過(guò)編寫(xiě)實(shí)驗(yàn)代碼和調(diào)試運(yùn)行，我們可以逐步積累調(diào)試C程序的經(jīng)驗(yàn)并逐漸培養(yǎng)我們的編程能力、用計(jì)算機(jī)解決實(shí)際問(wèn)題的能力。在課程設(shè)計(jì)過(guò)程中，我們不但有自己的獨(dú)立思考，還借助各種參考文獻(xiàn)來(lái)幫助我們完成系統(tǒng)。更為重要的是，我們同學(xué)之間加強(qiáng)了交流，在對(duì)問(wèn)題的認(rèn)識(shí)方面可以交換不同的意見(jiàn)。同時(shí)，師生之間的互動(dòng)也隨之改善，我們可以通過(guò)具體的實(shí)例來(lái)從老師那學(xué)到更多的實(shí)用的知識(shí)。數(shù)據(jù)結(jié)構(gòu)課程具有比擬強(qiáng)的理論性，同時(shí)也具有較強(qiáng)的可應(yīng)用性和實(shí)踐性。課程設(shè)計(jì)是一個(gè)重要的教學(xué)環(huán)節(jié)。我們?cè)谝话闱闆r下都能夠重視實(shí)驗(yàn)環(huán)節(jié)，但是容易忽略實(shí)驗(yàn)的總結(jié)，忽略實(shí)驗(yàn)報(bào)告的撰寫(xiě)。通過(guò)這次實(shí)驗(yàn)讓我們明白：作為一名大學(xué)生必須嚴(yán)格訓(xùn)練分析總結(jié)能力、書(shū)面表達(dá)能力。需要逐步培養(yǎng)書(shū)寫(xiě)科學(xué)實(shí)驗(yàn)報(bào)告以及科技論文的能力。只有這樣，我們的綜合素質(zhì)才會(huì)有好的提高。2.課題描述課題：哈夫曼編碼與譯碼的實(shí)現(xiàn)問(wèn)題描述：對(duì)文件哈夫曼.txt中的字符串進(jìn)行編譯，統(tǒng)計(jì)其中的字符種類、個(gè)數(shù)作為權(quán)值。1.從D盤的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)文件夾中建立哈夫曼.txt文件里讀出文章〔必須大寫(xiě)〕；2.運(yùn)用jsp函數(shù)統(tǒng)計(jì)這篇文章中的每個(gè)字符出現(xiàn)的次數(shù)；3.以字符出現(xiàn)字?jǐn)?shù)作為權(quán)值，構(gòu)建哈夫曼樹(shù)，并將哈夫曼樹(shù)的存儲(chǔ)結(jié)構(gòu)的初態(tài)和終態(tài)進(jìn)行輸出；4.對(duì)每個(gè)字符進(jìn)行編碼并將所編碼寫(xiě)入程序，然后對(duì)另一文件中的編碼編碼進(jìn)行破譯。具體介紹：在本課題中，我們?cè)谟脖PD盤中預(yù)先建立一個(gè)哈夫曼.txt文檔，在里面編輯一篇文章(大寫(xiě))。然后運(yùn)行程序，調(diào)用fileopen()函數(shù)讀出該文章，顯示在界面；再調(diào)用jsq()函數(shù)對(duì)該文章的字符種類進(jìn)行統(tǒng)計(jì)，并對(duì)每個(gè)字符的出現(xiàn)次數(shù)進(jìn)行統(tǒng)計(jì)，并且在界面上顯示；然后以每個(gè)字符出現(xiàn)次數(shù)作為權(quán)值，調(diào)用ChuffmanTree()函數(shù)構(gòu)建哈夫曼樹(shù)；并調(diào)用print1()和print2()函數(shù)將哈夫曼的存儲(chǔ)結(jié)構(gòu)的初態(tài)和終態(tài)進(jìn)行輸出。然后哈夫曼樹(shù)進(jìn)行編碼，再對(duì)另一文件哈夫曼譯碼.txt編碼進(jìn)行譯碼，再輸出至界面。至此，整個(gè)工作就完成了。3.程序設(shè)計(jì)3.1實(shí)驗(yàn)?zāi)康呐c根本要求利用赫夫曼編碼進(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)。一個(gè)完整的系統(tǒng)應(yīng)具有以下功能：(1)初始化〔Initialization〕。從文件哈夫曼.txt讀入字符集,，統(tǒng)計(jì)字母?jìng)€(gè)數(shù)作為權(quán)值，建立赫夫曼樹(shù)。(2)編碼〔Encoding〕。利用已建好的赫夫曼樹(shù)〔如不在內(nèi)存，那么從文件中讀入〕，對(duì)哈夫曼樹(shù)進(jìn)行編碼，然后將結(jié)果存入文件哈夫曼譯碼.txt中。(3)譯碼〔Decoding〕。利用已建好的赫夫曼樹(shù)將文件哈夫曼譯碼.txt中的代碼進(jìn)行譯碼3.2局部函數(shù)介紹①?gòu)挠脖P讀取字符串fileopen(參數(shù))②建立HuffmanTree通過(guò)三個(gè)函數(shù)來(lái)實(shí)現(xiàn)：voidselect(參數(shù))說(shuō)明：在ht[1k]中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)的算法intjsq(參數(shù))說(shuō)明：統(tǒng)計(jì)字符串中各種字母的個(gè)數(shù)以及字符的種類voidChuffmanTree()說(shuō)明：構(gòu)造哈夫曼樹(shù)③輸出哈夫曼樹(shù)的存儲(chǔ)結(jié)構(gòu)的初態(tài)和終態(tài)分別調(diào)用print1()和print2()來(lái)實(shí)現(xiàn)voidprint1(參數(shù))說(shuō)明：輸出哈夫曼樹(shù)的初態(tài)voidprint2(參數(shù))說(shuō)明：輸出哈夫曼樹(shù)的終態(tài)④哈夫曼編碼和譯碼voidHuffmanEncoding(參數(shù))說(shuō)明：哈夫曼編碼char*decode(參數(shù))說(shuō)明：哈夫曼譯碼3.3主要模塊程序流程圖①主函數(shù)流程圖：圖3.1流程圖注釋：圖3.1比擬簡(jiǎn)單，由該圖可知主要是調(diào)用各個(gè)函數(shù)模塊，首先代開(kāi)已經(jīng)存在的文件，然后統(tǒng)計(jì)總的字符數(shù)以及出現(xiàn)的各個(gè)字符和頻率。然后才開(kāi)始建立哈夫曼樹(shù)，接著在哈夫曼樹(shù)的根底上對(duì)其進(jìn)行編碼，編碼之后才是譯碼。最后輸出結(jié)束。②構(gòu)造哈夫曼樹(shù)：圖3.2流程圖注釋：圖3.2是表示構(gòu)造哈夫曼樹(shù)的過(guò)程。首先輸入num個(gè)葉結(jié)點(diǎn)的權(quán)值，當(dāng)i=num是循環(huán)結(jié)束。然后進(jìn)行哈夫曼樹(shù)的構(gòu)建，當(dāng)i=2*num-1是循環(huán)結(jié)束。最后輸出所得到的字符統(tǒng)計(jì)情況。③哈夫曼編碼：圖3.3流程圖解釋：流程圖3.3表示哈夫曼編碼情況。首先初始化，Cd[--start]=0,start=num。然后從首地址開(kāi)始進(jìn)行比擬，找節(jié)點(diǎn)的父母地址然后看節(jié)點(diǎn)為父母地址的左孩子是的話為’0’,反之為’1’.依次開(kāi)始上溯。將編碼存入H[i].bits。哈夫曼譯碼：圖3.4流程圖解釋：流程圖3.4表示哈夫曼譯碼情況。首先講哈夫曼編碼存入的文件翻開(kāi)，將哈夫曼編碼導(dǎo)出。然后將文件中讀出的字符與哈夫曼編碼cd進(jìn)行比擬strcmp(HC[j].bits,cd==0，相等的話開(kāi)始譯出str[k]=HC[j].ch。4系統(tǒng)實(shí)現(xiàn)各模塊關(guān)鍵代碼及算法的解釋：4.1主函數(shù)〔菜單函數(shù)〕主函數(shù)相對(duì)簡(jiǎn)單，只需了解順序，依次調(diào)用即可。這里不做解釋4.2建立HuffmanTree代碼解釋：該函數(shù)為在ht[1k]中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)的算法，其序號(hào)為s1和s2。voidselect(HuffmanTreeT,intk,int&s1,int&s2){ inti,j;intmin1=32767;for(i=1;i<=k;i++) if(T[i].weight<min1&&T[i].parent==0) { j=i;min1=T[i].weight; } s1=j;min1=32767; for(i=1;i<=k;i++) if(T[i].weight<min1&&T[i].parent==0&&i!=s1) { j=i;min1=T[i].weight; } s2=j;}代碼解釋：下面函數(shù)用來(lái)統(tǒng)計(jì)字符串中各種字母的個(gè)數(shù)以及字符的種類。當(dāng)字符在A和z之間時(shí)即被計(jì)數(shù)，并用str[j]保存字母到數(shù)組中，用cnt[j]統(tǒng)計(jì)每種字符個(gè)數(shù)。j返回總共讀取的字符數(shù)目。intjsq(char*s,intcnt[],charstr[]){ inti,j,k; char*p; inttemp[53]; for(i=1;i<=52;i++) temp[i]=0; for(p=s;*p!='\0';p++) { { if(*p>='A'&&*p<='z') k=*p-64; temp[k]++; } }//統(tǒng)計(jì)各種字符的個(gè)數(shù)for(i=1,j=0;i<=52;++i) if(temp[i]!=0) { j++; str[j]=i+64;//送對(duì)應(yīng)的字母到數(shù)組中cnt[j]=temp[i];//存入對(duì)應(yīng)字母的權(quán)值 } returnj;//j是輸入字母總數(shù)}代碼解釋：下面函數(shù)用來(lái)構(gòu)造哈夫曼樹(shù)HT。首先初始化哈夫曼樹(shù)，然后輸入前面統(tǒng)計(jì)的各結(jié)點(diǎn)的權(quán)值，用for循環(huán)來(lái)構(gòu)造哈夫曼樹(shù)。voidChuffmanTree(HuffmanTreeHT,HuffmanCodeHC,intcnt[],charstr[]){ inti,s1,s2;for(i=1;i<=2*num-1;i++)//初始化HT，2*num-1是指哈夫曼//所有的結(jié)點(diǎn)數(shù)目 { HT[i].lchild=0;HT[i].rchild=0; HT[i].parent=0;HT[i].weight=0; } for(i=1;i<=num;i++)//輸入num個(gè)葉結(jié)點(diǎn)的權(quán)值HT[i].weight=cnt[i]; for(i=num+1;i<=2*num-1;i++) { select(HT,i-1,s1,s2); HT[s1].parent=i;HT[s2].parent=i; HT[i].lchild=s1;HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; }//在ht[1k]中選擇parent為0且權(quán)值最小//的兩個(gè)根結(jié)點(diǎn),其序號(hào)為s1和s2,i為雙親for(i=0;i<=num;i++)//輸入字符集的中字符HC[i].ch=str[i];//字符的種類i=1;while(i<=num) printf("字符%c次數(shù):%d\n",HC[i].ch,cnt[i++]);}//輸出統(tǒng)計(jì)的情況4.3生成Huffman編碼并寫(xiě)入文件代碼解釋：根據(jù)哈夫曼樹(shù)T求哈夫曼編碼H。voidHuffmanEncoding(HuffmanTreeT,HuffmanCodeH){ intc,p,i;//c和p分別指示t中孩子和雙親charcd[n];//臨時(shí)存放編碼串intstart;//指示碼在cd中的起始位置cd[num]='\0';//最后一位〔第num個(gè)〕放上串結(jié)束符for(i=1;i<=num;++i) { start=num;//初始位置c=i;//從葉子結(jié)點(diǎn)t[i]開(kāi)始上溯while((p=T[c].parent)>0)//直至上溯到t[c]是樹(shù)根為止 {cd[--start]=(T[p].lchild==c)?'0':'1'; c=p; }//假設(shè)t[c]是t[p]的左孩子//那么生成0;否那么生成底碼１strcpy(H[i].bits,&cd[start]); H[i].len=num-start; }}voidcoding(HuffmanCodeHC,char*str){//對(duì)str所代表的字符串進(jìn)行編碼并寫(xiě)入文件inti,j; FILE*fp; fp=fopen("D:\\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)\\哈夫曼譯碼.txt","w"); while(*str) { for(i=1;i<=num;i++) { for(j=0;j<HC[i].len;j++) {if(HC[i].ch==*str) {fputc(HC[i].bits[j],fp);}}//將編碼寫(xiě)入文件 }str++; }fclose(fp);}4.4對(duì)文件哈夫曼譯碼.txt進(jìn)行譯碼譯碼代碼解釋：代碼文件哈夫曼譯碼.txt的譯碼，將翻譯的二進(jìn)制碼譯成原來(lái)的字符。char*decode(HuffmanCodeHC){ FILE*fp; charstr[254];//假設(shè)遠(yuǎn)文本文件不超過(guò)254個(gè)字符char*p; staticcharcd[n+1]; inti,j,k=0,cjs;fp=fopen("D:\\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)\\哈夫曼譯碼.txt","r");//翻開(kāi)文本文檔txtwhile(!feof(fp))//feof(fp)判斷文件是否真正結(jié)束，//feof(fp)=1時(shí)文件結(jié)束{cjs=0; for(i=0;i<num&&cjs==0&&!feof(fp);i++) { cd[i]='';cd[i+1]='\0'; cd[i]=fgetc(fp);//數(shù)組接受從fp指針?biāo)赶蛭募凶x//入的一個(gè)字符for(j=1;j<=num;j++) if(strcmp(HC[j].bits,cd)==0) { str[k]=HC[j].ch; k++; cjs=1;break;}//haffman編碼和密碼譯碼相比擬}} str[k]='\0';p=str; returnp;}5系統(tǒng)調(diào)試本次測(cè)試是在我的電腦的D盤中建立一個(gè)名為哈夫曼.txt的文本文檔，其中有大寫(xiě)字母KONGYONGKAISB運(yùn)行程序后，我們可以見(jiàn)到一下的運(yùn)行界面。首先選擇1翻開(kāi)文件哈夫曼.txt然后選擇2初始化并建立哈夫曼樹(shù)接下來(lái)選擇3開(kāi)始對(duì)已經(jīng)建立的哈夫曼樹(shù)進(jìn)行編碼并寫(xiě)入文件哈夫曼譯碼.txt最后對(duì)文件哈夫曼譯碼.txt進(jìn)行編譯選擇4開(kāi)始進(jìn)行譯碼的運(yùn)算由此可見(jiàn)此次程序圓滿成功。本程序能夠有效的多文件進(jìn)行編碼，并且在譯碼文件中至于要輸入你想要的子母編碼，在最后即可輸出?？偨Y(jié)通過(guò)兩周的課程設(shè)計(jì)使我對(duì)哈夫曼樹(shù)以及哈夫曼編碼有了更深的認(rèn)識(shí)和理解，也使我更加明白哈夫曼編碼譯碼在信息技術(shù)中的重要性和地位。首先我談?wù)勎以谠O(shè)計(jì)期間我遇到的難點(diǎn)。開(kāi)始的時(shí)候，代碼中有許多的錯(cuò)誤，其中之一便是局部信息無(wú)法有效的傳遞，不過(guò)在后面的改正中我發(fā)現(xiàn)的我的錯(cuò)誤。還有很多很多，例如，在樹(shù)的初始化輸出中，沒(méi)有權(quán)值的節(jié)點(diǎn)卻出現(xiàn)亂碼，這個(gè)問(wèn)題我最終是換了一種方法輸出才成功余興了，還有就是循環(huán)中出現(xiàn)的錯(cuò)誤。比方將哈夫曼編碼寫(xiě)入文件，就因?yàn)槎嗔艘粋€(gè)等號(hào)以至于哈夫曼譯碼總是不能成功譯出。許多的錯(cuò)誤讓我明白了一個(gè)道理細(xì)心是非常重要的。同時(shí)，對(duì)于編程者而言，思路清晰是相當(dāng)重要的。在適當(dāng)?shù)臅r(shí)候和同學(xué)一起交流探討是一個(gè)十分好的學(xué)習(xí)時(shí)機(jī)。請(qǐng)教老師也很重要，因?yàn)楫吘刮覀兪切率?，?duì)于某些問(wèn)題很難弄清楚。而且，某些錯(cuò)誤對(duì)于我們來(lái)說(shuō)有時(shí)候想半天都弄不來(lái)，但老師幾下下就搞好了，這樣就更加有效地節(jié)約了時(shí)間。這次課程設(shè)計(jì)不但讓我學(xué)得了一些編程知識(shí)，還學(xué)會(huì)了系統(tǒng)的做一份課程設(shè)計(jì)報(bào)告，明白了做事情只有認(rèn)真，才能真正做得更好！參考文獻(xiàn)[1]嚴(yán)蔚敏.吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版).清華大學(xué)出版社[2]施伯樂(lè).數(shù)據(jù)結(jié)構(gòu).復(fù)旦大學(xué)出版社[3]譚浩強(qiáng).C語(yǔ)言程序設(shè)計(jì)教程.高等教育出版社[4]金遠(yuǎn)平.數(shù)據(jù)結(jié)構(gòu).清華大學(xué)出版社[5]王燕.面向?qū)ο蟮睦碚撆cC++實(shí)踐.清華大學(xué)出版社[6]李春葆.C++語(yǔ)言──習(xí)題與解析.清華大學(xué)出版社[7]殷人昆，陶永雷，謝假設(shè)陽(yáng)等.數(shù)據(jù)結(jié)構(gòu).清華大學(xué)出版社[8]朱戰(zhàn)立，張選平.數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)指導(dǎo)與典型題解.西安：西安交通大學(xué)出版社，[9]羅文劼，王苗，石強(qiáng).數(shù)據(jù)結(jié)構(gòu)習(xí)題解答與實(shí)驗(yàn)指.中國(guó)鐵道出版社附錄源程序#include<stdio.h>#include<string.h>#include<stdlib.h>#include<fstream.h>#definen100//葉子結(jié)點(diǎn)數(shù)#definem2*n-1intg;//哈夫曼樹(shù)中的結(jié)點(diǎn)樹(shù)typedefstruct{ charch; charbits[9];//存放編碼位串 intlen;}CodeNode;typedefCodeNodeHuffmanCode[n+1];typedefstruct{ intweight;//權(quán)值 intlchild,rchild,parent;//左右孩子幾雙親指針}HTNode;typedefHTNodeHuffmanTree[m+1];//0號(hào)單元不用intnum;//**********************************建立HuffmanTree*************************voidselect(HuffmanTreeT,intk,int&s1,int&s2){//選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)的算法 //其為s1和s2 inti,j;intmin1=32767;for(i=1;i<=k;i++) if(T[i].weight<min1&&T[i].parent==0) { j=i;min1=T[i].weight; } s1=j;min1=32767; for(i=1;i<=k;i++) if(T[i].weight<min1&&T[i].parent==0&&i!=s1) { j=i;min1=T[i].weight; } s2=j;}intjsq(char*s,intcnt[],charstr[]){//統(tǒng)計(jì)字符串中各種字母的個(gè)數(shù)以及字符的種類 inti,j,k; char*p; inttemp[53]; for(i=1;i<=52;i++) temp[i]=0; for(p=s;*p!='\0';p++) { { if(*p>='A'&&*p<='z') k=*p-64; temp[k]++; } } for(i=1,j=0;i<=52;++i) if(temp[i]!=0) { j++; str[j]=i+64; cnt[j]=temp[i]; } returnj;//j是輸入字母總數(shù)}voidChuffmanTree(HuffmanTreeHT,HuffmanCodeHC,intcnt[]){//構(gòu)造哈夫曼樹(shù)HT inti,s1,s2; for(i=1;i<=2*num-1;i++) { HT[i].lchild=0;HT[i].rchild=0; HT[i].parent=0;HT[i].weight=0; } for(i=1;i<=num;i++)//輸入num個(gè)葉結(jié)點(diǎn)的權(quán)值 HT[i].weight=cnt[i]; for(i=num+1;i<=2*num-1;i++) { select(HT,i-1,s1,s2); HT[s1].parent=i;HT[s2].parent=i; HT[i].lchild=s1;HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; }}voidHuffmanEncoding(HuffmanTreeT,HuffmanCodeH)//生成哈夫曼編碼{ intc,p,i;//c和p分別指示t中孩子和雙親 charcd[n]; intstart; cd[num]='\0'; for(i=1;i<=num;++i) { start=num; c=i; while((p=T[c].parent)>0) { cd[--start]=(T[p].lchild==c)?'0':'1'; c=p; } strcpy(H[i].bits,&cd[start]); H[i].len=num-start; } for(i=1;i<=num;i++) printf("輸出編碼：%s\n",H[i].bits);}char*decode(HuffmanCodeHC){//代碼文件哈夫曼譯碼.txt的譯碼 FILE*fp; charstr[254];//假設(shè)文本文件不超過(guò)254個(gè)字符 char*p; staticcharcd[n+1]; inti,j,k=0,cjs;fp=fopen("D:\\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)\\哈夫曼譯碼.txt","r");//翻開(kāi)文本文檔txt while(!feof(fp))//feof(fp)判斷文件是否真正結(jié)束，feof(fp)=1時(shí)文件結(jié)束 { cjs=0; for(i=0;i<num&&cjs==0&&!feof(fp);i++) { cd[i]='';cd[i+1]='\0'; cd[i]=fgetc(fp);//數(shù)組接受從fp指針?biāo)赶蛭募凶x入的一個(gè)字符for(j=1;j<=num;j++) if(strcmp(HC[j].bits,cd)==0)//haffman編碼和密碼譯碼相比擬 { str[k]=HC[j].ch; k++; cjs=1;break; } } } str[k]='\0'; p=str; returnp;}//*************************輸出HuffmanTree存儲(chǔ)結(jié)構(gòu)*************************voidprint1(HuffmanTreeHT)//初建哈夫曼{ intx; for(x=1;x<=2*num-1;x++) { HT[x].parent=0; HT[x].lchild=0; HT[x].rchild=0; if(x>num) printf("\t@\t%d\t%d\t%d\n",HT[x].parent,HT[x].lchild,HT[x].rchild); else printf("\t%-6d%d\t%d\t%d\n",HT[x].weight,HT[x].parent,HT[x].lchild,HT[x].rchild); } printf("\n");}voidprint2(HuffmanTreeHT){ intk; for(k=1;k<=2*num-1;k++) { printf("\t%d\t%d\t%d\t%d\n",HT[k].weight,HT[k].parent,HT[k].lchild,HT[k].rchild); } printf("\n");}voidDhuffmanTree(HuffmanTreeHT,intcnt[]){//初始化哈夫曼樹(shù) inti; for(i=1;i<=num;i++) { //輸入num個(gè)葉結(jié)點(diǎn)的權(quán)值 HT[i].weight=cnt[i]; }}//*************************翻開(kāi)文本****************************************intopen(charstring[]){ FILE*fp;if((fp=fopen("D:\\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)\\哈夫曼.txt","r"))==NULL) { printf("不能翻開(kāi)文件!\n"); exit(1); } while(fgets(string,100,fp)!=NULL)printf("%s\n",string); fclose(fp); return0;}voidmain(){ charstring[100]; char*s,str[53]; intcnt[53]; intchoice; inti;HuffmanTreeHT; HuffmanCodeHC; while(choice) { printf("\n\n\n\t********哈夫曼編碼與譯碼的實(shí)現(xiàn)********\n\n\n");printf("\t\t\t1.翻開(kāi)D盤的的數(shù)據(jù)結(jié)構(gòu).txt文件\n\n");printf("\t\t\t2.初始化并建立哈夫曼樹(shù)\n\n");printf("\t\t\t3.進(jìn)行哈夫曼編碼\n\n");printf("\t\t\t4.進(jìn)行哈夫曼譯碼\n\n"); printf("\t\t\t0.退出編碼譯碼器\n\n"); printf("\n\n請(qǐng)輸入0-4,選擇要執(zhí)行的操作:"); scanf("%d",&choice); system("CLS"); switch(choice) { case1: