數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告_模板

1、 黃淮學(xué)院信息工程學(xué)院課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目：哈夫曼編碼/譯碼系統(tǒng)姓 名：學(xué) 號：專業(yè)班級：計(jì)算機(jī)科學(xué)與技術(shù)0601（本）系 （院）： 信息工程學(xué)院設(shè)計(jì)時(shí)間：20122013學(xué)年第一學(xué)期設(shè)計(jì)地點(diǎn)： 1#615機(jī)房 成績：指導(dǎo)教師簽名： 年 月 日- 16 - / 17² 課程設(shè)計(jì)目的1、能夠更靈活地應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識，獨(dú)立完成問題分析，結(jié)合數(shù)據(jù)結(jié)構(gòu)理論知識，編寫程序求解指定問題。 2.初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能；3.提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能力；4.用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)進(jìn)行軟件開發(fā)，鞏固、深化學(xué)生的理論

2、知識，提高編程水平，并在此過程中培養(yǎng)他們嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度和良好的工作作風(fēng)。5.由于現(xiàn)在市場上的加密很為重要,故應(yīng)當(dāng)做一個相關(guān)的程序,用來解決日常文章的加密與解密工作² 課程設(shè)計(jì)任務(wù)與要求：問題描述打開一篇英文文章，統(tǒng)計(jì)該文章中每個字符出現(xiàn)的次數(shù)，然后以它們作為權(quán)值，對每一個字符進(jìn)行編碼，編碼完成后再對其編碼進(jìn)行譯碼。利用哈夫曼編碼進(jìn)行信息通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫

3、一個哈夫曼編/譯碼系統(tǒng)。基本要求一個完整的系統(tǒng)應(yīng)具有以下功能：（1）I：初始化（Initialization）。從終端讀入字符集大小n，以與n個字符和n個權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。（2）E：編碼（Encoding）。利用已建好的哈夫曼樹（如不在存，則從文件htmTree中讀入），對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。（3）D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。（4）P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行5

4、0個代碼。同時(shí)將此字符形式的編碼寫入文件CodePrint中。（5）T：印哈夫曼樹（Tree Printing）。將已在存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件TreePrint中。測試數(shù)據(jù)新建一個.txt文件，用來存放待處理的數(shù)據(jù)，這些數(shù)據(jù)為ASCII碼值的集合，而且每種字符的數(shù)量并不能一樣。本實(shí)驗(yàn)擬設(shè)其中的數(shù)據(jù)為abbcccdddd.實(shí)現(xiàn)提示（1）文件CodeFile的基類型可以設(shè)為子界型bit = 0.1。（2）用戶界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號，再加上“Q”，表示運(yùn)行Quit。請用戶鍵入一個先把功能符，些功能執(zhí)行完畢后再

5、經(jīng)菜單，直至某次用戶先把了“E”為止。（3）在程序的一次執(zhí)行過程中，第一次執(zhí)行I、D或C命令之后，哈夫曼樹已經(jīng)在存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因?yàn)槲募fmTree可能早已建好。一 需求分析這是一個典型的哈夫曼樹問題，也是它的一個很有實(shí)際應(yīng)用的問題。在這里關(guān)鍵的問題便是要用清楚這些字符的種類以與它的相應(yīng)的權(quán)值，還應(yīng)該知道哈夫曼樹的建立，以與文件的打開與創(chuàng)建和讀寫。二 概要設(shè)計(jì)首先由于程序中要常用到字符的種類數(shù)以與他們的權(quán)值，故需用到兩個全局變量int charcount,int *w,int *wt對于輸入的字符還應(yīng)當(dāng)有一個用來存放的緩沖區(qū),因?yàn)檫@里的字符限定為ASCII碼，故

6、char buff256，用來存入Huffman譯碼的HuffmanDecode HDC 設(shè)計(jì)實(shí)現(xiàn)主要功能的函數(shù)有：獲得字符種類以與權(quán)值的子函數(shù)BOOL GetWeight();初始化哈夫曼樹的子函數(shù)BOOL InitHuffmamTree(HuffmanTree HT);創(chuàng)建哈夫曼樹的子函數(shù)BOOL CreatHuffmanTree(HuffmanTree HT);哈夫曼樹保存的子函數(shù)BOOL HuffmanTreeWriteIntoFile(HuffmanTree HT);哈夫曼樹讀取的子函數(shù)BOOL HuffmanTreeReadIntoMem(HuffmanTree HT);利用哈夫曼

