算法，用于地图的快速显示和查询。
注: 也可以完成课本第五章习题5.37题（P250）的代码设计作为本次课堂实验内容。
四、仪器设备: 计算机、VC++编译环境 五、实验方法：
用C++语言设计类，并实现相关类的基本操作，程序在VC++环境下调试通过。并选择恰当的测试数据验证算法的正确性。 六、实验步骤：
1、 在上机前提前完成设计代码； 2、 程序调试通过，可运行；
3、 通过测试数据和对象方法调用验证算法正确性。 七、实验结果处理：对程序调试中的问题要进行总结。
八、实验注意事项：独立完成实验及实验报告，抄袭者不给成绩。 九、预习与思考题：见课堂讲授课件和作业布置。
十、实验报告要求：本门课程实验报告格式见 附件1，鼓励手写，可以打印。
实验五 图的最短路径算法设计
实验类型： 验证性 实验学时：2学时
一、实验目的：
了解最短路径的概念，掌握求最短路径的方法(Dijkstra算法或Floyd算法)。 二、实验要求：
1、 C++完成图的相关类及算法的设计并上机调试通过。 2、 撰写实验报告，提供实验结果和数据。 三、实验内容:
建立一个包含6个结点的带权有向图，并求顶点V0到其它顶点的最短路径。 测试数据由同学们自行选择。
模拟简单的道路网数据进行交互式的最短路径查询算法（Dijkstra算法）示例。 注: 也可以完成课本第八章习题8.23题（P395）的代码设计作为本次课堂实验内容。
四、仪器设备: 计算机、VC++编译环境 五、实验方法：
用C++语言设计类，并实现相关类的基本操作，程序在VC++环境下调试通过。并选择恰当的测试数据验证算法的正确性。 六、实验步骤：
1、 在上机前提前完成设计代码； 2、 程序调试通过，可运行；
3、 通过测试数据和对象方法调用验证算法正确性。 七、实验结果处理：对程序调试中的问题要进行总结。
八、实验注意事项：独立完成实验及实验报告，抄袭者不给成绩。 九、预习与思考题：见课堂讲授课件和作业布置。
十、实验报告要求：本门课程实验报告格式见 附件1，鼓励手写，可以打印。
实验六 自定义类应用综合设计
实验类型： 综合性 实验学时：2学时
一、实验目的：
1、 进一步掌握各种数据结构的特点和适合解决问题的分析；
2、 通过具体的有实际应用意义的问题解决和对前面设计的类的使用进一步提高程
序设计能力和算法设计、分析能力。
3、 考察学生的程序设计中的逻辑思维能力和软件开发设计能力。 二、实验要求：
1、 完成程序或简单系统的设计并上机调试通过。 2、 撰写实验报告，提供实验结果和数据。 三、实验内容:
从下面给出的题目中选做其中的一题（多做可加分）： 1. 约瑟夫环问题
1）问题描述：有编号为1, 2?n 的 n 个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始给定一个正整数 m，从第一个人按顺时针方向自1开始报数，报到m者出列，不再参加报数，这时将出列者的密码作为m，从出列者顺时针方向的下一人开始重新自1开始报数。如此下去，直到所有人都出列。试设计算法，输出出列者的序列。
2）实验要求: 采用链式存储结构实现，结果可视化要友好。 3) 实现提示：用链式存储解决此问题时可以采用循环链表。 2. 停车场管理问题
1）问题描述：设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场的早晚依次从停车场最里面向大门口处停放(最先到达的第一辆车放在停车场的最里面)。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车走开，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。编写程序模拟该停车场的管理。
2）实验要求: 要求程序输出每辆车到达后的停车位置（停车场或便道上），以及某辆车离开停车场时应缴纳的费用和他在停车场内停留的时间。
3）实现提示：以栈模拟停车场，以队列模拟便道，按照从终端读入的车辆“到达”“离开”信息模拟停车场管理。 3. 实现一个哈夫曼编/译码系统
1）问题描述：利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码。对于双工信道，每端都需要一个完整的编码/译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。 2）实验要求：一个完整的系统应具有以下功能：
(1) I：初始化(Initialization)。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
(2) E：编码(Encoding)。利用已建好的哈夫曼树对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
(3) D：译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
(4) P：打印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。
(5) T：打印哈夫曼树(Tree printing)。将已在内存中的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。 3) 实现提示：
(1) 文件CodeFile的基类型可以设为字节型。
(2) 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退
出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“E”为止。
(3) 在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。
4. 利用最小生成树算法解决通信网的总造价最低问题
1）问题描述：若在n个城市之间建通信网络，秩序架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网络的最小生成树问题。 2）实验要求：利用克鲁斯卡尔算法求网的最小生成树
3) 实现提示：通信线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。为简单起见，图的顶点数不超过10个，网中边的权值设置成小于100。 5. 教学计划编制问题
1）问题描述：软件专业的学生要学习一系列课程，其中有些课程必须在其先修课完成后才能学习。
2）实验要求：假设每门课程的学习时间为一个学期，试为该专业的学生设计教学计划，使他们能在最短时间内修完专业要求的全部课程。 3) 实现提示：
以顶点代表课程，弧代表课程的先后修关系，按课程先后关系建立有向无环图。利用拓扑排序实现。
6．公交线路优化路径的查询 【问题描述】
对于某城市的公交线路，乘坐公交的顾客希望在这样的线路上实现各种优化路径的查询。设该城市的公交线路的输入格式为：
线路编号：起始站名(该站坐标)；经过的站点1名(该站坐标)；经过的站点2名(该站坐标)；??；经过的站点n名(该站坐标)；终点站名(该站坐标)。该线路的乘坐价钱；该线路平均经过多少时间来一辆；车速。
例如：63：A(32,45)；B(76,45)；C(76,90)；??；N(100,100) 。1元；5分钟；150米/每分钟。
假定线路的乘坐价钱与乘坐站数无关，假定不考虑公交线路在路上的交通堵塞。 对这样的公交线路，需要在其上进行的优化路径查询包括：任何两个站点之间最便宜的路径；任何两个站点之间最省时间的路径。 【设计要求】
① 根据上述公交线路的输入格式，定义并建立合适的图模型。
② 针对上述公交线路，能查询获得任何两个站点之间最便宜的路径，即输入站名S，T后，可以输出从S到T的最便宜的路径，输出格式为：线路x ：站名S，?，
