数据结构课程设计：哈夫曼编码实践

《数据构造与算法》课程设计（学年第二学期第周）2023/202320指导教师王老师班级计算机科学与技术（）班3学号姓名

四、概要设计问题分析哈夫曼树的定义1I哈夫曼树节点的数据类型定义为

1.typedef struct{〃赫夫曼树rJ构造体char ch;int weight;〃权值int parent,lchild,rchild;}htnode,*hfmtree;所实现的功能函数如下2J、初始化哈夫曼树，处理1void hfmcodinghfmtree HT,hfmcode HC,int nInputHuffman HuffmanHfm函数得到的数据，按照哈夫曼规则建立叉树此函数块调用了函数2Select

2、void Selecthfmtree HT,int a,int*pl,int*p2//Select函数，选出HT树到a为止，权值最小且为区|个节点parent

02、（）2int main主函数运用已建好日勺哈夫曼树（如不在内存，则从文献中读入）hfmtree.txt对文献中的正文进行编码，然后将成果存入文献中假如正文中没有要编码日勺字符，则键盘读入codefile,txt并存储到文献中读入中将要编码的内容，将编码好区哈夫曼编码存储到中ToBeTran ToBeTranI CodeFile、3Encoding编码功能对输入字符进行编码、4Decoding译码功能运用已建好日勺哈夫曼树将文献中的代码进行译码，成果存入文献中codefile,txt textfile,dat（）打印功能函数输出哈夫曼树，字符，权值，以及它对应的编码Print.主函数日勺简要阐明，主函数重要设计的是一种分支语句，让顾客挑选所实现的功能5使用链树存储，然后分别调用记录频数函数，排序函数，建立哈夫曼函数，编码函数，译码函数来实现功能）系统构造图（功能模块图）2五.程序阐明

1.哈夫曼编码/译码器源代码#includeiostream.h#includestdio.h#includestdlib.h#includestring.h#includefstream.h//赫夫曼树的构造体typedef struct{Ichar ch;〃权值int weight;int parent,lchild,rchild;}htnode,*hfmtree;typedef char**hfmcode;void SelecthfmtreeHT,int a,int*pl,int*p2//Select函数，选出HT树到a为止，权值最小且parent为0U勺2个节点int i,j,x,y;forj=l;j=a;++j{ifHT[j].parent==0{x=j;break;fori=j+1;i=a;++i{ifHT[i].weightHT[x].weightHT[i].parent==O{〃选出最小的节点x=i;forj=l；j=a;++j{ifHT[j].parent==Ox!=j{y=j；break;fori=j+1;i=a;++iifHT[i|.weightHT[y].weightHT[i].parent==Ox!=i〃选出次小胜节点y=i;I}ifxy{*pl=y;*p2=x;else*pl=x;*p2=y;}〃构建赫夫曼树并求出个字符的赫夫曼编码void hfmcodinghfmtreeHT,hfmcode HC,int nHT,n HCint i,start,c,f,m,w;int pl,p2;char*cd,z;ifn=l{return;m=2*n_l;HT=hfmtreemallocm+l*sizeofhtnode;〃初始化个叶子结点fori=l;iv=n;++i nprintf请输入第％d字符信息和权值:1;scanfn%c%dn,z,w;whilegetchar!=,\n,continue;HT[i].ch=z;HT[i].weight=w;HT[i].parent=O;HT[i].lchild=O;HT[i].rchild=O;}//初始化其他的结点for;i=m;++iHT|i].ch=,0,;HT[i].weight=O;HT[i].parent=O;HT[i].lchild=O;HT[i].rchild=O;}〃建立赫夫曼树fori=n+1;i=m;++iSelectHT,i-l,pl,p2;HT[p1].parent=i;HT[p2].parent=i;HT[i].lchild=pl;HT[i].rchild=p2;HT[i].weight=HT[p1].weight+HT[p2].weight;HC=hfmcodemallocn+l*sizeofchar*;fori=l;i=n;++i〃给n个字符编码cd=char*mallocn*sizeofchar;start=n-1;forc=i,f=HT[i].parent;f!=O;c=f,f=HT[f].parentifHT[f].lchild=ccd[--start]=O;elsecd[—start]-T;HC[i]=char*mallocn-start*sizeofchar;strcpy HC[i],cd[start];}freecd;int main{char code

