數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)----huffman編碼(編輯修改稿)
2025-02-14 17:17 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 應(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)制編碼，而赫夫曼樹是一種最優(yōu)二叉樹，它的編碼也是一種最優(yōu)編碼。在赫夫曼樹中，規(guī)定往左編碼為0，往右編碼為1，則得到葉子節(jié)點(diǎn)的編碼為從根結(jié)點(diǎn)帶葉子結(jié)點(diǎn)中所有路徑中0和1的順序排列。（1） 設(shè)計(jì)包含的幾個(gè)方面：①赫夫曼樹的構(gòu)造假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的赫夫曼樹有n個(gè)葉子結(jié)點(diǎn)。n個(gè)權(quán)值分別為w1,w2,………wn,則赫夫曼樹構(gòu)造規(guī)則為：將w1,w2,…….wn,看成有n棵樹的森林。在森林中選出兩個(gè)根結(jié)點(diǎn)最小的樹合并，作為一棵新樹的左右子書，且新樹根結(jié)點(diǎn)權(quán)值為左右子樹根結(jié)點(diǎn)權(quán)值之和。從森林中刪除選取的兩棵樹，并將新樹加入森林。重復(fù)2和3步驟，直到森林中只剩一棵樹為止②赫夫曼編碼（1）結(jié)點(diǎn)類型 typedef struct { ElemType elem。 unsigned int weight。 unsigned int parent,lchild,rchild?！ HTNode,*HuffmanTree。//動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹（2）其他模塊偽碼算法void HuffmanCoding(HuffmanTreeamp。,HuffmanCodeamp。,int) ?。▊未a算法）void Select(HuffmanTree,int,int*,int*) ?。▊未a算法）void OutputHuffmanCode(HuffmanTree,HuffmanCode,int) ?。▊未a算法）(3)算法分析設(shè)計(jì)void HuffmanCoding(HuffmanTreeamp。HT,HuffmanCodeamp。HC,int n)。{ 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=1。i=n。i++) {//初始化前n個(gè)節(jié)點(diǎn) cout輸入元素和所占比例：。 cinchwei。 HT[i].elem=ch。 HT[i].weight=wei。 HT[i].parent=HT[i].lchild=HT[i]rchild=0。 } for(i=n+1。i=m。++i) {//初始化后n+1...m HT[i].elem=39。039。 HT[i].weight=HT[i].parent=HT[i]lchild=HT[i].rchild=0。 } for(i=n+1。i=m。++i) {//生成n+1...m Select(HT,i1,amp。s1,amp。s2)。//查找權(quán)值較小的兩個(gè)節(jié)點(diǎn) 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。 } HC=new char*[n+1]。 cd=new char[n]。 cd[n1]=39。\039。 for(i=1。i=m。++i) {//生成HuffmanCode
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1