【南邮】算法与数据结构设计授课计划[2025-06-02]

【南邮】算法与数据结构设计授课计划[2025-06-02]

算法与数据结构设计授课计划

开发工具：Turbo C / Visual C++ / C# 等等，用C、C++或Java等（自选）程序设计语言中的一种编写完整的程序。
具体要求：用上述系统平台和开发工具完成所分配题目的程序，并撰写报告。
一、 关于题目的分配
原则上针对学号后2位除6余1的做每组的第一道题目，依次类推，余2的做第二道题目，……，余0的做第6道题目。

1.家谱管理系统
（一）课题内容
家谱管理系统是查询家谱信息必不可少的一部分，利用家谱管理系统可以清楚的了解家族成员信息。该家谱管理系统是通过树来实现的。要求系统界面友好，易于操作。
（二）课题要求
（1）需要设置普通用户、超级管理员不同角色，不同角色登录后的权限各不相同，普通用户可以进行查询；超级管理员有对所有成员增加、删除和修改的权限。
（2）家谱中成员的信息中均应包含姓名、出生日期、婚否、地址、健在否、死亡日期（若其已死亡）等 ，也可附加其它信息，并存储于文本文件中。
（3）查询功能。可按照姓名查询，输出成员信息（包括其本人、父亲、孩子的信息、所在辈分）；按照出生日期查询成员名单。
（4）按出生日期对家谱中所有人排序。
（5）打开家谱时，提示当天生日的健在成员。
（6）输入任意两个姓名，能够查询这两个姓名之间的是否具有直系祖先后裔关系。
提高要求：界面美观，交互方便， 以图形方式显示家谱。

2.最短路径算法
（一）课题内容
课题内容
该最短路径算法主要以南京地铁线为模板，实现任意两个站点之间站数最短路径（例如软件大道站——仙林中心站）的查询、最短路径的换乘方案以及最短路径的费用计算。请使用C/C++或Java实现。下图为南京地铁线路图。

课题要求：
(1) 编程实现，数据结构选用邻接矩阵或邻接表来实现；
(2) 实物演示时要求讲出程序原理；
(3) 程序操作友好、界面清晰；
(4) 至少包含1号线、
提高要求：包含1号南延线、2号线和机场线。

3.旅行飞行路线规划系统

课题内容和要求
用户选择在一个月内从其所在城市出发乘坐飞机进行N天旅游，其路费预算为K，计划访问城市集合为S（|S|>1）。要求系统能够返回一个满足路费预算的飞行计划。
例如南京用户想在11月休年假10天，想去青岛、成都和北京游玩，路费预算为5000，是否存在满足该预算和旅行路线的飞行计划。
请使用C/C++或Java实现。
基本要求：
(1) 可以参考网上的飞机票价格、飞行时间等信息；用户可选择旅行的城市至少包含：厦门、北京、青岛、成都、丽江；用户所在城市默认为南京；
(2) 不允许用户输入很少的天数，却要求旅行很多城市（例如3天假期却要旅行3个城市）；对每个城市的停留时间要有合理的最小值（例如最少呆24小时）；
(3) 计算结果应该包含：建议的出发日期和返程日期、访问所选择城市的顺序、飞机起飞与降落时间、机票价格；当有多个可行的飞行计划时，按照费用从小到大的顺序排列显示前几个；当不存在满足预算的规划，则向用户显示其所能计算出的费用最低的规划；
(4) 实物演示时需讲出程序原理和算法分析；
(5) 用户输入信息操作友好、健壮、简洁；规划结果显示界面排版整齐美观。
提高要求：
(1)为用户生成满足预算的最舒适飞行计划：飞机飞行时间介于8:00-20:00、每个城市停留48小时以上、飞行费用在预算内。
(2) 智能规划旅行路线：当用户只输入旅行天数N（N>3）与路费预算K，而不选择访问城市时，由系统为其选择旅行城市和飞行线路，要求每个城市停留时间不低于48小时、飞行计划舒适、满足路费预算且访问的城市越多越好；
(3)高效先进的算法。

4.两篇文章的相似性
课题内容和要求
对于两篇文章，用哈希表的方法分别统计两个文章语言关键字的情况，并最终按定量的计算结果，得出两份文本的相似性。
基本要求：建立关键字的哈希表，统计在每个文本中关键字出现的频度, 得到两个向量X1 和X2，通过计算向量X1 和X2 的相对距离来判断两篇文章的相似性。
每个词都可以表示为一个唯一的token，以token来向量化，例如下面两个文档，每个词用一个id表示，其值用其频度表示。
例如:
Text， mining ，is， a， powerful ，technology， for ，quickly， distilling ，information
文章1 关键字频度4 3 0 4 3 0 7 0 0 2
文章2 关键字频度4 2 0 5 4 0 5 2 0 1
X1=[4,3,0,4,3,0,7,0,0,2]
X2=[4,2,0,5,4,0,5,2,0,1]
设s 是向量X1 和X2 的相对距离，s=sqrt(Σ(xi1-xi2)2)，当X1=X2 时，s=0, 反映出可能是表达同一意思的文章；s 值越大，则两篇文章的差别可能也越大。
测试数据: 选择若干组文章，文章之间有相近的和差别大的，用上述方法求s, 对比两篇文章的相似性。
提高要求：采用余弦相似性来判断两个文章的相似性。

5.管道铺设施工的最佳方案
课题内容与要求
问题描述:需要在某个城市的n 个小区铺设管道，则在这n 个小区之间铺设n-1 条管道即可，假设任意两个居民区之间都可以架设管道，但由于地理环境的不同，所需经费不同，选择最优的施工方案使总投资尽可能的少。
要求：输入表示小区间关系的图及每条管道的权值，选择出n-1 条管道, 使总投资最小。图的信息输入一次后, 保存到文件中, 选择的n-1 条管道输出到显示器的同时, 也保存于文件中。
测试用例：任意选择一个图，模拟小区间可能铺设的管道及费用。
提高要求：显示原始图及选择n-1 条管道后的图。

6.哈希表的设计与实现
课题内容与要求
问题描述：针对某公司中花名册设计哈希表，并完成相应的建表和查表程序。
课题要求：
（1）假设花名册为汉字拼音形式。名称的长度不少于4个字符、不多于10个字符；
（2）随机生成花名列表，个数不少于4000个，保存到文本文件中，构建哈希表时读入；
（3）至少实现三个不同的哈希函数（采用不同的方法）和对应的冲突处理函数；
（4）计算比较不同的方法的平均查找长度。
提高要求：把信息以文件形式保存下来，能够实现插入、查找、删除表中元素的功能。

源码联系UP主 -> https://space.bilibili.com/329101171