[100],h

[100],hl

[100];int n,i,j,k,l;〃文献输入输出流ifstream input_file;ofstream output_file;char choice,str

[100];hfmtreeHT;hfmcode HC;cout«n\nn;cout«n计算机3班“v n«nQ07620307n«HH«nXXX\nn;cout«H//tf****1*****1****赫夫曼编码/译码器■卜•卜•卜•卜•卜•卜♦[、一]、•.、•卜•卜•卜•[、whilechoice!=,Qchoice!=q〃当choice时值不为q且不为Q时循环cout«,,«HLInitn«u n«nE.Encodingn«nn«HD.DecodingH«n n«,Q.Exit\nn;〈”请输入您要操作的环节”；coutcin»choice;ifchoice==,r||choice==,i,〃初始化赫夫曼树〈”请输入字符个数”；coutvcin»n;hfmcodingHT,HC,n;fori=l;i=n;4-+icout«HT[i].ch«H:n«HC[i]«endl;output_file.open,hfmTree.txtH;if!output_file{cout«ncan,t oenfile!H«endl;return1;fori=l;i=n;i++output_file«,,n«HT[i].ch«HC[i]«,,n;output_file.close;赫夫曼树已经创立完毕，并且已经放入文献中coutvv”hfmTree.txt!”endl;else ifchoice==,E||choice==,e〃进行编码，并将字符放入ToBeTran.txt,码值放入中CodeFile.txt请输入字符”；printffgetsstr;output_file.opennToBeTran.txtH;if!output_filecout«ncan,t oenfile!H«endl;return1;output_file«str«endl;output_file.close;output_file.openHCodeFile.txtH;if!output_file{cout«,,can,t oenfile!«endl;return1;fori=O;istrlenstr;i++{《数据构造与算法》课程设计目录序言

1.摘要

2.《数据构造与算法》课程设计任务书、试验目的、题目一赫夫曼编码/译码器

1.问题描述

2.基本规定

3.测试规定

4.实现提醒

四、需求分析一详细规定

五、概要设计

六、程序阐明

七、详细设计

