數(shù)據(jù)結(jié)構(gòu)課程設計報告---前綴編碼問題

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：10 大?。?92.00KB 人氣指數(shù)：12 舉報 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)課程設計報告---前綴編碼問題_第1頁

已閱讀1頁，還剩9頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領

文檔簡介

1、　　數(shù) 據(jù) 結(jié) 構(gòu)　　課程設計報告　　題目： 　　專業(yè)： 　　班級：

2、 　　學號： 　　姓名： 　　指導老師： &

3、lt;p>　　時間： 　　一、課程設計題目及所涉及知識點　　設計題目是：“前綴編碼問題”。　　所涉及的知識點主要是：　　本課程設計利用二叉樹來設計二進制的前綴編碼，前綴編碼顧名思義就是任意一字符的編碼

4、都不是另一個字符的編碼的前綴，主要難點在于如何根據(jù)輸入的字符和使用頻度構(gòu)造出最優(yōu)二叉樹，并根據(jù)構(gòu)造的最優(yōu)二叉樹輸出每個字符的編碼，這主要設計到對每個字符的權(quán)值進行冒泡排序找出最小的兩個權(quán)值作為左右孩子結(jié)點，以他們的和作為父母結(jié)點，并把父母結(jié)點作為新的權(quán)值數(shù)重新排序，最終構(gòu)造出完整的哈夫曼樹，以根的左右路徑分別代表值“0”與“1”連續(xù)存儲，得到每個字符的編碼。　　二、課程設計思路及算法描述<

5、/p>　　設計思路：通過構(gòu)造哈夫曼樹的結(jié)構(gòu)體定義一個哈夫曼樹組，對用戶輸入的字符以及使用頻率進行存儲和初始化，然后對字符進行編譯處理，通過構(gòu)造哈夫曼樹編譯出每個字符的編碼，然后對每個編碼進行存儲并與字符相關聯(lián)，并輸出每個字符以及對應的編碼。最終根據(jù)用戶選擇的功能進行編碼和譯碼操作。　　問題一：哈夫曼樹的表示。　　設計哈夫曼樹的

6、結(jié)構(gòu)體，其中包含使用頻率（權(quán)重）、左孩子、右孩子、雙親和要編碼的字符。用這個結(jié)構(gòu)體定義個一個哈夫曼數(shù)組。　　哈夫曼結(jié)構(gòu)體定義如下：　　typedef struct　　{　　int weight;

7、;　　int lchild;　　int rchild;　　int parent;　　char key;　　}htnode;　　typedef htnode

8、 hfmt[MAXLEN];　　問題二：對輸入字符進行編碼。　　初始化哈夫曼樹，每個節(jié)點的孩子及雙親默認值為-1，使用頻率為0。根據(jù)用戶選擇輸入字符個數(shù)n，以及n個字符和n個權(quán)值，構(gòu)造出哈夫曼樹，并顯示出每個字符及對應編碼。　　1.void creathfmt(hfmt t)//創(chuàng)建哈夫曼樹的函數(shù)</p&g

9、t;　　2.void selectmin(hfmt t,int i,int *p1,int *p2)//選出兩個最小的字符權(quán)值　　3.void phfmnode(hfmt t)//對字符進行初始編碼　　問題三：對用戶輸入的電文進行編碼。　　用戶輸入一連串原本輸入的字符構(gòu)成電文，電文長度在10

10、00字符以內(nèi)，由程序進行編碼轉(zhuǎn)換。并輸出轉(zhuǎn)換后的編碼。　　void encoding(hfmt t)//對用戶輸入的電文進行編碼 　　{ 　　char r[1000];//用來存儲輸入的字符串 　　int i,j;&

11、lt;/b>　　printf("\n請輸入需要編碼的字符:");　　gets(r);　　printf("編碼結(jié)果為:"); 　　for(j=0;r[j]!='\0';j++

12、)　　for(i=0;i<n;i++)　　if(r[j]==t[i].key)　　hfmtpath(t,i,j); 　　printf("\n");　　}</p&

13、gt;　　問題四：對用戶輸入的密文進行譯碼。　　用戶輸入一連串二進制代碼字符構(gòu)成密文，電文長度在100個二進制代碼以內(nèi)，由程序進行編碼轉(zhuǎn)換。并輸出轉(zhuǎn)換后的譯碼。　　void decoding(hfmt t)//對用戶輸入的密文進行譯碼　　{</p&

