Huffman课程设计报告 完整版.docx
- 文档编号:10964010
- 上传时间:2023-05-28
- 格式:DOCX
- 页数:31
- 大小:231.95KB
Huffman课程设计报告 完整版.docx
《Huffman课程设计报告 完整版.docx》由会员分享,可在线阅读,更多相关《Huffman课程设计报告 完整版.docx(31页珍藏版)》请在冰点文库上搜索。
Huffman课程设计报告完整版
课程设计
课程设计名称:
数据结构课程设计
专业班级:
学生姓名:
学号:
指导教师:
课程设计时间:
2012.6.11—2012.6.24
计算机科学与技术专业课程设计任务书
学生姓名
专业班级
学号
题目
哈夫曼编码/译码器
课题性质
A
课题来源
D
指导教师
同组姓名
无
主要内容
学习掌握并熟练运用C语言进行程序设计;
针对具体应用问题,选择、设计和实现合适的抽象数据类型;
进行简单的需求分析,给出设计方案。
任务要求
综合运用和融化所学理论知识,提高分析和解决实际问题的能力,达到培养良好程序设计能力和习惯的目的,为开发满足问题要求的小型应用软件奠定基础,达到软件工程的综合性基础训练的目的。
完成需求分析报告,报告中对关键部分给出图表说明。
要求格式规范,工作量饱满。
参考文献
《数据结构(C语言版)》严蔚敏清华大学出版社
《C语言程序设计》(第三版)谭浩强清华大学出版社
审查意见
指导教师签字:
教研室主任签字:
年月日
1需求分析
用huffman编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。
但是,这要求在发送端通过一个编码系统对待传输数据预先编码,在接收端将传来的数据进行译码(复原)。
对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。
是为着这样的信息收发站写一个huffman编/译码系统。
在整个功能中主要分三大模块:
其一,由已知信息建立Huffman树;其二,由Huffman树进行相应结点编码操作;其三,由第二部分的编码进行对码流的译码操作;其次,本程序能连续建Huffman树并对其进行不同文件的保存、读取操作,对Huffman编码有其保存操作,对用户新建的Huffman树可以随时查看初始化、构造过程、构造结果等功能
2概要设计
.该系统主要功能俯视:
该系统具有以下功能如图1所示:
其中各功能对应函数声明如表1所示:
功能名称
函数首部
新建哈夫曼树
voidCreateHuffmanTree(HnodeTypearr[])
查看哈夫曼树
voidSearchHuffmanTree(HnodeTypearr[])
保存哈夫曼树
voidSaveHuffmanTree(HnodeTypearr[])
读取哈夫曼树
voidread(HnodeTypearr[],intn)
哈夫曼编码器
voidHuffmanCode(HnodeTypearr[],HCodeTypeHCarr[])
哈夫曼译码器
voidHuffmanDecording(HnodeTypearr[])
表1.各功能函数首部对应表
.各功能模块讲解:
1.新建哈夫曼树:
在功能中会提示用户从终端读入n个结点信息(结点可以是整型、字符型、字符串、文本格式等),信息包括结点名称及相应权值,建立哈夫曼树,哈夫曼树中每个结点定义如下:
typedefstructHuffNode
{
charnode[100];//结点
intweighe;//权值
intparent;//该结点双亲
intlchild;//该结点左孩子指针
intrchild;//该结点右孩子指针
}HnodeType;
2.查看哈夫曼树:
在查看哈夫曼树功能中用户可以任意查看哈夫曼树初始化、构造过程、以及直接查看构造结果,如图2所示查看子功能结构图:
3.保存哈夫曼树:
由于本系统能很好地连续新建Huffman树,故当用户保存当前新建的Huffman树时系统会显示用户已将其保存至第几个哈夫曼表中。
4.读取哈夫曼树:
如保存功能所述,当用户建树超过两次时点击读取功能键时就会提醒用户,要读取已保存的第几颗Huffman树,当用户只保存一颗Huffman树时会直接读取,不会提醒用户。
5.哈夫曼编码器:
当用户新建一颗Huffman树并对其执行编码操作时,会在屏幕上显示当前Huffman树各叶结点的编码,并会提醒用户是否保存当前编码,保存则保存至第几个Huffman编码表中,在进行哈夫曼编码操作时,需借助一个辅助数组来存放每个结点的编码信息(即01代码),每个结点的编码信息存储类型如下:
typedefstructHCodeType
{
intbit[MaxBit];//存储叶结点编码
intstart;//编码起始位
}HCodeType;
6.哈夫曼译码器:
当进行译码器操作时,会让用户输入待译码的码流(即01代码),点击译码即刻输出译码结果。
3运行环境
硬件环境:
Pentium(R)D;CPU2.8GHz;内存1.00GB
软件环境:
MicrosoftWindowsXPProfessional版本2002ServicePack3
4开发工具和编程语言
VisualC++6.0、C语言
5详细设计
、新建哈夫曼树算法源程序
voidCreateHuffmanTree(HnodeTypearr[])
{
system("colora4");
voidselect(HnodeTypearr[],intn);//函数声明该程序中要用到select函数
inti;//建树整个过程
cout<<"请输入叶结点数:
";
cin>>global_n;
while(true){
if(!
cin){
cin.clear();//调用cin.clear取消cin的fail状态
cin.ignore(1024,'\n');//调用cin.ignore清楚已输入内容
cout< } elsebreak;//输入正确则跳出循环 cin>>global_n;//重新输入 } printf("\t\t\t请输入%d个叶结点及相应的权值: \n\n",global_n); for(i=1;i<=global_n;i++)//对Huffman结构体数组初始化 { printf("第%d个叶结点: ",i); cin>>arr[i].node; printf("第%d个叶结点的权值: ",i); cin>>arr[i].weighe; while(true){ if(! cin){ cin.clear();//调用cin.clear取消cin的fail状态 cin.ignore(1024,'\n');//调用cin.ignore清楚已输入内容 cout< } elsebreak;//输入正确则跳出循环 cin>>arr[i].weighe;//重新输入 } arr[i].parent=0; arr[i].lchild=0; arr[i].rchild=0; cout< } for(i=global_n+1;i<=2*global_n-1;i++){ arr[i].weighe=0; arr[i].parent=0; arr[i].lchild=0; arr[i].rchild=0; } for(i=global_n+1;i<=2*global_n-1;i++){ select(arr,i-1); arr[i].lchild=global_x1; arr[i].rchild=global_x2; arr[i].weighe=arr[global_x1].weighe+arr[global_x2].weighe; arr[global_x1].parent=i; arr[global_x2].parent=i; }//end建树过程 } 辅助函数select()算法如下: voidselect(HnodeTypearr[],intn) { inti; intj; for(i=1;i<=n;i++) { if(arr[i].parent==0) { global_x1=i; break; } for(j=i+1;j<=n;j++) { if(arr[j].parent==0) { global_x2=j; break; } for(i=1;i<=n;i++) { if(arr[global_x1].weighe>arr[i].weighe&&arr[i].parent==0&&global_x2! =i) global_x1=i; } for(i=1;i<=n;i++) { if(arr[global_x2].weighe>arr[i].weighe&&arr[i].parent==0&&global_x1! =i) global_x2=i; } if(arr[global_x1].weighe>arr[global_x2].weighe)//小权值为做孩子,大权值为右孩子 { inttemp; temp=global_x1; global_x1=global_x2; global_x2=temp; } 、查看哈夫曼树算法源程序 voidSearchHuffmanTree(HnodeTypearr[]) { voidselect(HnodeTypearr[],intn);//函数声明该程序中要用到的select函数 inti,j,k,choice; while(true) { system("cls"); cout< cout<<"\t\t\t\t1-查看初始化\t\t"< cout<<"\t\t\t\t2-查看构造过程\t\t"< cout<<"\t\t\t\t3-直接查看构造结果\t\t"< cout<<"\t\t\t\t0-退出\t\t"< cout<<"请选择: "; cin>>choice; hile(true){ if(! cin){ cin.clear();//调用cin.clear取消cin的fail状态 cin.ignore(1024,'\n');//调用cin.ignore清楚已输入内容 cout< } elsebreak;//输入正确则跳出循环 cin>>choice;//重新输入 } switch(choice) { case1: { system("cls");system("color80"); cout< getchar(); getchar(); for(i=1;i<=global_n;i++)//对Huffman结构体数组初始化 { arr[i].parent=0; arr[i].lchild=0; arr[i].rchild=0; } for(i=global_n+1;i<=2*global_n-1;i++) { arr[i].weighe=0; arr[i].parent=0; arr[i].lchild=0; arr[i].rchild=0; } cout< cout<<"\t\t\t叶子权值双亲左孩子右孩子"< for(i=1;i<=global_n;i++)//循环输出各结点信息cout<<"\t\t"< for(i=global_n+1;i<=2*global_n-1;i++) cout<<"\t\t\t"< //显示初始化之后立刻进入建树操作,以防用户进行其他操作如: //初始化后直接进行编码操作,此时Huffman树还未建,会引起程序崩溃 for(i=global_n+1;i<=2*global_n-1;i++) { select(arr,i-1); arr[i].lchild=global_x1; arr[i].rchild=global_x2; arr[i].weighe=arr[global_x1].weighe+arr[global_x2].weighe; arr[global_x1].parent=i; arr[global_x2].parent=i; } cout<<"按任意键继续......"; getchar(); break; case2: { system("cls"); system("colorf4"); cout< getchar();//Huffman表已经存在,在调用select函数时会出错 getchar(); cout< if(global_n>1) { for(i=1;i<=global_n;i++)//对Huffman结构体数组初始化 { arr[i].parent=0; arr[i].lchild=0; arr[i].rchild=0; } for(i=global_n+1;i<=2*global_n-1;i++) { arr[i].weighe=0; arr[i].parent=0; arr[i].lchild=0; arr[i].rchild=0; } for(i=global_n+1;i<=2*global_n-1;i++)//确定双亲结点i的左右孩子 {//需从1到(i-1)中找出权值最小的两结点 select(arr,i-1);//选择函数,找最小结点,返回下标global_x1、global_x2 arr[i].lchild=global_x1; arr[i].rchild=global_x2; arr[i].weighe=arr[global_x1].weighe+arr[global_x2].weighe; arr[global_x1].parent=i; arr[global_x2].parent=i; cout< getchar(); cout<<"\t\t\t叶子权值双亲左孩子右孩子"< for(j=1;j<=global_n;j++) cout<<"\t\t"< for(k=global_n+1;k<=2*global_n-1;k++) cout<<"\t\t\t"< < } else//global_n==1最后一层循环都用不上,要另考虑 { cout<<"\t\t\t叶子权值双亲左孩子右孩子"< } } cout<<"按任意键继续......"; getchar(); break; case3: { system("cls");system("color7f"); cout< getchar(); getchar(); for(i=1;i<=global_n;i++)//对Huffman结构体数组初始化 { arr[i].parent=0; arr[i].lchild=0; arr[i].rchild=0; } for(i=global_n+1;i<=2*global_n-1;i++) { arr[i].weighe=0; arr[i].parent=0; arr[i].lchild=0; arr[i].rchild=0; } cout< for(i=global_n+1;i<=2*global_n-1;i++) { select(arr,i-1); arr[i].lchild=global_x1; arr[i].rchild=global_x2; arr[i].weighe=arr[global_x1].weighe+arr[global_x2].weighe; arr[global_x1].parent=i; arr[global_x2].parent=i; } cout<<"\t\t\t叶子权值双亲左孩子右孩子"< for(i=1;i<=global_n;i++) cout<<"\t\t"< for(i=global_n+1;i<=2*global_n-1;i++) cout<<"\t\t\t"< < } cout<<"按任意键继续......"; getchar(); break; case0: { gotoend0; break; } default: cout<<"输入错误"< } 、保存哈夫曼树算法源程序 voidSaveHuffmanTree(HnodeTypearr[]) { FILE*fp; inti; charfilename[100]="哈夫曼_表"; charis[10]; itoa(filenum,is,10);//调用itoa函数将整形filename转换成十进制并保存在字符变量is中 strcat(filename,is);//将huffman表序号追加在filename后 strcat(filename,".txt");//将.txt追加在filename后以形成最终要保存的文件名 if((fp=fopen(filename,"w"))==NULL){ cout< exit(0); } for(i=1;i<=global_n;i++) fprintf(fp,"\t\t%6s%8d%8d%8d%8d\n",arr[i].node,arr[i].weighe,arr[i].parent, arr[i].lchild,arr[i].rchild); for(i=global_n+1;i<=2*global_n-1;i++) fprintf(fp,"\t\t\t%8d%8d%8d%8d\n",arr[i].weighe,arr[i].parent, arr[i].lchild,arr[i].rchild); fclose(fp); printf("\n"); cout< "< } voidread(HnodeTypearr[],intn)//参数n为打开第几个文件文件 { FILE*fp; inti; charfilename[100]="哈夫曼_表"; charis[10]; itoa(n,is,10);//调用itoa函数将整形n转换成十进制并保存在字符变量is中 strcat(filename,is);//将要访问的huffman表序号追加在filename后 strcat(filename,".txt");//将.txt追加在filename后以形成最终要访问的文件名 if((fp=fopen(filename,"r"))==NULL){ cout< exit(0); } cout< while(! feof(fp))//当,! 没有,feof到文件尾, {//当没有到文件尾就循环,否则退出 for(i=1;i<=global_n;i++){ fscanf(fp,"\t\t%6s%8d%8d%8d%8d\n",&arr[i].node,&arr[i].weighe,&arr[i].parent,&arr[i].lchild,&arr[i].rchild); cout<<"\t\t"<
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Huffman课程设计报告 完整版 Huffman 课程设计 报告