数据结构课程设计报告-模板.doc

黄淮学院信息工程学院课程设计报告设计题目： 哈夫曼编码/译码系统 姓 名： 学 号： 专业班级： 计算机科学与技术0601（本） 系 （院）： 信息工程学院 设计时间： 20122013学年第一学期 设计地点： 1#615机房 成绩：指导教师签名： 年 月 日² 课程设计目的1、能够更灵活地应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。5.由于现在市场上的加密很为重要,故应当做一个相关的程序,用来解决日常文章的加密与解密工作² 课程设计任务与要求：问题描述打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，对每一个字符进行编码，编码完成后再对其编码进行译码。利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。基本要求一个完整的系统应具有以下功能：（1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。（2）E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3）D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。（4）P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。（5）T：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。测试数据 新建一个.txt文件，用来存放待处理的数据，这些数据为ASCII码值的集合，而且每种字符的数量并不能相同。本实验拟设其中的数据为abbcccdddd.实现提示（1）文件CodeFile的基类型可以设为子界型bit = 0.1。（2）用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示运行Quit。请用户键入一个先把功能符，些功能执行完毕后再经菜单，直至某次用户先把了“E”为止。（3）在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。一 需求分析 这是一个典型的哈夫曼树问题，也是它的一个很有实际应用的问题。在这里关键的问题便是要用清楚这些字符的种类以及它的相应的权值，还应该知道哈夫曼树的建立，以及文件的打开与创建和读写。二 概要设计 首先由于程序中要常用到字符的种类数以及他们的权值，故需用到两个全局变量int charcount,int *w,int *wt对于输入的字符还应当有一个用来存放的缓冲区,因为这里的字符限定为ASCII码，故char buff256，用来存入Huffman译码的HuffmanDecode HDC 设计实现主要功能的函数有：获得字符种类以及权值的子函数BOOL GetWeight();初始化哈夫曼树的子函数BOOL InitHuffmamTree(HuffmanTree HT);创建哈夫曼树的子函数BOOL CreatHuffmanTree(HuffmanTree HT);哈夫曼树保存的子函数BOOL HuffmanTreeWriteIntoFile(HuffmanTree HT);哈夫曼树读取的子函数BOOL HuffmanTreeReadIntoMem(HuffmanTree HT);利用哈夫曼树将字符编码的函数BOOL HuffmanTreeCoding(HuffmanTree HT,HuffmanCode HC); 利用哈夫曼树将字符串译码的函数HuffmanTreeDecoding(HuffmanTree HT,HuffmanCode HC);将哈夫曼树编码打印的函数BOOL HCPrint(HuffmanTree HT,HuffmanCode HC); 将哈夫曼树打印的函数BOOL HTPrint(HuffmanTree HT);将哈夫曼树销毁的函数BOOL DestroyHuffmanTree(HuffmanTree HT,HuffmanCode HC);main()函数中使用一个switch()语句实现菜单作用，用来对各个子函数的调用。程序运行中，为了保持屏幕的清楚和美观，时刻进行清屏也是必要的。抽象数据类型线性表的定义如下：ADT HuffmanTree 数据对象：D=ai| ai ElemSet,i=1,2,3，n,n0数据关系：基本操作：BOOL GetWeight()操作结果：获得字符种类以及权值的。 BOOL InitHuffmamTree(HuffmanTree HT)初始条件：字符的种类数已知操作结果：初始化哈夫曼树BOOL CreatHuffmanTree(HuffmanTree HT)初始条件：哈夫曼树已存在，以及相应的权值。操作结果：创建哈夫曼树BOOL HuffmanTreeWriteIntoFile(HuffmanTree HT)初始条件：哈夫曼树已存在。操作结果：哈夫曼树保存。HuffmanTreeReadIntoMem(HuffmanTree HT)初始条件：哈夫曼树已存在且已知道存储的文件名操作结果：哈夫曼树读取BOOL HuffmanTreeCoding(HuffmanTree HT,HuffmanCode HC)初始条件：哈夫曼树已存在操作结果：利用哈夫曼树将字符编码并显示在屏幕上HuffmanTreeDecoding(HuffmanTree HT,HuffmanCode HC)初始条件：哈夫曼树已存在且已知道其编码操作结果：利用哈夫曼树将字符译码并显示在屏幕上BOOL HCPrint(HuffmanTree HT,HuffmanCode HC)初始条件：已知道其编码操作结果：将字符译码显示在屏幕上并存入文件BOOL HTPrint(HuffmanTree HT)初始条件：哈夫曼树已存在操作结果：将哈夫曼树以直观方式显示在屏幕上并存入文件BOOL DestroyHuffmanTree(HuffmanTree HT,HuffmanCode HC)初始条件：程序中所有的堆操作结果：将程序所占的所有内存释放。三 详细设计1）定义全局变量、结构体：/*声明哈夫曼树结点类型，及树类型*/typedef struct char ver; unsigned int weight; unsigned int lchild,rchild,parent;HTNode ,*HuffmanTree;unsigned int *w=NULL,*wt=NULL;/*声明全局变量w,wt分别存储每个字符对应的个数以及其权值*/int charcount,mode;/*声明全局变量，分别表示出现字符的种类个数，以及所采用的数据给定方式*/char buff256,file25, *charmap;/*用来缓冲输入的字符，以及文件名。charmap用来表示每个叶子结点的下标*/typedef char * HuffmanCode;HuffmanCode HC;2）各主要部分的算法/*主函数的算法如下：*/void main() HuffmanTree HT=NULL; int i,j,action,tag; char flag,*test; while(1) system("cls"); printf("%20s",""); for(i=0;i<40;i+) putchar('*'); putchar('n'); putchar('n'); printf("%26s",""); printf("欢迎使用哈夫曼树编码译码系统!"); putchar('n'); putchar('n'); printf("%21s",""); printf("Vertion 2008.6.22 Author :CaiQinghe"); putchar('n'); putchar('n'); printf("%20s",""); for(i=0;i<40;i+) putchar('*'); putchar('n'); printf("%20s",""); printf("1.本程序可以用来进行加密与解密工作.nn其使用范围为ASCII码中除'n'之外的所有字符.n"); printf("n%20s",""); printf("2.本程序为作者力作,请您在使用时勿必尊重作者的权利.nn"); printf("n%20s",""); printf("3.本程序中的每种数据的权值都应保证是完全不同的。nn"); printf("下面请您任输入一个字符进入程序:nn"); getch(); system("cls"); printf("哈夫曼编译码请选1:nnn"); printf("哈夫曼树打印显示2:nnn"); scanf("%d",&tag); switch(tag) case 1: printf("首先将建立一个哈夫曼树nn"); WeightGet(); HT=InitHuffmanTree();CreatHuffmanTree(HT);printf("你想将该哈夫曼树存入文件吗?'y'/'n'n");getchar();scanf("%c",&flag);if(flag='y'|flag='Y')HuffmanTreeWriteIntoFile(HT);printf("你想将此树打印在屏幕上吗?'y'/'n'n");getchar();scanf("%c",&flag);printf("%c",flag);if(flag='y'|flag='Y')printf("该树用凹凸表可表示为:n");HTPrint(SearchRoot(HT),1,HT);HuffmanTreeCoding(HT);printf("请打印编码并存入文件吗?n'y'/'n'n");getchar();scanf("%c",&flag);if(flag='y'|flag='Y') HCPrint(HT,HC);printf("请选择编码还是译码nn1.编码nn2.译码nn"); scanf("%d",&tag); while(tag<1|tag>2) printf("n你输入的数据非法，请键入一个1-2中的一个数字n"); scanf("%d",&tag); if(tag=1) HuffmanTreeCoding(HT); else HuffmanTreeDecoding(HT); break; case 2: HT=NULL;HT=HuffmanTreeReadIntoMem(HT);printf("该树用凹凸表可表示为:n");HTPrint(SearchRoot(HT),1,HT); printf("请问你要退出这个程序吗?n'y'/'n'n");getchar();scanf("%c",&flag);if(flag='y'|flag='Y')goto out; getch();out:;/*寻找哈夫曼树的根结点下标的算法*/*构建哈夫曼树时求解最小的两个结点的算法*/*统计每个字符的权值的算法*/*初始化哈夫曼树的算法*/*创建哈夫曼树的算法*/*将哈夫曼树写入文件的算法*/*将哈夫曼树读入内存中的算法*/*哈夫曼树编码的算法*/*哈夫曼树译码的算法*/*用来打印生成的哈夫曼编码的算法*/*该函数可用来打印一棵树的凹凸形式的算法*/各部分之间的相互调用关系图示如下： 主函数哈夫曼编译码哈夫曼打印获取权值初始建立哈夫曼选择是否显示该树选择是否打印生成的编码并存入文件将已存在的哈夫曼树调入内存在屏幕上显示该树选择是否退出程序选择是编码还是译码 四 设计与调试分析从上面的算法和调用关系可以看出，这个程序的基本样子已经非常的清楚，但是真正的程序中还要考虑各种限制条件。例如在在从文件中读取信息的时候，可能文件是不存在的，就要给出不存在此文件的提示等。当输入的数据非法时，也应当给出相应的提示。还有就是涉及到返回值得问题和程序中所要用到的变量的问题。在调试的过程中所遇到的问题很多。例如数值的类型不匹配。以及文件的读取和格式的对齐，都不是很容易，往往容易出错。五 用户手册1 本程序可以在vc+6.0 的环境下运行。2 在vc中创建一个C+文件，将源程序复制到.cpp中，编译链接就可以。3 选择编译、运行以后会出现运行界面，选择相应的选项，根据提示即可进行演示。界面如下：注：任意输入一个数据后进入系统，然后根据系统提示操作即可。六 测试成果注：在这里的pp或任意文件都是事先存在的。里面存的是相关的数据。本程序用这些数据来构建相应的哈夫曼树，以及生成相应的哈夫曼编码。注意：在这里的文件名的输入可以不输入辍，因为系统默认为.txt的，不过，也可以输入。例如：此处如果选1，则有：如果选2则有：注意：该文件用来存储已存在的huffmanTree,它的存储是有相应的格式的。其中的ver,weight,lchild,rchild,parent分别占据6，8，8，8，8列。此中，ver为char；其余为unsigned int下边的数据中，第一行表示该树中共有多少个结点，凡是#的表示非叶子结点。七 附录（源程序清单）八.课程设计心得 本次的课程设计做得虽然可以调试过关，但是距我心中的设计还是有一定的距离的。总的说来，还是由于知识掌握地不够扎实。不过，在这次设计中，我还是找到一点自信。就是，以前觉得程序的设计并不是一件很轻松的事情，经过这次设计，我逐渐学会了一些东西发现程序的设计并不是一个很高深的东西。哈夫曼编译码是一个很重要的应用，能将这个算法研究透彻将会有很大的用处。本次程序设计，使我明白了，程序与软件的区别，虽然这个程序不是很大，但他的规模已经不小了，几百行的代码写起来常常感到迷乱，这其实还主要是面向过程编程的思想不够熟练，自顶向下，逐步求精。本程序是由我一人设计的，当然，里面还存在这不少的漏洞，还有一些初期预想的功能并没有能够顺利实现。但是，通过此次编程，找到自信是一点，认识到不足也是很重要的。通过这个简单的程序，使我能够对软件能略窥一斑，在以巩固知识的目的和前题下。这也算是我的意外收获