数据结构课程设计

数据结构课程设计总体要求：明确每道题的逻辑和物理存储结构。总体设计要画流程图。提供程序测试方案。界面友好。提供实习报告，团队分工项目需详细说明个人的实现的功能。实习报告模板，注意仅粘贴关键代码和注释，不需要把所有代码都贴到实习报告里。题目一（个人完成，共30分）:带环链表问题设计目的：掌握链表的基本操作。掌握带环链表的相关操作算法。设计内容：基于课程上机关于单链表的作业，要求进一步实现以下需求:1.构造链表后，将元素值为m和n（从键盘输入，如有多个相同元素值，仅考虑首个出现的元素）的节点建立连接，注意判断节点出现的先后关系，将后面出现的节点（假设为n）的链域连到先出现的节点（假设为m），同时需销毁原n节点的后续节点，避免内存泄露；2.利用课程ppt中关于判断链表是否有环的方法，判断链表是否有环路，并需给出环路出现的位置，即m，n节点的序号，请使用环路判断函数，不可直接查找m,n；3.将环路链接取消，恢复单链表。题目二（个人完成，共40分）:交通咨询系统设计设计目的：熟练掌握迪杰斯特拉算法和费洛伊德算法,能够利用它们解决最短路径问题。掌握图的深度，广度遍历算法。掌握快速排序算法。设计内容：设计一个交通咨询系统，通过读取全国城市距离图（参考，请转为文本文件并在程序运行时动态加载到内存），能够让用户查询从任一个城市定点到另一个城市定点之间的最短路径（两种算法均要实现，界面上可自行切换）以及所有不重复的可行路径，并利用快速排序对所有路径方案依据总长度进行排序输出，每一条结果均需包含路径信息及总长度。题目三（团队完成，自行组队，每队不超过4人，需有队长及队员的明确分工，实习报告中需明确注明团队组成及队员的分工，共30分）:简单搜索引擎系统设计目的：掌握倒排索引相关算法。掌握字符串的相关处理方法。掌握文件的操作。学习使用开源代码库。学习团队分工合作。设计内容：给定n个文本文件（检查时我会提供测试数据，编程时请自行收集，需实现导入某一个文件夹下所有文本文件的功能。同时也鼓励大家直接从网页上抓取数据，例如从搜狐网抓取新闻并去掉html标签即为文本文件，该功能即为网页爬虫，可利用任何开源代码，请自行网上查找，不要求看懂内部实现，会用即可，如实现该功能有加分），具体需求如下:1.依次读取n个文本文件并利用分词函数建立倒排索引（详查看字符串章节ppt，请利用开源代码或者，亦可自行网上查找其他解决方案，不需要自行实现和看懂内部实现，只需要会用），注意：请自行实现，不能直接简单使用VC中HashTable类或者Vector类等；2.自行设计查找算法，支持从倒排索引中检索给定的字符串，请提供用户输入查找字符串的页面，相当于百度首页的输入框；3.自行设计排序算法，即需要考虑当查询字符串出现在多个文档中时，哪个文档在输出后的结果中排第一or第二or...，可参考pagerank算法，也可自行设计任何可用、有一定意义的算法，简单/复杂均可。4.自行设计搜索结果展示界面，要求能将关键字出现的位置附近的上下文显示出来，请参考百度的搜索结果展示页面，注意，不能在检索后对所有检索结果用字符串模式匹配函数进行关键字查找！测试数据：