哈弗曼数据结构专题实验报告讲述.doc

数据结构与程序设计专题 实验报告 姓名： 学号： 班级：信息45班 姓名： 学号： 班级：信息45班 姓名： 学号： 班级：信息45班 实验指导老师：李峰 实验地点： 西一楼一层计算机中心机房 实验结束日期：12月5日 联系电话： 实验任务： 对于给定的源文档 SourceDoc.txt， 1) 统计其中所有字符的频度（某字符的频度等于其出现的总次数除以总字符数），字符包括字母（区分大小写）、标点符号及格式控制符（空格、回车等）。 2) 按频度统计结果构建哈夫曼编码表。 3) 基于哈夫曼编码表进行编码，生成对应的二进制码流，并输出到文件 Encode.dat，完成信源的编码过程。 4) 根据生成的哈夫曼编码表，对二进制码流文件 Encode.dat 进行解码，把结果输出到文件 TargetDoc.txt，完成信源的解码过程。 5) 判断 TargetDoc.txt 与 SourceDoc.txt 内容是否一致，以 验证编解码系统的正确性。 实验内容: 1) 线性链表的构建以及排序; 2) 哈夫曼树的构建; 3) 基于哈夫曼码进行编码; 4) 对二进制码进行解码; 5） 程序运行结果： 源程序代码： #includestdio.h #includestdlib.h #includemath.h #include string.h typedef struct aa {char data; double rate; int count; struct aa *next; struct aa *pre; char haffmancode[120]; }NODE; NODE *creat(char b[]) { NODE *h, *p, *s,*death; int i; h=(NODE*)malloc(sizeof(NODE));p=(NODE*)malloc(sizeof(NODE)); h-next=p;h-pre=NULL; p-pre=h;p-next=NULL; p-data=b[0]; p-count=1.0; for(i=1;b[i]!=\0;i++) {s=(NODE*)malloc(sizeof(NODE)); s-data=b[i]; s-count=1.0; s-next=NULL; s-pre=p; p-next=s; p=s; } return h; } void fun(NODE* h,int amount) { NODE *p,*q,*death; for(p=h-next;p;p=p-next){ for(q=p-next;q;){ if(q-data==p-data){ (p-count)++; if (q-next == NULL){ q-pre-next = NULL; free(q); break; } else{ q-pre-next=q-next; q-next-pre=q-pre; death=q; q=q-next; free(death); } } else q=q-next; } (p-rate)=1.0*(p-count)/amount; //printf(%c:\t%d\t%f\n,p-data,p-count,p-rate); }puts(构建链表完成\n); } void outlink(NODE* h,int *n) { //printf(%d,amount); NODE* p=(NODE*)malloc(sizeof(NODE)); NODE* s=(NODE*)malloc(sizeof(NODE)); int i; char ch; double r; for(p=h-next;p;p=p-next) { for(s=p-next;s;s=s-next) { if(s-count p-count) { i=p-count; p-count=s-count; s-count=i; ch=p-data; p-data=s-data; s-data=ch; r=p-rate; p-rate=s-rate; s-rate=r; } }