应用数据结构课程设计(哈夫曼树)

1、学号：0120803490117课程设计题目Huffman编/译码命学院管理学院专业信息管理与信息系统班级0801姓名王涛指导教师燕翔课程设计任务书学生姓名：王涛专业班级：信管0801指导教师：燕翔工作单位：管理学院题目：Huffman编/译码器初始条件：利用Huffman编码进行通信可以大大提高信道利用率.缩短信息传输时间，降低 传输成本，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的 数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个 完整的编/译码系统。试为这样的信息收发站写一个Huffman码的编/译码系统。要求完成的主要任务:（包括课程

2、设计工作量及其技术要求、说明书撰写等具体要求）一个完整的系统应具有以下功能：（l ） I :初始化。从终端读入字符集大小 n,以及n个字符和n个权值，建立哈夫 曼树，并将它存于文件 hfmTree中。（2）E：编码。利用已建好的Huffman树（如不在内存，则从文件hfmTree中读入）， 对文件ToBeTran中的正文进行编码，然后将结果存入文件 CodeFile中。（3） D：译码。利用已建好的 Huffman树将文件CodeFile中的代码进行译码，结 果存入文件TextFile（4） P：印代码文件。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。（5） T:印哈夫曼树。

3、将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。时间安排：指导教师签名:系主任（或责任教师）签名:年07月02日在舁 厅P设计内容所用时间1问题分析和任务定义0.5天2数据类型和系统设计0.5天3编码实现和静态检查3天4上机准备和上机调试r 2大5总结和整理设计报告1天合 计7天2010年07月02日1 .需求分析1.1 程序的任务：利用Huffman编码进行通信可以大大提高信道利用率.缩短信息传输时间，降 低传输成本，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将 传来的数据进行译码（复原）。对于双工信道

4、（即可以双向传输信息的信道），每端 都需要一个完整的编/译码系统。此程序就是为这样的信息收发站写一个Huffman码的编/译码系统。1.2 程序的输入和输出：从终端读入字符集大小n,以及n个字符及各个字符的权值，建立赫夫曼树，并 将它存储到文件hfmTree中；利用已建好的赫夫曼树将文件中的字符编码，如果赫 夫曼树不在内存中，则从文件hfmTree中读取到内存；将译得的代码存到文件CodeFile中；利用已建好的赫夫曼树对 CodeFile中的代码进行译码，将结果存入文 件TextFile中；最后将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显 示在终端上，同时将此字符形式的哈夫曼树写入

