《数据结构》课程设计报告书123

《数据结构》课程设计报告报告（论文）题目：1.迷宫问题2.哈夫曼编码作者姓名：作者学号：指导教师姓名:《数据结构》课程设计报告书2.1输入/输出形式和输出值的范围（1） 迷宫定义外围为1,作为墙壁，内部用0、1输入，0表示有可走，1表示不可走。入口默认为左上角，出口默认为右下角。（2） 哈夫曼编码，输入信息以加载存档的reading.txt文件为方式，加载不成功，提示出错信息，加载成功后，系统对其编码，并按照选择对各种相关信息存档。2.2程序功能（1） 迷宫问题在迷宫问题中，可由操作者自己输入迷宫的大小，系统会对输入的数据进行判断其合法性，如不正确，系统会有提示语句，让操作者重新输入。最后输出一条迷宫的出路。（2） 哈夫曼编码问题可以读入操作者存在指定文件里的信息，并对其进行哈夫曼编码以及将编码信息存档。2.3测试数据2.3.1正确的输入及输出结果（1）迷宫问题：在生成迷宫后，将迷宫路径输出，如图2-1所示:产生随机迷宫.吾:输出可行的所有路径.季退出为>ir{pMpwpMp^p^!pwp^!p^pev!p^pMpwp^!p^p^!p^p^!p^p^!p^f^ ^p^p^sp^p^sp^p^sp^p^请输入操作代码：1输入迷宫太小（行数,列数）:"产生RS机迷宫成功：1oo-uoo011oo-uoo1：0I11*1：产生Sfi机迷宫.吾:输出可行的所有路径歹1出声'I请输入操作代码：2第1条可行路径：（ugii1,3-02n13|2j第2条可行路径：（1；1）K2,1）I（过I3我A迷宫共有2条可行路径图2-1迷宫的正确输入、输出结果截图（2）哈夫曼编码问题：在读入文件信息后，对文件进行编码，并显示编码规则等信息，如图2-2所示：幻：从文件读取信息2：显示编码规则 /将原文件信息写进文件 •荒祉将编码规则写进文件5：将编码后的信息写进文件&将译码后的信息写进文件7：退出米.请输入操作代码E1读取文件成功幻『从文件读取信息 '%显示编码规则 安'潮原文件信息写进文件M：将编码规则写进文件与将编码后的信息写进文件电将译码后的信息写进文件7：退出*请输入操作代码：2I11111110a10m1111110s111110t0umwdmoe110n111111112.3.2错误的输入及输出结果迷宫问题：在输出迷宫的可行路径前，需要先生成迷宫。因此，在未生成迷宫时输入“输出可行路径”的命令时，将提示出错信息，如图2-3所示：¥1：产生随机迷宫2Y输出可行的所有路径&退出浆 r请输入操作代码：2 :£未产生随机迷宫，请先生成随机迷宫图2-3测迷宫的错误输入、输出结果截图哈夫曼编码问题：在进行编码、译码及存储编码规则和编码、译码后的信息前，需要先读取文件信息，因此，在未读取文件信息时，输入“显示编码规则”等命令时，会提示出错：如图2-4所示：幻：从文件读取信息-2：显示编码规则 &将原文件信息写进文件 M：将编码规则写进文件5：将编码后的信息写进文件6：将译码后的信息写进文件7：退出*」请输入操作代码：2请先从文件中读取信息！图2-4哈夫曼的错误输入、输出结果截图第3章概要设计3.1设计思想用二维数组来表示迷宫，用栈来保存走过的路径和方向，用一结构体存储方向。哈夫曼树用邻接矩阵作为存储结构，借助静态链表来实现遍历。3.2函数间的关系(1)迷宫问题，函数间的关系，如图3-1所示：图3-1迷宫问题中函数间的关系(2)哈夫曼系统，函数间的关系如图3-2所示:第4章详细设计4.1迷宫的主要结构结构定义如下：#defineMAXSIZE100typedefstruct{intx,y,d;}Datatype;〃栈中元素类型定义typedefstruct{Datatypedata[MAXSIZE*MAXSIZE];inttop;}Seqstack;〃栈定义typedefstruct{intx;inty;}zuobiao;〃元素坐标定义Seqstack*s1,*s2;//定义两个栈方便按顺序输出栈中元素Datatypeitem;//定义临时坐标intnumber;//定义可行路径条数intmaze[MAXSIZE][MAXSIZE];//定义迷宫数组各功能函数的声明及说明如下：Seqstack*Init_Seqstack();栈初始化voidPush_Seqstack(Seqstack*s,Datatypeitem);入栈voidPop_Seqstack(Seqstack*s,Datatype*item);出栈voidInit_Move(zuobiaomove[4]);Move[]方向数组初始化voidInit_Maze(intm,intn);产生随机迷宫voidoutput(intm,intn);显示迷宫voidMaze(zuobiaomove[4],intm,intn,intmark);搜索迷宫路径voidresult(Seqstack*s);输出迷宫路径4.2哈夫曼的主要结构(1)结构定义：#defineMAXVALUE1000//定义最大权值#defineMAXBIT100//定义哈夫曼树中叶子结点个数typedefstruct{chardata;//字符值intnum;//某个值的字符出现的次数}TotalNode;〃统计结点，包括字符种类和出现次数typedefstruct{TotalNodetot[300];//统计结点数组intnum;//统计数组中含有的字符个数}Total;〃统计结构体，包括统计数组和字符种类数typedefstruct{charmes[300];//字符数组intnum;//总字符数}Message;〃信息结构体，包括字符数组和总字符数typedefstruct{intlocked[500];//密码数组intnum;//密码总数}Locking;〃哈夫曼编码后的密文信息typedefstruct{chardata;//字符intweight;//权值intparent;//双亲结点在数组HuffNode[]中的序号intlchild;//左孩子结点在数组HuffNode[]中的序号intrchild;//右孩子结点在数组HuffNode[]中的序号}HNodetype;〃哈夫曼树结点类型，包括左右孩子，权值和信息typedefstruct{intbit[MAXBIT];intstart;}HCodetype;〃哈夫曼编码结构体，包括编码数组和起始位(2)主要函数声明及功能描述如下：voidreading_file(Message*message);从文件中读取信息voidwriting_file(Message*message);将信息写进文件voidtotal_message(Message*message,Total*total);统计信息中各字符的出现次数voidHaffmanTree(Total*total,HNodetypeHuffNode[]);构建哈夫曼树voidHaffmanCode(HNodetypeHuffNode[],HCodetypeHuffCode[],Total*total);建立哈夫曼编码voidwriting_HCode(HNodetypeHuffNode[],HCodetypeHuffCode[],Total*total);将编码规则写进文件voidlock(Message*message,HNodetypeHuffNode[],HCodetypeHuffCode[],Total*total,Locking^locking);给文件信息加密编码voidwriting_lock(Locking*locking);将已编码信息写进文件voidwriting_translate(Locking*locking,HCodetypeHuffCode[],HNodetypeHuffNode[],Total*total);将已编码信息翻译过来并写进文件第5章调试分析5.1问题描述（1） 用什么样的储存方式。（2） 考虑栈和队列对迷宫探究的不同。5.2解决方案（1） 采用静态链表储存。（2） 栈是先进后出，队列是先进先出。5.3对设计实现的回顾讨论和分析程序使用了文件来编码和译码，创建哈夫曼树并用层次遍历输出，把编码后的信息存入文件并译码，再输出并保存。系统二是对迷宫问题探究的系统，其核心思想用栈是实现对迷宫通路的求解。该过程中应用了栈的先进后出的特点去探究路径，保存后输出。建立了数组实现迷宫的虚拟化，用move[]数组来指示求路径时的方向。5.4对算法的分析和改进设想（1） 功能不是很强大，对错误字符编码但不输出，要能输入入口坐标。（2） 栈和队列是受限制的线性表，是软件中常用的两种数据结构，可以很方便的对它们进行操作。还可改进成更为简洁、灵活的程序。5.5经验和体会（1） 编程时要认真，出现错误要及时找出并改正，遇到问题要去查相关的资料。反复的调试程序，把各个注意的问题要想到；同时要形成自己的调试程序的风格，从每个细节出发，不放过每个知识点。另外，要注意符号的使用。（2） 通过此次课设我学到了好多东西，以前会的知识更加熟悉了，而且有了更深的认识；不太清楚的知识点也有了新的理解。

第6章测试并列出测试结果6.1迷宫问题测试结果选择“产生随机迷宫，，，输入迷宫的行数和列数，生成随机迷宫，如图6-1所示:*T：产生随机迷宫2;输出可行的所有路径2退出*请输入操作代码：1输入迷宫大小W行数i列数).；54产生随切迷宫成功：111O11O1oO一―一―-on-一―oooO-11：0i1i0■:1：图6-1产生随机迷宫截图选择“输出可行的所有路径”，输出迷宫的可行路径条数及每条路径所经过的点，点用坐标形式表示，方向用箭头指明，如图6-2所示:、.十、.十、.十、.十、"t：产生随机迷宫输出可行的所有路径3退出'请输入操作代码：艺第1条可行路径：(1,1.)1(2,1.)1(浏)f(：3留)1(4,2)-(4,<01(5.箴)一第2条可行路径：〈1,1)1(玲)」3,1)1(4,1)-C4?2T戚)I(5覆)-迷宫共有2条可行路径图6-2输出迷宫所有路径截图6.2哈夫曼系统测试结果选择“从文件读取信息”，程序将从文件读取信息，如果读取失败（不存在该信息文件），则结束，如果读取成功，则输出读取成功的提示信息，如图6-3及图6-4所示：珏从文件iUft息 2：显示编碍规则 3：将原文件信息写进文件*烛将■编隔规则写述文件5：将编码后的信息写进文件6：将译码后的信息写进文件7：退蝌'上"土\L*"J/1♦'**L\L**土'，1'*\L*r~J/r'JL'hl"\L*°£‘**L ，JL‘**L\L* \L**%!?*值'**卜\L**‘即**上\L" \Li7Jz1，土『-上，』上，，昼.=■■,心*•】_』■«,上,日；laj》■［，，即,j.史,,史项.土1，和.上 4:，'**•_!/4*1'***L"\L**史’「L%L-4/*4,.上*8土1 k七L*，i?%L、L*浦辘入操作代码；1淮取文件成功图6-3从文件读取信息截图・届di面吁记事本Iamastudent图6-4存放原信息的文档reading.txt截图选择“显示编码规则”，则将信息编码并输出编码规则，如图6-5所示:<文件读取信息2：显示编码规则 3；将原文件信息写进文件•凌:料；将编码规则写进文件5：将编码后的信息写进文件6|将译码后的信息写进文件7：退出*请输入操作代码：2I1111111。aWm111111。t0u1111。d111。e110n11111111图6-5显示编码规则截图选择“将原文件信息写进文件”，则将读入内存中的文件信息存储到文档writing.txt中，如图6-6及图6-7所示：「「叶、.中..■!■..，卞 -代 .中..■!■. .■!,..,(■..■(■. .■!■..■!■..,十■..，甲、.座、叶、可、叶、,■代外从文件读取信息'%显示编码规则 3：将原文件信息写进文件>|荆：将编码规则写进文件尽.将编码后的信息写进文件6：：将译码后的信息写进文件7,...1出*叶■•押、■•押■•押、「.中、.中、汗、永 ■•押.中、.中、请输入操作代码：a t信息写进文件成功图6-6将原文件信息写入文件截图|lamastudent 口|图6-7存放原信息的文档writing.txt截图在读入信息的前提下，选择“将编码规则写进文件”，则对信息编码并将编码规则写入文档HCode.txt中，如图6-8及图6-9所示：.十..-|■.--|■.-■!,..,!■■.■|,..■|-..十.--|■.--|,..中..■|,..■|,..十..十.--|■.-■!,..中..■|,..■|-..十..-|■.--|,..中..■!,■.■|,..■|-..十.--|■.--|,..中..■|,..■|,..十..-|■.--|■.-■!,..,!■■.■|,..■|-..十..-|■.--|,..中..■!,■.■|-..十..十.--|■.-■!,..中..■|,..■|,..十..-|■.--|■.-■!,..小*.■|,.幻：从文件读取信息2：显示编码规则 尊将原文件信息写进文件 米M：将编码规则写进文件5：将编码后的信息写进文件&将译码后的信息写进文件7：退出来请输入操作代码：4编码规则写进文件成功图6-8将编码规则写入文件截图祐藏匚匏事本 -FF文件E编辑E格式廷)查看如帮助但)||11111110 口a10m1111110s111110t0u11110d1110e110n11111111图6-9存放编码规则的文档HCode.txt截图选择“将编码后的信息写进文件”，则对信息编码并将编码后的信息写入文档locking.txt中，如图6-10及图6-11所示：小..■|,..十.--|,..■!■■.■|-..-|,..小..■|,..-|,..小..■|,..十.--|,..■!■■.■|-..-|,..小..■|-..-|,..小..■|,..十.--|,..■!■■.■|-..-|,..小..■|-..-|,..小..■|,..十.--|,..■!■■.■|-..-|,..小..■|-..-|,..小..■|,..十.--|,..■!■■.■|-..-|,..小..■|-..-|,..小..■|,..十.--|■.*1：从文件读取信息2：显示编码规则 盅将原文件信息写进文件 湄物：将编码规则写进文件巽将编码后的信息写进文件理将译码后的信息写进文件宣退出*请输入操作代码：5已编码信息写进文件成功图6-10将编码后的信息写入文件截图locking-,也事本[]史件E编辑E，格式回查看0帮助(H)|11111110101111110101111100111101110110111111110 ;图6-11存放编码后的信息的文档locking.txt截图选择“将译码后的信息写进文件”，则对编码信息译码并将译码后的信息写入文档translate.txt中，如图6-12及图6-13所示：初*从文件读取信息•宠显示编码规则 与m将原文件信息写进文件YM：将编码规则写进文件5：将编码后的信息写进文件?.：将译码后的信息写进文件7：退出阳.中*中、*中、请输入操作代码庭6醐译信息写进文件成功图6-12将译码后的信息写入文件截图Iamastudent图6-13存放译码信息的文档translate.txt截图第7章总结7.1设计体会7.1.1系统的优点（1）特色：有完整的界面管理，清楚的信息提示，方便的执行过程，严谨的结构控制。7.1.2本系统的不足（1） 操作选择中，对字符和整型间的输入无法判断，只能终止程序。迷宫问题中，出入口为默认，迷宫地图为随机生成，用户无法自定义。哈弗曼问题中，只能对存入文档的信息进行编码、译码，且文件名及位置已指定，用户无法进行直接输入。（2） 函数间的兼容性弱，结构不明了，不便于改变参数和数据。（3） 程序代码不够简练，并且可读性也不是很好。7.1.3可改进的地方（1） 各个菜单界面可以设计的更为美观，更简洁易懂。（2） 可以从各个方面考虑设置容错机制使程序更健壮。7.2结束语通过将近两周的课设练习，认识到知识的迁移运用，理论应用实际和相互间的密切联系，感受到理论知识的重要，在今后的学习中一定会更加努力，认真。体会到自己知识有所缺乏，和个人能力的有限，只有通过同学、老师间的密切配合才能完成一项不错的工作。从中也体会到了学习中的乐趣，可以自由的创作自己喜欢的东西并自己调试。致谢在课程设计过程中遇到了很多问题，不过在老师和和同学们的帮助下大部分都得以解决，首先要对他们表示感谢。同时，我们也要感谢学校为我们提供了大量的图书，通过看书我们也学到了很多课堂上学不到的东西。通过此次课程设计我最大的收获是学会了自主学习，也增加了与老师和同学们的交往、增进了相互之间的感情。参考文献严蔚敏，吴伟民.《数据结构：C语言版》.北京：清华大学出版社，1997.刘国钧、郑如斯.《中国书的故事》.北京：中国青年出版社，1979.周霭如、林伟健.《C++程序设计基础》.北京：电子工业出版社.耿国华.《数据结构》.北京：高等教育出版社，2005.姚伯元.《课程设计（论文）规范化管理与培养学生综合素质》.中国高等教育网教学研究，2005.附录附录1:迷宫问题源代码：(1)头文件head.h#defineMAXSIZE100typedefstruct{intx,y,d;}Datatype;〃栈中元素类型定义typedefstruct{Datatypedata[MAXSIZE*MAXSIZE];inttop;}Seqstack;//栈定义typedefstruct{intx;inty;}zuobiao;〃元素坐标定义Seqstack*s1,*s2;//定义两个栈方便按顺序输出栈中元素Datatypeitem;//定义临时坐标intnumber;//定义可行路径条数intmaze[MAXSIZE][MAXSIZE];//定义迷宫数组Seqstack*Init_Seqstack();//栈初始化voidPush_Seqstack(Seqstack*s,Datatypeitem);//入栈voidPop_Seqstack(Seqstack*s,Datatype*item);//出栈voidInit_Move(zuobiaomove[4]);//MOVE方向数组初始化voidInit_Maze(intm,intn);//产生随机迷宫voidoutput(intm,intn);//显示迷宫voidMaze(zuobiaomove[4],intm,intn,intmark);//搜索迷宫路径voidresult(Seqstack*s);//输出迷宫路径(2)源文件source.cpp#include"head.h"#include<iostream>#include<time.h>#include<stdlib.h>usingnamespacestd;intmain(){intm,n,mm,nn,mark=0;zuobiaomove[4];//定义方向数组，包含上、下、左、右四个方向Init_Move(move);//MOVE方向数组初始化s1=Init_Seqstack();//栈1初始化s2=Init_Seqstack();//栈2初始化while(1){intchoice;一一一一 coutvv*************************************************vvendl：coutvv"*1：产生随机迷宫2：输出可行的所有路径3退出*"vvendl;一"一一 ■■coutvv*************************************************vvendl;coutvv"请输入操作代码：”；cin>>choice;switch(choice){case1:number=0;//可行路径条数初始化coutvv"输入迷宫大小(行数，列数)：":cin>>mm>>nn;//输入迷宫行列数if(mm>25lln>25)coutvv"迷宫地图太大，无法生成"vvendl;elseif(mmv1llnnv1)coutvv"参数错误，无法生成迷宫"vvendl;else{m=mm+2;n=nn+2;mark=-1;//mark初始化while(number==0)//直到找到所有迷宫的可行路径为止{Init_Maze(m,n);//产生随机迷宫Maze(move,m,n,mark);//搜索迷宫可行路径}cout<<"产生随机迷宫成功："<<endl;output(m,n);//显示迷宫cout<<endl;}break;case2:number=0;//可行路径条数初始化if(mark==0)cout<<"未产生随机迷宫，请先生成随机迷宫"<<endl;else{mark=1;//mark赋值为1表示再次搜索路径时输出路径Maze(move,m,n,mark);//搜索路径并输出可行路径coutvv"迷宫共有"vvnumbervv"条可行路径"<<endl;cout<<endl;}break;case3:exit(1);default:coutvv"输入错误，请重新输入"vvendl;}}return0;}Seqstack*Init_Seqstack(){Seqstack*s;s=newSeqstack;s->top=-1;returns;}〃栈初始化voidPush_Seqstack(Seqstack*s,Datatypeitem){s->top++;s->data[s->top].x=item.x;s->data[s->top].y=item.y;s->data[s->top].d=item.d;}//入栈voidPop_Seqstack(Seqstack*s,Datatype*item){(*item).x=s->data[s->top].x;(*item).y=s->data[s->top].y;(*item).d=s->data[s->top].d;s->top--;}//出栈voidInit_Move(zuobiaomove[4]){move[0].x=0;move[0].y=1;//向右move[1].x=1;move[1].y=0;//向下move[2].x=0;move[2].y=-1;〃向左move[3].x=-1;move[3].y=0;//向上}//MOVE方向数组初始化voidInit_Maze(intm,intn){inti,j;srand((unsigned)time(NULL));for(i=0;i<m;i++)//对迷宫数组遍历for(j=0;j<n;j++){if(i=0||i=m-1llj=0llj=n-1)//迷宫外围墙壁maze[i][j]=1;elsemaze[i][j]=rand()%2;//产生0或1的随机数}maze[m-2][n-2]=0;//出口可行maze[1][1]=-1;//入口不可重复}〃产生随机迷宫，左上角为入口，右下角为入口voidMaze(zuobiaomove[4],intm,intn,intmark){intx,y,d,i,j;item.x=item.y=1;//初始化入口坐标item.d=-1;Push_Seqstack(s1,item);while(s1->top!=-1)//栈空则搜索完毕，否则继续搜索{Pop_Seqstack(s1,&item);if(item.d!=-1)maze[item.x+move[item.d].x][item.y+move[item.d].y]=0;x=item.x;y=item.y;d=item.d+1;while(d<4)//每个节点的四个方向均搜索一遍{i=x+move[d].x;j=y+move[d].y;if(maze[i][j]=0)//下一个节点可行{item.x=x;item.y=y;item.d=d;Push_Seqstack(s1,item);//压入栈中x=i;y=j；maze[x][y]=-1;//表示已经走过的路径，以防重复if(x==m-2&&y==n-2)//输出迷宫路径并且搜索下条可行路径{number++;//可行路径条数加1maze[x][y]=0;//初始化终点坐标if(mark==1)result(s1);//输出可行路径d++;x=s1->data[s1->top].x;y=s1->data[s1->top].y;}elsed=0;//方向初始化}elsed++;//从下一个方向开始}}}〃搜索迷宫路径voidresult(Seqstack*s1){cout<<"第"<<number<<"条可行路径："<<endl;while(s1->top!=-1)//将栈1中路径倒入栈2{Pop_Seqstack(s1,&item);//出栈1Push_Seqstack(s2,item);//入栈2}while(s2->top!=-1)//将栈2中路径倒入栈1，同时输出路径顺序{Pop_Seqstack(s2,&item);〃出栈2cout<<"("<<item.x<<","<<item.y<<")";if(item.d==0)cout<<"f";if(item.d==1)cout<<"I";if(item.d==2)cout<<"";if(item.d==3)cout<<"t";Push_Seqstack(s1,item);//入栈1}cout<<endl;}〃输出迷宫路径voidoutput(intm,intn){inti,j;for(i=0;i<m;i++){for(j=0;j<n;j++){if(maze[i][j]==-1)maze[i][j]=0;//恢复迷宫cout<<maze[i][j]<<"";//显示迷宫}cout<<endl;}}〃显示迷宫附录2：哈夫曼编码问题源代码：(1)头文件head.h#defineMAXVALUE1000//定义最大权值#defineMAXBIT100//定义哈夫曼树中叶子结点个数typedefstruct{chardata;//字符值intnum;//某个值的字符出现的次数}TotalNode;〃统计结点，包括字符种类和出现次数typedefstruct{TotalNodetot[300];//统计结点数组intnum;//统计数组中含有的字符个数}Total;〃统计结构体，包括统计数组和字符种类数typedefstruct{charmes[300];//字符数组intnum;//总字符数}Message;〃信息结构体，包括字符数组和总字符数typedefstruct{intlocked[500];//密码数组intnum;//密码总数}Locking;〃哈夫曼编码后的密文信息typedefstruct{chardata;//字符intweight;//权值intparent;//双亲结点在数组HuffNode[]中的序号intlchild;//左孩子结点在数组HuffNode[]中的序号intrchild;//右孩子结点在数组HuffNode[]中的序号}HNodetype;〃哈夫曼树结点类型，包括左右孩子，权值和信息typedefstruct{intbit[MAXBIT];intstart;}HCodetype;〃哈夫曼编码结构体，包括编码数组和起始位voidreading_file(Message*message);//从文件中读取信息voidwriting_file(Message^message);//将信息写进文件voidtotal_message(Message*message,Total*total);//统计信息中各字符的次数voidHaffmanTree(Total*total,HNodetypeHuffNode[]);//构建哈夫曼树voidHaffmanCode(HNodetypeHuffNode[],HCodetypeHuffCode[],Total*total);//建立哈夫曼编码voidwriting_HCode(HNodetypeHuffNode[],HCodetypeHuffCode[],Total*total);//将编码规则写进文件voidlock(Message*message,HNodetypeHuffNode[],HCodetypeHuffCode[],Total*total,Locking^locking);//给文件信息加密编码voidwriting_lock(Locking*locking);//将已编码信息写进文件voidwriting_translate(Locking*locking,HCodetypeHuffCode[],HNodetypeHuffNode[],Total*total);//将已编码信息翻译过来并写进文件(2)源文件source.cpp#include"head.h”#include<iostream>#include<fstream>usingnamespacestd;intmain(){inti,j,choice,mark=0;//mark标记文件信息是否读入到内存中HNodetypeHuffNode[500];//保存哈夫曼树中各结点信息HCodetypeHuffCode[300];Locking^locking;Total*total;Message*message;locking=newLocking;locking->num=0;total=newTotal;total->num=0;message=newMessage;message->num=0;〃初始化变量while(1){J一-II“““““““““““““““““““““““““““““““““““““““““““““““““““““““““““11

