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

1、精品文檔程序設(shè)計(jì)(大作業(yè))報(bào)告課程名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 設(shè)計(jì)題目：哈夫曼編碼器 院 系：信息技術(shù)學(xué)院 班 級(jí)：計(jì)算機(jī)科學(xué)與技術(shù)2 班設(shè) 計(jì) 者：郭彩丁 學(xué) 號(hào)：202111010205 指導(dǎo)教師：王亞寧 設(shè)計(jì)時(shí)間：2021.1.91 昆明學(xué)院昆明學(xué)院課程設(shè)計(jì)大作業(yè)任務(wù)書(shū)姓 名：郭彩丁 院 系：信息技術(shù)學(xué)院專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)專業(yè) 學(xué) 號(hào)：202111010205 任務(wù)起止日期：1 課程設(shè)計(jì)題目：哈夫曼編碼器 課程設(shè)計(jì)要求：1初始化：鍵盤輸入n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)2編碼：利用建好的huffman樹(shù)生成huffman編碼3輸出編碼4字符和頻度如下： 字符：空格 A B C D E

2、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 頻度：48 51 80 23 8 18 1 16工作方案及安排1在上機(jī)之前選題2選擇適宜的數(shù)據(jù)結(jié)構(gòu)3結(jié)點(diǎn)結(jié)構(gòu)的設(shè)計(jì)4算法設(shè)計(jì)與分析5程序設(shè)計(jì)、實(shí)現(xiàn)、調(diào)試6提交課程設(shè)計(jì)報(bào)告指導(dǎo)教師簽字 年 月 日 課程設(shè)計(jì)大作業(yè)成績(jī)學(xué)號(hào)：202111010205 姓名：郭彩丁 指導(dǎo)教師：王亞寧 老師課程設(shè)計(jì)題目： 哈夫曼編碼器 總結(jié)： 通過(guò)此次的課程設(shè)計(jì)使我認(rèn)識(shí)了哈夫曼樹(shù)的建立與應(yīng)用，復(fù)習(xí)了數(shù)據(jù)結(jié)構(gòu)中的樹(shù)的存儲(chǔ)結(jié)

3、構(gòu)，怎樣構(gòu)造哈夫曼樹(shù)以及用哈夫曼樹(shù)進(jìn)行編碼。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)能使我們?yōu)槠渌n程打好根底，而課程設(shè)計(jì)作為數(shù)據(jù)結(jié)構(gòu)中一個(gè)重要環(huán)節(jié)能更好的使我們加深對(duì)它的了解。指導(dǎo)教師評(píng)語(yǔ)：成績(jī)：填表時(shí)間：指導(dǎo)教師簽名： 目錄程序設(shè)計(jì)(大作業(yè))報(bào)告1昆明學(xué)院課程設(shè)計(jì)大作業(yè)任務(wù)書(shū)21.問(wèn)題描述52.根本要求53.數(shù)據(jù)結(jié)構(gòu)54.總體設(shè)計(jì)55.詳細(xì)設(shè)計(jì)65.1程序流程圖65.2初始化哈夫曼樹(shù)75.3輸入權(quán)值函數(shù)75.4選擇根結(jié)點(diǎn)，存放權(quán)值最小和次小序號(hào)75.5構(gòu)造哈夫曼樹(shù)75.6根據(jù)哈夫曼樹(shù)求哈夫曼編碼76.測(cè)試與調(diào)試76.1程序步驟演示7輸入各字符的權(quán)值7輸入字符8得到哈夫曼編碼86.2程序測(cè)試結(jié)果87.源程序清單108.

