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

《算法与数据结构课程设计哈夫曼编译码系统宾馆客房管理系统.doc》由会员分享，可在线阅读，更多相关《算法与数据结构课程设计哈夫曼编译码系统宾馆客房管理系统.doc（32页珍藏版）》请在三一文库上搜索。

1、* 实践教学实践教学 * 兰州理工大学兰州理工大学 计算机与通信学院 2015 年秋季学期 算法与数据结构算法与数据结构课程设计课程设计 题 目：哈夫曼编译码系统 宾馆客房管理系统 专业班级：软件工程（2）班 姓 名： 学 号： 指导教师： 成 绩：_ 目目 录录 摘摘 要要.3 一一哈夫曼编哈夫曼编译码系统译码系统.4 1.采用类语言定义相关的数据类型.4 2.算法设计.5 3.函数的调用关系图.5 4.调试分析.9 5.测试结果.9 6.源程序（带注释）.12 二二宾馆客房管理系统宾馆客房管理系统.20 1.采用类语言定义相关的数据类型.20 2.算法设计.20 3.函数的调用关系图.20

2、 4.调试分析.22 5.测试结果.22 6.源程序（带注释）.24 总总 结结.30 参考文献参考文献.31 致致 谢谢.32 摘摘 要要 Huffman 编码是一种可变长编码方式，是二叉树的一种特殊转化形式。它的原理是： 将使用次数多的代码转换成长度较短的编码，而使用次数少的可以使用较长的编码，并且保 持编码的唯一可解性。本文根据 Huffman 编码原理，在详细设计中，根据权值和最小的根本 原则，我们输入要编码的字符集及其它的权值，再根据在概要设计中提到的节点 Node 类， 算法 SuanFa 类以及主类 JieMian 类，建立哈夫曼树，并进行编码，最后输出哈夫曼编码。 在完成 Hu

3、ffman 编码后，我们利用其构建的哈夫曼编码树来进行译码。与编码过程不同， 译码过程中，我们将用户输入的二进制代码串依次与字符集中的每个字符的编码进行比较， 译出一个字符后，循环比较下一个字符的编码，直到所有二进制码全部译出为止。 在编码和译码的过程中，我们遇到很多问题，诸如算法、语法问题，但我们都通过不断 的分析，和调试将这些问题一一解决，最终建立了一个完整的编/译 近年来，宾馆业迅猛发展，市场的竞争日趋激烈，全面提高宾馆的软件管理水准，已成 为宾馆业发展的当务之急。尤其是对于星级宾馆，既需要完成前台的一些服务工作，还需要 完成后台的管理工作。然而，传统的人工管理模式已经远远不能满足有效、

4、快捷地处理经营 中产生的大量信息数据的需要，从而使得企业决策层无法及时、准确地掌握一线资料，继而 影响对市场进行正确地分析和预测。像沿海城市三星级以上宾馆引进外方管理，使小部分宾 馆管理水准几乎接近或达到国际水平。但对占 80%以上的广大中小型宾馆来说，是难以做到 的。因此，欲在竞争中甩开对手，取得优势，必须在经营、管理、产品、服务等方面具备独 到之处。而对宾馆的经营状况起决定作用的是客房的管理。简单的服务标准已不是制胜的锦 囊，只有管理做到最细微之处，才能让顾客体会到宾馆服务的高标准、高质量，而准确、快 速、周全往往就是最基本的成功要素。 传统的管理方法已经不能适应现代社会的需要，因此采用电

5、脑管理业务、财务等诸 多环节已成为推动宾馆业迅速发展的先决条件，宾馆客房管理信息系统是各大中小型宾馆所 需要使用的一个管理系统。 关键词： 关键词：Huffman 编码树；最优二叉树；编码；译码；宾馆客房；管理；顺序 遍历；模块。 一一哈夫曼编译码系统哈夫曼编译码系统 利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。 这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码 （复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码 系统。试为这样的信息收发站编写一个赫夫曼码的编/译码系统。 哈夫曼编码(Huffman

6、 Coding)是一种编码方式，以哈夫曼树即最优二叉树，带权 路径长度最小的二叉树，经常应用于数据压缩。是指使用一张特殊的编码表将源字符（例如 某文件中的一个符号）进行编码。这种方法是由 David.A.Huffman 发展起来的。例如，在英 文中，e 的出现概率很高，而 z 的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩 时，e 极有可能用一个位(bit)来表示，而 z 则可能花去 25 个位（不是 26） 。用普通的表示 方法时，每个英文字母均占用一个字节（byte） ，即 8 个位。二者相比，e 使用了一般编码的 1/8 的长度，z 则使用了 3 倍多。倘若我们能实现对于英文中各个

