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

1、<p>　　本科生課程設(shè)計(jì)說(shuō)明書(shū)</p><p>　　題 目：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</p><p>　　—— 哈夫曼編碼和譯碼</p><p><b>　　學(xué)生姓名： </b></p><p><b>　　學(xué) 號(hào)： </b></p><p>　　專

2、業(yè)：軟件工程</p><p><b>　　班 級(jí)： </b></p><p><b>　　指導(dǎo)教師： </b></p><p>　　日 期：2016年1月8日</p><p><b>　　課程設(shè)計(jì)任務(wù)書(shū)</b></p><p><b&g

3、t;　　目 錄</b></p><p>　　內(nèi)蒙古科技大學(xué)課程設(shè)計(jì)任務(wù)書(shū)1</p><p>　　第一章 需求分析3</p><p>　　1.1程序的功能3</p><p>　　1.2輸入輸出的要求3</p><p>　　第二章概要設(shè)計(jì)3</p><p>　　2

4、.1總體設(shè)計(jì)3</p><p>　　2.2數(shù)據(jù)類型設(shè)計(jì)（或數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)）4</p><p>　　2.3接口設(shè)計(jì) //函數(shù)聲明5</p><p>　　第三章詳細(xì)設(shè)計(jì)6</p><p>　　3.1工程視圖6</p><p>　　3.2類圖視圖6</p><p>　　3.3

5、函數(shù)的調(diào)用關(guān)系7</p><p>　　3.4主程序流程圖8</p><p>　　3.5主要算法流程圖9</p><p>　　第四章測(cè)試分析11</p><p>　　4.1測(cè)試程序執(zhí)行情況11</p><p>　　第五章 用戶手冊(cè)（可選）12</p><p>　　第六章課程

6、設(shè)計(jì)總結(jié)13</p><p>　　附錄：程序代碼14</p><p><b>　　第一章 需求分析</b></p><p>　　1.1.程序的功能 </p><p>　　能對(duì)輸入的字符串實(shí)現(xiàn)Huffman編碼，且能利用生成的編碼對(duì)Huffman代碼串進(jìn)行譯碼，輸出相應(yīng)字符串。 </p>

7、;<p>　　2.2.輸入輸出的要求 </p><p>　　首先，輸入一個(gè)字符串，程序會(huì)列出字符串中包含的字符種類及每一種字符出現(xiàn)的次數(shù)，然后輸出通過(guò)Huffman編碼得到的各種字符的Huffman編碼。此時(shí)程序要求輸入一串Huffman代碼串，輸入完畢程序會(huì)判斷輸入的代碼串是否合法，若合法則輸出譯碼結(jié)果。 </p><p><b>　　概要設(shè)計(jì)

8、</b></p><p><b>　　總體設(shè)計(jì)</b></p><p>　　數(shù)據(jù)類型設(shè)計(jì)（或數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)）</p><p>　　enum Child{none,lchild,rchild}; //采用枚舉，標(biāo)記是左孩子還是右孩子</p><p>　　class element //元素類</p>

