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

《数据结构课程设计报告-模板.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告-模板.docx（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数据结构课程设计报告-模板 黄淮学院信息工程学院课程设计报告设计题目： 姓 名： 哈夫曼编码/译码系统 学 号：专业班级： 系 （院） ： 设计时间： 设计地点：计算机科学与技术 0601（本） 信息工程学院 20222022 学年第一学期 1#615 机房成绩：指导教师签名：年 月 日-1- 数据结构课程设计报告? 课程设计目的1、能够更灵活地应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解 指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4.用系统的观点和软

2、件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在 此过程中培养他们严谨的科学态度和良好的工作作风。 5.由于现在市场上的加密很为重要,故应当做一个相关的程序,用来解决日常文章的加密与解密工作? 课程设计任务与要求：问题描述 打开一篇英文文章， 统计该文章中每个字符出现的次数， 然后以它们作为权值， 对每一个字符进行编码， 编码完成后再对其编码进行译码。 利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这 要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原） 。对于双工 信道（即可以双向传输信息的信道

3、） ，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈 夫曼编/译码系统。 。 基本要求 一个完整的系统应具有以下功能： （1）I：初始化（Initialization） 。从终端读入字符集大小 n，以及 n 个字符和 n 个权值，建立哈夫曼树， 并将它存于文件 hfmTree 中。 （2）E：编码（Encoding） 。利用已建好的哈夫曼树（如不在内存，则从文件 htmTree 中读入） ，对文件 ToBeTran 中的正文进行编码，然后将结果存入文件 CodeFile 中。 （3）D：译码（Decoding） 。利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码，

4、结果存入文件 TextFile 中。 （4）P：印代码文件（Print） 。将文件 CodeFile 以紧凑格式显示在终端上，每行 50 个代码。同时将此 字符形式的编码写入文件 CodePrint 中。 （5）T：印哈夫曼树（Tree Printing） 。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示 在终端上，同时将此字符形式的哈夫曼树写入文件 TreePrint 中。 测试数据 新建一个.txt 文件，用来存放待处理的数据，这些数据为 ASCII 码值的集合，而且每种字符的数量并不 能相同。本实验拟设其中的数据为 abbcccdddd. 实现提示 （1）文件 CodeFile

5、 的基类型可以设为子界型 bit = 0.1。 （2）用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示运行 Quit。请用户键入一 个先把功能符，些功能执行完毕后再经菜单，直至某次用户先把了“E”为止。 （3）在程序的一次执行过程中，第一次执行 I、D 或 C 命令之后，哈夫曼树已经在内存了，不必再读入。 每次执行中不一定执行 I 命令，因为文件 hfmTree 可能早已建好。-1- 数据结构课程设计报告 一 需求分析 这是一个典型的哈夫曼树问题，也是它的一个很有实际应用的问题。在这里关键的问题便 是要用清楚这些字符的种类以及它的相应的权值，还应该知道哈夫曼树的建立，以及文

6、件的打 开与创建和读写。 二 概要设计首先由于程序中要常用到字符的种类数以及他们的权值， 故需用到两个全局变量 int charcount,int *w,int *wt 对于输入的字符还应当有一个用来存放的缓冲区,因为这里的字符限定为 ASCII 码，故 char buff256，用 来存入 Huffman 译码的 HuffmanDecode HDC 设计实现主要功能的函数有：获得字符种类以及权值的子函数 BOOL GetWeight();初始化哈夫曼树的子 函数 BOOL InitHuffmamTree(HuffmanTree HT);创建哈夫曼树的子函数 BOOL CreatHuffman

7、Tree(HuffmanTree HT);哈夫曼树保存的子函数 BOOL HuffmanTreeWriteIntoFile(HuffmanTree HT);哈夫曼树读取的子函数 BOOL HuffmanTreeReadIntoMem(HuffmanTree HT); 利 用 哈 夫 曼 树 将 字 符 编 码 的 函 数 BOOL HuffmanTreeCoding(HuffmanTree HT,HuffmanCode HC); 利 用 哈 夫 曼 树 将 字 符 串 译 码 的 函 数 HuffmanTreeDecoding(HuffmanTree HT,HuffmanCode HC); 将

8、 哈 夫 曼 树 编 码 打 印 的 函 数 BOOL HCPrint(HuffmanTree HT,HuffmanCode HC); 将哈夫曼树打印的函数 BOOL HTPrint(HuffmanTree HT);将哈夫曼 树销毁的函数 BOOL DestroyHuffmanTree(HuffmanTree HT,HuffmanCode HC);main()函数中使用一个 switch()语 句实现菜单作用，用来对各个子函数的调用。 程序运行中，为了保持屏幕的清楚和美观，时刻进行清屏也是必要的。 抽象数据类型线性表的定义如下： ADT HuffmanTree 数据对象：D=ai| ai El

