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

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