(完整word版)数据结构课设报告+哈夫曼编译器+C语言+源码.doc

(完整word版)数据结构课设报告+哈夫曼编译器+C语言+源码

中南大学

数据结构课程设计报告

题 目 哈夫曼编译器
学生姓名 孙毅
指导教师 杨希
学 院 信息科学与工程学院
专业班级 信息安全1401班

二○一六 年 十一 月

2

目录

一、课程设计目的 3
二、课程设计的内容 3
2.1、问题描述 3
2.2、基本要求 3
三、 问题描述，解决的方法 3
3.1从键盘读入字符集大小n , 以及n个字符和权值，建立哈夫曼树。 3
3.2利用已建好的哈夫曼树对文件正文进行编码，将结果存入相关文件中。 5
3.3利用已建好的哈夫曼树将编码文件中的代码进行译码，结果存入文件中。 6
3.4输出代码文件，以紧凑格式显示。 7
3.5以直观的方式输出哈夫曼树，同时将此字符形式的哈夫曼树写入文件中。 7
四、 程序模块功能，程序设计组成框图、流程图 8
4.1程序模块功能 8
4.2程序设计框图 8
4.3流程图 9
五、 调试与测试。调试方法，测试结果的分析与讨论，遇到的主要问题及采取的解决措施。 10
5.1调试方面 10
5.2测试结果方面 10
六、测试结果，用几组测试数据进行测试算法设计的正确性 10
6.1第一组数据如下 10
6.2第二组测试数据如下： 14
七、 本次课程设计的心得体会 16
八、 附录：源程序清单 17

一、课程设计目的
数据结构是计算机专业的核心课程，是计算机科学的算法理论基础和软件设计的技术基础，实践性强，课程设计是加强学生实践能力的一个重要手段。课程设计要求学生在完成程序设计的同时能够写出规范的设计报告，培养学生分析问题、解决问题，提高学生软件设计能力。

二、课程设计的内容
哈夫曼编译器
2.1、问题描述
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码。对于双向传输信息的信道，每端都需要一个完整的编译码系统。为这样的信息收发站编写哈夫曼编译系统。
2.2、基本要求
(1)从键盘读入字符集大小n , 以及n个字符和权值，建立哈夫曼树。
(2)利用已建好的哈夫曼树对文件正文进行编码，将结果存入相关文件中。
(3)利用已建好的哈夫曼树将编码文件中的代码进行译码，结果存入文件中。
(4)输出代码文件，以紧凑格式显示。
(5)以直观的方式输出哈夫曼树，同时将此字符形式的哈夫曼树写入文件中。

三、 问题描述，解决的方法
3.1从键盘读入字符集大小n , 以及n个字符和权值，建立哈夫曼树。
a.首先设计一个结构体，成员有权值、左右儿子、以及字符本身，再设计一个输入函数，函数中要求输入字符集大小n，以及这n个字符和他们各自对应的权值。

b.再根据以上的各种输入结合建立哈夫曼树的思想原理建立起哈夫曼树，设计的函数包括有两个，一个是选中最小权值的两棵树，另一个是创建哈夫曼树。

3.2利用已建好的哈夫曼树对文件正文进行编码，将结果存入相关文件中。
a.第一步是要求用户输入待编码文件的路径，再根据路径读取待编码文件里的内容，再利用哈夫曼树将内容编码。

b.将编码的结果存入文件中，文件起名为编码结果.txt，这个工作已经在编码路径的同时并完成了。

3.3利用已建好的哈夫曼树将编码文件中的代码进行译码，结果存入文件中。
a.跟（2）是一样的，先是要求用户输入待译码文件的路径，再根据路径读取待译码文件里的内容，再利用哈夫曼树将内容进行译码，只是这里的待译码文件即是前面的编码结果.txt。

b.在将译码结果打印到窗口的同时写进文件里面，文件命名为译码结果.txt

3.4输出代码文件，以紧凑格式显示。
这一步在将编码或者译码结果进行写文件的同时已经将结果打印到了窗口。

3.5以直观的方式输出哈夫曼树，同时将此字符形式的哈夫曼树写入文件中。
挨个将各个节点的内容的值打印到窗口以及写入文件，文件名为哈夫曼树.txt。