7、樹將字符編碼的函數(shù)BOOL HuffmanTreeCoding(HuffmanTree HT,HuffmanCode HC); 利用哈夫曼樹將字符串譯碼的函數(shù)HuffmanTreeDecoding(HuffmanTree HT,HuffmanCode HC);將哈夫曼樹編碼打印的函數(shù)BOOL HCPrint(HuffmanTree HT,HuffmanCode HC); 將哈夫曼樹打印的函數(shù)BOOL HTPrint(HuffmanTree HT);將哈夫曼樹銷毀的函數(shù)BOOL DestroyHuffmanTree(HuffmanTree HT,HuffmanCode HC);main()函數(shù)中

8、使用一個switch()語句實(shí)現(xiàn)菜單作用，用來對各個子函數(shù)的調(diào)用。程序運(yùn)行中，為了保持屏幕的清楚和美觀，時(shí)刻進(jìn)行清屏也是必要的。抽象數(shù)據(jù)類型線性表的定義如下：ADT HuffmanTree 數(shù)據(jù)對象：D=ai| ai ElemSet,i=1,2,3，n,n0數(shù)據(jù)關(guān)系：基本操作：BOOL GetWeight()操作結(jié)果：獲得字符種類以與權(quán)值的。 BOOL InitHuffmamTree(HuffmanTree HT)初始條件：字符的種類數(shù)已知操作結(jié)果：初始化哈夫曼樹BOOL CreatHuffmanTree(HuffmanTree HT)初始條件：哈夫曼樹已存在，以與相應(yīng)的權(quán)值。操作結(jié)果：創(chuàng)建哈

9、夫曼樹BOOL HuffmanTreeWriteIntoFile(HuffmanTree HT)初始條件：哈夫曼樹已存在。操作結(jié)果：哈夫曼樹保存。HuffmanTreeReadIntoMem(HuffmanTree HT)初始條件：哈夫曼樹已存在且已知道存儲的文件名操作結(jié)果：哈夫曼樹讀取BOOL HuffmanTreeCoding(HuffmanTree HT,HuffmanCode HC)初始條件：哈夫曼樹已存在操作結(jié)果：利用哈夫曼樹將字符編碼并顯示在屏幕上HuffmanTreeDecoding(HuffmanTree HT,HuffmanCode HC)初始條件：哈夫曼樹已存在且已知道其編

10、碼操作結(jié)果：利用哈夫曼樹將字符譯碼并顯示在屏幕上BOOL HCPrint(HuffmanTree HT,HuffmanCode HC)初始條件：已知道其編碼操作結(jié)果：將字符譯碼顯示在屏幕上并存入文件BOOL HTPrint(HuffmanTree HT)初始條件：哈夫曼樹已存在操作結(jié)果：將哈夫曼樹以直觀方式顯示在屏幕上并存入文件BOOL DestroyHuffmanTree(HuffmanTree HT,HuffmanCode HC)初始條件：程序中所有的堆操作結(jié)果：將程序所占的所有存釋放。三 詳細(xì)設(shè)計(jì)1）定義全局變量、結(jié)構(gòu)體：/*聲明哈夫曼樹結(jié)點(diǎn)類型，與樹類型*/typedef struct

11、 char ver; unsigned int weight; unsigned int lchild,rchild,parent;HTNode ,*HuffmanTree;unsigned int *w=NULL,*wt=NULL;/*聲明全局變量w,wt分別存儲每個字符對應(yīng)的個數(shù)以與其權(quán)值*/int charcount,mode;/*聲明全局變量，分別表示出現(xiàn)字符的種類個數(shù)，以與所采用的數(shù)據(jù)給定方式*/char buff256,file25, *charmap;/*用來緩沖輸入的字符，以與文件名。charmap用來表示每個葉子結(jié)點(diǎn)的下標(biāo)*/typedef char * HuffmanCod