7、字母出现概率的较准确的 估算，就可以大幅度提高无损压缩的比例。 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(Hnodet

8、ype huffnodeMaxnode)/输入叶子节点的个数及权值：初始化函数 2.2.算法设计算法设计 1.构造哈夫曼树，使用静态链表作为哈夫曼树的存储 在构造哈夫曼树时，设计一个结构体数组 Huffnode 来保存哈夫曼树的各个结点的 信息，根据二叉树的性质可知，具有 n 个叶子结点的哈夫曼树共有 2n-1 个结点，所以 数组 Huffnode 的大小设置为 2n-1，在实际设计过程中，定义符号常量 Maxleaf，为最大 的叶节点的个数，然后再定义一个符号常量 Maxnode 为 Maxleaf*2-1，代表最大的总的 结点的个数。 2求哈夫曼编码时使用一维结构数组 Huffcode 作

9、为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿叶结点的 双亲链域回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈 夫曼码值。由于一个字符的哈夫曼编码是从根结点到相应叶结点所经过的各个分支所组 成的 0，1 序列，因此先得到的分支代码为所求代码的低位码，后得到的分支代码为所 求编码的高位码。 3.采用文件读写的方式读取结点信息，存入结点信息，减少传递参数带来的不便， 且同时将数据信息有效的保存起来。 3.3.函数的调用关系图函数的调用关系图 开始 从 data1.txt 读取 n 从 data2.txt 读取 huffnode in

10、 cd.start=n-1 左孩子 将 0 存入 bit将 1 存入 bit 否 是 start- 将 cd 的值赋给 huffcode 是 将 huffcode 存入文件 data3.txt 结束 开始 从 data1.txt 读取 n 从 data2.txt 读取 huffnode 从 data3.txt 读取 huffcode 输入字符串 a 长度为 len 沿左 孩子 遍历 ai=0ai=1 沿右 孩子 遍历 叶结点 是 遍历 huffcode 寻找对应字符 存入文件 data4.txt 否 结束 开始 输入 m(0-3) m 不为 0 inputfun() creattree() c

11、odefun() output2() outputcode() encode() m=1m=2m=3 从文件 data1.txt 中读取 n 从文件 data1.txt 中读取 n n 为 0n 为 0 否否 是 是 m=0 结束 4 4. .调试分析调试分析 a、 调试过程中遇到的问题主要是对部分变量的定义不明确导致程序在运行时不能理解 该变量的意义，还有就是刚开始设计函数时是按照功能模块来设计的，所以在最后 的代码调试阶段出现大量的功能模块融入不到一块的问题。解决这些问题主要是通 过阅读相关的文献重新学习 C 语言而解决的。 b、算法的时间复杂度和空间复杂度都是 O（nlogn） 。 5.

12、5.测试结果测试结果 1.初始化函数 2.输出函数 2.1 输出各个结点的权重、左孩子、右孩子、双亲结点的下标的编码表及叶结点的字符对应 编码的编码情况 3.译码函数 4.此时的 4 个文本文件 6.6.源程序（带注释）源程序（带注释） int i; char zifu10; ofstream in; in.open(data1.txt,ios:trunc); coutn; while(n20) coutn; innn; for(i=0;i2*n-1;i+) huffnodei.weight=0; huffnodei.parent=-1; huffnodei.lchild=-1; huffno

