数据结构课程设计(哈夫曼编译码)(含代码).doc

数据结构课程设计报告哈夫曼编/译码的设计与实现 一、简介1设计目的：通过对简单哈夫曼编/译码系统的设计与实现来熟练掌握树型结构在实际问题中的应用,并能熟悉运用。2问题的描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码。系统具有如下的几个功能：接收原始数据、编码、译码、打印编码规则。 2、 数据结构的设计 1、构造哈夫曼树时使用顺序表作为哈夫曼树的存储结构；/*定义哈夫曼树结点*/typedef struct char data; /存放结点字符 unsigned int weight; /存放结点的权值unsigned int parent,lchild,rchild; /分别存放该结点的双亲、左右孩子的位置huffnode,*hufftree; /动态分配数组存储哈夫曼树 2、求哈夫曼编码时使用一维结构数组作为哈夫曼编码信息的存储。3、 功能设计 本程序包括四个模块，初始化功能模块，建立哈夫曼树的功能模块，建立哈夫曼编码的功能模块，译码的功能模块。 1、初始化功能模块此模块的功能为用户从键盘输入字符个数n，和n个字符及这n个字符对应的权值。 2、建立哈夫曼树的功能模块此模块功能为使用初始化模块中得到的相关数据按照哈夫曼树的算法构建哈夫曼树，并将得到的哈夫曼树存于文件E:C程序哈夫曼树.txt中，将得到的字符的相关编码存于文件E:C程序哈夫曼编码.txt。 3、建立哈夫曼编码的功能模块此模块功能为从模块2中得到的文件E:C程序需要译码的字符串.txt中读入相关的字符信息进行哈夫曼编码，然后将结果 也存入E:C程序需要译码的字符串.txt，同时将用户所输入的字符与其0、1代码串打印到屏幕上。 4、译码的功能模块此模块功能为接收用户输入需要译码的0、1代码串，按照3中建立的哈夫曼编码规则将其翻译成字符集中的字符所组成的字符串形式存入文件E:C程序译码.txt，同时将翻译的结果在屏幕上打印输出。四、界面设计通过使用一个欢迎函数welcome()，在此函数中利用printf函数的功能，设计出如下的欢迎界面：五、 程序设计：程序中使用到的函数共有七个： 1、主函数main()； 2、欢迎界面函数welcome(),此函数实现了一个可以供用户选择的主菜单欢迎界面； 3、构建哈夫曼树函数BuildHuffmantree(),此函数实现了按照建立哈夫曼树的相关算法构建一棵哈夫曼树的功能；4、编码函数HuffmanCoding()，通过调用此函数可以根据用户在上一步中建立的哈夫曼树，对用户输入的字符串进行编码；5、译码函数TranslateCoding(),利用此函数实现对用户输入的0、1代码进行译码的功能； 6、哈夫曼树存盘函数KeepHuffmanTree(),在用户构建哈夫曼树成功之后，程序通过调用此函数对用户所创建的树进行存盘，并在存盘的文件中显示出每一个结点的左右孩子及其权值； 7、哈夫曼编码存盘函数KeepHuffmanCode(),在使用此程序过程中，用户输入的字符串及其相应的编码会被系统通过调用该函数存盘，以便用户查阅。：程序中函数各层次之间的调用关系如下：mainwelcomeBuildHuffmanTreeHuffmanCodingTranslateCodingKeepHuffmanTreeKeepHuffmanCode 、程序流程图开始 输入1 是否覆盖原文件 否 是初始化 输入3输入4输入2 译码退出编码、编写代码期间遇到的问题及其解决办法:问题一：在写程序时，要用到文件操作，有关fopen、fclose和fputs语句的使用不是很清楚，特别是文件的“w”、“r”、“w+”和“wb”的运用，经查阅C程序设计一书有所了解，又请教了几个同学，明白了有关文件的操作。fopen是打开文件，fclose是关闭文件，而fputs是将接收的语段写入文件中。“w”指的是只写文件，“r”指的是只读文件，“w+”是以二进制形式写入文件，“wb”指的是以十进制形式写入文件。问题二：对全局变量的位置不确定，起先把程序中要用到的全局变量N在main函数中定义，结果程序显示有错误，经过不断调试找到了合适的位置，应该紧随头文件之后。 六、运行与测试1、测试的数据及其结果：（1） 令叶子结点个数n为4，权值集合为1,3,5,7，字符集合为A,B,C,D，并有如下对应关系，A-1、B-3、C-5、D-7,得到的编码为A-100、B-101、C-11、D-0.在程序运行中显示为：（2） 令字符数为4,字符及权值有如下对应关系，a-7,b-5,c-2,d-4.得到的编码为a-0,b-10,c-110,d-111.（3） 输入字符串abcd，得到相应的译码序列为010110111输入0、1代码100101110，得到字符串abcd.2、运行与测试期间遇到的问题及其解决办法: 问题一及解决方案： 在编写语句 printf(tt请输入需要编码的字符串:); getchar(); gets(sentence)；开始未写 getchar()语句，结果程序无法正常接收字符串，经请教同学得知，必须有一个getchar函数接收printf后的回车，然后才能正常接收用户输入的字符串。问题二及解决方案：在运行程序时，因为在程序中指定了路径“Ec程序文件名.txt.由于没有在E盘提前建立“c程序”文件夹，导致程序虽然正常运行，但是创建文件失败。原来系统只能自动创建文件，而不能自动创建文件夹，后经过思考，把文件指定路径直接写为“E文件名.txt.问题三及解决方案：整个程序虽然没有语法和编译错误，在运行时候却出现结果不正确，或者根本无法运行。这说明程序在书写过程中可能存在逻辑上的错误。后使用调试工具，按F10，逐句检查，在界面下方会显示各个变量的值的变化情况，以方便找到错误；然后按F11，进入嵌套的子函数，进入子函数后，仍然按F10进行逐句检查。最终解决了问题。七、结论 在哈夫曼编译码的这次课程设计中，我用到了数据结构中的树，具体的说是最优二叉树（哈夫曼树），学会了如何建立一棵哈夫曼树，明白了在建立哈夫曼树之后，为求编码需从叶子节点出发走一条从叶子到根的路径，而为求译码需从根出发走一条从根到叶子节点的路径。此外，我还对有关C语言中文件操作部分有了更进一步的了解和掌握，能够独立正确的使用fprintf、fputs以及fclose语句。当然，在该程序中还存在很多不足之处，比如程序缺少打印哈夫曼树功能，这一点我会在以后的学习中逐渐掌握。八、设计后的思考通过本次课程设计，我感触颇深，原本以为不会太难，可是真正到自己亲手去做的时候才知道原来不是那么容易的，我甚至还去