數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼譯碼器課程設(shè)計(jì)報(bào)告(有源程序)

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

已閱讀1頁，還剩28頁未讀，繼續(xù)免費(fèi)閱讀

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

文檔簡介

1、　　JAVA語言實(shí)驗(yàn)報(bào)告　　學(xué) 院計(jì)算機(jī)工程學(xué)院班級計(jì)算1013 　　姓名 xxxx 學(xué) 號 201081xxxx　　成績指導(dǎo)老師 xxxx　　201

2、2年09月03日　　目錄　　目錄1　　1 課程設(shè)計(jì)的目的和意義2　　2 需求分析3　　3 系統(tǒng)（項(xiàng)目）

3、設(shè)計(jì)5　?、僭O(shè)計(jì)思路及方案………………………………………………5　　②模塊的設(shè)計(jì)及介紹……………………………………………5　?、壑饕K程序流程圖…………………………………………8　　4 系統(tǒng)實(shí)現(xiàn)11<

4、;p>　?、僦髡{(diào)函數(shù)…………..…………………………..……………..12　　②建立HuffmanTree……………………………………………12　?、凵蒆uffman編碼并寫入文件……………………………..15　?、茈娢淖g碼……………………………………………………..16<p

5、>　　5 系統(tǒng)調(diào)試17　　參考文獻(xiàn)20　　附錄源程序21　　1 課程設(shè)計(jì)的目的和意義　　在當(dāng)今信息爆炸時(shí)代，如何采用有效的數(shù)據(jù)壓縮技術(shù)來節(jié)省數(shù)據(jù)

6、文件的存儲空間和計(jì)算機(jī)網(wǎng)絡(luò)的傳送時(shí)間已越來越引起人們的重視。哈夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。　　哈夫曼編碼的應(yīng)用很廣泛，利用哈夫曼樹求得的用于通信的二進(jìn)制編碼稱為哈夫曼編碼。樹中從根到每個(gè)葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個(gè)對應(yīng)的字符的編碼，這就是哈夫曼編碼。</

7、p>　　通常我們把數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報(bào)通信是傳遞文字的二進(jìn)制碼形式的字符串。但在信息傳遞時(shí)，總希望總長度盡可能最短，即采用最短碼。　　作為信息管理專業(yè)的學(xué)生，我們應(yīng)該很好的掌握這門技術(shù)。在課堂上，我們能過學(xué)到許多的理論知識，但我們很少有過自己動手實(shí)踐的機(jī)會！課程設(shè)計(jì)就是為解決這個(gè)問題提供了一個(gè)平臺。

8、;　　在課程設(shè)計(jì)過程中，我們每個(gè)人選擇一個(gè)課題，認(rèn)真研究，根據(jù)課堂講授內(nèi)容，借助書本，自己動手實(shí)踐。這樣不但有助于我們消化課堂所講解的內(nèi)容，還可以增強(qiáng)我們的獨(dú)立思考能力和動手能力；通過編寫實(shí)驗(yàn)代碼和調(diào)試運(yùn)行，我們可以逐步積累調(diào)試C程序的經(jīng)驗(yàn)并逐漸培養(yǎng)我們的編程能力、用計(jì)算機(jī)解決實(shí)際問題的能力。　　在課程設(shè)計(jì)過程中，我們不但有自己的獨(dú)立思考，還借助各種參考文獻(xiàn)來幫助我們完成系統(tǒng)。更為重要的是，我們

9、同學(xué)之間加強(qiáng)了交流，在對問題的認(rèn)識方面可以交換不同的意見。同時(shí)，師生之間的互動也隨之改善，我們可以通過具體的實(shí)例來從老師那學(xué)到更多的實(shí)用的知識。　　數(shù)據(jù)結(jié)構(gòu)課程具有比較強(qiáng)的理論性，同時(shí)也具有較強(qiáng)的可應(yīng)用性和實(shí)踐性。課程設(shè)計(jì)是一個(gè)重要的教學(xué)環(huán)節(jié)。我們在一般情況下都能夠重視實(shí)驗(yàn)環(huán)節(jié)，但是容易忽略實(shí)驗(yàn)的總結(jié)，忽略實(shí)驗(yàn)報(bào)告的撰寫。通過這次實(shí)驗(yàn)讓我們明白：作為一名大學(xué)生必須嚴(yán)格訓(xùn)練分析總結(jié)能力、書面表達(dá)能

10、力。需要逐步培養(yǎng)書寫科學(xué)實(shí)驗(yàn)報(bào)告以及科技論文的能力。只有這樣，我們的綜合素質(zhì)才會有好的提高。　　2 需求分析　　課題：哈夫曼編碼譯碼器系統(tǒng)　　問題描述：打開一篇英文文章，統(tǒng)計(jì)該文章中每個(gè)字符出現(xiàn)的次數(shù)，然后以它們作為權(quán)值，對每一個(gè)字符進(jìn)行編碼，編碼完成后再對其編碼進(jìn)行

11、譯碼。　　問題補(bǔ)充：1. 從硬盤的一個(gè)文件里讀出一段英語文章；　　2. 統(tǒng)計(jì)這篇文章中的每個(gè)字符出現(xiàn)的次數(shù)；　　3. 以字符出現(xiàn)字?jǐn)?shù)作為權(quán)值，構(gòu)建哈夫曼樹，并將哈夫曼樹的存儲結(jié)構(gòu)的初態(tài)和終態(tài)進(jìn)行輸出；　　4. 對每個(gè)字符進(jìn)行編碼并將所編碼寫入文件然后對所編碼進(jìn)行破譯。&l