9、;<p><b>　　{</b></p><p>　　public://類的公有成員</p><p>　　elememt(); //構(gòu)造函數(shù)</p><p>　　void change(char l,char *c,int p,Child h,int w) //對(duì)對(duì)象進(jìn)行修改操作</p><p>　　vo

10、id getparent(int p) //對(duì)父結(jié)點(diǎn)的值進(jìn)行修改操作</p><p>　　void geta(Child h) //對(duì)孩子結(jié)點(diǎn)進(jìn)行修改操作</p><p>　　void getweight(int w) //對(duì)權(quán)值進(jìn)行修改操作</p><p>　　int returnweight() //返回權(quán)值操作</p><p>　　f

11、riend void Select(element h[],int k,int *a,int *b);//友元函數(shù)的聲明</p><p>　　friend void HuffmanTreeCode(element HT[]);</p><p>　　friend void HuffmanTreeYima(element huff[],char cod[],int b);</p>

12、<p>　　private://類的私有成員</p><p>　　char letter,*code; //letter為字符,*code指向編碼字符串 </p><p>　　int weight; //權(quán)值</p><p>　　int parent; //父結(jié)點(diǎn)</p>

13、;<p>　　Child a; //為父結(jié)點(diǎn)的左孩子還是右孩子</p><p><b>　　};</b></p><p><b>　　接口設(shè)計(jì) </b></p><p>　　主函數(shù)：對(duì)輸入的字符段進(jìn)行存儲(chǔ)，并對(duì)字符數(shù)和對(duì)應(yīng)的權(quán)值（字符個(gè)數(shù)）進(jìn)行統(tǒng)計(jì)存儲(chǔ)。</p>

14、<p>　　哈夫曼樹(shù)初始化函數(shù)：對(duì)給定的字符數(shù)和權(quán)值，創(chuàng)建一棵哈夫曼樹(shù)。</p><p>　　權(quán)值大小比較函數(shù)：找到每次所給集合的最小值和次小值，并返回給哈夫曼樹(shù)初始化函數(shù)。</p><p>　　哈夫曼樹(shù)編碼函數(shù)：對(duì)創(chuàng)建的哈夫曼樹(shù)，為左孩子的賦值為0，右孩子賦值為1，然后對(duì)葉子結(jié)點(diǎn)依次編碼。</p><p>　　哈夫曼樹(shù)譯碼函數(shù)：對(duì)輸入的01二進(jìn)制數(shù)一一

15、與葉子結(jié)點(diǎn)的編碼依次比較匹配。</p><p><b>　　詳細(xì)設(shè)計(jì)</b></p><p><b>　　工程視圖</b></p><p><b>　　圖3.1工程視圖</b></p><p><b>　　類圖視圖</b></p><p

16、><b>　　圖3.2類圖視圖</b></p><p><b>　　函數(shù)的調(diào)用關(guān)系</b></p><p><b>　　如下圖：</b></p><p>　　圖3.3函數(shù)調(diào)用關(guān)系圖</p><p><b>　　主程序流程圖</b></p>

17、<p>　　圖3.4主程序流程圖</p><p><b>　　主要算法流程圖</b></p><p>　　圖3.5.1哈夫曼編碼函數(shù)</p><p>　　圖3.5.2哈夫曼譯碼函數(shù)</p><p><b>　　測(cè)試分析</b></p><p><b>

18、　　測(cè)試程序執(zhí)行情況</b></p><p>　　準(zhǔn)備典型的測(cè)試數(shù)據(jù)和測(cè)試方案，包括正確的輸入及輸出結(jié)果和含有錯(cuò)誤的輸入及輸出結(jié)果：</p><p><b>　　輸入： </b></p><p><b>　　編碼輸入演示圖 </b></p><p><b>　　輸出：

19、</b></p><p><b>　　編碼輸出演示圖</b></p><p>　　正確輸入哈夫曼編碼代號(hào)：</p><p>　　正確譯碼輸入演示圖 </p><p><b>　　輸出：</b></p><p>　　正確輸入譯碼譯碼結(jié)果輸出演示圖</

20、p><p>　　錯(cuò)誤輸入哈夫曼編碼代號(hào)：</p><p>　　錯(cuò)誤輸入哈夫曼編碼代碼串示意圖</p><p><b>　　輸出：</b></p><p>　　錯(cuò)誤輸入哈夫曼編碼代碼串輸出示意圖 </p><p><b>　　用戶手冊(cè)（可選）</b></p><

21、p>　　運(yùn)行程序，程序首先會(huì)要求你輸入需要編碼的字符串，輸入完畢按回車即可進(jìn)行編碼：</p><p><b>　　程序啟動(dòng)畫(huà)面</b></p><p><b>　　輸出： </b></p><p><b>　　編碼輸出畫(huà)面</b></p><p>　　輸出編碼后，程序會(huì)提

22、示輸入需要譯碼的哈夫曼編碼串，輸入后按回車即可進(jìn)行譯碼：</p><p><b>　　譯碼輸入界面 </b></p><p><b>　　輸出：</b></p><p><b>　　譯碼輸出界面 </b></p><p>　　3.譯碼結(jié)束后，輸入N可退出程序，輸入Y可

23、繼續(xù)進(jìn)行譯碼。</p><p><b>　　課程設(shè)計(jì)總結(jié)</b></p><p>　　此次課程設(shè)計(jì)，我編寫程序的時(shí)候遇到了不少問(wèn)題，在攻克這些問(wèn)題，最終實(shí)現(xiàn)課題任務(wù)的過(guò)程中，我學(xué)到了不少東西： </p><p>　　首先，在完成一個(gè)課題之前，要仔細(xì)理解課題要求。我在此次課程設(shè)計(jì)中犯的最嚴(yán)重的錯(cuò)誤，應(yīng)該算沒(méi)有仔細(xì)審題。課題的要求是用讀取文件的方式

24、輸入需要編碼字符，譯碼所需的編碼代號(hào)也要用文本方式輸入。我在拿到這個(gè)課題的時(shí)候，因?yàn)闆](méi)有仔細(xì)理解這些要求，就采用了鍵盤輸入字符進(jìn)行編碼和譯碼的方式，以致沒(méi)有完全達(dá)到課題的要求。 </p><p>　　另外，這次課程設(shè)計(jì)充分暴露了我的惰性思想。在拿到這個(gè)課題后，因?yàn)閷?duì)哈夫曼編碼這個(gè)知識(shí)點(diǎn)理解比較到位，所以沒(méi)花多少時(shí)間就完成了課題要求實(shí)現(xiàn)的功能。然而，在此之后，我由于自我感覺(jué)良好和惰性，沒(méi)有積極地去尋找改進(jìn)程序的方