12、e;HuffmanCode HC;2）各主要部分的算法/*主函數(shù)的算法如下：*/void main() HuffmanTree HT=NULL; int i,j,action,tag; char flag,*test; while(1) system("cls"); printf("%20s",""); for(i=0;i<40;i+) putchar('*'); putchar('n'); putchar('n'); printf("%26s","&

13、quot;); printf("歡迎使用哈夫曼樹編碼譯碼系統(tǒng)!"); putchar('n'); putchar('n'); printf("%21s",""); printf("Vertion 2008.6.22 Author :CaiQinghe"); putchar('n'); putchar('n'); printf("%20s",""); for(i=0;i<40;i+) putchar('

14、;*'); putchar('n'); printf("%20s",""); printf("1.本程序可以用來進(jìn)行加密與解密工作.nn其使用圍為ASCII碼中除'n'之外的所有字符.n"); printf("n%20s",""); printf("2.本程序?yàn)樽髡吡ψ?請您在使用時(shí)勿必尊重作者的權(quán)利.nn"); printf("n%20s",""); printf("3.本程序中的每種

15、數(shù)據(jù)的權(quán)值都應(yīng)保證是完全不同的。nn"); printf("下面請您任輸入一個字符進(jìn)入程序:nn"); getch(); system("cls"); printf("哈夫曼編譯碼請選1:nnn"); printf("哈夫曼樹打印顯示2:nnn"); scanf("%d",&tag); switch(tag) case 1: printf("首先將建立一個哈夫曼樹nn"); WeightGet(); HT=InitHuffmanTree();CreatHuf

16、fmanTree(HT);printf("你想將該哈夫曼樹存入文件嗎?'y'/'n'n");getchar();scanf("%c",&flag);if(flag='y'|flag='Y')HuffmanTreeWriteIntoFile(HT);printf("你想將此樹打印在屏幕上嗎?'y'/'n'n");getchar();scanf("%c",&flag);printf("%c"

17、;,flag);if(flag='y'|flag='Y')printf("該樹用凹凸表可表示為:n");HTPrint(SearchRoot(HT),1,HT);HuffmanTreeCoding(HT);printf("請打印編碼并存入文件嗎?n'y'/'n'n");getchar();scanf("%c",&flag);if(flag='y'|flag='Y') HCPrint(HT,HC);printf("請選擇編碼

18、還是譯碼nn1.編碼nn2.譯碼nn"); scanf("%d",&tag); while(tag<1|tag>2) printf("n你輸入的數(shù)據(jù)非法，請鍵入一個1-2中的一個數(shù)字n"); scanf("%d",&tag); if(tag=1) HuffmanTreeCoding(HT); else HuffmanTreeDecoding(HT); break; case 2: HT=NULL;HT=HuffmanTreeReadIntoMem(HT);printf("該樹用凹凸表可表

19、示為:n");HTPrint(SearchRoot(HT),1,HT); printf("請問你要退出這個程序嗎?n'y'/'n'n");getchar();scanf("%c",&flag);if(flag='y'|flag='Y')goto out; getch();out:;/*尋找哈夫曼樹的根結(jié)點(diǎn)下標(biāo)的算法*/*構(gòu)建哈夫曼樹時(shí)求解最小的兩個結(jié)點(diǎn)的算法*/*統(tǒng)計(jì)每個字符的權(quán)值的算法*/*初始化哈夫曼樹的算法*/*創(chuàng)建哈夫曼樹的算法*/*將哈夫曼樹寫入文件的算法*/*將

20、哈夫曼樹讀入存中的算法*/*哈夫曼樹編碼的算法*/*哈夫曼樹譯碼的算法*/*用來打印生成的哈夫曼編碼的算法*/*該函數(shù)可用來打印一棵樹的凹凸形式的算法*/各部分之間的相互調(diào)用關(guān)系圖示如下：主函數(shù)哈夫曼編譯碼哈夫曼打印獲取權(quán)值初始建立哈夫曼選擇是否顯示該樹選擇是否打印生成的編碼并存入文件將已存在的哈夫曼樹調(diào)入內(nèi)存在屏幕上顯示該樹選擇是否退出程序選擇是編碼還是譯碼四 設(shè)計(jì)與調(diào)試分析從上面的算法和調(diào)用關(guān)系可以看出，這個程序的基本樣子已經(jīng)非常的清楚，但是真正的程序中還要考慮各種限制條件。例如在在從文件中讀取信息的時(shí)候，可能文件是不存在的，就要給出不存在此文件的提示等。當(dāng)輸入的數(shù)據(jù)非法時(shí)，也應(yīng)當(dāng)給出相應(yīng)的提示。還有就是涉與到返回值得問題和程序中所要用到的變量的問題。在調(diào)試的過程中所遇到的問題很多。例如數(shù)值的類型不匹配。以與文件的讀取和格式的對齊，都不是很容易，往往容易出錯。五 用戶手冊1 本程序可以在vc+6.0 的環(huán)境下運(yùn)行。2 在vc中創(chuàng)建一個C+文件，將源程序復(fù)制到.cpp中，編譯就可以。3 選擇編譯、運(yùn)行以后會出現(xiàn)運(yùn)行界面，選擇相應(yīng)的選項(xiàng)，根據(jù)提示即可進(jìn)行演示。界面如下：注：任意輸入一個數(shù)據(jù)后進(jìn)入系統(tǒng)，然后根據(jù)系統(tǒng)提示操作即