數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---哈夫曼編碼器

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---哈夫曼編碼器_第1頁

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

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

文檔簡介

1、　　程序設(shè)計(大作業(yè))報告　　課程名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 　　設(shè)計題目：哈夫曼編碼器 　　院系：信息技術(shù)學(xué)院 　　班級：計算機(jī)科學(xué)與技術(shù)2 班　　設(shè) 計者：

2、 　　學(xué) 號： 　　指導(dǎo)教師： 　　設(shè)計時間：2012.1.9-2012.1.11 　　課程設(shè)計（大作業(yè)）任務(wù)書　　課程設(shè)計題目：哈夫曼編碼器 &l

3、t;/p>　　課程設(shè)計要求：　　（1）初始化：鍵盤輸入n個字符和n個權(quán)值，建立哈夫曼樹　?。?）編碼：利用建好的huffman樹生成huffman編碼　　（3）輸出編碼

4、　　（4）字符和頻度如下：　?、?字符：空格 A B C D E F G H I J K L M N O P Q　　頻度：186 64 13 22 32 103 21 15 47 57 1 2 32 20 57 63 15 1　?、?字符：R S T U V W X Y Z

5、;　　頻度：48 51 80 23 8 18 1 16　　工作計劃及安排　　（1）在上機(jī)之前選題　?。?）選擇合適的數(shù)據(jù)結(jié)構(gòu)　?。?）結(jié)點(diǎn)結(jié)構(gòu)的設(shè)計　　（4）算法設(shè)計與分析

6、　　（5）程序設(shè)計、實現(xiàn)、調(diào)試　?。?）提交課程設(shè)計報告　　指導(dǎo)教師簽字 　　年月日 　　課程設(shè)計（大作業(yè)）成績　　學(xué)號：姓名：指導(dǎo)教師：

7、老師　　課程設(shè)計題目：哈夫曼編碼器 　　總結(jié)：　　通過此次的課程設(shè)計使我認(rèn)識了哈夫曼樹的建立與應(yīng)用，復(fù)習(xí)了數(shù)據(jù)結(jié)構(gòu)中的樹的存儲結(jié)構(gòu)，怎樣構(gòu)造哈夫曼樹以及用哈夫曼樹進(jìn)行編碼。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)能使我們?yōu)槠渌n程打好基礎(chǔ)，而課程設(shè)計作為數(shù)據(jù)結(jié)構(gòu)中一個重要環(huán)節(jié)能更好的使我們加深

8、對它的了解。　　指導(dǎo)教師評語：　　成績：　　填表時間：　　指導(dǎo)教師簽名： 　　目錄&

9、lt;/b>　　程序設(shè)計(大作業(yè))報告1　　昆明學(xué)院課程設(shè)計（大作業(yè)）任務(wù)書2　　1.問題描述5　　2.基本要求5　　3.

10、數(shù)據(jù)結(jié)構(gòu)5　　4.總體設(shè)計5　　5.詳細(xì)設(shè)計6　　5.1程序流程圖6　　5.2初始化哈夫曼樹7　　5.3輸入權(quán)值函數(shù)7&l

11、t;/p>　　5.4選擇根結(jié)點(diǎn)，存放權(quán)值最小和次小序號7　　5.5構(gòu)造哈夫曼樹7　　5.6根據(jù)哈夫曼樹求哈夫曼編碼7　　6.測試與調(diào)試7　　6.1程序步驟演示7<p&

12、gt;　　6.1.1輸入各字符的權(quán)值7　　6.1.2輸入字符8　　6.1.3得到哈夫曼編碼8　　6.2程序測試結(jié)果8　　7.源程序清單10　　8.實驗心得13

13、　　1.問題描述　　構(gòu)造一棵哈夫曼樹，根據(jù)所需輸入的字符數(shù)目，分別輸入字符的頻度和字符，得到它們相應(yīng)的編碼，也就是設(shè)計一個哈夫曼編碼器。　　2.基本要求　　以字符的頻度為權(quán)值，建立哈夫曼樹，求哈夫曼編碼。根據(jù)字符及權(quán)值

14、得到其相應(yīng)的編碼。　　3.數(shù)據(jù)結(jié)構(gòu)　　typedef struct 　　{int weight; /*結(jié)點(diǎn)的權(quán)值*/　　int lchild,rchild,parent;

15、 /*左、右孩子及雙親的下標(biāo)*/　　}htnode;　　typedef htnode huffmantree[m+1]; /* huffmantree是結(jié)構(gòu)數(shù)組類型,其0號單元不用，存儲哈夫曼樹 */　　typedef struct