cout<<***********************************************************;cout<<"*1:从文件读取信息 2：显示编码规则 3：将原文件信息写进文件*";cout<<"*4:将编码规则写进文件 5：将编码后的信息写进文件6：将译码后的信息写进文件7：退出*";一"一一■■cout<<*****************************************************<<enQi:cout<<"请输入操作代码："；cin>>choice：switch(choice){case1:reading_file(message)：//从文件中读取信息mark=1;break：case2://显示编码规则if(mark=0)cout<<"请先从文件中读取信息!"<<endl：else{total_message(message,total)：//统计信息中各字符的出现次数HaffmanTree(total,HuffNode);//构建哈夫曼树HaffmanCode(HuffNode,HuffCode,total)：//建立哈夫曼编码for(i=0：ivtotal->num：i++)//显示编码规则{coutvvtotal->tot[i].data<<”":for(j=HuffCode[i].start+1：j<total->num：j++)cout<<HuffCode[i].bit[j]：cout<<endl：}}break：case3://将原文件信息写进文件if(mark=0)cout<<"请先从文件中读取信息!"<<endl：elsewriting_file(message)：//将信息写进文件break：case4://将编码规则写进文件if(mark=0)cout<<"请先从文件中读取信息!"<<endl：else{total_message(message,total)：//统计信息中各字符的出现次数HaffmanTree(total,HuffNode);//构建哈夫曼树HaffmanCode(HuffNode,HuffCode,total);//建立哈夫曼编码writing_HCode(HuffNode,HuffCode,total);//将编码规则写进文件}break;case5://将编码后的信息写进文件if(mark==0)cout<<"请先从文件中读取信息!"<<endl;else{total_message(message,total);//统计信息中各字符的出现次数HaffmanTree(total,HuffNode);//构建哈夫曼树HaffmanCode(HuffNode,HuffCode,total);//建立哈夫曼编码lock(message,HuffNode,HuffCode,total,locking);//给文件信息加密编码writing_lock(locking);//将已编码信息写进文件}break;case6://将译码后的信息写进文件if(mark==0)cout<<"请先从文件中读取信息!"<<endl;else{total_message(message,total);//统计信息中各字符的出现次数HaffmanTree(total,HuffNode);//构建哈夫曼树HaffmanCode(HuffNode,HuffCode,total);//建立哈夫曼编码writing_translate(locking,HuffCode,HuffNode,total);//将已编码信息翻译过来并写进文件}break;case7:exit(1);default:cout<<"输入错误，请重新选择"<<endl;}}for(i=0;i<locking->num;i++)if(locking->locked[i]==-1)cout<<"";elsecout<<locking->locked[i];cout<<endl;for(i=0;i<total->num;i++)cout<<total->tot[i].data<<""<<total->tot[i].num<<endl;for(i=0;i<2*(total->num)-1;i++)cout<<HuffNode[i].parent<<"";cout<<endl;return0;}voidreading_file(Message*message){/打开reading文件，失败则结束。不断读取字符并保存进message数组中，直到遇到#结束，记录字符总数*/inti=0;charch;ifstreaminfile("c:\\reading.txt”,ios::in|ios::out);if(!infile)//打开失败则结束{cout<<"打开c:\\reading.txt文件失败"<<endl;exit(1);}elsecout<<"读取文件成功"<<endl;while(infile.get(ch)&&ch!='#')//读取字符直到遇到#{message->mes[i]=ch;i++;}message->num=i;//记录总字符数infile.close();//关闭文件}〃从文件中读取信息voidwriting_file(Message^message)//将信息写进文件{/*打开writing文件，失败则结束。将信息写进文件*/inti;ofstreamoutfile("c:\\writing.txt”,ios::inlios::out);//打开文件if(!outfile)//打开失败则结束{cout<<"打开c:\\writing.txt文件失败"<<endl;exit(1);}for(i=0;i<message->num;i++)//写文件outfile.put(message->mes[i]);cout<<"信息写进文件成功"<<endl;outfile.close();//关闭文件}〃将原信息写入文件voidtotal_message(Message*message,Total*total){/*将message中的字符种类及出现次数统计保存到total数组中，重复字符用mark标记，否则新建字符种类。记录下字符种类的个数*/inti,j,mark;for(i=0;i<message->num;i++)//遍历message中的所有字符信息{if(message->mes[i]!='')//字符不为空格时{mark=0;for(j=0;j<total->num;j++)//在total中搜索当前字符if(total->tot[j].data==message->mes[i])//搜索到，则此字符次数加1，mark标志为1{total->tot[j].num++;mark=1;break;}if(mark==0)//未搜索到，新建字符种类，保存进total中，字符类加1{total->tot[total->num].data=message->mes[i];total->tot[total->num].num=1;total->num++;}}}}〃统计信息中各字符的出现次数voidHaffmanTree(Total*total,HNodetypeHuffNode[]){/*通过每次选取最小和次小两权值建立二叉树，最终构建成哈夫曼树，且左孩子权值比右孩子小*/inti,j,min1,min2,x1,x2;for(i=0;i<2*(total->num)-1;i++)//初始化哈夫曼树并存入叶子结点权值和信息{if(i<=total->num-1)HuffNode[i].data=total->tot[i].data;HuffNode[i].weight=total->tot[i].num;HuffNode[i].parent=-1;HuffNode[i].lchild=-1;HuffNode[i].rchild=-1;}for(i=0;i<total->num-1;i++){min1=min2=MAXVALUE;x1=x2=0;for(j=0;j<total->num+i;j++)//选取最小x1和次小x2的两权值{if(HuffNode[j].parent==-1&&HuffNode[j].weight<min1){min2=min1;x2=x1;min1=HuffNode[j].weight;x1=j;elseif(HuffNode[j].parent==-1&&HuffNode[j].weight<min2)min2=HuffNode[j].weight;{x2习；}}HuffNode[x1].parent=total->num+i;//修改亲人结点位置HuffNode[x2].parent=total->num+i;HuffNode[total->num+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;HuffNode[total->num+i].lchild=x1;//左孩子比右孩子权值小HuffNode[total->num+i].rchild=x2;}}〃构建哈夫曼树voidHaffmanCode(HNodetypeHuffNode[],HCodetypeHuffCode[],Total*total){/*在建立的哈夫曼树基础上，左分支为0,右分支为1,从叶结点向上直到根结点建立哈夫曼编码，并保存每个叶结点起始位*/inti,j,c,p;HCodetypecd;for(i=0;i<total->num;i++)//建立叶子结点个数的编码{cd.start=total->num-1;//起始位初始化p=HuffNode[i].parent;c=i;while(p!=-1)//从叶结点向上爬直到到达根结点{if(HuffNode[p].lchild==c)//左分支则为0cd.bit[cd.start]=0;elsecd.bit[cd.start]=1;//右分支则为1cd.start--;//起始位向前移动c=p;p=HuffNode[p].parent;}for(j=cd.start+1;j<total->num;j++)//保存求出的每个叶结点编码和起始位HuffCode[i].bit[j]=cd.bit[j];HuffCode[i].start=cd.start;}}〃建立哈夫曼编码voidwriting_HCode(HNodetypeHuffNode[],HCodetypeHuffCode[],Total*total){/*打开HCode文件，失败则结束。将信息写进文件*/inti,j;ofstreamoutfile("c:\\HCode.txt",ios::inlios::out);if(!outfile)//打开失败则结束{cout<<"打开c:\\HCode.txt文件失败"<<endl;exit(1);}for(i=0;ivtotal->num;i++)//写文件{outfile.put(HuffNode[i].data);outfile<<"";for(j=HuffCode[i