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

*实践教学* 兰州理工大学计算机与通信学院2015年秋季学期算法与数据结构课程设计题 目：哈夫曼编译码系统 宾馆客房管理系统专业班级：软件工程（2）班 姓 名： 学 号： 指导教师： 成 绩：_目 录摘 要3一哈夫曼编译码系统41.采用类语言定义相关的数据类型42.算法设计53.函数的调用关系图54.调试分析95.测试结果96.源程序（带注释）12二宾馆客房管理系统201.采用类语言定义相关的数据类型202.算法设计203.函数的调用关系图204.调试分析225.测试结果226.源程序（带注释）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. 采用类语言定义相关的数据类型 typedef structunsigned int weight;unsigned int parent, lchild, rchild; HTNode, *HuffmanTree; int weight;int parent;int lchild;int rchild;Hnodetype;typedef structint bitMaxbit;int start;Hcodetype;int n=0;void inputfun(Hnodetype huffnodeMaxnode)/输入叶子节点的个数及权值：初始化函数2. 算法设计1.构造哈夫曼树，使用静态链表作为哈夫曼树的存储在构造哈夫曼树时，设计一个结构体数组Huffnode来保存哈夫曼树的各个结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组Huffnode的大小设置为2n-1，在实际设计过程中，定义符号常量Maxleaf，为最大的叶节点的个数，然后再定义一个符号常量Maxnode 为Maxleaf*2-1，代表最大的总的结点的个数。2求哈夫曼编码时使用一维结构数组Huffcode作为哈夫曼编码信息的存储。求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿叶结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值。由于一个字符的哈夫曼编码是从根结点到相应叶结点所经过的各个分支所组成的0，1序列，因此先得到的分支代码为所求代码的低位码，后得到的分支代码为所求编码的高位码。3.采用文件读写的方式读取结点信息，存入结点信息，减少传递参数带来的不便，且同时将数据信息有效的保存起来。3. 函数的调用关系图开始从data1.txt读取n 从data2.txt读取huffnode i<ncd.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不为0inputfun()creattree() codefun()output2()outputcode()encode()m=1m=2m=3从文件data1.txt中读取n从文件data1.txt中读取nn为0n为0否否是是m=0结束4.调试分析a、 调试过程中遇到的问题主要是对部分变量的定义不明确导致程序在运行时不能理解该变量的意义，还有就是刚开始设计函数时是按照功能模块来设计的，所以在最后的代码调试阶段出现大量的功能模块融入不到一块的问题。解决这些问题主要是通过阅读相关的文献重新学习C语言而解决的。b、算法的时间复杂度和空间复杂度都是O（nlogn）。5. 测试结果1.初始化函数2.输出函数2.1输出各个结点的权重、左孩子、右孩子、双亲结点的下标的编码表及叶结点的字符对应编码的编码情况3.译码函数4.此时的4个文本文件6.源程序（带注释）int i;char zifu10;ofstream in;in.open("data1.txt",ios:trunc);cout<<"请输入叶子节点的个数"cin>>n;while(n<=0|n>20)cout<<"输入错误，请重新输入"cin>>n;in<<n<<"n"for(i=0;i<2*n-1;i+)huffnodei.weight=0;huffnodei.parent=-1;huffnodei.lchild=-1;huffnodei.rchild=-1;cout<<"请分别输入这"<<n<<"个叶子节点的字符名称及权值"for(i=0;i<n;i+)cout<<endl<<"字符-"cin>>zifui;in<<zifui<<" "cout<<" 权重-" cin>>huffnodei.weight; in<<huffnodei.weight<<"n"in.close();void creattree(Hnodetype *huffnode)/哈夫曼树的建立int m1,m2,x1,x2,n;int i,j; fstream out1; out1.open("data1.txt",ios:in);out1>>n; out1.close();for(i=0;i<n-1;i+)m1=m2=Maxvalue;x1=x2=0;for(j=0;j<n+i;j+)if(huffnodej.parent=-1&&huffnodej.weight<m1)m2=m1;x2=x1;m1=huffnodej.weight;x1=j;else if(huffnodej.parent=-1&&huffnodej.weight<m2)m2=huffnodej.weight;x2=j;huffnodex1.parent=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;i<2*n-1;i+)in<<huffnodei.weight<<" " <<huffnodei.lchild<<" " <<huffnodei.rchild<<" " <<huffnodei.parent<<"n"in.close();void output2()/输出编码表：权重、左孩子、右孩子及双亲的下标地址int a,b,c,d,m;fstream out1; out1.open("data1.txt",ios:in);out1>>m; out1.close();fstream out;out.open("data2.txt",ios:in);for(int i=0;i<2*m-1;i+)out>>a>>b>>c>>d;cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;out.close();void codefun()/哈夫曼编码函数Hcodetype cd;Hcodetype huffcodeMaxleaf;Hnodetype huffnodeMaxnode;int i,j,c,p,n;fstream out1; out1.open("data1.txt",ios:in);out1>>n; out1.close();fstream out2;out2.open("data2.txt",ios:in);for(i=0;i<2*n-1;i+)out2>>huffnodei.weight>>huffnodei.lchild>>huffnodei.rchild>>huffnodei.parent;for(i=0;i<n;i+)cd.start=n-1;c=i;p=huffnodei.parent;while(p!=-1)if(huffnodep.lchild=c)cd.bitcd.start=0;else cd.bitcd.start=1;cd.start-;c=p;p=huffnodec.parent;for(j=cd.start+1;j<n;j+)huffcodei.bitj=cd.bitj;huffcodei.start=cd.start;out2.close();ofstream in;in.open("data3.txt",ios:trunc);for(i=0;i<n;i+)in<<huffcodei.start<<" "for(int j=huffcodei.start+1;j<n;j+)in<<huffcodei.bitj<<" "in<<endl;in.close();void outputcode()/输出哈夫曼编码：形式为A-010char s;int w;int m,b,d;fstream out1;out1.open("data1.txt",ios:in);fstream out2;out2.open("data3.txt",ios:in);out1>>m;for(int c=0;c<m;c+)out1>>s>>w;cout<<s<<"-"out2>>b;for(int r=b+1;r<m;r+)out2>>d; cout<<d;cout<<endl;out1.close();out2.close();void encode()/哈夫曼解码函数char a100;char zifu30;int len,cc,n,w;int j=0;int p,c=0,mm;Hnodetype huffnodeMaxnode;Hcodetype huffcodeMaxleaf;fstream out1; out1.open("data1.txt",ios:in);out1>>n;for(int v=0;v<n;v+) out1>>zifuv>>w; out1.close();fstream out2;out2.open("data2.txt",ios:in);for(v=0;v<2*n-1;v+)out2>>huffnodev.weight>>huffnodev.lchild>>huffnodev.rchild>>huffnodev.parent;out2.close();fstream out3;out3.open("data3.txt",ios:in);for(v=0;v<n;v+)out3>>huffcodev.start;for(int u=huffcodev.start+1;u<n;u+)out3>>huffcodev.bitu;out3.close();ofstream in;in.open("data4.txt",ios:trunc);/ios:trunc表示在打开文件前将文件清空，文件不存在则创建cout<<"请输入一串二进制编码"<<endl;cin>>a;len=strlen(a);p=huffnodec.parent;while(p!=-1)c+; p=huffnodec.parent; /求树中结点的总数目为c,根节点在huffnode中的下表地址为ccc=c;/记录当前的下表地址cout<<"译码结果为"for(int i=0;i<len;i+)if(ai='0')cc=huffnodecc.lchild;else if(ai='1')cc=huffnodecc.rchild;if(huffnodecc.lchild=-1&&huffnodecc.rchild=-1)/从j到i为一个字符的编码for(int k=0;k<n;k+) mm=huffcodek.start+1;for(int hh=j;hh<=i,mm<n;hh+,mm+)if(ahh-'0')!=huffcodek.bitmm)break;if(hh>=i&&mm=n) cout<<zifuk; in<<zifuk;j=i+1; cc=c;/更新j和cc的值 break;in.close(); int main()int m,n;Hnodetype huffnodeMaxnode; cout<<endl<<"-哈夫曼编译码系统-"<<endl;cout<<" 1.建立哈夫曼树"<<endl<<" 2.输出哈夫曼编码"<<endl<<" 3.进行哈夫曼译码"<<endl<<" 0.退出"<<endl<<"请选择:"cin>>m;while(m<0|m>3)cout<<"输入错误，请重新输入"cin>>m;while(m)fstream out1; out1.open("data1.txt",ios:in);out1>>n; out1.close();if(m=1)inputfun(huffnode); creattree(huffnode); codefun();else if(m=2) if(n=0) cout<<"请先初始化，建立哈夫曼树"<<endl; else cout<<endl<<"输出哈夫曼树的各个节点的信息为"<<endl;output2();cout<<endl<<"输出哈夫曼树的各个字符的编码为"<<endl; outputcode(); else if(m=3) if(n=0) cout<<"请先初始化，建立哈夫曼树"<<endl;elseencode();cout<<endl;cout<<"返回主菜单为"<<endl;cout<<endl<<"-哈夫曼编译码系统-"<<endl;cout<<" 1.建立哈夫曼树"<<endl<<" 2.输出哈夫曼编码"<<endl<<" 3.进行哈夫曼译码"<<endl<<" 0.退出"<<endl<<"请选择:"cin>>m;while(m<0|m>3)cout<<"输入错误，请重新输入"cin>>m;return 0;二宾馆客房管理系统1. 采用类语言定义相关的数据类型 struct Nodeint Count; /指示该房间有多少个房客char nameOne20; /房客1的名字char nameTwo20; /房客2的名字int sexOne; /房客1的性别 -1代表女，0代表没有，1代表男int sexTwo; /房客2的性别int roomNumber; /房间号roomArray5; 2. 算法设计1.这是一个小型的管理系统，使用结构体数组存储客房的信息。2一般的管理系统都应该具备插入，修改，查询，删除，浏览，排序，统计，追加等功能，通过使用一个简易菜单进行执行动作的选择。3.用函数实现模块化设计，调理清晰，使程序易读写。4.把程序与文件联系，使数据能存储在磁盘中，更具实用性。3.函数的调用关系图开始定义静态链表执行main函数执行choice函数调用Iive_in函数调用live_away函数调用look_through函数调用live_in_two函数调用live_in_one函数结束4.调试分析a.在调试过程中的主要问题为程序没有与文件建立联系，所进行的的操作结果在程序运行结束后不能保存，所以等下次重新打开程序是之前的数据将会丢失。B.通过对该程序的各项操作的分析：旅客入住，信息查询，旅客入住，信息插入，信息追加，信息删除的时间复杂度都为O（1），而信息排序，信息统计的时间复杂度为O（n2）,所以综合上述操作的时间复杂度为O（n2）。5. 测试结果 1. 这是主操作页面调试图 2.这是进行旅客入住操作图 3.这是对已入住旅客信息查询操作图6.源程序（带注释）/初始化房间数组void InitArray()int i;for(i=0;i<5;i+)roomArrayi.roomNumber = 301+i;memset(roomArrayi.nameOne,0,20);memset(roomArrayi.nameTwo,0,20);roomArrayi.sexOne = 0;roomArrayi.sexTwo = 0;roomArrayi.Count = 0;void fun1() /旅客入住的操作char name20;int sex;int i;printf("n输入入住旅客姓名和性别（空格隔开,1为男,-1为女）：");scanf("%s %d",name,&sex);for(i=0;i<5;i+)if(roomArrayi.Count = 2)continue;else if(roomArrayi.Count = 1)if(roomArrayi.sexOne != sex)continue;strcpy(roomArrayi.nameTwo,name);roomArrayi.sexTwo = sex;roomArrayi.Count+;system("cls");printf("客人已经成功入住,在房间%d",roomArrayi.roomNumber);return;elsestrcpy(roomArrayi.nameOne,name);roomArrayi.sexOne = sex;roomArrayi.Count+;system("cls");printf("客人已经成功入住,在房间%d",roomArrayi.roomNumber);return;printf("无法入住，房间已经住满或者是没有适合的房间");void fun2() /退房操作int i;char name20;printf("请输入要退房旅客的姓名： ");scanf("%s",name);for(i=0;i<5;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);roomArrayi.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.按照房号查询n");scanf("%d",&index);if(index = 1) for( i=0;i<5;i+)printf("房间%d:",roomArrayi.roomNumber);if(roomArrayi.Count = 0)printf("没有客人入住n");else if(roomArrayi.Count = 1)if(roomArrayi.sexTwo = 0)printf("当前有1位客人-> 姓名%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.sexTwo = -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("性别：女，");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<5;i+)if(strcmp(roomArrayi.nameOne,name) = 0 | strcmp(roomArrayi.nameTwo,name) = 0)printf("%s房客入住在房间%d!n",name,roomArrayi.roomNumber);return;printf("没有找到该旅客的信息!");else if(index = 3)printf("请输入你要查询的房间号：");scanf("%d",&number);j = number - 301;if(roomArrayj.Count = 0)printf("没有客人入住n");else if(roomArrayj.Count = 1)printf("当前有1位客人-> 姓名%s,性别%d!",roomArrayj.nameOne,roomArrayj.sexOne);elseprintf("当前有两个客人入住 姓名%s,性别%d 姓名%s,性别%d n",roomArrayj.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");show();scanf("%d",&i);switch(i)case 1:fun1();break;case 2:fun2();bre