四、 程序模块功能，程序设计组成框图、流程图
4.1程序模块功能
本编译器本人给简单的设计为四个模块，分别是：输入字符相关内容并建立哈夫曼树、根据哈夫曼树对文件内容进行编码、根据哈夫曼树对文件内容进行译码以及退出功能。

4.2程序设计框图
开始
从键盘输入字符相关内容并建立哈夫曼树
编码
译码
退出

4.3流程图
显示译码结果并写入文件
输入待编码文件路径
输入待译码文件路径
i==1
i==2
i！=0
开始
输入字符集大小n
输入这n个字符以及权值
输入序号i进行编码与译码及退出的选择
结束

no

yes

no Yes

no

显示编码结果并写入文件
yes

五、 调试与测试。调试方法，测试结果的分析与讨论，遇到的主要问题及采取的解决措施。
5.1调试方面
本次程序用的语言是C，在文件读写方面多多少少有些忘记了，所以本人此次的代码编写部分就大概分为两个阶段来完成的，第一个阶段就是完成建立哈夫曼树、写好编码以及译码函数，和主函数；第二部分呢就是完成读写文件。
在第一阶段完成后，利用键盘输入的方式进行了编码与译码，测试还算顺利，在多次对比之下结果也鉴定为正确。
在第二阶段的读写文件代码编写过程中，读文件的相关操作还算顺利，但就是在写文件上出了不少的岔子，首先第一个问题出在字符串的定义上，开始是俩字符串死活接不上，后来字符串的定义方式改成了这样：。可算是成功的接上了两个字符串，但是后来发现，起始一个文件在打开之后关闭之前，写的内容是不会被覆盖的，只是在再次打开并进行写操作是才会被覆盖掉，所以后来也就没有对两个字符串进行连接，只是依次写入了文件而已。
这只是在进行编码过程中的写文件的一个小坎坷，后来在写译码函数时的写文件时，那是死活都写不进去，尽管是效仿编码时的写法与否，都不行，后来是将文件的打开与关闭放在了函数的外面才可行的，但应该不是直接的原因，具体是怎么样现在也想不起来了，所以现在开始意识到在写代码的过程中写一份记录程序进程文档是很有必要的。

5.2测试结果方面
在测试结果这方面，由于完完全全是一步一步的按照课程设计的要求来写的所以也不存在一些意想不到的错误，出了在写文件上花了些脑筋意外，测试还算顺利。

六、测试结果，用几组测试数据进行测试算法设计的正确性
6.1第一组数据如下
字符集大小n=3；
字符本身以及权值分别为：a,b,c和2,1,3；
待编码文件内容为：aaaaaabbbbbbcccccc。

哈夫曼树.txt的内容为：

选择编码并输入带编码文件的路径：

按回车键进行编码：

查看待编码以及编码结果两个文件的内容进行验证：

选择译码并输入带编码文件的路径：

按回车键进行译码：

查看译码结果文件夹进行验证：

选择3看有什么情况：

选择退出：

6.2第二组测试数据如下：
字符集大小n=6；
自负本身以及权值分别是：a,b,c,d,e,f和9,0,1,3,2,5；
待编码文件内容为：aaabbbcccdddeeefff。

查看哈夫曼树.txt文件：

选择1编码并输入待编码文件的路径：

回车进行编码：

查看待编码和编码结果俩个文件进行验证：

选择2译码并输入待译码文件的路径：

回车进行译码：

查看译码结果文件进行验证：

