版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、<p> 課程設(shè)計(jì)說(shuō)明書(shū)(論文)</p><p> 題 目 哈夫曼編碼問(wèn)題的設(shè)計(jì)和實(shí)現(xiàn) </p><p> 課 程 名 稱(chēng) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) </p><p> 院(系、部、中心) </p><p>
2、 專(zhuān) 業(yè) </p><p> 班 級(jí) </p><p> 學(xué) 生 姓 名 </p><p> 學(xué) 號(hào)
3、 </p><p> 設(shè) 計(jì) 地 點(diǎn) </p><p> 指 導(dǎo) 教 師 </p><p> 設(shè)計(jì)起止時(shí)間:2008 年6月 2日至 2008 年 6月 6 日</p><p><b> 目錄</b></p>
4、;<p><b> 1問(wèn)題描述2</b></p><p> 1.1題目?jī)?nèi)容2</p><p> 1.2基本要求2</p><p> 1.3測(cè)試數(shù)據(jù)2</p><p><b> 2需求分析2</b></p><p> 2.1程序的
5、基本功能2</p><p> 2.2輸入值、輸出值以及輸入輸出形式2</p><p> 2.3各個(gè)模塊的功能要求3</p><p><b> 3概要設(shè)計(jì)4</b></p><p> 3.1所需的ADT,每個(gè)程序中使用的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)說(shuō)明(如果指定存儲(chǔ)結(jié)構(gòu)請(qǐng)寫(xiě)出該存儲(chǔ)結(jié)構(gòu)的定義)4</p>
6、;<p> 3.2主程序流程以及模塊調(diào)用關(guān)系4</p><p> 3.3各個(gè)模塊的算法設(shè)計(jì)說(shuō)明4</p><p><b> 4詳細(xì)設(shè)計(jì)7</b></p><p> 4.1數(shù)據(jù)類(lèi)型7</p><p> 4.2函數(shù)調(diào)用8</p><p> 5各個(gè)算法實(shí)現(xiàn)
7、的源程序8</p><p><b> 6調(diào)試分析11</b></p><p><b> 7使用說(shuō)明12</b></p><p><b> 8測(cè)試結(jié)果12</b></p><p><b> 9源程序12</b></p>
8、<p><b> 問(wèn)題描述</b></p><p><b> 題目?jī)?nèi)容</b></p><p> 哈夫曼編碼問(wèn)題的設(shè)計(jì)和實(shí)現(xiàn)</p><p> 輸入一個(gè)英文字符串,對(duì)該字符串中各字符個(gè)數(shù)進(jìn)行統(tǒng)計(jì)取得各字符的出現(xiàn)次數(shù);以其出現(xiàn)次數(shù)作為關(guān)鍵字建立哈夫曼樹(shù)并進(jìn)行編碼,最后輸出各個(gè)字符對(duì)應(yīng)的碼值。</p&
9、gt;<p><b> 基本要求</b></p><p> 要求:設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)、基本算法(主要采用程序流程圖體現(xiàn));完成基本算法的實(shí)現(xiàn)代碼;設(shè)計(jì)測(cè)試輸入數(shù)據(jù)對(duì)程序進(jìn)行測(cè)試,分析輸出結(jié)果數(shù)據(jù)、算法的時(shí)間復(fù)雜度分析,如有改進(jìn)算法則提出算法的改進(jìn)方法。</p><p><b> 測(cè)試數(shù)據(jù)</b></p><p&g
10、t;<b> 測(cè)試數(shù)據(jù)三組:</b></p><p> AAAABBBCCD(判斷連續(xù)的字符串是否可行)</p><p> AABBAABCDC(判斷間段的字符串是否可行)</p><p> AAAA BBBCCD(判斷含空格的字符串是否可行)</p><p><b> 需求分析</b>&
11、lt;/p><p><b> 程序的基本功能</b></p><p> 該程序大體上有兩個(gè)功能:</p><p> 輸入任何一個(gè)字符串后,該程序能統(tǒng)計(jì)不同字符串的個(gè)數(shù),并以不同字符串的個(gè)數(shù)作為權(quán)值。</p><p> 已知不同字母的權(quán)值,以該權(quán)值作為葉結(jié)點(diǎn),構(gòu)造一棵帶權(quán)路徑最小的樹(shù),對(duì)該樹(shù)從葉結(jié)點(diǎn)到根結(jié)點(diǎn)路徑分支遍歷
12、,經(jīng)過(guò)一個(gè)分支就得到一位夫曼編碼值。(規(guī)定哈夫曼樹(shù)中的左分支為0,右分支為1,則從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)所經(jīng)過(guò)的分支對(duì)應(yīng)的0和1組成的序列便為該結(jié)點(diǎn)對(duì)應(yīng)字符的編碼)</p><p> 輸入值、輸出值以及輸入輸出形式</p><p> 輸入值 :AAAABBBCCD</p><p> 輸出值 :W =4 C=0</p><p> W=3
13、 C=10</p><p> W=2 C=111</p><p> W=1 C=110</p><p> 輸入值 :AABBAABCDC</p><p> 輸出值 :W=4 C=0</p><p> W=3 C=10</p><p> W=2 C=111<
14、;/p><p> W=1 C=110</p><p> 輸入值 :AAAA BBBCCD</p><p> 輸出值 :W=4 C=11</p><p> W=1 C=010</p><p> W=3 C=10</p><p> W=2 C=00</p>
15、<p> W=1 C=011</p><p><b> 各個(gè)模塊的功能要求</b></p><p><b> 統(tǒng)計(jì)模塊</b></p><p> 任意輸入一個(gè)字符串,不論字母是否相聯(lián),字符串中是否含空格都能統(tǒng)計(jì)出不同字母的個(gè)數(shù)。</p><p><b> 建立哈夫曼
16、樹(shù)模塊</b></p><p> 以統(tǒng)計(jì)的字符串個(gè)數(shù)作為權(quán)值,利用仿真存儲(chǔ)結(jié)構(gòu),建立帶權(quán)路徑最小的樹(shù)。</p><p> 其中對(duì)結(jié)點(diǎn)的存儲(chǔ)需要六個(gè)域,分別是 weight 域,flag域, parent域,leftChild 域,rightChild域。weight 域是對(duì)權(quán)值的存放,flag 域是一個(gè)標(biāo)志域,flag=0時(shí)表示該結(jié)點(diǎn)尚未加入到哈夫曼樹(shù)中,flag=1時(shí)表示
17、該結(jié)點(diǎn)已加入到哈夫曼樹(shù)中。</p><p><b> 哈夫曼編碼模塊</b></p><p> 從哈夫曼樹(shù)的葉結(jié)點(diǎn)到根結(jié)點(diǎn)路徑分支逐步遍歷,每經(jīng)過(guò)一個(gè)分支就得到一位哈夫曼編碼。哈夫曼編碼也利用仿真存儲(chǔ)結(jié)構(gòu)。</p><p><b> 主函數(shù)模塊</b></p><p> 從屏幕上輸入字符串,
18、調(diào)用函數(shù),輸出每個(gè)字母的權(quán)值與編碼。</p><p><b> 概要設(shè)計(jì)</b></p><p> 所需的ADT,每個(gè)程序中使用的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)說(shuō)明(如果指定存儲(chǔ)結(jié)構(gòu)請(qǐng)寫(xiě)出該存儲(chǔ)結(jié)構(gòu)的定義)</p><p> 抽象數(shù)據(jù)類(lèi)型集合:在該程序中未用到抽象數(shù)據(jù)類(lèi)型,主要用到的數(shù)據(jù)類(lèi)型為 :int ,char 。</p><p&g
19、t; 在哈夫曼樹(shù)的建立與哈夫曼樹(shù)的編碼中用到仿真存儲(chǔ)</p><p> 主程序流程以及模塊調(diào)用關(guān)系</p><p> 輸入字符串——〉調(diào)用count 函數(shù)——〉申請(qǐng)內(nèi)存空間——〉調(diào)用 Haffman</p><p> ——〉調(diào)用 HaffmanCode——〉輸出權(quán)值與編碼。</p><p> 各個(gè)模塊的算法設(shè)計(jì)說(shuō)明</p>
20、;<p><b> 主函數(shù)模塊</b></p><p><b> n</b></p><p><b> y</b></p><p><b> y</b></p><p><b> n</b></p>
21、<p><b> n</b></p><p><b> y</b></p><p> 主函數(shù)中利用gets輸入一個(gè)字符串,調(diào)用count 函數(shù)統(tǒng)計(jì)不同字母的個(gè)數(shù),在調(diào)用</p><p> Haffman 函數(shù)建立哈夫曼樹(shù),然后調(diào)用HaffmanCode函數(shù)進(jìn)行編碼,如果成功,輸出權(quán)</p>
22、<p> 值與編碼,否則退出。</p><p><b> 統(tǒng)計(jì)函數(shù)</b></p><p><b> y</b></p><p><b> N</b></p><p><b> y</b></p><p>&
23、lt;b> y</b></p><p><b> N</b></p><p><b> Y</b></p><p> 統(tǒng)計(jì)函數(shù)在統(tǒng)計(jì)不同字符個(gè)數(shù)時(shí)先利用一個(gè)for循環(huán)遍歷所有的字母,每遍歷一個(gè)不同字母前令temp=1,然后用一個(gè)for循環(huán)將其后的字母與之比較,若相等則temp++,且將該字母從字符
24、串中刪除,否則從下一個(gè)字母遍歷。如此循環(huán)直到字符串結(jié)束。</p><p> Haffman 函數(shù)</p><p><b> n</b></p><p><b> yn</b></p><p><b> n</b></p><p><b&
25、gt; y </b></p><p><b> n</b></p><p><b> y</b></p><p><b> n</b></p><p><b> y</b></p><p><b>
26、 y</b></p><p> Haffman函數(shù)主要以仿真結(jié)構(gòu)存儲(chǔ)信息,開(kāi)始對(duì)每個(gè)域開(kāi)始賦值,再根據(jù)不同的情況對(duì)每個(gè)域的值進(jìn)行修改,如此循環(huán)下去,直到每個(gè)域的值修改完全。</p><p> HffmanCode 函數(shù)</p><p><b> n</b></p><p><b> y<
27、;/b></p><p><b> n</b></p><p><b> nny</b></p><p><b> y</b></p><p> HaffmanCode 函數(shù)主要以仿真結(jié)構(gòu)存儲(chǔ)信息 ,由葉結(jié)點(diǎn)向根結(jié)點(diǎn)遍歷,從數(shù)據(jù)域start域開(kāi)始編碼,bit數(shù)
28、組存放編碼,其編碼為0,1序列.。</p><p><b> 詳細(xì)設(shè)計(jì)</b></p><p><b> 數(shù)據(jù)類(lèi)型</b></p><p> typedef struct</p><p><b> {</b></p><p> int weig
29、ht; /*權(quán)值*/</p><p> int flag; /*標(biāo)記*/</p><p> int parent; /*雙親結(jié)點(diǎn)下標(biāo)*/</p><p> int leftChild; /*左孩子下標(biāo)*/</p><p> int rightChild; /*右孩子下標(biāo)*/
30、</p><p> }HaffNode; /*哈夫曼樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)*/</p><p> typedef struct</p><p><b> {</b></p><p> int bit[MaxN]; /*數(shù)組*/</p><p> int start;
31、 /*編碼的起始下標(biāo)*/</p><p> int weight; /*字符的權(quán)值*/</p><p> }Code; /*哈夫曼編碼結(jié)構(gòu)*/ </p><p> int weight[16]; /*用于存放權(quán)值*/</p><p> char s[30]; /* 存放
32、字符串*/</p><p><b> 函數(shù)調(diào)用</b></p><p> 各個(gè)算法實(shí)現(xiàn)的源程序</p><p> 1.字符串統(tǒng)計(jì)源程序:</p><p> int count(char * s,int * weight,int n)</p><p><b> {</b&g
33、t;</p><p> int i,j,temp,k=0,p;</p><p> for(i=0;i<n&&s[i]!='\0';i++)</p><p><b> {</b></p><p><b> temp=1;</b></p>&l
34、t;p> for(j=0;j<n;j++) /*遍歷相同的字母*/</p><p><b> {</b></p><p> if(s[j]==s[i]&&i!=j)</p><p><b> {</b></p><p><b> temp
35、++;</b></p><p> for(p=j;p<n;p++) /*刪除相同的字母*/</p><p> s[p]=s[p+1];</p><p><b> n--;</b></p><p><b> j--;</b></p><p>
36、;<b> }</b></p><p><b> }</b></p><p> weight[k++]=temp; /*temp 作為權(quán)值賦給weight數(shù)組*/</p><p><b> }</b></p><p> return i;
37、 /*返回權(quán)值個(gè)數(shù)*/</p><p><b> }</b></p><p> 2.哈夫曼樹(shù)建立源程序</p><p> void Haffman( int weight[],int n,HaffNode haffTree[])</p><p> /*建立葉結(jié)點(diǎn)個(gè)數(shù)為n,權(quán)值數(shù)組為weig
38、ht的哈夫曼樹(shù)haffTree*/</p><p><b> {</b></p><p> int i,j,m1,m2,x1,x2;</p><p> for(i=0;i<2*n-1;i++)</p><p><b> {</b></p><p><b&g
39、t; if(i<n)</b></p><p> haffTree[i].weight=weight[i];</p><p><b> else</b></p><p> haffTree[i].weight=0;</p><p> haffTree[i].parent=0;</p>
40、<p> haffTree[i].flag=0;</p><p> haffTree[i].leftChild=-1;</p><p> haffTree[i].rightChild=-1;</p><p><b> }</b></p><p> /*構(gòu)造哈夫曼樹(shù)haffTree的n-1個(gè)非葉結(jié)點(diǎn)
41、*/</p><p> for(i=0;i<n-1;i++)</p><p><b> {</b></p><p> m1=m2=MaxValue;</p><p><b> x1=x2=0;</b></p><p> for(j=0;j<n+i;j++
42、)</p><p><b> {</b></p><p> if(haffTree[j].weight<m1&&haffTree[j].flag==0)</p><p><b> {</b></p><p><b> m2=m1;</b></
43、p><p><b> x2=x1;</b></p><p> m1=haffTree[j].weight;</p><p><b> x1=j;</b></p><p><b> }</b></p><p><b> else</b
44、></p><p> if(haffTree[j].weight<m2&&haffTree[j].flag==0)</p><p><b> {</b></p><p> m2=haffTree[j].weight;</p><p><b> x2=j;</b>&
45、lt;/p><p><b> }</b></p><p><b> }</b></p><p> /*將找出的兩顆權(quán)值最小的子樹(shù)合并為一棵子樹(shù)*/</p><p> haffTree[x1].parent=n+i;</p><p> haffTree[x2].paren
46、t=n+i;</p><p> haffTree[x1].flag=1;</p><p> haffTree[x2].flag=1;</p><p> haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;</p><p> haffTree[n+i].leftChi
47、ld=x1;</p><p> haffTree[n+i].rightChild=x2;</p><p><b> }</b></p><p><b> } </b></p><p> 3.哈夫曼樹(shù)編碼函數(shù)</p><p> void HaffmanCode(Haf
48、fNode haffTree[],int n,Code haffCode[])</p><p> /*由n個(gè)結(jié)點(diǎn)的哈夫曼樹(shù)haffTree構(gòu)造哈夫曼編碼haffCode*/ </p><p><b> {</b></p><p> Code *cd=(Code *)malloc(sizeof(Code));</p><
49、p> int i,j,child,parent;</p><p> /*求n個(gè)結(jié)點(diǎn)的哈夫曼編碼*/</p><p> for(i=0;i<n;i++)</p><p><b> {</b></p><p> cd->start=n-1;</p><p> cd->
50、;weight=haffTree[i].weight;</p><p><b> child=i;</b></p><p> parent=haffTree[child].parent;</p><p> /*由葉結(jié)點(diǎn)向上直到根結(jié)點(diǎn)*/</p><p> while(parent!=0)</p>&
51、lt;p><b> {</b></p><p> if(haffTree[parent].leftChild==child)</p><p> cd->bit[cd->start]=0; /*左孩子分支編碼0*/</p><p><b> else</b></p><p&
52、gt; cd->bit[cd->start]=1; /*左孩子分支編碼1*/</p><p> cd->start--;</p><p> child=parent;</p><p> parent=haffTree[child].parent;</p><p><b> }</b>&l
53、t;/p><p> for(j=cd->start+1;j<n;j++)</p><p> haffCode[i].bit[j]=cd->bit[j]; /*保存每個(gè)葉結(jié)點(diǎn)的編碼*/</p><p> haffCode[i].start=cd->start; /*保存不等長(zhǎng)編碼的起始位置*/</p><p
54、> haffCode[i].weight=cd->weight; /*保存相應(yīng)字符的權(quán)值*/</p><p><b> }</b></p><p><b> }</b></p><p><b> 調(diào)試分析</b></p><p> 測(cè)試數(shù)據(jù)與輸出結(jié)果
55、與2.2結(jié)果相同。對(duì)過(guò)函數(shù)的分析:</p><p> 1.count 函數(shù):最壞情況下時(shí)間復(fù)雜度為O(n*n*n),調(diào)試時(shí)必須給定字符串的長(zhǎng)度,否則會(huì)輸出亂碼,這很不方便。只要在條件語(yǔ)句中加上”s[i]!='\0'” ,就能解決。同時(shí)對(duì)入含空格的字符串不能正確統(tǒng)計(jì),因?yàn)檩斎胱址且詓canf 的形式輸入,scanf 遇到空格自動(dòng)結(jié)束,將scanf 改為gets 即可,出現(xiàn)gets(s);<
56、;/p><p> 2.Haffman函數(shù)在最壞情況下計(jì)算的次數(shù)為2*n-1+(3*n-3)*n/2時(shí)間復(fù)雜度最壞情況下為O(n*n); Haffman函數(shù)在書(shū)寫(xiě)時(shí)要注意定義變量的位置。</p><p> 3.HaffmanCode函數(shù)在最壞情況下計(jì)算的次數(shù)為n*(3*n-1),時(shí)間復(fù)雜度為O(n*n); HaffmanCode函數(shù)在書(shū)寫(xiě)時(shí)要注意定義變量的位置。</p><
57、;p> 4.主函數(shù)的時(shí)間復(fù)雜度又輸入的字符串決定。曾在主函數(shù)中將printf("輸入:\n"); get(s),n=count(s,weight,30)放在Haffman(weight,n,myHaffTree);HaffmanCode(myHaffTree,n,myHaffCode)前面,出現(xiàn)很多問(wèn)題,像“HaffNode undefine”,”see undeclear HaffNode”等, 調(diào)整后
58、沒(méi)有問(wèn)題。主函數(shù)的時(shí)間復(fù)雜度由輸入的字符串決定。</p><p> 算法改進(jìn)設(shè)想:由于統(tǒng)計(jì)函數(shù)時(shí)間復(fù)雜度較高,是否降低其時(shí)間復(fù)雜度?統(tǒng)計(jì)函數(shù)中用到三個(gè)循環(huán),一個(gè)用于遍歷所有字符,一個(gè)用于尋找相同字符,一個(gè)用于刪除相同字符。而且三個(gè)循環(huán)嵌套,如果能減少循環(huán)的次數(shù)或者是由較少的循環(huán)嵌套,就能降低時(shí)間復(fù)雜度了。</p><p><b> 使用說(shuō)明</b></p&g
59、t;<p> 在寫(xiě)源程序前先將所要用到的函數(shù)都寫(xiě)好,以“haffman.h”保存起來(lái)。再書(shū)寫(xiě)主函數(shù),保存到相同的位置。在vc環(huán)境下,用“Build”里面的“complie”,進(jìn)行編譯 ,運(yùn)行。利用Debug中的F5,F10,F9,F11設(shè)置斷點(diǎn)等進(jìn)行調(diào)試。</p><p><b> 測(cè)試結(jié)果</b></p><p><b> 源程序<
60、;/b></p><p> 包含哈夫曼樹(shù)和圖,以哈夫曼樹(shù)為主要。圖在壓縮文件中</p><p><b> 哈夫曼樹(shù)</b></p><p> #include<stdio.h></p><p> #include<stdlib.h></p><p> #de
61、fine MaxValue 10000</p><p> #define MaxBit 4</p><p> #define MaxN 10</p><p> typedef struct</p><p><b> {</b></p><p> int weight; /*
62、權(quán)值*/</p><p> int flag; /*標(biāo)記*/</p><p> int parent; /*雙親結(jié)點(diǎn)下標(biāo)*/</p><p> int leftChild; /*左孩子下標(biāo)*/</p><p> int rightChild; /*右孩子下標(biāo)*/</p>&
63、lt;p> }HaffNode; /*哈夫曼樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)*/</p><p> typedef struct</p><p><b> {</b></p><p> int bit[MaxN]; /*數(shù)組*/</p><p> int start; /*編碼的起
64、始下標(biāo)*/</p><p> int weight; /*字符的權(quán)值*/</p><p> }Code; /*哈夫曼編碼結(jié)構(gòu)*/</p><p> void Haffman( int weight[],int n,HaffNode haffTree[])</p><p> /*建立葉結(jié)點(diǎn)個(gè)數(shù)為n,權(quán)
65、值數(shù)組為weight的哈夫曼樹(shù)haffTree*/</p><p><b> {</b></p><p> int i,j,m1,m2,x1,x2;</p><p> for(i=0;i<2*n-1;i++)</p><p><b> {</b></p><p>
66、;<b> if(i<n)</b></p><p> haffTree[i].weight=weight[i];</p><p><b> else</b></p><p> haffTree[i].weight=0;</p><p> haffTree[i].parent=0;&l
67、t;/p><p> haffTree[i].flag=0;</p><p> haffTree[i].leftChild=-1;</p><p> haffTree[i].rightChild=-1;</p><p><b> }</b></p><p> /*構(gòu)造哈夫曼樹(shù)haffTree的
68、n-1個(gè)非葉結(jié)點(diǎn)*/</p><p> for(i=0;i<n-1;i++)</p><p><b> {</b></p><p> m1=m2=MaxValue;</p><p><b> x1=x2=0;</b></p><p> for(j=0;j<
69、;n+i;j++)</p><p><b> {</b></p><p> if(haffTree[j].weight<m1&&haffTree[j].flag==0)</p><p><b> {</b></p><p><b> m2=m1;</b&
70、gt;</p><p><b> x2=x1;</b></p><p> m1=haffTree[j].weight;</p><p><b> x1=j;</b></p><p><b> }</b></p><p><b> el
71、se</b></p><p> if(haffTree[j].weight<m2&&haffTree[j].flag==0)</p><p><b> {</b></p><p> m2=haffTree[j].weight;</p><p><b> x2=j;<
72、;/b></p><p><b> }</b></p><p><b> }</b></p><p> /*將找出的兩顆權(quán)值最小的子樹(shù)合并為一棵子樹(shù)*/</p><p> haffTree[x1].parent=n+i;</p><p> haffTree[x
73、2].parent=n+i;</p><p> haffTree[x1].flag=1;</p><p> haffTree[x2].flag=1;</p><p> haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;</p><p> haffTree[n+i]
74、.leftChild=x1;</p><p> haffTree[n+i].rightChild=x2;</p><p><b> }</b></p><p><b> }</b></p><p> void HaffmanCode(HaffNode haffTree[],int n,Cod
75、e haffCode[])</p><p> /*由n個(gè)結(jié)點(diǎn)的哈夫曼樹(shù)haffTree構(gòu)造哈夫曼編碼haffCode*/ </p><p><b> {</b></p><p> Code *cd=(Code *)malloc(sizeof(Code));</p><p> int i,j,child,pare
76、nt;</p><p> /*求n個(gè)結(jié)點(diǎn)的哈夫曼編碼*/</p><p> for(i=0;i<n;i++)</p><p><b> {</b></p><p> cd->start=n-1;</p><p> cd->weight=haffTree[i].weigh
77、t;</p><p><b> child=i;</b></p><p> parent=haffTree[child].parent;</p><p> /*由葉結(jié)點(diǎn)向上直到根結(jié)點(diǎn)*/</p><p> while(parent!=0)</p><p><b> {</
78、b></p><p> if(haffTree[parent].leftChild==child)</p><p> cd->bit[cd->start]=0; /*左孩子分支編碼0*/</p><p><b> else</b></p><p> cd->bit[cd->st
79、art]=1; /*左孩子分支編碼1*/</p><p> cd->start--;</p><p> child=parent;</p><p> parent=haffTree[child].parent;</p><p><b> }</b></p><p> for(
80、j=cd->start+1;j<n;j++)</p><p> haffCode[i].bit[j]=cd->bit[j]; /*保存每個(gè)葉結(jié)點(diǎn)的編碼*/</p><p> haffCode[i].start=cd->start; /*保存不等長(zhǎng)編碼的起始位置*/</p><p> haffCode[i].weight=
81、cd->weight; /*保存相應(yīng)字符的權(quán)值*/</p><p><b> }</b></p><p><b> }</b></p><p> int count(char * s,int * weight,int n)</p><p><b> {</b>
82、;</p><p> int i,j,temp,k=0,p;</p><p> for(i=0;i<n&&s[i]!='\0';i++)</p><p><b> {</b></p><p><b> temp=1;</b></p><
83、;p> for(j=0;j<n;j++)</p><p><b> {</b></p><p> if(s[j]==s[i]&&i!=j)</p><p><b> {</b></p><p><b> temp++;</b></p&
84、gt;<p> for(p=j;p<n;p++)</p><p> s[p]=s[p+1];</p><p><b> n--;</b></p><p><b> j--;</b></p><p><b> }</b></p><
85、;p><b> }</b></p><p> weight[k++]=temp;</p><p><b> }</b></p><p><b> return i;</b></p><p><b> }</b></p><
86、;p> void main()</p><p><b> {</b></p><p> int i,j,n;</p><p> int weight[16];</p><p> char s[30];</p><p> HaffNode *myHaffTree;</p>
87、;<p> Code *myHaffCode;</p><p> printf(" ************輸入字符串************\n");</p><p><b> gets(s);</b></p><p> n=count(s,weight,30);</p&
88、gt;<p> myHaffTree=(HaffNode*)malloc(sizeof(HaffNode)*(2*n+1));</p><p> myHaffCode=(Code*)malloc(sizeof(Code)*n);</p><p> if(n>MaxN)</p><p><b> {</b></p
89、><p> printf("給出的n越界,修改MaxN!\n");</p><p><b> exit(1);</b></p><p><b> }</b></p><p> Haffman(weight,n,myHaffTree);</p><p>
90、 HaffmanCode(myHaffTree,n,myHaffCode);</p><p> /*輸出每個(gè)葉結(jié)點(diǎn)的哈夫曼編碼*/</p><p> for(i=0;i<n;i++)</p><p><b> {</b></p><p> printf(" W=
91、%d C= ",myHaffCode[i].weight);</p><p> for(j=myHaffCode[i].start+1;j<n;j++)</p><p> printf("%d",myHaffCode[i].bit[j]);</p><p> printf("\n"
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--哈夫曼編碼問(wèn)題的設(shè)計(jì)和實(shí)現(xiàn)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---哈夫曼編碼
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)----哈夫曼編碼
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)哈夫曼編碼
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--哈夫曼編碼
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---哈夫曼編碼
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)哈夫曼編碼
- 數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)之哈夫曼編碼
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--電文編碼譯碼(哈夫曼編碼)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--哈夫曼編碼和譯碼報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)電文編碼譯碼(哈夫曼編碼)
- 哈夫曼編碼譯碼數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---哈夫曼編碼器
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---哈夫曼編碼器
- 哈夫曼編碼譯碼數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-哈夫曼編碼譯碼器
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告----哈夫曼
- 哈夫曼樹(shù)_數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---哈夫曼編碼器
- 哈夫曼樹(shù)_數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
評(píng)論
0/150
提交評(píng)論