数据结构课程试验报告.docx
- 文档编号:14794596
- 上传时间:2023-06-27
- 格式:DOCX
- 页数:34
- 大小:75.33KB
数据结构课程试验报告.docx
《数据结构课程试验报告.docx》由会员分享,可在线阅读,更多相关《数据结构课程试验报告.docx(34页珍藏版)》请在冰点文库上搜索。
数据结构课程试验报告
数据结构课程实验报告
题目:
哈夫曼编/译码器
班级:
电信0608
姓名:
彭飞
学号:
012006013517
指导老师:
刘玉
华中科技大学电信系
2007年12月
1.需求分析...............................1
2.概要设计...............................2
2.1抽象数据类型定义.........................................2
2.2主程序...................................................2
2.3模块.....................................................2
3.详细设计...............................3
3.1哈夫曼编码类型...........................................3
3.2相关基本操作.............................................3
3.3主程序伪码算法...........................................9
3.4函数调用关系图...........................................11
4.调试分析..............................12
5.用户手册..............................13
6.测试结果..............................14
7.附录...................................16
一、需求分析
1.哈夫曼编码对象为任意字符,包括数字及各种符号,通过统计用户输入字符串中个关键对象出现次数,建立相应的哈夫曼树。
2.演示程序以用户和计算机的对话方式执行,即在计算机终端上显示“提示信息”,用户由键盘输入数字命令,执行相应命令后显示操作结果。
3.程序执行的命令:
1)建立哈夫曼树;
2)求哈夫曼编码;
3)打印哈夫曼树;
4)对哈夫曼编码进行译码,提示用户输入合法编码;
4.输入过程中能自动滤去合法字符以外的其他字符,并能在输入不当时输出相应的提示信息。
5.测试数据:
1)输入:
Hello!
world!
2)输出:
见测试结果。
二、概要设计
1.抽象数据类型的定义如下:
ADTHuffmanTree{
数据对象D:
D={ai|ai∈Htnode型结点,i=1,2,…,n,n≥0}
数据关系:
R={
基本操作:
select(HuffmanTreeHT,intn,int&s1,int&s2)
初始条件:
HT已存在。
操作结果:
在树HT中的前n个结点中找出权值最小的两个结点分别记录在s1,s2上。
HuffmanCoding(HuffmanTree&HT,Weight*w,intm)
初始条件:
HT已存在。
操作结果:
将HT建成哈夫曼树,建树过程中调用Select()函数。
Decoding(HuffmanTreeHT,Weight*w,intm)
初始条件:
HT已建成哈夫曼树。
操作结果:
对输入的二进制编码根据已建成的HT哈夫曼树进行译码。
bianma(HuffmanTreeHT,HuffmanCodeHC,Weight*w,intm,intn)
初始条件:
HT已建成哈夫曼树。
操作结果:
将HT中个结点对应编码存入HC中。
Counting(Weight*w,char*c)
初始条件:
字符已输入。
操作结果:
统计各字数输入频率,存入相应权值单元w[]中。
Print()
初始条件:
无。
操作结果:
打印操作命令菜单。
}ADTHuffmanTree
2.主程序
voidmain(){
输入信息;
do{
接受命令;
处理命令;
}while(“命令”!
=“退出”);
3.本程序包含两个模块
1)主程序模块
2)哈夫曼树模块——实现哈夫曼树的建立,编码及译码。
三、详细设计
1.哈夫曼编码类型:
typedefstruct
{
charzifu;//不同的字符
unsignedintquanzhi;
unsignedintd;
charelem;//输入的字符
char*bianma;//各个字符的编码
charxx;//存放译码字符
intweizhi;
intflag;
}Weight;
typedefstruct
{
unsignedintweight;
unsignedintparent,lchild,rchild;
}Htnode,*HuffmanTree;
typedefchar**HuffmanCode;
2.相关的基本操作有:
voidselect(HuffmanTreeHT,intn,int&s1,int&s2)
//找权值最小的两个节点
voidHuffmanCoding(HuffmanTree&HT,Weight*w,intm)
//建立哈夫曼树
voidDecoding(HuffmanTreeHT,Weight*w,intm)
//译码
voidbianma(HuffmanTreeHT,HuffmanCodeHC,Weight*w,intm,intn)
//对输入的字符串编码
voidHuffmanbianma(HuffmanTreeHT,HuffmanCode&HC,Weight*w,intm)
//对每个字符进行哈夫曼编码
intcounting(Weight*w,char*c)
//频率统计
voidPrint()
//命令提示
intchoose()
//字符输入正误判断
各部分操作的伪码算法如下:
voidselect(HuffmanTreeHT,intn,int&s1,int&s2)
{//找权值最小的两个节点
inti,j;
for(i=1;i<=n;i++)
if(!
HT[i].parent)//双亲为0表示未选
{
s1=i;
break;
}
for(j=i+1;j<=n;j++)
if(!
HT[j].parent)
{
s2=j;
break;
}
for(i=1;i<=n;i++)
if((HT[s1].weight>HT[i].weight)&&(!
HT[i].parent)&&(s2!
=i))//找权值更小的
s1=i;
for(j=1;j<=n;j++)
if((HT[s2].weight>HT[j].weight)&&(!
HT[j].parent)&&(s1!
=j))
s2=j;
printf("s1=%d,s2=%d\n",s1,s2);
if(s1>s2)
{
i=s1;
s1=s2;
s2=i;
}
}
voidHuffmanCoding(HuffmanTree&HT,Weight*w,intm)
{//建立哈夫曼树
inti;
ints1,s2;
HT=(HuffmanTree)malloc((2*m-1)*sizeof(Htnode));
for(i=1;i<=2*m-1;i++)//初始化
{
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=1;i<=m;i++)
{
HT[i].weight=w[i].quanzhi;}//初始化
for(i=m+1;i<=2*m-1;i++)
{
select(HT,i-1,s1,s2);
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
}
voidDecoding(HuffmanTreeHT,Weight*w,intm)
{//译码
inti;
intk;
inty=1;
charp[30];
intj=0;
unsignedintc,f;
printf("请输入要编码的二进制数:
");
_P:
scanf("%s",p);
getchar();
printf("\n");
c=2*m-1;
for(k=0;*(p+k)!
='\0';k++)
{
if(*(p+k)>='2'||*(p+k)<'0')
{
printf("含有非01字符!
请重新输入:
");
goto_P;
}
}
for(k=0;*(p+k)!
='\0';k++);//求二进制数长度
for(i=1,j=c;i<=k&&j>=1;i++)
{
if(i>k)
break;
c=j;
while(HT[c].lchild&&HT[c].rchild)
{
if(*(p+i-1)=='1')
{
f=HT[c].rchild;
c=f;
}
elseif(*(p+i-1)=='0')
{
f=HT[c].lchild;
c=f;
}
else
{
printf("\n输入的第%d个二进制数有误!
\n",i);
break;
}
i++;
if(*(p+i-1)=='\0')
break;
}
if(HT[c].lchild==HT[c].rchild)
{
printf("%c",w[c].zifu);
i=i-1;
}
}
if(*(p+i-1)!
='\0')
printf("\n输入的第%d位有误!
\n",i-2);
printf("\n");
}
voidbianma(HuffmanTreeHT,HuffmanCodeHC,Weight*w,intm,intn)
{//对输入的字符串编码
inti,t;
t=m;
for(i=1;i<=n;i++)
w[i].bianma="qqq";
for(i=1;i<=n;i++)
{
t=w[i].weizhi;
w[i].bianma=HC[t];
}
for(i=1;i<=n;i++)
printf("%s",w[i].bianma);
printf("\n");
}
voidHuffmanbianma(HuffmanTreeHT,HuffmanCode&HC,Weight*w,intm)
{//对每个字符进行哈夫曼编码
unsignedintf;
unsignedintc;
intstart,i;
char*cd;
cd=(char*)malloc(m*sizeof(char));
cd[m-1]='\0';
for(i=1;i<=m;i++)
{
start=m-1;
for(c=i,f=HT[i].parent;f!
=0;c=f,f=HT[f].parent)
if(HT[f].lchild==c)
cd[--start]='0';
elsecd[--start]='1';
HC[i]=(char*)malloc((m-start)*sizeof(char));
strcpy(HC[i],&cd[start]);//将编码存如HC中
}
for(i=1;i<=m;i++)
w[i].bianma=HC[i];
}
intcounting(Weight*w,char*c)
{//频率统计
inti,j,n,k=0,m=1;
for(i=0;*(c+i)!
='\0';i++);
n=i;
for(i=1;i<=n;i++,k++)//初始化
{
w[i].elem=*(c+k);
w[i].d=0;//初始每个字符个数为0
w[i].flag=1;
w[i].weizhi=1;
}
for(i=1;i<=n;i++)
{
k=0;
for(j=1;j<=n;j++)
if(w[j].flag)
{
if(w[i].elem==w[j].elem)
{
w[j].weizhi=m;
w[j].flag=0;
k++;
}
}
if(k>0)
m++;
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
if(w[i].elem==w[j].elem)
{
w[i].d=w[i].d+1;
}//统计各个字符的个数
}
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
if(w[i].elem==w[j].elem&&w[i].d>=w[j].d&&w[j].d!
=0)
w[j].d=0;//除去相同字符
for(i=1,m=1;i<=n;i++)
{
if(w[i].d!
=0)//放入权值
{
w[m].zifu=w[i].elem;
w[m].quanzhi=w[i].d;
m++;
}
}
returnm-1;
}
voidPrint()
{
printf("1:
察看各个字符权值\n");
printf("2:
察看各个字符编码\n");
printf("3:
查看哈夫蔓表\n");
printf("4:
对输入字符串编码\n");
printf("5:
对数字译码\n");
printf("6:
清屏\n");
printf("0:
退出\n");
}
intchoose()
{
intflag=1;
intk;
inti;
chars[10];
printf("请选择:
");
scanf("%s",s);
getchar();
printf("\n");
for(i=0;s[i]!
='\0';i++);
if(i>1)
goto_F;
if(s[0]>='0'&&s[0]<='9')
{
k=s[0]-'0';
flag=0;
}
_F:
while(flag)
{
printf("输入错误,请重新选择:
");
scanf("%s",s);
getchar();
printf("\n");
for(i=0;s[i]!
='\0';i++);
if(i>1)
goto_F;
if(s[0]>='0'&&s[0]<='9')
{
k=s[0]-'0';
flag=0;
}
}
returnk;
}
3.主程序伪码算法
voidmain()
{
char*c;
intk=0;
inti;
intm=1;//不同字符的个数
intn;//输入字符的个数
HuffmanTreeHT;
Weight*w;
c=(char*)malloc(30*sizeof(char));
_L:
printf("请输入字母:
");
gets(c);
for(i=0;*(c+i)!
='\0';i++);
n=i;
if(n==0)
{
printf("没有输入字符!
\n");
goto_L;
}
printf("\n以下是对%s的操作:
\n",c);
Print();
HuffmanCodeHC;
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
w=(Weight*)malloc((n+1)*sizeof(Weight));
m=counting(w,c);
HuffmanCoding(HT,w,m);
Huffmanbianma(HT,HC,w,m);
while((k=choose()))
{
switch(k)
{
case1:
printf("字符权值\n");
for(i=1;i<=m;i++)
{
printf("%c%d\n",w[i].zifu,w[i].quanzhi);
}
break;
case2:
for(i=1;i<=m;i++)
printf("%cis%s\n",w[i].zifu,w[i].bianma);
break;
case3:
printf("位置权值双亲左子右子\n");
for(i=1;i<=2*m-1;i++)
printf("%d%d%d%d%d\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
break;
case4:
printf("输入的字符串编码为:
");
bianma(HT,HC,w,m,n);
printf("\n");
break;
case5:
Decoding(HT,w,m);
break;
case6:
system("cls");
printf("请输入字母:
%s",c);
printf("\n以下是对%s的操作:
\n",c);
Print();
break;
case0:
exit
(1);
default:
printf("选择错误!
\n");
}
}
}
4.函数的调用关系图
四、调试分析
1.本次实验作业题目难度适当,加之几个主要算法已在书上出现并且进行过上机练习,故思路比较正确,作业完成比较顺利。
2.本程序的主要算法是Select,HuffmanCoding,Yima,Bianma,Counting.这几过程中主要考虑的是要求实现的功能,主程序对于各个程序的调用以及异常处理,没有处理好会使整个程序运行混乱。
每个功能完成之后要如何结束再进入主界面选择也是比较烦恼的一部分。
每次操作完后要能恢复有序。
3.在解码过程中,很容易就把最后一个字符忽略了,应该注意。
4.算法时空复杂度分析:
建树时时间效率较低,初始化树为o(n)级,建树时为o((m-n)*(m))=o(n*n)级(其中m=2*n-1为哈夫曼结点总个数)。
五、用户手册
1.本程序的运行环境为DOS操作系统,执行文件为:
Hafuman.exe。
2.进入演示程序后即显示提示信息:
“请输入字母:
”以等待用户输入字母。
如下图:
3.
4.输入结束后,以回车结束,程序进行统计并给出提示菜单,如下图:
5.
6.选择“1”则显示出刚才输入的各个字符及其权值,选择“2”则显示各个字符及其哈夫曼编码,选择“3”则打印出哈夫曼表,选择“4”则对输入字符串编码,选择“5”则要求再输入二进制哈夫曼编码,从而进行译码,选择“6”则清屏,选择“7”退出。
六、测试结果
1.输入“Hello!
World!
”:
2.输入“1”:
3.输入“2”:
4.输入“3”:
5.输入“4”:
6.输入“5”,并输入相应二进制编码:
7.输入“6”后清屏:
8.输入“8”,退出程序。
以上结果中,编码与译码正好对应一致,说明程序结果正确。
七、附录
源程序(带注释):
#include
#include"stdlib.h"
#include"malloc.h"
#include"iomanip.h"
#include"string.h"
typedefstruct
{
charzifu;//不同的字符
unsignedintquanzhi;
unsignedintd;
charelem;//输入的字符
char*bianma;//各个字符的编码
charxx;//存放译码字符
intweizhi;
intflag;
}Weight;
typedefstruct
{
unsignedintweight;
unsignedintparent,lchild,rchild;
}Htnode,*HuffmanTree;
typedefchar**HuffmanCode;
voidselect(HuffmanTreeHT,intn,int&s1,int&s2)
{//找权值最小的两个节点
inti,j;
for(i=1;i<=n;i++)
if(!
HT[i].parent)//双亲为0表示未选
{
s1=i;
break;
}
for(j=i+1;j<=n;j++)
if(!
HT[j].parent)
{
s2=j;
break;
}
for(i=1;i<=n;i++)
if((HT[s1].weight>HT[i].weight)&&(!
HT[i].parent)&&(s2!
=i))//找权值更小的
s1=i;
for(j=1;j<=n;j++)
if((HT[s2].weight>HT[j].weight)&&(!
HT[j].parent)&&(s1!
=j))
s2=j;
printf("s1=%d,s2=%d\n",s1,s2);
if(s1>s2)
{
i=s1;
s1=s2;
s2=i;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程 试验报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)