【正文】 赫夫曼編 \譯碼器 摘 要 本次課程設(shè)計(jì)過程中我主要根據(jù)課本中的實(shí)現(xiàn)思想及算法編寫程序，體現(xiàn)以課本知識的應(yīng)用為主，在學(xué)習(xí)了線性表、棧、隊(duì)列、二叉樹、樹和圖等結(jié)構(gòu)的基礎(chǔ)上，以能夠更加熟練的應(yīng)用所學(xué)知識，并能結(jié)合一些著名算法來實(shí)現(xiàn)對一些實(shí)際問題的應(yīng)用，例如，赫夫曼樹等，從而更為深刻理解數(shù)據(jù)結(jié)構(gòu)的內(nèi)涵，熟悉它們各自的應(yīng)用場合及方法。有些在平時(shí)課程中并沒有掌握的內(nèi)容在這次課程設(shè)計(jì)中都是先通過看課本學(xué)懂了，然后再在課程設(shè)計(jì)中加深印象，實(shí)現(xiàn)算法的應(yīng)用和擴(kuò)展。這次課程設(shè)計(jì)的設(shè)計(jì)內(nèi)容主要是通過實(shí)際的例子和程序來實(shí)現(xiàn)課本中所 學(xué)習(xí)的算法的應(yīng)用。 程序設(shè)計(jì)設(shè)計(jì)語言采用 C++,程序運(yùn)行平臺為 Windows XP。 赫夫曼編 \譯碼器的主要功能是先建立赫夫曼樹，然后利用建好的赫夫曼樹生成哈夫曼編碼后進(jìn)行譯碼 。 赫夫曼編譯系統(tǒng)分為五個功能模塊：原始數(shù)據(jù)載入 ，打印編碼規(guī)則、編碼、譯碼。以二 叉樹的應(yīng)用為基礎(chǔ)，包括統(tǒng)計(jì)信息，并通過構(gòu)建赫夫曼樹、對信息進(jìn)行赫 夫曼編碼，將編碼信息等存入文檔。 關(guān)鍵字 數(shù)據(jù)結(jié)構(gòu) 棧和隊(duì)列 赫夫曼樹 赫夫曼編碼 目 錄 1 引言 …………………………………………… …………………………………… .1 課程設(shè)計(jì)目的 …………………………………………… ………………… .1 課程設(shè)計(jì)背景 …………………………………………… ………………… .1 課程設(shè)計(jì)主要內(nèi)容 …………………………………………… …………… .1 2 需求分析 …………………………………………… ……………………………… .3 3 概要設(shè)計(jì) …………………………………………… …………………………… ....4 設(shè)計(jì)思想 …………………………………………… ……………………… 4 函數(shù)間的關(guān)系 …………………………………………… …… …………… 4 數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì) …………………………………………… ………… 4 4 詳細(xì)設(shè)計(jì) …………………………………………… ……………………………… .6 赫夫曼的主要結(jié)構(gòu) …………………………………………… …………… ..6 5 調(diào)試分析 …………………………………………… …………………………… ..8 6 測試并列出測試結(jié)果 …………………………………………… ……………… ..9 測試方式 …………………………………………… …………………… … 9 測試結(jié)果 ………………… ………………………… ……………………… ..9 7 總結(jié) …………………………………………… ………………………………… 13 致 謝 …………………………………………… …………………………………… ..14 參考文獻(xiàn) ……………………………………… …………………………………… ..14 附錄 ……………………………………… ………………………………………… ..15 1 1 引 言 當(dāng)今社會，計(jì)算機(jī)技術(shù)和通信技術(shù)已不斷發(fā)展，處理和傳輸?shù)臄?shù)據(jù)量越來越龐大。如何采用有效的數(shù)據(jù)壓縮技術(shù)引起了人們的極大重視。從而產(chǎn)生了哈夫 曼編碼，它是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)，該技術(shù)一般可將數(shù)據(jù)壓縮20%至 90%，通常我們將壓縮技術(shù)稱為編碼，解壓縮過程稱為解碼。 樹狀結(jié)構(gòu)簡稱為樹，是一種以分支關(guān)系進(jìn)行定義的層次結(jié)構(gòu)，是十分重要的非線性數(shù)據(jù)結(jié)構(gòu)，在計(jì)算機(jī)軟件設(shè)計(jì)方面，有著廣泛的應(yīng)用。 課程設(shè)計(jì) 目的 本課程設(shè)計(jì)是為了讓同學(xué)們了解數(shù)據(jù)結(jié)構(gòu)的作用和意義。 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)、計(jì)算機(jī)信息管理與應(yīng)用專業(yè)和電子商務(wù)的專業(yè)的基礎(chǔ)課，是十分重要的課程。所有的計(jì)算機(jī)系統(tǒng)軟件和應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。因此，想要更好地運(yùn) 用計(jì)算機(jī)來解決實(shí)際問題，僅掌握幾種計(jì)算機(jī)程序設(shè)計(jì)語言是難以應(yīng)付當(dāng)前眾多復(fù)雜的課題，想要有效地使用計(jì)算機(jī)，充分發(fā)揮它的性能，還必須學(xué)習(xí)和掌握好數(shù)據(jù)結(jié)構(gòu)的有關(guān)知識，打好數(shù)據(jù)結(jié)構(gòu)這門課的扎實(shí)基礎(chǔ)，對于學(xué)習(xí)計(jì)算機(jī)專業(yè)的其他課程，如操作系統(tǒng)、 軟件工程、編譯原理、人工智能等十分有益。 課程設(shè)計(jì) 背景 當(dāng)今社會，計(jì)算機(jī)技術(shù)和通信技術(shù)已不斷發(fā)展，處理和傳輸?shù)臄?shù)據(jù)量越來越龐大。如何采用有效的數(shù)據(jù)壓縮技術(shù)引起了人們的極大重視。從而產(chǎn)生了哈夫曼編碼，它是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)，該技術(shù)一般可將數(shù)據(jù)壓縮20%至 90%，通常我們將壓縮技術(shù)稱為編碼，解壓縮過程稱為解碼。 樹狀結(jié)構(gòu)簡稱為樹，是一種以分支關(guān)系進(jìn)行定義的層次結(jié)構(gòu)，是十分重要的非線性數(shù)據(jù)結(jié)構(gòu)，在計(jì)算機(jī)軟件設(shè)計(jì)方面，有著廣泛的應(yīng)用。 在這信息量發(fā)達(dá)的時(shí)代，隨著社會的進(jìn)步，信息不斷地增多和更新，為了使信息更加快速、準(zhǔn)確有的傳遞。需要一個程序來完成。 課程設(shè)計(jì) 主要內(nèi)容 本課程設(shè)計(jì) 要求完成發(fā)送端對待傳送數(shù)據(jù)的編碼和接收端對傳送來的數(shù)據(jù) 2 的譯碼。要實(shí)現(xiàn)五個功能 :接受原始數(shù)據(jù)、編碼、譯碼、打印編碼規(guī)則、將編碼、譯碼存檔。通過系統(tǒng)的提示要建立哈夫曼樹并對載入的原文件進(jìn) 行編碼，并保存到 文件中，同時(shí)輸出到屏幕。最后將建立的赫夫曼樹用某種樹的儲存方式儲存后輸出。 3 2 需求分析 一套完整的編碼譯碼系統(tǒng)應(yīng)該具有以下功能： （ 1） I：初始化（ initialization）。從終端讀入字符集大小 n，以及 n 個字符和 n 個權(quán)值，建立赫夫曼樹。并將他存于文件 中。 (2)E：編碼（ encoding）。利用已經(jīng)建立好的赫夫曼樹（如不在內(nèi)存，則從文件 中讀入），對文件 中的正文進(jìn)行編碼。然后將結(jié)果存入文件 文件中。 (3)D：譯碼（ decoding）。利用已經(jīng)建立好的赫夫曼樹將文件 中的代碼進(jìn)行譯碼，將結(jié)果存入文件 中。 （ 4） P：印代碼文件（ print）。將文件 以緊湊格式顯示在終端上。每行 50 個代碼。同時(shí)將字符形式的編碼文件寫入到文件 中。 （ 5） T：印赫夫曼樹（ treeprint）。將已在內(nèi)存中的赫夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時(shí)將此字符形式的赫夫曼樹寫入文件 中。 4 3 概要設(shè)計(jì) 設(shè)計(jì)思想 赫夫曼樹用鄰接矩陣作為存儲結(jié)構(gòu)，借助靜態(tài)鏈表來實(shí)現(xiàn)遍歷。 函數(shù)間的關(guān)系 函數(shù)間的關(guān)系如圖 所示： 圖 函數(shù)間的關(guān)系 數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì) 赫夫曼編 \譯碼器的主要功能是先建立赫夫曼樹，然后利用建好的赫夫曼樹生成赫 夫曼編碼后進(jìn)行譯碼 。 在數(shù)據(jù)通信中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符 0、 1 組成的二進(jìn)制串，稱之為編碼。構(gòu)造一棵赫夫曼樹，規(guī)定赫夫 曼樹中的左分之代表 0，右分支代表 1，則從根節(jié)點(diǎn)到每個葉子節(jié)點(diǎn)所經(jīng)過的路徑分支組成的 0和 1的序列便為該節(jié)點(diǎn)對應(yīng)字符的編碼，稱之為赫夫曼編碼。 最簡單的二進(jìn)制編碼方式是等長編碼。若采用不等長編碼，讓出現(xiàn)頻率高的字符具有較短的編碼，讓出現(xiàn)頻率低的字符具有較長的編碼，這樣可能縮短傳送電文的總長度。赫夫曼樹課用于構(gòu)造使電文的編碼總長最短的編碼方案。 其主要流程圖如圖 所示。 主函數(shù) 顯 示表頭 初始化樹 輸入字符 編碼 譯碼 打 印編碼 打 印赫夫曼樹 選 最小兩個權(quán)值 Select() 5 圖 赫夫曼樹編 \譯碼器流程圖 開始 結(jié)點(diǎn)數(shù)是否大于 1 將 data 和權(quán)值賦給 ht 輸出根結(jié)點(diǎn)和權(quán)值 調(diào)用 SELECT 函數(shù) 計(jì)算根結(jié)點(diǎn)函數(shù) 父結(jié)點(diǎn)為兩子結(jié)點(diǎn)之和 輸出兩子結(jié)點(diǎn)和已構(gòu)造的結(jié)點(diǎn) 是否為根結(jié)點(diǎn)？ 左子是否為空？ 此時(shí)編碼為 0 I2*N? I++ 編碼為 1 結(jié)束 否 否 否 右子是否為空 是 是 否 否 是 是 是 6 4 詳細(xì)設(shè)計(jì) 赫夫曼樹編、譯碼設(shè)計(jì)功能如 下： 1．赫夫曼樹抽象數(shù)據(jù)類型定義 ADT HuffmanCoding{ 數(shù)據(jù)對象 T：具有相同特性的數(shù)據(jù)元素的集合 數(shù)據(jù)關(guān)系 R：滿足最優(yōu)二叉樹的關(guān)系 基本操作 P： Init（ amp。t） 操作結(jié)果：構(gòu)造一個空赫夫曼樹 t。 encode() 操作結(jié)果：利用赫夫曼樹進(jìn)行編碼 Decode（） 操作結(jié)果：利用赫夫曼樹進(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； 打印赫夫曼樹； break； Default：輸入錯誤，重新選擇； } 3. 求赫夫曼編碼 [5] if(t[j].weightkamp。amp。t[j].parent==0) 7 k=t[j].weight,flag=j。 //flag 為標(biāo)志符， 為不小于可能的值 t[flag].parent=1。 4. 建赫夫曼樹 HT[s1].parent=HT[s2].parent=i。//將選好的兩個結(jié)點(diǎn)設(shè)置成有同一個雙親結(jié)點(diǎn) HT[i].lchild=s1。//左孩子的權(quán)值 HT[i].rchild=s2。//右孩子的權(quán)值 HT[i].weight=HT[s1].weight+HT[s2].weight。//將兩個權(quán)值相加作為新的權(quán)值 } HC=(HuffmanCode)malloc((n+1)*sizeof(char*))。//為赫夫曼代碼分配空間 5. 將赫夫曼編碼寫入文件 用 fputs(HC[i],htmTree)。 fputs(r,htmTree)。fclose(htmTree) 這些函數(shù) 來實(shí)現(xiàn) 編碼寫入文件 。 6. 完成譯碼功能并將譯碼寫入文件 因?yàn)楹辗蚵鼧浣ê煤笫亲蠛⒆咏Y(jié)點(diǎn)旁標(biāo)上 0，右孩子結(jié)點(diǎn)上標(biāo)上 1 所以碰到 1 是用左孩子結(jié)點(diǎn)， 2 是用右孩子結(jié)點(diǎn)，可以用條件語句來實(shí)現(xiàn)。 if(i2==39。039。) m=HT[m].lchild。 if(i2==39。139。) m=HT[m].rchild。 fputs(outext,txtfile)。//將譯碼寫入文件 8 5 調(diào)試分析 1．本程序要執(zhí)行首先要初始化一個赫夫曼樹，按照用戶設(shè)定的字符集大小，輸入每個字符及其對應(yīng)的出現(xiàn)概率即權(quán)值。分別存放在 w和 z這兩個變量中。再利用這兩個變量構(gòu)造赫夫曼樹。 2．執(zhí)行輸入字符命令時(shí)，程序?qū)⒂脩糨斎氲淖址嫒胛募?中。以便執(zhí)行下一步編碼操作