课程设计报告：哈夫曼编译-码器2.docx

《课程设计报告：哈夫曼编译-码器2.docx》由会员分享，可在线阅读，更多相关《课程设计报告：哈夫曼编译-码器2.docx（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、合肥季晚必算机科学与技木系课程设计报告20122013学年第二学期2013年6月FILE* fp;文件类型指针-int real_n, i, xl, x2; ; real_n用来存放字符集长度-fp二fopen (readfile. txt，rt); 翻开待编码文件-if (IsError(fp)判断是否正确翻开文件- return 0; 翻开文件失败，返回主菜单-real_n=ReadCode (code, fp);从readfile文件读取字符，将字符集合元素存入code数 组，将集合元素个数存入real-fclose(fp);关闭文件-ReadDataWeight_Init (huffm

2、tree, code, real_n);初始化HuffmanTree 中从 1 到 real_n 的元素一InitHuffmanTree (huffmtree, real_n, 2*real_n-l) ;/初始化 HuffmanTree 中 real_n 至 2*real_n的元素-for(i=real_n+l; i=2*real_n-l; i+) (Sleet (huffmtree, i-1, &xl, &x2); 找到权值最小的两个节点，并将其下标值保 存在xl, x2中-huffmtreei. wi = huffmtreeExl. wi + huffmtreex2. wi;/计算双亲节点

3、权值一huffmtree xl. parent = huffmtree x2. parent = i;/计算双亲节点土也土止一huffmtreei. Ichild = xl; huffmtreei. rchild = x2; 计算双亲节点左右孩子地 址-)printf Cnttt成功创立哈夫曼树! n);getchO ;return realn;(12) void Translate (codetype code, huffmtype huffmtree, int real_n)为译码函 数。利用编码文件codefile中的01码找到哈夫曼树中相应的字符并输出。将文件中的编码 字符依次赋值给变

4、量C,假设c为0那么访问当前节点的左孩子。假设c为1那么访问右孩子，假设左 孩子或右孩子的孩子为0那么表示为叶子节点，输出该节点。void Translate (codetype code, huffmtype huffmtree , int real_n)译码函数FILE *fp, *fp2;int i,n=l, real_m;char c, ch1000;fp=fopen (CodeFile. txt，rb);fp2=fopen(writefile. txt，wt);if (IsError(fp) return; i=real_m=2*real_n - 1;while(c=fgetc(fp

5、) != EOF) 依次访问编码文件中的字符(if(c=O)判断字符为0或1 i=huffmtreei. Ichild;将当前节点的孩子地址给ielse i=huffmtreei. rchild;if (huffmtreei. lchild=0) 判断当前节点是否为叶子节点假设是那么输出该字符fputc (codei. c, fp2);chn+=codei. c;i 二 real m;)fclose(fp);fclose (fp2);printf (t);for (i=l;in; i+)在屏幕上显示译码后的文本printf (%c, chi);printf (nttt 完成译码任务);getc

6、hO ;)(13) void display(huffmtype *huffmtree, int real_n)输出哈夫曼树。将哈夫曼树的逻 辑存储位置，以邻接表的存储形式表达。输出时就可以直接输出。首先申请一个linklist 类型的指针数组用来存储头指针。然后将哈夫曼树按曾分开分别存储到邻接表的不同单链表 中，单链表中以尾差法实现隔层字符的存储void display (huffmtype *huffmtree, int real_n) 以直观的形式输出哈夫曼树int i, j, n=20, xl, x2, flag=0;linklist *L100, *p,*q;printf Cttt