14、gt;　　char r[100];　　int i,j,len;　　j=2*n-2;//j初始從樹的根節(jié)點開始　　printf("\n請輸入需要譯碼的字符串:");　　gets(r);</

15、p>　　len=strlen(r);　　printf("譯碼的結(jié)果是:");　　for(i=0;i<len;i++)　　{　　if(r[i]=='0')</p

16、>　　{　　j=t[j].lchild;　　if(t[j].lchild==-1)　　{　　printf("%c",t[j].key);</p

17、>　　j=2*n-2;　　}　　}　　else if(r[i]=='1')　　{</b&g

18、t;　　j=t[j].rchild;　　if(t[j].rchild==-1)　　{　　printf("%c",t[j].key);　　j=2*n-2;&

19、lt;/b>　　}　　}　　}　　printf("\n");　　}<

20、;/b>　　三、課程設計中遇到的難點及解決辦法　　在程序設計中遇到的問題主要是如何根據(jù)輸入的字符頻率構(gòu)造哈夫曼樹，這其中涉及到對哈夫曼樹的存儲，以及根據(jù)樹的左孩子路徑為“0”右孩子路徑“1”對字符進行二級制編碼，在參考課文和網(wǎng)絡資源后進行整理和加工，設計出了構(gòu)造哈夫曼樹的程序。由于事先不知道用戶要輸入幾個字符，所以無法判斷最終二進制編碼的長度，通過

21、定義一個比較大的存儲空間存儲編碼。在對每個字符構(gòu)造出編碼后根據(jù)用戶選擇進行編碼和譯碼，這其中遇到的難點主要是根據(jù)用戶輸入的信息進行翻譯，特別是譯碼過程，主要難點的解決時上網(wǎng)百度和詢問老師解決的。　　總結(jié)　　通過這次課程設計，我對前綴編碼問題有了深刻的認識，對哈夫曼樹的優(yōu)越性也有了深刻的了解，利用哈夫曼編碼可以極大的縮

22、短編碼長度，提高信息的傳輸時間，在社會的實際應用時很廣泛的，同時通過程序設計中對哈夫曼樹的構(gòu)造，對我的編程思想有了很大的提高，我對數(shù)據(jù)結(jié)構(gòu)也有了更好的掌握，雖然距離完全的掌握每一個功能操作還有一定的差距，但是我相信通過不斷地學習和努力，我一定能做的更好更完善。　　附錄—主要源程序代碼及運行結(jié)果　　#include <stdio.h></

23、p>　　#include <stdlib.h>　　#include <string.h>　　#define MAXLEN 100　　typedef struct　　{</p&

24、gt;　　int weight;　　int lchild;　　int rchild;　　int parent;　　char key;　　}htnode;

25、　　typedef htnode hfmt[MAXLEN];　　int n;　　void selectmin(hfmt t,int i,int *p1,int *p2)//選中兩個權(quán)值最小的函數(shù)

26、　　{　　long min1=999999;　　long min2=999999;　　int j;　　for(j=0;j<=i;j++)//選擇最小權(quán)值字符的下標返回

27、;　　if(t[j].parent==-1)　　if(min1>t[j].weight)　　{　　min1=t[j].weight;　　*p1=j;

28、　　}　　for(j=0;j<=i;j++)//選擇次小權(quán)值字符的下標還回　　if(t[j].parent==-1)　　if(min2>t[j].weight&&j!=(*p1))　　{&

29、lt;/b>　　min2=t[j].weight;　　*p2=j;　　}　　}　　void creathfmt

30、(hfmt t)//創(chuàng)建哈夫曼樹的函數(shù) 　　{　　int i,w,p1,p2;　　char k;//k表示獲取的字符　　printf("\n");　　printf(&quo

31、t;------------------------------------------------\n");　　printf("*********************輸入?yún)^(qū)*********************\n");　　printf("\n請輸入字符個數(shù)：");<

32、;p>　　scanf("%d",&n);　　getchar();　　for(i=0;i<2*n-1;i++)//對結(jié)構(gòu)體進行初始化 　　{　　t[i].weight=0;

