數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)----huffman編碼(編輯修改稿)
2025-07-08 22:52 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 g,h） ， 其概率分別是 :， ， ， ， ， ， ① 輸入 8 種字符的概率 ； ② 構(gòu)造赫夫曼樹(shù) ； ③ 輸出每個(gè)字符的赫夫曼編碼 。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) Huffman 編碼 學(xué)號(hào)： 姓名： 9 三 . 概要設(shè)計(jì) （ 1）為了實(shí)現(xiàn)上述程序功能，需要定義單鏈表的抽象數(shù)據(jù)類型： ADT BinaryTree { 數(shù)據(jù)對(duì)象 D： D 是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系 R： 若 D=? ，則 R= ，稱 BinaryTree為空二叉樹(shù)； 若 D? ?，則 R={H} 基本操作： void HuffmanCoding(HuffmanTreeamp。,HuffmanCodeamp。,int) 操作結(jié)果： 求赫夫曼編碼 void Select(HuffmanTree,int,int*,int*) 操作結(jié)果： 查找權(quán)值較小的兩個(gè)結(jié)點(diǎn) void OutputHuffmanCode(HuffmanTree,HuffmanCode,int) 操作結(jié)果： 輸出赫夫曼編碼 （ 2）本程序包含 4 個(gè)函數(shù)： ① 主函數(shù) main() ② 求赫夫曼編碼 函數(shù) HuffmanCoding()。 ③ 查找權(quán)值較小的兩個(gè)結(jié)點(diǎn) 函數(shù) Select ()。 ④ 輸出赫夫曼編碼 函數(shù) OutputHuffmanCode () 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) Huffman 編碼 學(xué)號(hào)： 姓名： 10 各函數(shù)間關(guān)系如下： HuffmanCoding() Main Select () OutputHuffmanCode () 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) Huffman 編碼 學(xué)號(hào)： 姓名： 11 四 . 詳細(xì)設(shè)計(jì) 實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有的數(shù)據(jù)類型，對(duì)每個(gè)操作給出偽碼算法。對(duì)主程序和其他模塊也都需要寫出偽碼算法。 哈夫曼編譯碼系統(tǒng)的主要功能是先建立哈夫曼樹(shù)，然后利用建好的哈夫曼樹(shù)生成哈夫曼編碼后進(jìn)行譯碼 。 在通信中可以采用 0 和 1 的不同排列來(lái)表示不同的字符，稱為二進(jìn)制編碼。而赫夫曼樹(shù)在數(shù)據(jù)編碼中的應(yīng)用是數(shù)據(jù)的最小冗余編碼問(wèn)題他是數(shù)據(jù)壓縮學(xué)的基礎(chǔ)。若每個(gè)字符出現(xiàn)的頻率相同 ，則可以采用等長(zhǎng)的二進(jìn)制編碼，頻率不同，采用不等長(zhǎng)的二進(jìn)制編碼，頻率達(dá)的字符采用位數(shù)較少的編碼，頻率小的采用位數(shù)較多的編碼。赫夫曼編碼就是一種不等長(zhǎng)的二進(jìn)制編碼，而赫夫曼樹(shù)是一種最優(yōu)二叉樹(shù)，它 的編碼也是一種最優(yōu)編碼。在赫夫曼樹(shù)中，規(guī)定往左編碼為 0，往右編碼為 1，則得到葉子節(jié)點(diǎn)的編碼為從根結(jié)點(diǎn)帶葉子結(jié)點(diǎn)中所有路徑中 0 和 1 的順序排列。 （ 1） 設(shè)計(jì)包含的幾個(gè)方面： ① 赫夫曼樹(shù)的構(gòu)造 假設(shè)有 n 個(gè)權(quán)值，則構(gòu)造出的赫夫曼樹(shù)有 n 個(gè)葉子數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) Huffman 編碼 學(xué)號(hào)： 姓名： 12 結(jié)點(diǎn)。 n 個(gè)權(quán)值分別為 w1,w2,??? wn,則赫夫曼樹(shù)構(gòu)造規(guī)則為： 將 w1,w2,?? .wn,看成有 n 棵樹(shù)的森林。 在森林中選出兩個(gè)根結(jié)點(diǎn)最小的樹(shù)合并，作為一棵新樹(shù)的左右子書(shū)，且新樹(shù)根結(jié)點(diǎn)權(quán)值為左右子樹(shù)根結(jié)點(diǎn)權(quán)值之和。 從森林中刪除選取的兩棵樹(shù)，并將新樹(shù)加入森林。 重復(fù) 2 和 3 步驟，直到森林中只剩一棵樹(shù)為止 ② 赫夫曼編碼 （ 1） 結(jié)點(diǎn)類型 typedef struct { ElemType elem。 unsigned int weight。 unsigned int parent,lchild,rchild。 } HTNode,*HuffmanTree。//動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹(shù) （ 2） 其他模塊偽碼算法 void HuffmanCoding(HuffmanTreeamp。,HuffmanCodeamp。,int) （偽碼算法） void Select(HuffmanTree,int,int*,int*) （偽碼算法） void OutputHuffmanCode(HuffmanTree,HuffmanCode,int) （偽碼算法） (3)算法分析設(shè)計(jì) void HuffmanCoding(HuffmanTreeamp。HT,HuffmanCodeamp。HC,int n)。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) Huffman 編碼 學(xué)號(hào)： 姓名： 13 { int i,m,s1,s2,start,c,f。 char*cd。 char chl//元素 if(n=1) return。 m=2*n1。 HT=new HTNode[m+1]。 for(i=
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1