数据结构课程设计报告哈夫曼编码译码器

..哈弗曼编码译码器专业班级：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<"|哈夫曼编码译码器