25、法，也沒(méi)對(duì)程序運(yùn)行的界面進(jìn)行美化，使其擁有良好的用戶使用體驗(yàn)。最終在考核的時(shí)候，交給老師的是一個(gè)界面簡(jiǎn)陋，功能不全面的程序。 </p><p>　　通過(guò)這次課程設(shè)計(jì)，我更加深入了理解了哈夫曼編碼的過(guò)程，以及利用哈夫曼編碼對(duì)數(shù)據(jù)進(jìn)行壓縮的優(yōu)越性，并且使我能夠更熟練地運(yùn)用樹(shù)形的數(shù)據(jù)結(jié)構(gòu)。并且體會(huì)到了在學(xué)習(xí)中，要嚴(yán)格要求自己，不能因?yàn)橐稽c(diǎn)點(diǎn)的成功就驕傲自滿，停止不前。</p><p><b

26、>　　附錄：程序代碼</b></p><p>　　#include <iostream.h></p><p>　　#include<fstream.h></p><p>　　#include <string.h></p><p>　　#include <malloc.h><

27、;/p><p>　　#include <stdio.h></p><p>　　const int Lengh=1000; //最大長(zhǎng)度為1000</p><p>　　char coding[100]; //存儲(chǔ)二進(jìn)制字符串</p><p>　　int n; //定義全局變量</p><

28、;p>　　ofstream file1("編碼.txt");; //創(chuàng)建編碼保存文件</p><p>　　ofstream file2("譯碼.txt");; //創(chuàng)建譯碼保存文件</p><p>　　enum Child{none,lchild,rchild}; //采用枚舉標(biāo)記事左孩子還是右孩子&l

