哈工大数据结构大作业——哈夫曼树生成、编码、遍历(共14页).docx
精选优质文档-倾情为你奉上一、 问题描述1. 用户输入字母及其对应的权值，生成哈夫曼树；2. 通过最优编码的算法实现，生成字母对应的最优0、1编码；3. 先序、中序、后序遍历哈夫曼树，并打印其权值。二、 方法思路1.哈夫曼树算法的实现§存储结构定义#define n 100 /* 叶子树*/#define m 2*(n) 1 /* 结点总数*/typedef struct /* 结点型*/double weight ; /* 权值*/int lchild ; /* 左孩子链*/int rchild ; /* 右孩子链*/int parent; /* 双亲链*/ 优点？HTNODE ;typedef HTNODE HuffmanT m ;/* huffman树的静态三叉链表表示*/ 算法要点1)初始化：将T0，Tm-1共2n-1个结点的三个链域均置空( -1 ),权值为0；2)输入权值：读入n 个叶子的权值存于T的前n 个单元T0，Tn, 它们是n 个独立的根结点上的权值；3)合并：对森林中的二元树进行n-1次合并，所产生的新结点依次存放在Ti(n<=i<=m-1)。每次合并分两步：(1) 在当前森林中的二元树T 0，Ti-1所有结点中选取权值最小和次最小的两个根结点Tp1和Tp2作为合并对象，这里0<= p1，p2<= i 1;(2) 将根为Tp1和Tp2的两株二元树作为左、右子树合并为一株新二元树，新二元树的根结点为Ti。即Tp1.parent =Tp2.parent = i ,Ti.lchild= p1, Ti.rchild=p2， Ti.weight =Tp1.weight + Tp2.weight。 2. 用huffman算法求字符集最优编码的算法：1) 使字符集中的每个字符对应一株只有叶结点的二叉树，叶的权值为对应字符的使用频率；2) 利用huffman算法来构造一株huffman树；3) 对huffman树上的每个结点，左支附以0，右支附以1（或者相反），则从根到叶的路上的0、1序列就是相应字符的编码 Huffman编码实现： 存储结构typedef structchar ch; /存储字符char bitsn+1; /字符编码位串CodeNode;typedef CodeNode HuffmanCoden;HuffmanCode H; 3. 二叉树遍历的递归定义先根顺序遍历二叉树：若二叉树非空则： 访问根结点；先根顺序遍历左子树；先根顺序遍历右子树； 中根顺序遍历二叉树：若二叉树非空则： 中根顺序遍历左子树； 访问根结点； 中根顺序遍历右子树； 后根顺序遍历二叉树： 若二叉树非空则： 后根顺序遍历左子树； 后根顺序遍历右子树； 访问根结点； ；三、主要数据结构及源程序代码及其注释1.扩充二叉树：内结点、外结点（增长树）2. 哈夫曼树3. Huffman编码实现源程序代码及注释#include "stdafx.h"#include <stdio.h>#include <string.h>#include<stdlib.h>#define n 10#define m 2*(n)-1typedef struct/建立哈夫曼结点结构体 char data; float weight; int lchild; int rchild; int parent;htnode;typedef struct/建立哈夫曼编码结构体 char ch; char bitsn+1;htcode;void SelectMin(htnode Tm,int nn,int&p1,int&p2)/选择哈夫曼树所有结点中权值最小的两个根结点 int i,j; for(i=0;i<=nn;i+) if(Ti.parent=-1) p1=i; break; for(j=i+1;j<=nn;j+) if(Tj.parent=-1) p2=j; break; for(i=0;i<=nn;i+) if(Tp1.weight>Ti.weight)&&(Ti.parent=-1) &&(p2!=i) p1=i; for(j=0;j<=nn;j+) if(Tp2.weight>Tj.weight)&&(Tj.parent=-1) &&(p1!=j) p2=j; void CreatHT(htnode Tm)/建立哈夫曼树 int i,p1,p2; for(i=0;i<m;i+) Ti.parent=Ti.lchild=Ti.rchild=-1;/赋初值 for(i=n;i<m;i+) SelectMin(T,i-1,p1,p2); Tp1.parent=Tp2.parent=i; if(Tp1.weight<Tp2.weight) Ti.lchild=p1; Ti.rchild=p2; else Ti.lchild=p2; Ti.rchild=p1; Ti.weight=Tp1.weight+Tp2.weight;void HuffmanEncoding(htnode Tm,htcode Cn)/哈夫曼编码 int c,p,i; char cdn+1; int start; cdn='0'/结束表示 for(i=0;i<n;i+) Ci.ch=Ti.data; start=n; c=i; while(p=Tc.parent)>=0) start=start-1; if(Tp.lchild=c) cdstart='0' else cdstart='1' c=p; strcpy(Ci.bits,&cdstart);void preorder(htnode T,int i)/先序遍历哈夫曼树：递归的办法 printf("%f",Ti.weight);if(Ti.lchild!=-1) preorder(T,Ti.lchild); preorder(T,Ti.rchild); void inorder(htnode T,int i)/中序遍历哈夫曼树 if(Ti.lchild!=-1) inorder(T,Ti.lchild); printf("%f",Ti.weight); inorder(T,Ti.rchild); else printf("%f",Ti.weight);/防止左儿子为空，程序退出void postorder(htnode T,int i)/后序遍历哈夫曼树 if(Ti.lchild!=-1) postorder(T,Ti.lchild); postorder(T,Ti.rchild); printf("%f",Ti.weight); else printf("%f",Ti.weight);/防止左儿子为空，程序退出 void main()int i;int j;j=m-1;htnode Tm;htcode Cn;htnode *b;printf("Input 10 elements and weights:");for (i=0;i<n;i+)/用户输入字母及对应的权值 printf("Input NO.%d element:n",i); scanf(" %c",&Ti.data); printf("Input the weight of NO.%d element:n",i); scanf(" %f",&Ti.weight);CreatHT(T);/建立哈夫曼树HuffmanEncoding(T,C);/建立哈夫曼编码printf("Output Huffman coding:n");for (i=0;i<n;i+)printf("%c:",Ci.ch);printf("%sn",Ci.bits); printf("Output Haffman Tress in preorder way:n");preorder(T,j);/先序遍历哈夫曼树printf("n");printf("Output Haffman Tress in inorder way:n");/中序遍历哈夫曼树inorder(T,j);printf("Output Haffman Tress in postorder way:n");/后序遍历哈夫曼树postorder(T,j); while(1);/运行结果停止在当前画面 四、运行结果#include "stdafx.h"#include <stdio.h>#include <string.h>#include<stdlib.h>#define n 10#define m 2*(n)-1typedef struct/建立哈夫曼结点结构体 char data; float weight; int lchild; int rchild; int parent;htnode;typedef struct/建立哈夫曼编码结构体 char ch; char bitsn+1;htcode;void SelectMin(htnode Tm,int nn,int&p1,int&p2)/选择哈夫曼树所有结点中权值最小的两个根结点 int i,j; for(i=0;i<=nn;i+) if(Ti.parent=-1) p1=i; break; for(j=i+1;j<=nn;j+) if(Tj.parent=-1) p2=j; break; for(i=0;i<=nn;i+) if(Tp1.weight>Ti.weight)&&(Ti.parent=-1) &&(p2!=i) p1=i; for(j=0;j<=nn;j+) if(Tp2.weight>Tj.weight)&&(Tj.parent=-1) &&(p1!=j) p2=j; void CreatHT(htnode Tm)/建立哈夫曼树 int i,p1,p2; for(i=0;i<m;i+) Ti.parent=Ti.lchild=Ti.rchild=-1;/赋初值 for(i=n;i<m;i+) SelectMin(T,i-1,p1,p2); Tp1.parent=Tp2.parent=i; if(Tp1.weight<Tp2.weight) Ti.lchild=p1; Ti.rchild=p2; else Ti.lchild=p2; Ti.rchild=p1; Ti.weight=Tp1.weight+Tp2.weight;void HuffmanEncoding(htnode Tm,htcode Cn)/哈夫曼编码 int c,p,i; char cdn+1; int start; cdn='0'/结束表示 for(i=0;i<n;i+) Ci.ch=Ti.data; start=n; c=i; while(p=Tc.parent)>=0) start=start-1; if(Tp.lchild=c) cdstart='0' else cdstart='1' c=p; strcpy(Ci.bits,&cdstart);void preorder(htnode T,int i)/先序遍历哈夫曼树：递归的办法 printf("%f",Ti.weight);if(Ti.lchild!=-1) preorder(T,Ti.lchild); preorder(T,Ti.rchild); void inorder(htnode T,int i)/中序遍历哈夫曼树 if(Ti.lchild!=-1) inorder(T,Ti.lchild); printf("%f",Ti.weight); inorder(T,Ti.rchild); else printf("%f",Ti.weight);/防止左儿子为空，程序退出void postorder(htnode T,int i)/后序遍历哈夫曼树 if(Ti.lchild!=-1) postorder(T,Ti.lchild); postorder(T,Ti.rchild); printf("%f",Ti.weight); else printf("%f",Ti.weight);/防止左儿子为空，程序退出 void main()int i;int j;j=m-1;htnode Tm;htcode Cn;htnode *b;printf("Input 10 elements and weights:");for (i=0;i<n;i+)/用户输入字母及对应的权值 printf("Input NO.%d element:n",i); scanf(" %c",&Ti.data); printf("Input the weight of NO.%d element:n",i); scanf(" %f",&Ti.weight);CreatHT(T);/建立哈夫曼树HuffmanEncoding(T,C);/建立哈夫曼编码printf("Output Huffman coding:n");for (i=0;i<n;i+)printf("%c:",Ci.ch);printf("%sn",Ci.bits); printf("Output Haffman Tress in preorder way:n");preorder(T,j);/先序遍历哈夫曼树printf("n");printf("Output Haffman Tress in inorder way:n");/中序遍历哈夫曼树inorder(T,j);printf("Output Haffman Tress in postorder way:n");/后序遍历哈夫曼树postorder(T,j); while(1);/运行结果停止在当前画面 专心-专注-专业
