課程設(shè)計說明書

課程設(shè)計說明書課程名稱：數(shù)據(jù)結(jié)構(gòu)設(shè)計題目：哈夫曼編/譯碼器學院：計算機科學與信息工程學院學生姓名：申恒恒學生學號業(yè)班級：網(wǎng)絡(luò)工程13-01指導教師：馮賀2015年6月25日課程設(shè)計任務(wù)書設(shè)計題目哈夫曼編/譯碼器學生姓名申恒恒所在院部計算機科學與信息工程學院專業(yè)、班級網(wǎng)絡(luò)工程13-1設(shè)計要求：1、根據(jù)哈夫曼樹編碼原理，構(gòu)造哈夫曼樹，創(chuàng)建一套哈夫曼編碼；2、讀取文本文件，并對文件內(nèi)容編碼，生成編碼文件；3、對編碼文件進行譯碼，獲得恢復文件；4、比較恢復文件和原文件是否相同。學生應完成的工作：1.學生應認真學習參考程序，理解每個文件、每個函數(shù)以及各個變量的作用和意義。在此基礎(chǔ)上進一步改進程序，最后正確地運行程序。2.對程序進行測試，設(shè)計詳細的測試計劃，然后根據(jù)測試計劃設(shè)計測試用例，對程序進行測試。測試時應注意對各種邊緣情況進行測試。3.完成課程設(shè)計報告。參考文獻：1.嚴蔚敏數(shù)據(jù)結(jié)構(gòu)（C語言版）清華大學出版社20112.譚浩強C程序設(shè)計（第四版）清華大學出版社2010工作計劃：1.小組審題，查閱資料，進行設(shè)計前的必要資料準備（3天）。2.把程序完整運行出來（4天）。3.增加改進程序（3天）。4.寫課程設(shè)計報告（3天）。5.提交課程設(shè)計報告及答辯（1天）任務(wù)下達日期：2015年6月9日任務(wù)完成日期：2015年6月22日指導教師（簽名）：學生（簽名）：申恒恒

哈夫曼編/譯碼器摘要：采用哈夫曼編碼思想實現(xiàn)對字符串的編碼，以及對編碼的解碼。字符串的長度不小于5000字節(jié)。讀取要編碼的文本文件，將文件的內(nèi)容進行編碼，生成新的文件。對編碼文件進行解碼，獲得文本文件。將譯碼的文本文件和原文件進行比較，恢復文件和原文件必須完全一致。關(guān)鍵詞：哈夫曼編碼哈夫曼譯碼解碼目錄TOC\o"1-4"\h\z\u哈夫曼編/譯碼器 21.設(shè)計背景 41.1程序的功能 41.2輸入輸出的要求 42.設(shè)計方案 52.1程序結(jié)構(gòu) 52.2數(shù)據(jù)結(jié)構(gòu) 53.方案實施 63.1詳細設(shè)計 63.2調(diào)試分析 63.2.1發(fā)現(xiàn)問題 63.2.2逐步解決問題 63.2.3代碼實現(xiàn)過程 73.3核心源程序清單 124.結(jié)果與結(jié)論 144.1程序運行結(jié)果圖 144.2結(jié)論與心得體會 155.參考文獻 161.設(shè)計背景1.1程序的功能(1)從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹并將它存于文件hfmTree中.將已在內(nèi)存中的哈夫曼樹以直觀的方式（比如樹）顯示在終端上；(2)利用已經(jīng)建好的哈夫曼樹（如不在內(nèi)存，則從文件htmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入文件CodeFile中，并輸出結(jié)果，將文件CodeFile以緊湊格式先是在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrint中；(3)利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結(jié)果存入文件TextFile中，并輸出結(jié)果。1.2輸入輸出的要求先在執(zhí)行文件的同根目錄下創(chuàng)建abc.txt文件，在abc文件中輸入各字母及相應的權(quán)值。測試數(shù)據(jù)：字符空格ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ

頻度5763151485180238181161