12、t;/p>　　具體介紹：在本課題中，我們在硬盤E盤中預(yù)先建立一個(gè)file1.txt文檔，在里面編輯一篇文章(大寫)。然后運(yùn)行程序，調(diào)用fileopen()函數(shù)讀出該文章，顯示在界面；再調(diào)用jsq()函數(shù)對該文章的字符種類進(jìn)行統(tǒng)計(jì)，并對每個(gè)字符的出現(xiàn)次數(shù)進(jìn)行統(tǒng)計(jì)，并且在界面上顯示；然后以每個(gè)字符出現(xiàn)次數(shù)作為權(quán)值，調(diào)用ChuffmanTree()函數(shù)構(gòu)建哈夫曼樹；并調(diào)用print1()和print2()函數(shù)將哈夫

13、曼的存儲結(jié)構(gòu)的初態(tài)和終態(tài)進(jìn)行輸出。然后調(diào)用HuffmanEncoding()函數(shù)對哈夫曼樹進(jìn)行編碼，調(diào)用coding()函數(shù)將編碼寫入文件；再調(diào)用decode()對編碼進(jìn)行譯碼，再輸出至界面。至此，整個(gè)工作就完成了。　　測試數(shù)據(jù)：例如從文本中讀到文章為：IAMASTUDENT。　　則效果如下：

14、　　IAMASTUDENT　　--------------------------------------　　HuffmanTree的初態(tài):　　2 0 0 0　　1 0 0 0</

15、p>　　1 0 0 0　　1 0 0 0　　1 0 0 0　　1 0 0 0　　1 0

16、 0 0　　2 0 0 0　　1 0 0 0　　- 0 0 0　　- 0 0 0

17、　- 0 0 0　　- 0 0 0　　- 0 0 0　　- 0 0 0　　- 0 0 0</p&

18、gt;　　- 0 0 0　　--------------------------------------　　字符A次數(shù):2　　字符D次數(shù):1

19、　　字符E次數(shù):1　　字符I 次數(shù):1　　字符M次數(shù):1　　字符N 次數(shù):1　　字符S 次數(shù):1<

20、;/b>　　字符T次數(shù):2　　字符U次數(shù):1　　--------------------------------------　　HuffmanTree的終態(tài):<

21、p>　　2 13 0 0　　1 10 0 0　　1 10 0 0　　1 11 0 0　　1 11 0

22、 0　　1 12 0 0　　1 12 0 0　　2 14 0 0　　1 13 0 0　　2

23、 14 2 3　　2 15 4 5　　2 15 6 7　　3 16 9 1　　4 16 8 10<

24、;/p>　　4 17 11 12　　7 17 13 14　　11 0 15 16　　--------------------------------------<

25、;p>　　譯碼后的字符串:　　IAMASTUDENT　　**********************************************************　　Press any key to continue

