数据结构课程设计哈夫曼树.doc

课 程 设 计

课程设计名称： 数据结构课程设计
专 业 班 级 ：
学 生 姓 名 ：
学 号 ：
指 导 教 师 ： 李磊
课程设计时间： 2023.7.06—2023.7.10

计算机类 专业课程设计任务书

学生姓名

专业班级

学号

题 目
哈夫曼树编/译码系统
课题性质
A
课题来源
D
指导教师
李磊
同组姓名
无
重要内容
1. 学习掌握并纯熟运用C语言进行程序设计,
2.针对具体应用问题，选择、设计和实现合适的抽象数据类型；
3.进行整体设计使各个函数之间紧密联系起来；
任务规定

1.综合运用和融化所学理论知识，提高分析和解决实际问题的能力，达成培养良好程序设计能力和习惯的目的，为开发满足问题规定的小型应用软件奠定基础，达成软件工程的综合性基础训练的目的。,
2.完毕需求分析报告，报告中对关键部分给出图表说明。
规定格式规范，工作量饱满。
参考文献
《C语言程序设计》（第三版）谭浩强 清华大学出版社
《C Primer Plus》(第5版) Stephen prata 北京人民邮电出版社

审查意见
指导教师签字：
教研室主任签字： 年 月 日

目录
目录 1
1需求分析 2
1.1系统介绍 2
1.2程序的输入和输出 2
1.3程序要达成的功能 2
1.4调试过程介绍 2
2概要设计 3
2.1数据结构设计 3
2.2系统模块设计 3
3具体设计 4
4系统演示 12
4.1主界面 12
4.2数据录入 12
4.3翻译短文 13
4.4反译编码 13
4.5打印文献编码 14
4.6打印哈夫曼树 14
5运营环境 15
6课程心得总结 16
参考文献； 16

1需求分析
1.1系统介绍
运用Huffman编码进行通信可以大大提高信道运用率．缩短信息传输时间，减少传输成本，这规定在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编／译码系统。此程序就是为这样的信息收发站写一个Huffman码的编／译码系统。
1.2程序的输入和输出
从终端读入字符集大小n，以及n个字符及各个字符的权值，建立赫夫曼树，并将它存储到文献hfmTree中；运用已建好的赫夫曼树将文献中的字符编码，假如赫夫曼树不在内存中，则从文献hfmTree中读取到内存；将译得的代码存到文献CodeFile中；运用已建好的赫夫曼树对CodeFile中的代码进行译码，将结果存入文献TextFile中；最后将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文献TreePrint中。
1.3程序要达成的功能
用户可以运用菜单根据自己的需要来选择要进行编码或是译码,并将转换好的字符或编码以文献的形式存到相应的文献里面。
1.4调试过程介绍
（l）运用教材中的数据调试程序。
（2）用下表给出的字符集和频度的实际记录数据建立哈夫曼树，并实现以下报文的编码和译码："THIS PROGRAM IS MY FAVORITE"。
字符

A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
频度
186
64
13
22
32
103
21
15
47
57
1
5
32
20
57
63
15
1
48
51
80
23
8
18
1
16
1

选择2，输入THIS PROGRAM IS MY FAVORITE，屏幕上显示
同时文献codefile里面也出现相应的代码
选择3，从codefile中调入代码，终端显示THIS PROGRAM IS MY FAVORITE，并且文献textfile中也相应的存入了这段话。
选择4，文献CodeFile以紧凑格式显示在终端上。
选择5，将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文献TreePrint中。
选择其他的数字，将出现犯错提醒，并重新回到选择菜单。

2概要设计
2.1数据结构设计
InitHuffman(Huffman Hfm)；//初始化哈夫曼树
Encoding(Huffman Hfm)； //翻译短文
Decoding(Huffman Hfm)； //反译编码
Print1(Huffman Hfm)； //打印文献编码
Print2(Huffman Hfm)； //打印哈夫曼树
typedef char **HuffmanCode;//动态分派数组存储霍夫曼表码表
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;//动态分派数组存储霍夫曼树
typedef struct{
HuffmanTree HT;
char *c;
int length;
HuffmanCode HC;
}Huffman;//分派数组存储字符串及其相应的霍夫曼树
Huffman Hfm;
2.2系统模块设计

