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

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