版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領
文檔簡介
1、<p> JAVA語言 實驗報告</p><p> 學 院 計算機工程學院 班 級 計算1013 </p><p> 姓 名 xxxx 學 號 201081xxxx</p><p> 成 績 指導老師 xxxx</p><p> 201
2、2年09月03日</p><p><b> 目 錄</b></p><p><b> 目錄1</b></p><p> 1 課程設計的目的和意義2</p><p><b> 2 需求分析3</b></p><p> 3 系統(tǒng)(項目)
3、設計5</p><p> ?、僭O計思路及方案………………………………………………5</p><p> ?、谀K的設計及介紹……………………………………………5</p><p> ?、壑饕K程序流程圖…………………………………………8</p><p><b> 4 系統(tǒng)實現(xiàn)11</b></p><
4、;p> ?、僦髡{(diào)函數(shù)…………..…………………………..……………..12</p><p> ②建立HuffmanTree……………………………………………12</p><p> ?、凵蒆uffman編碼并寫入文件……………………………..15</p><p> ④電文譯碼……………………………………………………..16</p><p
5、><b> 5 系統(tǒng)調(diào)試17</b></p><p><b> 參考文獻20</b></p><p><b> 附錄 源程序21</b></p><p> 1 課程設計的目的和意義</p><p> 在當今信息爆炸時代,如何采用有效的數(shù)據(jù)壓縮技術來節(jié)省數(shù)據(jù)
6、文件的存儲空間和計算機網(wǎng)絡的傳送時間已越來越引起人們的重視。哈夫曼編碼正是一種應用廣泛且非常有效的數(shù)據(jù)壓縮技術。</p><p> 哈夫曼編碼的應用很廣泛,利用哈夫曼樹求得的用于通信的二進制編碼稱為哈夫曼編碼。樹中從根到每個葉子都有一條路徑,對路徑上的各分支約定:指向左子樹的分支表示“0”碼,指向右子樹的分支表示“1”碼,取每條路徑上的“0”或“1”的序列作為和各個對應的字符的編碼,這就是哈夫曼編碼。</
7、p><p> 通常我們把數(shù)據(jù)壓縮的過程稱為編碼,解壓縮的過程稱為解碼。電報通信是傳遞文字的二進制碼形式的字符串。但在信息傳遞時,總希望總長度盡可能最短,即采用最短碼。</p><p> 作為信息管理專業(yè)的學生,我們應該很好的掌握這門技術。在課堂上,我們能過學到許多的理論知識,但我們很少有過自己動手實踐的機會!課程設計就是為解決這個問題提供了一個平臺。</p><p>
8、; 在課程設計過程中,我們每個人選擇一個課題,認真研究,根據(jù)課堂講授內(nèi)容,借助書本,自己動手實踐。這樣不但有助于我們消化課堂所講解的內(nèi)容,還可以增強我們的獨立思考能力和動手能力;通過編寫實驗代碼和調(diào)試運行,我們可以逐步積累調(diào)試C程序的經(jīng)驗并逐漸培養(yǎng)我們的編程能力、用計算機解決實際問題的能力。</p><p> 在課程設計過程中,我們不但有自己的獨立思考,還借助各種參考文獻來幫助我們完成系統(tǒng)。更為重要的是,我們
9、同學之間加強了交流,在對問題的認識方面可以交換不同的意見。同時,師生之間的互動也隨之改善,我們可以通過具體的實例來從老師那學到更多的實用的知識。</p><p> 數(shù)據(jù)結(jié)構課程具有比較強的理論性,同時也具有較強的可應用性和實踐性。課程設計是一個重要的教學環(huán)節(jié)。我們在一般情況下都能夠重視實驗環(huán)節(jié),但是容易忽略實驗的總結(jié),忽略實驗報告的撰寫。通過這次實驗讓我們明白:作為一名大學生必須嚴格訓練分析總結(jié)能力、書面表達能
10、力。需要逐步培養(yǎng)書寫科學實驗報告以及科技論文的能力。只有這樣,我們的綜合素質(zhì)才會有好的提高。</p><p><b> 2 需求分析</b></p><p> 課 題:哈夫曼編碼譯碼器系統(tǒng)</p><p> 問題描述:打開一篇英文文章,統(tǒng)計該文章中每個字符出現(xiàn)的次數(shù),然后以它們作為權值,對每一個字符進行編碼,編碼完成后再對其編碼進行
11、譯碼。</p><p> 問題補充:1. 從硬盤的一個文件里讀出一段英語文章;</p><p> 2. 統(tǒng)計這篇文章中的每個字符出現(xiàn)的次數(shù);</p><p> 3. 以字符出現(xiàn)字數(shù)作為權值,構建哈夫曼樹,并將哈夫曼樹的存儲結(jié)構的初態(tài)和終態(tài)進行輸出;</p><p> 4. 對每個字符進行編碼并將所編碼寫入文件然后對所編碼進行破譯。&l
12、t;/p><p> 具體介紹:在本課題中,我們在硬盤E盤中預先建立一個file1.txt文檔,在里面編輯一篇文章(大寫)。然后運行程序,調(diào)用fileopen()函數(shù)讀出該文章,顯示在界面;再調(diào)用jsq()函數(shù)對該文章的字符種類進行統(tǒng)計,并對每個字符的出現(xiàn)次數(shù)進行統(tǒng)計,并且在界面上顯示;然后以每個字符出現(xiàn)次數(shù)作為權值,調(diào)用ChuffmanTree()函數(shù)構建哈夫曼樹;并調(diào)用print1()和print2()函數(shù)將哈夫
13、曼的存儲結(jié)構的初態(tài)和終態(tài)進行輸出。然后調(diào)用HuffmanEncoding()函數(shù)對哈夫曼樹進行編碼,調(diào)用coding()函數(shù)將編碼寫入文件;再調(diào)用decode()對編碼進行譯碼,再輸出至界面。至此,整個工作就完成了。</p><p> 測試數(shù)據(jù):例如從文本中讀到文章為:IAMASTUDENT。</p><p><b> 則效果如下:</b></p>
14、<p> IAMASTUDENT</p><p> --------------------------------------</p><p> HuffmanTree的初態(tài):</p><p> 2 0 0 0</p><p> 1 0 0 0</
15、p><p> 1 0 0 0</p><p> 1 0 0 0</p><p> 1 0 0 0</p><p> 1 0 0 0</p><p> 1 0
16、 0 0</p><p> 2 0 0 0</p><p> 1 0 0 0</p><p> - 0 0 0</p><p> - 0 0 0</p><p>
17、 - 0 0 0</p><p> - 0 0 0</p><p> - 0 0 0</p><p> - 0 0 0</p><p> - 0 0 0</p&
18、gt;<p> - 0 0 0</p><p> --------------------------------------</p><p><b> 字符A次數(shù):2</b></p><p><b> 字符D次數(shù):1</b></p><p>
19、<b> 字符E次數(shù):1</b></p><p><b> 字符I 次數(shù):1</b></p><p><b> 字符M次數(shù):1</b></p><p><b> 字符N 次數(shù):1</b></p><p><b> 字符S 次數(shù):1<
20、;/b></p><p><b> 字符T次數(shù):2</b></p><p><b> 字符U次數(shù):1</b></p><p> --------------------------------------</p><p> HuffmanTree的終態(tài):</p><
21、p> 2 13 0 0</p><p> 1 10 0 0</p><p> 1 10 0 0</p><p> 1 11 0 0</p><p> 1 11 0
22、 0</p><p> 1 12 0 0</p><p> 1 12 0 0</p><p> 2 14 0 0</p><p> 1 13 0 0</p><p> 2
23、 14 2 3</p><p> 2 15 4 5</p><p> 2 15 6 7</p><p> 3 16 9 1</p><p> 4 16 8 10<
24、;/p><p> 4 17 11 12</p><p> 7 17 13 14</p><p> 11 0 15 16</p><p> --------------------------------------</p><
25、;p><b> 譯碼后的字符串:</b></p><p> IAMASTUDENT</p><p> **********************************************************</p><p> Press any key to continue</p><p>
26、 三維谷屋 www.3vgw.com</p><p> 3 系統(tǒng)(項目)設計</p><p> (1)設計思路及方案</p><p> 本課題是用最優(yōu)二叉樹即哈夫曼樹來實現(xiàn)哈夫曼編碼譯碼器的功能。假設每種字符在電文中出現(xiàn)的次數(shù)為Wi,編碼長度為Li,電文中有n種字符,則電文編碼總長度為(W1*L1)+(W2*L2)+…+(Wi*Li)。若將此對應到二叉樹上,W
27、i為葉結(jié)點,Li為根結(jié)點到葉結(jié)點的路徑長度。那么,(W1*L1)+(W2*L2)+…+(Wi*Li)恰好為二叉樹上帶權路徑長度。 三維谷屋 www.3vgw.com</p><p> 因此,設計電文總長最短的二進制前綴編碼,就是以n種字符出現(xiàn)的頻率作權,構造一棵哈夫曼樹,此構造過程稱為哈夫曼編碼。</p><p> 該系統(tǒng)將實現(xiàn)以下幾大功能:從硬盤讀取字符串,建立哈夫曼樹,輸出哈夫曼樹
28、的存儲結(jié)構的初態(tài)和終態(tài),輸出各種字符出現(xiàn)的次數(shù)以及哈夫曼編碼的譯碼等。 </p><p> (2)模塊的設計及介紹</p><p><b> ?、購挠脖P讀取字符串</b></p><p> fileopen(參數(shù))</p><p><b> {</b></p><p
29、><b> 實現(xiàn)命令;</b></p><p><b> 打印輸出;</b></p><p><b> }</b></p><p> ?、诮uffmanTree</p><p> 通過三個函數(shù)來實現(xiàn):</p><p> void s
30、elect(參數(shù))</p><p><b> {</b></p><p><b> 初始化;</b></p><p><b> for</b></p><p><b> { </b></p><p><b> 接
31、受命令;</b></p><p><b> 處理命令;</b></p><p><b> }</b></p><p><b> }</b></p><p> 說明:在ht[1....k]中選擇parent為0且權值最小的兩個根結(jié)點的算法</p>
32、<p> int jsq(參數(shù))</p><p><b> {</b></p><p><b> 初始化;</b></p><p><b> for</b></p><p><b> {</b></p><p>
33、;<b> 接受命令;</b></p><p><b> 處理命令;</b></p><p><b> } </b></p><p><b> }</b></p><p> 說明:統(tǒng)計字符串中各種字母的個數(shù)以及字符的種類</p>&
34、lt;p> void ChuffmanTree()</p><p><b> {</b></p><p><b> 初始化;</b></p><p><b> for</b></p><p><b> { </b></p>&
35、lt;p><b> 接受命令;</b></p><p><b> 處理命令;</b></p><p><b> }</b></p><p><b> 輸出字符統(tǒng)計情況;</b></p><p><b> }</b>&l
36、t;/p><p><b> 說明:構造哈夫曼樹</b></p><p> ?、圯敵龉蚵鼧涞拇鎯Y(jié)構的初態(tài)和終態(tài)</p><p> 分別調(diào)用print1()和print2()來實現(xiàn)</p><p> void print1(參數(shù))</p><p><b> {</b>&l
37、t;/p><p><b> 初始化;</b></p><p><b> 輸出初態(tài);</b></p><p><b> }</b></p><p> 說明:輸出哈夫曼樹的初態(tài)</p><p> void print2(參數(shù))</p>&
38、lt;p><b> {</b></p><p><b> for</b></p><p><b> {</b></p><p><b> 輸出終態(tài);</b></p><p><b> }</b></p>
39、<p><b> }</b></p><p> 說明:輸出哈夫曼樹的終態(tài)</p><p><b> ?、芄蚵幋a和譯碼</b></p><p> void HuffmanEncoding(參數(shù))</p><p><b> {</b></p>&
40、lt;p><b> 定義變量;</b></p><p><b> {</b></p><p><b> 處理命令;</b></p><p><b> }</b></p><p><b> }</b></p>
41、<p><b> 說明:哈夫曼編碼</b></p><p> char*decode(參數(shù))</p><p><b> {</b></p><p><b> 定義變量;</b></p><p><b> while</b></
42、p><p><b> {</b></p><p><b> 接受命令;</b></p><p><b> 處理命令;</b></p><p><b> }</b></p><p><b> }</b>&l
43、t;/p><p><b> 說明:哈夫曼譯碼</b></p><p> (3)主要模塊程序流程圖</p><p> 下面介紹三個主要的程序模塊流程圖:</p><p><b> ?、僦骱瘮?shù)流程圖:</b></p><p><b> 圖3.1</b>&
44、lt;/p><p><b> 流程圖注釋:</b></p><p> 該圖比較簡單,主要是調(diào)用各個函數(shù)模塊,首先代開已經(jīng)存在的文件,然后統(tǒng)計總的字符數(shù)以及出現(xiàn)的各個字符和頻率。然后才開始建立哈夫曼樹,接著在哈夫曼樹的基礎上對其進行編碼,編碼之后才是譯碼。最后輸出結(jié)束。</p><p><b> ?、跇嬙旃蚵鼧洌?lt;/b>&
45、lt;/p><p><b> 圖3.2</b></p><p><b> 流程圖注釋:</b></p><p> 該圖是表示構造哈夫曼樹的過程。首先輸入num個葉結(jié)點的權值,當i=num是循環(huán)結(jié)束。然后進行哈夫曼樹的構建,當i=2*num-1是循環(huán)結(jié)束。最后輸出所得到的字符統(tǒng)計情況。</p><p&g
46、t; 三維谷屋返利 www.3vgw.com</p><p><b> ?、酃蚵幋a:</b></p><p><b> 圖3.3</b></p><p><b> 流程圖解釋:</b></p><p> 該流程圖表四哈夫曼編碼情況。首先初始化,Cd[--start
47、]=0,start=num。然后進行</p><p> 編碼,使用了一個三目運算符。cd[--start]=(T[p].lchild==c) ? '0' : '1',即當cd[--start]=T[p].lchild= =c時,cd[--start]=0;當cd[--start]=T[p].lchild!= =c時,cd[--start]=1。這個編碼循環(huán)一直到i=num時結(jié)束。
48、</p><p><b> 4 系統(tǒng)實現(xiàn)</b></p><p> 各模塊關鍵代碼及算法的解釋:</p><p><b> 主調(diào)函數(shù) </b></p><p> 代碼解釋:這是main函數(shù)里的各個函數(shù)調(diào)用情況。</p><p> fileopen(string);
49、 //從硬盤中讀取文件</p><p> num=jsq(string,cnt,str); //統(tǒng)計字符種類及各類字符出現(xiàn)的頻率</p><p> DhuffmanTree(HT,cnt,str); </p><p> printf("HuffmanTree的初態(tài):\n");</p><p>
50、; print1(HT); //輸出哈夫曼樹的初態(tài)</p><p> ChuffmanTree(HT,HC,cnt,str);//建立哈夫曼樹 </p><p> HuffmanEncoding(HT,HC); //生成哈夫曼編碼</p><p> printf("HuffmanTree的終態(tài):\n&q
51、uot;);</p><p> print2(HT); //輸出哈夫曼樹的終態(tài)</p><p> s=decode(HC); //讀編碼文件譯碼 </p><p> printf("譯碼后的字符串:\n");</p><p> printf("%
52、s\n",s); //輸出譯碼后的字符串</p><p> 建立HuffmanTree</p><p> 代碼解釋:該函數(shù)為在ht[1....k]中選擇parent為0且權值最小的兩個根結(jié)點的算法,其序號為s1和s2。</p><p> void select(HuffmanTree T,int k,int &s1,int
53、 &s2)</p><p><b> { </b></p><p><b> int i,j;</b></p><p> int min1=101;</p><p> for(i=1;i<=k;i++)</p><p> if(T[i].weight&
54、lt;min1 &&T[i].parent==0) </p><p><b> {</b></p><p> j=i;min1=T[i].weight;</p><p><b> }</b></p><p> s1=j;min1=32767;</p><p
55、> for (i=1;i<=k;i++)</p><p> if(T[i].weight<min1 && T[i].parent==0 && i!=s1)</p><p><b> {</b></p><p> j=i;min1=T[i].weight;</p><p
56、><b> }</b></p><p><b> s2=j;</b></p><p><b> }</b></p><p> 代碼解釋:下面函數(shù)用來統(tǒng)計字符串中各種字母的個數(shù)以及字符的種類。當字符在A和Z之間時即被計數(shù),并用str[j]保存字母到數(shù)組中,用cnt[j]統(tǒng)計每種字符個數(shù)。j
57、返回總共讀取的字符數(shù)目。</p><p> int jsq(char *s,int cnt[],char str[])</p><p><b> { </b></p><p> int i,j,k; </p><p><b> char *p;</b></p><p&g
58、t; int temp[27]; </p><p> for(i=1;i<=26;i++)</p><p> temp[i]=0; </p><p> for(p=s; *p!='\0';p++) </p><p><b> {</b></p><p>&l
59、t;b> { </b></p><p> if(*p>='A'&&*p<='Z')</p><p><b> k=*p-64;</b></p><p> temp[k]++;</p><p><b> }<
60、/b></p><p> } //統(tǒng)計各種字符的個數(shù)</p><p> for(i=1,j=0;i<=26;++i)</p><p> if(temp[i]!=0 ) </p><p><b> {</b></p>
61、<p><b> j++;</b></p><p> str[j]=i+64; //送對應的字母到數(shù)組中</p><p> cnt[j]=temp[i]; //存入對應字母的權值</p><p> } </p><p>
62、return j; //j是輸入字母總數(shù)</p><p><b> }</b></p><p> 代碼解釋:下面函數(shù)用來構造哈夫曼樹HT。首先初始化哈夫曼樹,然后輸入前面統(tǒng)計的各結(jié)點的權值,用for循環(huán)來構造哈夫曼樹。</p><p> void ChuffmanTree(HuffmanTree HT,HuffmanC
63、ode HC,int cnt[],char str[])</p><p><b> {</b></p><p> int i,s1,s2;</p><p> for(i=1;i<=2*num-1;i++)//初始化HT,2*num-1是指哈夫曼</p><p><b> //所有的結(jié)點數(shù)目<
64、/b></p><p><b> {</b></p><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>
65、 for(i=1;i<=num;i++) //輸入num個葉結(jié)點的權值</p><p> HT[i].weight=cnt[i];</p><p> for(i=num+1;i<=2*num-1;i++)</p><p><b> {</b></p><p> select(HT,i-1,s1
66、,s2);</p><p> HT[s1].parent=i;HT[s2].parent=i;</p><p> HT[i].lchild=s1; HT[i].rchild=s2;</p><p> HT[i].weight=HT[s1].weight+HT[s2].weight;</p><p><b> }</b&
67、gt;</p><p> //在ht[1....k]中選擇parent為0且權值最小</p><p> //的兩個根結(jié)點,其序號為s1和s2,i為雙親</p><p> for(i=0;i<=num;i++) //輸入字符集的中字符</p><p> HC[i].ch=str[i]; //字符的種類</
68、p><p> i=1;while(i<=num)</p><p> printf("字符%c次數(shù):%d\n",HC[i].ch,cnt[i++]);</p><p> } //輸出統(tǒng)計的情況</p><p> 生成Huffman編碼并寫入文件</p&g
69、t;<p> 代碼解釋:根據(jù)哈夫曼樹T求哈夫曼編碼H。</p><p> void HuffmanEncoding(HuffmanTree T,HuffmanCode H)</p><p><b> {</b></p><p> int c,p,i; //c和p分別指示t中孩子和雙親&l
70、t;/p><p> char cd[n]; //臨時存放編碼串</p><p> int start; //指示碼在cd中的起始位置</p><p> cd[num]='\0'; //最后一位(第num個)放上串結(jié)束符</p><
71、p> for(i=1;i<=num;++i)</p><p><b> {</b></p><p> start=num; //初始位置</p><p> c=i; //從葉子結(jié)點t[i]開始上溯</p><p> while((p
72、=T[c].parent)>0) //直至上溯到t[c]是樹根為止</p><p><b> {</b></p><p> cd[--start]=(T[p].lchild==c) ? '0' : '1';</p><p><b> c=p;</b></p><
73、;p> } //若t[c]是t[p]的左孩子</p><p> //則生成0;否則生成底碼1</p><p> strcpy(H[i].bits,&cd[start]);</p><p> H[i].len=num-start;</p><p><b> }<
74、;/b></p><p><b> }</b></p><p> 代碼解釋:對str所代表的字符串進行編碼并寫入文件。將翻譯的二進制碼寫入文本文件。</p><p> void coding(HuffmanCode HC ,char *str)</p><p><b> { </b>&
75、lt;/p><p><b> int i,j;</b></p><p><b> FILE *fp;</b></p><p> fp=fopen("codefile.txt","w");</p><p> while(*str)</p>&l
76、t;p><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);</
77、p><p><b> break;</b></p><p><b> }</b></p><p><b> str++;</b></p><p> }fclose(fp);</p><p><b> }</b></p&g
78、t;<p><b> 電文譯碼</b></p><p> 代碼解釋:代碼文件codefile.txt的譯碼,將翻譯的二進制碼譯成原來的字符。</p><p> char*decode(HuffmanCode HC)</p><p> {FILE *fp;</p><p> char str[25
79、4]; //假設遠文本文件不超過254個字符</p><p><b> char *p;</b></p><p> static char cd[n+1];</p><p> int i,j,k=0,cjs;</p><p> fp=fopen("codefile.txt&qu
80、ot;,"r");//一只讀的方式打開文本文檔//codefile.txt</p><p> while(!feof(fp)) //feof(fp)判斷文件是否真正結(jié)束,</p><p> //feof(fp)=1時文件結(jié)束</p><p><b> {</b></p><p
81、><b> cjs=0;</b></p><p> for(i=0;i<num && cjs==0 && !feof(fp);i++)</p><p><b> {</b></p><p> cd[i]=' ';</p><p>
82、 cd[i+1]='\0';</p><p> cd[i]=fgetc(fp); //數(shù)組接受從fp指針所指向文件中讀</p><p><b> //入的一個字符</b></p><p> for(j=1;j<=num;j++)</p><p> if(strcmp(HC[j].bi
83、ts,cd)==0)</p><p><b> {</b></p><p> str[k]=HC[j].ch;</p><p><b> k++;</b></p><p> cjs=1;break;</p><p> } //haffma
84、n編碼和密碼譯碼相比較</p><p><b> } </b></p><p><b> }</b></p><p> str[k]='\0';</p><p><b> p=str;</b></p><p><b>
85、 return p;</b></p><p><b> }</b></p><p><b> 5 系統(tǒng)調(diào)試</b></p><p> 本次測試是在我的電腦的E盤中建立一個名為file1.txt的文本文檔,其中有大寫字母IAMASTUDENT,期望程序能將其讀出至界面并實現(xiàn)其他相關的功能。</p>
86、;<p> 運行程序后,我們可以見到一下的運行界面。</p><p> 從硬盤中讀出已有的文本文件(見圖5.1):</p><p><b> 圖5.1</b></p><p> 輸出哈夫曼樹存儲結(jié)構的初態(tài)(見圖5.2):</p><p><b> 圖5.2</b></p
87、><p> 輸出所讀字符的種類和每種字符的個數(shù)(見圖5.3):</p><p><b> 圖5.3</b></p><p> 輸出哈夫曼樹存儲結(jié)構的終態(tài)(見圖5.4):</p><p><b> 圖5.4</b></p><p> 輸出譯碼后的字符(見圖5.5)<
88、/p><p><b> 圖5.5</b></p><p> 由此可見,此次測試很成功。我們能夠?qū)⑽谋疚臋nfile1.txt中的文段讀出,并將其統(tǒng)計并輸出字符種類和每種字符出現(xiàn)的頻率。同時輸出哈夫曼樹存儲結(jié)構的初態(tài)和終態(tài)。然后輸出譯碼后的字符。</p><p><b> 小 結(jié)</b></p><p
89、> 通過兩周的課程設計使我對哈夫曼樹以及哈夫曼編碼有了更深的認識和理解,也使我更加明白哈夫曼編碼譯碼在信息技術中的重要性和地位。</p><p> 首先我談談我在設計期間我遇到的難點。開始的時候,代碼中有許多的錯誤,特別是有一個“無法找到文件”的錯誤讓我束手無策,最后還是屏蔽了定義的四個頭文件然后慢慢地改正錯誤才讓我又看到了希望。然后在實現(xiàn)文章的讀入時,由于對文件不是太熟悉,只好翻開C語言書本仿照其模式
90、編寫,但后來進入了死循環(huán),最后的解決方式是把main函數(shù)里的一個do…while循環(huán)去掉。在程序中,我還另外加了一個功能----輸出哈夫曼樹的存儲結(jié)構的初態(tài)和終態(tài)。這使得我更加的明白了哈夫曼到底是怎么存儲信息的。</p><p> 許多的錯誤讓我明白了一個道理---細心是非常重要的。同時,對于編程者而言,思路清晰是相當重要的。在適當?shù)臅r候和同學一起交流探討是一個十分好的學習機會。請教老師也很重要,因為畢竟我們是
91、新手,對于某些問題很難弄清楚。而且,某些錯誤對于我們來說有時候想半天都弄不來,但老師幾下下就搞好了,這樣就更加有效地節(jié)約了時間。</p><p> 三維谷屋返利 www.3vgw.com</p><p> 這次課程設計不但讓我學得了一些編程知識,還學會了系統(tǒng)的做一份課程設計報告,學會了如何截圖,學會了如何更好的畫流程圖,明白了做事情只有認真,才能真正做得更好!</p>&
92、lt;p> 這段時間里,可謂是酸甜苦辣都嘗過。有時,為了一個錯誤而焦頭爛額;有時,編程熬夜到凌晨兩點;有時,連吃飯都是匆匆了事;但一旦程序運行成功,總會讓我興奮不已。</p><p> 通過這次課程設計,我看清楚了自己的編程功底和動手能力還不如人意,這主要是平時實踐太少的緣故。我想,在未來的暑假中,我會努力嘗試編寫一些程序。雖然我們信息管理專業(yè)的學生,但現(xiàn)在編程的能力太差了,畢竟多精通一門技術總是好事。
93、</p><p> 在這個程序中,還有許多地方值得完善。比如,讀出文本只能是大寫的文檔,空格和小寫不能識別,更不用說是任意的ASCⅡ碼字符了。由于時間問題,暫時不能實現(xiàn)了。我想在暑假里好好研究這個問題。</p><p><b> 參考文獻</b></p><p> [1] 嚴蔚敏.數(shù)據(jù)結(jié)構(C語言版).清華大學出版社,2007</p
94、><p> [2] 蘇仕華.數(shù)據(jù)結(jié)構課程設計.機械工業(yè)出版社,2007</p><p> [3] 譚浩強.C語言程序設計教程.高等教育出版社,2006</p><p><b> 附錄 源程序</b></p><p> #include <stdio.h></p><p> #in
95、clude <string.h></p><p> #include <stdlib.h></p><p> #include<fstream.h></p><p> //*************************類型相關變量的定義******************************</p>
96、<p> #define n 100 //葉子結(jié)點數(shù)</p><p> #define m 2*n-1 //哈夫曼樹中的結(jié)點樹</p><p> typedef struct{</p><p><b> char c
97、h;</b></p><p> char bits[9]; //存放編碼位串</p><p> int len; </p><p> }CodeNode;</p><p> typedef CodeNode HuffmanCode[n+1];</p>
98、<p> typedef struct {</p><p> int weight; //權值</p><p> int lchild,rchild,parent; //左右孩子幾雙親指針 </p><p><b> }HTNode;</
99、b></p><p> typedef HTNode HuffmanTree[m+1]; //0號單元不用</p><p><b> int num;</b></p><p> //**********************************建立HuffmanTree*****************
100、********</p><p> void select(HuffmanTree T,int k,int &s1,int &s2)</p><p> { //在ht[1....k]中選擇parent為0且權值最小的兩個根結(jié)點的算法</p><p> //其序號為s1和s2</p><p> int i,j;int
101、min1=101;</p><p> for(i=1;i<=k;i++)</p><p> if(T[i].weight<min1 &&T[i].parent==0) </p><p><b> {</b></p><p> j=i;min1=T[i].weight;</p>
102、;<p><b> }</b></p><p> s1=j;min1=32767;</p><p> for (i=1;i<=k;i++)</p><p> if(T[i].weight<min1 && T[i].parent==0 && i!=s1)</p>&l
103、t;p><b> {</b></p><p> j=i;min1=T[i].weight;</p><p><b> }</b></p><p><b> s2=j;</b></p><p><b> }</b></p>&l
104、t;p> int jsq(char *s,int cnt[],char str[])</p><p> { //統(tǒng)計字符串中各種字母的個數(shù)以及字符的種類</p><p> int i,j,k; </p><p><b> char *p;</b></p><p> int temp[27]; <
105、/p><p> for(i=1;i<=26;i++)</p><p> temp[i]=0; </p><p> for(p=s; *p!='\0';p++) </p><p><b> {</b></p><p> {
106、 //統(tǒng)計各種字符的個數(shù) </p><p> if(*p>='A'&&*p<='Z')</p><p><b> k=*p-64;</b></p><p> temp[k]++;</p><p><b> }&
107、lt;/b></p><p><b> }</b></p><p> for(i=1,j=0;i<=26;++i)</p><p> if(temp[i]!=0 ) </p><p><b> {</b></p><p><b> j++;&
108、lt;/b></p><p> str[j]=i+64; //送對應的字母到數(shù)組中</p><p> cnt[j]=temp[i]; //存入對應字母的權值</p><p><b> }</b></p><p> return j;
109、 //j是輸入字母總數(shù)</p><p><b> }</b></p><p> void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt[],char str[])</p><p> { /
110、/構造哈夫曼樹HT</p><p> int i,s1,s2;</p><p> for(i=1;i<=2*num-1;i++)//初始化HT,2*num-1是指哈夫曼樹所有的結(jié)點數(shù)目</p><p><b> {</b></p><p> HT[i].lchild=0;HT[i].rchild=0;&l
111、t;/p><p> HT[i].parent=0;HT[i].weight=0;</p><p><b> }</b></p><p> for(i=1;i<=num;i++) //輸入num個葉結(jié)點的權值</p><p> HT[i].weight=cnt[i];</p&
112、gt;<p> for(i=num+1;i<=2*num-1;i++)</p><p> { //在ht[1....k]中選擇parent為0且權值最小的兩個根結(jié)點</p><p> //其序號為s1和s2</p><p><b> //i為雙親</b></p><p> select(
113、HT,i-1,s1,s2);</p><p> HT[s1].parent=i;HT[s2].parent=i;</p><p> HT[i].lchild=s1; HT[i].rchild=s2;</p><p> HT[i].weight=HT[s1].weight+HT[s2].weight;</p><p><b>
114、 }</b></p><p> for(i=0;i<=num;i++) //輸入字符集的中字符</p><p> HC[i].ch=str[i]; //字符的種類</p><p> i=1;while(i<=num)</p><p> printf(
115、"字符%c次數(shù):%d\n",HC[i].ch,cnt[i++]);</p><p><b> }</b></p><p> //*************************生成Huffman編碼并寫入文件************************</p><p> void HuffmanEncoding
116、(HuffmanTree T,HuffmanCode H)</p><p> { //根據(jù)哈夫曼樹T求哈夫曼編碼H</p><p> int c,p,i; //c和p分別指示t中孩子和雙親</p><p> char cd[n];
117、 //臨時存放編碼串</p><p> int start; //指示碼在cd中的起始位置</p><p> cd[num]='\0'; //最后一位(第num個)放上串結(jié)束符</p><p> for(i=1;i<=num;++i)</p><p>
118、;<b> {</b></p><p> start=num; //初始位置</p><p> c=i; //從葉子結(jié)點t[i]開始上溯</p><p> while((p=T[c].parent)>0) //直至上溯到t[c]是樹根為止</p>&
119、lt;p> { //若t[c]是t[p]的左孩子,則生成0;否則生成底碼1</p><p> cd[--start]=(T[p].lchild==c) ? '0' : '1';</p><p><b> c=p;</b></p><p><b>
120、 }</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>
121、void coding(HuffmanCode HC ,char *str)</p><p> { //對str所代表的字符串進行編碼 并寫入文件</p><p><b> int i,j;</b></p><p><b> FILE *fp;</b>&
122、lt;/p><p> fp=fopen("codefile.txt","w");</p><p> while(*str)</p><p><b> {</b></p><p> for(i=1;i<=num;i++)</p><p> if(H
123、C[i]. ch==*str){</p><p> for(j=0;j<=HC[i].len;j++)</p><p> fputc(HC[i].bits[j],fp);</p><p><b> break;</b></p><p><b> }</b></p><
124、;p><b> str++;</b></p><p> }fclose(fp);</p><p><b> }</b></p><p> //*************************電文譯碼****************************************</p><
125、;p> char*decode(HuffmanCode HC)</p><p> { //代碼文件codefile.txt的譯碼</p><p><b> FILE *fp;</b></p><p> char str[254]; //假設遠
126、文本文件不超過254個字符</p><p><b> char *p;</b></p><p> static char cd[n+1];</p><p> int i,j,k=0,cjs;</p><p> fp=fopen("codefile.txt","r");//一
127、只讀的方式打開文本文檔codefile.txt</p><p> while(!feof(fp))//feof(fp)判斷文件是否真正結(jié)束,feof(fp)=1時文件結(jié)束</p><p><b> {</b></p><p><b> cjs=0;</b></p><p> for(i=0;
128、i<num && cjs==0 && !feof(fp);i++)</p><p><b> {</b></p><p> cd[i]=' ';cd[i+1]='\0';</p><p> cd[i]=fgetc(fp);//數(shù)組接受從fp指針所指向文件中讀入的一個字符
129、</p><p> for(j=1;j<=num;j++)</p><p> if(strcmp(HC[j].bits,cd)==0)//haffman編碼和密碼譯碼相比較</p><p><b> {</b></p><p> str[k]=HC[j].ch;</p><p>&l
130、t;b> k++;</b></p><p> cjs=1;break;</p><p><b> }</b></p><p><b> } </b></p><p><b> }</b></p><p> str[k]=
131、39;\0';</p><p><b> p=str;</b></p><p><b> return p;</b></p><p><b> }</b></p><p> //*************************輸出HuffmanTree存儲結(jié)構
132、*************************</p><p> void print1(HuffmanTree HT)</p><p><b> {</b></p><p><b> int x; </b></p><p> for(x=1;x<=2*num-1;x++)<
133、/p><p><b> { </b></p><p> HT[x].parent=0;</p><p> HT[x].lchild=0;</p><p> HT[x].rchild=0;</p><p> printf("%11d %d\t %d\t %d\n"
134、,HT[x].weight,HT[x].parent,HT[x].lchild,HT[x].rchild);</p><p><b> }</b></p><p> printf("--------------------------------------\n");</p><p><b> } <
135、/b></p><p> void print2(HuffmanTree HT)</p><p><b> {</b></p><p><b> int k;</b></p><p> for(k=1;k<=2*num-1;k++) </p><p>&
136、lt;b> {</b></p><p> printf(" %d\t %d\t %d\t %d\n",HT[k].weight,HT[k].parent,HT[k].lchild,HT[k].rchild);</p><p><b> }</b></p><p> printf("----
137、----------------------------------\n");</p><p><b> } </b></p><p> void DhuffmanTree(HuffmanTree HT,int cnt[],char str[])</p><p> {
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構課程設計-哈夫曼編碼譯碼器
- (哈夫曼編碼譯碼器)(課程設計報告)
- 哈夫曼編碼譯碼器課程設計
- 數(shù)據(jù)結(jié)構課程設計--電文編碼譯碼(哈夫曼編碼)
- 數(shù)據(jù)結(jié)構課程設計--哈夫曼編碼和譯碼報告
- 哈夫曼編碼譯碼數(shù)據(jù)結(jié)構課程設計
- 數(shù)據(jù)結(jié)構課程設計電文編碼譯碼(哈夫曼編碼)
- 哈夫曼編碼譯碼數(shù)據(jù)結(jié)構課程設計
- 哈夫曼課程設計報告--哈夫曼編譯碼器
- 赫夫曼編譯碼器數(shù)據(jù)結(jié)構課程設計
- 哈夫曼編譯碼器課程設計報告
- 數(shù)據(jù)結(jié)構課程設計報告---哈夫曼編碼器
- 數(shù)據(jù)結(jié)構課程設計---哈夫曼編碼
- 數(shù)據(jù)結(jié)構課程設計----哈夫曼編碼
- 數(shù)據(jù)結(jié)構課程設計哈夫曼編碼
- 數(shù)據(jù)結(jié)構課程設計--哈夫曼編碼
- 數(shù)據(jù)結(jié)構課程設計---哈夫曼編碼器
- 數(shù)據(jù)結(jié)構課程設計---哈夫曼編碼
- 數(shù)據(jù)結(jié)構課程設計哈夫曼編碼
- 數(shù)據(jù)結(jié)構課程設計---哈夫曼編碼器
評論
0/150
提交評論