哈夫曼树编/译码系统

录入数据

翻译短文

反译编码

打印文献编码

打印哈夫曼树

退出系统

3具体设计
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include<stdlib.h>
#define NULL 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAX_NUM 32767
#define MAX 60
typedef char **HuffmanCode;//动态分派数组存储哈夫曼表码表

typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;//动态分派数组存储哈夫曼树
typedef struct{
HuffmanTree HT;
char *c;
int length;
HuffmanCode HC;
}Huffman;//全局结构体变量，来存储字符与代码
/*------------------------------------------寻找权值最小的两个节点-------------------------------------*/
void Select(HuffmanTree HT,int end,int *s1,int *s2)
{
int i;
int min1=MAX_NUM;
int min2;
for (i=1;i<=end;i++)/*遍历查找权值最小的结点S1*/
{
if (HT[i].parent==0&&HT[i].weight<min1)
{
*s1=i;
min1=HT[i].weight;
}
}
min2=MAX_NUM;
for(i=1;i<=end;i++)/*遍历查找除S1外权值最小的结点S2*/
{
if(HT[i].parent==0&&(*s1!=i)&&min2>HT[i].weight)
{
*s2=i;
min2=HT[i].weight;
}
}
}
/*------------------------------------对哈夫曼树进行编码-------------------------------------*/
Huffman HuffmanCoding(Huffman Hfm)
{
int i,n,m,s1,s2,start;
int c,f;
char *cd;
n=Hfm.length;
if(n<=1) return Hfm;
m=2*n-1;
for(i=n+1;i<=m;++i) /*选择HT[1....i-1]中无双亲且权值最小的两个节点，其序号为s1，s2*/
{
Select(Hfm.HT,i-1,&s1,&s2);
Hfm.HT[s1].parent=i; /*修改父亲位置*/
Hfm.HT[s2].parent=i;
Hfm.HT[i].lchild=s1; /*修改孩子位置*/
Hfm.HT[i].rchild=s2;
Hfm.HT[i].weight=Hfm.HT[s1].weight+Hfm.HT[s2].weight;/*父亲结点权值为左右孩子权值之和*/
}
/*从叶子结点到根逆向求每个字符的哈夫曼编码*/
Hfm.HC=(HuffmanCode)malloc((n+1)*sizeof(char *));/*分派n个字符编码的头指针向量*/
cd=(char *)malloc(n*sizeof(char));/*分派求编码的工作空间*/
cd[n-1]='\0';/*编码结束符*/

for(i=1;i<=n;++i)/*逐个字符求哈夫曼编码*/
{
start=n-1;/*编码结束符位置*/
for(c=i,f=Hfm.HT[i].parent;f!=0;c=f,f=Hfm.HT[f].parent)/*从叶子到根逆向求编码*/
{
if(c==Hfm.HT[f].lchild) cd[--start]='0';
else cd[--start]='1';
}
Hfm.HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(Hfm.HC[i],&cd[start]);/*从cd复制编码到Hfm.HC*/
}
free(cd);
return Hfm;
}
/*------------------------------------录入数据函数-------------------------------------*/
Huffman InputHuffman(Huffman Hfm)
{
int i,n;
printf("\n\n********************录入数据*********************\n");
printf("录入的字符及其权值将保存于:\hfmTree\ \n");
printf("请输入录入字符个数: ");
scanf("%d",&n);
if(n<=1)
{printf("只有一个字符无需编码");
printf("\n");
printf("请输入录入字符个数: ");
scanf("%d",&n);}
Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));
Hfm.c=(char *)malloc((n+1)*sizeof(char));
for(i=1;i<=n;i++)
{
printf("请输入字符:");
scanf("%s",&Hfm.c[i]);
printf("请输入字符权值:");
scanf("%d",&Hfm.HT[i].weight);
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
for(;i<=2*n-1;++i)
{
Hfm.HT[i].weight=0;
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
Hfm.length=n;
return Hfm;
}
/*------------------------------------初始化哈夫曼树-------------------------------------*/
Huffman InitHuffman(Huffman Hfm)
{
int n,i;
char x;
FILE *fp;
fp=fopen("hfmTree","rt");/*对文献hfmTree以读文本的形式打开*/
if(fp==NULL)
{
Hfm=InputHuffman(Hfm);/*调用InputHuffman函数，用户输入字符和相应权值存入哈夫曼数中*/
fp=fopen("hfmTree","wt");
fprintf(fp,"%d\n",Hfm.length);
for(i=1;i<=Hfm.length;i++)
fprintf(fp,"%c %d ",Hfm.c[i],Hfm.HT[i].weight);
rewind(fp);
}
else
{printf("哈夫曼树已经存在!\n你是否需要重新初始化哈夫曼树?('Y'or'N')\n");/*询问是否重新初始化*/
printf("请输入选择:");
scanf("%s",&x);
if(x=='Y')
{ Hfm=InputHuffman(Hfm);/*调用InputHuffman函数，用户输入字符和相应权值存入哈弗曼数中*/
fp=fopen("hfmTree","w+");
fprintf(fp,"%d\n",Hfm.length);
for(i=1;i<=Hfm.length;i++)
fprintf(fp,"%c %d ",Hfm.c[i],Hfm.HT[i].weight);
rewind(fp);
}

else
{fscanf(fp,"%d\n",&n);
Hfm.c=(char *)malloc((n+1)*sizeof(char));
Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));
for(i=1;i<=n;i++)
fscanf(fp,"%s %d ",&Hfm.c[i],&Hfm.HT[i].weight);/*将已经在文献中的字符和其相应的权重输入到Hfm.c[i]和&Hfm.HT[i].weight中*/
for(i=1;i<=n;i++)/*对每个节点初始化*/
{
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
for(;i<=2*n-1;++i)
{
Hfm.HT[i].weight=0;
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
Hfm.length=n;
}
}
fclose(fp);
Hfm=HuffmanCoding(Hfm);
return Hfm;
}
/*------------------------------------翻译短文-------------------------------------*/
void Encoding(Huffman Hfm)/*运用已建好的Huffman树(如不在内存，则从文献hfmTree中读入)对文献ToBeTran中的正文进行编码，然后将结果存入文献CodeFile中。*/
{
int i=0,j=0,n;
char ch[MAX];
FILE *fp,*fw;
n=Hfm.length;
printf("\n\n*******************翻译短文**************************\n\n");
if((fw=fopen("ToBeTran","r+"))==NULL)/*尝试打开ToBeTran*/
{
printf("\n请输入需要翻译成编码的短文: ");
scanf("%s",ch);
printf("\n");
fp=fopen("CodeFile","wt+");
}
else
{
fscanf(fw,"%s",ch);
fclose(fw);
}
while(ch[j])
{
for(i=1;i<=n;i++)
if(ch[j]==Hfm.c[i])
{
printf("%s",Hfm.HC[i]);
fprintf(fp,"%s",Hfm.HC[i]);
break;
}
j++;
}
printf("\n");
rewind(fp);
fclose(fp);
}
/*------------------------------------反译编码-------------------------------------*/
void Decoding(Huffman Hfm)/*运用已建好的Huffman树将文献CodeFile中的代码进行译码，结果存入文献TextFile中。*/
{
HuffmanTree p;
int i,n;
int j=0;
char d[500];
char x;
FILE *fp;
n=Hfm.length;
printf("\n\n******************反译************************\n\n");
if((fp=fopen("CodeFile","r+"))==NULL)
{
printf("Please input the code:");
scanf("%s",d);
}
else
{
printf("文献中已有编码,是否需要更换编码?('Y'or'N')\n");
printf("请输入选择:");
scanf("%s",&x);
if(x=='Y')
{
printf("请输入需要反译的新编码:");
scanf("%s",d);
}
else
{
fscanf(fp,"%s",d);/*将文献中的字符输入到数组d中*/
fclose(fp);
}
}
printf("\n反译后得到的短文为: ");
fp=fopen("TextFile","wt+");/*以写入文献的形式打开TextFile*/
while(d[j])
{
p=&Hfm.HT[2*n-1];
while(p->lchild||p->rchild)
{
if(d[j]=='0')
{ i=p->lchild; p=&Hfm.HT[i]; }
else
{ i=p->rchild; p=&Hfm.HT[i]; }
j++;
}
printf("%c",Hfm.c[i]);
fprintf(fp,"%c",Hfm.c[i]);
}
printf("\n");
fclose(fp);
}

/*------------------------------------打印文献编码-------------------------------------*/
void Print1(Huffman Hfm)
{
int i,n;
int m=1;
char ch;
FILE* fprint;
n=Hfm.length;
printf("\n\n******************打印文献编码****************\n\n");
fprint=fopen("CodeFile","rb");
while ( feof(fprint)==0 )
{
ch=fgetc(fprint);
printf("%c",ch);
m++;
if (m%50==0)
printf("\n");
}
printf("\n");
fclose(fprint);

}
/*------------------------------------打印哈夫曼树-------------------------------------*/
void Print2(Huffman Hfm)
{
int i,n;
n=Hfm.length;
printf("\n\n******************打印哈夫曼树****************\n\n");
for(i=1;i<=n;i++)
{
printf("\n");
printf("Char:%c\t",Hfm.c[i]);
printf("Weight:%d\t",Hfm.HT[i].weight);
printf("parent:%d\t",Hfm.HT[i].parent);
printf("lchild:%d\t",Hfm.HT[i].lchild);
printf("rchild:%d\t",Hfm.HT[i].rchild);
printf("Code:");
puts(Hfm.HC[i]);
}
printf("\n");
}
/*------------------------------------主函数-------------------------------------*/
void main()
{
Huffman Hfm;
char k;
while(1)
{
printf("\n");
printf(" 〒〒〒〒〒欢迎进入哈夫曼编/译码系统:〒〒〒〒〒\n");
printf(" ★★★★★★★welcome★★★★★★★\n");
printf("\t ＊ 【1】录入数据 ＊\n");
printf("\t ＊ 【2】翻译短文 ＊\n");
printf("\t ＊ 【3】反译编码 ＊\n");
printf("\t ＊ 【4】打印文献编码 ＊\n");
printf("\t ＊ 【5】打印哈夫曼树 ＊\n");
printf("\t ＊ 【0】退出系统 ＊\n");
printf("\n");
printf("请输入你的选择:");
scanf("%c",&k);
system("cls");
switch(k)
{ case '1': Hfm=InitHuffman(Hfm); getchar();break;
case '2': Encoding(Hfm); getchar();break;
case '3': Decoding(Hfm); getchar();break;
case '4': Print1(Hfm); getchar();break;
case '5': Print2(Hfm); getchar();break;
case '0': exit(0);
default: printf("无效选项!请重新输入\n"); }
}
}
4系统演示
4.1主界面

4.2数据录入

4.3翻译短文

4.4反译编码

4.5打印文献编码

4.6打印哈夫曼树

5运营环境
1,软件环境：
操作系统:Windows98/XP/Windows7以上版本
2.硬件环境：
1，解决器：Intel 166MX以上
2，内存：32MB
3：硬盘空间：2GB
2，开发工具和编程语言
Vc 6.0；
用C语言编写；

6课程心得总结
我学习数据结构的时间也不短了，其中学习过程中或多或少有些漏掉的知识点没有领悟透彻，通过这次做大程序的机会，得以将过去学习的部分知识点再次连贯起来，有了一次比较综合的再学习，这次的大程序也尚有一些功能由于所学知识的因素未能实现。这次的大程序只是运用了数据结构中的少部分知识，也使我结识到自己也许对其他知识点还没有完全掌握，这将会激励我以后努力学习，争取更上一层楼。

参考文献；
[1] 谭浩强 ，C语言程序设计，第2版.北京：高等教育出版社2023.
[2] Stephen C Prata,Primer Plus,第5版. 北京：人民邮电出版社