29、t;/p><p>　　class element</p><p><b>　　{</b></p><p><b>　　public:</b></p><p>　　elememt();</p><p>　　void change(char l,char *c,int p,Child

30、 h,int w)</p><p><b>　　{</b></p><p><b>　　code=c;</b></p><p><b>　　letter=l;</b></p><p><b>　　a=h;</b></p><p>&

31、lt;b>　　weight=w;</b></p><p><b>　　parent=p;</b></p><p><b>　　}</b></p><p>　　void getparent(int p)</p><p><b>　　{</b></p>

32、<p><b>　　parent=p;</b></p><p><b>　　}</b></p><p>　　void geta(Child h)</p><p><b>　　{</b></p><p><b>　　a=h;</b></p

33、><p><b>　　}</b></p><p>　　void getweight(int w)</p><p><b>　　{</b></p><p><b>　　weight=w;</b></p><p><b>　　}</b>&l

34、t;/p><p>　　int returnweight()</p><p><b>　　{</b></p><p>　　return weight;</p><p><b>　　}</b></p><p>　　friend void Select(element h[],int

35、k,int *a,int *b);</p><p>　　friend void HuffmanTreeCode(element HT[]);</p><p>　　friend void HuffmanTreeYima(element huff[],char cod[],int b);</p><p><b>　　private:</b><

36、/p><p>　　char letter,*code; //letter為字符,*code指向編碼字符串 </p><p>　　int weight; //權(quán)值域</p><p>　　int parent; //父結(jié)點(diǎn)序號(hào)</p><p>　　Child a;

37、 //為父結(jié)點(diǎn)的左孩子還是右孩子</p><p><b>　　};</b></p><p>　　void Select(element h[],int k,int *a,int *b);//尋找最小和次小節(jié)點(diǎn)的序號(hào)</p><p>　　void InitHuffmanTree(element huffTree[],char

38、t[],int w[]) //哈夫曼樹(shù)的初始化</p><p><b>　　{</b></p><p>　　int i,m=2*n-1,s1,s2; //no+n2=n 所以一要申請(qǐng)m個(gè)空間</p><p>　　for(i=0;i<n;i++) //初始前n個(gè)結(jié)點(diǎn) </p><

39、;p><b>　　{</b></p><p>　　huffTree[i].change(t[i],'\0',-1,none,w[i]);</p><p><b>　　}</b></p><p>　　for(;i<=m;i++) //后m-n個(gè)結(jié)點(diǎn)置空</p&g

40、t;<p><b>　　{ </b></p><p>　　huffTree[i].change(' ','\0',-1,none,0);</p><p><b>　　}</b></p><p>　　for(i=n;i<m;i++) //建立哈夫曼樹(shù)&

41、lt;/p><p><b>　　{</b></p><p>　　Select(huffTree,i-1,&s1,&s2); //在huffTree中找權(quán)值最小的兩個(gè)結(jié)點(diǎn)s1,s2</p><p>　　huffTree[s1].getparent(i); //將s1,s2合并，則s1,s2的雙

42、親是i</p><p>　　huffTree[s2].getparent(i);</p><p>　　huffTree[s1].geta(lchild); //s1是左孩子</p><p>　　huffTree[s2].geta(rchild); //s2是右孩子</p><p>　　huffTree[i].get

43、weight(huffTree[s1].returnweight()+huffTree[s2].returnweight());//s1,s2的雙親的權(quán)值為s1，s2權(quán)值之和</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void Select(element h[],

44、int k,int *a,int *b) //尋找最小和次小節(jié)點(diǎn)的序號(hào) </p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　int min1=1000; //初始化最小結(jié)點(diǎn)和次小結(jié)點(diǎn) </

45、p><p>　　int min2=1000; </p><p>　　for (i=0;i<=k;i++)//找最小的結(jié)點(diǎn)序號(hào)</p><p><b>　　{ </b></p><p>　　if (h[i].parent==-1&&h[i].weight<min1) //如果沒(méi)有父結(jié)點(diǎn)并且它的權(quán)

46、值小于min1的權(quán)值</p><p><b>　　{ </b></p><p>　　*a=i; //將i放入a中</p><p>　　min1=h[i].weight; //找到第一個(gè)最小結(jié)點(diǎn)</p><p><b>　　} </b></p>

47、<p><b>　　}</b></p><p>　　for(i=0;i<=k;i++) //找次小結(jié)點(diǎn)的序號(hào) </p><p><b>　　{</b></p><p>　　if(h[i].parent==-1&&(*a!=i)&&h[i].weight&

48、lt;min2) //滿足沒(méi)有父結(jié)點(diǎn)，此序號(hào)不等于最小結(jié)點(diǎn)的序號(hào)，權(quán)值小于min2</p><p><b>　　{ </b></p><p><b>　　*b=i; </b></p><p>　　min2=h[i].weight; //找到次最小結(jié)點(diǎn)</p><p><b>　　

49、} </b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void HuffmanTreeCode(element HT[]) //字符編碼</p><p><b>　　{</b></p

