《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)成果報(bào)告-哈夫曼編碼的實(shí)現(xiàn).doc

河南工程學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)成果報(bào)告哈夫曼編碼的實(shí)現(xiàn)學(xué)生學(xué)號(hào)： 學(xué)生姓名： 學(xué) 院： 計(jì)算機(jī)學(xué)院 專(zhuān)業(yè)班級(jí)： 1341軟件工程 專(zhuān)業(yè)課程： 數(shù)據(jù)結(jié)構(gòu)與算法 指導(dǎo)教師： 2014 年 12 月 29 日題 目哈夫曼編碼的實(shí)現(xiàn)考核項(xiàng)目考核內(nèi)容得分平時(shí)考核（30分）出勤情況、態(tài)度、效率；知識(shí)掌握情況、基本操作技能、知識(shí)應(yīng)用能力、獲取知識(shí)能力系統(tǒng)設(shè)計(jì)（20分）分析系統(tǒng)的功能模塊編程調(diào)試（20分）實(shí)現(xiàn)系統(tǒng)的各個(gè)功能模塊，并完成調(diào)試回答問(wèn)題（15分）回答老師針對(duì)課程設(shè)計(jì)提出的問(wèn)題課程設(shè)計(jì)報(bào)告撰寫(xiě)（10分）嚴(yán)格按照規(guī)范要求完成課程設(shè)計(jì)報(bào)告源代碼（5分）按照規(guī)范要求完成課程設(shè)計(jì)源代碼的排版總 評(píng) 成 績(jī)指導(dǎo)教師評(píng)語(yǔ)： 日期： 年 月 日目 錄目 錄31 課程設(shè)計(jì)目標(biāo)與任務(wù)11.1 課程設(shè)計(jì)目標(biāo)11.2 課程設(shè)計(jì)任務(wù)11.3 設(shè)計(jì)內(nèi)容12 分析與設(shè)計(jì)22.1 題目需求分析22.2 存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)22.3 算法描述22.4 程序流程圖32.5 測(cè)試程序說(shuō)明63 程序清單74 測(cè)試104.1 測(cè)試數(shù)據(jù)104.2 測(cè)試結(jié)果分析105 總結(jié)11參考文獻(xiàn)121 課程設(shè)計(jì)目標(biāo)與任務(wù)1.1 課程設(shè)計(jì)目標(biāo)根據(jù)課堂講授的內(nèi)容，做相應(yīng)的自主練習(xí)，消化課堂所講解的內(nèi)容，通過(guò)調(diào)試典型例題或習(xí)題積累調(diào)試c程序的經(jīng)驗(yàn)，通過(guò)完成輔助教材中的編程題，逐漸培養(yǎng)學(xué)生的編程能力，用計(jì)算機(jī)解決實(shí)際問(wèn)題的能力。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的目標(biāo)是，通過(guò)設(shè)計(jì)掌握數(shù)據(jù)結(jié)構(gòu)課程中學(xué)到的基本理論和算法并綜合運(yùn)用于解決實(shí)際問(wèn)題中，它是理論與實(shí)踐相結(jié)合的重要過(guò)程。設(shè)計(jì)要求學(xué)會(huì)如何對(duì)實(shí)際問(wèn)題定義相關(guān)數(shù)據(jù)結(jié)構(gòu)，并采用恰當(dāng)?shù)脑O(shè)計(jì)方法和算法解決問(wèn)題，同時(shí)訓(xùn)練進(jìn)行復(fù)雜程序設(shè)計(jì)的技能和培養(yǎng)良好的程序設(shè)計(jì)習(xí)慣。1.2 課程設(shè)計(jì)任務(wù)1、深刻理解信源編碼的基本思想與目的；2、理解哈夫曼編碼方法的基本過(guò)程與特點(diǎn)；3、提高綜合運(yùn)用所學(xué)理論知識(shí)獨(dú)立分析和解決問(wèn)題的能力；4、使用MATLAB或其他語(yǔ)言進(jìn)行編程。5、編寫(xiě)的函數(shù)要有通用性；6、信源可以自由選擇，符號(hào)信源于圖像信源均可。1.3 設(shè)計(jì)內(nèi)容假設(shè)已知一個(gè)信源的各符號(hào)概率，編寫(xiě)適當(dāng)函數(shù)，對(duì)其進(jìn)行哈夫曼編碼，得出碼子，平均碼長(zhǎng)和編碼效率，總結(jié)該編碼方法的特點(diǎn)和運(yùn)用。1、從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)并將它存于文件haffTree中，將已在內(nèi)存中的哈夫曼樹(shù)以直觀的方式（比如樹(shù)）顯示在終端上；2、利用已經(jīng)建好的哈夫曼樹(shù)（如不在內(nèi)存，則從文件haffmTree中讀入），對(duì)文件TexT、txt中的正文進(jìn)行編碼，然后將結(jié)果存入文件Code.txt中。3、利用已建好的哈夫曼樹(shù)將文件Code.txt中的代碼進(jìn)行譯碼，結(jié)果存入文件TexT、txt中，并輸出結(jié)果。2 分析與設(shè)計(jì)2.1 題目需求分析該程序大體上有兩個(gè)功能：1、輸入任何一個(gè)字符串后，該程序能統(tǒng)計(jì)不同字符串的個(gè)數(shù)，并以不同字符串的個(gè)數(shù)作為權(quán)值。2、已知不同字母的權(quán)值，以該權(quán)值作為葉節(jié)點(diǎn)，構(gòu)造一顆帶權(quán)路徑最小的數(shù)，對(duì)該數(shù)從葉節(jié)點(diǎn)到根節(jié)點(diǎn)路徑分支遍歷，經(jīng)歷一個(gè)分支就得到一位哈夫曼編碼值。（規(guī)定哈夫曼樹(shù)種的左分支為0，右分支為1，則從根節(jié)點(diǎn)到每個(gè)葉節(jié)點(diǎn)所經(jīng)過(guò)的分支對(duì)應(yīng)的0和1組成的序列便為該結(jié)點(diǎn)對(duì)應(yīng)字符的編碼）2.2 存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)：typedef structint weight,flag,parent,leftChild,rightChild;HaffNode;Typedef structint bitMaxN,start,weight;/*數(shù)組編碼的起始下標(biāo)字符的權(quán)值*/Code;/*哈夫曼編碼結(jié)構(gòu)*/Int weight16;Char s30;2.3 算法描述1、統(tǒng)計(jì)模塊任意輸入一個(gè)字符串，不論字母是否相聯(lián)，字符串是否含空格都能統(tǒng)計(jì)出不同字母的個(gè)數(shù)。2、建立哈夫曼樹(shù)模塊以統(tǒng)計(jì)的字符串個(gè)數(shù)作為權(quán)值，利用仿真存儲(chǔ)結(jié)構(gòu)，建立帶權(quán)路徑最小的樹(shù)。其中對(duì)結(jié)點(diǎn)的存儲(chǔ)需要六個(gè)域，分別是weight域，flag域，parent域，leftChlid域，rightChild域。Weight域是對(duì)權(quán)值的存放，flag域是一個(gè)標(biāo)志域，flag=0時(shí)表示該結(jié)點(diǎn)尚未加入到哈夫曼樹(shù)中，flag=1時(shí)表示該結(jié)點(diǎn)已加入到哈夫曼樹(shù)中。3、哈夫曼編碼模塊從哈夫曼樹(shù)的葉節(jié)點(diǎn)到根節(jié)點(diǎn)路徑分支逐步遍歷，每經(jīng)過(guò)一個(gè)分支就得到一位赫夫曼編碼。赫夫曼編碼也利用仿真存儲(chǔ)結(jié)構(gòu)。4、主函數(shù)模板從屏幕上輸入字符串，調(diào)用函數(shù)，輸出每個(gè)字母的權(quán)值與編碼。開(kāi)始定義初始化變量nMHaffmanHaffmancodein結(jié)束輸入j=myHaffCodei.starjn輸出j+i+打印n越界2.4 程序流程圖1、主函數(shù)nyi=0y輸出nny 圖2-1主函數(shù)流程圖主函數(shù)中利用gets輸入一個(gè)字符串，統(tǒng)計(jì)不同字母的個(gè)數(shù)，在調(diào)用Haffman函數(shù)建立哈夫曼樹(shù)，然后調(diào)用HaffmanCode函數(shù)進(jìn)行編碼，如果成功，輸出權(quán)值與編碼，否則退出。2、統(tǒng)計(jì)函數(shù)開(kāi)始I=0，k=0，nin&si!=0Temp=1Jnj=si&i!=jTemp+PnP+結(jié)束Weightk+=tempI+ NSp=sp+1J+ 圖2-2 統(tǒng)計(jì)函數(shù)流程圖統(tǒng)計(jì)函數(shù)在統(tǒng)計(jì)不同字符個(gè)數(shù)時(shí)先利用一個(gè)for循環(huán)遍歷所有的字母每遍歷一個(gè)不同字母前令temp=1，然后用一個(gè)for循環(huán)將其后的字母與之比較，若相等則temp+，且將該字母從字符串中刪除，否則從下一個(gè)字母遍歷。如此循環(huán)直到字符串結(jié)束。in初始化結(jié)束Parent！=0haffTreeparen.leftChild=child開(kāi)始cd.bitcd.start=1 3、HffmanCode函數(shù)ncd.bitcd.start=0InhaffCodei.bitj=cd.bitjhaffCodei.start=cd.start;haffCodei.weight=cd.weight;I+cd.start-;child=parent;parent=haffTreechild.parent;圖2-3haffman函數(shù)流程圖可以利用二叉樹(shù)來(lái)設(shè)計(jì)二進(jìn)制的前綴編碼，假設(shè)有一顆二叉樹(shù)，其四個(gè)葉子結(jié)點(diǎn)分別為A,B,C,D這4個(gè)字符，且約定左分支表示字符0，右分支表示字符1，則可以從跟結(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑上分支字符組成的字符串作為該葉子節(jié)點(diǎn)字符的編碼。2.5 測(cè)試程序說(shuō)明主要有字符串統(tǒng)計(jì)源程序，哈夫曼樹(shù)建立源程序，哈夫曼樹(shù)編碼函數(shù)這三個(gè)組成，各自完成不同的任務(wù)，其中字符串統(tǒng)計(jì)程序主要是遍歷字符，哈夫曼程序主要是建立葉節(jié)點(diǎn)和根節(jié)點(diǎn)，哈夫曼編碼主要是確立分支編碼，然后形成編碼。1、 首先是哈夫曼樹(shù)的定義：假設(shè)有n個(gè)權(quán)值，試構(gòu)造一顆有n個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)，每個(gè)葉子帶權(quán)值為wi，其中樹(shù)帶權(quán)路徑最小的二叉樹(shù)成為哈夫曼樹(shù)或者最優(yōu)二叉樹(shù)；2、 哈夫曼樹(shù)的構(gòu)造：weight為輸入的頻率數(shù)組，把其中的值賦給依次建立的HTNode對(duì)象中的data屬性，即每一個(gè)HTNode對(duì)于一個(gè)輸入的頻度。然后根據(jù)data屬性按從小到大順序排序，每次從data取出兩個(gè)最小和次小的HTNode，將他們的data相加，構(gòu)造出新的HTNode作為他們的父結(jié)點(diǎn)，指針parent，leftchlid，rightchild賦相應(yīng)的值。在把這個(gè)新的結(jié)點(diǎn)插入最小堆。按此步驟可以構(gòu)造出一顆哈夫曼樹(shù)。通過(guò)已經(jīng)構(gòu)造出來(lái)的哈夫曼樹(shù)，自底向上，有頻率結(jié)點(diǎn)開(kāi)始向上尋找parent，直到parent為樹(shù)的頂點(diǎn)為止。這樣，根據(jù)每次向上搜索后，原結(jié)點(diǎn)為父結(jié)點(diǎn)的左孩子還是右孩子，來(lái)記錄1或0，這樣，每個(gè)頻率都會(huì)有一個(gè)01編碼與之唯一對(duì)應(yīng)，并且任何編碼沒(méi)有前部分是同其它完整編碼一樣的。3 程序清單1、 字符串統(tǒng)計(jì)源程序：int count(char*s,int*weight,int n)int I,j,temp,k=0,p;for(i=0;in&si!=0;i+)temp=1;for(j=0;jn;j+) /*遍歷相同的字母*/ if(sj=si&i!=j) temp+; for(p=j;pn;p+)/*刪除相同的字母*/ sp=sp+1; n-;j-;Weightk+=temp;/*temp作為權(quán)值賦給weight數(shù)組*/Return I;/* 返回權(quán)值個(gè)數(shù)*/2、 哈夫曼樹(shù)建立源程序void Haffman(int weight,int n,HaffNode haffTree)/*建立葉節(jié)點(diǎn)個(gè)數(shù)為n，權(quán)值數(shù)組為weight的哈夫曼樹(shù)HaffTree*/int I,j,m1,m2,x1,x2; For(i=0;i2*n-1;i+) if(in)haffTreei.flag=0;weighti;else haffTreei.weight=0;haffTreei.parent=0;haffTreei.flag=0;haffTreei.leftChild=-1;haffTreei.rightChild=-1;/* 構(gòu)造哈夫曼樹(shù)haffTree的n-1個(gè)非葉節(jié)點(diǎn)*/For(i=0;In-1;i+)m1=m2=MaxValue;X1=x2=0;For(j=0;jn+I;j+)if(haffTreej.weightm1&haffTreej,flag=0)m2=m1;X2=x1;M1=haffTreej.weightr;X1=j;Else if(haffTreej.weightm2&haffTreej,flag=0)m2=haffTreej.weightr;X2=j;/*將找出的兩顆權(quán)值最小的子樹(shù)合并為一顆子樹(shù)/*haffTreex1.parent=n+i;haffTreex2.parent=n+i;haffTreex1.flag=1;haffTreex2.flag=1haffTreen+i.weight=haffTreex1.weight+ haffTreex2.weight;haffTreen+i.leftChild=x1;haffTreen+i.rightChild=x2;3、哈夫曼樹(shù)編碼函數(shù)Void HaffmanCode(HaffNode haffTree,int n,Code haffCode)/*有n個(gè)結(jié)點(diǎn)的哈夫曼haffTree構(gòu)造哈夫曼編碼haffCode*/Code*cd=(Code*)malloc(sizeof(Code);Int I,j,child,parent;/*求n個(gè)結(jié)點(diǎn)的哈夫曼編碼*/For(i=0;in;i+)cd.start=n-1;cd.weight= haffTreei.weight;child=i;parent= haffTreechild.parent/*由葉節(jié)點(diǎn) 直到根節(jié)點(diǎn)*/while(parent!=0)if(haffTreeparent.leftChild=child)Cd.bitcd.start=0; /*左孩子分支編碼0/*Else Cd.bitcd.start=1; /*左孩子分支編碼1/*cd.start-;child=parent;parent=haffTreechild.parent;For（j= cd.start+1;jMaxN)printf(“給出的n越界，修改MaxN！n”);Exit(1);Haffman(weight,n,myHaffTree);HaffmanCode(myHaffTree,n,myHaffCode);For(i=0;in;i+)printf(“ ”,myHaffCodei.weight);For(j=myHaffCodei.start+1;jMaxN)printf(“給出的n越界，修改MaxN！n”);Exit(1);Haffman(weight,n,myHaffTree);HaffmanCode(myHaffTree,n,myHaffCode);For(i=0;in;i+)printf(“ ”,myHaffCodei.weight);For(j=myHaffCodei.start+1;jn;j+)Printf(”%d”,myHaffCodei.bitj);Printf(“n”);int count(char*s,int*weight,int n)int I,j,temp,k=0,p;for(i=0;in&si!=0;i+)temp=1;for(j=0;jn;j+) /*遍歷相同的字母*/ if(sj=si&i!=j) temp+; for(p=j;pn;p+)/*刪除相同的字母*/ sp=sp+1; n-;j-;Weightk+=temp;/*temp作為權(quán)值賦給weight數(shù)組*/Return I;/* 返回權(quán)值個(gè)數(shù)*/void Haffman(int weight,int n,HaffNode haffTree)/*建立葉節(jié)點(diǎn)個(gè)數(shù)為n，權(quán)值數(shù)組為weight的哈夫曼樹(shù)HaffTree*/int I,j,m1,m2,x1,x2; For(i=0;i2*n-1;i+) if(in)haffTreei.flag=0;weighti;else haffTreei.weight=0;haffTreei.parent=0;haffTreei.flag=0;haffTreei.leftChild=-1;haffTreei.rightChild=-1;/* 構(gòu)造哈夫曼樹(shù)haffTree的n-1個(gè)非葉節(jié)點(diǎn)*/For(i=0;In-1;i+)m1=m2=MaxValue;X1=x2=0;For(j=0;jn+I;j+)if(haffTreej.weightm1&haffTreej,flag=0)m2=m1;X2=x1;M1=haffTreej.weightr;X1=j;Else if(haffTreej.weightm2&haffTreej,flag=0)m2=haffTreej.weightr;X2=j;/*將找出的兩顆權(quán)值最小的子樹(shù)合并為一顆子樹(shù)/*haffTreex1.parent=n+i;haffTreex2.parent=n+i;haffTreex1.flag=1;haffTreex2.flag=1haffTreen+i.weight=haffTreex1.weight+ ha