七、 本次课程设计的心得体会
本次课程设计的心得主要是在文件的相关操作的学习上，之前是没有怎么学文件的相关操作，通过本次的课程设计，本人对C语言的文件的相关操作有了相当的了解，并成功的完成了课程设计所要求的文件的读写功能，可以说是有很大的收获的，不仅仅是在文件操作的这一单方面。
在完成一个课题之前，要仔细理解课题要求。我在此次课程设计中犯的最严重的错误，应该算没有仔细审题。课题的要求是用读取文件的方式输入需要编码字符，译码所需的编码代号也要用文本方式输入。我在拿到这个课题的时候，因为没有仔细理解这些要求，就采用了键盘输入字符进行编码和译码的方式，
以致走了不少弯路。
另外，这次课程设计充分暴露了我的惰性思想。在拿到这个课题后，因为对
哈夫曼编码这个知识点理解比较到位，所以没花多少时间就完成了课题要求实现
的功能。然而，在此之后，我由于自我感觉良好和惰性，没有积极地去寻找改进
程序的方法，也没对程序运行的界面进行美化，使其拥有良好的用户使用体验。
最终在答辩的时候，交给老师的是一个界面简陋的程序。 
通过这次课程设计，我更加深入了理解了哈夫曼编码的过程，以及利用哈夫曼编码对数据进行压缩的优越性，并且使我能够更熟练地运用树形的数据结构。并且体会到了在学习中，要严格要求自己，不能因为一点点的成功就骄傲自满，停止不前。

八、 附录：源程序清单
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXLEN 100
typedef struct {
int weight;
int lchild;
int rchild;
int parent;
char key;
}htnode;

typedef htnode hfmt[MAXLEN];
int n;
void inithfmt(hfmt t)//对结构体进行初始化
{
int i;
printf("\n");
printf("---------------------------------------------------------------------------\n");
printf("******************************输入区***************************************\n");
printf("\n请输入字符集大小n=");
scanf("%d",&n);
getchar();
for(i=0;i<2*n-1;i++)//对结构体进行初始化
{
t[i].weight=0;
t[i].lchild=-1;
t[i].rchild=-1;
t[i].parent=-1;
}
printf("\n");
}

void inputweight(hfmt t)//输入函数
{
int w;//w表示权值
int i;
char k;//k表示获取的字符
for(i=0;i<n;i++)
{
printf("请输入第%d个字符:",i+1);
scanf("%c",&k);
getchar();
t[i].key=k;
printf("请输入第%d个字符的权值:",i+1);
scanf("%d",&w);
getchar();
t[i].weight=w;
printf("\n");
}
}

void selectmin(hfmt t,int i,int *p1,int *p2)//选中两个权值最小的函数
{
long min1=999999;
long min2=999999;
int j;
for(j=0;j<=i;j++)//选择最小权值字符的下标返回
if(t[j].parent==-1)
if(min1>t[j].weight)
{
min1=t[j].weight;
*p1=j;
}
for(j=0;j<=i;j++)//选择次小权值字符的下标还回
if(t[j].parent==-1)
if(min2>t[j].weight && j!=(*p1))//注意 j!=(*p1))
{
min2=t[j].weight;
*p2=j;
}
}

void creathfmt(hfmt t)//创建哈夫曼树的函数
{
int i,p1,p2;
inithfmt(t);
inputweight(t);
for(i=n;i<2*n-1;i++)
{
selectmin(t,i-1,&p1,&p2);
t[p1].parent=i;
t[p2].parent=i;
t[i].lchild=p1;
t[i].rchild=p2;
t[i].weight=t[p1].weight+t[p2].weight;
}
}

void printhfmt(hfmt t)//打印哈夫曼树
{
FILE *f1;
char str[10000];
char *s;
int i;
if((f1=fopen("哈夫曼树.txt","w"))!=NULL)
{
printf("------------------------------------------------------------------\n");
s = "------------------------------------------------------------------\n";
fprintf(f1,"%s",s);
printf("**********************哈夫曼树关系结构****************************\n");
s = "**********************哈夫曼树关系结构****************************\n";
fprintf(f1,"%s",s);
printf("\t\t权重\t父母\t左孩子\t右孩子\t字符\t");
s = "\t\t权重\t父母\t左孩子\t右孩子\t字符\t";
fprintf(f1,"%s",s);
for(i=0;i<2*n-1;i++)
{
printf("\n");
printf("\t\t%d\t%d\t%d\t%d\t%c",t[i].weight,t[i].parent,t[i].lchild,t[i].rchild,t[i].key);
fprintf(f1,"\n\t\t%d\t%d\t%d\t%d\t%c",t[i].weight,t[i].parent,t[i].lchild,t[i].rchild,t[i].key);
}
printf("\n------------------------------------------------------------------\n");
s = "\n------------------------------------------------------------------\n";
fprintf(f1,"%s",s);
fclose(f1);
printf("已将哈夫曼树存入文件，文件名为：哈夫曼树\n\n");
}
}

