c-结构的效率

Question

我有以下结构

struct scoreentry_node {
    struct scoreentry_node *next;
    int score;
    int max;
    char name[1];    
}
;
typedef struct scoreentry_node *score_entry;

我有一个函数add，它构建了我的结构：

int max(int a, int b) {    
   if (a > b) return a;
   return b;
}
score_entry add(int in, char* n, score_entry en) {      
   score_entry r = malloc(sizeof(struct scoreentry_node) + strlen(n))
   if (en == NULL){ r->max = in; }
   else {  r->max = max(in, en->max); }
   r->score = in;
   strcpy(r->name, n);
   r->next = en;  
   return r;   
}

我有以下功能，它扫描我的结构，搜索一个名字，并产生该名字的最高分数：

int maxiscore(score_entry a, char* name)
{    
 int highestscore = -1000000000;    
   for (a; a != NULL; a = a->next)
    {
      if (strcmp(a->name, name) == 0 && a->score > highestscore)
        {
          highestscore = a->score;                
       }
     }
 return highestscore;
} 

我想知道我是否可以让我的maxiscore函数在O（1）中运行[不必扫描我的结构]？我想在我的结构中添加另一个字段，但我必须考虑它需要根据特定的输入名称而变化。有什么建议/提示吗？

Answer 1

正如一些评论者所指出的，这基本上是一个算法/数据组织问题。

您可以花时间创建"有组织的"数据结构，例如每个用户的得分表、哈希、平衡树等等；或者，您可以花时间搜索"杂乱无章"的数据结构。甚至还有混合方法：使它们"无组织"，然后根据需要动态组织（例如，展开树）。

如果你已经有了关于你将"做得最多"的信息，你现在可以进行优化。否则，如果您希望以后能够进行优化，请决定您需要什么样的功能，并提供特定的功能来"做每件事"（添加一个带有一组分数的名称？添加一个具有一个分数的名称吗？查找特定名称的所有分数吗？查找N个最高分数吗？找到特定名称的N个最高得分吗？前面的任何/全部？等等）。一旦一切正常，就可以使用评测来找出时间的去向，然后选择如何组织通过这些函数访问的数据。

事实上，我认为你的问题开始时有点"太低了"，即"我已经有了这套特定的指甲，所以我应该用哪把锤子"，而螺丝或胶水可能会更好。：-）

Answer 2

您可以将一组结构封装在scorelist类中，该类包含指向第一个元素的score_entry指针和包含条目中的最大得分（以及指向相关元素的指针）。您可以更新add()上的biggets分数并重写指针。您将能够访问在O（1）中得分最高的元素。