長春大學課程設計(哈夫曼)

1、長 春 大 學課 程 設 計 說 明 書題目名稱 哈夫曼編碼/ 譯碼器 院（系） 計算機科學與技術 專業(yè)（班級） 網(wǎng)絡五班 學生姓名 董迎順 指導教師 朱德新 起止日期 2015.9.7-2015.9.11 目 錄1.設計目的與任務12.算法設計32.1設計思想32.2設計表示33.用戶手冊44.測試數(shù)據(jù)及測試結(jié)果55.課程設計總結(jié)9程序清單91.設計目的與任務1.1設計目的：（1）了解并掌握數(shù)據(jù)結(jié)構與算法的設計方法，具備初步的獨立分析和設計力；（2）初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼、測試等基本方法和技能；（3）提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；（4）

2、訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所具備的科學的工作方法和作風。1.2 設計任務：設計一個利用哈夫曼算法的編碼和譯碼系統(tǒng)，重復地顯示并處理以下項目，直到選擇退出為止。2.算法設計2.1設計思想（1）數(shù)據(jù)結(jié)構設計對問題描述中涉及的操作對象定義相應的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。 本程序定義了相應的結(jié)構體變量，包括weight權值，parent雙親結(jié)點，lchild左孩子，rchild右孩子。通過結(jié)構體構建哈夫曼樹，實現(xiàn)哈夫曼的編碼和譯碼功能。結(jié)構體變量如下：typedef struct/結(jié)構體 char data; i

3、nt weight; /權值 int parent;/雙親結(jié)點 int lchild;/左孩子 int rchild;右孩子 HTNode; HTNode ht80; 功能：該結(jié)構體儲存相關數(shù)據(jù)包括輸入的權值weight，構建哈夫曼樹所需要的雙親parent，左孩子lchild，右孩子rchild。同時建立結(jié)構體數(shù)組HTNode ht80;typedef struct char cd30; /字符串 int start;HCode; HCode hcd80;功能：該結(jié)構體儲存輸入的字符。（2）算法設計 本程序在運行過程中用到的算法是哈弗曼算法，它是由n個帶權葉子結(jié)點構成的所有二叉樹中帶權路徑長

4、度最短的二叉樹，根據(jù)給定的n個權值構成n棵二叉樹的集合，其中每棵二叉樹中只有一個帶權weight的根結(jié)點，左右子樹均空，選擇兩棵根結(jié)點權值最小的樹作為左右子樹構造一棵新的二叉樹，且至新的二叉樹的根結(jié)點的權值為其左右子樹上根結(jié)點的權值之和，即為哈夫曼樹算法。本程序先定義結(jié)構體，通過創(chuàng)建哈弗曼樹，對輸入的字符進行編碼和譯碼。2.2設計表示（1）函數(shù)調(diào)用關系圖及其說明如下：哈夫曼編/譯碼器 主函數(shù)main（）初始化哈弗曼樹CreateHT（）輸入CodeInput（）顯示哈夫曼樹Shuchu（）哈夫曼編碼CreateHCode（）保存save（） 結(jié)束exit（）（2）函數(shù)接口說明：函數(shù)中的參數(shù)均是

5、使用的全局變量的傳遞，因而在函數(shù)間進行傳遞的過程中比較簡單，下面就將主要函數(shù)及他們之間的參數(shù)的關系列出如下：void CodeInput(int n,HTNode ht)/輸入字符及權值 進行哈夫曼編碼void CreateHCode( HTNode ht , HCode hcd , int n )/進行哈夫曼編碼void CodeOutput( int n , HCode hcd )函數(shù)輸出哈夫曼編碼。void shuchu(HCode hcd , int n)/輸出哈夫曼樹void save( int n)/ 將其存入data.text文件中3.用戶手冊 點擊運行程序，在彈出的窗口中，會提

6、示要輸入的信息：（1）界面信息：顯示5個選項，分別為1：輸入哈夫曼樹2：哈夫曼編碼3：顯示哈夫曼樹4：哈夫曼權值存儲5：退出。（2）操作：用戶輸入界面的1-5選項，若輸入其他選項則提示（"輸入有誤 ! 請輸入 <1 - 5>選項），程序分別調(diào)用相關函數(shù)。（3）用戶需要輸入哈夫曼樹，程序會生成哈夫曼編碼和哈夫曼樹并顯示在屏幕上，可以對哈夫曼權值保存。當退出時，選擇5 直接退出。4.測試數(shù)據(jù)及測試結(jié)果測試數(shù)據(jù)如下：a s d f g h7 8 9 4 5 2程序運行結(jié)果如下:圖1：菜單顯示界面，選擇操作類型。圖2：選擇1，輸入哈夫曼樹，先輸入所有字符然后輸入權值。圖3：選擇2

7、，輸出哈夫曼編碼。圖4：選擇3，顯示哈夫曼樹。圖5：選擇4，保存哈夫曼權值到"d:data.txt"。圖6：選擇5，退出程序。5.課程設計總結(jié)在這次課程設計過程中，遇到了很多困難，之前對哈夫曼算法不是很了解，在編寫源代碼時有很多知識都忘了，多次翻閱課本學習，網(wǎng)上查找相關資料，使得編寫的效率很慢。調(diào)試程序的過程中，出現(xiàn)了很多錯誤，逐個分析每一個錯誤，我學到了很多東西，比如一些課上沒有懂的知識，我通過實踐搞懂了，而且通過此次的課程設計，讓我更深入的理解數(shù)據(jù)結(jié)構，并且還運用了以前所學的有關C語言的知識，并且應用到我的程序中去，對哈夫曼樹也有了更深的了解，并且真正會用這種算法了，通