char ch;
FILE *f2;

void hfmtpath(hfmt t,int i,int j)//编码的重要哈夫曼树路径递归算法
{
int a,b;
a=i;
b=j=t[i].parent;
if(t[j].parent!=-1)
{
i=j;
hfmtpath(t,i,j);
}
if(t[b].lchild==a)
{
printf("0");
fputc('0',f2);
}
else
{
printf("1");
fputc('1',f2);
}
}

void phfmnode(hfmt t)//对字符进行初始编码
{
int i,j,a;
printf("\n------------------------------------------------------------------\n");
printf("**************************哈夫曼编码******************************");
printf("\n\t\t字符\t权值\t编码结果");
for(i=0;i<n;i++)
{
j=0;
printf("\n");
printf("\t\t%c\t%d\t",t[i].key,t[i].weight);
hfmtpath(t,i,j);
}
printf("\n------------------------------------------------------------------\n");
}

void encoding(hfmt t)//对用户输入的文件的内容进行编码
{
FILE *f3;
char r[1000],h[1000];//用来存储输入的字符串
int i,j;
printf("\n\n请输入需要编码的文件路径:");
gets(h);
f3=fopen(h,"r");
fgets(r,1000,f3);
printf("\n待编码文件正文内容为:%s\n",r);
printf("编码结果为:");
for(j=0;r[j]!='\0';j++)
for(i=0;i<n;i++)
if(r[j]==t[i].key)
hfmtpath(t,i,j);
fclose(f3);
printf("\n\n已将编码结果存入文件，文件名为：编码结果\n\n");
}

FILE *f5;

void decoding(hfmt t)//对用户输入的密文进行译码
{
FILE *f4;
char r[1000],h[1000];
int i,j,len;
j=2*n-2;//j初始从树的根节点开始
printf("\n\n请输入需要译码的文件路径:");
gets(h);
f4=fopen(h,"r");
fgets(r,1000,f4);
len=strlen(r);
printf("\n待译码文件中的代码为:%s\n",r);
printf("译码的结果是:");
//f5=fopen("译码结果.txt","w");
for(i=0;i<len;i++)
{
if(r[i]=='0')
{
j=t[j].lchild;
if(t[j].lchild==-1)
{
printf("%c",t[j].key);
fputc(t[j].key,f5);
j=2*n-2;
}
}
else if(r[i]=='1')
{
j=t[j].rchild;
if(t[j].rchild==-1)
{
printf("%c",t[j].key);
fputc(t[j].key,f5);
j=2*n-2;
}
}
}
fclose(f4);
//fclose(f5);
printf("\n\n已将译码结果存入文件，文件名为：译码结果\n\n");
}

int main()
{
int i,j;
hfmt ht;
char flag;
printf(" |----------------------|\n");
printf(" | 信安1401--孙毅--CSU |\n");
printf(" |**********************|\n");
printf(" | 哈夫曼编码课程设计 |\n");
printf(" |**********************|\n");
printf(" | 完成时间:2016/10/26 |\n");
printf(" |----------------------|\n");
creathfmt(ht);
printhfmt(ht);
phfmnode(ht);
printf("\n---------------------------------------------------------------------\n");
printf("***************************编码&&译码&&退出&&保存***********************");
printf("\n【1】编码\t【2】译码\t【0】退出");
printf("\n您的选择是：");
flag=getchar();
getchar();
while(flag!='0')
{
if(flag=='1')
{
f2=fopen("编码结果.txt","wt");
encoding(ht);
fclose(f2);
}
else if(flag=='2')
{
f5=fopen("译码结果.txt","wt");
decoding(ht);
fclose(f5);
}
else
printf("您的输入有误，请重新输入。\n");
printf("\n***************************编码&&译码&&退出**********************");
printf("\n【1】编码\t【2】译码\t【0】退出");
printf("\n您的选择是：");
flag=getchar();
getchar();
}
printf("\n\n-----------------------------------------------------------------\n");
printf("***************欢迎使用孙毅的哈夫曼编译系统********************\n");
printf("-----------------------------------------------------------------\n");
system("pause");
}
39