(论文)数据结构课程设计 迷宫问题求解系统的设计哈弗曼编码译码求解系统的设计交通咨询系统设计最新优秀毕业论文资料搜集呕血奉献

课程设计报告报告题目： 迷宫问题求解系统的设计 哈弗曼编码译码求解系统的设计 交通咨询系统设计 作者所在系部： 计算机科学与工程系 作者所在专业： 计算机科学与技术专业 作者所在班级： 作 者 姓 名 ： 作 者 学 号 ： 指导教师姓名： 完 成 时 间 ： 学院教务处制课程设计任务书课题名称数据结构课程设计完成时间指导教师职称学生姓名班级总体设计要求总体设计要求：题目：1、交通咨询系统设计（1）创建图的存储结构使用邻接矩阵。（2）查询分为两类。一类是能让旅客咨询从一个城市到另外所有城市的最短路径（要求使用迪杰斯特拉算法），显示出所有路径，按升序排列。第二类是任意 两个城市间的最短路径（要求使用弗洛伊德算法），显示最短路径。2、迷宫问题（1）迷宫中不能使用递归算法查找路径。（2）试探方向限定为上、下、左、右四个方向。（3）迷宫要随机生成。（4）生成从迷宫入口到出口的所有路径。3、哈弗曼编码译码（1）建立一个文本文件，统计该文件中各字符频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成原文件。工作内容及时间进度安排第一周、周：设计动员，分组，布置课程设计任务。第一周、周2：查阅资料，制定方案，进行程序总体设计。第一周、周3第二周2：详细设计, 系统调试。第二周、周3：整理，撰写设计报告。第二周、周4-周5：验收，提交设计报告，评定成绩。毕业设计成果1、课程设计报告书一份2、源程序清单一份3、成果使用说明书一份摘 要通过一学期的数据结构学习，我们对程序设计有了更为深刻地理解和感触，同时我们学习中也存在很多的问题和不足，发现这些缺点和不足并改进是我们进步的重要方法。这次课程设计让我们自己动手去解决实际问题既加深我们对程序设计的理解又让我们体会到学以致用的真谛。本文利用C+语言编写程序，在Microsoft Visual C+ 6.0的开发环境下实现了三个课题的设计：课题一，实现了交通咨询系统的创建；课题二，实现了对迷宫问题求解系统的创建；课题三，实现了对信息进行哈弗曼编码译码求解系统的创建。课题一，交通咨询系统主要有两个功能某块：查找从一个城市到所有城市的路程、时间、花费的最优路径，任意两个城市间的路程、时间、花费的最优路径。 课题二，迷宫问题求解系统主要有两个功能模块：创建并显示迷宫矩阵、输出每一条走出迷宫的路径。课题三，哈弗曼编码译码求解系统主要有两个功能某块：对信息进行哈弗曼编码，将哈弗曼编码翻译成字符信息。三个课题均已经过全面的系统测试，能够很好的运行，达到了预期的效果。关键词：系统设计 数据结构 迷宫 哈弗曼编码 最短路径 目 录第1章 绪论11.1 课程设计选题的目的及意义11.2 选题的背景11. 2.1 理论研究基础11.2.2 技术层面的支持11.3 课题研究的主要内容21.3.1迷宫问题求解系统的主要内容21.3.2 哈弗曼编码译码系统的主要内容21.3.3交通咨询系统的主要内容2第2章 系统需求分析32.1 问题的提出32.2 系统的设计目标32.3 系统的实现设计32.3.1 交通咨询系统的实现设计32.3.1 迷宫问题求解系统的实现设计42.3.3哈弗曼编码译码求解系统的实现设计42.4 测试数据52.4.1 交通咨询系统52.4.2 迷宫问题求解系统102.4.3哈弗曼编码译码求解系统11第3章 概要设计133.1 设计思想133.2 实现方法133.3 系统中主要函数及其关系143.3.1交通咨询系统143.3.2迷宫求解系统153.3.3哈弗曼编码译码求解系统15第4章 详细设计164.1 实现定义的数据类型164.2 实现定义伪代码算法164.2.1 交通咨询系统实现定义操作伪代码164.2.2 迷宫问题求解系统实现定义操作伪代码174.2.3哈弗曼编码译码求解系统174.3 实现操作伪代码算法184.2.1 交通查询系统实现操作伪代码184.2.2 迷宫问题求解系统实现操作伪代码214.2.3哈弗曼编码译码求解系统实现操作伪代码23第5章 系统调试分析265.1 问题描述265.2 问题的解决方案265.3设计实现的回顾讨论和分析265.4分析算法以及经验和体会27第6章 测试结果286.1交通咨询系统测试结果286.2迷宫问题求解系统测试结果336.3哈弗曼编码译码求解系统测试结果34总 结37致 谢38参考文献39附 录40第1章 绪论现代社会生活里汽车、火车、飞机、磁悬浮列车等各种形式交通工具的出现无疑为我们的出行带来了便捷，可与此同时它也给我们带来了麻烦。面对如此多的信息，我们该如何快速有效的将它传达给广大旅客，作为各大交通工具的经营者又该如何高效的处理这些多变的信息？实现信息化管理是快节奏生活对我们提出的要求。就像是一个复杂的迷宫求解问题，人工来解决必然行得通，但也必然需要一定时间。而如果我们采用电脑自动化去解决，势必会大大缩短我们求解问题的时间，提高我们的工作效率。在信息化管理中信息的传递是一个重要环节，哈弗曼编码可以保障高效安全的传递信息，为信息化管理提供方便。因此，要提升企业竞争力，就要大力推进企业信息化建设，实现企业的信息化管理，利用先进的办公自动化系统来实现企业内部信息管理、共享及交流，才能使企业在竞争激烈的21世纪取得先机。目前随着信息产业的飞速发展，信息化管理已经引入并应用到各行业管理领域。1.1 课程设计选题的目的及意义信息化管理逐步应用到各行各业，并逐渐成为各大企业竞争的焦点。本课题立足实现信息化管理的理念，从迷宫问题的求解，哈弗曼编码译码的求解，交通咨询系统的创建三个方面探究实现信息化的途径，对现实的发展具有实际的借鉴意义，对即将步入社会的我们更是一次锻炼解决实际问题的机会。1.2 选题的背景1. 2.1 理论研究基础（1）C+程序设计语言基础；（2）计算机的基本操作技能；（3）数据结构基础知识；（4）基于Microsoft Vitual C+ 6.0开发环境下的软件开发技能；（5）基本程序设计思路、思想。1.2.2 技术层面的支持硬件设备：计算机软件支持：Microsoft Vitual C+ 6.0开发环境1.3 课题研究的主要内容1.3.1迷宫问题求解系统的主要内容（1）创建一个迷宫问题；（2）输出迷宫矩阵；（3）输出一条迷宫路径。1.3.2 哈弗曼编码译码系统的主要内容（1）统计文章中每个字符出现的频率；（2）创建哈弗曼树；（3）规定编码规则；（4）对信息进行哈弗曼编码；（5）将哈弗曼编码翻译成信息；1.3.3交通咨询系统的主要内容（1）创建公路图；（2）求一个城市到所有城市的最优路径；（3）求任意两个城市间的最优路径；第2章 系统需求分析随着人们生活水平的提高及各种便捷交通工具的出现，越来越多的人选择假期出行。根据不同的标准，人们往往需要不同的最优路径。因此交通信息管理部门计划出不同的行车路线，迅速适应客户的新需求和市场新机遇，是时代对交通信息管理部门的要求。随着社会的发展信息也越来越繁琐，信息的传递也变的多种多样，这就需要有一种方法使信息高效安全的传递，哈弗曼编码译码就提供了这样一种方法。此外，当今人们日益加快的生活节奏，让我们看到信息化不仅仅应用在管理领域，人们也在利用信息化去解决一些繁琐的问题，迷宫求解问题就是一个很好的例子。2.1 问题的提出（1）交通系统越来越发达，人们出行的目的和选择出行路线的标准也多种多样。因此就需要设计一个系统，为不同人的不同需求提供不同的出行路线。（2）人们生活节奏加快已经是一个不争的事实，将复杂而重复的工作转交给计算机来处理更是日渐普遍。作为复杂而重复的迷宫问题交由计算机来处理是再好不过的选择了。（3）信息的传递最重要的就是要高效安全，从而可以加快信息的交流，保障其准确性。人们一直在不断的寻找一种更加高效安全的传递方式。2.2 系统的设计目标（1）交通咨询系统：本系统是对航班的信息包括起点、终点、不同标准的最优路径及其途径的城市等进行一体化管理的软件，其核心思想是实现对交通信息查询的管理。（2）哈弗曼编码译码系统：本系统实现对信息的编码，对哈弗曼编码的解码。（3）迷宫问题求解系统：本系统的核心思想是实现一条迷宫路径的求解。2.3 系统的实现设计2.3.1 交通咨询系统的实现设计（1）输入输出形式和输入输出值范围：本系统最多可容纳100个城市信息的录入，输入时从文件读入城市的实际个数，公路条数，城市名称，城市代号及两个直接相邻城市间的路程、花费、时间。若输入失败则显示提示信息。城市代号的取值范围是125，不相通的两城市间的信息为100000。（2）系统功能的实现：设置void GreateMGraph(MGraph *G)函数实现城市信息信息的创建。定义void LShortestPath_1(MGraph *G,int v0)函数求出给定城市到其他城市的最短距离路径及其途经城市，定义void FShortestPath_1(MGraph *G,int v0)求出给定城市到其他城市的最少花费路径及其途经城市，定义void TShortestPath_1(MGraph *G,int v0)求出给定城市到其他城市的最少时间路径及其途经城市。设置void LShortestPath_2(MGraph*G,CostType D,CostType P)求出任意两城市间的距离最优路径及其途经城市，设置void FShortestPath_2(MGraph*G,CostType D,CostType P)求出任意两城市间的花费最优路径及其途经城市，设置void TShortestPath_2(MGraph*G,CostType D,CostType P)求出任意两城市间的时间最优路径及其途经城市。2.3.1 迷宫问题求解系统的实现设计（1）输入输出形式和输入输出值范围：本系统最大支持100100迷宫问题的求解，输入时迷宫中元素的值为0或1，由系统随机生成，其中1代表不通0代表通路。寻找路径前输入迷宫的入口及出口，当输入信息有误时则给以提示重新录入。（2）系统功能的实现：设置void creat(int a,int b,int r1,int s1,int r2,int s2)函数实现随机创建一个迷宫，设置void display_migong(int a,int b)函数实现迷宫矩阵的输出，设置void find(int a,int b,int r1,int s1,int r2,int s2)函数实现迷宫路径的求解，设置栈来存放找到的路径并设置void display()函数输出迷宫的具体路径。系统最终要能给出任一可求解迷宫问题的所有路径。2.3.3哈弗曼编码译码求解系统的实现设计（1）输入输出形式和输入输出值范围：本系统中出现的字符种类最多有100种。文章中涉及的的字符种类，信息内容从，翻译后的编码均从文件读入，若读入失败则给出相关提示信息。信息内容以#结束。哈弗曼编码由0和1组成，向哈弗曼树的右子树走用1表示，向哈弗曼树的左子树走用0表示。（2）系统功能的实现：设置void Leaf_Value()函数初始化叶结点，设置HNodeType *HaffmanTree()函数构建哈弗曼树，设置void HaffmanCode()函数规定编码规则，定义void Translate_word()函数对信息进行哈弗曼编码，定义void Translate()函数将编码翻译成信息原文。2.4 测试数据2.4.1 交通咨询系统（1）正确的输入及输出（1）正确输入及输出图21进入1号查询界面图22北京到其他城市距离最优路径图23用代号在1号菜单中查询时间最优路线图24在1号菜单中株州到其他城市的时间最优路径图25在1号菜单中郑州到其他城市的花费最优路径图26在1号菜单中郑州到其他城市的花费最优路径图27在2号菜单中郑州到南宁的三种最优路径（2）错误的输入及输出图28主界面输入错数据图29下级菜单输入错误图210两个城市间查询界面输入错误数据2.4.2 迷宫问题求解系统（1）正确的输入及输出（1）正确输入及输出图211输出迷宫所有路径图212迷宫没有路径（2）错误的输入及输出图213输入错误数据2.4.3哈弗曼编码译码求解系统（1）正确输入及输出图214部分编码规则图215文章编码图216将译码输入到文件中（2）错误的输入及输出图217操作输入错误第3章 概要设计3.1 设计思想（1）交通咨询系统：进入系统主界面就是键入操作选择，包括查询某城市到所有城市的最优路线，查询任意两城市间的最优路线及退出三项功能选项。进入查询某城市到所有城市的最优路线后，有距离最优，时间最优，费用最优，退出四个功能选项，最优功能选项中又有用城市名查询，用城市代号查询，退出该查询三个功能选项。进入查询任意两城市间的最优路线后，有用城市名查询，用城市代号查询，退出该查询三个功能选项，再进入下一级菜单后又有距离最优，时间最优，费用最优，退出四个功能选项。（2）迷宫问题求解系统：系统主界面是寻找迷宫路径及退出的两个操作选择，进入迷宫问题求解系统后，给以输入提示，然后录入迷宫大小、入口、出口，录入结束后输出迷宫矩阵和求解了，路径。（3）哈弗曼编码译码求解系统：进入系统主界面就是操作选择键，包括设置哈弗曼编码规则，将文章译成码，将哈弗曼编码解码，退出四项功能选项。进入哈弗曼编码规则后会输出各个字符的哈弗曼编码规则；进入将文章译成码选项后将翻译成的编码输出到相应文件中，并显示“文章编码成功！”的提示语；进入解码选项后输出解码后的信息。3.2 实现方法（1）交通咨询系统：以路程、费用、时间最为权值，用一个二维数组存储交通图城市间的信息，并且将路程、费用、时间三个变量封装在一个结构体内。将二维数组、城市信息、城市个数、公路条数封装在一个结构体内，并将其定义成一个用邻接矩阵存储的图。在弗洛伊德算法中将每次查找的前驱、和的最小权值、最优路径的终点城市代号封装在一个结构体中，以便于按路径的权值从小到大进行排序。对路程、时间、费用分别调用迪杰斯特拉算法和弗洛伊德算法求出不同的最优路径。（2）迷宫问题求解系统：将迷宫中的元素，元素的移动方向、坐标、进栈标志封装在一个结构体中。用循环语句实现迷宫元素的随机生成及迷宫矩阵的输出；用二维数组来存储迷宫信息；迷宫中定义move数组，从上开始顺时针向四个方向试探出路。定义一个栈，栈中存放已找到通路的迷宫的信息。栈的元素是由迷宫的坐标、进栈标志组成的结构体。（3）哈弗曼编码译码求解系统：从文件中读入数据初始化叶结点，从文件中读入信息统计结点字符的权值。利用静态链表存储结构，构建哈弗曼树。将读入的信息根据哈弗曼树译成哈夫曼编码，左子树用字符0标记，右子树用字符1标记。从根结点开始搜索，遇到0向左走，遇到1向右走，将编码翻译成字符信息。3.3 系统中主要函数及其关系3.3.1交通咨询系统一个城市到其他城市的最优路径距离最优：LShortestPath_1()时间最优：TShortestPath_1()费用最优：FShortestPath_1()任意两城市间最优路径输出函数Shortest_display()邻接矩阵存储图GreateMGraph() 主函数main()距离最优：LShortestPath_2()时间最优：TShortestPath_2()费用最优：FShortestPath_2()图313.3.2迷宫求解系统创建迷宫creat();输出迷宫display_migong()搜索迷宫路径find()主函数main()入栈push()出栈pop()输出迷宫路径display() 图323.3.3哈弗曼编码译码求解系统叶结点初始化Leaf_Value()构建哈弗曼HaffmanTree()哈弗曼编码规则HaffmanCode()编码Translate_word()译码Translate()主函数main() 图33第4章 详细设计4.1 实现定义的数据类型（1）交通咨询系统：时间、路程、费用为整型并将其封装在一个结构体内，城市代号，城市个数，公路条数为整型，城市名称为字符串类型。（2）迷宫问题求解系统：迷宫信息定义为由整型组成的结构体，迷宫数组定义为该结构体数组，迷宫出口和入口的值定义为整型，迷宫move数组定义为结构体整型数组。（3）哈弗曼编码译码系统：结点元素定义为字符类型，哈弗曼树结点定义为由整型数据组成的结构体，字符编码定义为由字符数组构成的结构体4.2 实现定义伪代码算法4.2.1 交通咨询系统实现定义操作伪代码（1）权值的结构体：typedef struct 时间；费用；路程；CostType;（2）邻接矩阵的结构体：typedef struct 城市代号； CostType 定义 权值信息； 城市个数；边的条数；MGraph（3）弗洛伊德算法中的结构体：typedef struct前驱；最小权值；终点城市代号； HomeType;4.2.2 迷宫问题求解系统实现定义操作伪代码（1）迷宫数组char mazemn。（2）迷宫出口、入口(r1,s1) (r2,s2)（3）迷宫移动数组move4typedef structint x2;int y2;item;item move4= -1,0,0,1,1,0,0,-1 （4）迷宫信息结构体：typedef struct 迷宫元素； 坐标x,y； 进栈标志； 移动方向；nodetype; 迷宫数组：nodetype datamaxsizemaxsize;4.2.3哈弗曼编码译码求解系统（1）叶结点结构体定义：typedef struct 叶结点字符； 叶结点权值Leaf;叶结点数组：Leaf leafMAXLEAF;（2）哈弗曼树结点定义： typedef struct 权值； 双亲； 右子树； 左子树；HNodeType; 哈弗曼树结点数组：HNodeType HuffNodeMAXNODE;（3）哈弗曼编码结构体： typedef struct 一个字符的哈弗曼编码数组； 在数组中编码的起始位置；HCodeType;HCodeType HuffCodeMAXLEAF;4.3 实现操作伪代码算法4.2.1 交通查询系统实现操作伪代码（1）邻接矩阵初始化：void GreateMGraph(MGraph *G) 从文件中读入城市个数Vnum，公路条数Enumfor(j=1;jVnum;j+)用最大值初始化城市间的信息for(k=0;kEnum;k+)/从文件中读取边上的3个权值及对应的顶点的信息从文件中读入公路信息for(i=1;iVnum;i+)从文件中读入城市名；（2）迪杰斯特拉算法：void LShortestPath_1(MGraph *G,int v0)finalMaxVertexNum;标志数组/home.P前驱下标，home.D是最短路径长度HomeType homeMaxVertexNum; for(v=1;vVnum;v+) 初始化finalMaxVertexNumhome.P，home.Dhomev0.D=MAXCOST;homev0.P=-1;/开始主循环，每次求得V0到某个顶点V的最短路径 for(i=1;iVnum;i+)min=MAXCOST;for(w=1;wVnum;w+)/选出D中最小值if(!finalw)if(homew.Dmin)v=w;min=homew.D;finalv=1;for(w=1;wVnum;w+)/修改Dw,Pwif(!finalw&(min+G-edgesvw.Longedgesvw.Long;homew.P=v;/结束主循环for(i=1;iVnum;i+)/输出最短路径if(homei.P=-2)coutmax:iendl;else if(homei.end!=v0)cout最短路径长度:homei.Dendl;cout最短路径:Cityhomei.end(homei.end);/到i的最短路径pre=homei.P;while(pre!=v0)int loca;cout-Citypre(pre);for(loca=1;locaVnum&homeloca.end!=pre;loca+)pre=homeloca.P;cout-Cityv0(v0)endl;（3）弗洛伊德算法：void LShortestPath_2(MGraph*G,CostType D,CostType P)/D路径带权长度，P前驱int v,w,u;for(v=1;vVnum;v+)for(w=1;wVnum;w+)Dvw.Long=G-edgesvw.Long;if(Dvw.LongMAXCOST)Pvw.Long=v;else if(v!=w)Pvw.Long=-2;elsePvw.Long=-1;for(u=1;uVnum;u+)for(v=1;vVnum;v+)for(w=1;wVnum;w+)if(Dvu.Long+Duw.LongDvw.Long)Dvw.Long=Dvu.Long+Duw.Long;Pvw.Long=Puw.Long;（4）将最短榉距离按升序排列：void Sort(MGraph *G,HomeType *home)int t,i,j;/用选择法按最短距离排序for(i=1;iVnum;i+)for(j=i;jVnum;j+)if(homei.Dhomej+1.D)交换homei和homej+1中的各个量4.2.2 迷宫问题求解系统实现操作伪代码（1）迷宫的创建：void creat(int a,int b,int r1,int s1,int r2,int s2)int i,j; srand(time(NULL); for(i=1;i=a;i+) for(j=1;j=b;j+)/对迷宫随机赋值 用随机函数初始化迷宫元素; 初始化迷宫结构体中的其他信息 设置出口和入口； （2）寻找迷宫路径：void find(int a,int b,int r1,int s1,int r2,int s2)p.top=-1;/栈的初始化int i,j;DataType z;/栈的结点类型，有三个元素,返回z起点入栈while(栈不为空)while(方向未探索完)i=p.dp.top.x+movep.dp.top.f.x;/改变搜索方向j=p.dp.top.y+movep.dp.top.f.y;if(通路且未被探索过)/若是通路则前进该点入栈,top增加1下一点搜索方向初始化if(找到出口)输出栈中信息，即一条路径栈尾元素出栈向该元素的下一个方向探索；;else 向下一个方向探索；继续出栈，向出栈元素的下一个方向探索；寻找结束!4.2.3哈弗曼编码译码求解系统实现操作伪代码（1）初始化叶结点：void Leaf_Value()从文件中读入叶结点个数leafnum，种类leafi.str；并初始化每种字符的权值leafi.value=0;逐个读入信息中的字符str；for(i=0;ileafnum;i+)f(lstr=已有字符)leafi.value+;（2）构造哈弗曼树：HNodeType *HaffmanTree()定义一个哈弗曼树结点数组HuffNodeMAXNODE；用leafnum个叶结点初始化HuffNodeMAXNODE；for(i=0;in-1;i+)从HuffNodeMAXNODE中选出权值最小的两个结点；权值m1m2，对应得位置分别为x1，x2；将两个结点合并为一棵二叉树，放到HuffNodeMAXNODE的后面；HuffNodex1.parent=n+i;HuffNodex2.parent=n+i;HuffNoden+i.weight=HuffNodex1.weight+HuffNodex2.weight;HuffNoden+i.lchild=x1;HuffNoden+i.rchild=x2;（3）哈夫曼编码规则：void HaffmanCode() HCodeType cd;/临时存放哈弗曼编码for(i=0;ileafnum;i+)/编辑每个字符的哈弗曼编码 cd.start=编码数组的末位置;p=第i个结点的双亲while(双亲存在)/用cd寻找每个字符的哈弗曼编码if(双亲的右孩子结点)编码为0;else编码为1;cd.start-;结点向上移动；双亲结点向上移动；/该循环结束后cd.start+1是编码的起始坐标for(j=cd.start+1;jMAXBIT;j+)/将哈弗曼编码放入HuffCodei.bitj数组中HuffCodei.bitj=cd.bitj;HuffCodei.start=cd.start;（4）将信息翻译成哈弗曼编码：void Translate_word()str初值=*；信息以#结束；while(str!=#)str=从文件中逐个读入信息字符；if(str=叶结点中的字符)cout该叶结点的哈弗曼编码；（5）.将编码译成字符信息：void Translate()int m;char t;/t为文件编码打开编码文件；while(!feof(in)，读入字符不为空)/哈夫曼编码译成文章 m=2*leafnum-2;/哈弗曼结点数组的末位置 while(结点的左右孩子结点存在) t=fgetc(in);/从文件读入编码 if(t=1) 向右孩子结点移动 else if(t=0) 向左孩子结点移动 cout输出翻译后的字符第5章 系统调试分析5.1 问题描述（1）交通咨询系统：a如何用数据结构存放城市及城市间的信息；b如何按权值大小排序而不影响输出路径；c如何进行城市编号和城市名称的转换；d如何将三种权值存放在一个邻接矩阵中。（2）迷宫问题求解系统：a如何随机生成迷宫；b该如何确定探索方向；c该如何保存探究出的路径；d该如何实现回溯；e如何找到从入口到出口的所有路径。（3）哈弗曼编码译码求解系统：a如何构造并存储哈弗曼树；b如何将信息翻译成哈弗曼编码；c如何将哈弗曼编码译成信息；5.2 问题的解决方案（1）交通咨询系统：a邻接矩阵存储城市及城市间的信息；b将找到的最小权值、终点城市及其前驱封装在一个结构体中，按权值大小对结构体进行排序；c将城市名称存放在一个数组中，数组下标即为城市编号；d将距离、时间、费用封装在一个结构体内，定义一个结构体类型的邻接矩阵；（2）迷宫问题求解系统：a调用随机函数对二维数组进行赋值；b用move数组初始化4个方向搜索迷宫通路；c用栈来保存探究的路径；d通过将元素进栈再逐个输出栈顶元素进行判断的形式来实现回溯，回溯位置存储在栈里；e找到一条路径后，让出口元素出栈，探索该元素的其他方向，若有通路进栈，不断向下探索直到找到出口输出路径，再重复出栈直到栈空为止；（3）哈弗曼编码译码求解系统：a用静态链表存储哈弗曼树，从结点中选出权值最小的两个结点，构造出一棵二叉树，直到将所有结点都放到二叉树中为止；b从叶结点开始向上遍历，若为右孩子结点则编码为1，若为右孩子结点则编码为0；c从根节点开始，若编码为1则向右孩子结点走，若编码为0则向左孩子结点走，直到找到叶结点为止；5.3设计实现的回顾讨论和分析（1）交通咨询系统：本系统主要是要实现交通线路咨询的一体化管理。从设计角度上来讲我的设计考虑了根据不同标准查询不同最优路线，同时也考虑了按城市编号和城市名称两种查询方式。虽然该系统设计了基本功能模块，但仍有不足之处，未能考虑到具体实施中可能面临的其它问题问题，如按不同的交通工具分类查询，路径途经城市最少等其他标准。此外查询界面不是特别理想，不太清晰。功能实现上来讲基本实现了不同的查询功能，但功能还不是特别全面，过于单一。（2）迷宫问题求解系统：本系统主要是寻找出，从出口到入口的迷宫的所有路径。从设计角度上讲，本系统基本实现了查找路径的要求。但设计上仍然存在不足，如不能进行人工手动查询，当没有路径时不能进行自动重新设置迷宫。从功能实现上看基本实现了要求。但从迷宫矩阵上看路径不是特别清晰。（3）哈弗曼编码译码求解系统：本系统主要是对信息进行哈弗码编码和译码。从设计角度上看，设计了对信息的编码和译码。但设计仍有不足之处，信息中字符的种类不能自动统计，只能统计字符频率；信息内容需要有一个结束字符标志，不便于自动操作。从功能上来讲，基本实现了对信息的编码和译码功能。但编码只由0、1字符组成，不能人工确定编码打组成字符。5.4分析算法以及经验和体会（1）交通咨询系统：本系统的算法时间复杂度为O（n3），代码比较简洁，将时间复杂度和空间复杂度彼此均衡，从整体上优化了算法。通过本系统的设计，理解了弗洛伊德算法和迪杰斯特拉算法的优越性，但是时间复杂度较大。在设计过程中，认识到了用数字处理问题的便捷性，但也看到了用字符显示的直观性。若输入字符信息只要在操作数字之前，将字符转换成数字即可；在操作结束后只要将数字进行一步转换即可显示字符信息。（2）迷宫问题求解系统：由于本系统功能比较简单，所以算法的时间复杂度和空间复杂度比较低。但算法不是特别易懂，代码不是很精简。在设计系统过程中充分感受到了栈先进后出的优越性。将找到的路径存放到栈中，再利用回溯法找到所有路径。（3）哈弗曼编码译码求解系统：本系统主要有三大算法：构建哈弗曼树，编码，译码。算法整体比较整洁易懂时间复杂度较小，但造成了占用空间较大。编码和译码是两个相反的过程，其算法既有相似性又有差异性。在编写过程中利用栈存储了编码，利用了其先进后出的特点将编码按正常顺序输出。第6章 测试结果6.1交通咨询系统测试结果（1）进入交通咨询系统主界面图61进入1号查询界面（2）进入查询一个城市到所有城市的最优路径界面图62北京到其他城市距离最优路径图63北京到其他城市距离最优路径图64北京到其他城市距离最优路径图65用代号在1号菜单中查询时间最优路线图66在1号菜单中株州到其他城市的时间最优路径图67在1号菜单中株州到其他城市的时间最优路径图68在1号菜单中株州到其他城市的时间最优路径图69在1号菜单中郑州到其他城市的花费最优路径图610在1号菜单中郑州到其他城市的花费最优路径图611在1号菜单中郑州到其他城市的花费最优路径（3）进入查询任意两个城市的最优路径界面图612在2号菜单中郑州到南宁的三种最优路径6.2迷宫问题求解系统测试结果图613进入迷宫求解系统图614输入迷宫信息图615输出迷宫及其所有路径6.3哈弗曼编码译码求解系统测试结果（1）进入哈弗曼编码译码求解系统图616主界面（2）规定编码规则 图617编码规则（3）对信息进行编码图618编码图619将编码输出到文件中（4）译码图620译码总 结以上系统通过调试运行，结果表明系统具有可行性与可扩充性，但系统还有待于进一步完善。系统的优点及创新：特色是界面提示信息较清楚，有比较好的容错机制，针对输入的错误信息可以给出错误提示，并可以继续输入正确操作，而不会退出系统。在交通咨询系统中即可输入城市名，又可输入城市代号，执行方便，便于使用。在设计过程中也采用了一些新的尝试，将同一类的数据封装在一个结构体内，处理时便于统一操作。例如在交通咨询系统中，将最小权值、前驱、终点数据封装在一个结构体内，便于按权值大小排序。不足和可改进的地方：用if语句设置的各级菜单层次感不是特别清晰，可以用switch语句设置层次感比较清晰地显示菜单。各个系统只是实现了基本的功能，不能完全应对实际中面临的问题。应进一步加强对实际问题的分析，增强系统的应变能力和容错能力。结束语：通过将近两周的课程设计练习，我在一定程度上巩固熟悉了所学的知识，锻炼了在实际问题中应用所学知识的能力。同时在另一方面也暴露了自己的不足，看到了自己知识面比较狭窄，对知识的综合运用和迁移能力比较弱，理论联系实际能力的不足，对实际问题的分析不够深度和广度。针对以上不足，在以后的实验和课程设计中，应加强对问题的分析，在实验之前做好整体规划。在设计过程中发现我所学知识有限，平时接触实际问题不多，在以后的学习中要扩大课外相关知识的学习，多参考课外书，对实际问题进行深入分析。此次课设中暴露的这些不足，是对我以前学习的一次总结也是我学习提高的一次机会，在以后的学习过程中，自己要多找一些实际问题进行分析，增强自己的实际应用能力。致 谢课程设计完成之际，我由衷地感谢指导老师的大力帮助和支持，感谢我的同学与朋友，在我遇到各种各样复杂问题的时候，给与我鼓励和帮助，使我的分析问题和解决问题能力有了很大的提高。课程设计期间，指导老师严肃的科学态度、严谨的治学精神、精益求精的工作作风深深地感染和激励着我。指导教师的严格要求促使我不断完善自己的课设，做出比较满意的成果。回顾整个课设过程，其中既有汗水，又有成功的喜悦。从体会了酸甜苦辣，让我变得更加有毅力，懂得了：坚强，勤奋。参考文献1刘振鹏，张小莉，郑艳娟. 数据结构. 北京：中国铁道出版社，20032谭浩强. C程序设计. 北京：清华