26、　三維谷屋 www.3vgw.com　　3 系統(tǒng)（項(xiàng)目）設(shè)計(jì)　　(1)設(shè)計(jì)思路及方案　　本課題是用最優(yōu)二叉樹即哈夫曼樹來實(shí)現(xiàn)哈夫曼編碼譯碼器的功能。假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為Wi，編碼長度為Li，電文中有n種字符，則電文編碼總長度為(W1*L1)+(W2*L2)+…+(Wi*Li)。若將此對應(yīng)到二叉樹上，W

27、i為葉結(jié)點(diǎn)，Li為根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑長度。那么，(W1*L1)+(W2*L2)+…+(Wi*Li)恰好為二叉樹上帶權(quán)路徑長度。三維谷屋 www.3vgw.com　　因此，設(shè)計(jì)電文總長最短的二進(jìn)制前綴編碼，就是以n種字符出現(xiàn)的頻率作權(quán)，構(gòu)造一棵哈夫曼樹，此構(gòu)造過程稱為哈夫曼編碼。　　該系統(tǒng)將實(shí)現(xiàn)以下幾大功能：從硬盤讀取字符串，建立哈夫曼樹，輸出哈夫曼樹

28、的存儲結(jié)構(gòu)的初態(tài)和終態(tài)，輸出各種字符出現(xiàn)的次數(shù)以及哈夫曼編碼的譯碼等。 　　(2)模塊的設(shè)計(jì)及介紹　?、購挠脖P讀取字符串　　fileopen(參數(shù))　　{<p

29、>　　實(shí)現(xiàn)命令；　　打印輸出；　　}　?、诮uffmanTree　　通過三個(gè)函數(shù)來實(shí)現(xiàn)：　　void s

30、elect(參數(shù))　　{　　初始化；　　for　　{ 　　接

31、受命令；　　處理命令；　　}　　}　　說明：在ht[1....k]中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)的算法

32、　　int jsq(參數(shù))　　{　　初始化；　　for　　{

33、;　　接受命令；　　處理命令；　　} 　　}　　說明：統(tǒng)計(jì)字符串中各種字母的個(gè)數(shù)以及字符的種類&

34、lt;p>　　void ChuffmanTree()　　{　　初始化；　　for　　{ &

35、lt;p>　　接受命令；　　處理命令；　　}　　輸出字符統(tǒng)計(jì)情況；　　}&l

36、t;/p>　　說明：構(gòu)造哈夫曼樹　?、圯敵龉蚵鼧涞拇鎯Y(jié)構(gòu)的初態(tài)和終態(tài)　　分別調(diào)用print1()和print2()來實(shí)現(xiàn)　　void print1(參數(shù))　　{&l

37、t;/p>　　初始化；　　輸出初態(tài)；　　}　　說明：輸出哈夫曼樹的初態(tài)　　void print2(參數(shù))&

38、lt;p>　　{　　for　　{　　輸出終態(tài)；　　}

39、　　}　　說明：輸出哈夫曼樹的終態(tài)　?、芄蚵幋a和譯碼　　void HuffmanEncoding(參數(shù))　　{&

40、lt;p>　　定義變量；　　{　　處理命令；　　}　　}

41、　　說明：哈夫曼編碼　　char*decode(參數(shù))　　{　　定義變量；　　while</

42、p>　　{　　接受命令；　　處理命令；　　}　　}&l

43、t;/p>　　說明：哈夫曼譯碼　　(3)主要模塊程序流程圖　　下面介紹三個(gè)主要的程序模塊流程圖：　?、僦骱瘮?shù)流程圖：　　圖3.1&

44、lt;/p>　　流程圖注釋：　　該圖比較簡單，主要是調(diào)用各個(gè)函數(shù)模塊，首先代開已經(jīng)存在的文件，然后統(tǒng)計(jì)總的字符數(shù)以及出現(xiàn)的各個(gè)字符和頻率。然后才開始建立哈夫曼樹，接著在哈夫曼樹的基礎(chǔ)上對其進(jìn)行編碼，編碼之后才是譯碼。最后輸出結(jié)束。　?、跇?gòu)造哈夫曼樹：&

45、lt;/p>　　圖3.2　　流程圖注釋：　　該圖是表示構(gòu)造哈夫曼樹的過程。首先輸入num個(gè)葉結(jié)點(diǎn)的權(quán)值，當(dāng)i=num是循環(huán)結(jié)束。然后進(jìn)行哈夫曼樹的構(gòu)建，當(dāng)i=2*num-1是循環(huán)結(jié)束。最后輸出所得到的字符統(tǒng)計(jì)情況。<p&g

