【正文】 行編碼Decode（）操作結(jié)果：利用赫夫曼樹(shù)進(jìn)行譯碼}2. 主函數(shù)Void mian（）{打印表頭；While(選擇項(xiàng)不為q){輸入選擇項(xiàng)；Switch(選擇項(xiàng)){Case i： 初始化；break。開(kāi)始結(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í)編碼為0I2*N?I++編碼為1結(jié)束否否否右子是否為空是是否否是是是 赫夫曼樹(shù)編\譯碼器流程圖4 詳細(xì)設(shè)計(jì)赫夫曼樹(shù)編、譯碼設(shè)計(jì)功能如下：1．赫夫曼樹(shù)抽象數(shù)據(jù)類型定義ADT HuffmanCoding{數(shù)據(jù)對(duì)象T：具有相同特性的數(shù)據(jù)元素的集合數(shù)據(jù)關(guān)系R：滿足最優(yōu)二叉樹(shù)的關(guān)系基本操作P：Init（amp。赫夫曼樹(shù)課用于構(gòu)造使電文的編碼總長(zhǎng)最短的編碼方案。最簡(jiǎn)單的二進(jìn)制編碼方式是等長(zhǎng)編碼。在數(shù)據(jù)通信中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符0、1組成的二進(jìn)制串，稱之為編碼。3 概要設(shè)計(jì) 設(shè)計(jì)思想赫夫曼樹(shù)用鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)，借助靜態(tài)鏈表來(lái)實(shí)現(xiàn)遍歷。（5）T：印赫夫曼樹(shù)（treeprint）。（4）P：印代碼文件（print）。利用已經(jīng)建立好的赫夫曼樹(shù)（如不在內(nèi)存，）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立赫夫曼樹(shù)。最后將建立的赫夫曼樹(shù)用某種樹(shù)的儲(chǔ)存方式儲(chǔ)存后輸出。要實(shí)現(xiàn)五個(gè)功能:接受原始數(shù)據(jù)、編碼、譯碼、打印編碼規(guī)則、將編碼、譯碼存檔。需要一個(gè)程序來(lái)完成。樹(shù)狀結(jié)構(gòu)簡(jiǎn)稱為樹(shù)，是一種以分支關(guān)系進(jìn)行定義的層次結(jié)構(gòu)，是十分重要的非線性數(shù)據(jù)結(jié)構(gòu)，在計(jì)算機(jī)軟件設(shè)計(jì)方面，有著廣泛的應(yīng)用。如何采用有效的數(shù)據(jù)壓縮技術(shù)引起了人們的極大重視。因此，想要更好地運(yùn)用計(jì)算機(jī)來(lái)解決實(shí)際問(wèn)題，僅掌握幾種計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言是難以應(yīng)付當(dāng)前眾多復(fù)雜的課題，想要有效地使用計(jì)算機(jī)，充分發(fā)揮它的性能，還必須學(xué)習(xí)和掌握好數(shù)據(jù)結(jié)構(gòu)的有關(guān)知識(shí)，打好數(shù)據(jù)結(jié)構(gòu)這門課的扎實(shí)基礎(chǔ)，對(duì)于學(xué)習(xí)計(jì)算機(jī)專業(yè)的其他課程，如操作系統(tǒng)、軟件工程、編譯原理、人工智能等十分有益。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)、計(jì)算機(jī)信息管理與應(yīng)用專業(yè)和電子商務(wù)的專業(yè)的基礎(chǔ)課，是十分重要的課程。樹(shù)狀結(jié)構(gòu)簡(jiǎn)稱為樹(shù)，是一種以分支關(guān)系進(jìn)行定義的層次結(jié)構(gòu)，是十分重要的非線性數(shù)據(jù)結(jié)構(gòu)，在計(jì)算機(jī)軟件設(shè)計(jì)方面，有著廣泛的應(yīng)用。如何采用有效的數(shù)據(jù)壓縮技術(shù)引起了人們的極大重視。以二叉樹(shù)的應(yīng)用為基礎(chǔ)，包括統(tǒng)計(jì)信息，并通過(guò)構(gòu)建赫夫曼樹(shù)、對(duì)信息進(jìn)行赫夫曼編碼，將編碼信息等存入文檔。赫夫曼編\譯碼器的主要功能是先建立赫夫曼樹(shù)，然后利用建好的赫夫曼樹(shù)生成哈夫曼編碼后進(jìn)行譯碼 。這次課程設(shè)計(jì)的設(shè)計(jì)內(nèi)容主要是通過(guò)實(shí)際的例子和程序來(lái)實(shí)現(xiàn)課本中所學(xué)習(xí)的算法的應(yīng)用。 赫夫曼編\譯碼器摘 要本次課程設(shè)計(jì)過(guò)程中我主要根據(jù)課本中的實(shí)現(xiàn)思想及算法編寫程序，體現(xiàn)以課本知識(shí)的應(yīng)用為主，在學(xué)習(xí)了線性表、棧、隊(duì)列、二叉樹(shù)、樹(shù)和圖等結(jié)構(gòu)的基礎(chǔ)上，以能夠更加熟練的應(yīng)用所學(xué)知識(shí)，并能結(jié)合一些著名算法來(lái)實(shí)現(xiàn)對(duì)一些實(shí)際問(wèn)題的應(yīng)用，例如，赫夫曼樹(shù)等，從而更為深刻理解數(shù)據(jù)結(jié)構(gòu)的內(nèi)涵，熟悉它們各自的應(yīng)用場(chǎng)合及方法。有些在平時(shí)課程中并沒(méi)有掌握的內(nèi)容在這次課程設(shè)計(jì)中都是先通過(guò)看課本學(xué)懂了，然后再在課程設(shè)計(jì)中加深印象，實(shí)現(xiàn)算法的應(yīng)用和擴(kuò)展。程序設(shè)計(jì)設(shè)計(jì)語(yǔ)言采用C++,程序運(yùn)行平臺(tái)為Windows XP。赫夫曼編譯系統(tǒng)分為五個(gè)功能模塊：原始數(shù)據(jù)載入，打印編碼規(guī)則、編碼、譯碼。關(guān)鍵字 數(shù)據(jù)結(jié)構(gòu) 棧和隊(duì)列 赫夫曼樹(shù) 赫夫曼編碼 目 錄1引言………………………………………………………………………………….1……………………………………………………………….1 ……………………………………………………………….1………………………………………………………….12需求分析…………………………………………………………………………….33 概要設(shè)計(jì)…………………………………………………………………………....4 設(shè)計(jì)思想……………………………………………………………………4 函數(shù)間的關(guān)系………………………………………………………………4………………………………………………………44詳細(xì)設(shè)計(jì)…………………………………………………………………………….6 赫夫曼的主要結(jié)構(gòu)…………………………………………………………..65 調(diào)試分析…………………………………………………………………………..86 測(cè)試并列出測(cè)試結(jié)果……………………………………………………………..9 測(cè)試方式 ……………………………………………………………………9 測(cè)試結(jié)果……………………………………………………………………..97 總結(jié)………………………………………………………………………………13致謝…………………………………………………………………………………..14參考文獻(xiàn)……………………………………………………………………………..14附錄…………………………………………………………………………………..151 引 言當(dāng)今社會(huì)，計(jì)算機(jī)技術(shù)和通信技術(shù)已不斷發(fā)展，處理和傳輸?shù)臄?shù)據(jù)量越來(lái)越龐大。從而產(chǎn)生了哈夫曼編碼，它是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)，該技術(shù)一般可將數(shù)據(jù)壓縮20%至90%，通常我們將壓縮技術(shù)稱為編碼，解壓縮過(guò)程稱為解碼。 課程設(shè)計(jì)目的 本課程設(shè)計(jì)是為了讓同學(xué)們了解數(shù)據(jù)結(jié)構(gòu)的作用和意義。所有的計(jì)算機(jī)系統(tǒng)軟件和應(yīng)用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)。 課程設(shè)計(jì)背景當(dāng)今社會(huì)，計(jì)算機(jī)技術(shù)和通信技術(shù)已不斷發(fā)展，處理和傳輸?shù)臄?shù)據(jù)量越來(lái)越龐大。從而產(chǎn)生了哈夫曼編碼，它是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)，該技術(shù)一般可將數(shù)據(jù)壓縮20%至90%，通常我們將壓縮技術(shù)稱為編碼，解壓縮過(guò)程稱為解碼。在這信息量發(fā)達(dá)的時(shí)代，隨著社會(huì)的進(jìn)步，信息不斷地增多和更新，為了使信息更加快速、準(zhǔn)確有的傳遞。 本課程設(shè)計(jì)要求完成發(fā)送端對(duì)待傳送數(shù)據(jù)的編碼和接收端對(duì)傳送來(lái)的數(shù)據(jù)的譯碼。通過(guò)系統(tǒng)的提示要建立哈夫曼樹(shù)并對(duì)載入的原文件進(jìn)行編碼，同時(shí)輸出到屏幕。2 需求分析一套完整的編碼譯碼系統(tǒng)應(yīng)該具有以下功能：（1）I：初始化（initialization）。(2)E：編碼（encoding）。(3)D：譯碼（decoding）。每行50個(gè)代碼。將已在內(nèi)存中的赫夫曼樹(shù)以直觀的方式（樹(shù)或凹入表形式）顯示在終端上。 函數(shù)間的關(guān)系 ：主函數(shù)顯示表頭初始化樹(shù)輸入字符編碼譯碼打印編碼打印赫夫曼樹(shù)選最小兩個(gè)權(quán)值Select() 函數(shù)間的關(guān)系 數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)赫夫曼編\譯碼器的主要功能是先建立赫夫曼樹(shù)，然后利用建好的赫夫曼樹(shù)生成赫夫曼編碼后進(jì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)字符的編碼，稱之為赫夫曼編碼。若采用不等長(zhǎng)編碼，讓出現(xiàn)頻率高的字符具有較短的編碼，讓出現(xiàn)頻率低的字符具有較長(zhǎng)的編碼，這樣可能縮短傳送電文的總長(zhǎng)度。t）操作結(jié)果：構(gòu)造一個(gè)空赫夫曼樹(shù)t。Case w： 輸入要編碼的字符； break；Case e： 編碼字符； break；Case d； 譯碼操作；break；Case p； 打印代碼；break；Case t； 打印赫夫曼樹(shù)； break；Default：輸入錯(cuò)誤，重新選擇；}3. 求赫夫曼編碼[5] if(t[j].weightkamp。t[j].parent==0) k=t[j].weight,flag=j。 4. 建赫夫曼樹(shù) HT[s1].parent=HT[s2].parent=i。//左孩子的權(quán)值 HT[i].rchild=s2。//將兩個(gè)權(quán)值相加作為新的權(quán)值 } HC=(HuffmanCode)malloc((n+1)*sizeof(char*))。 fputs(r,htmTree)。 6. 完成譯碼功能并將譯碼寫入文件 因?yàn)楹辗蚵鼧?shù)建好后是左孩子結(jié)點(diǎn)旁標(biāo)上0，右孩子結(jié)點(diǎn)上標(biāo)上1所以碰到1是用左孩子結(jié)點(diǎn)，2是用右孩子結(jié)點(diǎn)，可以用條件語(yǔ)句來(lái)實(shí)現(xiàn)。039。 if(i2==39。) m=HT[m].rchild。//將譯碼寫入文件5 調(diào)試分析1．本程序要執(zhí)行首先要初始化一個(gè)赫夫曼樹(shù)，按照用戶設(shè)定的字符集大小，輸入每個(gè)字符及其對(duì)應(yīng)的出現(xiàn)概率即權(quán)值。再利用這兩個(gè)變量構(gòu)造赫夫曼樹(shù)。以便執(zhí)行下一步編碼操作時(shí)自己從文件調(diào)用。4．譯碼時(shí)，程序從codefile中讀取代碼，按照代碼從樹(shù)根開(kāi)始向葉子節(jié)點(diǎn)查找對(duì)應(yīng)的字符，直到全部代碼譯碼完成，5．打印編碼操作，按要求輸出到屏幕上。然后才能進(jìn)行后續(xù)的操作。5．選擇“e”，對(duì)剛輸入的字符進(jìn)行編碼。7．選擇“p”，打印編碼出的代碼。 測(cè)試結(jié)果： 初始化的內(nèi)容“”ABCDEFGHIJKLMN1866413223210321154757153220NOPQRSTUVWXYZ576315148580238181161: 初始化的結(jié)果,： 將字符寫入文件： 字符對(duì)應(yīng)的編碼： 要編碼的字符：：THIS PROGRAM IS MY FAVORIT： 譯碼操作： 赫夫曼樹(shù)7 總 結(jié)通過(guò)將近兩周的課設(shè)練習(xí)，認(rèn)識(shí)到知識(shí)的遷移運(yùn)用，理論應(yīng)用實(shí)際和相互間的密切聯(lián)系，感受到理論知識(shí)的重要，在今后的學(xué)習(xí)中一定會(huì)更加努力，認(rèn)真。從中也體會(huì)到了學(xué)習(xí)中的樂(lè)趣，可以自由的創(chuàng)作自己喜歡的東西并自己調(diào)試。同時(shí)，我們也要感謝學(xué)校為我們提供了大量的圖書，通過(guò)看書我們也學(xué)到了很多課堂上學(xué)不到的東西。參考文獻(xiàn)[1]嚴(yán)蔚敏，：C語(yǔ)言版. 北京：清華大學(xué)出版社,1997[2]王昆侖,：中國(guó)鐵道出版社 [3]周靄如，++程序設(shè)計(jì)基礎(chǔ). 北京：電子工業(yè)出版社, 2005[4]. 北京：高等教育出版社, 2005[5] 王衛(wèi)東. 數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)課. 西安: 電子科技大學(xué)出版社, 2001年[6] 趙文靜. 數(shù)據(jù)結(jié)構(gòu)輔導(dǎo). 西安：交通大學(xué)出版社, 1999年附錄：include include include include