算法与数据结构课程设计-哈夫曼编译码系统宾馆客房管理系统.doc

* 实践教学实践教学 * 兰州理工大学兰州理工大学 计算机与通信学院 2015 年秋季学期 算法与数据结构算法与数据结构课程设计课程设计 题 目：哈夫曼编译码系统 宾馆客房管理系统 专业班级：软件工程（2）班 姓 名： 学 号： 指导教师： 成 绩：_ 2 目目 录录 摘摘 要要.3 一一哈夫曼编哈夫曼编译码系统译码系统4 1.采用类语言定义相关的数据类型.4 2.算法设计.5 3.函数的调用关系图5 4.调试分析.9 5.测试结果9 6.源程序（带注释）.12 二二宾馆客房管理系统宾馆客房管理系统.20 1.采用类语言定义相关的数据类型.20 2.算法设计.20 3.函数的调用关系图.20 4.调试分析.22 5.测试结果.22 6.源程序（带注释）.24 总总 结结.30 参考文献参考文献.31 致致 谢谢.32 摘摘 要要 huffman 编码是一种可变长编码方式，是二叉树的一种特殊转化形式。它的原理是： 将使用次数多的代码转换成长度较短的编码，而使用次数少的可以使用较长的编码，并且保 持编码的唯一可解性。本文根据 huffman 编码原理，在详细设计中，根据权值和最小的根本 原则，我们输入要编码的字符集及其它的权值，再根据在概要设计中提到的节点 node 类， 算法 suanfa 类以及主类 jiemian 类，建立哈夫曼树，并进行编码，最后输出哈夫曼编码。 在完成 huffman 编码后，我们利用其构建的哈夫曼编码树来进行译码。与编码过程不同， 译码过程中，我们将用户输入的二进制代码串依次与字符集中的每个字符的编码进行比较， 译出一个字符后，循环比较下一个字符的编码，直到所有二进制码全部译出为止。 在编码和译码的过程中，我们遇到很多问题，诸如算法、语法问题，但我们都通过不断 的分析，和调试将这些问题一一解决，最终建立了一个完整的编/译 近年来，宾馆业迅猛发展，市场的竞争日趋激烈，全面提高宾馆的软件管理水准，已成 为宾馆业发展的当务之急。尤其是对于星级宾馆，既需要完成前台的一些服务工作，还需要 完成后台的管理工作。然而，传统的人工管理模式已经远远不能满足有效、快捷地处理经营 中产生的大量信息数据的需要，从而使得企业决策层无法及时、准确地掌握一线资料，继而 影响对市场进行正确地分析和预测。像沿海城市三星级以上宾馆引进外方管理，使小部分宾 馆管理水准几乎接近或达到国际水平。但对占 80%以上的广大中小型宾馆来说，是难以做到 的。因此，欲在竞争中甩开对手，取得优势，必须在经营、管理、产品、服务等方面具备独 到之处。而对宾馆的经营状况起决定作用的是客房的管理。简单的服务标准已不是制胜的锦 囊，只有管理做到最细微之处，才能让顾客体会到宾馆服务的高标准、高质量，而准确、快 速、周全往往就是最基本的成功要素。 传统的管理方法已经不能适应现代社会的需要，因此采用电脑管理业务、财务等诸 多环节已成为推动宾馆业迅速发展的先决条件，宾馆客房管理信息系统是各大中小型宾馆所 需要使用的一个管理系统。 关键词： 关键词：huffman 编码树；最优二叉树；编码；译码；宾馆客房；管理；顺序 遍历；模块。 一一哈夫曼编译码系统哈夫曼编译码系统 利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。 这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码 （复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码 系统。试为这样的信息收发站编写一个赫夫曼码的编/译码系统。 哈夫曼编码(huffman coding)是一种编码方式，以哈夫曼树即最优二叉树，带权 路径长度最小的二叉树，经常应用于数据压缩。是指使用一张特殊的编码表将源字符（例如 某文件中的一个符号）进行编码。这种方法是由 david.a.huffman 发展起来的。例如，在英 文中，e 的出现概率很高，而 z 的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩 时，e 极有可能用一个位(bit)来表示，而 z 则可能花去 25 个位（不是 26） 。用普通的表示 方法时，每个英文字母均占用一个字节（byte） ，即 8 个位。二者相比，e 使用了一般编码的 1/8 的长度，z 则使用了 3 倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的 估算，就可以大幅度提高无损压缩的比例。 1.1.采用类语言定义相关的数据类型采用类语言定义相关的数据类型 typedef struct unsigned int weight; unsigned int parent, lchild, rchild; htnode, *huffmantree; int weight; int parent; int lchild; int rchild; hnodetype; typedef struct int bitmaxbit; int start; hcodetype; int n=0; void inputfun(hnodetype huffnodemaxnode)/输入叶子节点的个数及权值：初始化函数 2.2.算法设计算法设计 1.构造哈夫曼树，使用静态链表作为哈夫曼树的存储 在构造哈夫曼树时，设计一个结构体数组 huffnode 来保存哈夫曼树的各个结点的 信息，根据二叉树的性质可知，具有 n 个叶子结点的哈夫曼树共有 2n-1 个结点，所以 数组 huffnode 的大小设置为 2n-1，在实际设计过程中，定义符号常量 maxleaf，为最大 的叶节点的个数，然后再定义一个符号常量 maxnode 为 maxleaf*2-1，代表最大的总的 结点的个数。 2求哈夫曼编码时使用一维结构数组 huffcode 作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿叶结点的 双亲链域回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈 夫曼码值。由于一个字符的哈夫曼编码是从根结点到相应叶结点所经过的各个分支所组 成的 0，1 序列，因此先得到的分支代码为所求代码的低位码，后得到的分支代码为所 求编码的高位码。 3.采用文件读写的方式读取结点信息，存入结点信息，减少传递参数带来的不便， 且同时将数据信息有效的保存起来。 3.3.函数的调用关系图函数的调用关系图 开始 从 data1.txt 读取 n 从 data2.txt 读取 huffnode in; while(n20) coutn; inzifui; inhuffnodei.weight; inn; out1.close(); for(i=0;im; out1.close(); fstream out; out.open(“data2.txt“,ios:in); for(int i=0;iabcd; coutn; out1.close(); fstream out2; out2.open(“data2.txt“,ios:in); for(i=0;ihuffnodei.weight huffnodei.lchild huffnodei.rchild huffnodei.parent; for(i=0;im; for(int c=0;csw; coutb; for(int r=b+1;rd; coutn; for(int v=0;vzifuvw; out1.close(); fstream out2; out2.open(“data2.txt“,ios:in); for(v=0;vhuffnodev.weight huffnodev.lchild huffnodev.rchild huffnodev.parent; out2.close(); fstream out3; out3.open(“data3.txt“,ios:in); for(v=0;vhuffcodev.start; for(int u=huffcodev.start+1;uhuffcodev.bitu; out3.close(); ofstream in; in.open(“data4.txt“,ios:trunc);/ios:trunc 表示在打开文件前将文件清空，文件不存在 则创建 couta; len=strlen(a); p=huffnodec.parent; while(p!=-1) c+; p=huffnodec.parent; /求树中结点的总数目为 c,根节点在 huffnode中的下表地址为 c cc=c;/记录当前的下表地址 cout=i while(m3) coutm; while(m) fstream out1; out1.open(“data1.txt“,ios:in); out1n; out1.close(); if(m=1) inputfun(huffnode); creattree(huffnode); codefun(); else if(m=2) if(n=0) coutm; while(m3) coutm; return 0; 二二宾馆客房管理系统宾馆客房管理系统 1.1.采用类语言定义相关的数据类型采用类语言定义相关的数据类型 struct node int count; /指示该房间有多少个房客 char nameone20; /房客 1 的名字 char nametwo20; /房客 2 的名字 int sexone; /房客 1 的性别 -1 代表女，0 代表没有，1 代表男 int sextwo; /房客 2 的性别 int roomnumber; /房间号 roomarray5; 2.2.算法设计算法设计 1.这是一个小型的管理系统，使用结构体数组存储客房的信息。 2一般的管理系统都应该具备插入，修改，查询，删除，浏览，排序，统计，追加等功能， 通过使用一个简易菜单进行执行动作的选择。 3.用函数实现模块化设计，调理清晰，使程序易读写。 4.把程序与文件联系，使数据能存储在磁盘中，更具实用性。 3.3.函数的调用关系图函数的调用关系图 开始 定义静态链表 执行 main 函数 执行 choice 函数 调用 iive_in 函 数 调用 live_away 函数调用 look_through 函 数 调用 live_in_two 函数 调用 live_in_one 函数 结束 4.4.调试分析调试分析 a.在调试过程中的主要问题为程序没有与文件建立联系，所进行的的操作结果在程序运 行结束后不能保存，所以等下次重新打开程序是之前的数据将会丢失。 b.通过对该程序的各项操作的分析：旅客入住，信息查询，旅客入住，信息插入，信息 追加，信息删除的时间复杂度都为 o（1） ，而信息排序，信息统计的时间复杂度为 o（n2）, 所以综合上述操作的时间复杂度为 o（n2） 。 5.5.测试结果测试结果 1. 这是主操作页面调试图 2.这是进行旅客入住操作图 3.这是对已入住旅客信息查询操作图 6.6.源程序（带注释）源程序（带注释） /初始化房间数组 void initarray() int i; for(i=0;i 姓名%s,“,roomaone); if(roomarrayi.sexone = 1) printf(“性别：男“); else if(roomarrayi.sexone = -1) printf(“性别：女“); printf(“n“); else if(roomarrayi.sexone = 0) printf(“当前有 1 位客人- 姓名%s,“,roomatwo); if(roomarrayi.sextwo = 1) printf(“性别：男“); else if(roomarrayi.sextwo = -1) printf(“性别：女“); printf(“n“); else /printf(“当前有两个客人 客人 1： 姓名%s,性别%d 客人 2： 姓名%s,性 别%d n“,roomaone,roomarrayi.sexone,roomatwo,roomarrayi. sextwo); printf(“当前有 2 位客人- 姓名%s,“,roomaone); if(roomarrayi.sexone = 1) printf(“性别：男，“); else if(roomarrayi.sexone = -1) printf(“性别：女，“); printf(“姓名：%s,“,roomatwo); if(roomarrayi.sextwo = 1) printf(“性别：男，“); else if(roomarrayi.sexone = -1) printf(“性别：女，“); printf(“n“); else if(index = 2) printf(“请输入你要查询房客的姓名:“); scanf(“%s“,name); for(i=0;i 姓名%s,性别%d!“,roomaone,roomarrayj. sexone); else printf(“当前有两个客人入住 姓名%s,性别%d 姓名%s,性别%d n“,roomarrayj. nameone,roomarrayj.sexone,roomatwo,roomarrayj.sextwo); void show() system(“color 9f“); printf(“*请选择操作*n“); printf(“ 1.旅客入住n“); printf(“ 2.旅客退房n“); printf(“ 3.信息查询n“); printf(“ 4.退出 exitn“); printf(“请输入你要选择的操作： “); int main() int i= 100; initarray(); printf(“*宾馆信息管理软件*n“); while(i != 4) printf(“n“); show(); scanf(“%d“, switch(i) case 1: fun1(); bre