《數據結構與算法》課程設計成果報告-哈夫曼編碼的實現(xiàn).doc

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