數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)----huffman編碼-在線瀏覽
2025-03-07 17:17本頁面
【正文】 法的集合相對(duì)應(yīng)，通過這組算法集合可以對(duì)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行某種操作。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)軟件和計(jì)算機(jī)硬件之間的一門計(jì)算機(jī)專業(yè)的核心課程，它是計(jì)算機(jī)程序設(shè)計(jì)、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。通過課程設(shè)計(jì)可以提高學(xué)生的思維能力，促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。 二．實(shí)驗(yàn)題目：赫夫曼編碼 已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符（a,b,c,d,e,f,g,h），其概率分別是:，?、佥斎?種字符的概率； ②構(gòu)造赫夫曼樹； ③輸出每個(gè)字符的赫夫曼編碼。樹中從根到 每個(gè)葉子都有一條路徑，對(duì)路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示 “1”碼，取每條路徑上的“0”或“1”的序列作為和每個(gè)葉子對(duì)應(yīng)的字符的編碼，這就是赫夫曼編碼。電報(bào)通信是傳遞文字的二進(jìn)制碼形式 的字符串，但在信息傳遞時(shí)，總希望總長度能盡可能短，即采用最短碼。 若將此對(duì)應(yīng)到二叉樹上，W i 為葉節(jié)點(diǎn)的權(quán) ，L i 為根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑長度。 因此，設(shè)計(jì)電文總長最短的二進(jìn)制前綴編碼，就是以n 種子符出現(xiàn)的頻率作權(quán)，構(gòu)造一刻赫夫曼樹， 此構(gòu)造過程成為赫夫曼編碼。（1）輸入的形式和輸入值的范圍：n中字符，其出現(xiàn)的頻率（2） 輸出的形式： 二進(jìn)制前綴編碼（3） 程序所能達(dá)到的功能：設(shè)計(jì)一顆赫夫曼樹，由此得到二進(jìn)制前綴編碼，即赫夫曼編碼。 三. 概要設(shè)計(jì)（1）為了實(shí)現(xiàn)上述程序功能，需要定義單鏈表的抽象數(shù)據(jù)類型：ADT BinaryTree { 數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。,HuffmanCodeamp。 ③查找權(quán)值較小的兩個(gè)結(jié)點(diǎn)函數(shù)Select ()。對(duì)主程序和其他模塊也都需要寫出偽碼算法。而赫夫曼樹在數(shù)據(jù)編碼中的應(yīng)用是數(shù)據(jù)的最小冗余編碼問題他是數(shù)據(jù)壓縮學(xué)的基礎(chǔ)。赫夫曼編碼就是一種不等長的二進(jìn)制編碼，而赫夫曼樹是一種最優(yōu)二叉樹，它在赫夫曼樹中，規(guī)定往左編碼為0，往右編碼為1，則得到葉子節(jié)點(diǎn)的編碼為從根結(jié)點(diǎn)帶葉子結(jié)點(diǎn)中所有路徑中0和1的順序排列。（1） 設(shè)計(jì)包含的幾個(gè)方面：赫夫曼樹的構(gòu)造n個(gè)權(quán)值分別為w1,w2,………wn,則赫夫曼樹構(gòu)造規(guī)則為：赫夫曼編碼（1）結(jié)點(diǎn)類型 typedef struct { ElemType elem。 unsigned int parent,lchild,rchild。//動(dòng)態(tài)分配數(shù)組存儲(chǔ)赫夫曼樹（2）其他模塊偽碼算法void HuffmanCoding(HuffmanTreeamp。,int) （偽碼算法）void Select(HuffmanTree,int,int*,int*) ?。▊未a算法）void OutputHuffmanCode(HuffmanTree,HuffmanCode,int) ?。▊未a算法）(3)算法分析設(shè)計(jì)void HuffmanCoding(HuffmanTreeamp。HC,int n)。 char*cd。 m=2*n1。 for(i=1。i++) {//初始化前n個(gè)節(jié)點(diǎn) cout輸入元素和所占比例：。 HT[i].elem=ch。 HT[i].parent=HT[i].lchild=HT[i]rchild=0。i=m。039。 } for(i=n+1。++i) {//生成n+1...m Select(HT,i1,amp。s2)。HT[s2]parent=i。HT[i].rchild=s2。 } HC=new char*[n+1]。 cd[n1]=39。 for(i
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1