數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告哈夫曼編碼譯碼器

..哈弗曼編碼譯碼器專業(yè)班級：XXXX學(xué)號：XXXX姓名：XXXX指導(dǎo)教師：XXXX課程設(shè)計(jì)時(shí)間：XXXX計(jì)算機(jī)專業(yè)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書學(xué)生姓名XXXX專業(yè)班級XXXX學(xué)號XXXX題目哈弗曼編碼譯碼器課題性質(zhì)工程設(shè)計(jì)課題來源XXXX指導(dǎo)教師XXXX同組姓名XXXX主要內(nèi)容設(shè)計(jì)一個(gè)哈弗曼編碼譯碼器,實(shí)現(xiàn)哈夫曼樹的建立,樹形輸出,編碼和解碼。任務(wù)要求1．研究哈弗曼樹的數(shù)據(jù)存儲方式2．實(shí)現(xiàn)哈弗曼編碼譯碼器的主要算法3．分析算法的運(yùn)行效率4．具有良好的運(yùn)行界面5．算法具有良好的健壯性6．按要求撰寫課程設(shè)計(jì)報(bào)告和設(shè)計(jì)總結(jié)。參考文獻(xiàn)1．《數(shù)據(jù)結(jié)構(gòu)〔C語言版》,嚴(yán)蔚敏、吳偉民,清華大學(xué)出版社,1997.審查意見指導(dǎo)教師簽字：教研室主任簽字：年月日1需求分析設(shè)計(jì)一個(gè)哈弗曼編碼譯碼器,實(shí)現(xiàn)哈夫曼樹的建立,樹形輸出,編碼和解碼。2概要設(shè)計(jì)mainmain退出系統(tǒng)幫助哈夫曼文件解碼哈夫曼文件編碼樹形輸出哈夫曼樹查看哈夫曼編碼建立哈夫曼樹退出系統(tǒng)幫助哈夫曼文件解碼哈夫曼文件編碼樹形輸出哈夫曼樹查看哈夫曼編碼建立哈夫曼樹3運(yùn)行環(huán)境〔軟、硬件環(huán)境硬件：PC機(jī)操作系統(tǒng)：Windows2000/XP/2003編譯環(huán)境：VisualC++6.04開發(fā)工具和編程語言開發(fā)工具：VISCALLc++6.0；編程語言：C語言。5詳細(xì)設(shè)計(jì)#include<stdio.h>#include<stdlib.h>#include<string.h>typedefstruct//結(jié)點(diǎn)的結(jié)構(gòu){ unsignedintweight;//結(jié)點(diǎn)的權(quán)值 unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//動態(tài)分配數(shù)組存儲哈夫曼樹typedefchar**HuffmanCode;//動態(tài)分配數(shù)組存儲哈夫曼編碼HuffmanTreeHT;HuffmanCodeHC;intn=8; constcharmenu[]= "|1建立哈夫曼樹|\n" "|2查看哈夫曼編碼|\n" "|3樹形輸出哈夫曼樹|\n" "|4哈夫曼文件編碼|\n" "|5哈夫曼文件解碼|\n" "|6幫助|\n" "|7退出系統(tǒng)|\n"; constcharhelpsabout[]= "|主要功能:|\n" "|利用哈夫曼編碼進(jìn)行通信可以大大提高信道的利用率,縮短信息的傳輸時(shí)間,降低|\n" "|傳輸成本。但是,這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對待傳輸?shù)臄?shù)據(jù)預(yù)先編碼,在接收|\n" "|端將傳來的數(shù)據(jù)進(jìn)行譯碼〔復(fù)原。對于雙工信道,每端都要有一個(gè)完整的編/譯碼系|\n" "|統(tǒng)。本系統(tǒng)即是為這樣的信息收發(fā)站寫一個(gè)哈夫曼碼的編/譯系統(tǒng)。|\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>;}}//--------------字符串拷貝函數(shù)----------------------------------------------------voidstringcopy<char*strDest,char*strSrc>{char*strDestCopy=strDest; if<!<strDest&&strSrc>>printf<"ERROR!">;while<<*strDest++=*strSrc++>!='\0'>;}//--------返回哈夫曼樹t的前i個(gè)結(jié)點(diǎn)中權(quán)值最小的樹的根結(jié)點(diǎn)序號,函數(shù)select<>調(diào)用------------intmin<HuffmanTreet,inti>{intj,m;unsignedintk=0xffffffff;//k存最小權(quán)值,初值取為不小于可能的值for<j=1;j<=i;j++>//對于前i個(gè)結(jié)點(diǎn)if<t[j].weight<k&&t[j].parent==0>//t[j]的權(quán)值小于k,又是樹的根結(jié)點(diǎn){k=t[j].weight;//t[j]的權(quán)值賦給km=j;//序號賦給m}t[m].parent=1;//給選中的根結(jié)點(diǎn)的雙親賦非零值,避免第2次查找該結(jié)點(diǎn)returnm;//返回權(quán)值最小的根結(jié)點(diǎn)的序號}//----在哈夫曼樹t的前i個(gè)結(jié)點(diǎn)中選擇2個(gè)權(quán)值最小的樹的根結(jié)點(diǎn)序號,s1為其中序號<權(quán)值>較小的----voidselect<HuffmanTreet,inti,int&s1,int&s2>{intj;s1=min<t,i>;//權(quán)值最小的根結(jié)點(diǎn)序號s2=min<t,i>;//權(quán)值第2小的根結(jié)點(diǎn)序號if<s1>s2>//s1的序號大于s2的{//交換j=s1;s1=s2;//s1是權(quán)值最小的2個(gè)中序號較小的s2=j;//s2是權(quán)值最小的2個(gè)中序號較小的}}//-------w存放n個(gè)字符的權(quán)值<均>0>,構(gòu)造哈夫曼樹HT----------------------------------------voidHuffmantree<int*w>{intm,i,s1,s2;HuffmanTreep;if<n<=1>//葉子結(jié)點(diǎn)數(shù)不大于nreturn;m=2*n-1;//n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有m個(gè)結(jié)點(diǎn)HT=<HuffmanTree>malloc<<m+1>*sizeof<HTNode>>;//0號單元未用for<p=HT+1,i=1;i<=n;++i,++p,++w>//從1號單元開始到n號單元,給葉子結(jié)點(diǎn)賦值{//p的初值指向1號單元<*p>.weight=*w;//賦權(quán)值<*p>.parent=0;//雙親域?yàn)榭?lt;是根結(jié)點(diǎn)><*p>.lchild=0;//左右孩子為空<是葉子結(jié)點(diǎn),即單結(jié)點(diǎn)樹><*p>.rchild=0;}for<;i<=m;++i,++p>//i從n+1到m<*p>.parent=0;//其余結(jié)點(diǎn)的雙親域初值為0for<i=n+1;i<=m;++i>//建哈夫曼樹{//在HT[1～i-1]中選擇parent為0且weight最小的兩個(gè)結(jié)點(diǎn),其序號分別為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號單元的權(quán)值是s1和s2的權(quán)值之和}}//-------并求出n個(gè)字符的哈夫曼編碼HC--------------------------------------------------voidHuffmancode<>{intstart;unsignedintf;inti;unsignedintc;char*cd;HC=<HuffmanCode>malloc<<n+1>*sizeof<char*>>;//分配n個(gè)字符編碼的頭指針cd=<char*>malloc<n*sizeof<char>>;//分配求編碼的字符數(shù)組cd[n-1]='\0';for<i=1;i<=n;i++>//逐個(gè)字符求哈夫曼編碼{start=n-1;//編碼結(jié)束符位置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個(gè)字符編碼分配空間stringcopy<HC[i],&cd[start]>;//從cd復(fù)制編碼串到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<"不能創(chuàng)建文件！">; 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>>;//動態(tài)生成存放m個(gè)權(quán)值的空間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輸出完成.按任意鍵繼續(xù)....">; 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<"不能創(chuàng)建文件！">; 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輸出完成.按任意鍵繼續(xù)....">; getchar<>; getchar<>; }//---------------------初始化哈夫曼樹------------------------------------------voidint_huffmantree<>{ system<"cls">; print_title<>; int*w,i;printf<"請輸入權(quán)值的個(gè)數(shù)<>1>：">;scanf<"%d",&n>;w=<int*>malloc<n*sizeof<int>>;//動態(tài)生成存放n個(gè)權(quán)值的空間printf<"請依次輸入%d個(gè)權(quán)值<整型>：\n",n>;for<i=0;i<n;i++>{ scanf<"%d",w+i>;}Huffmantree<w>;//根據(jù)w所存的n個(gè)權(quán)值構(gòu)造哈夫曼樹HT,Huffmancode<>;//n個(gè)哈夫曼編碼存于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<"錯(cuò)誤的選擇！〔請輸入1~7.按任意鍵繼續(xù)....">; 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<"|哈夫曼編碼譯碼器