5、文件TreePrint中。1.3 程序要达到的功能：用户可以利用菜单根据自己的需要来选择要进行编码或是译码，并将转换好的字符或编码以文件的形式存到相应的文件里面。1.4 测试数据如下表：（l）利用教材中的数据调试程序。（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报 文的编码和译码：THIS PROGRAM IS MY FAVORIT E字符ABCDEFGHIJKLMNOPQRSTUVW .XY Z频度186 (54 13 212 32 103 21 15、4757153220576351485180238181161选择 E , 输入 THIS PROGRAMS MY

6、FAVORITE, 屏幕 上显示 110100010110001111110001000101001100001001010101100101110110001111111001 0100011111110011101011000001001001001101101010同时文件codefile里面也出现相应的代码选择D,从codefile 中调入代码，终端显示 THIS PROGRAM IS MY FAVORITE并且文件 textfile 中也相应的存入了这段话。选才 P,文件CodeFile以紧凑格式显示在终端上。选择 T， 将已在内存中的哈夫曼树以直观的方式 (树或凹入表形式) 显示在

7、终端上，同时将此字符形式的哈夫曼树写入文件 TreePrint 中。选择其他的字母，将出现出错提示，并重新回到选择菜单。2 . 概要设计ADT BinaryTree 数据对象D： D是具有相同特性的数据元素集合。数据关系R：若 D 为空，则R 为空，称Huffmantree 为空霍夫曼树；若D不为空，则R=H, H是如下的二元关系：1、 H 满足二叉树的所有要求；2、 H 中所有数乘以该数所在节点的深度值之后和最小。基本操作P：InputHuffman(Huffman Hfm)操作结果：输入并存储字符和相应权值。Select(HuffmanTree HT,int end,int *s1,int

8、 *s2)初始条件：频率数组已经建立。操作结果： 选择 HT1i-1 中无双亲且权值最小的两个节点， 其序号为 s1， s2 。HuffmanCoding(Huffman Hfm)初始条件：频率数组已经建立。操作结果： w 存放 n 个字符的权值 (均 0) ， 构造赫夫曼树HT ，并求出 n 个字符的构造赫夫曼编码HC 。InitHuffman(Huffman Hfm)初始条件：频率数组已经建立。操作结果：要求用户输入字符和相应权值，初始化赫夫曼数Encoding(Huffman Hfm)初始条件：霍夫曼树HuffmanTree 已经存在。操作结果：利用已建好的 Huffman 树(如不在内

9、存，则从文件hfmTree 中读入) ， 对文件ToBeTran 中的正文进行编码，然后将结果存入文件 CodeFile 中。Decoding(Huffman Hfm)初始条件：霍夫曼树HuffmanTree 已经存在。操作结果： 利用已建好的 Huffman 树将文件 CodeFile 中的代码进行译码，结果存入文件 TextFile 中。Print(Huffman Hfm)初始条件：霍夫曼树HoffmanTree 已经存在。操作结果： 将文件 CodeFile 以紧凑格式显示在终端上， 每行 50 个 代码。Treeprint(Huffman Hfm)初始条件：霍夫曼树HuffmanTre

10、e 已经存在。操作结果：将已在内存中的哈夫曼树以凹入表的形式显示在终端上，同时将此字符形式的哈夫曼树写入文件 TreePrint 中。 ADT HuffmanTree2 . 2 主程序流程Void main()显示菜单；Switch(k)I ：初始化E:编码D:译码P:印代码文件T:印哈夫曼树Q退出运行292.3程序调用模块Main函数InitHuffmanEncodingDecodingPrintTreeprintQuit3 .详细设计3.1 数据类型：typedef char *HuffmanCode;动态分配数组存储霍夫曼表码表typedef structunsigned int wei

11、ght;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/动态分配数组存储霍夫曼树typedef structHuffmanTree HT;char *c;int length;HuffmanCode HC;Huffman;/分配数组存储字符串及其对应的霍夫曼树Huffman Hfm;char k; /*控制循环的标志*/3.2 伪码算法：主程序main()InitHuffman(Huffman Hfm)；Encoding(Huffman Hfm)；Decoding(Huffman Hfm)；Print(Huffman Hfm)；Tr

12、eeprint(Huffman Hfm) ；其他模块：/ 选择 HT1i-1 中无双void Select(HuffmanTree HT,int end,int *s1,int *s2) 亲且权值最小的两个节点，其序号为 s1 ， s2FOR (i=1;i*s1IF(HTi.parent 是次最小的 )THEN HTi.parent*s2Huffman HuffmanCoding(Huffman Hfm) /w 存放 n 个字符的权值(均0) ，构造赫夫曼树HT,并求出n个字符的构造赫夫曼编码HCFOR(i=n+1;i=2*n-1;+i) / 选择 HT1i-1 中无双亲且权值最小的两个节点，

13、其序号为 s1， s2Select(Hfm.HT,i-1,&s1,&s2);修改父亲位置；修改孩子位置；父亲结点权值为左右孩子权值之和；/ 从叶子结点到根逆向求每个字符的赫夫曼编码FOR(i=1;i=n;+i)/ 逐个字符求赫夫曼编码 start=n-1;/ 编码结束符位置for(c=i,f=Hfm.HTi.parent;f!=0;c=f,f=Hfm.HTf.parent)/ 从叶子到根逆向求编码IF(c=Hfm.HTf.lchild) cd-start=0;ELSE cd-start=1;再从 cd 复制编码到 Hfm.HCRETURN Hfm;Huffman InitHuffman(Huf

14、fman Hfm)/ 初始化赫夫曼数，要求用户输入字符和相应权值对文件 hfmTree 以读文本的形式打开IF(fp=NULL)调用 InputHuffman 函数，用户输入字符和相应权值存入赫夫曼数中ELSE输出 The Huffmantree has already existed!nPlease choose again!nn);读入 hfmTree 中文本FOR(i=1;i=n;i+)作为独立结点对结点的parent ， lchild ， rchild 分别赋值0FOR(;i=2*n-1;+i)作为独立结点对结点的weight ， parent ， lchild ， rchild 分别

15、赋值0Hfm=HuffmanCoding(Hfm);RETURN Hfm;void Encoding(Huffman Hfm) / 利用已建好的 Huffman 树(如不在内存，则从文件hfmTree 中读入) ，对文件 ToBeTran 中的正文进行编码，然后将结果存入文件 CodeFile 中。输出 nn*Encoding*nnIF(ffp=fopen(ToBeTran,rt)=NULL)提示输入 Please input the sentence:scanf(%s,ch);printf(n);以写文本的形式打开CodeFileELSE读入ToBeTran文件中的字符；WHILE(chj)

16、FOR(i=1;i0， rchild 1 来输出入到文件TextFile 中 关闭文件void Print(Huffman Hfm) /将文件CodeFile以紧凑格式，示在终端上，每行 50个代FOR(i=1;iedseinpu ttlev/eicjhI ofthe匚hdf: 21yeaseinputtlechar: Gedeinpu ttleweigh I ufthechdr: 15easeinputtlechar: H犷easeinputtleweight ofthechar: 4 7yeaseinouttlechar: I.easeinptjltleweight oftheciter:

17、 57easeinputtlechdr: Jeaseinputtleweight ofth电char1 1Pleaseinputtheclidr: KPledgeinputtheghf ofthechar : 5PleaseinputLite仁hd： LPleaseinputtheMdighl ofthechor: 32inpu ttlechar: Keaseinputtweiqhl ofthech： 20J.easeinputtleclidr: NyeaseinputtrewciM ofthechar: 57edseinputtleclidr: 0）：easeinnult1ewei gh1

18、ofthechar: 63easeinputtlechar: Poasoi nou tt10weidhi oft heeh: 15PlPrlsAi np(ittlhpchar: Q3lettseinputIieweight oft hechar:13leaseinputilechar: Rleaseinput1leweight ofihechar:48JlcasoinputtICchar: SPleaseinputtheweight ofchar:51Pleasei nputthechar: T5leasenwti ttieweLuht ofI hechdr:80leaseinpuiiiech

19、ar* Uleaseinputtleweight ofthechar:23Pleaseinputihechar; VPleaseinputtheweight ofthechar:8Plea,sei nptit寸hachrir: U3leaseHWU tIieweight ufI hechar:18leaseinputtlechar: XleaseinputIleweight ofthechar:1Jlcaseinputthechar: VPleaseinputtheweight ofihechar:16PlPrlSPi nputthechar: 2Pleaseinputtheweight of

20、thechar:1图4、5在字符个数处输入“ 27”，之后依次输入各字符及其权值。Jhank Vou To list; MV Huffman PruyrdwI.InitializationF, Fngdi ng l).kcoding P,Printing T.TreePrintQ.Ait!Pierisp Tnuuf ?our OptionEnethnjPl心口士已 ifiput thd i铀rilitncn:在菜单界面选择E,出现提示语句，要求输入句子I Ih.mk Von Io 比： 修.并加 ProoronIII.InitializationC.EikocKiwDDficorlirwP.P

21、r ini ingF.TreefrintQ.ExitPI ease Ir巾ul Vour Un t i atiMFWW H WW+fli 暨*量*片* /Eric口 ding*1 胃洞” 8/-X1Mll1*%m州，*，:f：dsp inpLit the 工印Ibtie; IHIS PROGRFH IS NV FAVDRITfLieiwtai j noti jniiHuuy uoi in 呢 11 即如 i 州 i uio u uui jiiiBiiuBuniiiii aoiyiawuinLlUO8111O191lO00OOtOOlMinill 101910输入“THIS_PROGRAM_IS

22、_MY_FAV。R|TE车之后，显示出该句的哈夫曼编码图8将译出的字符显示出50个。结果如下图:（此处为求简捷，将空格用下划线“ _”作为代替）I Thank Von To Use MV Huffman Program jII.In i 11d1i1i onF.Fncodino DDecodiro P Print inn T,TreePrxnt!O.EHitiPlease Input Vour Option D口”口 d i ng1The file is : THIS PROGRAM IS MY FAVORITE在菜单界面选择D,则对文件中已有的哈夫曼编码进行反译, 来。| Thi?nk Yo

23、u To Lha MV Huffitin ProarLimI.Ini 1inlization|E.Encoding n.npcodirtoP.；Pri niingT.TrRePrint|JU.ExiliPlease JnpuI Vour Op I ionP图 9在菜单界面选择P,将文件中的哈夫曼编码紧凑输出，每行t th白LiMiH ui Lviifl ，rid三触外科- 1 lor. _Ueiyiil.166CMet：111thw 11Nr i ih 1 -64Code;HUQ口ISUeiiL13CM&；制MM忡hflr ：MgM -22Codp 脚oneth Jr- Dlileidit l

24、32Code:10110?hdr 匚Weight;103Code 1eioihtfr- r21Cmle:1UMIHChrtr- G15CodR：i白俱贴iCfl.ir H加曲1klCo Ln hl：心IE1Jeigh-tlC l hT :版fllH/Ei, hrtf23ieiglrt-BIH1-11a禽 iylrt 二irihflluMt-2Jb i kx；34 1 g bt-44 iy ht=9Aigg17ihti前岛:j qht：11Ae iflliltiK足 IghT：后 if|hl?翎.如知h*二b4j-3 jit-A72/LhM：屈 iqhrt：11/4词 Lil ht- , hP-

25、Tircfi t 45nraiS心rm把Gt1 27Faremt4BIaremt 4：36IoJvtit 13writ：孤Firrmt i43Faruii* 二如fdJPVIlt 31F山附而二3Faif&nC iFdLFSflC =43FBiriri Z4434PAremt t20PFemt42rarefit 42Fnrsine 鼎白Fnrevit: S37I-a-rrm t -32K-a-rvtit -鸣FaJrvflt ：FdJPVlt :*11alTt 二2?3HFri PMIIlt M3口PiirAfl t ?31Paretrt i32：J5Pn曰iidt工3HFnreii.t：3薛

26、Paremt t4 3Farem t 黑49rnrefifrt41PrtFFIl t： m4Ia-Tffmt -45v七i4&rfljpvfie ：47P4rmt 47Lern t =48Pm ir 日料4 ：；-1 ?TjcMldUM Id iLehi Id； Lclii Id t Uhild： UhildT Lchild： Lcliild： Uhlldi uhi id； Uhildi Le hi hl iTiChild： Lchildi LcMldi UMlidi LrhildxLehi Id ： LchAldt UlsildT LchildT Uhild：Ida hud： LehilRc

27、hildL：MHclixlift：UIkJiill：耻lll心RciiildzBJklixld：勺融IM,艇 Hldh9Itehildl：等felhild：gRc)illd) =ARclhildl：ARcjhiltl：gRcliildL：修RcHIMmItelhlHzftUchi lii：0Rciixldz修JkJnldLHfell illsw曲 liilM：gftdilld.修ItoJilldL：Ilf曜RchilAs曾9Rell tig12ItehlM：31Iklillfl：ftMEnciiiiti：24Fkhllil:7Itehilrtz22Heli i Id?14jhiiildi13M

28、Zil士如llDtiildlsVUchi IdsRcMld =15lb图14在菜单界面选择T,打印处内存中的哈夫曼树各节点的值及其双亲节点和子节点TEXTFILE -记事本其锹D期I西格式章看M糊画|THI S_PRCKRAB_IS_MY_FAVDRITE图15TEXTFILE.TX”本文件，记录用户输入的需要进行编码的句子4匚8皿a事Mil Wrtra MMmcnoijiiiiimiiiiitn -ujiciciijiioiiOiQOKlimoikuici11utiquonLiniouiiojqihiliicwiii1咖ninMgLiiJLhw/Q图16CODEFILE.TXT：本文件，记录

29、TEXTFILE.TX位本文件中字符的哈弗曼编码。一HfkfTR=E = OK*-*.I Q | 曰一文aH #垃 E； fcj.O) V)里助 H：一27_ 155 A 64 B 13 C 22 D 晓 E 103 F 21 C 15 H 47 I 57 J 1 E 5 L 32It 20 N 57 C 63 F 15 0 1 R 48 3 Ei I 80 Lr S3 V S W 18 X 1 Y 1& 工二图17HFMTREE.TXT本文件，记录输入的各字符及其权值7.附录记录待编码的句子 记录哈夫曼编码 记录字符个数、名称及权值源程序文件名清单：TEXTFILE.TXTCODEFILE.

30、TXTHFMTREE.TXT源代码：#include #include #include #include#include#define NULL 0#define OK 1#define ERROR 0#define OVERFLOW -2#define MAX_NUM 32767#define MAX 60typedef char *HuffmanCode;/ 动态分配数组存储哈夫曼表码表typedef structunsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/ 动态分配数组存储哈夫曼树

31、typedef structHuffmanTree HT;char *c;int length;HuffmanCode HC;Huffman;/ 全局结构体变量，来存储字符与代码void Select(HuffmanTree HT,int end,int *s1,int *s2)/选择 HT1i-1 中无双亲且权值最小的两个节点，其序号为 s1， s2int i;int min1=MAX_NUM;int min2;for (i=1;i=end;i+)/ 遍历查找权值最小的结点 S1if (HTi.parent=0&HTi.weightmin1)*s1=i;min1=HTi.weight;min

32、2=MAX_NUM;for(i=1;iHTi.weight)*s2=i;min2=HTi.weight;Huffman HuffmanCoding(Huffman Hfm) / 存放 n 个字符的权值(均0)，构造哈夫曼树HT,并求出n个字符的构造哈夫曼编码 HCint 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)/ 选择 HT1i-1 中无双亲且权值最小的两个节点， 其序号为 s1 ， s2Select(Hfm.HT,i-1,&s1,&s2);Hfm.H