八、试验心得与体会forj=0;j=n;++jifHT[j].ch==str[i]output_file«HC[j];break;output_file.close;cout«n\nn;cout«”编码完毕，并且已经存入CodeFile.txt文献！\nn;input_file.opennCodeFile.txtn;〃从CodeFile.txt中读入编码，输出在终端if!input_file{cout«ncan*t oenfile!H«endl;return1;input_file»code;coutvv”编码码值为n«code«endl;input_file.close;else ifchoice==,D||choice=d,〃读入CodeFile.txt中Utl编码进行译码，将译出来的字符放入中Textfile.txt{input_file.openHCodeFile.txtn;if!input_file{cout«ncan,t oenfile!H«endl;return1;input_file»h;input_file.close;output_file.opennTextfile.txtn;if!output_file{cout«,,can,t oenfile!n«endl;return1;k=0;whileh[k]!=,\0,〃先用编码中的I前几种和字符的I编码相比较，然后往后移fori=l;i=n;i++{l=k;forj=0;jstrlenHC[i];j++,l++{hlU]=h[l];hl[j]=\O；ifstrcmpHC[i],hl==Ooutput_file«HT[i].ch;k=k+strlenHC[i];break;output_file.close;input_file.opennTextfile.txtH;if!input_file{cout«ncan,t oenfile!H«endl;return1;input_file»h;cout«h«endl;input_file.close;cout译码结束，字符已经存入Textfile.txt文献中！endl;else ifchoice==Q||choice==q〃退出程序exitO;}〃假如选了选项之外的就让顾客重新选择else{cout您没有输入对的的环节，请重新输入！n«endl;cout«endl;return0;六.调试分析，c\E:\E08620305\Debug\E

08620305.exe《信息扉口权且U23U8W18X1y16z iA64且信息不口权信息扉注信息不口权且且E100F01010G110110H0110子息牛口权且I1010K0011110L0010M01000N11000:1110P110111Q001111110R0111S10111:000U01011U田口权00111011:01001X00111111100110信信息口杈目且Z00111110信息不口权赫夫曼树己经创建完毕，并且己经放入文件中:hfehee.txt编码I.In itE.Encoding D.Decoding Q.Exit萼修霍呼的步骤:E褊码完毕，并且已经存入文件！编码科值为Co deFile.txt0I.Init E.Encoding D.Decoding Q.Exit请揄入您詈操作的步骤E请输入字符THISPROGRAME ISMY FOUERITEXXXXXXXXXXXXXXXXXXXXXXXX X市市夫易编码码XX XX XXX XXX XXX XXX XXX XXX XXXMocmR1231112222xxxxxxli78B9W04+443+-{编码兀毕，并且已经存入文件！Co deFile.txt多扁码码值为、译码巾夫管编码/举电马jXXXXMXXXXXXMXXXXXXMXXXXX哧I.Init E.Encoding D.Decoding Q.ExitIIHISPROGRAMEISMVFOUERITE青输入您要操作的步骤D译码结束，字符己经存入文件中!Text file.txt、退出，，，，，市京夫寻褊科半码莒Mm WX XXXXXXXXXX XX WXXXX XXX关X3XXWXX XXX,）＜）（聚X关XXX,）＜美/fI.In itE.Encoding D.Decoding Q.Exit请输入您要操作的步骤Q Pressany keyto continue七.试验心得与体会在我自己课程设计中，就在编写好源代码后区调试中出现了不少的错误，碰到了诸多麻烦及困难,我的调I试及其中的错误和我最终找出错误，修改为对的日勺可以执行的程序中，通过度析，我学到了在定义头文献时可多不可少，即我们可多写些头文献，肯定不会出错，不过若没有定义所引用日勺有关头文献，必然调试不通过；在执行译码操作时，不知什么原因，总是不能把要编译的二进制数与编译成的字符用连接号连接起来，而是按次序直接放在一起，视觉效果不是很好尚有就是，很遗憾的是，我们的哈夫曼编码/译码器没有像老师I规定的那样完毕编一种文献的功能，这是我们设计的失败之处通过本次数据构造的课程设计，我学习了诸多在上课没懂日勺知识，并对求哈夫曼树及哈夫曼编码/译码日勺算法有了愈加深刻的理解，更巩固了课堂中学习有有关哈夫曼编码的知识，真正学会一种算法了当求解一种算法时，不是拿到问题就不加思索地做，而是首先要先对它有个大概日勺理解，接着再详细地分析每一步怎么做，无论自己此前与否有处理过相似日勺问题，只要按照以上日勺环节，必然会顺利地做出来这次课程设计，我在编辑中犯了不应有日勺错误，设计记录字符和合并时忘掉应当怎样保留数据，对文献的操作也很生疏在不停分析后明确并改正了错误和疏漏，我的程序有了更高的质量考核成绩评估表指导教师考核成绩答辩成绩总成绩签字:摘要

1.伴随计算机的普遍应用与日益发展，其应用早已不局限于简朴的数值运算，而波及到问题的分析、数据构造框架的设计以及设计最短路线等复杂的非数值处理和操作算法与数据构造的学习就是为后来运用计算机资源高效地开发非数值处理日勺计算机程序打下坚实的理论、措施和技术基础算法与数据构造意在分析研究计算机加工的数据对象的特性，以便选择合适的数据构造和存储构造，从而使建立在其上的处理问题的算法抵达最优数据构造是在整个计算机科学与技术领域上广泛被使用的术语它用来反应一种数据日勺内部构成,即一种数据由那些成分数据构成，以什么方式构成，呈什么构造数据构造有逻辑上及数据构造和物理上的数据构造之分逻辑上的数据构造反应成分数据之间的逻辑关系，而物理上时数据构造反应成分数据在计算机内部的存储安排数据构造是数据存在的形式《数据构造》重要简介某些最常用的数据构造，阐明多种数据构造内在日勺逻辑关系，讨论其在计算机中日勺存储体现，以及在其上进行多种运算时的实现算法，并对算法的效率进行简朴日勺分析和讨论数据构i i造是介于数学、计算机软件和计算机硬件之间的一门计算机专业的关键课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等多种领域学习数据构造是为了将实际问题中所波及日勺对象在计算机中体现出来并对它们进行处理通过课程设计可以提高学生的思维能力，增进学生的综合应用能力和专业素质的提高《数据构造与算法》课程设计任务书

2.《数据构造与算法》是计算机专业重要日勺关键课程之一，在计算机专业日勺学习过程中占有非常重要日勺地位《数据构造与算法课程设计》就是要运用本课程以及到目前为止日勺有关课程中的知识和技术来处理实际问题尤其是面临非数值计算类型口勺应用问题时，需要选择合适的数据构造，设计出满足一定期间和空间限制的有效算法本课程设计规定同学独立完毕一种较为完整的应用需求分析并在设计和编写具有一定规模程序时过程中，深化对《数据构造与算法》课程中基本概念、理论和措施的理解；训练综合运用所学知识处理实际问题的能力，强化面向对象日勺程序设计理念；使自己的程序设计与调试水平有一种明显的提高

二、试验目的数据构造作为一门学科重要研究数据欧多种逻辑构造和存储构造，以及对数据的多种操作因此,重要I有三个方面日勺内容数据的逻辑构造；数据的物理存储构造；对数据的操作（或算法）一般，算法的I II设计取决于数据的逻辑构造，算法的实现取决于数据的物理存储构造数据构造是信息的一种组织方式，其目日勺是为了提高算法日勺效率，它一般与一组算法日勺集合相对应，通过这组算法集合可以对数据构造中口勺数据进行某种操作在当今信息时代，信息技术己成为现代知识经济的关键技术我们时刻都在和数据打交道例如人们在外出工作时找最短途径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系实际上，现实世界中的实体通过抽象后来，就可以成为计算机上所处理的数据数据构造课程重要是研究非数值计算口勺程序设计问题中所出现的计算机操作对象以及它们之间欧关系和J操作的学科数据构造是介于数学、计算机软件和计算机硬件之间的一门计算机专业日勺关键课程,它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等多种领域学习数据构造是为了将实际问题中所波及日勺对象在计算机中体现出来并对它们进行处理通过课程设计可以提高学生的思维能力，增进学生的综合应用能力和专业素质勺提高通过本次课程设计重要抵达如下目时:H理解并掌握数据构造与算法的设计措施，具有初步的独立分析和设计能力；♦初步掌握软件开发过程勺问题分析、系统设计、程序编码、测试等基本措施和技能；♦H提高综合运用所学的理论知识和措施独立分析和处理问题的能力；♦训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具有口勺科学的工♦作措施和作风

三、题目■赫夫曼编码/译码器1问题描述.运用赫夫曼编码进行通信可以大大提高信道运用率，缩短信息传播时间，减少传播成本这规定在发送端通过一种编码系统看待传播数据预先编码，在接受端将传来的数据进行译码复原对于双工信道即可以双向传播信息的信道，每端都需要一种完整的编/译码系统试为这样的信息收发站编写一种赫夫曼码的编/译码系统

2.基本规定一种完整勺系统应具有如下功能H11初始化Initialization从终端读入字符集大小n,以及n个字符和n个权值，建立赫夫曼树，并将它存于文献中hfmTree22E编码Encoding运用已建好欧J赫夫曼树如不在内存，则从文献hfmTree中读入，对文献ToBeTran中％正文进行编码，然后将成果存入文献中I CodeFile3D译码Decoding运用已建好日勺赫夫曼树将文献CodeFile中日勺代码进行译码，成果存入文献Textfile中如下为选做4P印代码文献Print将文献CodeFile以紧凑格式显示在终端上，每行50个代码同步将此字符形式的I编码文献写入文献中CodePrin5T印赫夫曼树Tree printingo将已在内存中的赫夫曼树以直观日勺方式例如树显示在终端上,同步将此字符形式的赫夫曼树写入文献中TreePrint测试规定

3.已知某系统在通信联络中只也许出现八种字符,其频率分别为试设计赫夫

10.05,

0.29,

0.07,

0.08,

0.14,

0.23,

0.03,

0.11,曼编码用下表给出附字符集和频度的实际记录数据建立赫夫曼树，并实现如下报文日勺编码和译码2“THISPROGRAME ISMY FAVORITE”字符A BC DE FG HI JK LM频度1866413223210321154757153220字符N0P QR ST UV WX YZ频度5763151485180238181161实现提醒

4.编码成果以文本方式存储在文献中1Codefile2顾客界面可以设计为“菜单”方式显示上述功能符号，再加上“Q”，体现退出运行Quit请顾客键入一种选择功能符此功能执行完毕后再显示此菜单，直至某次顾客选择了为止在程序日勺一次执行过程中，第一次执行或命令之后，赫夫曼树已经在内存了，不必再读入3I,D C每次执行中不一定执行命令，由于文献也许早已建好I hfmTree

四、详细规定课程设计成果勺内容必须由如下四个部分构成，缺一不可H上交源程序学生按照试验题目的详细规定所开发的所有源程序应当放到一种文献夹中；1上交程序的阐明文献保留在中在阐明文档中应当写明上交程序所在的目录，上交程序的主程序文

2.txt献名，假如需要安装，要有程序的安装使用阐明；设计汇报保留在文档中，文献名规定按照“姓名—学号—设计题目”起名，如文献名为“张3word三赫夫曼编码打印稿用纸_XXX_doc A4其中包括题目；♦试验目的；♦需求分析在该部分中论述实现的功能规定；♦J概要设计:在此阐明每个部分的算法设计阐明（可以是描述算法的流程图），每个程序中使用欧存储构造设计阐明I（假如指定存储构造请写出该存储构造的定义）；详细设计♦各个算法实现的源程序，对每个题目要有对应的源程序（可以是一组源程序，每个功能模块采用不同样H勺函数实现）源程序要按照写程序的规则来编写要构造清晰，重点函数口勺重点变量、重点功能部分要加上清晰的程序注释；调试分析♦测试数据，测试输出的成果，时间复杂度分析，和每个模块设计和调试时存在问题区思索（问题是哪些？I问题怎样处理？），算法的改善设想；总结♦总结可以包括设计过程勺收获、碰到问题及处理问题过程的思索、程序调试能力的思索、对数据构造H这门课程欧思索、在设计过程中对《数据构造》课程的认识等内容I

（4）考核成绩评估原则本课程设计的评价由三部分构成，包括程序演示（50%）,课程设计汇报（30%）,回答教师提问（20%）程序演示

1.优功能完善，所有测试对时，并且可以对局部进行完善良功能完善，但测试欠缺中功能基本完善，但程序尚有部分错误及格完毕内存中赫夫曼编码/译码，但不波及文献操作不及格功能不完善，且程序错误较多，无法运行课程设计汇报:

2..优包括设计内容，设计思想，已经完毕的任务及抵达的目的，设计思绪清晰、书写1条理清晰，源程序构造合理、清晰，注释阐明完整，有对本次课程设计日勺心得体会良包括设计内容，设计思想，已经完毕的任务及抵达的目勺，设计思绪基本清晰、

2.H书写条理基本清晰，源程序构造合理、清晰，注释阐明基本完整，有对本次课程设计的心得体会中课程设计汇报内容基本完整，思绪较清晰，书写基本清晰，源程序构造尚可，有

3.注释阐明但不完整及格课程设计汇报内容基本完整，思绪较差，书写尚清晰

4.不及格课程设计汇报内容不完整，书写没有条理

5.回答教师提问

6.优能回答教师提出的所有问题，并完全对的思绪清晰

1.I,良基本能回答教师提出的所有问题，有些小错误

2.I中基本能回答教师提出的问题，少数问题回答错误或不清晰

3.及格能回答教师提出的问题，但较多问题回答错误或不能回答

4.不及格基本不能回答教师提出日勺问题5,。