129
struct stacknode{
int NodeLevel; //结点的层次
int NodeElem; //结点的序号
};
采用顺序栈存储结构。 算法描述如图 7-6 所示。 接口参数：(无) 读哈夫曼树数据文件数据 初始化栈:top=0 结点指针指向哈夫曼树根结点：node=m-1 结点层次初始化：level=1 输出凹进的空格 输出结点层次、权值和字符 while(node!=-1) 右孩非空 stack[top].NodeElem=ht[ node].rchild stack[top].NodeLevel=lev el+1 while((node!=-1)||(top! =0)) top++ 指针移向左孩：node=ht[node].lchild Level++ node!==-1 栈不空 top-- node=stack[top].NodeElem level=stack[top].NodeLevel 释放内存空间
图 7-6 显示哈夫曼树算法描述示意图
4、选择具有最小权值的两个根结点的函数 Select 算法描述
原理：根结点的条件是指向父结点的指针为空。
130
选择第一个具有最小权值的跟结点时，首先要找到第一个根结点，即父结点指针为 空的结点，再以此为基础找具有最小权值的根结点。
选择第二个具有最小权值的根结点时，首先要找到第一个根结点，即父结点指针为空， 而且不是第一个被选择的的结点，在以此为基础找具有最小权值的根结点时，同样要注 意，满足条件的结点既是根结点，又不是第一个已选结点。 算法描述如下图 7-7 所示。
接口参数：struct node ht[],int n, int *s1,int *s2 *s1=0 while(*s1<=n&&ht[*s1].parent!=-1) ++(*s1) i=(*s1)+1 ht[i].parent==-1&&ht[i].weight ++(*s2) j=(*s2)+1 while(i<=n) j!=*s1&&ht[j].parent==-1&&ht[j].weight 七、思考题 1、若字符的编码不用“0”和“1”的字符表示，而采用 0 和 1 的字节二进制位表示，该 如何实现？ 2、凹式形式显示哈夫曼树的算法若采用先序遍历的递归算法，该如何实现？ 131 八、部分函数代码 #include /*----------哈夫曼树结点结构-------------*/ struct node { char ch; int weight; int parent; int lchild,rchild; } *ht; //指向哈夫曼树的存储空间的指针变量 /*----------字符编码结点结构-------------*/ struct HuffmanCoding { char ch; char coding[NODENUM]; }; /*--------哈夫曼树遍历时栈的结点结构------*/ struct stacknode{ int NodeLevel; int NodeElem; }; /*---------------常量文件名---------------*/ const char *TableFileName = \ //哈夫曼树数据文件 const char *CodeFileName = \ //字符编码数据文件 const char *SourceFileName = \ //需编码的字符串文件 const char *EnCodeFileName = \编码数据文件 const char *DecodeFileName = \译码字符文件 /************************************************************/ /* 释放哈夫曼树数据空间函数 */ /************************************************************/ void free_ht() { if(ht != NULL) { free(ht); ht = NULL; } 132 } /************************************************************/ /* 从文件读取哈夫曼树数据函数 */ /************************************************************/ int ReadFromFile() { int i; int m; FILE *fp; if((fp=fopen(TableFileName,\ { printf(\ getch(); return 0; } fread(&m,sizeof(int),1,fp); //m 为数据个数 free_ht(); ht=(struct node *)malloc(m*sizeof(struct node)); fread(ht,sizeof(struct node),m,fp); fclose(fp); return m; } /************************************************************/ /* 吃掉无效的垃圾字符函数函数 /* 从键盘读字符数据时使用，避免读到无效字符 /************************************************************/ void EatCharsUntilNewLine() { while(getchar()!='\\n') continue; } /************************************************************/ /* 选择权值最小的两个根结点函数 */ /************************************************************/ void Select(struct node ht[],int n, int *s1,int *s2) { int i,j; 选择权值最小的两个根结点的代码 （由学生独立完成） } /************************************************************/ /* 创建哈夫曼树和产生字符编码的函数 */ /************************************************************/ */ */ 133 void Initialization() { int i=0,n,m,j,f,s1,s2,start; char cd[NODENUM]; struct HuffmanCoding code[NODENUM]; FILE *fp; printf(\输入字符总数 n:\ scanf(\ EatCharsUntilNewLine(); m=2*n-1; ht=(struct node *)malloc(m*sizeof(struct node)); //申请哈夫曼树的存储空间 /********************************************************/ /* 创建哈夫曼树 */ /* 1、输入字符和权值 */ /* 2、初始化哈夫曼树 */ /* 3、建立哈夫曼树 */ /********************************************************/ 创建哈夫曼树的代码 （由学生独立完成） //把哈夫曼树的数据存储到文件中 if((fp=fopen(TableFileName,\ {printf(\open%s\\n\ getch(); return; } fwrite(&m,sizeof(int),1,fp); fwrite(ht,sizeof(struct node),m,fp); fclose(fp); /*********************************************************/ /* 产生字符编码 */ /* 从页结点开始，沿父结点上升，直到根结点 ，若沿 /* 父结点的左分支上升，则得编码字符“0”， 若沿父结 /* 点的右分支上升，则得编码字符“1” */ /*********************************************************/ 产生字符编码的代码 （由学生独立完成） */ */