33、Ts1.parent=i;/修改父亲位置Hfm.HTs2.parent=i;Hfm.HTi.lchild=s1;/修改孩子位置Hfm.HTi.rchild=s2;Hfm.HTi.weight=Hfm.HTs1.weight+Hfm.HTs2.weight;/ 父亲结点权值 为左右孩子权值之和/ 从叶子结点到根逆向求每个字符的哈夫曼编码Hfm.HC=(HuffmanCode)malloc(n+1)*sizeof(char *);/ 分配 n 个字符编码的 头指针向量cd=(char *)malloc(n*sizeof(char);/分配求编码的工作空间cdn-1=0;/ 编码结束符for(i=1

34、;i=n;+i)/ 逐个字符求哈夫曼编码start=n-1;/ 编码结束符位置for(c=i,f=Hfm.HTi.parent;f!=0;c=f,f=Hfm.HTf.parent)/从叶子到根逆向求编码if(c=Hfm.HTf.lchild) cd-start=0;else cd-start=1;Hfm.HCi=(char *)malloc(n-start)*sizeof(char);strcpy(Hfm.HCi,&cdstart);/从 cd 复制编码到 Hfm.HCfree(cd);/ 释放工作空间return Hfm;Huffman InputHuffman(Huffman Hfm)/ 输入函数，控制用户输入字符和相应权值int i,n;pr