山西大学计算机与信息技术学院实验报告姓名学号专业班级课程名称数据结构实验日期成绩指导教师批改日期实验名称哈夫曼编/译码器一、实验目的：为信息收发站写一个哈弗曼编码的编译系统。二、实验内容:1、概要设计（1）抽象数据类型树的定义如下：ADTTree{数据对象D:D是具有相同特性的数据元素的集合。数据关系R:若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则R={H},H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root}≠Φ，则存在D-{root}的一个划分D1，D2，⋯，Dm（m＞1），对任意j≠k（1≤j，k≤m）有Dj∩Dk=Φ,且对任意的i（1≤i≤m），唯一存在数据元素xi∈Di有∈H；（3）对应于D-{root}的划分，H-{，⋯，}有惟一的一个划分H1，H2，⋯，Hm（m＞0），对任意j≠k（1≤j，k≤m）有Hj∩Hk=Φ,且对任意的i（1≤i≤m），Hi是Di上的二元关系（Di，{Hi}）是一棵符合本定义的树，称为根root的子树。基本操作P:InitTree(&T)；操作结果：构造空树T。DestroyTree(&T)；初始条件：树T存在。操作结果：销毁树T。CreateTree(&T，definition)；初始条件：definition给出树T的定义。操作结果：按definition构造树T。ClearTree(&T)；初始条件：树T存在。操作结果：将树T清为空树。TreeEmpty(T)；初始条件：树T存在。操作结果：若T为空树，返回TREE，否则返回FALSE。TreeDepth(T)；初始条件：树T存在。操作结果：返回T的深度。Root(T)；初始条件：树T存在。操作结果：返回T的根。Value(T，cur_e)；初始条件：树T存在，cur_e是T中某个结点。操作结果：返回cur_e的值。Assign(T，cur_e,value)；初始条件：树T存在，cur_e是T中某个结点。操作结果：结点cur_e赋值给value。Parent(T，cur_e)；初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非根结点，则返回它的双亲，否则返回函数值为“空”。LeftChild(T，cur_e)；初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空”。RightSibling(T，cur_e)；初始条件：树T存在，cur_e是T中某个结点。操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则返回函数值为“空”。InsertChild(&T,&p,i,c)；初始条件：树T存在，p指向T中某个结点，1≤i≤p所指结点的度+1，非空树c与T不相交。操作结果：插入c为T中p指结点的第i棵子树。DeleteChild(&T,&p,i)；初始条件：树T存在，p指向T中某个结点，1≤i≤p指结点的度。操作结果：删除c为T中p指结点的第i棵子树。TraverseTree(T,Visit())；初始条件：树T存在，Visit是对结点操作的应用函数。操作结果：按某种次序对T的每个结点调用函数visit（）一次且至多一次。一旦visit（）失败，则操作失败。}ADTTree（2）主程序voidmain（）{初始化；do{接受命令；处理命令；}while（“命令”！=“退出”）；}2、详细设计#include"stdafx.h"#include#include#include#defineMAX100#defineMAXVALUE10000typedefstruct{intweight;intflag;intparent;charch;intlchild;intrchild;}HafNode;typedefstruct{intbit[MAX];intstart;intweight;charch;}Code;typedefstruct{charbit[MAX];charch;intweight;}Coding;voidhaffman(intweight[],charch[],intn,HafNodehaffTree[])//生成哈夫曼树的函数{inti,j,m1,m2,x1,x2;for(i=0;i<2*n-1;i++){if(i
