哈夫曼编码译码器.docx
《哈夫曼编码译码器.docx》由会员分享，可在线阅读，更多相关《哈夫曼编码译码器.docx（45页珍藏版）》请在冰点文库上搜索。
哈夫曼编码译码器
西安郵電學院
数据结构课程设计报告
题目1：
哈夫曼编码/译码器
题目2：
学生信息管理系统
系部名称
：
通信工程系
专业名称
：
通信工程
班级
：
****
学号
：
*****
学生姓名
：
****
指导教师
：
*****
时间
：
2009年12月16日至2009年12月25日
题目1.哈夫曼编码/译码器
一、课程设计目的
通过对哈夫曼编码/译码器的实现，熟悉了解Huffman树的创建过程以及存储结构，对Huffman编码/译码过程及原则有了更深层次的认识，锻炼了动手能力，使知识更好的学以致用，为解决数据压缩问题提供方法。
二、课程设计内容
通过统计文件中各字符的出现频率，建立Huffman树，再通过建立的已经Huffman的树，对文件中各字符进行编码，将结果存入新的文件中，然后从文件中读取Huffman编码，进行解码，结果存入新的文件中，并与源文件进行比较。
三、需求分析
1．统计字符频率：
存文件中读入字符，并对各字符出现频率进行统计；
2．建立Huffman树：
将各字符出现的频率作为权值，建立Huffman树；
3．Huffman编码：
通过已经建立的Huffman树，对个各字符进行编码，并存入新的文件中；
4.译码：
读取存放Huffman编码的文件，对文件中编码进行译码，把译码结果存入新的文件中；
5.结果验证：
将译码结果与原文件内容进行比较；
四、概要设计
1.系统结构图（功能模块图）
2．功能模块说明
1：
统计字符频率：
定义结构体
typedefstructstr
{
chardata;
charnum;
}str;
其中data域存放字符名称，num域存放字符出现频率，读取文件ywq1.txt，通过循环比较将结果赋入S2[128]中；
2：
创建Huffman树:
定义结构体
typedefstruct
{
chardata;
intweight;
intparent;
intlchild;
intrchild;
}HTNode,HuffmanTree[M+1];
作为Huffman树存储节点类型，调用CrtHuffmanTree（）函数，初始化各节点均为0；然后将存储字符频率的数组S2的值赋值给各节点，字符出现频率作为权值，创建Huffman树；
3：
对文件编码：
定义结构体
typedefstruct
{
chardata;
charbits[N+1];
}CodeNode,HuffmanCode[N];
作为HuffmanCode的存储类型，调用CrtHuffmanCode（）函数，从叶子节点向上回溯，是lchild则赋值‘0’，是rchild则赋值为‘1’，对各字符编码，再调用WriteToFile（）函数，将结果写入文件ywq2.txt中；
4：
对文件译码:
读取编码文件ywq2.txt中数据，调用DecodHuffmanCode（）函数，从根节点开始，读取‘1’，走向rchild，读取‘0’,走向lchild,直到叶子节点，将叶子节点data域的值写入文件ywq3.txt中；
五、详细设计及运行结果
1．读文件统计字符频率（read（）函数中实现）：
源文件ywq1.txt：
运行结果：
2：
创建Huffman树，CrtHuffmanTree（）:
运行结果：
3：
Huffman编码，CrtHuffmanCode（）;
运行结果：
编码文件ywq2.txt：
3：
译码，DecodHuffmanCode（）:
运行结果：
文件ywq3.txt:
4:
结果验证：
比较源文件ywq1.txt与译码文件ywq3.txt可知，译码结果与源文件一致。
运行结果：
六、调试情况，设计技巧及体会
通过本次数据结构---哈夫曼编码的应用------课程设计为期两周的实习，让我对数据结构这门课有了深刻的体会，数据结构是在C语言的基础上建立起来的，它是一个程序的必要条件之一，通过本次实习，也让我真正领略到数据结构在一个程序中占有多么重要的地位，程序=算法+数据结构。
不同的程序运用不同的数据结构可以起到事半功倍的作用。
在这次实习，我就已经深深体会到数据结构的精彩运用。
这次实习的题目是哈夫曼编码的应用，在给定的源文件情况下，要根椐所学的哈夫曼树来建立各字符对应的编码从而达到使字符编码化的目的，又要通过解码使所生成的编码能原封不动地解成原来的文件。
在编写程序的过程中，也遇到了许多问题，也更让我体会到了编写程序应该是一步一个脚印得来的，编写一个模块，调试一个，不能全部编写的差不多了，在进行调试，这样反而是得不偿失，遇到一大堆的错误让人无从找起。
从最开始的统计，建树，选择最小次小值，到后来的编码、译码，自己写了一些，也参考了一下别人好的程序，例如在选择最小值和次小值时，按照书上是给min1和min2初始赋值为32767，但参照了一些好的程序之后，我选择将min1，min2初始赋值位一个小于等于零的数，这样会更好，因为字符的频率不吭能为一个小于等于零的数，如此更符合逻辑；又如统计字符频率时利用ASC码进行统计会更加方便与明了。
当我们写一段程序前，一定要反复的思考，怎样写更方便，更完美，这样才能写出一个好的程序来。
另外调试程序前要有一个大概的图样，这样在编程时可以有目的，针对性的建立函数，对函数的形参与实参也要在大脑中有个清晰的认识，否则问题出在这就很难解决了。
由于哈夫曼编码中会运用到很多循环，所以在编写循环时一定要注意控制语句，防止造成死循环。
七、参考文献
C语言程序设计--------------科学出版社
数据结构（C语言描述）-----清华大学出版社
数据结构（使用C语言）-----电子科技大学出版社
八、附录：
源代码
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"conio.h"
#defineN100
#defineM2*N-1
typedefstruct//定义哈夫曼树存储节点结构体类型
{
chardata;
intweight;
intparent;
intlchild;
intrchild;
}HuffmanTree[M];
typedefstruct//定义哈夫曼编码结构体类型
{
chardata;
charbits[N];
}HuffmanCode[N];
typedefstructstr//定义字符串存储单元结构体类型
{
chardata;
charnum;
}str;
intread（strs2[]）
{
FILE*fp;
charch;
inti,k;
strs1[128];
for（i=0;i<=128;i++）
{
s1[i].num=0;s1[i].data=0;
s2[i].num=0;s2[i].data=0;
}
if（（fp=fopen（"d:
\\ywq\\ywq1.txt","r"））==NULL）
{
printf（"\n库文件不存在!
"）;
exit
（1）;
}
printf（"\n①.读取字符串为:
\n"）;
ch=fgetc（fp）;
while（!
feof（fp））//统计字符频率
{
printf（"%c",ch）;
s1[ch].num++;
s1[ch].data=ch;
ch=fgetc（fp）;
}
fclose（fp）;
for（i=1,k=1;i<=128;i++）
{
if（s1[i].num!
=0）
{
s2[k].num=s1[i].num;
s2[k].data=s1[i].data;
k++;
}
}
printf（"\n\n②.统计结果为（字符频率）:
\n"）;
for（i=1;i{
printf（"<%c%d>",s2[i].data,s2[i].num）;
}
printf（"（共%d种字符）\n",k-1）;
returnk;
}
voidSelectMin（HuffmanTreeht,inti,int*p1,int*p2）//查找哈夫曼链表中两个权值最小的节点
{
intj,min1,min2;
min1=min2=-1;
for（j=1;j<=i;j++）
{
if（ht[j].parent==0）
{
if（ht[j].weight{
if（min1!
=-1）
{min2=min1;*p2=*p1;}
min1=ht[j].weight;*p1=j;
}
elseif（ht[j].weight{
min2=ht[j].weight;
*p2=j;
}
}
}
}
voidCrtHuffmanTree（HuffmanTreeht,strs[],intn）//创建哈夫曼树
{
inti,m,p1,p2;
for（i=1;i{
ht[i].data=s[i].data;
ht[i].weight=s[i].num;
ht[i].parent=0;
ht[i].lchild=0;
ht[i].rchild=0;
}
m=2*n-3;
for（i=n;i<=m;i++）
{
ht[i].data=0;
ht[i].weight=0;
ht[i].parent=0;
ht[i].lchild=0;
ht[i].rchild=0;
}
for（i=n;i<=m;i++）
{
SelectMin（ht,i-1,&p1,&p2）;//调用SelectMin函数
ht[i].weight=ht[p1].weight+ht[p2].weight;
ht[p1].parent=i;ht[p2].parent=i;
ht[i].lchild=p1;ht[i].rchild=p2;
}
}
voidCrtHuffmanCode（HuffmanTreeht,HuffmanCodehc,intk）//利用建立好的哈夫曼树对字符串进行编码
{
intc,p,i;
charcd[N+1];
intstart;
for（i=1;i{
hc[i].data=ht[i].data;
start=k-1;
cd[start]='\0';
c=i;
while（（p=ht[c].parent）!
=NULL）
{
cd[--start]=（ht[p].lchild==c）?
'0':
'1';//左分支为0，右分支为1
c=p;
}
strcpy（hc[i].bits,&cd[start]）;
}
printf（"\n\n③.每个字符对应的编码为:
\n"）;
for（i=1;iprintf（"<%d%c%s>\n",i,hc[i].data,hc[i].bits）;
}
voidWriteToFile（HuffmanCodehc,intn）//将编码结果存储在文件文件ywq2.txt中
{
FILE*fp1,*fp2;
charch;
inti;
if（（fp1=fopen（"d:
\\ywq\\ywq1.txt","r"））==NULL）
{
printf（"\n文件不存在!
"）;
exit
（1）;
}
if（（fp2=fopen（"d:
\\ywq\\ywq2.txt","w"））==NULL）
{
printf（"\n文件不存在!
"）;
exit
（1）;
}
ch=fgetc（fp1）;
printf（"\n④.编码结果为：
"）;
while（ch!
=EOF）
{
for（i=1;iif（ch==hc[i].data）
{
fputs（hc[i].bits,fp2）;
printf（"%s",hc[i].bits）;
}
ch=fgetc（fp1）;
}
fclose（fp1）;
fclose（fp2）;
printf（"\n"）;
}
voidDecodHuffmanCode（HuffmanTreeht,intn）//码结果进行译码，并将结果存储
在文件ywq3中
{
FILE*fp1,*fp2;
charch;
intp,k;
if（（fp1=fopen（"d:
\\ywq\\ywq2.txt","r"））==NULL）
{
printf（"\n文件不存在!
"）;
exit
（1）;
}
if（（fp2=fopen（"d:
\\ywq\\ywq3.txt","w"））==NULL）
{
printf（"\n文件未能创建!
"）;
exit
（1）;
}
p=k=2*n-3;
ch=fgetc（fp1）;
printf（"⑥.译码为:
"）;
while（ch!
=EOF）
{
if（ch=='0'）p=ht[p].lchild;
elseif（ch=='1'）p=ht[p].rchild;
if（ht[p].data!
=0）
{
printf（"%c",ht[p].data）;
fputc（ht[p].data,fp2）;
p=k;
}
ch=fgetc（fp1）;
}
printf（"\n"）;
fclose（fp1）;fclose（fp2）;
}
voidcompare（intk）
{
FILE*fp1,*fp2;
chars1[N],s2[N];
inti=1,j=1;
printf（"\n\n⑦.编译前后结果的比较:
"）;
if（（fp1=fopen（"d:
\\ywq\\ywq1.txt","rt"））==NULL）
{
printf（"\n打开文件失败！
\n"）;
exit
（1）;
}
printf（"\n\n原文件ywq1.txt中的字符为:
"）;
for（i=1;（s1[i]=fgetc（fp1））!
=EOF;i++）
printf（"%c",s1[i]）;
fclose（fp1）;
if（（fp2=fopen（"d:
\\ywq\\ywq3.txt","rt"））==NULL）
{
printf（"\n打开文件失败！
\n"）;
exit
（1）;
}
printf（"\n文件ywq3.txt中的字符为:
"）;
for（i=1;（s2[i]=fgetc（fp2））!
=EOF;i++）
printf（"%c",s2[i]）;
fclose（fp2）;
while（j{
if（s1[j]==s2[j]）
j++;
else
{
printf（"\n编码失败！
\n"）;
break;
}
}
if（j==k）
printf（"\n前后数据一致，编码成功！
。
。
。
O（∩_∩）O。
。
。
！
\n"）;
}
voidmain（）
{
inti,k;
intj=1;
HuffmanTreeht;
HuffmanCodehc;
strs2[128];
system（"colorF5"）;
printf（"\n-------------------------------哈夫曼编码译码器---------------------------------"）;
k=read（s2）;
getch（）;
CrtHuffmanTree（ht,s2,k）;
CrtHuffmanCode（ht,hc,k）;
WriteToFile（hc,k）;
getch（）;
printf（"\n\n"）;
printf（"⑤.建立的哈夫曼树为:
"）;
printf（"\nnumber\tdata\tweight\tlchild\trchild\tparent"）;
for（i=1;i{
printf（"\n%d:
%c%d%d%d%d",i,ht[i].data,ht[i].weight,ht[i].lchild,ht[i].rchild,ht[i].parent）;
}
printf（"\n\n"）;
DecodHuffmanCode（ht,k）;
getch（）;
compare（k）;
printf（"\n\n按任意键退出...\n"）;
}
题目2.学生信息管理系统
一、课程设计目的
1．数据结构课程设计是综合运用数据结构课程中学到的几种典型数据结构，以及程序设计语言（C语言），自行实现一个较为完整的应用系统的设计与开发
2．通过课程设计，自己通过系统分析、系统设计、编程调试，写实验报告等环节，进一步掌握应用系统设计的方法和步骤，灵活运用并深刻理解典型数据结构在软件开发中的应用。
3．学会将知识应用于实际的方法，提高分析和解决问题的能力，增加综合能力。
学生信息管理系统：
（1）熟练掌握链表存储结构及其建立过程和常用操作；
（3）学会自己调试程序的方法并掌握一定的技巧
二、课程设计内容
建立学生信息管理系统，通过链表实现对学生信息的输入，查找，删除，插入和排序等操作。
三、需求分析
1．每位学生的信息有：
学号，姓名，性别，出生日期，E-mile，电话，c成绩，数学成绩等，用链表对学生的信息进行存储。
2．全部数据可以只放在内存中；
3．系统能实现的操作和功能如下：
a）输入学生信息：
对不同学生分别输出下列信息：
学号，姓名，性别，出生日期，E-mile，电话，c成绩，数学成绩等。
b）查找学生信息：
根据学生的学号或姓名对学生的信息进行查找。
c）删除学生信息：
删除某个学生的所有信息。
d）插入学生信息：
将某个学生的信息插入到已经输入的信息中。
e）显示学生信息：
将所有学生的信息显示出来。
f）排序：
将所有学生按某个学科的成绩依次排序。
四、概要设计
1．系统结构图（功能模块图）
2．功能模块说明
①．输入学生信息，creat（）函数：
建立单向链表，组织循环，将学生的信息依次录入。
②：
查找学生信息：
a.按学号查找,find1（）函数；
b.按姓名查找,find2（）函数；
③．删除学生信息，del（）函数：
建立指针，在链表中寻找要删除信息的学生的学号，找到后p->next=p->next->next,将其删除。
④．插入学生信息，insert（）函数；
输入要插入的信息，建立指针，寻找要插入的节点。
⑤．显示学生信息，print（）函数；
将以存在的学生信息输出
⑥．按某科成绩对学生进行排序，sort（）函数；
五、详细设计及运行结果
1.菜单：
2.creat（）函数.
3.find（）函数.
find1（）:
find2（）:
3.del（）函数.
4.insert（）函数.
5.print（）函数.
6.sort（）函数.
六、调试情况，设计技巧及体会
通过这次课程设计，我对这门课又有了一个新的理解，最大的喜悦不是写出程序，而是从中学会了怎么去写，该如何去写，在老师的严格监督下，自己也养成了独立思考的习惯，真的从中得到了很多好处，从思想到着手，所有都是程序化的，必须踏踏实实的来。
通过学生信息管理系统的设计，使我对链表有了更深的了解，也懂得了如何用链表进行输入，插入，排序等操作，两个礼拜的实习很快就过去了，这一次真的学到了很多东西，我也将会将自己所学到的东西用到自己以后的学习中去。
七、参考文献
C语言程序设计--------------科学出版社
数据结构（C语言描述）-----清华大学出版社
数据结构（使用C语言）-----电子科技大学出版社
八、附录：
源代码
#include
#include
#include
#defineNsizeof（structstu）
voidclearscreen（）/*清屏函数*/
{getchar（）;
system（"cls"）;
}
structdate/*定义出生年月日的结构体*/
{intyear;
intmouth;
intday;
};
structstu/*定义学生信息的结构体*/
{intnumber;
charname[30];
charsex[5];
structdatebirthday;
charmail[30];
charphone[30];
intcscore,mscore;
structstu*next;
};
/*输出函数*/
intprint（structstu*p）
{
while（p!
=NULL）/*如果P所指的结点不为空执行循环*/
{printf（"学号姓名性别出生日期E-mail电话C成绩数学成绩\n"）;
printf（"%2d%6s%6s%8d-%2d-%2d%11s%11s%6d%8d\n",p->number,p->name,p->sex,p->birthday.year,p->birthday.mouth,p->birthday.day,p->mail,p->phone,p->cscore,p->mscore
）;
p=p->next;
}
printf（"\n\n按回车键返回\n\n"）;
getchar（）;
return0;
}
/*创建链表*/
structstu*creat（）
{structstu*p,*head;
inti,k;
printf（"请输入学生的数：
\n"）;
scanf（"%d",&k）;
p=head=（structstu*）malloc（N）;
printf（"请输入学号\n"）;
scanf（"%d",&p->number
升级会员 