50、><p><b>　　int i; </b></p><p>　　char *temp; </p><p>　　temp=(char *)malloc(n*sizeof(char)); //分配n個(gè)字符空間 </p><p>　　temp[n-1]='\0'; //最后一個(gè)字

51、符以后結(jié)束字符串</p><p><b>　　int p;</b></p><p><b>　　int s; </b></p><p>　　for(i=0;i<n;i++) //n個(gè)字符結(jié)點(diǎn)一個(gè)個(gè)處理</p><p><b>　　{ </b></p>

52、<p><b>　　p=i; </b></p><p>　　s=n-1; //s為最后一個(gè)結(jié)點(diǎn)</p><p>　　while(HT[p].parent!=-1) //從字符結(jié)點(diǎn)回溯,直至根結(jié)點(diǎn)</p><p><b>　　{</b></p><p

53、>　　if(HT[p].a==lchild) //p指向的如果是左孩子</p><p>　　temp[--s]='0'; //s位置字符為0</p><p>　　else if(HT[p].a==rchild) //p指向的如果是右孩子</p><p>　　temp[--s]='1';

54、 //s位置字符為1</p><p>　　p=HT[p].parent; //回溯父結(jié)點(diǎn)</p><p><b>　　} </b></p><p>　　HT[i].code=(char *)malloc((n-s)*sizeof(char));//分配結(jié)點(diǎn)編碼長(zhǎng)度的內(nèi)存空間 </p><p>　

55、　strcpy(HT[i].code,temp+s); //將temp中從第s個(gè)位置開(kāi)始，將編碼拷貝到 HT[i].code </p><p>　　printf("%c",HT[i].letter);</p><p>　　printf(": "); </p><p>　　printf(&qu

56、ot;%s\n",HT[i].code); //打印出字符即對(duì)應(yīng)的二進(jìn)制字符串 </p><p>　　file1<<HT[i].letter <<":"<<HT[i].code <<endl; //保存至編碼文件中</p><p><b>　　} </b>&l

57、t;/p><p><b>　　}</b></p><p>　　void HuffmanTreeYima(element huff[],char cod[],int b) //譯碼</p><p><b>　　{ </b></p><p>　　char sen[100]; </p

58、><p>　　char temp[50]; </p><p>　　char voidstr[]=" "; //空白字符串</p><p>　　int t=0; int s=0; </p><p><b>　　int xx=0;</b></p><p>　　for(int

59、 i=0 ; i<b; i++)</p><p><b>　　{ </b></p><p>　　temp[t++]=cod[i]; //讀取字符</p><p>　　temp[t] = '\0'; //有效字符串</p><p>　　for(int j=0;j<n;j++

60、) //依次與所有字符編碼開(kāi)始匹配</p><p><b>　　{ </b></p><p>　　if (!strcmp(huff[j].code,temp)) //匹配成功</p><p><b>　　{</b></p><p>　　sen[s]=hu

61、ff[j].letter; //將字符保存到sen中</p><p><b>　　s++; </b></p><p><b>　　xx+=t;</b></p><p>　　strcpy(temp,voidstr); //將TEMP置空 </p><p>　　t=0

62、; //t置空</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　} </b></p><p><b>　　} </b></p><p>　　if

63、(t==0) //t如果被置空了，表示都匹配出來(lái)了，打印譯碼</p><p><b>　　{</b></p><p>　　sen[s]='\0';</p><p>　　cout<<"譯碼為:"<<endl; </p><p>　　file2<<

64、;sen;</p><p>　　cout<<sen<<endl;</p><p><b>　　}</b></p><p>　　else //t如果沒(méi)有被置空 ， 源碼無(wú)法被完全匹配</p><p>　　{ cout<<"

65、二進(jìn)制源碼有錯(cuò)！從第"<<xx+1<<"位開(kāi)始"<<endl;</p><p>　　file2<<"二進(jìn)制源碼有錯(cuò)！從第"<<xx+1<<"位開(kāi)始"<<endl;</p><p><b>　　}</b></p&