4、實(shí)驗(yàn)心得131.問(wèn)題描述 構(gòu)造一棵哈夫曼樹(shù)，根據(jù)所需輸入的字符數(shù)目，分別輸入字符的頻度和字符，得到它們相應(yīng)的編碼，也就是設(shè)計(jì)一個(gè)哈夫曼編碼器。2.根本要求以字符的頻度為權(quán)值，建立哈夫曼樹(shù)，求哈夫曼編碼。根據(jù)字符及權(quán)值得到其相應(yīng)的編碼。3.數(shù)據(jù)結(jié)構(gòu)typedef struct int weight; /*結(jié)點(diǎn)的權(quán)值*/int lchild,rchild,parent; /*左、右孩子及雙親的下標(biāo)*/htnode;typedef htnode huffmantreem+1; /* huffmantree是結(jié)構(gòu)數(shù)組類型,其0號(hào)單元不用，存儲(chǔ)哈夫曼樹(shù) */typedef structchar ch;

5、/*存儲(chǔ)字符*/ char coden+1; /*存放編碼位串*/codenode;typedef codenode huffmancoden+1; /*huffmancode是結(jié)構(gòu)數(shù)組類型,其0號(hào)單元不用,存儲(chǔ)哈夫曼編碼*/4.總體設(shè)計(jì)功能模塊劃分void main() /主函數(shù)void inithuffmantree(huffmantree ht) /初始化哈夫曼樹(shù)函數(shù)inithuffmantree()void inputweight(huffmantree ht) /輸入權(quán)值函數(shù) void selectmin(huffmantree ht, int i, int *p1, int *p2

6、)void createhuffmantree(huffmantree ht) /構(gòu)造huffman樹(shù)，htm為其根結(jié)void huffmancodes(huffmantree ht,huffmancode hcd) /*根據(jù)huffman樹(shù)ht求huffman編5.詳細(xì)設(shè)計(jì)5.1程序流程圖開(kāi)始設(shè)置字符數(shù)目n輸入權(quán)值假設(shè)輸入=n，輸入字符 N Y輸出編碼數(shù)結(jié)束5.2初始化哈夫曼樹(shù) void inithuffmantree(huffmantree ht)5.3輸入權(quán)值函數(shù)void inputweight(huffmantree ht)5.4選擇根結(jié)點(diǎn)，存放權(quán)值最小和次小序號(hào)void select

7、min(huffmantree ht, int i, int *p1, int *p2)5.5構(gòu)造哈夫曼樹(shù)void createhuffmantree(huffmantree ht)5.6根據(jù)哈夫曼樹(shù)求哈夫曼編碼void huffmancodes(huffmantree ht,huffmancode hcd)6.測(cè)試與調(diào)試 6.1程序步驟演示 輸入各字符的權(quán)值輸入字符得到哈夫曼編碼6.2程序測(cè)試結(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頻度：186 64 13 22

8、 32 103 21 15 47 57 1 2 32 20 57 63 15 17.源程序清單#include#include / 用到系統(tǒng)標(biāo)準(zhǔn)輸出函數(shù)的#include#include /用到像getch()這種鍵盤輸入函數(shù)/* Huffman 樹(shù)的存儲(chǔ)結(jié)構(gòu)*/#define n 9 /*葉子數(shù)目根據(jù)需要設(shè)定*/#define m 2*n-1 /* Huffman 樹(shù)中結(jié)點(diǎn)總數(shù) */* Huffman 樹(shù)的存儲(chǔ)結(jié)構(gòu)*/typedef struct /*結(jié)構(gòu)體定義*/int weight; /*結(jié)點(diǎn)的權(quán)值*/int lchild,rchild,parent; /*左、右孩子及雙親的下標(biāo)*/ht