33、　　t[i].lchild=-1;　　t[i].rchild=-1;　　t[i].parent=-1;　　}　　printf("\n");　　for(i=

34、0;i<n;i++)　　{　　printf("請輸入第%d個字符:",i+1);　　scanf("%c",&k);　　getchar();

35、　　t[i].key=k;　　printf("請輸入第%d個字符的權(quán)值:",i+1);　　scanf("%d",&w);　　getchar();　　t[i].weight=w;　　p

36、rintf("\n");　　} 　　for(i=n;i<2*n-1;i++)　　{　　selectmin(t,i-1,&p1,&p2);

37、;　　t[p1].parent=i;　　t[p2].parent=i;　　t[i].lchild=p1;　　t[i].rchild=p2;　　t[i].weight=t[p1].weight+t[p2].weight; <

38、;p>　　}　　}　　void hfmtpath(hfmt t,int i,int j)//編碼的重要哈夫曼樹路徑遞歸算法 　　{

39、int a,b;　　a=i;　　b=j=t[i].parent;　　if(t[j].parent!=-1) 　　{

40、　i=j;　　hfmtpath(t,i,j);　　}　　if(t[b].lchild==a)　　printf("0");　　else&

41、lt;/b>　　printf("1");　　}　　void phfmnode(hfmt t)//對字符進行初始編碼　　{<

42、b>　　int i,j;　　printf("------------------------------------------------\n");　　printf("*******************哈夫曼編碼*******************\n");

43、　　for(i=0;i<n;i++)　　{　　j=0;　　printf("\n");　　printf("\t\t%c\t\t",t[

44、i].key,t[i].weight);　　hfmtpath(t,i,j);　　}　　}　　void encoding(hfmt t)//對用戶輸入的電文進行編碼 <

45、p>　　{ 　　char r[1000];//用來存儲輸入的字符串 　　int i,j;　　printf("\n請輸入需要編碼的字符:");　　gets

46、(r);　　printf("編碼結(jié)果為:"); 　　for(j=0;r[j]!='\0';j++)　　for(i=0;i<n;i++)　　if(r[j]==t[i].key)<p&

47、gt;　　hfmtpath(t,i,j); 　　printf("\n");　　}　　void decoding(hfmt t)//對用戶輸入的密文進行譯碼　　{</p&g

48、t;　　char r[100];　　int i,j,len;　　j=2*n-2;//j初始從樹的根節(jié)點開始　　printf("\n請輸入需要譯碼的字符串:");　　gets(r);</p

49、>　　len=strlen(r);　　printf("譯碼的結(jié)果是:");　　for(i=0;i<len;i++)　　{　　if(r[i]=='0')</p&

50、gt;　　{　　j=t[j].lchild;　　if(t[j].lchild==-1)　　{　　printf("%c",t[j].key);</p&

51、gt;　　j=2*n-2;　　}　　}　　else if(r[i]=='1')　　{

52、;　　j=t[j].rchild;　　if(t[j].rchild==-1)　　{　　printf("%c",t[j].key);　　j=2*n-2;&l

53、t;/b>　　}　　}　　}　　printf("\n");　　}<

54、/b>　　void main()　　{　　hfmt ht;　　char flag;　　printf("------------------

55、------------------------------\n");　　printf(" **********說明********** \n"); 　　printf(" * 11級數(shù)據(jù)結(jié)構(gòu)課程設計 * \n");　　pri

56、ntf(" * 哈夫曼編碼 * \n");　　printf(" * 科學與技術專業(yè) 邵帥 * \n");　　printf(" ************************ \n"); &

57、lt;p>　　creathfmt(ht);//創(chuàng)建哈夫曼樹的函數(shù)　　phfmnode(ht); //對字符進行初始編碼 　　printf("\n------------------------------------------------\n");　　do{</

58、b>　　printf("********************功能選擇********************\n");　　printf("【1】編碼\t【2】譯碼\t【0】退出\n");　　printf("您的選擇：");

59、　　flag=getchar();　　getchar();　　if(flag=='1')　　encoding(ht);　　else if(flag=='2')　　decoding

60、(ht);　　else if(flag=='0')　　return;　　else　　printf("您的輸入有誤，請重新輸入。\n");

61、　　}while(flag!='0');　　printf("\n");　　}　　運行結(jié)果：　　六、指導老師評語及成績

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設計報告---前綴編碼問題

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設計報告---前綴編碼問題

文檔簡介

溫馨提示

最新文檔

評論

免費下載