數(shù)據(jù)結(jié)構(gòu)課程設計報告課題:專業(yè)班級：學號：姓名：指導教師:1課程設計的目的和意義在當今信息爆炸時代，如何采用有效的數(shù)據(jù)壓縮技術(shù)來節(jié)省數(shù)據(jù)文件的存儲空間和計算機網(wǎng)絡的傳送時間已越來越引起人們的重視。哈夫曼編碼正是一種應用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。哈夫曼編碼的應用很廣泛，利用哈夫曼樹求得的用于通信的二進制編碼稱為哈夫曼編碼。樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0〞碼，指向右子樹的分支表示“1〞碼，取每條路徑上的“0〞或“1〞的序列作為和各個對應的字符的編碼，這就是哈夫曼編碼。通常我們把數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報通信是傳遞文字的二進制碼形式的字符串。但在信息傳遞時，總希望總長度盡可能最短，即采用最短碼。2．需求分析課題：哈夫曼編碼譯碼器系統(tǒng)問題描述：翻開一篇英文文章，統(tǒng)計該文章中每個字符出現(xiàn)的次數(shù)，然后以它們作為權(quán)值，對每一個字符進行編碼，編碼完成后再對其編碼進行譯碼。問題補充：1.從硬盤的一個文件里讀出一段英語文章；2.統(tǒng)計這篇文章中的每個字符出現(xiàn)的次數(shù)；3.以字符出現(xiàn)字數(shù)作為權(quán)值，構(gòu)建哈夫曼樹4.對每個字符進行編碼并將所編碼寫入文件然后對所編碼進行破譯。具體介紹：在本課題中，我們在硬盤D盤中預先建立一個file.txt文檔，在里面編輯一篇文章(大寫)。然后運行程序，調(diào)用fileopen()函數(shù)讀出該文章，顯示在界面；再調(diào)用tongji()函數(shù)對該文章的字符種類進行統(tǒng)計，并對每個字符的出現(xiàn)次數(shù)進行統(tǒng)計，并且在界面上顯示；然后以每個字符出現(xiàn)次數(shù)作為權(quán)值，調(diào)用Create_huffmanTree()函數(shù)構(gòu)建哈夫曼樹。然后調(diào)用Huffman_bianma()函數(shù)對哈夫曼樹進行編碼，調(diào)用coding()函數(shù)將編碼寫入文件。測試數(shù)據(jù)：例如從文本中讀到文章為：IAMASTUDENT。那么效果如下：讀出文本為：IAMASTUDENT字符A次數(shù):2字符D次數(shù):1字符E次數(shù):1字符I次數(shù):1字符M次數(shù):1字符N次數(shù):1字符S次數(shù):1字符T次數(shù):2字符U次數(shù):1輸出編碼：00010100110101111010011101111010110Pressanykeytocontinue3系統(tǒng)〔工程〕設計(1)設計思路及方案本課題是用最優(yōu)二叉樹即哈夫曼樹來實現(xiàn)哈夫曼編碼譯碼器的功能。假設每種字符在電文中出現(xiàn)的次數(shù)為Wi，編碼長度為Li，電文中有n種字符，那么電文編碼總長度為(W1*L1)+(W2*L2)+…+(Wi*Li)。假設將此對應到二叉樹上，Wi為葉結(jié)點，Li為根結(jié)點到葉結(jié)點的路徑長度。那么，(W1*L1)+(W2*L2)+…+(Wi*Li)恰好為二叉樹上帶權(quán)路徑長度。因此，設計電文總長最短的二進制前綴編碼，就是以n種字符出現(xiàn)的頻率作權(quán)，構(gòu)造一棵哈夫曼樹，此構(gòu)造過程稱為哈夫曼編碼。該系統(tǒng)將實現(xiàn)以下幾大功能：從硬盤讀取字符串，建立哈夫曼樹，輸出哈夫曼樹的存儲結(jié)構(gòu)的初態(tài)和終態(tài)，輸出各種字符出現(xiàn)的次數(shù)以及哈夫曼編碼的譯碼等。(2)模塊的設計及介紹1從硬盤讀取字符串fileopen(參數(shù)){實現(xiàn)命令；打印輸出；}2建立HuffmanTree通過三個函數(shù)來實現(xiàn)：voidselect_min(參數(shù)){初始化；for{接受命令；處理命令；}}說明：在ht[1....k]中選擇parent為0且權(quán)值最小的兩個根結(jié)點的算法inttongji(參數(shù)){初始化；for{接受命令；處理命令；}}說明：統(tǒng)計字符串中各種字母的個數(shù)以及字符的種類voidCreate_huffmanTree(){初始化；for{接受命令；處理命令；}輸出字符統(tǒng)計情況；}說明：構(gòu)造哈夫曼樹3哈夫曼編碼voidHuffman_bianma(參數(shù)){定義變量；{處理命令；}}說明：哈夫曼編碼(3)主要模塊程序流程圖下面介紹三個主要的程序模塊流程圖：①主函數(shù)流程圖：結(jié)束結(jié)束統(tǒng)計字符種類及頻率字符總數(shù)num建立哈夫曼樹哈夫曼編碼翻開文件？開始否是圖3.1流程圖注釋：該圖比擬簡單，主要是調(diào)用各個函數(shù)模塊，首先代開已經(jīng)存在的文件，然后統(tǒng)計總的字符數(shù)以及出現(xiàn)的各個字符和頻率。然后才開始建立哈夫曼樹，接著在哈夫曼樹的根底上對其進行編碼。最后輸出結(jié)束。②構(gòu)造哈夫曼樹：開始開始結(jié)束第i個結(jié)點權(quán)值i=num?創(chuàng)立哈夫曼樹輸出字符統(tǒng)計情況第i個根結(jié)點i=2*num-1?i=num?否是否是否是圖3.2流程圖注釋：該圖是表示構(gòu)造哈夫曼樹的過程。首先輸入num個葉結(jié)點的權(quán)值，當i=num是循環(huán)結(jié)束。然后進行哈夫曼樹的構(gòu)建，當i=2*num-1是循環(huán)結(jié)束。最后輸出所得到的字符統(tǒng)計情況。③哈夫曼編碼：結(jié)束結(jié)束開始T[p].left=c?i<=num?Cd[--start]=0,start=numCd[--start]=0Cd[--start]=1否否是是圖3.3流程圖解釋：該流程圖表四哈夫曼編碼情況。首先初始化，Cd[--start]=0,start=num。然后進行編碼，當cd[--start]=T[p].lchild==c時，cd[--start]=0；當cd[--start]=T[p].left！==c時，cd[--start]=1。這個編碼循環(huán)一直到i=num時結(jié)束。4系統(tǒng)實現(xiàn)各模塊關(guān)鍵代碼及算法的解釋：主調(diào)函數(shù)代碼解釋：這是main函數(shù)里的各個函數(shù)調(diào)用情況。fileopen(string);//從硬盤中讀取文件 num=tongji(string,cishu,str);//統(tǒng)計字符種類及各類字符出現(xiàn)的頻率 Create_huffmanTree(HT,HC,cishu,str);//建立哈夫曼樹 Huffman_bianma(HT,HC);//生成哈夫曼編碼建立HuffmanTree代碼解釋：該函數(shù)為在ht[1....k]中選擇parent為0且權(quán)值最小的兩個根結(jié)點的算法，其序號為s1和s2。voidselect_min(HuffmanTreeT,intk,int&x1,int&x2){ inti,j; intmin1=1000;for(i=1;i<=k;i++) if(T[i].weight<min1&&T[i].parent==0) { j=i; min1=T[i].weight; } x1=j;min1=1000; for(i=1;i<=k;i++) if(T[i].weight<min1&&T[i].parent==0&&i!=x1) { j=i; min1=T[i].weight; } x2=j;}代碼解釋：下面函數(shù)用來統(tǒng)計字符串中各種字母的個數(shù)以及字符的種類。當字符在A和Z之間時即被計數(shù)，并用str[j]保存字母到數(shù)組中，用cnt[j]統(tǒng)計每種字符個數(shù)。j返回總共讀取的字符數(shù)目。inttongji(char*s,intcishu[],charstr[]){ inti,j,k; char*p; intt[27]; for(i=1;i<=26;i++) t[i]=0; for(p=s;*p!='\0';p++) { if(*p>='A'&&*p<='Z') k=*p-64; t[k]++; } for(i=1,j=0;i<=26;++i) if(t[i]!=0) { j++; str[j]=i+64; cishu[j]=t[i]; returnj;}代碼解釋：下面函數(shù)用來構(gòu)造哈夫曼樹HT。首先初始化哈夫曼樹，然后輸入前面統(tǒng)計的各結(jié)點的權(quán)值，用for循環(huán)來構(gòu)造哈夫曼樹。voidCreate_huffmanTree(HuffmanTreeht,HuffmanCodehc,intcishu[],charstr[]){//生成哈夫曼樹HT inti,s1,s2; for(i=0;i<2*num-1;i++) { ht[i].left=0; ht[i].right=0; ht[i].parent=0; ht[i].weight=0; } for(i=1;i<=num;i++)//輸入num個葉結(jié)點的權(quán)值 ht[i].weight=cishu[i]; for(i=num+1;i<=2*num-1;i++) {//選擇parent為0且權(quán)值最小的兩個根結(jié)點，其序號為s1和s2,i為雙親 select_min(ht,i-1,s1,s2); ht[s1].parent=i;ht[s2].parent=i; ht[i].left=s1;ht[i].right=s2; ht[i].weight=ht[s1].weight+ht[s2].weight; } for(i=0;i<=num;i++) hc[i].ch=str[i];//字符的種類 i=1;while(i<=num) printf("字符%c次數(shù):%8d\n",hc[i].ch,cishu[i++]); }生成Huffman編碼并寫入文件代碼解釋：根據(jù)哈夫曼樹T求哈夫曼編碼H。voidHuffman_bianma(HuffmanTreeT,HuffmanCodeH)//根據(jù)哈夫曼樹T求哈夫曼編碼H{ intchild,parent,i;//child和parent分別指示t中孩子和雙親 charcode[n];//存放編碼 intstart;//指示碼在code中的起始位置 code[num]='\0';//最后一位〔第num個〕放上串結(jié)束符 for(i=1;i<=num;++i) { start=num;//初始位置 child=i;//從葉子結(jié)點到根結(jié)點進行遍歷 while((parent=T[child].parent)>0)//直至t[child]是樹根為止 {//假設t[child]是t[parent]的左孩子,那么生成0;否那么生成1 if(T[parent].left==child) code[--start]='0'; else code[--start]='1'; child=parent; } strcpy(H[i].co,&code[start]); H[i].len=num-start; }}代碼解釋：對str所代表的字符串進行編碼并寫入文件。將翻譯的二進制碼寫入文本文件。voidcoding(HuffmanCodehc,char*str){//對str所代表的字符串進行編碼并寫入文件 inti,j; FILE*fp; fp=fopen("codefile.txt","w"); while(*str) { for(i=1;i<=num;i++) if(hc[i].ch==*str){ for(j=0;j<=hc[i].len;j++) fputc(hc[i].co[j],fp); break; } str++; }fclose(fp);}5系統(tǒng)調(diào)試本次測試是在我的電腦的D盤中建立一個名為file.txt的文本文檔，其中有大寫字母IAMASTUDENT，期望程序能將其讀出至界面并實現(xiàn)其他相關(guān)的功能。運行程序后，我們可以見到一下的運行界面。從硬盤中讀出已有的文本文件輸出所讀字符的種類和每種字符的個數(shù)輸出編碼小結(jié)通過一周的課程設計使我對哈夫曼樹以及哈夫曼編碼有了更深的認識和理解，也使我更加明白哈夫曼編碼譯碼在信息技術(shù)中的重要性和地位。首先我談談我在設計期間我遇到的難點。開始的時候，代碼中有許多的錯誤，特別是有一個“無法找到文件〞的錯誤讓我束手無策，最后還是屏蔽了定義的四個頭文件然后慢慢地改正錯誤才讓我又看到了希望。然后在實現(xiàn)文章的讀入時，由于對文件不是太熟悉，只好翻開C語言書本仿照其模式編寫，但后來進入了死循環(huán)，最后的解決方式是把main函數(shù)里的一個do…while循環(huán)去掉。許多的錯誤讓我明白了一個道理---細心是非常重要的。同時，對于編程者而言，思路清晰是相當重要的。在適當?shù)臅r候和同學一起交流探討是一個十分好的學習時機。這次課程設計不但讓我學得了一些編程知識，還學會了系統(tǒng)的做一份課程設計報告，學會了如何截圖，學會了如何更好的畫流程圖，明白了做事情只有認真，才能真正做得更好！通過這次課程設計，我看清楚了自己的編程功底和動手能力還很缺乏，這主要是平時實踐太少的緣故。我想，在未來的暑假中，我會努力嘗試編寫一些程序。在這個程序中，還有許多地方值得完善。比方，讀出文本只能是大寫的文檔，空格和小寫不能識別。由于時間問題，暫時不能實現(xiàn)了，我想在暑假里好好研究這個問題。未完成：哈夫曼譯碼附錄源程序#include<stdio.h>#include<string.h>#include<stdlib.h>#include<fstream.h>//類型相關(guān)變量的定義#definen100#definem2*n-1typedefstruct{ charch; charco[9];//存放編碼 intlen;}CodeNode;typedefCodeNodeHuffmanCode[n+1];typedefstruct{ intweight; intleft,right,parent;}HTNode;typedefHTNodeHuffmanTree[m+1];intnum;voidselect_min(HuffmanTreeT,intk,int&x1,int&x2){//選擇權(quán)值最小的兩個根結(jié)點,其序號為x1和x2 inti,j; intmin1=1000;for(i=1;i<=k;i++)//找最小值 if(T[i].weight<min1&&T[i].parent==0) { j=i; min1=T[i].weight; } x1=j;min1=1000; for(i=1;i<=k;i++)//找次小值 if(T[i].weight<min1&&T[i].parent==0&&i!=x1) { j=i; min1=T[i].weight; } x2=j;}inttongji(char*s,intcishu[],charstr[]){//統(tǒng)計字符串中各種字母的個數(shù)以及字符的種類 inti,j,k; char*p; intt[27]; for(i=1;i<=26;i++) t[i]=0; for(p=s;*p!='\0';p++)//統(tǒng)計各種字符的個數(shù) { if(*p>='A'&&*p<='Z') k=*p-64; t[k]++; } for(i=1,j=0;i<=26;++i) if(t[i]!=0) { j++; str[j]=i+64;//送對應的字母到數(shù)組中 cishu[j]=t[i];//存入對應字母的權(quán)值 } returnj;//j是輸入字母種數(shù)}voidCreate_huffmanTree(HuffmanTreeht,HuffmanCodehc,intcishu[],charstr[]){//生成哈夫曼樹HT inti,s1,s2; for(i=0;i<2*num-1;i++) { ht[i].left=0; ht[i].right=0; ht[i].parent=0; ht[i].weight=0; } for(i=1;i<=num;i++)//輸入num個葉結(jié)點的權(quán)值 ht[i].weight=cishu[i]; for(i=num+1;i<=2*num-1;i++) {//選擇parent為0且權(quán)值最小的兩個根結(jié)點，其序號為s1和s2,i為雙親 select_min(ht,i-1,s1,s2); ht[s1].parent=i;ht[s2].parent=i; ht[i].left=s1;ht[i].right=s2; ht[i].weight=ht[s1].weight+ht[s2].weight; } for(i=0;i<=num;i++) hc[i].ch=str[i];//字符的種類 i=1;while(i<=num) printf("字符%c次數(shù):%8d\n",hc[i].ch,cishu[i++]); }voidHuffman_bianma(HuffmanTreeT,HuffmanCodeH)//根據(jù)哈夫曼樹T求哈夫曼編碼H{ intchild,parent,i;//child和parent分別指示t中孩子和雙親 charcode[n];//存放編碼 intstart;//指示碼在code中的起始位置 code[num]='\0';//最后一位〔第num個〕放上串結(jié)束符 for(i=1;i<=num;++i) { start=num;//初始位置 child=i;//從葉子結(jié)點到根結(jié)點進行遍歷 while((parent=T[child].parent)>0)//直至t[child]是樹根為止 {//假設t[child]是t[parent]的左孩子,那么生成0;否那么生成1 if(T[parent].left==child) code[--start]='0'; else code[--start]='1'; child=parent; } strcpy(H[i].co,&code[start]); H[i].len=num-start; }}voidcoding(HuffmanCodehc,char*str){//對str所代表的字符串進行編碼并寫入文件 inti,j; FILE*fp; fp=fopen("codefile.txt","w"); while(*str) { for(i=1;i<=num;i++) if(hc[i].ch==*str){ for(j=0;j<=hc[i].len;j++) fputc(hc[i].co[j],fp); break; } str++; }fclose(fp);}voidoutput()//輸出編碼{ FILE*fp; charch; if((fp=fopen("codefile.txt","r+"))==NULL) { printf("error\n"); exit(0); } printf("編碼為:\n"); ch=fgetc(fp); while(!feof(fp)) { putchar(ch); ch=fgetc(fp); }printf("\n");}intfileopen(charstring[])//讀入文件{ FILE*fp;if((fp=fopen("D:\\數(shù)據(jù)結(jié)構(gòu)課程設計\\file.txt","r"))==NU