9、node; /*哈夫曼樹(shù)結(jié)點(diǎn)類型*/typedef htnode huffmantreem+1; /* huffmantree是結(jié)構(gòu)數(shù)組類型,其0號(hào)單元不用，存儲(chǔ)哈夫曼樹(shù) */typedef structchar ch; /*存儲(chǔ)字符*/ char coden+1; /*存放編碼位串*/codenode; /*編碼結(jié)點(diǎn)類型*/typedef codenode huffmancoden+1; /*huffmancode是結(jié)構(gòu)數(shù)組類型,其0號(hào)單元不用,存儲(chǔ)哈夫曼編碼*/void inithuffmantree(huffmantree ht) /*初始化哈夫曼樹(shù)函數(shù)inithuffmantree()

10、*/int i; for(i=0;i=m;i+) hti.weight=0; hti.lchild=hti.rchild=hti.parent=0; void inputweight(huffmantree ht) /*輸入權(quán)值函數(shù) */int i; for(i=1;i=n;i+) printf( 請(qǐng)輸入第%d個(gè)權(quán)值: ,i);scanf(%d,&hti.weight); printf(n); void selectmin(huffmantree ht, int i, int *p1, int *p2)/* 在ht1.i中選兩個(gè)權(quán)值最小的根結(jié)點(diǎn)，其序號(hào)為*p1和*p2，*p1中放權(quán)值最小的根結(jié)

11、點(diǎn)的序號(hào)，*p2中放權(quán)值次小的根結(jié)點(diǎn)的序號(hào)*/int j,min1,min2; /* min1,min2分別是最小權(quán)值和次小權(quán)值*/ min1=min2=32767; *p1=*p2=0; for(j=1;j=i;j+) if(htj.parent=0) /* j 為根結(jié)點(diǎn)*/ if(htj.weightmin1|min1=32767) if(min1!=32767) min2=min1; *p2=*p1; min1=htj.weight; *p1=j; else if(htj.weightmin2|min2=32767) min2=htj.weight; *p2=j; void create

12、huffmantree(huffmantree ht) /*構(gòu)造huffman樹(shù)，htm為其根結(jié)點(diǎn)*/ int i,p1,p2; inithuffmantree(ht); /* 將ht初始化*/ inputweight(ht); /* 輸入葉子權(quán)值至ht 1.n的weight域*/ for(i=n+1;i=m;i+) /* 共進(jìn)行n-1次合并，新結(jié)點(diǎn)依次存于hti中*/ selectmin(ht,i-1,&p1,&p2); /*在ht 1. i-1中選擇兩個(gè)權(quán)值最小的根結(jié)點(diǎn)，其序號(hào)分別為p1和p2*/ htp1.parent=htp2.parent=i; hti.lchild=p1; /* 最

13、小權(quán)值的根結(jié)點(diǎn)是新結(jié)點(diǎn)的左孩子*/ hti.rchild=p2; /* 次小權(quán)值的根結(jié)點(diǎn)是新結(jié)點(diǎn)的右孩子*/ hti.weight=htp1.weight+htp2.weight; void huffmancodes(huffmantree ht,huffmancode hcd) /*根據(jù)huffman樹(shù)ht求huffman編碼*/int c,p,i; /* c和p分別指示 ht中孩子和雙親的位置 */char cdn+1; /* 臨時(shí)存放編碼*/int start; /* 指示編碼在cd 中的起始位置*/cdn=0; getchar(); /* 編碼結(jié)束符*/printf(2.請(qǐng)依次輸入字符

14、:); for(i=1;i=n;i+) /* 依次求葉子ht i的編碼*/ hcdi.ch=getchar(); /* 讀入葉子ht i對(duì)應(yīng)的字符*/ start=n; /* 編碼起始位置的初值*/ c=i; /* 從葉子ht i開(kāi)始上溯*/ while(p=htc.parent)!=0) /* 直至上溯到ht c是樹(shù)根為止*/ cd-start=(htp.lchild=c)?0:1; /*假設(shè)ht c是htp的左孩子，那么生成代碼0，否那么生成代碼1*/ c=p; /* 繼續(xù)上溯*/ strcpy(hcdi.code,&cdstart); /* 復(fù)制編碼位串*/ printf(n);printf(3.哈夫曼編碼結(jié)果為：n);printf(n);for(i=1;i=n;i+)printf( 第%d個(gè)字符%c的編碼為：%sn,i,hcdi.ch,hcdi.code);void main()huffmantree t; huffmancode h; printf(|*#*|n); printf(|*歡送使用哈弗曼編碼系統(tǒng)！*|n); printf(|*#*|n); printf(n); printf(1.請(qǐng)輸入%d個(gè)權(quán)值:n,n); printf(n); createhuffmantree(t); /* 構(gòu)造huffman樹(shù)*/ huffmancodes(t,h); /*