数据结构实验报告（三） 题目：树和二叉树的应用 班级：计算机 1002 班 姓名：岳明轩 学号：20102682 一、 实验内容 哈夫曼编码设计 二、 实验目的 掌握树和二叉树的概念及工作原理，运用其原理及概念完成上述实验题中的内容。 三、 实验要求 为了使学生更好的掌握与理解课堂上老师所讲的概念与原理，实验前每个学生要认真 预习所做的实验内容及编写源程序伪码（写在纸上及盘中均可）以便在实验课中完成 老师所布置的实验内容。 四、 设计原理 哈夫曼树的构建： 将所有节点（字符）放入集合 A 中，选出权值最小的两个节点，以其为左右儿子节点 构建新节点，新节点权值为两节点的和，将细节点加入集合 A，将原来两节点从集合 A 中删除，重复上述过程，直到生成根节点。这样所有的叶子节点即为编码，约定左分 支表示“0”，右分支表示“1”，即可得到每个节点的编码。 五、 程序清单 1. structure.h typedef struct { int weight; int parent,lchild,rchild; }HTnode,* HTree; typedef char ** Hcode; 2. function.h #include"structure.h" #include"stdio.h" #include"stdlib.h" #include"string.h" //给节点赋值 void value(HTnode &t,int w,int p,int l,int r) { } t.weight=w; t.parent=p; t.lchild=l; t.rchild=r; //选择权值最小的两个节点，返回其位置 void Select(HTree HT,int k,int &a,int &b) { 

int i; for (i=1;i<=k;i++) { } if(HT[i].parent==0) {a=i;break;} for (i=1;i<=k;i++) { } if((HT[i].parent==0)&&HT[i].weight

cd[n-1]='\0'; for (i=1;i<=n;++i) { //从第一个开始逐个编码 start=n-1; //从结尾开始逐个向前编码 for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) { } if (HT[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; Hc[i]=(char *)malloc((n-start)*sizeof (char)); //为第 i 个编码分配存放字符串的空 间 } strcpy(Hc[i],&cd[start]); //将 cd 中编好的字符串放到 HC 中 } free(cd); //将临时空间释放 3. 主函数 ///////////////////鄙视从网上下载的//////////////////////////// #include"function.h" void main() { HTree HT; Hcode Hc; int i,number=9; char* p; int* q; char Letter[10]="ABCDEFGHI"; int Weigh[10]={1,5,7,2,5,8,4,3,9}; HuffmanCode(HT,Hc,Weigh,number); for (p=Letter,q=Weigh,i=1;i<=number;i++,p++,q++) { } char** m=Hc; printf("%c\t%d\t%s",*p,*q,m[i]); printf("\n"); } 六、 实验结果 

七、 遇到的问题及解决办法 1. 选择最小的两个节点的函数设计：初次设计为考虑 a 与 b 重复的问题，第二次未 考虑判断 parent=0 的问题，第三次发现 a 和 b 应先设定为 parent=0 的节点再进行 大小比较，经过多次使用 DEBUG，观察值的变化，最终完善了 Select 函数。 cd 临时空间分配的长度也是 n，但是是从 0 开始分配的，末尾是 n-1，很容易与 Hc 和 HT 中的 n 混淆。 2. 3. 在复制字符串的时后，start 是应该先减后使用还是先使用后减，并且与之后的分 配空间长度“n-start”相对应，需要理清逻辑，画出字符数组，即可看出。 4. 对于存储 n 个字符串的数组 Hc，char**的意义，指针和二维数组的对应关系，需 要明确理解。（Hc 是二维字符数组，其意义是一个指向存放字符串（一个指向字符 的地址）的地址，Hc[i]表示第 i 个字符串，也是一个一维字符数组，以\0 结尾）。