数据结构课内实验报告
哈夫曼树
专业：计算机信息工程学院
班级：物联网 姓名： 25678899
学号： 23458900 指导老师：张红
“哈夫曼树”实验报告
一、实验目的：
（1）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； （2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
（3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力； （4）训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。
二、实验内容：
a.随机生成数据并统计
b.创建哈夫曼树; c.哈夫曼编码 d.哈夫曼译码；
三、概要设计
1、创建哈夫曼树的描述：
数据结构：数据的逻辑结构是树状结构；采用静态的三叉链表存放； 算法思想：1.先把三叉链表中1-N个元素进行初始化，存放叶子节点，他们都没有孩子和双亲。2.再初始化后n-1个非叶子节点元素。3.从当前森林中（在森林中树的根节点的双亲为0）选择两棵根的权值最小的树；删除合并是将选到的两棵树的根权和存入数组当前最前面的空闲元素中，并置入相应的双亲与孩子的位置。4.重复上述步骤直到森林中只含有一棵二叉树为止；
2、哈夫曼树编码的描述：
数据结构：数据的逻辑结构是树状结构；采用静态的三叉链表存放； 算法思想：1.申请存储哈夫曼编码串的头指针数组，申请一个字符型指针，用来存放临时的编码串；2.从叶子节点开始向上倒退，若其为它双亲节点的左孩子则编码标0，否则标1；直到根节点为止，最后把临时存储编码复制到对应的指针数组所指向的内存中；3.重复上述步骤，直到所有的叶子节点都被编码完；
哈夫曼树译码的描述：
数据结构：数据的逻辑结构是树状结构；采用静态的三叉链表存放；
算法思想：1.从根结点开始向下递推，若其编码当前的数值为0，则到该节点的左孩子，否则转到其右孩子；重复上述步骤直到该编码中全部访问完，则树中对应的叶子节点则为所求2.依据上述步骤，对编码数组
中所有编码全部进行译码；
四、模块划分：
1.选择两个权值最小的结点； 2.创建哈夫曼树； 3.打印哈夫曼树 4.哈夫曼编码 5.哈夫曼译码
五、详细设计及运行结果：
1.哈夫曼编码：
六、调试情况，设计技巧及体会
实验中对数据变量的修改有一部分没有太注意，没有传引用，导致实验结果和预期不对，断点调试后才找出问题所在。
通过这次试验，自我感觉收获很深，无论是对于编程本身还是对集成开发环境的使用上，还有对知识掌握的熟练程度上，都有了很大的提高。对于哈夫曼树的算法有了很深的印象。
七、流程图
开始
八、源程序清单 Function.h
生成随机文件生成随机概率生成哈夫曼树哈夫曼编码哈夫曼译码
#include
#define Status int #define OK 1 #define ERROR 0
#define random(x) (rand()%x)
typedef struct{ double weight;
unsigned int parent,lchild,rchild; char ch;
}HTNode, *HuffmanTree;
typedef char **HuffmanCode;
using namespace std;
Status CreatRandomNum() {
srand(time(NULL)); fstream file;
file.open(\ int RNum[10000];
for(int i=0;i<10000;i++) {
RNum[i]=random(10); file< file.close(); puts(\随机数已产生，保存在程序目录下的random.txt\ return OK; } Status GeHuffmanPos(double *n) { ifstream file(\ if(file.fail()) return ERROR; char temp; while(file.get(temp)) { int t; t=(int)temp-48; n[t]+=1; } file.close(); for(int i=0;i<10;i++) { n[i]/=10000; cout<<(n[i])< return OK; } void Select(HuffmanTree HT,int t,int &s1,int &s2) { int i; double m,n; m=n=1; for(i=1;i<=t;i++) { if(HT[i].parent==0&&(HT[i].weight n=HT[i].weight; s2=i; } else { m=HT[i].weight; s1=i; } } if(s1>s2) //s1放较小的序号 { i=s1; s1=s2; s2=i; } } Status HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,double n,Status &Huffcode) { if(w[0]==0) return ERROR; if(n<=1) return ERROR; *w,int puts(\int m=2*n-1; int i; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); puts(\HuffmanTree p; for(p=HT+1,i=1;i<=n;++i,++p,++w) { p->weight=*w; p->lchild=0; p->rchild=0; p->parent=0; } for(;i<=m;++i,++p) { p->weight=0; p->lchild=0; p->rchild=0; p->parent=0; } puts(\int j; for(i=0,j=0;i<10;i++) { HT[j+1].ch=i+'0'; j++; } int s1,s2; for(i=n+1;i<=m;++i) { Select(HT,i-1,s1,s2); HT[s1].parent=i;HT[s2].parent=i; HT[i].lchild=s1;HT[i].rchild =s2; HT[i].weight =HT[s1].weight+HT[s2].weight; } HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); char *cd; cd=(char*)malloc(n*sizeof(char)); cd[n-1]='\\0'; int start,c; unsigned int f; 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)); strcpy(HC[i],&cd[start]); puts(HC[i]); } free(cd); Huffcode=OK; return OK; } Status PrintHuffman(HuffmanCode HC,Status &Huffcode) { if(!Huffcode) return ERROR; for(int i=1;i<=10;i++) { printf(\ } return OK; } Status HuffEncrypt(HuffmanCode HC,Status &Huffcode,Status &Huffcrypt) { if(!Huffcode) return ERROR; ifstream file(\ if(file.fail()) return ERROR; char temp; int i; fstream encryptfile; encryptfile.open(\ while(file.get(temp)) { for(i=0;HC[temp-47][i]!='\\0';i++) { encryptfile<<(HC[temp-47][i]-48); } } puts(\编码结果存放在目录下的encrypt.txt\ file.close(); encryptfile.close(); Huffcrypt=OK; return OK; } Status HuffDecrypt(HuffmanTree HT,Status &Huffcrypt,int n) { if(!Huffcrypt) return ERROR; int m=2*n-1; int mm; //if(!Huffcrypt) return ERROR; ifstream file1(\ char *CodeStr; int k=0; char chch; while(file1.get(chch)) { k++; } file1.close(); CodeStr=new char[k+1]; ifstream file2(\ k=0; while(file2.get(chch)) CodeStr[k++]=chch; file2.close(); ofstream file3(\ CodeStr[k]='\\0'; mm=m; for(int i=0;i<=k;) { if(HT[mm].lchild==0&&HT[mm].rchild==0) { file3.put(HT[mm].ch); mm=m; continue; } else { if(CodeStr[i]=='0') { mm=HT[mm].lchild; } i++; } else { mm=HT[mm].rchild; i++; } } } puts(\编码结果存放在目录下的decrypt.txt\file3.close(); return OK; Main.cpp #include\ void main() { double NumCount[10]={0}; int n=10; int ChooSe; Status Huffcode=ERROR; Status Huffcrypt=ERROR; HuffmanCode HC; HuffmanTree HT; while(true) { puts(\ puts(\哈弗曼编解码实验 \ puts(\生成随机数文件\ puts(\显示随机数概率\ puts(\生成哈夫曼编码树及哈夫曼编码\ puts(\哈夫曼编码\ } } puts(\显示码文\puts(\译码并输出\puts(\退出\cin>>ChooSe; switch(ChooSe) { case 1: if(!CreatRandomNum()) puts(\随机数生成失败\ break; case 2: if(!GeHuffmanPos(NumCount)) puts(\概率生成失败\ break; case 3: if(!HuffmanCoding(HT,HC,NumCount,n,Huffcode)) puts(\哈夫曼树生成失败\ break; case 4: if(!HuffEncrypt(HC,Huffcode,Huffcrypt)) puts(\未生成哈夫曼树及编码\ break; case 5: if(!PrintHuffman(HC,Huffcode)) puts(\未生成哈夫曼树及编码\ break; case 6: HuffDecrypt(HT,Huffcrypt,n); break; case 7: exit(NULL); break; default: puts(\} getchar();