版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、<p> 學 年 設 計 報 告</p><p> 設計題目 哈夫曼樹的建立與實現(xiàn) </p><p> 作者姓名 </p><p> 所學專業(yè) 網(wǎng)絡工程 </
2、p><p> 指導教師 </p><p> 2011年8月23日</p><p><b> 學年設計任務書</b></p><p><b> 目 錄</b></p><p><b> 1 引 言
3、4</b></p><p><b> 2 需求分析4</b></p><p><b> 3 概要設計4</b></p><p> 3.1 設計思路及方案4</p><p> 3.2 模塊的設計及介紹5</p><p><b>
4、; 4 詳細設計8</b></p><p> 4.1 主調函數(shù)8</p><p> 4.2 建立HuffmanTree9</p><p> 4.3生成Huffman樹并寫入文件10</p><p> 5 調試與操作說明11</p><p> 5.1讀出文本11</p>
5、<p> 5.2輸出哈夫曼樹存儲結構的初態(tài)12</p><p> 5.3輸出哈夫曼樹存儲結構的終態(tài)12</p><p> 5.4輸出哈夫曼樹構成后的抽象圖14</p><p> 6學年設計總結與體會14</p><p> 7 參考文獻15</p><p><b> 8
6、 致謝15</b></p><p><b> 9 附錄15</b></p><p><b> 學年設計的主要內容</b></p><p><b> 1 引 言</b></p><p> 隨著當今信息技術的發(fā)展,為了方便和節(jié)省信息的存儲和傳遞速度,人們
7、便創(chuàng)建了哈夫曼編碼。哈夫曼編碼是將文件進行壓縮的一種壓縮方法。哈夫曼編碼的最大的功能是能夠用更少的內存空間來存儲更多的信息。若要對文件進行編碼則必須對其建立哈夫曼樹,其次對這個哈夫曼樹進行編碼。本學年設計的主要目標就是對如何建立哈夫曼樹和如何進行編碼的一個詳細介紹。</p><p><b> 2 需求分析</b></p><p> 問題描述:打開一篇英文文章,統(tǒng)
8、計該文章中每個字符出現(xiàn)的次數(shù),然后以它作為權值,對所有字符進行構建哈夫曼樹。</p><p> 問題補充:⑴ 從硬盤的一個文件里讀出一段英語文章; </p><p> ?、?統(tǒng)計這篇文章中的每個字符出現(xiàn)的次數(shù);</p><p> ?、?以字符出現(xiàn)字數(shù)作為權值,構建哈夫曼樹,并將哈夫曼樹的存儲結構的初態(tài)和終態(tài)進行輸出。</p><p><
9、;b> 具體介紹:</b></p><p> 在E盤中預先建立一個filel.txt文檔,在文檔中編輯一篇文章(大寫)。然后運行程序,調用fileopen()函數(shù)讀出該文章,顯示在界面;再調用jsq()函數(shù)對該文章的字符種類進行統(tǒng)計,并對每個字符的出現(xiàn)次數(shù)進行統(tǒng)計,并且在界面上顯示;然后以每個字符出現(xiàn)次數(shù)作為權值,調用ChuffmanTree()函數(shù)構建哈夫曼樹,并調用print1()和pr
10、int2()函數(shù)將哈夫曼的存儲結構的初態(tài)和終態(tài)進行輸出。</p><p><b> 3 概要設計</b></p><p> 3.1 設計思路及方案</p><p> 假設每種字符在電文中出現(xiàn)的次數(shù)為Wi,編碼長度為Li,電文中有n種字符,則電文編碼總長度為(W1*L1)+(W2*L2)+.......(Wi*Li)。若將此對應到二叉
11、樹上,Wi為葉結點,Li為根結點到葉結點的路徑長度。那么,(W1*L1)+(W2*L2)+.......(Wi*Li) 恰好為二叉樹上帶權路徑長度。以n種字符出現(xiàn)的頻率作權,構造一棵哈夫曼樹。</p><p> 該系統(tǒng)將實現(xiàn)以下幾大功能:從硬盤讀取字符串,建立哈夫曼樹,輸出哈夫曼樹的存儲結構的初態(tài)和終態(tài)。</p><p> 3.2 模塊的設計及介紹</p><p
12、> ?、?從硬盤讀取字符串</p><p> fileopen(參數(shù)){</p><p> //利用此函數(shù)進行對將文件打開</p><p><b> 實現(xiàn)命令;</b></p><p><b> 打印輸出;</b></p><p><b> }&l
13、t;/b></p><p> ?、?建立HuffmanTree</p><p> 通過三個函數(shù)來實現(xiàn):</p><p> void select(參數(shù)){ //從數(shù)組中選取兩個最小的字符作為//根節(jié)點的左右結點</p><p><b> 初始化;</b
14、></p><p><b> for{ </b></p><p><b> 接受命令;</b></p><p><b> 處理命令;</b></p><p><b> }</b></p><p> 說明:在ht[l.
15、......k]中選擇parent為0且權值最小的兩個根結點的算法</p><p> int jsq(參數(shù)){ </p><p> // 統(tǒng)計字符的種類及其個數(shù)</p><p><b> 初始化;</b></p><p><b> for{</b></p><p>
16、<b> 接受命令;</b></p><p><b> 處理命令;</b></p><p><b> }</b></p><p><b> }</b></p><p> 說明:統(tǒng)計字符串中各種字母的個數(shù)以及字符的種類</p><
17、;p> void ChuffmanTree(){初始化; //利用此函數(shù)構造出哈夫曼樹</p><p><b> for{</b></p><p><b> 接受命令;</b></p><p><b> 處理命令; </b></p>
18、<p><b> }</b></p><p><b> 輸出字符統(tǒng)計情況;</b></p><p><b> }</b></p><p><b> 說明:構造哈夫曼樹</b></p><p> ⑶ 輸出哈夫曼樹的存儲結構的初態(tài)和終態(tài)
19、</p><p> 分別調用print1()和print2()來實現(xiàn)</p><p> void print1(參數(shù)){ //輸出哈夫曼樹的初態(tài)</p><p><b> 初始化;</b></p><p><b> 輸出初態(tài);</b>&
20、lt;/p><p><b> }</b></p><p> 說明:輸出哈夫曼樹的初態(tài)</p><p> void print2(參數(shù)){ //輸出哈夫曼樹的終態(tài)</p><p><b> for{</b></p><p&
21、gt;<b> 輸出終態(tài);</b></p><p><b> }</b></p><p><b> }</b></p><p> 說明:輸出哈夫曼樹的終態(tài)</p><p> ?、?哈夫曼算法是通過對輸入數(shù)據(jù)的統(tǒng)計,根據(jù)其頻率來構造出權值,再通過對構造的權值進行建立哈夫
22、曼樹。并對其進行0和1的賦值,進而可以對每一個權值所對應的位置進行編碼。</p><p> 圖1哈夫曼算法實現(xiàn)流程圖</p><p> ?、?哈夫曼編碼是通過對構成最優(yōu)二叉樹的結點進行有規(guī)律的0和1的編碼,之后從根結點往下進行不斷地延伸,且在延伸的過程中會途徑所有的結點并記住每一個結點所對應的數(shù)值是0還是1并進行記錄,進而可以將每個途徑的結點所對應的數(shù)值記錄在數(shù)組中。直到所有的結點都遍
23、歷了一遍的時候,整個編碼的過程也就完成了,而此時數(shù)組中所存儲的0,1代碼便是每一個結點所對應的編碼</p><p> 圖2哈夫曼編碼流程圖</p><p> (6) 構造哈夫曼樹其實就是對以上已經(jīng)建立好的權值利用哈夫曼算法把它建立成一個最優(yōu)二叉樹即哈夫曼樹。其詳細的過程是通過比較權值域來選取最小的兩個權值,進行一步步的合并和刪除直到權值域中只剩下唯一的一個所謂的權值時,則整個哈夫曼樹
24、的構造便順利的完成了,而這唯一的一個權值便是整棵二叉樹的根結點。</p><p> 圖3哈夫曼樹構造流程圖</p><p><b> 4 詳細設計</b></p><p> 各模塊分別為主調函數(shù)、建立Huffman Tree、生成Huffman Tree并寫入文件。具體過程如下:</p><p><b>
25、; 4.1 主調函數(shù)</b></p><p> 代碼解釋:這是main函數(shù)里的各個函數(shù)調用情況。</p><p> fileopen(string); //從C盤內中讀取文件</p><p> num=jsq(string,cnt,str); //統(tǒng)計字符種類及各類字符出現(xiàn)的頻率<
26、;/p><p> DhuffmanTree(HT,cnt,str);</p><p> printf(“HuffmanTree的初態(tài):\n”);</p><p> print1(HT); //輸出哈夫曼樹的初態(tài)</p><p> ChuffmanTree(HT,HC,cnt,str);
27、 //建立哈夫曼樹</p><p> HuffmanEncoding(HT,HC); //生成哈夫曼樹</p><p> printf(“HuffmanTree的終態(tài):\n”);</p><p> print2(“HuffmanTree的終態(tài):\n”);</p><p> 4.2 建立HuffmanTre
28、e</p><p> 代碼解釋:該函數(shù)為在ht[l......k]中選擇patent為0且權值最小的根結點的算法,其序號為s1和s2.</p><p> void select (HuffmanTree T,int k,int &s1,int &s2){ //選取最小的根結點的函數(shù)</p><p><b> int i, j;<
29、;/b></p><p> s2=s1 //以s1和s2作為兩個最小節(jié)點的變量</p><p> for(i=1;i<=k;i++)</p><p> if(T[i].weight<min1 &&T[i].patent==0){ //利用此循環(huán)將最小結點
30、s1找到</p><p> j=i; min1=T[i].weight;</p><p><b> }</b></p><p> s1=j; min1=32767;</p><p> for(i=1;i<=k;i++) //利用此循環(huán)將另一個最小結點s2找到
31、</p><p> if(T[i].weight<min1 &&T[i].patent==0 &&i!=s1){</p><p> j=i; min1=T[i].weight;</p><p><b> }</b></p><p><b> s2=j;</b&
32、gt;</p><p><b> }</b></p><p> //對所有的字母進行統(tǒng)計種類和出現(xiàn)的次數(shù)</p><p> int jsp(char *s,int cnt[],char str[]){ //str[]存放所有字符,cnt[]來存放每種字</p><p> int i ,j
33、,k; //母的權值</p><p> char *p; //統(tǒng)計字符串中各種字母的個數(shù)以及字</p><p> int temp[27]; //存每種字母的個數(shù)</p><p>
34、for(i=1;i<=26;i++)</p><p> temp[i]=0;</p><p> for(p=s;*p!=’\0’;p++){</p><p> if(*p>=’A’&&*p<=’Z’)</p><p> k=*p-64; //找到該字
35、母的位置</p><p> temp[k]++;</p><p> } //統(tǒng)計各種字符的個數(shù)</p><p> for(i=1,j=0;i<=26;++i)</p><p> if(temp[i]!=0){</p><p><b&g
36、t; j++;</b></p><p> str[j]=i+64; //送對應字母到數(shù)組中</p><p> cnt[j]=temp[i]; //存入對應字母的權值</p><p><b> }</b></p><p
37、> return j; //j是輸入字母總數(shù)</p><p><b> }</b></p><p> 代碼解釋:下面函數(shù)用來構造哈夫曼樹HT。首先初始化哈夫曼樹,然后輸入前面統(tǒng)計的各個結點的權值,用for循環(huán)來構造哈夫曼樹。</p><p> void ChuffmanTre
38、e(HuffmanTree HT,HuffmanCode HC,int cnt[],char str[]){</p><p> int i,s1 ,s2;</p><p> for(i=1;i<=2*num-1;i++){ //初始化HT,2*num-1是指哈夫曼所有的節(jié)//點數(shù)目</p><p> HT[i].lchild
39、=0;HT[i].rchild=0;</p><p> HT[i].patent=0;HT[i].weight=0;</p><p><b> }</b></p><p> for(i=1;i<=num;i++) //輸入num個葉結點的權值</p><p> HT[i].w
40、eight=cnt[i];</p><p> for(i=num+1;i<=2*num-1;i++) {</p><p> select(HT,i-1,s1,s2);</p><p> HT[s1].patent=i;HT[s2].patent=i;</p><p> HT[i].lchild=s1;HT[i].rchild=s
41、2;</p><p> HT[i]weight=HT[s1].weight*HT[s2].weight;</p><p> } //在ht[l.....k]中選擇patent為0且權值最小的兩</p><p> //個根結點,其序號為s1和s2,i為雙親</p><p> f
42、or(i=0;i<=num;i++); //輸入字符集中字符</p><p> HC[i].ch=str[i]; //字符種類</p><p> i=1;while(i<=num)</p><p> printf(“字符%c次數(shù):%d”,HC[i].ch,cnt[i++]);</p>
43、<p> } //輸出統(tǒng)計的情況</p><p> 4.3生成Huffman樹并寫入文件</p><p> 代碼解釋:根據(jù)所輸入的字符構建哈夫曼樹T 。</p><p> void HuffmanEncoding (HuffmanT\ree T,HuffmanCode
44、H){</p><p> int c,p,i; //c和p分別指示t中孩子和雙親</p><p> char cd[n]; //臨時存放編碼串</p><p> int start; //指示碼在cd中的
45、起始位置</p><p> cd[num]=’\0’; //最后一位(第num個)放上串結束符</p><p> for(i=1;i<=num;++i){</p><p> start=num; //初始位置</p><p> c=i;
46、 //從葉子結點t[i]開始上溯</p><p> while((p=T[c].patent)>0){ //直至上溯到t[c]是樹根為止</p><p> Cd[--start]=(T[p].lchild==c) ?’0’:’1’;</p><p><b> c=p;<
47、;/b></p><p> } //若t[c]是t[p]的左孩子則生成0;否則生成1</p><p> Strcpy(H[i].bits,*cde[start]);</p><p> H[i].len=num-start;</p><p><b> }
48、</b></p><p><b> }</b></p><p> 代碼解釋:對str所代表的字符串進行構建哈夫曼樹并寫入文件。將翻譯的二進制碼寫入文本文件。</p><p> void coding(HuffmanCode HC, char *str) //對str所代表的字符串進行編碼并寫入文件</p>
49、<p><b> {</b></p><p><b> int i,j;</b></p><p> FILE *fp; //定義文件的指針</p><p> fp=fopen(“codefile.txt”,”w”);
50、 //打開文件的函數(shù)</p><p> while(*str){ //str為編碼的指針</p><p> for(i=1;i<=num;i++)</p><p> if(HC[i].ch==*str){</p><p> for(j=0;j<=HC[i].le
51、n;j++)</p><p> Fputc(HC[I].bits[j],fp);</p><p><b> break;</b></p><p><b> }</b></p><p><b> str++;</b></p><p> } fc
52、lose(fp); //將文件關閉</p><p><b> }</b></p><p> 5 調試與操作說明</p><p> 本次測試是通過建立一個名為file1.txt的文本文檔,其中有一篇英文字母的文章期望程序能將其讀出至界面并實現(xiàn)其它相關的功能。運行程序后,我們可以見到以下運行界
53、面。</p><p><b> 5.1讀出文本</b></p><p> 從file1.txt中讀取剛輸入的字符串并將其輸出到顯示屏如圖3所示。</p><p><b> 圖3讀出文本示意圖</b></p><p> 5.2輸出哈夫曼樹存儲結構的初態(tài)</p><p>
54、 下圖所示的為哈夫曼樹的初態(tài)。其中的每行數(shù)字分別表示字符的權值,字符的雙親,字符的左孩子,字符的右孩子,而本圖為哈夫曼樹的初始化如圖4所示。</p><p> 圖4哈夫曼樹的初態(tài)圖</p><p> 5.3輸出哈夫曼樹存儲結構的終態(tài)</p><p> 該圖為哈夫曼樹的終態(tài)。本圖顯示的是哈夫曼樹的構建以后的其字符的權值,雙親下標,左孩子,右孩子如圖5所示。&l
55、t;/p><p> 圖5 哈夫曼的終態(tài)圖1</p><p> 圖6 哈夫曼樹的終態(tài)圖2</p><p> 5.4輸出哈夫曼樹構成后的抽象圖</p><p> 此圖的構成首先是從權值域中選取最小的兩個權值,在此例中其分別為4、4. 通過這兩個最小的權值合并成為雙親結點8.之后在將8插入到權值域中,同時將此兩個最小的結點刪除。按照此方法一步步
56、的運行下去最終使得權值域中只剩下唯一的一個權值,至此最優(yōu)二叉樹便建立好了。并且這個最后的結點便是整棵二叉樹中的根結點,在本例子中456便是整棵最優(yōu)二叉樹的根結點。</p><p><b> 圖6哈夫曼樹示意圖</b></p><p><b> 學年設計總結與體會</b></p><p> 本學年設計的主要目的是要建立
57、一個哈夫曼樹并將其實現(xiàn)。通過構建哈夫曼編碼結構體來解決一系列因編碼帶來的復雜問題。同時利用幾個數(shù)組來存儲字符出現(xiàn)的頻率和種類。且在此過程中也用到了哈夫曼編碼函數(shù)和哈夫曼構建函數(shù)等,因而使得整個程序繁而不亂有條不紊的編輯和運行</p><p> 在此次的學年設計中,對于構建哈夫曼樹主要的思想是通過記錄文件中字符的頻率來作為在哈夫曼樹構造中必不可少的權值,再根據(jù)權值來構造哈夫曼樹,進而根據(jù)這棵建好的哈夫曼樹來進行字
58、符編碼,并將其存儲在所對應的文件中。 </p><p><b> 7 參考文獻 </b></p><p> [1] 嚴蔚敏,胡學剛.數(shù)據(jù)結構(C語言版)[M]. 清華大學出版社,2007</p><p> [2] 蘇仕華. 數(shù)據(jù)結構課程設計[M].機械工業(yè)出版社,2007</p><p> [3] 譚浩強. C
59、語言程序設計教程[M].高等教育出版社,2006</p><p><b> 8 致謝 </b></p><p> 對于老師詳細的指導和同學們的積極配合予以感謝,同時對各個參考文件的提供出版社以真誠的感謝。</p><p><b> 9 附錄 </b></p><p> # includ
60、e<stdio.h></p><p> # include<string.h></p><p> # include<stdlib.h></p><p> # include<fstream.h></p><p> //*********************類型相關變量的定義****
61、************************//</p><p> # define n 100 //葉子結點數(shù)</p><p> # define m 2*n-1 //哈夫曼樹中的結點數(shù)</p><p> typedef str
62、uct{</p><p> char ch; //相關的字母</p><p> char bits[9]; //存放編碼位串</p><p> int len;
63、 //該字母編碼的長度</p><p> }CodeNode; //編碼的類型</p><p> typedef CodeNode HuffmanCode[n+1]; //所有的葉子結點的編碼數(shù)組</p><p> typedef struct{</p&g
64、t;<p> int weight; //權值</p><p> int lchild,rchild,parent; //左右孩子及雙親指針</p><p> }HTNode; //
65、哈夫曼樹結點的類型</p><p> typedef HTNode HuffmanTree[m+1]; //0號單元不用</p><p> int num; //統(tǒng)計每種字母出現(xiàn)的次數(shù)和種類數(shù)目</p><p> // ******************
66、********建立HuffmanTree/**************************//</p><p> void select(HuffmanTree T,int k,int &s1,int &s2){</p><p> //在ht[1......k]中選擇parent為0且權</p><p> //值最小的兩個根結點的算法&l
67、t;/p><p> //其序號為s1和s2</p><p> int i,j;int min1=101; //min1的數(shù)字無何意義只是初始值之后//用來記錄權值,i為循環(huán)</p><p> //最小權值的下標,k為數(shù)組結點的總數(shù)</p><p> for(i=1;i<=k;i++
68、)</p><p> if (T[i].weight<min1 &&T[i].parent==0){</p><p> j=i; min1=T[i].weight; //賦權值</p><p><b> }</b></p><p> s1=j; min1=
69、32767; //找到權值最小的其中之一</p><p> for (i=1; i<=k; i++)</p><p> if(T[i].weight<min1 &&T[i].parent==0 && i!=s1)//不讓s2和s1的數(shù)組下標重合</p><p><
70、;b> {</b></p><p> j=i ; min1=T[i].weight; //找到權值最小的其中之一</p><p><b> }</b></p><p><b> s2=j ;</b></p><p><b> }
71、</b></p><p> int jsq(char *s, int cnt [],char str[]) //str[]存放所有字符,cnt[]來存放每種字//母的權值</p><p> { //統(tǒng)計字符串中各種字母的個數(shù)以及字//符的種類,s為數(shù)組&
72、lt;/p><p><b> //的首地址指針</b></p><p> int i,j,k;</p><p><b> char *p;</b></p><p> int temp[27]; //存每種字母的個數(shù)</p>
73、<p> for(i=1;i<=26;i++)</p><p> temp[i]=0; //初始化為0</p><p> for(p=s;*p!='\0';p++)</p><p> {
74、 </p><p><b> {</b></p><p> if(*p>='A' &&*p<='Z' ) </p><p> k=*p-64;
75、 //找到字母在數(shù)組中的下標</p><p> temp[k]++; //字母個數(shù)累加</p><p><b> }</b></p><p><b> }</b></p><p> for(i=1,j=0;i<=26;++i)
76、 </p><p> if( temp[i] !=0)</p><p><b> {</b></p><p> j++; //j為字母的總數(shù)</p><p> str[j]=i+64; //
77、送對應的字母到數(shù)組中</p><p> cnt[j]=temp[i]; //存入對應字母的權值</p><p><b> }</b></p><p> return j; //j是輸入字母總數(shù)</p>&
78、lt;p><b> }</b></p><p> void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt[], char str[])</p><p> { //構造哈夫曼樹HT</p><p&
79、gt; int i,s1,s2;</p><p> for(i=1;i<=2*num-1;i++)</p><p> { //初始化HT,2*num-1是指哈夫曼樹所</p><p><b> //有的結點數(shù)目</b></p>&l
80、t;p> HT[i].lchild=0;HT[i].rchild=0; //初始化為根結點</p><p> HT[i].parent=0;HT[i].weight=0; //初始化為根結點</p><p><b> }</b></p><p> for(i=1;i<=num
81、;i++) //輸入num個葉子結點的權值</p><p> HT[i].weight=cnt[i]; //賦權值</p><p> for(i=num+1;i<=2*num-1;i++)</p><p><b> {</b></p>
82、;<p> select(HT,i-1,s1,s2); //在ht[1.....k]中選擇parent為0且權值 </p><p> //最小的兩個根結點 </p><p> HT[s1].parent=i;HT[s2].parent=i; //其序
83、號為s1和s2</p><p> HT[i].lchild=s1;HT[i].rchild=s2; //i為雙親</p><p> HT[i].weight=HT[s1].weight+HT[s2].weight;</p><p><b> }</b></p><p> for(i=0;i&
84、lt;=num;i++) //輸入字符集的中字符</p><p> HC[i].ch=str[i]; //字符的種類</p><p> i=1;while(i<=num)</p><p> printf("字符%c次數(shù):%d\n",HC[
85、i].ch,cnt[i++]);</p><p><b> }</b></p><p> //*************************生成Huffman樹并寫入文件*****************//</p><p> void HuffmanEncoding(HuffmanTree T,HuffmanCode H)</
86、p><p> { //根據(jù)哈夫曼樹T求哈夫曼編碼H</p><p> int c,p,i; //c和p分別指示t中孩子和雙親</p><p> char cd[n];
87、 //臨時存放編碼串,n為字母總數(shù)</p><p> int start; //指示碼在cd中的起始位置</p><p> cd[num]='\0'; //num為葉子結點的總數(shù)
88、 </p><p> for(i=1;i<=num;++i) //對所有的葉子節(jié)點進行大循環(huán)的編碼</p><p><b> {</b></p><p> start=num; //從最后的葉子結點上
89、溯編碼 </p><p> c=i; //從葉子結點t[i]開始上溯</p><p> while((p=T[c].parent)>0)</p><p> { //直至上溯到t[c]是樹根為止</p>
90、<p> //若t[c]是t[p]的左孩子,則生成0,否則//生成1</p><p> cd[--start]=(T[p].lchild==c)?'0':'1';</p><p> c=p; //使得可以進行循環(huán)</p><p><b> }&
91、lt;/b></p><p> strcpy(H[i].bits,&cd[start]);</p><p> H[i].len=num-start;</p><p><b> }</b></p><p><b> }</b></p><p> void
92、 coding(HuffmanCode HC,char *str)</p><p> { //對str所代表的字符串進行構建哈夫曼</p><p><b> //樹并寫入文件</b></p><p> int i,j; </p>&
93、lt;p> FILE*fp; //定義文件的指針</p><p> fp=fopen("codefile.txt","w"); //打開文件 的函數(shù)</p><p> while (*str) </p><p>&l
94、t;b> {</b></p><p> for(i=1;i<=num;i++)</p><p> if(HC[i].ch==*str){</p><p> for(j=0;j<=HC[i].len;j++)</p><p> fputc(HC[i].bits[j],fp);</p><
95、;p><b> break;</b></p><p><b> }</b></p><p><b> str++;</b></p><p> }fclose(fp); //關閉文件</p><p><
96、;b> }</b></p><p> //***************輸出HuffmanTree存儲結構*********************//</p><p> void print1(HuffmanTree HT)</p><p><b> {</b></p><p><b&g
97、t; int x;</b></p><p> for(x=1;x<=2*num-1;x++)</p><p><b> {</b></p><p> HT[x].parent=0;</p><p> HT[x].lchild=0;</p><p> HT[x].rch
98、ild=0;</p><p> printf("%11d %d\t%d\n",HT[x].weight,HT[x].parent,HT[x].lchild,HT[x].rchild);</p><p><b> }</b></p><p> printf("------------------------
99、-----\n");</p><p><b> }</b></p><p> void print2(HuffmanTree HT)</p><p><b> {</b></p><p><b> int k;</b></p><p>
100、; for(k=1;k<=2*num-1;k++)</p><p><b> {</b></p><p> printf("%d\t%d\t%d\n",HT[k].weight,HT[k].parent,HT[k].lchild,HT[k].rchild);</p><p><b> }</b&
101、gt;</p><p> printf("--------------------------\n");</p><p><b> }</b></p><p> void DhuffmanTree(HuffmanTree HT,int cnt[],char str[]){ //構造哈夫曼樹 </p>&
102、lt;p><b> int i;</b></p><p> //char x;</p><p> for (i=1;i<=num;i++){ //輸入num個葉結點的權值 </p><p> HT[i].weight=cnt[i];</p>&
103、lt;p> if(i>=str[i]){</p><p> HT[i].weight=(char)'*';</p><p><b> }</b></p><p><b> }</b></p><p><b> }</b></p>
104、<p> //**************************打開文本************************//</p><p> int fileopen(char string[]){ // string[]為字母的首地址 </p><p> FILE *fp;
105、 //文件的指針</p><p> if((fp=fopen("file1.txt","r"))==NULL) //判斷該文件是否為空,若是則判空 </p><p> printf("不能打開文件!\n");</p><p&g
106、t; while(fgets(string,100 ,fp)!=NULL)</p><p> printf("%s\n",string); //將所有的字母進行輸出</p><p> fclose(fp); //關閉文件</p
107、><p><b> return 0;</b></p><p><b> }</b></p><p> void main (){</p><p> char string[500]; //用來存儲所有的字母</p>&
108、lt;p> char*s,str[27];</p><p> int cnt[27]; //用來存儲字母的權值</p><p> HuffmanTree HT; //定義哈夫曼樹</p><p> HuffmanCode H
109、C; //定義哈夫曼結點</p><p> printf("讀出文本為:\n");</p><p> fileopen(string); //打開字符串所在地文件</p><p> num=jsq(string,cnt,s
110、tr); //統(tǒng)計字符的種類及各類字符出現(xiàn)的//頻率</p><p> DhuffmanTree(HT,cnt,str); //構造哈夫曼樹 </p><p> printf("-------------------\n");</p><p>
111、printf("HuffmanTree的初態(tài):\n"); //輸出哈夫曼的初態(tài)</p><p> print1(HT); </p><p> ChuffmanTree(HT,HC,cnt,str); //建立哈夫曼樹</p><p> HuffmanEncoding(
112、HT,HC); //生成哈夫曼樹</p><p> coding(HC,string); //建立電文哈夫曼編碼文件</p><p> printf("--------------------------------\n");</p><p>
113、 printf("HuffmanTree的終態(tài):\n"); //輸出哈夫曼的終態(tài)</p><p> print2(HT);</p><p> printf("*************************\n");</p><p><b> }</b></p
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
評論
0/150
提交評論