数据结构课程设计题目.doc

数据结构课程设计注意事项1：选题要求：在同一班中不能重题。选题后未经指导老师同意则不得改题。2：文档格式要求：按照课程设计的最新格式要求，其中内容格式按照数据结构题集P75的要求。3：文档内容要求：内容充实，叙述清楚合理，排版美观规范，中文文字不能少于1000，程序代码必须有详细的中文注释。4：答辩要求：答辩时，可以用电子文档来答辩，但是必须在指定时间上交纸质的文档。答辩时间地点另行通知。要求:程序能正确运行，功能实现完整，能理解代码，清楚问题解决过程的重要算法和思路。成绩将根据答辩情况和文档情况确定。5：递交的材料的要求：答辩完毕，经修改后，最后每位同学须提交的材料：1：正式的课程设计文档纸质档1份。2：正式的课程设计文档的电子档1份。3：源代码的电子档1份。源代码中只需要所有的*.h、*.cpp、*.dsw、*.dsp文件，其他所有的文件或文件夹都不需要。要求：每个同学在建立一个文件夹，名字为：“学号”+ “姓名”，以上电子档材料存放该文件夹，班级汇总后由各班的学习委员统一收齐于19周星期五之前交到信息工程办公室（6教205）。6：成绩评定1、根据程序设计的情况、课程设计文档的质量和等综合打分。成绩评定实行优秀、良好、中等、及格和不及格五个等级。2、独立按时完成规定的工作任务，不得弄虚作假，不准抄袭他人内容，发现雷同，一律不及格。7：其他：课程设计依靠自己完成，有问题可与我联系123706809希望同学们按时来答辩，往后拖延答辩和文档递交的同学其成绩递减。不按时提交文档影响课程设计的成绩录入者，将取消课程设计成绩。题目：1. 稀疏矩阵的应用（难度*）要求：1实现三元组下的稀疏矩阵的加法和乘法。2 用十字链表实现稀疏矩阵的加法和乘法。以下是例子。2. 二叉树的遍历（难度*）要求：1）二叉树的2叉链的存储方式的实现。2）二叉树的中序、前序、后序的递归遍历算法的实现。3）二叉树的中序、前序、后序的递归遍历算法的实现。3. 银行业务模拟（难度*）见课本P65。4. 最小生成树的Prime算法实现（难度*）要求：1) 先任意创建一个图；2) 用Prime算法，求出该图的最小生成树5. 最小生成树的Kruskal算法实现（难度*）要求：1) 先任意创建一个图；2) 利用Kruskal算法，求出该图的最小生成树6. 线索二叉树的应用（难度*）要求：1：建立前序线索树，并且实现在此树上利用线索前序遍历该树2：建立中序线索树，并且实现在此树上利用线索中序遍历该树3：建立后序线索树，并且实现在此树上利用线索后序遍历该树7. 哈夫曼编码/译码器（难度*）【问题描述】设计一个利用哈夫曼算法的编码系统，重复地显示并处理以下项目，直到选择退出为止。【基本要求】1) 将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) 2) 初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；3) 编码：利用建好的哈夫曼树生成哈夫曼编码；4) 输出（1）各个字符的编码；（2）8. 链式串的实现（难度*）要求：使用链表作为字符串的存储结构，实现字符串的新建，插入，删除，KMP算法，复制，2个字串的拼接，字符串的比较，求字符串的长度等操作。9. 树的应用（难度*）要求：实现任意形状的树（使用广义表的方式从键盘输入）与二叉树的相互转换的实现。转换成为二叉树后，请输入该二叉树的前序、中序、后序遍历的序列。10. 多项式运算的实现。（难度*）11. 利用栈求表达式的值。（难度*）要求：（1）判断表达式是否正确，主要是括号问题（2）题目涉及加减乘除，带括弧的混合运算 （3）参与运算的数字可以是多位数。12. 数制转换问题（难度*）设计一个程序可以将十进制、二进制、八进制、十六进制数之间相互转换。13. 排序综合（难度*） 利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。要求：1) 至少采用5种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序，基数排序）。并把排序后的结果保存在不同的文件中。2) 利用系统提供的时间函数，统计每一种排序方法的运行性能（以若干此运行程序所花费的平均时间为准进行对比），找出其中两种较快的方法。14. 校园导航问题（难度*）设计要求：根据学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，各条路径的长度大概估计。要求：1：实现Dijistra算法，求出指定起点到终点的最短路径长度和具体的路径。2实现Floyd算法，求出任意2点之间的最短路径长度和具体路径15. 字典设计（难度*）编写一个基数排序算法，将一组英文单词按字典序排序，设最长的单词有n个字母。并且可查找到指定单词。16. 哈希表设计（难度*）针对本年级的2个班中的实际姓名，设计一个哈希表，使得平均查找长度较短。完成建表和查表，人名的添加和删除等操作。17. 图的搜索（难度*）要求：1：用邻接表存储图2：用邻接矩阵保存图3：分别在这两种存储结构上实现图的深度优先搜索和广度优先搜索。18. 关键路径求解（难度*）问题描述AOE网(即边表示活动的网络)，在某些工程估算方面非常有用。它可以使人们了解：（1）研究某个工程至少需要多少时间？（2）哪些活动是影响工程进度的关键? 在AOE网络中，从源点到汇点的有向路径可能不止一条，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和，这条路径就叫做关键路径（critical path）。设计步骤1 以某一工程为蓝本，采用图的结构表示实际的工程计划时间。2 调查并分析和预测这个工程计划每个阶段的时间。 3 用调查的结果建立AOE网，并用图的形式表示。 4 用CreateGraphic ()函数建立图的邻接表存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中。5 用SearchMaxPath()函数求出最大路径，并打印出关键路径。 6 编写代码并调试、测试通过。测试数据利用教材p185的图7.30（a）中的数据调试程序。实现提示实现的关键和难点在于对四个术语的理解和应用即：ei表示顶点vi所代表的事件的最早发生时间；li表示顶点vi所代表的事件的最迟发生时间；Tes(i,j)表示活动ak的最早开工时间；Tls(i,j)表示活动ak的最迟开工时间。活动ak为关键活动的充分必要条件是活动ak的最早开工时间与它的最迟开工时间相等。19. 拓扑排序（难度*）问题描述 建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中，再编写函数实现图的拓扑排序。基本要求 选择邻接表作为有向图的存储结构模拟整个过程，并输出拓扑排序的顶点序列。测试数据 利用下图中的数据调试程序实现提示 参考教材p163图的邻接表存储表示定义及p182拓扑排序的算法描述。20. 运动会分数统计（难度*）任务：参加运动会有10个学校，学校编号为110。比赛分成18个男子项目，和12个女子项目。项目编号为男子118，女子1930。不同的项目取前三名积分，前三名的积分分别为：5、3、2。功能要求：1) 可以输入各个项目的前三名的成绩；2) 能统计各学校总分；3) 可以按学校编号或名称、学校总分、男女团体总分排序输出；4) 数据存入文件并能随时查询 5) 规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称输出形式：有中文提示，各学校分数为整型存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在C语言程序设计的书上，请自学解决）；测试数据：测试数据及测试结果请在上交的资料中写明；21. 飞机订票系统（难度*）任务：通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能； 22. 文章编辑（难度*）功能：从键盘输入一页文字，静态存储在一个文件中要求：（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；23. 纸牌游戏（难度*）任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；.再依次5的倍数的牌翻一次，6的，7的 直到以52为基数的翻过，输出：这时正面向上的牌有哪些？ 24. 宿舍管理查询软件（难度*）任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：（1）建立数据文件 ，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种)（2）实现如下查询功能: 按姓名查询 按学号查询 按房号查询（3）打印任意查询结果（可以连续操作）25. 学生成绩管理（难度*） 实现功能：输入、输出、插入、删除、查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出。26. 活期储蓄帐目管理（难度*） 活期储蓄处理中，储户开户、销户、存入、支出活动频繁，系统设计要求：1) 能比较迅速地找到储户的帐户，以实现存款、取款记账；2) 能比较简单，迅速地实现插入和删除，以实现开户和销户的需要。27. 手机通讯录的制作（难度*）设计目的：用数据结构中的双向链表作数据结构。编写一个手机通讯录管理系统。以把所学数据结构知识应用到实际软件开发中去。设计内容：本系统应完成一下几方面的功能：1) 添加信息;2) 显示信息：它可以按按固定电话排列、按手机、联系人名字的拼音顺序排列。3) 查找：可以不同的关键字作为查找的依据，进行查找;4) 编辑信息5) 删除信息6) 保存到文件：将以上信息保存到文件，以便下次运行程序时能载入此通信录设计要求：1) 每条信息至包含 ：姓名（NAME ）,手机号，固定电话号，电子邮箱，QQ号码，城市（CITY）邮编（EIP）几项2) 作为一个完整的系统，应具有友好的界面和较强的容错能力3) 上机能正常运行，并写出课程设计报告28. 图书管理系统（难度*）【问题描述】设计一个计算机管理系统完成图书管理基本业务。【基本要求】1) 每种书的登记内容包括书号、书名、著作者、现存量和库存量；2) 对书号建立索引表（线性表）以提高查找效率；3) 系统主要功能如下：*采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；*借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；*归还：注销对借阅者的登记，改变该书的现存量。29. 走迷宫（难度*）程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。要求：1) 老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；2) 迷宫的墙足够结实，老鼠不能穿墙而过；3) 正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，否则提示失败；4) 找出走出迷宫的所有路径，以及最短路径。30. 敢死队问题（难度*） 有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。 排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。 31. 猴子吃桃子问题（难度*） 有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。 要求：1) 采用数组数据结构实现上述求解2) 采用链数据结构实现上述求解3) 采用递归实现上述求解32. HTML文档标记匹配算法（难度*）要求：输入一段HTML代码，判断该代码是否符合HTML的语法提示：HTML文档由不同的标记划分为不同的部分与层次。与括号类似，这些标记需要成对出现，对于名为的起始标记，相应的结束标记为。常用的HTML标记：l :HTML文档l :文档标题l :文档体l :节的头部l :居中对齐l :左对齐l :段落l 。HTML语言有合理的嵌套，如 33. 分配策略（难度*）有n个人去分m个蛋糕，每个蛋糕的底面积不等。（假设蛋糕的高度是相同的）要求，1：一个人只能从某块蛋糕中分到其中的一块，不能从2个以上的不同蛋糕中分得蛋糕。2：要求每个人分到的蛋糕块体积相同，同时，每个分到的蛋糕的体积是最大的。对于给定的n，m以及m各蛋糕的底面积，求分配的方案，以及每人能分到多大面积的蛋糕。例如：假定有6个人分3块蛋糕，每块底面积的大小分别为：3，9，7。那么最终的分配方案为：1人分半径为3蛋糕，2人分半径为7的蛋糕，3人分半径为9的蛋糕，每人能分到面积为3的蛋糕。34. 语言中平衡符号的问题（难度*）要求：设C语言程序代码中包含如下符号/* */，（），编写程序检测一段C代码中上述符号是否正确。35. 烫手山芋问题（难度*）（约瑟夫环问题）一群小孩编号为1，2，n(n0)围成一圈，有一个刚出锅的山芋在他们之间传递。假设刚开始由1号拿着山芋，然后依次计数把山芋交给下一个小孩，当数到某个特定的k时，拿着山芋的小孩退出游戏，然后从下一个小孩重新开始计数，如此不断，最后剩下的那个孩子就是幸运者。要求设计一个程序模拟次过程，并给出不同的n，k组合下那个幸运者是谁？36. 车厢调度（难度*）一列货运列车共有n节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1 n，货运列车按照第n站至第1站的次序经过这些车站。车厢的编号与它们的目的地相同。为了便于从列车上卸掉相应的车厢，必须重新排列车厢，使各车厢从前至后按编号1到n的次序排列。当所有的车厢都按照这种次序排列时，在每个车站只需卸掉最后一节车厢即可。我们在一个转轨站里完成车厢的重排工作，在转轨站中有一个入轨、一个出轨和k个缓冲铁轨（位于入轨和出轨之间），每个缓冲铁轨的容量小于总车厢个数的1/k。图5-5a 给出了一个转轨站，其中有k= 3个缓冲铁轨H1，H2和H3，每个缓冲铁轨的容量为2个车厢。开始时，n节车厢的货车从入轨处进入转轨站，转轨结束时各车厢从右到左按照编号1至编号n的次序离开转轨站（通过出轨处）。在图5-5a 中，n= 9，车厢从后至前的初始次序为5，8，1，7，4，2，9，6，3。如下图所示，给出了按所要求的次序重新排列后的结果。具有三个缓冲铁轨的转轨站 a) 开始 b) 结束要求：对于给定的初始状态与终止状态，判断是否能在指定缓冲铁轨的容量条件下调度成功，如果能，请输出调度的过程。37. 入学考试问题（难度*）某地大学入学考试，相关信息如下：(1)参加人数：10万。(2)共有8门考试课程，每门课程满分均为100分，所有课程成绩均进行了4舍5入的处理，考生的总分也照此处理。(3)所有考生的考试成绩保存在文件scores.txt中，文件格式如下：每个考生成绩一行，每行格式如下：最开始为考生姓名，然后为每门课程的分数，考生姓名与课程分数之间，以及不同课程分数之间均用一个英文逗号隔开，如：张三,98,92,60,54,87,75,86,92个别考生成绩行的格式可能会有误。(4)共招收三个批次的学生，第一批次30000人，第二批次60000人，第三批次10000人。录取顺序为：第一批次，第二批次，第三批次。程序要求：(1)确定每一批次的录取分数线，并将批次、分数线、实际录取人数输出到文本文件soutput.txt中，每一批次录取信息占一行，格式自定。确定分数线时，如果在分数线处有多名考生，则将这些考生全部录取，即每一批次的实际录取人数可能会超过预定人数。例如：假定在确定第一批次分数线时，有7800人的总分高于等于750分，有8050人的总分高于等于749分，则第一批次分数线应确定为749分，实际录取人数为8050人。(2)如果考生成绩行的格式不对，则丢弃该考生的成绩，不作为确定分数线的依据，但要求将该考生姓名输出到文本文件serror.txt中，格式自定。(3)将总分为650分的考生姓名输出到文本文件soutput.txt中，格式自定。(4)将第三批次录取的所有考生的平均成绩（4舍5入）输出到文本文件soutput.txt中，格式自定。(5)要求将下面两个时间值（单位为秒）输出到文件soutput.txt的最后：从打开scores.txt文件到读完所有考生成绩的时间；从打开scores.txt文件到程序结束的时间。38. 词汇统计（难度*）文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”英文小说存在于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数。39. 括号嵌套问题（难度*）某个序列完全由圆括号组成，一个“（”和一个“）”称为一对括号，且序列中的括号成对出现。设n为序列中出现的括号对数，k为序列中括号的最大嵌套深度；那么，序列“()()()()()”的n为8，k为3。1、请编程判断任意给定的圆括号序列，是否是一个深度为k的序列。 要求：（1）先输入嵌套深度k，然后输入任意一个序列，最后给出判定结果（是，不是，或者输入序列中的括号不配对） （2）可以反复输入数据，当k为0时，程序结束。while(k!=0)输入示例：3()()()()()2()()()()()5()()()()()输出的判定结果：测试1：YES测试2：NO测试3：括号不配对2、编程输出括号对数为n，嵌套深度为k的所有序列。(1=k=nn时，程序结束。输出结果示例（n=5，k=3）：1: ()()()2: ()()()3: ()()()4: ()()5: ()()()6: ()()()7: ()()8: ()()()9: ()()()10: ()()()11: ()()()12: ()()()13: ()()14: ()()()15: ()()()16: ()()()17: ()()()18: ()()()5对括号，3层嵌套问题,共求出18种情况3、求解括号对数为n，嵌套深度为k的序列的总数（不输出具体序列）。(1=k=n=30)输入示例：321532011输出结果：32：3种153：497845种2011：94817125种40. 树重建 (Rebuild) （难度*） 给出一棵标号树的BFS序列和DFS序列，设计一个算法重新建立这棵树（结点数n1000）。当某结点被扩展时，它的所有孩子应该按照编号从小到大的顺序访问。例如一棵树的BFS序列为43512876，DFS序列为43172658，则一棵满足条件的树如右图所示。输入格式第一行输入结点数n。第二行n个用空格隔开的整数，描述这棵树的BFS序列；第三行n个用空格隔开的整数，描述这棵树的DFS序列。输出格式一共输出n-1行，每行两个整数i,j描述一条边，表示第i个结点与第j个结点之间连一条边。样例输入84 3 5 1 2 8 7 64 3 1 7 2 6 5 8样例输出4 55 84 33 22 63 11 7提示：我们曾经遇到过相似的题目，给出一棵二叉树的先序，中序，后续遍历中的其中两种，要你还原这棵二叉树。而这题改为了给出DFS和BFS序列，虽然形式上变了，但是原理还是相似的，我们只需抓住树的性质和充分利用这两个序列的特性就能把这种题目解决。 拿题目数据做例子。首先，无论是BFS（广度优先搜索）序列还是DFS（深度优先搜索）序列，第一个点都必定是根结点。接着我们看BFS序列，跟在根结点4后面的连续若干个结点就是4的儿子结点，但是究竟有多少个是4的儿子呢？首先，题目中的一个条件说：“某结点被扩展时，它的所有孩子应该按照编号从小到大的顺序访问”，因此4的儿子应该是按由小到大出现在BFS序列中的。后面31，所以1就肯定不是4的儿子。然而即使后面若干个数满足升序的条件，也不一定全都是4的儿子，这时我们就要借助DFS序列了。因为DFS的规律是遍历完一棵子树才到另一棵，所以4的儿子在DFS序列中也是按由小到大出现，只是它们之间可能被若干个结点隔开罢了。根据这两个条件，我们就能判断哪些是4的儿子了。例如在BFS序列中紧挨着4出现的3,5，在DFS序列中也是按照由小到大的顺序先出现3，再出现5，因此3,5都是4的儿子。 接下来怎么做呢？由于4的儿子都确定了，剩下的就是把4的每一棵子树都确定下来，而这就是一个子问题了。若我们确定了根结点有k个儿子，若第i个儿子在DFS中的位置为P1，第i+1个儿子在DFS中的位置为P2，则在DFS序列中位置P1与P2之间的所有结点就是以第i个儿子为根的子树的结点。而我们可以建立一个队列，每确定一个结点就把它加到队列里面去，模拟BFS的过程。在模拟广搜的过程中，若当前要处理的结点为k，由于以k为根的整棵子树在DFS序列中是连续的一段，而究竟是那一段在前面的广搜过程中是可以顺带求出的。然后我们利用BFS序列和DFS序列中连续的一段确定出k的所有儿子，并加到广搜队列里面。直到广搜结束，问题就解决了。41. 背包问题的求解（难度*）假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , , wn 的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + + wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积1，8，4，3，5，2时，可找到下列4组解：（1，4，3，2）（1，4，5）（8，2）（3，5，2）。提示：可利用回溯法的设计思想来解决背包问题。首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品太大不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明刚刚装入背包的那件物品不合适，应将它取出弃之一边，继续再从它之后的物品中选取，如此重复，直至求得满足条件的解，或者无解。由于回溯求解的规则规则是后进先出因此自然要用到栈。42. 全国交通咨询模拟（难度*）【问题描述】处于对不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则希望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。【基本要求】（1）提供对城市信息进行编辑（如：添加或删除）的功能。 （2）城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑（增设或删除）的功能。 （3）提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。 （4）旅途中耗费的总时间应该包括中转站的等候时间。 （5）咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具，输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。【测试数据】【实现提示】（1）对全国城市交通图和班车时刻表及飞机航班表的编辑，应该提供文件形式输入和键盘输入两种方式。飞机航班表的信息应包括：起始站的出发时间、终点站的到达时间和票价；列车时刻表则需根据交通图给出各个路段的详细信息，例如：对于从北京到上海的火车，需给出北京至天津、天津至徐州及徐州至各段的出发时间、到达时间和票价信息。 （2）以邻接表作交通图的存储结构，表示边的结点内除含有邻接点的信息外，包括交通工具、路程中消耗的时间和花费以及出发和到达的时间等多项属性。43. LZW压缩器/解压器（难度*）【问题描述】为了节省存储空间，常常需要把文本文件采用压缩编码的方式储存。例如：一个包含1000个x的字符串和2000个y的字符串的文本文件在不压缩时占用的空间为3002字节（每个x或每个y占用一个字节，两个字节用来表示串的结尾）。同样是这个文件，采用游程长度编码（run-length coding），可以存储为字符串1000x2000y，仅为10个字母，占用12个字节。若采用二进制表示游程长度（1000和2000）可以进一步节约空间。如果每个游程长度占用2个字节，则可以表示的最大游程长度为2*pow(16)，这样，上例中的字符串只需要用8个字节来存储。当要读取编码文件时，需要对其进行解码。由压缩器（compressor）对文件进行编码，由解压器（decompressor）进行解码。（1）长度-游程编码的压缩/解压；+（2）LZW压缩/解压（散列）；（1）长度-游程编码的压缩/解压；+（3）霍夫曼编码压缩/解压 (霍夫曼树) 【基本要求】要求选用二种压缩/解压策略实现压缩/解压器（1）为必选。输入的为本文文件（.txt），输出的为一种自定义的文件（.nz）。考虑当构成文本的字符集合为a,b,c,z,0,1,2,9时，请用实例测试你的压缩/解压器。你的压缩器会不会出现抖动？（压缩后的文本比原来的还要大）。扩充构成文本的字符集合以便使它适应更一般的情况。【实现提示】LZW：由Lempel、Ziv和Welch这三位科学家所开发的技术。该方法把文本的字符串映射为编码，首先，为该文本中所有可能出现的字母分别分配一个代码。例如：要压缩的对象是aaabbbbbbbaabaaba，由a和b组成。为a分配代码0,为b分配代码1。字符串和编码的关系被存储在字典中。字典如下：Key 01234567CodeAbAaaabbbbbbbbbaaaba LZW压缩器不断的在输入文件中寻找在字典中出现的最长的前缀p,并输出其相应的代码。若输入文件的下一个字符为c，则为pc分配下一个代码，并插入字典，这种策略称为LZW规则。相反，在解压时，编码表由压缩文件重新构造，LZW原则使这种重建成为可能。 如上例子，压缩时，文件中第一个在字典中出现的最长前缀是a, 输出其编码0,然后为字符串aa分配代码2，并插入到字典中。余下的字符串在字典中出现的最长前缀是aa,输出aa的对应代码2，同时为字符串aab分配代码3并将其插入到字典中。依次类推，由此，输出0214537 解压时，要输入代码，然后用代码所表示的文本来替换这些代码。代码到文本的映射可按下面的方法重建：首先把分配给单一字母的代码插入到字典中。象前面一样，字典的入口为key-code对。然而此时是根据给定的代码（key）去寻找相应的入口（而不是根据文本Code）。压缩文件中的第一个代码对应于单一的字母，因此可以由该字母代替。对于压缩文件中的其他代码p,要考虑两种情况：1）在字典中；2）不在字典中。在1）情况下，找到p对应的文本text(p)输出。并且，根据压缩原理可知，若在压缩文件中代码q写在p之前且text(q)是与q对应的文本，则压缩器会为文本text(q)（其后紧跟fc(p)，text(p)的第一个字符）分配一新代码。因此在字典中插入序偶（下一个代码，text(q)fc(p)）。 情况2）时，只有在当前文本段形如text(q)text(q)fc(q)且text(p)=text(q)fc(q)时才会发生。相应的压缩文件段是qp。在压缩过程中，为text(q)fc(q)分配的代码为p。在解压过程中，在用text(q)代替q后，又遇到代码p。然而，此时字典中没有与p对应的文本。因为这种情况只在解压文本段为text(p)text(q)fc(q)时才发生，因此可以对p解码。当遇到一个没有定义代码文本对的代码p时，p对应的文本为text(q)