1

我有点需要决定这个，看看我是否能在我的学校项目截止日期前的几个小时内实现它，但我对数据结构不太了解，我需要建议......

我需要做两件事，他们可能会使用不同的数据结构。

  1. 我需要一个数据结构来保存个人资料记录。个人资料必须可以按姓名和社会安全号码进行搜索。SSN 是独一无二的，所以我可能可以利用它来获得优势？我想哈希图是最好的选择吗？但是如何在哈希映射中使用 SSN 来利用它作为查找特定配置文件的优势？一个基本且易于理解的解释将不胜感激。

  2. 我需要一个数据结构来保存有关城市的记录。我需要知道访问者最多的城市、访问量较少的城市以及访问特定城市的客户（从#1 中的数据结构中提取有关客户数据的配置文件）。

这是我的项目需要的第三个数据结构，它是我不知道从哪里开始的数据结构。如果可能，请提供有关使用哪种类型的数据结构的建议，并以粗体显示如何旧数据的示例。

注意：第一个数据结构已经完成（我在上一个问题
中谈到过）。第二个发布在 #1 上，尽管其他小组成员正在处理这个问题，但我只需要知道我们正在尝试做的是否是“最佳”方法。第三个是#2，我最需要帮助的那个。

4

3 回答 3

3

正确答案位于平衡搜索树和数组之间。

您在这里提到的情况和 else-thread 错过了一个非常重要的点：您正在处理的数据的大小。您可以根据必须处理的数据量来选择数据结构和算法。重要的是您能够证明您的选择是正确的。使用效率较低的通用算法并不总是坏事。能够支持您的选择（例如：选择冒泡排序，因为数据大小始终<10）表明a）对该领域的更大控制和b）实用主义-两者都供不应求。

于 2009-03-22T04:36:47.877 回答
1

在家庭作业问题之外，您将为此使用关系数据库。但这可能对您没有帮助……</p>

正如其他人已经指出的那样，您需要弄清楚的第一件事是您正在处理多少数据。只要n很小，O( n ) 蛮力搜索就足够快。由于微不足道的数据量会使这成为微不足道的问题（将其放入数组中，然后进行暴力搜索），因此我将假设数据量很大。

储存城市

首先，您的搜索要求似乎需要以多种方式对数据进行排序：

  1. 一些城市唯一标识符（名称？）
  2. 参观人数

这其实并不难满足。(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. 只拿独特的物品，你就有答案了。

哦，这里似乎有问题：对于您的讲师来说，这似乎是一个非常多的代码，需要在几个小时内完成！

于 2009-03-22T08:44:27.657 回答
1

为了跨多个键的可搜索性，以任何方便的形式存储数据，并在键上提供快速查找索引。

(key, data*)这可以像将数据按创建顺序保存在数组（或链表，或...）中一样简单，并为所有有趣的键（SSN ）保存一堆 {hashtables|sorted arrays|btrees} ， 姓名， ...）。

如果你有更多的时间，你甚至可以弄清楚如何为每张不同的地图设置不同struct的......

我认为这个解决方案可能适用于您的两个问题。

祝你好运。

为了清楚起见：

首先，我们有一个简单的学生记录数组

typedef
struct student_s {
   char ssn[10]; // nul terminated so we can use str* functions 
   char name[100];
   float GPA;
   ...
} student;
student slist[MAX_STUDENTS];

这是你去的时候填写的。它没有顺序，因此对任何键的搜索都是线性时间操作。1,000 个条目不是问题，但可能是 10,000 个问题，当然还有 100 万个问题。请参阅dirkgently 的评论。

如果我们希望能够快速搜索，我们需要另一层结构。我在键和主要数据结构之间构建了一个映射，如下所示：

typedef
struct str_map {
   char* key;
   student *data;
} smap;
smap skey[MAX_STUDENTS]

并保持 skey在键上排序，以便我可以快速查找。（只有数组很难保持排序，所以我们可能更喜欢树或哈希图。）

如果您只想在单个字段上进行快速搜索，则不需要（当然应该避免）这种复杂性。

于 2009-03-22T04:18:01.777 回答