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

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

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

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

文檔簡介

1、　　本科生課程設(shè)計說明書　　題目：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計　　—— 哈夫曼編碼和譯碼　　學(xué)生姓名： 　　學(xué) 號： 　　專

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

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

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

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

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

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

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

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

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

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

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

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

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

15、與葉子結(jié)點的編碼依次比較匹配。　　詳細設(shè)計　　工程視圖　　圖3.1工程視圖　　類圖視圖<p

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

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

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

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

20、p>　　錯誤輸入哈夫曼編碼代號：　　錯誤輸入哈夫曼編碼代碼串示意圖　　輸出：　　錯誤輸入哈夫曼編碼代碼串輸出示意圖 　　用戶手冊（可選）<

21、p>　　運行程序，程序首先會要求你輸入需要編碼的字符串，輸入完畢按回車即可進行編碼：　　程序啟動畫面　　輸出： 　　編碼輸出畫面　　輸出編碼后，程序會提

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

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

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

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

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

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

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

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

30、 h,int w)　　{　　code=c;　　letter=l;　　a=h;&

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

62、; //t置空　　break;　　}　　} 　　} 　　if

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

64、;sen;　　cout<<sen<<endl;　　}　　else //t如果沒有被置空，源碼無法被完全匹配　　{ cout<<"

65、二進制源碼有錯！從第"<<xx+1<<"位開始"<<endl;　　file2<<"二進制源碼有錯！從第"<<xx+1<<"位開始"<<endl;　　}</p&

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

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

68、;不能打開文件1!";　　return;　　}　　if(!file2)　　{　　cout<<&

69、quot;不能打開文件2!";　　return;　　}　　cout<<"\t\t\t\t哈夫曼編碼與譯碼\t\t\t\t"<<endl;　　c

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

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

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

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

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

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

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

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

78、t;　　k=0;　　symbol=1;　　while(symbol)　　{ 　　cin>

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

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

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

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

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

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

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

眾賞文庫> 全部分類> 畢業(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)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載