46、t;　　三維谷屋返利 www.3vgw.com　?、酃蚵幋a：　　圖3.3　　流程圖解釋：　　該流程圖表四哈夫曼編碼情況。首先初始化，Cd[--start

47、]=0,start=num。然后進(jìn)行　　編碼，使用了一個(gè)三目運(yùn)算符。cd[--start]=(T[p].lchild==c) ? '0' : '1'，即當(dāng)cd[--start]=T[p].lchild= =c時(shí)，cd[--start]=0；當(dāng)cd[--start]=T[p].lchild！= =c時(shí)，cd[--start]=1。這個(gè)編碼循環(huán)一直到i=num時(shí)結(jié)束。

48、　　4 系統(tǒng)實(shí)現(xiàn)　　各模塊關(guān)鍵代碼及算法的解釋：　　主調(diào)函數(shù) 　　代碼解釋：這是main函數(shù)里的各個(gè)函數(shù)調(diào)用情況。　　fileopen(string);

49、 //從硬盤中讀取文件　　num=jsq(string,cnt,str); //統(tǒng)計(jì)字符種類及各類字符出現(xiàn)的頻率　　DhuffmanTree(HT,cnt,str); 　　printf("HuffmanTree的初態(tài):\n");

50、;　　print1(HT); //輸出哈夫曼樹的初態(tài)　　ChuffmanTree(HT,HC,cnt,str);//建立哈夫曼樹 　　HuffmanEncoding(HT,HC); //生成哈夫曼編碼　　printf("HuffmanTree的終態(tài):\n&q

51、uot;);　　print2(HT); //輸出哈夫曼樹的終態(tài)　　s=decode(HC); //讀編碼文件譯碼　　　printf("譯碼后的字符串:\n");　　printf("%

52、s\n",s); //輸出譯碼后的字符串　　建立HuffmanTree　　代碼解釋：該函數(shù)為在ht[1....k]中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)的算法，其序號為s1和s2。　　void select(HuffmanTree T,int k,int &s1,int

53、 &s2)　　{ 　　int i,j;　　int min1=101;　　for(i=1;i<=k;i++)　　if(T[i].weight&

54、lt;min1 &&T[i].parent==0) 　　{　　j=i;min1=T[i].weight;　　}　　s1=j;min1=32767;<p

55、>　　for (i=1;i<=k;i++)　　if(T[i].weight<min1 && T[i].parent==0 && i!=s1)　　{　　j=i;min1=T[i].weight;<p

56、>　　}　　s2=j;　　}　　代碼解釋：下面函數(shù)用來統(tǒng)計(jì)字符串中各種字母的個(gè)數(shù)以及字符的種類。當(dāng)字符在A和Z之間時(shí)即被計(jì)數(shù)，并用str[j]保存字母到數(shù)組中，用cnt[j]統(tǒng)計(jì)每種字符個(gè)數(shù)。j

57、返回總共讀取的字符數(shù)目。　　int jsq(char *s,int cnt[],char str[])　　{ 　　int i,j,k; 　　char *p;<p&g

58、t;　　int temp[27]; 　　for(i=1;i<=26;i++)　　temp[i]=0; 　　for(p=s; *p!='\0';p++) 　　{&l

59、t;b>　　{　 　　if(*p>='A'&&*p<='Z')　　k=*p-64;　　temp[k]++;　　}<

60、/b>　　} //統(tǒng)計(jì)各種字符的個(gè)數(shù)　　for(i=1,j=0;i<=26;++i)　　if(temp[i]!=0 ) 　　{

61、　　j++;　　str[j]=i+64; //送對應(yīng)的字母到數(shù)組中　　cnt[j]=temp[i]; //存入對應(yīng)字母的權(quán)值　　}

62、return j; //j是輸入字母總數(shù)　　}　　代碼解釋：下面函數(shù)用來構(gòu)造哈夫曼樹HT。首先初始化哈夫曼樹，然后輸入前面統(tǒng)計(jì)的各結(jié)點(diǎn)的權(quán)值，用for循環(huán)來構(gòu)造哈夫曼樹。　　void ChuffmanTree(HuffmanTree HT,HuffmanC

63、ode HC,int cnt[],char str[])　　{　　int i,s1,s2;　　for(i=1;i<=2*num-1;i++)//初始化HT，2*num-1是指哈夫曼　　//所有的結(jié)點(diǎn)數(shù)目<

64、/b>　　{　　HT[i].lchild=0;HT[i].rchild=0;　　HT[i].parent=0;HT[i].weight=0;　　}

65、　　for(i=1;i<=num;i++) //輸入num個(gè)葉結(jié)點(diǎn)的權(quán)值　　HT[i].weight=cnt[i];　　for(i=num+1;i<=2*num-1;i++)　　{　　select(HT,i-1,s1

66、,s2);　　HT[s1].parent=i;HT[s2].parent=i;　　HT[i].lchild=s1; HT[i].rchild=s2;　　HT[i].weight=HT[s1].weight+HT[s2].weight;　　}</b&

