《哈弗曼数据结构专题实验报告》.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;