7、哈夫曼树为:n)；for(i=l;i=2*real_n-l;i+)huffmtreei. tag=IN;for (i=l;i100;i+)Li=NULL;for(i=real_n+l;inext=NULL;p=L n;if(huffmtreexl. Ichild=0&huffmtreex2. lchild=0) q二(linklist*)malloc(sizeof(linklist);q-c=huffmtreexl. c;q-next=NULL;p-next=q;P=q；q二(linklist*)malloc(sizeof(linklist);q-c=huffmtreex2. c;q-next

8、=NULL;p-next=q;P=q；else if (huffmtreexl. lchild=0)(q= (linklist*)malloc(sizeof (linklist);q-c=huffmtreexl. c;q-next=NULL;p-next=q;PF；)if(huffmtreex2j. lchild=0)q= (1inklist*)malloc(sizeof(linklist);q-c=huffmtreex2. c;q-next=NULL;p-next=q;PF；)n；)for(i=l;inext!=NULL)(for(j=l;jnext-c);Li=Li-next;flag=l

9、;)if(flag) printf(n);getch()：o(14) int main。主函数。通过主函数定义各种变量，利用switch语句实现功能选择的操作int main ()(encodetype encode;int choice; int real_n = 0;codetype codeNN;huffmtype huffmtreeNN;while (1)(system(，cls/，);PRINT ();scanf(%d, fechoice);switch (choice)case 1 :real_n = CreatHuffmanTree ( code, huffmtree); 创立哈

10、夫曼树 break;case 2 :if (realn)Encode(huffmtree, code, encode , real n) ;break;编码并写入到文件case 3 :if (real n)Translate ( code, huffmtree, real_n) ; break;译码并写入到文件case 4 :if(real_n) display(huffmtree, real_n); break;case 5 exit (1);default :printf (ttt 无效输入);getch();break;return 0;三、程序运行截图1、菜单显示G:数据结的、课程设计

11、代码Debug拾天曼编译码exeHuffman编/译码器12 3 442T 文文 入入 写写 树码码 昌蕴译 哈开开 立码码出 建编茕莘 4J 选 图2主菜单显示图2主菜单显示2、建立哈夫曼树G:傲据结的课程设计代取DebugVe夫曼编译码.exJHuffman /译码器人入 写写 树码码 曷蕴译 哈开开 V码码出 建编茕 、 12 3 4人入 写写 树码码 曷蕴译 哈开开 V码码出 建编茕 、 12 3 4选择:工成功创立哈夫曼树!图3成功建立哈夫曼树3、编码G:数据结为课程设计、代码Debug哈夫曼编译码exeHuffman编/译码器、12 3 4Tfl 昌篇译 哈开开 立码码出 建编自人

12、入写写选择：2完成编码-保存至加（1”口81；文件巾图4成功编码并保存4、译码GA数据纲课程设计、代码Debug哈夫曼编译码,exeHuffman编/译码器昌第译 哈开开 立码码出 建编苴 、 、 、 、 12 3 4写写选择：3Different people haue t of money. Sone people dream famous. Sone people dream of选择：3Different people haue t of money. Sone people dream famous. Sone people dream ofdifferent dreams. of

13、liuing a happy going abroad, andSone people dream of making a lolife. Sone people dream of beingso on. But ny drean is different.Maybe you will get a surprise after you knou my drean.完成译码任务图5成功译码并显示译码内容5、显示哈夫曼树iG:赢结为、课程设计代码Debug唱天曼骗译码Huff man编/译码器人入 写写 树码患 昌蓊译日黄夫立码码出出建编 、 、 、 、 、 12 3 4 5为JJJ曼串 4, J

14、 选 z zft#人入写写 树码码 昌镐译 哈开外 立码码出 建编？ 、 、 、 、 12 3 4回图6哈夫曼树的显示6、退出系统数据结为课程设计代码Debug哈夫曼编译码exSHuffman编/译码器选择：4ress any key to continue图7成功退出程序四、测试结果及程序功能分析本程序有一缺点就是只能从文件中读取信息，限制了输入。在功能实现方面，关于哈夫 曼树的直观显示是没有完美的是实现，只能输出叶子节点但是不能完全以树的形式输出。这 是这个程序唯一没能实现的地方。另外在编程实现建立哈夫曼树时，一直没能很好的实现，书上的算法实现不了。之后我 将书上算法的思想弄明白后，分成许

15、多小步骤，逐步实现创立哈夫曼树的功能。在编码与译 码的过程中我参考了许多资料才是功能得以实现。五、用户使用考前须知建立哈夫曼树前需将要编码的文本放在程序根目录下，并以readfile命名。六、参考文献1王昆仑，李红.数据结构与算法.北京：中国铁道出版社，2006年5月。2李建学编著，数据结构课程设计案例精编（用C/C+描述），清华大学出版社2007. 23殷人昆主编，数据结构:用面向对象方法与C+语言描述，清华大学出版社2007.6 4姜仲秋等主编，c语言程序设计，南京大学出版社，1998年12月5徐孝凯，魏荣数据结构，机械工业出版社，1996年6徐孝凯数据结构简明教程，清华大学出版社，199

16、5年7陈文博，朱青数据结构与算法，机械工业出版社，1996年8许卓群，张乃孝，杨冬青，唐世渭数据结构，高等教育出版社，1988年七、程序源代码#include #include #include #include #include #define NN 10000#define M 2*NN-1#define IN 0#define OUT 1#define MAXJNT 32767 typedef struct(int wi;char c; int tag;int parent, Ichild, rchild;Jhuffmtype;typedef char *encodetypeNN+1 ；

17、typedef struct(char c;int times; codetype;typedef struct nodechar c;struct node *next;linklist;void PRINTOprintf（ntt Huffman 编/译码器nH）;printf（Mtt =nH）;printf（ntt 1、建立哈夫曼树 nn）;printf（ntt 2、编码并将编码写入文件n”）；printf（ntt 3、译码并将译码写入文件nn）;printf（Htt 4、输出哈夫曼树n）;printf（ntt5、退出nnn）;printf（ntt 选择:）；int ReadCode(co

18、detype code, FILE* fp) (char c;保存某次从文件中读入字符-intn= 1;记录首次出现字符在数组中的下标-int i;循环变量-int ent = 1;int tag; /标志某次读入字符是否为首次出现字符，tag=l表示是首次出现;tag=O表示本次 读入字符为已有字符while(c = fgetc(fp) != EOF)当文件没有结束0寸读入字符-从fp指向文件中读取字符，存入字符变量中-tag = 1;假设本次读取字符为首次出现字符-for(i=l; in; i+)(if(c=codei.c)如果本次读入字符为存储在下标为i已有字符-(codei.times

19、+;权值加 1-tag=0;标记本字符为已有字符-break;在已有数组元素中找到本次读入字符，结束for(;)循环-)if(tag)/当本字符为首次出现字符时(coden.c = c; 把该字符存入n指向的数组单元中-coden.times = 1;记字符出现次数为1-n+;n指向下一个数组地址-题目、哈夫曼编/译码器【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成 本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据 进行译码(复原)。对于双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编/ 译码系统。试为这样的信

20、息收发站写一个哈夫曼码的编/译码系统。【基本要求】一个完整的系统应具有以下功能：(1)1：初始化(Initialization)。从终端读入字符集大小n ,以及n个字符和n个权 值，建立哈夫曼树，并将它存于文件hfmTree中。(2)E：编码(Encoding)。利用已建好的哈夫曼树(如不在内存，那么从文件hfmTree中读 人)，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。(3)D:译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码, 结果存入文件TextFile中。(4) P：打印代码文件(Print)。将文件CodeFi

21、le以紧凑格式显示在终端上，每行50个 代码。同时将此字符形式的编码文件写入文件CodePrin中。(5)T：打印哈夫曼树(Tree printing)。将已在内存中的哈夫曼树以直观的方式(树或凹 入表形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。【测试数据】(1)利用教科书例6-2中的数据调试程序。(2)用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码:“THIS PROGRAM IS MY FAVORITE”。字符ABCI)EFGHIJKLM频度1866413223210321154757153220字符N0PQRSTUVWXYZ

22、频度5763151485180238181161【选作内容】上述文件CodeFile中的每个0或 1实际上占用了一个字节的空间，只起到示意或)return n-l;返回文件中字符集合的元素个数- void InitHuffmanTreeChuffmtype* huffmtree, int real_n, int real_m)初始化- (int i;for(i = real_n; i = real_m; i+) (huffmtreei.wi = 0;huffmtree|i.c = 0;huffmtreei.tag 二 IN;huffmtreei.Ichild = huffmtreei.rchi

23、ld = huffmtreei.parent = 0;) )void ReadDataWeight_Init(huffmtype* huffmtree, codetype *code, int real_n)获取权值及数值 域值- (int i;for(i = 1; i = real_n; i+)(huffmtreei.wi = codeij.times;huffmtreei.c = codei.c;huffmtreei.tag = IN;huffmtreei.Ichild = huffmtreei.rchild = huffmtreei.parent = 0; )int LeastNode(

24、huffmtype *huffmtree, int max_i)找到最小权值节点地址- (int i,least_i;int max = MAXNT;for(i = 1; i = max_i; i+) 遍历 1 至U max_i 节点- (if(huffmtree|i.wi max & huffmtreei.tag = IN) 假设节点权值比 max 小并且在森林中- (max = huffmtrcci.wi; 刷新 max 值least_i = i; /保存当前节点地址- )huffmtreeleast_i.tag = OUT;/将最小权值节点从森林中移除-return least;返回最小

25、节点地址 void Slect(huffmtype *huffmtree, int max_i, int *xl, int *x2)找到权值最小的两个节点，并将其下标值保 存在xl, x2中- (*xl = LeastNode(huffmtree, max_i);计算合法最下权值下标-*x2 = LeastNode(huffmtree, max_i);/ )void WriteToFile(FILE *fp, encodetype encode, codetype code, int real_n)将编码输出至文件 (int i,j,cnt=l;char codNN, c;FILE *fp2;

26、fp2 = fopen(”readfile.txt*以可读可写形式翻开文件while(c = fgetc(fp2)!= EOF) codcnt+ = c; fclose(fp2);for(i = 1; i ent; i+)(for(j=l ;j=real_n;j+) if(codi=codej.c) break; fprintf(fp,n%sn,encodefj );fclose(fp);)void Encode(huffmtype* huffmtree,codetype code, encodetype encode,int real_n )依据已仓建 的HuffmanTree对字符进行编码

27、-(FILE *fp;char *cd; int i,start, c, p;cd =(char*)malloc(real_n*sizeof(char); /cd用来存放某次运行时当前字符编码cdreaLn - 1 = ;作为字符结束符-for(i = 1; i = rcal_n; i+) 对 rcal_n 个节点进行遍历start = real_n-l;c = i;c保存当前节点地址(下标)-p = huffmtreei.parent;p保存当前节点双亲地址-while(p)start-;计算编码的起始地址-if(huffmtreep.lchild = c)假设当前节点为其双亲的左孩子- c

28、dstart =。； 编码为 0-else 假设为右孩子- cdstart = ,l,; 编码为 1-c = p; 节点前进一p = huffmtreep .parent; 计算前进后节点双亲节点地址-)encodei =(char*)malloc(real_n - start)*sizeof(char); 申请空间用于存放编码- strcpy(encodei, &cdstart); 将本次编码存入 encode 数组中-)free(cd); /释放闲置存储空间-c=i;printf(、”)；for(i=l ;ic;i+)printf(%sn,encodei);fp 二 fopen(CodeF

29、ile.txt wb”);翻开待写入文件-WriteToFile(fp, encode,code, real”);/将 encode 数组中元素写入到文件中-fclose(fp); 关闭文件-printf(Hnttt完成编码并保存至CodeFile.txt文件中)/打印完成编码信息-getch();等待用户输入任意键返回主菜单-) int IsError(FILE *fp)对翻开文件进行出错判断- (if(!fp)(printf(nttt X翻开文件错误n)printf(nttt任意键返回主菜单)getch();return 1;文件翻开失败-)return 0;文件翻开成功-int Crea

30、tHuffmanTree(codetype codelJ, huffmtype *huffmtree)(FILE* fp;文件类型指针-int reaLn,i,xl, x2; /real_n用来存放字符集长度-fp=fopen(nreadfile.txtn, Hrtn);/翻开待编码文件-if(IsError(fp)判断是否正确翻开文件- return 0; 翻开文件失败，返回主菜单-real_n=ReadCode(code, fp);从readfile文件读取字符，将字符集合元素存入code数组，将 集合元素个数存入real_n-fclose(fp); 关闭文件-ReadDataWeight

31、_Init(huffmtree, code, real_n);初始化 HuffmanTree 中从 1 至U real_n 的元素-InitHuffmanTree(huffmtree, real_n, 2*real_n-l);初始化 HuffmanTree 中 real_n 到 2*real_n 的 元素-for(i=real_n+l; i=2*real_n-l; i+)(Slect(huffmtree, i-1, &xl, &x2);找到权值最小的两个节点，并将其下标值保存在x l, x2 中-huffmtreei.wi = huffmtreexl J.wi + huffmtreex2.wi

32、;计算双亲节点权值-huffmtreex 1 .parent = huffmtreex2.parent = i;计算双亲节点地址-huffmtreei.lchild = xl; huffmtreei.rchild = x2; 计算双亲节点左右孩子地址-)printf(Hnttt成功创立哈夫曼树! nH);getch();return real_n;)void Translate(codetype code, huffmtype huffmtree, int real_n) 译码函数(FILE *fp,*fp2;int i,n=l, real m;char c, ch 1000;fp=fopen

33、(nCodeFile.txt; Hrbn);fp2=fopen(writefile.txtn, nwtn);if(IsError(fp) return; i=real_m=2 *real_n - 1;while(c=fgetc(fp) != EOF) (if(c=O) i=huffmtreei.lchild;else i=huffmtreei.rchild;if(huffmtreei .lchild=0)(fputc(codei.c, fp2);chn+=codei.c;i 二 real_m;)fclose(fp);fclose(fp2);printf(ntn);for(i=l;in;i+)p

34、rintf(H%cH,chi);printf(nnttt完成译码任务) getch();)void display(huffmtype *huffmtree,int real_n) 以直观的形式输出哈夫曼树 (int i,j,n=20,xl,x2,flag=0;linklist *L100,*p,*q;printf(nttt 哈夫曼树为:n”);for(i=l;i=2*real_n-l ;i+)huffmtreei.tag=IN;for(i=l ;i100;i+) Li=NULL;for(i=real_n+l ;inext=NULL; p=L n;if(huffmtreexl.lchild=0

35、&huffmtreex2.lchild=0) q=(linklist*)malloc(sizeof(linklist);q-c=huffmtreex l.c;q-next=NULL;p-next=q;p=q;q=(linklist*)malloc(sizeof(linklist);q-c=huffmtreex2 .c;q-next二NULL;p-next=q;p=q;)else if(huffmtreexl.Ichild=O)(q=(linklist*)malloc(sizeof(linklist);q-c=huffmtreex l.c;q-next=NULL;p-next=q;p二q；)if

36、(huffmtree| x2 .lchild=O)(q=(linklist*)malloc(sizeof(linklist);q-c=huffmtreex2 .c;q-next=NULL;p-next=q;p=q;)n-；)for(i=l ;inext!=NULL)(for(j=l;jnext-c);Li=Li-next;flag=l;if(flag) printf(nnn);) getch();)int main()(encodetype encode;int choice; int real_n = 0;codetype codeNN;huffmtype huffmtreeNN;while

37、(l)(system(nclsn);PRINTO;scanf(H%dn,&choice);switch(choice)(case 1 :real_n = CreatHuffmanTree( code, huffmtree); /创立哈夫曼树 break;case 2 :if(real_n)Encode(huffmtree,code, encode ,real_n);break;编码并写入到文件case 3 :if(real_n)Translate( code, huffmtree, real_n); break;译码并写入到文件case 4 :if(real_n) display(huffmt

38、ree,real_n); break;case 5 exit(l);default:printf(nttt 无效输入)getch();break;)return 0;模拟的作用。为最大限度地利用编码存储能力，试改写你的系统，将编码结果以二进制形式 存放在文件CodeFile中。(2)修改你的系统，实现对你的系统的原程序的编码和译码(主要是将行尾符编/译码问 题)。(3)实现各个转换操作的源/目文件，均由用户在选择此操作时指定。一、问题分析及任务定义首先要搞清楚什么是哈夫曼树，然后怎么构建哈夫曼树。利用哈夫曼树进行编码，可以降 低误码率，减少代码量，高效的进行编码任务。利用文件操作从文本中读取文

39、章，并建立哈夫曼树。建好树之后进行编码，将编码写入文件 codefile中，再利用编码文件和已经建好的哈夫曼树进行译码。二、数据结构的选择和概要设计1、数据结构的选择#include #include #include #include #include #define NN 10000#define NN 10000字符个数#define M 2*NN-1#define IN 0#define IN 0#define OUT 1宏定义IN标致变量宏定义OUT标致变量#define MAXJNT 32767 定义最大值 MAX-INTtypedef struct/树的节点类型的定义(int w

40、i;权值变量wichar c; int tag;字符变量ctag为标致变量int parent, Ichild, rchild; /child、rchild 用来存放左右孩子的地址 Jhuffmtype;typedef char *encodetypeNN+1 ；typedef struct存放借点变量的值以及权值的结构体(char c;int times; codetype;typedef struct node输出哈夫曼树时的链表节点类型 char c;struct node *next;Jlinklist;2、概要设计进入哈夫曼编译码系统，首先应先建立哈夫曼树，要能够建立哈夫曼树必须先建

41、立一个 文本文件readfile, txt,系统会根据此文本文件创立哈夫曼树。建好哈夫曼树后可进行编 码操作或者输出哈夫曼树的操作，假设选编码操作后，可继续进行译码操作。假设想停止操作可 在主菜单目录下按5,那么会推出程序。int CreatHuffmanTree (codetype code, huffmtype *huffmtree) 仓建哈夫曼树 void Encode(huffmtype* huffmtree, codetype code, encodetype encode, int real_n ) 依据已创立的HuffmanTree对字符进行编码-void Translate (

42、codetype code, huffmtype huffmtree, int real_n) /译码函 数void display(huffmtype *huffmtree, int real n)以直观的形式输出哈夫曼树1、系统函数流程图图1设计思路流程图2、函数的详细设计思路(1) PRINT。菜单函数，菜单函数就是多个输出语句依次输出 void PRINT0printf (，zttHuffman 编/译码器n);printf=n);printf (z，tt1、建立哈夫曼树 n)；printf (tt2、编码并将编码写入文件n)；printf (tt3、译码并将译码写入文件n)；printf4、输出哈夫曼树n)；printf (tt5、退出 nn)；printf (tt选择：);(2) Readcode ()函数的功能是从文本中读取文章涉及到的字