《数据结构》
课程设计报告
设计题目哈夫曼(Huffman)编译码器
学院名称信息工程学院
专业班级 13计本1 姓名 hhh
学号1312219999
目录
一、实验题目-哈夫曼(Huffman)编/译码器 ------------------------------
二、问题描述-----------------------------------------------
三、设计目标-----------------------------------------------
四、需求分析-----------------------------------------------
五、概要设计-----------------------------------------------
1---系统结构图--------------------------------------
2--各个模块功能的详细描述------------------------------- 六、详细设计-----------------------------------------------
1——详细代码--------------------------------------
a)头文件代码--------------------------------------
b)主函数代码--------------------------------------
2——系统流程图--------------------------------------
七、测试分析-----------------------------------------------
八、使用说明-----------------------------------------------
1、白盒-----------------------------------------------
2、黑盒-----------------------------------------------
九、课程设计总结----------------------------------------------
一、实验题目
哈夫曼(Huffman)编/译码器
二、问题描述
利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。
三、设计目标
设计一个程序,该程序可以实现哈夫曼的编码及译码过程。
四、需求分析
一个完整的系统应具有以下功能:
1)I:初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值(见
下表),建立哈夫曼树,并将它存于文件hfmTree.txt中。
2)E:编码(Encoding)。利用已建好的哈夫曼树(如不在内存,则从文件hfmTree.txt中
读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。
3)D:译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结
果存入文件TextFile中。
4)P:打印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上,每行50个代
码。同时将此字符形式的编码文件写入文件CodePrin中。
5)T:打印哈夫曼树(Tree Printing)。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中
五、概要设计
1、系统结构功能图
menu2()
menu1()menu3()
reaD ata( data );//载入数据pri
ntD
ata
(da
ta)
;//
输
出
数
据
sort
(dat
a);/
/
对数
据进
行排
序
reaHF
Data(
hmdat
a);
sortH
MC(hm
data)
;载入
哈夫
曼码
并排
序
bthe
ad =
crea
tebt
(dat
a);/
/
建哈
夫曼
树
HuffM
anCod
ing(b
thead
, 0,
fp);/
/
并写
入文
件
HuffM
anfil
e();/
/
显示
哈夫
曼树
bthea
d =
destr
oybt(
bthea
d);
//
销毁
哈夫
曼树
HFDat
a(hmd
ata);
Encod
ing(h
mdata
);
Enco
ding
(hmd
ata)
;编
码
Deco
ding
();
译码
PreOr
derPr
int(b
thead
);//
打印
哈夫
曼树
Prin
tCod
eFil
e();
//
打印
代码
文件
函数功能图
2 各个模块功能的详细描述
int reaData(mytype d[])//载入数据
int reaHFData(HuffM d[])//从hfmTree.txt文件读取数据
int printData(mytype d[]) //数据显示字符频度
int printHFData(HuffM d[]) //显示哈夫曼树字符编码
int sort(mytype d[])//对数据频度大小排序建哈夫曼树时调用
int sortHMC(HuffM d[])//对哈夫曼树字符排序译码文件时调用
int sort1(bitree* temp[N],int n)//对新的数据重新频度大小排序建树时调用
bitree * createbt(mytype d[])//建哈夫曼树
bitree * destroybt(bitree * head)//销毁哈夫曼树,释放空间递归调用 void HuffManCoding(bitree *BT, int len,FILE *fp) //哈夫曼树编码利用 static函数并写入文件
int printHuffManfile() //输出哈夫曼树字符频度编码
int Encoding(HuffM d[])//编码
int Decoding(HuffM d[])//编码
void PrintCodeFile()
void PreOrderPrint(bitree *HT)
六、详细设计
1 详细代码
a)头文件
#include "stdio.h"
#include "string.h"
#define N 30
typedef struct hm{
char ch;
char code[20];
}HuffM;
typedef struct s{
char ch;
int frq;
}mytype;
typedef struct bt{
struct bt *lchild;
mytype dt;
struct bt *rchild;
}bitree;
int g_flag=0;
int Encoding(HuffM d[]);
int PreOrderPrint(bitree *HT);
void PrintCodeFile();
int Decoding(HuffM d[]);
b)主函数
#include "myhead.h"
int reaData(mytype d[])//载入数据
{
FILE * fp;
int i=0;
fp=fopen("data.txt","r");
if(NULL==fp)
{
return -1;
}
while(!feof(fp))
{
fscanf(fp,"%c",&(d[i].ch));
fscanf(fp,"%d",&(d[i].frq));
fseek(fp,2,SEEK_CUR);
i++;
if(i==N-2)
break;
}
g_flag=1;
fclose(fp);
return 0;
}
int reaHFData(HuffM d[])//从hfmTree.txt文件读取数据{
FILE * fp;
int i=0,td;
char c,data[20];
fp=fopen("hfmTree.txt","r");
if(NULL==fp)
{
printf("打开哈夫曼编码数据文件出错。\n");
return -1;
}
while(1)
{
fscanf(fp,"%c%d%s",&c,&td,data);
if(feof(fp))
break;
//printf("%c\t%d\t%s\n",c,td,data);
d[i].ch=c;
strcpy(d[i].code,data);
i++;
fseek(fp,2,SEEK_CUR);=
}
g_flag=1;
fclose(fp);
return 0;
}
int printData(mytype d[]) //数据显示字符频度
{
int i=0;
if(g_flag<1)
{
printf("请先载入数据文件。\n");
return 0;
}
for(;i { printf("%c\t%d\n",d[i].ch,d[i].frq); } return 0; } int printHFData(HuffM d[]) //显示哈夫曼树字符编码{ int i=0; if(g_flag<1) { printf("请先载入数据文件。\n"); return 0; } for(;i { printf("%c\t%s\n",d[i].ch,d[i].code); } return 0; } int sort(mytype d[])//对数据频度大小排序建哈夫曼树时调用{ int i,j; mytype temp; if(g_flag<1) { printf("请先载入数据文件。\n"); return 0; } for(i=0;i { for(j=0;j { if(d[j].frq>d[j+1].frq) { temp=d[j]; d[j]=d[j+1]; d[j+1]=temp; } } } } int sortHMC(HuffM d[])//对哈夫曼树字符排序译码文件时调用{ int i,j; HuffM temp; if(g_flag<1) { printf("请先载入数据文件。\n"); return 0; } for(i=0;i { for(j=0;j { if(d[j].ch>d[j+1].ch) { temp=d[j]; d[j]=d[j+1]; d[j+1]=temp; } } } } int sort1(bitree* temp[N],int n)//对新的数据重新频度大小排序建树时调用{ int i,j; bitree* tmp; for(i=0;i { for(j=0;j { if(temp[N-3-n+j]->dt.frq>temp[N-3-n+j+1]->dt.frq) { tmp=temp[N-3-n+j]; temp[N-3-n+j]=temp[N-3-n+j+1]; temp[N-3-n+j+1]=tmp; } } } } bitree * createbt(mytype d[])//建哈夫曼树 { bitree* head=NULL; bitree* temp[N]={NULL}; int i=0; if(g_flag<1) { printf("请先载入数据文件。\n"); return 0; } sort(d); while(i { temp[i]=(bitree *)malloc(sizeof(bitree)); temp[i]->dt=d[i]; temp[i]->lchild=NULL; temp[i]->rchild=NULL; i++; } i=0; while(i { head=(bitree *)malloc(sizeof(bitree)); head->dt.ch='*'; head->dt.frq=temp[i]->dt.frq + temp[i+1]->dt.frq; head->lchild=temp[i]; head->rchild=temp[i+1]; temp[i+1]=head; temp[i]=NULL; sort1(temp,N-i-4); i++; } g_flag = 11; return head; } bitree * destroybt(bitree * head)//销毁哈夫曼树,释放空间递归调用 { bitree *temp; if(head==NULL) return NULL; temp=head; if(head->lchild) head->lchild=destroybt(temp->lchild); if(head->rchild) head->rchild=destroybt(temp->rchild); free(head); head=NULL; return NULL; } void HuffManCoding(bitree *BT, int len,FILE *fp) //哈夫曼树编码利用static函数并写入文件 { static int a[10]; int i; if(g_flag<11) { printf("请先建立哈夫曼树。\n"); return 0; } if(BT!=NULL){ if(BT->lchild==NULL&&BT->rchild==NULL){ //printf("字符%c的权值为%d的编码:",BT->dt.ch,BT->dt.frq); fprintf(fp,"%c\t%d\t",BT->dt.ch,BT->dt.frq); for(i=0;i //printf("%d ",a[i]); fprintf(fp,"%d",a[i]); fprintf(fp,"\n"); //printf("\n"); } else{ a[len]=0; HuffManCoding(BT->lchild, len+1,fp); a[len]=1; HuffManCoding(BT->rchild, len+1,fp); } } } int menu() { int n; printf("*****************************\n"); printf("字符集和频度操作:\n"); printf("\t1.载入数据文件。\n"); printf("\t2.显示数据。\n"); printf("\t3.排序。\n"); printf("哈夫曼树操作:\n"); printf("\t4.建立哈夫曼树。\n"); printf("\t5.写入哈夫曼编码文件。\n"); printf("\t6.显示哈夫曼编码文件。\n"); printf("\t7.销毁哈夫曼树。\n"); printf("哈夫曼编译码操作:\n"); printf("\t8.载入哈夫曼编码。\n"); printf("\t9.显示哈夫曼编码。\n"); printf("\t10.编码ToBeTran文件.\n"); printf("\t11.译码CodeFile文件.\n"); printf("\t12.打印CodeFile文件.\n"); printf("\t13.打印哈夫曼树.\n"); printf("\t14.退出\n"); printf("*****************************\n"); printf("请输入选择:"); { scanf("%d",&n); if(n>0&&n<15) break; printf("输入错误,请重输:"); } system("cls"); return n; } int printHuffManfile() //输出哈夫曼树字符频度编码{ FILE * fp; char data[50],c; int d; fp=fopen("hfmTree.txt","r"); if(NULL==fp) { printf("打开文件哈夫曼编码错误。\n"); return -1; } while(1) { fscanf(fp,"%c%d%s",&c,&d,data); if(feof(fp)) break; printf("%c\t%d\t%s\n",c,d,data); fseek(fp,2,SEEK_CUR); } fclose(fp); } main() { mytype data[N]={0}; HuffM hmdata[N]={0}; int flag; int choose,count; FILE *fp; bitree * bthead=NULL; count=0; g_flag=0;//刚开始时数据为空。 { choose=menu(); switch(choose) { case 1: flag=reaData(data); if(-1==flag) { printf("Open data.txt file error!\n"); return; } break; case 2: printData(data); break; case 3: sort(data); break; case 4: bthead=createbt(data); break; case 5: fp=fopen("hfmTree.txt","w+"); if(NULL==fp) { printf("写入哈夫曼编码错误!\n"); return; } HuffManCoding(bthead,0,fp); g_flag=111; fclose(fp); break; case 6: printHuffManfile(); break; case 7: if(g_flag<11) { printf("请先建立哈夫曼树。\n"); break; } bthead=destroybt(bthead); g_flag=1; break; case 8: flag=reaHFData(hmdata); if(-1==flag) { printf("Open data.txt file error!\n"); return; } sortHMC(hmdata); break; case 9: printHFData(hmdata); break; case 10: Encoding(hmdata); break; case 11: Decoding(hmdata); break; case 12: PrintCodeFile(); break; case 13: PreOrderPrint(bthead,count); break; case 14: destroybt(bthead); return 0; break; } } } int Encoding(HuffM d[])//编码 { FILE *fp,*pfc; char data[256]={0},c; fp=fopen("ToBeTran.txt","r"); pfc=fopen("CodeFile.txt","w+"); if(NULL==fp) { printf("打开文件ToBeTran.txt出错,编码未完成.\n"); return -1; } if(NULL==pfc) { fclose(fp); printf("CodeFile.txt出错,编码未完成.\n"); return -1; } while(1) { fread(&c,1,1,fp); if(c>='a'&&c<='z') c-=32; if(c>='A'&&c<='Z') { //printf("%s",d[c-'A'+1].code); fprintf(pfc,"%s",d[c-'A'+1].code); } else if (c==' ') //printf("%s",d[0].code); fprintf(pfc,"%s",d[0].code); else //printf("%c",c); fprintf(pfc,"%c",c); //printf("%c",c); if(feof(fp)) break; } fclose(fp); fclose(pfc); } int Decoding(HuffM d[])//编码 { FILE *fp, *pfc; char data[20] = { 0 },c; int i;//, flag fp = fopen("ToBeTran.txt", "r"); pfc = fopen("TextFile.txt", "w+"); if (NULL == fp) { printf("打开文件ToBeTran.txt出错,译码未完成.\n"); return -1; } if (NULL == pfc) { fclose(fp); printf("TextFile.txt出错,译码未完成.\n"); return -1; } while (1) { fread(&c, 1, 1, fp); if (c=='1' || c=='0') { // return 1; for(i=0;i<27;i++) { data[i]=c; while (strcmp(d[i].code,data)==0) fprintf(pfc,"%c",d[i].ch); } } else //printf("%c",c); fprintf(pfc,"%c",c); //printf("%c",c); if (feof(fp)) break; } fclose(fp); fclose(pfc); return 1; } void PrintCodeFile() { FILE *fc; int flag; char ch; printf("打印编码后的文件:\n "); fc=fopen("CodeFile.txt", "r"); if (NULL==fc) { printf("打印编码后的文件失败!! "); exit(0); } flag = 1; while (!feof(fc)) { ch = fgetc(fc); if (ch == -1) { printf("结束打印\n"); } else { printf("%c", ch); if (flag <= 49) flag++; else { flag = 1; printf("\n"); } } } fclose(fc); //关闭文件 } int PreOrderPrint(bitree *HT,int count) { int n = 2 * (N - 3) - 1, i; if(NULL!=HT){ for (i = 0; i printf(" "); printf("%c%d\n",HT->dt.ch,HT->dt.frq); PreOrderPrint(HT->lchild, ++count); PreOrderPrint(HT->rchild, ++count); } return 1; } 2 流程图 1、载入数据 2 、hfmTree.txt 文件读取数据 开始 FILE * fp;int i=0; fp=fopen("data.txt","r"); NULL==fp fscanf(fp,"%c",&(d[i].ch));fscanf(fp,"%d",&(d[i].drq)); Feof(fp)== -1 i++; fseek(fp,2,SEEK_CUR);fclose(fp); 结束 N N Y Y 文件打开失败 i==N-2 y N 开始 FILE * fp;int i=0,td; Char c,Data[20]; fp=fopen("hfmTree.txt","r"); NULL==fp fscanf(fp,"%c%d%s",&c,&td,data ); Feof(fp)== -1 d[i].ch=c; Strcpy(d[i].code,data);i++;fseek(fp,2,SEEK_CUR);fclose(fp); 结束 N N Y Y 文件打开失败 3、哈夫曼树字符排序 4、建哈夫曼树 开始 Int i=0,j=0; HuffM temp; i Temp=d[j]; d[j]=d[j+1]; d[j+1]=temp; J j++; 结束 N N Y Y d[j].ch>d[j+1 ].ch y N i++; Y 开始 bitree* head=NULL; bitree* temp[N]={NULL}; int i=0; 结束 N 调用sort(d);函数,对传进来的数组数据排序 i Temp[i]=(bitree*)malloc(sizeof(bitree)); temp[i]>dt=d[i]; Temp[i]>lchild=NULL;temp[i]>rchild=NULL; i++ i=0 i head=(bitree *)malloc(sizeof (bitree));head>dt.ch='*'; Head>dt.frq=temp[i]->dt.frq + temp[i+1]>dt.frq;head->lchild=temp[i];head->rchild=temp[i+1];temp[i+1]=head;temp[i]=NULL;sort1(temp,N-i-4); i++y y n n 5、销毁哈夫曼树 6、哈夫曼树编码 开始 staticint a[10]; Int i=0; Len=0 结束 N BT!=NULL fprintf(fp,"%c\t%d\t",BT->dt.ch,BT->dt.frq); fprintf(fp,"%d",a[i]); BT->lchild==NULL&&BT->rchild==NULL) a[len]=0; y y n n i y 7、译码 开始 结束 FILE *fp,*pfc; char data[256]={0},c; fp=fopen("ToBeTran.txt","r");pfc=fopen("CodeFile.txt","w+"); NULL==fp NULL==pfc fread(&c,1,1, fp); c>='a'&&c<= 'z' c>='A'&&c<= 'Z') fprintf(pfc,"%s",d[c-'A'+1].code); c==' ') fprintf(pfc,"%s",d[0].code); fprintf(pfc,"%c",c); (feof(fp)) fclose(fp); fclose(pfc); c-=32; 打开文件ToBeTr an.txt 出错,编码未完成."CodeFile.txt 出错,编码未完 成. return -1; y n y y y y y n n n n n n n 数据结构课程设计设计题目:哈夫曼树编码译码 目录 第一章需求分析 (1) 第二章设计要求 (1) 第三章概要设计 (2) (1)其主要流程图如图1-1所示。 (3) (2)设计包含的几个方面 (4) 第四章详细设计 (4) (1)①哈夫曼树的存储结构描述为: (4) (2)哈弗曼编码 (5) (3)哈弗曼译码 (7) (4)主函数 (8) (5)显示部分源程序: (8) 第五章调试结果 (10) 第六章心得体会 (12) 第七章参考文献 (12) 附录: (12) 在当今信息爆炸时代,如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视,哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式,以哈夫曼树—即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩。哈弗曼编码使用一张特殊的编码表将源字符(例如某文件中的一个符号)进行编码。这张编码表的特殊之处在于,它是根据每一个源字符出现的估算概率而建立起来的(出现概率高的字符使用较短的编码,反之出现概率低的则使用较长的编码,这便使编码之后的字符串的平均期望长度降低,从而达到无损压缩数据的目的)。哈夫曼编码的应用很广泛,利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径,对路径上的各分支约定:指向左子树的分支表示“0”码,指向右子树的分支表示“1”码,取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码,这就是哈夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码,输入二进制代码时可以编译成字符串。 第二章设计要求 对输入的一串电文字符实现哈夫曼编码,再对哈夫曼编码生成的代码串进行译码,输出电文字符串。通常我们把数据压缩的过程称为编码,解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时,总希望总长度能尽可能短,即采用最短码。假设每种字符在电文中出现的次数为Wi,编码长度为Li,电文中有n种字符,则电文编码总长度为∑WiLi。若将此对应到二叉树上,Wi为叶结点的权,Li为根结点到叶结点的路径长度。那么,∑WiLi 恰好为二叉树上带权路径长度。因此,设计电文总长最短的二进制前缀编码,就是以n种字符出现的频率作权,构造一棵哈夫曼树,此构造过程称为哈夫曼编码。设计实现的功能: (1) 哈夫曼树的建立; (2) 哈夫曼编码的生成; (3) 编码文件的译码。 算法与数据结构课程设计哈夫曼编码/译码器设计 学生姓名: 学号: 专业:(计算机科学与技术) 年级:(大二) 指导教师:(汪洋) 2009年6月19日 哈夫曼编码/译码器 问题描述: 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本,但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道)每端都需要一个完整的编/译码系统。试为这样的信息收发站写一哈夫曼编/译码系统。 基本要求: I:初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中。 E:编码(Encoding)。利用已建好的哈夫曼树(如不在内存,则从文件hfmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。 D:译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。 P:打印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。 T:打印哈夫曼树(Tree printing)。将已在中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。 大体解题思路: (1)对输入的一段欲编码的字符串进行统计各个字符出现的次数,并它们转化为权值{w1,w2,……,wN}构成n棵二叉树的集合F={T1,T2,……,Tn}把它们保存到结构体数组HT[n]中,其中{Ti是按它们的ASCⅡ码值先后排序。其中每棵二叉树Ti中只有一个带权为Wi的根结点的权值为其左、右子树上根结点的权值之和。 (2)在HT[1..i]中选取两棵根结点的权值最小且没有被选过的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。 (3)哈夫曼树已经建立后,从叶子到根逆向求每一个字符的哈夫曼编码。 概要设计: 实现的功能:1.查看原文(showpassage()),2.字符统计(showdetail()), 兰州商学院陇桥学院 工学系课程设计报告 设计题目:哈夫曼(huffman)编译码器系别: 专业 (方向): 年级、班: 学生姓名: 学生学号: 指导教师: 年月日 目录 哈夫曼(huffman )编译码器 (3) 一、编译码器开发的背景 (3) 二、系统的分析与设计 (3) (一)系统功能要求 (3) (二)系统模块结构设计 (4) 三、系统的设计与实现 (6) (一)main() (6) (二)运算 (7) 1. 权值运算quanzhi() (7) 2. 印二叉树函数huffmantree( ) (7) 3.编译码运算huffmancode() (9) 4. 输出运算 shuchu() (9) 四、系统测试 (10) (一)测试主函数 (10) (二)测试印二叉树函数 (10) (三)测试译码运算函数 (11) 五、总结 (12) 六、附件(代码、部分图表) (13) 哈夫曼(huffman )编译码器 一、编译码器开发的背景 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。 二、系统的分析与设计 (一)系统功能要求 一个完整的系统应具有以下功能: 1)I:初始化(Initialization)。从终端读入字符集大小n,以 及n个字符和n个权值,建立哈夫曼树,并将它存于文件 hfmTree中。 2)E:编码(Encoding)。利用以建好的哈夫曼树(如不在内存, 则从文件hfmTree中读入),对文件ToBeTran中的正文进行编 码,然后将结果存入文件CodeFile中。 3)D:译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile 中的代码进行译码,结果存入文件TextFile中。 4)P:印代码文件(Print)。将文件CodeFile以紧凑格式显示在 数据结构课程设计评阅书 2011—2012学年第一学期 专业:信息管理与信息系统学号: 1021024016 姓名:万永馨 课程设计名称:数据结构课程设计 设计题目:哈夫曼编码与译码的实现 完成期限:自 2012 年 2 月 20 日至 2012 年 3 月 2 日共 2 周 设计依据、要求及主要内容(可另加附页): 该设计题目将按以下要求完成: 哈夫曼编码与译码是信息传输中应用的经典算法,运用C或VC++结合数据结构等基础知识,按 以下要求编程实现各种进制的转换。 任务要求:1)阐述设计思想,画出流程图;2)需要对哈夫曼编码/译码的相关原理有所了解,设计数 据结构,建立必要的信息数据文件(最好存储成外部文件),并分析完成用户所需的基本操作功能;3)实现给定信息的编码和译码功能;4)应有较好的界面设计,说明程序测试方法;5)按照格式要 求完成课程设计说明书。 设计要求: 1)问题分析和任务定义:根据设计题目的要求,充分地分析和理解问题,明确问题要求做什么?(而不是怎么做?)限制条件是什么?确定问题的输入数据集合。 2)逻辑设计:对问题描述中涉及的操作对象定义相应的数据类型,并按照以数据结构为中心的 原则划分模块,定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定 义(包括数据结构的描述和每个基本操作的功能说明),各个主要模块的算法,并画出模块之间的调 用关系图; 3)详细设计:定义相应的存储结构并写出各函数的伪码算法。在这个过程中,要综合考虑系统 功能,使得系统结构清晰、合理、简单和易于调试,抽象数据类型的实现尽可能做到数据封装,基 本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精, 写出数据存储结构的类型定义,写出函数形式的算法框架; 4)程序编码:把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言, 使程序中逻辑概念清楚; 5)程序调试与测试:能够熟练掌握调试工具的各种功能,设计测试数据确保程序正确。调试正 确后,认真整理源程序及其注释,形成格式和风格良好的源程序清单和结果; 6)结果分析:程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算 法的时间、空间复杂性分析; 7)编写课程设计报告; 以上要求前三个阶段的任务完成后,将设计说明书的草稿交指导老师面审,审查合格方可进入 后续阶段的工作。设计工作结束,经指导老师验收合格后将设计说明书装订,并答辩。 数据结构课程设计哈夫曼编码-2 《数据结构与算法》课程设计 目录 一、前言 1.摘要 2.《数据结构与算法》课程设计任务书 二、实验目的 三、题目--赫夫曼编码/译码器 1.问题描述 2.基本要求 3.测试要求 4.实现提示 四、需求分析--具体要求 五、概要设计 六、程序说明 七、详细设计 八、实验心得与体会 前言 1.摘要 随着计算机的普遍应用与日益发展,其应用早已不局限于简单的数值运算,而涉及到问题的分析、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。算法与数据结构的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。 算法与数据结构旨在分析研究计算机加工的数据对象的特性,以便选择适当的数据结构和存储结构,从而使建立在其上的解决问题的算法达到最优。 数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成,即一个数据由那些成分数据构成,以什么方式构成,呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系,而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。 《数据结构》主要介绍一些最常用的数据结构,阐明各种数据结构内在的逻辑关系,讨论其在计算机中的存储表示,以及在其上进行各种运算时的实现算法,并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程,它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础,广泛的应用于信息学、系统工程等各种领域。 学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力,促进学生的综合应用能力和专业素质的提高。 JAVA语言实验报告 学院计算机工程学院班级计算1013 姓名 xxxx 学号 201081xxxx 成绩指导老师 xxxx 2012年09月03日 目录 目录 (1) 1 课程设计的目的和意义 (2) 2 需求分析 (3) 3 系统(项目)设计 (5) ①设计思路及方案 (5) ②模块的设计及介绍 (5) ③主要模块程序流程图 (8) 4 系统实现 (11) ①主调函数 (12) ②建立HuffmanTree (12) ③生成Huffman编码并写入文件 (15) ④电文译码 (16) 5 系统调试 (17) 参考文献 (21) 附录源程序 (22) 1 课程设计的目的和意义 在当今信息爆炸时代,如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。 哈夫曼编码的应用很广泛,利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径,对路径上的各分支约定:指向左子树的分支表示“0”码,指向右子树的分支表示“1”码,取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码,这就是哈夫曼编码。 通常我们把数据压缩的过程称为编码,解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时,总希望总长度尽可能最短,即采用最短码。 作为信息管理专业的学生,我们应该很好的掌握这门技术。在课堂上,我们能过学到许多的理论知识,但我们很少有过自己动手实践的机会!课程设计就是为解决这个问题提供了一个平台。 在课程设计过程中,我们每个人选择一个课题,认真研究,根据课堂讲授内容,借助书本,自己动手实践。这样不但有助于我们消化课堂所讲解的内容,还可以增强我们的独立思考能力和动手能力;通过编写实验代码和调试运行,我们可以逐步积累调试C程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。 在课程设计过程中,我们不但有自己的独立思考,还借助各种参考文献来帮助我们完成系统。更为重要的是,我们同学之间加强了交流,在对问题的认识方面可以交换不同的意见。同时,师生之间的互动也随之改善,我们可以通过具体的实例来从老师那学到更多的实用的知识。 数据结构课程具有比较强的理论性,同时也具有较强的可应用性和实践性。课程设计是一个重要的教学环节。我们在一般情况下都能够重视实验环节,但是容易忽略实验的总结,忽略实验报告的撰写。通过这次实验让我们明白:作为一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。只有这样,我们的综合素质才会有好的提高。 《数据结构》课程设计 设计题目:哈弗曼编/译码器 专业:网络工程 班级:24070901 学号:2407090133 姓名:王璇 目录 1. 问题描述……………………………………………第 2页 2. 系统设计……………………………………………第 2页 3. 数据结构与算法描述………………………………第 5页 4. 测试结果与分析……………………………………第 6页 5. 总结 (10) 6. 参考文献 (10) 附录程序源代码 (11) 课程设计题目 1. 问题描述 利用哈夫曼编码进行信息通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。试为这样的信息传输写一个哈夫曼编/译码系统。 2. 系统设计 2.1 设计目标 一个完整的系统应具有以下功能: 1)I:初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中。输出哈夫曼树,及各字符对应的编码。 2)W:输入(Input)。从终端读入需要编码的字符串s,将字符串s存入文件Tobetran.txt中。 3)E:编码(Encoding)与译码(Decoding)。 编码(Encoding)。利用已建好的哈夫曼树(如不在内存,则从文件htmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。 译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中。 印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码写入文件CodePrint中。 4)T:印哈夫曼树(Tree Printing)。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件TreePrint中。 5)Q:退出程序。返回WINDOWS界面。 2.2 设计思想 哈夫曼编码(Huffman Coding)是一种编码方式,以哈夫曼树─即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩。是指使用一张特殊的编码表将源字符(例如某文件中的一个符号)进行编码。这种方法是由David.A.Huffman发展起来的。例如,在英文中,e 的出现概率很高,而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时,e极有可能用一个位(bit)来表示,而z则可能花去25个位(不是26)。用普通的表示方法时,每个英文字母均占用一个字节(byte),即8个位。二者相比,e使用了一般编码的1/8的长度,z 则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算,就可以大幅 《数据结构与算法》课程设计(2009/2010学年第二学期第20周) 指导教师:王老师 班级:计算机科学与技术(3)班 学号: 姓名: 《数据结构与算法》课程设计 目录 一、前言 1.摘要 2.《数据结构与算法》课程设计任务书 二、实验目的 三、题目--赫夫曼编码/译码器 1.问题描述 2.基本要求 3.测试要求 4.实现提示 四、需求分析--具体要求 五、概要设计 六、程序说明 七、详细设计 八、实验心得与体会 前言 1.摘要 随着计算机的普遍应用与日益发展,其应用早已不局限于简单的数值运算,而涉及到问题的分析、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。算法与数据结构的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。 算法与数据结构旨在分析研究计算机加工的数据对象的特性,以便选择适当的数据结构和存储结构,从而使建立在其上的解决问题的算法达到最优。 数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成,即一个数据由那些成分数据构成,以什么方式构成,呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系,而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。 《数据结构》主要介绍一些最常用的数据结构,阐明各种数据结构内在的逻辑关系,讨论其在计算机中的存储表示,以及在其上进行各种运算时的实现算法,并对算法的效率进行简单的分析和讨论。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程,它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础,广泛的应用于信息学、系统工程等各种领域。 学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力,促进学生的综合应用能力和专业素质的提高。 2.《数据结构与算法》课程设计任务书 《数据结构与算法》是计算机专业重要的核心课程之一,在计算机专业的学习过程中占有非常重要的地位。《数据结构与算法课程设计》就是要运用本课程以及到目前为止的有关课程中的知识和技术来解决实际问题。特别是面临非数值计算类型的应用问题时,需要选择适当的数据结构,设计出满足一定时间和空间限制的有效算法。 本课程设计要求同学独立完成一个较为完整的应用需求分析。并在设计和编写具有一定规模程序的过程中,深化对《数据结构与算法》课程中基本概念、理论和方法的理解;训练综合运用所学知识处理实际问题的能力,强化面向对象的程序设计理念;使自己的程序设计与调试水平有一个明显的提高。 哈夫曼编译码器课程设计报告完整版 XXX学院本科 数据结构课程设计总结报告 设计题目:实验一、哈夫曼编/译码器 学生姓名:XXX 系别:XXX 专业:XXX 班级:XXX 学号:XXX 指导教师:XXX XXX 6 月 21日 xxx学院 课程设计任务书 题目一、赫夫曼编译码器 专业、班级 xxx 学号 xxx 姓名 xxx 主要内容、基本要求、主要参考资料等: 1. 主要内容 利用哈夫曼编码进行信息通信可大大提高信道利用率,缩短信息传输时间,降低传输成本。要求在发送端经过一个编码系统对待传数据预先编码;在接收端将传来的数据进行译码(复原)。对于双工信道(既能够双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。 2. 基本要求 系统应具有以下功能: (1)C:编码(Coding)。对文件tobetrans中的正文进行编码,然后将结果存入文件codefile中,将以此建好的哈夫曼树存入文件HuffmanTree中 (2)D:解码(Decoding)。利用已建好的哈夫曼树将文件codefile中的代码进行译码,结果存入textfile中。 (3)P:打印代码文件(Print)。将文件codefile以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入 文件codeprint中。 (4)T:打印哈夫曼树(Tree Printing)。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件treeprint中。 3. 参考资料:数据结构(C语言版)严蔚敏、吴伟民编著; 数据结构标准教程胡超、闫宝玉编著 完成期限: 6月21 日 指导教师签名: 课程负责人签名: 6月 21 日 一、设计题目(任选其一) 实验一、哈夫曼编/译码器 二、实验目的 1巩固和加深对数据结构的理解,提高综合运用本课程所学知识的能力; 2 深化对算法课程中基本概念、理论和方法的理解; 3 巩固构造赫夫曼树的算法; 4 设计试验用程序实验赫夫曼树的构造。 三、运行环境(软、硬件环境) Windows xp sp3,Visual C++ 6.0英文版 XXX学院本科 数据结构课程设计总结报告 设计题目:实验一、哈夫曼编/译码器 学生姓名:XXX 系别:XXX 专业:XXX 班级:XXX 学号:XXX 指导教师:XXX XXX 2012年6 月21日 xxx学院 课程设计任务书 题目一、赫夫曼编译码器 专业、班级xxx 学号xxx 姓名xxx 主要内容、基本要求、主要参考资料等: 1. 主要内容 利用哈夫曼编码进行信息通信可大大提高信道利用率,缩短信息传输时间,降低传输成本。要求在发送端通过一个编码系统对待传数据预先编码;在接收端将传来的数据进行译码(复原)。对于双工信道(既可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。 2. 基本要求 系统应具有以下功能: (1)C:编码(Coding)。对文件tobetrans中的正文进行编码,然后将结果存入文件codefile中,将以此建好的哈夫曼树存入文件HuffmanTree中 (2)D:解码(Decoding)。利用已建好的哈夫曼树将文件codefile中的代码进行译码,结果存入textfile中。 (3)P:打印代码文件(Print)。将文件codefile以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。 (4)T:打印哈夫曼树(Tree Printing)。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件treeprint中。 3. 参考资料:数据结构(C语言版)严蔚敏、吴伟民编着; 数据结构标准教程胡超、闫宝玉编着 完成期限:2012年6月21 日 指导教师签名: 课程负责人签名: 2012年 6月 21 日 一、设计题目(任选其一) 实验一、哈夫曼编/译码器 二、实验目的 1巩固和加深对数据结构的理解,提高综合运用本课程所学知识的能力; 2 深化对算法课程中基本概念、理论和方法的理解; 3 巩固构造赫夫曼树的算法; 4 设计试验用程序实验赫夫曼树的构造。 三、运行环境(软、硬件环境) Windows xp sp3,Visual C++ 英文版 四、算法设计的思想 (1)初始化赫夫曼树,输入文件中各字符及其权值,并保存于文件中 (2)编码(Coding)。对文件tobetrans中的正文进行编码,然后将结果存入文件codefile 中 (3)D:解码(Decoding)。利用已建好的哈夫曼树将文件codefile中的代码进行译码,结果存入textfile中。 (4)P:打印代码文件(Print)。将文件codefile以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。 1)内容: 利用 Huffman 编码进行通信可以大大提高信道的利用率,缩短信息传输时间,降低 传输成本。但是,这要求在发送端通过一个编码系统对待传数据进行预先编码,在 接收端进行解码。对于双工信道(即可以双向传输信息的信道),每端都需要一个 完整的编/解码系统。 2)要求: 一个完整的huffman编解码系统应该具有以下功能: 初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建 立Huffman 树,并将它存入hfmTree 中。 编码(Encoding)。利用已经建好的Huffman树(如果不在内存,则应从文件hfmTree 中读取),对文件ToBeTran中的正文进行编码,然后将结果存入文件hfmTree中读取),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。 解码(Decoding)。利用已经建立好的Huffman树将文件CodeFile中的代码进行解码, 结果存入TextFile中。 打印代码文件(Print)。将文件CodeFile以紧凑的格式显示在终端上,每行 50 个 代码。同时将此字符形式的编码文件写入文件CodePrint中。 打印Huffman树(Tree Printing)。将已经在内存中的Huffman树以直观的形式(树或者凹入的形式)显示在终端上,同时将此字符形式的Huffman 树写入文件TreePrint中。 3) 测试数据: 用下表给出的字符集和频度的实际统计数据建立Huffman树,并对以下报文进行编码和译码:“THIS PROGRAM IS MY FAVORITE”。 完整代码如下: #include 课程设计任务书 题目:基于哈夫曼编码的图像编解码系统设计及实现 初始条件: 计算机 Windows8操作系统 MATLAB7.8.0软件 要求完成的主要任务: 设计哈夫曼编码的图像编解码系统、利用软件编写程序、仿真实现 时间安排: 第1-18周:理论讲解 第19周:理论设计,实验室安装调试以及撰写设计报告 答辩: 时间:7月2日 地点: 鉴主15楼通信实验室四 指导教师签名:年月日 系主任(或责任教师)签名:年月日 目录 目录........................................................................................................................ I矚慫润厲钐瘗睞枥庑赖。摘要....................................................................................................................... I I聞創沟燴鐺險爱氇谴净。ABSTRACT ......................................................................................................... I II残骛楼諍锩瀨濟溆塹籟。1引言..................................................................................................................... 1酽锕极額閉镇桧猪訣锥。 1.1图像数据压缩的目的.............................................................................. 1彈贸摄尔霁毙攬砖卤庑。 1.2图像数据压缩的原理.............................................................................. 1謀荞抟箧飆鐸怼类蒋薔。 1.3常用的压缩编码方法.............................................................................. 3厦礴恳蹒骈時盡继價骚。2哈夫曼编码......................................................................................................... 3茕桢广鳓鯡选块网羈泪。 2.1 哈夫曼编码简介..................................................................................... 3鹅娅尽損鹌惨歷茏鴛賴。 2.2哈夫曼编码步骤...................................................................................... 3籟丛妈羥为贍偾蛏练淨。 2.3 哈夫曼编码的缺点................................................................................. 5預頌圣鉉儐歲龈讶骅籴。3基于哈夫曼编码的图像编解码系统的程序设计............................................. 6渗釤呛俨匀谔鱉调硯錦。 3.1 分块程序设计分析................................................................................. 6铙誅卧泻噦圣骋贶頂廡。 3.2主程序...................................................................................................... 8擁締凤袜备訊顎轮烂蔷。 3.3程序函数.................................................................................................. 9贓熱俣阃歲匱阊邺镓騷。 3.3.1编码函数....................................................................................... 9坛摶乡囂忏蒌鍥铃氈淚。 3.3.2解码函数..................................................................................... 12蜡變黲癟報伥铉锚鈰赘。 3.3.3符号概率计算函数..................................................................... 14買鲷鴯譖昙膚遙闫撷凄。 3.3.4节点添加函数............................................................................. 14綾镝鯛駕櫬鹕踪韦辚糴。 3.3.5解码返回符号函数..................................................................... 15驅踬髏彦浃绥譎饴憂锦。4系统仿真结果................................................................................................... 15猫虿驢绘燈鮒诛髅貺庑。 4.1程序运行结果........................................................................................ 15锹籁饗迳琐筆襖鸥娅薔。 4.2 程序运行结果分析............................................................................... 17構氽頑黉碩饨荠龈话骛。 5.总结................................................................................................................... 18輒峄陽檉簖疖網儂號泶。参考文献.............................................................................................................. 19尧侧閆繭絳闕绚勵蜆贅。 题目:哈夫曼编码器 班级:031021班姓名:李鑫学号:03102067 完成日期:2011/12 1. 问题描述 利用赫夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个赫夫曼码的编/译码系统。 2.基本要求 一个完整的系统应具有以下功能: (1) I:初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建立赫夫曼树,并将它存于文件hfmTree中。 (2) E:编码(Encoding)。利用已建好的赫夫曼树(如不在内存,则从文件hfmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。 (3) D:译码(Decoding)。利用已建好的赫夫曼树将文件CodeFile中的代码进行译码,结果存入文件Textfile中。 以下为选做: (4) P:印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。 (5) T:印赫夫曼树(Tree printing)。将已在内存中的赫夫曼树以直观的方式(比如树)显示在终端上,同时将此字符形式的赫夫曼树写入文件TreePrint 中。 3.测试 (1)利用教科书例6-2中的数据调试程序。 (2) 用下表给出的字符集和频度的实际统计数据建立赫夫曼树,并实现以下报文的编码和译码:“THIS PROGRAME IS MY FA VORITE”。 字符 A B C D E F G H I J K L M 频度186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符N O P Q R S T U V W X Y Z 频度57 63 15 1 48 51 80 23 8 18 1 16 1 4.实现提示 (1) 编码结果以文本方式存储在文件Codefile中。 (2) 用户界面可以设计为“菜单”方式:显示上述功能符号,再加上“Q”,表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单,直至某次用户选择了“Q”为止。 (3) 在程序的一次执行过程中,第一次执行I,D或C命令之后,赫夫曼树已经在内存了,不必再读入。每次执行中不一定执行I命令,因为文件hfmTree可能早已建好。 目录 目录 (2) 1课程设计的目的和意义 (3) 2需求分析 (4) 3概要设计 (4) 4详细设计 (8) ¥ 5调试分析和测试结果 (11) 6总结 (12) 7致谢 (13) 8附录 (13) 参考文献 (20) . | ; 1 课程设计目的与意义 在当今信息爆炸时代,如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。 哈夫曼编码的应用很广泛,利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径,对路径上的各分支约定:指向左子树的分支表示“0”码,指向右子树的分支表示“1”码,取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码,这就是哈夫曼编码。 通常我们把数据压缩的过程称为编码,解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时,总希望总长度尽可能最短,即采用最短码。 作为计算机专业的学生,我们应该很好的掌握这门技术。在课堂上,我们能过学到许多的理论知识,但我们很少有过自己动手实践的机会!课程设计就是为解决这个问题提供了一个平台。 ( 在课程设计过程中,我们每个人选择一个课题,认真研究,根据课堂讲授内容,借助书本,自己动手实践。这样不但有助于我们消化课堂所讲解的内容,还可以增强我们的独立思考能力和动手能力;通过编写实验代码和调试运行,我们 可以逐步积累调试C程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。 在课程设计过程中,我们不但有自己的独立思考,还借助各种参考文献来帮助我们完成系统。更为重要的是,我们同学之间加强了交流,在对问题的认识方面可以交换不同的意见。同时,师生之间的互动也随之改善,我们可以通过具体的实例来从老师那学到更多的实用的知识。 数据结构课程具有比较强的理论性,同时也具有较强的可应用性和实践性。课程设计是一个重要的教学环节。我们在一般情况下都能够重视实验环节,但是容易忽略实验的总结,忽略实验报告的撰写。通过这次实验让我们明白:作为一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。只有这样,我们的综合素质才会有好的提高。 2 需求分析 课题:哈夫曼编码译码器 ) 问题描述:打开一篇英文文章,统计该文章中每个字符出现的次数,然后以它们作为权值,对每一个字符进行编码,编码完成后再对其编码进行译码。问题补充:1. 从硬盘的一个文件里读出一段英语文章; 2. 统计这篇文章中的每个字符出现的次数; 3. 以字符出现字数作为权值,构建哈夫曼树,并将哈夫曼树的存储 结构的初态和终态进行输出; 4. 对每个字符进行编码并将所编码写入文件然后对所编码进行破 译。 具体介绍:在本课题中,我们在硬盘中预先建立一个文档,在里面编辑一篇文章。然后运行程序,调用函数读出该文章,显示在界面;再调用函数对该文章的字符种类进行统计,并对每个字符的出现次数进行统计,并且在界面上显示;然后以每个字符出现次数作为权值,调用函数构建哈夫曼树;并调用函数将哈夫曼的存储结构的初态和终态进行输出。然后调用函数对哈夫曼树进行编码,调用函数将编码写入文件;再调用对编码进行译码,再输出至界面。至此,整个工作就完成了 3 概要设计。 目录 摘要………………………………………………………………………..………………II Abstract …………………………………………………………………………..………... II 第一章课题描述 (1) 1.1 问题描述 (1) 1.2 需求分析…………………………………………………..…………………………… 1 1.3 程序设计目标…………………………………………………………………………… 第二章设计简介及设计方案论述 (2) 2.1 设计简介 (2) 2.2 设计方案论述 (2) 2.3 概要设计 (2) 第三章详细设计 (4) 3.1 哈夫曼树 (4) 3.2哈夫曼算 法 (4) 3.2.1基本思 想 (4) 3.2.2存储结 构 (4) 3.3 哈夫曼编码 (5) 3.4 文件I/O 流 (6) 3.4.1 文件流 (6) 3.4.2 文件的打开与关闭 (7) 3.4.3 文件的读写 (7) 3..5 C语言文件处理方式…………………………………………………………………… 第四章设计结果及分析 (8) 4.1 设计系统功能 (8) 4.2 进行系统测试 (8) 总结 (13) 致谢 (14) 参考文献 (15) 附录主要程序代码 (16) 摘要 在这个信息高速发展的时代,每时每刻都在进行着大量信息的传递,到处都离不开信息,它贯穿在人们日常的生活生产之中,对人们的影响日趋扩大,而利用哈夫曼编码 进行通信则可以大大提高信道利用率,缩短信息传输时间,降低传输成本。在生产中则可以更大可能的降低成本从而获得更大的利润,这也是信息时代发展的趋势所在。本课程设计的目的是使学生学会分析待加工处理数据的特性,以便选择适当的逻辑结构、存储结构以及进行相应的算法设计。学生在学习数据结构和算法设计的同时,培养学生的抽象思维能力、逻辑推理能力和创造性的思维方法,增强分析问题和解决问题的能力。此次设计的哈夫曼编码译码系统,实现对给定报文的编码和译码,并且任意输入报文可以实现频数的统计,建立哈夫曼树以及编码译码的功能。这是一个拥有完备功能的系统程序,对将所学到的知识运用到实践中,具有很好的学习和研究价值. 关键词:信息;通讯;编码;译码;程序 Abstract This is a date that information speeding highly development and transmit 一、设计思想 程序要求: 利用哈夫曼树对字符串进行编码,要求每个字符有自己唯一的编码。将得到的一串字串译成0、1编码后存到一个文件夹中,然后再从这个文件夹中读出这串编码进行解码。 实现方法: 输入一串字符,要求字符的区间为大写的26个英文字母,将获得的串字符用计算权值的函数(jsquanzhi())进行字符统计,统计出现的字符种数以及每种字符出现的次数,将该种字符出现的次数作为它的权值。将出现的字符的权值和该字符依次分别赋给两个结构体HT和HC,利用HT(节点)权值的大小建立哈夫曼树,首先用选择函数select()函数选择两个权值最小的字符作为叶子节点,创建一个新的节点作为这两个叶节点的父节点,被选中的节点给他的HT[i].parent赋值是他下次不再被选中,父节点的权值为,子节点的权值之和。然后将该将父节点放入筛选区中,再进行选择(被选过的不再被使用),直到所有的节点都被使用,这样一个哈夫曼树就被建立了。根据每个字符在哈夫曼书中的位置来编译每个字符的0、1密文代码,从叶节点判断该叶节点是其父节点的左右字左字为‘0’,右子为‘1’,在判断父节点是上级父节点的左右子直至根节点,将生成的0、1字符串按所表示的字符倒序存入HC相应的字符的bins[]数组。 重新一个一个字符的读取输入的字符串,按照字符出现的顺序将它转为0、1代码并存到一个txt文件夹中去。解码时从文件夹中,一个一个字符的读出那串0、1代码赋给一个临时字符串cd[],用该字符串与每个字符的HC[i].bins密文比较,直到与一个字符的密文相同时,译出该字符,将字符存放在临时字符数组tempstr[]中,清空临时字符串继续读取0、1代码进行翻译,直至文件密文结束为止。于是就得到了原先被加密的那串字符串。哈夫曼树编码译码实验报告(DOC)
哈夫曼编码程序设计
哈夫曼(huffman)编译码器课程设计
哈夫曼编码与译码的实现
数据结构课程设计哈夫曼编码-2
数据结构哈夫曼编码译码器课程设计报告(有源程序)
数据结构课程设计哈夫曼编译码器
数据结构课程设计哈夫曼编码(DOC)
哈夫曼编译码器课程设计报告完整版
哈夫曼编译码器课程设计报告完整版
哈夫曼编解码 完整c程序代码
基于哈夫曼编码的图像编解码系统设计及实现
数据结构课程设计哈夫曼编码
哈夫曼编码译码器---课程设计报告
哈夫曼编码译码系统课程设计实验报告(含源代码C++_C语言)
哈夫曼编码与译码报告