数据结构实验报告八—哈夫曼编译码(2)

//简而言之就是遇到0向左，遇到一向右，直到找到叶子

数据结构 实验报告 哈夫曼编/译码

while(p->lchild||p->rchild)

{

if(d[j]=='0')

{

i=p->lchild;

p=&huf.HT[i];

}

else

{ i=p->rchild;

p=&huf.HT[i]; }

j++;

}

printf("%c",huf.c[i]);

//将找到叶子节点的字符写入TextFile.dat

fprintf(code,"%c",huf.c[i]); }

fclose(code);

printf("译码成功，结果保存到文件TextFile.dat中");

}

4、 打印代码文件

//将文件CodeFile每行50个代码显示到终端

//将此字符形式的编码写入CodePrin中

void Print()

{

char ch;

//code是指向CodeFile的指针，codeprin是指向

//CodePrin的指针

FILE *code,*codeprin;

code=fopen("CodeFile.dat","r");

codeprin=fopen("CodePrin.dat","w");

//每行输出50个字符，将编码写进文件CodePrin中

for(int i=1;(ch=fgetc(code))!=EOF;i++)

{

if(i>=50){

printf("\n");

fputc('\n',codeprin);

i=1;

}

putchar(ch);

fputc(ch,codeprin);

}

fclose(codeprin);

fclose(code);

数据结构 实验报告 哈夫曼编/译码

printf("\n已经写入到文件CodePrin.dat中\n");

}

5、 打印哈夫曼树

//输出哈夫曼树节点，权值，双亲，左孩子，右孩子

//前n个结点打出对应的字符

void Treeprinting(Huf huf)

{

int j,n;

FILE *tree;

tree=fopen("TreePrint.dat","w");

n=huf.len;

for (j=1; j<=n; j++){

printf("\n%4d(%c)%5d%8d%8d%8d",j,huf.c[j],huf.HT[j].weight,huf.HT[j].parent,huf.HT[j].lchild, huf.HT[j].rchild);

fprintf(tree,"\n%4d(%c)%5d%8d%8d%8d",j,huf.c[j],huf.HT[j].weight,huf.HT[j].parent,huf.HT[j].lchild, huf.HT[j].rchild);

}

for (int h=n+1; h<=2*n-1; h++){

printf("\n%4d%8d%8d%8d%8d",h,huf.HT[h].weight,huf.HT[h].parent,huf.HT[h].lchild, huf.HT[h].rchild);

fprintf(tree,"\n%4d%8d%8d%8d%8d",h,huf.HT[h].weight,huf.HT[h].parent,huf.HT[h].lchild, huf.HT[h].rchild);

}

fclose(tree);

}

6、 主函数

//通过不接收不同的输入，调用相应的函数

void main()

{Huf huf;

int num;

char input;

while(1){

cout<<"I:初始化"<<endl;

cout<<"E:编码"<<endl;

cout<<"D:译码"<<endl;

cout<<"P:印代码文件"<<endl;

cout<<"T:打印哈夫曼树"<<endl;

数据结构 实验报告 哈夫曼编/译码

cout<<"Q:退出"<<endl<<endl;

cout<<"请输入你的选择：";

cin>>input;

if(input=='I'||input=='i'){

num=1;

}else if(input=='E'||input=='e'){

num=2;

}else if(input=='D'||input=='d'){

num=3;

}else if(input=='P'||input=='p'){

num=4;

}else if(input=='T'||input=='t'){

num=5;

}else if(input=='Q'||'q'){

num=6;

}else{

num=7;

}

switch(num){

case 1:

huf=Initialization();

getch(); break;

case 2:

Encoding(huf);

getch(); break;

case 3:

Decoding(huf);

getch(); break;

case 4:

Print();

getch(); break;

case 5:

Treeprinting(huf);

getch(); break;

case 6:

return;

default:

printf("选择有错，请重新选择\n");

getch(); break;

}}

}

数据结构 实验报告 哈夫曼编/译码

四、调试分析

1. 开始时并未设计Huf这个结构体，但后来发现进行操作的时候很费力，在编写的过程中，就将后面要用到东西都放到这个结构体中了。可以说这个结构体是在编程过中不断完善的。

2. 在调试过程中发现有一些常犯的错误，如字母的拼写、结尾的分号等，在以后的编程过程中要避免这些错误。在写报告的同时还发现一些细节上的错误，如格式化输出的地方。

3. 由于缺乏MFC的知识，只是将哈夫曼树打印出来，没有将哈夫曼树以树的形式画出来。

4. Select算法的时间复杂度为O(n), setHuffmanTree的时间复杂度为O(n*n), setHuffmanCode的时间复杂度为O(n)。

五、测试结果

本实验的测试结果截图如下：

六、用户使用说明（可选）

1 、本程序的运行环境为windows 操作系统，执行文件为111.exe 2 、运行程序时

提示输入数据 并且输入数据然后回车就可以得到输出结果哈夫曼编码

3.此程序还具有译码功能。

数据结构 实验报告 哈夫曼编/译码

七、实验心得（可选）

通过编写哈夫曼编码器算法及程序的调试，清楚的掌握了二叉树这种存储结构在解决一些问题时的应用和优点，但是在对二叉树进行操作时，尤其对树的编历具体用程序实现时还是不能完全掌握。

附录（实验代码）：

#include<iostream.h>

#include<windows.h>

#include<string.h>

#define MAX 99

char cha[MAX],str[MAX];

char hc[MAX-1][MAX];

int s1,s2; //设置全局变量，以便在select(函数)中返回两个变量

typedef struct //huffman树存储结构

{unsigned int weight;//权值字符出现的频率

int lchild,rchild,parent;

}huftree;

void select(huftree tree[],int k) //找寻parent为0,权最小的两个节点

{int i;

for (i=1;i<=k && tree[i].parent!=0 ;i++); s1=i;

for (i=1;i<=k;i++)

if (tree[i].parent==0 && tree[i].weight<tree[s1].weight) s1=i;

for (i=1; i<=k ; i++)

if (tree[i].parent==0 && i!=s1) break; s2=i;

for (i=1;i<=k;i++)

if ( tree[i].parent==0 && i!=s1 && tree[i].weight<tree[s2].weight) s2=i;

}

void huffman(huftree tree[],int *w,int n) //生成huffman树

{ int m,i;

if (n<=1) return;

m=2*n-1;

for (i=1;i<=n;i++)//将各个字符的频率权值作为森林中的每一棵子树

{ tree[i].weight=w[i]; tree[i].parent=0;

tree[i].lchild=0; tree[i].rchild=0; }

for (i=n+1;i<=m;i++)

{ tree[i].weight=0; …… 此处隐藏：3004字，全部文档内容请下载后查看。喜欢就下载吧 ……