专业基础实践报告题目哈夫曼树及应用起讫日期2008年6月30日至2008年7月11日所在院系软件学院学生姓名专业计算机班级学号指导教师职称所在单位软件学院2008年7 月11 日目录一、任务及要求 (1)二、总体设计 (3)三、运行效果 (16)四、总结 (22)五、附录 (23)参考文献1.唐策善•《数据结构---用C语言描述》•高等教育出版社•1995 •p50~p1202.谭浩强•《C程序设计》•清华大学出版社• 2005 • p330！p348一、任务及要求在本专业基础实践中，综合C语言程序设计、离散数学、数据结构等学过的专业基础课程中的基本概念、基础知识和基本理论，进行软件设计的思想、方法和过程的训练，提高综合素质和动手能力，达到加强专业基础知识理解程度和熟练程度的目的。
具体任务及要求如下：1、任务（1）给定一个包含10个以上字符的字符串，长度不少于100个字符，统计各个字符的概率，存放在数组中。
（2）根据上面统计的结果建立哈夫曼树。
（3）实现哈夫曼编码。
（4）实现哈夫曼译码。
（5）自己选做1～2个附加的任务。
2、要求（1）算法中处理的数据要存放在文件中，实现文件的读写操作。
（2）设计程序中的各个C函数、画出模块图。
（3）程序的代码要规范、有详细的注释。
（4）按照指导教师给出的模板进行专业基础实践报告书写。
二、工作量在2周（10个工作日）时间里，完成15-20个C函数，150-200行代码。
并提交专业实践报告一份，字数不少于5000字（包括英文字符）。
三、计划安排第1个工作日－第2个工作日：查找相关资料、书籍；确定逻辑结构并进行运算的定义；选择存储结构并进行算法设计。
第3个工作日－第7个工作日：完成程序的编码，并且自己调试、测试。
穿插进行实践报告的撰写。
第8个工作日－第9个工作日：整理并完成专业基础实践报告，提交指导教师。
第10个工作日：由教师检查软件测试效果、审阅实践报告，评定成绩。
指导教师签字：2008年6月26日一．总体设计1．功能模块设计本C语言程序共包括12个C函数，函数名及其功能如表1所示2．函数之间的调用关系函数之间调用的功能模块图如图1所示。
二、详细设计1．数据的逻辑结构本程序主要讨论哈夫曼树的逻辑结构，而简化之即时讨论一般二叉树的逻辑结构。
假设有A ，B ，C，D，E，F，G ，H ,I节点，树形结构如下：设B=(K,R),r∈R。
K={A,B,C,D,E,F,G,H,I}r={(A,B),(A,C),(B,D),(D,G),(D,H),(E,E),(C,F),(F,I)}2.数据的存储结构同样主要讨论哈夫曼树的存储结构：哈夫曼树采用链型性结构。
定义：detypef constrct{float weight;int lchild,rchild,parent;}hufmantree;hufmantree tree[m]；由定义知，tree[]可看做是链型存储的结构体数组，weight是其权值，lchild为另一节点即左孩子的序号，同理rchild为另一节点即右孩子的序号，而parent为该节点的父节点的序号。
树形存储结构如下：A上图中，A节点为跟点，无父节点p=0，D和H和I无左右孩子节点i=0，r=0其中节点的权weight（w)为其子女的的和，也是结构体数组的序号。
3.数据的运算（1）HUFMAN函数的IPO图如下：OPENFILE(): 输入：以存在在文件名处理：存入数组，调用输出：无CREATFILE(): 输入：新文件名处理：存入数组，准备调用输出：无READ()：输入：无处理：调用文件名数组，打开，读取，统计总数输出：总数iEACHREAD()：输入：无处理：存入文件名数组，依次读取，分别统计每个字符数目输出：无PRABABL Y()：输入：无处理：每个字符数目除以总数，得到概率，存入树组输出：无HUAMANTREE()输入：无处理：以概率为权建立哈夫曼树tree[]输出：无HUFMANCODE():输入：无处理：调用tree[],对每个字符进行初始化编码输出：无CHCODE()：输入：无处理：调用原始字符树组和code[]，把所有字符存入与其相对应的code[i].ch输出：无OUTPUTCODES():输入：无处理：依次输出code[i].ch=code[i].bits输出：所有字符及对应的编码DECODES(): 输入：二进制编码处理：调用tree[]得到与code[].ch输出：字符TANSFER(): 输入：26个字母和5个常用符号中的任意串处理：与code[].ch比较，得到code[i].bits输出：二进制编码MAIN()：输入：无处理：调用子程序输出：无（2(3) C函数模块及注释①全局定义，本程序一共涉及到31个字符，即26个英文字母和六个常用符号#define n 31 /*涉及到的字符种类个数*/#define m 2*n-1 /*哈夫曼树结点个数*/#define maxval 65536.00typedef int datatype;typedef struct{float weight; /*权*/int lchild,rchild,parent;}hufmantree; /*定义哈夫曼树结点类型*/typedef struct{char bits[n]; /*位串*/int start; /*编码在位串中的开始位置*/char ch;}codetype; /*定义编码类型*/②把已存在的字符文件名保存在filename中以备调用void OPENFILEFILE(char filename[]) /*输入要读取的已存在的文件名*/ {FILE * fp;printf("the name of file you open:\n");scanf("%s",filename);return;}③新建文件并输入字符保存，把文件名存入filename以备调用void CREATFILE(char filename[]) /*新建文件并存入数据*/{FILE * fp; /*定义文件指针*/char ch;printf("the name of file you creat:\n");scanf("%s",filename); /*输入新建文件名*/printf("the file's name is %s\n\n",filename);printf("input your words to the file:\n");if((fp=fopen(filename,"w"))==NULL) /*以写入方式新建并打开文件*/ {printf("cannot open the file\n");exit(0); /*空则退出*/}ch=getchar(); /*读取回车*/ch=getchar();while(ch!='#'){fputc(ch,fp);ch=getchar(); /*向文件写入字符以#结束*/}putchar(10); /*换行*/printf("successful!!\n\n");fclose(fp); /*关闭文件*/return;}④打开文件并依次读取，统计所有字符的总数i，其实i比实际数目大1 float READ(char filename[]) /*统计文件字符总数i*/{FILE *fp;char ch;float i=0;if((fp=fopen(filename,"r"))==NULL) /*读取方式打开文件*/{printf("cannot open the file\n");exit(0); /*文件为空则退出*/}while(!feof(fp)){ch=fgetc(fp); /*读取字符数i直到读取完毕*/i++;}fclose(fp);return(i);}⑤打开文件，依次读取，并分别统计初始化的31个字符中每个在文件中出现的次数，对应地存入数组No[n]中void EACHREAD(char filename[],char word[],float No[]) /*分别读取文件中每个字符总数*/{FILE *fp;char ch;int i;if((fp=fopen(filename,"r"))==NULL){printf("cannot open the file\n");exit(0);}while(!feof(fp)){ch=fgetc(fp); /*依次读取每个字符*/for(i=0;i<=30;i++){if(word[i]==ch)No[i]=No[i]+1;} /*与word字符数组中字符分别比较，把数目存入对应的No数组*/}printf("the No of each word is:\n");for(i=0;i<=31;i++){printf("%c=%.0f ",word[i],No[i]); /*分别输出字符数*/if(i%5==0&&i!=0)printf("\n");}fclose(fp);return;}⑥计算每个字符咋爱文件中出现的概率，存入数组，即gailv[i]=No[i]/totalvoid PROBABL Y(float No[],float gailv[],float total) /*统计每个字符概率*/{int i;printf("\n\n");printf("the probably of each No is:\n");for(i=0;i<n;i++){gailv[i]=No[i]/total; /*每个字符数除以总数得概率存入数组gailv*/printf("%f ",gailv[i]);if(i%5==0&&i!=0)printf("\n");}printf("\n");return;}⑦通过概率数组gailv[n]，以概率大小为权建立哈夫曼树，并把树保存在结构体数组TREE[2n-1]中。
HUFMANTREE(hufmantree tree[],float gailv[]) /*以概率为权建立哈夫曼树*/{int i,j,k,p1,p2;float small1,small2,f;for(i=0;i<m;i++) /*初始化*/{tree[i].parent=0;tree[i].lchild=0;tree[i].rchild=0;tree[i].weight=0.0;}for(i=0;i<n;i++) /*读入前n个接点的权*/tree[i].weight=gailv[i];}for(i=n;i<m;i++) /*进行n-1次合并，产生n-1个新节点*/{p1=0; p2=0;small1=maxval; small2=maxval;for(j=0;j<=i-1;j++) /*选出两个权最小的节点*/if(tree[j].parent==0)if(tree[j].weight<small1){small2=small1; /*改变最小权，次小权及相应的位置*/small1=tree[j].weight;p2=p1;p1=j;}elseif(tree[j].weight<small2){small2=tree[j].weight; /*改变次小全及位置*/p2=j;}tree[p1].parent=i+1;tree[p2].parent=i+1;tree[i].lchild=p1+1;tree[i].rchild=p2+1; /*次小权跟接点是新接点的右孩子*/tree[i].weight=tree[p1].weight+tree[p2].weight;}printf("the quan of each word is:\n");for(i=0;i<m;i++)printf("%f ",tree[i].weight);}⑧通过建立的哈夫曼树对每个概率（对应字符）进行二进制编码，并保存在结构体数组code[n].bits中。