




版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領
文檔簡介
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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年安徽省濉溪縣聯(lián)考英語八下期末監(jiān)測試題含答案
- 天津事業(yè)單位試題及答案
- 團校試題及答案
- 2025年能源管道建設與維護策劃合作協(xié)議
- 2025年策劃業(yè)務合作優(yōu)化協(xié)議書
- 2025年數(shù)據(jù)分析行業(yè)咨詢合作協(xié)議
- 2025年修訂版股東協(xié)議
- 2025年工傷賠償標準協(xié)議書范文
- 大數(shù)據(jù)時代出版業(yè)的精準營銷策略
- 健美操文化傳播的創(chuàng)新路徑與實踐
- 教育數(shù)字化轉(zhuǎn)型背景下中小學課堂教學變革研究
- 八年級英語下學期期末考試(廣州專用)(解析版)
- 浙江省寧波市鎮(zhèn)海中學2025年5月第二次模擬考試 英語試卷+答案
- 項目管理與評估試題及答案
- 2024年安徽省淮南市田家庵區(qū)小升初數(shù)學試卷(空白卷)
- 航海英語閱讀與寫作能力測試考核試卷
- 環(huán)境設計人才培養(yǎng)方案
- 檳榔轉(zhuǎn)讓合同協(xié)議書
- 龍巖市2025年高中高三畢業(yè)班五月教學質(zhì)量檢政治試卷(含答案)
- 自動跟蹤定位射流滅火系統(tǒng)設計與實施及驗收標準化研究
- 巴黎奧運會試題及答案
評論
0/150
提交評論