在家庭作业问题之外,您将为此使用关系数据库。但这可能对您没有帮助……</p>
正如其他人已经指出的那样,您需要弄清楚的第一件事是您正在处理多少数据。只要n很小,O( n ) 蛮力搜索就足够快。由于微不足道的数据量会使这成为微不足道的问题(将其放入数组中,然后进行暴力搜索),因此我将假设数据量很大。
储存城市
首先,您的搜索要求似乎需要以多种方式对数据进行排序:
- 一些城市唯一标识符(名称?)
- 参观人数
这其实并不难满足。(1) 最简单。将城市存储在某个数组中。数组索引成为唯一标识符(假设:我们没有删除城市,或者如果我们确实删除了城市,我们可以让该数组点不使用,浪费一些内存。添加是可以的)。
现在,我们还需要能够找到最多和最少的访问。假设可能会发生修改(例如,添加城市、更改访客数量等)并从关系数据库中借用,我建议使用某种形式的平衡树创建索引。数据库通常使用 B-Tree,但不同的可能对您有用:检查维基百科关于树木的文章。在每个树节点中,我只保留城市数据的指针(或数组索引)。没有理由再复制一份!
我推荐一个哈希树,原因很简单:你可以很容易地进行前序或逆序遍历来找到顶部或底部的 N 个项目。哈希不能做到这一点。
当然,如果修改可能不会发生,只需使用另一个数组(指向项目的指针,再一次,不要复制它们)。
将城市链接到个人资料
如何做到这一点取决于您必须如何查询数据,以及它可以采用什么形式。最通用的是每个profile可以关联多个城市,每个城市可以关联多个profile。此外,我们希望能够从任一方向高效查询——同时询问“谁访问了凤凰城?” 和“鲍勃访问了哪些城市?”。
再次无耻地从数据库中提取,我将创建另一个数据结构,一个相当简单的数据结构:
struct profile_city {
/* btree pointers here */
size_t profile_idx; /* or use a pointer */
size_t city_idx; /* for both indices */
};
因此,如果说 Bob(个人资料 4)访问过凤凰城(城市 2),您将拥有
profile_idx = 4
和city_idx = 2
。假设 Bob 也访问了拉斯维加斯(城市 1),您需要添加另一个,因此您将拥有其中两个给 Bob。
现在,您有一个选择:您可以将它们存储在树或散列中。就个人而言,我会选择树,因为该代码已经编写好了。但是对于查找,哈希将是 O( n ) 而不是 O(log n )。
此外,就像我们对城市访问计数所做的那样,创建一个索引,
city_idx
以便也可以从那一侧进行查找。
结论
您现在可以查找访问次数最多的 5 个城市(通过按顺序遍历城市访问计数索引),并找出谁访问了这些城市,方法是搜索city_idx
索引中的每个城市以获取
profile_idx
. 只拿独特的物品,你就有答案了。
哦,这里似乎有问题:对于您的讲师来说,这似乎是一个非常多的代码,需要在几个小时内完成!