8、過不斷的改正錯誤，我的程序有了更高的質(zhì)量。在編寫的時候也犯了很多不該犯的錯誤，不過我及時糾正了，遺憾的是，我的程序功能不是很全，某些部分沒有按照要求去做，說明我的編程能力有待提高。程序清單#include <stdio.h>#include <string.h>#include <stdlib.h>typedef struct/結(jié)構體 char data; int weight; /權值 int parent; /雙親結(jié)點 int lchild; /左孩子 int rchild; /右孩子 HTNode; HTNode ht80; typedef struc

9、t char cd30; int start; HCode; HCode hcd80; void CreateHT( HTNode ht , int n )/創(chuàng)建哈弗曼樹 int i , k , lnode, rnode ;int min1 , min2 ; for ( i = 0 ; i < 2*n-1 ; i+ ) hti.parent = hti.lchild = hti.rchild = 0; for ( i = n ; i < 2*n-1 ; i+ ) min1 = min2 = 9999; lnode = rnode = 0; for ( k=0 ; k <= i

10、-1; k+) if ( htk.parent = 0) if (htk.weight < min1) min2 = min1;min1 = htk.weight;rnode = lnode; lnode = k; else if ( htk.weight < min2) min2 = htk.weight;rnode = k; htlnode.parent = i; htrnode.parent = i; hti.weight = htlnode.weight + htrnode.weight; hti.lchild = lnode;hti.rchild = rnode; voi

11、d CreateHCode( HTNode ht , HCode hcd , int n )/進行哈夫曼編碼 int i , f , c; HCode hc;for( i = 0 ; i < n; i+) hc.start = n; c = i; f = hti.parent; while (f != 0) if( htf.lchild = c) hc.cdhc.start- = '0' else hc.cdhc.start- = '1' c=f ; f=htf.parent; hc.start+; hcdi = hc; void CodeInput(in

12、t n,HTNode ht)/輸入字符及權值 進行哈夫曼編碼 int i; char ch30; scanf( "%s" , ch ); for ( i=0 ; i<n ; i+ )scanf( "%ld" , &hti.weight );printf("*- n");void CodeOutput( int n , HCode hcd )/輸出哈夫曼編碼 int i , j ; printf (" 所有字符的哈弗曼編碼為:"); for ( i = 0 ; i < n ; i+ ) for(

13、j=hcdi.start ; j<=n ; j+ ) printf( "%lc" , hcdi.cdj ); printf("n");for ( i=0 ; i<n ; i+ )printf( " 序號%d : " , i );for( j = hcdi.start ; j <= n ; j+ ) printf( "%lc" , hcdi.cdj ); printf( "n" ); void shuchu(HCode hcd , int n)/輸出哈夫曼樹int i; prin

14、tf("nHTi:t權值t雙親t左孩子t右孩子n"); for(i = 1;i<2*n;i+) /共打?。?*len-1）組 if(i <= n) printf("%2d:t %2d;t%2d,t %2d,t %2d.n",i,hti.weight,hti.parent,hti.lchild,hti.rchild); /打印代碼相應的權值，雙親左右孩子 void save( int n)/ 將其存入data.text文件中int i ;FILE *fp;if( ( fp = fopen ( "d:data.txt" , &

15、quot;w" ) ) = NULL ) printf( " can't open this file ! " ) ;exit(0) ;elsefor ( i = 1 ; i <= n ; i+ )fprintf( fp , " %ld ", hti.weight );printf(" 保存文件成功 !");fclose (fp) ;void main()/主函數(shù)int num ,n,i;char flag ='y'while( flag = 'y' | flag = '

16、Y' ) system( "cls" );printf(" *n"); printf(" * 歡迎使用 哈夫曼編碼系統(tǒng) *n "); printf(" *n"); printf(" * 1. 生成哈夫曼樹 *n");printf(" * 2. 哈夫曼編碼 *n"); printf(" * 3. 顯示哈夫曼樹 *n");printf(" * 4.哈夫曼權值存儲 *n");printf(" * 5. 退出 *n"

17、);printf(" *n");printf(" 請選擇操作類型 ( 1 - 5 ) : " ); scanf( " %d" , &num );printf("*n");switch(num)case 1 : printf(" 請輸入要輸入的字符數(shù)量n為: ");if(scanf(" %ld", &n )&&(n!=0)printf("n 請輸入 %d 個字符和 %d 個對應權值 <先將所有字符輸入 再輸對應權值> n:

18、" , n , n );CodeInput( n , ht );CreateHT( ht , n ); printf(" 對應的權值為 ： n"); for( i = 0 ; i < n ; i+ ) printf( " %d : %ld " , i , hti.weight );if(i+1) % 4 = 0)printf("n");printf("n*- n");break;case 2 : CreateHCode( ht , hcd , n ); CodeOutput( n , hcd ); printf("*");break;case 3 : printf("n");shuc