67、gt;　　//在ht[1....k]中選擇parent為0且權(quán)值最小　　//的兩個(gè)根結(jié)點(diǎn),其序號為s1和s2,i為雙親　　for(i=0;i<=num;i++) //輸入字符集的中字符　　HC[i].ch=str[i]; //字符的種類</

68、p>　　i=1;while(i<=num)　　printf("字符%c次數(shù):%d\n",HC[i].ch,cnt[i++]);　　} //輸出統(tǒng)計(jì)的情況　　生成Huffman編碼并寫入文件</p&g

69、t;　　代碼解釋：根據(jù)哈夫曼樹T求哈夫曼編碼H。　　void HuffmanEncoding(HuffmanTree T,HuffmanCode H)　　{　　int c,p,i; //c和p分別指示t中孩子和雙親&l

70、t;/p>　　char cd[n]; //臨時(shí)存放編碼串　　int start; //指示碼在cd中的起始位置　　cd[num]='\0'; //最后一位（第num個(gè)）放上串結(jié)束符<

71、p>　　for(i=1;i<=num;++i)　　{　　start=num; //初始位置　　c=i; //從葉子結(jié)點(diǎn)t[i]開始上溯　　while((p

72、=T[c].parent)>0) //直至上溯到t[c]是樹根為止　　{　　cd[--start]=(T[p].lchild==c) ? '0' : '1';　　c=p;<

73、;p>　　} //若t[c]是t[p]的左孩子　　//則生成0;否則生成底碼１　　strcpy(H[i].bits,&cd[start]);　　H[i].len=num-start;　　}<

74、;/b>　　}　　代碼解釋：對str所代表的字符串進(jìn)行編碼并寫入文件。將翻譯的二進(jìn)制碼寫入文本文件。　　void coding(HuffmanCode HC ,char *str)　　{ &

75、lt;/p>　　int i,j;　　FILE *fp;　　fp=fopen("codefile.txt","w");　　while(*str)&l

76、t;p>　　{　　for(i=1;i<=num;i++)　　if(HC[i]. ch==*str){　　for(j=0;j<=HC[i].len;j++)　　fputc(HC[i].bits[j],fp);</

77、p>　　break;　　}　　str++;　　}fclose(fp);　　}</p&g

78、t;　　電文譯碼　　代碼解釋：代碼文件codefile.txt的譯碼，將翻譯的二進(jìn)制碼譯成原來的字符。　　char*decode(HuffmanCode HC)　　{FILE *fp;　　char str[25

79、4]; //假設(shè)遠(yuǎn)文本文件不超過254個(gè)字符　　char *p;　　static char cd[n+1];　　int i,j,k=0,cjs;　　fp=fopen("codefile.txt&qu

80、ot;,"r");//一只讀的方式打開文本文檔//codefile.txt　　while(!feof(fp)) //feof(fp)判斷文件是否真正結(jié)束，　　//feof(fp)=1時(shí)文件結(jié)束　　{<p

81、>　　cjs=0;　　for(i=0;i<num && cjs==0 && !feof(fp);i++)　　{　　cd[i]=' ';

82、　cd[i+1]='\0';　　cd[i]=fgetc(fp); //數(shù)組接受從fp指針?biāo)赶蛭募凶x　　//入的一個(gè)字符　　for(j=1;j<=num;j++)　　if(strcmp(HC[j].bi

83、ts,cd)==0)　　{　　str[k]=HC[j].ch;　　k++;　　cjs=1;break;　　} //haffma