16、;　　{char ch; /*存儲字符*/　　char code[n+1]; /*存放編碼位串*/　　}codenode;　　typedef codenode huffmancode[n+1]; /*huffmancode是結(jié)構(gòu)數(shù)組

17、類型,其0號單元不用,存儲哈夫曼編碼*/　　4.總體設(shè)計　　功能模塊劃分　　void main() //主函數(shù)　　void inithuffmantree

18、(huffmantree ht) //初始化哈夫曼樹函數(shù)inithuffmantree()　　void inputweight(huffmantree ht) //輸入權(quán)值函數(shù) 　　void selectmin(huffmantree ht, int i, int *p1, int *p2)　　vo

19、id createhuffmantree(huffmantree ht) //構(gòu)造huffman樹，ht[m]為其根結(jié)　　void huffmancodes(huffmantree ht,huffmancode hcd) /*根據(jù)huffman樹ht求huffman編　　5.詳細(xì)設(shè)計<

20、;p>　　5.1程序流程圖　　N　　Y　　5.2初始化哈夫曼樹　　void inithuffmantree(huffmantree ht)</p&

21、gt;　　5.3輸入權(quán)值函數(shù)　　void inputweight(huffmantree ht)　　5.4選擇根結(jié)點(diǎn)，存放權(quán)值最小和次小序號　　void selectmin(huffmantree ht, int i, int *p1, int

22、*p2)　　5.5構(gòu)造哈夫曼樹　　void createhuffmantree(huffmantree ht)　　5.6根據(jù)哈夫曼樹求哈夫曼編碼　　void huffmancodes(huffmantree ht,huffmanco

23、de hcd)　　6.測試與調(diào)試　　6.1程序步驟演示　　6.1.1輸入各字符的權(quán)值　　6.1.2輸入字符　　6.

24、1.3得到哈夫曼編碼　　6.2程序測試結(jié)果　　字符：R S T U V W X Y Z　　頻度：48 51 80 23 8 18 1 16 10　　字符: A B C D E F G H I J K L M N O P Q</

25、p>　　頻度：186 64 13 22 32 103 21 15 47 57 1 2 32 20 57 63 15 1　　7.源程序清單　　#include<stdio.h>　　#include<stdlib.h>

26、 // 用到系統(tǒng)標(biāo)準(zhǔn)輸出函數(shù)的　　#include<string.h>　　#include<conio.h> //用到像getch()這種鍵盤輸入函數(shù)　　/* Huffman 樹的存儲結(jié)構(gòu)*/　　#defi

27、ne n 9 /*葉子數(shù)目根據(jù)需要設(shè)定*/　　#define m 2*n-1 /* Huffman 樹中結(jié)點(diǎn)總數(shù) */　　/* Huffman 樹的存儲結(jié)構(gòu)*/　　typedef struct /*結(jié)構(gòu)體定義*/

28、{int weight; /*結(jié)點(diǎn)的權(quán)值*/　　int lchild,rchild,parent; /*左、右孩子及雙親的下標(biāo)*/　　}htnode; /*哈夫曼樹結(jié)點(diǎn)類型*/　　typedef htnode huffmantree[m+1]; /

29、* huffmantree是結(jié)構(gòu)數(shù)組類型,其0號單元不用，存儲哈夫曼樹 */　　typedef struct　　{char ch; /*存儲字符*/　　char code[n+1]; /*存放編碼位串*/　　}codenode