66、gt;<p><b>　　} </b></p><p>　　void main()</p><p><b>　　{</b></p><p>　　char a[Lengh],p;</p><p>　　int i,b[Lengh]; </p><p>　　int s

67、ymbol=1;</p><p><b>　　int x;</b></p><p><b>　　int k;</b></p><p>　　if(!file1)</p><p><b>　　{</b></p><p>　　cout<<"

68、;不能打開(kāi)文件1!";</p><p><b>　　return;</b></p><p><b>　　}</b></p><p>　　if(!file2)</p><p><b>　　{</b></p><p>　　cout<<&

69、quot;不能打開(kāi)文件2!";</p><p><b>　　return;</b></p><p><b>　　}</b></p><p>　　cout<<"\t\t\t\t哈夫曼編碼與譯碼\t\t\t\t"<<endl;</p><p>　　c

70、out<<"編碼："<<endl;</p><p>　　cout<<"請(qǐng)輸入一句話進(jìn)行初始編碼：";</p><p>　　char buff[1024]={0};//零時(shí)存放輸入的話</p><p>　　cin.getline(buff,1024);//讀入一行包括空格鍵，以回車鍵結(jié)束<

71、;/p><p>　　int len=strlen(buff);</p><p>　　element h[Lengh];</p><p>　　for (i=0;i<len;i++)</p><p><b>　　{</b></p><p>　　for(int j=0;j<n;j++)</

72、p><p><b>　　{</b></p><p>　　if (a[j]==buff[i])</p><p><b>　　{</b></p><p>　　b[j]=b[j]+1;</p><p><b>　　break;</b></p><

73、;p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　if (j>=n)</b></p><p><b>　　{</b></p><p>　　a[n]=buff[i];</p><

74、p><b>　　b[n]=1;</b></p><p><b>　　n++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for (i=0;i<n;i++)</p>

75、<p><b>　　{</b></p><p>　　cout<<"字符："<<(char)a[i]<<" 權(quán)值："<<(int)b[i]<<endl;//a[]存字符 b[]存權(quán)值；</p><p><b>　　}</b></p&

76、gt;<p>　　InitHuffmanTree(h,a,b); //哈夫曼樹(shù)的初始化</p><p>　　HuffmanTreeCode(h); //編碼</p><p>　　cout<<"譯碼："<<endl;</p><p><b>　　while(1)</b>&l

77、t;/p><p><b>　　{ </b></p><p>　　cout<<"請(qǐng)輸入要譯碼的二進(jìn)制字符串,輸入'#'結(jié)束：";</p><p>　　file2<<"二進(jìn)制字符串:";</p><p><b>　　x=1;</b&g

78、t;</p><p><b>　　k=0;</b></p><p><b>　　symbol=1;</b></p><p>　　while(symbol)</p><p><b>　　{ </b></p><p><b>　　cin>

79、;>p; </b></p><p>　　if(p!='1'&&p!='0'&&p!='#') //若存在其它字符，x設(shè)為0，表示輸入的不是二進(jìn)制</p><p><b>　　{</b></p><p><b>　　x=0;</b&g

80、t;</p><p><b>　　}</b></p><p>　　coding[k]=p;</p><p>　　if(p=='#') </p><p>　　symbol=0; //#號(hào)結(jié)束標(biāo)志</p><p><b>　　else </b></p&g

81、t;<p><b>　　file2<<p;</b></p><p><b>　　k++;</b></p><p><b>　　}</b></p><p><b>　　if(x==1)</b></p><p><b>　　

82、{</b></p><p>　　file2<<endl<<"譯碼為:";</p><p>　　HuffmanTreeYima(h,coding,k-1); //進(jìn)行譯碼</p><p>　　file2<<endl;</p><p><b>　　}<

83、;/b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　cout<<"有非法字符！"<<endl;</p><p>　　file2<<endl<<"有非法字

84、符！"<<endl;</p><p><b>　　}</b></p><p>　　cout<<"是否繼續(xù)?(Y/N):";</p><p><b>　　cin>>p;</b></p><p>　　if(p=='y'||

85、p=='Y')</p><p><b>　　continue;</b></p><p><b>　　else</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p