長春大學(xué)課程設(shè)計(jì)(哈夫曼)

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

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

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

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

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

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

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

8、過不斷的改正錯(cuò)誤，我的程序有了更高的質(zhì)量。在編寫的時(shí)候也犯了很多不該犯的錯(cuò)誤，不過我及時(shí)糾正了，遺憾的是，我的程序功能不是很全，某些部分沒有按照要求去做，說明我的編程能力有待提高。程序清單#include <stdio.h>#include <string.h>#include <stdlib.h>typedef struct/結(jié)構(gòu)體 char data; int weight; /權(quán)值 int parent; /雙親結(jié)點(diǎn) 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 )/進(jì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)/輸入字符及權(quán)值 進(jìn)行哈夫曼編碼 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權(quán)值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); /打印代碼相應(yīng)的權(quán)值，雙親左右孩子 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.哈夫曼權(quán)值存儲 *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 個(gè)字符和 %d 個(gè)對應(yīng)權(quán)值 <先將所有字符輸入 再輸對應(yīng)權(quán)值> n:

18、" , n , n );CodeInput( n , ht );CreateHT( ht , n ); printf(" 對應(yīng)的權(quán)值為 ： 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