30、; /*編碼結(jié)點(diǎn)類型*/　　typedef codenode huffmancode[n+1]; /*huffmancode是結(jié)構(gòu)數(shù)組類型,其0號單元不用,存儲哈夫曼編碼*/　　void inithuffmantree(huffmantree ht) /*初始化哈夫曼樹函數(shù)inithuffmantree

31、()*/　　{int i;　　for(i=0;i<=m;i++)　　{ht[i].weight=0;　　ht[i].lchild=ht[i].rchild=ht[i].parent=0;

32、　　}　　}　　void inputweight(huffmantree ht) /*輸入權(quán)值函數(shù) */　　{int i;　　for(i=1

33、;i<=n;i++)　　{　　printf(" ……請輸入第[%d]個權(quán)值: ",i);　　scanf("%d",&ht[i].weight);　　}</

34、b>　　printf("\n");　　}　　void selectmin(huffmantree ht, int i, int *p1, int *p2)　　/* 在ht[1..i]中選兩個權(quán)值最小的

35、根結(jié)點(diǎn)，其序號為*p1和*p2，*p1中放權(quán)值最小的根結(jié)點(diǎn)的序號，*p2中放權(quán)值次小的根結(jié)點(diǎn)的序號*/　　{int j,min1,min2; /* min1,min2分別是最小權(quán)值和次小權(quán)值*/　　min1=min2=32767;　　*p1=*p2=0;</p&

36、gt;　　for(j=1;j<=i;j++)　　{if(ht[j].parent==0) /* j 為根結(jié)點(diǎn)*/　　if(ht[j].weight<min1||min1==32767)　　{&l

37、t;p>　　if(min1!=32767) {min2=min1; *p2=*p1;}　　min1=ht[j].weight; *p1=j;　　}　　else　　if(ht[j].

38、weight<min2||min2==32767)　　{min2=ht[j].weight; *p2=j;}　　}　　}　　void createhuffmantree(huffmantr

39、ee ht) /*構(gòu)造huffman樹，ht[m]為其根結(jié)點(diǎn)*/　　{ 　　int i,p1,p2;　　inithuffmantree(ht); /* 將ht初始化*/　　inputweight(ht)

40、; /* 輸入葉子權(quán)值至ht [1..n]的weight域*/　　for(i=n+1;i<=m;i++) /* 共進(jìn)行n-1次合并，新結(jié)點(diǎn)依次存于ht[i]中*/　　{selectmin(ht,i-1,&p1,&p2); /*在ht [1.. i-1]中選

41、擇兩個權(quán)值最小的根結(jié)點(diǎn)，其序號分別為p1和p2*/　　ht[p1].parent=ht[p2].parent=i;　　ht[i].lchild=p1; /* 最小權(quán)值的根結(jié)點(diǎn)是新結(jié)點(diǎn)的左孩子*/　　ht[i].rchild=p2; /* 次小權(quán)值的根結(jié)點(diǎn)是新

42、結(jié)點(diǎn)的右孩子*/　　ht[i].weight=ht[p1].weight+ht[p2].weight;　　}　　}　　void huffmancodes(huffmantree ht,huffma

43、ncode hcd) /*根據(jù)huffman樹ht求huffman編碼*/　　{　　int c,p,i; /* c和p分別指示 ht中孩子和雙親的位置 */　　char cd[n+1];

44、 /* 臨時存放編碼*/　　int start; /* 指示編碼在cd 中的起始位置*/　　cd[n]='\0'; 　　getchar(); /* 編碼結(jié)束符*/

45、　　printf("2.……請依次輸入字符……:");　　for(i=1;i<=n;i++) /* 依次求葉子ht [i]的編碼*/　　{ hcd[i].ch=getchar(); /* 讀入葉子ht [i]對應(yīng)的字符*/</p&

46、gt;　　start=n; /* 編碼起始位置的初值*/　　c=i; /* 從葉子ht [i]開始上溯*/　　while((p=ht[c].parent)!=0) /* 直至上溯到ht [ c]是樹根為止*/&

47、lt;p>　　{ cd[--start]=(ht[p].lchild==c)?'0':'1'; /*若ht [ c]是ht[p]的左孩子，則生成代碼0，否則生成代碼1*/　　c=p; /* 繼續(xù)上溯*/　　}<

48、/b>　　strcpy(hcd[i].code,&cd[start]); /* 復(fù)制編碼位串*/　　}　　printf("\n");　　printf("3.………哈夫曼編碼結(jié)果

49、為：……\n");　　printf("\n");　　for(i=1;i<=n;i++)　　printf(" ……第[%d]個字符[%c]的編碼為：%s\n",i,hcd[i].ch,hcd[i].code);<

50、;b>　　}　　void main()　　{huffmantree t;　　huffmancode h;　　printf("|^^^^^^^^^^^^^^^^^^^^^^^^^^^*########################*^^

51、^^^^^^^^^^^^^^^^^|\n");　　printf("|^^^^^^^^^^^^^^^^^^^^^^^^^^^*歡迎使用哈弗曼編碼系統(tǒng)！*^^^^^^^^^^^^^^^^^^^|\n");　　printf("|^^^^^^^^^^^^^^^^^^^^^^^^^^^*###################

52、#####*^^^^^^^^^^^^^^^^^^^|\n");　　printf("\n");　　printf("1.…………請輸入%d個權(quán)值:……\n",n);　　printf("\n");　　crea

53、tehuffmantree(t); /* 構(gòu)造huffman樹*/　　huffmancodes(t,h); /* 構(gòu)造huffman編碼*/　　}　　8.實驗心得&

54、lt;/b>　　通過這次課程設(shè)計，使我獲益匪淺。學(xué)好數(shù)據(jù)結(jié)構(gòu)對于我們是非常重要的，能使我們在以后的程序設(shè)計方面給我們很大的幫助。以此同時，這門課程的學(xué)習(xí)也是非常艱辛的，因為它比較抽象難懂，這需要我們在實踐中不斷的克服。　　將近一個多星期的設(shè)計工作，讓我體會到作為一個編程人員是非常辛苦的。一個程序從算法到實現(xiàn)，再到應(yīng)用開發(fā)是需要走很長的一段路，不是一

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

溫馨提示

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)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---哈夫曼編碼器

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---哈夫曼編碼器

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載