13、dei.rchild=-1; cout请分别输入这n个叶子节点的字符名称及权值; for(i=0;in;i+) coutendlzifui; inzifui ; couthuffnodei.weight; inhuffnodei.weightn; out1.close(); for(i=0;in-1;i+) m1=m2=Maxvalue; x1=x2=0; for(j=0;jn+i;j+) if(huffnodej.parent=-1 x2=x1; m1=huffnodej.weight; x1=j; else if(huffnodej.parent=-1 x2=j; huffnodex1.p

14、arent=n+i; huffnodex2.parent=n+i; huffnoden+i.weight=huffnodex1.weight+huffnodex2.weight; huffnoden+i.lchild=x1; huffnoden+i.rchild=x2; ofstream in; in.open(data2.txt,ios:trunc); for(i=0;i2*n-1;i+) inhuffnodei.weight huffnodei.lchild huffnodei.rchild huffnodei.parentm; out1.close(); fstream out; out

15、.open(data2.txt,ios:in); for(int i=0;iabcd; couta b c dn; out1.close(); fstream out2; out2.open(data2.txt,ios:in); for(i=0;ihuffnodei.weight huffnodei.lchild huffnodei.rchild huffnodei.parent; for(i=0;in;i+) cd.start=n-1; c=i; p=huffnodei.parent; while(p!=-1) if(huffnodep.lchild=c) cd.bitcd.start=0;

16、 else cd.bitcd.start=1; cd.start-; c=p; p=huffnodec.parent; for(j=cd.start+1;jn;j+) huffcodei.bitj=cd.bitj; huffcodei.start=cd.start; out2.close(); ofstream in; in.open(data3.txt,ios:trunc); for(i=0;in;i+) inhuffcodei.start ; for(int j=huffcodei.start+1;jn;j+) inhuffcodei.bitj ; inm; for(int c=0;csw

17、; coutsb; for(int r=b+1;rd; coutd; 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

18、.start+1;uhuffcodev.bitu; out3.close(); ofstream in; in.open(data4.txt,ios:trunc);/ios:trunc 表示在打开文件前将文件清空，文件不存在 则创建 cout请输入一串二进制编码a; len=strlen(a); p=huffnodec.parent; while(p!=-1) c+; p=huffnodec.parent; /求树中结点的总数目为 c,根节点在 huffnode中的下表地址为 c cc=c;/记录当前的下表地址 cout译码结果为; for(int i=0;ilen;i+) if(ai=0)c

19、c=huffnodecc.lchild; else if(ai=1)cc=huffnodecc.rchild; if(huffnodecc.lchild=-1kn;k+) mm=huffcodek.start+1; for(int hh=j;hh=i,mm=i inzifuk; j=i+1; cc=c;/更新 j 和 cc 的值 break; in.close(); int main() int m,n; Hnodetype huffnodeMaxnode; coutendl-哈夫曼编译码系统-endl; cout 1.建立哈夫曼树endl 2.输出哈夫曼编码endl 3.进行哈夫曼译码end

20、l 0.退出endl m; 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) cout请先初始化，建立哈夫曼树endl; else coutendl输出哈夫曼树的各个节点的信息为endl; output2(); coutendl输出哈夫曼树的各个字符的编码为endl; outputcode(); else

21、if(m=3) if(n=0) cout请先初始化，建立哈夫曼树endl; else encode(); coutendl; cout返回主菜单为endl; coutendl-哈夫曼编译码系统-endl; cout 1.建立哈夫曼树endl 2.输出哈夫曼编码endl 3.进行哈夫曼译码endl 0.退出endl m; while(m3) coutm; return 0; 二二宾馆客房管理系统宾馆客房管理系统 1.1.采用类语言定义相关的数据类型采用类语言定义相关的数据类型 struct Node int Count; /指示该房间有多少个房客 char nameOne20; /房客 1 的名

22、字 char nameTwo20; /房客 2 的名字 int sexOne; /房客 1 的性别 -1 代表女，0 代表没有，1 代表男 int sexTwo; /房客 2 的性别 int roomNumber; /房间号 roomArray5; 2.2.算法设计算法设计 1.这是一个小型的管理系统，使用结构体数组存储客房的信息。 2一般的管理系统都应该具备插入，修改，查询，删除，浏览，排序，统计，追加等功能， 通过使用一个简易菜单进行执行动作的选择。 3.用函数实现模块化设计，调理清晰，使程序易读写。 4.把程序与文件联系，使数据能存储在磁盘中，更具实用性。 3.3.函数的调用关系图函数的

23、调用关系图 开始 定义静态链表 执行 main 函数 执行 choice 函数 调用 Iive_in 函 数 调用 live_away 函数调用 look_through 函 数 调用 live_in_two 函数 调用 live_in_one 函数 结束 4.4.调试分析调试分析 a.在调试过程中的主要问题为程序没有与文件建立联系，所进行的的操作结果在程序运 行结束后不能保存，所以等下次重新打开程序是之前的数据将会丢失。 B.通过对该程序的各项操作的分析：旅客入住，信息查询，旅客入住，信息插入，信息 追加，信息删除的时间复杂度都为 O（1） ，而信息排序，信息统计的时间复杂度为 O（n2）,

24、 所以综合上述操作的时间复杂度为 O（n2） 。 5.5.测试结果测试结果 1. 这是主操作页面调试图 2.这是进行旅客入住操作图 3.这是对已入住旅客信息查询操作图 6.6.源程序（带注释）源程序（带注释） /初始化房间数组 void InitArray() int i; for(i=0;i5;i+) roomArrayi.roomNumber = 301+i; memset(roomArrayi.nameOne,0,20); memset(roomArrayi.nameTwo,0,20); roomArrayi.sexOne = 0; roomArrayi.sexTwo = 0; room

25、Arrayi.Count = 0; void fun1() /旅客入住的操作 char name20; int sex; int i; printf(n 输入入住旅客姓名和性别（空格隔开,1 为男,-1 为女）：); scanf(%s %d,name, for(i=0;i5;i+) if(roomArrayi.Count = 2) continue; else if(roomArrayi.Count = 1) if(roomArrayi.sexOne != sex) continue; strcpy(roomArrayi.nameTwo,name); roomArrayi.sexTwo = s

26、ex; roomArrayi.Count+; system(cls); printf(客人已经成功入住,在房间%d,roomArrayi.roomNumber); return; else strcpy(roomArrayi.nameOne,name); roomArrayi.sexOne = sex; roomArrayi.Count+; system(cls); printf(客人已经成功入住,在房间%d,roomArrayi.roomNumber); return; printf(无法入住，房间已经住满或者是没有适合的房间); void fun2() /退房操作 int i; char

27、name20; printf(请输入要退房旅客的姓名： ); scanf(%s,name); for(i=0;i5;i+) if(strcmp(roomArrayi.nameOne,name) = 0) memset(roomArrayi.nameOne,0,20); roomArrayi.sexOne = 0; roomArrayi.Count-; system(cls); printf(%s 客人已经成功退房n,name); return; if(strcmp(roomArrayi.nameTwo,name) = 0) memset(roomArrayi.nameTwo,0,20); ro

28、omArrayi.sexTwo = 0; roomArrayi.Count-; system(cls); printf(%s 客人已经成功退房n,name); return; system(cls); printf(没有名为%s 的客人，请检查输入的正确性!n,name); void fun3() /查询操作 int index; int i; char name20; int number; int j; system(cls); printf(*请选择要查询的种类*n); printf( 1.所有房间入住信息显示n); printf( 2.按照姓名查询n); printf( 3.按照房号查

29、询n); scanf(%d, if(index = 1) for( i=0;i 姓名%s,roomArrayi.nameOne); if(roomArrayi.sexOne = 1) printf(性别：男); else if(roomArrayi.sexOne = -1) printf(性别：女); printf(n); else if(roomArrayi.sexOne = 0) printf(当前有 1 位客人- 姓名%s,roomArrayi.nameTwo); if(roomArrayi.sexTwo = 1) printf(性别：男); else if(roomArrayi.sex

30、Two = -1) printf(性别：女); printf(n); else /printf(当前有两个客人 客人 1： 姓名%s,性别%d 客人 2： 姓名%s,性 别%d n,roomArrayi.nameOne,roomArrayi.sexOne,roomArrayi.nameTwo,roomArrayi. sexTwo); printf(当前有 2 位客人- 姓名%s,roomArrayi.nameOne); if(roomArrayi.sexOne = 1) printf(性别：男，); else if(roomArrayi.sexOne = -1) printf(性别：女，);

31、printf(姓名：%s,roomArrayi.nameTwo); 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!,roomArrayj.nameOne,roomArrayj. sexOne); else printf(当前有两个客人入住 姓名%s,性别%d 姓名%s,性别%d n,room

32、Arrayj. nameOne,roomArrayj.sexOne,roomArrayj.nameTwo,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);

33、show(); scanf(%d, switch(i) case 1: fun1(); break; case 2: fun2(); break; case 3: fun3(); break; system(pause); return 0; 总总 结结 回顾起此次课程设计，我有很多的感慨，自从拿到题目到完成整个编程，从理论到实践的过 程中，可以学到很多很多的的东西，同时不仅可以巩固以前所学过的知识，而且学到了很多 在书本上所没有学到过的知识。这次课题实验是我将理论应用于实践过程中的自我探究，独 立自觉摸索的过程，在培养对计算机编程兴趣的同时，增强了我们的实践编程能力。在遇到 难题的时候我们会

34、查阅相关书籍，寻求老师帮助，并且积极的查阅有关资料和向他人请教。 我们提高了兴趣，丰富了知识，锻炼了能力。 在实践过程中，我们强烈感受到了彼此之间的积极性，体会到了开发软件项目的乐趣以 及取得成就之后的成就感。虽然在此过程中，我们付出了汗水与劳动，但对成功的不懈追求 以及彼此之间的相互勉励是我们感到充实而骄傲！ 参考文献参考文献 1 谭浩强，C 程序设计教程，清华大学出版社，2007 年 2 谭浩强编著， C 程序设计 ，清华大学出版社，1991 年 致致 谢谢 这次实践课程对我们来说是一个挑战，因为要自己独立完成这样一个项目对每个人来说都 有或大或小的困难。同时也是一个机遇，因为他给了我们一个检验自己所学知识及综合运 用的机会。感谢老师能在百忙之中抽出时间到学校来指导监督我们按时完成任务，感谢老 师能对待我们每个同学的悉心指导与批评。总的来说，老师的指导和监督在这次实践中起 到了重要的作用。