9、emSet,i=1,2,3，n,n0 数据关系： 基本操作： BOOL GetWeight() 操作结果：获得字符种类以及权值的。 BOOL InitHuffmamTree(HuffmanTree HT) 初始条件：字符的种类数已知 操作结果：初始化哈夫曼树 BOOL CreatHuffmanTree(HuffmanTree HT) 初始条件：哈夫曼树已存在，以及相应的权值。 操作结果：创建哈夫曼树 BOOL HuffmanTreeWriteIntoFile(HuffmanTree HT) 初始条件：哈夫曼树已存在。 操作结果：哈夫曼树保存。 HuffmanTreeReadIntoMem(Hu

10、ffmanTree HT) 初始条件：哈夫曼树已存在且已知道存储的文件名 操作结果：哈夫曼树读取 BOOL HuffmanTreeCoding(HuffmanTree HT,HuffmanCode HC) 初始条件：哈夫曼树已存在 操作结果：利用哈夫曼树将字符编码并显示在屏幕上 HuffmanTreeDecoding(HuffmanTree HT,HuffmanCode HC) 初始条件：哈夫曼树已存在且已知道其编码 操作结果：利用哈夫曼树将字符译码并显示在屏幕上-2- 数据结构课程设计报告BOOL HCPrint(HuffmanTree HT,HuffmanCode HC) 初始条件：已知道

11、其编码 操作结果：将字符译码显示在屏幕上并存入文件 BOOL HTPrint(HuffmanTree HT) 初始条件：哈夫曼树已存在 操作结果：将哈夫曼树以直观方式显示在屏幕上并存入文件 BOOL DestroyHuffmanTree(HuffmanTree HT,HuffmanCode HC) 初始条件：程序中所有的堆 操作结果：将程序所占的所有内存释放。 三 详细设计1）定义全局变量、结构体： /*声明哈夫曼树结点类型，及树类型*/ typedef struct char ver; unsigned int weight; unsigned int lchild,rchild,paren

12、t; 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()

13、HuffmanTree HT=NULL; int i,j,action,tag; char flag,*test; while(1) -3- 数据结构课程设计报告system(cls); printf(%20s,); for(i=0;i40;i+) putchar(*); putchar(n); putchar(n); printf(%26s,); printf(欢迎使用哈夫曼树编码译码系统!); putchar(n); putchar(n); printf(%21s,); printf(Vertion 2022.6.22 Author :CaiQinghe); putchar(n); put

14、char(n); printf(%20s,); for(i=0;i40;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); print

15、f(哈夫曼编译码请选 1:nnn); printf(哈夫曼树打印显示 2:nnn); scanf(%d,&tag); switch(tag) case 1: printf(首先将建立一个哈夫曼树nn); WeightGet(); HT=InitHuffmanTree(); CreatHuffmanTree(HT); printf(你想将该哈夫曼树存入文件吗?y/nn); getchar(); scanf(%c,&flag); if(flag=y|flag=Y) HuffmanTreeWriteIntoFile(HT); printf(你想将此树打印在屏幕上吗?y/nn); getchar();

16、 scanf(%c,&flag);-4- 数据结构课程设计报告printf(%c,flag); if(flag=y|flag=Y) printf(该树用凹凸表可表示为:n); HTPrint(SearchRoot(HT),1,HT); HuffmanTreeCoding(HT); printf(请打印编码并存入文件吗?ny/nn); getchar(); scanf(%c,&flag); if(flag=y|flag=Y) HCPrint(HT,HC); printf(请选择编码还是译码nn1.编码nn2.译码nn); scanf(%d,&tag); while(tag2) printf(n

17、你输入的数据非法，请键入一个 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(请问你要退出这个程序吗?ny/nn); getchar(); scanf(%c,&flag); if(flag=y|flag=Y) goto out; ge

18、tch(); out:; -5- 数据结构课程设计报告/*寻找哈夫曼树的根结点下标的算法*/*构建哈夫曼树时求解最小的两个结点的算法*/*统计每个字符的权值的算法*/*初始化哈夫曼树的算法*/*创建哈夫曼树的算法*/*将哈夫曼树写入文件的算法*/*将哈夫曼树读入内存中的算法*/*哈夫曼树编码的算法*/*哈夫曼树译码的算法*/*用来打印生成的哈夫曼编码的算法*/*该函数可用来打印一棵树的凹凸形式的算法*/各部分之间的相互调用关系图示如下：-6- 数据结构课程设计报告主函数哈 夫 曼 编 译 码哈 夫 曼 打 印获取权值初始建立哈夫曼选择是否显示该树选择是否打印生成的编码并存入文件将 已 存 在

19、的 哈 夫 曼 树 调 入 内 存在屏幕上显示该树 选择是编码还是译 码选择是否退出程序四 设计与调试分析从上面的算法和调用关系可以看出，这个程序的基本样子已经非常的清楚，但是真正的程序中还要考 虑各种限制条件。例如在在从文件中读取信息的时候，可能文件是不存在的，就要给出不存在此文件的提示 等。当输入的数据非法时，也应当给出相应的提示。 还有就是涉及到返回值得问题和程序中所要用到的变量的问题。在调试的过程中所遇到的问题很多。 例如数值的类型不匹配。以及文件的读取和格式的对齐，都不是很容易，往往容易出错。五 用户手册1 本程序可以在 vc+6.0 的环境下运行。 2 在 vc 中创建一个 C+文件，将源程序复制到.cpp 中，编译链接就可以。 3 选择编译、运行以后会出现运行界面，选择相应的选项，根据提示即可进行演示。界面如下：-7- 数据结构课程设计报告注：任意输入一个数据后进入系统，然后根据系统提示操作即可。六 测试成果-8- 数据结构课程设计报告-9- 数据结构课程设计报告注：在这里的 pp 或任意文件都是事先存在的。里面存的是相关的数据。本程序用这些数据来 构建相应的哈夫曼树，以及生成相应的哈夫曼编码。注意：在这里的文件名的输入可以不输入辍，因为系统默认为.txt 的，不过，也可以输入。例 如：- 10 -