84、n編碼和密碼譯碼相比較　　} 　　}　　str[k]='\0';　　p=str;

85、　return p;　　}　　5 系統(tǒng)調(diào)試　　本次測試是在我的電腦的E盤中建立一個(gè)名為file1.txt的文本文檔，其中有大寫字母IAMASTUDENT，期望程序能將其讀出至界面并實(shí)現(xiàn)其他相關(guān)的功能。

86、;　　運(yùn)行程序后，我們可以見到一下的運(yùn)行界面。　　從硬盤中讀出已有的文本文件(見圖5.1)：　　圖5.1　　輸出哈夫曼樹存儲結(jié)構(gòu)的初態(tài)(見圖5.2)：　　圖5.2</p

87、>　　輸出所讀字符的種類和每種字符的個(gè)數(shù)(見圖5.3)：　　圖5.3　　輸出哈夫曼樹存儲結(jié)構(gòu)的終態(tài)(見圖5.4)：　　圖5.4　　輸出譯碼后的字符(見圖5.5)<

88、/p>　　圖5.5　　由此可見，此次測試很成功。我們能夠?qū)⑽谋疚臋nfile1.txt中的文段讀出，并將其統(tǒng)計(jì)并輸出字符種類和每種字符出現(xiàn)的頻率。同時(shí)輸出哈夫曼樹存儲結(jié)構(gòu)的初態(tài)和終態(tài)。然后輸出譯碼后的字符。　　小結(jié)<p

89、>　　通過兩周的課程設(shè)計(jì)使我對哈夫曼樹以及哈夫曼編碼有了更深的認(rèn)識和理解，也使我更加明白哈夫曼編碼譯碼在信息技術(shù)中的重要性和地位。　　首先我談?wù)勎以谠O(shè)計(jì)期間我遇到的難點(diǎn)。開始的時(shí)候，代碼中有許多的錯(cuò)誤，特別是有一個(gè)“無法找到文件”的錯(cuò)誤讓我束手無策，最后還是屏蔽了定義的四個(gè)頭文件然后慢慢地改正錯(cuò)誤才讓我又看到了希望。然后在實(shí)現(xiàn)文章的讀入時(shí)，由于對文件不是太熟悉，只好翻開C語言書本仿照其模式

90、編寫，但后來進(jìn)入了死循環(huán)，最后的解決方式是把main函數(shù)里的一個(gè)do…while循環(huán)去掉。在程序中，我還另外加了一個(gè)功能----輸出哈夫曼樹的存儲結(jié)構(gòu)的初態(tài)和終態(tài)。這使得我更加的明白了哈夫曼到底是怎么存儲信息的。　　許多的錯(cuò)誤讓我明白了一個(gè)道理---細(xì)心是非常重要的。同時(shí)，對于編程者而言，思路清晰是相當(dāng)重要的。在適當(dāng)?shù)臅r(shí)候和同學(xué)一起交流探討是一個(gè)十分好的學(xué)習(xí)機(jī)會。請教老師也很重要，因?yàn)楫吘刮覀兪?/p>

91、新手，對于某些問題很難弄清楚。而且，某些錯(cuò)誤對于我們來說有時(shí)候想半天都弄不來，但老師幾下下就搞好了，這樣就更加有效地節(jié)約了時(shí)間。　　三維谷屋返利 www.3vgw.com　　這次課程設(shè)計(jì)不但讓我學(xué)得了一些編程知識，還學(xué)會了系統(tǒng)的做一份課程設(shè)計(jì)報(bào)告，學(xué)會了如何截圖，學(xué)會了如何更好的畫流程圖，明白了做事情只有認(rèn)真，才能真正做得更好！&

92、lt;p>　　這段時(shí)間里，可謂是酸甜苦辣都嘗過。有時(shí)，為了一個(gè)錯(cuò)誤而焦頭爛額；有時(shí)，編程熬夜到凌晨兩點(diǎn)；有時(shí)，連吃飯都是匆匆了事；但一旦程序運(yùn)行成功，總會讓我興奮不已。　　通過這次課程設(shè)計(jì)，我看清楚了自己的編程功底和動手能力還不如人意，這主要是平時(shí)實(shí)踐太少的緣故。我想，在未來的暑假中，我會努力嘗試編寫一些程序。雖然我們信息管理專業(yè)的學(xué)生，但現(xiàn)在編程的能力太差了，畢竟多精通一門技術(shù)總是好事。

