數據結構課程設計報告哈夫曼編碼譯碼器

..哈弗曼編碼譯碼器專業班級：XXXX學號：XXXX姓名：XXXX指導教師：XXXX課程設計時間：XXXX計算機專業數據結構課程設計任務書學生姓名XXXX專業班級XXXX學號XXXX題目哈弗曼編碼譯碼器課題性質工程設計課題來源XXXX指導教師XXXX同組姓名XXXX主要內容設計一個哈弗曼編碼譯碼器,實現哈夫曼樹的建立,樹形輸出,編碼和解碼。任務要求1．研究哈弗曼樹的數據存儲方式2．實現哈弗曼編碼譯碼器的主要算法3．分析算法的運行效率4．具有良好的運行界面5．算法具有良好的健壯性6．按要求撰寫課程設計報告和設計總結。參考文獻1．《數據結構〔C語言版》,嚴蔚敏、吳偉民,清華大學出版社,1997.審查意見指導教師簽字：教研室主任簽字：年月日1需求分析設計一個哈弗曼編碼譯碼器,實現哈夫曼樹的建立,樹形輸出,編碼和解碼。2概要設計mainmain退出系統幫助哈夫曼文件解碼哈夫曼文件編碼樹形輸出哈夫曼樹查看哈夫曼編碼建立哈夫曼樹退出系統幫助哈夫曼文件解碼哈夫曼文件編碼樹形輸出哈夫曼樹查看哈夫曼編碼建立哈夫曼樹3運行環境〔軟、硬件環境硬件：PC機操作系統：Windows2000/XP/2003編譯環境：VisualC++6.04開發工具和編程語言開發工具：VISCALLc++6.0；編程語言：C語言。5詳細設計#include<stdio.h>#include<stdlib.h>#include<string.h>typedefstruct//結點的結構{ unsignedintweight;//結點的權值 unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//動態分配數組存儲哈夫曼樹typedefchar**HuffmanCode;//動態分配數組存儲哈夫曼編碼HuffmanTreeHT;HuffmanCodeHC;intn=8; constcharmenu[]= "|1建立哈夫曼樹|\n" "|2查看哈夫曼編碼|\n" "|3樹形輸出哈夫曼樹|\n" "|4哈夫曼文件編碼|\n" "|5哈夫曼文件解碼|\n" "|6幫助|\n" "|7退出系統|\n"; constcharhelpsabout[]= "|主要功能:|\n" "|利用哈夫曼編碼進行通信可以大大提高信道的利用率,縮短信息的傳輸時間,降低|\n" "|傳輸成本。但是,這要求在發送端通過一個編碼系統對待傳輸的數據預先編碼,在接收|\n" "|端將傳來的數據進行譯碼〔復原。對于雙工信道,每端都要有一個完整的編/譯碼系|\n" "|統。本系統即是為這樣的信息收發站寫一個哈夫曼碼的編/譯系統。|\n" "||\n" "||\n";voidHuffmantree<>;voidHuffmancode<>;voidpreorder<>;voidstringcopy<>;intmin<>;voidselect<>;voiddecode<>;voidencode<>;voidint_huffmantree<>;voidprint_end<>;voidprint_title<>;voidprint_menu<>;voidprint_helpabout<>;voidprint_huffmancode<>;voidprint_tree<>;//------------------先序遍歷----------------------------------------------------voidpreorder<introot,intdepth>{ inti; for<i=1;i<=depth;i++> printf<"">; if<depth!=0> printf<"└">; else printf<"">; printf<"%d",HT[root].weight,depth>; if<root<=n> printf<":%s\n",HC[root]>;//依次輸出哈夫曼編碼 else printf<"\n">; if<HT[root].lchild!=0> {depth++;preorder<HT[root].lchild,depth>;} if<HT[root].rchild!=0> {preorder<HT[root].rchild,depth>;}}//--------------字符串拷貝函數----------------------------------------------------voidstringcopy<char*strDest,char*strSrc>{char*strDestCopy=strDest; if<!<strDest&&strSrc>>printf<"ERROR!">;while<<*strDest++=*strSrc++>!='\0'>;}//--------返回哈夫曼樹t的前i個結點中權值最小的樹的根結點序號,函數select<>調用------------intmin<HuffmanTreet,inti>{intj,m;unsignedintk=0xffffffff;//k存最小權值,初值取為不小于可能的值for<j=1;j<=i;j++>//對于前i個結點if<t[j].weight<k&&t[j].parent==0>//t[j]的權值小于k,又是樹的根結點{k=t[j].weight;//t[j]的權值賦給km=j;//序號賦給m}t[m].parent=1;//給選中的根結點的雙親賦非零值,避免第2次查找該結點returnm;//返回權值最小的根結點的序號}//----在哈夫曼樹t的前i個結點中選擇2個權值最小的樹的根結點序號,s1為其中序號<權值>較小的----voidselect<HuffmanTreet,inti,int&s1,int&s2>{intj;s1=min<t,i>;//權值最小的根結點序號s2=min<t,i>;//權值第2小的根結點序號if<s1>s2>//s1的序號大于s2的{//交換j=s1;s1=s2;//s1是權值最小的2個中序號較小的s2=j;//s2是權值最小的2個中序號較小的}}//-------w存放n個字符的權值<均>0>,構造哈夫曼樹HT----------------------------------------voidHuffmantree<int*w>{intm,i,s1,s2;HuffmanTreep;if<n<=1>//葉子結點數不大于nreturn;m=2*n-1;//n個葉子結點的哈夫曼樹共有m個結點HT=<HuffmanTree>malloc<<m+1>*sizeof<HTNode>>;//0號單元未用for<p=HT+1,i=1;i<=n;++i,++p,++w>//從1號單元開始到n號單元,給葉子結點賦值{//p的初值指向1號單元<*p>.weight=*w;//賦權值<*p>.parent=0;//雙親域為空<是根結點><*p>.lchild=0;//左右孩子為空<是葉子結點,即單結點樹><*p>.rchild=0;}for<;i<=m;++i,++p>//i從n+1到m<*p>.parent=0;//其余結點的雙親域初值為0for<i=n+1;i<=m;++i>//建哈夫曼樹{//在HT[1～i-1]中選擇parent為0且weight最小的兩個結點,其序號分別為s1和s2select<HT,i-1,s1,s2>;HT[s1].parent=HT[s2].parent=i;//i號單元是s1和s2的雙親HT[i].lchild=s1;//i號單元的左右孩子分別是s1和s2HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;//i號單元的權值是s1和s2的權值之和}}//-------并求出n個字符的哈夫曼編碼HC--------------------------------------------------voidHuffmancode<>{intstart;unsignedintf;inti;unsignedintc;char*cd;HC=<HuffmanCode>malloc<<n+1>*sizeof<char*>>;//分配n個字符編碼的頭指針cd=<char*>malloc<n*sizeof<char>>;//分配求編碼的字符數組cd[n-1]='\0';for<i=1;i<=n;i++>//逐個字符求哈夫曼編碼{start=n-1;//編碼結束符位置for<c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent>//從葉子到根逆向求編碼if<HT[f].lchild==c>//c是其雙親的左孩子cd[--start]='0';//由葉子向根賦值'0'else//c是其雙親的右孩子cd[--start]='1';//由葉子向根賦值'1'HC[i]=<char*>malloc<<n-start>*sizeof<char>>;//為第i個字符編碼分配空間stringcopy<HC[i],&cd[start]>;//從cd復制編碼串到HC矩陣}free<cd>;//釋放工作空間}//---------------------譯碼-----------------------------------------------------voidencode<>{ FILE*fp1=NULL,*fp2=NULL; charinput[20]="input.txt",output[20]="output.txt"; printf<"請輸入輸入文件名<input.txt>：">; scanf<"%s",input>; if<<fp1=fopen<input,"r">>==NULL> { printf<"無此文件！">; getchar<>; getchar<>; return; } printf<"請輸入輸出文件名<output.txt>：">; scanf<"%s",output>; if<<fp2=fopen<output,"w">>==NULL> { printf<"不能創建文件！">; getchar<>; getchar<>; return; } inti,k; unsignedint*w,p,m=0,j; for<k=0;!feof<fp1>;k++> { if<fgetc<fp1>==''> m++; } printf<"哈夫曼編碼為:">; fp1=fopen<input,"r">;w=<unsignedint*>malloc<m*sizeof<unsignedint>>;//動態生成存放m個權值的空間for<j=0;j<=m-1;j++>{ fscanf<fp1,"%d",w+j>;//依次輸入原碼} for<p=0;p<m;p++> { for<i=0;i<n;i++> if<*<w+p>==HT[i+1].weight> { fprintf<fp2,"%s",HC[i+1]>; printf<"%s",HC[i+1]>; } } fclose<fp1>;fclose<fp2>; printf<"\n輸出完成.按任意鍵繼續....">; getchar<>; getchar<>;}//-------------------------解碼------------------------------------------------- voiddecode<> { FILE*fp1=NULL,*fp2=NULL; charinput[20],output[20]; char*code; code=<char*>malloc<n*sizeof<char>>; printf<"請輸入輸入文件名<input.txt>：">; scanf<"%s",input>; if<<fp1=fopen<input,"r">>==NULL> { printf<"無此文件！">; getchar<>; getchar<>; return; } printf<"請輸入輸出文件名<output.txt>：">; scanf<"%s",output>; if<<fp2=fopen<output,"w">>==NULL> { printf<"不能創建文件！">; getchar<>; getchar<>; return; } inti,j; printf<"哈夫曼譯碼為:">; for<i=0;!feof<fp1>;i++> { *<code+i>=fgetc<fp1>; *<code+i+1>='\0'; for<j=0;j<n;j++> if<strcmp<code,HC[j+1]>==0> { fprintf<fp2,"%d",HT[j+1].weight>; printf<"%d",HT[j+1].weight>; i=-1; break; } } fclose<fp1>;fclose<fp2>; printf<"\n輸出完成.按任意鍵繼續....">; getchar<>; getchar<>; }//---------------------初始化哈夫曼樹------------------------------------------voidint_huffmantree<>{ system<"cls">; print_title<>; int*w,i;printf<"請輸入權值的個數<>1>：">;scanf<"%d",&n>;w=<int*>malloc<n*sizeof<int>>;//動態生成存放n個權值的空間printf<"請依次輸入%d個權值<整型>：\n",n>;for<i=0;i<n;i++>{ scanf<"%d",w+i>;}Huffmantree<w>;//根據w所存的n個權值構造哈夫曼樹HT,Huffmancode<>;//n個哈夫曼編碼存于HCprint_end<>;printf<"哈夫曼編碼為：\n">;for<i=1;i<=n;i++>printf<"%5d:%s\n",*<w+i-1>,HC[i]>;print_end<>; printf<"按任意鍵返回...">; getchar<>; getchar<>;}//-----------------哈夫曼編碼菜單----------------------------------voidprint_huffmancode<>{ inti; system<"cls">; print_title<>;printf<"哈夫曼編碼為：\n">;for<i=1;i<=n;i++>printf<"%5d:%s\n",HT[i].weight,HC[i]>;print_end<>; printf<"按任意鍵返回...">; getchar<>; getchar<>;}//--------------幫助菜單-------------------------------------------voidprint_helpabout<> { system<"cls">; print_title<>; printf<helpsabout>; print_end<>; printf<"按任意鍵返回...">; getchar<>; getchar<>; }//----------------樹形輸出菜單--------------------------------------voidprint_tree<>{ system<"cls">; print_title<>; printf<"哈夫曼樹為：\n">; preorder<2*n-1,0>; print_end<>; printf<"按任意鍵返回...">; getchar<>; getchar<>;}//--------------------選擇菜單輸出-------------------------------------------------voidprint_menu<> { while<1> { intselected=0; system<"cls">; print_title<>; printf<menu>; print_end<>; printf<">請選擇[1~7]">; scanf<"%d",&selected>; if<selected<1||selected>7> { printf<"錯誤的選擇！〔請輸入1~7.按任意鍵繼續....">; getchar<>; getchar<>; } switch<selected>{ case1: int_huffmantree<>; break; case2: print_huffmancode<>; break; case3: print_tree<>; break; case4: encode<>; break; case5: decode<>; break; case6: print_helpabout<>; break; case7: exit<0>; break; } } }voidprint_title<>{printf<"+=============================================================================+\n">;printf<"|哈夫曼編碼譯碼器