2.設(shè)計方案2.1程序結(jié)構(gòu)2.2數(shù)據(jù)結(jié)構(gòu)typedefstruct{intweight;//權(quán)重intparent,lchild,rchild;//父親節(jié)點，左孩子，右孩子}HTNode,*HuffmanTree;//定義節(jié)點和哈夫曼樹結(jié)構(gòu)體3.方案實施3.1詳細設(shè)計初始化哈夫曼鏈表:voidInitialization();輸入帶編碼的字符并寫入文件：voidInputCode();編碼:Encoding();譯碼:Decoding();打印編碼:Code_printing(); 3.2調(diào)試分析3.2.1發(fā)現(xiàn)問題如何根據(jù)輸入的字符和使用頻率構(gòu)建哈夫曼樹并得到它的哈夫曼編碼？3.2.2逐步解決問題哈夫曼樹是什么？給定n個權(quán)值作為n個葉子結(jié)點，構(gòu)造一棵二叉樹，若帶權(quán)路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffmantree)。如何構(gòu)建哈夫曼樹？假設(shè)有n個權(quán)值，則構(gòu)造出的哈夫曼樹有n個葉子結(jié)點。n個權(quán)值分別設(shè)為w1、w2、…、wn，則哈夫曼樹的構(gòu)造規(guī)則為：(1)將w1、w2、…，wn看成是有n棵樹的森林(每棵樹僅有一個結(jié)點)；(2)在森林中選出兩個根結(jié)點的權(quán)值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點權(quán)值為其左、右子樹根結(jié)點權(quán)值之和；(3)從森林中刪除選取的兩棵樹，并將新樹加入森林；(4)重復(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。哈夫曼編碼是什么？哈夫曼編碼(HuffmanCoding)是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。Huffman于1952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來構(gòu)造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫作Huffman編碼。如何得到哈夫曼編碼？

通過從哈夫曼樹根結(jié)點開始，對左子樹分配代碼“0”，右子樹分配代碼“1”，一直到達葉子結(jié)點為止，然后將從樹根沿每條路徑到達葉子結(jié)點的代碼排列起來，便得到了哈夫曼編碼。3.2.3代碼實現(xiàn)過程//哈夫曼編碼//w存放n個字符的權(quán)值(均>0),構(gòu)造哈夫曼樹HT,并求出n個字符的哈夫曼編碼HCvoidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){intm,i,s1,s2,start;intc,f;HuffmanTreep;char*cd;if(n<=1)return;//檢測結(jié)點數(shù)是否可以構(gòu)成樹m=2*n-1;//需要構(gòu)造多少個頂點HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0號單元未用for(p=HT+1,i=1;i<=n;++i,++p,++w)//初始化樹節(jié)點{p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;}for(;i<=m;++i,++p)//初始化其它節(jié)點p->parent=0;for(i=n+1;i<=m;++i)//建哈夫曼樹{select(HT,i-1,s1,s2);//在HT[1~i-1]中選擇parent為0且weight最小的兩個結(jié)點,其序號分別為s1和s2HT[s1].parent=HT[s2].parent=i;//建立父親節(jié)點HT[i].lchild=s1;//初始化左右孩子節(jié)點HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;//把孩子節(jié)點的權(quán)值累加到父親節(jié)點} HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//從葉子到根逆向求每個字符的哈夫曼編碼 cd=(char*)malloc(n*sizeof(char));//分配n個字符編碼的頭指針向量([0]不用)cd[n-1]='\0';//編碼結(jié)束符for(i=1;i<=n;i++)//逐個字符求哈夫曼編碼{start=n-1;//編碼結(jié)束符位置for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//從葉子到根逆向求編碼if(HT[f].lchild==c)cd[--start]='0';//左子樹為'0'elsecd[--start]='1';//右子樹為'1'HC[i]=(char*)malloc((n-start)*sizeof(char));//為第i個字符編碼分配空間strcpy(HC[i],&cd[start]);//從cd復制編碼(串)到HC}free(cd);//釋放工作空間}編碼：上面已經(jīng)得到了相應的字符的編碼。直接輸出即可。如何進行哈夫曼編碼的譯碼？

知道了編碼用的哈夫曼樹后。從根結(jié)點出發(fā)，逐個讀入編碼的二進制碼；若代碼為“0”，則走左子樹的根結(jié)點，否則走向右子樹的根結(jié)點；一旦到達葉子結(jié)點，便譯出代碼所對應的字符。然后又重新從根結(jié)點開始繼續(xù)譯碼，直到二進制編碼結(jié)束。編碼和譯碼的代碼如下：//編碼函數(shù)voidEncoding(){printf("下面對目錄下文件tobetran.txt中的字符進行編碼\n");FILE*tobetran,*codefile; if((tobetran=fopen("tobetran.txt","rb"))==NULL)//打開將要編碼的文件{printf("不能打開文件\n");}if((codefile=fopen("codefile.txt","wb"))==NULL)//保存編碼結(jié)果的文件{printf("不能打開文件\n");}char*tran;i=99;tran=(char*)malloc(100*sizeof(char));while(i==99){if(fgets(tran,100,tobetran)==NULL){printf("不能打開文件\n");break;}for(i=0;*(tran+i)!='\0';i++){for(j=0;j<=n;j++){if(*(z+j-1)==*(tran+i))//找到對應字母的編碼，并輸出{fputs(HC[j],codefile); printf("%s",HC[j]);if(j>n){printf("字符錯誤，無法編碼!\n");break;}}}}}printf("\n…………編碼完成…………\n編碼寫入目錄下的codefile.txt中\(zhòng)n\n");fclose(tobetran);fclose(codefile);free(tran);}//譯碼函數(shù)voidDecoding(){ printf("下面對根目錄下文件codefile.txt中的字符進行譯碼\n");FILE*codef,*txtfile;if((txtfile=fopen("Textfile.txt","w"))==NULL)//打開譯碼結(jié)果保存的文件{printf("不能打開文件\n");}if((codef=fopen("codefile.txt","r"))==NULL)//打開將要譯碼的文件{ printf("不能打開文件\n");} char*work,*work2,i2; inti4=0,i,i3;unsignedlonglength=10000;work=(char*)malloc(length*sizeof(char)); fgets(work,length,codef); work2=(char*)malloc(length*sizeof(char)); i3=2*n-1;//n=26i3==huffman樹的全部節(jié)點數(shù) i=0; do { i2=*(work+i);//求編碼后的二進制 if(HT[i3].lchild==0&&HT[i3].rchild==0)//如果到達葉子節(jié)點 { *(work2+i4)=*(z+i3-1); i4++; i3=2*n-1;//重新從根節(jié)點開始查找 i--; } elseif(i2=='0')i3=HT[i3].lchild;//左子樹為'0' elseif(i2=='1')i3=HT[i3].rchild;//右子樹為'1' i++; }while(*(work+i-1)!='\0'); *(work2+i4)='\0'; fputs(work2,txtfile); printf("…………譯碼完成…………\n內(nèi)容寫入根目錄下的文件textfile.txt中\(zhòng)n\n"); free(work); free(work2);fclose(txtfile);fclose(codef);}3.3核心源程序清單voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){intm,i,s1,s2,start;intc,f;HuffmanTreep;char*cd;if(n<=1)return;//檢測結(jié)點數(shù)是否可以構(gòu)成樹m=2*n-1;//需要構(gòu)造多少個頂點HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0號單元未用for(p=HT+1,i=1;i<=n;++i,++p,++w)//初始化樹節(jié)點{p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;}for(;i<=m;++i,++p)//初始化其它節(jié)點p->parent=0;for(i=n+1;i<=m;++i)//建哈夫曼樹{select(HT,i-1,s1,s2);//在HT[1~i-1]中選擇parent為0且weight最小的兩個結(jié)點,其序號分別為s1和s2HT[s1].parent=HT[s2].parent=i;//建立父親節(jié)點HT[i].lchild=s1;//初始化左右孩子節(jié)點HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;//把孩子節(jié)點的權(quán)值累加到父親節(jié)點} HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//從葉子到根逆向求每個字符的哈夫曼編碼 cd=(char*)malloc(n*sizeof(char));//分配n個字符編碼的頭指針向量([0]不用)cd[n-1]='\0';//編碼結(jié)束符for(i=1;i<=n;i++)//逐個字符求哈夫曼編碼{start=n-1;//編碼結(jié)束符位置for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//從葉子到根逆向求編碼