93、　　在這個(gè)程序中，還有許多地方值得完善。比如，讀出文本只能是大寫的文檔，空格和小寫不能識別，更不用說是任意的ASCⅡ碼字符了。由于時(shí)間問題，暫時(shí)不能實(shí)現(xiàn)了。我想在暑假里好好研究這個(gè)問題。　　參考文獻(xiàn)　　[1] 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)(C語言版).清華大學(xué)出版社，2007</p

94、>　　[2] 蘇仕華.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì).機(jī)械工業(yè)出版社，2007　　[3] 譚浩強(qiáng).C語言程序設(shè)計(jì)教程.高等教育出版社，2006　　附錄源程序　　#include <stdio.h>　　#in

95、clude <string.h>　　#include <stdlib.h>　　#include<fstream.h>　　//*************************類型相關(guān)變量的定義******************************

96、　　#define n 100 //葉子結(jié)點(diǎn)數(shù)　　#define m 2*n-1 //哈夫曼樹中的結(jié)點(diǎn)樹　　typedef struct{　　char c

97、h;　　char bits[9]; //存放編碼位串　　int len; 　　}CodeNode;　　typedef CodeNode HuffmanCode[n+1];

98、　　typedef struct {　　int weight; //權(quán)值　　int lchild,rchild,parent; //左右孩子幾雙親指針 　　}HTNode;</

99、b>　　typedef HTNode HuffmanTree[m+1]; //0號單元不用　　int num;　　//**********************************建立HuffmanTree*****************

100、********　　void select(HuffmanTree T,int k,int &s1,int &s2)　　{ //在ht[1....k]中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)的算法　　//其序號為s1和s2　　int i,j;int

101、min1=101;　　for(i=1;i<=k;i++)　　if(T[i].weight<min1 &&T[i].parent==0) 　　{　　j=i;min1=T[i].weight;

102、;　　}　　s1=j;min1=32767;　　for (i=1;i<=k;i++)　　if(T[i].weight<min1 && T[i].parent==0 && i!=s1)&l

103、t;p>　　{　　j=i;min1=T[i].weight;　　}　　s2=j;　　}&l

104、t;p>　　int jsq(char *s,int cnt[],char str[])　　{ //統(tǒng)計(jì)字符串中各種字母的個(gè)數(shù)以及字符的種類　　int i,j,k; 　　char *p;　　int temp[27]; <

105、/p>　　for(i=1;i<=26;i++)　　temp[i]=0; 　　for(p=s; *p!='\0';p++) 　　{　　{

106、 //統(tǒng)計(jì)各種字符的個(gè)數(shù) 　 　　if(*p>='A'&&*p<='Z')　　k=*p-64;　　temp[k]++;　　}&

107、lt;/b>　　}　　for(i=1,j=0;i<=26;++i)　　if(temp[i]!=0 ) 　　{　　j++;&

108、lt;/b>　　str[j]=i+64; //送對應(yīng)的字母到數(shù)組中　　cnt[j]=temp[i]; //存入對應(yīng)字母的權(quán)值　　}　　return j;

109、 //j是輸入字母總數(shù)　　}　　void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt[],char str[])　　{ /

110、/構(gòu)造哈夫曼樹HT　　int i,s1,s2;　　for(i=1;i<=2*num-1;i++)//初始化HT，2*num-1是指哈夫曼樹所有的結(jié)點(diǎn)數(shù)目　　{　　HT[i].lchild=0;HT[i].rchild=0;&l

111、t;/p>　　HT[i].parent=0;HT[i].weight=0;　　}　　for(i=1;i<=num;i++) //輸入num個(gè)葉結(jié)點(diǎn)的權(quán)值　　HT[i].weight=cnt[i];</p&

112、gt;　　for(i=num+1;i<=2*num-1;i++)　　{ //在ht[1....k]中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)　　//其序號為s1和s2　　//i為雙親　　select(

113、HT,i-1,s1,s2);　　HT[s1].parent=i;HT[s2].parent=i;　　HT[i].lchild=s1; HT[i].rchild=s2;　　HT[i].weight=HT[s1].weight+HT[s2].weight;

114、　}　　for(i=0;i<=num;i++) //輸入字符集的中字符　　HC[i].ch=str[i]; //字符的種類　　i=1;while(i<=num)　　printf(

115、"字符%c次數(shù):%d\n",HC[i].ch,cnt[i++]);　　}　　//*************************生成Huffman編碼并寫入文件************************　　void HuffmanEncoding

