第1页共8页华北水利水电大学数据结构实验报告2015~2016学年第一学期2013级计算机科学与技术专业班级:2013156学号:201315607姓名:冯浩亮实验三树的应用一、实验题目:树的应用——哈夫曼编码二、实验内容:利用哈夫曼编码进行通信可以大大提高信道的利用率,缩短信息传输的时间,降低传输成本。根据哈夫曼编码的原理,编写一个程序,在用户输入结点权值的基础上求哈夫曼编码。从键盘输入若干字符及每个字符出现的频率,将字符出现的频率作为结点的权值,建立哈夫曼树,求出各字符的哈夫曼编码。要求:1.输出存放哈夫曼树的数组HT的初态和终态;2.输出每个字符的哈夫曼编码;3.输入由上述若干字符组成的字符串,对电文进行编码并输出;4.(选作)输入电文的哈夫曼编码,进行译码并输出。三、实验要求:1.使用C语言完成算法设计和程序设计并上机调试通过。2.撰写实验报告,提供实验结果和数据。3.写出算法设计小结和心得。四、程序源代码:#includestdio.h#includestring.h#includestdlib.h#includememory.h#includeconio.h#defineINIT_CAPCITY100structHTNode//结点信息{charc;//数据项intparent;//双亲结点的位置intlchild;intrchild;intweight;//权值};structChNode//定义一个结构体,用来存放字符串的各个字符和权值信息{charc;intweight;};structHCode第2页共8页{charcode[INIT_CAPCITY];//存放当前结点的哈夫曼编码intm_start;//开始存放的位置};//创建哈夫曼树voidCreateHT(HTNodeht[],intn,ChNodes[]){inti,k,lnode,rnode;//lnode为最小权值结点的位置,rnode为次小权值结点的位置intmin1,min2;//min1为最小值,min2为次小值for(i=0;i2*n-1;i++)//初始化{ht[i].parent=-1;ht[i].lchild=-1;ht[i].rchild=-1;ht[i].weight=0;}for(i=0;in;i++){ht[i].c=s[i].c;ht[i].weight=s[i].weight;}printf(哈夫曼树初态为:\n);printf(dataweightparentlchildrchild\n);for(i=0;i2*n-1;i++){printf(%-6c%-6d%-6d%-6d%-6d\n,ht[i].c,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);}for(i=n;i2*n-1;i++){min1=min2=32767;lnode=rnode=0;for(k=0;k=i-1;k++){if(ht[k].parent==-1){if(ht[k].weightmin1){min2=min1;rnode=lnode;min1=ht[k].weight;lnode=k;}elseif(ht[k].weightmin2){min2=ht[k].weight;第3页共8页rnode=k;}}}ht[lnode].parent=i;ht[rnode].parent=i;ht[i].weight=ht[lnode].weight+ht[rnode].weight;ht[i].lchild=lnode;ht[i].rchild=rnode;}printf(\n哈夫曼树终态为:\n);printf(dataweightparentlchildrchild\n);for(i=0;i2*n-1;i++){printf(%-6c%-6d%-6d%-6d%-6d\n,ht[i].c,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);}printf(\n);}//哈夫曼编码voidCreateCode(HTNodeht[],HCodehcd[],intn){inti,f,c;HCodehc;for(i=0;in;i++){hc.m_start=n-1;c=i;f=ht[i].parent;while(f!=-1){if(ht[f].lchild==c)hc.code[hc.m_start--]='0';elsehc.code[hc.m_start--]='1';c=f;f=ht[f].parent;}hc.m_start++;hcd[i]=hc;}printf(哈夫曼编码:\n);printf(结点信息权值哈夫曼编码\n);for(i=0;in;i++){第4页共8页printf(%c%s%d%s,ht[i].c,,ht[i].weight,);for(intj=hcd[i].m_start;jn;j++)printf(%c,hcd[i].code[j]);printf(\n);}}//译码voidCoding(HTNodeht[],HCodehcd[],intn,charbuf[]){for(inti=0;buf[i]!='\0';i++){for(intj=0;jn;j++){if(buf[i]==ht[j].c){for(intk=hcd[j].m_start;kn;k++){printf(%c,hcd[j].code[k]);}break;}}}printf(\n);}//解码voidDeCode(HTNodeht[],HCodehcd[],intn,charbuf[],intlen){chartemp[10];//用来存放某哈夫曼编码的字符数组intnLen=0;while(nLenlen){for(inti=0;in;i++){memset(temp,0,10);intj=0;for(intk=hcd[i].m_start;kn;k++){temp[j++]=hcd[i].code[k];}intm=n-hcd[i].m_start;intnResult=strncmp(buf,temp,m);if(nResult==0)//匹配成功{printf(%c,ht[i].c);第5页共8页break;}}buf=buf+n-hcd[i].m_start;nLen+=n-hcd[i].m_start;}printf(\n);}voidMenu(){char*str[]={1.创建哈夫曼树并查看初态和终态\n,2.创建并查看哈夫曼编码\n,3.译码\n,4.解码\n,0.退出\n};for(inti=0;i5;i++){printf(%s,str[i]);}printf(请选择0-4);}voidmain(){charbuf[INIT_CAPCITY];printf(请输入一段英文字母:\n);scanf(%s,buf);ChNodes[20];memset(s,0,sizeof(ChNode)*20);intj=0;for(inti=0;buf[i]!='\0';i++){intflag=0;for(intk=0;kj;k++){if(buf[i]==s[k].c)//若buf[i]在s中已经存在,将其权值加1{s[k].weight++;flag=1;break;}}第6页共8页if(!flag)//若s中不存在buf[i],将其添加到s中,并将权值置为1{s[j].c=buf[i];s[j].weight=1;j++;}}HTNodeht[INIT_CAPCITY];memset(ht,0,sizeof(HTNode)*INIT_CAPCITY);HCodehcd[INIT_CAPCITY];intnChoice=-1;while(1){Menu();scanf(%d,&nChoice);if(nChoice==0)break;switch(nChoice){case1:{CreateHT(ht,j,s);}break;case2:{CreateCode(ht,hcd,j);}break;case3:{charstr[INIT_CAPCITY];printf(请输入译文:\n);scanf(%s,str);printf(译码后为:);Coding(ht,hcd,j,str);}break;case4:{charss[INIT_CAPCITY];printf(请输入要解码的0,1序列:\n);scanf(%s,ss);第7页共8页printf(解码后为:);DeCode(ht,hcd,j,ss,strlen(ss));}break;default:break;}printf(按任意键继续...);getch();system(cls);}}五、程序运行情况(采用截图方式给出运行结果)第8页共8页六、小结(包括收获、心得体会、存在的问题及解决问题的方法、建议等)通过这次试验我能熟练掌握及应用了树的结构及非线性特点,递归特点和动态性,进一步巩固了对指针的使用和二叉树的建立方法,能比较熟练的运用建立哈夫曼树及求哈夫曼编码的算法,对以后的学习有很大帮助。本次试验是关于哈夫曼树的,比较有难度,尤其是译码和解码的处理方式。另外,在处理输入方面也稍有难度,在输入字符序列的同时,应该统计出字符的种类以及各个字符的权值,本次试验采用了结构体数组来存储这些内容。在处理解码的时候,开始一直找不到合适的匹配方式,后来想到用strncmp函数,比较n个字符,问题才得以巧妙的解决。总之,本次试验的内容综合性比较强,以后应该重点练习类似的综合性程序。
本文标题:《数据结构》实验三
链接地址:https://www.777doc.com/doc-7331535 .html