116、(HuffmanTree T,HuffmanCode H)　　{ //根據(jù)哈夫曼樹T求哈夫曼編碼H　　int c,p,i; //c和p分別指示t中孩子和雙親　　char cd[n];

117、 //臨時(shí)存放編碼串　　int start; //指示碼在cd中的起始位置　　cd[num]='\0'; //最后一位（第num個(gè)）放上串結(jié)束符　　for(i=1;i<=num;++i)

118、;　　{　　start=num; //初始位置　　c=i; //從葉子結(jié)點(diǎn)t[i]開始上溯　　while((p=T[c].parent)>0) //直至上溯到t[c]是樹根為止&

119、lt;p>　　{ //若t[c]是t[p]的左孩子,則生成0;否則生成底碼１　　cd[--start]=(T[p].lchild==c) ? '0' : '1';　　c=p;

120、　　}　　strcpy(H[i].bits,&cd[start]);　　H[i].len=num-start;　　}　　}

121、void coding(HuffmanCode HC ,char *str)　　{ //對str所代表的字符串進(jìn)行編碼并寫入文件　　int i,j;　　FILE *fp;&

122、lt;/p>　　fp=fopen("codefile.txt","w");　　while(*str)　　{　　for(i=1;i<=num;i++)　　if(H

123、C[i]. ch==*str){　　for(j=0;j<=HC[i].len;j++)　　fputc(HC[i].bits[j],fp);　　break;　　}<

124、;p>　　str++;　　}fclose(fp);　　}　　//*************************電文譯碼****************************************<

125、;p>　　char*decode(HuffmanCode HC)　　{ //代碼文件codefile.txt的譯碼　　FILE *fp;　　char str[254]; //假設(shè)遠(yuǎn)

126、文本文件不超過254個(gè)字符　　char *p;　　static char cd[n+1];　　int i,j,k=0,cjs;　　fp=fopen("codefile.txt","r");//一

127、只讀的方式打開文本文檔codefile.txt　　while(!feof(fp))//feof(fp)判斷文件是否真正結(jié)束，feof(fp)=1時(shí)文件結(jié)束　　{　　cjs=0;　　for(i=0;

128、i<num && cjs==0 && !feof(fp);i++)　　{　　cd[i]=' ';cd[i+1]='\0';　　cd[i]=fgetc(fp);//數(shù)組接受從fp指針?biāo)赶蛭募凶x入的一個(gè)字符

129、　　for(j=1;j<=num;j++)　　if(strcmp(HC[j].bits,cd)==0)//haffman編碼和密碼譯碼相比較　　{　　str[k]=HC[j].ch;&l

130、t;b>　　k++;　　cjs=1;break;　　}　　} 　　}　　str[k]=&#

131、39;\0';　　p=str;　　return p;　　}　　//*************************輸出HuffmanTree存儲結(jié)構(gòu)

132、*************************　　void print1(HuffmanTree HT)　　{　　int x; 　　for(x=1;x<=2*num-1;x++)<

133、/p>　　{ 　　HT[x].parent=0;　　HT[x].lchild=0;　　HT[x].rchild=0;　　printf("%11d %d\t %d\t %d\n"

134、,HT[x].weight,HT[x].parent,HT[x].lchild,HT[x].rchild);　　}　　printf("--------------------------------------\n");　　} <

135、/b>　　void print2(HuffmanTree HT)　　{　　int k;　　for(k=1;k<=2*num-1;k++) &

136、lt;b>　　{　　printf(" %d\t %d\t %d\t %d\n",HT[k].weight,HT[k].parent,HT[k].lchild,HT[k].rchild);　　}　　printf("----

137、----------------------------------\n");　　} 　　void DhuffmanTree(HuffmanTree HT,int cnt[],char str[])　　{

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

溫馨提示

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

數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼譯碼器課程設(shè)計(jì)報(bào)告(有源程序)

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)哈夫曼編碼譯碼器課程設(shè)計(jì)報(bào)告(有源程序)

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載